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

UptoLike

ВУЗ: 

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

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

Рубрика: 

104
L
ν
,
ν
= 0,1,2,..., определяется следующим образом:
)(
)(
νν
ξ
xf≡ ,
где
()
ν
x − решение задачи
ν
L .
Если задача
ν
L не имеет решения, то полагается −∞≡
ν
ξ
.
В процессе решения строится дерево задач, в котором
ν
-я,
ν
= 0,1,2,..., вершина соответствует задаче
ν
L . Обозначим
через I множество вершин, из которых возможно ветвление. Для
ветвления на k-м, k =1,2,..., этапе выбирается
ν
-я,
ν
∈I, вершина
(задача
ν
L ), которая имеет максимальную верхнюю оценку
ν
ξ
.
Пусть в решении
)(
ν
x некото рая компонента
)(
ν
r
x ,
nr ≤≤1
, не
является целочисленной. Допустимое, т.е. целочисленное, значе-
ние
r
x должно удовлетворять одному из неравенств, представ-
ляющих собой необходимые условия целочисленност и
r
x :
либо ][
)(
ν
rr
xx ≤ , либо 1][
)(
+≥
ν
rr
xx ,
где [a] − целая часть действительного числа а.
В рез ультате задача L
ν
разветвляется (разбивается) на две
не связанные между собой задачи
12
−
k
L и
k
L
2
. Задача
12
−
k
L пред-
ставляет собой задач у
ν
L с дополнительным ог раничением
][
)
(
í
rr
xx ≤ , а задача L
2k
− задачу
ν
L с дополнительным ограниче-
нием 1][
)(
+≥
ν
rr
xx , т.е.
≤
−
];[
,
)(
12
ν
ν
r
k
xx
L
L
+≥ .1][
,
)(
2
ν
ν
r
k
xx
L
L
Для ускорения процесса решения вводится нижняя грани-
ца целевой функции f для целочисленного решения, обозначаемая
Θ
. После решения задачи
ν
L значение
ν
Θ определяется сле-
дующим образом:

Страницы