Двойственность в линейном программировании — это принцип, согласно которому двойная задача может быть сформулирована для любой задачи линейного программирования.
Каждая задача линейного программирования может быть определенным образом связана с некоторой другой задачей линейного программирования, называемой двойственной или сопряженной по отношению к исходной или прямой. Связь между исходной проблемой и двойственной проблемой заключается главным образом в том, что решение одной из них может быть получено непосредственно из решения другой.
Теория математического линейного программирования позволяет не только получать оптимальные планы с помощью эффективных вычислительных процедур, но и делать ряд экономически содержательных выводов, основанных на свойствах задачи, которая является двойственной по отношению к исходной ЗЛП.
двойственной
Различают симметричные, асимметричные и смешанные двойственные задачи.
1. Виды двойственных задач и составление их математических моделей
Симметричные двойственные задачи
Дана исходная задача
L (x) = c1x1 + c2x2 +…+ cnxn → max
при ограничениях:
a11x1 + a12x2 + … + a1nxn ≤ b1 │ y1 ,
a21x1 + a22x2 + … + a2nxn ≤ b2 │ y2 ,
………………………………………
am1x1 + am2x2 + … + amnxn ≤ bm │ ym ,
xj≥0 , j = 1,n , i = 1,m.
Задача дана в неканоническом виде. Составим математическую модель двойственной задачи, для этого:
- каждому неравенству системы ограничений исходной задачи приводим в соответствие переменную yi ;
- составляем целевую функцию, коэффициентами которой являются свободные члены системы ограничений исходной задачи;
- составляем систему ограничений. Коэффициенты системы ограничений образуют транспонированную матрицу коэффициентов системы ограничений исходной задачи. Знаки неравенств меняются на противоположные;
- свободными членами системы ограничений являются коэффициенты целевой функции исходной задачи. Все переменные двойственной задачи неотрицательны.
Математическая модель двойственной задачи имеет вид
S(y) = b1y1 + b2y2 +…+ bmym → min
при ограничениях:
a11y1 + a12y2 + … + am1ym ≤ c1 ,
Применение линейного программирования для решения экономических ...
... анализ применения линейного программирования для решения экономических задач. Задачами курсовой работы являются: 1. Теоретико-методическое описание метода линейного программирования; 2. Выявление области применения и ограничения использования линейного программирования для решения экономических задач; 3. Оптимизация прибыли с применением метода линейного программирования; 4. Постановка задачи и ...
a12y1 + a21y2 + … + am2ym ≤ c2 ,
………………………………………
a1ny1 + a2ny2 + … + amnym ≤ cn ,
yj ≥0 , i = 1,m , j = 1,n.
Несимметричные двойственные задачи
Дана исходная задача
L (x) = c1x1 + c2x2 +…+ cnxn → max
при ограничениях:
a11x1 + a12x2 + … + a1nxn = b1 │ y1 ,
a21x1 + a22x2 + … + a2nxn = b2 │ y2 ,
………………………………………
am1x1 + am2x2 + … + amnxn = bm │ ym ,
xj ≥0 , j = 1,n.
Задача дана в каноническом виде. Составим математическую модель двойственной задачи.
Для ее составления пользуемся тем же правилом, что и для составления симметричной задачи, с учетом следующих особенностей:
- ограничениями двойственной задачи будут неравенства. Если в целевой функции двойственной задачи требуется найти минимум, то знак неравенства ≥, если максимум, то ≤ ;
- переменные yi — произвольные по знаку.
Математическая модель двойственной задачи имеет вид
S(y) = b1y1 + b2y2 +…+ bmym → min
при ограничениях:
a11y1 + a21y2 + … + am1ym ≥ c1 ,
a12y1 + a22y2 + … + am2ym ≥ c2 ,
………………………………………
a1ny1 + a2ny2 + … + amnxn ≥ cn ,
yj ≥0 , i = 1,m , j = 1,n.
yi – произвольные по знаку, i = 1,m.
Смешанные двойственные задачи
Математическая модель исходной задачи имеет условия для симметричных и асимметричных задач. При составлении двойственной задачи необходимо соблюдать правила симметричной и асимметричной задач.
2. Основные теоремы двойственности
ТЕОРЕМА 1. Если одна из двойственных задач имеет оптимальное решение, то другая также имеет оптимальное решение, причем для любых оптимальных решений X и Y выполняется равенство
L(x)max = S(y)min.
Если одна из двойственных задач неразрешима ввиду того, что
L(x)max→ ∞ (или S(y)min→ — ∞), то другая задача не имеет допустимых решений.
ТЕОРЕМА 2. Для оптимальности допустимых решений X и Y пары двойственных задач необходимо и достаточно, чтобы они удовлетворяли системе уравнений
Xопт j( ∑aijyопт i — cj ) = 0,
yопт i ( ∑aijxоптj — bi ) = 0.
Теоремы позволяют определить оптимальное решение одной из двух задач для решения другой.
3. Решение двойственных задач
Решение симметричных задач
Рассмотрим решение задач с использованием теорем двойственности.
Исходная задача Двойственная задача
L (x) = x1 — x2 → max S(y) = 2y1 + 2y2 + 5y3 → min
при ограничениях: при ограничениях:
- 2×1 + x2 ≤ 2│ y1 -2y1 + y2 + y3 ≥ 1 │x1
x1 — 2×2 ≤ 2 │ y2 y1 – 2y2 + y3 ≥ -1 │x2
x1 + x2 ≤ 5 │ y3 yi ≥0, I = 1,3.
x1 ≥0 , x2 ≥0.
Решим исходную задачу графическим методом, получим Хопт = (4,1), при этом L(x)max = 3.
На основании 1-й теоремы двойственности
L(x)max = S(y)min = 3.
Так как x1, x2 > 0, то по 2-й теореме двойственности систему ограничений можно записать в виде равенств:
- 2y1 + y2 + y3 = 1,
y1 – 2y2 + y3 = -1.
Подставим Хопт в систему ограничений исходной задачи:
- 2*4 + 1 ≤ 2, 9 <
- 2 ═>
- у1 = 0,
4 – 2*1 ≤ 2, 2 = 2 ═> у2 > 0,
4 + 1 ≤ 5, 5 = 5 ═> у3 > 0.
Тогда система ограничений двойственной задачи примет вид
y2 + y3 = 1,
- 2y2 + y3 = -1.
Откуда Yопт = (0, 2/3, 1/3), при этом S(y)min = 3.
Пусть дано решение двойственной задачи Yопт = (0, 2/3, 1/3), S(y)min= 3, найдем решение исходной.
По 1-й теореме двойственности L(x)max = S(y)min = 3. Так как y2 , y3 > 0, то по 2-й теореме двойственности второе и третье неравенства исходной задачи обращаются в равенства:
x1 — 2×2 = 2 ,
x1 + x2 = 5.
Откуда Хопт = (4,1), при этом L(x)max = 3.
Рассмотрим решение задач методом, основанным на взаимно однозначном соответствии между переменными: основные переменные исходной задачи соответствуют равновесным переменным двойственной, и наоборот. Для этого решим двойственную задачу симплексным методом:
S(y) = 2y1 + 2y2 + 5y3 → mах
При ограничениях:
- 2y1 + y2 + y3 – у4 = 1,
y1 – 2y2 + y3 – у5 = 1,
| bi | БП | У1 | У2 | У3 | У4 | У5 | cj |
| -2 | 1 | 1 | -1 | 0 | 1 | ||
| У5 | 1 | 2 | -1 | 0 | 1 | 1 | |
| 5 | У3 | -2 | 1 | 1 | -1 | 0 | 1 |
| 0 | У5 | -3 | 3 | 0 | -1 | 1 | 2 |
| ∆j | -12 | 3 | 0 | -5 | 0 | 5 | |
| 5 | У3 | -1 | 0 | 1 | -2/3 | -1/3 | 1/3 |
| 2 | У2 | -1 | 1 | 0 | -1/3 | 1/3 | 2/3 |
| ∆j | 9 | 0 | 0 | -4 | -1 | 3 |
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 | 0 | 0 | 0 | L (x) |
| х1 | х2 | х3 | х4 | х5 | bi | ||
| 0 | х3 | -2 | 1 | 1 | 0 | 0 | 2 |
| 0 | Х4 | 1 | -2 | 0 | 1 | 0 | 2 |
| 0 | Х5 | 1 | 1 | 0 | 0 | 1 | 5 |
| ∆j | -1 | 1 | 0 | 0 | 0 | 0 | |
| 0 | х3 | 0 | -3 | 1 | 2 | 0 | 6 |
| 1 | Х1 | 1 | -2 | 0 | 1 | 0 | 2 |
| 0 | Х5 | 0 | 3 | 0 | -1 | 1 | 3 |
| ∆j | 0 | -1 | 0 | 1 | 0 | 2 | |
| 0 | х3 | 0 | 0 | 1 | 1 | 1 | 9 |
| 1 | Х1 | 1 | 0 | 0 | 1/3 | 2/3 | 4 |
| -1 | Х2 | 0 | 1 | 0 | -1/3 | 1/3 | 1 |
| ∆j | 0 | 0 | 0 | 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 < 3 → х3 = 0,
- 2*1/2 – 2 ≤ 1,-3 < 1 → х4 = 0.
Так как х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-го ресурса.
Используя yi, можно определить степень влияния ограничений на значение целевой функции. Предельные значения (нижняя и верхняя границы) ограничений ресурсов, для которых остаются неизменными, определяются по формулам:
bi = min (xj / dij ) , bi = max (xj / dij ) ,
где xj – значение переменной в оптимальном решении; dij– элементы матрицы ( dij ) = А , обратной к матрице базиса оптимального решения, для которой А = ( аij )m×n .
5. Стратегическое планирование выпуска изделий с учетом имеющихся ресурсов
Фирма выпускает три вида изделий, располагая при этом сырьем 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) = 3×1 + 4×2 + 2×3 → max
при ограничениях:
x1 + 2×2 + x3 ≤ 18,
2×1 + 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,
L3max = 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.
Поскольку прибыль превышает затраты, имеет смысл ввести в производственный план четвертый вид продукции.
Заключение
Двойственная задача — это вспомогательная задача линейного программирования, сформулированная с использованием определенных правил непосредственно из условий исходной задачи или прямой задачи, применимая к любой форме представления прямой задачи. Этот подход основан на том, что использование симплекс-метода требует приведения любой LPP к каноническому виду.
Правила получения двойственной задачи из задачи исходной.
1. Если в исходной задаче искать максимум целевой функции, то в двойственной — минимум.
2. Коэффициенты переменных в целевой функции одной задачи являются свободными членами системы ограничений другой задачи.
3. В исходной ЗЛП все функциональные ограничения — неравенства вида «≤», а в задаче, двойственной ей, — неравенства вида «≥».
4. Коэффициенты переменных в системах ограничений для взаимно двойственных задач описываются матрицами, транспонированными друг относительно друга.
5. Количество неравенств в системе ограничений одной задачи совпадает с количеством переменных в другой.
6. Условие неотрицательности переменных сохраняется в обеих задачах.
Теория математического линейного программирования позволяет не только получать оптимальные планы с помощью эффективных вычислительных процедур, но и делать ряд экономически содержательных выводов, основанных на свойствах задачи, которая является двойственной по отношению к исходной ЗЛП.
Библиографический список
1. Белолипецкий В. М. Математическое моделирование в задачах. / В.М. Белолипецкий, Ю.И. Шокин. – М. : Финансы и статистика, 2002.- 774 с.
2. Красс М. С. Основы математики и ее приложения в экономическом образовании: учебник. — 5-е изд., испр. и доп. / М.С. Красс, Б.П. Чупрынов. – М. : Дело, 2006. – 720 с.
3. Солодовников А. С. Математика в экономике. / А.С. Солодовников, В.А. Бабайцев, А.В. Браилов. – М. : Изд–во МГУ, 1999. – 591 с.
4. Черемных Ю. Н. Математические методы в экономике. 2 — изд. / Ю.Н. Черемных. – М. : Дело и сервис, 2001. – 657 с.
5. http://lib.mexmat.ru
6. http://slovari.yandex.ru
