ТЗ с промежуточными пунктами

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

Для пояснения этого рассмотрим задачу на примере. Имеются три завода по производству связного оборудования и два центра его распределения (A, B, С и 1, 2). В модели с промежуточными пунктами будет пять исходных пунктов и пять пунктов назначения. На рис. 3.1 изображена соответствующая сеть. Для того чтобы учесть транзитные перевозки, в каждом исходном пункте назначения предусматривается буфер емкостью D (буфер - это своего рода склад, емкость которого должна быть не меньше суммарного объема произ­водства). Предположим, что объемы производства составляют А- 1000 ед., B- 1500 ед., С- 1200 ед., тогда емкость буфера соста­вит 3700 ед.

Рис. 3.1

Таблица 3.13

	A	B	C
A	3700 0	130	90	1000 80	215
B	135	3700 0	200 101	1300 100	108
C	95	105	3500 0	102	1400 68
	79	99	110	3700 0	205
	200	107	72	205	3700 0

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

Помимо рассмотренной выше ситуации могут быть и более сложные варианты. Например, кроме двух центров распределения продукции имеется пять потребителей (3, 4, 5, б, 7). Спрос у потребителей характеризуется следующими цифрами: 600, 500, 750, 1000, 650 ед. В такой ситуации, как показано на рис. 3.3, промежуточными пункта­ми могут быть только центры распределения. Построенная c учетом этого модель приведена в табл. 3.14. Заштрихованные клетки говорят о том, что перевозки c завода непосредственно потребителю не предусмотрены.

Рис. 3.2

Рис. 3.3

Таблица 3.14

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

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

Для иллюстрации модели рассмотрим сеть, приведенную на рис. 3.4. В отличие от алгоритма для сетей без циклов, при котором автоматически вычисляются кратчайшие пути между узлом 1 всеми другими узлами, в модели с промежуточными пунктами находится крат­чайшее расстояние лишь между двумя пунктами. В табл. 3.15 представлена модель с промежуточными пунктами, соот­ветствующая задаче, в которой требуется определить кратчайшее расстояние между узлами 1 и 7. В этом случае емкость буфера равна 1, поскольку в любой момент через любой узел сети проходит не более одной единицы груза. Заметим также, что узел 1 не мо­жет рассматриваться в качестве промежуточного пункта назначения, поскольку он является исходным пунктом для всей сети. Аналогич­но узел 7 не может быть промежуточным пунктом, поскольку он яв­ляется конечным пунктом доставки информации. "Стоимости перевоз­ки" полагаются равными соответствующим расстояниям на сети. Заштрихованные ячейки таблицы означают, что такого маршрута не су­ществует и, следовательно, при решении задачи им следует пробе­жать очень большое расстояние. Расстояние от некоторого узла до него самого полагается равным нулю.

Рис. 3.4

Таблица 3.14

	1 2	8	5	9
	0	3		5	1 1		0+D
	4	1 0			2		0+D
		9	1 0		2	23	0+D
				0	7	1 9	0+D
	8	3	5	1 1	0	10	0+D
	0+D	0+D	0+D	0+D	0+D

Задача решается как типичная транспортная задача. Из таблицы следует, что

x₁₂=1, x₂₆=1, x₃₃=1, x₄₄=1, x₅₇=1, x₆₅=1.

Величины x₃₃=x₄₄=1 не дают вклада в решение, поскольку они соответствуют петлям в узлах 3 и 4. Остальные величины мож­но упорядочить следующим образом:

x₁₂=1, x₂₆=1, x₆₅=1, x₅₇=1

Поэтому оптимальный маршрут выглядит так:

1à2à6à5à7.