Найти оптимальный план прямой задачи графическим методом.
2. Построить двойственную задачу.
3. Найти оптимальный план двойственной задачи из графического решения прямой, используя условия дополняющей нежесткости.
4. Найти оптимальный план прямой задачи с применением функции поиска решения в Excel.
5. Найти оптимальный план двойственной задачи по первой теореме двойственности, используя отчет по устойчивости поиска решения, полученную при решении прямой задачи (см. п. 4). Проверить утверждение «значения целевых функций пары двойственных задач на своих оптимальных решениях совпадают».
6. Дать интерпретацию изменения решения (по отчету на устойчивость) при условии изменения коэффициентов целевой функции на 3% и 2,5% соответственно. Показать изменения оптимального плана при изменении правой части первого из ограничений задачи в системе уравнений на 6%. Сравнить результаты с результатом, полученный графическим методом (см. п.1).
Решение:
1. Найдем оптимальный план прямой задачи графическим методом:
Рис. 1. Графическое решение ЗЛП
Линия уровня касается в крайнем положение области допустимых решений в точке В:
26917656286500-x1+19×2=23
4×1+2×2=10
Откуда:
x1 = 111/13, x2 = 14/13
Fmin = 12*111/13 + 9*14/13 = 3312/13
2. Построим двойственную задачу:
Прямая задача
Двойственная задача
4711704889500F=12×1 + 9×2 → min
2393954889500Z=23y1 + 10y2 – 22y3 – 45y4 → max
– x1 + 19×2≥23
y1 ≥ 0
4×1 + 2×2≥10 ↔ y2 ≥ 0
6×1 – 5×2≥-22
y3 ≥ 0
– 8×1 + 7×2≥-45
y4 ≥ 0
x1 ≥ 0
– y1 + 4y2 + 6y3 – 8y4≤12
x2 ≥ 0
19y1 + 2y2 – 5y3 + 7y4≤9
3. Найдем оптимальный план двойственной задачи из графического решения прямой, используя условия дополняющей нежесткости.
19481802095500×1(- y1 + 4y2 + 6y3 – 8y4-12)=0
x2(19y1 + 2y2 – 5y3 + 7y4-9)=0
y1(- x1 + 19×2-23)=0
y2(4×1 + 2×2-10)=0
y3(6×1 – 5×2+22)=0
y4(- 8×1 + 7×2+45)=0
Подставляем решение прямой задачи:
19481802095500111/13 (- y1 + 4y2 + 6y3 – 8y4-12)=0
14/13 (19y1 + 2y2 – 5y3 + 7y4-9)=0
y1(-111/13+ 19*14/13-23)=0
y2(4*111/13 + 2*14/13-10)=0
y3(6*111/13 – 5*14/13+22)=0
y4(- 8*111/13 + 7*14/13+45)=0
Получим:
21475702095500(- y1 + 4y2 + 6y3 – 8y4=12
19y1 + 2y2 – 5y3 + 7y4=9
y3=0
y4=0
Тогда решение двойственной задачи:
y1 = 2/13
y2 = 31/26
y3 = 0
y4 = 0
Z(Y) = 23*2/13+10*31/26+22*0+45*0 = 3312/13
4. Найдем оптимальный план прямой задачи с применением функции поиска решения в Excel.
Оформляем исходные данные:
В режиме формул:
Используем поиск решений:
Результаты решения:
5. Найдем оптимальный план двойственной задачи по первой теореме двойственности, используя отчет по устойчивости поиска решения, полученный при решении прямой задачи.
Ячейки переменных
Окончательное Приведенн. Целевая функция Допустимое Допустимое
Ячейка Имя Значение Стоимость Коэффициент Увеличение Уменьшение
$D$7 X1 1,85 0 12 6 12,47
$E$7 X2 1,31 0 9 1E+30 3
Ограничения
Окончательное Тень Ограничение Допустимое Допустимое
Ячейка Имя Значение Цена Правая сторона Увеличение Уменьшение
$F$2 23,00 0,15 23 64,69 25,50
$F$3 10,00 3,04 10 21,19 7,58
$F$4 -4,54 0,00 22 1E+30 26,54
$F$5 5,62 0,00 45 1E+30 39,38
y1 = 0.12
y2 = 3.04
y3 = 0
y4 = 0
Проверим утверждение «значения целевых функций пары двойственных задач на своих оптимальных решениях совпадают»:
Z(Y) = 23*0.12+10*3.04+22*0+45*0 = 33.92
Z(Y) =F(X)
6. Дадим интерпретацию изменения решения (по отчету на устойчивость) при условии изменения коэффициентов целевой функции на 3% и 2,5% соответственно:
∆b1=0.03*23= 0,69
∆b2=0.025*10= 0,25
Изменения лежат в интервале устойчивости, поэтому целевая функция оптимального решения изменится:
∆F=y1*∆b1+y2*∆b2=0.12*0.69+3.04*0.25=0,87
И составит:
F=33,92+0.87=34,79
Покажем изменения оптимального плана при изменении правой части первого из ограничений задачи в системе уравнений на 6%.
∆С1=0.06*12= 0,72
Изменения лежат в интервале устойчивости, поэтому целевая функция оптимального решения изменится:
∆F=x1*∆C1= 1,846*0.72= 1,33
И составит:
F=33,92+ 1,33= 35,25
Значения двойственных оценок и целевой функции совпадают с результатом, полученным графическим методом (см. п.1).
1.3. Задачи межотраслевого баланса
