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

UptoLike

ВУЗ: 

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

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

Рубрика: 

93 94
),...,,1(...
11
tjcyaya
jmmjj
=
≥
+
+
при ограничениях-равенствах:
),...,,1(...
11
ntjcyaya
jmmjj
+
=
=
+
+
т.е. задачу, получаемую из исходной по следующим правилам:
1. Количество переменных двойственной задачи равно
m –
числу ограничений исходной задачи, а число ограничений двой-
ственной задачи равно
n – количеству переменных исходной за-
дачи.
2. Свободные члены
),1( mib
i
= исходной задачи являются ко-
эффициентами целевой функции двойственной задачи, а коэффици-
енты
),1( njс
j
= целевой функции исходной задачи становятся
правыми частями системы ограничений двойственной задачи.
3. Матрицей коэффициентов системы ограничений двойст-
венной задачи служит матрица A
T
, получаемая транспонировани-
ем матрицы А коэффициентов системы ограничений исходной
задачи.
4. Каждому ограничению-неравенству:
),1(...
11
kibxaxa
inini
=≤++
исходной задачи соответствует неотрицательная переменная:
),1(0 kiy
i
=≥
двойственной задачи, а каждому ограничению-равенству:
),1(...
11
mkibxaxa
inini
+==++
соответствует свободная переменная:
y
i
<
>
0 )1( m,ki +=
двойственной задачи.
5. Каждой неотрицательной переменной
),1(0 tjx
j
=≥ пря-
мой задачи соответствует ограничение-неравенство:
),1(...
11
tjcyaya
jmmjj
=≥++
двойственной задачи с тем же знаком неравенства, а каждой сво-
бодной переменной х
j
<
>
0 )1( n,tj += соответствует ограничение-
равенство:
)1(
11
n,tjcya...ya
jmmjj
+==++
двойственной задачи.
6. Максимизация целевой функции исходной задачи заменя-
ется минимизацией целевой функции двойственной задачи.
Параллельная запись обеих задач выглядит следующим образом:
Исходная задача Двойственная задача
max...
11
→
+
+
=
nn
xcxcZ min...
11
→
+
+
=
mm
ybybW
inini
bxaxa
≤
+
+
...
11
)1( k,i = 0≥
i
y )1( k,i =
inini
bxaxa
=
+
+
...
11
),1( mki +=
y
i
<
>
0
)1( m,ki +=
0≥
j
x
),1( tj =
jmmjj
cyaya ≥
+
+
...
11
)1( t,j =
x
j
<
>
0
),1( ntj +=
jmmjj
cyaya
=
+
+
...
11
)1( n,tj +=
Нетрудно проверить (убедитесь самостоятельно!), что ис-
ходную задачу можно рассматривать как
двойственную по
отношению к своей двойственной
, т.е. обе задачи являются
взаимно двойственными. Поэтому принято говорить о
паре
двойственных (сопряженных) задач.
7.3. Симметричные двойственные задачи
Пусть модель исходной ЗЛП задана в стандартной форме:
).,1(0
,
,
,
max,
2211
22222121
11212111
2211
njx
bxaxaxa
bxaxaxa
bxaxaxa
xсxсxсZ
j
mnmnmm
nn
nn
nn
=≥
⎪
⎪
⎩
⎪
⎪
⎨
⎧
≤+++
≤+++
≤+++
→
+
+
+
=
L
LLLLLLL
L
L
L
(7.1)
Составим модель двойственной ЗЛП, используя правила, из-
ложенные в п. 7.2. 
              a1 j y1 + ... + a mj y m ≥ c j ( j = 1, ..., t ),                         a1 j y1 + ... + amj ym = c j    ( j = t + 1, n)
при ограничениях-равенствах:                                          двойственной задачи.
            a1 j y1 + ... + a mj y m = c j ( j = t + 1, ..., n),           6. Максимизация целевой функции исходной задачи заменя-
т.е. задачу, получаемую из исходной по следующим правилам:            ется минимизацией целевой функции двойственной задачи.
      1. Количество переменных двойственной задачи равно m –
числу ограничений исходной задачи, а число ограничений двой-          Параллельная запись обеих задач выглядит следующим образом:
ственной задачи равно n – количеству переменных исходной за-
                                                                              Исходная задача                          Двойственная задача
дачи.
      2. Свободные члены bi (i = 1, m) исходной задачи являются ко-      Z = c1 x1 + ... + c n x n → max           W = b1 y1 + ... + bm y m → min
эффициентами целевой функции двойственной задачи, а коэффици-         ai1 x1 + ... + ain x n ≤ bi (i = 1,k ) y i ≥ 0 (i = 1,k )
енты с j ( j = 1, n) целевой функции исходной задачи становятся
                                                                      ai1 x1 + ... + ain xn = bi (i = k + 1, m) yi <> 0 (i = k + 1,m)
правыми частями системы ограничений двойственной задачи.
    3. Матрицей коэффициентов системы ограничений двойст-              x j ≥ 0 ( j = 1, t )                     a1 j y1 + ... + a mj y m ≥ c j ( j = 1,t )
венной задачи служит матрица AT, получаемая транспонировани-
                                                                       xj <> 0 ( j = t + 1, n)                  a1 j y1 + ... + amj ym = c j ( j = t +1,n)
ем матрицы А коэффициентов системы ограничений исходной
задачи.                                                                   Нетрудно проверить (убедитесь самостоятельно!), что ис-
    4. Каждому ограничению-неравенству:                               ходную задачу можно рассматривать как двойственную по
                     ai1 x1 + ... + ain x n ≤ bi (i = 1, k )          отношению к своей двойственной, т.е. обе задачи являются
исходной задачи соответствует неотрицательная переменная:             взаимно двойственными. Поэтому принято говорить о паре
                                                                      двойственных (сопряженных) задач.
                             y i ≥ 0 (i = 1, k )
двойственной задачи, а каждому ограничению-равенству:                              7.3. Симметричные двойственные задачи
               ai1 x1 + ... + ain x n = bi (i = k + 1, m)                  Пусть модель исходной ЗЛП задана в стандартной форме:
соответствует свободная переменная:                                                 Z = с1 x1 + с 2 x 2 + L + с n x n → max,
                           yi <> 0   (i = k + 1,m)                                            ⎧ a11 x1 + a12 x 2 + L + a1n x n ≤ b1 ,
двойственной задачи.                                                                          ⎪ a x + a x +L+ a x ≤ b ,
                                                                                              ⎪ 21 1        22 2            2n n      2
    5. Каждой неотрицательной переменной x j ≥ 0 ( j = 1, t ) пря-                            ⎨                                                       (7.1)
                                                                                              ⎪    L     L    L     L   L    L     L
мой задачи соответствует ограничение-неравенство:                                             ⎪⎩a m1 x1 + a m 2 x 2 + L + a mn x n ≤ bm ,
                  a1 j y1 + ... + a mj y m ≥ c j ( j = 1, t )
двойственной задачи с тем же знаком неравенства, а каждой сво-                                         x j ≥ 0 ( j = 1, n).
бодной переменной хj <> 0 ( j = t + 1,n) соответствует ограничение-       Составим модель двойственной ЗЛП, используя правила, из-
равенство:                                                            ложенные в п. 7.2.

                                        93                                                                         94

Страницы