Динамическое программирование

Особенности модели динамического программирования, история формирования принципа оптимальности. Рассмотрение уравнения Беллмана, применения метода динамического программирования, изучение распределения ресурсов между технологическими процессами.

Рубрика Программирование, компьютеры и кибернетика
Вид реферат
Язык русский
Дата добавления 28.03.2020
Размер файла 83,6 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Динамическое программирование

Динамическое программирование (ДП) - метод оптимизации, приспособленный к операциям, в которых процесс принятия решения может быть разбит на этапы (шаги). Такие операции называются многошаговыми. Начало развития ДП относится к 50-м годам ХХ в. Оно связано с именем американского математика Р. Беллмана.

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

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

Приведем общую постановку задачи ДП. Рассматривается управляемый процесс, например, экономический процесс распределения средств между предприятиями, ресурсов в течение ряда лет, замены оборудования, пополнения запасов и т.п. В результате управления система (объект управления) S переводится из начального состояния s0 в состояние S.

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

Обозначим через Хk управление на k-м шаге (k=1, 2, ..., п). Переменные Хk удовлетворяют некоторым ограничениям и в этом смысле называются допустимыми (Хk может быть числом, точкой в п-мерном пространстве, качественным признаком).

Пусть Х (Х1, Х1, ..., Хn) - управление, переводящее систему S из состояния s0 в состояние sn Обозначим через sk состояние системы после k-го шага управления. Получаем последовательность состояний s0, s1,..., sk-1, sk,..., sn-1, sn=Sm, которую изобразим кружками (рис. 1.1).

Рис.1.1.

Показатель эффективности рассматриваемой управляемой операции - целевая функция - зависит от начального состояния и управления:

Z=F(s0,Х) (1.1)

Сделаем несколько предположений.

1. Состояние sk системы в конце k-го шага зависит только предшествующего состояния sk-1 и управления на k-м шаге Хk. (и не зависит от предшествующих состояний и управлений). Это требование называется «отсутствием последействия». Сформулированное положение записывается в виде уравнений:

sk=k(sk-1,Хk),k=1,2,…,n, (1.2)

которые называются уравнениями состояний.

2. Целевая функция (1) является аддитивной от показателя эффективности каждого шага. Обозначим показатель эффективности k-го шага через

Zk=fk(sk-1,Хk),k=1,2,…,n, (1.3)

Тогда

Z=(sk-1,Хk). (1.4)

Задача пошаговой оптимизации (задача ДП) формулируется так: определить такое допустимое управление Х, переводящее систему S из состояния s0 всостояние , при котором целевая функция (1.4) принимает наибольшее(наименьшее) значение.

Выделим особенности модели ДП:

1. Задача оптимизации интерпретируется как п-шаговый процесс управления динамическое программирование беллман

2. Целевая функция равна сумме целевых функций каждого шага.

З. Выбор управления на k-м шаге зависит только от состояния системы к этому шагу, не влияет на предшествующие шаги (нет обратной связи).

4. Состояние sk после k-го шага управления зависит только от предшествующего состояния sk-1 и управления Хk (отсутствие последействия).

5. На каждом шаге управление Хk зависит от конечного числа управляющих переменных, а состояние sk - от конечного числа параметров.

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

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

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

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

Уравнения Беллмана. Вместо исходной задачи ДП с фиксированным числом шагов п и начальным состоянием s0 рассмотрим последовательность задач, полагая последовательно п=1, 2, ... при различных s - одношаговую, двухшаговую и т.д., - используя принцип оптимальности.

Рассмотрим пример применения метода динамического программирования к задаче, которую можно интерпретировать как задачу распределения ресурсов между технологическими процессами. Имеется технологических процессов, по которым надо распределить однородный ресурс (например деньги, или рабочую силу, или энергию) так, чтобы максимизировать общий доход. Пусть использование в i-м технологическом процессе ресурса в количестве приносит доход , а общее количество ресурса равняется . Тогда задача состоит в максимизации функции:

,

при ограничении .

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

,

Эта формула справедлива при любых и , поэтому для исходной задачи имеем цепочку соотношений:

,

,

и т.д. Для первого процесса, когда ресурсы по остальным процессам уже распределены, получаем:

,

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

,а условно оптимальное использование ресурса в первом процессе есть .

Далее,,

Дифференцируя выражение в квадратных скобках по и приравнивая производную к нулю, получаем соотношение

,

Откуда

,

.

На следующем шаге

,

.

Решая эту задачу максимизации, как и на предыдущем шаге, получаем

,

.

Продолжая вычисления по процедуре, получаем общие выражения для и :

,

.

Так как для последнего технологического процесса должно выполняться ограничение , то на n-м шаге находим просто оптимальное значение задачи.

и оптимальное использование ресурса в n-м процессе

.

Подставляя в выражение для, затем в и т.д., получаем решение задачи

.

Размещено на Allbest.ru

...

Подобные документы

  • Модель динамического программирования для решения задач оптимального распределения ресурсов. Принцип оптимальности, уравнение Беллмана. Двумерная и дискретная динамическая модель. Значение метода в решении прикладных задач различных областей науки.

    курсовая работа [400,2 K], добавлен 01.10.2009

  • Сущность и особенности выполнения метода динамического программирования. Решение математической задачи, принцип оптимальности по затратам, ручной счёт и листинг программы. Применение метода ветвей и границ, его основные преимущества и недостатки.

    курсовая работа [38,9 K], добавлен 15.11.2009

  • Постановка задачи динамического программирования. Поведение динамической системы как функция начального состояния. Математическая формулировка задачи оптимального управления. Метод динамического программирования. Дискретная форма вариационной задачи.

    реферат [59,9 K], добавлен 29.09.2008

  • Обзор задач, решаемых методом динамического программирования. Составление маршрута оптимальной длины. Перемножение цепочки матриц. Задача "Лестницы". Анализ необходимости использования специальных методов вероятностного динамического программирования.

    курсовая работа [503,3 K], добавлен 28.06.2015

  • Класс задач, к которым применяются методы динамического программирования. Решения задачи распределения капитальных вложений между предприятиями путем построения математической модели. Программа "Максимизации капиталовложений" на базе Microsoft Excel.

    курсовая работа [1,4 M], добавлен 28.10.2014

  • Достижения математики в теории полумарковских процессов. Связь управляемых полумарковских процессов и динамического программирования. Разработка программы модели управляемого полумарковского процесса, реализованной на языке программирования СИ++.

    курсовая работа [356,7 K], добавлен 10.09.2017

  • Общая характеристика динамического программирования: задачи о коммивояжере, о назначении, о теории расписаний. Численные методы ветвей и границ, методы отсечения. Задачи целостного программирования с булевыми переменными. Аддиктивный метод Балаша.

    учебное пособие [534,1 K], добавлен 11.07.2010

  • Применение принципа оптимальности в задачах на рациональное распределение средств на расширение производства. Понятие динамического программирования и теоретические основы рекуррентной природы вычислительной схемы Беллмана в среде Microsoft Excel.

    курсовая работа [75,8 K], добавлен 30.09.2010

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

    курсовая работа [873,9 K], добавлен 02.07.2014

  • Основные понятия и принципы динамического программирования, реккурентность природы задач данного типа и функциональные уравнения Беллмана. Разработка структуры блок-схемы и реализация на ЭВМ построенного алгоритма на выбранном языке программирования.

    курсовая работа [30,2 K], добавлен 26.11.2010

  • Постановка задачи синтеза системы управления. Применение принципа Максимума Понтрягина. Метод аналитического конструирования оптимальных регуляторов. Метод динамического программирования Беллмана. Генетическое программирование и грамматическая эволюция.

    дипломная работа [1,0 M], добавлен 17.09.2013

  • Понятие Web-сайта и его типы, основы классификации. Достоинства и недостатки сайтов динамического наполнения. Языки программирования серверного выполнения, которые используются для их создания. Проектирование динамического сайта со справочным материалом.

    курсовая работа [959,8 K], добавлен 05.03.2014

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

    курсовая работа [73,7 K], добавлен 15.10.2010

  • Определение совокупности шаговых управлений. Решение задач динамического программирования двухэтапным способом. Решение последовательности задач условной оптимизации. Оптимальное распределение памяти, политика замены оборудования, замена форвардера.

    презентация [674,9 K], добавлен 30.10.2013

  • Методы решения задачи оптимального резервирования технической системы. Решение задачи методами неопределенных множителей Лагранжа и динамического программирования. Построение оптимальной схемы системы при нагруженном резервировании ее элементов.

    лабораторная работа [31,5 K], добавлен 10.06.2009

  • Обеспечение наибольшей прибыли от реализации выпускаемой продукции мебельной фабрики. Решение задачи в среде MS Excel. Выполнение преобразования симплексной таблицы методом Жордана-Гаусса. Применение метода динамического программирования и сечения Гомори.

    курсовая работа [58,9 K], добавлен 28.10.2014

  • Форма организации основного переменно-поточного производства. Особенности переналадки станков как задача динамического программирования. Общая характеристика алгоритма формирования метода ветвей и границ. Сущность понятия комбинаторная конфигурация.

    курсовая работа [3,2 M], добавлен 20.12.2008

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

    презентация [1,8 M], добавлен 05.11.2016

  • Понятие большой системы управления. Модель структурного сопряжения элементов. Организация многоуровневой структуры управления. Общая задача линейного программирования. Элементы динамического программирования. Постановка задачи структурного синтеза.

    учебное пособие [1,3 M], добавлен 24.06.2009

  • Суть программирования с использованием библиотеки OpenGL, его назначение, архитектура, преимущества и базовые возможности. Разработка приложения для построения динамического изображения трехмерной модели объекта "Компьютер", руководство пользователя.

    курсовая работа [866,8 K], добавлен 22.06.2011

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.