Алгоритм решения транспортной задачи

Метод Фогеля.

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

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

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

Проверка плана транспортной задачи на оптимальность основывается на критерии оптимальности, связанном с задачей, двойственной к рассматриваемой транспортной задаче (6):

в которой — двойственные переменные.

Учитывая теоремы двойственности (см. 4.3) имеем, что если — оптимальный план прямой транспортной задачи, то ему соответствует система из чисел и , удовлетворяющих условиям:

для

для ().

Числа и называют потенциалами соответственно строки и столбца.

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

1. Каждой занятой клетке транспортной таблицы соответствует сумма потенциалов, равная стоимости перевозки этой клетки, т.е. ;

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

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

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

Дата добавления: 2014-12-29