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) и т. д. Через конечное число таких шагов будет найдено оптимальное решение транспортной задачи.
О Рассмотрим следующую транспортную задачу:
4 | 3 | 6 | 4 | 40 |
I | 6 | 2 | 8 | 30 |
2 | 4 | 5 | 7 | 20 |
30 | 25 | 15 | 20 | hi . |
Ниже приведены все этапы решения этой задачи (начальное опорное решение построено методом «минимального элемента»):
зо
25
15
р=5
^ч^ | і | 3 | 2 | 4 |
О | 4 | 3 20 | 6 | 4 20 |
0 | 1 15 | 6 | 2 15 | 8 |
і | 2 15 | 4 5 | 5 | 7 |
В последней таблице записан оптимальный план перевозок, стимость которых составляет 20 ■ 3 + 20^4+15 • 1 +15-2+15-2 + + 5 4=235 единиц.
Обсуждение Справочник по математике для экономистов
Комментарии, рецензии и отзывы