 |
 |
 |
 |
|
 |
 |
66
Из транспортной таблицы 3.7 видно, что полученный план оптимален, так как все разности
потенциалов для небазисных
клеток ?
i,j
= v
j
– u
i
не превышают соответствующих цен с
i,j
. По данному
плану вычисляется оптимальное (наименьшее) значение суммарных издержек на перевозку
Завершая разговор о методе потенциалов, следует отдельно остановиться на ситуации возникновения
вырожденного плана. Возможность получения вырожденного плана уже отмечалась при описании
метода северо-западного угла. Нетрудно заметить, что вырожденный план также может получиться на
этапе преобразования текущего плана по цепочке: если одинаковое минимальное значение будет
достигнуто сразу на нескольких клетках, помеченных знаком «—», то при вычитании перемещаемого
по цепочке объема в новом плане будет меньше чем m+n-1 ненулевых компонент. Способ преодоления
вырожденности в транспортной задаче весьма прост, а именно: предлагается дополнить текущий план
необходимым количеством нулевых клеток (фиктивными перевозками) таким образом, чтобы они
позволяли рассчитать полную систему потенциалов, и далее действовать в соответствии с правилами
описанного выше алгоритма. Фактически здесь мы имеем дело не с чем иным, как с аналогом метода
возмущений для транспортной задачи как частного случая ЗЛП. К такому выводу легко прийти, если
положить, что добавляемые фиктивные клетки содержат некоторый малый объем
?
.
3.2. СЕТЕВЫЕ ЗАДАЧИ
3.2.1. Основные понятия и определения. Многие экономические задачи, такие как перевозка
грузов, перекачка нефти и газа по трубопроводам, управление запасами и т. п., удобно моделировать и
решать в терминах сетей и потоков. Основой подобного рода моделей служат ориентированные или
неориентированные графы. Приведем некоторые определения.
Ориентированным графом называется тройка (I, D, G), в которой I — непустое множество
вершин,
D
—
множество
дуг
и G
— отображение, которое каждой дуге d?D ставит в
соответствие упорядоченную пару вершин (i, j), где i, j ? I.
Неориентированным графом
называется тройка (I, D, G), в которой I — непустое множество
вершин, D
— множество
ребер
и G — отображение, которое каждому ребру d?D ставит в
соответствие неупорядоченную пару вершин [i, j], где i, j? I.
Граф (I, D, G) называется конечным, если множества I и D конечны.