Метод потенциалов
Метод потенциалов используется для решения транспортной задачи. Основой вычислительного процесса при улучшении опорного плана является определение критерия оптимальности dij:dij = сij* - сij,
где сij - затраты (истинные тарифы), связанные с доставкой одной единицы груза из i-того пункта отправления в j-ый пункт назначения;
сij* - расчётные затраты (косвенные тарифы), связанные с доставкой одной единицы груза из i-того пункта отправления в j-ый пункт назначения, определяемые для тех клеток опорного плана, ресурсы в которые не распределены (для незаполненных клеток).
Инструкция. Необходимо выбрать вид исходных данных.
Полученное решение сохраняется в файле MS Word. см. также метод потенциалов для ориентированного графа.
Алгоритм метода потенциалов
План транспортной задачи является оптимальным, если для всех свободных клеток таблицы перевозок значение критерия оптимальности dij<=0. Если для всех свободных клеток таблицы перевозок критерий оптимальности dij<0, то этот план перевозок является единственным. Если для некоторых свободных клеток таблицы перевозок критерий оптимальности dij=0, то этот оптимальный план перевозок не является единственным. Наконец, если имеются свободные клетки, для которых критерий оптимальности dij>0, то полученный план перевозок не является оптимальным. Алгоритм метода потенциалов состоит в следующем: каждому поставщику Ai ставится в соответствие некоторое число u, которое называется потенциалом Ai-того поставщика; каждому потребителю Bj ставится в соответствие некоторое число v, которое называется потенциалом Bj-того потребителя. Для каждой заполненной клетки, т. е. для каждой базисной переменной строится соотношение:ui+vj=cij
Получаем систему с числом уравнений, равным количеству базисных переменных. Из этой системы определяем неизвестные потенциалы ui и vj, полагая ui=0. Для каждой незаполненной клетки, т. е. для каждой небазисной переменной, рассчитываются косвенные тарифы cij* по формуле: cij* = ui+vj. Затем полученный план проверяют на оптимальность по критерию оптимальности dij. Если для каждой незаполненной клетки выполняется условие: dij<=cij*<=0, то исходный план является оптимальным. Если некоторые dij>0, то необходимо перейти к новому плану путем перемещения перевозки в клетку, отвечающую условию max(dij). Если таких клеток несколько, то выбирают любую из них.
Для правильного перемещения перевозок, чтобы не нарушить ограничения задачи, строят так называемый цикл, т. е. замкнутый многоугольник, соединяющий выбранную клетку с ней же самой и проходящий через заполненные клетки.
Цикл строится следующим образом: вычёркиваются (мысленно) все строки и столбцы, содержащие ровно одну заполненную клетку, при этом считается, что выбранная клетка без поставки является заполненной; все оставшиеся после вычеркивания клетки составляют цикл и лежат в его углах, они соединяются ломаной линией.
В каждую клетку цикла, начиная с незаполненной, поочередно вписывают знаки “+” и “-“. В клетках с отрицательными знаками выбирается минимальная величина поставки, обозначаемая как D. В те вершины, которые имеют знак “+” прибавляется поставка D, а в вершинах со знаком “-“ поставки уменьшаются на величину D. При этом суммы поставок по строкам и столбцам не изменяются. В результате клетка, для которой строился цикл, станет занятой, а в одной из бывших занятых клеток окажется нулевая поставка и её надо объявить свободной. Общее количество заполненных клеток не изменится, следовательно, новый план перевозок является невырожденным.
Если в результате пересчета одновременно в нескольких ранее занятых клетках цикла поставки примут нулевые значения, то свободной объявляется лишь одна из них. Остальные считаются условно занятыми с нулевыми поставками.
Значения переменных, включенных в цикл, после пересчета переносятся в новую таблицу без изменений. Полученный новый план проверяется на оптимальность.
Такое улучшение плана можно проводить неоднократно до тех пор пока все критерии для незаполненных клеток окажутся dij<=0. Затем вычисляется оптимальная стоимость перевозок.
Пример. Используя метод потенциалов, составьте план перевозок однородного от пунктов производства к пунктам потребления, при котором суммарные транспортные расходы будут минимальными.