MO_conspect

4.Все остальные элементы симплексной таблицы вычисляются по следующей формуле:

a

aij arl

arj ail

a

arj ail

.

ij

arl

ij

arl

x4

x5

1

x1 =

1

–2

1

Разрешающий элемент, соответствую-

x2 =

–2

1

2

щий замене базисной переменной x2

на

x3 =

3

1

3

небазисную переменную x5 .

Q x =

-1

1

0

x4

x2

1

x1 =

–3

2

5

Разрешающий элемент, соответствую-

x5 =

–2

1

2

щий замене базисной переменной x3

на

x3 =

5

–1

1

небазисную переменную x4 .

Q x =

1

–1

–2

x3

x2

1

x1 =

3/5

7/5

28/5

Все коэффициенты в строке целевой

x5 =

2/5

3/5

12/5

функции отрицательны, т.е. мы нашли

x4 =

1/5

–1/5

1/5

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

Q x =

–1/5

–4/5

–11/5

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

Q x c1x1 c2 x2 ... cn xn min max

a1,1 x1 ........... a1,n xn b1

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

am,1 x1

.......... am,n xn bm

am 1,1 x1 ... am 1,n xn bm 1

.

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

........ am p,n xn bm p

am p,1 x1

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

71

			0 b1 a1,1 x1 ...............				a1,n xn
		.........................................................
			0 bm am,1 x1 ............				am,n xn		,
			x	b	a	x	a	x
			n 1	m 1	m 1,1	1		m 1,n n
		.........................................................
							am p,n xn
		xn p bm p am p,1 x1 ....
где 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
	x				….		….		0

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

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

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

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

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

на (противоречива).

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

b	b			b
r	min	i		i	0 ,
arl	i ail			ail

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

72

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

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

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

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

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

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

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

рон многоугольника условий стягиваются в точку.

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

костей xi 0 .

В предположении о невырожденности задачи находилось только одно значение, соответствующее минимальному значению

73

b			b
min	i		i	0 , по которому определялся индекс выводимого из ба-
i ail			ail

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

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

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

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

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

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

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

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

	b			b
0	min	i		i	0 . Множество индексов	i , для которых выполняется
	i ail			ail
данное условие, обозначим через E0 . Если E0						состоит из одного элемента,

то из базиса исключается вектор условий Ai (переменная xi делается небазисной).

	Если		E0		состоит более чем из одного элемента, то составляется
множество			E1 ,		которое состоит из i E0 , на	которых достигается
1	min	ai1		. Если E1 состоит из одного индекса		k , то из базиса выво-
	i E0 ail

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

т.д.

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

74

u 0.

Q x p1x1 p2 x2 p3 x3 max

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

8.4.1. Введение

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

Q x p

x

max

W

u

b

u

min

Ax b,

(1)

A

p,

(2)

u

x 0

0

u

Задача (2) называется двойственной по отношению к прямой (1) (и наобо-

рот!) [8].

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

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

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

a11x1 a12 x2 a13 x3 b1 , a21x1 a22 x2 a23 x3 b2 , a31x1 a32 x2 a33 x3 b3 ,

x 0 ,

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

вида.

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

W u b1u1 b2u2 b3u3 min

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

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

75

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

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

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

8.4.2.Преобразования при решении прямой и двойственной задач

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

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

Q x pT x max

Ax b

x 0

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

W u bT u min AT u p

u 0

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

yAx b 0

x0

v AT u p 0 u 0

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

	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

76

…	…	…	…	…	…	…
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

Пусть 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 .

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

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

77

	v1 =	…	vs =	…	vn =	W
	x1		xS		xn	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 .

8.4.3. Теоремы двойственности

8.4.3.1. Основная теорема двойственности линейного программирования

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

Q x p x max

u min

W u b

Ax b

(1)

A u p

(2)

x 0

u 0

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

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

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

		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

78

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

мальному	решению	задачи		(1), то 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 1 0 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 (нельзя сделать ее положительной). То есть, система несовместна.

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

8.4.3.2. Вторая теорема двойственности

Теорема [8]. Если хотя бы одно оптимальное решение одной из двойственных задач обращает i -е ограничение этой задачи в строгое неравенство, то i -я компонента (т.е. xi или ui ) каждого оптимального решения вто-

рой двойственной задачи равна нулю.

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

Т.е. оптимальные решения x* и u * пары двойственных задач удовлетворяют условиям

79

	m
			0,	j 1, n,
	x j aijui p j
	i 1

n
ui aij x j	bi	0,	i 1, m.
j 1

(1)

(2)

Доказательство: Пусть x*

и

*

– оптимальные решения пары двой-

u

ственных задач. Тогда для

n

Q x p j x j

max ,

j 1

m

W

biui

min

u

i 1

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

ai1 x1 ai 2 x2 ... ain xn bi ,

i

1, m

,

x*j 0,

j 1, n,

(3)

a1 j u1 a2 j u2 ... amj um p j

.

, j

1, n

,

ui* 0,

i 1, m.

Умножим (3), соответственно, на ui и x j

и просуммируем получен-

ные выражения:

n

m

n

m

p j x j aijui x j

biui .

(4)

j 1

i 1 j 1

i 1

Из основной теоремы двойственности следует

n

m

p j x j

biui .

(5)

j 1

i 1

И с учетом (4) получаем:

n

n

m

p j x j

aijui x j ,

j 1

j 1

i 1

m

m

n

biui

aij x j ui .

i 1

i 1

j 1

Первое из этих выражений можем переписать в виде

n

m

x j

aijui p j 0

,

j 1

i 1

и так как все x и выражения в скобках неотрицательны, то опуская , по-
j
лучим:
	m
			0,	j 1, n .
x j	aijui p j
	i 1

80