Решение транспортных задач методом потенциалов (стр. 2 из 8)

Этап 1. На этом этапе производится исследование плана

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

для всех . (1.3)

В силу предположения о невырожденности исследуемой задачи любые два пункта

, можно соединить маршрутом, состоящим из основных коммуникаций плана . Далее, из опорности плана вытекает, что отмеченный маршрут строится однозначно. Поэтому решение системы (1.3) осуществляется предельно просто.

Зададимся значением одной из неизвестных систем (1.3), например положим

. Допустим, что пункт снабжает в соответствии с планом пункты . Тогда из соответствующих уравнений системы (1.3) определяем

.

Далее аналогичным способом определяем значения

для тех , которые снабжают один из пунктов . Например, если снабжает пункт , то

.

Затем определяются

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

Если предварительные потенциалы

, таковы, что для любой пары i, j имеет место неравенство

,

то функция W, определяемая условиями

- потенциал задачи T и, следовательно, , будучи потенциальным, является вместе с тем и оптимальным планом исследуемой задачи.

Если же для некоторых индексов i, j

,

то план

не оптимален. Необходим переход к этапу 2, на котором этот план будет улучшен.

Этап 2. Вычислим уклонения

( ).

По условию среди чисел

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

.

Соединим пункты

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

Рассмотрим перевозки по тем коммуникациям маршрута, которые при движении от

к проводятся в положительном направлении, т.е. от пункта производства к пункту потребления. Минимальную среди них обозначим через . Таким образом,

.

Введем в план

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