Целочисленные решения задач линейного программирования

V.2.4. Целочисленные решения задач линейного программирования [c.193]

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

Минимизация этой функции производится методом ветпей и границ. Задача составления расписания в наиболее общих случаях относится к числу трудно формализуемых, и обычно расписания составляют, исходя из особенностей конкретной оптимизируемой системы известную трудность представляет также решение задач теории расписаний. По содержанию эти задачи относятся к классу комбинаторных, для которых сущсстненное значение имеет размерность. Как правило, размерность ладач составления оптимальных расписаний настолько велика, что решать их простым перебором вариантов не представляется возможным даже на современных быстродействующих вычислительных машинах. Поэтому для снижения размерности прибегают к различного рода эвристическим приемам или используют. методы направленного перебора (ветвей и границ). Часто задачи составления расписаний сводятся к задачам целочисленного линейного программирования (в том числе многоиндексного), для решения которых используются широко известные методы отсечения или ветвей и границ. Рассмотрим несколько примеров составления оптимальных расписаний. [c.300]

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

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

МОЖНО находить, например, при помощи аддитивного алгоритма для решения целочисленных задач линейного программирования с булевыми переменными. Этот алгоритм позволяет сократить число вариантов структур НПЗ, рассматриваемых при движении к оптимуму функции (У,5). Следует отметить, что если все члены исходных неравенств (У,6а) связаны между собой общими множителями, то преобразование их в линейную форму влечет за собой перечисление всех возможных вариантов структур НПЗ, что равносильно нахождению оптимума функции (У,5) путем последовательного перебора вариантов НПЗ, [c.205]

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

Если такие группы образовать нельзя, то надо из имеющегося материала (Z прутков) выкроить нужное число заготовок так, чтобы отходы от каждого прутка были наименьшими. Для этого сначала выкраивают крупные заготовки, а из оставшихся концов более мелкие с учетом условия комплектности. Блок-схема приближенного алгоритма для получения целочисленного решения задачи раскроя пруткового проката приведена на рис. 14 . Подробное рассмотрение методов линейного и динамического программирования не входит в содержание данной книги, поскольку по этому вопросу имеется обширная литература [29, 41, 48, 66, 70, 83—85]. [c.37]

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

Изложенная методика позволяет преобразовать нелинейные уравнения математической модели обобщенной гипотетической стр>"ктуры НПЗ к виду, удобному для решения методами дискретного или целочисленного линейного программирования. Преобразование нелинейных уравнений (представляющих уравнения математической модели структуры НПЗ) в линейные сопровождается перечислением всех возможных альтернативных вариантов технологической схемы НПЗ, что может привести к резкому увеличению размеров задачи. Так, для рассмотренных выше 25 технологических процессов нефтепереработки преобразование [без учета ограничений (У,21а)] приводит к задаче дискретного программирования, содержащей более 10 независимых дискретных переменных. [c.214]

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

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

Задачи, сформулированные в терминах линейного программирования и содержащие требование все или некоторые Х — целые числа , играют важную роль в исследованиях ХТС. Появление указанного требования приводит к пересмотру некоторых геометрических представлений, изложенных в разд. V.2.I. В первую очередь это относится к области допустимых решений, которая отождествляется теперь с совокупностью дискретных точек — узлов целочисленной решетки (если все Х целочисленны) или с набором непересекающихся линий, плоскостей и т. п. (см. рис. V.5). [c.193]

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

Задача ЦЛП (целочисленного линейного программирования). Дана система линейных неравенств с целыми коэффициентами. Есть ли у неё целочисленное решение (Другими словами, совместна ли система ) [c.35]

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

Разработано достаточное количество пакетов, предусматривающих реализацию основных задач планирования, оперативного управления, контроля. В частности, широко внедряются ППП по годовому планированию, планированию ресурсов, оптимизации размеров партий запуска, учету и анализу производства и др. Пакеты такого типа называются проблемно-ориентированными. Разработаны и методо-ориентированные пакеты, реализующие различные математические методы, которые используются при решении задач управления, например ППП Линейное программирование в АСУ , Целочисленное программирование , Математическое программирование , Сетевое планирование и др. [c.66]

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

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

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

Далее рассматривается сопр5сжение данного алгоритма с задачей линейного программирования. На первом этапе сопряжения решается задача линейного программирования (ЛП) без учета условия целочисленности. На втором этапе, основываясь на полученном решении ЛП, строим задачу остатка, которая решается с помощью ПОЗЭВ. Этот прием позволяет пол) -чать оптимальное целочисленное решение для задач с большим числом элементов. Для повышения эффективности данного подхода используется метод группировки, основанный на приёме объединения элементов с близкими мера.ми в общие группы. Доказанная лемма показывает, что данное обобщение ие приводит к потере оптимального решения при соблюдении дополнительных условий. [c.81]

Более широкие возможности имеет пакет Стохастическая оптимизация , созданный на базе ППП Линейное программирование в АСУ (ППП ЛП АСУ) [102]. ППП ЛП АСУ предназначен для решения и анализа задач линейного программирования (ЛП), нелинейного программирования (НЛП) с нелинейными функциями сепарабельного вида, целочисленного программирования (ЦП) и задач специальной узкоблочной структуры. Размерность решаемых задач составляет для ЛП до 16000 строк, для ЦП — до 4095 целочисленных переменных и 60 000 строк для задач узкоблочной структуры. Пакет может быть использован также для решения задач стохастического программирования (СТП) при построчных вероятностных ограничениях. В последнем случае необходимо предварительно построить детерминированный аналог. [c.179]

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

Перечисленными соображениями объясняется тот факт, что многие оценочные модели реализуются с применением различных модификаций методов линейной оптимизации. Так, например, в схемы линейного программирования (ЛП) удачно вписываются задачи оптимизации производственной структуры мелиорируемых земель, выбора типа очистных сооружений и некоторые другие. Если в задачах присутствуют альтернативы с ярко выраженной дискретностью, то применяются методы частично целочисленного Л П. В зонах неустойчивого увлажнения велика роль как случайных природных факторов (речной сток, осадки), так и потребности в воде на орошение. Это обуславливает целесообразность явного их включения в формулировки соответствующих задач. При этом многие модели приобретают форму задач стохастического ЛП со случайными переменными и/или ограничениями. Например, можно отметить применение стохастического программирования (линейного и нелинейного соответственно) в задачах оптимизации орошаемого земледелия в зонах неустойчивого увлажнения [Прясисинская, 1985 Математическое моделирование..., 1988] и при решении агрегированных задач управления качеством вод [ ardwell, [c.64]

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

Приведенные выше задачи оптимизации надежностп ХТС являются задачами целочисленного нелинейного программирования с линейными или нелинейными ограничениями в виде неравенств. Предложены различные методы решения основных задач оптимизации резервирования технических систем, которые рассмотрены в разделе 8.2. Все указанные методы решения основных задач оптимизации резервирования ХТС и различных технических систем [2, 7, 231, 237] являются одноуровневыми. Они учитывают влияние включения резервных элементов на повышение надежности системы без использования обобщенных технико-экономических показателей. В качестве КЭ оптимального резервирования в данных методах используются лишь капитальные затраты на резервные элементы системы или величина Р(Х). [c.204]

Справочник химика 21

Химия и химическая технология