Таблица 13

Базис		1		-x9	-x8
q	–7		0		1
x1	2		–1		1
x2	5		1		–2
x3	3		–4		3
x4	2		2		–5
x5	2		–3		2
x6	1		1		–3
x7	1		-2		1

Известны и другие алгоритмы Гомори, обеспечивающие решение неполностью целочисленной задачи, исключение влияния ошибок округления при проверке целочисленности решения, решение дискретных задач общего вида.

4.4. Двойственная задача линейного программирования

Рассмотрим две задачи линейного программирования, представленные в форме ОЗЛП.

Первая задача с m базисными и l=n-m свободными переменными с записью в алгебраической форме:

l
q = α00 − ∑α0 jx′′j → max ,
j=1
l
xi′ = αi0 − ∑aij x′′j ≥ 0	, i=1,2,…,m,	(44)

j=1

или в форме матрицы коэффициентов

	α00	α01	...	α0l
	α10	α11	...	α1l	.	(45)
	...	... ... ...
	αm0	αm1	...	αml

Вторая задача с l базисными и m свободными переменными с записью в алгебраической форме:

m

q′ = α00 + ∑αi0ui′′ → min , i=1

75

m
u′j = α0 j + ∑aijui′′ ≥ 0	, j=1,2,…,l,	(46)

i=1

или в форме матрицы коэффициентов

	α00	α10 ... αm0
	α01	α11	...	αm1	.	(47)
	... ... ... ...
	α0l	α1l	...	αml

Отметим следующее:

1.Строки и столбцы матрицы (45) совпадают соответственно со столбцами и строками матрицы (47).

2.Как было показано в п. 4.2.2, неотрицательность элементов

первого столбца и первой строки матрицы (45) без учета α00 – условия соответственно допустимости и оптимальности представленного матрицей базисного решения первой задачи.

3. Аналогично п. 4.1.1 нетрудно установить, что для достижения минимума целевой функции достаточно, чтобы все коэффи-

циенты ее разложения по свободным переменным (кроме α00) были положительны. Таким образом, неотрицательность элементов

первого столбца и первой строки матрицы (47) без учета α00 – условия соответственно допустимости и оптимальности представленного матрицей базисного решения второй задачи.

4. С учетом непосредственной связи матриц (45) и (47) можно сделать вывод о том, что решение первой задачи дает и решение второй, и наоборот.

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

Пример 29. Определить значения переменных состояния системы x1 ,x2 , x3 ,x4 , доставляющие максимум целевой функции q=x1 –x2 с учетом ограничений:

x3 = 2 − x1 + 2x2 , x4 = 5 − x1 − x2 , xi ≥ 0 ; i=1,2,3,4.

Задача представлена в форме разложения целевой функции q и базисных переменных x3 ,x4 по свободным переменным x1 ,x2 . Исходный линейный план приведен табл. 14, промежуточный в табл. 15.

76

						Таблица 14
Базис			1		-x1	-x2
q		0		–1		1
			2		1	–2
x3		2		1		–2
			2		1	–2
x4		5		1		1
			–2		–1	2
						Таблица 15
Базис			1		-x3	-x2
	2			1		-1
q			1		–1/3	1/3
	2			1		-2
x1			2		–2/3	2/3
x4	3			-1		3
			1		–1/3	1/3

Решение задачи после двух преобразований плана приведено в табл. 16: x1 =4, x2 =1, x3 =x4 =0, q=3.

Таблица 16

Базис	1	-x3	-x4
q	3	2/3	1/3
x1	4	1/3	2/3
x2	1	–1/3	1/3

Пример 30. Определить значения переменных состояния системы u1 ,u2 , u3 ,u4 , доставляющие минимум целевой функции q=2u1 +5u2 с учетом ограничений:

u3 = −1 + u1 + u2 , u4 =1 − 2u1 + u2 , ui ≥ 0 ; i=1,2,3,4.

Изменив знак целевой функции q′ = −2u1 − 5u2 , получим при-

вычную задачу на максимум, представленную разложением целевой функции q′ и базисных переменных u3 ,u4 по свободным пе-

ременным u1 ,u2 . Исходный линейный план приведен в табл. 17, промежуточный – в табл. 18.

77

								Таблица 17
	Базис			1			-u1	-u2
	q'		0			2		5
				–2			2	–2
	u3		–1			–1		–1
				1			–1	1
	u4		1			2		–1
				–2			2	–2
								Таблица 18
	Базис			1			-u3	-u2
	q'	–2			2			3
				–1			2	1
		1			–1			1
	u1			–1/3			2/3	1/3
	u4	–1			2			–3
				1/3			–2/3	–1/3

Решение задачи после двух преобразований плана представлено в табл. 19: u1 =2/3, u2 =1/3, x3 =x4 =0, q' = –3 и соответственно q=3.

Таблица 19

Базис		1		-u3	-u4
q'	–3		4		1
u1	2/3		–1/3		1/3
u2	1/3		–2/3		–1/3

Сравнивая первые строки и столбцы табл. 16 и 19, можем убедиться в справедливости сформулированных выше выводов.

Первую из рассмотренных задач (задачу на максимум целевой функции – пример 29) принято называть основной, вторую (задачу на минимум – пример 30) двойственной. Очевидно, что несложные алгебраические преобразования позволяют поменять их местами.

С практической точки зрения эффект двойственности существенного значения для решения задач линейного программирова-

78