Метод северо-западного угла - Математическое моделирование в менеджменте и маркетинге
Этап I. Поиск первого опорного плана.
1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи.
План начинается заполняться с верхнего левого угла.
Искомый элемент равен c11=7. Для этого элемента запасы равны 20, потребности 25. Поскольку минимальным является 20, то вычитаем его.
X11 = min(20,25) = 20.
7 |
X |
X |
X |
X |
X |
20 - 20 = 0 |
5 |
7 |
0 |
2 |
3 |
0 |
60 |
1 |
4 |
10 |
2 |
6 |
0 |
45 |
3 |
4 |
2 |
7 |
8 |
0 |
70 |
25 - 20 = 5 |
40 |
50 |
30 |
45 |
5 |
Искомый элемент равен c21=5. Для этого элемента запасы равны 60, потребности 5. Поскольку минимальным является 5, то вычитаем его.
X21 = min(60,5) = 5.
7 |
X |
X |
X |
X |
X |
0 |
5 |
7 |
0 |
2 |
3 |
0 |
60 - 5 = 55 |
X |
4 |
10 |
2 |
6 |
0 |
45 |
X |
4 |
2 |
7 |
8 |
0 |
70 |
5 - 5 = 0 |
40 |
50 |
30 |
45 |
5 |
Искомый элемент равен c22=7. Для этого элемента запасы равны 55, потребности 40. Поскольку минимальным является 40, то вычитаем его.
X22 = min(55,40) = 40.
7 |
X |
X |
X |
X |
X |
0 |
5 |
7 |
0 |
2 |
3 |
0 |
55 - 40 = 15 |
X |
X |
10 |
2 |
6 |
0 |
45 |
X |
X |
2 |
7 |
8 |
0 |
70 |
0 |
40 - 40 = 0 |
50 |
30 |
45 |
5 |
Искомый элемент равен c23=0. Для этого элемента запасы равны 15, потребности 50. Поскольку минимальным является 15, то вычитаем его.
X23 = min(15,50) = 15.
7 |
X |
X |
X |
X |
X |
0 |
5 |
7 |
0 |
X |
X |
X |
15 - 15 = 0 |
X |
X |
10 |
2 |
6 |
0 |
45 |
X |
X |
2 |
7 |
8 |
0 |
70 |
0 |
0 |
50 - 15 = 35 |
30 |
45 |
5 |
Искомый элемент равен c33=10. Для этого элемента запасы равны 45, потребности 35. Поскольку минимальным является 35, то вычитаем его.
X33 = min(45,35) = 35.
7 |
X |
X |
X |
X |
X |
0 |
5 |
7 |
0 |
X |
X |
X |
0 |
X |
X |
10 |
2 |
6 |
0 |
45 - 35 = 10 |
X |
X |
X |
7 |
8 |
0 |
70 |
0 |
0 |
35 - 35 = 0 |
30 |
45 |
5 |
Искомый элемент равен c34=2. Для этого элемента запасы равны 10, потребности 30. Поскольку минимальным является 10, то вычитаем его.
X34 = min(10,30) = 10.
7 |
X |
X |
X |
X |
X |
0 |
5 |
7 |
0 |
X |
X |
X |
0 |
X |
X |
10 |
2 |
X |
X |
10 - 10 = 0 |
X |
X |
X |
7 |
8 |
0 |
70 |
0 |
0 |
0 |
30 - 10 = 20 |
45 |
5 |
Искомый элемент равен c44=7. Для этого элемента запасы равны 70, потребности 20. Поскольку минимальным является 20, то вычитаем его.
X44 = min(70,20) = 20.
7 |
X |
X |
X |
X |
X |
0 |
5 |
7 |
0 |
X |
X |
X |
0 |
X |
X |
10 |
2 |
X |
X |
0 |
X |
X |
X |
7 |
8 |
0 |
70 - 20 = 50 |
0 |
0 |
0 |
20 - 20 = 0 |
45 |
5 |
Искомый элемент равен c45=8. Для этого элемента запасы равны 50, потребности 45. Поскольку минимальным является 45, то вычитаем его.
X45 = min(50,45) = 45.
7 |
X |
X |
X |
X |
X |
0 |
5 |
7 |
0 |
X |
X |
X |
0 |
X |
X |
10 |
2 |
X |
X |
0 |
X |
X |
X |
7 |
8 |
0 |
50 - 45 = 5 |
0 |
0 |
0 |
0 |
45 - 45 = 0 |
5 |
Искомый элемент равен c46=0. Для этого элемента запасы равны 5, потребности 5. Поскольку минимальным является 5, то вычитаем его.
X46 = min(5,5) = 5.
7 |
X |
X |
X |
X |
X |
0 |
5 |
7 |
0 |
X |
X |
X |
0 |
X |
X |
10 |
2 |
X |
X |
0 |
X |
X |
X |
7 |
8 |
0 |
5 - 5 = 0 |
0 |
0 |
0 |
0 |
0 |
5 - 5 = 0 |
1 |
2 |
3 |
4 |
5 |
6 |
Запасы | |
1 |
7[20] |
3 |
4 |
8 |
6 |
0 |
20 |
2 |
5[5] |
7[40] |
0[15] |
2 |
3 |
0 |
60 |
3 |
1 |
4 |
10[35] |
2[10] |
6 |
0 |
45 |
4 |
3 |
4 |
2 |
7[20] |
8[45] |
0[5] |
70 |
Потребности |
25 |
40 |
50 |
30 |
45 |
5 |
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 9, а должно быть m + n - 1 = 9. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 7*20 + 5*5 + 7*40 + 0*15 + 10*35 + 2*10 + 7*20 + 8*45 + 0*5 = 1315
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем Предварительные потенциалы uI, vJ. по занятым клеткам таблицы, в которых uI + vJ = cIj, полагая, что u1 = 0.
U1 + v1 = 7; 0 + v1 = 7; v1 = 7
U2 + v1 = 5; 7 + u2 = 5; u2 = -2
U2 + v2 = 7; -2 + v2 = 7; v2 = 9
U2 + v3 = 0; -2 + v3 = 0; v3 = 2
U3 + v3 = 10; 2 + u3 = 10; u3 = 8
U3 + v4 = 2; 8 + v4 = 2; v4 = -6
U4 + v4 = 7; -6 + u4 = 7; u4 = 13
U4 + v5 = 8; 13 + v5 = 8; v5 = -5
U4 + v6 = 0; 13 + v6 = 0; v6 = -13
V1=7 |
V2=9 |
V3=2 |
V4=-6 |
V5=-5 |
V6=-13 | |
U1=0 |
7[20] |
3 |
4 |
8 |
6 |
0 |
U2=-2 |
5[5] |
7[40] |
0[15] |
2 |
3 |
0 |
U3=8 |
1 |
4 |
10[35] |
2[10] |
6 |
0 |
U4=13 |
3 |
4 |
2 |
7[20] |
8[45] |
0[5] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых uI + vJ > cIj
- (1;2): 0 + 9 > 3; ?12 = 0 + 9 - 3 = 6 (3;1): 8 + 7 > 1; ?31 = 8 + 7 - 1 = 14 (3;2): 8 + 9 > 4; ?32 = 8 + 9 - 4 = 13 (4;1): 13 + 7 > 3; ?41 = 13 + 7 - 3 = 17 (4;2): 13 + 9 > 4; ?42 = 13 + 9 - 4 = 18 (4;3): 13 + 2 > 2; ?43 = 13 + 2 - 2 = 13
Max(6,14,13,17,18,13) = 18
Выбираем максимальную оценку свободной клетки (4;2): 4
Для этого в перспективную клетку (4;2) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".
1 |
2 |
3 |
4 |
5 |
6 |
Запасы | |
1 |
7[20] |
3 |
4 |
8 |
6 |
0 |
20 |
2 |
5[5] |
7[40][-] |
0[15][+] |
2 |
3 |
0 |
60 |
3 |
1 |
4 |
10[35][-] |
2[10][+] |
6 |
0 |
45 |
4 |
3 |
4[+] |
2 |
7[20][-] |
8[45] |
0[5] |
70 |
Потребности |
25 |
40 |
50 |
30 |
45 |
5 |
Цикл приведен в таблице (4,2 > 4,4 > 3,4 > 3,3 > 2,3 > 2,2).
Из грузов хIj стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (4, 4) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из ХIj, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
5 |
6 |
Запасы | |
1 |
7[20] |
3 |
4 |
8 |
6 |
0 |
20 |
2 |
5[5] |
7[20] |
0[35] |
2 |
3 |
0 |
60 |
3 |
1 |
4 |
10[15] |
2[30] |
6 |
0 |
45 |
4 |
3 |
4[20] |
2 |
7 |
8[45] |
0[5] |
70 |
Потребности |
25 |
40 |
50 |
30 |
45 |
5 |
Проверим оптимальность опорного плана. Найдем Предварительные потенциалы uI, vJ. по занятым клеткам таблицы, в которых uI + vJ = cIj, полагая, что u1 = 0.
U1 + v1 = 7; 0 + v1 = 7; v1 = 7
U2 + v1 = 5; 7 + u2 = 5; u2 = -2
U2 + v2 = 7; -2 + v2 = 7; v2 = 9
U4 + v2 = 4; 9 + u4 = 4; u4 = -5
U4 + v5 = 8; -5 + v5 = 8; v5 = 13
U4 + v6 = 0; -5 + v6 = 0; v6 = 5
U2 + v3 = 0; -2 + v3 = 0; v3 = 2
U3 + v3 = 10; 2 + u3 = 10; u3 = 8
U3 + v4 = 2; 8 + v4 = 2; v4 = -6
V1=7 |
V2=9 |
V3=2 |
V4=-6 |
V5=13 |
V6=5 | |
U1=0 |
7[20] |
3 |
4 |
8 |
6 |
0 |
U2=-2 |
5[5] |
7[20] |
0[35] |
2 |
3 |
0 |
U3=8 |
1 |
4 |
10[15] |
2[30] |
6 |
0 |
U4=-5 |
3 |
4[20] |
2 |
7 |
8[45] |
0[5] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых uI + vJ > cIj
- (1;2): 0 + 9 > 3; ?12 = 0 + 9 - 3 = 6 (1;5): 0 + 13 > 6; ?15 = 0 + 13 - 6 = 7 (1;6): 0 + 5 > 0; ?16 = 0 + 5 - 0 = 5 (2;5): -2 + 13 > 3; ?25 = -2 + 13 - 3 = 8 (2;6): -2 + 5 > 0; ?26 = -2 + 5 - 0 = 3 (3;1): 8 + 7 > 1; ?31 = 8 + 7 - 1 = 14 (3;2): 8 + 9 > 4; ?32 = 8 + 9 - 4 = 13 (3;5): 8 + 13 > 6; ?35 = 8 + 13 - 6 = 15 (3;6): 8 + 5 > 0; ?36 = 8 + 5 - 0 = 13
Max(6,7,5,8,3,14,13,15,13) = 15
Выбираем максимальную оценку свободной клетки (3;5): 6
Для этого в перспективную клетку (3;5) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".
1 |
2 |
3 |
4 |
5 |
6 |
Запасы | |
1 |
7[20] |
3 |
4 |
8 |
6 |
0 |
20 |
2 |
5[5] |
7[20][-] |
0[35][+] |
2 |
3 |
0 |
60 |
3 |
1 |
4 |
10[15][-] |
2[30] |
6[+] |
0 |
45 |
4 |
3 |
4[20][+] |
2 |
7 |
8[45][-] |
0[5] |
70 |
Потребности |
25 |
40 |
50 |
30 |
45 |
5 |
Цикл приведен в таблице (3,5 > 3,3 > 2,3 > 2,2 > 4,2 > 4,5).
Из грузов хIj стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (3, 3) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из ХIj, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
5 |
6 |
Запасы | |
1 |
7[20] |
3 |
4 |
8 |
6 |
0 |
20 |
2 |
5[5] |
7[5] |
0[50] |
2 |
3 |
0 |
60 |
3 |
1 |
4 |
10 |
2[30] |
6[15] |
0 |
45 |
4 |
3 |
4[35] |
2 |
7 |
8[30] |
0[5] |
70 |
Потребности |
25 |
40 |
50 |
30 |
45 |
5 |
Проверим оптимальность опорного плана. Найдем Предварительные потенциалы uI, vJ. по занятым клеткам таблицы, в которых uI + vJ = cIj, полагая, что u1 = 0.
U1 + v1 = 7; 0 + v1 = 7; v1 = 7
U2 + v1 = 5; 7 + u2 = 5; u2 = -2
U2 + v2 = 7; -2 + v2 = 7; v2 = 9
U4 + v2 = 4; 9 + u4 = 4; u4 = -5
U4 + v5 = 8; -5 + v5 = 8; v5 = 13
U3 + v5 = 6; 13 + u3 = 6; u3 = -7
U3 + v4 = 2; -7 + v4 = 2; v4 = 9
U4 + v6 = 0; -5 + v6 = 0; v6 = 5
U2 + v3 = 0; -2 + v3 = 0; v3 = 2
V1=7 |
V2=9 |
V3=2 |
V4=9 |
V5=13 |
V6=5 | |
U1=0 |
7[20] |
3 |
4 |
8 |
6 |
0 |
U2=-2 |
5[5] |
7[5] |
0[50] |
2 |
3 |
0 |
U3=-7 |
1 |
4 |
10 |
2[30] |
6[15] |
0 |
U4=-5 |
3 |
4[35] |
2 |
7 |
8[30] |
0[5] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых uI + vJ > cIj
- (1;2): 0 + 9 > 3; ?12 = 0 + 9 - 3 = 6 (1;4): 0 + 9 > 8; ?14 = 0 + 9 - 8 = 1 (1;5): 0 + 13 > 6; ?15 = 0 + 13 - 6 = 7 (1;6): 0 + 5 > 0; ?16 = 0 + 5 - 0 = 5 (2;4): -2 + 9 > 2; ?24 = -2 + 9 - 2 = 5 (2;5): -2 + 13 > 3; ?25 = -2 + 13 - 3 = 8 (2;6): -2 + 5 > 0; ?26 = -2 + 5 - 0 = 3
Max(6,1,7,5,5,8,3) = 8
Выбираем максимальную оценку свободной клетки (2;5): 3
Для этого в перспективную клетку (2;5) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".
1 |
2 |
3 |
4 |
5 |
6 |
Запасы | |
1 |
7[20] |
3 |
4 |
8 |
6 |
0 |
20 |
2 |
5[5] |
7[5][-] |
0[50] |
2 |
3[+] |
0 |
60 |
3 |
1 |
4 |
10 |
2[30] |
6[15] |
0 |
45 |
4 |
3 |
4[35][+] |
2 |
7 |
8[30][-] |
0[5] |
70 |
Потребности |
25 |
40 |
50 |
30 |
45 |
5 |
Цикл приведен в таблице (2,5 > 2,2 > 4,2 > 4,5).
Из грузов хIj стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (2, 2) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из ХIj, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
5 |
6 |
Запасы | |
1 |
7[20] |
3 |
4 |
8 |
6 |
0 |
20 |
2 |
5[5] |
7 |
0[50] |
2 |
3[5] |
0 |
60 |
3 |
1 |
4 |
10 |
2[30] |
6[15] |
0 |
45 |
4 |
3 |
4[40] |
2 |
7 |
8[25] |
0[5] |
70 |
Потребности |
25 |
40 |
50 |
30 |
45 |
5 |
Проверим оптимальность опорного плана. Найдем Предварительные потенциалы uI, vJ. по занятым клеткам таблицы, в которых uI + vJ = cIj, полагая, что u1 = 0.
U1 + v1 = 7; 0 + v1 = 7; v1 = 7
U2 + v1 = 5; 7 + u2 = 5; u2 = -2
U2 + v3 = 0; -2 + v3 = 0; v3 = 2
U2 + v5 = 3; -2 + v5 = 3; v5 = 5
U3 + v5 = 6; 5 + u3 = 6; u3 = 1
U3 + v4 = 2; 1 + v4 = 2; v4 = 1
U4 + v5 = 8; 5 + u4 = 8; u4 = 3
U4 + v2 = 4; 3 + v2 = 4; v2 = 1
U4 + v6 = 0; 3 + v6 = 0; v6 = -3
V1=7 |
V2=1 |
V3=2 |
V4=1 |
V5=5 |
V6=-3 | |
U1=0 |
7[20] |
3 |
4 |
8 |
6 |
0 |
U2=-2 |
5[5] |
7 |
0[50] |
2 |
3[5] |
0 |
U3=1 |
1 |
4 |
10 |
2[30] |
6[15] |
0 |
U4=3 |
3 |
4[40] |
2 |
7 |
8[25] |
0[5] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых uI + vJ > cIj
- (3;1): 1 + 7 > 1; ?31 = 1 + 7 - 1 = 7 (4;1): 3 + 7 > 3; ?41 = 3 + 7 - 3 = 7 (4;3): 3 + 2 > 2; ?43 = 3 + 2 - 2 = 3
Max(7,7,3) = 7
Выбираем максимальную оценку свободной клетки (3;1): 1
Для этого в перспективную клетку (3;1) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".
1 |
2 |
3 |
4 |
5 |
6 |
Запасы | |
1 |
7[20] |
3 |
4 |
8 |
6 |
0 |
20 |
2 |
5[5][-] |
7 |
0[50] |
2 |
3[5][+] |
0 |
60 |
3 |
1[+] |
4 |
10 |
2[30] |
6[15][-] |
0 |
45 |
4 |
3 |
4[40] |
2 |
7 |
8[25] |
0[5] |
70 |
Потребности |
25 |
40 |
50 |
30 |
45 |
5 |
Цикл приведен в таблице (3,1 > 3,5 > 2,5 > 2,1).
Из грузов хIj стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (2, 1) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из ХIj, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
5 |
6 |
Запасы | |
1 |
7[20] |
3 |
4 |
8 |
6 |
0 |
20 |
2 |
5 |
7 |
0[50] |
2 |
3[10] |
0 |
60 |
3 |
1[5] |
4 |
10 |
2[30] |
6[10] |
0 |
45 |
4 |
3 |
4[40] |
2 |
7 |
8[25] |
0[5] |
70 |
Потребности |
25 |
40 |
50 |
30 |
45 |
5 |
Проверим оптимальность опорного плана. Найдем Предварительные потенциалы uI, vJ. по занятым клеткам таблицы, в которых uI + vJ = cIj, полагая, что u1 = 0.
U1 + v1 = 7; 0 + v1 = 7; v1 = 7
U3 + v1 = 1; 7 + u3 = 1; u3 = -6
U3 + v4 = 2; -6 + v4 = 2; v4 = 8
U3 + v5 = 6; -6 + v5 = 6; v5 = 12
U2 + v5 = 3; 12 + u2 = 3; u2 = -9
U2 + v3 = 0; -9 + v3 = 0; v3 = 9
U4 + v5 = 8; 12 + u4 = 8; u4 = -4
U4 + v2 = 4; -4 + v2 = 4; v2 = 8
U4 + v6 = 0; -4 + v6 = 0; v6 = 4
V1=7 |
V2=8 |
V3=9 |
V4=8 |
V5=12 |
V6=4 | |
U1=0 |
7[20] |
3 |
4 |
8 |
6 |
0 |
U2=-9 |
5 |
7 |
0[50] |
2 |
3[10] |
0 |
U3=-6 |
1[5] |
4 |
10 |
2[30] |
6[10] |
0 |
U4=-4 |
3 |
4[40] |
2 |
7 |
8[25] |
0[5] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых uI + vJ > cIj
- (1;2): 0 + 8 > 3; ?12 = 0 + 8 - 3 = 5 (1;3): 0 + 9 > 4; ?13 = 0 + 9 - 4 = 5 (1;5): 0 + 12 > 6; ?15 = 0 + 12 - 6 = 6 (1;6): 0 + 4 > 0; ?16 = 0 + 4 - 0 = 4 (4;3): -4 + 9 > 2; ?43 = -4 + 9 - 2 = 3
Max(5,5,6,4,3) = 6
Выбираем максимальную оценку свободной клетки (1;5): 6
Для этого в перспективную клетку (1;5) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".
1 |
2 |
3 |
4 |
5 |
6 |
Запасы | |
1 |
7[20][-] |
3 |
4 |
8 |
6[+] |
0 |
20 |
2 |
5 |
7 |
0[50] |
2 |
3[10] |
0 |
60 |
3 |
1[5][+] |
4 |
10 |
2[30] |
6[10][-] |
0 |
45 |
4 |
3 |
4[40] |
2 |
7 |
8[25] |
0[5] |
70 |
Потребности |
25 |
40 |
50 |
30 |
45 |
5 |
Цикл приведен в таблице (1,5 > 1,1 > 3,1 > 3,5).
Из грузов хIj стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (3, 5) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из ХIj, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
5 |
6 |
Запасы | |
1 |
7[10] |
3 |
4 |
8 |
6[10] |
0 |
20 |
2 |
5 |
7 |
0[50] |
2 |
3[10] |
0 |
60 |
3 |
1[15] |
4 |
10 |
2[30] |
6 |
0 |
45 |
4 |
3 |
4[40] |
2 |
7 |
8[25] |
0[5] |
70 |
Потребности |
25 |
40 |
50 |
30 |
45 |
5 |
Проверим оптимальность опорного плана. Найдем Предварительные потенциалы uI, vJ. по занятым клеткам таблицы, в которых uI + vJ = cIj, полагая, что u1 = 0.
U1 + v1 = 7; 0 + v1 = 7; v1 = 7
U3 + v1 = 1; 7 + u3 = 1; u3 = -6
U3 + v4 = 2; -6 + v4 = 2; v4 = 8
U1 + v5 = 6; 0 + v5 = 6; v5 = 6
U2 + v5 = 3; 6 + u2 = 3; u2 = -3
U2 + v3 = 0; -3 + v3 = 0; v3 = 3
U4 + v5 = 8; 6 + u4 = 8; u4 = 2
U4 + v2 = 4; 2 + v2 = 4; v2 = 2
U4 + v6 = 0; 2 + v6 = 0; v6 = -2
V1=7 |
V2=2 |
V3=3 |
V4=8 |
V5=6 |
V6=-2 | |
U1=0 |
7[10] |
3 |
4 |
8 |
6[10] |
0 |
U2=-3 |
5 |
7 |
0[50] |
2 |
3[10] |
0 |
U3=-6 |
1[15] |
4 |
10 |
2[30] |
6 |
0 |
U4=2 |
3 |
4[40] |
2 |
7 |
8[25] |
0[5] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых uI + vJ > cIj
- (2;4): -3 + 8 > 2; ?24 = -3 + 8 - 2 = 3 (4;1): 2 + 7 > 3; ?41 = 2 + 7 - 3 = 6 (4;3): 2 + 3 > 2; ?43 = 2 + 3 - 2 = 3 (4;4): 2 + 8 > 7; ?44 = 2 + 8 - 7 = 3
Max(3,6,3,3) = 6
Выбираем максимальную оценку свободной клетки (4;1): 3
Для этого в перспективную клетку (4;1) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".
1 |
2 |
3 |
4 |
5 |
6 |
Запасы | |
1 |
7[10][-] |
3 |
4 |
8 |
6[10][+] |
0 |
20 |
2 |
5 |
7 |
0[50] |
2 |
3[10] |
0 |
60 |
3 |
1[15] |
4 |
10 |
2[30] |
6 |
0 |
45 |
4 |
3[+] |
4[40] |
2 |
7 |
8[25][-] |
0[5] |
70 |
Потребности |
25 |
40 |
50 |
30 |
45 |
5 |
Цикл приведен в таблице (4,1 > 4,5 > 1,5 > 1,1).
Из грузов хIj стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (1, 1) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из ХIj, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
5 |
6 |
Запасы | |
1 |
7 |
3 |
4 |
8 |
6[20] |
0 |
20 |
2 |
5 |
7 |
0[50] |
2 |
3[10] |
0 |
60 |
3 |
1[15] |
4 |
10 |
2[30] |
6 |
0 |
45 |
4 |
3[10] |
4[40] |
2 |
7 |
8[15] |
0[5] |
70 |
Потребности |
25 |
40 |
50 |
30 |
45 |
5 |
Проверим оптимальность опорного плана. Найдем Предварительные потенциалы uI, vJ. по занятым клеткам таблицы, в которых uI + vJ = cIj, полагая, что u1 = 0.
U1 + v5 = 6; 0 + v5 = 6; v5 = 6
U2 + v5 = 3; 6 + u2 = 3; u2 = -3
U2 + v3 = 0; -3 + v3 = 0; v3 = 3
U4 + v5 = 8; 6 + u4 = 8; u4 = 2
U4 + v1 = 3; 2 + v1 = 3; v1 = 1
U3 + v1 = 1; 1 + u3 = 1; u3 = 0
U3 + v4 = 2; 0 + v4 = 2; v4 = 2
U4 + v2 = 4; 2 + v2 = 4; v2 = 2
U4 + v6 = 0; 2 + v6 = 0; v6 = -2
V1=1 |
V2=2 |
V3=3 |
V4=2 |
V5=6 |
V6=-2 | |
U1=0 |
7 |
3 |
4 |
8 |
6[20] |
0 |
U2=-3 |
5 |
7 |
0[50] |
2 |
3[10] |
0 |
U3=0 |
1[15] |
4 |
10 |
2[30] |
6 |
0 |
U4=2 |
3[10] |
4[40] |
2 |
7 |
8[15] |
0[5] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых uI + vJ > cIj
(4;3): 2 + 3 > 2; ?43 = 2 + 3 - 2 = 3
Выбираем максимальную оценку свободной клетки (4;3): 2
Для этого в перспективную клетку (4;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".
1 |
2 |
3 |
4 |
5 |
6 |
Запасы | |
1 |
7 |
3 |
4 |
8 |
6[20] |
0 |
20 |
2 |
5 |
7 |
0[50][-] |
2 |
3[10][+] |
0 |
60 |
3 |
1[15] |
4 |
10 |
2[30] |
6 |
0 |
45 |
4 |
3[10] |
4[40] |
2[+] |
7 |
8[15][-] |
0[5] |
70 |
Потребности |
25 |
40 |
50 |
30 |
45 |
5 |
Цикл приведен в таблице (4,3 > 4,5 > 2,5 > 2,3).
Из грузов хIj стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (4, 5) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из ХIj, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
5 |
6 |
Запасы | |
1 |
7 |
3 |
4 |
8 |
6[20] |
0 |
20 |
2 |
5 |
7 |
0[35] |
2 |
3[25] |
0 |
60 |
3 |
1[15] |
4 |
10 |
2[30] |
6 |
0 |
45 |
4 |
3[10] |
4[40] |
2[15] |
7 |
8 |
0[5] |
70 |
Потребности |
25 |
40 |
50 |
30 |
45 |
5 |
Проверим оптимальность опорного плана. Найдем Предварительные потенциалы uI, vJ. по занятым клеткам таблицы, в которых uI + vJ = cIj, полагая, что u1 = 0.
U1 + v5 = 6; 0 + v5 = 6; v5 = 6
U2 + v5 = 3; 6 + u2 = 3; u2 = -3
U2 + v3 = 0; -3 + v3 = 0; v3 = 3
U4 + v3 = 2; 3 + u4 = 2; u4 = -1
U4 + v1 = 3; -1 + v1 = 3; v1 = 4
U3 + v1 = 1; 4 + u3 = 1; u3 = -3
U3 + v4 = 2; -3 + v4 = 2; v4 = 5
U4 + v2 = 4; -1 + v2 = 4; v2 = 5
U4 + v6 = 0; -1 + v6 = 0; v6 = 1
V1=4 |
V2=5 |
V3=3 |
V4=5 |
V5=6 |
V6=1 | |
U1=0 |
7 |
3 |
4 |
8 |
6[20] |
0 |
U2=-3 |
5 |
7 |
0[35] |
2 |
3[25] |
0 |
U3=-3 |
1[15] |
4 |
10 |
2[30] |
6 |
0 |
U4=-1 |
3[10] |
4[40] |
2[15] |
7 |
8 |
0[5] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых uI + vJ > cIj
- (1;2): 0 + 5 > 3; ?12 = 0 + 5 - 3 = 2 (1;6): 0 + 1 > 0; ?16 = 0 + 1 - 0 = 1
Max(2,1) = 2
Выбираем максимальную оценку свободной клетки (1;2): 3
Для этого в перспективную клетку (1;2) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".
1 |
2 |
3 |
4 |
5 |
6 |
Запасы | |
1 |
7 |
3[+] |
4 |
8 |
6[20][-] |
0 |
20 |
2 |
5 |
7 |
0[35][-] |
2 |
3[25][+] |
0 |
60 |
3 |
1[15] |
4 |
10 |
2[30] |
6 |
0 |
45 |
4 |
3[10] |
4[40][-] |
2[15][+] |
7 |
8 |
0[5] |
70 |
Потребности |
25 |
40 |
50 |
30 |
45 |
5 |
Цикл приведен в таблице (1,2 > 1,5 > 2,5 > 2,3 > 4,3 > 4,2).
Из грузов хIj стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (1, 5) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из ХIj, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
5 |
6 |
Запасы | |
1 |
7 |
3[20] |
4 |
8 |
6 |
0 |
20 |
2 |
5 |
7 |
0[15] |
2 |
3[45] |
0 |
60 |
3 |
1[15] |
4 |
10 |
2[30] |
6 |
0 |
45 |
4 |
3[10] |
4[20] |
2[35] |
7 |
8 |
0[5] |
70 |
Потребности |
25 |
40 |
50 |
30 |
45 |
5 |
Проверим оптимальность опорного плана. Найдем Предварительные потенциалы uI, vJ. по занятым клеткам таблицы, в которых uI + vJ = cIj, полагая, что u1 = 0.
U1 + v2 = 3; 0 + v2 = 3; v2 = 3
U4 + v2 = 4; 3 + u4 = 4; u4 = 1
U4 + v1 = 3; 1 + v1 = 3; v1 = 2
U3 + v1 = 1; 2 + u3 = 1; u3 = -1
U3 + v4 = 2; -1 + v4 = 2; v4 = 3
U4 + v3 = 2; 1 + v3 = 2; v3 = 1
U2 + v3 = 0; 1 + u2 = 0; u2 = -1
U2 + v5 = 3; -1 + v5 = 3; v5 = 4
U4 + v6 = 0; 1 + v6 = 0; v6 = -1
V1=2 |
V2=3 |
V3=1 |
V4=3 |
V5=4 |
V6=-1 | |
U1=0 |
7 |
3[20] |
4 |
8 |
6 |
0 |
U2=-1 |
5 |
7 |
0[15] |
2 |
3[45] |
0 |
U3=-1 |
1[15] |
4 |
10 |
2[30] |
6 |
0 |
U4=1 |
3[10] |
4[20] |
2[35] |
7 |
8 |
0[5] |
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию uI + vJ ? cIj.
Минимальные затраты составят: F(x) = 3*20 + 0*15 + 3*45 + 1*15 + 2*30 + 3*10 + 4*20 + 2*35 + 0*5 = 450
Анализ оптимального плана.
Из 1-го склада необходимо часть груза (20) направить в 2-й магазин.
Из 2-го склада необходимо груз направить в 3-й магазин (15), в 5-й магазин (45)
Из 3-го склада необходимо груз направить в 1-й магазин (15), в 4-й магазин (30)
Из 4-го склада необходимо груз направить в 1-й магазин (10), в 2-й магазин (20), в 3-й магазин (35)
На 4-ом складе остался невостребованным груз в количестве 5 ед.
Оптимальный план является вырожденным, так как базисная переменная x46=0.
Похожие статьи
-
A 25 40 50 30 45 20 7 3 4 8 6 60 5 7 2 3 5 45 1 4 10 2 6 70 3 4 2 7 8 Допустим, стоимость доставки единицы груза из каждого пункта отправления в...
-
Метод Фогеля - Математическое моделирование в менеджменте и маркетинге
Этап I. Поиск первого опорного плана . 1. Используя метод Фогеля, построим первый опорный план транспортной задачи. Для каждой строки и столбца таблицы...
-
Математическая модель транспортной задачи: F = ??cIjXIj, (1) При условиях: ?xIj = aI, i = 1,2,..., m, (2) ?xIj = bJ, j = 1,2,..., n, (3)...
-
Теоретическое обоснование математического моделирования - Математические методы и модели в экономике
Коммерческая деятельность в том или ином виде сводится к решению таких задач: как распорядиться имеющимися ресурсами для достижения наибольшей выгоды или...
-
Решение: Строим на плоскости х1Ох2 многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки...
-
Решение транспортной задачи методом потенциалов - Математическая модель решения транспортной задачи
Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями...
-
Условие задачи. Пусть имеются n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами CIj (i, j = 1,2,..., n)....
-
Метод конечных разностей -- широко известный и простейший метод интерполяции. Его суть заключается в замене дифференциальных коэффициентов уравнения на...
-
Методы исследования математических моделей - Математическое моделирование в менеджменте и маркетинге
Все методы математического моделирования можно разделить на четыре класса: -аналитические (априорные); -имитационные (априорно-апостериорные) модели;...
-
Классификация моделей - Математическое моделирование в менеджменте и маркетинге
Классифицировать модели можно по разным критериям. Например, по характеру решаемых проблем модели могут быть разделены на функциональные и структурные. В...
-
1. Универсальность - характеризует полноту отображения моделью изучаемых свойств реального объекта. 2. Адекватность - способность отражать нужные...
-
Алгоритм решения ТЗ методом потенциалов - Экономико-математические методы
Построить опорный план по одному из правил. Проверить план на невырожденность. Если полученный план вырожденный, формально заполняют нулями некоторые из...
-
Метод конечных элементов - МАтематическое моделирование в экономике
- Метод конечных элементов: триангуляция - Метод конечных элементов ( МКЭ ) -- численный метод решения задач прикладной механики. - Широко используется...
-
Проникновение математики в экономическую науку связано с преодолением значительных трудностей. В этом отчасти была "по-винна" математика, развивающаяся...
-
Календарный производственный программирование однооперационный Все существующие методы решения задач календарного планирования3 по степени достижения...
-
Решение задачи графическим методом - Математическое моделирование в менеджменте и маркетинге
Необходимо найти максимальное значение целевой функции L(x)= 2x1+2x2 > max, при системе ограничений: 6x1+8x2?48, (1) 8x1+11x2?88, (2)...
-
Классификация математических моделей - Математическое моделирование в менеджменте и маркетинге
Математические модели могут быть Детерменированными и Стохастическими . Детерменированные модели - это модели, в которых установлено взаимно-однозначное...
-
С середины XX в. в самых различных областях человеческой деятельности стали широко применять математические методы и ЭВМ. Возникли такие новые...
-
Задание. Рассматривается вычислительная система состоящая из n вычислительных машин. Имеется n задач. Задана матрица T определяющая время решения i-й...
-
Решение симплекс-методом с помощью симплекс-таблиц - Математические методы и модели в экономике
Определим оптимальный план выпуска продукции, решив задачу линейного программирования (ЗЛП). Для этого сначала приведем модель к каноническому виду...
-
В основе метода площадей лежит предположение, что объект может быть описан линейным дифференциальным уравнением с постоянными коэффициентами, а его...
-
В инженерной практике в настоящее время широко используются современные программные комплексы позволяющие моделировать сложные физические процессы. Для...
-
Методы построения решений по математическим моделям - Математическое моделирование в электромеханике
Системы дифференциальных уравнений, полученные для конкретных ти-пов электрических машин, содержат в скрытом виде исчерпывающую инфор-мацию о всех...
-
К числу приближенных методов оптимизации задач календарного планирования относятся: частичный и направленный перебор, метод Монте-Карло,...
-
Пример решения транспортной задачи - Экономико-математические методы
На четырех строительных площадках В1, В2, В3, В4 монтируется в день соответственно 20,120,20 60 м3 сборных плит перекрытий. Производство этих плит...
-
Транспортные задачи, имеющие некоторые усложнения в постановке - Экономико-математические методы
Транспортная задача с избытком запасов: Для отыскания оптимального плана вводят фиктивный (n+1)-й пункт назначения Bn+1 с потребностью bn+1 и полагают...
-
Построение исходного опорного плана - Экономико-математические методы
Моделирование экономический математический опорный Построение опорных планов, а также их преобразование будем производить непосредственно в...
-
На основании проведенного моделирования можно сделать выводы: - происходящие тепловые процессы скоротечны и не приводят к перегреву конструкции блока...
-
Модели и моделирование - Экономико-математические методы
Одним из основных методов научного познания является эксперимент, а самой распространенной его разновидностью - метод моделирования систем. В процессе...
-
Введение - Методы экономико-математического моделирования
Экономико-математическое моделирование является неотъемлемой частью любого исследования в области экономики. Бурное развитие математического анализа,...
-
В 1974г. группа аргентинских ученых во главе с профессором А. Эррерой получила предварительные результаты работы над латиноамериканской моделью...
-
В большинстве реальных больших систем не обойтись без учета "состояний природы" -- воздействий Стохастического типа, случайных величин или случайных...
-
На сегодняшний день существует достаточно большое количество методов моделирования бизнес процессов. Эти методы относятся к разным видам моделирования и...
-
Элементы матричного анализа - Методы решения системы линейных уравнений
Вектором, как на плоскости, так и в пространстве, называется направленный Отрезок , то есть такой Отрезок , один из концов которого выделен и называется...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ. ПРИМЕРЫ - Задача коммивояжера
Рассмотрим конкретный пример реализации метода ветвей и границ для решения задачи о коммивояжере. Итак, требуется найти легчайший простой основный...
-
Любой электромеханический преобразователь можно рассматривать в установившемся и динамическом режиме. Модель в установившемся режиме, по сути, является...
-
Введение - Математическое моделирование в электромеханике
Математическое моделирование является основой для проведения исследований практически во всех областях науки и техники. Соответственно не является...
-
Как в теоретическом, так и в прикладном отношении представляют интерес работы по построению и использованию производственных функций для анализа...
-
Датой рождения метода Монте-Карло принято считать 1949 г., когда появилась статья под названием "The Monte Carlo method". Создателями этого метода...
-
Известно, что проблема замены старого парка машин новыми, устаревших орудий -- современными -- одна из основных проблем индустрии. Оборудование со...
Метод северо-западного угла - Математическое моделирование в менеджменте и маркетинге