Главная / Программирование / Транспортная задача с промежуточными пунктами

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

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

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

рис. 3.1копия 200013

Таблица 3.13

A

B

C

1

2

A

3700 0

130

90

1000 80

215

4700

B

135

3700 0

200 101

1300 100

108

5200

C

95

105

3500 0

102

1400 68

4900

1

79

99

110

3700 0

205

3700

2

200

107

72

205

3700 0

3700

3700

3700

3700

6000

5100

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

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

рис. 3.2копия 200014

Рис. 3.3

Таблица 3.14

4

5

6

7

8

9

10

1

1000

2

1500

3

1200

4

3700

5

3700

3700

3700

800

500

750

1000

650

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

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

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

рис. 3.4копия (2) 200014

Таблица 3.14

2

3

4

5

6

7

1

1 2

8

5

9

1

2

0

3

5

1 1

0+D

3

4

1 0

2

0+D

4

9

1 0

2

23

0+D

5

0

7

1 9

0+D

6

8

3

5

1 1

0

10

0+D

0+D

0+D

0+D

0+D

0+D

1

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

X12=1, x26=1, x33=1, x44=1, x57=1, x65=1.

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

X12=1, x26=1, x65=1, x57=1

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

1a2a6a5a7.