Метод штучного базису розв’язання задач лінійного програмування

Метод штучного базису розглянемо на прикладі розв’язання двоїстої задачі до задачі про використання ресурсів.

Крок 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

Якщо серед оцінок оптимальності немає від’ємних елементів, однак не всі штучні змінні виключені з базису, то така задача не має розв’язку.

Із третьої симплексної таблиці двоїстої задачі випливає, що всі оцінки оптимальності невід’ємні і всі штучні змінні виведені з базису. Це означає, що опорний план третьої ітерації є оптимальним:

,

а значення функції максимальним. Оскільки , то

грн.