Постановка и основные свойства транспортной задачи

border="0" /> и столбца . Далее вычисляем . На этом (k+1) – й шаг заканчивается. Описанный процесс повторяется до тех пор, пока матрица Х не будет заполнена полностью.

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

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

Формальное описание алгоритма. Элементы матрицы нумеруют, начиная от минимального в порядке возрастания, а затем в этом же порядке заполняют матрицу Х₀.

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

Дале этот процесс повторяют с незаполненной частью матрицы Х₁.

Пример 1. Найти начальный базисный план методом минимального элемента для Табл. 3. следующей задачи.

Таблица. 3.

Ai Bj	1	2	3	4	Bj / ai
1	7(10)	8(11)	5(7)	3(5)	11
2	2(3)	4(4)	5(8)	9(12)	11
3	6(9)	3(4)	1(1)	2(2)	8
Ai / bj	5	9	9	7	bj ai

Цифры в скобках указывают порядок заполнения элементов в матрице Х₀ (табл. 3.4).

Соответствующее значение целевой функции равно

 3*8 + 1*5 + 3*7 + 5*2 + 6*4 + 8*1 = 92

Таблица 4

Х0
	0	3	1	7	11	4	3	0
	5	6	0	0	11	6	0
	0	0	8	0	8	0
	5	9	9	7
	0	3	1	0
		0	0

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

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

Рассмотрим два случая.

1. Вырожденный план является начальным Х₀. Тогда выбирают некоторые нулевые элементы матрицы Х₀ в качестве базисных так, чтобы при этом не нарушалось условие базисного плана. Число этих элементов равняется . Далее данные элементы заменяют на  (где  – произвольное, бесконечно малое число) и рассматривают их как обычные базисные элементы плана. Задачу решают как невырожденную, а в последнем оптимальном плане Х_k вместо пишут нули.

2. Вырожденный план получается при построении плана Х_k+1 на базе Х_k, если цепочка в плане Х_k содержит не менее двух минимальных нечетных элементов. В таком случае в матрице Х_k+1 полагают равным нулю только один из этих элементов, а остальные заменяют на , и далее решают задачу как невырожденную. Если на k-м шаге , то при переходе от Х_k к Х_k+1 значение целевой функции не изменяется, а в базис вводится элемент , для которого перевозка станет равной .

Пример 2. Решим Т-задачу со следующими условиями (см. Табл.6)

Проверим условие баланса

Предварительный этап. Методом минимального элемента строим начальный базисный план Х₀ (Табл. 5)

Таблица 5

C =	ai bj	4	6	8	6
	6	2(5)	2(4)	3(6)	4(11)
	8	6(12)	4(10)	3(9)	1(3)
	10	1(1)	2(6)	2(7)	1(2)

Так как m + n – 1 = 6; k = 4, то план х₀ – вырожденный; l = m+ n -1 – k = 2.

Два нулевых элемента Х₀ делаем базисными так, чтобы не нарушить условие опорности. Выберем в качестве базисных элементов ,  и положим их равными .

Схема перевозок для плана Х₀ показана на рис. 6.

Рис. 6.

Для вычисления предварительных потенциалов выберем начальный пункт А₁ и допустим, что . Потенциалы всех остальных пунктов вычисляем по формулам

,

Для проверки оптимальности плана х₀ строим матрицу С₁, элементы которой вычисляем по соотношению

Так как в матрице С₁ элемент С₂₃ = – 3 < 0, то план Х₀ – неоптимальный.

Первая итерация. Второй этап.

		*	6*	0	0						6	0	0
X0 =		0*	*	8	0+			X1 =		0	0	6	
		4	0	0	6*		1 = 			4	0	0	6

В результате построения Х₁ в базис вводим. План Х₁ является вырожденным (в цепочке есть два минимальных элемента). Поэтому один из этих элементов, например , в плане Х₁ заменяем на .

Вторая итерация. Первый этап

			0	2	2					0	0	-1	2
С1 =		2	0		-3		+3	С2 =		5	3	0	0
		0	1	2	0					0	1	-1	0
				-3

Второй этап.

			6	0	0						6	0	0
X1 =		0	0	8*	*			X2 =		0	0	2	6
		4	0	0+	6*		3 =min {8, 6}= 6			4	0	6	0

Третья итерация. Первый этап.

				-1	2		+1			0	0	0	3
С2 =		5	3					С2 =		4	2	0	0
			1	-1	0		+1			0	1	0	1
		-1	-1

Так как в матрице С₃ нет отрицательных элементов, план Х₂ – оптимальный.

Венгерский метод для транспортной задачи

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

Пусть требуется решить Т-задачу следующего вида

минимизировать

при условиях

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

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

, (1.3.1)

. (1.3.2)

Если в условиях (1.3.1), (1.3.2) строгие равенства, то матрица Х₀ является решением Т-задачи.

Матрицу, построенную в результате k-й итерации, обозначим . Обозначим также

. (1.3.3)

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

Описание алгоритма Венгерского метода

Предварительный этап. В каждом из столбцов матрицы транспортных издержек  отыскивают минимальный элемент, который вычитают из всех элементов этого столбца. Получают матрицу С'. Далее в каждой строке матрицы С' выбирают минимальный элемент и вычитают его из всех элементов рассматриваемой строки. Приходят к матрице С₀ (С₀ ~ C), все элементы которой неотрицательны, причем в каждой строке и столбце С₀ имеем по крайней мере, один нуль. Строят матрицу Х₀ так, чтобы ее ненулевые элементы были расположены в позициях нулей матрицы С₀.

Пусть - номер строки, в которой расположен k-й нуль j-го столбца матрицы С₀. Тогда элементы первого столбца матрицы Х₀ определяют по рекуррентной формуле

(3.3.4)

Т.е. все элементы первого столбца , которым соответствуют ненулевые элементы в матрицы С₀, заполняют нулями, а остальные элементы этого столбца заполняют по методу северо-западного угла.

Допустим, что столбцы Х₀ от первого до (j-1) – го включительно уже заполнены. Тогда элементы j-го столбца определяют в соответствии с формулой

(3.3.5)

Если , то Х₀ – оптимальный план Т-задачи. Если , то переходим к первой итерации.

(k+1) – я итерация. Каждая итерация состоит из двух или трех этапов. Итерация начинается первым этапом, а заканчивается вторым. Между первым и вторым этапами в общем случае несколько раз могут быть проведены третий и первый этапы.

Допустим, что уже проведено k итераций, причем . В этом случае необходимо, используя матрицы С_k и Х_k, провести следующую (k+1) – ю итерацию. Перед началом итерации выделяют знаком '+' те столбцы матрицы С_k, для которых невязки по столбцам равны

.

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

.

Возможен один из двух случаев: 1), 2). В первом случае -ю строку С_k отмечают знаком '+' справа от нее, а сам невыделенный нуль отмечают штрихом. Далее просматривают элементы -й строки, которые лежат в выделенных столбцах и ищут среди них существенные нули (напомним, что существенным нулем С_k называется такой элемент , для которого ). Если таким существенным нулем оказался элемент , а сам столбец  – выделен, то знак выделения '+' над столбцом  уничтожают, а сам этот нуль отмечают звездочкой.

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

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

1) найдем очередной невыделенный нуль матрицы С_k, для которого невязкая в строке . Тогда отметив его штрихом, переходим ко второму этапу;

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

Во втором случае, отметив этот нуль штрихом, сразу переходим к третьему этапу.

Второй этап. Состоит в построении цепочки из нулей матрицы С_k, отмеченных штрихами и звездочками, и в последующем переходе к новой матрице Х_k+1

Пусть для некоторого нуля со штрихом матрицы С_k, расположенного, например, в позиции (), невязка строки . Начиная с этого элемента , строят цепочку из отмеченных нулей матрицы С_k: двигаясь по столбцу , выбирают нуль со звездочкой , далее двигаясь от него по строке , находят нуль со штрихом . Потом движутся от него по столбцу ₂ к следующему нулю со звездочкой и т.д. Такой последовательный переход от 0' к 0^* по столбцу и от 0^* к 0' по строке осуществляют до тех пор, пока это возможно.

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

После того как цепочка вида

построена, осуществляют переход к матрице  от матрицы Х_k по формулам

(1.3.7)

где (1.3.8)

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

Вычисляем невязку для

На этом (k+1) – я итерация заканчивается.

Третий этап. Итак, допустим, что все нули выделены. Третий этап заключается в переходе от матрицы С_k к эквивалентной матрице С′_k, в которой появляется новый невыделенный нуль (или нули). Пусть , где минимум выбирают из всех невыделенных элементов матрицы С_k. Тогда из всех элементов невыделенных строк матрицы С_k вычитают h, а ко всем элементам выделенных столбцов прибавляют h. В результате получают матрицу С'_k(С'_k ~ C_k), в которой все существенные нули матрицы С_k остаются нулями, и кроме того, появляются новые невыделенные нули.

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

Если после выполнения второго этапа  то Х_k+1 – оптимальный план. В противном случае переходим к (k+2) итерации.

Отметим некоторые важные особенности венгерского метода.

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

Метод позволяет на каждой итерации по величине невязки оценить близость Х_k к оптимальному плану, а также верхнюю границу необходимого числа оставшихся итераций N_ост:

. (1.3.9)

Эта формула справедлива для целочисленных значений всех переменных  и .

Список литературы

1. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа.

2. Вентцель Е.С. Исследование операций. – М.: Наука, 1976.

3. Горелик В.А., Ушаков И.А. Исследование операций. – М: Машиностроение, 1986. – 286 с.

4. Давыдов Э.Т. Исследование операций: Учебное пособие для студентов вузов. – М.: Высшая школа, 1990. – 383 с.

5. Ермолаев Ю.М. Математические методы исследования операций. – К.: Наука, 1979.

6. Кузнецов Ю.Н. Математическое программирование. – М.: Наука, 1976.

7. Минц М. Математическое программирование. Теория и алгоритмы. – М.: Наука, 1990.

8. Таха Х. Введение в исследование операций. – м.: Мир, 1985.

9. Толбатов Ю.А. Эконометрика в Excel. – К.: Четверта хвиля, 1997.