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

 

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

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

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


Естественным образом возникает необходимость в нахождении приближенного решения задачи (5.1.1). Ставится задача о нахожде-
138

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

нии решения ж* Є G такого, что

f(x*)-f(x°)<? (5.1.2)

ИЛИ

f(x')-f(x°)

f(x О) <*, (5.1.3)

/ (ж0) ф 0, є > 0.

Отметим, что существуют задачи типа (5.1.1), для которых постановки задач (5.1.2) и (5.1.3) являются принципиально различными. Поясним это на примере задачи об одномерном булевом ранце

п

Y cjxj max, j=i

Yl, ajxj < ^ xj є {0? j (5.1.1 )

J=і

Cj > Oj 0 < aj < 6, j = 1, 2,..., п.

Если х° — оптимальное решение этой задачи, ж* — приближенное решение, то постановки (5.1.2) и (5.1.3) соответственно имеют вид

f{x°)-f(x*)<e, (5.1.2')

f(x°) - f{x•) ,

/(x°) - • ( }

Рассматриваемая задача (5.1.1') является NP-трудной, и переход от задачи (5.1.1') к задаче (5.1.2') приводит снова к TVP-трудной задаче. В то же время переход от задачи (5.1.1') к задаче (5.1.3') переводит задачу (5.1.1') из класса NP в класс P1 т.е. задача (5.1.3') полиномиально разрешима. Если P ф NP, то задачи (5.1.2') и (5.1.3') являются принципиально различными. Для задачи коммивояжера переход от постановки (5.1.1) к любой из постановок (5.1.2) или (5.1.3) снова приводит к TVP-трудной задаче (см. подробнее в [6]).

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

Сформулированные здесь соображения касаются задач типа (5.1.1), для которых сравнительно легко находятся допустимые решения: задач о ранце, о коммивояжере в классической постановке, о покрытиях графов и других. Однако существуют задачи типа (5.1.1), для которых нахождение хотя бы одного допустимого решения равносильно
Гл. 5. Постановка задачи о поиске приближенного решения 139

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

Остановимся на некоторых соображениях, связанных с необходимостью перехода от точного решения задачи к приближенному:

— нахождение точного решения задачи может потребовать слишком больших вычислительных ресурсов и связано с преодолением вычислительных трудностей принципиального характера;

— в прикладных задачах математическая модель является, как правило, лишь приближенным описанием реальной задачи, получение точного решения в этом случае может представлять лишь академический интерес, и вряд ли оправдано;

— параметры математической модели известны с погрешностями, и нахождение точного решения в этом случае не представляется оправданным.

Отметим, что существуют задачи, для которых переход к приближенной постановке не представляется возможным. В задачах этого типа следует дать один из двух ответов: «да» или «нет». В качестве примера такой задачи можно привести задачу о существовании гамильтонова цикла в графе.

5.2. Общая характеристика алгоритмов приближенного решения и их классификация

Алгоритм приближенного решения характеризуется следующими основными параметрами:

— трудоемкость;

— объем оперативной памяти;

— получаемая точность решения.

Для характеристики алгоритмов точного решения используются первые два параметра.

Под трудоемкостью будем понимать объем вычислений, число вершин дерева ветвления, число итераций и т.д. в зависимости от размерности и параметров задачи.

Остановимся на оценке точности получаемого решения при решении регулярных задач математического программирования (см. 1.2). В регулярных задачах рассматриваются алгоритмы, основанные на построении последовательности приближенных решений. При этом оценивается скорость сходимости: линейная, сверхлинейная, квадратичная и т.д. Задачи дискретного программирования не являются регулярными, для алгоритмов их решения, как правило, не удается
140

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

оценить не только точность, но и другие из указанных параметров. Оценка объема оперативной памяти обычно не представляется возможной, например, для алгоритмов типа ветвей и границ, учитывая непредсказуемость их поведения.

В дальнейшем рассматриваются алгоритмы следующих типов:

— алгоритмы гарантированного функционирования;

— алгоритмы локальной оптимизации и эвристические процедуры;

— комбинированные алгоритмы, использующие локальную оптимизацию и эвристические процедуры;
Предыдущая << 1 .. 41 42 43 44 45 46 < 47 > 48 49 50 51 52 53 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100