Дискретное программирование
Cтраница 3
Другим важным толчком к построению теории дискретного программирования явился новый подход к некоторым экстремальным комбинаторным задачам, разработанный в середине 50 - х годов и основанный на использовании линейного программирования. [31]
После рассмотрения схемы для общей задачи дискретного программирования рассматривается применение этой схемы для разработки алгоритмов решения задач различных типов. [32]
 |
Спуск по методу оврагов j. [33] |
Для решения более узкого класса задач нелинейного дискретного программирования с аддитивной функцией цели целесообразно применение идей метода динамического программирования. [34]
Пессимизм в отношении возможностей О бщих методов дискретного программирования, например, в логическом синтезе порожден в известной мере тем, что от методов требуется умение оптимизировать схему, отвечающую любой булевой функции п переменных или любому конечному автомату с заданным числом входов и внутренних состояний. Между тем, можно полагать, что класс булевых функций или автоматов, с которыми связано про-ектирование устройств, решающих ограниченные классы задач, далеко не исчерпывает множества всех операторов данной раз-мерности. [35]
Отметим, что всякая классификация прикладных задач дискретного программирования неизбежно оказывается неполной, ибо среди этих моделей мы находим и задачи сельскохозяйственного производства, и задачу оптимальной синхронизации сигналов при регулировании уличного движения и пр. [36]
Эта часть посвящена второй большой группе методов дискретного программирования. [37]
В этом параграфе описывается подход к задачам дискретного программирования, основанный на сочетании случайного поиска с локальной оптимизацией. Идея этого подхода весьма проста. Производится случайный выбор исходного плана. Далее некоторым естественным образом определяется окрестность этого плана и на ходится локальный оптимум целевой функции на точках окрестности. Поиск этого оптимума чаще всего ведется прямым перебором, ибо окрестность по самому своему построению состоит из относительно небольшого числа точек. Затем производится случайный выбор нового плана и снова находится локальный оптимум в окрестности этого плана. Процесс этот повторяется много кратно, и из полученных локальных оптимумов выби рается наилучший в смысле значения целевой функции. Он и принимается за приближенное решение задачи. [38]
В этом разделе книги излагаются некоторые вопросы дискретного программирования, представляющие теоретический интерес и не связанные непосредственно с вычислительными методами. [39]
Надо подчеркнуть, что при решении задач дискретного программирования возникают значительные трудности. Методы решения задач дискретного программирования не так эффективны, как методы линейного программирования. [40]
Среди рассмотренных общих точных методов решения задач дискретного программирования более подробно рассмотрены динамическое программирование, методы отсечений, ветвей и границ. Некоторые из приближенных методов решения задач дискретного программирования будут рассмотрены в гл. [41]
Основные известные методы получения точного решения задач дискретного программирования можно изложить и на общей задаче линейного дискретного программирования, но при этом возможно засорение основных идей методов подробностями, навязанными общностью исследуемой модели. В последнее время все в большей степени намечается тенденция максимального использования специфики задачи при разработке алгоритмов ее решения. Поэтому среди задач линейного дискретного программирования выделим наиболее распространенные частные классы задач и на их примере поясним основные идеи точных методов. [42]
Надо подчеркнуть, что при решении задач дискретного программирования возникают значительные трудности. Методы решения задач дискретного программирования не так эффективны, как методы линейного программирования. Тем не менее алгоритмы для решения задач такого рода также существуют и могут быть использованы при: анализе проблем, возникающих в практической деятельности. [43]
Задача (6.72) - (6.76) также является задачей дискретного программирования с псевдобулевыми переменными. Подставляя в целевую функцию задачи оптимизации другие параметры, в частности стоимость, Время решения задач, энергетические и другие параметры системы памяти, можно оптимизировать структуру системы памяти ЭВМ по соответствующим критериям. [44]
Для учета указанных взаимосвязей приходится применять методы дискретного программирования при большом числе структурных переменных. Но, как мы заметили выше, в настоящее время не существует достаточно эффективных методов решения подобных задач. [45]
Страницы: 1 2 3 4