Решение транспортной задачи

Цель: Составить план перевозок горючего, минимизирующий общую сумму транспортных расходов.

Задача: В пунктах А и В находятся соответственно 150 и 90 т горючего. Пунктам 1, 2, 3 требуются соответственно 60, 70, 110 т горючего. Стоимость перевозки 1 т горючего из пункта А в пункты 1, 2, 3 равна 60, 10, 40 тыс. руб. за 1 т соответственно, а их пункта В в пункты 1, 2, 3 – 120, 20, 80 тыс. руб. за 1 т соответственно. Составить план перевозок горючего, минимизирующий общую сумму транспортных расходов.

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

Экономико-математическая модель задачи:

Пусть – Xij- объем перевозки от i- го поставщика j-ому потребителю.

Потребители Вj	В1	В2	В3	Запасы пост.
Поставщики Ai
А1	X11		X12		X13
А2	X21		X22		X23
Спрос потр.

Запасы на базах и спрос потребителей накладывают ограничения на переменную Xij.

Х₁₁ + Х₁₂ + Х₁₃ = 150

Х₂₁ + Х₂₂ + Х₂₃ = 90

(1) Х₁₁ + Х₂₁ = 60

Х₁₂ + Х₂₂ = 70

Х₁₃ + Х₂₃ = 110

Составим целевую функцию:

(2) Z = 60X₁₁ + 10X₁₂ + 40X₁₃ + 120 X₂₁ + 20X₂₂ + 80X₂₃ → min

Таким образом, на множестве неотрицательных решений, системы ограничений (1) найдем такое решение

Х₁₁ Х₁₂ Х₁₃

Х = Х₂₁ Х₂₂ Х₂₃ ,

при котором целевая функция (2) принимает наименьшее значение.

Занесем данные в транспортную таблицу:

Ui	Потребители Вj	В1	В2	В3	Запасы пост.
Поставщики Ai
U1=	А1
U2=	А2
	Спрос потр.
	Vj	V1=	V2=	V3=

Найдем первый опорный план поставок. Для этого воспользуемся методом наименьших затрат. Найдем в таблице клетку с наименьшим тарифом. Это клетка (1, 2). ЕЕ тариф С₁₂ = 10. Дадим в эту клетку максимально возможную поставку. Х₁₂ = min (150, 70) = 70. Клетку (2, 1) вычеркиваем (в эту клетку поставок давать не будем), т.к. потребность второго пункта полностью удовлетворена. Находим следующую клетку с наименьшим тарифом. Это клетка (1, 3), ее тариф С₁₃ = 40. Дадим в эту клетку максимально возможную поставку. Х₁₃ = min (150 – 70, 110) = 80. Клетку (1, 1) вычеркиваем (в эту клетку поставок давать не будем), т.к. запас первого поставщика (пункт А) полностью использован. Находим следующую клетку с наименьшим тарифом. Это клетка (2, 3), ее тариф С₂₃ = 80. Дадим в эту клетку максимально возможную поставку. Х₂₃ = min (110 – 80, 90) = 30. И в последнюю свободную клетку (2, 1) даем поставку 60.

Проверяем баланс по строкам и столбцам (соответствующие суммы).

Т.О. получен первый опорный план поставок. Полученный план невырожденный, т.к. число занятых клеток равно рангу системы. Ранг системы вычисляется по формуле: r = m + n – 1, где m – число поставщиков, n – число потребителей.

r = 2 + 3 – 1 =4, число занятых клеток р = 4.

Х₁ = 0 70 80

60 0 30

Z₁ = 70*10 + 80*40 + 60*120 + 30*80 = 13500 руб.

Проверим, будет ли полученный план оптимальным. Для этого воспользуемся методом потенциалов. Обозначим потенциалы поставщиков U_i , а потенциалы потребителей V_j . Для нахождения этих потенциалов составим систему уравнений по формуле U_i + V_j = С_{i j} , где С_{i j} – тариф занятой клетки.

U₁ + V₂ = 10 Эта система имеет бесконечное множество решений.

U₁ + V₃ = 40 Найдем одно их них. Положим U₁ = 0. Тогда V₂ = 10,

U₂ + V₁ = 120 V₃ = 40, U₂ = 40, V₁ = 80.

U₂ + V₃ = 80

Ui	Потребители Вj	В1	В2	В3	Запасы пост.
Поставщики Ai
U1=0	А1	—
U2=40	А2			—
	Спрос потр.
	Vj	V1=80	V2=10	V3=40

Далее, оценим свободные клетки по формуле: D_{i j} = С_{i j} – (U_i + V_j), где С_{i j} – тариф свободной клетки.

D₁₁ = 60 – (0 + 80) = - 20 ≤ 0, D₂₂ = 20 – (40 + 10) = - 30 ≤ 0

Среди оценок свободных клеток есть отрицательные. Это значит, что полученный план не является оптимальным. Поэтому надо перераспределить поставки в одну из этих свободных клеток (с отрицательной оценкой). Перераспределим поставки в клетку (1, 1) (отрицательная оценка по модулю меньше). Для этого введем несколько определений.

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

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

Цикл пересчета называется означенным, если в его вершинах расставлены знаки «+» и «−», так, что в свободной клетке стоит знак «+», а соседние вершины имеют противоположные знаки «−».

НАПРИМЕР

—	—	70 +	120 ‒	—
	— + *	20 ‒	—
—	60 ‒	—	50 +	—
	—	—	—	—

—	— *		120	—
	—		—
—	60	—		—
	—	—	—	—

Построим для клетки (1, 1) означенный цикл пересчета:

+ −

* 80

Величина пересчета λ = min (60, 80) = 60.

− 60 30 +

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

Ui		В1	В2	В3	Запасы пост.
U1=	А1
U2=	А2	—		—
	Спрос потр.
	Vj	V1=	V2=	V3=

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

Х₁ = 60 70 20

0 0 90

Z₁ = 60*60 + 70*10 + 20*40 + 90*80 = 12300 руб.

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

Для нахождения новых потенциалов составим систему уравнений по формуле U_i + V_j = С_{i j} , где С_{i j} – тариф занятой клетки.

U₁ + V₁ = 60 Эта система имеет бесконечное множество решений.

U₁ + V₂ = 10 Найдем одно их них. Положим U₁ = 0. Тогда V₁ = 60,

U₁ + V₃ = 40 V₂ = 10, V₃ = 40, U₂ = 40,.

U₂ + V₃ = 80

Ui		В1	В2	В3	Запасы пост.
U1=0	А1
U2=40	А2	—		—
	Спрос потр.
	Vj	V1=60	V2=10	V3=40

Далее, оценим свободные клетки по формуле: D_{i j} = С_{i j} – (U_i + V_j), где С_{i j} – тариф свободной клетки.

D₂₁ = 120 – (40 + 60) = 20 ≥ 0, D₂₂ = 20 – (40 + 10) = - 30 ≤ 0

Среди оценок свободных клеток есть отрицательная. Это значит, что полученный план не является оптимальным. Поэтому надо перераспределить поставки в одну из этих свободных клеток (с отрицательной оценкой). Перераспределим поставки в клетку (2, 2) (отрицательная оценка).

Построим для клетки (2, 2) означенный цикл пересчета:

− +

70 20

Величина пересчета λ = min (70, 90) = 70.

+ * 90 −

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

Ui		В1	В2	В3	Запасы пост.
U1=0	А1			—
U2=40	А2	—
	Спрос потр.
	Vj	V1=60	V2= - 20	V3=40

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

Х₁ = 60 0 90

0 70 20

Z₁ = 60*60 + 90*40 + 70*20 + 20*80 = 10200 руб.

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

Для нахождения новых потенциалов составим систему уравнений по формуле U_i + V_j = С_{i j} , где С_{i j} – тариф занятой клетки.

U₁ + V₁ = 60 Эта система имеет бесконечное множество решений.

U₁ + V₃ = 40 Найдем одно их них. Положим U₁ = 0. Тогда V₁ = 60,

U₂ + V₂ = 20 V₂ = - 20, V₃ = 40, U₂ = 40,.

U₂ + V₃ = 80

Далее, оценим свободные клетки по формуле: D_{i j} = С_{i j} – (U_i + V_j), где С_{i j} – тариф свободной клетки.

D₂₁ = 120 – (40 + 60) = 20 ≥ 0, D₁₂ = 10 – (0 + (- 20)) = 30 ≥ 0.

Среди оценок свободных клеток нет отрицательных. Все оценки положительны. Это значит, что полученный план оптимален.

Х_опт = 60 0 90

0 70 20

Z_опт = 60*60 + 90*40 + 70*20 + 20*80 = 10200 руб.

Экономический анализ. Общая сумма транспортных расходов будет минимальной и составит 10200 руб., если перевозку горючего запланировать следующим образом: из пункта А доставить в пункт 1- 60 тонн горючего, в пункт 3 – 90 тонн; из пункта В отправить в пункт 2- 70 тонн, в 3 пункт – 20 тонн горючего. При этом запасы в пунктах А и В полностью реализованы и потребности пунктов 1, 2 и 3 будут удовлетворены.