Page 26 - 4168

6. Складається самплекс-таблиця і шукається розв’язок,
включивши в число базових змінні R i.
Двоетапний розв’язок
Недолік М-методу пов’язаний з можливістю помилок у
розрахунках, оскільки коефіцієнт М значний за величиною.
Двоетапний метод дозволяє уникнути цих труднощів.
При використані двоетапного методу штучні змінні вводять
таким же чином, як і у М-методі. Однак коефіцієнт М при цьо-
му не фігурує, що досягається розчленуванням процесу
розв’язання задачі на два етапи.
Алгоритм розв’язку:
Етап 1. Вводять штучні змінні, що необхідні для отри-
мання стартової точки. Записують нову цільову функцію, яка
передбачає мінімізацію суми штучних змінних при вихідних
обмеженнях, видозмінених за рахунок введення штучних змін-
них. Якщо мінімальне значення нової цільової функції дорів-
нює нулю, вихідна задача має допустимий розв’язок. Перехо-
дять до етапу 2. У протилежному випадку, коли мінімум нової
цільової функції буде більшим від нуля, вихідна задача не має
допустимого розв’язку і процес обчислення закінчується.
Етап 2. Оптимальний базовий розв’язок, що отриманий
на етапі 1, використовують як початкове розв’язання вихідної
задачі.
Транспортна задача
Транспортна задача формулюється наступним чином. За-
дано m пунктів виробництва однорідного продукту та п пунк-
тів його споживання. Задані обсяги виробництва а і кожного
пункту виробництва і обсяги споживання b j кожного пункту
споживання. Вартість перевезень одиниці продукції з і-го пун-
кту виробництва до j-го пункту споживання становить c ij, а ві-
дповідна кількість продукту, що перевозитьсядорівнює x ij
(i=1,2,…,m; j=1,2,…,n). Необхідно скласти оптимальний план
перевезень.
План буде оптимальний при мінімумі транспортних
втрат, тобто цільова функція тут має вигляд
m n
c
min ∑ ∑ ij ⋅ x ij
= i 1 = j 1
при обмеженнях

26