Стандартна задача лінійного програмування (стр. 7 из 8)
2. Якщо при переході у симплекс-методі від одного опорного плану задачі до іншого в напрямному стовпчику немає додатних елементів
, тобто неможливо вибрати змінну, яка має бути виведена з базису, то це означає, що цільова функція задачі лінійного програмування є необмеженою й оптимальних планів не існує.3. Якщо для опорного плану задачі лінійного програмування всі оцінки
задовольняють умову оптимальності, але при цьому хоча б одна штучна змінна є базисною і має додатне значення, то це означає, що система обмежень задачі несумісна й оптимальних планів такої задачі не існує.Навчальні завдання розв'язування задач симплекс-методом
Розглянемо застосування симплекс-методу для розв'язування деяких задач лінійного програмування.
Задача 2.41.
Продукція чотирьох видів А, В, С і Д проходить послідовну обробку на двох верстатах. Тривалість обробки одиниці продукції кожного виду задано таблицею.
| Верстат | Тривалість обробки, год, одиниці продукції | |||
| А | В | С | Д | |
| 1 2 | 2 3 | 3 2 | 4 1 | 2 2 |
Витрати на виробництво одиниці продукції кожного виду визначають як величини, прямо пропорційні до часу використання верстатів (у машино-годинах). Вартість однієї машино-год становить 10 дол. для верстата 1 і 15 дол. — для верстата 2. Можливий час використання верстатів обмежений: для верстата 1 він становить 450 машино-год, а для верстата 2 — 380 машино-год.
Ціна одиниці продукції кожного виду дорівнює відповідно 73, 70, 55 та 45 дол.
Визначити оптимальний план виробництва продукції всіх чотирьох видів, який максимізує загальний чистий прибуток.
Побудова математичної моделі. Нехай
— план виробництва продукціїу-го виду, де у може набувати значень від 1 до 4.Умовами задачі будуть обмеження на час використання верстатів для виробництва продукції всіх видів:
для верстата 1
(машино-год);для верстата 2
(машино-год).Цільова функція задачі визначається як загальний чистий прибуток від реалізації готової продукції і складається з різниці між ціною та собівартістю виготовлення продукції кожного виду:
Отже, математична модель поставленої задачі має такий вигляд:
Розв'язування. Розв'яжемо задачу симплекс-методом згідно з розглянутим алгоритмом.
1. Запишемо систему обмежень задачі в канонічному вигляді. Для цього перейдемо від обмежень-нерівностей до строгих рівнянь, увівши до лівої частини обмежень додаткові змінні х5 та х6.
Ці додаткові змінні за економічним змістом означають можливий, але не використаний для виробництва продукції час роботи верстатів 1 та 2. У цільовій функції Z додаткові змінні мають коефіцієнти, які дорівнюють нулю:
Канонічну систему обмежень задачі запишемо у векторній формі: >і
де
Оскільки вектори
та 
одиничні та лінійно незалежні, саме з них складається початковий базис у зазначеній системі векторів. Змінні задачі 
та 
, що відповідають одиничним базисним векторам, називають базисними, а решту вільними змінними задачі лінійного програмування. Прирівнюючи вільні змінні до нуля, з кожного обмеження задачі дістаємо значення базисних змінних: 
Згідно з визначеними
векторна форма запису системи обмежень задач матиме вигляд 
Оскільки додатні коефіцієнти х5 та х6 відповідають лінійно незалежним векторам, то за означенням
є опорним планом задачі і для цього початкового плану
2. Складемо симплексну таблицю для першого опорного плану задачі.
Елементи останнього рядка симплекс-таблиці є оцінками Δj, за допомогою яких опорний план перевіряють на оптимальність. їх визначають так:
У стовпчику «План» оцінкового рядка записують значення цільової функції Z, якого вона набуває для визначеного опорного плану:
=0-450 + 0-380 = 0.3. Після обчислення всіх оцінок опорний план перевіряють на оптимальність. Для цього продивляються елементи оцінкового рядка. Якщо всі
(для задачі на max) або 
(для задачі на min), визначений опорний план є оптимальним. Якщо ж в оцінковому рядку присутня хоча б одна оцінка, що не задовольняє умову оптималь-ності (від'ємна в задачі на max або додатна в задачі на min), то опорний план є неоптимальним і його можна поліпшити.У цій задачі в оцінковому рядку дві оцінки
та 
суперечать умові оптимальності, і тому перший визначений опорний план є неоптимальним. За алгоритмом симплекс-методу необхідно від нього перейти до іншого опорного плану задачі.4. Перехід від одного опорного плану до іншого виконують зміною базису, тобто за рахунок виключення з поточного базису якоїсь змінної та включення замість неї нової з числа вільних змінних.
Для введення до нового базису беремо змінну
, оскільки їй відповідає найбільша за абсолютною величиною оцінка серед тих, які не задовольняють умову оптимальності ( 
).Щоб визначити змінну, яка підлягає виключенню з поточного базису, для всіх додатних елементів стовпчика «х2» знаходимо відношення
і вибираємо найменше значення. Згідно з даними симплексної таблиці бачимо, що min 
, і тому з базису виключаємо змінну 
, а число 
= 3 називатимемо розв'язувальним елементом. Подальший перехід до нового опорного плану задачі полягає в побудові наступної симплексної таблиці, елементи якої розраховують за методом Жордана—Гаусса.Друга симплексна таблиця має такий вигляд:
У цій таблиці спочатку заповнюють два перших стовпчики «Базис» і «
», а решту елементів нової таблиці розраховують за розглянутими далі правилами:1. Розв'язувальний (напрямний) рядок необхідно поділити на розв'язувальний елемент і здобуті числа записати у відповідний рядок нової симплексної таблиці.
2. Розв'язувальний стовпчик у новій таблиці записують як одиничний з одиницею замість розв'язувального елемента.
3. Якщо в напрямному рядку є нульовий елемент, то відповідний стовпчик переписують у нову симплексну таблицю без змін.
4. Якщо в напрямному стовпчику є нульовий елемент, то відповідний рядок переписують у нову таблицю без змін.
Усі інші елементи наступної симплексної таблиці розраховують за правилом прямокутника.
Щоб визначити будь-який елемент нової таблиці за цим правилом, необхідно в попередній симплексній таблиці скласти умовний прямокутник, вершини якого утворюються такими числами:;
1 — розв'язувальний елемент;
2 — число, що стоїть на місці елемента нової симплексної таблиці, який ми маємо розрахувати;
3 та 4 — елементи, що розміщуються в двох інших протилежних вершинах умовного прямокутника.
Необхідний елемент нової симплекс-таблиці визначають так:
