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

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

74
7. СИМПЛЕКС МЕТОД ИЛИ МЕТОД ПОСЛЕДОВАТЕЛЬНОГО
УТОЧНЕНИЯ ОЦЕНОК
Метод предназначен для решения общей задачи линейного программиро-
вания.
Пусть имеем следующую задачу:
1 1 2 2
... min
nn
Q x c x c x c x
,
с системой ограничений следующего вида:
11 1 12 2 1 1
1 1 2 2
... ,
..................................................
... .
nn
m m mn n m
a x a x a x b
a x a x a x b
Разрешим эту систему относительно переменных
1
,...,
m
xx
:
' ' '
1 1, 1 1 1, 1
' ' '
, 1 1 ,
... ,
....................................................
... .
m m n n
m m m m m n n m
x a x a x b
x a x a x b


(7.3)
Векторы условий, соответствующие
1
,...,
m
xx
, образуют базис. Переменные
1
,...,
m
xx
назовем базисными переменными. Остальные переменные задачи –
небазисные.
Целевую функцию можно выразить через небазисные переменные:
' ' ' '
1 1 2 2 0
... min
m m m m n n
Q x c x c x c x c
.
Если приравнять небазисные переменные нулю
12
0, 0, ...; 0
m m n
x x x

,
то соответствующие базисные переменные примут значения
' ' '
1 1 2 2
; ; ...;
mm
x b x b x b
.
Вектор
с такими компонентами представляет собой угловую точку мно-
гогранника решений (допустимую) при условии, что
'
0
i
b
(опорный план).
Теперь необходимо перейти к другой угловой точке с меньшим значением
целевой функции. Для этого следует выбрать некоторую небазисную перемен-
ную и некоторую базисную так, чтобы после того, как мы «поменяем их места-
ми», значение целевой функции уменьшилось. Такой направленный перебор в
конце концов приведет нас к решению задачи.

Страницы