НЕЛІНІЙНЕ ПРОГРАМУВАННЯ. ЗАДАЧІ ДРОБОВО-ЛІНІЙНОГО ПРОГРАМУВАННЯ. Звіт до лабораторної роботи з Математичні методи дослідження операцій. Робота № 527416

НЕЛІНІЙНЕ ПРОГРАМУВАННЯ. ЗАДАЧІ ДРОБОВО-ЛІНІЙНОГО ПРОГРАМУВАННЯ

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

АСУ

Інформація про роботу

Рік:

2015

Тип роботи:

Звіт до лабораторної роботи

Предмет:

Математичні методи дослідження операцій

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти і науки, молоді та спорту України Національний Університет «Львівська Політехніка» кафедра АСУ Звіт до лабораторної роботи №9 на тему: «НЕЛІНІЙНЕ ПРОГРАМУВАННЯ. ЗАДАЧІ ДРОБОВО-ЛІНІЙНОГО ПРОГРАМУВАННЯ» з дисципліни: «Математичні методи дослідження операцій» Лабораторна робота №9 «НЕЛІНІЙНЕ ПРОГРАМУВАННЯ. ЗАДАЧІ ДРОБОВО-ЛІНІЙНОГО ПРОГРАМУВАННЯ» Короткі теоретичні відомості Геометрична інтерпретація задачі дробово-лінійного програмування У разі, коли задача дробово-лінійного програмування містить лише дві змінні, для її розв’язування зручно скористатися графічним методом. Нехай маємо таку задачу: / (1.4) за умов: / (1.5) /, / (1.6) Спочатку, як і для звичайної задачі лінійного програмування будуємо геометричне місце точок системи нерівностей (1.5), що визначає деякий багатокутник допустимих розв’язків. Допустимо, що /, і цільова функція набуває деякого значення: /. Після елементарних перетворень дістанемо: / або /. (1.7) Останнє рівняння описує пряму, що обертається навколо початку системи координат залежно від зміни значень х1 та х2. Розглянемо кутовий коефіцієнт нахилу прямої (1.7), що виражає цільову функцію: /. (1.8) Отже, кутовий коефіцієнт є функцію від Z. Для визначення умов зростання (спадання) функції (1.8) дослідимо зміну знака її похідної: /(1.9) Використовуючи формулу (1.9), можна встановити правила пошуку максимального (мінімального) значення цільової функції: а) якщо /, то функція (1.8) є зростаючою, і при збільшенні значення Z (значення цільової функції) кутовий коефіцієнт нахилу прямої (1.7) також збільшується. Тому у разі, якщо /, то для відшукання точки максимуму необхідно повертати пряму, що описує цільову функцію, навколо початку системи координат у напрямку проти годинникової стрілки; б) якщо /, то функція (1.8) є спадною, і при збільшенні значення Z (значення цільової функції) кутовий коефіцієнт нахилу прямої (1.7) зменшується. Тому у разі, якщо /, то для відшукання точки максимуму необхідно повертати пряму, що описує цільову функцію, навколо початку системи координат у напрямку за годинниковою стрілкою. При розв’язуванні задачі дробово-лінійного програмування графічним методом можливі такі випадки: - багатокутник розв’язків задачі обмежений, - і максимальне та мінімальне значення досягаються у його кутових точках; - багатокутник розв’язків задачі необмежений, - однак існують кутові точки, в яких досягаються максимальне та мінімальне значення цільової функції; - багатокутник розв’язків задачі необмежений, - і досягається лише один із екстремумів; - багатокутник розв’язків задачі необмежений, - і точки екстремумів визначити неможливо. Приклад 1.1 Розв’яжемо графічно задачу дробово-лінійного програмування: / за умов: / /. Розв’язання. Побудуємо на площині область допустимих розв’язків задачі. Маємо трикутник АВС. / Рис. 1.1 Цільова функція задачі - це пряма, що обертається навколо початку системи координат (на рис. 1.1 позначена пунктиром). Отже, залежно від напрямку обертання точками максимуму та мінімуму будуть відповідно точки А і С. Скористаємося правилами визначення максимального та мінімального значень цільової функції. Перевіримо умову /, тобто для будь-якого значення Z функція / є спадною. Отже, зі зростанням Z кутовий коефіцієнт нахилу прямої, що виражає цільову функцію, зменшуватиметься, а тому відповідну пряму потрібно обертати навколо початку координат за годинниковою стрілкою. Виконуючи зазначений порядок дій, маємо: С — точка максимуму, а точка А є точкою мінімуму цієї задачі. Розв’язування дробово-лінійної задачі зведенням до задачі лінійного програмування Нехай потрібно розв’язати задачу (1.1)—(1.3). Позначимо / і введемо заміну змінних /. Тоді цільова функція (1.1) матиме вигляд: /. Отримали цільову функцію, що виражена лінійною залежністю. Оскільки /, то звідси маємо: /. Підставимо виражені через нові змінні значення /в систему обмежень (1.2): / / Крім того, з початкової умови /. Умова (1.3) стосовно невід’ємності змінних набуває вигляду: /. Виконані перетворення приводять до такої моделі задачі: / , / , / Отримали звичайну задачу лінійного програмування, яку можна розв’язувати симплексним методом. Допустимо, що оптимальний розв’язок останньої задачі існує і позначається: /. Тоді оптимальні значення початкової задачі (1.1) — (1.3) визначають за формулою: / /.

Звіт до лабораторної роботи Математичні методи дослідження операцій

Edited

06.12.2015 15:25

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись