6. Исследование очередного решения на оптимальность

С помощью метода потенциалов, уменьшающего объём вычислений, легко определить, является ли полученное решение оптимальным. Так для определе-ния оптимальности решения, представленного таблицей 2, каждый тариф с_ij, находящийся в одной клетке с базисной переменной, выражается в виде суммы потенциалов соответствующей базы α_i и заказчика β_j. Тогда для найденного плана перевозок образуется система уравнений

с ₁₁ = α₁ + β₁ = 70,

с₁₂ = α₁ + β₂ = 50,

с₁₃ = α₁ + β₃ = 15,

с₂₁ = α₂ + β₁ = 80,

с₂₄ = α₂ + β₄ = 60,

с₃₄ = α₃ + β₄ = 11.

Если α₁ = 0, то β₁ = 70,

α₂ = 10, β₂ = 50,

α₃ = – 39, β₃ = 15,

β₄ = 50.

При этом значения алгебраической суммы тарифов для свободных клеток таблицы 2 оказываются равными

s₁₄ = c₁₄ – c'₁₄ = c₁₄ – (α₁ + β₄) = 80 – 50 = 30,

s₂₂ = c₂₂ – c'₂₂ = c₂₂ – (α₂ + β₂) = 90 – (10 + 50) = 30,

s₂₃ = c₂₃ – c'₂₃ = c₂₃ – (α₂ + β₃) = 40 – (10 + 15) = 15,

s₃₁ = c₃₁ – c'₃₁ = c₃₁ – (α₃ + β₁) = 50 – (–39 + 70) = 19,

s₃₂ = c₃₂ – c'₃₂ = c₃₂ – (α₃ + β₂) = 10 – (–39 + 50) = –1,

s₃₃ = c₃₃ – c'₃₃ = c₃₃ – (α₃ + β₃) = 90 – (–39 + 15) = 114.

В ычисления показывают, что план перевозок, соответствующий последнему решению, представленному в таблице 2, можно улучшить, производя цикл пересчёта со свободной клеткой (3;2):

Таблица 3

Базы	Заказчики				Запасы на базах
	В1	В2	В3	В4
А1	70 140	50 60	15 100	80 –	300 т.
А2	80 30	90 –	40 –	60 120	150 т.
А3	50 –	10 50	90 –	11 –	50 т.
Потребности заказчика	170 т.	110 т.	100 т.	120 т.	500 т. 500 т.

Исследование очередного решения на оптимальность продолжается аналогичным образом:

с ₁₁ = α₁ + β₁= 70, с₂₁ = α₂ + β₁= 80,

с₁₂ = α₁ + β₂= 50, и с₂₄ = α₂ + β₄= 60,

с₁₃ = α₁ + β₃= 15 с₃₂ = α₃ + β₂= 10.

Тогда, если α₁ = 0, то β₁= 70,

α₂ = 10, β₂= 50,

α₃ = – 40, β₃= 15,

β₄= 50.

При этом значения алгебраической суммы тарифов для свободных клеток таблицы 3 оказываются равными

s₁₄ = c₁₄ - c'₁₄ = c₁₄ – (α₁ + β₄) = 80 – 50 = 30,

s₂₂ = c₂₂ - c'₂₂ = c₂₂ – (α₂ + β₂) = 90 – (10 + 50) = 30,

s₂₃ = c₂₃ - c'₂₃ = c₂₃ – (α₂ + β₃) = 40 – (10 + 15) = 15,

s₃₁ = c₃₁ - c'₃₁ = c₃₁ – (α₃ + β₁) = 50 – (– 40 + 70) = 20,

s₃₃ = c₃₃ - c'₃₃ = c₃₃ – (α₃ + β₂) = 90 – (– 40 + 15) = 115,

s₃₄ = c₃₄ - c'₃₄ = c₃₄ – (α₃ + β₄) = 11 – (– 40 + 50) = 1.

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

Ответ: При оптимальном плане перевозок потребность заказчика В₁ удовлетворяется как базой А₁, из которой поступает 140т. так и базой А₂, из которой поступает 30т. ; потребность заказчика В₂ удовлетворяется базами А₁, из которой поступает 60т. и А₃, из которой поступает 50т.; потребность заказчика В₃ удовлетворяет база А₁ , из которой поступает 100т., а потребность заказчика В₄ удовлетворяет база А₂, из которой поступает 120т. При этом стоимость перевозок составит

F_опт. = 70 ·140 + 50 · 60 + 15 · 100 + 80 · 30 + 60 ·120 + 10 · 50 = 24400 (т.км.),

что меньше стоимости перевозки по первоначальному плану (F_нач.= 25650 т.км.) на 1250 т.км.

Пример №2

На трёх базах находится однородный груз. На базе А₁ в количестве 22т., на базе А₂ в количестве 13т., на базе А₃ в количестве 10т. Весь этот груз необходимо развести трём заказчикам так, чтобы стоимость перевозок была наименьшей. Заказчику в пункте В₁ должно поступить 20т., в пункте В₂ - 15т., в пункте В₃  10т. груза. В угловых скобках таблицы 4 указаны стоимости перевозки одной тонны груза между базами и заказчиками в тысячах рублей.