Автор работы: Пользователь скрыл имя, 12 Января 2015 в 15:44, контрольная работа
1. Задачу решите графическим методом.
2. Задание 2
Задачу решите симплексным методом.
Задание 3
Составьте оптимальный план перевозки грузов от поставщиков с грузами 160, 60, 180 т к потребителям с запросами 80, 60, 60 и 200 т. Стоимости перевозок единицы груза от каждого поставщика к каждому потребителю даны матрицей
Цикл приведен в таблице (1,4 → 1,3 → 2,3 → 2,4).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 3) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
Запасы | |
1 |
8[80] |
6[60] |
9 |
2[20] |
160 |
2 |
7 |
16 |
12[60] |
12[0] |
60 |
3 |
6 |
15 |
8 |
3[180] |
180 |
Потребности |
80 |
60 |
60 |
200 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 8; 0 + v1 = 8; v1 = 8
u1 + v2 = 6; 0 + v2 = 6; v2 = 6
u1 + v4 = 2; 0 + v4 = 2; v4 = 2
u2 + v4 = 12; 2 + u2 = 12; u2 = 10
u2 + v3 = 12; 10 + v3 = 12; v3 = 2
u3 + v4 = 3; 2 + u3 = 3; u3 = 1
v1=8 |
v2=6 |
v3=2 |
v4=2 | |
u1=0 |
8[80] |
6[60] |
9 |
2[20] |
u2=10 |
7 |
16 |
12[60] |
12[0] |
u3=1 |
6 |
15 |
8 |
3[180] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(2;1): 10 + 8 > 7; ∆21 = 10 + 8 - 7 = 11
(3;1): 1 + 8 > 6; ∆31 = 1 + 8 - 6 = 3
max(11,3) = 11
Выбираем максимальную оценку свободной клетки (2;1): 7
Для этого в перспективную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 |
2 |
3 |
4 |
Запасы | |
1 |
8[80][-] |
6[60] |
9 |
2[20][+] |
160 |
2 |
7[+] |
16 |
12[60] |
12[0][-] |
60 |
3 |
6 |
15 |
8 |
3[180] |
180 |
Потребности |
80 |
60 |
60 |
200 |
Цикл приведен в таблице (2,1 → 2,4 → 1,4 → 1,1).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 4) = 0. Прибавляем 0 к объемам грузов, стоящих в плюсовых клетках и вычитаем 0 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
Запасы | |
1 |
8[80] |
6[60] |
9 |
2[20] |
160 |
2 |
7[0] |
16 |
12[60] |
12 |
60 |
3 |
6 |
15 |
8 |
3[180] |
180 |
Потребности |
80 |
60 |
60 |
200 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 8; 0 + v1 = 8; v1 = 8
u2 + v1 = 7; 8 + u2 = 7; u2 = -1
u2 + v3 = 12; -1 + v3 = 12; v3 = 13
u1 + v2 = 6; 0 + v2 = 6; v2 = 6
u1 + v4 = 2; 0 + v4 = 2; v4 = 2
u3 + v4 = 3; 2 + u3 = 3; u3 = 1
v1=8 |
v2=6 |
v3=13 |
v4=2 | |
u1=0 |
8[80] |
6[60] |
9 |
2[20] |
u2=-1 |
7[0] |
16 |
12[60] |
12 |
u3=1 |
6 |
15 |
8 |
3[180] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;3): 0 + 13 > 9; ∆13 = 0 + 13 - 9 = 4
(3;1): 1 + 8 > 6; ∆31 = 1 + 8 - 6 = 3
(3;3): 1 + 13 > 8; ∆33 = 1 + 13 - 8 = 6
max(4,3,6) = 6
Выбираем максимальную оценку свободной клетки (3;3): 8
Для этого в перспективную клетку (3;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 |
2 |
3 |
4 |
Запасы | |
1 |
8[80][-] |
6[60] |
9 |
2[20][+] |
160 |
2 |
7[0][+] |
16 |
12[60][-] |
12 |
60 |
3 |
6 |
15 |
8[+] |
3[180][-] |
180 |
Потребности |
80 |
60 |
60 |
200 |
Цикл приведен в таблице (3,3 → 3,4 → 1,4 → 1,1 → 2,1 → 2,3).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3) = 60. Прибавляем 60 к объемам грузов, стоящих в плюсовых клетках и вычитаем 60 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
Запасы | |
1 |
8[20] |
6[60] |
9 |
2[80] |
160 |
2 |
7[60] |
16 |
12 |
12 |
60 |
3 |
6 |
15 |
8[60] |
3[120] |
180 |
Потребности |
80 |
60 |
60 |
200 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 8; 0 + v1 = 8; v1 = 8
u2 + v1 = 7; 8 + u2 = 7; u2 = -1
u1 + v2 = 6; 0 + v2 = 6; v2 = 6
u1 + v4 = 2; 0 + v4 = 2; v4 = 2
u3 + v4 = 3; 2 + u3 = 3; u3 = 1
u3 + v3 = 8; 1 + v3 = 8; v3 = 7
v1=8 |
v2=6 |
v3=7 |
v4=2 | |
u1=0 |
8[20] |
6[60] |
9 |
2[80] |
u2=-1 |
7[60] |
16 |
12 |
12 |
u3=1 |
6 |
15 |
8[60] |
3[120] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(3;1): 1 + 8 > 6; ∆31 = 1 + 8 - 6 = 3
Выбираем максимальную оценку свободной клетки (3;1): 6
Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 |
2 |
3 |
4 |
Запасы | |
1 |
8[20][-] |
6[60] |
9 |
2[80][+] |
160 |
2 |
7[60] |
16 |
12 |
12 |
60 |
3 |
6[+] |
15 |
8[60] |
3[120][-] |
180 |
Потребности |
80 |
60 |
60 |
200 |
Цикл приведен в таблице (3,1 → 3,4 → 1,4 → 1,1).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
Запасы | |
1 |
8 |
6[60] |
9 |
2[100] |
160 |
2 |
7[60] |
16 |
12 |
12 |
60 |
3 |
6[20] |
15 |
8[60] |
3[100] |
180 |
Потребности |
80 |
60 |
60 |
200 |
Информация о работе Контрольная работа по дисциплине «Методы оптимальных решений»