|
Прямая задача ЛП
|
Двойственная задача ЛП
|
|
f(x) = < 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-4x2
max;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.
· продать их.
Рассмотрим оба способа.
Исходные данные приведены в таблице:
|
Ресурсы
|
Расход ресурса на единицу продукции
|
Запас ресурсов
|
|
P1
|
P2
|
P3
|
|
|
R1
|
1
|
2
|
1
|
10
|
|
R2
|
2
|
3
|
8
|
|
Удельная прибыль
|
$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) заменим
парой неравенств
Ax b,
Ax b,
или, что то же самое
Ax b,
Ax - b,
Получим стандартную задачу ЛП с 2m
ограничениями.
f(x)=< c, x >
max;b,
- Ax - b,
x 0.
Построим к ней двойственную задачу
ЛП по известным правилам.
Для этого введем двойственные
переменные:
u = (u1,…, um) 0,
v = (v1,…, vm) 0.
Заметим, что, так как в прямой
задаче ЛП было 2m ограничений, то в двойственной будет 2m переменных.
Целевая функция двойственной задачи
примет вид:
g (u, v)=< b, u >
+ < - b, v > min,
а ограничения запишутся так:
ATu - ATv c,
u 0, v 0.
Перепишем эту задачу более
компактно:
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-го ограничения
|
[Ax]i bi
|
yi 0
|
Знак i-й переменной
|
|
[Ax]i bi
|
yi 0
|
|
|
[Ax]i = bi
|
yi
- любого знака
|
|
|
Знак j-ой переменной
|
xj 0
|
[ATy]j cj
|
Тип j-го ограничения
|
|
xj 0
|
[ATy]j cj
|
|
|
xj
свободная переменная
|
[ATy]j = cj
|
|
|
Прямая задача линейного Программирования
|
Двойственная задача линейного программирования
|
|
Целевая функция
|
< c, x > min
|
< b, y > max
|
Целевая
функция
|
|
Тип i-го ограничения
|
[Ax]i bi
|
yi 0
|
Знак i-ой переменной
|
|
[Ax]i bi
|
yi 0
|
|
|
[Ax]i = bi
|
yi
- любого знака
|
|
|
Знак j-ой переменной
|
xj 0
|
[ATy]j cj
|
Тип j-го ограничения
|
|
xj 0
|
[ATy]j cj
|
|
|
xj
свободная переменная
|
[ATy]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)
|
|
Между решениями этих задач
существует тесная связь, отражаемая следующими свойствами и теоремами.
7. Первая теорема
двойственности
Кроме основного неравенства и
достаточного признака оптимальности планов взаимно двойственных задач
существуют и другие связи между их решениями. Важно установить, влияет ли
наличие или отсутствие решения одной из пары задач на существование решения в
другой. Ответ на этот вопрос дает следующая теорема, известная как первая
теорема двойственности.
Теорема 1. Если одна из пары
двойственных задач имеет оптимальный план, то и другая имеет оптимальный план,
причем значения целевых функций на этих планах равны
(x*) = g(x*)
или < c, x*> = < b, y*>.
Если же целевая функция одной из
пары двойственных задач не ограничена на своём множестве планов (прямая -
сверху, двойственная - снизу), то множество планов другой задачи пусто.
Из первой части теоремы, которую мы
приводим без доказательства, следует, что равенство (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* =
(x1*,…, xn*) и y* = (y1*,…,
ym*) - оптимальны (каждый в своей задаче), тогда и только
тогда, когда выполняются условия:
< Ax* - b, y* > = 0, (4.15)
< ATy* - c, x* > = 0, (4.16)
Доказательство.
Проведем доказательство для
несимметричной пары двойственных задач.
|
Прямая задача ЛП
|
Двойственная задача ЛП
|
|
f(x) = < c,
x >
max
|
g(y) = < b, y >
min
|
|
(4.17) Ax = b
|
ATy c
|
|
x 0
|
|
Необходимость.
Пусть x*, y* -
оптимальные планы прямой и двойственной задач соответственно. Покажем, что
условия (4.15), (4.16) выполняются.
Заметим, что при x = x*
из (4.17) следует (4.15). Так как Ax* - b= 0, значит и скалярное
произведение <Ax* - 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)
Содержательный смысл условий (1) -
(2) рассмотрим для симметричной пары двойственных задач. Запишем эту пару в
координатной форме:
|
Прямая задача ЛП
|
Двойственная задача ЛП
|
|
f(x) = c1 x1
+ … + cn xn max
|
g(y) = b1 y1+
…+ bm ymmin
|
|
ai1 x1
+ … + ain xn bi, i =1,…, m
|
a1j y1
+ … + amj ym cj, j = 1,…, n
|
|
xj 0, j =
1,…, n
|
yi 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)
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 с.