Математика для экономистов - Красс М.С.
ISBN 5-94723-672-9
Скачать (прямая ссылка):
3
1
0
-1
-1
0 і I
-3
1
2
5
А,-
-12 3
0
5
0
5
Г ~
-1
0
1
2/3
-1/3
1/3
2
Уї
_> _
_ л. j_ °_.
0 0
-1/3
л
1/3
-1
2/3 3
14,3. Двойственные задачи 277
Из таблицы следует, что ynm =(,0, 2/3, V3),S(y)mn = 3. На основании теоремы двойственности 14.1 имеем:
Решение другой задачи найдем по соответствию между переменными:
Исходная задача
ОгИиВКЫС liepVHflUlblf
Балансовые переменные J-V ^
Двойственная задача
Балансовые переменные Hi' Ух
Основные переменные Jo: УЇ- Уз
Значение т, определяем по последней симплексной таблице в строке Д, в соответствующем столбце, причем значения Xj берем по модулю
.г, -» у*, X1 = I Д.л I = I-4 | = 4,
'і -> і/з. Хг = \А5\ = \ -I I= 1.
Таким образом, решение исходной аадачи:
тВ1ТГ =(4,1), при этом Л(.ї)|11лі =3.
Если исходная задача решена симплексным методом, то решение двойственной задачи может быть найдено по формуле
где С - матрица-строка коэффициентов при базисных переменных целевой функции в оптимальном решении исходной задачи; Л~[ — обратная матрица для матрицы Л, являющейся матрицей коэффициентов базисных переменных системы ограничений исходной задачи в оптимальном решении.
Б. Теперь решим симплексным методом исходную задачу
L{x) =xt -Ху -> птах при ограничениях (с учетом балансовых переменных)
-Zy1 + Tj + X3 =2, - .y1 -2.Tj + .т., -% .г, + T2 + xh = 5,
-т, >0, i = U Соответствующая таблица решения имеет следующий вид.
278 Глава 14. Линейное программирование
Таблица 14.2
с,
БП
1
I
Q
0
0
*1
*я
*ч
*5
ь,
0
*3
-г
1
I
0
0
2
D
xi
і
-2
0
1
0
2
0
-?
і
1
0
D
1
5
-
-і
1
(1
0
0
0
0
0
-3
1
2
0
6
]
-Tl
і
-2
U
1
0
2
0
¦Ч
0
3
0
-1
!
3
-
0
-1
0
1
0
2
D
D
0
1
1
1
9
I
*1
1
0
0
1/3
2/3
•1
-1
0
1
0
1/3
1/3
1 •
--
Д2
0
0
0
2/3
1/3
3
Из таблицы следует, что Jf01n =(4,1), і(Jt)111111 = 3. Выпишем матрицы пересчета:
Г-2 1 П ГО 1/3 2/34I
C=(I -1 0)1М, A =
1 -2 0 1 1 0
, тогда А' =
0 -1/3 1/3
1 1 1
УОГ1Т = CT' =(1 -10)
ft) 1/3 2/3^
0 -1/3 1/3
1 1 1
= (0, 2/3, V3).
Таким образом, решение двойственной задачи:
ут =(0, 2/3, УЗ). пр„ этом S(y)mm = 3.
14.3. Двойственные задачи 279
Решение несимметричных задач
Рассмотрим на примере решение несимметричных задач с использованием теорем двойственности
Исходная задача I(.r) = Зд', + X7 + З.Г;, + xi -» min, 2х, - 2х7 + 3? - .V1 = 9 I jr„ X1 + хг - Ur1 - xi = 6 I уъ
Двойственная задача S(y)= fy\ + Gy5 -> max,
-2,y, + .Vi s 1 I л„ 3^i - 6i/2 < 3 I .V3, -2y,-ys<l I x4.
Здесь переменные двойственной задачи у{ и у2 — произвольные по знаку.
Решим двойственную задачу графическим методом, получим:
у„г,Д1/2, 2), при этом S(y)„t =33/2. По теореме двойственности 14.1 L(x)mm =S(y)miK =33/2. Подставим у ^ в систему ограничений двойственной задачи:
'2.V2 + 2<3, 3 = 3,
-2-1/2 + 2 < I 1 = 1, ^31/2-62^3, -21/2 <3. -+.т, =0,
-2'1/2-2<1, -3>1 -»л-( =0.
Так как дг3 = Лі=0, то система ограничений исходной задачи примет вид
12*, -Ix7 =? |х, +X1 =6.
Решая данную систему, получим:
г,,,,, =(21/4, 3/4, 0, 0), при этом I(.v)„„n =33/2.
Решение задач можно также получить с использованием обратной матрины.
Пусть решение исходной задачи:
хиш =(21/4, 3/4, O1 0) при этом /.(*)„,,„ =33/2, Решение двойственной задачи найдем по формуле
280 Глава и. Линейное программирование
ГДЕ
C= (З 1), А
(1
, /Г1 =
1 [
1/4 IfA
1/4 1/2 -1/4 1/2
:(1/2 2).
-1/4 V2J
Таким образом, yi)fr, =(1/2, 2), при этом .V(~)„]iis =3,3/2. Решение смешанных двойственных задач
Смешанные двойственные задачи также можно решать е использованием теорем двойственности. Поясним это па примере.
Исходная задача Цх) = X1 -.T1 -» max, Lv1 +3.V2 +Зг3 =3 I1V1, }2лг, + 3.V3 ? 4 I U1, X1 >Ц ; = П-
Двойственная задача
¦5"(F) = ^i + 4^г -> min, у, +2у2 a 1 I X,,
\x.lt
Зу, +?, >-1 I Jr3,
//[ — произвольная по знаку, г/2 > 0. Найдем оптимальное решение двойственной задачи;
х,т =(i а 2/3) при этом ?<*)_ =1/3, По теореме двойственности 14.1
і (J?),™ =-5(F)11111, =1/3. По теореме двойственности 14.2, так как г, > 0, лл > 0, то 1-е и 3-е ограничения двойственной задачи выполняются а виде равенств;
^y, =1, 3V г =-!>
откуда yt = -5/3, уг = А/3, т. с. #„11Г =-5/3, 4/3).
14.3.3. Экономический анализ задачи оптимального использования ресурсов
Рассмотрим задачу оптимального использования ресурсов, запишем ее математическую модель:
14.3. Двойственные задачи 281
п
МО = Zs-1"; ~* тах
при ограничениях
]Г я^.д: <b; \ у, X1 >Q, і = t т j = \п
Двойственная задача имеет вид
3(У) = У, тпїп
і=і
при ограничениях
