Транспортная задача

^{Стоимость доставки единицы  продукции от поставщика A1 к указанным потребителям равна 4, 5, 2, 8, 6 ден.ед.}

^{Стоимость доставки единицы  продукции от поставщика A2 к указанным потребителям равна 3, 1, 9, 7, 3 ден.ед.}

^{Стоимость доставки единицы  продукции от поставщика A3 к указанным потребителям равна 9, 6, 7, 2, 1 ден.ед.}

^{Требуется найти оптимальное  решение доставки продукции от поставщиков  к потребителям с  максимальной прибылью.}

^{Решение :}  

Математическая  модель транспортной задачи:

F = ∑∑c_ijx_ij,    (14)

при условиях:

∑x_ij = a_i,  i = 1,2,…, m,   (15)

 

∑x_ij = b_j,  j = 1,2,…, n,   (16)

 

С целью составления  двойственной задачи переменные x_ij в условии (15) заменим на u₁, u₂, u_i,.., u_m, а переменные x_ij в условия (16) на v₁, v₂, v_j,.., v_n.

Поскольку каждая переменная x_ij входит в условия (15, 16) и целевую функцию (14) по одному разу, то двойственную задачу по отношению к прямой транспортной задаче можно сформулировать следующим образом.

Требуется найти  не отрицательные числа u_i (при i  = 1,2,…,m) и v_j (при j = 1,2,..,n), обращающие в максимум целевую функцию

G = ∑a_iu_i + ∑b_jv_j  (17)

при условии

u_i + v_j ≤ c_ij, i = 1,2,..,m; j = 1,2,..,n    (18)

В систему  условий (4) будет mxn неравенств. По теории двойственности для оптимальных планов прямой и двойственной задачи для всех i,j должно быть:

u_i + v_j ≤ c_ij, если x_ij = 0,

u_i + v_j = c_ij, если x_ij ≥ 0,

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

Числа u_i , v_j называются потенциалами. Причем число u_i называется потенциалом поставщика, а число v_j – потенциалом потребителя.

По первой теореме двойственности в оптимальном решении значения целевых функций прямой и двойственных задач совпадают: F = G.

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие  пункты назначения задана матрицей тарифов.

Таблица 2

	1	2	3	4	5	Запасы
1	4	5	2	8	6	115
2	3	1	9	7	3	175
3	9	6	7	2	1	130
Потребности	70	220	40	30	60

 

Проверим  необходимое и достаточное условие  разрешимости задачи.

∑a = 115 + 175 + 130 = 420

∑b = 70 + 220 + 40 + 30 + 60 = 420

Условие баланса  соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

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

 

 

 

Таблица 3

	1	2	3	4	5	Запасы
1	4	5	2	8	6	115
2	3	1	9	7	3	175
3	9	6	7	2	1	130
Потребности	70	220	40	30	60

 

Этап 1. Поиск первого опорного плана.

1.1 Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел a_i, или b_j.

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

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

Искомый элемент  равен 1.

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

x₂₂ = min(175,220) = 175.

Таблица 4

4	5	2	8	6	115
x	1	x	x	x	175 - 175 = 0
9	6	7	2	1	130
70	220 - 175 = 45	40	30	60	0

Искомый элемент  равен 1

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

x₃₅ = min(130,60) = 60.

Таблица 5

4	5	2	8	x	115
x	1	x	x	x	0
9	6	7	2	1	130 - 60 = 70
70	45	40	30	60 - 60 = 0	0

 

Искомый элемент  равен 2

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

x₁₃ = min(115,40) = 40.

Таблица 6

4	5	2	8	x	115 - 40 = 75
x	1	x	x	x	0
9	6	x	2	1	70
70	45	40 - 40 = 0	30	0	0

 

Искомый элемент  равен 2

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

x₃₄ = min(70,30) = 30.

Таблица 7

4	5	2	x	x	75
x	1	x	x	x	0
9	6	x	2	1	70 - 30 = 40
70	45	0	30 - 30 = 0	0	0

 

Искомый элемент  равен 4

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

x₁₁ = min(75,70) = 70.

Таблица 8

4	5	2	x	x	75 - 70 = 5
x	1	x	x	x	0
x	6	x	2	1	40
70 - 70 = 0	45	0	0	0	0

 

Искомый элемент  равен 5

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

x₁₂ = min(5,45) = 5.

Таблица 9

4	5	2	x	x	5 - 5 = 0
x	1	x	x	x	0
x	6	x	2	1	40
0	45 - 5 = 40	0	0	0	0

 

Искомый элемент  равен 6

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

x₃₂ = min(40,40) = 40.

Таблица 10

4	5	2	x	x	0
x	1	x	x	x	0
x	6	x	2	1	40 - 40 = 0
0	40 - 40 = 0	0	0	0	0

 

Таблица 11

	1	2	3	4	5	Запасы
1	4[70]	5[5]	2[40]	8	6	115
2	3	1[175]	9	7	3	175
3	9	6[40]	7	2[30]	1[60]	130
Потребности	70	220	40	30	60

 

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

 Подсчитаем  число занятых клеток таблицы,  их 7, а должно быть m + n - 1 = 7. Следовательно,  опорный план является невырожденным.

Значение  целевой функции для этого  опорного плана равно:

F(x) = 4*70 + 5*5 + 2*40 + 1*175 + 6*40 + 2*30 + 1*60  = 920

Этап 2. Улучшение опорного плана.

Проверим  оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₁ = 4; 0 + v₁ = 4; v₁ = 4

u₁ + v₂ = 5; 0 + v₂ = 5; v₂ = 5

u₂ + v₂ = 1; 5 + u₂ = 1; u₂ = -4

u₃ + v₂ = 6; 5 + u₃ = 6; u₃ = 1

u₃ + v₄ = 2; 1 + v₄ = 2; v₄ = 1

u₃ + v₅ = 1; 1 + v₅ = 1; v₅ = 0

      u₁ + v₃ = 2; 0 + v₃ = 2; v₃ = 2

 

 

 

Таблица 12

	v1=4	v2=5	v3=2	v4=1	v5=0
u1=0	4[70]	5[5]	2[40]	8	6
u2=-4	3	1[175]	9	7	3
u3=1	9	6[40]	7	2[30]	1[60]

 

Опорный план не является оптимальным, так как  существуют оценки свободных клеток, для которых u_i + v_i > c_ij

(1;4): 0 + 1 < 8; ∆₁₄ = 0 + 1 - 8 = -7

(1;5): 0 + 0 < 6; ∆₁₅ = 0 + 0 - 6 = -6

(2;1): -4 + 4 < 3; ∆₂₁ = -4 + 4 - 3 = -3

(2;3): -4 + 2 < 9; ∆₂₃ = -4 + 2 - 9 = -11

(2;4): -4 + 1 < 7; ∆₂₄ = -4 + 1 - 7 = -10

(2;5): -4 + 0 < 3; ∆₂₅ = -4 + 0 - 3 = -7

(3;1): 1 + 4 < 9; ∆₃₁ = 1 + 4 - 9 = -4

(3;3): 1 + 2 < 7; ∆₃₃ = 1 + 2 - 7 = -4

max(7,6,3,11,10,7,4,4) = -11

Выбираем  максимальную оценку свободной клетки (2;3): 9

Для этого  в перспективную клетку (2;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки  «-», «+», «-».

Таблица 13

	1	2	3	4	5	Запасы
1	4[70]	5[5][+]	2[40][-]	8	6	115
2	3	1[175][-]	9[+]	7	3	175
3	9	6[40]	7	2[30]	1[60]	130
Потребности	70	220	40	30	60