korobov

131

Как в предыдущем случае, в верхней части оценочной строки записывается 13 , в

		4
	нижней - −	3	.
	Такое разделение оценочной строки не обязательно, однако создает некоторые удобства в
	дальнейших вычислениях.
	Программа Р2, соответствующая 2-й итерации (x1			= 2/3, y1	= 5, y2=	26	, y4 = 4,
						3

остальные xj и у3 равны нулю), оказалась также не оптимальной. Наибольшая двойственная оценка из положительных 4 = 4М-2 находится в столбце, соответствующем неизвестной x4. Этот столбец следует принять за ключевой, переменную x4 надо ввести в базис вместо переменной y4, чтобы обеспечить переход к лучшему опорному плану. Все дальнейшие преобразования выполняются обычным порядком. Результаты записываются в таблице (3.8) в частях, соответствующих последовательным итерациям.

Итак, в оценочной строке, соответствующей 5-й итерации, в симплексной табл. 3.8 нет ни одной двойственной оценки больше нуля. Следовательно, программа Р5 (x1=2/3, xз =

10/3, x4=2, х6=1/3), а с учетом коэффициента сокращения 100 —
		x	=	200		, x		=	1000	, x		= 200, x		=	100	, x		= 0, x		= 0, x			= 0, x		= 0, x		= 0.
							3				4		6				2		5			7		8		9
		1	3					3						3
является			оптимальной. Целевая функция F5															приняла			минимальное значение, равное
	62	или	620		, откорректировав на принятые ранее условности (коэффициенты 100 и 0,1).
3
			3

Нами получен такой же результат, как и при решении задачи первым способом. Иначе не должно быть. Решение задачи закончено.

Теперь перейдем к решению первого примера (3.12, 3.13) этого параграфа.

Здесь примем несколько иную форму изложения: более краткую (с надеждой на то, что читатель уже освоил «механику» симплексного метода); кроме того, будем применять более строгую математическую терминологию, свойственную линейному программированию (с тем, чтобы неподготовленный читатель постепенно привыкал к чтению математических разделов и книг).

Рассмотрим решение этой задачи на максимум целевой функции. Для этого составим эквивалентную задачу максимизации. В нашем примере надо найти неотрицательные числа х1, x2, x3, x4, максимизирующие целевую функцию (3.13)

F= — 2x1-x2+x3+x4

при условиях 3.13:

x1 − x2			+ 2x3 − x4 = 2,
2x1 + x2 − 3x3 + x4 = 6,
x	+ x	2	+ x	3	+ x	4	= 7
1

Сформулируем расширенную задачу максимизации

Найти неотрицательные числа x1, х2, х3, x4 и y1, y2, y3, максимизирующие целевую функцию

F1= -2x1- x2+ x3+ x4-My1- My2- My3*		(3.29)

* Поскольку целевую функцию F в данной задаче необходимо максимизировать, искусственные переменные у1, у2 и у3, вводим в нее с отрицательными коэффициентами (-M). Здесь —М величина меньше всякого другого сколь угодно малого отрицательного числа.

									132
при условиях
x1 − x2 + 2x3 − x4 + y1								= 2,
2x1 + x2		− 3x3 + x4				+ y2			(3.30)
								=6,
x + x	2	+ x	3	+ x	4	+ y	3	= 7
1

Имеем очевидную программу этой задачи х1 = 0, x2=0, xз = 0, x4 = 0, y1 = 2, y2 = 6, у3=7, связанную с единичной подматрицей. Составляем симплексную таблицу. Исходная программа отражена в 1-й итерации (табл. 3.9). Данная таблица в отличие от предшествующих не содержит столбцов для искусственных переменных y1, y2, y3, без них можно обойтись.

Применяя алгоритм симплексного метода, получаем в табл. 3.9 опорные планы на последующих итерациях.

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

Поскольку и вторая программа Р2 оказалась также не оптимальной, переходим к следующей Р3. Для этого введем в нее неизвестную x2 вместо базисной неизвестной у2.

На следующей итерации будет вытеснена из базисных последняя искусственная переменная у3 и мы получим программу исходной задачи, с базисными переменными х1, х2, x3. Поэтому оценочная строка (в данном случае в 4-й итерации) должна быть заново сосчитана по формуле (3.12).

															Табл. 3.9
				-2				-1			1	1
Со		Р0	В		x1				x2		xз	x4	∑	β		α
						1-я итерация
-М		y1	2		1			-1			2	-1	3	2		-1
-М		y2	6	2				1			-3	1	7	3		2
-М		y3	7	1				1			1	1	11	7		1
	М→		-15	-4				-1			0	-1	-21	—		-4
			0	2				1			-1	-1	1	—		2
											2-я итерация
-2		x1	2	1				-1			2	-1	3	—		-1/3
-М		y2	2	0							-7	3	1	2/3		—
									3
-М		yз	5	0				2			-1	2	8	5/2		2/3
	М→		-7	0				-5			8	-5	-9	—		-5/3

																		133
				-4		0		3		-5			1			-5	—	1
																Продолжение табл.3.9
											3-я итерация
-2		x1		8/3		1		0		-1/3			0			10/3	—	-1/11
-1		x2		2/3		0		1		-7/3			1			1/3	—	-7/11
-M		y3		11/3		0		0					0			22/3	1	-
											11/3
		M→		-11/3		0		0		-11/3			0			-22/3	—	- 1
				-6		0		0		2			-2			-6	—	6/11
				4-я итерация
-2		x1		3		1		0		0			0			4	∞	0
-1		x2		3		0		1		0						5	3	-
														1
1		xз		1		0		0		1			0			2	∞	0
				-8		0		0		0			-2			-10	—	-2
											5-я итерация
-2		x1		3
1		x4		3
1		x3		1
				-2		0		2		0			0			0

Четвертая программа (x1 = 3, x2=3, х3=1, х4=0) не является оптимальной, так как в оценочной строке, соответствующей 4-й итерации, двойственная оценка 4= -2<0. Переходим к «лучшей» программе. С этого момента мы уже отошли от расширенной задачи и перешли к решению исходной задачи, правда, замененной еще эквивалентной задачей максимизации.

На 5-й итерации получено оптимальное решение исходной задачи. Оно характеризуется следующими значениями переменных: x1=3, x2=0, х3=1, x4=3 и целевая функция F = 2 = min.

Из рассмотренных примеров видно, что оптимальное решение исходной задачи (если она разрешима) содержится в оптимальном решении расширенной М-задачи при нулевых значениях искусственныхпеременных.

134

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

иприменение теории двойственности

Вгл. I было указано, что стандартной задачей максимизации является задача

нахождения неотрицательных чисел x1, x2, . . . , xn, обращающих в максимум целевую функцию

F=c1x1+ c2x2+…+ cjxj.+…+cnxn

при условиях:

a x + a x

+ ...+ a

x

+ ...+ a

x

≤ b ,

11 1

12

2

1 j

j

1n

n

1

................................................................

ai1x1 + ai2 x2 + + aij xj + + ain xn ≤ bi ,

................................................................

a

x + a

m2

x

2

+ ...+ a

mj

x

j

+ ...+ a

x

n

≤ b

.

m1 1

mn

m

n

Или в краткой записи

F(x j ) = ∑cj x j

= max

j=1

при условии

(3.31)

(3.32)

(3.31')

n
∑aij x j	≤ bi ; i =					(3.32')
				1,m
j=1
x j ≥ 0;	j =
		1,n.

Аналогично формулируется стандартная задача минимизации, которая отличается в записи от стандартной задачи максимизации только знаками неравенств в системе ограничений (3.32). В стандартной задаче минимизации все ограничения-неравенства выражаются со знаками неравенств ≥.

Стандартной задаче максимизации соответствует стандартная задача минимизации, которая составляется по заданным числовым характеристикам аij, bi, cj исходной задачи следующим образом.

Будем называть исходную задачу (3.31), (3.32) прямой задачей. Каждому ограничению-неравенству (3.32) прямой задачи ставится в соответствие неотрицательная переменная двойственной задачи. Таким образом, число переменных y1, y2,…,yт в двойственной задаче равно числу ограничений в прямой задаче. Коэффициентами целевой функции двойственной задачи являются свободные члены b1, b2, ...,bт в ограничениях-неравенствах прямой задачи. Число ограничений-неравенств в двойственной задаче равно числу переменных в прямой задаче, так что каждой переменной xj ставится в соответствие j-е ограничение двойственной задачи. Коэффициентами этого j-го ограничения являются коэффициенты a1j, a2j,..., amj при переменной xj в системе ограничений (3.32) прямой задачи, т. е. j-и столбец Aj матрицы системы ограничений, а свободным членом — коэффициент cj при переменной xj в целевой функции (3.31) прямой задачи. Таким образом, двойственная задача по отношению к прямой задаче (3.31), (3.32) будет следующая задача.

Найти неотрицательные числа y1, y2,..., yт, обращающие в минимум целевую функцию

G = b1y1 + b2y2+ ...

+biyi+ ... +bmym

(3.33)

при условиях:

135

a y + a

y

+ ...+ a

y

+ ...+ a

y

≥ c ,

11 1

21

2

i1

i

m1

m

1

................................................................

a1 j y1 + a2 j y2

+ ...+ aij yi

+ ...+ amj ym

≥ c j

,

(3.34)

................................................................

a y + a

2n

y

2

+ ...+ a

in

y

i

+ ...+ a

mn

y

m

≥ c

.

1n 1

n

m

Или в краткой записи

G(yi ) = ∑bi

yi

= min

(3.33')

i=1

при условиях

n

∑aij yi ≥ c j ; j =

(3.34')

1,n

i=1

yi ≥ 0; i = 1,m.

Если по вышеуказанным правилам составить задачу двойственную по отношению к последней задаче (3.33), (3.34), то получится исходная задача (3.31), (3.32). Поэтому обе эти задачи называются взаимосопряженными. Какую из этих задач называть прямой и какую

— двойственной, зависит каждый раз от нашего соглашения.

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

Оптимальное решение задачи — это такое допустимое решение, при котором целевая функция имеет наибольшее (или наименьшее) значение среди множества значений целевой функции на бесчисленном множестве допустимых решений. Этими определениями мы постоянно будем пользоваться при изложении основных соотношений между взаимосопряженными стандартными задачами.

Лемма. Если x1, x2, ...,хn допустимое решение стандартной задачи на максимум (3.31), (3.32) и y1, y2,..., ym допустимое решение двойственной стандартной задачи на минимум (3.33), (3.34), то имеет место неравенство:

n		m
∑c j x j	≤∑aij x j yi	≤∑bi yi .	(3.35)
j=1	i, j	i=1

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

Д о к а з а т е л ь с т в о . Умножим неравенства (3.34) соответственно на неотрицательные числа x1, x2, ..., хп и просуммируем их; в результате получаем:

n	n	m
∑c j x j	≤∑x j ∑aij yi		= ∑aij x j yi .	(3.36)
j=1	j=1	i=1	i, j

Аналогично, умножая неравенства (3.32) соответственно на неотрицательные числа y1, y2,. . . , ym и суммируя их, получаем:

m	n	= ∑aij x j yi	m
∑ yi ∑aij xj			≤ ∑bi yi .	(3.37)
i=1	j=1	i, j	i=1

Сопоставление неравенств (3.36) и (3.37) дает нам неравенство (3.35) и лемма доказана. На основании доказанной леммы установим признак оптимальности допустимых

решений взаимосопряженных стандартных задач.

136

Теорема 1 (первая теорема двойственности). Если для допустимых решений x1, x2,

..., хп и y1, y2,...,ym взаимосопряженных стандартных задач

n	m
∑c j x j	= ∑bi yi	(3.38)
j=1	i=1

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

совпадают при некоторых их допустимых решениях, то оба эти решения являются оптимальными.

Доказательство. Пусть x'			, x'	,..., x'	— какое-нибудь другое решение	задачи	на
		1	2	m
максимум. Тогда по лемме
		n		m
		∑c j x	'j ≤	∑bi yi .
		j=1		i=1
Заменяя сумму в правой части этого неравенства равной суммой, на основании
соотношения (3.38) получаем:
		n		n
		∑cj x'j ≤		∑cj xj .
		j=1		j=1
Это неравенство показывает, что значение целевой функции па любом допустимом
решении x'	, x'	,..., x' получается	меньше,		чем на допустимом решении x1,	x2, ...,	хп,
1	2	m

удовлетворяющем условию теоремы. Это значит, что последнее допустимое решение задачи на максимум оптимальное. Аналогично можно доказать оптимальность допустимого решения y1, y2,. . . , ym двойственной задачи на минимум.

В теории линейного программирования не так просто доказывается, что условие равенства целевых функций (3.38) является не только достаточным, но и необходимым условием оптимальности допустимых решений; взаимосопряженных стандартных задач, т. е.

если x1, x2, ..., хп, и y1, y2,...,ym оптимальные решения взаимосопряженных задач, то

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

Теорема 2 (вторая теорема двойственности). Допустимые решения х1,х2,…,хn и y1, y2,...,ym взаимосопряженных стандартных задач являются оптимальными решениями этих задач тогда и только тогда, если в парах их двойственных условий

		n
yi	≥ 0,	∑aij x j	≤ bi .	(3.39)
		j=1
и
		m
x j	≥ 0,	∑aij yi	≥ c j .	(3.40)

i=1

первое условие является равенством, как только второе строгимнеравенством.

Разъяснение. Строгие неравенства имеют знак > или <. Доказательство. Допустим, что условия теоремы выполнены, т. е. что

		n
yi	= 0 при	∑aij x j	< bi .	(3.41)
		j=1
и
		m
x j	= 0 при	∑aij yi	> c j .	(3.42)

i=1

137

Умножим ограничения-неравенства (3.32) соответственно на y1, y2,...,ym, тогда при условии (3.41) все они превратятся в равенства

	n
bi yi = yi ∑aij x j , i = 1,2,...,m.
	j=1
Суммируя эти равенства, получим:
m	m	n
∑bi yi	= ∑ yi ∑aij x j		= ∑aij x j	yi .	(3.43)
i=1	i=1	j=1	i, j
Аналогичноизограничений-неравенств		(3.34),при условии(3.42),мыимеем
n	n	m
∑c j x j	= ∑x j	∑aij yi	= ∑aij x j	yi ,	(3.44)
j=1	j=1	i=1	i, j
а равенства (3.43) и (3.44) показывают, что
n	m
∑c j x j = ∑bi yi .
j=1	i=1

поэтому в силу теоремы 1 допустимые решения x1, x2, ..., хп и y1, y2,...,ym являются

оптимальными решениями.

Наоборот, если допустимые решения x1, x2, ..., хп и y1, y2,...,ym являются оптимальными решениями, то значения целевых функций при этих решениях должны быть одинаковы, т. е. неравенство (3.35) должно быть равенством:

n					m
∑c j x j = ∑aij x j				yi	=∑bi yi .	(3.45)
j=1		i, j			i=1
Из соотношения (3.45) получаем два равенства:
n		n	m
∑c j x j = ∑x j ∑aij yi ,
j=1		j=1	i=1
m		m	n
∑bi yi = ∑ yi			∑aij x j
i=1		i=1	j=1
или
n		m	− c j		= 0,	(3.46)
∑x j		∑aij yi
j=1	i=1

m

∑ yi bi

i=1

n
− ∑aij		= 0.	(3.47)
	xi
j=1

Поскольку числа x1, x2, ..., хп и y1, y2,...,ym являются допустимыми, слагаемые сумм (3.46) и (3.47) неотрицательны. Но сумма неотрицательных чисел может равняться нулю только в том случае, если каждое слагаемое равно нулю. Следовательно,

		m		= 0	для всех j.	(3.48)
x j		∑aij yi − c j
	i=1
		n
				= 0	для всех i	(3.49)
yi bi − ∑aij x j
		j=1

откуда следуют условия теоремы (3.41) и (3.42).

138

Более того, из равенств (3.48) и (3.49) следует, что при оптимальных xj>0 и yi>0 соответствующие им ограничения-неравенства должны быть равенствами.

Полученный результат можно интерпретировать с точки зрения экономики. Например, задача определения оптимального производственного плана выпуска п видов продукции при имеющихся запасах m видов сырья имеет модель типа задачи максимизации (3.31) — (3.32), в котором: свободные члены bi ограничений-неравенств (3.32)—объемы имеющихся запасов сырья; коэффициенты cj целевой функции (3.31)— прибыли, приходящиеся на единицу j-и продукции, производимой предприятием; коэффициенты aij в ограничениях (3.32) —затраты i-ro вида сырья на изготовление единицы j-и продукции. Целевая функция (3.31) представляет собой суммарную прибыль от реализации всех п видов продукции.

Каждое из ограничений-неравенств (3.32) выражает, что расход j-го вида сырья не может превышать его запаса bi.

Переменные yi двойственной задачи минимизации (3.33) — (3.34) можно интерпретировать как цены (относительные оценки) единицы i-го сырья, которые учитывают лимитированность и интенсивность расходования i-ro сырья при изготовлении всей продукции. Целевая функция (3.33) двойственной задачи (суммарная стоимость всего сырья, которым располагает производство) должна быть минимальной. Ограничения-неравенства (3.34) двойственной задачи выражают, что относительная стоимость сырья, затрачиваемая на производство единицы j-го продукта, должна быть не меньше получаемой от реализации единицы этого продукта прибыли сj

Равенство целевых функций (3.31) и (3.33) при оптимальных решениях обеих задач, означает, что максимальная прибыль получается при равной минимальной относительной стоимости всех видов сырья, в том числе и не полностью израсходованных.

Условие (3.41) означает, что если на предприятии имеется избыток i-ro вида сырья (i-e сырье расходуется при оптимальном плане производства не полностью), то цена его yi (относительная оценка, с точки зрения лимитированности и интенсивности расходования) должна опуститься до нуля.

Условие (3.42) означает, что если стоимость сырья, затрачиваемого на производство единицы j-го продукта, превосходит прибыль cj от реализации этой единицы, то j-и продукт производить не рационально (с точки зрения получения максимальной общей прибыли), т. е. должно быть в оптимальном плане производства xj=0.

Пусть теперь дана каноническая форма задачи линейного программирования, заключающаяся в нахождении неотрицательных чисел x1, x2, ..., хп обращающих в

максимум целевую функцию
F=c1x1+ c2x2+…+ cjxj.+…+cnxn	(3.50)
при условиях:

a

x

+ a

x

+ ...+ a

x

+ ...+ a

x

= b ,

11 1

12

2

1 j

j

1n

n

1

................................................................

ai1x1 + ai2 x2

+ ...+ aij xj

+ ...+ ain xn = bi ,

(3.51)

................................................................

a

x

+ a

m2

x

2

+ ...+ a

mj

x

j

+ ...+ a

mn

x

n

= b .

m1 1

m

В этой задаче система ограничений (3.51) представляет собой систему т<п линейных уравнений с п неизвестными. Двойственная задача по отношению к данной задаче (3.50) — (3.51) составляется так же, как и для стандартной задачи, с той лишь разницей, что на переменные у1, y2,..., ут не накладываются никакие ограничения по знаку, т. е. эти переменные могут иметь любой знак.

139

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

Требуется найти числа у1, y2,..., ут, обращающие в минимум целевую функцию

G = b1y1 + b2y2+

... +biyi+

... +bmym

(3.52)

при условиях:

a y + a

y

+ ...+ a

y

+ ...+ a

y

≥ c ,

11 1

21

2

i1

i

m1

m

1

................................................................

a1 j y1 + a2 j y2

+ ...+ aij yi

+ ...+ amj ym

≥ c j

,

(3.53)

................................................................

a y + a

2n

y

2

+ ...+ a

in

y

i

+ ...+ a

mn

y

m

≥ c

.

1n 1

n

Для задач (3.50), (3.51) и (3.52), (3.53) приемлема первая теорема двойственности, а также вторая теорема двойственности, в которой рассматриваются только пары двойственных условий (3.40).

Аналогично составляется задача двойственная к канонической задаче минимизации, с той лишь разницей, что в ограничениях-неравенствах двойственной задачи должны быть знаки неравенств ≤.

F(x j ) = ∑c j x j				m
	= min			G = ∑bi yi = max
				i=1
n				m
∑aij x j = bi ,	i =			∑aij yi ≤ c j , j =
		1,m			1,n
j=1				i=1

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

их знаками в задачах минимизации и с обратными знаками в задачах максимизации.

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

Применяя изложенные выше положения теории двойственности, проверим правильность решения задач, приведенных в § 1 и 2 данной главы.

Так, табл. 3.5 в 3.1 является последней симплексной таблицей, в которой

содержится результат решения задачи: найти максимум целевой функции
F = 3x1 + 4x2 + 6x3	(3.54)
при условиях:

x1≥0, x2≥0 x3≥0

							140
2x1 + 3x2			+ 5x3		≤ 1500,
x1 + 4x2			+ 2x3		≤ 1000,
							(3.55)
3x1 + 2x2			+ 3x3		≤ 1800,
4x	+ 2x	2	+ 5x	3	≤ 2200.
1

Из табл. 3.5 было получено следующее оптимальное решение:

x =	11800	; x		=	3300	;	x		=	2000	.	(3.56)
			2					3
1	29			29					29

В исходной симплексной табл. 3.2 базисными переменными являются дополнительные (выравнивающие) переменные x4, x5, x6, x7, которые соответствуют первому, второму, третьему и четвертому ограничениям-неравенствам. Следовательно, оптимальным решением двойственной задачи будет совокупность двойственных оценок y1= 4, y2= 5, y3 = 6, y4= 7 в последней симплексной таблице. Эти оценки находятся в последней строке табл. 3.5 в столбцах x4, x5, x6, x7. Откуда:

y	=	24	; y		=	7	;	y		= 0; y		=	8	.	(3.57)
						29							29
1	29			2					3		4
Составим двойственную задачу.
Найти минимум целевой функции
G = 1500y1 + 1000y2+1800y3+2200y4															(3.58)
при условиях: y1≥0, y2≥0; y3≥0; y4≥0

2y1 + y2 + 3y3 + 4y4							≥ 3,
3y1	+ 4y2		+ 2y3 + 2y4					(3.59)
							≥ 4,
5y + 2y		2	+ 3y	3	+ 5y	4	≥ 6.
1
Решения (3.56) и	(3.57) допустимы, так как они неотрицательны и условия (3.55)

и (3.59) соответственно выполняются. Значения целевых функций (3.54) и (3.58) для этих

	допустимых решении max F =	60600	и minG =	60600	одинаковы, следовательно, по
		29		29

первой теореме двойственности оба допустимых решения (3.56) и (3.57) действительно являются оптимальными. Значит задача решена правильно.

Проверим также правильность решения раскройной задачи (3.16), (3.17),

приведенной в 3.2, в которой требовалось найти минимум целевой функции
F = 0,5x1 + 0,6x2 + 0,4x3+0,2x4+0,3x5				(3.60)
при условиях:
x3	+ x4	≥ 500,
2x1 + x2 + 2x3	+ x4
		≥ 1000,		(3.61)
3x1	+ x5	≥ 200,
x2	+ 2x4 + x5 ≥ 400.

Решение этой задачи проведено так, что искусственные переменные (мы их обозначали уi в отличие от основных и дополнительных xj) у1, y2, у3, y4, которые являлись исходными базисными переменными в 1-й итерации в симплексной табл. 3.6, в результативной таблице 3.7 опущены. Поэтому оптимального решения двойственной задачи в окончательной табл. 3.7 не содержится. Однако мы можем проконтролировать