83247

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

Доклад

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

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

Русский

2015-03-12

42.96 KB

1 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

25748. Анализ учетной (бухгалтерской) и экономической рентабельности 28.5 KB
  Исследование показателя прибыли во взаимосвязи с показателями выручки от продаж затрат активов собственного акционерного уставного капитала представляет возможность оценить эффективность деятельности организации привлечения дополнительного капитала и заемных средств. Показатели рентабельности прибыльности оценивают величину прибыли полученной с каждого рубля средств вложенных в активы и деятельность организации. затратоотдача или рентабельность основной деятельности определяется отношением прибыли от продаж к сумме затрат на...
25749. Анализ финансовой устойчивости 30 KB
  Абсолютными являются показатели характеризующих степень обеспеченности запасов источниками их формирования. Для характеристики источников формирования запасов определяют три основных показателя: 1. наличие долгосрочных источников формирования запасов определяется путем увеличения суммы собственных оборотных средств на сумму долгосрочных обязательств; 3. общая величина основных источников формирования запасов определяется путем увеличения предыдущего показателя на сумму краткосрочных кредитов и займов.
25750. Аудит денежных средств и расчетов с подотчетными лицами 32 KB
  № 4 Главная книга Журнал ордер № 7 синтетический аналитический учет Основанные задачи аудиторской проверки является Проверка соответствия лиц получающих наличные деньги из кассы на хозяйственные операции расходы со списком лиц имеющих на это право и утвержденному руководителем предприятия. Проверка получения подотчетных сумм денежных средств лицами не отчитавшимися за ранее полученному авансу в течение 3 дня Проверка соответствия фактических подотчетных сумм с целями на которые они были выданы Проверка подотчетных лиц на наличие в...
25751. Аудит кассовых операций 51 KB
  Цель аудита кассовых операций: установление соответствия применяемой в организации методики бух учета действующей в проверяемом периоде и нормативным документам. проверка своевременного и полного отражения в БУ операций с ДС при соблюдении требований законодательства 2. правильное документальное оформление операций с ДС контроль за сохранностью ДС документов в кассе 3.
25752. Аудит затрат на производство продукции (работ‚ услуг) 50.5 KB
  Методика и цели преследуемые при проведении аудита предполагают проверку надежности учетной информации; точности достоверности и полноты отражения отдельных элементов и статей затрат; выявления случаев нарушения достоверности общей калькуляции себестоимости товарной продукции и результатов хозяйственной деятельности; соблюдения требований вытекающих из специфики проверяемого хозяйствующего субъекта; ограничений учетного периода; оценку общей информации представленной в финансовой отчетности а также применение и раскрытие принципов...
25753. Аудит учета основных средств 29 KB
  проверка договоров и первичной документации их наличие и движении 2. проверка правильности оценки и переоценки ос 3. проверка полноты оприходования и правильности отражения в учет регистрах хоз операций по перемещению и выбытию 4. проверка соблюдений условий для отнесения имущества к оснк РФ пбу 601 классификатор 2.
25754. Аудит продажи и финансовых результатов деятельности организации 36 KB
  Положение по ведению бухгалтерского учета и бухгалтерской отчетности в РФ Приказ МФ РФ № 34н от 29 июля 1998 г. План счетов бухгалтерского учета и Инструкция по его применению Приказ МФ РФ № 94н от 31 октября 2000 г. Аудит учета финансовых результатов и их использования. Объектом проверки финансовых результатов является бухгалтерская прибыль убыток представляющая собой конечный финансовый результат выявленный за отчетный период на основании бухгалтерского учета всех хозяйственных операций организации и оценки статей бухгалтерского...
25755. Аудит кредитов 52.5 KB
  Задачи аудита кредитов займов и средств целевого финансирования: изучение кредитных договоров договоров залога договоров займа источников поступления средств целевого финансирования; оценка состояния синтетического и аналитического учета кредитов займов и средств целевого финансирования; изучение правомерного расходования средств кредитов займов целевого финансирования; установление правильности отражения на счетах бухгалтерского учета и в бухгалтерской отчетности кредитов займов и средств целевого финансирования; проверка...
25756. Аудит расчетов с бюджетом 32.5 KB
  Налоговая инспекция имеет право перепроверить правильность представленного аудиторами заключения в случаях если ею будет установлена недоброкачественность аудита приведшая к ущемлению интересов бюджета. Аудитору необходимо проверить: правильно ли исчислены налогооблагаемые базы; правильность исчисления прибыли переходного периода; правильно ли применены ставки налогов и платежей; своевременно ли и полностью уплачены платежи в бюджет; правильно ли и обоснованно применены льготы; правильно ли ведется аналитический и синтетический...