Загальний підхід - при вирішенні лінійних оптимізаційних задач
Стандартна задача ЛП має вигляд
при
Розглянемо різні випадки линейної оптимізаційної задачі ЛОЗ
1. F= 2. F= 3. F= (*)
випадок 1 випадок 2 випадок 3
Випадок 1 - без обмежень – зрозуміло що F , потрібно тільки вибрати рух по градієнту.
Далі наведемо Фундаментальне твердження (більш строго сформулюємо пізніше):
При лінійній опуклій області рішень і лінійному функціонал оптимум знаходитися не в середині області і не на її межі, а саме в вершині симплекса (сімлекс - так називають таку лінійну опуклу область допустимих рішень)
Тому у випадку 2. можна шукати оптимум навіть тупо методом перебору обчислюючи значення ф-ла в кожній вершині.
А ось у випадку 3. - вершин може бути так багато що перебором можна займатися нескінченно - !!! – ось тепер розкажімо про ідеї підходу - симплекс-методу (Данцига).
Він складається з 2-етапів:
далі розмірковуємо в термінах стандартної задачі, тобто область ДР вирізається з початкового простору Х нерівностями типу " "
Этап 1.
1 а. Оскількі ми знаємо, що оптимальне рішення знаходиться в вершині області ДР, то на початку виходимо на довільну вершину, нехай навіть неприпустиму - рис 3.1
1б. Включаємо деякий механізм-процедуру пошуку вершини, але яка вже належить ОДР - тобто допустиму вершину симплекса
Етап 2. Далі слід спрямований перебір: з поточної вершини переходимо в ту сусідню, в якій отримуємо максимальний приріст функціоналу серед інших сусідніх, зберігаючи при цьому перебування в ОДР.
Йдемо по сімлексу використовуючи даний принцип, поки не досягнемо вершини, де значення ф-ла у всіх сусідів буде менше, ніж в поточному - ми досягли глобального максімума.
Відмітимо еше раз - такий висновок справедливий лише при лінійній опуклій області і лінійніх обмеженнях. Інакше, це може бути локальний максимум а не глобальний
Достарыңызбен бөлісу: |
