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

 

 

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

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

x₂₁ = min(20,80) = 20.

0	0	0	0	0
0	x	0	x	20 - 20 = 0
0	x	x	x	x
80 - 20 = 60	x	0	0	0

 

 

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

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

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

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

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

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

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

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

 

 

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

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

x₃₁ = min(90,60) = 60.

x	0	0	0	0
0	x	0	0	0
0	x	0	0	90 - 60 = 30
60 - 60 = 0	x	x	x	x

 

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

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

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

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

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

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

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

 

 

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

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

x₁₄ = min(50,80) = 50.

0	0	0	0	50 - 50 = 0
0	x	x	x	x
0	0	0	0	x
0	0	0	80 - 50 = 30	x

 

 

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

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

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

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

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

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

 

 

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

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

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

0	0	0	0	0
0	0	0	0	x
0	0	0	0	30 - 30 = 0
0	x	x	30 - 30 = 0	x

 

 

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

 

Сведем все  вычисления в одну таблицу.

	1	2	3	4	Запасы	d1	d2	d3	d4
1	8	1[60]	9	7[50]	110	6	1	1	1
2	4[20]	6	2[170]	12	190	2	2	8	-
3	3[60]	5	8	9[30]	90	2	5	6	6
Потребности	80	60	170	80
d1	1	4	6	2
d2	1	-	6	2
d3	1	-	-	2
d4	5	-	-	2

 

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

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

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

F(x) = 1*60 + 7*50 + 4*20 + 2*170 + 3*60 + 9*30  = 1280

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

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

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

u₁ + v₄ = 7; 0 + v₄ = 7; v₄ = 7

u₃ + v₄ = 9; 7 + u₃ = 9; u₃ = 2

u₃ + v₁ = 3; 2 + v₁ = 3; v₁ = 1

u₂ + v₁ = 4; 1 + u₂ = 4; u₂ = 3

u₂ + v₃ = 2; 3 + v₃ = 2; v₃ = -1

	v1=1	v2=1	v3=-1	v4=7
u1=0	8	1[60]	9	7[50]
u2=3	4[20]	6	2[170]	12
u3=2	3[60]	5	8	9[30]

 

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

Минимальные затраты составят:

F(x) = 1*60 + 7*50 + 4*20 + 2*170 + 3*60 + 9*30  = 1280

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

G = 0*110 + 3*190 + 2*90 + 1*80 + 1*60 + -1*170 + 7*80  = 1280

 

 

 

 

 

 

5. Аналитическое решение нахождения опорного плана транспортной задачи методом Фогеля

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6 Программная реализация нахождения  опорного плана транспортной  задачи методом Фогеля