Динамическое программирование. Условия применимости, принцип оптимальности Беллмана. Уравнение Беллмана для задачи распределения инвестиций, задачи коммивояжера.

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

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

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

Уравнение Беллмана для задачи коммивояжера:

Если и , то

Для задачи распределения инвестиций:

9. Ориентированный граф, основные определения. Задача сетевого планирования.

Математически конечным графом G называется пара (Е,е), где Е – непустое конечное множество элементов (вершин), а е – конечное (возможно, пустое) множество пар элементов из Е (дуг или ребер).

Дугой называется ориентированная пара () вершин графа и , где - начальная вершина дуги, а - конечная.

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

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

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

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

Модели управления запасами. Основные понятия. Однопродуктовая статическая модель.

Задачи управления запасами возникают, когда необходимо создать запас материальных ресурсов или предметов потребления с целью удовлетворения спроса на заданном интервале времени. Любая модель должна ответить на 2 вопроса: 1) какое количество продукции заказывать; 2) когда заказывать. Ответ на 2 вопрос зависит от вида контроля за объемом запасов. Контроль бывает периодическим и непрерывным.

Точка заказа – объем запаса на складе, при котором делается новый заказ.

Модели делятся:

1) Детерминированные (статические и динамические). Все параметры – неслучайные величины.

2) Вероятностные(статические и динамические). Часть параметров – случайные величины.

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

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

Затраты на хранение запаса, которые представляют собой расходы на содержание запаса на складе (затраты на переработку, амортизационные расходы, эксплуатационные расходы) обычно возрастают с увеличением уровня запаса.

Потери от дефицита представляют собой расходы, обусловленные отсутствием запаса необходимой продукции.

Оптимальный уровень запаса соответствует минимуму суммарных затрат.

Однопродуктовая статическая модель:

Модель управления запасами простейшего типа характеризуется постоянным во времени спросом, мгновенным пополнением запаса и отсутствием дефицита.

Предполагается, что интенсивность спроса (в единицу времени) равна b. Наивысшего уровня запас достигает в момент поставки заказа размером y (предполагается, что запаздывание поставки является заданной константой). Уровень запаса достигает нуля спустя у /b единиц времени после получения заказа размером у.

Пусть К – затраты на оформление заказа, имеющие место всякий раз при его размещении, h – затраты на хранение единицы заказа в единицу времени. Следовательно, суммарные затраты в единицу времени можно представить в виде: .

Продолжительность цикла движения заказа составляет t₀=у /b.

Средний уровень запаса равен у/2.

Оптимальный размер заказа: -формула экономичного размера заказа Уилсона.

Не нашли, что искали? Воспользуйтесь поиском: