Двоїстий симплекс-метод
З математичної моделі двоїстої пари задач випливає, що оцінкою при розв’язуванні прямої задачі є величина Cj , а для двоїстої задачі Таким чином, двоїсту пару задач можна зобразити у вигляді однієї симплекс-таблиці. Тільки процес побудови сукупності базисних змінних двоїстої задачі робиться у протилежному напрямку, тобто в першу чергу визначають базисну змінну, яку виводять із базису, а потім змінну, яку треба ввести до базису замість виведеної. На цій основі розроблено так званий двоїстий симплекс-метод, або метод послідовного уточнення оцінок. Щоб використовувати двоїстий симплекс-метод, математичну модель задачі треба завжди перетворювати так, щоб у моделі були тільки додаткові змінні, тобто призвести обмеження до вигляду „ Тобто, для розв’язання задачі двоїстим симплекс-методом обмеження математичної моделі необхідно звести до типу „ Далі наведемо алгоритм двоїстого симплекс-методу. 1. Вибір у базисній колонці вільних членів елемента, для якого 2. Вибраний елемент показує на головний рядок 3. Для 4. Вибране співвідношення зазначає головну колонку 5. Перетворення симплекс-таблиці згідно з основним симплекс-методом.
6. Аналіз знайденого розв’язку на оптимальність: якщо 7. Якщо знайдений розв’язок тільки допустимий, то при Зустрічається випадок, коли в початковій симплекс-таблиці
У разі застосування двоїстого симплекс-методу зменшується обсяг обчислень, оскільки не треба виконувати умову Блок-схему алгоритму зображено на рис.2.1.
![]() ![]()
Рис. 2.1 Приклад. Нехай задано таку математичну модель: – цільова функція – обмеження Задану математичну модель задачі зводимо до вигляду, який потрібний при застосуванні двоїстого симплекс-методу: Спочатку складаємо першу симплекс-таблицю.
Потім складаємо відповідно другу та третю симплекс-таблиці:
Оптимальний розв’язок
Двоїсті оцінки
Читайте также: Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|