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

1. Заповнюємо симплексну таблицю, знаходимо оцінки , значення .

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

3. Серед від’ємних значень знаходимо найбільше по модулю число і відповідний йому стовпчик вибираємо за провідний. Нехай це буде стовпчик з номером . Якщо в провідному стовпчику всі елементи ( ), то маємо випадок 2: цільова функція необмежена і розв’язування закінчене. Якщо не всі , то перейти до п.4.

4. Для кожного додатного елемента -го (провідного) стовпчика знаходимо відношення , вибираємо найменше (тобто знаходимо симплексне відношення ), і називаємо рядок, де воно досягається, провідним. Нехай це буде рядок з номером . Елемент на перетині провідного рядка і провідного стовпця буде провідним.

5. Виконуємо жорданове перетворення таблиці від стовпця В до An, від 1-го рядка до ( +1)-го з провідним елементом і переходимо до кроку 2.

Послідовність операцій 2-5 називається ітерацієюсимплекс-методу.

Зауваження 1. У другій і далі таблицях і можна шукати за правилом прямокутника як і інші елементи.

Зауваження 2. Якщо на кроці 3 є декілька найбільших по модулю оцінок , то в базис включають той вектор, якому відповідає найбільше .

Точнішим є таке правило: якщо не виконується умова оптимальності , , то в базис включають той вектор, якому відповідає min ∆j, при ∆j<0.

Якщо ж мінімальних оцінок декілька, то беруть вектор , якому відповідає максимальне .

Зауваження 3. Якщо в (1) , то умовою оптимальності плану є ∆j≤0, j=1,…,n.

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

,

Складаємо симплекс-таблицю

Сб -3
-1
-3 -1
-18 -5
-3
-3
-3

Всі , тому базисний розв’язок є оптимальний .

Відповідь: .

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

;

, , ; .

Зведемо задачу до канонічного вигляду

;

, .

Складемо симплекс-таблицю

 

i -1
-1
-4 -1
m + 1 ∆ -1 -3
-1
-2
-1
-4
-2
-2 -1
-1
11
-1 1

 

, , .

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

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

;

, .

Задача записана в канонічному базисному вигляді.

Складаємо симплексну таблицю

i
-2
-1
-1
-2 -4
-2
-5
-1
-10
∆

 

,

Відповідь: – невироджений оптимальний план, .