Математические методы

3.3  Метод  аппроксимации Фогеля 

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

Если  минимальная стоимость одинакова  для нескольких клеток столбца (строки), то для заполнения выбирают ту клетку, которая расположена в столбце (строке), соответствующем наибольшей разности между двумя минимальными стоимостями, находящимися в данном столбце (строке).

 

 

 

 

 

 

 

 

 

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

^{Задача :}  

^{У поставщиков A1 , A2 , A3 находится соответственно 110,190,90 единиц однотипной продукции, которая должна быть доставлена потребителям B1 , B2 , B3 , B4 в количествах 80,60,170,80 единиц соответственно.}

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

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

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

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

^{Решение :}  

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

F = ∑∑c_ijx_ij,  

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

∑x_ij = a_i,  i = 1,2,…, m, 

∑x_ij = b_j,  j = 1,2,…, n,  

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

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

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

G = ∑a_iu_i + ∑b_jv_j           (10)

при условии

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

В систему  условий (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.

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

	1	2	3	4	Запасы
1	8	1	9	7	110
2	4	6	2	12	190
3	3	5	8	9	90
Потребности	80	60	170	80

 

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

∑a = 110 + 190 + 90 = 390

∑b = 80 + 60 + 170 + 80 = 390

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

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

	1	2	3	4	Запасы
1	8	1	9	7	110
2	4	6	2	12	190
3	3	5	8	9	90
Потребности	80	60	170	80

 

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

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

Данный метод  состоит в следующем:

1. на каждой  итерации находят разности между  двумя наименьшими тарифами во  всех строках и столбцах, записывая  их в дополнительные столбец  и строку таблицы;

2. находят  максимальную разность и заполняют  клетку с минимальной стоимостью  в строке (столбце), которой соответствует  данная разность.

Находим разности по строкам.

Для строки N=1 первый минимальный элемент min¹₁ = 1, второй минимальный элемент min²₁ = 7. Их разность равна d = min²₁ - min¹₁ = 6.

Для строки N=2 первый минимальный элемент min¹₂ = 2, второй минимальный элемент min²₂ = 4. Их разность равна d = min²₂ - min¹₂ = 2.

Для строки N=3 первый минимальный элемент min¹₃ = 3, второй минимальный элемент min²₃ = 5. Их разность равна d = min²₃ - min¹₃ = 2.

Находим разности по столбцам.

Для столбца N=1 первый минимальный элемент min¹₁ = 3. второй минимальный элемент min²₁ 4. Их разность d = min²₁ - min¹₁ = 1.

Для столбца N=2 первый минимальный элемент min¹₂ = 1. второй минимальный элемент min²₂ 5. Их разность d = min²₂ - min¹₂ = 4.

Для столбца N=3 первый минимальный элемент min¹₃ = 2. второй минимальный элемент min²₃ 8. Их разность d = min²₃ - min¹₃ = 6.

Для столбца N=4 первый минимальный элемент min¹₄ = 7. второй минимальный элемент min²₄ 9. Их разность d = min²₄ - min¹₄ = 2.

Вычислив  все эти разности, видим, что наибольшая из них соответствует строке (1). В  этой строке минимальный тариф записан  в клетке, находящейся на пересечении  строки (1) и столбца (2).

	1	2	3	4	Запасы	Разности по строкам
1	8	1	9	7	110	6
2	4	6	2	12	190	2
3	3	5	8	9	90	2
Потребности	80	60	170	80	0	0
Разности по столбцам	1	4	6	2	0

 

 

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

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

x₁₂ = min(110,60) = 60.

0	0	0	0	110 - 60 = 50
0	x	x	x	x
0	x	x	0	0
0	60 - 60 = 0	x	0	0

 

 

Находим разности по строкам.

Для строки N=1 первый минимальный элемент min¹₁ = 7, второй минимальный элемент min²₁ = 8. Их разность равна d = min²₁ - min¹₁ = 1.

Для строки N=2 первый минимальный элемент min¹₂ = 2, второй минимальный элемент min²₂ = 4. Их разность равна d = min²₂ - min¹₂ = 2.

Для строки N=3 первый минимальный элемент min¹₃ = 3, второй минимальный элемент min²₃ = 8. Их разность равна d = min²₃ - min¹₃ = 5.

Находим разности по столбцам.

Для столбца N=1 первый минимальный элемент min¹₁ = 3. второй минимальный элемент min²₁ 4. Их разность d = min²₁ - min¹₁ = 1.

Для столбца N=3 первый минимальный элемент min¹₃ = 2. второй минимальный элемент min²₃ 8. Их разность d = min²₃ - min¹₃ = 6.

Для столбца N=4 первый минимальный элемент min¹₄ = 7. второй минимальный элемент min²₄ 9. Их разность d = min²₄ - min¹₄ = 2.

Вычислив  все эти разности, видим, что наибольшая из них соответствует столбцу (3). В этом столбце минимальный тариф  записан в клетке, находящейся  на пересечении строки (2) и столбца (3).

	1	2	3	4	Запасы	Разности по строкам
1	8	1	9	7	50	1
2	4	6	2	12	190	2
3	3	5	8	9	90	5
Потребности	80	0	170	80	0	0
Разности по столбцам	1	-	6	2	0

 

 

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

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

x₂₃ = min(190,170) = 170.

0	0	x	0	0
0	0	0	x	190 - 170 = 20
0	x	x	x	x
0	0	170 - 170 = 0	x	0

Находим разности по строкам.

Для строки N=1 первый минимальный элемент min¹₁ = 7, второй минимальный элемент min²₁ = 8. Их разность равна d = min²₁ - min¹₁ = 1.

Для строки N=2 первый минимальный элемент min¹₂ = 4, второй минимальный элемент min²₂ = 12. Их разность равна d = min²₂ - min¹₂ = 8.

Для строки N=3 первый минимальный элемент min¹₃ = 3, второй минимальный элемент min²₃ = 9. Их разность равна d = min²₃ - min¹₃ = 6.

Находим разности по столбцам.

Для столбца N=1 первый минимальный элемент min¹₁ = 3. второй минимальный элемент min²₁ 4. Их разность d = min²₁ - min¹₁ = 1.

Для столбца N=4 первый минимальный элемент min¹₄ = 7. второй минимальный элемент min²₄ 9. Их разность d = min²₄ - min¹₄ = 2.

Вычислив  все эти разности, видим, что наибольшая из них соответствует строке (2). В  этой строке минимальный тариф записан  в клетке, находящейся на пересечении  строки (2) и столбца (1).

	1	2	3	4	Запасы	Разности по строкам
1	8	1	9	7	50	1
2	4	6	2	12	20	8
3	3	5	8	9	90	6
Потребности	80	0	0	80	0	0
Разности по столбцам	1	-	-	2	0