Инструменты пользователя

Инструменты сайта


examination:mo:question10

Вопрос 10

Метод потенциалов

Этот первый точный метод решения транспортной задачи предложен в 1949 году Кантаровичем А. В. И Гавуриным М. К. по существу он является детализацией метода последовательного улучшения плана применительно к транспортной задаче. Однако в начале он был изложен вне связи с общими методами линейного программирования. Несколько позднее аналогичный алгоритм был разработан Данциом, который исходил из общей идеи линейного программирования. В американской литературе принято называть модифицированным распределительным методом. Метод потенциалов позволяет определить отправляясь от некоторого опорного плана перевозок построить решение транспортной задачи за конечное число шагов (итераций).

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

В основе данного метода лежит признак оптимальности:

1)

2) - для базисных клеток

Ui - потенциал пунктов производства

Vj – потенциал пунктов потребления

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

Далее составляем систему потенциалов. Эта система недоопределенная, поэтому можно один потенциал назначить произвольно, а остальные по условию 2).

После проверяется выполнение условия 1). Если условие выполняется, то план является оптимальным, если не выполняется, то ищем клетку, в которой «сильнее всего» не выполняется условие и отмечаем ее. Эта клетка обязательно составляет с некоторыми клетками текущего базисного решения единственный цикл. Составляем таблицу, в которой описан цикл. Рассматриваем две клетки полученной таблицы, по вертикали (выше/ниже) и по горизонтали (левее/правее) от отмеченной клетки. Затем из этих клеток вычитаем найденное значение, а к другим клеткам (отмеченной и к той, что по диагонали к ней) прибавляем. Получаем новое базисное решение, с которым продолжаем работать таким же образом. Повторяем эти действия, пока не получим оптимальное решение.

Конечность метода

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

examination/mo/question10.txt · Последние изменения: 2014/01/15 12:19 (внешнее изменение)