3. Після обчислення всіх оцінок опорний план перевіряють на оптимальність. Для цього продивляються елементи оцінкового рядка. Якщо всі (для задачі на max) або (для задачі на min), визначений опорний план є оптимальним. Якщо ж в оцінковому рядку присутня хоча б одна оцінка, що не задовольняє умову оптималь-ності (від'ємна в задачі на max або додатна в задачі на min), то опорний план є неоптимальним і його можна поліпшити.

У цій задачі в оцінковому рядку дві оцінки та суперечать умові оптимальності, і тому перший визначений опорний план є неоптимальним. За алгоритмом симплекс-методу необхідно від нього перейти до іншого опорного плану задачі.

Для введення до нового базису беремо змінну, оскільки їй відповідає найбільша за абсолютною величиною оцінка серед тих, які не задовольняють умову оптимальності ().

Щоб визначити змінну, яка підлягає виключенню з поточного базису, для всіх додатних елементів стовпчика «х2» знаходимо відношення і вибираємо найменше значення. Згідно з даними симплексної таблиці бачимо, що min, і тому з базису виключаємо змінну, а число= 3 називатимемо розв'язувальним елементом. Подальший перехід до нового опорного плану задачі полягає в побудові наступної симплексної таблиці, елементи якої розраховують за методом Жордана--Гаусса.

Друга симплексна таблиця має такий вигляд:

У цій таблиці спочатку заповнюють два перших стовпчики «Базис» і «», а решту елементів нової таблиці розраховують за розглянутими далі правилами:

1. Розв'язувальний (напрямний) рядок необхідно поділити на розв'язувальний елемент і здобуті числа записати у відповідний рядок нової симплексної таблиці.

Усі інші елементи наступної симплексної таблиці розраховують за правилом прямокутника.

Наприклад, визначимо елемент , який розміщується в новій таблиці в другому рядку стовпчика «Х4». Складемо умовний прямокутник:

Тоді = (3-2-2-2):3 = 2/3. Це значення записуємо в стовпчик «» другого рядка другої симплексної таблиці.

Аналогічно розраховують усі елементи нової симплексної таблиці, у тому числі елементи стовпчика «План» та оцінкового рядка. Наявність двох способів визначення оцінок опорного плану (за правилом прямокутника та за відповідною формулою) дає змогу контролювати правильність арифметичних обчислень на кожному кроці симплекс-методу.

Після заповнення нового оцінкового рядка перевіряємо виконання умови оптимальності для другого опорного плану. Цей план також неоптимальний, оскільки . Використовуючи процедуру симплекс-методу, визначаємо третій опорний план задачі, який наведено у вигляді таблиці:

В оцінковому рядку третьої симплексної таблиці немає від'ємних чисел, тобто всі і задовольняють умову оптимальності. Це означає, Що знайдено оптимальний план задачі:

Або

Отже, план виробництва продукції, що передбачає випуск 48 одиниць продукції А та 118 од. продукції В, оптимальний і дає найбільший прибуток 1564 дол. При цьому час роботи верстатів використовується повністю (х5 = х6 = 0).

Задачу можна розв'язати симплекс-методом, узявши не три симплексні таблиці, а одну, в якій послідовно записувати всі ітерації.

Розв'язати задачу 2.41 із додатковою умовою: продукція С має виготовлятися в кількості не менш як 9 одиниць.

Застосовуючи для розв'язування поставленої задачі симплекс-метод, спочатку записуємо систему обмежень у канонічній формі, а далі -- у векторній:

Серед записаних векторів є лише Два одиничні -- та , а базис у тривимірному просторі має складатися з трьох одиничних векторів. Ще один одиничний вектор можна дістати, увівши в третє обмеження з коефіцієнтом +1 штучну змінну х8 якій відповідатиме одиничний вектор

Тепер можемо розглянути розширену задачу лінійного програмування:

На відміну від додаткових змінних штучна змінна має в цільовій функції Z коефіцієнт +М (для задачі на min) або -М (для задачі на max), де М-- досить велике додатне число.

У розширеній задачі базисними змінними є x5, х6, х8, а решта змінних вільні. Початковий опорний план задачі:

Розраховуючи оцінки першого опорного плану, дістаємо z0 = 0 - 9М, Z1 - С1 = -8, Z2 - С2 = -10, Z3 - С3 = 0 - М і т. д. Як бачимо, значення оцінок складаються з двох частин, одна з яких містить М, а інша -- просто число. Тому для зручності розбиваємо оцінковий рядок на два. У перший оцінковий рядок записуємо просто число, а в другий -- число з коефіцієнтом М.

Висновок

Література