Метод потенциалов решения транспортных задач

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

Введем строку потенциалов u _i и столбец потенциалов v _j.

Полагая, что u₁=0,  остальные u _i и v _j найдем так, чтобы

а) для заполненных клеток  выполнялись равенства ;

б) для незаполненных клеток  выполнялись равенства  (оценки пустых клеток).

Критерий оптимальности:

Если известны потенциалы решения Х₀ транспортной задачи и для всех незаполненных ячеек выполняются условия то Х₀ является оптимальным планом транспортной задачи.

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

Пример3: Проверить план,  построенный методом северо-западного угла на оптимальность методом потенциалов.

Возьмем таблицу с построенным планом и добавим еще столбец и строку потенциалов.

(перепишите в свою заготовленную таблицу план, полученный методом северо-западного угла).

По заполненным клеткам вычислим потенциалы по правилу :

Таким образом, мы вычислили потенциалы заполненных клеток.

Для пустых клеток вычислим их оценки .

Будем их записывать в верхний правый угол клетки.

Так среди оценок пустых клеток есть отрицательные – план не оптимальный.

Необходимо построить следующий план. Для этого построим цикл перерасчета таблицы.

Цикл перерасчёта таблицы – это последовательность клеток, удовлетворяющая условиям:

§   Одна клетка пустая с отрицательной оценкой, все остальные заполненные.

§   Любые две соседние клетки находятся в одной строке или в одном столбце.

§ Пустой клетке присваивают знак "+", остальным – поочерёдно знаки "–" и "+".

Далее составляем новую таблицу по следующему правилу:

§ Клетки вне цикла остаются без изменения.

§ В минусовых клетках находят число X = min(X_ij).

§ В плюсовых клетках цикла добавляем Х.

§ Из минусовых клеток цикла вычитаем Х.

Получим новую таблицу, дающую новое решение Х, такое, что F (X₁) ≤ F (X₀); оно снова проверяется на оптимальность через конечное число шагов, обязательно найдем оптимальный план транспортной задачи, ибо он всегда существует.

Пример4: Для плана примера 3 построим цикл перерасчета.

 

Заполним одну из пустых клеток с отрицательной оценкой. Возьмем клетку А3В3, так как в ней стоимость меньше, чем в клетке А3В1.

Построим цикл перерасчета:

Построим второй опорный план:

Заполненных клеток должно быть 3+5-1=7.

Вычислим суммарную стоимость перевозок для построенного плана:

F = 15*1+5*5+12*1+0*2+5*1+8*3+15*3=126.

Проверим план на оптимальность методом потенциалов.

Так среди оценок пустых клеток есть отрицательные – план не оптимальный.

Построим следующий план.  

Для этого построим цикл перерасчета таблицы.

Третий опорный план:

Вычислим суммарную стоимость перевозок для построенного плана:

F = 15*1+5*5+12*1+5*1+8*3+0*3+15*3=126.

Проверим план на оптимальность методом потенциалов.

Так среди оценок пустых клеток есть отрицательные – план не оптимальный.

Построим следующий план.

Для этого построим цикл перерасчета таблицы.

Четвертый опорный план:

Так как среди оценок пустых клеток нет отрицательных значений, то построенный план оптимальный.

При этом суммарная стоимость перевозок

F = 15*1+5*4+12*1+5*1+8*3+0*3+15*3=121 является минимальной.

Запишем ответ задачи:

Ответ: Чтобы транспортные расходы были минимальными 121 ден.ед. необходимо перевозить: с 1-го склада – 15 компьютеров в 1-ый магазин; со 2-ого склада – 12 - во 2-ой магазин, 8 - в 4-ый и 5 - в 5-ый магазин; с 3-его склада – 5 компьютеров в 1-ый магазин, 5 – во 2-ой и 10 – в 5-ый.

Контрольные вопросы

1. Как построить опорный план транспортной задачи?

2. В чем суть метода потенциалов?

3. Как строится цикл перерасчета?

Еще хотелось бы обратить ваше внимание, на различные виды циклов перерасчета таблицы.