Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Сигал И.Х. -> "Введение в прикладное дискретное программирование " -> 49

Введение в прикладное дискретное программирование - Сигал И.Х.

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 43 44 45 46 47 48 < 49 > 50 51 52 53 54 55 .. 84 >> Следующая


Стратегия решения, подтвержденная обширным вычислительным экспериментом, такова. Выбирая большое значение S, получаем некоторое количество рекордов, которые, как правило, улучшить не удается. Постепенно уменьшая S, реализуем комбинированный выбор,

и, полагая S = 0, переходим к фронтальному выбору.

5.3.2. Глобальные подходы. Переход к ^-оптимизации.

Глобальные подходы повышения эффективности следует искать путем перехода от поиска точного решения к г-оптимизации. Рассмотрим задачу о ранце. Основной результат для этой задачи состоит в том, что переход к г-оптимизации переводит задачу о ранце из класса NP в класс Р, т.е. при г-оптимизации наблюдается полиномиальный рост числа вершин дерева ветвления. Этот результат представляет лишь академический интерес, так как степень полинома, описывающего рост числа вершин дерева ветвления, оценивается величиной порядка 1/г. Вычислительная реализация алгоритма подобного типа не представляется тривиальной.

Алгоритм ветвей и границ при нахождении точного решения общей задачи дискретной оптимизации (5.1.1) позволяет получить последовательность приближенных решений (рекордов) X1, ж2,. . . , Xk, . . . таких, что

/(^1) >f(x2) >--->f(xh) >...,

при этом

Wo < / (х°) < / (хк) . (5.3.1)

Таким образом, задача (5.1.2) оказывается решенной с применением алгоритма поиска точного решения, как только / (хк) — Wo < г, так как / (хк) — / (ж0) < / (хк) — Wq < г. Если алгоритм ориентиро-
Гл. 5. Постановка задачи о поиске приближенного решения 143

вать с самого начала на поиск приближенного решения ж* с условием (5.1.2) или (5.1.3), то это может усилить отсев и повысить сходимость алгоритма при решении конкретных задач.

Опишем алгоритм поиска г-оптимального решения х* в соответствии с 5.1.2. Пусть G разбито на г подмножеств (?, еще не под-

г

вергавшихся разбиению: G= IJ Gi, Gi Q Gj = 0 при г ф j. Пусть

Ї G G — рекорд и ip (Gk) — нижняя оценка для Gk в методе ветвей и границ. Правило отсева в алгоритме поиска точного решения имеет вид (р (Gk) > / (х). Перепишем это правило в виде f (х) — <р (Gk) < 0.

Теорема 5.1. Правило отсева f (х) — (р (Gk) < є гарантирует получение є-оптимального решения х*.

Доказательство. Пусть оптимальное решение х° є Gk- Если множество Gk не отсеяно, то в процессе решения получено оптимальное решение. Пусть множество Gk отсеяно. Покажем, что х* = х. По определению оценки имеем f(x°) > Ip(Gk) > f(x) — є, т.е. / (х) — —/ (ж0) < є. Поскольку в процессе решения рекорд X может только улучшиться, то разность / (х) — / (ж0) может только уменьшиться, поэтому X = ж*, аж — г-оптимальное решение. Теорема доказана.

Следует отметить, что различные типы TVP-полных задач ведут себя по-разному при переходе к г-оптимизации. Для задачи коммивояжера поиск г-приближенного решения (5.1.2) или (5.1.3) представляет собой TVP-трудную задачу, если P ф NP. Для задачи о ранце поиск г-приближенного решения (5.1.3) есть задача из класса Р. Для общей задачи (5.1.1) результаты о глобальном повышении эффективности неизвестны. Поэтому представляет большой интерес выделение классов NP-трудных задач, для которых переход к г-оптимизации делает их полиномиально разрешимыми.

5.4. s-оптимальный алгоритм ветвей и границ для задачи о ранце

5.4.1. Постановка задачи и алгоритм. Нахождение точного решения задачи с применением алгоритма ветвей и границ требует значительных вычислительных ресурсов. При этом для хранения информации о дереве ветвления может потребоваться большой объем памяти. Отметим также, что в процессе работы алгоритма на каждом шаге процесса ветвления известна оценка отклонения приближенного решения (рекорда) от оптимума. Интуитивно представляются естественными следующие предположения. Если алгоритм ориентировать с самого начала на нахождение г-приближенных решений, то это может привести к усилению отсева. При этом сократится информация о дереве ветвления и уменьшится число решаемых подзадач.
144

Разд. III. Приближенные методы и алгоритмы

Рассмотрим задачу в следующем виде:

п

(5.4.1)

j=i

п

Yai3x3^bi, і = 1,2,... ,т, і=і

(5.4.2)

Xj Є {0; 1}, j = 1,2,...,11,

(5.4.3)

Cj >0, j = 1,2,...,п,

(5.4.4)

bi > 0, і = 1,2,..., то,

(5.4.5)

0 <aij<bi, г = 1,2,...,то, j = 1,2,...,п,

Yan >Ьі' і = 1,2,...,т,

J=і

П

(5.4.6)

(5.4.7)

(5.4.8)

Предполагается также, что т < п.

Зададим 0 < є < I — верхнюю границу относительной погрешности искомого приближенного решения задачи, х° — оптимальное решение.

Определение. Приближенное решение х назовем г-оптималъ-

Определение. Алгоритм решения задачи назовем є-оптимальным, если он гарантирует получение г-оптимального решения.

Отметим основные особенности г-оптимального алгоритма.

1. Изменяется правило отсева подмножеств, не содержащих оптимальных решений.

2. Конкретизируется способ выбора переменной для ветвления.

3. Нецелочисленное решение задачи-кандидата округляется и сравнивается с рекордом. Если округленное решение лучше рекорда, то оно становится новым рекордом.
Предыдущая << 1 .. 43 44 45 46 47 48 < 49 > 50 51 52 53 54 55 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100