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

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

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

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

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

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

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

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

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

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

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

(2.8)

Компоненты оптимального решения двойственной задачи принято называть двойственными оценками . Часто употребляется также термин «объективно обусловленные оценки».

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

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

Формулировка прямой (исходной) задачи:

y 1 ≥ 0, y 2 ≥ 0, y 3 ≥ 0.

В результате решения получим следующие оптимальные планы:

= (24, 4); = (1/3, 1/3, 0).

Легко убедиться, что при подстановке оптимальных планов в целевые функции задач оба получаемых значения равны 64.

Перейдем к рассмотрению свойств двойственных оценок.

Свойство 1. Оценки как мера дефицитности ресурсов. Двойственные оценки отражают сравнительную дефицитность факторов производства. Чем выше величина оценки , тем выше дефицитность i-го ресурса. Факторы, получившие нулевые оценки, не являются дефицитными и не ограничивают производство.

В нашем примере нулевую оценку получил третий ресурс ( = 0), поэтому он не является дефицитным, т.е., с точки зрения задачи, фонд рабочего времени на участке С не ограничивает производство. Напротив, первый (участок А) и второй (участок В) ресурсы являются дефицитными, причем ограничивают производство в одинаковой степени ( = = 1/3).

Последнее утверждение легко подтвердить, подставив и в ограничения исходной задачи:

4ּ24 + 6ּ4 = 120, 2ּ24 + 6ּ4 = 72, 4 < 10.

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

Свойство 2. Оценки как мера влияния ограничений на значение целевой функции. Величина двойственной оценки какого-либо ресурса показывает, насколько возросло бы максимальное значение целевой функции, если бы объем данного ресурса увеличился на единицу. В связи с этим значение объективно обусловленной оценки иногда называют теневой ценой ресурса . Теневая цена - это стоимость единицы ресурса в оптимальном решении.

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

Для нашего примера увеличение (уменьшение) фонда времени на участке А или В должно приводить к увеличению (уменьшению) максимальной прибыли на $1/3. Соответственно, например, при увеличении фонда времени участка А на 12 н-часов общая прибыль должна увеличиться на $4 (1/3ּ12).

Свойство 3. Оценки как инструмент определения эффективности отдельных хозяйственных решений. С помощью двойственных оценок можно определить выгодность выпуска новых изделий, эффективность новых технологических способов производства. При этом эффективным может считаться тот вариант производства, для которого сумма прибыли, недополученной из-за отвлечения дефицитных ресурсов, будет меньше прибыли получаемой. Разница между этими величинами (Δ j) вычисляется как:

(2.9)

В том случае, если Δ j ≤ 0, вариант производства является выгодным, если Δ j > 0 – вариант невыгоден.

Вернемся к нашему примеру. Пусть предприятие планирует к выпуску новый вид изделий: бейсбольные биты. Для производства одной биты необходимо затратить 3 часа работы на участке А, 4 часа работы на участке В и 1 час работы на участке С. Прибыль, получаемая от продажи одной биты, составляет $3. Выгодно ли предприятию выпускать новую продукцию?

Для ответа на вопрос рассчитаем Δ j по формуле (2.9):

Δ j = 3ּ + 4ּ + 1ּ - 3 = 3ּ1/3 + 4ּ1/3 + 1ּ0 - 3 = -2/3,

Δ j < 0, значит производить бейсбольные биты выгодно.

Свойство 4. Оценки как мера относительной заменяемости ресурсов с точки зрения конечного эффекта. Например, отношение / показывает, сколько единиц k-го ресурса может быть высвобождено при увеличении объема i-го ресурса на единицу, для того чтобы максимум целевой функции остался на прежнем уровне; или наоборот, сколько единиц k-го ресурса необходимо дополнительно ввести при уменьшении на единицу объема i-го ресурса, если мы хотим, чтобы значение целевой функции не изменилось.

В нашем примере двойственные оценки первого и второго ресурсов равны. Это означает, что, например, при уменьшении фонда времени на участке А на 1 н-час необходимо увеличить фонд времени на участке В на 1 н-час, чтобы общая получаемая предприятием прибыль осталась неизменной.

Завершая рассмотрение вопроса, отметим, что применение теорем двойственности (а именно, соотношений (2.6) и (2.7)) позволяет, зная оптимальное решение одной из взаимно двойственных задач, без труда отыскать оптимальное решение другой задачи.

Проиллюстрируем это утверждение примером .

Для производства четырех видов изделий А 1 , А 2 , А 3 и А 4 завод должен использовать три вида сырья I, II и III. Запасы сырья на планируемый период составляют, соответственно, 1000, 600 и 150 единиц.

Технологические коэффициенты (расход каждого вида сырья на производство единицы каждого изделия) и прибыль от реализации единицы каждого изделия приведены в таблице 2.12.

Таблица 2.12 - Исходные данные задачи о четырех видах изделий

Требуется, зная решение данной задачи, решить задачу, двойственную ей.

Сформулируем исходную ЗЛП.

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

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

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

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

f(x) = c1 x1 + c2 x2 + …+ cn xnmax,11 x1 + a12 x2 + … + a1n xn b1,21 x1 + a22 x2 + … + a2n xn b2,

…………………………………….……m1 x1 + am2 x2 + … + amn xn bm,j 0, j = 1, 2, …, n.

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

g(y) = b1 y1+ b2 y2 + …+ bm ym??min11 y1 + a21 y2 + … + am1 ym c112 y1 + a22 y2 + … + am2 ym c2

………………………….………………1n y1 + a2n y2 + … + amn ym cn

yi 0, i = 1, 2, …, m.

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

видим, что Адв = АTпр.

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

< c, x > max; Ax ?b, x ?0.g(y) = < b, y > min; ATy ?с, y ?0.

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

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

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

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

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

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

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

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

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

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

f(x)=2x1-4x2max;1+ 3x2 8,

3x1+ x2 -7,

2x1 - 5x2 10,

x1, x2 0.

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

g(y)=8 y1-7y2+10 y3 min;1 - 3 y2+ 2 y3 2,

3y1+ y2 -5 y3 -4,1, y2 0.

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

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

g(y)= -8y1+7y2-10y3 max;1+ 3y2 - 2y3 -2,

3y1 - y2+ 5y3 4,1, y2 0.

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

f(x)= - 2x1+ 4 x2 min;

x1 - 3x2 -8,

x1 - x2 7,

2x1+ 5x2 -10,

x1, x2 0.

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

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

f(x) = < c, x > min; b, x 0,

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

g(y) = < b, y > max;Ty с, y 0.

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

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

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

·организовать из них выпуск 3 новых видов продукции: P1, P2, P3.

·продать их.

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

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

РесурсыРасход ресурса на единицу продукцииЗапас ресурсовP1P2P3R112110R22138Удельная прибыль$6$4$4

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

Пусть xj - план выпуска продукции Pj.

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

f(x)=6x1+4x2+4x3 max;

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

1+2x2+x3 10,

x1+x2+3x3 8,j 0, j=1,2,3.

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

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

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

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

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

Пусть y1 - цена одной единицы ресурса R1, y2 - цена одной единицы ресурса R2.

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

g(y) = 10 y1+ 8 y2 min.

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

y1+2y2 6,

y1+y2 4,

y1+3y2 4,

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

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

y1, y2, y3 0,

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

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

Прямая задача Определить такой план выпуска продукции x =(x1, x2,…, xn), используя ограниченные запасы ресурсов, при котором прибыль от реализации продукции будет максимальной.Двойственная задача Установить такой набор цен ресурсов y =(y1, y2,…, ym), при которых стоимость ресурсов, затраченных на выпуск единицы продукции будет не ниже прибыли от ее реализации, но при этом суммарная стоимость затрат будет минимальна.

Цены ресурсов y1, y2,…, ym носят названия теневых, неявных или внутренних цен. Эти названия отличают их от «внешних», заранее известных цен с1, с2,…, сn на выпускаемую продукцию. Цены y1, y2,…, ym на ресурсы определяются из решения двойственной задачи и характеризуют стоимость затрат на выпуск конкретных видов продукции, поэтому их часто называют двойственными оценками ресурсов.

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

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

f(x) = < c, x > max;(4.1)Ax = b,(4.2)x 0.(4.3)

Здесь x = (x1,…, xn), c = (c1,…, cn), b = (b1,…, bm), так что число уравнений в системе (4.2) равно m.

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

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

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

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

f(x)=< c, x > max;b,

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

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

u = (u1,…, um) 0,

v = (v1,…, vm) 0.

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

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

g (u, v)=< b, u > + < - b, v > min,

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

ATu - ATv c,

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

g (u, v)=< b, u - v> min,T (u - v) c, 0, v 0.

Введем новый вектор двойственных переменных y = (y1, y2,…, ym) с координатами yi = ui - vi. Поскольку разность неотрицательных чисел может быть и отрицательной (например, 2-5= -3), то двойственные переменные yi не имеют ограничений по знаку.

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

g(y) = < b, y > min;Ty 0,

Переменная любого знака !

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

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

Прямая задача линейного программированияДвойственная задача линейного программированияЦелевая функция< c, x > max< b, y > minЦелевая функцияТип i-го ограниченияi biyi 0Знак i-й переменнойi biyi 0i = biyij 0j cjТип j-го ограниченияxj 0j cjxj ? свободная переменнаяj = cj

Прямая задача линейного ПрограммированияДвойственная задача линейного программированияЦелевая функция< c, x > min< b, y > ?maxЦелевая функцияТип i-го ограниченияi biyi ?0Знак i-ой переменнойi biyi 0i = biyi - любого знакаЗнак j-ой переменнойxj 0j cjТип j-го ограниченияxj 0j cjxj ? свободная переменнаяj = cj

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

1. f(x) = 2x1 - 2x2+ 3x3 - 6x4 max

x1+ x2 - 2x3 + x4 = -101 - 5x2 - x3 + 2x4 = 35j 0, j=1,2,3,4

F(x) = - x1 - 3x2+ x3 min1+ x2+ x3 61 - x2+ x3 8j 0, j=1,2,3

F(x) = 9x1+ 2x2+ 3x3+ 2x4 min

x1+ x2+ 2x3 = 2

x1+ x2 - x3 - 4x4 = -1j 0, j=1,2,3,4

F(x) = x1 - 2x2 max1+ x2 4

x1 - x2 8

x1+ x2 0

x2 0

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

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

f(x) = < c, x > max;(4.4)g(y) = < b, y > min;(4.7)Ax b(4.5)ATy c(4.8)x 0(4.6)(y 0(4.9)x = (x1,…, xn)y = (y1,…, ym)

Между решениями этих задач существует тесная связь, отражаемая следующими свойствами и теоремами.

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

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

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

(x*) = g(x*) или < c, x*> = < b, y*>.

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

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

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

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

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

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

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

< Ax* - b, y* > = 0,(4.15)

< ATy* - c, x* > = 0,(4.16)

Доказательство.

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

Прямая задача ЛПДвойственная задача ЛПf(x) = < c, x > maxg(y) = < b, y > min(4.17) Ax = bATy cx 0

Необходимость.

Пусть x*, y* - оптимальные планы прямой и двойственной задач соответственно. Покажем, что условия (4.15), (4.16) выполняются.

Заметим, что при x = x* из (4.17) следует (4.15). Так как Ax* - b= 0, значит и скалярное произведение * - b, y* > тоже равно нулю. По первой теореме двойственности для оптимальных планов x*, y* выполняется равенство: < c, x* > = < b, y* >. Подставим сюда выражение для b из (14): b = Ax*. Используя правило перекидки, получим:

< c, x* > = < Ax*, y* >= < x*, ATy* > = < ATy*, x* >,

откуда следует < ATy* - c, x* > = 0. А это не что иное как условие (4.16)

Достаточность.

Пусть для допустимых планов x*, y* справедливо (4.15), (4.16). Докажем их оптимальность.

Условия (4.15) и (4.16) можно записать следующим образом

< Ax*, y* > = < b, y* >, < ATy*, x* > = < c, x* >.

По правилу перекидки < Ax*, y* > = < ATy*, x* >. Так как левые части условий равны, то равны и правые части:

< b, y* > = < c, x* >,

отсюда по свойству 2 заключаем, что x* - оптимальный план прямой задачи,* - оптимальный план двойственной задачи. Что и требовалось доказать.

. Условия равновесия

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

< Ax* - b, y* > = 0,(4.18)

< ATy* - c, x* > = 0. (4.19)

Прямая задача ЛПДвойственная задача ЛП f(x) = c1 x1 + … + cn xn maxg(y) = b1 y1+ …+ bm ym??minai1 x1 + … + ain xn bi, i =1,…, ma1j y1 + … + amj ym cj, j = 1,…, nxj 0, j = 1,…, nyi 0, i = 1,…, m

Раскрывая скалярные произведения, распишем условия (4.18) и (4.19) более подробно.

å (ai1 x1*+ … + ain xn* - bi) yi* = 0,(4.20)

å (a1j y1*+ … + amj ym* - cj) xj* = 0.(4.21)

В сумме (4.20) каждое слагаемое есть произведение разности левой и правой частей ограничения прямой задачи на соответствующую двойственную переменную. Очевидно, что все слагаемые имеют один и тот же знак «0», так как разности в круглых скобках меньше или равны нулю, а yi 0. Отсюда следует, что сумма (4.20) равна нулю тогда и только тогда, когда каждое слагаемое в ней равно нулю.

(ai1 x1*+ … + ain xn* - bi) yi* = 0, i =1,…, m. (4.22)

двойственность неравенство равновесие линейный

В сумме (4.21) каждое слагаемое равно произведению разности левой и правой частей ограничения двойственной задачи на соответствующую переменную прямой задачи. Все слагаемые в этой сумме одного знака (0), так как разности в круглых скобках и переменные xj* неотрицательны. Для того, чтобы сумма равнялась нулю, любое слагаемое в сумме должно быть равно нулю.

(a1j y1*+ … + amj ym* - cj) xj* = 0, j = 1,…, n. (4.23)

Учитывая знаки сомножителей в произведении (4.22), из него можно получить пару условий

Если ai1 x1*+ … + ain xn* < bi, то yi* = 0. (4.22a)

Если yi* > 0, то ai1 x1*+ … + ain xn* = bi. (4.22b)

Аналогично, из (6) следует пара условий

Если a1j y1*+ … + amj ym* > cj, то xj* = 0. (4.23a)

Если xj* > 0, то a1j y1*+ … + amj ym* cj.(4.23b)

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

·если какое-либо ограничение одной задачи на оптимальном плане выполняется как строгое неравенство, то соответствующая координата оптимального плана другой задачи равна нулю (условия (4.22a) и (4.23a)).

·Если какая-либо координата оптимального плана одной задачи положительна, то соответствующее ограничение другой задачи обращается в равенство (условия (4.22b) и (4.23b)).

Эти условия называются условиями дополняющей нежесткости или условиями равновесия.

. Геометрический смысл условий равновесия

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

ai1 x1 + … + ain xn bi(4.24)

называется связным или активным на плане x", если на этом плане оно обращается в равенство

ai1 x1"+ … + ain xn" bi.

Определение 2 . Ограничение (4.24) называется несвязным (неактивным, пассивным) на плане x", если на этом плане оно выполняется как строгое неравенство

ai1 x1"+ … + ain xn" < bi.

Геометрически, ограничение, активное в точке x", проходит через эту точку, а неактивное - не проходит.

На рисунке в точке x" P1 и P3 - активные, связные ограничения; P2 - неактивное ограничение. В точке x» P1, P2 - активные ограничения; P3 - неактивное ограничение.

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

На оптимальных планах двойственных задач

·неактивному ограничению одной задачи соответствует нулевая переменная плана другой задачи.

·положительной переменной оптимального плана одной задачи соответствует активное ограничение другой задачи.

Литература

1. Айвазян С.А., Иванова С.С. Эконометрика. Краткий курс: учеб. пособие / С.А. Айвазян, С.С. Иванова. - М.: Маркет ДС, 2007. - 104 с.

Бородич С.А. Вводный курс эконометрики: Учебное пособие. - Мн.: БГУ, 2009. - 354 с.

Бывшев В.А. Эконометрика: учеб. пособие / В.А. Бывшев. - М.: Финансы и статистика, 2008. - 480 с.

Доугерти Кристофер. Введение в эконометрику: Учебник для экон. спец. вузов / Пер. с англ. Е.Н. Лукаш и др. - М.: ИНФРА-М, 2007. - 402 с.

Дубров А.М., Мхитарян В.С., Трошин Л.И. Многомерные статистические методы: Учебник. - М.: Финансы и статистика, 2009. - 352 с.

Дуброва Т.А. Прогнозирование социально-экономических процессов. Статистические методы и модели: учеб. пособие / Т.А. Дуброва. - М.: Маркет ДС, 2007. - 192 с.

Магнус Я.Р., Катышев П.К., Пересецкий А.А. Эконометрика. Начальный курс: Учебник. -3-е изд., перераб. и доп. - М.: Дело, 2008. - 400 с.

Методы математической статистики в обработке экономической информации: учеб. пособие / Т.Т. Цымбаленко, А.Н. Баудаков, О.С. Цымбаленко и др.; под ред. проф. Т.Т. Цымбаленко. - М.: Финансы и статистика; Ставрополь: АРГУС, 2007. - 200 с.

Палий И.А. Прикладная статистика: Учебное пособие. - М.: Издательско-торговая корпорация «Дашков и К», 2008. - 224 с.

Порядина О.В. Эконометрическое моделирование линейных уравнений регрессии: Учебное пособие. - Йошкар-Ола: МарГТУ, 2006. - 92 с.

Практикум по эконометрике: Учеб. пособие / И.И. Елисеева, С.В. Курышева, Н.М. Гордеенко и др.; Под ред. И.И. Елисеевой. - 2-е изд., перераб. и доп. - М.: Финансы и статистика, 2007. - 344 с.

Прикладная статистика. Основы эконометрики: Учебник для вузов: В 2 т. 2-у изд., испр. - Т. 2: Айвазян С.А. Основы эконометрики. - М.: ЮНИТИ-ДАНА, 2009. - 432 с.

Симчера В.М. Методы многомерного анализа статистических данных: учеб. пособие. - М.: Финансы и статистика, 2008. - 400 с.

Чураков Е.П. Прогнозирование эконометрических временных рядов: учеб. пособие / Е.П. Чураков. - М.: Финансы и статистика, 2008. - 208 с.

Эконометрика: учеб. / под ред. д-ра экон. наук, проф. В.С. Мхитаряна. - М.: Проспект, 2008. - 384 с.

Эконометрика: учеб. / под ред. И.И. Елисеевой. - М.: Проспект, 2009. - 288 с.

Эконометрика: Учебник/И.И. Елисеева, С.В. Курышева, Т.В. Костеева и др., Под ред. И.И. Елисеевой. - 2-е изд., перераб. и доп. - М.: Финансы и статистика, 2006. - 576 с.

Репетиторство

Нужна помощь по изучению какой-либы темы?

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

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

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

План

1. Постановка и модель двойственной задачи

2. Методы решения

3. Теоремы теории двойственности и ее экономическое содержание

1. Постановка и модель двойственной задачи

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

Напомним, что в основе задачи линейного программирования рассматривается предприятие, имеющее ресурсы b i , где i = 1, 2, …, m . Оно тратит их на изготовление готовой продукции и эту продукцию реализует. При этом ставится цель - получить максимум продукции в стоимостном выражении не перерасходуя ресурсы. Модель задачи выглядит следующим образом: двойственный симплекс линейный программирование

I) Ж = с 1 х 1 + с 2 х 2 + … + с n х n max.

II) a 11 х 1 + а 12 х 2 + … + а 1 n х n ? b 1 ,

a 21 х 1 + а 22 х 2 + … + а 2 n х n ? b 2 ,

………………………………

a m 1 х 1 + а m 2 х 2 + … + а mn х n ? b m .

III) х j ? 0, j = 1, 2, …, n .

Предположим, что некоторое предприятие решило не тратить ресурсы на изготовление продукции, а продать эти ресурсы. Тогда возникает вопрос: по какой цене продавать ресурсы? Цена должна устраивать как продавца, так и покупателя. Интерес покупающей стороны заключается в том, чтобы заплатить за ресурсы как можно меньше, а интерес продающей стороны - в том, чтобы получить за ресурсы не меньше того, что она получила бы за реализованный готовый товар.

Тогда, в так называемой двойственной модели , целевая функция будет описывать интерес покупающей стороны, система ограничений - интерес продающей стороны (необходимо оценить ресурсы, которые пошли бы на изготовление единицы продукции и стоимость этих ресурсов ограничить ценой реализованной единицы продукции). Третье условие (неотрицательность переменных величин) будет выполняться в силу того, что цена единицы ресурса не может быть отрицательной. Введя в качестве цены единицы ресурса величину u i 0 (i = 1, 2, …, m ), ее еще называют оценкой ресурса (или двойственной оценкой), получим следующую модель:

I) F = b 1 u 1 + b 2 u 2 + … + b m u m min.

II) a 11 u 1 + a 21 u 2 + … + a m 1 u m c 1 ,

a 12 u 1 + a 22 u 2 + … + a m 2 u m c 2 ,

………………………………

a 1 n u 1 + a 2 n u 2 + … + a mn u m c n .

III) u i 0, i = 1, 2, …, m .

Сопоставим обе задачи:

Первая - задача на максимум (z max), вторая - на минимум (F min);

В первой система ограничений типа, во второй;

В первой задаче n неизвестных и m ограничений, во второй m неизвестных и n ограничений;

Коэффициенты в целевых функциях и величины в правых частях неравенств при переходе из одной задачи в другую меняются местами (в первой задаче c j - коэффициенты целевой функции, во второй c j - свободные члены; в первой задаче b i - свободные члены, во второй b i - коэффициенты целевой функции);

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

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

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

1) тип экстремума целевой функции меняется;

2) каждому ограничению исходной задачи ставится в соответствие переменная двойственной задачи;

3) свободные члены исходной задачи становятся коэффициентами при переменных в целевой функции двойственной задачи;

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

Рассмотрим конкретный пример построения двойственной модели:

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

I) Z = 6x 1 + 4x 2 max.

II) 2x 1 +4 x 2 ? 8,

2x 1 + x 2 ? 6.

III) x 1 ? 0, x 2 ? 0.

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

I) F = 8u 1 + 6u 2 min.

II) 2u 1 + 2u 2 ? 6,

4u 1 + u 2 ? 4.

III) u 1 ? 0, u 2 ? 0.

Следует отметить, что:

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

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

2. Методы решения

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

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

исходная задача (введем y i 0):

I) Ж = с 1 х 1 + с 2 х 2 + … + с n х n max.

II) y 1 = -a 11 х 1 - а 12 х 2 - … - а 1 n х n + b 1 ,

y 2 = -a 21 х 1 - а 22 х 2 - … - а 2 n х n + b 2 ,

…………………………………..

y m = -a m 1 х 1 - а m 2 х 2 - … - а mn х n + b m .

III) х j ? 0, j = 1, 2, …, n .

двойственная задача (введем v j 0):

I) F = b 1 u 1 + b 2 u 2 + … + b m u m min.

II) v 1 = a 11 u 1 + a 21 u 2 + … + a m 1 u m - c 1 ,

v 2 = a 12 u 1 + a 22 u 2 + … + a m 2 u m - c 2 ,

……………………………………

v n = a 1 n u 1 + a 2 n u 2 + … + a mn u m - c n .

III) u i 0, i = 1, 2, …, m .

Обе модели записываются в двойственную симплекс-таблицу следующим образом (таблица 4):

Таблица 4 - Двойственная симплексная таблица

					v n
					-x n	Свободные члены
					a 1 n
					a 2 n
u m	y m	a m 1	a m 2		a mn	b m
Свободные члены					-c n

Замечания:

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

Прежде чем составлять модель двойственной задачи, необходимо у исходной модели «выровнять» знаки, т.е. если целевая функция стремится к max , то все знаки в системе ограничений должны быть ? , а если к min , то ? . Система приводится в соответствие путем домножения обеих частей «неподходящего» неравенства на (-1). Например, чтобы записать модель, двойственную к приведенной модели

I) Z = 4x 1 + 2x 2 + 3x 3 min.

II) -4x 1 - 3x 2 +x 3 ? -4,

5x 1 + x 2 +2x 3 ? 6.

III) x 1 ? 0, x 2 ? 0, x 3 ? 0,

необходимо исходную переписать в виде:

I) Z = 4x 1 + 2x 2 + 3x 3 min.

II) 4x 1 + 3x 2 - x 3 ? 4,

5x 1 + x 2 +2x 3 ? 6.

III) x 1 ? 0, x 2 ? 0, x 3 ? 0.

Тогда двойственная задача будет выглядеть так:

I) F = 4u 1 +6u 2 max.

II) 4u 1 + 5u 2 ? 4,

3u 1 + u 2 ? 2,

-u 1 + 2u 2 ? 3.

III) u 1 ? 0; u 2 ? 0;

В центр двойственной симплекс-таблицы (таблицы 4) всегда ставится задача на max, вне зависимости от того какова целевая функция исходной задачи.

3. Основные теоремы теории двойственности и ее экономическое содержание

В качестве основной теоремы двойственности выделяют следующую формулировку: если одна из взаимно двойственных задач имеет оптимальное решение, то и другая также имеет оптимальное решение, при этом соответствующие им оптимальные значения целевых функций равны (т.е. max z = min F ).

Кроме этого варианта возможны следующие взаимоисключающие случаи:

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

Обе из рассматриваемых задач имеют пустые допустимые множества (т.е. обе не имеют решения).

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

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

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

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

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

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

Абсолютные значения оценок можно трактовать как некоторые расчетные «цены» ресурсов и потребностей, выраженные в тех же единицах, что и критерий, а знак «+» или «-» при этих «ценах» показывает, ведет ли увеличение данного фактора к возрастанию или уменьшению значения критерия;

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

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

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

Размещено на Allbest.ru

...

Подобные документы

Построение математической модели. Выбор, обоснование и описание метода решений прямой задачи линейного программирования симплекс-методом, с использованием симплексной таблицы. Составление и решение двойственной задачи. Анализ модели на чувствительность.

курсовая работа , добавлен 31.10.2014


Понятие теории оптимизации экономических задач. Сущность симплекс-метода, двойственности в линейном программировании. Элементы теории игр и принятия решений, решение транспортной задачи. Особенности сетевого планирования и матричное задание графов.

курс лекций , добавлен 14.07.2011


Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.

курсовая работа , добавлен 21.03.2012


Сущность линейного программирования. Математическая формулировка задачи ЛП и алгоритм ее решения с помощью симплекс-метода. Разработка программы для планирования производства с целью обеспечения максимальной прибыли: блок-схема, листинг, результаты.

курсовая работа , добавлен 11.02.2011


Оптимальный план прямой задачи графическим, симплекс-методом. План двойственной задачи по первой теореме двойственности. Определение целочисленного решения графическим, методом Гомори. Сравнение значений функций целочисленного и нецелочисленного решений.

задача , добавлен 29.12.2013


Постановка задач линейного программирования. Примеры экономических задач, сводящихся к задачам линейного программирования. Допустимые и оптимальные решения. Алгоритм Флойда - алгоритм для нахождения кратчайших путей между любыми двумя узлами сети.

контрольная работа , добавлен 08.09.2010


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

курсовая работа , добавлен 09.12.2008


Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.

контрольная работа , добавлен 11.04.2012


Анализ решения задачи линейного программирования. Симплексный метод с использованием симплекс-таблиц. Моделирование и решение задач ЛП на ЭВМ. Экономическая интерпретация оптимального решения задачи. Математическая формулировка транспортной задачи.

контрольная работа , добавлен 15.01.2009


Применение методов линейного программирования для решения оптимизационных задач. Основные понятия линейного программирования, свойства транспортной задачи и теоремы, применяемые для ее решения. Построение первичного опорного плана и системы потенциалов.

Основные определения теории двойственности .

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

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

F = 3х 1 + 5х 2 + 4х 3 + 5х 4 → max.

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

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

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

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

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

Неравенства, соединенные стрелочками, будем называть сопряженными .
Содержательная постановка двойственной задачи : найти такой набор цен (оценок) ресурсов Y = (y 1 , у 2 ..., у m), при котором общие затраты на ресурсы будут минимальны при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли (выручки) от реализации этой продукции.
Цены ресурсов у 1 , у 2 ..., у m в экономической литературе получили различные названия: учетные, неявные, теневые. Смысл этих названий состоит в том, что это условные, «ненастоящие» цены. В отличие от «внешних» цен с 1 , с 2 ..., с n на продукцию, известных, как правило, до начала производства цены ресурсов у 1 , у 2 ..., у m являются внутренними, ибо они задаются не извне, а определяются непосредственно в результате решения задачи, поэтому их чаще называют оценками ресурсов.
Связь прямой и двойственной задач состоит, в частности, в том, что решение одной из них может быть получено непосредственно из решения другой.

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

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

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

Если одна из пары двойственных задач 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 i y i

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

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

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

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

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

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

5x 1 +0,4x 2 +2x 3 +0,5x 4 ≤400	5*0+0,4*40+2*0+0,5*100=66<400	Ограничение выполняется как строгое неравенство, т.е. ресурс 1-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y 1 = 0.
5x 2 +x 3 +x 4 ≤300	5*40 + 0 + 100 = 300 = 300	Ограничение прямой задачи выполняется как равенство. Это означает, что 2-й ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y 2 ≠ 0)
x 1 + x 3 + x 4 ≤ 100	0 + 0 + 100 = 100 = 100	y 3 ≠ 0
x 1 ≥ 0	x 1 = 0	Первое ограничение в двойственной задаче будет неравенством 5y 1 + y 3 ≥ 3
x 2 ≥ 0	x 2 = 40 > 0	Второе ограничение в двойственной задаче будет равенством 0,4y 1 + 5y 2 = 5
x 3 ≥ 0	x 3 = 0	Третье ограничение в двойственной задаче будет неравенством 2y 1 + y 2 + y 3 ≥ 4
x 4 ≥ 0	x 4 = 100 > 0	Четвертое ограничение в двойственной задаче будет равенством 0,5y 1 + y 2 + y 3 = 5

Поскольку 1, 5, 7 неравенства строгие (имеют знак "<" или ">"), то соответствующие им неравенства в задаче II из пары сопряженных обязаны обратиться в равенства. имеем:

или

т.е. у * = (0, 1, 4) - оптимальное решение.

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

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

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

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

Запишем таблицу, учитывая соответствие между переменными х i и y j .

		у 4	у 2	у 6	у 3
	базисные	-х 1	-х 6	-х 3	-х 7	свободные
у 1	х 5					334
у 5	х 2					40
у 7	х 4					100
	-F	1	1	1	4	700

В силу соответствия и II теоремы двойственности переменные у 1 , у 5 , у 7 обязаны равняться 0, т.к. х 5 , х 2 , х 4 >0 строго. А переменные у 4 , у 2 , у 6 , у 3 принимают значения из индексной строки 1, 1, 1, 4 соответственно, т.к. им соответствующие переменные х 1 , х 6 , х 3 , х 7 = 0, как свободные. Итак, из последней таблицы задачи II, не проводя даже никаких вычислений и пользуясь лишь соответствием переменных:

у * = (у 1 *, у 2 *, у 3 *, у 4 *, у 5 *, у 6 *, у 7 *) = (0, 1, 4, 1, 0, 1, 0).

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

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

5.1 Понятие двойственности 83

5.2 Экономическая интерпретация двойственной задачи 87

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

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

5.5 Третья теорема двойственности 92

5.6 Пример решения сопряженных задач 96

5.6.1 Задача, двойственная задаче о диете 96

5.6.2 Выполнение основной теоремы двойственности 97

5.6.3 Выполнение теоремы о равновесии 99

5.6.4 Выполнение теоремы об оценке 99

5.7 Вопросы и упражнения 106

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

5.1 Понятие двойственности

Рассмотрим задачи линейного программирования в стандартной форме, записанные в матричной форме:

где С = (с 1 . . . с n), X =, B =, A =

,

где Y= (y 1 . . .y m).

Здесь X, Y - переменные * ; A, B, C - константы.

Задача (21) и любая эквивалентная ей задача линейного программирования называется двойственной задаче (20) и любой эквивалентной ей задаче.

Подчеркнем, что новых переменных вводится ровно столько, сколько в задаче (20) ограничений, т.е. m.

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

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

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

Доказательство . Построим задачу линейного программирования, двойственную (21). Поскольку определение дает возможность построить двойственную задачу только для задачи в той же форме записи, что и задача (20), вначале преобразуем задачу (21) таким образом, чтобы форма ее записи была такой же.

Приведем задачу (21) к стандартной форме на максимум:

Транспонируем входящие сюда величины, чтобы порядок действий над векторами и матрицами был таким же, как и в задаче (20):

mах -B Т Y Т

Теперь можно построить двойственную задачу в соответствии со сформулированным определением. Введем строку переменных Z.

Эта задача является двойственной к двойственной. Преобразуем ее.

Эта задача эквивалентна задаче (20) с точностью до обозначения.

Теорема доказана.

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

Рассмотрим задачу в канонической форме. Чтобы построить задачу, двойственную к ней, преобразуем ее к стандартной форме.

Построим теперь двойственную задачу. Отметим, что число ограничений задачи возросло в два раза (каждое уравнение преобразовано в два неравенства). Вектор-строку переменных двойственной задачи разобьем на две части, в каждую из которых будет входить равное число переменных, и обозначим его (U,V) = (u 1 , …,u m ,v 1 , …,v m).

При этом во всех линейных выражениях компоненты вектора В и матрицы А можно вынести за скобки, а в скобках останется разность векторов U = (u 1 , …,u m) и V = (v 1 , …,v m). Например, при перемножении строки переменных на первый столбец матрицы А будет получено: (a 11 u 1 +a 21 u 2 + …+ a m1 u m - a 11 v 1 - a 21 v 2 - … - a m1 v m = a 11 (u 1 - v 1) + a 21 (u 2 – v 2) + … + a m1 (u m – v m); - и т.д.

Обозначим U - V = Y. При этом переменные Y = (u 1 -v 1 ; …;u m –v m) = = (y 1 . . .y m) не ограничены по знаку. Тогда двойственная задача примет вид:

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

На основании проведенных рассуждений можно сделать вывод, что для построения двойственной задачи не обязательно каждый раз приводить задачу линейного программирования к стандартной форме, а именно нет необходимости преобразовывать уравнения к неравенствам, а не ограниченные по знаку переменные - к неотрицательным. Пусть в задаче в смешанной форме первые m` ограничений – уравнения, а остальныеm-m` - неравенства; и первыеn` переменных неотрицательны, а остальныеn-n` переменных по знаку могут быть любыми. Между задачей линейного программирования в смешанной форме и двойственной ей задачей линейного программирования можно установить следующее соответствие:

max c j x j	min b i y i
a ij x j = b i ,	a ij y i c j ,
a ij x j b i ,	a ij y i = c j ,
x j 0,	y i 0,
x j 0,	y i 0,

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

а) Переменные двойственной задачи соответствуют ограничениям исходной задачи, а ограничения - переменным.

б) Если исходная задача линейного программирования задана на максимум, то двойственная строится на минимум, и наоборот.

в) В задаче линейного программирования на максимум в ограничениях-неравенствах должен стоять знак , а на минимум -.

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

д) Неотрицательным переменным исходной задачи соответствуют ограничения неравенства двойственной задачи, а не ограниченным по знаку - уравнения.

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

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

min 2х 1 + 3х 2 - 4х 3 + х 5

4х 1 - 3х 2 - х 3 + х 4 + х 5 10

х 1 + 4х 2 + х 3 + х 5 = 15

2х 1 - 4х 2 - х 3 + х 4 3

Так как задача на минимум, умножим обе части первого ограничения на -1, чтобы получить знак неравенства : -4х 1 + 3х 2 + х 3 - х 4 - х 5  -10.

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

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

Первое ограничение двойственной задачи соответствует переменной х 1 прямой задачи, поэтому коэффициенты этого ограничения берут из столбца коэффициентов при х 1 , а свободный член – из целевой функции прямой задачи. Так как х 1 0, это ограничение – неравенство. Так как двойственная задача на максимум, знак неравенства. Аналогично строятся второе, третье и пятое ограничения. Четвертое ограничение соответствует переменной х 4 , знак которой может быть любым. Поэтому оно – уравнение.

Переменные y 1 иy 3 соответствуют первому и третьему ограничениям прямой задачи, которые представляют собой неравенства. Поэтому эти переменные – неотрицательные. Второе ограничение прямой задачи – уравнение, поэтому переменнаяy 2 не ограничена по знаку.

max -10y 1 + 15y 2 + 3y 3

4y 1 + y 2 + 2y 3  2

3y 1 + 4y 2 - 4y 3  3