ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ
ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ МЕНЕДЖМЕНТА
Реферат
по дисциплине «Математические методы принятия управленческих решений»
на тему: «Двойственность линейного программирования»
Выполнила студентка
очной формы обучения
специальности «Менеджмент организации»
третьего курса 32 группы
Шумакова Ю. А.
Проверила
Кочетова Л.А.
Оренбург
2009
Содержание
Введение………………………………………………………………..…….3
1. Виды двойственных задач и составление их математических
моделей……………………………………………………………………….4
2. Основные теоремы двойственности……………………………………..6
3. Решение двойственных задач…………………………………………….7
4.Экономический анализ задач с использованием теории двойственности……………………………………………………………….….12
5. Стратегическое планирование выпуска изделий с учетом имеющихся ресурсов…………………………………………………………………………..14
Заключение…………………………………………………...……………..18
Библиографический список……………………………………………......19
Введение
Двойственность в линейном программировании - принцип, заключающийся в том, что для каждой задачи линейного программирования можно сформулировать двойственную задачу.
Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу линейного программирования, называемую двойственной или сопряженной по отношению к исходной или прямой. Связь исходной и двойственной задач заключается главным образом в том, что решение одной из них может быть получено непосредственно из решения другой.
Теория математического линейного программирования позволяет не только получать оптимальные планы с помощью эффективных вычислительных процедур, но и делать ряд экономически содержательных выводов, основанных на свойствах задачи, которая является двойственной по отношению к исходной ЗЛП.
Произвольную задачу линейного программирования можно определенным образом сопоставить с другой задачей линейного программирования, называемой двойственной. Первоначальная задача является исходной. Эти две задачи тесно связаны между собой и образуют единую двойственную пару.
Различают симметричные, несимметричные и смешанные двойственные задачи.
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 ,
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
при ограничениях: при ограничениях:
-2x1 + x2 ≤ 2│ y1 -2y1 + y2 + y3 ≥ 1 │x1
x1 - 2x2 ≤ 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 - 2x2 = 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
при ограничениях:
-2x1 + x2 + x3 = 2,
x1 - 2x2 + x4 =2,