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

Каждому поставщику (ограничению по запасам) поставим в соответствие потенциал u_i (i = ), а каждому потребителю (ограничению по спросу) — потенциал v_j (j = ).

Согласно теореме о потенциалах, каждой занятой клетке будет соответствовать уравнение u_i + v_j = c_ij. Так как всех занятых клеток должно быть т+п– 1, т. е. на единицу меньше числа потенциалов, то для определения чисел u_i, v_j необходимо решить систему из т+п– 1 уравнений с т+п неизвестными: u_i+ v_{j =} c_ij. Одному из потенциалов задают обычно значение, равное нулю.

Для исследования плана на оптимальность по каждой свободной клетке проверяется условие u_i+ v_j ≤ c_ij. Если хотя бы одна свободная клетка не удовлетворяет данному условию, то опорный план не является оптимальным, его можно улучшить за счет загрузки этой клетки. Если таких клеток несколько, то наиболее перспективной для загрузки является клетка, для которой разность (оценка) между тарифом клетки и суммой потенциалов наименьшая, т. е. S_ij = с_ij – (u_i + v_j) < 0.

Например, для клеток (i;k) и (i;t) имеем оценки: S_ik= -5, S_it= -10. Здесь наиболее потенциальной является клетка (i;t). Экономически оценка показывает, на сколько денежных единиц уменьшатся транспортные издержки от загрузки данной клетки единицей груза. Эффективность плана от загрузки потенциальной клетки грузом в λ единиц составит ΔF = S_ij · λ ден.ед. Если для всех свободных клеток оценки S_ij≥ 0, то опорный план перевозок является оптимальным.

Итак, если для опорного плана перевозок указанное условие оптимальности не выполняется, то за счет загрузки свободной клетки с отрицательной оценкой план перевозок улучшается. Для наиболее перспективной свободной клетки строится замкнутый цикл с вершинами в загруженных клетках. Вершинам этого цикла условно приписываются знаки: свободной клетке – плюс, следующей по часовой или против часовой стрелки занятой клетке – минус, следующей – снова плюс и т. д. Из поставок в клетках цикла с «отрицательными» вершинами выбирается наименьшее количество λ груза, которое и перемещается по клеткам этого цикла: прибавляется к поставкам в положительных вершинах и вычитается из поставок в отрицательных вершинах, в результате чего баланс цикла не нарушится.

Сформулируем алгоритм решения ТЗ методом потенциалов:

1) построить опорный план по одному из правил;

2) вычислить потенциалы поставщиков и потребителей u_i и v_j (i = ),; (j = ), решив систему уравнений вида u_i+ v_{j =} c_ij;

3) вычислить оценки Sij для всех свободных клеток по
формуле S_ij = с_ij – (u_i + v_j). Если все S_ij≥ 0, то полученный план является оптимальным. При этом если все S_ij≥ 0, то полученный оптимальный план единственный. В случае, если хотя бы одна оценка S_ij= 0, имеем бесчисленное множество оптимальных планов с одним и тем же значением целевой функции.

ПРИМЕР 2.1: В трех хранилищах А₁, А₂, А₃ имеется соответственно 70, 90 и 50 т топлива. Требуется спланировать перевозку топлива четырем потребителям В₁, В₂, В₃, В₄, спрос которых равен соответственно 50, 70, 40 и 40 т, так, чтобы затраты на транспортировку были минимальны. Стоимость перевозки 1 т указана в табл. 2.1.

Таблица 2.1.

Хранилища	Потребители	Запас топлива, т
B1	В2	В3	B4
Стоимость перевозки 1 т топлива, ден.ед.
A1
А2
А3
Потребность в топливе, т					210 > 200

РЕШЕНИЕ: Поскольку запасы топлива в хранилищах превышают спрос потребителей, задача является открытой, вводится фиктивный потребитель, спрос которого b₅ = 210 – 200 = 10 т. Все затраты для фиктивного потребителя с_i5 = 0 (i = ). После введения фиктивного потребителя открытая модель задачи преобразовалась в закрытую, а распределительная таблица принимает вид таблицы 2.2.

Таблица 2.2.

Хранилища	Потребители	Запас топлива, т
B1	В2	В3	В4	В5
Стоимость перевозки 1 т топлива, ден. ед.
А1
А2
А3
Потребность в топливе, т

Исходный опорный план получим, например, по правилу «минимального элемента». Так как наименьшими являются нулевые тарифы для клеток (1; 5), (2; 5), (3; 5), то загрузим первой, например, клетку (1; 5), х₁₅= 10 т. Второй загружаем клетку (3; 3), х_зз = 40 т. Далее загружаем клетки (1; 2), (3; 1), (2; 2), (2; 4), полагая х₁₂ = 60 т, х₃₁ = 10 т, х₂₂ = 10 т, х₂₁ = 40 т, х₂₄= 10 т (таблица 2.3).

Таблица 2.3.

В А

B1

В2

В3

В4

В5

За-пас

А1

+

2

– 0

u1=0

А2

–

+ 0

u2=1

А3

u3=-1

Спрос

v1=3

v2=2

v3=2

v4=6

v5=0

В результате распределения топлива по потребителям получили невырожденный план: условие для занятых клеток m+n–1=3+5–1=7 выполняется.

Для определения потенциалов составляем уравнения для занятых клеток: u₁ + v₂ = 2, u₁ + v₅ = 0, u₂ + v₁ = 4, u₂ + v₂ =3, и₂ + v₄ =7, u₃ + v₁ = 2, u₃ + v₃ =1. Положим, например, u₁ = 0, тогда и₂ = 1, u₃ = –1, v₁ =3, v₂ = 2, v₃ = 2, v₄ = 6, v ₅ = 0.

Определим оценки свободных клеток:

S11 = 5 − (0 + 3) = 2 > 0, S23 = 5 − (1 + 2) = 2 > 0, S34 = 5 − (-1 + 6) = 0,

S13 = 3 − (0 + 2) = 3 > 0, S25 = 0 − (0 + 2) = -2 < 0, S35 = 0 − (-1 -0) = 2 > 0,

S14 = 6 − (0 + 6) = 0, S32 = 4 − (-1 + 2) = 3 > 0,

Определив потенциалы, устанавливаем, что среди оценок свободных клеток одна отрицательная: S₂₅ = –1, следовательно, план перевозок можно улучшить за счет загрузки клетки (2;5). Цикл для нее выделен линией в таблице 2.3.

Наименьшее количество топлива в отрицательных вершинах цикла равно 10 т. После смещения по циклу 10 т получаем новый план перевозок (таблица 2.4). Полученный план является вырожденным. Поставим число 0, например, в клетку (2; 2).

Таблица 2.4.

В А

B1

В2

В3

В4

В5

За-пас

А1

u1=-1

А2

u2=0

А3

u3=-2

Спрос

v1=4

v2=3

v3=3

v4=7

v5=0

Для нового плана определяем новые потенциалы и находим оценки свободных клеток: S₁₁ = 2 >0, S₁₃ = l >0, S₁₄ = 0, S₁₅ = 1 > 0, S₂₃ = 2 > 0, S₃₂ = 3 > 0, S₃₄=0, S₃₅ = 2 >0.

Оценки всех свободных клеток S_ij > 0, следовательно, получен оптимальный план. Поскольку среди оценок имеются равные нулю, то за счет загрузки клеток (1; 4), (3; 4) можно получить новые планы, но значение целевой функции не изменится. Это случай бесчисленного множества оптимальных планов.

Итак, в таблице 2.4 получили оптимальный план

Х^* = , для которого значение целевой функции равно

F(X^*) = 2 · 70 + 4 · 40 + 7 · 40 + 2 · 10 + 1 · 40 = 640.

Десять тонн топлива, находящегося в хранилище А₂, осталось нераспределенным.