- •5. Транспортна задача лiнiйного програмування
- •5.1. Змiстовна постановка та формальна модель транспортної задачi лiнiйного програмування
- •5.2. Умова iснування розв’язку транспортної задачі лінійного програмування
- •5.3. Побудова формальної моделi транспортної задачі лінійного програмування при порушеннi умов балансу в змiстовiй постановцi
- •5.4. Векторна форма запису транспортної задачі лінійного програмування
- •5.5. Метод потенцiалiв
- •5.5.1. Загальна схема алгоритму
- •5.5.2. Методи побудови початкового допустимого базисного розв’язку
- •Крок 3.
- •5.5.4. Знаходження змінної, що виводиться з базису (побудова циклу)
- •5.5.5. Перехiд до нового допустимого базисного розв’язку
- •5.5.6. Схема методу потенціалiв
- •5.6. Приклад розв’язання транспортної задачi лiнiйного програмування
- •5.7. Приклади компенсаторних циклiв
- •5.8. Зіставлення методу потенціалів I симплекс-методу
- •Задачi для самостійної роботи
- •Контрольнi запитання
- •Завдання до контрольної роботи
- •Двоїстий симплекс-метод
- •6.1. Основні теоретичні положення
- •6.2. Схема двоїстого симплекс-методу для задачі максимізації цільової функції
- •6.3. Сфера застосування двоїстого симплекс-методу
- •6.4. Приклад застосування двоїстого симплекс-методу
- •6.5. Додавання нового обмеження
- •Завдання до самостійної роботи
- •Варіанти завдань
- •Контрольні завдання
- •Список літератури
Двоїстий симплекс-метод
6.1. Основні теоретичні положення
Нехай задана задача лінійного програмування в канонічній формі [0, 0]
cT x max; (6.1)
A x = b; (6.2)
x0. (6.3)
Задача, двоїста задачі (6.1) — (6.3), має вигляд
Задачу (6.1) — (6.3) будемо надалі називати прямою задачею.
Критерій оптимальності задачі (6.1) — (6.3) має вигляд
,
де dN — вектор відносних оцінок небазисних змінних; — вектор оцінок обмежень.
За аналогією з вектором dN введемо вектор dB: Визначаємо вектор відносних оцінок змінних таким чином:
;
.
Критерій оптимальності задачі (6.1) — (6.3) можна записати так:
;
;
. (6.4)
Співвідношення (6.4) розглядаємо як вираз допустимості вектора двоїстих змінних . Таким чином у симплекс-методі, підтримуючи допустимість прямого розв’язку, можна прагнути до допустимості двоїстого розв’язку. Такий алгоритм називається прямим. Так само можна розпочати з допустимого двоїстого розв’язку і прагнути допустимості прямого. Такий алгоритм називають двоїстим симплекс - методом.
Двоїстий симплекс-метод – це симплекс-метод, який пристосований до двоїстої задачі, але працює з перетворюваною прямою задачею.
Нехай пряму перетворену задачу записано в такому вигляді:
(6.5)
при обмеженнях
. (6.6)
Припустимо, що двоїстий розв’язок цієї задачі, записаної у формі таблиці, є допустимим, тобто виконуються умови оптимальності базисного розв’язку прямої задачі, але розв’язок прямої задачі не обов’язково є допустимим. Іншими словами, маємо недопустимий, але оптимальний розв’язок прямої задачі і поточний базис визначає допустимий, але неоптимальний розв’язок двоїстої задачі.
6.2. Схема двоїстого симплекс-методу для задачі максимізації цільової функції
Розглянемо теоретичне обґрунтування методу [0].
Крок 1. Вибір змінної, що виводиться з множини базисних (умови допустимості)
За змінну, що виводиться з базису, треба вибрати найбільшу за абсолютною величиною від’ємну базисну змінну, тобто вибрати ведучий рядок q, такий, що
.
Якщо всі базисні змінні 0 (тобто такого q не існує), то СТОП, одержали допустимий і оптимальний розв’язок. У протилежному випадку стовпчик, що відповідає змінній , повинен бути виведений з базису.
Крок 2. Вибір змінної, що вводиться в множину базисних (умова оптимальності)
Якщо j-й небазисний стовпчик замінює q-й базисний, тоді після застосування перетворень Гаусса відносна оцінка q-го стовпчика в новому ДБР буде дорівнювати . Для того, щоб компоненти вектора dN, як і раніше, були невід’ємні (виконувалась умова оптимальності), знаменник повинен бути від’ємним.
Визначимо коефіцієнт за формулою
(6.7)
і нехай мінімум досягається при j = p.
Якщо у q-му рядку немає жодного дляj, які відповідають небазисним змінним (ознака відсутності допустимих розв’язків), то СТОП, пряма задача не має допустимих розв’язків.
Отже, у множину базисних будемо вводити змінну :
;
.
Якщо взяти більше значення параметра , ніж те, яке дає (6.7), наприклад значення, яке відповідає j = r , і якщо змінну ввести в базис, то в новому розв’язку одержимо
, тому що
і умови оптимальності ДБР прямої задачі не будуть виконуватися.
Крок 3. Перехід до нового ДБР
За допомогою елементарних перетворень Гауcса виконується операція заміщення на. Перехід докроку 1.
Схема двоїстого симплекс-методу для задачі мінімізації ЦФ відрізняється від схеми розв’язання задачі на максимум у правилі вибору змінної, що виводиться (критерії оптимальності).
Коефіцієнт визначають за формулою
(6.7а)
(як і раніше розглядаються тільки відношення з від’ємним знаменником).
Ознака відсутності допустимих розв’язків така сама: у рядку, що відповідає вивідній змінній, немає жодного дляj, які відповідають небазисним змінним.
З урахуванням (6.7) і (6.7а) можна записати єдине (для задач максимізації та мінімізації) правило вибору ведучого стовпчика:
.
Таким чином, двоїстий симплекс-метод на кожному кроці забезпечує умову оптимальності розв’язку і систематичне наближення його до області допустимих розв’язків. Коли отриманий розв’язок виявляється допустимим, ітераційний процес обчислень закінчується, оскільки цей розв’язок є і оптимальним.
У табл. 6.1 наведено порівняльну характеристику прямого і двоїстого симплекс-методів.
Таблиця 6.1
|
Прямий симплекс-метод |
Двоїстий симплекс-метод |
1 |
2 |
3 |
Проміжний розв’язок |
Задача на мінімізацію хj 0 і j dj > 0. Проміжні розв’язки є допустимими, але неоптимальними за критерієм оптимальності |
Задача на максимізацію dj 0, але jxj < 0. Проміжні розв’язки є оптимальними за критерієм оптимальності, але не є допустимими |
Проміжний розв’язок |
Задача на максимізацію хj 0 і jdj < 0. Проміжні розв’язки є допустимими, але не є оптимальними. |
Задача на мінімізацію dj 0, але jxj < 0. Розв’язки є оптимальними за критерієм оптимальності, але не є допустимими. |
Опти-мальний розв’язок |
Задача на мінімізацію | |
xj 0 dj 0 |
xj 0 dj 0 |
Продовження таблиці 6.1
1 |
2 |
3 | |
|
Задача на максимізацію | ||
xj 0 dj 0 |
xj 0 dj 0 | ||
Етапи методу |
1. Умова оптимальності. Вибір змінної, що вводиться у базис: вводимо ту змінну xjу якійdj > 0 (min); dj < 0 (max). 2. Умова допустимості. Вибір змінної, що виводиться з базису: вибираємо змінну таким чином, щоб зберегти допустимість розв’язку, що отримується |
1. Умова допустимості. Вибір змінної, що виводиться з базису: виводимо ту змінну xj, для якої виконується: xj < 0. 2. Умова оптимальності. Вибір змінної, що вводиться в базис: вибираємо змінну таким чином, щоб зберегти оптимальність розв’язку |