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

Д

3*10 – Розмірність задачі см.

3*7 – розмірність задачі ДСМ.

ля розв’язання задачі двоїстим симплекс-методом (ДСМ) треба також звести модель до канонічного виду, чим і є псевдоплан. Для ознайомлення з розрахунком псевдоплану для ДСМ розглянемо приклад:

Зведення ЦФ до максимуму, а обмежень до рівностей (канонічного вигляду):			Запис двоїстої задачі згідно з правилами та вибір спряженого базису:
				A0
	y1			A1
	y2			A2
	y3			A3
				A4
				A5
				A6
				A7

Побудова незалежних векторів на підставі рядків ДЗ:

A0 =	8		A1 =	3		A2 =	2		A3 =	-1		A4 =	5		A5 =	-1		A6 =	0		A7 =	0
	4			0			-1			-3			6			0			-1			0
	0			2			0			1			-1			0			0			-1

Вибір спряженого базису розміром m, що включає такі етапи:

_{ довільний вибір m рівнянь (у даному випадку вибираємо рівняння А5, А6 та А7, де вектор Y = (0, 0, 0);}

_{ розв’язання цієї систем з m рівнянь;}

_{ підстновка розв’язку в кожне із залишених n-m обмежень (А1, А2, А3 та А4) та перевірка: чи задовольняє спряжений базис;}

_{ якщо спряжений базис задовільняє, то формування псевдоплану (розрахунок симплекс-таблиці);}

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

Отже, маємо складену симплекс-таблицю :

			-4	-3	-10	-5	0	0	0
Cx	Bx	A0	A1	A2	A3	A4	A5	A6	A7
0	x5	-8	-3	-2	1	-5	1	0	0
0	x6	4	0	1	3	-6	0	1	0
0	x7	0	-2	0	-1	1	0	0	1
	Δ	0	4	3	10	5	0	0	0
											…
Xb = (x5, x6, x7) = (-8, -4, 0)						Xb = (-3, 0, -2)

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

• коефіцієнти ЦФ відповідають верхньому рядку таблиці;

• обмеження відповідають векторам А₀-А₇, а знак обмежень – «=».

Для розрахунку псевдоплану можна викликати програму <can plan file_in file_out>, яка створена на основі процедур мови Pascal:

while next_variant do

{генареція наст. вар. спряж. базису}

begin

if (Gauss and Test) then

{розв’язок сис-ми рівнянь}

begin

FormSymTable; break;

{заповнення симплекс таблиці}

end;

end;

Примітка. Для виклику програми ДСМ є команда <double file_in file_out>, де file_in та file_out – файли з початковими даними та ітераціями розрахунку.