Методы оптимизации. Харчистов Б.Ф. - 29 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

29
дующем.
1. Ограничения задачи КП преобразуются к виду
.,1,0)(
mixg
i
=≤
2. Составляется функция Лагранжа
∑
=
+=
m
i
ii
xgxfxL
1
).()(),(
λλ
3. Находятся частные производные ;,1,
nj
x
L
j
=
∂
∂
,
i
L
λ
∂
∂
mi
,1
=
, и составляются условия Куна
−
Таккера (3.1)
−
(3.6).
4. Посредством введения дополнительных переменных
miwnjv
ij
,1 , ;,1 ,
==
, неравенства
0 ,0
≤
∂
∂
≥
∂
∂
ij
L
x
L
λ
преобразуются в равенства
,0 ,0
=+
∂
∂
=−
∂
∂
i
i
j
j
w
L
v
x
L
λ
в результате получается система (3.7)
−
(3.12).
5. Вводятся искусственные переменные
l
z
, с оставляется
вспомогательная задача ЛП минимизации
∑
=
l
l
zzF
)( при огра-
ничениях (3.7)
−
(3.12) с введенными неотрицательными искусст-
венными переменными.
6. Решается вспомогательная задача ЛП симплекс-
методом с учетом условий до полняющей нежесткости.
Если в результате решения ,0)(min
=zF
z
то оптимальное
допустимое базисное решение вспомогательной задачи определя-
ет решение
*
x
задачи КП.
Если ,0)(min
>zF
z
то задача КП не имеет решения.
Пример
. Решить следующую задачу КП:
min,64222)(
21
2
221
2
1
→−−++= xxxxxxxf

Страницы