МО-Лекции

Построение опорного плана. Пусть необходимо решить задачу:

Q x	c1x1 c2 x2	... cn xn	min max
	a1,1x1 ...........	a1,n xn	b1
	................................................
	am,1x1 ..........	am,n xn	bm
	am 1,1x1 ...	am 1,n xn	bm 1
	.................................................
	am p,1x1 ........	am p,n xn	bm p .

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

0	b1	a1,1x1 ...............			a1,n xn
.........................................................
0 bm		am,1x1 ............			am,n xn
xn 1	bm 1		am 1,1x1	...	am 1,n xn
.........................................................
xn p	bm	p	am p,1x1	....	am p,n xn ,

где xn i 0 i 1, p .

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

			x1	x2	….	xS	.…	xn	1
0 =			a1,1	a1,2	….	a1,S	….	a1,n	b1
….			….	.…	….	.…	.…	.…	.…
0 =			am,1	am,2	….	am,S	….	am,n	bm
xm 1 =			am 1,1	am 1,2	….	am 1,s	….	am 1,n	bm 1
….			….	….	….	….	….	….	…
xm p =			am p,1	am p,2	….	am p,S	….	am p,n	bm p
Q		=	c1	c2	….	cS	….	cn	0
	x

90

Правила выбора разрешающего элемента при поиске опорного плана

1. При условии отсутствия «0-строк» (ограничений-равенств) и «свободных» переменных (т.е. переменных, на которые не наложено требование неотрицательности).

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

•Есть отрицательные элементы в столбце свободных членов, на-

пример bi 0 . В такой строке ищем отрицательный коэффициент ail , и этим самым определяем разрешающий столбец l . Если не найдем отрицательный ail , то система ограничений несовместна (противо-

речива).

• В качестве разрешающей выбираем строку, которой соответствует минимальное отношение

br	min	bi		bi	0 ,
arl		ail		ail
	i

где r – номер разрешающей строки. Таким образом, arl – разрешаю-

щий элемент.

• После того как разрешающий элемент найден, делаем шаг модифицированного жорданова исключения с направляющим элементом arl и переходим к следующей симплексной таблице.

2. В случае присутствия ограничений-равенств и «свободных» переменных поступают следующим образом.

•Выбирают разрешающий элемент в «0-строке» и делают шаг модифицированного жорданова исключения, после чего вычеркивают этот разрешающий столбец. Данную последовательность действий продолжают до тех пор, пока в симплексной таблице остается хотя бы одна «0-строка» (при этом таблица сокращается).

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

91

8.3.3. ВЫРОЖДЕННОСТЬ В ЗАДАЧАХ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Рассматривая симплекс-метод, мы предполагали, что задача линейного программирования является невырожденной, т. е. каждый опорный план содержит ровно m положительных компонент, где m – число ограничений в задаче. В вырожденном опорном плане число положительных компонент оказывается меньше числа ограничений: некоторые базисные переменные, соответствующие данному опорному

плану, принимают нулевые значения.
	Используя геометрическую интер-
	претацию для простейшего случая,
	когда n m 2 (число небазисных
	переменных равно 2), легко отличить
	вырожденную задачу от невырожден-
	ной. В вырожденной задаче в одной
	вершине многогранника условий пе-
	ресекается более двух прямых, опи-
	сываемых	уравнениями вида xi 0
Рис. 8.2. Допустимая область	(рис. 8.2). Это значит, что одна или
	несколько	сторон многоугольника,

свырожденными опорными

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

Аналогично при n m 3 в вырожденной задаче в одной вершине пересекается более трех плоскостей xi 0 .

В предположении о невырожденности задачи находилось

только	одно значение, соответствующее минимальному значению
min		bi		bi	0 , по которому определялся индекс выводимого из
		ail		ail
i

базиса вектора условий (переменной, выводимой из числа базисных).

В вырожденной задаче min	bi		bi	0 может достигаться на не-
	ail		ail
i

скольких индексах сразу (для нескольких строк). В этом случае в находимом опорном плане несколько базисных переменных будут нулевыми.

92

Если задача линейного программирования оказывается вырожденной, то при плохом выборе вектора условий, выводимого из базиса, может возникнуть бесконечное движение по базисам одного и того же опорного плана. Это так называемое явление зацикливания. Хотя в практических задачах линейного программирования зацикливание – явление крайне редкое, возможность его не исключена.

Один из приемов борьбы с вырожденностью состоит в преобразовании задачи путем «незначительного» изменения вектора правых частей системы ограничений на величины i , таким образом, чтобы зада-

ча стала невырожденной и в то же время, чтобы это изменение не повлияло реально на оптимальный план задачи.

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

Пусть переменную x j необходимо сделать базисной. Рассмотрим множество индексов E0 , состоящее из тех i , для которых достигается

0	min			bi			bi	0	. Множество индексов i , для которых выполня-
				ail			ail
	i
ется данное условие,									обозначим через E0 . Если E0		состоит из одного
элемента, то из базиса исключается вектор условий											Ai (переменная xi
делается небазисной).
	Если	E0				состоит более чем из одного элемента, то составляется
множество					E1 , которое					состоит из i E0 , на которых достигается
1	min		ai1				. Если E1			состоит из одного индекса k , то из базиса вы-
			a
	i E0
				il

водится переменная xk . В противном случае составляется множество

E2 и т. д.

Практически правилом надо пользоваться, если зацикливание уже обнаружено.

93

8.4. ДВОЙСТВЕННОСТЬ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

8.4.1. ПОНЯТИЕ ДВОЙСТВЕННОЙ ЗАДАЧИ

Рассмотрим задачу максимизации линейной формы и одновременно задачу минимизации:

Q x

p

x

max,

(10)

Ax

b,

x

0.

W

b

min,

u

u

(11)

A u

p,

0.

u

Задача (11) называется двойственной по отношению к прямой (10) (и наоборот!) [8].

Пример. Предприятие выпускает три вида продукции. Каждая продукция требует обработки на трех различных типах установок. Ресурс времени каждого типа установок ограничен. Известна прибыль от единицы каждого вида продукции p1, p2 , p3 . Если количество выпускае-

мой продукции каждого вида x1, x2 , x3 , тогда необходимо максимизировать прибыль

Q x p1x1 p2 x2 p3 x3 max

при ограничениях следующего вида:

a11x1 a12 x2 a13x3 b1 , a21x1 a22 x2 a23x3 b2 , a31x1 a32 x2 a33x3 b3 ,

x 0 ,

где b1, b2 , b3 – ресурсы времени установок первого, второго и третьего типов. Величины aij определяют количество ресурса времени уста-

94

новки i -го типа, которое необходимо для выпуска одной единицы продукции j -го вида.

Двойственная к ней задача будет иметь вид

W u b1u1 b2u2 b3u3 min

при ограничениях:

a11u1	a21u2	a31u3	p1,
a12u1	a22u2	a32u3	p2 ,
a13u1	a23u2	a33u3	p3 ,

u 0.

Здесь u1 – это оценка (цена), соответствующая одной единице ограни-

ченного ресурса по первой установке. И она равна величине, на которую могла бы возрасти суммарная прибыль, если бы количество этого ограниченного ресурса увеличилось на единицу, и если это увеличение было бы использовано оптимально. Иными словами, u1 – это количе-

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

личин u2 и u3 .

8.4.2.ПРЕОБРАЗОВАНИЯ ПРИ РЕШЕНИИ ПРЯМОЙ

ИДВОЙСТВЕННОЙ ЗАДАЧ

Пусть имеются прямая и двойственная задачи следующего вида:

Прямая задача:

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

pT x max

Q x

y

Ax b 0

x

0

Ax

b

x 0

Двойственная к ней задача:

T

v

AT

p 0

W

b

min

u

u

u

0

AT

p

u

u

0

u

95

Для ограничений прямой задачи симплексная таблица имеет вид

	x1	…	xs	…	xn	1
y1 =	a11	… a1s		… a1n		b1
…	…	…	…	…	…	…
yr =	ar1	… ars		… arn		br
…	…	…	…	…	…	…
ym =	am1	… ams		… amn		bm
Q x =	p1	…	ps	…	pn	0

Пусть ars – разрешающий элемент. Сделаем шаг модифицированного жорданова исключения и получим таблицу:

		x1	…	yr	…	xn	1
	y1 =	b11	… a1s		… b1n		b1,n 1
	…	…	…	…	…	…	…
	xs =	ar1	… 1		… arn		br
	…	…	…	…	…	…	…
	ym =	bm1	… ams		… bmn		bm,n 1
	Q x =	bm 1,1	…	ps	…	bm 1,n	bm 1,n 1 ,
где bij aij ars		arj ais , и всю данную таблицу следует разделить еще

на ars .

Симплексную таблицу для двойственной задачи запишем, развернув ее на 90 . Получаем:

	v1 =	…	vs =	…	vn =	W
u1	a11	…	a1s	…	a1n	b1
…	…	…	…	…	…	…
ur	ar1	…	ars	…	arn	br
…	…	…	…	…	…	…
um	am1	…	ams	…	amn	bm
1	p1	…	ps	…	pn	0

96

Пусть ars – направляющий элемент. Сделаем шаг обыкновенного

жорданова исключения (отличие от модифицированного состоит в том, что элементы в разрешающей строке меняют знаки, а в столбце знаки сохраняются; в остальном преобразование остается тем же):

			v1 =	… ur =		… vn =		W
	u1		b11	…	a1s	…	b1n	b1,n 1
	…		…	…	…	…	…	…
	vs		ar1	…	1	…	arn	br
	…		…	…	…	…	…	…
	um		bm1	…	ams	…	bmn	bm,n 1
1			bm 1,1	…	ps	…	bm 1,n	bm 1,n 1
Здесь bij		aij ars arj ais , и всю данную таблицу также следует разде-

лить еще на ars .

Замечание. Не следует забывать при преобразованиях, что в данном случае у нас таблица развернута.

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

	v1 = x1	…	vs = xs	…	vn = xn	W 1
u1 y1 =	a11	…	a1s	…	a1n	b1
…	…	…	…	…	…	…
ur yr =	ar1	…	ars	…	arn	br
…	…	…	…	…	…	…
um ym =	am1	…	ams	…	amn	bm
1 Q x =	p1	…	ps	…	pn	0.

Можно показать, что, решая основную задачу линейного программирования, решаем и двойственную к ней. И наоборот. Причем max Q min W .

97

8.4.3. ТЕОРЕМЫ ДВОЙСТВЕННОСТИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Основная теорема [8]. Пусть рассматривается пара двойственных задач:

Q x

p x

max,

Ax

b,

(12)

x

0.

W

b

min,

u

u

A

p,

(13)

u

0.

u

Если одна из этих задач обладает оптимальным решением, то и двойственная к ней задача также имеет оптимальное решение. Причем экстремальные значения соответствующих линейных форм равны: max Q min W .

Если же у одной из этих задач линейная форма не ограничена, то двойственная к ней задача противоречива.

Доказательство. Пусть основная задача (12) имеет конечное решение и получена окончательная симплексная таблица:

		u1 =	….	us =	vs 1 =	….	vn =	W =
		y1	….	ys	xs 1	….	xn	1
v1	x1 =	b1,1	….	b1,s	b1,s 1	….	b1,n	b1,n 1
….	….	….	….	….	….	….	….	….
vs	xs =	bs,1	….	bs,s	bs,s 1	….	bs,n	bs,n 1
us 1	ys 1 =	bs 1,1	….	bs 1,s	bs 1,s 1	….	bs 1,n	bs 1,n 1
….	….	….	….	….	….	….	….	….
um	ym =	bm,1	….	bm,s	bm,s 1	….	bm,n	bm,n 1
1	Q =	q1	….	qs	qs 1	….	qn	q0

98

Так как данная таблица, по предположению, соответствует опти-

мальному

решению задачи

(12),

то

b1,n 1

0, ..., bm,n 1

0

и

q1

0, ..., qn

0 .

При

этом

max Q

q0

достигается

при

y1

... ys

xs

1

...

xn

0 .

Рассмотрим полученную таблицу двойственной задачи. Полагая

значения переменных слева (небазисных) равными нулю.

v1

...

vs

us 1 ...

um

0 ,

найдем u1

q1

0,

…,

us

qs

0 ,

vs

1

qs 1

0 ,

…,

vn

qn

0 .

Следовательно, получено опорное решение:

u1

q1 , …, us

qs , us 1

0 , …, um

0 .

Из последнего столбца

W

b1,n 1v1 ...

bs,n 1vs

bs

1,n 1us

1 ...

bm,n 1um

q0

в точке

v1

...

vs

us 1 ...

um

0

что bi,n

0

будет минимальным в силу того,

1

i , i

1, m . Следова-

тельно, max Q

min W .

Пусть теперь линейная форма прямой задачи не ограничена, т. е.

для некоторой верхней переменной, например

ys , соответствующий

коэффициент qs

0 , а все коэффициенты этого столбца симплексной

таблицы неположительны: b1,s

0 ,

b2,s

0 , …,

bm,s

0 . Тогда из таб-

лицы для двойственной задачи:

us

b1,sv1

...

bs,svs

bs

1,sus

1 ...

bm,sum

qs

qs

0 ,

т. е. система ограничений двойственной задачи противоречива, поскольку из неотрицательности v1, ..., vs , us 1, ..., um следует неположи-

тельность us (нельзя сделать ее положительной), т. е. система несов-

местна.

Теорема доказана.

99