Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Метод штучного базису розглянемо на прикладі розв’язання двоїстої задачі до задачі про використання ресурсів.
Крок 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
Якщо серед оцінок оптимальності немає від’ємних елементів, однак не всі штучні змінні виключені з базису, то така задача не має розв’язку.
Із третьої симплексної таблиці двоїстої задачі випливає, що всі оцінки оптимальності невід’ємні і всі штучні змінні виведені з базису. Це означає, що опорний план третьої ітерації є оптимальним:
,
а значення функції ‑ максимальним. Оскільки , то
грн.
Дата публикования: 2015-01-10; Прочитано: 1474 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!