Двоїстий симплекс метод. Приклад розв’язку задачі лінійного програмування двоїстим симплекс методом

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

Розглянемо задачу лінійного програмування, яка полягає у визначенні максимального значення функції мети:

при обмеженнях:

Де компоненти вектора містять від’ємні числа і серед векторів – існує  одиничних.

Розв’язок являється допустимим планом розв’язку системи обмежень (2). Але, оскільки цей розв’язок містить від’ємні елементи, то він не може бути розв’язком задачі лінійного програмування (1) – (3). Його прийнято називати псевдопланом.

Твердження 1: якщо в псевдоплані  системи лінійних рівнянь (2), який визначається базисом векторів , для будь-якого усі , то задача (1) – (3) немає розв’язків.

Твердження 2: псевдоплан  системи лінійних рівнянь (2), який визначений базисом векторів  може привести до покращення значення функції мети, якщо для будь-якого  існує хоча б один елемент .

Далі, на основі вище розглянутих тверджень сформулюємо алгоритм двоїстого симплекс методу:

  1. Будуємо симплекс таблицю і вносимо відповідні дані згідно нашої задачі лінійного програмування записаної у векторній формі і де серед векторів   існує  одиничних.
  2. Серед елементів стовпця  визначаємо найбільший по модулю елемент серед від’ємних. Якщо їх буде декілька, то вибираємо довільний.
  3. Вектор, який відповідає вибраному  в пункті 2, виключаємо з базису.
  4. Визначаємо вектор, який необхідно включити в базис. Для цього знаходимо , де . Нехай це буде стовпець, який відповідає вектору . Даний вектор  вводимо в базис. Елемент називається ведучим. Рядок і стовпець називаються направляючим рядком і стовпцем. Подальші перерахунки ведуться аналогічно симплекс методу.

Ітераційний процес двоїстого симплекс методу продовжується до тих пір, поки усі від’ємні елементи стовпця  не будуть виключені або поки в стовбці  буде хоча б один від’ємний елемент, але в рядку де знаходиться цей елемент не буде жодного від’ємного серед . Перший випадок приведе до отримання оптимального розв’язку задачі лінійного програмування. Другий випадов вказує на те, що дана задача немає розв’язків.

Зауваження: усі розрахунки згідно двоїстого симплекс методу ведуться за допомогою симплекс таблиць.

Розв’язком задачі лінійного програмування двоїстим симплекс методом – приклад:

Знайти розв’язок наступної задачі лінійного програмування, використовуючи при цьому двоїстий симплекс метод:

Для побудови першого опорного плану систему нерівностей запишемо у канонічній формі , тобто нерівності типу «» перетворимо у рівності шляхом введенням у ліву частину обмежень додаткових змінних зі знаком «-». У цільову функцію ці змінні увійдуть з нульовими коефіцієнтами:

Далі, перепишемо канонічну форму так, щоб в системі був повний набір базисних змінних:

На наступному кроці, виходячи з того, що усі розрахунки згідно двоїстого симплекс методу ведуться за допомогою симплекс таблиці, то записавши дану задачу у векторній формі, побудуємо першу таблицю та обчислемо для даного опорного плану оцінки векторів :

Двоїстий симплекс метод приклад

Початковий опорний плану задачі лінійного програмування

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

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

Виходячи з того, що ми отримали два одинакових мінімальних значення, то в якості ведучого можемо взяти один з двох елементів: . Нехай це буде елемент , тому вектор вводимо в базис. Наступним кроком буде побудова другої симплекс таблиці і визначення всіх її коефіцієнтів згідно нового базису:

Двоїстий симплекс метод приклад

Другий опорний план задачі лінійного програмування

Далі, проаналізувавши елементи вектора , приходимо до висновку, що отриманий на другій ітерації опорний план є оптимальним , максимальне значення функції мети для якого дорівнює .

Блок-схема алгоритму знаходження розв’язку задачі лінійного програмувнання двоїстим симплекс методом

Двоїстий симплекс метод блок-схема

Залишити коментар

Your email address will not be published. Required fields are marked *

*