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

 

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

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

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 3 4 5 6 7 8 < 9 > 10 11 12 13 14 15 .. 84 >> Следующая


— нахождение универсального правила формирования отсечений;

— доказательство конечности процесса отсечения;

— борьба с чрезмерным «разрастанием» размерности задач при добавлении ограничений.

Только решение этих проблем может привести к универсальному и реализуемому в вычислительном отношении алгоритму. Р. Гомори удалось решить эти проблемы.

Трудности вычислительной реализации. В дальнейшем выявилась большая непредсказуемость в поведении различных алгоритмов отсечения. Вычислительный эксперимент показал, что существуют задачи сравнительно небольшой размерности, решение которых не удается получить при больших затратах машинного времени. В дальнейшем было найдено теоретическое объяснение этого явления. Было показано (см. [42]), что для некоторых вариантов алгоритма Гомори существуют задачи, в которых число отсечений быстро растет с ростом размерности задачи и ростом коэффициентов, а в текущих симплекс-таблицах появляются весьма большие числа.

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

— определение того, какое отсечение (из большого их числа) есть сильнейшее, есть сложная в вычислительном отношении задача;
24 Разд. I. Предмет и модели дискретного программирования

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

— методы отсечения не приспособлены для решения задач со слабо заполненными матрицами.

Здесь алгоритмы этого типа не рассматриваются, их изложение содержится в [18, 41, 42].

1.3.2. Комбинаторные методы. Основная идея комбинаторных методов состоит в использовании конечности множества допустимых решений и замене полного их перебора сокращенным (направленным перебором). Если каким-либо образом удается показать, что подмножество G1 С G не может содержать оптимальных решений, то в дальнейшем задача (1.1.1) решается на множестве х Є G\G'. Таким образом, главную роль в сокращении перебора играют оценка и отбрасывание подмножеств, заведомо не содержащих оптимальных решений. Эта идея реализуется путем последовательного разбиения множества всех допустимых решений на подмножества. При этом среди подмножеств, последовательно порождаемых на каждом шаге процесса, могут обнаружиться как подмножества, не содержащие допустимых решений, так и подмножества, не содержащие оптимальных решений. Отбрасывание таких подмножеств позволяет заменить полный перебор частичным и тем самым делает реализуемым вычислительный процесс.

Таким образом, комбинаторные методы основаны на двух элементах:

— последовательное разбиение на подмножества;

— оценивание получаемых подмножеств.

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

Остановимся на классификации комбинаторных методов. Среди этих методов выделим следующие, наиболее часто применяемые при решении задач:

— метод последовательного анализа вариантов [27, 45];

— метод ветвей и границ [14-18, 42];

— методы, основанные на последовательностных схемах [8];

— метод динамического программирования [1, 4, 10-12];

— аппроксимационно-комбинаторный метод [13, 43, 44];

— метод последовательных расчетов [13].

Первым из отмеченных здесь методов был метод последовательных расчетов В. П. Черенина, предложенный им в 1948 г., когда еще
Гл. 1. Постановка задач дискретного программирования 25

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

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

1.3.3. Приближенные методы. Эти методы широко применяются при решении задач вида (1.1.1), так как нахождение точного решения может потребовать значительных вычислительных ресурсов. Современные приближенные методы обычно являются комбинированными, т.е. содержат в себе элементы различных методов. В приближенных методах решение задачи производится обычно в два этапа: построение начального решения и улучшение начального решения. При этом на первом этапе широко используются эвристические алгоритмы — алгоритмы, основанные на правдоподобных, но не обоснованных строго предположениях о свойствах оптимального решения задачи. Примером эвристического алгоритма может быть алгоритм решения задачи коммивояжера, в котором на каждом шаге реализуется переход в ближайшую из оставшихся точку. Алгоритмы такого типа носят название «greedy» (жадные, пожирающие алгоритмы). Эти алгоритмы на каждом шаге решают «локальную» задачу оптимизации; полученное решение может быть сколь угодно далеким от оптимума. На втором этапе используются алгоритмы локальной оптимизации, связанные с введенным понятием окрестности; при этом можно использовать несколько алгоритмов этого типа, изменяя правила выбора окрестности. Отметим также, что в последнее время широкое распространение получили приближенные методы, являющиеся модификациями точных методов, с самого начала ориентированные на поиск приближенного решения с оценкой отклонения от оптимального (см., например, [42]). Приближенным методам посвящена обширная литература (см., например, [14, 17, 19, 34-36, 42]).
Предыдущая << 1 .. 3 4 5 6 7 8 < 9 > 10 11 12 13 14 15 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100