83247

Нелинейное и динамическое программирование

Доклад

Информатика, кибернетика и программирование

Задача поиска наибольшей увеличивающейся подпоследовательности: дана последовательность требуется найти самую длинную возрастающую подпоследовательность. Задача о редакционном расстоянии расстояние Левенштейна: даны две строки требуется найти минимальное количество стираний...

Русский

2015-03-12

42.96 KB

3 чел.

Нелинейное и динамическое программирование

Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой (англ.), выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.

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

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

Классические задачи динамического программирования

  1.  Задача о наибольшей общей подпоследовательности: даны две последовательности, требуется найти самую длинную общую подпоследовательность.
  2.  Задача поиска наибольшей увеличивающейся подпоследовательности: дана последовательность, требуется найти самую длинную возрастающую подпоследовательность.
  3.  Задача о редакционном расстоянии (расстояние Левенштейна): даны две строки, требуется найти минимальное количество стираний, замен и добавлений символов, преобразующих одну строку в другую.
  4.  Задача о вычислении чисел Фибоначчи
  5.  Задача о порядке перемножения матриц: даны матрицы , …, , требуется минимизировать количество скалярных операций для их перемножения.
  6.  Задача о выборе траектории
  7.  Задача последовательного принятия решения
  8.  Задача об использовании рабочей силы
  9.  Задача управления запасами
  10.  Задача о ранце: из неограниченного множества предметов со свойствами «стоимость» и «вес» требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при ограниченном суммарном весе.
  11.  Алгоритм Флойда — Уоршелла: найти кратчайшие расстояния между всеми вершинами взвешенного ориентированного графа.
  12.  Алгоритм Беллмана — Форда: найти кратчайший путь во взвешенном графе между двумя заданными вершинами.
  13.  Максимальное независимое множество вершин в дереве: дано дерево, найти максимальное множество вершин, никакие две из которых не связаны ребром.

Нелинейное программирование (NLPангл. NonLinear Programming) — случай математического программирования, в котором целевой функцией или ограничением являетсянелинейная функция.

Задача нелинейного программирования ставится как задача нахождения оптимума определенной целевой функции  при выполнении условий

где  — параметры,  — ограничения,  — количество параметров,  — количество ограничений.

В отличие от задачи линейного программирования, в задаче программирования нелинейного оптимум не обязательно лежит на границе области, определенной ограничениями.

Методы решения задачи

Одним из методов, которые позволяют свести задачу нелинейного программирования к решению системы уравнений, является метод неопределенных множителей Лагранжа.

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

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

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

Существуют несколько методов для решения невыпуклых задач. Один подход заключается в использовании специальных формулировок задач линейного программирования. Другой метод предусматривает использование методов ветвей и границ, где задача делится на подклассы, чтобы быть решенной с выпуклыми (задача минимизации) или линейными аппроксимациями, которые образуют нижнюю границу общей стоимости в пределах раздела. При следующих разделах в определенный момент будет получено фактическое решение, стоимость которого равна лучшей нижней границе, полученной для любого из приближенных решений. Это решение является оптимальным, хотя, возможно, не единственным. Алгоритм можно прекратить на ранней стадии, с уверенностью, что оптимальное решение находится в рамках допустимого отклонения от найденной лучшей точки; такие точки называются ε-оптимальными. Завершение ε-оптимальных точек, как правило, необходимое для обеспечения конечности завершения. Это особенно полезно для больших, сложных задач и задач с неопределенными расходами или значениями, где неопределенность может быть определена из соответствующей оценки надежности.

Дифференцирование и условия регулярности, условия Каруша — Куна — Такера (ККТ) обеспечивают необходимые условия оптимальности решения. При выпуклости, эти условия являются и достаточными.


 

А также другие работы, которые могут Вас заинтересовать

20211. НЕОБСЛУЖИВАЕМЫЙ РЕГЕНЕРАЦИОННЫЙ ПУНКТ НРП-К12 СИСТЕМЫ ПЕРЕДАЧИ ИКМ-30 57.5 KB
  Ознакомиться с составом оборудования и конструкцией НРПК12 ИКМ30. Изучить структурную схему НРП. Оборудование НРП.
20212. ПРИНЦИПЫ ПОСТРОЕНИЯ МНОГОКАНАЛЬНОЙ СИСТЕМЫ ПЕРЕДАЧИ С ЧАСТОТНЫМ РАЗДЕЛЕНИЕМ КАНАЛОВ 1.32 MB
  Источниками первичных сигналов являются генераторы синусоидальных сигналов Г. Зарисовать осциллограмму следующих сигналов: первичных сигналов первого второго и третьего каналов форму напряжений на выходе генераторов Г; несущих частот этих каналов гнезда 789; на выходе каждого модулятора предварительно соединив дужкой источник первичного сигнала с соответствующим модулятором; на выходе каждого канального фильтра; группового сигнала: а для случая одного канального сигнала; б для случая двух канальных сигналов; в для случая трех...
20213. ИЗУЧЕНИЕ ПРИНЦИПОВ ПОСТРОЕНИЯ АППАРАТУРЫ МНОГОКАНАЛЬНОЙ СВЯЗИ С РАЗДЕЛЕНИЕМ КАНАЛОВ ПО ВРЕМЕНИ 77.5 KB
  Соединив гнезда 12 14 и 16 17 включают между ними усилитель имитирующий линию с нелинейными искажениями. Зарисовать осциллограмму следующих сигналов: первичных сигналов одного канала например первого гнездо 1; групповой сигнал на выходе сумматора гнездо 12 предварительно соединив дужкой гнезда 1 2; сигналы в точках 26 и 29 соединив дужками гнезда 12 13 15 17. Групповой сигнал на выходе сумматора гнездо 12 при подключении всех трех каналов соединив дужками гнезда 2 4 5 6. Подключить усилитель имитирующий линию с...
20214. ИССЛЕДОВАНИЕ ЭЛЕКТРИЧЕСКИХ ХАРАКТЕРИСТИК КАНАЛА ТОНАЛЬНОЙ ЧАСТОТЫ 90.5 KB
  Исследование основных электрических характеристик канала тональной частоты ТЧ. Изучение характеристик канала ТЧ и методов их измерения. Измерение характеристик канала ТЧ.
20215. Система передачи ИКМ – 30 61.5 KB
  В системе ИКМ 30 для каждого канала ТЧ организуются по два специально выделенных канала СК1 и СК2 для передачи сигналов взаимодействия и управления с УВ сигналы. Циклы и сверхциклы ИКМ 30 мы уже рассматривали ранее. В настоящее время выпускается система ИКМ304 четвертого поколения с сервисным оборудованием мирового уровня.
20216. Синхронная цифровая иерархия 47.5 KB
  Такой путь признан мировым сообществом в качестве оптимального и для его реализации разработана технология СИНХРОННОЙ ЦИФРОВОЙ ИЕРАРХИИ СЦИ Synchronous Digital Hierarchy SDH.707 МККТТ приводятся его следующие преимущества: упрощённая техника объединения разделения цифровых потоков; прямой доступ к компонентам без необходимости расшивки всего потока; расширение возможностей эксплуатации в сети и технического обслуживания; лёгкий переход ко всё более высоким скоростям передачи; возможна передача как сигналов SDH систем так и PDH...
20217. Среды передачи Секций мультиплексных Волоконно – оптическая сеть регенерационных Физическая среда 69 KB
  Сеть каналов слой обслуживающий пользователей содержит электронные АТС обеспечивающие подключение терминалов пользователей к тем или иным комплектам оконечных АТС системы SDH. Горизонтальное деление структуры сети SDH дополняется вертикальным на подсети например международные национальные межзоновые соединённые друг с другом соединительными линиями. На первом этапе пока SDH системы не являются основными в задачу создаваемых SDH сетей входит передача потоков образованных РDH системами. Для адаптации РDH потоков для компенсации...
20218. ОПРЕДЕЛЕНИЕ ОПТИМАЛЬНОГО БЫСТРОДЕЙСТВИЯ ПРОЦЕССОРА 58.88 KB
  Исследование способов организации вычислительного процесса в цифровых управляющих системах и определение быстродействия процессора ЭВМ. В ходе выполнения работы студент знакомится с основными способами организации вычислительного процесса для различных режимов работы
20219. Обобщённая структурная схема ЦСП 44.5 KB
  С выхода АЦП получаемый ИКМ сигнал объединяется с необходимыми сигналами сигнализации сигналами синхронизации СС дискретной информации ДИ и сигналами управления и взаимодействия СУВ. потеря синхронизации. Поэтому вопросам синхронизации в ЦСП уделяют особое внимание. Устройство временного разделения ВР демультиплексор разделяет высокоскоростной поток на низкоскоростные компоненты из которых в блоке выделения служебных сигналов ВСС выделяются сигналы синхронизации управления и взаимодействия.