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

UptoLike

ВУЗ: 

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

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

Рубрика: 

103
11. МЕТОД ВЕТВЕЙ И ГРАНИЦ
Метод ветвей и границ относится к группе комбинато рных
методов дискретного программиро вания и является одним из
наибо лее распространенных методов эт ой группы. Центральную
идею комбинаторных мето дов составляет замена полного пере-
бора допустимого множества X частичным перебором. В случае
метода ветвей и границ это осуществляется путем последова-
тельного разбиения до пустимого множества на подмножества
(ветвления) и вычисления оценок (границ), позволяющих отбра-
сывать подмножества, заведомо не содержащие решения задачи.
При реализации общей схемы метода ветвей и границ для раз-
личных задач дискретного про г раммирования необхо димо, исхо-
дя из специфики этих задач, конкретизировать правила ветвления
и вычисления границ.
На практическом занятии рассматривается метод ветвей и
границ для задачи целочисленного линейного программиро в ания
(ЛП) следую щего вида:
max)(
1
→
∑
=
=
n
j
jj
xcxf ,
i
n
j
jij
bxa
≤
∑
=
1
, mi ,1= ,
0≥
j
x ,
nj
,1
=
,
j
x − целые, nj ,1= .
Допустимое множество Х данной задачи предполагается
ограниченным.
В данно м случае на каждом этапе (шаге) решаются непре-
рывные задачи ЛП: на предварительном (нулевом) этапе – задача
L
0
; на k-м, k = 1, 2,..., этапе − задачи L
2k-1
и L
2k
. Задача
0
L , как и в
методе отсечений, представляет собой исходную задачу без учета
требования целочисленности; задача
ν
L ,
ν
= 1,2,..., получается в
результате добавления к задаче L
0
дополнительных о г раничений.
Верхняя граница (оценка)
ξ
ν
целевой функции f для задачи

Страницы