83247

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

Доклад

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

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

Русский

2015-03-12

42.96 KB

3 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

30126. Создание устройства для дистанционного мониторинга основных физиологических показателей человека, программного обеспечения для регистрации частоты сердечных сокращений и температуры тела 3.2 MB
  Устройство для дистанционного мониторинга физиологических показателей человека позволяет удалённо следить за температурой и частотой пульса пациента. Устройство закрепляется на внутренней стороне плеча, что позволяет точнее измерять температуру.
30127. Разработка аппарата коррекции речи, который использует такие методы лечения заикания как «метроном» и «задержанная акустическая связь» 2.4 MB
  Благодаря речи индивидуальное сознание каждого человека, не ограничиваясь личным опытом, собственными наблюдениями, питается и обогащается результатами общественного опыта: наблюдения и знания всех людей становятся или могут благодаря речи стать достоянием каждого. Огромное многообразие стимулов, которое получает благодаря этому человек, дало мощный толчок для дальнейшего развития его мозга
30128. Микро- и наноэлектроника. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ДИПЛОМНОМУ ПРОЕКТИРОВАНИЮ 835 KB
  ЦЕЛИ И ЗАДАЧИ ДИПЛОМНОГО ПРОЕКТИРОВАНИЯ Дипломное проектирование по специальности Микро и наноэлектроника является заключительным этапом обучения студента в университете и имеет следующие цели: систематизацию закрепление и расширение теоретических и практических знаний по специальности применение этих знаний при решении конкретных научных технических экономических и производственных задач; развитие навыков ведения самостоятельной работы и овладение методикой исследования и экспериментирования при решении разрабатываемых в...
30129. Исследование методов позиционирования, а так же разработка устройства для дистанционного мониторинга технических объектов, транспортных средств и человека 873.95 KB
  Одним из основных компонентов системы позиционирования является устройство под названием GPSтрекер.4 Применение систем навигации Кроме навигации координаты получаемые благодаря спутниковым системам используются в следующих отраслях: Геодезия: с помощью систем навигации определяются точные координаты точек Картография: системы навигации используется в гражданской и военной картографии Навигация: с применением систем навигации осуществляется как морская так и дорожная навигация Спутниковый мониторинг транспорта: с помощью систем...
30130. Створення газети на тему «Молодь обирає спорт» у програмі Page Maker 639.28 KB
  Програма PageMaker є складовою частиною лінійки програмних продуктів фірми Adobe, до складу якої крім того входять Adobe Table, Adobe FrameMaker, Adobe PageMill, Adobe Photoshop, Adobe Illustrator, Adobe Streamline, Adobe Premier. Практично кожна з цих програм є світовим лідером в своїй області
30131. Создание управляющих программ с использованием сплайновой интерполяции типов AKIMA(ASPLINE), NURBS(BSPLINE) и кубического сплайна(CSPLINE). Воспроизведение сплайновой интерполяции в системе ЧПУ WinPCNC 184.33 KB
  Воспроизведение сплайновой интерполяции в системе ЧПУ WinPCNC Выполнил: студент гр. Ход Работы В процессе обучения будет рассмотрено использование сплайновой интерполяции на двух примерах. Будем использовать три основных типа сплайна: SPLINE kim сплайн BSPLINE NURBS сплайн CSPLINE кубический сплайн.
30132. Генерация и редактирование сплайн контуров. Создание и отработка управляющих программ 236.41 KB
  Полученную кривую можно сохранить в файле в формате txt, где будут записаны последовательности координат X и Y. Таким образом, с помощью программы можно не только просмотреть, как будет строиться та или иная кривая, но и использовать полученные оцифрованные точки в дальнейшем.
30133. Основы программирования в оболочке ОС UNIX 25.44 KB
  Пользователь имеет возможность присвоить переменной значение некоторой строки символов. Например команда mrk= usr ndy bin присваивает значение строки символов usr ndy bin переменной mrk типа строка символов . Для этого в соот ветствующем месте командной строки должно быть употреблено имя этой переменной которому предшествует метасимвол . Использование значения присвоенного некоторой переменной называется подстановкой.
30134. БАЗЫ ДАННЫХ 34.53 KB
  В начале работы следуют выбрать интересующего работника. После этого будут выведены данные о заданиях выбранного работника в соответствующую таблицу. При выборе конкретного задания выводятся данные о работниках.