Сетевая постановка открытой транспортной задачи

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

Ребрам, инцидентным фиктивной вершине, присваиваются высокие значения c_ij. Это необходимо, чтобы априори сделать неэффективным использование фиктивной вершины (Ф = –15) как промежуточного пункта, поскольку в реальной сети его нет (рис. 9.9).

В примере открытой задачи (см. рис. 9.9) суммарная мощность поставщиков превышает суммарный спрос потребителей на 15 единиц продукции (Ф = –15). Фиктивный потребитель в вершине Ф соединен со всеми поставщиками ребрами, показатели c_ij которых равны 100. При расчете функционала не учитывается фиктивная вершина. Необходимо из показателя мощности вершины (b_i), из которой исходит стрелка к фиктивной вершине, сначала вычесть величину символической поставки этой стрелки (15), а затем эту разность умножить на потенциал реально существующей вершины (λ_b = 10). Функционал оптимального плана:

F = 10 ∙ 70 + 10 ∙ (90 – 15) + 15 ∙ (–55) + 12 ∙ (–50) + 13 ∙ 40 + 14 ∙ (–20) + + 14 ∙ 15 + 19 ∙ (–75) = –950

Рис. 9.9. Открытая транспортная задача

Транспортно-производственная задача

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

Для представления ситуации в сетевой постановке используем рис. 9.8 как исходную основу. Пусть поставщик на вершине с имеет производственные затраты 35 единиц, а поставщик на вершине d – 45 единиц. На графе (см. рис.9.8) каждая положительная вершина заменяется  нулевой мощностью и к ней добавляется ребро под названием «ус», на конце которого ставится поставка этой нулевой вершины, а на ребре – производственная затрата.

На рис. 9.10 отражены «усы», производственные затраты на ребрах и мощности нулевых вершин на конце «усов». Место вершины с заняла нулевая вершина r, а вершины d – нулевая вершина u. К нулевым вершинам добавлены тупиковые отрезки (усы) с производственными затратами на ребрах, равными 35 и 45. На концах усов величины поставок 120 и 60.

Рис. 9.10. Граф транспортно-производственной задачи

Способ решения транспортно-производственной задачи на сети тот же, что и транспортно-производственной задачи матрицы.

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

При проверке допустимого плана на оптимальность с помощью потенциалов должны отсутствовать контуры, а граф быть в форме дерева.