Учебная САПР электронных средств. Асланянц В.Р. - 31 стр.

      Могут быть заданы ограничения на взаимное назначение некоторых
цепей на выводы узла, например для усилителя следует разнести его вход-
ные и выходные цепи.
      Математические модели
      Задачу РЦВУ можно формально описать с помощью полного дву-
дольного графа, взвешенного по ребрам. Вершины одной доли графа –
внешние электрические цепи (т.е. те, которые необходимо вывести из кон-
структивного узла), вершины второй доли – внешние выводы узла (т.е.
контакты соединителей узла).
      Вес Еik ребра двудольного графа рассчитываются как кратчайшая
длина проводника при назначении i-ой электрической цепи на k-й вывод
соединителя.
      Результат решения задачи РЦВУ – максимальное паросочетание
двудольного графа с минимальным весом ребер.
      Формализованная формулировка задачи
      Техническая задача РЦВУ сводится к математической задаче опре-
деления на взвешенном по ребрам полном двудольном графе максималь-
ного паросочетания с минимальным весом ребер.
      Сведения к задаче математического программирования
      С использованием введенной математической модели РЦВУ можно
свести к линейной задаче оптимального назначения [7]. Это частный слу-
чай целочисленного линейного программирования (ЦЛП).
      Алгоритмы РЦВУ
      1. Венгерский алгоритм.
      2. Метод ветвей и границ (МВГ).
      3. Последовательный алгоритм.
      4. Дихотомический алгоритм.
      Первые два алгоритма дают точное решение, остальные алгоритмы –
эвристические.

                    4.3. Описание программы PLACE-3

     В программе PLACE-3 для размещения элементов реализован алго-
ритм парных перестановок [1, 5, 6]. Схема программы представлена на рис.
5.




                                                                      31