Двойственность в линейном программировании реферат

Обновлено: 02.07.2024

Двойственность в линейном программировании ( реферат , курсовая , диплом , контрольная )

Двойственность в линейном программировании

1. Двойственные задачи линейного программирования

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

Рассмотрим стандартную задачу ЛП с n переменными и m ограничениями в форме неравенств

Двойственной к ней называется задача ЛП следующего вида:

Выписывая матрицы условий для прямой и двойственной задачи

Следовательно, пара двойственных задач может быть записана в матричной форме:

Прямая задача ЛП

Двойственная задача ЛП

2. Симметричная пара двойственных задач

Пара двойственных задач, в которых прямая задача — стандартная, называется симметричной парой двойственных задач.

Правила построения двойственной задачи к стандар т ной задаче ЛП.

· Число переменных двойственной задачи равно числу основных ограничений прямой задачи и наоборот.

· Если прямая задача есть задача на max при ограничениях ««, то двойственная задача — задача на min при ограничениях ««.

· Правые части ограничений прямой задачи — числа b_i — становятся коэффициентами целевой функции двойственной задачи.

· Коэффициенты целевой функции прямой задачи — числа c_j — становятся правыми частями ограничений двойственной задачи ЛП.

· j — й столбец матрицы условий прямой задачи превращается в j — ю строку матрицы условий двойственной задачи.

· Переменные прямой и двойственной задачи неотрицательны.

Пример. Рассмотрим стандартную задачу ЛП с двумя переменными, тремя ограничениями в форме неравенств и условиями неотрицательности.

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

Покажем, что двойственная к двойственной задаче ЛП совпадает с прямой задачей ЛП, для чего воспользуемся предыдущим примером.

Сначала приведем двойственную задачу к стандартному виду

Построим к ней двойственную задачу по правилам 1−6, обозначая двойственные переменные через x_1, x_2.

Чтобы получить исходную задачу, достаточно умножить коэффициенты целевой функции и все ограничения на (-1).

Из вышесказанного следует, что если прямая задача имеет вид:

то двойственной к ней будет задача

3. Экономический смысл двойственной задачи

Рассмотрим следующую производственную задачу.

Предприятие после выпуска основной продукции имеет излишки ресурсов двух типов: R₁ — 10 единиц, R₂ — 8 единиц. Существует два способа распорядиться этими ресурсами:

· организовать из них выпуск 3 новых видов продукции: P₁, P₂, P₃.

Рассмотрим оба способа.

Исходные данные приведены в таблице:

Расход ресурса на единицу продукции

Согласно первому способу, надо составить такой план выпуска продукции, который максимизирует суммарную прибыль. Построим математическую модель этой задачи.

Пусть x_j — план выпуска продукции P_j.

Тогда целевая функция будет выглядеть следующим образом:

Ограничения по ресурсам:

Получили стандартную задачу ЛП.

Рассмотрим второй способ использования ресурсов, а именно, их продажу.

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

В свою очередь покупатель заинтересован в приобретении ресурсов по таким ценам, при которых затраты на покупку будут минимальны.

Задача согласования цен на ресурсы, устраивающих обе стороны может быть описана следующей математической моделью.

Пусть y₁ — цена одной единицы ресурса R_1, y₂ — цена одной единицы ресурса R_2.

Интерес покупателя будет выражаться целевой функцией, равной суммарной стоимости приобретаемых ресурсов

Интерес продавца будет описываться ограничениями:

в которых левая часть означает стоимость ресурсов, затраченных на выпуск единицы соответствующей продукции, а правая — удельную прибыль от ее реализации.

Присоединяя естественные условия неотрицательности цен:

получаем двойственную задачу ЛП.

Таким образом, симметричной паре двойственных задач можно придать определенный экономический смысл.

Прямая задача

Определить такой план выпуска продукции x =(x₁, x₂,…, x_n), используя ограниченные запасы ресурсов, при котором прибыль от реализации продукции будет максимальной.

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

Установить такой набор цен ресурсов y =(y₁, y₂,…, y_m), при которых стоимость ресурсов, затраченных на выпуск единицы продукции будет не ниже прибыли от ее реализации, но при этом суммарная стоимость затрат будет минимальна.

4. Несимметричная пара двойственных задач

Пусть теперь исходная задача — каноническая, то есть имеет вид:

Для построения двойственной задачи к задаче (4.1) — (4.3) сведем ее к стандартной форме.

Каждое равенство в (4.2) заменим парой неравенств

или, что-то же самое

Получим стандартную задачу ЛП с 2m ограничениями.

Построим к ней двойственную задачу ЛП по известным правилам.

Для этого введем двойственные переменные:

Заметим, что, так как в прямой задаче ЛП было 2m ограничений, то в двойственной будет 2m переменных.

Целевая функция двойственной задачи примет вид:

а ограничения запишутся так:

Перепишем эту задачу более компактно:

Введем новый вектор двойственных переменных y = (y_1, y_2,…, y_m₎ с координатами y_i = u_i — v_i. Поскольку разность неотрицательных чисел может быть и отрицательной (например, 2−5= -3), то двойственные переменные y_i не имеют ограничений по знаку.

Таким образом, двойственная задача к канонической будет иметь вид:

y — переменная любого знака !

5. Таблицы для построения двойственной задачи

Для любой задачи ЛП можно построить двойственную. Для этого нужно свести её к стандартному или каноническому виду. Можно также воспользоваться таблицами, приведенными ниже.

Прямая задача линейного программирования

Двойственная задача линейного программирования

Тип i-го ограничения

Знак i-й переменной

y_i — любого знака

Знак j-ой переменной

Тип j-го ограничения

x_j? свободная переменная

Прямая задача линейного Программирования

Двойственная задача линейного программирования

Тип i-го ограничения

Знак i-ой переменной

y_i — любого знака

Знак j-ой переменной

Тип j-го ограничения

x_j? свободная переменная

Задание . Составить двойственные задачи к следующим задачам ЛП.

6. Связь между планами двойственных задач

Рассмотрим симметричную пару двойственных задач:

7. Первая теорема двойственности

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

Теорема 1. Если одна из пары двойственных задач имеет оптимальный план, то и другая имеет оптимальный план, причем значения целевых функций на этих планах равны

f (x * ) = g (x * ) или * > = * >.

Если же целевая функция одной из пары двойственных задач не ограничена на своём множестве планов (прямая — сверху, двойственная — снизу), то множество планов другой задачи пусто.

Из первой части теоремы, которую мы приводим без доказательства, следует, что равенство (4.14) является не только достаточным, но и необходимым условием оптимальности планов пары двойственных задач.

Утверждение второй части теоремы легко доказывается от противного. Предположим, что в прямой задаче (4.4) — (4.6) целевая функция не ограничена сверху на множестве X, то есть max f (x) Ґ—, xО X, но множество планов Y двойственной задачи не пусто — существует хотя бы одна точка yО Y. Тогда в силу основного неравенства теории двойственности: max f (x) —g (y), что противоречит неограниченности целевой функции прямой задачи. Таким образом, неограниченность сверху целевой функции исходной задачи влечет за собой несовместность ограничений двойственной задачи. Аналогично доказывается, что из неограниченности снизу двойственной целевой функции g (y) на множестве Y, следует пустота множества планов X прямой задачи.

Интересно, что обратное утверждение не верно. Из пустоты множества планов одной задачи еще не следует неограниченность целевой функции в двойственной к ней задаче. (Оба множества могут быть пусты).

Первая теорема двойственности позволяет исследовать любой заданный план на оптимальность.

8. Вторая теорема двойственности

Теорема 2. Планы x * = (x₁ * ,…, x_n * ) и y * = (y₁ * ,…, y_m * ) — оптимальны (каждый в своей задаче), тогда и только тогда, когда выполняются условия:

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

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

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

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

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

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 ,

Задача дана в каноническом виде. Составим математическую модель двойственной задачи.

Для ее составления пользуемся тем же правилом, что и для составления симметричной задачи, с учетом следующих особенностей:

- ограничениями двойственной задачи будут неравенства. Если в целевой функции двойственной задачи требуется найти минимум, то знак неравенства ≥, если максимум, то ≤ ;

- переменные 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→ - ∞), то другая задача не имеет допустимых решений.

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

Решим исходную задачу графическим методом, получим Хопт = (4,1), при этом L(x)max = 3.

На основании 1-й теоремы двойственности

L(x)max = S(y)min = 3.

Так как x1, x2 > 0, то по 2-й теореме двойственности систему ограничений можно записать в виде равенств:

Подставим Хопт в систему ограничений исходной задачи:

-2*4 + 1 ≤ 2, 9 у1 = 0,

4 – 2*1 ≤ 2, 2 = 2 ═> у2 > 0,

4 + 1 ≤ 5, 5 = 5 ═> у3 > 0.

Тогда система ограничений двойственной задачи примет вид

Откуда 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-й теореме двойственности второе и третье неравенства исходной задачи обращаются в равенства:

Откуда Хопт = (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

Из таблицы следует, что Yопт = (0, 2/3, 1/3), S(y)min = 3.

На основании 1-й теоремы двойственности получаем

L(x)max = S(y)min = 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

Из таблицы (см. ниже) следует, что Хопт = (4,1), L(x)max = 3. матрицы записываются в виде

С = (1 -1 0)1×3 , -2 1 1

Уопт = С*А = (1 -1 0) × 0 -1/3 1/3 = (0 2/3 1/3).

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

Таким образом, решение двойственной задачи следующее:

Yопт = (0, 2/3, 1/3), при этом S(y)min= 3.

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

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

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

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 -2y1 + y2 ≤ 1 │x2

xj ≥0 , j = 1,4. 3y1 - 6y2 ≤ 3 │x3

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 ≤ 1, 1 = 1,

3*1/2 – 6*2 ≤ 3, -21/2 0, х3 > 0, то по 2-й теореме двойственности первое и третье ограничения двойственной задачи выполняются в виде равенств:

Откуда y1 = -5/3, y2 = 4/3, т.е. Yопт = (-5/3, 4/3).

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

Рассмотрим задачу оптимального использования ресурсов, запишем ее математическую модель

xj ≥0, i = 1,m, j = 1,n.

Двойственная задача имеет вид

∑ 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 можно определить степень влияния ограничений на значение целевой функции. Предельные значения (нижняя и верхняя границы) ограничений ресурсов, для которых остаются неизменными, определяются по формулам:

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) = 3x1 + 4x2 + 2x3 → max

x1 + 2x2 + x3 ≤ 18,

2x1 + x2 + x3 ≤ 16 ,

Решаем задачу симплексным методом, при этом последняя таблица будет иметь вид

с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. Матрица коэффициентов при этих переменных в системе ограничений примет вид

А = (аij) = 2 1 1 0 .

Тогда обратная матрица для матрицы А следующая:

Найдем интервал устойчивости оценок по видам сырья:

∆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),

к третьему ограничению:

к четвертому ограничению:

3. Изменения сырья согласно условиям задачи на +6, -3, +2, +2 т приводят к ограничению запаса сырья до 24, 13, 10, 8 т соответственно. Поскольку эти изменения находятся в пределах устойчивости оценок, на что указывают интервалы, то раздельное их влияние на прибыль определяется по формуле

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. Для оценки целесообразности введения в план производства фирмы четвертого вида изделий используем формулу

Файлы: 1 файл

Двойственность в линейном программировании.doc

Двойственность в линейном программировании

Пусть в качестве исходной дана задача:

Задача линейного программирования, двойственная задаче (2.4), будет иметь вид:

Можно сформулировать правила получения двойственной задачи из задачи исходной.

1. Если в исходной задаче ищется максимум целевой функции, то в двойственной ей - минимум.

2. Коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений другой задачи.

3. В исходной ЗЛП все функциональные ограничения - неравенства вида “≤”, а в задаче, двойственной ей, - неравенства вида “≥”.

4. Коэффициенты при переменных в системах ограниче ний взаимно двойственных задач описываются матрицами, транспонированными относительно друг друга.

5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой.

6. Условие неотрицательности переменных сохраняется в обеих задачах.

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

Теорема 1. Если одна из двойственных задач имеет конечный оптимум, то другая также имеет конечный оптимум, причем экстремальные значения целевых функций совпадают:

Если целевая функция одной из двойственных задач не ограничена, то условия другой задачи противоречивы.

Теорема 2 (о дополняющей нежесткости). Для того чтобы план и план являлись оптимальными решениями, соответственно, задач (2.5) и (2.6) необходимо и достаточно, чтобы выполнялись следующие соотношения:

Таким образом, если компонент оптимального плана больше нуля, то при подстановке в соответствующее ограничение двойственной задачи оптимального плана это ограничение обращается в верное равенство, и наоборот.

Теорема об оценках. Значения переменных в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов b_i в системе ограничений прямой задачи на величину целевой функции :

На свойствах двойственных оценок базируется экономико-математический анализ распределения ресурсов. В пределах устойчивости двойственных оценок имеют место свойства, рассмотренные ниже.

При описании свойств двойственных оценок будем пользоваться задачей о хоккейных клюшках и шахматных наборах для наглядной иллюстрации рассматриваемых положений. Компания специализируется на выпуске хоккейных клюшек и наборов шахмат. Каждая клюшка приносит компании прибыль в размере $2, а каждый шахматный набор - в размере $4. На изготовление одной клюшки требуется четыре часа работы на участке A и два часа работы на участке B. Шахматный набор изготавливается с затратами шести часов на участке A, шести часов на участке B и одного часа на участке C. Доступная производственная мощность участка A составляет 120 н-часов в день, участка В - 72 н-часа и участка С - 10 н-часов.

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

Условия задач указанного класса часто представляют в табличной форме (см. таблицу 2.1).

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

Рассмотрим задачу о планируемом выпуске продукции.

Содержательная постановка прямой задачи: составить такой план выпуска продукции X = (х₁,х₂ . х_n), при котором прибыль (выручка) от реализации продукции будет максимальной при условии, что потребление ресурсов по каждому виду продукции не превзойдет имеющихся запасов.

Общие правила составления двойственной задачи:

Прямая	Двойственная
Целевая функция (max)	Правая часть ограничений
Правая часть ограничений	Целевая функция (min)
A - матрица ограничений	A T – матрица ограничений
i -ое ограничение: ≤ 0, (≥ 0)	Переменная y_i ≥ 0, (≤ 0)
i -ое ограничение: = 0	Переменная y_i≠ 0
Переменная x_j ≥ 0 (≤ 0)	j -ое ограничение: ≤ 0 (≥ 0)
Переменная x_j ≠ 0	j -ое ограничение: = 0

max → min

Прямая	Двойственная
Целевая функция (min)	Правая часть ограничений
Правая часть ограничений	Целевая функция (max)
A - матрица ограничений	A T – матрица ограничений
i -ое ограничение: ≥ 0, (≤ 0)	Переменная y_i ≥ 0, (≤ 0)
i -ое ограничение: = 0	Переменная y_i≠ 0
Переменная x_j ≥ 0 (≤ 0)	j -ое ограничение: ≤ 0 (≥ 0)
Переменная x_j ≠ 0	j -ое ограничение: = 0

Количество переменных в двойственной задаче равно количеству неравенств в исходной.
Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной.
Столбец свободных членов исходной задачи является строкой коэффициентов для целевой функции двойственной. Целевая функция в одной задаче максимизируется, в другой минимизируется.
Условиям неотрицательности переменных исходной задачи соответствуют неравенства-ограничения двойственной, направленные в другую сторону. И наоборот, неравенствам-ограничениям в исходной соответствуют условия неотрицательности в двойственной.

Заметим, что строки матрицы задачи I являются столбцами матрицы задачи II. Поэтому коэффициенты при переменных y_i в задаче II - это, соответственно, коэффициенты i -го неравенства в задаче I.
Полученная модель и есть экономико-математическая модель задачи, двойственной к прямой задаче.

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

Двойственность является фундаментальным понятием в теории линейного программирования. Основные результаты теории двойственности заключены в двух теоремах, называемых теоремами двойственности.

Первая теорема двойственности .

Если одна из пары двойственных задач I и II разрешима, то разрешима и другая, причем значения целевых функций на оптимальных планах совпадают, F(x*) = G(y*), где х *, у * - оптимальные решения задач I и II

Вторая теорема двойственности .

Планы х * и у * оптимальны в задачах I и II тогда и только тогда, когда при подстановке их в систему ограничений задач I и II соответственно хотя бы одно из любой пары сопряженных неравенств обращается в равенство.
Это основная теорема двойственности. Другими словами, если х * и у * - допустимые решения прямой и двойственной задач и если c T x*=b T y*, то х * и у * – оптимальные решения пары двойственных задач.

Третья теорема двойственности . Значения переменных y_i в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов b_i системы ограничений - неравенств прямой задачи на величину целевой функции этой задачи:
Δf(x) = b_iy_i

Решая ЗЛП симплексным методом, мы одновременно решаем двойственную ЗЛП. Значения переменных двойственной задачи y_i, в оптимальном плане называют объективно обусловленными, или двойственными оценками. В прикладных задачах двойственные оценки y_i часто называются скрытыми, теневыми ценами или маргинальными оценками ресурсов.

В одной задаче ищут максимум линейной функции, в другой — минимум.
Коэффициенты при переменных в линейной функции одной задачи являются свободными членами системы ограничений в другой.
Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида ≤ , а в задаче минимизации все неравенства вида ≥ .
Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг к другу:
Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.
Условия неотрицательности переменных имеются в обеих задачах.

Итак, имеем исходную задачу I и ее оптимальное решение х * = (0, 40, 0, 100) и F(х*) = 700.

Применяя теорему двойственности, получим решение двойственной задачи по известному решению исходной задачи.
Найдем решение двойственной задачи II у* = (у₁, у₂, у₃), не прибегая к симплекс-методу, а воспользовавшись второй теоремой двойственности и известным оптимальным планом х *.

Рассмотрим выполнение неравенств задачи I при подстановке х* в систему ограничений.

5x₁+0,4x₂+2x₃+0,5x₄≤400	50+0,440+20 + 0,5100 = 66 0	Второе ограничение в двойственной задаче будет равенством 0,4y₁ + 5y₂ = 5
x₃ ≥ 0	x₃ = 0	Третье ограничение в двойственной задаче будет неравенством 2y₁ + y₂ + y₃ ≥ 4
x₄ ≥ 0	x₄ = 100 > 0	Четвертое ограничение в двойственной задаче будет равенством 0,5y₁ + y₂ + y₃ = 5

Поскольку 1, 5, 7 неравенства строгие (имеют знак " "), то соответствующие им неравенства в задаче II из пары сопряженных обязаны обратиться в равенства. имеем:
y₁=0
0.4y₁+5y₂=5
0.5y₁+y₂+y₃=5 или
y₁=0, y₂=1, y₃=4
т.е. у* = (0, 1, 4) - оптимальное решение.

Заметим, что действительно G(y*) = 400y₁+ 300y₂+ 100y₃= 400 · 0 + 300 · 1 + 100 · 4 = 700 = F(x*).

Итак, в силу второй теоремы двойственности мы очень быстро нашли оптимальное решение задачи II, пользуясь условием обращения в равенство хотя бы одного из пары сопряженных неравенств в системах ограничений двойственных задач.
Между переменными исходной задачи и переменными двойственной существует глубокая связь. А именно: после приведения обеих задач I и II к каноническому виду основные и дополнительные переменные задач соответствуют друг другу следующим образом:

Установив такую связь, можно заметить, что, решив задачу I симплекс-методом и получив последнюю симплекс-таблицу (табл.), мы фактически решим и задачу II.
Запишем таблицу, учитывая соответствие между переменными х _i и y_j .

у₄	у₂	у₆	у₃
базисные	-х₁	-х₆	-х₃	-х₇	свободные
у₁	х₅	334
у₅	х₂	40
у₇	х₄	100
-F	1	1	1	4	700

В силу соответствия и II теоремы двойственности переменные у₁, у₅, у₇ обязаны равняться 0, т.к. х₅, х₂, х₄>0 строго. А переменные у ₄, у ₂, у ₆, у ₃ принимают значения из индексной строки 1, 1, 1, 4 соответственно, т.к. им соответствующие переменные х₁, х₆, х₃, х₇ = 0, как свободные. Итак, из последней таблицы задачи II, не проводя даже никаких вычислений и пользуясь лишь соответствием переменных:

Мы научились по решению исходной задачи находить решение двойственной. Это оказалось возможно благодаря глубокой связи между переменными х_i и y_j. Осталось разобраться, каково экономическое содержание этих взаимосвязей.

Теорема равновесия

Задача 2
Составить двойственную задачу к задаче 1. Найти ее решение по теореме равновесия.
3x₁+x₂≥12
x₁+2x₂≥14
4x₁+11x₂≥68

Теорема равновесия. Пусть X*=(x₁*. x_n*) и Y*=(y₁*. y_n*) - допустимые планы пары двойственных задач в симметричной форме. Эти планы являются оптимальными тогда и только тогда, когда выполняются следующие условия дополняющей нежесткости:

Теорема 4 позволяет определить оптимальное решение одной из пары двойственных задач по решению другой. Если ограничение одной задачи при подстановке оптимального решения обращается в строгое неравенство, то соответствующая двойственная переменная в оптимальном решении двойственной задачи равна 0. Если в оптимальном плане одной задачи какая-нибудь переменная положительна, то соответствующее ей ограничение двойственной задачи является уравнением.
Дадим экономическую интерпретацию условиям дополняющей нежесткости. Если в оптимальном решении какое-нибудь сырье имеет отличную от 0 оценку, то оно будет израсходовано полностью (ресурс является дефицитным). Если сырье расходуется не полностью (находится в избытке), то его оценка равна 0. Таким образом, получаем, что двойственные оценки – это мера дефицитности сырья. Оценка показывает, на сколько возрастет значение целевой функции при увеличении запаса соответствующего сырья на 1 ед. Если некоторый вид продукции входит в план производства, то затраты на его производство совпадают со стоимостью произведенной продукции. Если затраты на производство какого-нибудь вида продукции больше стоимости продукции, то продукция не производится.
В случае если одна из пары двойственных задач содержит две переменных, ее можно решить графически, а, затем, найти решение двойственной задачи, используя Теоремы 3 и 4. При этом могут возникнуть 3 случая: обе задачи имеют допустимые решения, допустимые решения имеет только одна задача, обе задачи не имеют допустимых решений.

Пример 2
Составить двойственную задачу и найти ее решение по теореме равновесия
x₂-2x₃+2x₄-2x₅≤4
-2x₁-2x₂+2x₃+2x₄+x₅≥2
x_i≥0, i= 1,5
Z=10x₁-9x₂-19x₃-13x₄-11x₅ → max, если известно решение исходной задачи: Zmax=(3;4;0;0;0).
Построим двойственную задачу. Согласуем знаки неравенств с целью исходной задачи.

Пример 3
Составить двойственную задачу к задаче из примера раздела 1.5 и найти ее решение по теореме равновесия
x₁+3x₂≥12
5x₁+4x₂≥31
2x₁+3x₂≥18
x₁, x₂≥0
Z(x₁,x₂)=12000x₁+16000x₂→min
В разделе 1.5 было найдено решение исходной задачи средствами MS Excel: Zmin(3;4)=100000
Составим двойственную задачу. Знаки неравенств уже согласованы с целью задачи.

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

1. Теоретическая часть. Методы линейного программирования, двойственность в линейном программировании

Линейное программирование — это частный раздел оптимального программирования. В свою очередь оптимальное (математическое) программирование — раздел прикладной математики, изучающий задачи условной оптимизации. В экономике такие задачи возникают при практической реализации принципа оптимальности в планировании и управлении. Необходимым условием использования оптимального.

Среди универсальных методов решения задач линейного программирования наиболее распространен симплексный метод (или симплекс-метод), разработанный американским ученым Дж. Данцигом. Суть этого метода заключается в том, что вначале получают допустимый вариант, удовлетворяющий всем ограничениям, но необязательно оптимальный (так называемое начальное опорное решение); оптимальность достигается последовательным улучшением исходного варианта за определенное число этапов (итераций). Нахождение начального опорного решения и переход к следующему опорному решению проводятся на основе применения метода Жордана-Гаусса для системы линейных уравнений в канонической форме, в которой должна быть предварительно записана исходная задача линейного программирования (ЗЛП); направление перехода от одного опорного решения к другому выбирается при этом на основе критерия оптимальности (целевой функции) исходной задачи.

2.Практическая часть. Решение задач

2.1. Задача №1

Решите графическим методом типовую задачу оптимизации. Осуществите проверку правильности решения с помощью средств MS Excel (надстройка Поиск решения).

Условие: Фирма выпускает два вида комплексных удобрений для газонов в упаковке – обычное и улучшенное. Обычное удобрение стоит 3 ден. ед./уп. и включает 3 кг азотных, 4 кг фосфорных и 1 кг калийных удобрений. Улучшенное удобрение стоит 4 ден. ед./уп. и включает 2 кг азотных, 6 кг фосфорных и 3 кг калийных удобрений. Для подкормки некоторого газона требуется по меньшей мере 10 кг азотных, 20 кг фосфорных и 7 кг калийных удобрений. Определите, сколько и каких удобрений нужно купить, чтобы обеспечить эффективное питание растений и минимизировать стоимость покупки. Постройте экономико-математическую модель задачи, дайте необходимые комментарии к ее элементам и получите решение графическим методом. Что произойдет, если решать задачу на максимум, и почему?

2.2. Задача №2

Рассчитайте параметры моделей экономически выгодных размеров заказываемых партий.

а) оптимальный объем заказа;

б) годовые расходы на хранение запасов;

в) период поставок;

М = 900 упаковок – годовой спрос

t = 3 дня – время поставки

К = 200 руб. – стоимость заказа (накладные расходы)

h = 2 руб. 60 коп. - затраты на хранение одной упаковки (удельные издержки хранения)

Т = 300 дней – количество рабочих дней в году

2.3. Задача №3

В бухгалтерии организации в определенные дни непосредственно с сотрудниками работают два бухгалтера. Если сотрудник заходит в бухгалтерию для оформления документов (доверенностей, авансовых отчетов и пр.) в тот момент, когда оба бухгалтера заняты обслуживанием ранее обратившихся коллег, то он уходит из бухгалтерии, не ожидая обслуживания. Статистический анализ показал, что среднее число сотрудников, обращающихся в бухгалтерию в течение часа, равно 16 , а среднее время, которое затрачивает бухгалтер на оформление документа, – 10 мин.

Оцените основные характеристики работы данной бухгалтерии как СМО с отказами (указание руководства не допускать непроизводительных потерь рабочего времени!). Определите, сколько бухгалтеров должно работать в бухгалтерии в отведенные дни с сотрудниками, чтобы вероятность обслуживания сотрудников была выше 85%.

Если вам нужна помощь в написании работы, то рекомендуем обратиться к профессионалам. Более 70 000 авторов готовы помочь вам прямо сейчас. Бесплатные корректировки и доработки. Узнайте стоимость своей работы

Читайте также: