Реферат: Линейное и динамическое программирование
x2 (2y1 +3y2 +5y3 -30)=0 y2 (2х1 +3х2 +1х3 +2х4 )-96=0
x3 (4y1 +1y2 +1y3 -29)=0 y3 (6х1 +5х2 +1х3 +0х4 )-228=0
x4 (3y1 +2y2 +0y3 -10)=0
В решении исходной задачи х1 >0, х3 >0, поэтому
3y1 +2y2 +6y3 -48=0
4y1 +1y2 +1y3 -29=0
Учитывая, что второй ресурс был избыточным и, согласно теореме двойственности его оценка равна нулю – y2 =0, то приходим к системе:
3y1 +6y3 -48=0
4y1 +1y3 -29=0
из которой следует, что y1 =6; y3 =5.
Таким образом получили двойственные оценки ресурсов: y1 =6; y2 =0; y3 =5; общая оценка всех ресурсов Z=198y1 +228y3 =2328.
Заметим, что полученное решение содержалось в последней строке последней симплексной таблицы исходной задачи
Таблица N 3
| C | B | H | 48 | 30 | 29 | 10 | 0 | 0 | 0 |
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | |||
| 29 | х3 | 24 | 0 | -1 /7 | 1 | 6 /7 | 2 /7 | 0 | -1 /7 |
| 0 | x6 | 4 | 0 | 13 /7 | 0 | 13 /7 | -4 /21 | 1 | -5 /21 |
| 48 | х1 | 34 | 1 | 6 /7 | 0 | -1 /7 | -1 /21 | 0 | 4 /21 |
| 2328 | 0 | 7 | 0 | 8 | 6 | 0 | 5 |
Решение одной из пары двойственных задач можно найти, зная только ответ к другой задаче и пользуясь 2-й теоремой двойственности: если i-e ограничение одной из пары двойственных задач на компонентах оптимального решения есть строгое неравенство, то оптимальное значение i-й переменной другой задачи равно 0, или, что то же самое - если оптимальное значение j-й переменной одной задачи строго положительно, то j-e ограничение другой из пары двойственных задач на компонентах оптимального решения есть равенство.
Важен экономический смысл двойственных оценок. Двойственная оценка, например, третьего ресурса у3 =5 показывает, что добавление одной единицы третьего ресурса обеспечит прирост прибыли на 5 единиц.
Расшивка "узких мест" производства
Таблица N 3
| C | B | H | 48 | 30 | 29 | 10 | 0 | 0 | 0 |
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | |||
| 29 | х3 | 24 | 0 | -1 /7 | 1 | 6 /7 | 2 /7 | 0 | -1 /7 |
| 0 | x6 | 4 | 0 | 13 /7 | 0 | 13 /7 | -4 /21 | 1 | -5 /21 |
| 48 | х1 | 34 | 1 | 6 /7 | 0 | -1 /7 | -1 /21 | 0 | 4 /21 |
| 2328 | 0 | 7 | 0 | 8 | 6 | 0 | 5 |
При выполнении оптимальной производственной программы первый и третий ресурсы используются полностью, тем самым они образуют "узкие места" производства. Будем их заказывать дополнительно. Пусть Т=( t1 ,t2 ,t3 ) - вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие H+Q- l Т≥0, где Н - значения базисных переменных в последней симплексной таблице, а Q-1 - обращенный базис, который образуют столбцы при балансовых переменных в этой таблице. Задача состоит в том, чтобы найти вектор Т, максимизирующий суммарный прирост прибыли W=6t1 +5 t3 при условии сохранения двойственных оценок ресурсов (и, следовательно, ассортимента выпускаемой продукции), предполагая, что можно получить дополнительно не более 1/3 первоначального объема ресурсов каждого вида.
24 2 /7 0 -1 /7 t1 0
4 + -4 /21 1 -5 /21 0 ≥ 0
34 -1 /21 0 4 /21 t3 0
t1 198
0 ≤ 1 /3 96
t3 228
t1 ≥0, t3 ≥0.
W=6t1 +5t3 -max
-2 /7 t1 + 1 /7 t3 ≤ 24
4 /21 t1 + 5 /21 t3 ≤ 4
1 /21 t1 - 4 /21 t3 ≤ 34
t1 ≤198 /3 , t3 ≤228 /3 .