ють нульові елементи в вирішуючому стовпці колишньої таблиці, то всі рядки з цими нулями переписуються без зміни в нову таблицю.
Якщо існують нульові елементи в роздільної рядку колишньої таблиці, то відповідні стовпці з цими нулями переписуються в нову таблицю.
Складається опорна рядок у новій таблиці діленням колишньої роздільної рядка на дозволяючий елемент.
Всі інші елементи знаходять за правилом трикутника: новий елемент дорівнює колишньому значенню мінус добуток відповідного по рядку елемента в вирішуючому стовпці колишньої таблиці на елемент в опорній рядку стовпця шуканого елемента нової таблиці. Виняток - коефіцієнт в цільовій функції, де замість В«-В» у правилі трикутника необхідно використовувати В«+В». p> Якщо виконується критерій оптимальності: коефіцієнти, коефіцієнти (за неіскусственное змінних) цільової функції, то отриманий оптимальний план. Інакше - перехід до пункту 2 даного алгоритму. p> Алгоритм двоїстого симплекс-методу (якщо все, але існують)
1. Записати в нульову таблицю вихідну канонічну стандартну форму.
2.Среді негативних вільних членів вибрати максимальний по модулю. Відповідний рядок - роздільна. p>. Серед всіх відносин коефіцієнтів цільової функції до негативних елементів роздільної рядки вибрати мінімальне по модулю. Відповідний стовпець - дозволяючий. p>. Далі рішення аналогічно основним симплекс-методом, починаючи з пункту 4.
Алгоритм змішаного симплекс-методу (існують і)
Почати рішення основним симплекс-методом, при цьому рівняння з негативною правою частиною не розглядаються при визначенні роздільної рядка (тобто відповідні їм базисні змінні не можна виводити з базису на цьому етапі).
Потому, як коефіцієнти цільової функції стануть, а серед правих частин рівнянь обмежень існують, продовжити вирішення двоїстим симплекс-методом.
Рішення ЗЛП методом штучного базису
Якщо у системі обмежень існують нерівності (зі знаками або>) або рівняння (без змінних, що створюють канонічний вигляд), то для створення канонічного виду стандартної форми зручно використовувати метод штучного базису.
При вирішенні ЗЛП методом штучного базису нерівності обмежень спочатку призводять до системи рівнянь. Після цього в рівняння без змінних, що створюють канонічний вигляд, вводять штучні змінні. Так як в рівняння вводяться невід'ємні змінні, то для відповідності нового завдання вихідної, необхідно, щоб штучні змінні були рівні нулю. Для цього складається цільова функція, що дорівнює сумі всіх введених штучних змінних. Функцію G необхідно виразити через неіскусственное змінні і ввести в симплекс-таблицю. При визначенні дозволяє стовпця в симплекс-таблиці вибирають максимальний по модулю негативний коефіцієнт функції (при неіскусственное змінних). Коли коефіцієнти цільової функції при неіскусственное змінних дорівнюють нулю, а при штучних змінних коефіцієнти рівні 1 (тобто сума всіх штучних змінних дорівнює нулю), тоді викреслюється рядок з допоміжною функцією і переходять до рядка цільової функції для визначення дозволяє стовпця і продовжують рішення. Якщо в процесі вирішення виходить, що всі коефіцієнти в рядку (при неіскусственное змінних) позитивні, то завдання нерозв'язна (допустима область значень порожній). br/>
Стійкість рішень ЗЛП при зміні параметрів
Якщо відомо рішення вихідної задачі, то наведені нижче формули розрахунку симплекс-таблиці дозволяють знайти оптимальне рішення задачі, при незначній зміні її параметрів, не вирішуючи завдання заново. Матриця, складена з оптимальною таблиці (з коефіцієнтів в шпальтах тих змінних, які були засадничими у вихідній (нульовий) таблиці) називається зверненим базисом. p> Симплекс-множники знаходяться в цільовій функції оптимальної таблиці під зверненим базисом.
Нижче представлені розрахункові формули, де значення, беруть в нульовий (вихідної) таблиці, а значення в даній (обчислюється) таблиці.
Формули розрахунку симплекс-таблиці за допомогою зверненого базису і симплекс-множників
Елементи табліциФормулиСтолбци Стовпець вільних членів Коефіцієнти при змінних , Цільова функція в стовпці ,
Рішення двоїстих задач лінійного програмування
Загальний вигляд прямої задачі:
В
Загальний вигляд двоїстої завдання
В
Правила побудови двоїстої задачі:
1. Число невідомих двоїстої задачі дорівнює числу обмежень прямої задачі. Число обмежень двоїстої задачі ...
