Cтраница 3
БУЛЕВО ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ [ Boolean linear programming ] - класс задач дискретного программирования, в которых все или некоторые искомые переменные являются булевыми величинами, а критерий и ограничения - линейные. [31]
Главы б и 7 посвящены в основном эвристическим алгоритмам решения задач дискретного программирования. Как уже отмечалось ранее, под эвристическими понимаются алгоритмы, основанные на правдоподобных, но не обоснованных строго предположениях о свойствах оптимального решения задач. Рассматривается применение различных эвристик для задач о ранце, о коммивояжере, о покрытии графов и ряда других. Показано, что эти эвристики могут приводить к решениям, сколь угодно далеким от оптимальных. Высказывается естественное предположение, что комбинация эвристик позволяет существенно улучшить качество приближенных решений. Описан комбинированный алгоритм для задачи коммивояжера, в котором сочетаются различные эвристики, и проведено его экспериментальное исследование. [32]
Если область G состоит из конечного числа точек, то получают задачу дискретного программирования. Задачами, в к-рых / и ( или) gi зависят от параметров, занимается параметрическое программирование. В задачах стохастического программирования учитывается зависимость / и ( или) g; от случайных факторов. Несколько особо стоит динамическое программирование, в к-ром принятие оптимального решения ( вне зависимости от конкретного вида / и gi) представляется в виде многошагового процесса. В этом случае речь уже не может идти о нахождении ее экстремума, а само понятие оптимальности следует пересмотреть. [33]
В данной главе приводятся алгоритмы решения двух ( двумерных по аргументу) задач дискретного программирования ( назначения и коммивояжера) с помощью метода, изложенного в гл. Выбор этих задач не случаен. Как правило, вновь создаваемые общие схемы в дискретном программировании тестируются на рассматриваемых в главе задачах. Рассматривается задача назначения с подробным изложением математической постановки задачи, с построением реализации элементарной операции, конкретизацией последней для задачи, приводящей к точному алгоритму решением модельного примера. Предлагаемый алгоритм решения задачи назначения наиболее близок к алгоритмам венгерской группы, отличаясь от него нетривиальными особенностями. По такой же схеме рассматривается и используется задача коммивояжера с получением точного алгоритма решения этой задачи. Как показывает сравнение с существующими точными алгоритмами решения этой задачи, рассматриваемый алгоритм наиболее близок к алгоритму Балаша - Кристофидеса - наиболее эффективному на сегодняшний день алгоритму решения задачи коммивояжера с асимметричной матрицей расстояний. Так, в частности, с помощью последнего алгоритма к настоящему времени решены задачи размерностей до 325 городов. [34]
Локальный подход, зародившийся в дискретном анализе, был затем развит применительно к задачам дискретного программирования [8], [34], [31] ( см. гл. [35]
Можно обратиться также к методу ветвей и границ, широко используемому для численного решения задач дискретного программирования. [36]
Всякая экономическая задача, где искомыми величинами являются показатели неделимых ресурсов, неизбежно оказывается задачей дискретного программирования. [37]
Задача минимизации функционала (5.40) на множестве возможных разделений / объектов на т групп является задачей дискретного программирования. [38]
В связи с тем, что модели задачи выбора наилучших проектных вариантов относятся к классу задач дискретного программирования с булевыми переменными, непосредственно воспользоваться одним из рассмотренных декомпозиционных алгоритмов не представляется возможным. Однако сама идея разбиения большой модели на ряд подмоделей и получения ее решения из решений этих подмоделей может быть использована для выбора наилучших проектных вариантов новых изделий. [39]
В простейшем случае, когда / z4 / z, а все DJ - конечные множества, задача дискретного программирования представляет собой задачу нахождения условного экстремума на конечном множестве. [40]
С е р г и е н к о и др. Пакет прикладных программ ДИСПРО, предназначенный для решения задач дискретного программирования. [41]
В случае если некоторые переменные проектирования могут принимать лишь определенные дискретные либо только целочисленные значения, задача оптимизации называется задачей дискретного программирования. [42]
Математические модели многих задач науки и техники, в том числе планирования и управления производством, могут быть отнесены к задачам дискретного программирования. [43]
Приведенные примеры показывают, что во многих случаях задачи структурного синтеза являются экстремальными комбинаторными задачами, которые могут быть сведены к задачам дискретного программирования. Оценка трудоемкости получения точных решений задач этого класса позволяет сделать вывод, что при реальном проектировании полупение точных решений либо невозможно, либо требует больших затрат машинного времени. [44]
Общие схемы комбинаторных методов обладают очень важными свойствами, а именно: они универсальны, что позволяет применять их практически ко всем задачам дискретного программирования; требуют для своей реализации сравнительно мало машинной памяти и, кроме того, применимы к задачам в комбинаторной постановке, без предварительного сведения к целочисленной задаче. [45]