Составители:
Рубрика:
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.
Страницы
- « первая
- ‹ предыдущая
- …
- 44
- 45
- 46
- 47
- 48
- …
- следующая ›
- последняя »
