Исследование операций / ИСО Учебник

нулю: cm+1 j = 0 ( j =1,n) . Этим задача сводится к обычной транспортной за-

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

Число переменных xij в транспортной задаче с т пунктами отправления и п пунктами назначения равно пт, а число уравнений в системах (2.17) и (2.18) равно n+m. Так как мы предполагаем, что выполняется условие (2.20), то число линейно независимых уравнений равно n+m–1.

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

Если в опорном плане число отличных от нуля компонент равно в точности n+m-1, то план является невырожденным, а если меньше — вырож-

денным.

Для определения опорного допустимого плана существует несколько методов. Ниже рассматриваются метод северо-западного угла и метод минимального элемента.

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

Ввиду исключительной практической важности транспортной задачи и специфики ее ограничений (каждая неизвестная входит лишь в два уравнения систем (2.17) и (2.18) и коэффициенты при неизвестных равны единице) для определения оптимального плана транспортной задачи разработаны специальные методы. Один из них — метод потенциалов — изложен ниже.

101

Определение опорного плана транспортной задачи

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

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

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

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

После того как проделаны т+п–2 описанных выше шагов, получают задачу с одним пунктом отправления и одним пунктом назначения. При этом останется свободной только одна клетка, а запасы оставшегося пункта отправления будут равны потребностям оставшегося пункта назначения. Заполнив эту клетку, тем самым делают (n+m–1)-й шаг и получают искомый опорный план. Следует заметить, что на некотором шаге (но не на последнем) может оказаться, что потребности очередного пункта назначения равны запасам очередного пункта отправления. В этом случае также временно исключают из рассмотрения либо столбец, либо строку (т. е. что-нибудь одно).

102

Таким образом, либо запасы соответствующего пункта отправления, либо потребности данного пункта назначения считают равными нулю. Этот нуль записывают в очередную заполняемую клетку. Указанные выше условия гарантируют получение n+т–1 занятых клеток, в которых стоят компоненты опорного плана, что является исходным условием для проверки последнего на оптимальность и нахождения оптимального плана.

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

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

Пример. На три базы А1, А2, А3 поступил однородный груз в количествах, соответственно равных 140, 180 и 160 ед. Этот груз требуется перевезти в пять пунктов назначения B1, В2, В3, В4, В5 соответственно в количествах 60, 70, 120, 130 и 100 ед. Тарифы перевозок единицы груза из каждого пункта отправления в соответствующие пункты назначения указаны в табл. 2.13.

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

Решение. Здесь число пунктов отправления m = 3, а число пунктов назначения n=5. Следовательно, опорный план задачи определяется числами, стоящими в 5+3–1=7 заполненных клетках.

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

103

												Таблица 2.13
	Пункты			Пункты назначения								Запасы
	отправления
		B1		B2		B3		B4		B5
	A1		2		3		4		2		4	140
	A2		8		4		1		4		1	180
	A3		9		7		3		7		2	160
	Потребности	60		70		120		130		100		480

Так как запасы пункта А1 больше, чем потребности пункта В1, то полагаем х11= 60, записываем это значение в соответствующей клетке табл. 2.14 и временно исключаем из рассмотрения столбец B1, считая при этом запасы пункта А1 равными 140-60=80. Теперь в пункте A1 осталось 80 единиц груза; этим количеством можно удовлетворить потребности пункта B2. Положим х12 = 70, запишем это значение в соответствующей клетке табл. 2.14 и временно исключим из рассмотрения столбец В2. После этого в A1 остается еще 80 – 70=10 единиц груза; отдадим их пункту B3. Потребности пункта В3 больше оставшихся запасов пункта А1. Положим х13=10 и исключим из рассмотрения строку А1. Значение x13=10 запишем в соответствующую клетку табл. 2.14 и считаем потребности пункта В3 равными 110 ед. Но заявка этого пункта еще не удовлетворена полностью; выделим недостающие 120–10=110 единиц из запасов других пунктов отправления.

Теперь перейдем к заполнению клетки для неизвестного x23 и т. д. Через шесть шагов остается один пункт отправления А3 с запасом груза 100 ед. и один пункт назначения В5 с потребностью 100 ед. Соответственно, имеется одна свободная клетка, которую и заполняем, полагая x35 =100 (табл. 2.15).

В результате получаем опорный план

	60	70	10	0	0
	0	0	110	70	0
X =						.
	0	0	0	60	100

104

																													Таблица 2.14
	Пункты										Пункты назначения																		Запасы
	отправления
				B1						B2				B3					B4					B5
	A1			60			2		70			3		10			4					2					4		140
	A2						8					4					1					4					1	180
	A3						9					7					3					7					2	160
	Потребности		60							70			120					130					100					480
																													Таблица 2.15
	Пункты										Пункты назначения																		Запасы
	отправления
				B1					B2					B3					B4					B5
	A1		60				2	70				3	10				4					2					4	140
	A2						8					4	110				1	70				4					1	180
	A3						9					7					3	60				7	100				2	160
	Потребности		60					70					120					130					100					480

Согласно данному плану перевозок, общая стоимость перевозок всего груза составляет

F=2·60 + 3·70 + 4·10+1·110 + 4·70 +7·60 + 2·100=1380.

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

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

105

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

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

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

												Таблица 2.16
Пункты			Пункты назначения									Запасы
отправления
	B1		B2		B3		B4		B5
A1	jj	2	j	3		4	jj	2			4	140
A2		8		4	jj	1		4	jj		1	180
A3		9		7		3		7	j		2	160
							130
Потребности	60		70		120				100			480

Минимальный тариф, равный 1, находится в клетке для переменной х23. Положим х23= 120, запишем это значение в соответствующую клетку табл. 4.6 и исключим временно из рассмотрения столбец B3 . А для пункта A2 запас будем считать равным 180–120=60 ед.

106

Кроме того, минимальный тариф, равный 1, находится в клетке для переменной х25. Положим х25 = 60, запишем это значение в соответствующую клетку табл. 2.17 и исключим временно из рассмотрения столбец B3 .

																						Таблица 2.17
	Пункты						Пункты назначения															Запасы
	отправления
				B1			B2			B3					B4				B5
	A1				2			3					4			2				4	140
	A2				8			4		120			1			4		60		1		180
	A3				9			7					3			7				2	160
	Потребности		60			70								130			100				480
									120

В оставшейся части таблицы с двумя строками А1 и А3 и четырьмя столбцами В1, В2, В4 и В5 клетка с наименьшим значением тарифа cij =2 находится на пересечении строки А3 и столбца В5, строки А1 и столбцов В1 иВ4. Не нарушая допустимости плана, положим x35 = 40, x11 = 60, x14 = 80 и внесем эти значения в соответствующие клетки табл. 2.18.

																											Таблица 2.18
	Пункты								Пункты назначения																		Запасы
	отправления
				B1					B2			B3					B4						B5
	A1			60			2			3					4		80			2				4			140
	A2						8			4		120			1					4		60		1			180
	A3						9			7					3					7		40		2		160
																										(120)
	Потребности			60				70				120				130						100				480
																(50)

107

Теперь исключим из рассмотрения строки A1 и A2 и столбцы B1, B3, B5, т. к. по ним выполнены условия допустимости. После этого аналогично заполняем оставшуюся часть таблицы (табл. 2.19).

																	Таблица 2.19
Пункты				Пункты назначения													Запасы
отправления
	B1			B2			B3			B4					B5
A1	60		2			3			4	80		2				4	140
A2			8			4	120		1			4		60		1	180
A3			9	70		7			3	50		7		40		2	160
Потребности	60			70			120			130				100			480
В результате получим опорный план
						60	0		0	80		0
						0	0		120	0		60
				X =
						0	70		0	50		40

При данном плане перевозок общая стоимость перевозок составляет

F= 2·60 + 2·80 + 1·120 + 1·60 + 7·70 + 7·50+2·40= 1380.

108

Лекция 2.2.2. Операционные модели транспортного типа. Методы их решения: нахождение оптимального решения транспортной задачи

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

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

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

Для определения опорного плана транспортной задачи будем пользоваться одним из методов, изложенных ранее. Эти методы гарантируют получение занятых в исходном плане п+т–1 клеток, причем в некоторых из них могут стоять нули. Построенный план следует проверить на оптимальность.

ТЕОРЕМА.

Если

для

некоторого опорного

плана

X * = (xij* )

(i =

j =

транспортной

задачи

существуют

такие

n+m чисел

1, m

1,n)

α1,α2 ,...,αm, β1, β2 ,..., βn , что

α

i

+ β

j

= c

при x > 0

(2.21)

ij

ij

и

α

i

+ β

j

≤ c

при

x = 0

(2.22)

ij

ij

для всех i =

и

j =

, то X * = (xij* ) — оптимальный план транспортной

1, m

1, n

задачи.

Числа αi и β j ,

(i =

j =

называются потенциалами, соответствен-

1, m

1, n)

но пунктов назначения и пунктов потребления.

109

Сформулированная теорема позволяет построить алгоритм нахождения решения транспортной задачи. Он состоит в следующем. Пусть одним из рассмотренных выше методов найден опорный план транспортной задачи. Для каждого из пунктов отправления и назначения определяют потенциалы αi и β j (i =1, m j =1,n) . Эти числа находят из системы уравнений

αi + β j = cij ,

(2.23)

где сij — тарифы, стоящие в заполненных клетках таблицы условий транспортной задачи.

Так как число заполненных клеток равно п + т – 1, то система (2.23) с п+m неизвестными содержит п + т – 1 уравнений. Поскольку число неизвестных превышает на единицу число уравнений, одно из неизвестных можно положить равным произвольному числу, например α1 = 0 , и найти последовательно из уравнений (2.23) значения остальных неизвестных. Для исследования плана на оптимальность для каждой свободной клетки проверяется условие αi + β j ≤ cij . Если хотя бы одна свободная клетка не удовлетворяет

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

γij = cij −(αi + βj )< 0 .

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

Если для всех свободных клеток чисела γij ≥ 0 , то опорный план перевозок является оптимальным.

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

110