Cтраница 2
Надо подчеркнуть, что при решении задач дискретного программирования возникают значительные трудности. Методы решения задач дискретного программирования не так эффективны, как методы линейного программирования. Тем не менее алгоритмы для решения задач такого рода также существуют и могут быть использованы при: анализе проблем, возникающих в практической деятельности. [16]
В этом параграфе описывается подход к задачам дискретного программирования, основанный на сочетании случайного поиска с локальной оптимизацией. Идея этого подхода весьма проста. Производится случайный выбор исходного плана. Далее некоторым естественным образом определяется окрестность этого плана и на ходится локальный оптимум целевой функции на точках окрестности. Поиск этого оптимума чаще всего ведется прямым перебором, ибо окрестность по самому своему построению состоит из относительно небольшого числа точек. Затем производится случайный выбор нового плана и снова находится локальный оптимум в окрестности этого плана. Процесс этот повторяется много кратно, и из полученных локальных оптимумов выби рается наилучший в смысле значения целевой функции. Он и принимается за приближенное решение задачи. [17]
Задача (6.72) - (6.76) также является задачей дискретного программирования с псевдобулевыми переменными. Подставляя в целевую функцию задачи оптимизации другие параметры, в частности стоимость, Время решения задач, энергетические и другие параметры системы памяти, можно оптимизировать структуру системы памяти ЭВМ по соответствующим критериям. [18]
Как мы видим, по своей постановке задача дискретного программирования отличается от общей задачи математического программирования специальным заданием прямого ограничения. [19]
Таким образом, задача календарного планирования есть задача частично дискретного программирования, которая может быть решена, например, методом ветвей и границ. [20]
В разделе III рассматриваются алгоритмы приближенного решения задач дискретного программирования. Необходимость применения алгоритмов этого типа обусловлена ограниченностью возможностей точных методов и величиной вычислительных ресурсов, которые разумно выделить для решения задач. [21]
Покажем, что данная задача сводится к задаче дискретного программирования. Переменная zl будет принимать значение 1, если данная дуга разрывается, и значение 0 - в противном случае. [22]
Несмотря на упрощения, задача В остается задачей дискретного программирования, которая не может быть решена известными точными методами. [23]
Раздел II содержит изложение комбинаторных методов для решения задач дискретного программирования; здесь рассмотрены два метода: метод ветвей и границ и метод динамического программирования. Каждый из этих методов реализует высказанную ранее идею нахождения подмножеств, не содержащих оптимальных решений. В методе ветвей и границ эта идея основана на применении оценок для подмножеств, в методе динамического программирования - на принципе оптимальности Беллмана. [24]
Все перечисленные здесь методы сводят задачу коммивояжера - задачу дискретного программирования - к последовательности решения более простых задач линейного программирования того или иного вида. [25]
Среди разработанных в монографии экономико-математических моделей, являющихся задачами дискретного программирования, часть представляет собой одноэтапные экономико-математические модели-задачи целочисленного линейного программирования, часть - многоэтапные, целочисленного нелинейного программирования. [26]
Если наборы / включают только целые числа, то задача дискретного программирования сводится к частному случаю, называемому задачей целочисленного программирования. [27]
В настоящее время разработаны современные методы и алгоритмы решения задач дискретного программирования, они описаны в научной и учебной литературе. Разработаны пакеты прикладных программ, позволяющие решать ряд стандартных задач дискретного программирования, например задачи частично целочисленного линейного программирования. Применение этих пакетов разумно, оправдано и вполне возможно без знания алгоритмов решения задач и технологий, обеспечивающих реализацию алгоритмов. [28]
В настоящем параграфе освещаются главным образом точные методы решения задач дискретного программирования. Эти методы базируются на таких общих подходах, как методы последовательного анализа вариантов [12] [ включая динамическое программирование ( гл. [29]
В зависимости от класса методов выделяются программы для решения задач линейного, нелинейного и дискретного программирования. В качестве примеров ППП для решения задач линейного программирования ( ЛП) можно привести пакет ОПТИМА-2, разработанный в Институте математики и механики УНЦ АН СССР для ЭВМ БЭСМ-6 и пакет ЛП-БЭСМ-6, созданный в ВЦ АН СССР. [30]