2.4.7. Методы распространения ограничений

Во многих задачах оптимизации и структурного синтеза мно­жество D допустимых вариантов, задаваемое ограничениями W(X) > 0 и/или Z(X) = 0, где X - множество управляемых пере­менных, включает сравнительно малое число элементов и в каче­стве результатов синтеза принимается любой из этих вариантов. Такое решение задачи часто выполняют с помощью метода рас­пространения ограничений.

Сущность этого метода заключается в сужении допустимых интервалов управляемых переменных X с помощью учета (распространения) исходных ограничений на выходные параметры W и Z.

Для пояснения метода рассмотрим простой пример.

П р и м е р 4. Пусть в задаче фигурируют три управляемые переменные х, у, z, заданы исходные интервалы допустимых значений этих переменных х є [1:100], у є [1:100], z є [10:100], а область D определена ограничениями

(2

х + у ≥ 5z,

х≥ у+5.

Распространение ограничения (2.2) на интервал переменной z приводит к уменьшению его верхней границы, поскольку z≤ (хтт+ + уmах)/5 = 40 , а с учетом ограничения (2.3) - к ее новой корректи­ровке z ≤ 39, ибо уmах= 95, и к увеличению нижних границ перемен­ных х и у, так как решение неравенств х + у ≥ 50 и (2.3) дает х ≥ 28, у ≥ 22. Таким образом, получено сужение допустимой области х є [28:100], y є [22:95], z є [10:39].

Метод легко распространяется на задачи с нечисловыми пара­метрами. В этом случае вместо сокращения числовых интервалов уменьшают мощности допустимых подмножеств значений пара­метров.

Одним из практических приложений метода распространения ограничений является поиск допустимых вариантов в множестве синтезируемых структур при ограничениях на совместимость эле­ментов структуры.

ПримерЗ. Рассмотрим фрагмент структуры, состоящий из трех компонентов А, В и С, причем А е {а1, а2, а3, а4, а5}, В е {bl ,b2, b3, b4}, С е {с1, с2, съ}. Заданы списки допустимых сочетаний компонентов в синтезируемой структуре:

LI: a2, b1; а2, b1; а4,b2; а5 ,b3; а5, b4;

L2: b1, с1; b3 с3; b4, с1; b4, с2;

L3: а2, с3; а3, с2,;а4, с3;а5,с2.

Сокращение первого списка выполняется путем поочередного выбора в нем аi, фиксации в L3 соответствующих значений ck, a затем в L2 сопряженных с ck значений bj. Если в L1 имеется элемент аi, bj, то он сохраняется в сокращенном списке, остальные сочетания с аi из L1 удаляются. В нашем примере, поскольку значения al в L3 нет, сочетание аi, bj недопустимо и из L1 удаляется. Далее для символа аг фиксируем в L3 значение с3, ему в L2 соответствует только значение b3. Поэтому а2,, b1 - также недопустимое сочетание. Обработав подобным образом все списки, получаем результат распространения ограничений в виде

Ll:a5, b4; L2: b4, c2; L3:a5, с2.

Следовательно, решение состоит из единственной допустимой структуры, включающей компоненты а5 ,b4 , сг.

В общем случае сокращение списков выполняется в итерацион­ном процессе до совпадения их содержимого на двух последних итерациях.