Численные методы оптимизации. Рейзлин В.И. - 60 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

60
Задача 4: Систему ограничений-неравенств (7.8) заменяем системой
11 1 12 2 1 3
21 1 22 2 2 4
31 1 32 2 3 5
41 1 42 2 4 6
51 1 52 2 5 7
,
,
,
,
.
a x a x b x
a x a x b x
a x a x b x
a x a x b x
a x a x b x
(7.18)
ограничений-равенств. Минимизируемая форма
1 1 2 2
F c x c x
остается без из-
менения.
Часто оказывается полезным, а для некоторых целей (например, для гео-
метрического толкования) необходимым свести основную задачу линейного
программирования к другой, эквивалентной ей задаче. Все ограничения этой эк-
вивалентной задачи состоят только из неравенств. К рассмотрению этой задачи
мы и переходим.
7.3. Основная задача линейного программирования с
ограничениями-неравенствами
Рассмотрим систему (7.10) ограничений-равенств основной задачи и рас-
смотрим случай
rn
(r – ранг системы, n – число неизвестных). Из линейной
алгебры известно, что в этом случае r неизвестных линейно выражаются через
остальные
rnk
неизвестных (эти последние принято называть свободными).
Всегда можно занумеровать неизвестные так, чтобы последние
1
,...,
kn
xx
выра-
зились через первые
1
,...,
k
xx
(поскольку
n k r
, то неизвестных
1
,...,
kn
xx
в
точности r штук).
1 11 1 12 2 1 1
2 21 1 22 2 2 2
1 1 2 2
,
,
...........................................................
.
k k k
k k k
n r r rk k r
x x x x
x x x x
x x x x
(7.19)
Система (7.19) эквивалентна системе (7.10).
Если теперь вместо величин
1
,...,
kn
xx
в выражении для формы F подста-
вить их значения из (7.19), то форма
примет другой вид:
0 1 1
...
kk
F x x
, (7.20)
то есть по-прежнему остается линейной, но выразится только через свободные
неизвестные
1
,...,
k
xx
.
Решая основную задачу, мы ограничиваемся лишь неотрицательными ре-
шениями системы (10) (или системы (7.19)). Поэтому с необходимостью должны
выполняться неравенства
0,( 1,2,..., )
i
x i k
. (7.21)

Страницы