Математика для экономистов - Красс М.С.
ISBN 5-94723-672-9
Скачать (прямая ссылка):
14.3. Двойственные задачи 273
ограничений теперь являются коэффициенты целевой функции исходной задачи. Требование максимизации целевой функции заменяется на минимизацию и наоборот. Все переменные двойственной задачи неотрицательные.
Математическая модель двойственной задачи имеет следующий вид; найти минимум целевой функции
S(y) = hlyl + b2y.2 +..- + Ьтуп mm при ограничениях:
аиу, + а21у2 + ... + ая1ут г с,,
(14.11)
(14.12)
у і >0, і = I1 т, j = 1, и. Несимметричные двойственные задачи
Расссмотрнм математическую модель исходной задачи в канонической форме.
Дана исходная задача нахождения максимума целевой функции
A(Jf) = C1-V1 +C1X1 + ... + спхп при ограничениях
'O11X1 +U11X2 +... + 0^n = Ь].\у,
a21a-, +U11X1 +...+U1nXn =Ь2,\уг
шах
0„i*t +a„-iXi
(іщ,хя =bm,\ym
X1 > 0, і = I1 т, j = 1, ті Составим математическую модель двойственной задачи.
Для ее составления пользуются тем же правилом, что и для составления симметричной задачи с учетом следующих особенностей:
• ограничениями двойственной задачи будут неравенства. Если в целевой функции двойственной задачи требуется найти минимум, то знак неравенства >, если максимум—то <;
274 Глава 14. Линейное программирование
• переменные у, произвольные по знаку, т. е. могут принимать как положительные, так и отрицательные значения.
Математическая модель двойственной задачи также состоит из соотношений (14.11), (14.12), с той лишь разницей, что теперь переменные
у, — произвольные по знаку, і = 1, т.
Совместное рассмотрение пары двойственных задач имеет практическое значение, так как, имея оптимальное реиіение одной задачи, на основании теорем двойственности можно найти оптимальное решение другой, не решая ее.
Смешанные двойственные задачи
Математическая модель исходной задачи имеет условия симметричных и несимметричных задач. При составлении двойственной задачи необходимо выполнять правила составления симметричных и несимметричных задач.
Приведем основные теоремы, необходимые для решения двойственных задач.
Теорема 14.1- Если одна из двойственных задач имеет оптимальное решение, то другая также имеет оптимальное решение, причем для любых оптимальных решений .г и у выполняется равенство
Если одна из двойственных задач неразрешима из-за I(-v),mjl -» <х> (или S(y)min -> -«>), то другая задача также не имеет допустима решений.
Теорема 14.2. Для оптимальности допустимых решении х и у нары
двойственных задач необходимо и достаточно, чтобы они удовлетворяли системе уравнений
Теорема утверждает, что если в оптимальном решении одной из двойственных задач какая-либо переменная строго больше нуля, то соответствующее ей ограничение в другой двойственной задаче выполняется как строгое равенство, и наоборот, если при оптимальном решении одной из двойственных задач какое-либо ограничение вы-
14.3. Действенные задачи 275
полняется как строгое неравенство, то соответствующая ему переменная в оптимальном решении другой задачи равна нулю.
Соотношения (14.14) представляют собой формулы пересчета решений двойственных задач.
14.3.2. Решение двойственных задач
Решение симметричных задач
Рассмотрим па примере решение задач с использованием теорем двойственности.
Исходная задача Двойственная задача
L(x) = дг( -т3 -> max $(у) = 2і/, + 2у2 + 5ул -» min
при ограничениях при ограничениях
лг, 2г 0, .г, > 0.
Решив исходную задачу графическим методом, получим
На основании теоремы двойственности 14.1
Д*)-о =S(y)mm = 3,
так как .г,, х2>0, по теореме двойственности 14.2 систему ограничений двойственной задачи можно записать в виде равенств:
Подставим xtm в систему ограничений исходной задачи: '-2¦ 4 + 1 <2, -1 <% поэтому у, ^0, J 4-21<2, 2=2 поэтому (у2>0, 4 + 1 <5, 5=5, поэтому уъ >0.
Тогда система ограничений двойственной задачи примет вид
-2л-, +Jf5, й2/у, X1 -2X1 <2/у3, X1 +T3 <5/у3,
і >
S1 a 0. 1 = 1, 3.
"2гу, +у2 + !/j = I1 У, -2уг + Уз = -1-
276 Глаза 14. Линейное программирование
Откуда у1йп = (0, 2/3, 1/3), при этом )nil1l =3.
Пусть дано решение двойственной задачи у,т = (0, 2/3, 1/3),
¦S = 3, найдем решение исходной.
Потеоремедвойственности U-I ?(*)„,„ = 5(,V)™,, = ЗТак какг/2 > 0 и ул> 0, по теореме двойственности 14.2 второе и третье неравенства исходной задачи выполняются как равенства:
X1 -2хг =2, л", + jf, = 5.
Откуда хат = (4,1) при этом і(.т)Іиаі = 3.
Рассмотрим решение задач методом, основанным на взаимно однозначном соответствии между переменными: основным переменным исходной задачи соответствуют балансовые переменные двойственной и наоборот.
А. Решим двойственную задачу симплексным методом: S(y) = 'lyx +'1уг + 5//3 max
при ограничениях
'-2у, -+у2 + у, -yt = J. З, ~ЇУї Н/э ~Уі ----1. (/, >0, і = ІД
Таблица 14.1
БІІ
Иг ! (Уз I ^ I
У*
-1
Уз U
JL
!
Уь
,
- I
D
1
1
0
Уз
у5
-2
1
