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

Коэффициенты ЦФ и ограничений во всех ЗЛП задаются в качестве исходных Дых или парам-ов модели. Оптим-ое решение полученное методами зависит от значения этих коэфф-ов. На практике значения коэфф-ов никогда неизвестны с абсолютной точностью, т.к. многие из них являются функ-ями многих парам-ов. Решение практич-ой задачи нельзя считать законченным, если только найдено оптим-ое решение. Любое изменение в исходных Дых меняет условие Зи, что в свою очередь может изменить найденное оптим-ое решение. Анализ оптим-ого решения с возможным изменением парам-ов модели называется анализом чувствительности. Он необходим по след. причинам:

1. Некоторые парметры ЗЛП такие как финансовые средства, запасы сырья, производ-ные мощности можно регулировать Если обнаруживается, что оптимальное решение можно значительно увеличить за счет небольшого изменения заданных параметров, то данные изменения надо произвести.

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

3. Большую часть проблематики анализа чувствительности можно свести к следующим вопросам:

Останется ли решение оптимальным, если уменьшить удельный вклад в прибыль одной из б/п.

К каким последствиям приведет уменьшение объема ресурсов

Что произойдет, если ввести в рассмотрение новую управляемую переменную.

Двойственность.

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

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

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

Y=C1*x1+…+Cn*xn→max

При ограничениях

A11*x1+…a1n*xn<=b1

Am1*x1+…amn*xn<=bm

Xj>=0 j=1,t t<=n

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

S=b1*y1+…+bm*ym→min

При ограничениях

a11*y1+…am1*ym>=C1

a1n*x1+…amn*ym>=Cn

yi>=0 i=1,k k<=m

Правила образования двойственной задачи (ДЗ):

1. Целевая функция исходной задачи задается на максимум, а целевая функция ДЗ на минимум и наоборот

2. Матрица исходной задачи:

A = a11 … a1n

…

am1… amn

Обратная матрица

A^(T) = a11 … am1

…

a1n … amn

3. Число переменных в ДЗ = числу ограничений прямой задачи, а число ограничений ДЗ = числу переменных прямой задачи.

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

5. Если переменная xj прямой задачи может принимать только положительное значение, то j-е условие в системе ограничений ДЗ является неравенством вида >=. Если переменная xj может принимать как положительное так и отрицательное значение, то j-е ограничение уравнение <=. Аналогичное состояние имеется между ограничениями исходной задачи и переменными ДЗ.

Все двойственные пары задач принято делить:

Симметричные

Несимметричные

В симметричной паре ограничения прямой и Дз является неравенствами вида >= переменные обеих симметричных задач, могут принимать только положительные значения.

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

Прямая задача	Двойственная задача
Max Const в пр.ч. ограничений Целевая функция j-й столбец коэф-ов огр-ий i-я строка коэф-ов огр-ий j-я неотр. Перем. j—я переменная не имеющая ограничения в знаке i-е нер-во вида <= i –е соотношение в виде =	Min Целевая функция Const в пр.ч. ограничений j-й строка коэф-ов огр-ий i-й столбец коэф-ов огр-ий j-е нер-во вида >= j–е соотношение в виде = i-я неотр. Перем. i—я переменная не имеющая ограничения в знаке

Связь между решениями прямой задачи и ДЗ.

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

Y=Cj*xj->max

Ограничения

aij*xj=bi I=1,m

xj>=0

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

S= bi*yi->min

Ограничения

aij*yi>=Ci j=1,n

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

Лемма1.

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

Y(x)<=S(y)

Лемма 2.

Если Y(x*)<=S(y*), то х*-оптимальный план прямой задачи

У*- оптимальный план ДЗ

Теорема 1 ( 1-я теорема двойственности)

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

Ymax=Smin

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

Теорема 2. (2-я теорема двойственности)

План X*=(x1*…xn*) – сходная задача

План Y*=(y1*…ym*) – ДЗ

Являются оптимальными планами этих задач тогда и только тогда, когда для любого j=1,n выполняется равенство

aij*yi*-Cj)x*j=0