Дискретная оптимизация - 12 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

12
§ 3. Метод ветвей и границ для линейных задач целочисленного
программирования
Рассмотрим целочисленную задачу линейного программирования (ЦЗЛП):
∑
=
→=
n
j
jj
xcx
1
min)( ϕ
=Ζ∈≤≤
=≤
Ω
∑
=
.,1,,0
,,1,
1
0
njxdx
mibxa
jjj
n
j
ijij
Процесс получения решения задачи начинается с решения соответствующей ей
оценочной задачи линейного программирования с отброшенным условием це-
лочисленности . Если полученная при этом оптимальная точка
0
x
имеет только
целые координаты , то она является решением исходной задачи . В противном
случае значение )(
0
x ϕ дает нижнюю оценку целевой функции.
Конкретизируем основные этапы метода ветвей и границ применительно к
данной задаче.
1) Ветвление. Пусть ),...,(
1
k
n
kk
xxx = - оптимальная точка в оценочной задаче
на множестве
k
Ω
. Если
k
x
удовлетворяет требованиям целочисленности ,
то множество
k
Ω
исключается из дальнейшего рассмотрения (найдено
оптимальное решение на нем ). Значение
)(
k
x ϕ
сравнивается с рекордным
(при этом возможно смена рекорда). Если же есть не целая компонента
k
j
x
, то множество
k
Ω
разбивается на два подмножества следующим обра-
зом:
21
kkk
Ω
∪
Ω
=
Ω
,
]}[,{
1
k
jjkk
xxx ≤Ω∈=Ω
,
}1][,{
2
+≥Ω∈=Ω
k
jjkk
xxx
,
где символом
]
[
⋅
обозначена целая часть числа.
2) Вычисление оценок . Оценочной задачей на множестве
k
Ω
будет являться
задача, в которой отброшено требование целочисленности переменных.
При решении оценочной задачи получаем оптимальную точку
k
x
. Зна-
чение
)(
k
x ϕ
дает нижнюю оценку множества
k
Ω
(можно в качестве
оценки брать целую часть )(
k
x ϕ ).
Правило обхода дерева вариантов, выбор перспективного множества при ветв -
лении и проверка критерия оптимальности осуществляются аналогично общей
схеме метода ветвей и границ .
Схема работы метода ветвей и границ для ЦЗЛП
Шаг 1. Определение начального рекорда. (При отсутствии дополнительной ин-
формации R=
∞
+
). Задать k =0. 
                                                      12
 § 3. Метод ветвей и границ для линейных задач целочисленного
                       программирования

Рассмотрим целочисленную задачу линейного программирования (ЦЗЛП):
                                                n
                                      ϕ( x) =∑ c j x j → min
                                               j =1

                                  �   n

                                  �   ∑ aij x j ≤b i , i =1, m,
                              Ω0 �    j =1
                                  � 0 ≤x ≤d , x ∈Ζ, j =1, n.
                                   �    j  j   j

Процесс получения решения задачи начинается с решения соответствующей ей
оценочной задачи линейного программирования с отброшенным условием це-
лочисленности. Если полученная при этом оптимальная точка x 0 имеет только
целые координаты, то она является решением исходной задачи. В противном
случае значение ϕ ( x 0 ) дает нижнюю оценку целевой функции.
Конкретизируем основные этапы метода ветвей и границ применительно к
данной задаче.
   1) Ветвление. Пусть x k =( x1k ,..., xnk ) - оптимальная точка в оценочной задаче
      на множестве Ω k . Если x k удовлетворяет требованиям целочисленности,
      то множество Ω k исключается из дальнейшего рассмотрения (найдено
      оптимальное решение на нем). Значение ϕ ( x k ) сравнивается с рекордным
      (при этом возможно смена рекорда). Если же есть не целая компонента
       x kj , то множество Ω k разбивается на два подмножества следующим обра-
      зом: Ω k =Ω k1 ∪ Ω k2 , Ω k1 ={x ∈Ω k , x j ≤[ x kj ]} , Ω k2 ={x ∈Ω k , x j ≥[ x kj ] +1} ,
      где символом [⋅] обозначена целая часть числа.
   2) Вычисление оценок. Оценочной задачей на множестве Ω k будет являться
      задача, в которой отброшено требование целочисленности переменных.
      При решении оценочной задачи получаем оптимальную точку x k . Зна-
      чение ϕ ( x k ) дает нижнюю оценку множества Ω k (можно в качестве
      оценки брать целую часть ϕ ( x k ) ).

Правило обхода дерева вариантов, выбор перспективного множества при ветв-
лении и проверка критерия оптимальности осуществляются аналогично общей
схеме метода ветвей и границ.

                Схема работы метода ветвей и границ для ЦЗЛП

Шаг 1. Определение начального рекорда. (При отсутствии дополнительной ин-
формации R= +∞ ). Задать k=0.

Страницы