Математическое программирование (линейное программирование). Киселева Э.В - 45 стр.

UptoLike

ВУЗ: 

НГАСУ «Сибстрин» | Новосибирск

Составители: 

Рубрика: 

91 92
.,jx
,xxx
,xxxx
,xxxx
,xxxxZ
j
)41(0
24022
40022
26032
max524
431
4321
4321
4321
=≥
⎪
⎩
⎪
⎨
⎧
≤++
≤+++
≤+++
→+++
=
Поставим в соответствие первому ресурсу оценку y
1
, второ-
му – y
2
, третьему – y
3.
Тогда общая оценка ресурса, используемого
на производство продукции, составит:
321
240400260 yyyW
+
+
=
.
Цель задачи – минимизировать эту величину.
Суммарная оценка ресурса, необходимого для производства
единицы продукции А, равна
.22
321
yyy ++
Согласно условию задачи эта величина должна быть не
меньше цены единицы продукции А, т.е.
122
321
≥++ yyy .
Из аналогичных соображений получаем:
⎪
⎩
⎪
⎨
⎧
≥++
≥++
≥+
.yyy
,yyy
,yy
522
23
42
321
321
21
Естественно предположить, что оценки y
1
, y
2
, y
3
неотрица-
тельны, т.е.
.y,y,y 000
321
≥≥≥
Итак, получаем математическую модель задачи:
,yyyW min240400260
321
→++
=
⎪
⎪
⎩
⎪
⎪
⎨
⎧
≥++
≥++
≥+
≥++
,yyy
,yyy
,yy
,yyy
522
23
42
122
321
321
21
321
,,iy
i
)31(0 =≥
которую называют
двойственной к задаче оптимального вы-
пуска продукции из имеющихся ресурсов.
Компоненты
*
3
*
2
*
1
,, yyy
оптимального плана
),,(
*
3
*
2
*
1
*
yyyY
называют
оптимальными оценками ресурсов. Это оценки ре-
сурсов в условиях конкретной задачи. Одни и те же ресурсы для
разных предприятий представляют различную ценность. Измене-
ние запасов ресурсов приводит к необходимости их переоценки.
Следуя Л.В. Канторовичу, будем называть их
объективно обу-
словленными оценками
.
Оптимальные решения прямой и двойственной задач будут
найдены позже.
7.2. Правила построения двойственных задач
Рассмотрим модель ЗЛП в общей форме, в которой ограни-
чения образуют смешанную систему, состоящую из неравенств и
равенств, а переменные разделяются на свободные и несвобод-
ные, т.е. задачу:
max...
11
→
+
+
=
nn
xcxcZ
при ограничениях-неравенствах:
),...,,1(...
11
kibxaxa
inini
=
≤
+
+
при ограничениях-равенствах:
),...,,1(...
11
nkibxaxa
inini
+
=
=
+
+
при неотрицательных переменных:
),...,,1(0 tjx
j
=
≥
при свободных переменных:
х
j
<
>
0 (j = t +1,…,n).
Двойственной к данной
прямой (исходной) задаче называют за-
дачу:
min...
11
→
+
+
=
mm
ybybW
при неотрицательных переменных:
),...,,1(0 kiy
i
=
≥
при свободных переменных:
i
y
<
>
),m...,,ki( 10
+
=
при ограничениях-неравенствах: 
                  Z = x1 + 4 x2 + 2 x3 + 5 x4 → max ,               которую называют двойственной к задаче оптимального вы-
                                                                    пуска продукции из имеющихся ресурсов.
                     ⎧ 2 x1 + x2 + 3 x3 + x4 ≤ 260 ,
                     ⎪                                                  Компоненты y1* , y 2* , y 3* оптимального плана Y * ( y1* , y 2* , y 3* )
                     ⎨ x1 + 2 x2 + x3 + 2 x4 ≤ 400 ,                называют оптимальными оценками ресурсов. Это оценки ре-
                     ⎪2x +         x3 + 2 x4 ≤ 240 ,
                     ⎩ 1                                            сурсов в условиях конкретной задачи. Одни и те же ресурсы для
                                x j ≥ 0 ( j = 1,4).                 разных предприятий представляют различную ценность. Измене-
                                                                    ние запасов ресурсов приводит к необходимости их переоценки.
    Поставим в соответствие первому ресурсу оценку y1, второ-       Следуя Л.В. Канторовичу, будем называть их объективно обу-
му – y2, третьему – y3. Тогда общая оценка ресурса, используемого   словленными оценками.
на производство продукции, составит:                                    Оптимальные решения прямой и двойственной задач будут
                      W = 260 y1 + 400 y2 + 240 y3 .                найдены позже.
    Цель задачи – минимизировать эту величину.                                7.2. Правила построения двойственных задач
    Суммарная оценка ресурса, необходимого для производства
единицы продукции А, равна                                              Рассмотрим модель ЗЛП в общей форме, в которой ограни-
                              2 y1 + y 2 + 2 y 3 .                  чения образуют смешанную систему, состоящую из неравенств и
                                                                    равенств, а переменные разделяются на свободные и несвобод-
    Согласно условию задачи эта величина должна быть не
                                                                    ные, т.е. задачу:
меньше цены единицы продукции А, т.е.
                                                                                              Z = c1 x1 + ... + c n x n → max
                            2 y1 + y 2 + 2 y 3 ≥ 1 .
                                                                    при ограничениях-неравенствах:
    Из аналогичных соображений получаем:
                                                                                      ai1 x1 + ... + ain x n ≤ bi (i = 1, ..., k ),
                           ⎧ y1 + 2 y2 ≥ 4,
                           ⎪                                        при ограничениях-равенствах:
                           ⎨ 3 y1 + y2 + y3 ≥ 2 ,                                  ai1 x1 + ... + ain x n = bi (i = k + 1, ..., n),
                           ⎪ y + 2 y + 2 y ≥ 5.                     при неотрицательных переменных:
                           ⎩ 1        2      3

    Естественно предположить, что оценки y1, y2, y3 неотрица-                                   x j ≥ 0 ( j = 1, ..., t ),
тельны, т.е. y1 ≥ 0 , y2 ≥ 0 , y3 ≥ 0.                              при свободных переменных:
    Итак, получаем математическую модель задачи:                                        хj <> 0     (j = t +1,…,n).
                W = 260 y1 + 400 y 2 + 240 y 3 → min ,               Двойственной к данной прямой (исходной) задаче называют за-
                                                                                                   дачу:
                         ⎧ 2 y1 + y2 + 2 y3 ≥ 1,                                       W = b1 y1 + ... + bm y m → min
                         ⎪⎪ y1 + 2 y2 ≥ 4,                          при неотрицательных переменных:
                          ⎨
                          ⎪ 3 y1 + y2 + y3 ≥ 2,                                             y i ≥ 0 (i = 1, ..., k ),
                          ⎪⎩ y1 + 2 y2 + 2 y3 ≥ 5,                  при свободных переменных:
                                                                                         y i <> 0 ( i = k + 1, ...,m ),
                              yi ≥ 0 (i = 1,3) ,
                                                                    при ограничениях-неравенствах:
                                   91                                                                       92

Страницы