Page 25 - 4168

8. Для всіх інших елементів таблиці внизу клітинок запи-
сати добуток обведених елементів у відповідних ведучих стрі-
чках і стовпчиках.
9. Переписати таблицю, замінивши базову і вільну змінні
місцями; елементи ведучих стрічок і стовпчиків – числами, які
стояли внизу клітинок; для інших клітинок – сумою верхніх і
нижніх елементів.
10. Якщо у стрічці z немає додатніх елементів, то маємо
оптимальний розв’язок, інакше крок 1.
Штучний початковий розв’язок
В симплексному методі для отримання початкового базо-
вого розв’язання використовувалось залишкові змінні. Однак,
коли вихідне обмеження записане як рівність, або має знак ≥,
не можна відразу отримати допустимий початковий базовий
розв’язок. Для розв’язання задачі в цьому випадку застосову-
ють штучні змінні. Ідея застосування штучних змінних досить
проста. Вона припускає включення додатних змінних в ліву
частину кожного із рівнянь, які не містять „очевидних” почат-
кових базових змінних. Однак, введення штучних змінних до-
пустиме тільки в тому випадку, коли алгоритм отримання оп-
тимального розв’язку забезпечує рівність нулю штучних змін-
них в оптимальному розв’язку.
Розроблено два методи отримання стартової точки за до-
помогою штучних змінних.
М-метод, або метод великих штрафів
Алгоритм розв’язку:
1. Зводимо задачу до стандартного вигляду.
2. До лівої частини обмежень виду =, або ≥ додаємо шту-
чні змінні R i.
3. Цільову функцію переписуємо як
max z=c 1x 1+c 2x 2+…+c nx n-MR 1-MR 2-…,
де, М– достатньо великий коефіцієнт.
4. Із обмежень виражаємо змінні R i через інші змінні:
R 1=b 1-a 11x 1-a 12x 2…
R 2=b 2-a 21x 1-a 22x 2…
………………........
5. Підставляємо ці вирази у цільову функцію замість R i і
перегруповуємо доданки відносно основних змінних. Таким
чином при x i=0 z=-kM (досить мале).

25