Устройство для моделирования задачи об экстремальном пути

Республик К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 4 иау дц,исимое от идетельства42 пт 4, 7/48 Заявлен 1.1967 ( 113590 рисоединением заявкиМПК 6 06 дУДК 681.33.001.5088.8) орит Комитет по делам зобретений и открытийпубликовано 28.Ч 1,1968. Бюллетень2ата опубликования описания 2.Х.1968 и Совете Министров СССР Авторыизобретения Л, Г. Александрова, И. М, Витенберг, Е. ф. ЕфИ. Л. Хранович ова, Л. Д. Раиков Заявите ТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИ ЭКСТРЕМАЛЬНОМ ПУТ АЧИ О Предложенное устройство для моделирования задачи об экстремальном пути относится к области вычислительной техники и может быть использовано для решения задачи об отыскании элементарных контуров с наименьшей (наибольшей) длиной, проходящих через Заданные узлы. Эта задача часто возникает в экономике и в автоматическом управлении (например, к ней сводятся задача о назначениях и во многих случаях задача коммивояжера).Известные устройства для моделирования задачи о кратчайшем и длиннейшем путях, основанные на установлении пути потока в соответствии с принципом минимизации мощности, выделяемой в модели, топология которой совпадаег с топологией моделируемой сети, позволяют решать простейшие задачи нахождения экстремального пути, проходящего через два заданных узла. Существуют важные задачи (например, задача коммивояжера и задача о назначениях), сводящиеся к нахождению экстремального пути, проходящего через заданные узлы сети, число которых больше двух, и в предельном случае могут быть решены на известных устройствах. Кроме того, решение задачи о длиннейшем пути возможно лишь для сетей, не содержащих замкнутых контуров в модели сетевого планирования; решение же этой задачи для сетей общего вида, например транспортной, невозможно, так как в этом случае система уравнений, описывающая модель, несовместима.Предложенное устройство отличается тем,что, с целью упрощения решения задачи выделения элементарных контуров, проходящих через заданные узлы, с экстремальной суммарной длиной, в заданные узлы введены источники потока. Модели всех входящих в 10 узел дуг подсоединены своими выходными зажимами к Одному зажим 7 источника потока 1 а модели всех исходящих дуг подсоединены своими входными зажимами к другому зажиму источника потока.15 Кроме того, с целью упрощения решениязадачи отыскания в сети контуров с наибольшей суммарной длиной, во все узлы модели, кроме заданных, включены блоки ограничения потока так, что модели всех входящих в 20 узел дуг подсоединены своими выходными зажимами к одному зажиму блока ограничения, а модели всех исходящих дуг соединены своими входными зажимами с другим зажимом блока ограничения потока.25 На фиг. 1 изображен участок модулируемой сети; на фиг. 2 - модель этого участка при условии выделения узла; на фиг. 3 - модель того же участка для случая, когда узел не выделен и решается задача определения 30 контуров с максимальной длиной.220642 Составитель Л, Б. ДмитриеваТекред Р. М. Новикова Корректор Н, И. Быстрова Редактор Е. В. Семанова Тирак 530 по делагв изооретепий и огкрьгтий при С Москва, Центр, пр. Серова, д. 4Подписио те Министров ССС 1Заказ 2839,1ЦНИИПИ Комите Типография, пр. Сапунова Пусть узел 1 - заданный узел, т, е. через него по условию задачи должен проходить искомый путь.При моделировании этого участка сети в устройстве все дуги, присоединенные к узлу, делятся на две группы: входящие 2 и 3 и исходящие 4 и 5, Каждая группа соединяется между собой и образует соответственно точки входа б и выхода 7, между которыми помещается источник потока 8 (аналогичным образом - во всех остальных заданных узлах сети). Такое построение модели обеспечивает прохождение искомого пути через выделенные узлы.Для решения задача определения контуров с максимальной длиной во все узлы модели сети, кроме заданных, вводятся блоки 9 ограничения потока, в заданные же узлы вводятся так же, как и в первом случае, источники потока равной величины. Предмет изобретения 1. Устройство для моделирования задачи обэкстремальном пути, содержащее модели дуг,соединенные согласно топологии исследуемой сети, от,ггсчагогчееая тем, что, с целью упрощения решения задачи выделения элементарных контуров, проходящи.; через заданные узлы, 5 с экстремальной суммарной длиной, в заданные узлы введены источники потока, причем модели всех входящих в узел дуг подсоединены своими выходными зажимами к одному зажиму источника потока, а модели всех исхо дящих дуг подсоединены своими входными зажимами к другому зажиму источника потока. 2, Устройство по п. 1, отличающееся тем,что, с целью упрощения решения задачи отыскания в сети контуров с наибольшей суммарной длиной, во все узлы модели, кроме заданных, включены блоки ограничения потока так, что модели всех входящих в узел дуг подсоединены своими выходными зажимами к одному зажиму блока ограничения, а модели всех исходящих дуг соединены своими входными зажимами с другим зажимом блока ограничения потока.