pizhurin_a_a_pizhurin_a_a_modelirovanie_i_optimizaciya_proce

3.7,2. Отыскание опорного решения транспортной задачи

Процесс решения транспортной задачи состоит из двух этапов, как

идля обычной задачи линейного программирования:

1)отыскания опорного решения;

2)последовательного его улучшения с целью отыскания оптималь­ ного решения задачи.

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

веро-западный угол. Обозначим клетку на пересечении строки А . и столб­

ца Вj через i, j. При решении транспортной задачи, условия которой при­

ведены в табл. 3.20, в левую верхнюю клетку (1,1) транспортной таблицы (табл. 3.22) запишем минимальное из чисел а х и b v В данном случае - это

число Ъ,= 30. Это означает, что заявка первого потребителя полностью

удовлетворена из запасов груза первого поставщика: * п=30, и столбец В х

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

						Т а б л и ц а		3.22
Но­		Поставщик			Потребитель
				1	2	3	4
мер	Обозначе­
п/п			Запас груза	*1	в 2	* 3
	ние
1				5	13		6	11
	л ,		а }=35	30	5

2

а 2

И N<	lO
а

4

7

12

8

5 40

	3				9	2	3	10
		Аз	o'	о			25	25
				>»/- II	1
	4	Потребность в грузе				Ь2 =10	63=65	= 25
					Ь}= 30

Переходим к клетке (1, 2), находящейся правее рассмотренной. У первого поставщика осталось еще 5 единиц груза, которые можно отпра­ вить второму потребителю. Поэтому число 5 вписываем в данную клетку: х ]2=5. Так как первый поставщик израсходовал свой груз, переходим к

заполнению второй строки таблицы, начиная с клетки (2,2). Сюда впишем 5 единиц груза из пункта А 2, которых недостает второму потребителю,

удовлетворив полностью его заявку. Оставшиеся у второго поставщика 40 единиц груза передадим третьему потребителю: х2Ъ= 40. Осталось рас­

смотреть третью строку. В клетку (3, 3) помещаем 25 единиц, удовлетво­ рив заявку пункта В3, а оставшиеся в пункте А3 25 единиц передадим в

В4. Таким образом, груз всех поставщиков полностью распределен, и

удовлетворены заявки всех потребителей, т. е. найдено допустимое реше­ ние данной задачи. Для того чтобы это решение было опорным, необходи­ мо выполнение следующего условия: число занятых клеток в транспорт­ ной таблице должно быть равно N = т + п - 1. В данном случае это усло­ вие выполнено: заполнено шесть клеток, и Л Г = 3 + 4 - 1 = 6 . Подсчитаем значение целевой функции, соответствующее найденному опорному реше­ нию:

JT = 5x30 + 13x5+ 7x5+ 12x40 + 3x25+ 10x25 = 1055.

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

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

Но­ мер п/п

1

9

3

					Т а б л и ц а 3.23
	Поставщик			Потребитель
			1	2	3	4
	Обозна­
		Запас		В 2	* 3	*4
	чение		я ,
		со II сГ	5	13	25 6 Н	11
	^1		(+)*		*10
	А	30	4	7	12	8
		­is• ll <3*	(		11^
	2				•	и
					(+)
	А 3	II СИ о	9	2	3	10
				10	40

4

Потребность

&!= 30

Ь2= 10

b з = 6 5

ъ

CN II

Продемонстрируем применение этого метода. Наименьшая стои­ мость перевозки единицы груза в транспортной табл. 3.20 соответствует клетке (3, 2): сЪ2= 2. В нее запишем наименьшее из чисел аъ и 62, т. е. 10

(табл. 3.23). Среди оставшихся клеток наименьшая стоимость перевозок

соответствует клетке (3, 3): с33 = 3. В нее запишем число 40. Это количест­

во груза, оставшееся в пункте Л3. Далее переходим к клетке (2, 1), записав

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

чающееся от предыдущего решения в табл. 3.22. Значение целевой функ­ ции для него, как легко вычислить, равно 640, т. е. значительно лучше, чем для опорного решения, полученного по методу северо-западного угла.

3.7.3. Отыскание оптимального решения транспортной задачи. Метод потенциалов

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

Нужно попытаться так изменить план перевозок, чтобы часть груза из за­ пасов первого поставщика досталась не четвертому, а первому потребите­ лю, для которого стоимость перевозок значительно ниже: с и = 5. Практи­

чески это означает, что часть груза из клетки (1,4) переносится в клетку (1, 1). В этом случае, однако, пункт В { получит излишек груза, а пункту

В 2 его будет недоставать. Чтобы восстановить баланс, можно это же ко­ личество груза перенести из клетки (2, 1) в клетку (2, 4). Идея подобного перераспределения ресурсов положена в основу нескольких методов оты­ скания оптимального решения транспортной задачи.

Рассмотрим один из них, называемый методом потенциалов. На­ помним, что имеется опорный план решаемой транспортной задачи. Его транспортная таблица содержит (т х п) клеток, из которых {т + п - 1) за­ няты, а остальные (тп - (т + п - 1)) свободны. Для иллюстрации в транс­ портной табл. 3.24 занятые клетки обозначены точками. Значения стоимо­ сти перевозок и величины переменных xiJ9 образующие опорный план, в

таблице опущены.

Метод потенциалов предполагает выполнение следующих этапов. 1. Каждому поставщику А. ставится в соответствие некоторая пе­

ременная и ■, называемая потенциалом данного поставщика. Каждому по­

требителю Bj ставится в соответствие переменная v^.- потенциал этого

потребителя (последний столбец и последняя строка табл. 3.24).

2. Для отыскания значений этих переменных, т. е. потенциалов по­ ставщиков и потребителей, составляется и решается система уравнений.

При этом каждой занятой клетке (/, j) соответствует свое уравнение, имеющее вид

ui+ vj = cij>

(з -79)

где Су- стоимость перевозки единицы груза для данной клетки;

щ и v • - соответственно потенциалы поставщика и потребителя.

Т а б л и ц а 3.24

Но­

Поставщик

Потребитель

Потенциал

1

2

3

4

5

6

7

8

мер

Обозна­

поставщи­

п/п

Запас

в 2

в*

*6

*7

*8

ка

чение

5 ,

* 5

h

-

1

«1

«1

4f

2

а 2

h

+

«2

Л

4

A

«2

-

3

Л,

аз

1

иъ

-

Hh

4

А 4

* k

ь

u4

а 4

-

н-

5

А*

* 5

-

+

U 5

6

^ 6

« 6

нh

4

7

Потребность

* 1

h

Ъъ

* 4

*5

b e

* 7

8

Потенциал по­

vi

v6

V8

требителя

v 2

V3

V 4

V 5

v 7

Всего составляется (т + п - 1) уравнений по ^ислу занятых клеток. Число переменных в системе равно (т + и), т. е. на единицу больше числа уравнений. Поэтому система легко решается: одной из переменных при­ дают произвольное значение, обычно нуль, и тогда однозначно определя­ ются значения остальных переменных.

3. Для каждой свободной клетки вычисляют сумму потенциалов со­ ответствующих ей поставщика и потребителя. Обозначим ее zb для к-го

поставщика и s-ro потребителя:

Z k s = U k + Vs -

Эту сумму называют псевдостоимостью. Далее для этой же клетки вычисляют разность

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

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

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

эта разность наибольшая по абсолютной величине.

5. В найденную свободную клетку следует записать некоторое ко­ личество груза, перераспределив перевозки. Для этого строится так назы­ ваемый цикл. Это многоугольник с прямыми углами, одна из вершин кото­ рого находится в найденной свободной клетке, а все остальные - в занятых клетках. Такой многоугольник, и при том единственный, всегда можно найти. Так, цикл для свободной клетки (2, 1) (см. табл. 3.24) содержит, кроме нее, еще три занятых клетки: (2, 2), (4, 2) и (4, 1). В этой таблице приведены в качестве примеров еще два цикла для свободных клеток (1 ,5 )

и(4,3).

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

6.Среди клеток, помеченных знаком «-», отыскивают ту, в которой записано минимальное количество груза. Это значение прибавляют к зна­ чениям количества груза в тех клетках цикла, которые помечены знаком

«+ », включая свободную клетку, и вычитают из значений в клетках цикла, помеченных знаком «-». Эта процедура называется перенос по циклу.

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

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

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

В соответствии с количеством поставщиков и потребителей рассмотрим три переменные их, и2 , м3 - потенциалы поставщиков и четыре переменные v,, v2, v3,

v4 - потенциалы потребителей. Для каждой занятой клетки в табл. 3.23 запишем

уравнение вида (3.79): w,+v3 = 6	- для клетки (1, 3); w,+v4 =l l - для (1,	4),
и 2 + vi = 4 - для (2, 1); и2 + v4 = 8 -	для (2, 4), w3 + v2 = 2 - для (3, 2); w3 + v3 = 3 -	для
(3, 3).

Примем w, = 0 , после чего найдем из записанной системы уравнений значения остальных потенциалов: v3 = 6 ; v4 = 11; и3 = -3; v2 = 5; и2 = -3 ; v, = 7.

На этапе 3 вычисляем суммы потенциалов поставщика и потребителя, соответ­ ствующие каждой свободной клетке. Они приведены в левых нижних углах этих клеток

(табл. 3.25).

Подсчитываем разности 3ь по формуле (3.80): <5П = 5 - 7 = - 2; Sl2 = 1 3 -5 = 8 ;

<*22 = 7 - 2 = 5; S23 =12 - 3 = 9; S3l = 9 - 4 = 5; S34 =10 - 8 = 2.

Как видно, для клетки (1,1) получена отрицательная разность: <5И = -2 . Сле­

довательно, исходный опорный план в табл. 3.23 не оптимален. Так как клетка с отри­ цательной разностью в данном случае единственная, то она и выбирается в качестве вершины цикла (этап 4). Этот цикл найден и построен в табл. 3.23. В соответствии с правилами его построения (этап 5), все вершины цикла, кроме одной, находятся в заня­ тых клетках. В цикле помечены вершины. При этом знаком «-» помечены две клетки: (1, 4) и (2, 1). Наименьшее из чисел, находящихся в них, равно 10. Поэтому 10 единиц груза прибавляем к числам в клетках (1, 1) и (2, 4) и вычитаем из чисел, находящихся в клетках (1, 4) и (2, 1). Полученный план приведен в табл. 3.26. Для него вновь отыски­ ваются потенциалы поставщиков и потребителей по результатам решения системы уравнений:

[щ +V! = 5; щ +v3 = 6; u2 +v, = 4;

| w 2 + v 4 = 8 ; w 3 + v 2 = 2 ; w3 + v 3 = 3.

							Т а б л и ц а		3.25
Поставщик				Потребитель
Обозначение	Потенциал	в ,		в г		в ,		В<
А	и х= 0	7	5 5		13		6		И
л 2	w2 = -3		4	2	7	3	12		8
Лз	i/3 = - 3	4	^		2		3	8	Ю
Потенциал потребителя		у , = 7		v2 =5		v3 = 6		v4 = l l
							Т а б л и ц а		3.26

	Поставщик
Обозначение	Запас
л	ах =35
Аг	К) II ty»
Аз	а3 =50
Потребность

Потенциал потребителя

			Потребитель
	1
	Потенциал	*1		*3	*4
	w, =5	5	13	6	11
		10	5	25	9
	и2 = 4	4	7	12	8
		20	4	5	25
	w3 = 2	9	2	3	10
		2	10	40	6
		Z>1= 30	Ъ2 =10	b3 =65	(N II сГ-
		v, = 0	v2 = 0	v3 =l	v4 =4

Найденные потенциалы, а также величины псевдостоимостей zks, рас­ считанные для каждой свободной клетки, приведены в табл. 3.26 (предварительно по­ ложили Vj = 0 ).

Отсюда видно, что в данном случае все числа zb не превышают соответствую­

щих стоимостей, что свидетельствует об оптимальности полученного решения. Ему со­ ответствует минимальное значение целевой функции, равное W = 5-10 + 6*25 + 4-20 + + 8 -25+ 2-10 + 3-40 = 620.

Выше отмечалось, что транспортная таблица, содержащая опорное решение транспортной задачи, должна содержать ровно [т + п - 1) заня­ тых клеток. Случай, когда число занятых клеток меньше указанного, назы­ вается вырожденным. Для отыскания оптимального решения при вырож­ денном опорном плане достаточно записать нуль в какую-либо свободную клетку и в дальнейшем оперировать с ней как с занятой.

3. 7.4. Открытая модель транспортной задачи

Во многих задачах о перевозках не нужно требовать, чтобы весь за­ пас груза у поставщиков был вывезен потребителям. Иными словами, име­ ется избыток груза. Поэтому условие (3.74) заменяется неравенством

тп

(3.81)

/=i >i

Вместо ограничений-равенств (3.76) также будут неравенства:

Z*,;/	(3.82)
У'= 1

Полученная модель, содержащая целевую функцию (3.77) и огра­ ничения (3.75), (3.81), (3.82) и (3.78), называется открытой моделью

транспортной задачи. Другой вариант открытой транспортной задачи (ТЗ) возникает, когда суммарный объем заявок превышает общий объем груза:

тп

2 > , < S V		(з.83)
/=i	j=\

В этом случае ограничения (3.76) сохраняются, а заявки выполня­ ются не полностью, поэтому равенства (3.75) заменяются неравенствами

£ х у < Ь у, j = 1,2,..., п.	(3.84)
1=1

Открытая транспортная задача легко сводится к рассмотренной выше закрытой транспортной задаче. Для задачи с избытком груза вводит­ ся фиктивный (п + 1)-й потребитель. Объем Ьп+] его заявки принимают

88

равным разности между суммарным запасом груза поставщиков и суммар­ ным объемом заявок потребителей:

b „ x = t ° , - i b j ,

(3-85)

/=1

а стоимости перевозок от любого поставщика к этому фиктивному потре­ бителю считают равными нулю:

*Ч,+1=0’ i =

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

Для открытой транспортной задачи с избытком заявок вводится (т+ 1)-й фиктивный поставщик с запасом груза, равным

7=1 /=1

Стоимость перевозок от этого поставщика к любому потребителю принимают равной нулю.

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

			Т а б л и ц а 3.27
Поставщик			Потребитель
Обозначение	Запас	*»	*2	*3
Л,	50	35	2	17
	100	4	34 ,	18
Лз	20	29	5	8
Потребность		40	70	50

Пример. Решение транспортной задачи, матрица которой приведена в табл. 3.27.

Сравнивая запасы груза = с суммарным объемом заявок потребите-

(3 )

лей ^ b j , = 160 , убеждаемся, что это открытая транспортная задача с избытком груза.

Ы)

Она преобразуется в закрытую транспортную задачу введением фиктивного четвертого потребителя с объемом заявок (табл. 3.28)

ь4 = Х а/ - Х Л = 10. 1=1 м

89

							Т а б л и ц а 3.28
Номер	Поставщик			Потребитель
			1	2			3		4
п/п
	Обозначение	Запас	в ,	в 2			*3
						2		17	*4
1		50	35	сл	ь		18		|к о	0
			4	jU	4	+			1 и
2		100	4			34		18	11п	0
			40	2			50 i	-	ш
			29			5			+
		20						8		0
3	А,		7	20 < -			21	+	3
4	Потребность		40	70			50		10

Опорное решение получено методом наименьшего элемента. В данном случае первой может быть заполнена любая из клеток последнего столбца, поскольку каждой из них соответствует нулевая стоимость перевозок. Полученный опорный план (см. табл. 3.28) оказался вырожденным: число занятых клеток в нем равно 5, что меньше числа (т + п —1) = 6. В соответствии с замечанием в п. 3.7.3, записан нуль в клетку (1,4), которая теперь считается занятой.

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

«j +v2 = 2 ; и2 +v3 =18;

{Mj + v4 = 0; м2 + v4 = 0;

u2 +v1= 4; иъ + v2 = 5.

Примем u2 = 0 (эта переменная встречается в системе чаще всего). Тогда легко отыскиваются значения остальных потенциалов: v1 = 4; v3 = 18; v4 = 0 ; ur = 0 ; v2 = 2 ; w3 =3. В левых нижних углах свободных клеток табл. 3.28 приведены вычисленные

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

данном случае псевдостоимости в трех клетках (1,3), (3, 3) и (3, 4) превышают величи­ ны соответствующих стоимостей. Разность 3ь = с оказалась отрицательной и

минимальной для клетки (3, 3). В соответствии с процедурой метода потенциалов най­ ден цикл. В нем помечены вершины (см. табл. 3.28). Среди клеток, помеченных знаком «-», минимальное количество груза, равное нулю, оказалось в клетке (1,4). Поэтому в данном случае осуществляется так называемый фиктивный перенос по циклу: при­ бавление или вычитание нуля к величинам груза, записанным в соответствующих клет­ ках. Эта операция, разумеется, не меняет чисел в клетках, однако клетку, в которую был записан нуль и считавшуюся занятой, после вычитания нуля будем считать сво­ бодной, как это произошло с клеткой (1, 4). И наоборот, свободная клетка после при­ бавления нуля считается занятой - в примере это клетка (3, 3). “Новый” опорный план представлен в табл. 3.29. В ней же приведены величины потенциалов поставщиков и потребителей, найденные из системы уравнений

w1+v2 = 2 ;	w2 +v4 = 0 ;
w2 + vi = 4;	w3 + v2 = 5;
(m2 + v 3 =18;	»3.+ v 3 = 8 .

При ее решении приняли и2 = 0. Этот план, как легко убедиться, является оп­

тимальным.								Т а б л и ц а		3.29
Поставщик					Потребитель
Обозначение	Потенциал		в ,		*2				*4
л ,	и:= - 13	- 9		35	50	2	5	17 -1 3		0
	ы2 = 0		40	4 15		34	50	18	10	0
А 3	м3 = -1 0	- 6		29	20	5	0	8		0
								-10
Потенциал потребителя			V! = 4		v2 =15		v3 =18		но

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

3.8. Задачи линейного программирования, приводимые к транспортной

3.8.1. Варианты задач о перевозках грузов

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

1. Транспортная задача с ограниченными пропускными способ­ ностями. Здесь вводятся дополнительные ограничения на пропускную способность коммуникаций. Поэтому требование xtj > О заменяется дву­

сторонним неравенством: 0 < xtj < dij9 где dtJ- заданное предельное коли­

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

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

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

Существует прием, позволяющий свести эту задачу к ТЗ с запретами.