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

следующей трассировки проводников;
      - электрические: минимум искажения логических сигналов в провод-
никах, минимальная задержка сигнала и др.
      - тепловые: равномерное распределение тепловыделяющих элемен-
тов по плате и т.п.
      В большей или меньшей степени эти цели достигаются за счет при-
менения следующих простых (быстро считаемых) критериев качества.
      1. Минимум суммарной длины соединений.
      2. Минимум длины самого длинного проводника.
      3. Максимум числа цепей, которые соединяют элементы, находя-
щиеся в соседних посадочных местах.
      4. Минимум числа пересечений проводников.
      5. Максимум числа соединений с возможно более простой конст-
рукцией.
      Ограничением задачи часто является ограничение на длину самого
длинного проводника (или конкретных проводников), что определяет вре-
мя распространения сигнала в этих проводниках, подверженность поме-
хам.
      Математические модели (ММ) объектов проектирования
      (электрической схемы и монтажного пространства)
      В качестве ММ схемы обычно применяется граф, взвешенный по
ребрам. Методика расчета весов ребер изложена в [2].
      ММ монтажного пространств – регулярная прямоугольная решетка,
каждая ячейка которой определяет соответствующее посадочное место.
      Формализованная формулировка задачи
      В терминах введенных математических моделей техническую задачу
размещения элементов в монтажном пространстве можно сформулировать
как математическую задачу оптимального вложения взвешенного по реб-
рам графа в прямоугольную решетку.
      Сведения к задаче математического программирования
       С использованием введенных математических моделей задачу раз-
мещения можно свести к хорошо изученной задаче квадратичного назна-
чения [7]. Это комбинаторная задача экстремального типа относится к
классу дискретных нелинейных оптимизационных задач (дискретное не-
линейное программирование).




                                                                    29