9.14. решение транспортной задачи методом потенциалов

9.14. решение транспортной задачи методом потенциалов

Решение транспортной задачи методом потенциалов проводится по следующей схеме:

1) находят начальное опорное решение а1 = (х'ц; х'^ ..J хт„). (Например, методом «минимального элемента».) Если в транспортной таблице заполненных клеток оказалось меньше, чем т + п — 1, дополнительно дописывают нули так, чтобы получился ацикличный набор из т + п — 1 заполненных клеток;

вычисляют потенциалы и, (<=1, 2, m); vj (J=, 2, п) опорного решения at. Если для всех незаполненных клеток (г, J) ui+vj^dj, то <*! — оптимальное решение и транспортная задача решена. В противном случае выбираем некоторую клетку (г, s) такую, что u,+vs>c„;

в транспортной таблице строим цикл, одна вершина которого находится в клетке (г, s), а все остальные вершины — в заполненных клетках (такой цикл всегда существует, и притом только один). Каждой вершине цикла присваивают знак « + » или « —» следующим образом: вершине в клетке (г, s) присваивают знак «+», а дальше расставляют знаки так, чтобы они от вершины к вершине чередовались.

Обозначим через р наименьшее из чисел {jc'y}, стоящих в клетках, которым присвоен знак «—»; пусть р=хы (если число находится не в одной, а в нескольких клетках, выбираем любую из них). После этого заполняем транспортную таблицу согласно следующему правилу:

а) клетки, в которые не попали вершины цикла, заполняют так

же, как и раньше;

б) если клетке (/, J) присвоен знак « + », то в эту клетку

записывают число х'у+р;

в) клетку {к, I) не заполняют, а в остальные отрицательные

клетки (i,J) записывают число хи—р.

В результате получаем ацикличный набор из т+п— 1 заполненных клеток транспортной таблицы, который определяет опорное решение а2 такое, что /(a2)</(at).

Принимая а2 за исходное опорное решение, повторяем п. 2) и 3) и т. д. Через конечное число таких шагов будет найдено оптимальное решение транспортной задачи.

О Рассмотрим следующую транспортную задачу:

Ниже приведены все этапы решения этой задачи (начальное опорное решение построено методом «минимального элемента»):

зо

25

15

р=5

В последней таблице записан оптимальный план перевозок, стимость которых составляет 20 ■ 3 + 20^4+15 • 1 +15-2+15-2 + + 5 4=235 единиц.