S , що гіперплоскость L (S) перетинає багатогранник хоча б в одній точці . Зауважимо, що перетинання оптимальної гіперплощини і багатогранника буде містити хоча б одну вершину, причому, їх буде більше однієї, якщо перетин містить ребро або k-мірну грань. Тому максимум функціоналу можна шукати в вершинах багатогранника. Принцип симплекс-методу полягає в тому, що вибирається одна з вершин багатогранника, після чого починається рух за його ребрах від вершини до вершини в сторону збільшення значення цільової функції. Коли перехід по ребру з поточної вершини в іншу вершину з більш високим значенням цільової функції неможливий, вважається, що оптимальне значення S знайдено.
Послідовність обчислень симплекс-методом можна розділити на два етапи:
1. знаходження нульового рішення (перша ітерація),
. послідовний перехід від однієї вершини до іншої, що веде до оптимізації значення цільової функції (проведення подальших ітерацій).
При цьому в деяких випадках нульовий рішення очевидно або його визначення не вимагає складних обчислень, наприклад, коли всі обмеження представлені нерівностями виду (2) (тоді нульовий вектор абсолютно точно є допустимим рішенням, хоча й, швидше за все , далеко не найбільш оптимальним).
Існують і інші методи пошуку оптимального набору, проте багато з них більшою чи меншою мірою спираються на симплекс-метод:
. Алгоритм Гомори - алгоритм, що використовується для вирішення цілочислових задач лінійного програмування. При отриманні нецілочисельне оптимального набору додається умова, «викреслюємо» дробову частину.
. Метод потенціалів є модифікацією симплекс-методу реш?? Ня задачі лінійного програмування стосовно до транспортної задачі, що полягає в наступному. Є якийсь однорідний вантаж, який потрібно перекласти з n складів на m заводів. Для кожного складу i відомо, скільки в ньому знаходиться вантажу a i , а для кожного заводу відома його потреба b j у вантажі. Вартість перевезення пропорційна відстані від складу до заводу (всі відстані c ij від i -го складу до j -го заводу відомі). У цій задачі потрібно скласти найбільш дешевий план перевезення.
1.6 Оптимізація нелінійних функцій (нелінійне програмування)
Нехай тепер у нас є довільна функція F (x) (вона годі й бути безперервною в початковій області визначення). Стандартна математична задача оптимізації формулюється таким чином: серед елементів x , що утворюють безлічі ? , знайти такий елемент x * , який доставляє мінімальне значення F (x *) заданої цільової функції F (x) . Якщо немає будь-яких умов і обмежень (таким чином,), то завдання зводиться до пошуку безумовного екстремуму і, відповідно, вирішення завдання оптимізації. Якщо ж є обмеження, то слід перейти до розгляду задачі на пошук умовного екстремуму.
Розгля...
