Исходная задача Двойственная задача

1 2 3

Реферат

по дисциплине «Математические методы принятия управленческих решений»

на тему: «Двойственность линейного программирования»

Выполнила студентка

очной формы обучения

специальности «Менеджмент организации»

третьего курса 32 группы

Шумакова Ю. А.

Проверила

Кочетова Л.А.

Оренбург

2009

Содержание

Введение………………………………………………………………..…….3

1. Виды двойственных задач и составление их математических

моделей……………………………………………………………………….4

2. Основные теоремы двойственности……………………………………..6

3. Решение двойственных задач…………………………………………….7

4.Экономический анализ задач с использованием теории двойственности……………………………………………………………….….12

5. Стратегическое планирование выпуска изделий с учетом имеющихся ресурсов…………………………………………………………………………..14

Заключение…………………………………………………...……………..18

Библиографический список……………………………………………......19

Введение

Двойственность в линейном программировании - принцип, заключающийся в том, что для каждой задачи линейного программирования можно сформулировать двойственную задачу.

Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу линейного программирования, называемую двойственной или сопряженной по отношению к исходной или прямой. Связь исходной и двойственной задач заключается главным образом в том, что решение одной из них может быть получено непосредственно из решения другой.

Теория математического линейного программирования позволяет не только получать оптимальные планы с помощью эффективных вычислительных процедур, но и делать ряд экономически содержательных выводов, основанных на свойствах задачи, которая является двойственной по отношению к исходной ЗЛП.

Произвольную задачу линейного программирования можно определенным образом сопоставить с другой задачей линейного программирования, называемой двойственной. Первоначальная задача является исходной. Эти две задачи тесно связаны между собой и образуют единую двойственную пару.

Различают симметричные, несимметричные и смешанные двойственные задачи.

Виды двойственных задач и составление их математических моделей

Симметричные двойственные задачи

Дана исходная задача

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.

Смешанные двойственные задачи

Математическая модель исходной задачи имеет условия симметричных и несимметричных задач. При составлении двойственной задачи необходимо выполнять правила симметричных и несимметричных задач.

Основные теоремы двойственности

ТЕОРЕМА 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.

Теоремы позволяют определить оптимальное решение одной из пары задач по решению другой.

Решение двойственных задач

Решение симметричных задач

Рассмотрим решение задач с использованием теорем двойственности.

Исходная задача Двойственная задача

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,

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)
ci	БП	х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