Использование метода динамического программирования для решения экономических задач

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

1.1 Многошаговые процессы в динамических задачах

1.2 Принцип оптимальности и рекуррентные соотношения

1.3 Вычислительная схема

1.4 Планирование производственной программы

1.5 Оптимальное распределение средств на расширение производство

2. РЕШЕНИЕ ЭКОНОМИЧЕСКИХ ЗАДАЧ МЕТОДОМ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

2.1 Задачи выбора кратчайшего пути

2.2 Задачи планирования производственной программы

2.3 Задачи оптимального распределения средств на расширение производства

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

ВВЕДЕНИЕ

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

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

Цель работы:

1) Изучить метод динамического программирования.

2) Применить метод динамического программирования к решению экономических задач.

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

1. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

1.1 Многошаговые процессы в динамических задачах

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

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

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

1.2 Принцип оптимальности и рекуррентные соотношения

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

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

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

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

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

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

fn – l(Sl) = (Rl + 1(Sl, Ul + 1) + fn – (l + 1)(Sl + 1)) (1.1)

(l =)

где – оптимальное значение эффекта, достигаемого за n - l шагов; n количество шагов (этапов); Sl = (sl(1);…;sl(m)) – состояние системы на l –м шаге; Ul = (ul(1);…;ul(m)) – решение (управление), выбранное на l-м шаге; Rl – непосредственный эффект, достигаемый на l-м шаге.

Optimum в выражении (1.1) означает максимум или минимум в зависимости от условия задачи.

Все вычисления, дающие возможность найти оптимальное значение эффекта, достигаемого за п шагов, fn(S0), проводятся по формуле (1.1), которая носит название основного функционального уравнения Беллмана или рекуррентного соотношения. Действительно, при вычислении очередного значения функции fn-l используются значение функции fn–(l+1), полученного на предыдущем шаге, и непосредственное значение эффекта Rl+1(Sl, Ul+1), достигаемого в результате выбора решения Ul+1 при заданном состоянии системы Sl. Процесс вычисления значений функции fn-l осуществляется при естественном начальном условии f0(Sn)= 0, которое означает, что за пределами конечного состояния системы эффект равен нулю.

1.3 Вычислительная схема

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

1. записать функциональное уравнение для последнего состояния процесса (ему соответствует l = n – 1):

 Скачать реферат