Дерево вариантов

Рис. 8.16. Дерево вариантов схем разделения четырехкомпонентной смеси (I = 1)

Для поиска оптимальных решений ИЗС применяют два вида деревьев вывода решений — деревьев граничных задач синтеза и деревьев вариантов решений. Вершины дерева граничных задач соответствуют постановкам ГЗС, возникающих при сведении исходной задачи к иерархической совокупности упрощенных задач синтеза [157, 158]. [c.130]

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

Метод последовательного конструирования, анализа и отбора вариантов, так же как и метод динамического программирования, рассмотренный ранее, основан на построении доминирующих последовательностей векторов поэлементного резерва ХТС [237]. По сравнению с методом полного перебора при использовании метода последовательного конструирования, анализа и отбора вариантов сокращается число просматриваемых векторов резерва. Однако для задач большой размерности данный метод также характеризуется значительными вычислительными трудностями. Поэтому для решения задач оптимизации надежности ХТС большой размерности рекомендуют использовать метод ветвей и границ, основанный на построении усеченного дерева вариантов решений [51, 157, 158, 242]. [c.207]

Совокупность всех полученных решений можно представить в виде дерева вариантов решений (рис. 8.3) [51, 158, 242]. Корень дерева соответствует решению ЗЛП Хо, полученному без учета ограничения на целочисленность. [c.222]

МВГ применен в ряде практических работ по оптимизации надежности технологических систем [239—241]. В этих работах метод развит для решения задач оптимизации поэлементного резервирования с мультипликативным КЭ. В работе [239] для получения оптимального нецелочисленного решения применен алгоритм, основанный на методе Бокса (метод деформируемого многогранника [243]). Этот алгоритм последовательно применяется на каждом уровне ветвления до получения полностью целочисленного решения. Ветвление осуществляется фиксированием некоторой переменной Xl в предшествующем нецелочисленном решении Xi, которому соответствует i-я активная вершина дерева вариантов решений. Следует отметить, однако, что в работе [239] не предложено правило, в соответствии с которым необходимо каждый раз выбирать фиксируемую переменную в i-й активной вершине дерева вариантов решений. [c.223]

Методом релаксации, или снижения размерности исходной задачи оптимизации, определяют ве] нее (или нижнее) значение КЭ, соответствующее решению Xi в i-й активной вершине дерева вариантов решений (см. рис. 8.3). По величине КЭ [c.223]

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

Рис. 8.20. Дерево вариантов технологических схем разделения алкилбензолов (первая цифра в кружке — точка деления, вторая — уровень завершенности схемы цифры слева — номера вершин)

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

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

Углубляющийся поиск состоит в том, что вершина, полученная последней, рассматривается первой на следующем этапе. Это означает, что анализ вершин ведется вдоль одной ветви схемы, пока не будет достигнута максимальная глубина (последняя вершина или вершина, для которой величина критерия оптимальности превосходит значение, полученное ранее,при движении по другим ветвям). Затем рассматриваются альтернативные пути той же или меньшей глубины, которые отличаются последним шагом. После этого рассматриваются пути, отличающиеся последними двумя шагами, и т. д. Вид дерева вариантов при таком поиске приведен на рис. 8.2,а, где порядок приоритета исследования получаемых вершин обозначен цифрами. Легко заметить, что при некорректном расчете вершин (например, по упрощенным моделям) вероятность потери оптимального варианта высокая. Углубляющийся поиск характерен для методов ветвей и границ, когда граничная оценка делается на основании просмотра одной из ветвей дерева. Сюда же можно отнести и процедуру разветвляющегося направленного поиска [41. [c.441]

Алгоритм упорядоченного поиска системы разделения. Алгоритм основан па использовании а) процедуры упорядоченного поиска оптимального варианта схемы на дереве вариантов б) ограничений, полученных на этапе анализа физико-химических и термодинамических свойств компонентов и смесей в) оценки вероятной стоимости незавершенной части схемы г) оценки возможности рекуперации тепла целевых и промежуточных потоков [52-54]. [c.488]

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

Рассмотрим применение алгоритма на примере разделения четырехкомпонентной смеси х,, х , х , компоненты которой расположены в порядке уменьшения коэффициентов относитель ной летучести. Смесь подлежит разделению на относительно чистые компоненты путем простой ректификации. Пространство поиска можно представить в виде дерева вариантов (рис. 8.16), вершина В которого является корнем дерева, соответствующим входу в систему исходной смеси. Остальные вершины qi представляют собой стадии получения завершенной схемы разделения, ведущие к целевой вершине, соответствующей завершенному варианту схемы, т. е. ситуации, когда все целевые продукты выделены. Связи между вершинами (дуги) соответствуют операторам разделения min) (г, / ) [q, которые служат для перехода из какой-либо вершины qi к желаемой вершине qj с помощью оператора Г и точки деления min (где т — легколетучий ига — тяжелолетучий компоненты в точке деления смесив. Каждой связи (дуге), соеди- [c.490]

Неравенство (8.41) является достаточным условием применимости алгоритма для нахождения пути минимальной стоимости (оптимального варианта технологической схемы). Это означает, что функция g является нижней границей и она может быть равна действительной стоимости только для завершенной схемы. Следовательно, если при раскрытии некоторой вершины другого пути действительная стоимость незавершенной схемы окажется больше эвристической, то эта ветвь дерева вариантов в дальнейшем не будет рассматриваться. Например, пусть при раскрытии вершины q (см. рис. 8.16) была получена оценочная функция g В, Т). Тогда, если при раскрытии вершины <7я (расчете колон- [c.492]

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

Рассчитанное граничное значение оказалось меньше всех оценочных стоимостных функций для области, которая исследовалась, что исключило необходимость дальнейшего проведения синтеза. Всего было просмотрено 22 вершины дерева вариантов при общем количестве 56. Оптимальная технологическая схема, полученная в результате синтеза, приведена на рис. 8.21. Здесь же приведены варианты схем, отличающиеся от оптимальной по затратам на 1 %. Количества и1 составы потоков оптимальной технологической схемы приведены в табл. 8.14. [c.509]

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

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

Поиск решений НФЗ в пространстве состояний отображается с помощью семантического графа, называемого деревом вариантов решений. [c.73]

Процедура сопоставления с фактами условия ПП (6.1) при поиске решения НФЗ порождает дерево вывода решений, или дерево вариантов решений (см. разд. 2.5), представляюш,их собой совокупность цепочек вывода. Результат решения НФЗ в виде ДВР хранится в БД, или в рабочей БЗ продукционной системы. [c.166]

Рассмотрим алгоритмы упорядоченного ограниченного перебора решений НФЗ на дереве вариантов решений (см. разд. 2.2 и 2.5). [c.183]

Для поиска оптимальных решений ИЗС используют три операции упорядоченного перебора вершин дерева вариантов волнового ветвления, лучевого ветвления и волно-лучевого ветвления. Каждая из этих операций устанавливает порядок выбора из всех висячих вершин только активных вершин, отображающих перспективные решения задач синтеза [158]. Чтобы в процессе поиска решений ИЗС можно было определять некоторое множество квазиоптимальных структур ХТС испсмьзуют модифицированное значение верхней границы Q = aQ-, 1<а<1,3. Коэффициент а позволяет осуществить выбор с учетом различ- [c.130]

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

К таким комбинированным методам относятся методы, предложенные в работах [42, 51 ]. Разница между работами состоит в том, что на нижнем уровне применяются различные комбинаторные подходы. В работе [42] применяется метод поиска на дереве вариантов с оценочной функцией. На этом методе мы подробно остановимся в разд. 1У.5.7. В работе [51 ] на нижнем уровне решается задача о назначениях. На верхнем уровне интервал температур от до Гк делится на т подинтервалов Т ,. .., Гг т-1, г.к и [c.147]

Рис. 8.3. Дерево вариантов решений з дач оптимизации поэлементного резервирования технической системы (Ха, л ьлГт-1 множество нецелочисленных решений задачи оптимального резервирования Хм — допустимое целочисленное решение)

Какой бы способ построения дерева вариантов не использовался, максимальное число висячих вершин, или вариантов, или ветвей равно т". Это число может быть весьма велико тогда полное построения дерева становится практически невозможным. Другими словами, для больших комбинаторных задач (с большими т и, особенно, п) решение путем перебора всех вариантов невозможно. [c.152]

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

Если параметры вектора не удовлетворяют требованию целочисле ност , то решение Хо декомпозируется н два jioBbix решения Xi и Х2. Если все решения, следующие за Xi и Х2, недопустимы, то осущ твляется повторная декомпозиция на базе исходного решения Ха решаются две граничные задачи линейного программирования с дополнительными ограничениями Xk = = л м1—1 и Xk2= Xko +2. Любая /-я вершина дерева вариантов решений (см. рис. 8.3) с нецелочисленным Xkt может иметь много вершин-потомков, соответствующих решениям граничных ЗЛП с дополнительными ограничениями Xk,i+ = Xkj, Xk,j+2= = 1,..., Xk,i+r= Xki + , Xk,i+r+i= Xki +2,... В процес- [c.222]

Декомпозиция исходной задачи оптимизации резервирования системы также осуществляется на каждом уровне ветвления и заключается в следующем. Фиксируемые переменные Х1 (/ = = 1,Л ) в активных вершинах дерева вариантов решений выбираются таким образом, чтобы как можно больше исключить из рассмотрения (отсеить) вершин дерева вариантов решений и снизить при этом размерность решаемых задач оптимизации. В связи с этим рекомендуют [241] фиксировать переменные XI 1=, М) в порядке возрастания разности как между верхними целыми значениями, так и между нижними целыми значениями переменных хю Х (1=1,N). Однако в предложенном методе выбора фиксируемых переменных [241] не учитывается их влияние на удельное повышение показателя надежности системы в целом. [c.224]

Большое число алгоритмов синтеза построено с использованием метода ветвей и границ [5, 20—22]. Основная идея алгоритмов состоит в последовательной генерации дерева вариантов, включающего все возможные системы теплообмена. Наряду с процедурой снижения размерности задачи в работе [20] предложен удачный способ формализации изображения систем теплообмена в виде матрицы связей потоков. На рис. 8.5 приведены система из двух холодных (0г) и трех горячих потоков (Я ) п соответствующая ей матрица связей, в клетках которой помещены номера теплообменников. Подобное представление (как и сам метод поиска) справедливо для систем без рециклических потоков. [c.458]

Процесс синтеза технологической схемы удобно представить в виде дерева вариантов (рис. 8.20 . Построение дерева начинается с генерации дочерних вершин исходной вершины , которая соответствует входу в систему исходной смеси компонентов (а 1Х2.. . х . При этом все массивы контрольного списка обнуляются, а в матрице связей сохраняются индексы 4 и 5, соответствующие вариантам схем с рекуперацией тепла. После построения вершин 1, 21 м рассчитываются действительные и эвристи- [c.504]

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

Рис. 2.5. Семантический г)>а( ) (дерево) вариантов решений исходной задачи синтеза системы ректификации т1>ехкомпонентной смеси (А, В, С) с выделением т]1ех продуктов

Рис. 2.12. Процедура поиска иа дереве вариантов решений способом в глубину (а) и в 1нир1н1у (б)

Недетерминированность процедур вывода решений НФЗ обусловлена тем, что знания накапливаются фрагментарно и нельзя а приори определить цепочку логических выводов, в которых они используются. Иными словами, необходимо методом проб и ошибок выбрать на дереве вариантов решений (ДВР) некую цепочку выводов и в случае неуспеха организовать перебор с возвратами для поиска другой цепочки и т, д. Такое управление процедурами вывода решений НФЗ является предпосылкой проявления гибкости и интеллектуальных способностей, позволяющих найти выход в различных ситуациях. [c.96]

В соответствии с математическими формулировками стратегий декомпозиции множества решений НФЗ, представленными соотношениями (6.7)—(6.10) предлагаются три алгоритма упорядоченного ограниченного перебора на дереве вариантов решений (ДВР), или три вида порождающих процедур построения для некоторого имплицитного ДВР усеченного эксплицитного дерева (см. разд. 2 5) процедуры перебора вершин волновым ветвлением , лучевым ветвлением и лучеволновым ветвлением 10]. [c.183]

Блок Б4 ( Блок вывода решений ) используется для поиска оптимального варианта размещения ЕО и трассировки ТП. Блок программно реализует процедуры генерации дерева вариантов решения с использованием различных стратегий бетвления (лучевого, волнового и луче-волнового — см. разд. 2.5 и 6.3), а также процедуру метода резолюций при использовании ПрФМ представления знаний. Блок написан на языках Пролог и Фортран-77 , требуемый объем памяти — 100 Кбт. [c.346]

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

Таким образом, применение Zq. бл для сокращения дерева вариантов уже не гарантирует получение точного решения. Но благодаря относительной близости к Zmin (IV.14) применение Zo. бл приводит к значительно большему сокращению числа вариантов. Поэтому Zo бл можно применять для решения реальных больших ЗС ОХТС. [c.118]

Сущность комбинаторных методов состоит в том, что для решения задачи строится дерево вариантов или порфириан. В общем виде дерево вариантов приведено на рис. IV.27. Применяются два способа построения дерева вариантов [c.151]

Когда дерево вариантов построено, решение комбинаторной задачи находится следующим образом для всех висячих вершин, для которых 5/ = в", ввчисляется критерий К ,- = /С (в , [c.152]

Работы в области исследования операций [49] и я1скусственного интеллекта [38, 50] направлены на сокращение дерева вариантов. Для оценки сокращения дерева вариантов в результате тех или иных приемов используются следующие показатели целенаправленность О и степень ветвления Я О = 1т/М, где М <с т — число построенных в сокращенном дереве вершин [c.152]

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

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