MO_conspect

i0 j0 maxi, j ij vj ui cij 0

среди тех клеток, для которых условие (1) не выполняется: i0 j0 25 5 .

Начиная с клетки i0 j0 , в направлении (для определенности) против часовой стрелки строится цепь из заполненных клеток таблицы (цикл). Совершая обход по цепи, помечаем клетки, начиная с i0 j0 , попеременно зна-

ками «+» и «–». Клетки со знаками «+» образуют положительную полуцепь, а со знаками «–» – отрицательную полуцепь. В клетках отрицательной полуцепи ищем минимальную перевозку

min xij .

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

							,
					xij
				xij' xij ,
						xij .
В нашем примере min x =20.
				ij
1. Новому плану соответствует таблица.
		v j	v	v			v			v		v5
					2			3			4
	ui		1
	u1		2		4				2		3		8
			30	80			10
	u2		3		5	–			6		6	+	2
							10			0		20
	u3		6		8				7		4		5
										30		10
	u4		3		4	+			2		1	–	4
												60

Затраты на перевозку по построенному плану равны:

Q 30 2 4 80 2 10 6 10 4 30 2 20 5 10 4 60 910 .

2. Строим систему потенциалов
v1 u1 2 ,		v2 u1 4 ,		v3 u1 2 ,
v3 u2 6 ,		v5 u2	2 ,	v4 u3 4 ,
v5 u3 5 ,		v5 u4	4 .
Полагаем	u1 0	и находим значения остальных потенциалов: u2 4 ,
u3 7 ,	u4 6 , v1 2 , v2 4, v3 2 ,			v4 3, v5 2.

3. Проверяем систему на потенциальность:

91

v1 u2 6 3,							v1 u3 9 6,					v1 u4 8 3 ,
v2 u2 8 5 ,							v2 u3 11 8,				v2 u4 10 4 ,
v3 u3 9 7 ,							v3 u4 8 2 ,				v4 u1 3 3,
v4 u4 3 1,							v5 u1 2 8,				v4 u2 1 6 ,
Система непотенциальна.											min x				=10. Улучшаем план.
1. Находим		i	j			43	6 , строим цикл,
														ij
		0	0
Новому плану соответствует таблица.
				v j			v	v			v		v				v5
									2			3		4
	ui						1
		u1					2		4			2			3		8
							30	80			10
		u2					3		5			6			6		2
											0		0				30
		u3					6		8			7	–		4	+	5
													30				10
		u4					3		4			2	+		1	–	4
											10						50

Затраты на перевозку по построенному плану равны:

Q30 2 4 80 2 10 2 10 4 30 2 30 5 10 4 50 850 .

2.Строим систему потенциалов

v1 u1 2 ,	v2 u1 4 ,		v3 u1 2 ,
v3 u4 2 ,	v5 u2	2 ,	v4 u3 4 ,
v5 u3 5 ,	v5 u4	4 .

Полагаем	u1 0			и находим значения			остальных потенциалов: u2 2,
u3 1,	u4 0, v1 2 , v2 4, v3 2 ,						v4 3 , v5 4 .
3. Проверяем систему на потенциальность:
v1 u2 0 3,						v1 u3 3 6 ,	v1 u4 2 3 ,
v2 u2 2 5 ,						v2 u3 5 8,	v2 u4 4 4,
v3 u3 3 7 ,						v3 u2 0 6 ,	v4 u1 3 3 ,
v4 u4 3 1,						v5 u1 4 8,	v4 u2 1 6 ,
Система непотенциальна.
1. Находим		i	j		44	2, строим цикл,	min x =30. Улучшаем план.
							ij
		0	0

Новому плану соответствует таблица.

92

	v j	v	v		v		v		v5
				2		3		4
ui		1
u1		2		4		2		3	8
		30	80		10
u2		3		5		6		6	2
									30
u3		6		8		7		4	5
							0		40
u4		3		4		2		1	4
					10		30		20

Затраты на перевозку по построенному плану равны:

Q30 2 4 80 2 10 2 10 1 30 2 30 5 40 4 20 790 .

2.Строим систему потенциалов

v1 u1 2 ,	v2 u1 4 ,		v3 u1 2 ,
v3 u4 2 ,	v5 u2	2 ,	v4 u4 1,
v5 u3 5 ,	v5 u4	4 .

Полагаем	u1 0 и находим значения		остальных потенциалов: u2 2,
u3 1,	u4 0, v1 2 , v2 4, v3 2 ,		v4 1, v5 4 .
3. Проверяем систему на потенциальность:
v1 u2 0 3,		v1 u3 3 6 ,	v1 u4 2 3 ,
v2 u2 2 5 ,		v2 u3 5 8,	v2 u4 4 4,
v3 u3 3 7 ,		v3 u2 0 6 ,	v4 u1 1 3,
v4 u4 1 1,		v5 u1 4 8,	v4 u2 1 6 ,

Система потенциальна, следовательно, план оптимален и окончательные затраты Qmin 790.

9.6. О вырожденности транспортной задачи

Определение 4. Допустимый опорный план транспортной задачи называется невырожденным, если число заполненных клеток транспортной таблицы, т.е. число положительных перевозок xij 0 , равно, где m – чис-

ло пунктов отправления, n – число пунктов назначения.

Определение 5. Если допустимый опорный план содержит менее m n 1 элементов xij 0 , то он называется вырожденным, а транспорт-

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

Следующая теорема позволяет определить вырожденность задачи до ее решения. m n 1

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

93

ный объем производства которой точно совпадает с суммарными потребностями некоторой группы пунктов потребления.

Другими словами, это условие означает, что для любых двух систем индексов i1, i2 ,..., it , j1, j2 ,..., jS , где t S n m , имеет место неравенст-

t	S
во ai	bj	. (Доказательство не сложно, от противного.)
k		k
k 1	k 1

Для решения транспортной задачи методом потенциалов строится система потенциалов v j ui cij , xij 0. Если опорное решение невы-

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

переменные, а xij 0 – небазисные. Если опорное решение вырожденно,

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

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

них также составить уравнения v j ui cij по условию (2) теоремы. Какие перевозки вида xij 0 включать в базисные? Выбираются такие клетки таблицы с xij 0 , чтобы из базисных переменных нельзя было организо-

вать ни одного цикла!

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

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

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

Контрольные вопросы

1.Сформулируйте транспортную задачу линейного программирования.

2.Что такое транспортная задача закрытого типа?

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

94

4.Сформулируйте теорему, на которую опирается алгоритм метода потенциалов?

5.В чем заключается проверка оптимальности опорного плана транспортной задачи? Что такое условие потенциальности?

6.Каким образом улучшается опорный план транспортной задачи?

7.Как можно проверить, является ли транспортная задача вырожденной?

8.К чему может привести вырожденность транспортной задачи?

10. Транспортная задача с ограничениями

10.1. Постановка задачи

Транспортная задача линейного программирования с ограничениями на пропускные способности путей сообщения может быть сформулирована следующим образом [9]. Необходимо минимизировать транспортные расходы

m n

Q X cij xij min

i 1 j 1

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

m
xij bj ,
i 1
n
xij ai ,
j 1
xij 0,	i 1, m,
xij dij ,	i 1, m,

	j 1, n,
	i 1, m,
								,
	j			1, n			,

j 1, n,

где cij - стоимость перевозки единицы продукции из пункта i в пункт j; xij

– планируемая величина перевозок из пункта i в пункт j (план перевозок X – матрица размерности m n ); b j - потребности в продукте в пункте j;

ai - запасы в пункте i; dij – ограничение на величину планируемой пере-

возки из пункта i в пункт j. Алгоритм состоит из 2-х этапов:

–определение опорного плана;

–определение оптимального плана методом потенциалов.

10.2.Метод потенциалов для определения оптимального плана

1.Пусть у нас есть опорный план. Для перевозок вида

0 xij dij ,

(1)

95

для определения потенциалов ui и v j соответствующих пунктов отправления и пунктов назначения составляется система уравнений

v j ui cij ,

(2)

инаходятся потенциалы ui и v j .

2.Для остальных клеток транспортной таблицы вычисляются значе-

ния

cij (v j ui ) .	(3)
Если для xij 0
ij cij (v j ui ) 0 ,	(4)
и для xij dij
ij cij (v j ui ) 0 ,	(4’)

то опорный план транспортной задачи оптимален.

Если эти условия не выполняются, то среди отрицательных чисел ij и ij выбираем наименьшее (максимальное по модулю). Пусть это наименьшее из чисел соответствует перевозке с индексами i0 и j0 .

Возможно 2 варианта:

а) наименьшее из чисел соответствует xi0 j0 0 ; б) наименьшее из чисел соответствует xi0 j0 di0 j0 .

Начиная с перевозки xi0 j0 , строим замкнутый цикл из базисных пере-

возок транспортной задачи (соответствующих (1)). В зависимости от случаев а) и б) дальнейшие действия отличаются.

а) В этом случае для улучшения плана мы должны ввести в базис перевозку xi0 j0 . Пометим перевозки цикла, начиная с i0 , j0 , поочередно зна-

ками “+” и “–” ( xi0 j0 помечаем знаком “+”).

Определим для отрицательной полуцепи

' min xij ,

для положительной полуцепи

" min dij xij

и возьмем

min ', ", di0 , j0 .

Для получения более экономичного плана перевозки положительной полуцепи увеличиваем на , а отрицательной – уменьшаем на .

После этого переходим к п.1.

б) В этом случае помечаем перевозку xi0 j0 помечаем знаком “–”, а ос-

тальные перевозки цикла помечаем последовательно “+” и “–”. Определим для отрицательной полуцепи

96

' min xij ,

для положительной полуцепи

" min dij xij .

Определяем

min ', ", di0 , j0 .

Увеличиваем перевозки положительной полуцепи на , а перевозки отрицательной полуцепи уменьшаем на . Переходим к п.1.

10.3. Построение опорного плана

Построение опорного плана состоит из 2-х этапов. Предварительного этапа, напоминающего метод минимального элемента, и ряд этапов метода потенциалов, применяемого к расширенной задаче.

Предварительный этап разбивается на несколько однотипных шагов.

Первый шаг. Среди элементов cij				матрицы C находим минималь-
ный. Если этим элементом является			ci j , то находим
			1 1			.
xi	j min ai , bj				, di j
1 1			1	1	1 1
Возможны 3 случая:
xi j ai		; xi j	bj ;		xi j	di j .
1 1	1	1 1	1		1 1	1 1
В первом случае все остальные перевозки строки xi j 0								j j1 ,
							1
во втором – все остальные перевозки столбца						xij 0	i i1 . В третьем
						1
случае заполняется только	xi	j . Далее вычеркиваем из матрицы C либо
	1 1

строку, либо столбец, либо элемент ci1 j1 . Преобразуем величины в таблице

a ,	i i ,		b	,	j j ,
ai1 i	1	b1j	j		1
ai1	xi1 j1 , i i1;		bj1 xi1 j1 ,		j j1.

Второй шаг состоит в проведении тех же операций применительно к невычеркнутым элементам матрицы C , не заполненным позициям матри-

цы X и величинам ai1 , b1j .

Шаги предварительного этапа следуют до полного заполнения матрицы X . Согласно процессу формирования матрицы X ее элементы удовлетворяют условиям

m

xij

bj ,

j

,

1, n

i 1

n

xij

ai ,

i

,

1, m

j 1

0 x d

i

,

j

.

ij

,

1, m

1, n

ij

97

Положим

	m
xm 1, j bj xij ,		j 1, n,
	i 1
	n
xi,n 1 ai xij ,		i	1, m			,
	j 1
m	n
xi,n 1 xm 1, j .
i 1	j 1

Если = 0, то очевидно, что матрица X является (опорным) планом задачи, которую обозначим Td .

Однако в общем случае > 0, и для получения искомого опорного плана задачи Td необходимо провести еще несколько итераций методом потенциалов.

Введем расширенную задачу Td (M ), которую образуем из Td						сле-
дующим образом. Присоединим к пунктам производства задачи Td						фик-
тивный пункт Am 1			с объемом производства am 1 , а к пунктам потреб-
		Bn 1 c	bn 1 . Пусть стоимость перевозки ci,n 1 ,	i			и
ления пункт					1, m
cm 1, j , j				0 .
	1, n	равна M (максимально большое число), а cm 1,n 1

Для этой задачи легко образовать опорный план, введя перевозки из i в n 1 и из m 1 в j , равные xi,n 1 и xm 1, j , и взяв xm 1,n 1 0 .

К задаче Td (M ) применяем метод потенциалов. При решении возможно 2 случая.

1.После ряда итераций строится опорный план X1 задачи Td (M ), согласно которому перевозка между Am 1 и Bn 1 равна .

В этом случае множество перевозок между пунктами ai и b j ,

i1, m , j 1, n , составят опорный план исходной задачи.

2.В оптимальном плане задачи Td (M ), который определяется за несколько итераций метода потенциалов, перевозка между пунктами

Am 1 и Bn 1 меньше .

В этом случае задача Td не имеет ни одного плана, т.е. неразрешима.

98

Пример.
		v1		v2		v3			v4			v5
	b j
	ai	15		30		35			20			1
u1	50	15) 14		35) 10		14)+ 2			10)	5	–	М
		12		23		14						1
u2	20	8)	11	4)	5	20)		4	12)	11		М
						20						0
u3	30	10)	9	7)	8	32)	12		20)	1		М
		3		7					20			0
u4	1		М		М			М		М +		0
		0		0		1			0			0
Должно быть 5+4 – 1 = 8 уравнений.
v1 u1 14 ,		v2 u1 10 ,						v1 u3 9 ,
v5 u1 M ,		v3 u4 M .
Задача вырожденная. Необходимо ввести в базис 3 перевозки:
x13 , нет циклов x13 = d13 =14;
x23 , нет циклов x23 = d23 =20;
x33 = 0, вводить нельзя, так как образуется цикл;
x34 , нет циклов x34 = d34 =20;
нельзя x21 , (т.к. x23 ), x22 , x24 , x25 , x35 , x41 , x42 …
Добавляем уравнения:
v3 u1 2 ,		v3 u2 4 ,				v4 u3 1.
Вычисляем:
u1 0	u4 2 M			v3 2
u2 2	v1 14			v4 6
u3 5	v2 10			v5 M
Проверяем условия потенциальности для xij							0 :
v4 u1 6 5	v1 u2 16 11,					v2 u2 12 5,
v4 u2 8 11,	v5 u2 M 2 M ,					v3 u3 3 12 ,
v5 u3 M 5 M ,		v1 u4 M 12 M ,						v2 u4 M 8 M ,
v4 u4 M 4 M ,		v5 u4 2M 2 M
Максимальное 45		2M 2 .
Проверяем для небазисных перевозок вида xij								dij :

99

v2 u3 5 8. Следовательно, 32		3.
45 32 , поэтому помечаем x45		(+)	и строим цикл,
min ', ", di		, j min 0,1, 0.
	0	0
Перевозку x13 из базиса, перевозку x45			в базис. Перевозка x45 вводится в
базис, но x45 0 .
Ищем новую систему потенциалов:
v1 u1 14 ,	v2 u1 10 ,			v1 u3 9 ,
v5 u1 M ,	v3 u4 M ,			v3 u2 4 ,
v4 u3 1 ,	v5 u4 0
u1 0	u4 M		v3 2M
u2 2M 4	v1 14		v4 6
u3 5	v2 10		v5 M

Проверяем условия потенциальности для xij 0 :

v4 u1 6 5 ,			v1 u2 18 2M 11, v2 u2 14 2M 5,
v4 u2 10 2M 11, v5 u2 4 M M ,				v3 u3 2M 5 12 ,
v5 u3 M 5 M , v1 u4 14 M M ,				v2 u4 10 M M .
33 2M 17 .
Проверяем для небазисных перевозок xij dij :
v2 u3 5 8,	v3 u1 2M 2.
Следовательно,	x		в базис.
min ', ", di		,33j	min 1, 3, 32 1.
	0	0

15+ 14		35	10	14	2	10	5	–	М
12	б	23	б	14				М	б
8	11	4	5	20	4	12	11		М
				20	б			0
10–	9	7	8	32	12	20	1		М
3	б	7		+		20	б	0
	М		М	–	М		М	+	0
0		0		1	б	0		0	б

100