Автор работы: Пользователь скрыл имя, 28 Апреля 2013 в 22:31, доклад
Одной из классических задач экономического содержания является транспортная задача, решаемая средствами линейного программирования. Данная задача относится к задачам прикладной направленности, и в промышленных регионах ее решение приобретает особо важное значение. Цель транспортной задачи - разработка наиболее рациональных путей и способов транспортирования товаров, устранение чрезмерно дальних, встречных, повторных перевозок. Все это сокращает время продвижения товаров, уменьшает затраты предприятий, фирм, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д.
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 3) = 40. Прибавляем 40 к объемам грузов, стоящих в плюсовых клетках и вычитаем 40 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Таблица 14
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
4[70] |
5[45] |
2 |
8 |
6 |
115 |
2 |
3 |
1[135] |
9[40] |
7 |
3 |
175 |
3 |
9 |
6[40] |
7 |
2[30] |
1[60] |
130 |
Потребности |
70 |
220 |
40 |
30 |
60 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
u1 + v1 = 4; 0 + v1 = 4; v1 = 4
u1 + v2 = 5; 0 + v2 = 5; v2 = 5
u2 + v2 = 1; 5 + u2 = 1; u2 = -4
u2 + v3 = 9; -4 + v3 = 9; v3 = 13
u3 + v2 = 6; 5 + u3 = 6; u3 = 1
u3 + v4 = 2; 1 + v4 = 2; v4 = 1
u3 + v5 = 1; 1 + v5 = 1; v5 = 0
Таблица 15
v1=4 |
v2=5 |
v3=13 |
v4=1 |
v5=0 | |
u1=0 |
4[70] |
5[45] |
2 |
8 |
6 |
u2=-4 |
3 |
1[135] |
9[40] |
7 |
3 |
u3=1 |
9 |
6[40] |
7 |
2[30] |
1[60] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
(1;4): 0 + 1 < 8; ∆14 = 0 + 1 - 8 = -7
(1;5): 0 + 0 < 6; ∆15 = 0 + 0 - 6 = -6
(2;1): -4 + 4 < 3; ∆21 = -4 + 4 - 3 = -3
(2;4): -4 + 1 < 7; ∆24 = -4 + 1 - 7 = -10
(2;5): -4 + 0 < 3; ∆25 = -4 + 0 - 3 = -7
(3;1): 1 + 4 < 9; ∆31 = 1 + 4 - 9 = -4
max(7,6,3,10,7,4) = -10
Выбираем максимальную оценку свободной клетки (2;4): 7
Для этого в перспективную клетку (2;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Таблица 16
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
4[70] |
5[45] |
2 |
8 |
6 |
115 |
2 |
3 |
1[135][-] |
9[40] |
7[+] |
3 |
175 |
3 |
9 |
6[40][+] |
7 |
2[30][-] |
1[60] |
130 |
Потребности |
70 |
220 |
40 |
30 |
60 |
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 4) = 30. Прибавляем 30 к объемам грузов, стоящих в плюсовых клетках и вычитаем 30 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Таблица 17
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
4[70] |
5[45] |
2 |
8 |
6 |
115 |
2 |
3 |
1[105] |
9[40] |
7[30] |
3 |
175 |
3 |
9 |
6[70] |
7 |
2 |
1[60] |
130 |
Потребности |
70 |
220 |
40 |
30 |
60 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
u1 + v1 = 4; 0 + v1 = 4; v1 = 4
u1 + v2 = 5; 0 + v2 = 5; v2 = 5
u2 + v2 = 1; 5 + u2 = 1; u2 = -4
u2 + v3 = 9; -4 + v3 = 9; v3 = 13
u2 + v4 = 7; -4 + v4 = 7; v4 = 11
u3 + v2 = 6; 5 + u3 = 6; u3 = 1
u3 + v5 = 1; 1 + v5 = 1; v5 = 0
Таблица 18
v1=4 |
v2=5 |
v3=13 |
v4=11 |
v5=0 | |
u1=0 |
4[70] |
5[45] |
2 |
8 |
6 |
u2=-4 |
3 |
1[105] |
9[40] |
7[30] |
3 |
u3=1 |
9 |
6[70] |
7 |
2 |
1[60] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
(1;5): 0 + 0 < 6; ∆15 = 0 + 0 - 6 = -6
(2;1): -4 + 4 < 3; ∆21 = -4 + 4 - 3 = -3
(2;5): -4 + 0 < 3; ∆25 = -4 + 0 - 3 = -7
(3;1): 1 + 4 < 9; ∆31 = 1 + 4 - 9 = -4
max(6,3,7,4) = -7
Выбираем максимальную оценку свободной клетки (2;5): 3
Для этого в перспективную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Таблица 19
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
4[70] |
5[45] |
2 |
8 |
6 |
115 |
2 |
3 |
1[105][-] |
9[40] |
7[30] |
3[+] |
175 |
3 |
9 |
6[70][+] |
7 |
2 |
1[60][-] |
130 |
Потребности |
70 |
220 |
40 |
30 |
60 |
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 5) = 60. Прибавляем 60 к объемам грузов, стоящих в плюсовых клетках и вычитаем 60 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Таблица 20
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
4[70] |
5[45] |
2 |
8 |
6 |
115 |
2 |
3 |
1[45] |
9[40] |
7[30] |
3[60] |
175 |
3 |
9 |
6[130] |
7 |
2 |
1 |
130 |
Потребности |
70 |
220 |
40 |
30 |
60 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
u1 + v1 = 4; 0 + v1 = 4; v1 = 4
u1 + v2 = 5; 0 + v2 = 5; v2 = 5
u2 + v2 = 1; 5 + u2 = 1; u2 = -4
u2 + v3 = 9; -4 + v3 = 9; v3 = 13
u2 + v4 = 7; -4 + v4 = 7; v4 = 11
u2 + v5 = 3; -4 + v5 = 3; v5 = 7
u3 + v2 = 6; 5 + u3 = 6; u3 = 1
Таблица 21
v1=4 |
v2=5 |
v3=13 |
v4=11 |
v5=7 | |
u1=0 |
4[70] |
5[45] |
2 |
8 |
6 |
u2=-4 |
3 |
1[45] |
9[40] |
7[30] |
3[60] |
u3=1 |
9 |
6[130] |
7 |
2 |
1 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
(2;1): -4 + 4 < 3; ∆21 = -4 + 4 - 3 = -3
(3;1): 1 + 4 < 9; ∆31 = 1 + 4 - 9 = -4
max(3,4) = -4
Выбираем максимальную оценку свободной клетки (3;1): 9
Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Таблица 22
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
4[70][-] |
5[45][+] |
2 |
8 |
6 |
115 |
2 |
3 |
1[45] |
9[40] |
7[30] |
3[60] |
175 |
3 |
9[+] |
6[130][-] |
7 |
2 |
1 |
130 |
Потребности |
70 |
220 |
40 |
30 |
60 |
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 70. Прибавляем 70 к объемам грузов, стоящих в плюсовых клетках и вычитаем 70 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Таблица 23
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
4 |
5[115] |
2 |
8 |
6 |
115 |
2 |
3 |
1[45] |
9[40] |
7[30] |
3[60] |
175 |
3 |
9[70] |
6[60] |
7 |
2 |
1 |
130 |
Потребности |
70 |
220 |
40 |
30 |
60 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.