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

1. Построить опорный план и проверить его на вырожденность. Опорный план – это первое приближение.

Для построения опорного плана можно использовать:

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

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

Клетки, которые содержат поставки, называются базисными, все остальные – свободными.

Целесообразно проверить опорный план на корректность. Как теперь рассчитать общий грузооборот? Функция, которую нужно минимизировать.

F_сз = 40*10 + 60*9 + 20*7 + 110*13 + 20*8 + 30*7 + 60*1 + 30*2 = 2960 тыс.ед.*км.

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

Проверка матрицы на вырожденность: должно выполняться условие: n + m – 1 = N_баз, где n – число строк (число производителей), m – число столбцов (число потребителей), N_баз­­ – количество базисных клеток.

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

Если n + m – 1 > N_баз, матрица вырождена, нужно добавить в нее базисные клетки с нулевыми поставками рядом с клетками, единственными по строке и столбцу.

Если n + m – 1 < N_баз, значит, в какую-то клетку введена не максимально возможная поставка.

В данном случае условие выполняется: 4 + 5 – 1 = 8.

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

б) Метод наименьшего элемента (более оптимальное решение). Это наиболее предпочтительный метод при ручном решении.

Максимально возможная поставка записывается сначала в ячейку с минимальной стоимостью, затем в ячейку со следующей по величине стоимостью и т.д.

Проверка на корректность, затем – расчет общего грузооборота.

F_нэ = 50*8 + 50*5 + 40*4 + 50*7 + 60*13 + 90*1 + 30*4 = 2150 тыс.ед.*км.

Проверка на вырожденность: 4 + 5 – 1 ¹ 7. Нужно добавить одну нулевую клетку.

2. Проверить план на оптимальность.

2.1. Рассчитать потенциалы строк и столбцов.

Потенциалы – это числа, которые назначаются строкам и столбцам.

Будем обозначать: u₁, u₂, … u_n – потенциалы строк, v₁, v₂, … v_m – потенциалы столбцов.

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

2) По имеющимся базисным клеткам рассчитать потенциалы оставшихся строк по формуле:

v_j = u_i + c_ij.

Потенциал потребителя равна потенциалу производителя + стоимость перевозки. С экономической точки зрения v_j – это стоимость продукта в точке потребления. u_i – стоимость продукта в точке производства.

То есть, сначала берем заполненную строку и рассчитываем потенциалы столбцов: v_j = u_i + c_ij. Потом рассчитываются потенциалы строк: u_i = v_j – c_ij.

F = 1970 тыс.ед.*км.

2.2. Проверить свободные клетки на соответствие критерию оптимальности: v_j – u_i £ c_ij.

Если критерий выполняется для всех свободных клеток, план оптимален. Клетки, для которых критерий не выполняется, отметить звездочкой.

3. Если план не оптимален, улучшить план по одной из отмеченных свободных клеток. Оптимально выбирать ту, для которой критерий не выполняется в большей степени.0

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

Теперь для клетки BH нужно сформировать перераспределение поставок.

В эту клетку нужно разместить поставку. Указывается +.

Перераспределение заключается в том, что к поставкам в положительных клетках прибавляется объем грузооборота, а из поставок в отрицательных клетках – вычитается.

Поставки нужно перераспределить на величину минимальной поставки в отрицательной клетке. Потому что в клетке не может содержаться отрицательное значение.

Значение стоимости равно F = 1950 тыс.ед.*км.

3.2. Перейти к шагу 2. Последовательность шагов 2 и 3 повторяется до тех пор, пока не будет получен оптимальный план.

План оптимален. Значение стоимости F = 1920 тыс.ед.*км.