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

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

Методы построения опорного плана

а) Метод северо-западного угла.

Метод позволяет за n+m-1 шаг заполнить клетки таблицы таким образом, чтобы удовлетворить все потребности, исчерпав при этом все запасы. Заполнение клеток таблицы начинается с левой верхней клетки ("северо-западной"), в которую ставят максимально возможное число, т.е. минимальное из чисел запасов и потребностей для этой клетки. При этом исчерпываются либо запасы, либо потребности (вычеркивается строка или столбец), выбирается следующая «северо-западная» клетка и т.д.

б) Метод минимального элемента.

Заполнение клеток осуществляется по принципу: "Самая дешевая перевозка осуществляется первой". Выбирается клетка с минимальным тарифом и заполняется максимально возможным числом, при этом исчерпываются либо запасы, либо потребности (вычеркивается строка или столбец), выбирается следующая клетка с минимальным тарифом и т.д.

в) Метод аппроксимации Фогеля.

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

Как правило, при построении опорного плана этими тремя методами выполняется следующее соотношение: F_в(x)F_б(x)F_а(x).

Схема решения.

1. Строят опорный план одним из методов.

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

ТЕОРЕМА. Если для некоторого опорного плана транспортной

задачи существуют такие числа и, что

при x_ij > 0 (4)

и при x_ij = 0 (5)

для всех и, то этот план является оптимальным.

ОПРЕДЕЛЕНИЕ 4. Числа и(,) называются потенциалами, соответственно, поставщиков и потребителей.

Т.о., найдя потенциалы поставщиков и потребителей, удовлетворяющие условиям теоремы, мы докажем оптимальность построенного плана. Как их найти? Т.к. число заполненных клеток, x_ij > 0, равно n+m-1 (невырожденный план), то система (4) с n+m неизвестными содержит n+m-1 уравнение. Положим одно из неизвестных равным нулю и последовательно найдем значения остальных неизвестных. Затем для всех свободных клеток, x_ij = 0, определим числа .

Если среди чисел нет положительных, то условия теоремы выполнены, и план является оптимальным. Если существует> 0, то построенный план не оптимален, и его следует улучшить.

3. Алгоритм улучшения плана:

1) среди всех > 0 выбирают максимальное;

2) для соответствующей клетки строят цикл пересчета;

3) помечают вершины цикла пересчета последовательно знаками "+" и "-" ,

начиная с "+" в исходной клетке;

4) среди чисел, стоящих в клетках, помеченных "-" , определяют минимальное;

5) к значениям, стоящим в "+"-клетках, прибавляют это минимальное число, а из

значений, стоящих в "-"-клетках, это число вычитают.

ОПРЕДЕЛЕНИЕ 5. Циклом пересчета называется ломаная линия, вершины которой расположены в занятых клетках, а звенья - вдоль строк и столбцов, причем в каждой вершине цикла может быть только два звена.

4. Измененный таким образом план опять проверяют на оптимальность, т.е. переход к п. 2.