Алгоритм метода потенциалов

Построение опорного плана

Задачи имитационного моделирования решаются итерационными методами (методами приближений). Решение транспортной задачи проводят в два этапа.

Методика решения транспортной задачи

1. Построение опорного плана. Находят произвольное решение, хотя бы и неудачное.

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

Одним из наиболее эффективных методов построения опорного плана является метод аппроксимации Фогеля, в основе которого лежит концепция штрафов, взимаемых за выбор неоптимального с точки зрения транспортных издержек и маршрута.

Алгоритм метода аппроксимации Фогеля

1. Вычисление разностей в каждой строке и каждом столбце матрицы между наименьшей стоимостью и ближайшей к ней по величине. Разности по строкам записываются справа в столбце разностей, разности по столбцам ‑ внизу в строке разностей.

2. Поиск максимальной из всех разностей, как по строкам, так и по столбцам (максимальная разность обводится рамкой).

3. Размещение в клетке, где находится наименьшая стоимость перемещения ресурсов для помеченной строки или столбца, максимально возможного количества ресурсов.

Когда все ресурсы отправителя в данной строке будут исчерпаны, строка исключается из дальнейших расчетов (во все клетки данной строки заносится прочерк).

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

5. Поиск минимального элемента в строке или в столбце с максимальной разностью, размещение в данной клетке максимально возможного количества ресурса, после чего возвращение к пункту 4, пока не будут распределены все ресурсы.

Нахождение оптимального плана

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

dij–cij=zij,

где cij – затраты, связанные с доставкой одной единицы ресурса из i-го в j-й пункт; zij – расчетные затраты, связанные с доставкой одной единицы ресурса из i-го в j-й пункт, для тех клеток опорного плана, ресурсы в которые не распределены.

Если все δij > 0, то данный план является оптимальным, если нет, то требуется его улучшение.

Пусть имеется матрица перевозок, соответствующая начальному решению хij ≠ 0 (распределенные ресурсы). Для свободных переменных (ресурсы не распределены) xij = 0. Клетки, соответствующие свободным ресурсам, помечены звездочками.

В крайний левый столбец матрицы введем неизвестные ui, а в верхнюю строку – неизвестные vj. Переменные ui и vj называются потенциалами. Они должны для всех i, j, соответствующих начальному решению, удовлетворять линейной системе уравнений

ui + vj = cij, (1)

Ранг системы уравнений для всех базисных решений равен
n+m–1, и, следовательно, систему всегда можно решить следующим способом. На первом шаге полагают un = 0. Если на k-м шаге найдено значение неизвестной, то в системе всегда имеется еще не определенная неизвестная, которая однозначно может быть найдена на (k+1)-м шаге из уравнения (1), так как значение другой неизвестной в этом уравнении уже известно. Это верно до тех пор, пока не найдены все неизвестные. То, какую неизвестную можно найти на (k+1)-м шаге, определяют методом проб.

Последовательность действий алгоритма

1.Составить и решить систему уравнений ui + vj = cij для клеток, в которые распределены ресурсы. Для облегчения расчетов рекомендуется задаваться нулевым значением одного из неизвестных (например u3=0).

2. Определить расчетные значения затрат zij для клеток, в которые ресурсы не распределены (со свободными переменными):

zij = ui + vj;

3. Вычислить разность заданных и расчетных затрат

dij = cij – zij

и проверить условие оптимальности dij > 0.

Если все dij > 0, то исходный план является оптимальным, и переходят к пункту 5, в противном случае переходят к построению нового плана.

4. Построить новый план (уточнить опорный план).

Выбрать dαβ, равное максимальному по модулю dij из состава отрицательных dij, т.е.

dαβ = max |–dij|, dij < 0.

Индексом αβ помечена свободная переменная xαβ, которая соответствует dαβ. Соответствующую aβ клетку транспортной таблицы отмечают знаком “+”.

Кроме клетки αβ транспортной таблицы, знаками «–» и «+» помечают клетки таблицы, в которые ресурсы распределены таким образом, что в каждой строке и столбце число знаков «+» будет равно числу знаков «–»,причем в каждой строке и в каждом столбце содержится максимум по одному «+» и «–».

Проставленные в таблице знаки «+» и «–» образуют прямоугольник, в клетках которого расположены соответствующие знаки. Этот прямоугольник представляет фрагмент матрицы, который состоит из четырех клеток, в которых проводят перераспределение ресурсов.

 

– + ¬dαβ<0
+ –  

 

Затем определяют минимум M из всех элементов, помеченных знаками «–», и выбирают клетку Z*, где этот минимум достигается. При этом Z* обозначает клетку, в которую ресурсы далее распределяться не будут, а все ее содержимое будет распределено между остальными тремя клетками по следующему правилу:

а) в клетку αβ новой таблицы, записывается число M;

б) клетка Z* остается пустой;

г) в остальных клетках, помеченных знаками «+» и «–», число M вычитается из стоящего в клетке числа или складывается с ним, в соответствии со знаками;

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

 

  Вγ Вβ  
Аα хαγ–М +М ¬dαβ<0
Аε Хεγ+М ¬Z*

 

Для его построения нового опорного плана строится фрагмент опорного плана относительно клетки αβ, имеющей отрицательный потенциал.

5. Определить значение целевой функции, с учетом перераспределения в матрице (уточнение матрицы проводится до тех пор, пока хотя бы одно значение di <0).

Далее рассчитываются суммарные затраты по новому плану:

На следующих шагах оптимизации повторяются пункты 1–5 алгоритма до тех пор, пока все δij не будут больше 0.