Метод потенциалов

Согласно теореме о потенциалах, каждой занятой клетке будет соответствовать уравнение . Так как всех занятых клеток должно быть , т.е. на единицу меньше, то для определения чисел и , необходимо решить систему из урав-нений с неизвестными. Система неопределенная, и, чтобы найти част-ные решения, одному из потенциалов придается произвольной числовое значение, тогда остальные потенциалы определятся однозначно. Для облегчения расчетов одному из по-тенциалов придается обычно значение, равное нулю.

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

.

Если для всех свободных клеток оценки , то опорный план перевозок явля-ется оптимальным. Если для опорного плана перевозок указанное условие оптимальности не выполняется, то за счет загрузки свободной клетки с отрицательной оценкой план перевозки улучшается. Для наиболее перспективной свободной клетки строится замк-нутый цикл с вершинами в загруженных клетках. Вершинам этого цикла условно припи-сываются знаки: свободной клетке – знак «+», следующей по часовой или против часовой стрелки занятой клетке – знак «-», следующей – снова «+» и т.д. Из поставок в клетках цикла с «отрицательными» вершинами выбирается наименьшее количество l груза, ко-торое и перемещается по клеткам этого цикла: прибавляется к поставкам в положи-тельных вершинах и вычитается из поставок в отрицательных вершинах, в результате чего баланс цикла не нарушается.

В общем случае цикл представляет собой замкнутую ломаную линию, состоящую из звеньев, пересекающихся под прямым углом. Каждое звено соединяет две клетки строки (столбца). Цикл включает одну свободную клетку, остальные клетки цикла заняты. В цикле всегда четное число клеток. Для свободной клетки всегда можно построить единственный цикл. Если из занятых клеток образуется цикл, то план перевозок не является опорным. Цикл строится лишь для свободных клеток.

Сформулируем алгоритм решения ТЗ методом потенциалов:

1) построить опорный план;

2) вычислить потенциалы поставщиков и потребителей и , решив систему уравнений вида ;

3) вычислить оценки для всех свободных клеток по формуле . Если , то полученный план является оптимальным. При этом если все , то по-лученный оптимальный план единственный. В случае, если хотя бы одна оценка , имеем бесчисленное множество оптимальных планов с одним и тем же значением целевой функции.

Пример 17.1. В пунктах производится однородная продукция в коли-чествах единиц. Готовая продукция поставляется в пункты , потребности которых составляют единиц. Стоимость c_ij перевозки единицы продукции из пункта A_i в пункт B_j заданы матрицей :

.

Требуется:

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

2) вычислить суммарные затраты f_min.

Дата добавления: 2014-01-04