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

1. Розв’язок ЗЛП безпосередньо. Двоїстий симплекс-метод може безпосередньо застосовуватись для розв’язання тільки певного класу задач. В цих задачах знаки коефіцієнтів цільової функції та знаки обмежень не можуть бути довільними.

1.1. Значення коефіцієнтів цільової функції:

1. якщо цільова функція мінімізується, то усі коефіцієнти цільової функції повинні бути невід’ємними¹:  c_j 0;

б) якщо цільова функція максимізується, то усі коефіцієнти цільової функції повинні бути недодатними²:  c_j 0.

1.2.Знаки обмежень. Обмеження початкової ЗЛП з невід’ємними компонен-тами вектора b мають лише знаки " " і " " (але не всі одночасно типу " ").

2. Розв’язок ЗЛП у випадках, коли після отримання оптимального розв’язку в задачу вводиться нове (додаткове) обмеження (найбільш важлива сфера застосування).

3. Параметричне програмування. В постоптимальному аналізі ми обмежувалися діапазонами зміни, при яких поточний базис залишався оптимальним, причому кожного разу разглядався вплив зміни лише однієї складової.

Параметричне програмування – це метод знаходження того, як зміниться розв’язок задачі зміною або вектора коефіцієнтів ЦФ, або вектора обмежень [1].

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

_{Задача 1.1. Розв’яжемо ЗЛП двоїстим симплекс-методом.}

; (8)

; (9)

; (10)

; (11)

. (12)

Зведемо спочатку усі обмеження до вигляду ” ”:

;

;

,

а тепер у кожне з них введемо відповідну остаточну змінну

;

;

.

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

= .

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

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

Таблиця 2

Базисні змінні						Розв’язок
z	-1	-1	0	0	0	0
	-2	-1	1	0	0	-4
	-1	-2	0	1	0	-4
	1	1	0	0	1	10

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

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

За умовою допустимості за виводжувану з базису змінну вибирається найбільша за модулем від’ємна базисна змінна. Таких змінних дві, розглянемо змінну .

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

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

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

Таблиця 3

Базисні змінні						Розв’язок
Z	-1	-1	0	0	0	0
	-1	-2	0	1	0	-4
Відношення	1	1/2	-	-	-	-

 = min{1,¹/₂}=¹/₂, тобто вводити до базису будемо змінну .

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

Таблиця 4

Базисні змінні						Розв’язок
Z	-1/2	0	0	-1/2	0	2
	-3/2	0	1	-1/2	0	-2
	-1	1	0	-1/2	0	2
	1	0	0	½	1	8

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

Ітерація 2.

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

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

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

Таблиця 5

Базисні змінні						Розв’язок
Z	-1/2	0	0	-1/2	0	2
	-3/2	0	1	-1/2	0	-2
	-1	1	0	-1/2	0	2
	1	0	0	1/2	1	8
Відношення	1/3	-	-	1	-

 = min{¹/₃,1}=¹/₃, отже вводити до базису будемо змінну .

Крок 3. Виконання операції заміщення. (табл. 6)

Таблиця 6

Базисні змінні						Розв’язок
Z	0	0	-1/3	-1/3	0	8/3
	1	0	-2/3	1/3	0	4/3
	0	1	1/3	-2/3	0	4/3
	0	0	1/3	1/3	1	22/3

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

Рис. 1. Графічна ілюстрація розв’язку задачі (8)-(12)