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

⇐ ПредыдущаяСтр 14 из 17Следующая ⇒

С помощью метода потенциалов, уменьшающего объём вычислений, легко определить, является ли полученное решение оптимальным. Так для определе-ния оптимальности решения, представленного таблицей 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

Базы	Заказчики				Запасы на базах
Базы	В₁	В₂	В₃	В₄	Запасы на базах
А₁	70 140	50 60	15 100	80 –	300 т.
А₂	80 30	90 –	40 –	60 120	150 т.
А₃	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 т.км.

Задания для самостоятельной работы

Расчетная работа 4

Вычислить определитель

С матрицами А, В, С совершить указанные действия. Найти обратную к матрице А.

Решить системы линейных уравнений: а) методом Крамера; б) методом Гаусса.

Найти начальное опорное решение методом северо-западного угла и методом минимального элемента.

1		2
3		4
5		6
7		8

5. По указанным ниже данным о ресурсах a_i , потребностях b_j и матрицы коэффициентов затрат с c оставить математические модели и решить соответствующие транспортные задачи.