Page 15 - 4719
P. 15
5. Всі елементи ведучої стрічки (крім a ij) множать на λ і
результат записують у нижню частину кліток.
6. Всі елементи ведучого стовпчика (крім a ij) множать на
”– λ” і результат записується у нижню частину кліток.
7. У ведучій стрічці обводять всі верхні елементи, крім
a ij, а у ведучому стовпчику всі нижні.
8. Для всіх інших елементів таблиці внизу клітинок
записують добуток обведених елементів у відповідних
ведучих стрічках і стовпчиках.
9. Переписують таблицю, замінивши базову і вільну
змінні місцями; елементи ведучих стрічок і стовпчиків –
числами, які стояли внизу клітинок; для інших клітинок –
сумою верхніх і нижніх елементів.
10. Якщо у стрічці z немає додатних елементів, то
отримано оптимальний розв’язок, інакше переходять до кроку
2.
Штучний початковий розв’язок
У симплексному методі для отримання початкового
базового розв’язання використовувалось залишкові змінні.
Однак, коли вихідне обмеження записане як рівність, або має
знак ≥, не можна відразу отримати допустимий початковий
базовий розв’язок. Для розв’язання задачі в цьому випадку
застосовують штучні змінні. Ідея застосування штучних
змінних досить проста. Вона припускає включення додатних
змінних у ліву частину кожного із рівнянь, які не містять
„очевидних” початкових базових змінних. Однак, введення
штучних змінних допустиме тільки в тому випадку, коли
алгоритм отримання оптимального розв’язку забезпечує
рівність нулю штучних змінних в оптимальному розв’язку.
Розроблено два методи отримання стартової точки за
допомогою штучних змінних.
Задача 3.1 Аналітично за допомогою симплекс методу
розв’язати задачу лінійного програмування. Знайти максимум
цільової функції:
Z = 3X + 5X
1
2
при обмеженнях:
14