Прогнозирование устойчивости. Жигулин Г.П - 114 стр.

UptoLike

ВУЗ: 

Университет ИТМО | Санкт-Петербург

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

Рубрика: 

116
6.1.3. Каноническая форма задач линейного программирования
Задача линейного программирования записана в канонической форме, если
она формулируется таким образом: найти минимум линейной формы
∑
=
=
n
j
jj
xcL
1
(6.19.)
при условиях:
mibxa
i
n
j
jij
,1,
1
==
∑
=
,
(6.20.)
njx
j
,1,0 =≥ .
(6.21.)
Встает вопрос: как от общей записи задачи (6.15)÷(6.19) перейти к
канонической форме?
Из условий (6.15.)÷(6.19.) видно, что для перехода к канонической форме
необходимо от ограничений-неравенств (6.18.) перейти к ограничениям-
равенствам. В условия (6.3.) введем дополнительные неотрицательные
переменные
0≥
j
x
, для
)(,,1 kmnnj −++=Κ
.
Тогда ограничения (6.3) можно представить в виде равенств:
⎪
⎪
⎭
⎪
⎪
⎬
⎫
=++++
=++++
=++++
−+
+++++
+++++
.
,
,
)(2211,
22,222,211,2
11,122,111,1
mkmnnmnmm
knnnkkk
knnnkkk
bxxaxaxa
bxxaxaxa
bxxaxaxa
Κ
ΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛ
Κ
Κ
(6.22.)
В линейную форму эти дополнительные переменные входят с нулевыми
коэффициентами.
1. Если
nn =
1
, (
1
n – число неотрицательных переменных в общей задаче
ЛП), то общая задача уже сведена к канонической форме.
2. Если
nn <
1
:
2.1. Если структуру условий задачи нежелательно изменять, то все
),,1(
1
nnjx
j
Κ+= необходимо заменить разностью неотрицательных
переменных
j
x
′
и
j
x
′′
:
jjj
xxx
′
′
−
′
=
,
(6.23.)
где
0;0 ≥
′′
≥
′
jj
xx .
Такая замена (6.20.) приводит к существенному росту общего числа
переменных.

Страницы