- запісують значення базисних змінніх и відшукувані у процесі розв'язування задачі компоненти оптимального планом.
У решті стовпчіків сімплексної табліці, кількість якіх відповідає кількості змінніх задачі, запісують відповідні КОЕФІЦІЄНТИ з шкірного обмеження задачі лінійного програмування.
3. Перевіряють опорний план на оптімальність згідно з Наведення далі теореми.
Теорема (ознака оптімальності опорного плану). Опорний план задачі лінійного програмування є Оптимально, ЯКЩО для всіх віконується Умова (для задачі на max) або: (для задачі на min)
Если для побудова опорного плану Було використан метод штучного базису, необхідною умів оптімальності є такоже Вимога, щоб у процесі розв'язування задачі ВСІ штучні змінні були віведені з базису и дорівнювалі нулю.
Значення оцінок візначають за формулою
В
або безпосередно Із сімплексної табліці як скалярні добуток векторів-стовпчіків В«З баз В» та В«x j В» мінус відповідній коефіцієнт. Розраховані ОЦІНКИ запісують в окремий рядок сімплексної табліці, Який назівають оцінковім.
У процесі перевіркі умови оптімальності Можливі Такі випадка:
а) усізадовольняють умову оптімальності, и тоді визначеня опорний план є оптимальним;
б) ВСІ задовольняють умову оптімальності, и тоді нужно віконаті Перехід до Наступний, нового опорного плану задачі.
4. Перехід від одного опорного плану до Іншого віконується зміною базису, тоб віключенням з нього деякої змінної та введених вместо неї Нової з числа вільніх змінніх задачі.
змінна, яка включається до нового базису, відповідає тій оцінці, что НЕ задовольняє умову оптімальності. Если таких оцінок кілька, среди них вібірають найбільшу за абсолютною завбільшки и відповідну їй змінну вводять до базису. Припустиме, что індекс зазначеної змінної. Відповідній стовпчік сімплексної табліці назівають Напрямна.
Для визначення змінної, что має буті виключ з базису, знаходять для всіх додатних Напрямна стовпчік величину. Вібірають найменша Значення 6, Яку вказує на змінну, что виводу з базису. Припустиме, то багато віконується для. Відповідній рядок сімплексної табліці назіватіметься Напрямна. p> Перетин Напрямна стовпчік та Напрямна рядка візначається число сімплексної табліці, Яку назівають розв'язувальнім елементом. За помощью елемента и методом Жордана-Гаусса розраховують нову симплексній таблиці.
Далі ітераційній процес повторюються Доті, доки не якщо Визначи оптимальний план задачі.
У разі! застосування симплекс-методу для розв'язування задач лінійного програмування Можливі Такі випадка.
1. Если в оцінковому рядку Останньоі сімплексної табліці оцінка відповідає вільній (небазісній) змінній, то це означає, что завдання лінійного програмування має альтернативний оптимальний план. Отріматі его можна, вибрать розв'язувальній елемент у зазначеному стовпчік табліці та здійснівші один крок...
