Метод минимального элемента

     4 Решение транспортной  задачи методом  минимального элемента

      ^{Задача:} 

     ^{У поставщиков A1 , A2 , A3 находится соответственно 115,175,130 единиц однотипной продукции, которая должна быть доставлена потребителям B1 , B2 , B3 , B4, В5 в количествах 70, 220, 40, 30, 60 единиц соответственно.}

     ^{Стоимость доставки единицы  продукции от поставщика 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.

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

     5

     Аналитическое решение нахождения опорного плана

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

     Таблица 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