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

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

82
граммирования зацикливание явлеется довольно редким, возможность его не ис-
ключена.
Один из приемов борьбы с вырожденностью состоит в преобразовании за-
дачи путем «незначительного» изменения вектора правых частей системы огра-
ничений на величины
i
таким образом, чтобы задача стала невырожденной, и, в
то же время, чтобы это изменение не повлияло реально на оптимальный план за-
дачи.
Чаще реализуемые алгоритмы включают в себя некоторые простые прави-
ла, снижающие вероятность возникновения зацикливания или его преодоления.
Пусть переменную
j
x
необходимо сделать базисной. Рассмотрим множе-
ство индексов
0
E
, состоящее из тех
i
, для которых достигается
0
min 0
ii
i
il il
bb
aa





. Множество индексов
i
, для которых выполняется данное
условие обозначим через
0
E
. Если
0
E
состоит из одного элемента, то из базиса
исключается вектор условий
i
A
(переменная
i
x
делается небазисной).
Если
0
E
состоит более чем из одного элемента, то составляется множество
1
E
, которое состоит из
0
iE
, на которых достигается
. Если
1
E
состоит из одного индекса
k
, то из базиса выводится переменная
k
x
. В против-
ном случае составляется множество
2
E
и т.д.
Практически правилом надо пользоваться, если зацикливание уже обна-
ружено.
7.3. Двойственность задачи линейного программирования
Рассмотрим задачу (7.1) максимизации линейной формы и, одновременно,
задачу (7.2) минимизации:
max,
,
0,
Q x p x
A x b
x

(7.1)
min,
,
0.
W u b u
x
A x p
u

(7.2)
Задача (7.2) называется двойственной по отношению к прямой (7.1) (и
наоборот).

Страницы