Теория двойственности в анализе оптимальных решений экономических задач линейного программирования. Теория двойственности в анализе оптимальных решений экономически. Различают три основные формы лп. Стандартная форма

• Название: Различают три основные формы лп. Стандартная форма
• Анкор: Теория двойственности в анализе оптимальных решений экономических задач линейного программирования
• Дата: 01.03.2022
• Размер: 258.54 Kb.
• Имя файла: Теория двойственности в анализе оптимальных решений экономически.docx
• Тип: Документы; #378683
• страница: 1 из 3

Различают три основные формы ЛП.

Стандартная форма – все ограничения являются ограничениями-неравенствами, а все переменные неотрицательны (удобна при решении задач ЛП графическим методом).

Каноническая форма – все ограничения являются ограничениями-равенствами с неотрицательными правыми частями, а все переменные неотрицательны. Основные вычислительные методы (симплекс-метод и его варианты) разработаны именно для этой формы.

Общая форма – часть ограничений являются равенствами, часть – неравенствами. Кроме того, не на все переменные наложены условия не отрицательности.

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

Приведём следующую задачу ЛП, представленную в общей форме, к канонической форме:

z=3х₁+4х₂max,

2х₁+3х₂=12,

5х₁-6х₂≤7,

-3х₁+2х₂≤-4,

x₁ не ограничена в знаке,x₂0.

Проведём следующие преобразования:

1. 
   Т.к. правые части ограничений должны быть неотрицательны, то умножим 3-е ограничение на -1, в результате получим 3х₁-2х₂≥4.
   
2. 
   Во 2-м ограничении левая часть не больше правой, поэтому, чтобы их уравнять (сбалансировать), необходимо в левую часть добавить балансовую переменную x₃0. Если данное ограничение определяет расход некоторого ресурса, переменную x₃ следует интерпретировать как остаток, или неиспользованную часть, данного ресурса.
   
3. 
   В 3-м ограничении левая часть не меньше правой, поэтому, чтобы их сбалансировать, необходимо от левой части отнять балансовую переменную x₄0. Переменную x₄ следует интерпретировать как избыток, или перерасход, данного ресурса.
   
4. 
   Любую переменную x_i, не имеющую ограничения в знаке, можно представить как разность двух неотрицательных переменных: x_i=x_i-x_i, где x_i, x_i0. Поэтому в целевой функции и во всех ограничениях необходимо подставить x₁=x₁-x₁, где x₁,x₁0.
   

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

z=3x₁-3x₁+4х₂max,

2x₁-2x₁+3х₂=12,

5x₁-5x₁-6х₂+х₃=7,

3x₁-3x₁-2х₂+х₄=4,

x₁,x₁,x₂,x₃,x₄0.
Кроме того, необходимо отметить, что максимизация некоторой функции эквивалентна минимизации той же функции, взятой с противоположным знаком, и наоборот. Например, максимизация функции z=3x₁-2x₂+4х₃ эквивалентна минимизации функции (-z)=-3x₁+2x₂-4х₃. Эквивалентность означает, что при одной и той же совокупности ограничений оптимальные значения переменных x₁,x₂,x₃ в обоих случаях будут одинаковы. Отличие заключается в том, что при одинаковых числовых значениях целевых функций их знаки будут противоположны.

Теория двойственности в анализе оптимальных решений экономических задач линейного программирования

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

Рассмотрим основные понятия и выводы специального раздела линейного программирования ─ теорию двойственности на примере задачи планирования производством. С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной.

Пример. Предприятие выпускает четыре вида продукции П₁, П₂, П₃ и П₄. Для производства продукции оно располагает тремя ресурсами, запасы которых ограничены величинами 35, 30 и 40 единиц. Удельные затраты на единицу продукции и цена единицы готовой продукции заданы в виде таблицы:

Ресурсы	Расход ресурсов на единицу продукции
	П1	П2	П3	П4
Р1 Р2 Р3	4 1 3	2 1 1	2 2 2	3 3 1
Цена (ден.ед.)	14	10	14	11

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

Модель задачи:

f = 14х₁+ 10х₂+ 14х₃+ 11х₄ max. (5.1)

4х₁+ 2х₂+ 2х₃+ 3х₄ 35,

х₁+ х₂ + 2х₃+ 3х₄ 30, (5.2)

3х₁+ х₂+ 2х₃+ х₄ 40.

х_j 0, (j= . (5.3)

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

Обозначим эти оценки за единицу каждого вида ресурса соответствен­но через y₁; y ₂ и y ₃ (Р₁, Р₂, Р₃). Эти оценки для упрощения иногда называют внутренними ценами на ресурсы в условиях данного производства (теневыми ценами). Т.е. они представляют объективно необходимые затраты на производство продукции в данных условиях.

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

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

П₁: 4у₁ + у₂ + 3у₃ 14

П₂: 2у₁ + у₂ + у₃ 10 (5.4)

П₃: 2у₁ + 2у₂ + 2у₃ 14

П₁: 3у₁ + 3у₂ + у₃ 11

2. Оценки по их смыслу должны выражаться не отрицательными чис­лами, т.е.

у_i 0, i = (5.5)

3. Для объективной оценки ресурсов необходимо требовать, чтобы общая стоимость всех ресурсов, находящихся в распоряжении предприятия, была возможно меньше, т.е.

φ = 35 у₁ + 30 у₂ + 40 у₃ min (5.6.)

Итак, получили модель задачи:

φ = 35 у₁ + 30 у₂ + 40 у₃ min

4у₁ + у₂ + 3у₃ 14

2у₁ + у₂ + у₃ 10 (5.7.)

2у₁ + 2у₂ + 2у₃ 14

3у₁ + 3у₂ + у₃ 11

у_i 0, i =

Таким образом, проблема правильной оценки ресурсов находится в распоряжении предприятия и сводится к решению стандартной ЗЛП. Задача (5.7.) называется двойственной к задаче (5.1.) — (5.3). Эти две задачи представляют собой числовой пример пары симметричных двойственных за­дач.

С экономической точки зрения в прямой задаче шла речь о нахож­дении оптимального плана выпуска продукции при ограничениях ресурсов из условия максимизации выручки. В двойственной задаче речь идет о нахождении систе­мы внутренних цен на используемые в производстве ресурсы, из условия минимизации стоимости всех запасов имеющихся на предприятии. Система двойственных оценок (у_i) тесно связана с конкретными условиями данного производства. С изменением этих условий меняется и система этих оценок.

В общем виде модели симметричных двойственных задач имеют сле­дующий вид:

Прямая или исходная	Двойственная
f = max (I)	φ = min (II)

Пусть нам дана задача линейной оптимизации в общем виде, тогда двойственная к ней примет вид:

Прямая или исходная	Двойственная
f = max (II)	φ = min (II`)

Свойство двойственности является взаимным, т.е. если к задачам (I`) и (II`) записать двойственные, то они совпадут с задачами (I) и (II) соответственно. Любую задачу внутри двойственной пары можно назвать прямой или исход­ной, тогда другая будет двойственной к ней.

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

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

2. Матрицы коэффициентов при переменных в двойственных задачах взаимно транспортированы.

3. Каждому ограничению ─ неравенству в двойственной задаче отвеча­ет неотрицательная переменная, а каждому ограничению равенству ─ пере­менная произвольного знака и наоборот: каждой неотрицательной перемен­ной ─ ограничение неравенство, а каждой переменной произвольного знака ─ ограничение равенство. При этом в задаче максимизации ограничения-неравенства имеют смысл « », а в задаче минимизации ─ « ».

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

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