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

      • градиентный метод;
      • метод наискорейшего спуска;
      • метод покоординатного спуска;
      • метод штрафных функций;
      • метод случайного поиска.
      Указанные методы обеспечивают нахождение одного из локальных
экстремумов. Для отыскания глобального экстремума применяют:
      • метод «кенгуру и мыши»;
      • метод Монте-Карло.
      Динамическое программирование – процесс решения естествен-
ным образом (или искусственно) распадается на этапы, и значение функ-
ции F определяется как сумма (произведение) соответствующих значений
F на отдельных этапах, т.е. целевая функция F аддитивна (мультиплика-
тивна).
      Примером может служить задача отыскания кратчайшего пути на
взвешенном по ребрам графе, для решения которой может быть применен
алгоритм Беллмана-Калаба. Частный случай этой задачи – трассировка
проводников на печатной плате, для которой применяется волновой алго-
ритм [6].
      Стохастическое программирование – параметры Z – случайные
величины, и вместо функции F отыскивается экстремум ее математическо-
го ожидания.
      Дискретное программирование – на X, Z наложено условие дис-
кретности (например, целочисленности), т.е. область определения D пред-
ставляет собой конечное множество. В зависимости от вида функции F и q
задачи дискретного программирования могут быть линейными (целочис-
ленное линейное программирование - ЦЛП) и нелинейными (дискретное
нелинейное программирование - ДНП).
      Для решения задач ЦЛП применяют:
      • метод отсечений, основанный на многократном применении сим-
плекс-метода;
      • метод ветвей и границ;
      • итерационные эвристические алгоритмы, которые можно назвать
дискретными аналогами градиентных методов и др.
      Для решения задач ДНП применяют:
      • метод ветвей и границ;




                                                                      9