2. Двоїста задача лінійного програмування
ЗАВДАННЯ 2. Побудувати математичну модель двоїстої задачі. Розв’язати двоїсту задачу симплексним методом. Порівняти отриманий результат із тим, що отримано, виходячи з останньої симплексної таблиці прямої задачі, а також, виходячи зі звіту по стійкості процедури «Поиск решения» прямої задачі. Зробити економічний аналіз результатів.
2.1 Математична модель двоїстої задачі
Випишемо математичну модель прямої (вихідної) задачі:
пар взуття – тижневий план випуску моделі №1,
пар взуття – тижневий план випуску моделі №2,
Складемо математичну модель двоїстої задачі.
1) Дана пряма задача на максимум, у ній усі нерівності системи обмежень мають знак «≤», тому змінювати форму запису математичної моделі прямої задачі немає необхідності.
2) Випишемо розширену матрицю системи і рядок коефіцієнтів цільової функції
.
3) Складаємо транспоновану матрицю
.
4) Складаємо математичну модель двоїстої задачі
.
Економічний зміст
змінних двоїстої задачі визначається
економічним змістом відповідних їм
нерівностей системи обмежень прямої
задачі. Оскільки першій двоїстій змінній
відповідає перше обмеження по витратах
робочого часу, другій – по витратах
шкіри I сорту, третій – по витратах шкіри
II сорту, то
грн. – тіньова ціна 1 люд.-год. робочого
часу;
грн. – тіньова ціна 1 шматка шкіри I
сорту;
грн. – тіньова ціна 1 шматка шкіри I
сорту.
2.2 Метод штучного базису розв’язання задач лінійного програмування
Метод штучного базису розглянемо на прикладі розв’язання двоїстої задачі до задачі про використання ресурсів.
Крок
1.
Зведемо
математичну модель двоїстої задачі до
канонічного вигляду, уводячи додаткові
невід’ємні змінні
.
Оскільки всі нерівності системи обмежень
виражаються знаком «≥», то додаткові
змінні ввійдуть у систему обмежень з
коефіцієнтом «-1». У цільову функцію
додаткові змінні завжди входять з
коефіцієнтом «0». Оскільки двоїста
задача на мінімум, то складемо допоміжну
функцію
.
Канонічний
вигляд запису двоїстої задачі:
. (6)
Крок 3. Побудова первинного базису.
Основна матриця системи (6)
містить одиничний
двовимірний вектор (0; 1), що відповідає
змінній
,
яка увійде у первинний базис. Ця змінна
міститься у другому рівнянні системи
(6) з коефіцієнтом «1». Щоб отримати
одиничну підматрицю у цій матриці,
введемо невід’ємну штучну
базисну змінну
яку додамо до лівої частини першого
рівняння. Штучну змінну
включимо в цільову функцію з коефіцієнтом
«-10000». Зазначимо, що абсолютна величина
коефіцієнтів при штучних змінних повинна
бути на порядок вище за всі абсолютні
величини коефіцієнтів цільової функції.
У результаті складемо математичну
модель розширеної
задачі:
. (7)
Отже, маємо: по-перше, усі вільні елементи системи (7) ‑ невід’ємні; по-друге, основна матриця системи (7)
містить одиничну
підматрицю, що утворена двовимірними
векторами (0; 1) і (1; 0), котрим відповідають
базисні змінні
,
причому кількість базисних змінних
дорівнює кількості рівнянь системи
(7), тому система (7) має первинний базис
.
Крок 5. Розв’язуємо отриману задачу симплексним методом за алгоритмом, що описано в п. 1.3. Відповідні симплексні таблиці задачі і зразки формул для EXEL наведені на рис. 2.1 і рис. 2.2 відповідно.
Слід зазначити, що ітераційний процес симплексного методу продовжується доти, поки оцінки оптимальності містять від’ємні елементи.
Рис. 2.1 Результати обчислень методом штучного базису)
Рис.2.2 Формули розрахунку методу штучного базису в таблицях EXCEL
Якщо серед оцінок оптимальності немає від’ємних елементів, однак не всі штучні змінні виключені з базису, то така задача не має розв’язку.
Із третьої симплексної таблиці двоїстої задачі випливає, що всі оцінки оптимальності невід’ємні і всі штучні змінні виведені з базису. Це означає, що опорний план третьої ітерації є оптимальним:
,
а
значення функції
‑ максимальним. Оскільки
,
то
грн.