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

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

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

,

где под

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

.

Вспомним, что все элементы, стоящие в квадратной скобке, кроме

, являются - существенными. Поэтому

.

Учитывая далее отрицательность уклонения

и положительность , имеем

.

Итак, составленный новый план перевозок

, соответствующий меньшему значению линейной формы транспортной задачи. Этап 2, а вместе с ним и -я итерация закончены.

Покажем, что вновь составленный план

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

, , (1.4)

плана

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

Заметим, что в силу предположения о невырожденности только одна перевозка последовательности (1.4) равна нулю. Система основных коммуникаций плана

путем замены одной коммуникации.

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

Вырожденность.

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

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

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

При построении базиса нового плана нам, как и в случае общей задачи линейного программирования, необходимо знать ответ на два вопроса: какой вектор необходимо ввести в старый базис, какой вектор (один!) необходимо из него вывести? При ответе на первый вопрос случай вырожденности не приводит ни к каким дополнительным трудностям. Что касается второго вопроса, то критерий, который использовался для ответа на него в невырожденном случае: нулевыми могут стать сразу несколько перевозок, отвечающих нечетным коммуникациям маршрута этапа 2.

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

Рассмотрим произвольную транспортную задачу Т. Свяжем с ней семейство транспортных задач

, объемы производства и потребления которых выражаются через соответствующие величины задачи Т по формулам

,

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

Существует такое число , что при любом , удовлетворяющем условию

, (2.1)

задача

обладает свойством невырожденности.

Существует такое число , что при любых и , удовлетворяющих условиям

, (2.2)

справедливы следующие утверждения:

а) если

- опорный план задачи , то - опорный план задачи ;