optBook1

4.4. Способы получения начального допустимого базисного вектора101

ДОКАЗАТЕЛЬСТВО.

НЕОБХОДИМОСТЬ. Предположим, что в графе есть цикл, образованный вершинами

(i0; j0); (i1; j1); : : : ; (it; jt);

(77)

перечисленными в порядке обхода (i0 = it, j0 = jt). В цикле (77) могут быть вершины двух типов. Вершину (ik; jk) назовем угловой, если

соседние с ней вершины (ik¡1; jk¡1) и (ik+1; jk+1) не лежат на одной горизонтали или вертикали. В противном случае вершина неугловая. Если

в (77) нет угловых вершин, то, очевидно, справедливо равенство

pi1j1 ¡ pi2j2 + : : : ¡ pitjt = 0:

Если же в (77) не все вершины угловые, то аналогичное равенство можно записать, предварительно исключив из последовательности (77) все неугловые вершины. В обоих случаях система (76) линейной зависима. ДОСТАТОЧНОСТЬ. Пусть система (76) линейно зависима. Тогда найдется нетривиальный набор чисел ®1; : : : ; ®t, такой, что

®1pi1j1 + : : : + ®tpitjt = 0:

(78)

Пусть ®k 6= 0 для некоторого k 2 f1; 2; : : : ; tg. Так как ik-ая и (m + jk)-ая компоненты столбца pikjk равна единице, то для того, чтобы (78) выпол-

нялось, необходимо, чтобы в системе (77) нашлись столбец, у которого ik-ая компонента равна 1, и столбец, у которого (m + jk)-ая компонента равна 1. Таким образом, всякая вершина (ik; jk) с ®k 6= 0 смежна двум другим вершинам. Ввиду конечности числа вершин в графе, он содержит цикл.

Следствие 4.8. Пусть t = m + n ¡ 1. Для того, чтобы система

pi1j1 ; pi2j2 ; : : : ; pitjt

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

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

С каждой столбцовой базой транспортной задачи свяжем упорядоченный набор B, состоящий из пар вида (i; j), где pij — столбец матрицы

102	Глава 4. Транспортная задача

A, входящий в базу. Так, например, если система (76) образует базу, то

B = h(i0; j0); (i1; j1); : : : ; (it; jt)i :

Как и ранее, для краткости, B тоже будем называть базой.

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

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

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

Алгоритм 5. [Метод северо-западного угла]

Шаг 0.	Присвоить всем x значение 0. Положить ai			= ai, bj = bj (i =
	1; 2; : : : ; m; j = 1; 2ij; : : : ; n), B = 0/, i = 1, j = 1.			e
Шаг 1.	В B добавить (i; j).		e
Шаг 2.	e	e	e e
	Если ai < bj, то положить xij = ai, bj = bj ¡ ai, увеличить i на
		e	e
	1. Иначе положить xij = bj, ai = ai ¡ bj, увеличить j на 1.

Шаг 3. Если i < m или j < n, то перейти на шаг 1. Иначе конец. База B и начальное допустимое базисное решение X = (xij) построены.

Пример 4.9. Рассмотрим транспортную задачу, в которой

a1 = 65;	a2 = 50;	a3 = 70;
b1 = 40;	b2 = 85;	b3 = 60;
c11 = 4;	c12 = 5;	c13 = 6;
c21 = 2;	c22 = 3;	c23 = 1;
c31 = 3;	c32 = 3;	c33 = 3:

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

4.4. Способы получения начального допустимого базисного вектора103

	40	85	60
65	4	5	6
	40	25
50	2	3	1
		50
70	3	3	3
		10	60

Слева от таблицы указаны величины ai, сверху записаны bj. В левом верхнем углу каждой клетки (i; j) стоит cij. Если (i; j) 2 B, то в правом нижнем углу соответствующей клетки записана величина xij. Построена база

B = h(1; 1); (1; 2); (2; 2); (3; 2); (3; 2)i :

Очевидно, шаг 1 алгоритма 5 будет выполняться m+n¡1 раз. При заполнении очередной клетки мы переходим либо к соседней справа, либо к соседней снизу, откуда следует, что граф, соответствующий построенному множеству B, не содержит циклов. Выполнение ограничений транспортной задачи очевидно. Итак, B является базой.

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

Вметоде минимального элемента используется эвристическое соображение, по которому сначала заполняются клетки xij с меньшим значе-

нием cij.

Алгоритм 6. [Метод минимального элемента]					e	f	; ;e: : : ; mg
	Ji = f1;;2;;::::::;;ng.			B
Шаг 0.	Присвоить всем xij		значение 0. Положить ai			= ai, bj		= bj
	( = 1 2	m; j = 1; 2; : : : ; n),			= 0/, I = 1 2				,
Шаг 1.	Выбрать r, s, такие, что crs = min fcij : i 2 I; j 2 Jg. Добавить
	(r; s) в B.

104			e e	Глава 4.	Транспортная задача
Шаг 2.				e e	e e
	Положить xrs = min ar; bs			, ar = ar ¡ xrs, bs = bs ¡ xrs. Если
	ar = 0, то исключитьnr из I.oИначе исключить s из J.
Шаг 3.	Если	= 0/ и	= 0/, то перейти на шаг 1.
	e	I 6	J 6

Шаг 4. [В вырожденном случае надо дописать еще несколько нулей.] Если I = 0/, то добавить в B пары вида (r; j), где j принимает все значения из J, кроме одного (любого). Иначе добавить в B пары вида (i; s), где i принимает все значения из I, кроме одного (любого). База B и начальное допустимое базисное решение X = (xij) построены.

Пример 4.10. Рассмотрим задачу из примера 4.9. Метод минимального элемента приводит к следующей базе и следующей таблице:

B = h(1; 2); (1; 3); (2; 3); (3; 1); (3; 2)i

40 85 60

65

4 5 6

55 10

2 3 1

50

50

70

3 3 3

40 30

Покажем, что таблица X, полученная по алгоритму 6, является допустимым базисным решением. Пусть в графе, построенному по множеству B, существует цикл, и пусть

(i1; j1); (i2; j2); : : : ; (is; js)

— его угловые клетки в порядке обхода. Далее пусть (ik; jk) — клетка цикла, которая заполнилась раньше других клеток цикла. Тогда в момент

e

перед заполнением клетки (ik¡1; jk¡1) было eajk¡1 =6 0 и bjk¡1 =6 0, а в e

момент перед заполнением клетки (ik+1; jk+1) было eajk+1 =6 0 и bjk+1 =6 0. Но этого не может быть, так как после заполнения клетки (ik; jk) либо

aik , либо bjk обратилось в нуль.

4.5. Пересчет базисного решения при изменении базы

105

4.5. Пересчет базисного решения при изменении базы

Пусть X — базисное решение, соответствующее базе

B = h(i1; j1); (i2; j2); : : : ; (im+n¡1; jm+n¡1)i :

Добавим к базе еще один элемент (i; j), тогда граф, соответствующий полученной системе, по утверждению 4.7 содержит цикл, очевидно, единственный. Для определенности будем считать, что угловыми элементами этого цикла являются

(i; j); (i1; j1); (i2; j2); : : : ; (is¡1; js¡1);

причем

i = i1; j1 = j2; : : : ; is¡2 = is¡1; js¡1 = j

(см. рис. 4.1). Заметим, что s — четно. Определим вектор X0 = (x0ij) следующим образом:

x0ij = xij + µ; x0i1j1 = xi1j1 ¡µ; x0i2j2 = xi2j2 + µ; : : : ; x0is¡1js¡1 = xis¡1js¡1 ¡µ;

где µ — некоторое положительное число. Остальные компоненты вектора X0 будут совпадать с соответствующими компонентами X. Очевидно, X0 удовлетворяет все ограничениям транспортной задачи (69) кроме, быть может, ограничений x0ij ¸ 0. Для того, чтобы эти ограничения были выполнены, необходимо, чтобы

xikjk ¡ µ ¸ 0; (k = 1; 3; : : : ; s ¡ 1):

(79)

Если положить

µ = min fxikjk : k = 1; 3; : : : ; s ¡ 1g ;

то, очевидно, условие (79) будет выполнено и, кроме того, хотя бы одна из компонент, для определенности, x0ir;jr , обратится в ноль. В базе B заменим (ir; jr) на (i; j). Полученная таким образом база B0 соответствует допустимому базисному решению X0. Заметим, что если база B0 невырождена, то (ir; jr) определяется единственным образом.

106	Глава 4. Транспортная задача
(i; j)	(i1; j1)
	(i2; j2)
(is¡2; js¡2)
(is¡1; js¡1)

Рис. 4.1.

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

Вэтом разделе мы опишем способ нахождения элемента, вводимого

вбазу. Этот способ называется методом потенциалов.

Идея метода заключается в следующем. Для текущей базы B находятся соответствующие ей цены (см. определение 2.29 из раздела 2.5), называемые в данном случае потенциалами. Затем с помощью этих цен, используя утверждение 2.30, строятся текущие относительные оценки (элементы нулевой строки симплекс-таблицы), среди которых выбирается отрицательная.

Перейдем к более детальному описанию метода. Обозначим потенциалы, соответствующие верхним m строкам матрицы A, через ui (i = 1; 2; : : : ; m), а потенциалы, соответствующие нижним n строкам матрицы A, через vj (j = 1; 2; : : : ; n). Напомним, что система ограничений транспортной задачи переопределена. Согласно замечанию 2.34 в качестве цен

e

(потенциалов) можно взять произвольное решение системы uB = cB, которая в нашем случае имеет вид:

ui + vj = cij

(i; j) 2 B:

Ранг этой системы совпадает с рангом матрицы A и равен m+n¡1, следовательно, количество свободных переменных равно 1. Нетрудно видеть, что в качестве свободной переменной можно выбрать любую, полагая ее равной произвольному значению. Действительно, в силу того, что граф,

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

107

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

Формула bc = c ¡ uA для нахождения относительных оценок bcij в нашем случае приобретает вид: bcij = cij ¡ ui ¡ vj. Если bcij ¸ 0 (i = 1; 2; : : : ; m, j = 1; 2; : : : ; n), т. е.

ui + vj · cij

(i = 1; 2; : : : ; m; j = 1; 2; : : : ; n);

(80)

то текущая база B оптимальна. В противном случае выберем произвольную пару (i; j) 2= B, для которой bcij < 0 и по способу, описанному в разделе 4.5, найдем элемент, выводимый из B.

Замечание 4.11. Запишем ЗЛП, двойственную (69). Обозначим переменные двойственной задачи, соответствующие верхним m строкам матрицы A, через ui (i = 1; 2; : : : ; m), а переменные, соответствующие нижним n строкам матрицы A, — через ui (i = 1; 2; : : : ; m). Двойственная ЗЛП выглядит следующим образом:

	m	n	¶
max	å aiui + å bjvj
ui + vj · cij	µi=1	j=1
	(i = 1; 2; : : : ; m; j = 1; 2; : : : ; n):

Заметим, что условия оптимальности (80) текущей базы совпадают с условиями допустимости вектора (u1; : : : ; um; v1; : : : ; vm).

Пример 4.12. Решим методом потенциалов транспортную задачу из примера 4.9, опираясь на начальную базу

B(0) = h(1; 2); (1; 3); (2; 3); (3; 1); (3; 2)i ;

найденную в примере 4.10. Для начального базисного решения получаем систему уравнений

>	u1	+ v2 = 5;
>		+ v3	= 6;
8 u1
<
> u2		+ v3 = 1;
>		+ v1	= 3;
> u3
>
>
:		+ v2	= 3;
> u3

из которой, полагая u1 = 0, последовательно получаем v2 = 5, v3 = 6, u2 =

¡5, v1 = 5, v5 = 5. Ограничение ui + vj · cij не выполнится, например, при i = 1, j = 1. Поэтому вводим (1; 1) в базу. Чтобы определить, какой

элемент будет выведен из базы, найдем возникший цикл:

108				Глава 4.		Транспортная задача
	40		85	60
	4	5		6		= 0
65	+		55¡	10	u1
50	2	3		1	u2	= ¡5
				50
70	3	3	+	3	u	= 2
	¡ 40		30		3	¡

v1 = 5 v2 = 5 v3 = 6

Минимальным среди элементов xij, стоящих в клетках, отмеченных символом «¡», является x31 = 40, поэтому исключим (3; 1) из базы. Получаем новую базу B(1) = h(1; 2); (1; 3); (2; 3); (1; 1); (3; 2)i и пересчитываем базисное решение:

	40	85		60
	4	5	6
65	40	+ 15		10¡	0
50	2	3	1		¡5
				50
70	3	3	3	+	¡2
		¡ 70
	4	5		6

Вычислим текущее значение потенциалов. Как и выше, значения переменных ui запишем справа от таблицы, а значения переменных vj — снизу от таблицы. Ограничение ui + vj · cij не выполняется при i = j = 3. Поэтому вводим в базу (3; 3). Чтобы определить, какой элемент будет выведен из базы, в образовавшемся цикле среди xij, отмеченных знаком «¡», определим минимальный. Им является x13 = 10, поэтому исключим (1; 3) из базы. Получаем новую базу B(2) = h(1; 2); (3; 3); (2; 3); (1; 1); (3; 2)i, пересчитываем базисное решение и текущие значения потенциалов:

4.6. Метод потенциалов					109
		40	85	60
65	4	5		6	0
		40	25
50	2	3		1	¡4
				50
70	3	3		3	¡2
			60	10
		4	5	5

Все неравенства ui + vj · cij выполнены, следовательно, текущее базисное решение

x11 = 40; x12 = 25; x23 = 50; x32 = 60; x33 = 10;

x13 = x21 = x22 = x31 = 0

оптимально. Значение целевой функции равно

4 ¢ 40 + 5 ¢ 25 + 1 ¢ 50 + 3 ¢ 60 + 3 ¢ 10 = 545:

Пример 4.13. Рассмотрим пример решения вырожденной задачи. Приведем соответсвующие таблицы. Начальное базисное решение найдем методом минимального элемента.

	40	85	60		40		85	60
50	2	1	5	50	2	1	5		0
		50					50
60	3	4	3	60	3	4	3	+	2
	40		20		¡	40		20
	4	6	6		4	6	6
75		35	40	75	+		35	40¡	5
						1	1	1

110	Глава 4. Транспортная задача

	40		85	60
50	2	1		5	0	50
			50
60	3	4	+	3	4	60
	¡ 0			60
	4	6		6
75	+ 40		35¡		5	75
	¡1		1	¡1

40	85	60
2	1	5	0
	50
3	4	3	4
	0	60
4	6	6	5
40	35
¡1	1	¡1