Page 11 - 100

Пошук оптимального розв’язку виконується шляхом обміну базових і
вільних змінних.

Алгоритм симплекс-методу:
1. Початковий розв’язок отримується шляхом прирівнювання до 0 n-m (базо-
вих) змінних.
2. Виділити ведучий стовпчик за найбільшим із додатніх коефіцієнтів с i 1-ї
стрічки (z).
3. Виділяється ведучий рядок, який відповідає найменшому додатному зна-
b
ченню i , a ij ≥ 0. з ведучого стовпчика.
a
ij
1
4. Визначається ведучий елемент a ij і визначається   , яке записується в
a
ij
нижній половині цієї клітинки.
5. Всі елементи ведучої стрічки (крім a ij) множаться на λ і результат запису-
ється у нижню частину кліток.
6. Всі елементи ведучого стовпчика (крім a ij) множиться на – λ і результат за-
писується у нижню частину кліток.
7. У ведучій стрічці обвести всі верхні елементи, крім a ij, а у ведучому стовп-
чику всі нижні.
8. Для всіх інших елементів таблиці внизу клітинок записати добуток обведе-
них елементів у відповідних ведучих стрічках і стовпчиках.
9. Переписати таблицю, замінивши базову і вільну змінні місцями; елементи
ведучих стрічок і стовпчиків – числами, які стояли внизу клітинок; для інших
клітинок – сумою верхніх і нижніх елементів.
10. Якщо у стрічці z немає додатніх елементів, то маємо оптимальний
розв’язок, інакше крок 1.

2.5 Штучний початковий розв’язок
В симплексному методі для отримання початкового базового
розв’язання використовувалось залишкові змінні. Однак, коли вихідне обме-
ження записане як рівність, або має знак ≥, не можна відразу отримати допус-
тимий початковий базовий розв’язок. Для розв’язання задачі в цьому випад-
ку застосовують штучні змінні. Ідея застосування штучних змінних досить
проста. Вона припускає включення додатних змінних в ліву частину кожного
із рівнянь, які не містять „очевидних” початкових базових змінних. Однак,
введення штучних змінних допустиме тільки в тому випадку, коли алгоритм
отримання оптимального розв’язку забезпечує рівність нулю штучних змін-
них в оптимальному розв’язку.
Розроблено два методи отримання стартової точки за допомогою штуч-
них змінних.

2.6 М-метод, або метод великих штрафів

11