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

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

Иллюстрации

Показать все

Реферат

 

О П И С А H И Е 220642

ИЗОБРЕТЕНИЯ

Союз Советских

Социалистических

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ,т®4 . Я;. д

Зависимое от авт. свидетельства №

Заявлено 20.11.1967 (№ 1135909/26-24) Кл. 42птт, 7/48 с присоединением заявки №

МПК G 06g

УДК 681.33.001.57 (088.8) Приоритет

Опубликовано 28.VI.1968. Бюллетень № 20

Дата опубликования описания 2.Х.1968

Комитет по делам изобретений и открытий при Совете Министров

СССР

Авторы изобретения Л. Г. Александрова, И. М, Витенберг, Е. Ф. Ефремова, Л. Д. Райков и

И. Л. Хранович

Заявитель

УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ЗАДАЧИ ОБ

ЭКСТРЕМАЛЬНОМ ПУТИ

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

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

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

Кроме того, с целью упрощения решения задачи отыскания в сети контуров с наибольшей суммарной длиной, во все узлы модели, кроме заданных, включены блоки or ðàíè÷åния потока так, что модели всех входящих в

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

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

ЗО контуров с максимальной длиной.

220642

@Llew 1 ( б

Составитель Л. Б. Дмитриева

Текред P. М. Новикова Корректор H. И. Быстрова

Редактор Е. В. Семанова

Заказ 2839/1 Тираж 530 Подписное

ЦНИИПИ Комитета по делам изооретсиий и otêðürrr.é при Совете Министров СССР

Москва, Центр, пр. Серова, д. 4

Типография, пр. Сапунова, 2

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

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

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

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

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

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