Решение транспортной задачи в сетевой постановке.

Рассмотрим транспортную задачу в виде сети (см. рис. 1), где - поставщики, а - потребители. Транспортные потоки идут от поставщиков потребителям. Найдем на рисунке 1 все наименьшие по стоимости пути от каждого поставщика ко всем потребителям. Сформируется сеть, представленная на рисунке 2. Из вершины в вершину ведет самый дешевый путь со стоимостью 18, другие пути из в более дорогие. Из вершины в вершину ведет самый дешевый путь () со суммарной стоимостью 19, где 0 — нулевая вершина; другие пути из в более дорогие. И так далее. В итоге можно составить условие транспортной задачи в табличном виде, в которой минимальные стоимости доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения заданы матрицей тарифов . Математическая модель транспортной задачи: F = ∑∑cijxij, при условиях: ∑xij = ai, i = 1,2,…, m, ∑xij = bj, j = 1,2,…, n, n=m=6. Построим начальную таблицу транспортной задачи. Запасы 18 19 13 13 12 15 30 28 19 13 13 12 15 30 22 13 13 7 5 9 30 29 21 15 15 13 17 45 23 15 9 9 7 11 45 26 18 12 12 10 14 20 Потребности 35 35 40 40 40 10

Ниже приведен 34 вариант транспортной задачи в сетевой постановке. Каждая задача изображена в виде неориентированного связного графа. На ребрах проставлены значения тарифов , на вершинах (в кружках) — значения запасов-потребностей . Построить пробный допустимый план, проверить его на оптимальность. В случае необходимости довести до оптимального плана методом потенциалов.

нет