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

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

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

Пример. В каждом из 3-х городов расположено по заводу. Объем производства первого завода составляет 100 единиц в год ( =100), второго –150 ( =150), третьего – 120 ( =120). Продукция поступает для последующего распределения на 2 склада. Величина спроса составляет 230 партий в год для первого склада ( =230) и 140 – для второго ( =140). Маршруты перевозок комплексов с заводов на склады могут пролегать, в том числе, и через те города, в которых такие же комплексы производятся. Расстояние между заводами и складами приведено в таблице 5. В этой таблице символами обозначены 1, 2 и 3 заводы, а символами - 1 и 2 склады.

Таблица 5

Заводы, склады	Заводы	Склады

В данной задаче фактическое число исходных пунктов равно числу заводов, то есть трем, а фактическое число конечных пунктов– числу складов, то есть двум. При допустимости транзитных перевозок каждый исходный и каждый конечный пункт могут оказаться транзитными. Это означает, что в стандартной транспортной задаче, при допустимости транзитных перевозок, число исходных пунктов должно равняться числу конечных и равняться сумме реальных исходных и конечных. Таким образом, в сетевой модели для нашего примера число исходных пунктов, как и число конечных равно 5, рис.3. Заметим, что реальными исходными являются вершины сетевой модели, а реальными конечными – вершины .

Обозначим количество продуктов, поступающих из i-го исходного пункта в j-й конечный, i, j =1, 2, …, 5. Тогда, количество ограничений будет равно сумме количества исходных и конечных вершин сети - 10 для модели. Запишем ограничения, соответствующие исходным вершинам модели. В каждую i-ю вершину, являющуюся одновременно транзитной, могут поступать единиц продукции в год, где . Исходить же из него может единиц продукции в год, если эта вершина соответствует реальному исходному пункту и B единиц продукции, если эта вершина соответствует реальному конечному пункту. Отсюда следует, что для исходной вершины сети рис.3, соответствующей реальному исходному пункту (i =1, 2, 3), ограничения имеют вид , а для вершины, соответствующей реальному конечному пункту (i = 4, 5) - вид .

 

B+100 B B+150 B   B+120 B   B B+230     B B+140

 

Рис. 3. Сетевая модель транспортной задачи с промежуточными пунктами

Из каждой конечной вершины сети рис.3, являющейся одновременно транзитной, может исходить единиц продукции. Поступает же в нее B единиц продукции, если эта вершина соответствует реальному исходному пункту задачи (j =1, 2, 3) и , если она соответствует реальному конечному пункту (j = 4, 5). Отсюда следует вторая половина системы ограничений: для j = 1, 2, 3 и j = 4, 5.

Обозначим, как и ранее, - стоимость перевозки из пункта i в пункт j. Примем эту стоимость равной расстоянию между данными пунктами, табл. 5. Тогда транспортная задача с промежуточными пунктами запишется в виде:

Транспортная таблица этой задачи изображена в табл. 6.

Таблица 6

⇐ Предыдущая1234567Следующая ⇒

Поделиться:

Популярное:

1. Стандартная транспортная задача
2. Тема «Управление транспортом. Транспортная документация».
3. Транспортная (транзитная) реклама
4. Транспортная стратегия Российской Федерации до 2030 года
5. Транспортная характеристика груза
6. Транспортная характеристика перевозимых грузов