2020-01-14
229
Рассмотрим решение задач с использованием теорем двойственности.
Исходная задача Двойственная задача
L (x) = 3x1 + x2 + 3x3 + x4 → min S(y) = 9y1 + 6y2 → mах
x1 - 2x2 + 3x3 - x4 = 9 │ y1 2y1 + y2 ≤ 3 │x1
x1 + x2 - 6x3 - x4 = 6 │ y2 -2 y1 + 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 < 3 → х3 = 0,
-2*1/2 – 2 ≤ 1,-3 < 1 → х4 = 0.
Так как х3 = х4 = 0, то система ограничений исходной задачи примет вид
2x1 - 2x2 = 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 - 6x2 - x3 → mах S(y) = 3y1 + 4y2 → min
x1 + 3x2 + 3x3 = 3 │ y1 y1 + 2y2 ≥ 1 │x1
2x1 + 3x3 ≤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).
Экономический анализ задач с использованием теории двойственности
Рассмотрим задачу оптимального использования ресурсов, запишем ее математическую модель
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.
Стратегическое планирование выпуска изделий с учетом имеющихся ресурсов
Фирма выпускает три вида изделий, располагая при этом сырьем 4 типов: А, Б, В, Г соответственно в количествах 18, 16, 8 и 6 т. Нормы затрат каждого типа сырья на единицу изделия первого вида составляют соответственно 1, 2, 1, 0, второго вида – 2, 1, 1, 1 и третьего вида 1, 1, 0, 1. Прибыль от реализации единицы изделия первого вида = 3 усл. ед., второго =4 усл. ед., третьего = 2 усл. ед.
Требуется:
1) составить план производства трех видов, максимизирующих прибыль;
2) определить дефицитность сырья;
3) установить размеры максимальной прибыли при изменении сырья А на 6 т, Б – на 3 т, В – на 2 т, Г – на 2 т. Оценить раздельное влияние этих изменений и суммарное их влияние на прибыль;
4) оценить целесообразность введения в план производства фирмы нового вида изделий (четвертого), нормы затрат на единицу которого соответственно равны 1, 2, 2, 0, а прибыль составляет 15 усл. ед.
|
|
|
Решение. 1. Обозначим через Х = (х1, х2, х3) план производства изделий трех видов, тогда математическая модель задачи примет вид
L (x) = 3x1 + 4x2 + 2x3 → max
при ограничениях:
x1 + 2x2 + x3 ≤ 18,
2x1 + x2 + x3 ≤ 16,
x1 + x2 ≤ 8,
x2 + x3 ≤ 6,
xj ≥0, j = 1,3.
Решаем задачу симплексным методом, при этом последняя таблица будет иметь вид
| сi | БП | х1 | х2 | х3 | х4 | х5 | Х6 | Х7 | bi |
| 0 | х4 | 0 | 0 | 0 | 1 | 0 | -1 | -1 | 4 |
| 2 | х3 | 0 | 0 | 1 | 0 | 1/2 | -1 | ½ | 3 |
| 3 | х1 | 1 | 0 | 0 | 0 | ½ | 0 | -1/2 | 5 |
| 4 | х2 | 0 | 1 | 0 | 0 | -1/2 | 1 | ½ | 3 |
| ∆j | 0 | 0 | 0 | 0 | 1/2 | 2 | 3/2 | 33 |
Из таблицы следует
Хопт = (5,3,3,4,0,0,0), при этом L(x)max = 33 усл. ед.
Согласно теоремам двойственности
Уопт = (0,1/2,2,3/2,0,0,0), при этом S(y)min = 33 усл. ед.
2. Наиболее дефицитным является сырье типа В, для которого двойственная оценка у3 = 2. Менее дефицитным является сырье вида Б, для которого у2 = ½. Совсем не дефицитным является сырье А (у1 =0).
Для определения интервала устойчивости оценок найдем обратную матрицу для матрицы коэффициентов при базисных переменных в оптимальном решении системы ограничений. Базисными переменными в оптимальном решении являются х1, х2, х3, х4. Матрица коэффициентов при этих переменных в системе ограничений примет вид
1 2 1 1
А = (аij) = 2 1 1 0.
1 1 0 0
0 1 1 0
Тогда обратная матрица для матрицы А следующая:
0 1/2 0 -1/2
А = 0 -1/2 1 1/2.
0 1/2 -1 1/2
1 0 -1 -1
Найдем интервал устойчивости оценок по видам сырья:
∆b1 = min (xоптj / d1j) = 3 / (1/2) = 6,
∆b1 = min (xоптj / d1j) = 4 / (-1/2) = 8.
Интервал устойчивости оценок по отношению к первому ограничению:
(b1 - b1; b1 + b1) = (18 – 6; 18 + 8) = (12; 26).
Аналогично определим интервалы устойчивости оценок по отношению к ограничениям остальных видов сырья:
∆b2 = min (3/1; 4/(1/2)) = 3, ∆b2 = │3/ (-1/2) │=6,
∆b3 = min (3/(1/2); 4/(1/2)) = 6, ∆b3 = │3/ (-1) │=3,
∆b4 =5/1 = 5, ∆b4 = max│3/ (-1); 4/(-1) │=3.
Интервалы устойчивости оценок по отношению ко второму ограничению:
|
|
|
(16 – 3; 16 + 6) = (13;22),
к третьему ограничению:
(8 – 6; 8 + 3) = (2;11),
к четвертому ограничению:
(6 – 5; 6 + 3) = (1;9).
3. Изменения сырья согласно условиям задачи на +6, -3, +2, +2 т приводят к ограничению запаса сырья до 24, 13, 10, 8 т соответственно. Поскольку эти изменения находятся в пределах устойчивости оценок, на что указывают интервалы, то раздельное их влияние на прибыль определяется по формуле
Li = yоптi * bi,
тогда
L1 max = yопт1 * b1 = 0*6 = 0,
L2 max = yопт2 * b2 = 1/2*(-3) = -3/2,
L 3max = yопт3 * b3 = 2*2 = 4,
L 4max = yопт4 * b4 = 3/2*2 = 3.
Суммарное влияние на прибыль:
L max = L1 max + L2 max + L3 max + L4 max = 0 – 3/2 +4 +3 = 11/2 усл. ед.
Если изменение сырья не находится в пределах устойчивости оценок, то необходимо найти новые условные оценки, т.е. решить задачу симплексным методом с изменением количества сырья соответствующих видов.
4. Для оценки целесообразности введения в план производства фирмы четвертого вида изделий используем формулу
∆4 = ∑ aijyоптi – c4 = 1*0 + 2*1/2 +2*2 + 0*3/2 -15 = -10 < 0.
Так как прибыль превышает затраты, то введение в план производства четвертого вида изделий целесообразно.
Заключение
Двойственная задача - это вспомогательная задача линейного программирования, формулируемая с помощью определенных правил непосредственноиз условий исходной, или прямой задачи, которая применима к любой форме представления прямой задачи. В основу такого подхода положен тот факт, что использование симплекс-метода требует приведения любой ЗЛП к каноническому виду.
Правила получения двойственной задачи из задачи исходной.
1. Если в исходной задаче ищется максимум целевой функции, то в двойственной ей - минимум.
2. Коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений другой задачи.
3. В исходной ЗЛП все функциональные ограничения - неравенства вида «≤», а в задаче, двойственной ей, - неравенства вида «≥».
4. Коэффициенты при переменных в системах ограничений взаимно двойственных задач описываются матрицами, транспонированными относительно друг друга.
5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой.
6. Условие неотрицательности переменных сохраняется в обеих задачах.
Теория математического линейного программирования позволяет не только получать оптимальные планы с помощью эффективных вычислительных процедур, но и делать ряд экономически содержательных выводов, основанных на свойствах задачи, которая является двойственной по отношению к исходной ЗЛП.
