Математическое программирование (линейное программирование). Киселева Э.В - 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.