алгоритм решения транспортной задачи в самом общем виде:
⦁ Построение транспортной таблицы.
⦁ Проверка задачи на закрытость.,
Задача называется открытой, если не соблюдается баланс между объемом спроса и объемом предложения. Например, если запасы на всех складах меньше или больше потребностей всех магазинов - потребителей, то имеем дело с открытой транспортной моделью.
Для того, чтобы применить к задаче метод потенциалов, необходимо привести открытую транспортную задачу к закрытой модели. Т.е. необходимо выполнить преобразования, при которых , "то, что есть, станет равным, тому, что надо".
Все очень просто. Если не хватает товара, чтобы удовлетворить потребности магазинов, нужно добавить мнимого (фиктивного) поставщика. Если предложение превышает над спросом, добавим мнимого (фиктивного) потребителя.
В открытой транспортной задаче это реализуется добавлением строки или столбца, в зависимости от того,чего не хватает. Так как в реальности фиктивный поставщик (потребитель) не существует, то стоимость доставки до него от любого пункта равна нулю.
Чтобы привести открытую транспортную задачу к закрытому (замкнутому) виду, добавляем столбец (строку) с нулевыми стоимостями.
⦁ Если превышают запасы - добавляем фиктивного потребителя (столбец)
⦁ Если превышает спрос - добавляем фиктивного поставщика (строку)
⦁
⦁ Составление опорного плана.
⦁ Проверка опорного плана на вырожденность.
⦁ Вычисление потенциалов для плана перевозки.
⦁ Проверка опорного плана на оптимальность.
⦁ Перераспределение поставок.
⦁ Если оптимальное решение найдено, переходим к п. 9, если нет – к п. 5.
⦁ Вычисление общих затрат на перевозку груза.
Построение графа перевозок.
