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

UptoLike

ВУЗ: 

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

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

Рубрика: 

106
4. Выбирается (произвольно) одна из нецело численных
компонент
)(
ν
r
x , осуществляется ветвление по переменной
r
x ,
составляются задачи
12
−
k
L и
k
L
2
.
5. Решается задача .2,12, k kj L
j
−=
Если задача
j
L не имеет решения, то полагается −∞=
j
ξ
,
1
−
Θ=Θ
jj
и осуществляется (при j=2k) переход к п. 7.
6. Находится
)(
j
x , вычисляется )(
)(
jj
xf=
ξ
.
Если решение
)(
j
x является целочисленным, то полагается
},max{
1
jjj
ξ
−
Θ=Θ и осуществляется (при j = 2k) переход к п. 7.
Если решение
)(
j
x не является целочисленным, то полага-
ется
1
−
Θ=Θ
jj
и осуществляется (при j = 2k) переход к п. 7.
7. Просматриваются вершины из I и прекращается ветвле-
ние, если выполняется условие
ki
2
Θ≤
ξ
, i ∈ I.
8. Проверяется условие окончания вычислений
I = ∅.
Если оно выполняется, то полагается
k
f
2
Θ=
∗
,
)(
ν
xx
=
∗
,
где
)(
ν
x определяется из условия
k
xf
2)(
)( Θ=
ν
, и вычисления за-
вершаются.
Если условие не выполняется, то полагается k = k +1 и
осуществляется переход к п. 3.
Пример. Решить методом ветвей и границ следующу ю
целочисленную задачу ЛП:
max32)(
21
→+= xxxf ,
3575
21
≤+ xx ,
3694
21
≤+ xx ,
0
1
≥x , 0
2
≥x ,
21
, x x − целые.

Страницы