Дискретное программирование

Эта задача является задачей дискретного программирования. Для задач с такой структурой разработаны различные алгоритмы, в том числе и приближенные. В последнее время удалось добиться существенных успехов в этом направлении. [c.174]

Эта. задача является задачей дискретного программирования со всеми вытекающими отсюда последствиями. Тем не менее для задач такой структуры разработаны различные алгоритмы, в том числе и приближенные. В последнее время удалось добиться существенных успехов в этом направлении. В задачах с дискретными вариантами мощностей также могут учитываться уже существующие мощности. [c.225]

Решение такой задачи обеспечивается методами дискретного программирования, однако необходимо заметить, что ее размерность может оказаться значительной. [c.119]

Под целочисленным, или дискретным программированием понимают задачи, в которых искомые переменные могут принимать только целые значения число рабочих, разделяемых по рабочим местам, количество единиц оборудования, устанавливаемых на заданной площади, и т. п. [c.126]

Таким образом, выше приведена постановка оптимизационной задачи, выбрана целевая функция, описан набор параметров и ограничений, что в совокупности образует математическую модель, а с учетом специфики-задачи - экономико-математическую модель. Из изложенного следует, что поставленная задача относится к задачам нелинейного дискретного программирования с разрывной целевой функцией и ограничениями, заданными в виде равенств, неравенств и алгоритмов. Ее решение возможно найти с помощью специально организованного перебора вариантов/" 2 J. В каждом случае решения задачи для одних исходных данных число рассматриваемых вариантов (определяемое по количеству сочетаний независимых переменных) не превысит 50, что для машинного счета представляется допустимым. [c.65]

В производстве очень часто встречаются неделимые материальные ресурсы (доменные печи, прокатные станы, печи в цементной промышленности, конвейерные автоматические линии в машиностроении и т. п.). Всякая экономическая задача, где искомыми величинами являются показатели неделимых ресурсов, неизбежно оказывается задачей дискретного программирования. [c.123]

Все предложенные в монографии экономико-математические модели относятся к классу задач дискретного программирования (за исключением модели (4.1) — (4.4)). И, как известно, методы решения такого типа задач математического программирования разработаны наиболее слабо. В этой главе сделана попытка систематизации методов решения задач дискретного программирования в преломлении к предложенным моделям. Что касается модели (4.1) —(4.4), то она представляет собой фактически формулировку общей задачи математического программирования. Рассматривать методы решения этой модели было бы целесообразно, если в нее входили бы конкретные функциональные зависимости. [c.187]

Среди разработанных в монографии экономико-математических моделей, являющихся задачами дискретного программирования, часть представляет собой одноэтапные экономико-математические модели-задачи целочисленного линейного программирования, часть — многоэтапные, целочисленного нелинейного программирования. iB качестве переменных взяты булевы переменные. [c.187]

Лихтенштейн В. Е. Модели дискретного программирования. М., Наука , 1971. [c.215]

Для решения задач дискретного программирования широко применяются комбинаторные методы, основная идея которых заключается в замене полного перебора всех решений их частичным перебором. Одним из таких методов является метод ветвей и границ, основе которого лежат следующие построения, позволяющие существенно уменьшить объем перебора решений [c.212]

Для решения задач используется ряд методов линейного программирования, дискретного программирования, методы ветвей и границ, сетевого планирования и управления. В последнее время особое развитие принимают приближенные методы решения, резко сокращающие перебор вариантов (метод Монте-Карло). [c.359]

Задача дискретного программирования [c.498]

Успешное овладение курсом предполагает знакомство с теорией множеств, дискретным программированием, математической логикой, теорией графов, теорией информации и кодирования, теорией экономических информационных систем, основами общей теории систем, алгоритмизации и программирования, проектирования баз данных и техническими средствами сбора и обработки информации. [c.3]

С помощью ППП методов дискретного программирования решаются задачи линейного, динамического, стохастического, нелинейного программирования и др. [c.126]

ОПТИМАЛЬНОЕ ПРОГРАММИРОВАНИЕ — общий термин, которым объединяются различные математические методы и дисциплины линейное программирование, нелинейное программирование, дискретное программирование, целочисленное программирование, динамическое программирование, выпуклое программирование и другие. [c.23]

Вот для чего это нужно. Если в ответе плановой задачи получилось, что вам надо построить полтора корабля или сорок пять с половиной автомобилей или ввести в действие тридцать три и одну треть парикмахерских, вряд ли такой план вас устроит. Поэтому и приходится приводить решения к целочисленному виду. Как показано в статье Дискретное программирование), это требует своеобразных вычислительных приемов и преодоления ряда трудностей. [c.117]

Для решения задач дискретного программирования применяется ряд способов. Самый простой — решение обычной задачи линейного программирования с проверкой полученного результата на целочисленность и округление его до приближенного целочисленного решения. Скажем, получилось у вас, что надо построить полторы домны, выбираете либо одну, либо две. Точно так же не 3,8 автомобиля, а 4 и т. д. [c.118]

Иногда дискретное программирование называют целочисленным как видно из приведенных примеров, это не лишено основания, хотя некоторые математики считают такой термин неправильным (исходя из того, что, строго говоря, дискретное — это не обязательно целочисленное. Например, ряд чисел—1,1 —1,2—1,3 и т. д.— дискретный, но не целочисленный). [c.118]

Поэтому для решения задач целочисленного программирования нередко применяются методы комбинаторного анализа. Остановимся здесь на одном из них — методе ветвей и границ. Изложим его применительно к общей задаче дискретного программирования. [c.113]

ТИПЫ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ [c.136]

Основные понятия. Многие экономические задачи характеризуются тем, что объемы управляемых ресурсов (в силу тех или иных объективных свойств) могут принимать только целые значения. Математическая формализация данных ситуаций приводит к моделям дискретного программирования. В общем виде задача дискретного программирования может быть сформулирована как задача нахождения максимума (или минимума) целевой функции f(x ,x2,...,xn) на множестве Д определяемом системой ограничений [c.136]

Перечисленные проблемы предопределили необходимость разработки специальных методов решения дискретных и целочисленных задач. Но прежде чем говорить собственно о методах решения, более подробно остановимся на классификации задач дискретного программирования. В литературе, как правило, выделяют следующие классы дискретных оптимизационных задач [c.138]

Условия (4.8) и (4.9) с содержательной точки зрения означают, что в каждый пункт можно въехать и выехать только один раз. Приведенная форма записи задачи коммивояжера (4.6)-(4.10) не является самой рациональной и предназначена только для того, чтобы подчеркнуть ее общность с другими задачами дискретного программирования. Существует и другая форма, которая более ярко отражает комбинаторный характер данной проблемы [c.140]

См., например, Корбут А. А., Ф и л ь к е н ш т е и н Ю. Ю., Дискретное программирование. — М. Наука, 1969. [c.168]

В связи с тем, что модели задачи выбора наилучших проектных вариантов относятся к классу задач дискретного программирования с булевыми переменными, непосредственно воспользоваться одним из рассмотренных декомпозиционных алгоритмов не представляется возможным. Однако сама идея разбиения большой модели на ряд подмоделей и получения ее решения из решений этих подмоделей может быть использована для выбора наилучших проектных вариантов новых изделий. Наиболее приемлем в данном отношении алгоритм, предложенный А. Г. Аганбегяном, К. А. Багриновским и А. Г. Гранбергом [7]. [c.190]

БУЛЕВО ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ [Boolean linear programming] — класс задач дискретного программирования, в которых все или некоторые искомые переменные являются булевыми величинами, а критерий и ограничения — линейные. [c.35]

ГОМОРИ СПОСОБ [Gomory method] — прием, с помощью которого достигается решение линейной задачи целочисленного программирования. Разработан американским математиком Р. Гомори. Состоит в автоматическом введении дополнительных ограничений, приводящих через конечное количество шагов к новой линейной задаче с целочисленным/решением, которое оказывается одновременно оптимальным целочисленным решением исходной задачи (если только она имеет решение). См. также Дискретное программирование. [c.64]

СКАЛЯРНАЯ ОПТИМИЗАЦИЯ [s alar optimization] — совокупность методов решения задач математического программирования, целевая функция которых представляет собой скаляр. Большинство задач, рассматриваемых в словаре (см. Линейное программирование, Нелинейное программирование, Дискретное программирование и др.), принадлежит к этому классу. Ср. Векторная оптимизация, Многокритериальная оптимизация. [c.330]

В свою очередь мето-доориентированные пакеты можно разделить в зависимости от особенностей алгоритмов и методов, которые они реализуют. Так, выделяют ППП (рис. 8.3), ориентированные на реализацию управления данными типовых процедур обработки данных методов математической статистики методов дискретного программирования методов решения непрерывных задач и др. [c.126]

ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ. Слово дискретность (от латинского dis retus — разделенный прерывный) противоположно понятию непрерывность , а если отказаться от математической терминологии — понятию плавность . [c.118]

Анализ модели обычно производится с помощью методов и алгоритмов решения условных экстремальных задач или посредством статистич. моделирования. К числу наиболее широко применяемых в И. о. методов относится линейное программирование. Модели, приводящие к задачам линейного программирования, глубоко изучены, имеются эффективные алгоритмы и стандартные программы для ЭВМ, позволяющие решать задачи, содержащие тысячи ограничений и десятки тысяч переменных. Как правило, анализ моделей И. о. с помощью методов линейного программирования позволяет не только получить оптимальное решение, но и сделать онредел. качеств, выводы по организации операции. Эти выводы базируются на теории двойственности (объективно-обусловленные оценки) и принципах декомпозиции. Если целевая функция или ограничения модели исследуемой операции не могут быть достаточно точно описаны с помощью линейных функций, для её анализа используются др. методы математического программирования. Модели, в к-рых по смыслу операции все переменные или их часть могут принимать лишь конечное число различных значений, изучаются методами целочисленного или дискретного программирования, в частности, сюда относится большое число нла-ново-производств. операций, укладывающихся в схему т. н. задач календарного планирования и теории расписаний. Это задачи, связанные с нахождением последовательности обработки определ. числа изделий с помощью фиксированной системы машин, характеристики к-рых заданы. При этом должны быть соблюдены опродел. технологич. требования, к-рые по большей части выделяют допустимые последовательности обработки каждой детали на различных машинах. Задачи теории расписаний часто встречаются во внутризаводском планировании, особенно на мапшностроит. предприятиях. Модели, описывающие протяжённые во времени операции, цель к-рых достигается лишь с их окончанием, а осуществление может быть разделено на этапы, время начала и завершения к-рых должно быть согласовано, исследуются методами сетевого [c.74]

В задачах с большим числом переменных могут применяться спец. методы для проверки оптимальности решении на каждой итерации. Здесь используются методы динамнч. и дискретного программирования и даже методы Л. и. (принцип разложения Данцига — Вульфа для задач с блочными ограничениями). [c.357]

Смотреть страницы где упоминается термин Дискретное программирование

Смотреть главы в: