Кудрявтсев Методы оптимизатсии 2015

	9 + T min
при ограничениях	4 / D, / 0.
Прямая задача записывается как
	9 D T max

	*
при ограничениях	4 ( +.

Между прямой и двойственной задачей имеются взаимосвязи:

1.	Если прямая задача является задачей максимизации, то это
	двойственная задача минимизации.
2.	Коэффициенты целевой функции прямой задачи
	становятся правой частью ограничений	двойственной задачи.
				,	, … ,

3.Правые части ограничений прямой задачи становятся коэффициентами целевой функции двойственной задачи.

4.Матрица ограничений двойственной задачи получается путем транспонирования матрицы ограничений прямой задачи.

5.Знаки неравенств в ограничениях изменяются на противоположные.

6.Число ограничений двойственной задачи равно числу переменных прямой задачи, и наоборот.

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

3.10.1 Теорема двойственности

Если и	– допустимые решения прямой и двойственной за-
	]	] a
выполняются ограничения
дачи, т.е.	a	и 9
			,
то выполняются соотношения(
	9 D ( 9 +

или в векторном виде (используя скалярное произведение)

111

]		( на	, получим		D , ( +,
			a					и. левую части неравенства
	Доказательство. Умножив правую*
					, 4 ( Y , +Z.				.
Выполнив матрично- , 4 /							, D D ,
Аналогично можно записать								*
				, 4		, 4	, 4 .
Следовательно,
				векторные преобразования, получим
					*		/ D ,		.
				Y , +Z /		, 4

3.10.2 Основная теорема двойственности

задачи и

и

a

Если

— допустимые решения прямой и двойственной

D ,

Y+,

Z,

если

то

и

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

Доказательство.

В соответствии с предыдущей теоремой двойст-

a

В условии теоремы

D ,

( Y+,

Z.

венности для всех допустимых решений

справедливо неравенство

Следовательно,

–

Y+,

Z D ,

,

D , ( D , .

и тогда неравен-

сказано, что *

*

сто записывается в виде

a

*

Так как

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

,D ,

( Y+, Z.

справедливо

всех допустимых решений

Аналогично для

, , a

Y+, Za( Y+, Z.

неравенство может быть

(

то последнее

записано как

Следовательно,*

–*оптимальное решение.

3.10.3 Другие теоремы двойственности

Рассмотрим еще несколько важных теорем двойственности. Теорема. Если в оптимальном решении прямой задачи i-е огра-

ничение выполняется как строгое неравенство, то оптимальное значение соответствующей∑двойственной/ ? переменнойa 0. равно нулю,

т.е. если для некоторого i , то

112

a

]

a

]

Доказательство.

Умножив скалярно неравенство

(

на

9

(

, а неравенство

9

a , ]

a , ! 0,

, ]

на

, получим

В силу основной

a , 0.

, a

нулю. a , ]

, ]

a

двойственности

,

,

а

теоремы

также

9

, указанные неравенства

строго равны

(

a

Раскрыв скалярное произведение, запишем

, ]

a

]

) *

! A a

]

) *

! A P

(

]

]

A a

) *

! a

! 0.

) *

a

0

]

уравнения

! 0, 1,

Поскольку

, а

) *

, то левая часть

может быть равна нулю только в том случае, если каж-

]) * ! ? 0, то a

0.

дое слагаемое равно нулю. Следовательно, если для некоторого i

Аналогично доказывается теорема.

Если в оптимальном решении двойственной задачи j-е ограничение выполняется как строгое неравенство, то оптимальное значение соответствующей переменной∑ / a Gпрямой задачи0равно. нулю, т.е.

если для некоторого j , то

Теорема существования

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

Теорема двойственности

Допустимый вектор оптимальный тогда и только тогда, когда
	,		, a					что
имеется такое допустимое решение
в двойственной задаче			(		a		,
выполняется соотношение				.

113

3.10.4 Двойственный симплекс-метод

Рассмотрим прямую	( ” max
			0
	] ,
и двойственную
	a ” min
	]9a ,		a 0

задачи линейного программирования. Введем понятие сопряжен-

ного базиса (или «базис двойственной задачи»).

\]

&, –

Сопряженным

базисом

назовем систему из m линейно-

независимых векторов

^

матрицы ограничений прямой за-

]

a ,

–

^

дачи, для которой

решение системы уравнений вида

систему уравнений

(

] a или ] a ,

–

удовлетворяет

ограничениям вида

9

.

Разложив вектор

именно записав

по сопряженному базису, а

]

,

Y

(

найдем базисное решение

^ , которое называют псевдо-

планом (псевдоопорным

решением) прямой задачи, так как может

\

&, –

. Таким образом, псевдоплан

оказаться, что для всех

^

базисным решением относительно сопря-

прямой задачи является – ,

0

женного базиса.

С псевдопланом связана важная теорема.

0

f –

n,

^ и

Вектор

размерности

для

которого

при

при

^, является псевдопланом

тогда и только тогда, ко-

–

гда все оценки векторов (симплекс-разности с противоположным

	0,	1, .
знаком) больше или равны нулю, т.е.
	Y
	114

Доказательство. Для сопряженного базиса справедливо выра-

жение

4 9 :

D ,

- 2 3 .

Тогда

(

9 D D 9 F9 : G D

"#

\

"#

D 4

D .

9 [9 :

D 9 :

"#

0,

.

]

a ,

a 0

С учетом того, что

удовлетворяют всем ограниче-

1,

задачи (т.е.

9

ниям двойственной

a , | 1,

), получим

Признак оптимальности псевдоплана

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

Доказательство. Рассмотрим следующие преобразования:

9 + 9 [9 : \ 9 F9 : G 9 D .

∑

0

f –

∑

"#

"#

"#

Так как

при

^ , то

Y

и, следова-

, a

!.

,

тельно,

выполняется условие теоремы двойственности

(

Таким образом

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

	3.10.5	Обобщенный алгоритм двойственного
	симплекс-метода		\] &, –
	1. Отыскание сопряженного базиса				, решение системы
				^
	уравнений	]
		Y
			(
		115

^ псевдоплан является

\

&, –

\

0&,

\

&, –

и нахождение псевдоплана

^.

–

^ , и если

для всех

2. Исследование знаков

оптимальным планом, решение найдено,

завершаем работу алгоритма.

сопряженномуα

, – ,

f –

3. Если имеются отрицательные компоненты, то вычисление ко-

эффициентов

^

]

^

разложения небазисных векторов по

∑

α

] ,

f –

базису, т.е. решение системы уравнений

Y

^.

4. Если для

некоторого

, а все

, то задача не-

α

0

разрешима, завершаем

работу алгоритма.

4,

? 0

5. Если для некоторого

|

, но существует

, то

6. Определяется

min\

&.

строка на основании соотношения:

определяется направляющая4,

? 0

α

? 0

)0

)0

направляющий:

:столбец] 0

на основании соотно-

шения

: ,

] 0 ,

+

строки вычис-

элементов направляющей

т.е. среди отрицательных min

´

|

µ

ляются оценки

и находится минимальная из них. Следует

отметить, что

в алгоритме двойственного симплекс-метода все

<

=

7. 0Выполняется.

исключающее преобразование Гаусса по фор-

мулам, полностью идентичным (3.12) — (3.14). 8. Переход к шагу 2.

116

3.10.6 Табличный алгоритм двойственного симплекс-метода

Этап 1. Составляют симплекс-таблицу вида табл. 3.20, которая отличается от симплекс-таблицы обычного метода тем, что в столбце 2 могут находиться отрицательные значения. Следовательно, ис-

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

оказываются положительными. С другой стороны, векторы, распо-
	] a		det ] › 0
ложенные в столбцах 9 — 14, образуют сопряженный базис, так
как всегда можно решить ситему		, поскольку	.

№	1	2
1
2
3
4
5
6
7

										Таблица 3.20
	Начальная симплекс-таблица
	3	4	5	6	7		8	9	10	11	12	13	14
								1	0		0		0
:		:	:		:			0	1		0		0
:		:		:		:		0	0		1		0
:		:		:		:		0	0		0		1
:
	с	: с	: с		:		с	0 0			0		0

Этап 2. Проводится анализ псевдоопорного/ 0, | 1,решения, путем анализа знаков столбца 2. Если все , то решение найдено.

Этап

3. Определяется направляющая строка i путем выбора

˜/

|/

)0 )0

.

? 0, | 1, š

элемента среди

максимального по

модулю

отрицательного

, т.е. определяется вектор, выводимый из

сопряженного базиса:

:

:

] 0

Этап 4. Если для некоторого] min \

|

, а&все

, то задача

алгоритма.

α 0

неразрешима, завершаем работу 4,

? 0

117

Этап 5. Определяется направляющий столбец j (т.е. определяется вектор, вводимый в сопряженный базис). Для всех отрицатель-

ных элементов направляющей строки вычисляются оценки

<

=

Θ min

|: ] 0¹ .

и находится минимальная из них, т.е.

,

,

,

Обоснование использования

данного соотношения будет рас-

:

/

? 0

0

Выполняется

смотрено ниже. Следует отметить, что так как

, по доказан-

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

, то

0

.

Этап 6.

исключающее преобразование Гаусса по

формулам аналогичным (3.12) — (3.14):

▪ для всех элементов направляющей строки

/

,

Š 1,2, … , A A 1;

/

) *

) *

/) *

▪для 1,2, … , ;/всех элементов1; / направляющего0, 4 ›столбца, 4) * ) *

▪ для всех остальных элементов матрицы

, 4 › .

/

/

/ , Š ›

) *

) *

) *

) *

/) *

троки можно записать

В частности, для индексной с

/

, 4 › ,

0.

) *

) *

) *

) *

) *

/) *

Этап 7.

Формирование

новой симплексной таблицы, получив-

/

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

Выбор направляющего столбца основан на следующих соображениях. Для того чтобы при выполнении преобразования Гаусса и переходе от одного базиса к другому не нарушать требования сопряженного0, 4 1,2,базиса… , и, псевдоплана,A 1, A 2, …необходимо, A обеспечить условие

.

118

Преобразования

на к-й итерации выполняются по формулам

, M 1,2, … , A, A 1, A 2, … , A ..

/

:

0

/

0

. Если

? 0,

) *

0

:

что

/ ? 0

. Если

при

этом

, то

Заметим,

) *

же

, то запишем

: F

G.

:

:

:

:

) *

Тогда

0, если :

; ? 0 или

?

. Сле-

довательно, если в качестве j выбрать столбец с минимальным зна-

) *

чением отношения

, то все

.

4. Проводится

анализ псевдоопроного решения, а именно иссле-

0

ным

\/

0& для всех –

дование знаков

\/ &, –^

.

Если

^ , псевдоплан является оптималь-

планом.

4, / ? 0, а все / 0, то задача нераз-

Если для некоторого

решима.

Если для некоторого

, но существует

, то пере-

ходим к шагу 2 этапа 2.

4, / ? 0

/ ? 0

3.10.7 Пример использования двойственного симплекс-алгоритма

Рассмотрим применение двойственного симплекс-алгоритма для решения следующей задачи [4]:

Необходимо найти минимум целевой функции

при ограничениях		3	/ 2		T min
	C 8 12 18
	_	3	/ 1
			/ 0.
		, ,
	C 8	12	18 T max

Представим данную задачу в каноноческом виде:

119

_			3	.		2
			3			1
				-
			, , / 0.

Составим начальную симплекс-таблицу (табл. 3.21).

						Таблица 3.21
Базис	План
	-2	-1	0	-3	1		0
	-1	-1	-3	0	0		1
:))	0	8	12	18	0		0
	—	8	—	6	—		—

Для наглядности определения направляющего столбца в табли-

цу добавлена еще одна строка с вычислениями							(для отрица-
тельных значений			). Как видно, значения	индексной строки яв-
ляются	положительными, элементы плана отрицательны и, следо-
		/

ся отрицательные,

вательно, данный план является псевдоопорным. В качестве разрешающей строки выберем строку с максимальным по модулю отрицательным значением ( #). Среди элементов этой строки имеютпоэтому возможен дальнейший поиск другого

псевдоопорного решения, и необходимо найти минимальное отно-

шение		(для отрицательных значений / ). Вычисленные от-

ношения представлены в последней строке симплекс-таблицы. Выбирая минимальное значение из последенй строки, определим разрешающий столбец ( !). Разрешающие строка и столбец выделены темным фоном. В результате выполнения исключающего преобразования Гаусса переменная ! вводится в базис, а # выводится из базиса. Новая симплекс-таблица будет иметь вид табл. 3.22.

120