ПОИСК Статьи Рисунки Таблицы Алгоритм оптимального разрыва циклов из "Моделирование сложных химико-технологических схем" Принятый критерий оптимальности мы обсудим несколько ниже. [c.76] необходимо найти такую совокупность дуг в комплексе, разрыв которых превращает комплекс в разомкнутую схему, причем величина 7 принимает наименьшее значение. Если размерности всех дуг равны, принятый критерий требует, чтобы было разорвано минимальное число дуг. [c.76] Отсюда задачу можно сформулировать следующим образом найти такие т двоичных переменных 2,-, удовлетворяющих условиям (IV,54), чтобы критерий (IV,55) принял минимальное значение. Эта задача является стандартной и для ее решения могут быть применены методы дискретного программирования. Правда, следует отметить, что какого-то одного универсального метода решения не существует имеются методы, обладающие достоинствами и недостатками, иногда довольно серьезными. В связи с этим мы здесь изложим развитие предложенного в работе [3, с. 110] метода решения указанной задачи, который не сводится к известным методам дискретного программирования. [c.77] В этой ситуации алгоритм предусматривает исключение Х2 из М/1. В условии (IV,56) вместо Т (Х , Х ) может фигурировать любое множество дуг, которое служит разрывающим для множества циклов Е Х Е (Х1), но при использовании Т (Х1, Хз) лишние множества отсеиваются наиболее полно. [c.78] Обоснование алгоритма дано в работе [И]. [c.79] Применение правил 1°—3° позволяет в ряде случаев существенно ул1еньшить размерность матрицы циклов. [c.80] Важным вопросом, связанным с реализацией алгоритма, является организация памяти для хранения мнон еств Для их запоминания должен быть выделен двумерный массив размерности т X п (п — максимально возможное число разрывающих множеств потоков в Mfe, т — максимально возможное число потоков в разрывающем множестве). В качестве т можно, очевидно, взять величину min т, п). Указать верхнюю оценку для п, не являющуюся слишком завышенной, однако, значительно сложнее. Практика счета показала, что оценка п = т обычно оказывается взятой с большим запасом. [c.80] На основе описанного выше алгоритма была составлена программа на языке алгол-60 , являющаяся составной частью общей программы структурного анализа сложных схем. В табл. 6 представлены некоторые данные о работе этой программы [с условием исключения (IV,58)] при определении ОРМ для некоторых сложных схем, а также для сравнения приведены сведения о работе программы использующей алгоритм, описанный в статье [10]. [c.81] Расчеты проводились на вычислительной машине Elliot (модель NE 4100) со средним быстродействием 100 ООО операций в секунду с применением правил предварительного исключения 1°—3°. [c.81] Вернуться к основной статье