Розв‘язання двоїстих злп

Виклад двоїстого симплекс-методу.

Двоїстий симплекс-метод (ДСМ) безпосередньо застосовується до розв'язування майже канонічної задачі лінійного програмування (МКЗЛП), яка формулюється таким чином:

Знайти вектор x = (x₁,...,x_n), що мiнiмiзує лінійну функцію

L(x) = c₁x₁ + ... + c_nx_n (4.1)

i задовольняє систему лінійних обмежень

x_i + a_i,m+1 x_m+1 + ... + a_inx_n = a_i0, i=1,...,m, (4.2)

x_j³0, j=1,...,n, (4.3)

(компоненти a_i0 вектора обмежень A₀ можуть бути від'ємними) при додатковій умові: відносні оцінки (симплекс-рiзницi) D_j змінних x_j невід'ємні.

Вектор x=(x₁,...,x_n) називається майже допустимим базисним розв'язком (МДБР) МКЗЛП, якщо його компоненти задовольняють обмеження (4.2), i ненульовим компонентам x_j відповідають лінійно незалежні вектори умов A_j.

Базис i базисна матриця МДБР визначаються подібно тому, як це робиться для СЗЛП.

МКЗЛП є частинним випадком СЗЛП. Iснують методи зведення довільної ЗЛП до майже канонічного вигляду.

Ознака оптимальності: Якщо на деякому кроцi ДСМ компоненти МДБР x* невід'ємні, то x* — оптимальний розв'язок МКЗЛП.

Ознака відсутності розв'язку: Оптимального розв'язку МКЗЛП не існує, якщо на якому-небудь кроцi ДСМ в рядку з a_i0<0 всі компоненти a_ij³0, j=1,...,n. В цьому випадку допустима множина розв'язкiв МКЗЛП порожня.

Алгоритм двоїстого симплекс-методу.

На кожному кроцi ДСМ виконуються такі дії (розрахункові формули наводяться лише для першого кроку).

1. Розглядається МДБР x=(a₁₀,...,a_m0,0,...,0).

Обчислюються відносні оцінки (симплекс-рiзницi) D_j небазисних змінних x_j, j=m+1,...,n, за формулою:

D_j=c_j – (c_б, A_j),

де c_б=(c₁,...,c_m), A_j — вектор умов, що відповідає змінній x_j (відносні оцінки базисних змінних дорівнюють нулю).

Якщо для всіх i=1,...,m виконується умова a_i0³0, то МДБР x буде оптимальним розв'язком МКЗЛП. Кiнець обчислень.

Якщо існує таке i, що a_i0<0, а коефіцієнти a_ij³0, j=1,...,n, то МКЗЛП не має допустимих розв'язкiв. Кiнець обчислень.

2. Якщо існують індекси i, для яких a_i0<0, а серед відповідних компонент a_ij, j=1,...,n, є від'ємні, то знаходять l:

l=argmina_i0,

i: a_i0<0

обчислюють відношення g_j=–D_j/a_lj для всіх a_lj<0 та визначають k:

k=argming_j.

i: a_lj<0

3. Переходять до нового МДБР, виключаючи з базису вектор A_l i вводячи до базису вектор A_k. Згаданий перехід здійснюється за допомогою симплекс-перетворень (елементарних перетворень Жордана-Гаусса з ведучим елементом a_lk) над елементами розширеної матриці умов. Перехiд до пункту 1.

Завдання.

В усіх задачах, що пропонуються далі, всі змінні невід'ємні.

1)	6 x1 + 4 x2 ® min,	2)	2 x1 + 3 x2 ® min,	3)	–6 x1 – 4 x2 ® max,
	2 x1 + x2 ³ 3,		x1 + 5 x2 ³ 16,		2 x1 + x2 ³ 3,
	x1 – x2 £ 1,		3 x1 + 2 x2 ³ 12,		x1 – 2 x2 £ 2,
	– x1 + 2 x2 ³ 1;		2 x1 + 4 x2 ³ 16;		3 x1 + 2 x2 ³ 1;

4)	6 x1 + 4 x2 ® min,	5)	7 x1 + x2 ® min,	6)	7 x1 + 10 x2 ® min,
	2 x1 + x2 ³ 3,		x1 + x2 ³ 3,		2 x1 + 28 x2 ³ 17,
	3 x1 + 2 x2 ³ 1,		5 x1 + x2 ³ 5,		x1 + 2 x2 ³ 3;
	– x1 – x2 ³ 6;		x1 + 5 x2 ³ 5;		x1 + 17 x2 ³ 19;

7)	x1 + x2 + 2 x3 ® min,	8)	–15x1 – 33 x2 ® max,
	2 x1 – x2 – 3 x3 + x4 = – 3,		3 x1 + 2 x2 ³ 6,
	x1 – 3 x2 – 4 x3 + x5 = – 1;		6 x1 + x2 ³ 6;

9)	x1 + 2 x2 ® min,	10)	78 x1 + 52 x2 ® min,	11)	5 x1 + 4 x2 ® min,
	2 x1 + x2 £ 18,		6 x1 + 2 x2  9,		x1 + x2 £ 6,
	x1 + 2 x2 ³ 14,		10 x1 + 14 x2 13,		2 x1 + x2 ³ 9,
	x1 – 2 x2 £ 10;		11 x1  x2 ³ 6;		3 x1 + x2 ³ 11.

Лабораторна робота 7-8.