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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

5
Алгоритмическая схема метода
Решается задача вида:
0
min)(
Ω∈
→
x
x
ϕ
.
Шаг 1. Инициализация.
Задать начальное рекордное значение R. Если отыскание начального рекорда
затруднительно , положить R=
∞
+
. Положить
=
I
Ø – множество номеров под-
множеств , подлежащих ветвлению ,
}
0
{
=
-множество номеров подмножеств ,
для которых будут решаться оценочные задачи .
Шаг 2. Вычисление оценок.
Решить оценочные задачи для множеств ,
j
Ω
где
j
∈
. Вычислить ,)(
Jj
ξ
ξ
=
Ω
.
j
∈
Шаг 3. Обновление рекорда.
Если на шаге 2 получены допустимые точки Ppx
p
,1, = , то положить
R=
)}(min,min{
p
p
xR ϕ
.
Шаг 4. Сокращение перебора.
Осуществить закрытие неперспективных множеств (включая те номера
i
, для
которых R
=
i
ξ
). Удалить их номера из множеств I и J . Положить
I
I
∪
=
,
=
J
Ø . Если
I
Ø , то перейти к шагу 7.
Шаг 5. Реализация стратегии.
Выбрать из множества I номер k – индекс подмножества
k
Ω
, подлежащего
ветвлению на данном этапе в соответствии с зафиксированным правилом.
Шаг 6. Ветвление.
Осуществить разбиение множества
k
Ω
на подмножества
Υ
Ss
kk
s
,1=
Ω
=
Ω
. Поло -
жить },1,{ SskJJ
s
=∪= . Перейти к шагу 2.
Шаг 7. Останов,
=
min
ϕ
R.
УПРАЖНЕНИЯ
1. Докажите свойство монотонности оценок в условиях , при которых ветвление
и составление оценочных задач осуществляется по правилам , указанным в п.п.
1 и 2.
2. Предложите другие стратегии обхода дерева вариантов.
3. Докажите , что при использовании основного правила отбрасывания непер -
спективных множеств (п .4) не происходит потери решения.
4. В предложенной алгоритмической схеме отыскивается одно решение, даже
если решение в задаче не единственно . Где происходит потеря решения ? Ис-
правьте алгоритм таким образом, чтобы появилась возможность отыскания всех
решений задачи . 
                                                5
                            Алгоритмическая схема метода

Решается задача вида:         ϕ ( x ) → min .
                                       x∈Ω0
Шаг 1. Инициализация.
Задать начальное рекордное значение R. Если отыскание начального рекорда
затруднительно, положить R= +∞ . Положить I =Ø – множество номеров под-
множеств, подлежащих ветвлению, J ={0} -множество номеров подмножеств,
для которых будут решаться оценочные задачи.
Шаг 2. Вычисление оценок.
Решить оценочные задачи для множеств Ω j , где j ∈J . Вычислить ξ (Ω j ) =ξ J ,
 j ∈J .
Шаг 3. Обновление рекорда.
Если на шаге 2 получены допустимые точки x p , p =1, P , то положить
R= min{R, min ϕ( x p )} .
             p
Шаг 4. Сокращение перебора.
Осуществить закрытие неперспективных множеств (включая те номера i , для
которых ξi =R ). Удалить их номера из множеств I и J. Положить I =I ∪ J ,
J =Ø. Если I =Ø, то перейти к шагу 7.
Шаг 5. Реализация стратегии.
Выбрать из множества I номер k – индекс подмножества Ω k , подлежащего
ветвлению на данном этапе в соответствии с зафиксированным правилом.
Шаг 6. Ветвление.
Осуществить разбиение множества Ω k на подмножества Ω k = Υ Ω ks . Поло-
                                                                s =1, S

жить J =J ∪ {k s , s =1, S} . Перейти к шагу 2.
Шаг 7. Останов, ϕmin =R.

                                    УПРАЖНЕНИЯ

1. Докажите свойство монотонности оценок в условиях, при которых ветвление
и составление оценочных задач осуществляется по правилам, указанным в п.п.
1 и 2.
2. Предложите другие стратегии обхода дерева вариантов.
3. Докажите, что при использовании основного правила отбрасывания непер-
спективных множеств (п.4) не происходит потери решения.
4. В предложенной алгоритмической схеме отыскивается одно решение, даже
если решение в задаче не единственно. Где происходит потеря решения? Ис-
правьте алгоритм таким образом, чтобы появилась возможность отыскания всех
решений задачи.

Страницы