Приклад застосування двоїстого симплекс-методу

Приклад 6.1.Розв’яжемо ЗЛП двоїстим симплекс-методом:

min z = x1 + x2; (6.8)

; (6.9)

; (6.10)

; (6.11)

. (6.12)

Зведемо спочатку всі обмеження до типу ”£”; для цього нерівності типу “³” помножимо на –1:

;

;

.

А тепер у кожне з них введемо відповідну залишкову змінну:

;

;

.

Ітерація 1. Початковий базисний розв’язок (недопустимий) задачі такий:

= .

На рис. 6.1 цей розв’язок відповідає точці А (0, 0).

Заповнюємо симплекс-таблицю (табл. 6.2).

Таблиця 6.2

Базисні змінні x1 x2 s1 s2 s3 Розв’язок
z -1 -1
s1 -2 -1 -4
s2 -1 -2 -4
s3

Значення залишкових змінних не забезпечують одержання допустимої стартової точки прямої задачі, але всі елементи z-рядка (dj) є недодатними — умова оптимальної задачі на мінімізацію виконується.

Крок 1. Вибираємо змінну, що виводиться з множини базисних

За умовою допустимості за виводжувану з базису змінну вибирається най­більша за модулем від’ємна базисна змінна. Таких змінних дві: s1 = –4; s2 = –4.
У цьому випадку можна вибрати будь-яку змінну. Виберемо змінну s2.

Крок 2. Вибираємо змінну, що вводиться у множину базисних

За умовою оптимальності змінна, що вводиться у базис, вибирається з небазисних таким чином: обчислюються відношення коефіцієнтів лівої частини z-рів­няння до відповідних коефіцієнтів рівняння, яке відповідає виводжуваній змінній. Відношення з додатними або нульовими значеннями знаменника не враховуються. У задачі на мінімізацію змінній, що вводиться, повинне відповідати найменше з вказаних співвідношень (табл. 6.3). У задачі на максимізацію вибираємо відношення, найменше за абсолютною величиною:


Таблиця 6.3

Базисні змінні x1 x2 s1 s2 s3 Розв’язок
Z -1 -1
s2 -1 -2 -4
Відношення 1 1/2 — — — —

Обчислюємо q = min{1,1/2} = 1/2, тобто вводимо до базису змінну x2.

Крок 3.Виконаємо операцію заміщення, використовуючи перетворення Жордана-Гаусса (тобто звичайні симплекс-перетворення) (табл. 6.4).

Таблиця 6.4

Базисні змінні x1 x2 s1 s2 s3 Розв’язок
z -1/2 -1/2
s1 -3/2 -1/2 -2
x2 1/2 -1/2
s3 1/2

Новий базисний розв’язок відповідає точці В (2, 0) (рис. 6.1).

Ітерація 2

Крок 1. Вибираємо змінну, що виводиться з множини базисних.

Розв’язок ще не допустимий (s1 = –2). За умовою допустимості за змінну, що виводиться з базису, вибираємо змінну s1.

Крок 2. Вибираємо змінну, що вводиться до базису (табл. 6.5).

Таблиця 6.5

Базисні змінні x1 x2 s1 s2 s3 Розв’язок
z -1/2 -1/2
s1 -3/2 -1/2 -2
x2 -1 -1/2
s3 1/2
Відношення 1/3 — — —  

Обчислюємо q = min{1/3, 1} = 1/3, тобто вводимо до базису змінну x1.

Крок 3. Виконуємо операцію заміщення (табл. 6.6).

Таблиця 6.6

Базисні змінні x1 x2 s1 s2 s3 Розв’язок
z -1/3 -1/3 8/3
x1 -2/3 1/3 4/3
x2 1/3 -2/3 4/3
s3 1/3 1/3 22/3

Розв’язок, що є оптимальним і допустимим, відповідає точці С (4/3, 4/3).

Рис. 6.1