Page 12 - 100

Алгоритм розв’язку:
1. Зводимо задачу до стандартного вигляду.
2. До лівої частини обмежень виду =, або ≥ додаємо штучні змінні R i.
3. Цільову функцію переписуємо як
max z=c 1x 1+c 2x 2+…+c nx n-MR 1-MR 2-…
де, М– достатньо великий коефіцієнт.
4. Із обмежень виражаємо змінні R i через інші змінні:
R 1=b 1-a 11x 1-a 12x 2…
R 2=b 2-a 21x 1-a 22x 2…
………………........
5. Підставляємо ці вирази у цільову функцію замість R i і перегруповуємо до-
данки відносно основних змінних. Таким чином при x i=0 z=-kM (досить мале).
6. Складається самплекс-таблиця і шукається розв’язок, включивши в число
базових змінні R i.

2.7 Двоетапний розв’язок
Недолік М-методу пов’язаний з можливістю помилок у розрахунках,
оскільки коефіцієнт М значний за величиною.
Двоетапний метод дозволяє уникнути цих труднощів. При використані
двоетапного методу штучні змінні вводять таким же чином, як і у М-методі.
Однак коефіцієнт М при цьому не фігурує, що досягається розчленуванням
процесу розв’язання задачі на два етапи.
Алгоритм розв’язку:
Етап 1. Вводять штучні змінні, що необхідні для отримання стартової
точки. Записують нову цільову функцію, яка передбачає мінімізацію суми
штучних змінних при вихідних обмеженнях, видозмінених за рахунок вве-
дення штучних змінних. Якщо мінімальне значення нової цільової функції
дорівнює нулю, вихідна задача має допустимий розв’язок. Переходять до
етапу 2. У протилежному випадку, коли мінімум нової цільової функції буде
більшим від нуля, вихідна задача не має допустимого розв’язку і процес об-
числення закінчується.
Етап 2. Оптимальний базовий розв’язок, що отриманий на етапі 1, ви-
користовують як початкове розв’язання вихідної задачі.

5. Транспортна задача.
Транспортна задача формулюється наступним чином. Задано m пунктів
виробництва однорідного продукту та п пунктів його споживання. Задані об-
сяги виробництва а і кожного пункту виробництва і обсяги споживання b j ко-
жного пункту споживання. Вартість перевезень одиниці продукції з і-го пунк-
ту виробництва до j-го пункту споживання становить c ij, а відповідна кіль-
кість продукту, що перевозитьсядорівнює x ij (i=1,2,…,m; j=1,2,…,n). Необхід-
но скласти оптимальний план перевезень.
План буде оптимальний при мінімумі транспортних втрат, тобто цільо-
ва функція тут має вигляд

12