Итоговое распределение поставок по методу потенциалов

Иногда в первоначальном плане или в процессе итераций количество занятых клеток может оказаться меньше, чем m + n – 1. Это, так назывемый, случай вырождения. Он грозит зацикливанием, т.е. бесконечным повторением итераций. Для предупреждения зацикливания базисный план или его итерации дополняются до необходимой величины m + n – 1 квадратами, в которых помещают перевозки, равные сколь угодно малой величине. В дальнейшем с этими перевозками, которые называют «нулевыми», выполняют те же действия, что и с обычными перевозками.

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

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

.

Такие транспортные задачи называются закрытыми. Если же нет равенства ресурсов и потребности, модель называется открытой. В такой модели ограничения выражаются неравенствами. При этом возможны два случая. В первом случае ресурсы превышают потребность, и задача состоит в том, чтобы определить, у кого из поставщиков и какое количество продукции следует оставить с точки зрения минимизации транспортных расходов. Во втором случае ресурсы меньше потребности, и задача состоит в том, чтобы определить, кто из потребителей и какое количество продукции должен недополучить при минимизации транспортных расходов.

Для решения открытой транспортной задачи методом потенциалов в таблицу вводят «фиктивного» потребителя, если ресурсы превышают потребность, или «фиктивного» поставщика, если потребность превышает ресурсы. Транспортные расходы по перевозке единицы продукции от «фиктивного» поставщика или к «фиктивному» потребителю принимаются заведомо большими или равными нулю, чтобы не затруднять поиска оптимального плана прикрепления потребителей к поставщикам.