Метод целочисленного программировани

Решение задачи раскроя методами целочисленного программирования целесообразно применять при небольшом количестве вариантов раскроя. В противном случае получается задача линей- [c.157]

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

Алгоритм решения задачи целочисленного программирования методом ветвей и границ заключается в следующем. На каждой итерации (обозначим номер итерации через t) имеются нижняя оценка F K) оптимального значения целевой функции и список задач линейного программирования, подлежащих решению. Процедура решения состоит в последовательном улучшении оценки F (X) и приближении ее к оптимальному значению [c.314]

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

В составе подсистемы Оптимизация рассматриваемой САПР нашли применение несколько методов поисковой оптимизации. В частности, разработан алгоритм экстраполяционного поиска, предусматривающий генерацию ряда состояний в окрестности каждой текущей точки с определением целевой функции и ограничений, а также их многомерную линейную аппроксимацию. Для решения задач целочисленного программирования, к которым часто сводится оптимизация электрических машин, применяется алгоритм последовательного улучшения функции [c.287]

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

Дискретное программирование предполагает дискретное изменение с некоторым шагом варьируемых параметров. В задачах целочисленного программирования параметры х ,. .., % могут быть только целыми (например, л" — число станков в автоматической линии). Задачи целочисленного программирования решаются с помощью методов полного перебора, ветвления, отсечений и т. д. 165]. Если Xj меняются непрерывно, а ограничения и целевая функция линейные, то решается задача линейного программирования. [c.194]

Все другие прямые, построенные по уравнению целевой функции и лежащие ниже линии Ф, соответствуют меньшим значениям целевой функции. Так линия, проходящая через начало координат, соответствует минимальному значению целевой функции Ф = 0. Данная задача относится к задаче целочисленного программирования, однако погрешность округления в этом случае незначительна и ее можно решать методом линейного программирования. [c.200]

Для небольшой размерности эта задача нелинейного целочисленного программирования может быть решена с помощью метода ветвей и границ [45]. [c.229]

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

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

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

Таким образом, задача разбиения формулируется как минимизация функционала (7.10) при ограничениях (7.11) и (7.12) и варьируемой матрице переменных В. Это задача нелинейного целочисленного программирования. Практическое применение для задач невысокой размерности нашли в основном методы сокращенного перебора, основанные на идеях метода ветвей и границ. Для задач большой размерности методы нелинейного целочисленного программирования неприменимы из-за чрезмерных затрат времени и памяти ЭВМ, поэтому используются приближенные алгоритмы решения задачи разбиения. Точные методы служат для теоретического обоснования и оценки точности этих алгоритмов. Приближенные алгоритмы делятся на две группы последовательные и итерационные [1]. [c.196]

В зависимости от вида функций я( ), /о (у), /,(у) могут быть выделены различные классы задач математического программирования линейное, квадратичное, геометрическое, выпуклое, целочисленное и т. д. [96, 221, 223]. Наибольшее применение при оптимизации устройств СВЧ находят методы выпуклого программирования. Последние развиты для минимизации выпуклых функций на выпуклых множествах. [c.146]

Задача целочисленного нелинейного программирования решается методом прямого перебора (комбинаторикой) ЭВМ просчитывает все варианты сочетания числа фильтров и их диаметра, отбрасывает неподходящее по скоростным характеристикам и запоминает наиболее дешевый. [c.100]

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

Дискретная оптимизация сложнее непрерывной. Комбинаторная задача общего вида относится к N9 полным, и сложность ее точного решения является экспоненциальной. Эффективные точные методы дискретной оптимизации существуют лишь для отдельных классов задач, поэтому для задач целочисленного линейного программирования и нелинейного дискретного программирования в САПР применяются приближенные методы локальной оптимизации и ветвей и границ. [c.76]

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

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

Для решения задачи используются методы целочисленного линейного программирования. Условие целочисленности определяется возможностью применить любой модуль только полностью, независимо от того, сколько реализованных в нем функций (задач) используется в конкретной системе. Точное решение задачи покрытия для реальных графов не представляется возможным [159], так как по существу это один из вариантов известной задачи идентификации графов. Комбинаторная сложность такой задачи определяется следующими выражениями [c.164]

Методы возврата. В этой группе методов имеются различные модификации. Наиболее распространенным среди них является метод ветвей и границ, который предназначен для решения частично целочисленных задач. Как и в методе отсечения, решение задачи начинается с отыскания оптимального решения задачи линейного программирования без учета условия целочисленности. Затем формируется семейство связанных, но различных задач линейного программирования. Термин возврат определяет специфический способ формирования и решения последовательности задач. [c.313]

Коротко остановимся на возможных подходах к решению подобных задач. Известно, что проблема целочисленности решена в основном в линейном программировании. Поэтому нелинейную задачу часто сводят к линейной целочисленной задаче, которую решают, например, известным методом отсекающих плоскостей Гомори [31] или используют прием Мартина для ускорения сходимости этого метода [32]. В случае булевых переменных применяют метод Балаша [33] и другие известные методы (на- [c.24]

Ю. Ю. Финкелъштейн. Алгоритм для решения задач целочисленного линейного программирования с булевыми переменными.— Экономика и математические методы, 1965, т. 1, вып. 5. [c.218]

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

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

Наиболее разработанные из них задачи линейного программирования, когда целевая функция одна и она и ограничения линейны. Для таких случаев разработаны различные эффективные алгоритмы решения. В задачах линейного программирования оптимальное решение, если оно существует, всегда располагается на границе области допустимых рещений, а в ряде случаев можно даже указать конечное множество точек границы, где оно может находиться. Это облегчает поиск оптимального решения, и на этом свойстве основаны алгоритмы решения задач линейного программирования. Среди них можно отметить методы решения задач целочисленного линейного программирования, когда на параметры Хх, Х2, Хп наложено условие целочисленности. Если функция цели или хотя бы одно ограничение имеют нелинейный характер, то метод решения существенно усложняется, хотя и здесь имеются эффективные алгоритмы для ряда случаев. В основном это такие, когда область допустимых решений выпукла. [c.109]

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

Э. Формен (один из авторов программной системы Expert hoi e) предложил объединить МАИ с традиционными методологиями исследования операций [Д25]. В работе обосновывается система поддержки принятия решений, которая понятна и релевантна для ЛПР в реальной жизни. Показано, как ЛПР могут разрабатывать, понимать и применять модели для принятия управленческих решений, что на практике они редко делают. Рассматривается объединение МАИ с линейным программированием, анализом очередей, методом критического пути, прогнозированием и целочисленным линейным программированием для решения ряда практических задач (дизайн новых видов продукции, распределение ресурсов во времени, по деньгам, труду и материалам с целью своевременного выполнения проекта). [c.303]

Энциклопедия по машиностроению XXL

Оборудование, материаловедение, механика и ...