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

UptoLike

ВУЗ: 

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

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

Рубрика: 

105
Θ
Θ
=Θ
−
ным.целочисленявляетсяесли}max{
нымцелочисленявляетсяне
либорешенияимеетнезадачаесли
)(
)(1
,
ννν
ν
ν
ν
ν
ξ
x,,
;
xL
1-
При этом −∞≡Θ
0
.
Ветвление на k-м, k = 1,2,.., этапе из i-й, i ∈ I, вершины
следует прекратить, если верхняя граница
i
ξ
целевой функции
для задачи
i
L не больше известной на данном шаге нижней гра-
ницы
k
2
Θ целевой функции для целочисленного решения. Про-
цесс решения завершается, когда отсутствуют вершины, из кото-
рых возможно ветвление, т.е. I = ∅. При этом оптимальное зна-
чение
k
f
2
Θ=
∗
, решение
)(
ν
xx =
∗
, где
)(
ν
x определятся из усло-
вия
k
xf
2)(
)( Θ=
ν
.
Итак, алгоритм решения целочисленной задачи ЛП методом
ветвей и границ заключается в следующем.
1. Ре шается задача ЛП L
0
.
Если задача
0
L не имеет решения, то исходная задача не
имеет целочисленного решения и вычисления завершаются.
2. Находится решение
)0(
x , вычисляется верхняя граница
)(
)0(0
xf=
ξ
.
Если решен ие
)0(
x
является целочисленным, то полагается
)0(
xx
=
∗
,
0
ξ
=
∗
f и вычисления завершаются.
Если решение
)0(
x не является целочисленным, то полага-
ется −∞=Θ
0
, k=1 и осуществляется переход к п. 3.
3. Выбирается для ветвления
ν
-я вершина из I, для которой
выполняется условие
i
Ii
ξξ
ν
∈
= max .

Страницы