Cтраница 2
НСМ может быть применен к широкому кругу задач дискретной оптимизации и структурного синтеза, характеризуемых следующими особенностями. [16]
Основная тематика: теория графов и гиперграфов, задачи дискретной оптимизации, приложения к структурной химии; рассматриваются также вопросы обоснования теории множеств, алгебры, математической логики и специальной теории относительности. [17]
Подобная математическая модель в виде графа широко используется в задачах дискретной оптимизации. [18]
В данном учебном пособии отражен мой многолетний опыт по решению задач дискретной оптимизации. Главы 8 10 написаны на основании научных результатов, полученных мною за время многолетней работы в Вычислительном центре им. [19]
Предлагается общий подход для формирования двойственных оценок для широкого класса задач дискретной оптимизации. Подход основывается на введении разрешающей функции и трактовке каждого из рассматриваемых видов двойственности как специального случая задания этой функции. Подход позволяет с единых позиций объяснить большинство существующих видов двойственности, установить их взаимосвязь, предложить новые виды двойственности и алгоритмы на их основе. [20]
Указанные особенности обусловливают сложность решения задач синтеза расписаний, являющихся задачами дискретной оптимизации. [21]
Рассматриваются оценки отклонения некоторых приближенных решений от оптимального решения в задачах дискретной оптимизации. Особое внимание уделяется отклонению от оптимума, следующего после оптимального решения задачи. Предложена общая схема получения таких оценок, которая конкретизирована для задач о целочисленном и булевом ранце с одним ограничением и задачи коммивояжера с симметричной матрицей расстояний. Основная особенность полученных результатов состоит в том, что указанные оценки зависят лишь от параметров исходной задачи и некоторых ее решений, для нахождения которых не требуется существенных затрат вычислительных ресурсов. [22]
Сформулированные принципы носят общий характер и применяются не только в задачах дискретной оптимизации. Уравнение, являющееся математической формулировкой принципа оптимальности ( например, уравнение (4.1)), часто называют уравнением Беллмана. [23]
Данный пакет программ, как уже отмечалось, ориентирован на решение задач дискретной оптимизации, являющихся комбинаторными задачами. [24]
Переход от параметрической формы задания выпуклого многогранника к аналитической имеет большое значение для задач дискретной оптимизации, так как позволяет сформулировать их в терминах линейного программирования. [25]
При возникновении новых нестандартных задач реализация алгоритмов их решения требует информации о технологии решения задач дискретной оптимизации. [26]
Итак, основной целью данного учебного пособия является изложение современных комбинаторных алгоритмов для практического решения задач дискретной оптимизации. При этом вовсе не ставится цель разработать такой алгоритм, который решает любую задачу ( например, задачу коммивояжера) с любой заранее заданной точностью: такая цель недостижима, что следует непосредственно из результатов, полученных в теории сложности алгоритмов. Для задачи коммивояжера необходимо разработать алгоритм, расширяющийся с учетом особенностей задачи и позволяющий получить приближенное решение с оценкой отклонения от оптимума. Существуют задачи из класса NP ( например, общая задача частично целочисленного линейного программирования), для которых даже эта цель недостижима, так как трудоемкость получения хотя бы одного допустимого решения сравнима с трудоемкостью нахождения оптимального решения. [27]
Мой учитель академик Н. Н. Моисеев еще в середине 60 - х годов во время моего обучения в аспирантуре обратил внимание на задачи дискретной оптимизации. Все изложенные здесь мои результаты неоднократно обсуждались в наших беседах и докладывались на проводимых им научных школах и семинарах. [28]
Данные табл. 2.1 - 2.4 интересны также тем, что они свидетельствуют о преимуществе НСМ перед обычными эвристическими методами решения задач дискретной оптимизации. [29]
В последующих параграфах этой главы исследуются точные ( § III.1 - III.5) и приближенные ( § III.6) методы решения задач дискретной оптимизации. [30]