ькість сировини 1-ого виду.
Перетворену систему рівнянь запишемо у векторній формі:
3. Визначення опорного плану
При вирішенні завдання симплексним методом опорний план можна безпосередньо записати, користуючись векторної формою запису завдання. Система одиничних векторів утворює базис. В опорному плані базисні змінні дорівнюють нулю, а інші дорівнюють відповідним вільним членам bj системи рівнянь. У прикладі первісний опорний план дорівнює x 0=(0,0,0,0,0,990,620,510,390,900). Складемо перше симплексну таблицю. У прикладі ця таблиця має вигляд:
Таблиця 3
IБАЗІСC б P012141728700000P1P2P3P4P5P6P7P8P9P101P6099010121157100002P7062068234010003P8051045639001004P9039012543000105P100900126512000016F 0=0-12-14-17-28-700000
Виходячи з таблиці робимо висновок, чи є знайдений опорний план оптимальним. У прикладі план x 0 оптимальним не є. Це видно з 6-го рядка таблиці, оскільки в ній є п'ять негативних числа: z 1 - c 1=- 12, z 2 - c 2=- 14, z 3 - c 3=- 17, z 4 - c 4 =- 28, z 5 - c 5=- 7. Негативні числа не тільки свідчать про можливість збільшення загальної вартості виробленої продукції, але і показують, наскільки збільшиться ця сума при введенні в план одиниці того чи іншого виду продукції.
Якщо в основній формі завдання лінійного програмування немає m одиничних векторів серед P j, то складається розширена задача. За допомогою звичайних обчислень симплекс - методу виключають штучні вектори з базису. Отриманий після виключення штучних векторів план і є опорним планом вихідної задачі.
4. Визначення оптимального плану
При вирішенні завдання симплексним методом оптимальний план задачі визначається в наступній послідовності:
1. Якщо початковий план не є оптимальним, то вивчити можливість покращення оптимального плану. Якщо така можливість є, тобто є хоча б одне негативне число? j, то скласти 2-ю симплекс - таблицю або встановити нерозв'язність завдання.
2. Знайти напрямні стовпець і рядок. Направляючий стовпець визначається найбільшою за абсолютною величиною негативним числом? j, а напрямна рядок - мінімальним з відносин компонент стовпця вектора P 0 до позитивних компонентам направляючого стовпця.
3. За формулами (7) - (10) визначити позитивні компоненти нового опорного плану, коефіцієнти розкладання векторів P j по векторах нового базису і числа F 0,? j. Всі ці числа записати в новій симплекс - таблиці.
b0=(7)
aij=(8)
F 0=F 0 - (b r / a rk) *? k (9)
? j =? j - (a rj / a rk) *? k (10)
4. Перевірити знайдений опорний план на оптимальність. Якщо план не оптимальний, то необхідно скласти нову симплекс - таблицю і перейти до нового опорного плану, а в разі отримання оптимального плану або встановлення нерозв'язності завдання закінчити процес рішення.
5. Привести знайдений оптимальний план, якщо він існує, і величину функції вартості.
Для прикладу знайдемо оптимальний план. Як видно з таблиці план не оптимальний.
Таблиця 4
IБА...
