МО-Лекции

Величины ui и v j называются потенциалами соответствующих

пунктов отправления и пунктов назначения. Условия (1) – (2) называются условиями потенциальности.

План X будем называть потенциальным, если для него существует система ui и v j , удовлетворяющая (1) – (2). Тогда теорема коротко

формулируется следующим образом.

Теорема. Для оптимальности плана транспортной задачи необходимо и достаточно, чтобы он был потенциален.

Доказательство. Достаточность. Пусть план X потенциален, так что существует система ui и v j , удовлетворяющая (1) – (2). Тогда для

любого допустимого плана X				[xij ]m		n
m n	m n					n	m			m	n
cij xij		v j	ui xij				v j	xij		ui	xij
i 1 j 1	i 1 j 1					j 1 i 1				i 1 j 1
n	m
v jbj		ui ai		для потенциального плана
j 1	i 1
		n	m	m			n
		v j		xij		ui	xij
	j	1	i 1	i	1		j 1
n m	m	n		n	m					n	m
v j xij		ui xij				v j		ui	xij		cij xij ,
j 1 i 1	i 1 j 1			j 1 i 1						j 1 i 1
т. е. стоимость перевозок по любому плану								X	не меньше стоимости
перевозок по потенциальному плану						X . Следовательно, план X оп-
тимален.

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

m n
Q X	cij xij min
i 1 j	1

110

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

	0 =	…	0 =	…	0 =	0 =	…	0 =	…	0 =	Q
	– u		– u		– u	– v1		– v j		– vn	1
	1		i		m
x11 y11 =	–1	…	0	…	0	1	…	0	…	0	c11
…	…	…	…	…	…	…	…	…	…	…	…
x1n y1n =	–1	…	0	…	0	0	…	0	…	1	c1n
…	…	…	…	…	…	…	…	…	…	…	…
xi1 yi1 =	0	…	–1	…	0	1	…	0	…	0	ci1
…	…	…	…	…	…	…	…	…	…	…	…
xij yij =	0	…	–1	…	0	0	…	1	…	0	cij
…	…	…	…	…	…	…	…	…	…	…	…
xin yin =	0	…	–1	…	0	0	…	0	…	1	cin
…	…	…	…	…	…	…	…	…	…	…	…
xm1 ym1 =	0	…	0	…	–1	1	…	0	…	0	Cm1
…	…	…	…	…	…	…	…	…	…	…	…
xmn ymn =	0	…	0	…	–1	0	…	0	…	1	Cmn
1 w =	a1	…	ai	…	an	b1	…	bj	…	bn	0

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

Получаем, что двойственная задача имеет вид

n		m
w	bj v j	aiui max
j	1	i 1
при ограничениях
yij ui v j	cij	0 , i 1, m , j 1, n ,

т. е. v j ui cij , i 1, m , j 1, n .

111

Пусть X [xij ]m n – оптимальное решение транспортной задачи.

Тогда на основании первой теоремы двойственности двойственная задача имеет оптимальное решение

u1*, ...,um* ; v1*, ...,vn* .

Убедимся, что эти числа являются потенциалами соответствующих пунктов транспортной задачи. Действительно, все ui*, v*j как опорное решение двойственной задачи удовлетворяют неравенствам (1).

Если x*ij 0 , то по второй теореме двойственности соответствующее ограничение двойственной задачи

yij* ui* v*j cij 0

обращается в строгое равенство

v*j ui* cij .

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

9.5. АЛГОРИТМ МЕТОДА ПОТЕНЦИАЛОВ

Алгоритм метода потенциалов состоит из предварительного этапа и повторяющегося основного этапа [9].

Предварительный этап

1.Каким-либо способом ищется допустимый план X (методом се- веро-западного угла или минимального элемента).

2.Для полученного плана строится система m + n чисел u1,..., um ,

v1, ...,vn , таких, что v j ui cij , xij 0 .

3. Построенная система ui и v j исследуется на потенциальность,

т. е. план X исследуется на оптимальность. Для этого проверяется

v j ui cij , xij 0 .

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

112

Основной этап

1. Улучшаем план,

т. е. от плана X переходим к плану X

такому,

что Q(X )

Q(X ) .

2.

Для плана

X

строим новую систему

ui , v j ,

i

1, m ,

j

1, n ,

такую, что v j

u j

cij ,

xij

0 .

3.

Исследуем систему

ui , v j

на потенциальность. Если система не-

потенциальна, то переходим на п. 1. Иначе – найден оптимальный план.

Найдем оптимальное решение задачи методом потенциалов, взяв в

качестве опорного план, построенный методом северо-западного угла

(1-й шаг предварительного этапа).

ui

1

u1

2

4

2

3

8

30

80

10

u2

3

5

6

–

6

+

2

10

20

u3

6

8

7

+

4

–

5

10

30

u4

3

4

2

1

4

60

2

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

v1

u1

2 ,

v2

u1

4 ,

v3

u1

2 ,

v3

u2

6 ,

v4

u2

6 ,

v4

u3

4 ,

v5

u3

5 ,

v5

u4

4 .

Число неизвестных больше числа уравнений, поэтому можем взять,

например,

u1

0 и найти значения остальных потенциалов,

u2

4 ,

u3

2 , u4

1, v1

2 , v2

4 , v3

2 , v4

2 , v5

3 .

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

v1

u2

6 3 ,

v1

u3

4 6 ,

v1

u4

3 3 ,

v2

u2

8 5 ,

v2

u3

6 8 ,

v2

u4

5 4 ,

v3

u3

4 7 ,

v3

u4

3 2 ,

v4

u1

2 3 ,

v4

u4

3 1 , v5

u1

3 8 ,

v5

u2

7 2 .

113

Система непотенциальна. Переходим к общему этапу.
1. Выбираем клетку, для которой неравенство вида															v j	ui	cij на-
рушается в наибольшей степени, т. е. находится число
		i		j		max		ij	v j		ui	cij	0
		0			0		i, j
среди	тех	клеток,			для		которых			условие			(1)	не	выполняется:
i0 j0	25	5 .
Начиная с клетки i0 j0 , в направлении (для определенности) против
часовой стрелки строится цепь из заполненных клеток таблицы (цикл).
Совершая обход по цепи,							помечаем клетки, начиная с								i0 j0 , попере-
менно знаками « + » и «–». Клетки со знаками « + » образуют положи-
тельную полуцепь, а со							знаками «–» – отрицательную полуцепь.
В клетках отрицательной полуцепи ищем минимальную перевозку
								min		xij .
Теперь улучшаем план следующим образом: перевозки отрицатель-
ной полуцепи уменьшаем на величину											,	а перевозки положительной
полуцепи увеличиваем на							. Новые перевозки
									xij		,
							xij		xij		,
									xij .
В нашем примере					min		xij	= 20.
1. Новому плану соответствует таблица
	ui	v1
							2
	u1		2					4		2					3		8
		30					80				10
	2		3					5			–				6	+	2
											10		0				20
	u3		6					8				7		30	4		5
																	10
	4		3					4			+	2			1		4
																	60
									114

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

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. Проверяем систему на потенциальность:
		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 .
		Система непотенциальна.
		1. Находим i				j	43		6 , строим цикл,						min	xij	= 10. Улуч-
					0	0
шаем план. Новому плану соответствует таблица
		ui
					v1
		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

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

Q

30

2

4

80

2

10

2

10

4

30

2

30

5

10

4

50

850 .

115

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 xij			= 30. Улуч-
					0 0
шаем план. Новому плану соответствует таблица
	ui												v j
					v1				v2				v3						v4			v5
	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
Затраты на перевозку по построенному плану равны
Q	30		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 .

116

Полагаем 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 1,

где	m – число пунктов отправления, n – число пунктов назначения.
	Определение 5. Если допустимый опорный план содержит менее
m	n 1 элементов xij 0 , то он называется вырожденным, а транс-
портная задача – вырожденной транспортной задачей.
	Следующая теорема позволяет определить вырожденность задачи
до ее решения.

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

Другими словами, это условие означает, что для любых двух систем

индексов 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 больше числа уравнений. При вырожденном опорном решении

117

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

собой базисные переменные, а xij 0 – небазисные. Если опорное ре-

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

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

xij 0 и для них также составить уравнения v j ui cij по условию

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

ных нельзя было организовать ни одного цикла!

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

рая находится следующим образом:

min xij . В вырожденной за-

даче это значение может достигаться на нескольких перевозках xij от-

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

КОНТРОЛЬНЫЕ ВОПРОСЫ

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

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

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

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

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

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

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

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

118

10.ТРАНСПОРТНАЯ ЗАДАЧА

СОГРАНИЧЕНИЯМИ

10.1. ПОСТАНОВКА ЗАДАЧИ

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

m

n

Q X

cij xij

min

i

1 j

1

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

m

xij

b j ,

j

1, n,

i

1

n

xij

a j ,

i

1, m,

j

1

xij

0,

i

1, m, j

1, n,

xij

dij , i 1, m,

j 1, n,

где cij

– стоимость перевозки единицы продукции из пункта i в пункт

j; xij

– планируемая величина перевозок из пункта i в пункт j (план

перевозок X – матрица размерности m

n ); b j – потребности в про-

дукте в пункте j; ai – запасы в пункте i;

dij – ограничение на величину

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

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

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

119