Двоїстий симплекс метод, як і симплекс метод, використовується для знаходження розв’язку задачі лінійного програмування, записаної в основній формі, де серед векторів існує одиничних. Якправило, при використанні симплекс методу, значення стовпця вільних членів задовільняє умову додатності. Двоїстий симплекс метод використовується в тому випадку, коли серед вільних членів системи обмежень існують такі, що приймають від’ємні значення.
Розглянемо задачу лінійного програмування, яка полягає у визначенні максимального значення функції мети:
при обмеженнях:
Де компоненти вектора містять від’ємні числа і серед векторів – існує одиничних.
Розв’язок являється допустимим планом розв’язку системи обмежень (2). Але, оскільки цей розв’язок містить від’ємні елементи, то він не може бути розв’язком задачі лінійного програмування (1) – (3). Його прийнято називати псевдопланом.
Твердження 1: якщо в псевдоплані системи лінійних рівнянь (2), який визначається базисом векторів , для будь-якого усі , то задача (1) – (3) немає розв’язків.
Твердження 2: псевдоплан системи лінійних рівнянь (2), який визначений базисом векторів може привести до покращення значення функції мети, якщо для будь-якого існує хоча б один елемент .
Далі, на основі вище розглянутих тверджень сформулюємо алгоритм двоїстого симплекс методу:
- Будуємо симплекс таблицю і вносимо відповідні дані згідно нашої задачі лінійного програмування записаної у векторній формі і де серед векторів існує одиничних.
- Серед елементів стовпця визначаємо найбільший по модулю елемент серед від’ємних. Якщо їх буде декілька, то вибираємо довільний.
- Вектор, який відповідає вибраному в пункті 2, виключаємо з базису.
- Визначаємо вектор, який необхідно включити в базис. Для цього знаходимо , де . Нехай це буде стовпець, який відповідає вектору . Даний вектор вводимо в базис. Елемент називається ведучим. Рядок і стовпець називаються направляючим рядком і стовпцем. Подальші перерахунки ведуться аналогічно симплекс методу.
Ітераційний процес двоїстого симплекс методу продовжується до тих пір, поки усі від’ємні елементи стовпця не будуть виключені або поки в стовбці буде хоча б один від’ємний елемент, але в рядку де знаходиться цей елемент не буде жодного від’ємного серед . Перший випадок приведе до отримання оптимального розв’язку задачі лінійного програмування. Другий випадов вказує на те, що дана задача немає розв’язків.
Зауваження: усі розрахунки згідно двоїстого симплекс методу ведуться за допомогою симплекс таблиць.
Розв’язком задачі лінійного програмування двоїстим симплекс методом – приклад:
Знайти розв’язок наступної задачі лінійного програмування, використовуючи при цьому двоїстий симплекс метод:
Для побудови першого опорного плану систему нерівностей запишемо у канонічній формі , тобто нерівності типу «» перетворимо у рівності шляхом введенням у ліву частину обмежень додаткових змінних зі знаком «-». У цільову функцію ці змінні увійдуть з нульовими коефіцієнтами:
Далі, перепишемо канонічну форму так, щоб в системі був повний набір базисних змінних:
На наступному кроці, виходячи з того, що усі розрахунки згідно двоїстого симплекс методу ведуться за допомогою симплекс таблиці, то записавши дану задачу у векторній формі, побудуємо першу таблицю та обчислемо для даного опорного плану оцінки векторів :
Початковий опорний плану задачі лінійного програмування
Після обчислення всіх оцінок опорний план перевіряємо на оптимальність. Для цього переглянувши елементи оцінкового рядка бачимо, що у даному прикладі перший опорний план не є оптимальним, бо серед елементів є такі, що мають від’ємні значення. Тому слідуючи алгоритму двоїстого симплекс методу переходимо до нового опорного плану.
Для цього, серед усіх від’ємних елементів вектора вибираємо те, яке по абсолютній величині приймає максимальне значення. В нашому випадку таким буде . Тобто вектор виключаємо з базису. Далі, скориставшись четвертим кроком вище розглянутого алгоритму, знайдемо ведучий елемен, і таким чином визначимо вектора, який необхідно включити в базис:
Виходячи з того, що ми отримали два одинакових мінімальних значення, то в якості ведучого можемо взяти один з двох елементів: . Нехай це буде елемент , тому вектор вводимо в базис. Наступним кроком буде побудова другої симплекс таблиці і визначення всіх її коефіцієнтів згідно нового базису:
Другий опорний план задачі лінійного програмування
Далі, проаналізувавши елементи вектора , приходимо до висновку, що отриманий на другій ітерації опорний план є оптимальним , максимальне значення функції мети для якого дорівнює .