–PAGE_BREAK–
yj≥ 0, i= 1,5.
Из таблицы следует, что Yопт = (0, 2/3, 1/3), S(y)min= 3.
На основании 1-й теоремы двойственности получаем
L(x)max= S(y)min= 3.
Решение другой задачи найдем по соответствию между переменными:
Основные
переменные
Балансовые
переменные
Исходная задача
Х1
Х2
Х3
Х4
Х5
двойственная
У4
У5
у1
У2
У3
Балансовые переменные
Основные переменные
Значение хjопределяем по последней симплексной таблице в строке ∆i в соответствующем столбце, причем значения хj берем по модулю:
Х1 → У4, Х1 = │∆4│= │-4│=4,
Х2 → У5, Х2 = │∆5│= │-1│=1.
Таким образом, решение исходной задачи:
Хопт= (4,1), при этом L(x)max= 3.
Если исходная задача решена симплексным методом, то решение двойственной задачи может быть найдено по формуле
Уопт = С*А ,
где С – матрица-строка коэффициентов при базисных переменных целевой функции в оптимальном решении исходной задачи; А — обратная матрица для матрицы А, являющейся матрицей коэффициентов базисных переменных системы ограничений исходной задачи в оптимальности решении.
Решим симплексным методом исходную задачу вида
L (x) = x1 — x2 → max
при ограничениях:
-2×1 + x2 + x3 = 2,
x1 — 2×2 + x4 =2,
x1 + x2 + x5 = 5,
x1≥0, j = 1,5.
Из таблицы (см. ниже) следует, что Хопт= (4,1), L(x)max= 3. матрицы записываются в виде
С = (1 -1 0)1×3, -2 1 1
А = 1 -2 0 ,
1 1 0 3×3
тогда
0 1/3 2/3
А = 0 -1/3 1/3 ,
1 1 1
0 1/3 2/3
Уопт = С*А = (1 -1 0) × 0 -1/3 1/3 = (0 2/3 1/3).
1 1 1
ci
БП
1
-1
L (x)
х1
х2
х3
х4
х5
bi
х3
-2
1
1
2
Х4
1
-2
1
2
Х5
1
1
1
5
∆j
-1
1
х3
-3
1
2
6
1
Х1
1
-2
1
2
Х5
3
-1
1
3
∆j
-1
1
2
х3
1
1
1
9
1
Х1
1
1/3
2/3
4
-1
Х2
1
-1/3
1/3
1
∆j
2/3
1/3
3
Таким образом, решение двойственной задачи следующее:
Yопт = (0, 2/3, 1/3), при этом S(y)min= 3.
Решение несимметричных задач
Рассмотрим решение задач с использованием теорем двойственности.
Исходная задача Двойственная задача
L (x) = 3×1 + x2 + 3×3 + x4 → min S(y) = 9y1 + 6y2 → mах
x1 — 2×2 + 3×3 — x4 = 9│ y1 2y1+ y2 ≤ 3 │x1
x1 + x2 — 6×3 — x4 = 6 │ y2 -2y1 + y2 ≤ 1 │x2
xj≥0, j = 1,4. 3y1— 6y2 ≤ 3 │x3
-2y1— y2 ≤ 1 │x4
y1, y2 — произвольные по знаку.
Решив двойственную задачу графическим методом, получим
Yопт = (1/2, 2), при этом S(y)max= 33/2.
По 1-й теореме двойственности L(x)min= S(y)mах= 33/2.
Подставим Yопт в систему ограничений двойственной задачи:
2*1/2 +2 ≤ 3, 3 = 3,
-2 *1/2 + 2 ≤ 1, 1 = 1,
3*1/2 – 6*2 ≤ 3, -21/2
-2*1/2 – 2 ≤ 1,-3
Так как х3= х4= 0, то система ограничений исходной задачи примет вид
2×1 — 2×2 = 9,
x1 +x2 =6.
Решая данную систему, получим
Хопт= (21/4, 3/4, 0,0), при этом L(x)min= 33/2.
Рассмотрим решение задач с использованием обратной матрицы.
Пусть решение исходной задачи
Xопт = (21/4,3/4,0,0), при этом L(x)min= 33/2.
Решение двойственной задачи найдем по формуле
Уопт = С*А ,
где
С = (3,1), А = 2 -2 , А = 1/4 1/2 ,
1 1 -1/4 1/2
Yопт = (3 1) * 1/4 1/2 = (1/2 2).
-1/4 1/2
Таким образом, Yопт = (1/2, 2), при этом S(y)mах= 33/2.
Решение смешанных двойственных задач
Смешанные двойственные задачи можно решать с использованием теорем двойственности.
Исходная задача Двойственная задача
L (x) = x1 — 6×2 — x3 → mах S(y) = 3y1 + 4y2 → min
x1 + 3×2 + 3×3 = 3│ y1 y1+ 2y2 ≥ 1 │x1
2×1 + 3×3 ≤4 │ y2 3y1 ≥ -6 │x2
xj≥0, j= 1,3. 3y1+ 3y2 ≥ -1 │x3
y1– произвольная по знаку, y2≥0.
Найдем оптимальное решение двойственной задачи:
Хопт= (1,0,2/3), при этом L(x)max= 1/3.
По 1-й теореме двойственности
L(x)max= S(y)min= 1/3.
Так как х1> 0, х3 > 0, то по 2-й теореме двойственности первое и третье ограничения двойственной задачи выполняются в виде равенств:
y1+ 2y2 = 1,
3y1 + 3y2 = -1,
Откуда y1= -5/3, y2 = 4/3, т.е. Yопт = (-5/3, 4/3).
4. Экономический анализ задач с использованием теории двойственности
Рассмотрим задачу оптимального использования ресурсов, запишем ее математическую модель
L(x)= ∑ сjxj→ mах
при ограничениях:
∑ aijxj≤ bi │y,
xj≥0, i = 1,m, j = 1,n.
Двойственная задача имеет вид
S(y) = ∑ biyi→ min
при ограничениях:
∑ aijуj≥ cj, уi≥ 0, i= 1,m.
ТЕОРЕМА 3. Значения переменных уi в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов системы ограничений исходной задачи на оптимальное значение ее целевой функции, т.е. уi= ðLi/ ðbi/
Примем ðLi ≈ ∆ Li, ðbi ≈ ∆bi, тогда ∆ Li ≈ уi* ∆bi.
Для задачи оптимального использования сырья это уравнение показывает, что при изменении i– ресурса оптимальный доход является линейной функцией его приращения, причем коэффициентом служит уi– i–я компонента оптимального решения двойственной задачи.
Если уi мало, то значительному увеличению i–го ресурса будет соответствовать небольшое увеличение оптимального дохода и ценность ресурса невелика.
Если уi= 0, то при увеличении i–го ресурса оптимальный доход остается неизменным и ценность этого ресурса равна нулю. В самом деле, сырье, запасы которого превышают потребности в нем, не представляют ценности для производства и его оценку можно принять за нуль.
Если уiвелико, то незначительному увеличению i–го ресурса будет соответствовать существенное увеличение оптимального дохода и ценность ресурса высока. Уменьшение ресурса ведет к существенному сокращению выпуска продукции.
Переменную уiсчитают некоторой характеристикой ценности i–го ресурса. В частности, при увеличении i–го ресурса на единицу оптимальный доход возрастает на уi, что позволяет рассматривать уi как «условную цену», оценку единицы i–го ресурса, объективно обусловленную оценку.
Так как уi представляет частную производную от оптимального дохода по i– му ресурсу, то уi характеризует скорость изменения оптимального дохода при изменении i–го ресурса.
С помощью уiможно определить степень влияния ограничений на значение целевой функции. Предельные значения (нижняя и верхняя границы) ограничений ресурсов, для которых остаются неизменными, определяются по формулам:
bi= min(xj/ dij) , bi= max(xj/ dij) ,
где xj– значение переменной в оптимальном решении; dij– элементы матрицы ( dij) = А, обратной к матрице базиса оптимального решения, для которой А = ( аij)m×n. продолжение
–PAGE_BREAK–