імуму цільової функції.
Із загальної теорії разрешимости задач ЛП нам відомо, що одним з рішень такого завдання є вершина багатогранника допустимих значень. Тому ми можемо знайти рішення шляхом перебору всіх вершин, обчислюючи там цільову функцію і вибираючи ту вершину, де її значення мінімально. Але при великому числі змінних і обмежень число вершин такого многогранника величезна, і перебір всіх вершин призводить до великого обсягу обчислень. Бажано організувати цей перебір так, щоб не розглядати вершини, де значення цільової функції свідомо більше, ніж у вже розглянутих вершинах. Одним із способів такого раціонального перебору вершин є так званий симплекс-метод.
Симплекс розмірності n - це найпростіший багатогранник цієї розмірності. Так, 2-симплекс - це будь трикутник, 3-симплекс - це будь тетраедр і т. П. Слово симплекс означає «найпростіший».
Ідея симплекс-методу така. Знайдемо якусь одну (початкову) вершину багатогранника допустимих значень. Будемо перебирати всі ребра, що виходять з цієї вершини, поки не знайдемо ребра, при переміщенні уздовж якого цільова функція спадає. Якщо такого ребра немає, то початкова вершина є точка мінімуму. Якщо ж ребро із зазначеним властивістю знайдеться, то ми переходимо уздовж цього ребра до наступної вершини, і починаємо перебір ребер, що виходять з неї.
Таким чином, ми рухаємося по ребрах багатогранника, щоразу переходячи до вершини з меншим значенням цільової функції, поки не прибудемо в точку її мінімуму.
Опишемо чисельну реалізацію цієї ідеї для задачі ЛП в канонічній формі.
Відзначимо, що серед обмежень (7.9) можуть бути взаємозалежні (скажімо, одне з рівностей дорівнює сумі двох інших). Обмеження, що є наслідками інших обмежень, необхідно відкинути, оскільки вони не містять ніякої додаткової інформації про значення невідомих. Нехай після такого відкидання залишилося m обмежень типу рівностей:
a11x1 + a12x2 + ... + a1nxn=b1x1 + a22x2 + ... + a2nxn=b2 (7.11)
............
am1x1 + am2x2 + ... + amnxn=bm
Тут n - це загальне число невідомих, включаючи додаткові (балансові) змінні. Коефіцієнти aij, bj - задані числа (але, взагалі кажучи, нові, отримані після приве?? ення до канонічного виду і відкидання залежних рівнянь). Оскільки будь-яка система з m gt; n лінійних рівнянь з n невідомими, або залежна, або несумісна, то ми повинні вважати, що m lt; n. Випадок m=n не відноситься до теорії оптимізації: в цьому випадку рішення системи (7.11) єдино, т. Е. Багатогранник допустимих значень складається з єдиної точки, проблеми вибору між різними точками цього багатогранника не варто.
Тому ми повинні розглядати лише випадок m lt; n.
Алгоритм симплексного методу складається з наступних п'яти кроків: 1. Висловимо першого m змінних x1, x2, x3, ..., xm через інші за допомогою рівнянь (7.11):
x1=p1 + q1, m + 1 xm + 1 + q1, m + 2 xm + 2 + ... + q1n xn=p2 + q2, m + 1 xm + 1 + q2, m +2 xm + 2 + ... + q2n xn (7.12)
................=pm + qm, m + 1xm + 1 + qm, m + 2xm + 2 + ... + qmnxn.
Для цього досить вирішити систему (7.11) щодо невідомих x1, x2, x3, ..., xm, вважаючи змінні xm + 1, xm + 2, ..., xn фіксованими.
Вільні члени p1, p2, ..., pm невід'ємні. Змінні x1, x2, x3, ..., xm називають базисними (залежними), а xm + 1, xm + 2, ..., xn- небазисними (вільними). ??
Представлення (7.12) дозволяє визначити вихідну вершину (опорне рішення). Для цього достатньо покласти xm + 1=xm + 2=...=xn=0 і обчислити змінні x1, x2, x3, ..., xm за формулами (7.12). Тим самим ми знаходимо одне з невід'ємних базисних рішень: (p1, p2, ..., pm, 0, ..., 0).
. Крім того, ми можемо підставити праві частини (7.12) у вираз цільової функції замість x1, x2, x3, ..., xm, і отримати її вираження через вільні змінні:
F=d0 + dm + 1 · xm + 1 + ... + dn · xn. (7.13)
Оскільки в початковій вершині xm + 1=...=xn=0, то функція F приймає в цій вершині значення d0.
З'ясуємо, чи не є початкова вершина оптимальної, тобто не дає вона рішення задачі мінімізації F. Вона є точкою мінімуму, якщо при будь-якій зміні вільних змінних значення F тільки збільшується. Оскільки xj? 0, то це відбудеться за умови dj? 0, j=m + 1, ..., n.
Отже, якщо всі коефіцієнти при вільних невідомих у поданні (7.13) невід'ємні, то точка мінімуму вже знайдена.
. Припустимо, що це не так, і серед цих коефіцієнтів є негативні коефіцієнти. Нехай для конкретності dm + 1 lt; 0. Тоді, при збільшенні xm + 1 з...
