Автор работы: Пользователь скрыл имя, 09 Сентября 2013 в 13:50, контрольная работа
Для приготовления комбикорма совхоз может закупить зерно 2-х сортов, отличающихся друг от друга содержанием питательных компонентов. Для обеспечения нормального питания скота в течение планируемого периода комбикорм должен содержать не менее bj единиц питательного компонента j -го типа (j=1,n). Одна тонна зерна i-ro сорта стоит Ri рублей и содержит aij единиц питательного компонента j-го типа. Складские помещения позволяют хранить не более А тонн зерна. Определить, какое минимальное количество средств должен вложить совхоз в закупку зерна, чтобы обеспечить заданную питательность комбикорма с учетом емкости складских помещений.
Сколько зерна каждого сорта необходимо закупить, если А=7000 тонн?
В результате получен
первый опорный план, который является
допустимым, так как все грузы
из баз вывезены, потребность магазинов
удовлетворена, а план соответствует
системе ограничений
2. Подсчитаем число
занятых клеток таблицы, их 4, а
должно быть m + n - 1 = 4. Следовательно,
опорный план является невырожд
Значение целевой функции для этого опорного плана равно:
F(x) = 40*6 + 50*2 + 30*4 + 20*8 = 620
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
u1 + v1 = 40; 0 + v1 = 40; v1 = 40
u2 + v1 = 30; 40 + u2 = 30; u2 = -10
u2 + v3 = 20; -10 + v3 = 20; v3 = 30
u1 + v2 = 50; 0 + v2 = 50; v2 = 50
v1=40 |
v2=50 |
v3=30 | |
u1=0 |
40[6] |
50[2] |
20 |
u2=-10 |
30[4] |
30 |
20[8] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
(1;3): 0 + 30 > 20; ∆13 = 0 + 30 - 20 = 10
(2;2): -10 + 50 > 30; ∆22 = -10 + 50 - 30 = 10
max(10,10) = 10
Выбираем максимальную оценку свободной клетки (1;3): 20
Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 |
2 |
3 |
Запасы | |
1 |
40[6][-] |
50[2] |
20[+] |
8 |
2 |
30[4][+] |
30 |
20[8][-] |
12 |
Потребности |
10 |
2 |
8 |
Цикл приведен в таблице (1,3; 1,1; 2,1; 2,3; ).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 6. Прибавляем 6 к объемам грузов, стоящих в плюсовых клетках и вычитаем 6 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
Запасы | |
1 |
40 |
50[2] |
20[6] |
8 |
2 |
30[10] |
30 |
20[2] |
12 |
Потребности |
10 |
2 |
8 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
u1 + v2 = 50; 0 + v2 = 50; v2 = 50
u1 + v3 = 20; 0 + v3 = 20; v3 = 20
u2 + v3 = 20; 20 + u2 = 20; u2 = 0
u2 + v1 = 30; 0 + v1 = 30; v1 = 30
v1=30 |
v2=50 |
v3=20 | |
u1=0 |
40 |
50[2] |
20[6] |
u2=0 |
30[10] |
30 |
20[2] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
(2;2): 0 + 50 > 30; ∆22 = 0 + 50 - 30 = 20
Выбираем максимальную оценку свободной клетки (2;2): 30
Для этого в перспективную клетку (2;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 |
2 |
3 |
Запасы | |
1 |
40 |
50[2][-] |
20[6][+] |
8 |
2 |
30[10] |
30[+] |
20[2][-] |
12 |
Потребности |
10 |
2 |
8 |
Цикл приведен в таблице (2,2; 2,3; 1,3; 1,2; ).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3) = 2. Прибавляем 2 к объемам грузов, стоящих в плюсовых клетках и вычитаем 2 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
Запасы | |
1 |
40 |
50[0] |
20[8] |
8 |
2 |
30[10] |
30[2] |
20 |
12 |
Потребности |
10 |
2 |
8 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
u1 + v2 = 50; 0 + v2 = 50; v2 = 50
u2 + v2 = 30; 50 + u2 = 30; u2 = -20
u2 + v1 = 30; -20 + v1 = 30; v1 = 50
u1 + v3 = 20; 0 + v3 = 20; v3 = 20
v1=50 |
v2=50 |
v3=20 | |
u1=0 |
40 |
50[0] |
20[8] |
u2=-20 |
30[10] |
30[2] |
20 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
(1;1): 0 + 50 > 40; ∆11 = 0 + 50 - 40 = 10
Выбираем максимальную оценку свободной клетки (1;1): 40
Для этого в перспективную клетку (1;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 |
2 |
3 |
Запасы | |
1 |
40[+] |
50[0][-] |
20[8] |
8 |
2 |
30[10][-] |
30[2][+] |
20 |
12 |
Потребности |
10 |
2 |
8 |
Цикл приведен в таблице (1,1; 1,2; 2,2; 2,1; ).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 0. Прибавляем 0 к объемам грузов, стоящих в плюсовых клетках и вычитаем 0 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
Запасы | |
1 |
40[0] |
50 |
20[8] |
8 |
2 |
30[10] |
30[2] |
20 |
12 |
Потребности |
10 |
2 |
8 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
u1 + v1 = 40; 0 + v1 = 40; v1 = 40
u2 + v1 = 30; 40 + u2 = 30; u2 = -10
u2 + v2 = 30; -10 + v2 = 30; v2 = 40
u1 + v3 = 20; 0 + v3 = 20; v3 = 20
v1=40 |
v2=40 |
v3=20 | |
u1=0 |
40[0] |
50 |
20[8] |
u2=-10 |
30[10] |
30[2] |
20 |
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij.
Минимальные затраты составят:
F(x) = 20*8 + 30*10 + 30*2 = 520
Проверим оптимальность найденного плана по первой теореме двойственности (в оптимальном решении значения целевых функций прямой и двойственных задач совпадают: F = G).
G = 0•8 -10•12 + 40•10 + 40•2 + 20•8 = 520
Информация о работе Моделирование однокритериальных задач принятия решений в условиях определенности