Контрольная работа по «Моделирование транспортных процессов»

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. 
u1 + v1 = 3; 0 + v1 = 3; v1 = 3 
u2 + v1 = 2; 3 + u2 = 2; u2 = -1 
u2 + v3 = 1; -1 + v3 = 1; v3 = 2 
u2 + v4 = 5; -1 + v4 = 5; v4 = 6 
u3 + v4 = 6; 6 + u3 = 6; u3 = 0 
u3 + v2 = 3; 0 + v2 = 3; v2 = 3 
u1 + v5 = 8; 0 + v5 = 8; v5 = 8

	v1=3	v2=3	v3=2	v4=6	v5=8
u1=0	3[50]	11	6	8	8[50]
u2=-1	2[10]	10	1[30]	5[30]	9
u3=0	6	3[10]	8	6[40]	1

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij 
(3;5): 0 + 8 > 1; ∆35 = 0 + 8 - 1 = 7 
Выбираем максимальную оценку свободной клетки (3;5): 1 
Для этого в перспективную клетку (3;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	3[50][+]	11	6	8	8[50][-]	100
2	2[10][-]	10	1[30]	5[30][+]	9	70
3	6	3[10]	8	6[40][-]	1[+]	50
Потребности	60	10	30	70	50

Цикл приведен в таблице (3,5 → 3,4 → 2,4 → 2,1 → 1,1 → 1,5). 
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 1) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	Запасы
1	3[60]	11	6	8	8[40]	100
2	2	10	1[30]	5[40]	9	70
3	6	3[10]	8	6[30]	1[10]	50
Потребности	60	10	30	70	50

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. 
u1 + v1 = 3; 0 + v1 = 3; v1 = 3 
u1 + v5 = 8; 0 + v5 = 8; v5 = 8 
u3 + v5 = 1; 8 + u3 = 1; u3 = -7 
u3 + v2 = 3; -7 + v2 = 3; v2 = 10 
u3 + v4 = 6; -7 + v4 = 6; v4 = 13 
u2 + v4 = 5; 13 + u2 = 5; u2 = -8 
u2 + v3 = 1; -8 + v3 = 1; v3 = 9

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

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij 
(1;3): 0 + 9 > 6; ∆13 = 0 + 9 - 6 = 3 
(1;4): 0 + 13 > 8; ∆14 = 0 + 13 - 8 = 5 
max(3,5) = 5 
Выбираем максимальную оценку свободной клетки (1;4): 8 
Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	3[60]	11	6	8[+]	8[40][-]	100
2	2	10	1[30]	5[40]	9	70
3	6	3[10]	8	6[30][-]	1[10][+]	50
Потребности	60	10	30	70	50

Цикл приведен в таблице (1,4 → 1,5 → 3,5 → 3,4). 
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 4) = 30. Прибавляем 30 к объемам грузов, стоящих в плюсовых клетках и вычитаем 30 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	Запасы
1	3[60]	11	6	8[30]	8[10]	100
2	2	10	1[30]	5[40]	9	70
3	6	3[10]	8	6	1[40]	50
Потребности	60	10	30	70	50

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. 
u1 + v1 = 3; 0 + v1 = 3; v1 = 3 
u1 + v4 = 8; 0 + v4 = 8; v4 = 8 
u2 + v4 = 5; 8 + u2 = 5; u2 = -3 
u2 + v3 = 1; -3 + v3 = 1; v3 = 4 
u1 + v5 = 8; 0 + v5 = 8; v5 = 8 
u3 + v5 = 1; 8 + u3 = 1; u3 = -7 
u3 + v2 = 3; -7 + v2 = 3; v2 = 10

Ответ:

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

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij. 
Минимальные затраты составят: F(x) = 3*60 + 8*30 + 8*10 + 1*30 + 5*40 + 3*10 + 1*40 = 800

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача №3.

 

Задана матрица транспортной сети .

Построить диаграмму и найти максимальный поток и минимальный разрез.

.

 

Решение.

1. Заданная транспортная система в графическом виде выглядит следующим образом:

                                                       Х6

                                    

                      Х2        5

                                                      10                          13

                                           18

            5                                         х3              4                                        х7

   Х1                 15                      х4           25

           13

                                            7

                           

                         Х5

 

 

 

2. Построим матрицу пропускных способностей :

								a) Выбираем путь из точки в точку :   б) минимальный поток по пути :
	5			13
					5
	18					4
						25
	15		7
		10				13

 

 

3.Построим матрицу пропускных  способностей  не учитывающую минимальный поток пропускаемый по пути :

								a) Выбираем другой путь из точки в точку :   б) минимальный поток по пути :
	0			13
					0
	18					4
						25
	15		7
		10				8

 

 

4.Построим матрицу пропускных способностей не учитывающую минимальные потоки пропускаемые по путям и :

								В полученной матрице из истока не выходит ни один поток.
	0			6
					0
	18					4
						18
	15		0
		10				8

 

 

5.Построим матрицу разности первоначальной матрицы и конечной матрицы :

								Граф минимального разреза транспортной сети при максимальном потоке:            Х2       5                        5                 х6                    5          х7 Х1      7             х4                  7                            7                 Х5
	0			6
					0
	18					4
						18
	15		0
		10				8

 

 

 

6.Максимальный поток равен:

 

 

Ответ:

Максимальный поток заданной транспортной сети равен: 12