опорными (лежат вне многогранника решений). Первое же допустимое решение (опорный план) будет оптимальным.

Пример. Решить следующую задачу методом последовательного уточнения оценок:

L(x) = −2x1 − x2 → min, x1 − 2x2 +3 ≥ 0,

−3x1 −7x2 + 21≥ 0,

−x1 + x2 + 2 ≥ 0,

−5x1 − 4x2 + 20 ≥ 0,

xi ≥ 0,

i =1,2.

x1

x2

1

y3

x2

1

y1=

1

–2

3

y1=

–1

–1

5

y2 =

–3

–7

21

y2 =

3

–10

15

y3 =

–1

1

2

x1=

–1

1

2

y4 =

–5

–4

20

y4 =

5

–9

10

L =

–2

–1

0

L =

2

–3

–4

y3

y1

1

y3

y2

1

x2 =

–1

–1

5

x2 =

0,3

–0,1

1,5

y2 =

13

10

–35

y1=

–1,3

0,1

3,5

x1=

–2

–1

7

x1=

–0,7

–0,1

3,5

y4 =

14

9

–35

y4 =

2,3

0,9

–3,5

L =

5

3

–19

L =

1,1

0,3

–8,5

y3

y4

1

Ответ:

x2 =

5/9

–1/9

10/9

y1=

14/9

1/9

35/9

Lmin = −7

1

1

1

x1=

4/9

–1/9

28/9

;

, 1

3

x = 3

9

9

.

y2 =

–23/9

10/9

35/9

L =

1/3

1/3

–22/3

7.5. Методы решения транспортной задачи

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

m n

Q(X )= ∑∑cij xij → min

i=1 j=1

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

91

m
				j =1,n,
∑xij = bj ,
i=1
n											,
∑xij = ai ,				i =				,
					1,m
j=1
x ≥ 0,	i =		,	j =						,
		1,m					1,n
ij

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

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

bj – потребности в продукте в пункте j;

ai – запасы в пункте i.

n m

Предполагается, что модель закрытого типа, то есть ∑bj = ∑ai .

							j=1	i=1
	n		j		m
	∑	b		≠	∑ i		, то ее всегда можно привести к
Если модель открытого типа						a
j=1					i=1

закрытому типу введением фиктивного пункта производства или фиктивного пункта потребления:

n	m	m	n
Если ∑bj < ∑ai , то bn+1 = ∑ai			−∑bj ,
j=1	i=1	i=1	j=1
n+1	m
тогда ∑bj = ∑ai , причем ci,n+1 = 0 i .
j=1	i=1
n	m	n	m	n	m+1
Если ∑bj > ∑ai , то am+1 = ∑bj −∑ai ,				∑bj = ∑ai и cm+1, j = 0 j .
j=1	i=1	j=1	i=1	j=1	i=1

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

случае основная трудность бывает связана с числом переменных задачи (m×n) и числом ограничений (m+n). Поэтому специальные алгоритмы оказываются более эффективными. К таким алгоритмам относятся метод потенциалов и венгер-

ский метод.

Алгоритм метода потенциалов, его называют еще модифицированным распределительным алгоритмом, начинает работу с некоторого опорного плана транспортной задачи (допустимого плана перевозок). Для построения опорного плана обычно используется один из двух методов: метод северо-западного угла

или метод минимального элемента.

92

7.5.1. Метод северо-западного угла

Он позволяет найти некоторый допустимый план перевозок. Составим транспортную таблицу некоторой задачи.

	bj	30			80		20			30			90
	ai
	120	2			4		2			3			8
		30			80		10
	30			3	5		6			6			2
							10			20
	40			6		8			7	4			5
										10			30
	60			3		4			2		1		4
													60

В данном случае имеем задачу закрытого типа, т.к.

4	5
∑ai = 250 = ∑bj .
i=1	j=1

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

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

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

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

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

Q = 30×2 + 4×80 + 2×10 + 6×10 + 6×20 + 4×10 +5×30 + 4×60 =1010.

Естественно, что найденный план далек от оптимального.

7.5.2. Метод минимального элемента

В таблице отыскивается min{cij}и в первую очередь заполняется соответствующая клетка: xij = min{ai ,bj}. Затем вычеркивается остаток соответствующей строки, если ai < bj , или столбца, если ai > bj , и корректируем остатки запа-

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

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

93

	bj	30		80				20		30		90
	ai
	120	2		4				2		3		8
		30		80								10
	30	3		5					6		6	2
												30
	40		6			8			7		4	5
												40
	60		3			4		2		1		4
								20		30		10

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

Q = 30×2 + 4×80 +8×10 + 2×30 +5×40 + 2×20 +1×30 + 4×10 =830.

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

Определение 1. Набором называется произвольная совокупность перевозок транспортной таблицы.

Определение 2. Цепью называют такие наборы, когда каждая пара соседних клеток в цепи расположены либо в одном столбце, либо в одной строке.

Определение 3. Циклом называется цепь, крайние элементы которой находятся либо в одной строке, либо в одном столбце.

7.5.3. Метод потенциалов

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

Теорема. Для того, чтобы некоторый план X =[xij ]m×n транспортной зада-

чи был оптимальным, необходимо и достаточно, чтобы ему соответствовала такая система m+n чисел u1,u2,...,um; v1,v2 ,...,vn , для которой выполняются условия

vj −ui ≤ cij , i =			,	j =		,	(7.8)
	1,m				1,n
vj −ui = cij , xij		> 0.					(7.9)
Величины ui и		vj		называются потенциалами соответствующих пунктов

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

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

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

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

94

Достаточность. Пусть план X потенциален,							так что существует система
ui и vj , удовлетворяющая			(7.8–7.9).		Тогда	для любого допустимого плана
X ' =[x'ij ]m×n
m n	m n			n	m	m	n
∑∑cij x'ij ≥ ∑∑(vj −ui )x'ij = ∑vj ∑x'ij −∑ui ∑x'ij =
i=1 j=1	i=1 j=1			j=1	i=1	i=1	j=1
n	m	n	m	m	n
= ∑vjbj −∑uiai =		∑vj ∑xij − ∑ui ∑xij =
j=1	i=1	j=1	i=1	i=1	j=1
n m	m n		n	m		n m
= ∑∑vj xij − ∑∑ui xij =∑∑(vj −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

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

	0=	…	0=	…	0=	0=	…	0=	…	0=	Q =
	–u1		–ui		–um	–v1		–v j		–vn	1
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 = ∑bjvj −∑aiui → max
j=1	i=1

95

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

yij = ui −vj + cij ≥ 0 , i =1,m, j =1,n ,

т.е. vj −ui ≤ cij , i =1,m, j =1,n .

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

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

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

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

ственной задачи удовлетворяют неравенствам (7,8).

Если xij > 0, то по второй теореме двойственности соответствующее ограничение

yij* = ui* −v*j + cij ≥ 0

двойственной задачи обращается в строгое равенство

v*j −ui* = cij .

Алгоритм метода потенциалов

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

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

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

1.	Для полученного плана	строится система m+n чисел u1,...,um ,
v1, ...,vn , таких, что vj −ui = cij , xij > 0.
2.	Построенная система ui	и vj исследуется на потенциальность (то

есть план X исследуется на оптимальность). Для этого проверяется vj −ui ≤ cij ,

xij = 0.

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

не оптимален), иначе оптимальный план найден.
Основной этап.
1.	Улучшаем план, то есть от плана X переходим к плану X ' такому,
что Q(X ) ≥ Q(X ') .
2.	Для плана X '	строим новую систему u'	, v'	,	i =		,	j =		, такую,
						1,m			1,n
		i	j

что v'j −u'j = cij , xij > 0.

3. Исследуем систему ui' , v'j на потенциальность. Если система непотенциальна, то переходим на п.1. Иначе найден оптимальный план.

96

Найдем методом потенциалов оптимальное решение задачи, взяв в каче-
стве опорного план, построенный методом северо-западного угла (1-й шаг пред-
варительного этапа).
v j
	v	v	2	v		v	4		v5
ui	1			3
u1	2		4	2			3		8
	30	80		10
							–
u2	3		5	6				+	2
							6
				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,

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

Переходим к общему этапу.

1. Выбираем клетку, для которой неравенство вида vj −ui ≤ cij нарушается в наибольшей степени, то есть, находится число

αi0 j0 = maxi, j {αij = vj −ui −cij > 0}

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

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

97

клетки, начиная с i0 j0 , попеременно знаками + и –. Клетки со знаками + образу-

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

θ = min{xij−}.

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

xij− −θ, xij' = xij+ + θ,

xij .

В нашем примере θ = min{xij−}=20.

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

vj

	v	v	2		v			v	4				v5
ui	1				3
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. Проверяем систему на потенциальность:

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 ,
Система непотенциальна.
		98

1. Находим αi0 j0	= α43 = 6 , строим цикл,				θ = min{xij−}=10. Улучшаем план.
Новому плану соответствует таблица.
v j
	v	v	2	v			v	4		v5
ui	1			3
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 .

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. Находим αi0 j0	= α44 = 2, строим цикл, θ = min{xij−}=30. Улучшаем план.
Новому плану соответствует таблица.

99

v j

	v	v	2	v	v	4	v5
ui	1			3
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.

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

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

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

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

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

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

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

100

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

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

t	S
∑aik	≠ ∑bjk . (Доказательство не сложно, от противного.)
k=1	k=1

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

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

xij = 0 – небазисные. Если опорное решение вырожденно, то часть базисных пе-

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

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

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

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

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

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

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

101