УСТРОЙСТВО для МОДЕЛИРОВАНИЯ ЗАДАЧИ ОБ ЭКСТРЕМАЛЬНОМ ПУТИ Советский патент 1968 года по МПК G06G7/122 

Предложенное устройство для моделирования задачи об экстремальном пути относится к области вычислительной техники и может быть использовано для решения задачи об отыскании элементарных контуров с наименьшей (наибольшей) длиной, проходяш,их через Заданные узлы. Эта задача часто возникает в экономике и в автоматическом управлении (например, к ней сводятся задача о назначениях и во многих случаях задача коммивояжера).

Известные устройства для моделирования задачи о кратчайшем и длиннейшем путях, основанные на установлении пути потока в соответствии с принципом минимизации мош,ности, выделяемой в модели, топология которой совпадает с топологией моделируемой сети, позволяют решать простейшие задачи нахождения экстремального пути, проходящего через два заданных узла. Суш,ествуют важные задачи (например, задача коммивояжера и задача о назначениях), сводящиеся к нахождению экстремального пути, проходящего через заданные узлы сети, число которых больше двух, и в предельном случае могут быть решены на известных устройствах. Кроме того, решение задачи о длиннейшем пути возможно лишь для сетей, не содержащих замкнутых контуров в модели сетевого планирования; решение же этой задачи для сетей

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

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

Кроме того, с целью упрощения решения задачи отыскания в сети контуров с наибольшей суммарной длиной, во все узлы модели, кроме заданных, включены блоки ограничения потока так, что модели всех входящих в узел дуг подсоединены своими выходными зажимами к одному зажиму блока ограничеиия, а модели всех исходящих дуг соединены своими входными зажимами с другим зажимом блока ограничения потока.

Па фиг. 1 .изображен участок модулируемой сети; на фиг. 2 - модель этого участка при условии выделения узла; на фиг. 3 - модель того же участка для случая, когда узел не выделен и решается задача определения контуров с максимальной длиной.

Пусть узел / - заданный узел, т. е. через него по условию задачи должен проходить искомый путь.

При моделировании этого участка сети в устройстве все дуги, присоединеииые к узлу, делятся на две группы: входящие 2 и 5 и исходящие 4 и 5. Каждая группа соединяется между собой и образует соответственно точки входа 6 и выхода 7, между которыми помещается источник потока 8 (аналогичным образом - во всех остальных заданных узлах сети). Такое построение модели обеспечивает прохождение искомого пути через выделенные узлы.

Для рещения задача определения контуров с максимальной длиной во все узлы модели сети, кроме заданных, вводятся блоки 9 ограничения потока, в заданные же узлы вводятся так же, как и в первом случае, источники потока равной величины.

Предмет изобретения

1. Устройство для моделирования задачи об экстремальном пути, содержащее модели дуг.

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

2. Устройство но п. 1, отличающееся тем, что, с целью упрощения решения задачи отыекания в сети контуров с наибольшей суммарной длиной, во все узлы модели, кроме заданных, включены блоки ограничения потока так, что модели всех входящих в узел дуг подсоединены своими выходными зажимами к одному зажиму блока ограничения, а модели всех исходящих дуг соединены своими входными зажимами с другим зажимом блока ограничения нотока.