На странице представлен фрагмент
Реши любую задачу с помощью нейросети.
9.
На трех базах находится однородный груз в количестве 240, 160, 200 условных единиц. Этот груз необходимо развести пяти потребителям, потребности которых в данном грузе оставляют 180, 40, 160, 120, 100 условных единиц соответственно.
Стоимость перевозок пропорциональна расстоянию и количеству перевозимого груза. Матрица тарифов имеет вид
Возможны поставки груза на третью базу с первой и второй по цене 0,5 и 1 за условную единицу соответственно и от первого и второго потребителя третьему, от пятого потребителя второму и четвертому по цене 2 за единицу.
От второй базы третьему потребителю разрешается перевозить не более 130 единиц груза, от первой базы первому потребителю – не более 200 единиц груза.
Составить план перевозок такой, чтобы их общая стоимость была минимальной.
Часть выполненной работы
1 2 3 4 5 6 7 8 9 10 Запасы
1 0[600] 60[140][-] 0.5 5 60 8 15 15 20 9[100][+] 840
2 60 0[460][+] 1[300][-] 8 8 7 6 60 12 14 760
3 60 60 0[300][+] 16[200] 16[300][-] 11 19 19 10 5 800
4 60 60 60 0 0[280][+] 60[320][-] 2 2 60 60 600
5 60 60 60 60 60 0[320][+] 2[130] 2[150][-] 60 60 600
6 60 60 60 60 60 60 0 0[480][+] 60[120][-] 60 600
7 60 60 60 60 60 60 60 60 0[600] 60 600
8 60 60 60 60 60 2 60 60 2[+] 0[600][-] 600
Потребности
600 600 600 200 580 640 130 630 720 700
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (6, 9) = 120. Прибавляем 120 к объемам грузов, стоящих в плюсовых клетках и вычитаем 120 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 2 3 4 5 6 7 8 9 10 Запасы
1 0[600] 60[20] 0.5 5 60 8 15 15 20 9[220] 840
2 60 0[580] 1[180] 8 8 7 6 60 12 14 760
3 60 60 0[420] 16[200] 16[180] 11 19 19 10 5 800
4 60 60 60 0 0[400] 60[200] 2 2 60 60 600
5 60 60 60 60 60 0[440] 2[130] 2[30] 60 60 600
6 60 60 60 60 60 60 0 0[600] 60 60 600
7 60 60 60 60 60 60 60 60 0[600] 60 600
8 60 60 60 60 60 2 60 60 2[120] 0[480] 600
Потребности
600 600 600 200 580 640 130 630 720 700
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 0; 0 + v1 = 0; v1 = 0
u1 + v2 = 60; 0 + v2 = 60; v2 = 60
u2 + v2 = 0; 60 + u2 = 0; u2 = -60
u2 + v3 = 1; -60 + v3 = 1; v3 = 61
u3 + v3 = 0; 61 + u3 = 0; u3 = -61
u3 + v4 = 16; -61 + v4 = 16; v4 = 77
u3 + v5 = 16; -61 + v5 = 16; v5 = 77
u4 + v5 = 0; 77 + u4 = 0; u4 = -77
u4 + v6 = 60; -77 + v6 = 60; v6 = 137
u5 + v6 = 0; 137 + u5 = 0; u5 = -137
u5 + v7 = 2; -137 + v7 = 2; v7 = 139
u5 + v8 = 2; -137 + v8 = 2; v8 = 139
u6 + v8 = 0; 139 + u6 = 0; u6 = -139
u1 + v10 = 9; 0 + v10 = 9; v10 = 9
u8 + v10 = 0; 9 + u8 = 0; u8 = -9
u8 + v9 = 2; -9 + v9 = 2; v9 = 11
u7 + v9 = 0; 11 + u7 = 0; u7 = -11
v1=0 v2=60 v3=61 v4=77 v5=77 v6=137 v7=139 v8=139 v9=11 v10=9
u1=0 0[600] 60[20] 0.5 5 60 8 15 15 20 9[220]
u2=-60 60 0[580] 1[180] 8 8 7 6 60 12 14
u3=-61 60 60 0[420] 16[200] 16[180] 11 19 19 10 5
u4=-77 60 60 60 0 0[400] 60[200] 2 2 60 60
u5=-137 60 60 60 60 60 0[440] 2[130] 2[30] 60 60
u6=-139 60 60 60 60 60 60 0 0[600] 60 60
u7=-11 60 60 60 60 60 60 60 60 0[600] 60
u8=-9 60 60 60 60 60 2 60 60 2[120] 0[480]
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;3): 0 + 61 > 0.5; ∆13 = 0 + 61 – 0.5 = 60.5
(1;4): 0 + 77 > 5; ∆14 = 0 + 77 – 5 = 72
(1;5): 0 + 77 > 60; ∆15 = 0 + 77 – 60 = 17
(1;6): 0 + 137 > 8; ∆16 = 0 + 137 – 8 = 129
(1;7): 0 + 139 > 15; ∆17 = 0 + 139 – 15 = 124
(1;8): 0 + 139 > 15; ∆18 = 0 + 139 – 15 = 124
(2;4): -60 + 77 > 8; ∆24 = -60 + 77 – 8 = 9
(2;5): -60 + 77 > 8; ∆25 = -60 + 77 – 8 = 9
(2;6): -60 + 137 > 7; ∆26 = -60 + 137 – 7 = 70
(2;7): -60 + 139 > 6; ∆27 = -60 + 139 – 6 = 73
(2;8): -60 + 139 > 60; ∆28 = -60 + 139 – 60 = 19
(3;6): -61 + 137 > 11; ∆36 = -61 + 137 – 11 = 65
(3;7): -61 + 139 > 19; ∆37 = -61 + 139 – 19 = 59
(3;8): -61 + 139 > 19; ∆38 = -61 + 139 – 19 = 59
(4;7): -77 + 139 > 2; ∆47 = -77 + 139 – 2 = 60
(4;8): -77 + 139 > 2; ∆48 = -77 + 139 – 2 = 60
(7;4): -11 + 77 > 60; ∆74 = -11 + 77 – 60 = 6
(7;5): -11 + 77 > 60; ∆75 = -11 + 77 – 60 = 6
(7;6): -11 + 137 > 60; ∆76 = -11 + 137 – 60 = 66
(7;7): -11 + 139 > 60; ∆77 = -11 + 139 – 60 = 68
(7;8): -11 + 139 > 60; ∆78 = -11 + 139 – 60 = 68
(8;4): -9 + 77 > 60; ∆84 = -9 + 77 – 60 = 8
(8;5): -9 + 77 > 60; ∆85 = -9 + 77 – 60 = 8
(8;6): -9 + 137 > 2; ∆86 = -9 + 137 – 2 = 126
(8;7): -9 + 139 > 60; ∆87 = -9 + 139 – 60 = 70
(8;8): -9 + 139 > 60; ∆88 = -9 + 139 – 60 = 70
max(60.5,72,17,129,124,124,9,9,70,73,19,65,59,59,60,60,6,6,66,68,68,8,8,126,70,70) = 129
Выбираем максимальную оценку свободной клетки (1;6): 8
Для этого в перспективную клетку (1;6) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 2 3 4 5 6 7 8 9 10 Запасы
1 0[600] 60[20][-] 0.5 5 60 8[+] 15 15 20 9[220] 840
2 60 0[580][+] 1[180][-] 8 8 7 6 60 12 14 760
3 60 60 0[420][+] 16[200] 16[180][-] 11 19 19 10 5 800
4 60 60 60 0 0[400][+] 60[200][-] 2 2 60 60 600
5 60 60 60 60 60 0[440] 2[130] 2[30] 60 60 600
6 60 60 60 60 60 60 0 0[600] 60 60 600
7 60 60 60 60 60 60 60 60 0[600] 60 600
8 60 60 60 60 60 2 60 60 2[120] 0[480] 600
Потребности
600 600 600 200 580 640 130 630 720 700
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 2 3 4 5 6 7 8 9 10 Запасы
1 0[600] 60 0.5 5 60 8[20] 15 15 20 9[220] 840
2 60 0[600] 1[160] 8 8 7 6 60 12 14 760
3 60 60 0[440] 16[200] 16[160] 11 19 19 10 5 800
4 60 60 60 0 0[420] 60[180] 2 2 60 60 600
5 60 60 60 60 60 0[440] 2[130] 2[30] 60 60 600
6 60 60 60 60 60 60 0 0[600] 60 60 600
7 60 60 60 60 60 60 60 60 0[600] 60 600
8 60 60 60 60 60 2 60 60 2[120] 0[480] 600
Потребности
600 600 600 200 580 640 130 630 720 700
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 0; 0 + v1 = 0; v1 = 0
u1 + v6 = 8; 0 + v6 = 8; v6 = 8
u4 + v6 = 60; 8 + u4 = 60; u4 = 52
u4 + v5 = 0; 52 + v5 = 0; v5 = -52
u3 + v5 = 16; -52 + u3 = 16; u3 = 68
u3 + v3 = 0; 68 + v3 = 0; v3 = -68
u2 + v3 = 1; -68 + u2 = 1; u2 = 69
u2 + v2 = 0; 69 + v2 = 0; v2 = -69
u3 + v4 = 16; 68 + v4 = 16; v4 = -52
u5 + v6 = 0; 8 + u5 = 0; u5 = -8
u5 + v7 = 2; -8 + v7 = 2; v7 = 10
u5 + v8 = 2; -8 + v8 = 2; v8 = 10
u6 + v8 = 0; 10 + u6 = 0; u6 = -10
u1 + v10 = 9; 0 + v10 = 9; v10 = 9
u8 + v10 = 0; 9 + u8 = 0; u8 = -9
u8 + v9 = 2; -9 + v9 = 2; v9 = 11
u7 + v9 = 0; 11 + u7 = 0; u7 = -11
v1=0 v2=-69 v3=-68 v4=-52 v5=-52 v6=8 v7=10 v8=10 v9=11 v10=9
u1=0 0[600] 60 0.5 5 60 8[20] 15 15 20 9[220]
u2=69 60 0[600] 1[160] 8 8 7 6 60 12 14
u3=68 60 60 0[440] 16[200] 16[160] 11 19 19 10 5
u4=52 60 60 60 0 0[420] 60[180] 2 2 60 60
u5=-8 60 60 60 60 60 0[440] 2[130] 2[30] 60 60
u6=-10 60 60 60 60 60 60 0 0[600] 60 60
u7=-11 60 60 60 60 60 60 60 60 0[600] 60
u8=-9 60 60 60 60 60 2 60 60 2[120] 0[480]
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(2;1): 69 + 0 > 60; ∆21 = 69 + 0 – 60 = 9
(2;4): 69 + -52 > 8; ∆24 = 69 + -52 – 8 = 9
(2;5): 69 + -52 > 8; ∆25 = 69 + -52 – 8 = 9
(2;6): 69 + 8 > 7; ∆26 = 69 + 8 – 7 = 70
(2;7): 69 + 10 > 6; ∆27 = 69 + 10 – 6 = 73
(2;8): 69 + 10 > 60; ∆28 = 69 + 10 – 60 = 19
(2;9): 69 + 11 > 12; ∆29 = 69 + 11 – 12 = 68
(2;10): 69 + 9 > 14; ∆210 = 69 + 9 – 14 = 64
(3;1): 68 + 0 > 60; ∆31 = 68 + 0 – 60 = 8
(3;6): 68 + 8 > 11; ∆36 = 68 + 8 – 11 = 65
(3;7): 68 + 10 > 19; ∆37 = 68 + 10 – 19 = 59
(3;8): 68 + 10 > 19; ∆38 = 68 + 10 – 19 = 59
(3;9): 68 + 11 > 10; ∆39 = 68 + 11 – 10 = 69
(3;10): 68 + 9 > 5; ∆310 = 68 + 9 – 5 = 72
(4;7): 52 + 10 > 2; ∆47 = 52 + 10 – 2 = 60
(4;8): 52 + 10 > 2; ∆48 = 52 + 10 – 2 = 60
(4;9): 52 + 11 > 60; ∆49 = 52 + 11 – 60 = 3
(4;10): 52 + 9 > 60; ∆410 = 52 + 9 – 60 = 1
max(9,9,9,70,73,19,68,64,8,65,59,59,69,72,60,60,3,1) = 73
Выбираем максимальную оценку свободной клетки (2;7): 6
Для этого в перспективную клетку (2;7) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 2 3 4 5 6 7 8 9 10 Запасы
1 0[600] 60 0.5 5 60 8[20] 15 15 20 9[220] 840
2 60 0[600] 1[160][-] 8 8 7 6[+] 60 12 14 760
3 60 60 0[440][+] 16[200] 16[160][-] 11 19 19 10 5 800
4 60 60 60 0 0[420][+] 60[180][-] 2 2 60 60 600
5 60 60 60 60 60 0[440][+] 2[130][-] 2[30] 60 60 600
6 60 60 60 60 60 60 0 0[600] 60 60 600
7 60 60 60 60 60 60 60 60 0[600] 60 600
8 60 60 60 60 60 2 60 60 2[120] 0[480] 600
Потребности
600 600 600 200 580 640 130 630 720 700
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (5, 7) = 130. Прибавляем 130 к объемам грузов, стоящих в плюсовых клетках и вычитаем 130 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 2 3 4 5 6 7 8 9 10 Запасы
1 0[600] 60 0.5 5 60 8[20] 15 15 20 9[220] 840
2 60 0[600] 1[30] 8 8 7 6[130] 60 12 14 760
3 60 60 0[570] 16[200] 16[30] 11 19 19 10 5 800
4 60 60 60 0 0[550] 60[50] 2 2 60 60 600
5 60 60 60 60 60 0[570] 2 2[30] 60 60 600
6 60 60 60 60 60 60 0 0[600] 60 60 600
7 60 60 60 60 60 60 60 60 0[600] 60 600
8 60 60 60 60 60 2 60 60 2[120] 0[480] 600
Потребности
600 600 600 200 580 640 130 630 720 700
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 0; 0 + v1 = 0; v1 = 0
u1 + v6 = 8; 0 + v6 = 8; v6 = 8
u4 + v6 = 60; 8 + u4 = 60; u4 = 52
u4 + v5 = 0; 52 + v5 = 0; v5 = -52
u3 + v5 = 16; -52 + u3 = 16; u3 = 68
u3 + v3 = 0; 68 + v3 = 0; v3 = -68
u2 + v3 = 1; -68 + u2 = 1; u2 = 69
u2 + v2 = 0; 69 + v2 = 0; v2 = -69
u2 + v7 = 6; 69 + v7 = 6; v7 = -63
u3 + v4 = 16; 68 + v4 = 16; v4 = -52
u5 + v6 = 0; 8 + u5 = 0; u5 = -8
u5 + v8 = 2; -8 + v8 = 2; v8 = 10
u6 + v8 = 0; 10 + u6 = 0; u6 = -10
u1 + v10 = 9; 0 + v10 = 9; v10 = 9
u8 + v10 = 0; 9 + u8 = 0; u8 = -9
u8 + v9 = 2; -9 + v9 = 2; v9 = 11
u7 + v9 = 0; 11 + u7 = 0; u7 = -11
v1=0 v2=-69 v3=-68 v4=-52 v5=-52 v6=8 v7=-63 v8=10 v9=11 v10=9
u1=0 0[600] 60 0.5 5 60 8[20] 15 15 20 9[220]
u2=69 60 0[600] 1[30] 8 8 7 6[130] 60 12 14
u3=68 60 60 0[570] 16[200] 16[30] 11 19 19 10 5
u4=52 60 60 60 0 0[550] 60[50] 2 2 60 60
u5=-8 60 60 60 60 60 0[570] 2 2[30] 60 60
u6=-10 60 60 60 60 60 60 0 0[600] 60 60
u7=-11 60 60 60 60 60 60 60 60 0[600] 60
u8=-9 60 60 60 60 60 2 60 60 2[120] 0[480]
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(2;1): 69 + 0 > 60; ∆21 = 69 + 0 – 60 = 9
(2;4): 69 + -52 > 8; ∆24 = 69 + -52 – 8 = 9
(2;5): 69 + -52 > 8; ∆25 = 69 + -52 – 8 = 9
(2;6): 69 + 8 > 7; ∆26 = 69 + 8 – 7 = 70
(2;8): 69 + 10 > 60; ∆28 = 69 + 10 – 60 = 19
(2;9): 69 + 11 > 12; ∆29 = 69 + 11 – 12 = 68
(2;10): 69 + 9 > 14; ∆210 = 69 + 9 – 14 = 64
(3;1): 68 + 0 > 60; ∆31 = 68 + 0 – 60 = 8
(3;6): 68 + 8 > 11; ∆36 = 68 + 8 – 11 = 65
(3;8): 68 + 10 > 19; ∆38 = 68 + 10 – 19 = 59
(3;9): 68 + 11 > 10; ∆39 = 68 + 11 – 10 = 69
(3;10): 68 + 9 > 5; ∆310 = 68 + 9 – 5 = 72
(4;8): 52 + 10 > 2; ∆48 = 52 + 10 – 2 = 60
(4;9): 52 + 11 > 60; ∆49 = 52 + 11 – 60 = 3
(4;10): 52 + 9 > 60; ∆410 = 52 + 9 – 60 = 1
max(9,9,9,70,19,68,64,8,65,59,69,72,60,3,1) = 72
Выбираем максимальную оценку свободной клетки (3;10): 5
Для этого в перспективную клетку (3;10) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 2 3 4 5 6 7 8 9 10 Запасы
1 0[600] 60 0.5 5 60 8[20][+] 15 15 20 9[220][-] 840
2 60 0[600] 1[30] 8 8 7 6[130] 60 12 14 760
3 60 60 0[570] 16[200] 16[30][-] 11 19 19 10 5[+] 800
4 60 60 60 0 0[550][+] 60[50][-] 2 2 60 60 600
5 60 60 60 60 60 0[570] 2 2[30] 60 60 600
6 60 60 60 60 60 60 0 0[600] 60 60 600
7 60 60 60 60 60 60 60 60 0[600] 60 600
8 60 60 60 60 60 2 60 60 2[120] 0[480] 600
Потребности
600 600 600 200 580 640 130 630 720 700
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 5) = 30. Прибавляем 30 к объемам грузов, стоящих в плюсовых клетках и вычитаем 30 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 2 3 4 5 6 7 8 9 10 Запасы
1 0[600] 60 0.5 5 60 8[50] 15 15 20 9[190] 840
2 60 0[600] 1[30] 8 8 7 6[130] 60 12 14 760
3 60 60 0[570] 16[200] 16 11 19 19 10 5[30] 800
4 60 60 60 0 0[580] 60[20] 2 2 60 60 600
5 60 60 60 60 60 0[570] 2 2[30] 60 60 600
6 60 60 60 60 60 60 0 0[600] 60 60 600
7 60 60 60 60 60 60 60 60 0[600] 60 600
8 60 60 60 60 60 2 60 60 2[120] 0[480] 600
Потребности
600 600 600 200 580 640 130 630 720 700
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 0; 0 + v1 = 0; v1 = 0
u1 + v6 = 8; 0 + v6 = 8; v6 = 8
u4 + v6 = 60; 8 + u4 = 60; u4 = 52
u4 + v5 = 0; 52 + v5 = 0; v5 = -52
u5 + v6 = 0; 8 + u5 = 0; u5 = -8
u5 + v8 = 2; -8 + v8 = 2; v8 = 10
u6 + v8 = 0; 10 + u6 = 0; u6 = -10
u1 + v10 = 9; 0 + v10 = 9; v10 = 9
u3 + v10 = 5; 9 + u3 = 5; u3 = -4
u3 + v3 = 0; -4 + v3 = 0; v3 = 4
u2 + v3 = 1; 4 + u2 = 1; u2 = -3
u2 + v2 = 0; -3 + v2 = 0; v2 = 3
u2 + v7 = 6; -3 + v7 = 6; v7 = 9
u3 + v4 = 16; -4 + v4 = 16; v4 = 20
u8 + v10 = 0; 9 + u8 = 0; u8 = -9
u8 + v9 = 2; -9 + v9 = 2; v9 = 11
u7 + v9 = 0; 11 + u7 = 0; u7 = -11
v1=0 v2=3 v3=4 v4=20 v5=-52 v6=8 v7=9 v8=10 v9=11 v10=9
u1=0 0[600] 60 0.5 5 60 8[50] 15 15 20 9[190]
u2=-3 60 0[600] 1[30] 8 8 7 6[130] 60 12 14
u3=-4 60 60 0[570] 16[200] 16 11 19 19 10 5[30]
u4=52 60 60 60 0 0[580] 60[20] 2 2 60 60
u5=-8 60 60 60 60 60 0[570] 2 2[30] 60 60
u6=-10 60 60 60 60 60 60 0 0[600] 60 60
u7=-11 60 60 60 60 60 60 60 60 0[600] 60
u8=-9 60 60 60 60 60 2 60 60 2[120] 0[480]
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;3): 0 + 4 > 0.5; ∆13 = 0 + 4 – 0.5 = 3.5
(1;4): 0 + 20 > 5; ∆14 = 0 + 20 – 5 = 15
(2;4): -3 + 20 > 8; ∆24 = -3 + 20 – 8 = 9
(4;4): 52 + 20 > 0; ∆44 = 52 + 20 – 0 = 72
(4;7): 52 + 9 > 2; ∆47 = 52 + 9 – 2 = 59
(4;8): 52 + 10 > 2; ∆48 = 52 + 10 – 2 = 60
(4;9): 52 + 11 > 60; ∆49 = 52 + 11 – 60 = 3
(4;10): 52 + 9 > 60; ∆410 = 52 + 9 – 60 = 1
max(3.5,15,9,72,59,60,3,1) = 72
Выбираем максимальную оценку свободной клетки (4;4): 0
Для этого в перспективную клетку (4;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 2 3 4 5 6 7 8 9 10 Запасы
1 0[600] 60 0.5 5 60 8[50][+] 15 15 20 9[190][-] 840
2 60 0[600] 1[30] 8 8 7 6[130] 60 12 14 760
3 60 60 0[570] 16[200][-] 16 11 19 19 10 5[30][+] 800
4 60 60 60 0[+] 0[580] 60[20][-] 2 2 60 60 600
5 60 60 60 60 60 0[570] 2 2[30] 60 60 600
6 60 60 60 60 60 60 0 0[600] 60 60 600
7 60 60 60 60 60 60 60 60 0[600] 60 600
8 60 60 60 60 60 2 60 60 2[120] 0[480] 600
Потребности
600 600 600 200 580 640 130 630 720 700
Из грузов хij стоящих в мин…
