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

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

2. Строят начальное опорное решение (методом северо – западного элемента, минимального элемента или методом Фогеля).

3. Опорный план проверяется на условие «вырождения». Согласно теореме Данцига количество занятых клеток в плане не должно превышать суммарного числа строк и столбцов минус единицу (Для дальнейшего решения необходимо добиться того, чтобы количество занятых клеток в плане в точности равнялось суммарному числу строк и столбцов минус единица , этого можно добиться вводя при необходимости нулевые перевозки, т.е. заполняя некоторые клетки нулями), где К_з – число занятых клеток; n – число строк (пунктов отправления); m – число столбцов (пунктов назначения).

4. Строят систему потенциалов, соответствующих опорному плану. Для этого одной из строк, или одному из столбцов (обычно тому, которому соответствует большее число занятых клеток) присваивают произвольное значение «потенциал» (значение потенциала удобно брать больше, чем значение максимального тарифа) и через заполненные клетки, используя соотношение + = (где – потенциал строки, а – потенциал столбца), строят систему потенциалов, т.е. получают потенциалы всех строк и столбцов. (Поясним, что предложенная для построения системы потенциалов формула + = позволяет по известной себестоимости товара в пункте отправления путем прибавления к ней тарифа за транспортировку определить себестоимость товара в пункте назначения, и обратно, преобразовав формулу – = по известной себестоимости товара в пункте назначения, становится возможным, вычтя тариф за транспортировку, определить себестоимость товара в пункте отправления. Еще раз отметим, что система потенциалов строится только через заполненные клетки.)

5. Проверяют условие оптимальности + , это условие можно проверять только для свободных клеток таблицы, т.к. в заполненных оно всегда выполнено (Отметим, что невыполнение данного условия фактически означает возможность уменьшения себестоимости товара в пункте назначения, которое может быть достигнуто за счет перераспределения транспортных потоков).

6. Если условие оптимальности выполнено для всех клеток матрицы, то нами получен оптимальный план перевозок (т.к. уменьшения себестоимости товара в пунктах назначения за счет перераспределения транспортных потоков невозможно) и необходимо только найти значение целевой функции L (X). Если же для какой-либо клетки условие оптимальности нарушается, то необходимо применить «формальное правило улучшения плана» и вернуться к пункту 3.

Формальное правило улучшения плана:

а) начиная с клетки, имеющей нарушение, двигаясь только по горизонталям и вертикалям, строится замкнутый контур с вершинами в занятых клетках;

б) начиная с клетки, имеющей нарушение, нумеруются вершины контура (направление обхода контура значения не имеет);

в) в четных вершинах контура находится значение минимальной перевозки;

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

Задача

Найдем оптимальное решение транспортной задачи опорный план которой представлен следующей транспортной матрицей: