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

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

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

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

В примере открытой задачи (см. рис. 9.9) суммарная мощность поставщиков превышает суммарный спрос потребителей на 15 единиц продукции (Ф = –15). Фиктивный потребитель в вершине Ф соединен со всеми поставщиками ребрами, показатели cij которых равны 100. При расчете функционала не учитывается фиктивная вершина. Необходимо из показателя мощности вершины (bi), из которой исходит стрелка к фиктивной вершине, сначала вычесть величину символической поставки этой стрелки (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. Граф транспортно-производственной задачи

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

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

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

10 декабря 2012 /
Похожие новости
Сетевые постановки транспортных задач
Топологический анализ сетей
Методы теории графов
Транспортно-производственная задача. Многоэтапная транспортная задача. Многопродуктовая транспортная задача
Факторный анализ.Сущность и возможности применения
Комментарии

НАПИСАТЬ КОММЕНТАРИЙ

Ваше Имя:
Ваш E-Mail:
Полужирный Наклонный текст Подчеркнутый текст Зачеркнутый текст | Выравнивание по левому краю По центру Выравнивание по правому краю | Вставка смайликов Выбор цвета | Скрытый текст Вставка цитаты Преобразовать выбранный текст из транслитерации в кириллицу Вставка спойлера
Вопрос:
Столица России?
Ответ:*
Введите код: