Классификация математических моделей, используемых в экономике и менеджменте

Курсовая работа

Классификация математических моделей, используемых в экономике и менеджменте

Содержание

Введение

1. Математические модели в экономике и менеджменте

1.1 Классификация экономико-математических моделей

2. Оптимизационное моделирование

2.1 Линейное программирование

2.1.1 Линейное программирование как инструмент математического моделирования экономики

2.1.2 Примеры моделей линейного программирования

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

2.2.1 Модель динамического программирования

2.2.2 Принцип оптимальности и уравнение Беллмана

2.2.3 Общее описание процесса моделирования и построения вычислительной схемы динамического программирования

2.2.4 Оптимальное распределение ресурсов

2.2.5 Оптимальное управление запасами

2.2.6 Задача о замене

Заключение

Введение

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

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

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

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

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

1. Математические модели в экономике и менеджменте

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

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

Самыми существенными моментами при постановке и решении экономических задачах в виде математической модели являются:

·  адекватность экономико-математической модели действительности;

·  анализ закономерностей, соответствующих данному процессу;

·  определение методов, с помощью которых можно решить задачу;

·  анализ полученных результатов или подведение итога.

Под экономическим анализом понимается прежде всего факторный анализ.

Пусть y=f(x_i) - некоторая функция, характеризующая изменение показателя или процесса; x₁,x₂,…,x_n - факторы, от которых зависит функция y=f(x_i). Задана функциональная детерминированная связь показателя y с набором факторов . Пусть показатель y изменился за анализируемый период. Требуется определить, какой частью численное приращение функции y=f(x₁,x₂,…,x_n) обязано приращению каждого фактора.

Можно выделить в экономическом анализе - анализ влияния производительности труда и численности работающих на объем произведенной продукции; анализ влияния величины прибыли основных производственных фондов и нормируемых оборотных средств на уровень рентабельности; анализ влияния заемных средств на маневренность и независимость предприятия и т. п..

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

В этом случае ставится обратная задача- так называемая задача обратного факторного анализа.

Пусть имеется набор показателей x₁,x₂,…,x_n, характеризующих некоторый экономический процесс F. Каждый из показателей характеризует этот процесс. Требуется построить функцию f(x_i) изменения процесса F, содержащую основные характеристики всех показателей x₁,x₂,…,x_n

Главный момент в экономическом анализе - определение критерия, по которому будут сравниваться различные варианты решения.

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

·  наличие выбора;

·  выбор варианта по определенному принципу.

Известны два принципа выбора решения: волевой и критериальный.

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

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

Критерий оптимизации называют целевой функцией.

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

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

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

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

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

Классификация задач оптимизации по функции управления:

Функция управления	Задачи оптимизации	Класс экономико-математических моделей
Техническая и организационная подготовка производства	Моделирование состава изделий; Оптимизация состава марок, шихты, смесей; Оптимизация раскроя листового материала, проката; Оптимизация распределения ресурсов в сетевых моделях комплексов работ; Оптимизация планировок предприятий, производств и оборудования; Оптимизация маршрута изготовления изделий; Оптимизация технологий и технологических режимов.	Теория графов Целочисленное программирование Дискретное программирование Линейное программирование Сетевое планирование и управление Имитационное моделирование Динамическое программирование Нелинейное программирование
Технико-экономическое планирование	Построение сводного плана и прогнозирование показателей развития предприятия; Оптимизация портфеля заказов и производственной программы; Оптимизация распределения производственной программы по плановым периодам.	Матричные балансовые модели “Затраты-выпуск” Корреляционно- регрессионный анализ Экстраполяция тенденций Линейное программирование
Оперативное управление основным производством	Оптимизация календарно-плановых нормативов; Календарные задачи; Оптимизация стандарт-планов; Оптимизация краткосрочных планов производств.	Нелинейное программирование Имитационное моделирование Линейное программирование Целочисленное программирование

Сочетание различных элементов модели приводит к различным классам задач оптимизации:

Исходные данные	Переменные	Зависимости	Задача
Детерминированные	Непрерывные	Линейные	Линейного программирования
	Целочисленные	Линейные	Целочисленного программирования
	Непрерывные, целочисленные	Нелинейные	Нелинейного программирования
Случайные	Непрерывные	Линейные	Стохастического программирования

1.1  Классификация экономико-математических моделей

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

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

Балансовые модели. Балансовые модели как статистические, так и динамические широко применяются в экономико-математическом моделировании. В основе создания этих моделей лежит балансовый метод – метод взаимного сопоставления материальных, трудовых и финансовых ресурсов и потребностей в них. Описывая экономическую систему в целом, под её балансовой моделью понимают систему уравнений, каждое из которых выражает потребность баланса между изготовленными отдельными экономическими объектами количества продукции и совокупной потребностью в этой продукции. При таком подходе экономическая система состоит из экономических объектов, каждый из которых выпускает некоторый продукт. Если вместо понятия «продукт» ввести понятие «ресурс», то под балансовой моделью необходимо понимать систему уравнений, которые удовлетворяют требования между определенным ресурсом и его использованием.

Наиболее важные виды балансовых моделей:

·  Материальные, трудовые и финансовые балансы для экономики в целом и отдельных ее отраслей;

·  Межотраслевые балансы;

·  Матричные балансы предприятий и фирм.

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

2. Оптимизационное моделирование   2.1 Линейное программирование   2.1.1 Линейное программирование как инструмент математического моделирования экономики

Исследование свойств общей системы линейных неравенств ведется с XIX в., а первая оптимизационная задача с линейной целевой функцией и линейными ограничениями была сформулирована в З0-е годы XX в. Одним из первых зарубежных ученых, заложивших основы линейного программирования, является Джон фон Нейман, широко известный математик и физик, доказавший основную теорему о матричных играх. Среди отечественных ученых большой вклад в теорию линейной оптимизации внесли лауреат Нобелевской премии Л.В. Канторович, Н.Н. Моисеев, Е.Г. Гольштейн, Д.Б. Юдин и многие другие.

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

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

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

2.1.2 Примеры моделей линейного программирования

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

Задача о раскрое материалов. На обработку поступает материал одного образца в количестве d единиц. Требуется изготовить из него к разных комплектующих изделий в количествах, пропорциональных числам а₁,..., а_к. Каждая единица материала может быть раскроена n различными способами, при этом использование i-го способа (i=1,…,n) дает b_ij, единиц j-го изделия (j = 1,...,k).

Требуется найти план раскроя, обеспечивающий максимальное число комплектов.

Экономико-математическая модель этой задачи может быть сформулирована следующим образом. Обозначим x_i— число единиц материалов, раскраиваемых i-м способом, и x — число изготавливаемых комплектов изделий.

Учитывая, что общее количество материала равно сумме его единиц, раскраиваемых различными способами, получим:

(1)

Условие комплектности выразится уравнениями:

 (j=1,…,k)(2)

Очевидно, что

x_i0 (i=1,…,n)(3)

Целью является определить такое решение Х= (x₁,…,x_n), удовлетворяющее ограничениям (1)-(3), при котором функция F = x принимает максимальное значение. Проиллюстрируем рассмотренную задачу следующим примером Для изготовления брусьев длиной 1,5 м, 3 м и 5 м в соотношении 2:1:3 на распил поступают 200 бревен длиной 6 м. Определить план распила, обеспечивающий максимальное число комплектов. Чтобы сформулировать соответствующую оптимизационную задачу линейного программирования, определим все возможные способы распила бревен, указав соответствующее число получаемых при этом брусьев (табл. 1).

Таблица 1

Способ распила i	Число получаемых брусьев различной длины
	1,5	3,0	5,0
1	4	-	-
2	2	1	-
3	-	2	-
4	-	-	1

Обозначим через x_i— число бревен, распиленных i-м способом (i = 1.2, 3, 4); х —число комплектов брусьев.

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

х → max

при ограничениях:

x₁+x₂+x₃+x₄=200

4x₁+2x₂=2x

x₂+2x₃=x

x₄=2x

x_i0 (i=1,2,3,4)

Задача выбора оптимальной производственной программы предприятия. Пусть предприятие может выпускать n различных видов продукции. Для выпуска этих видов продукции предприятие использует М видов материально-сырьевых ресурсов и N видов оборудования. Необходимо определить объемы производства предприятия (т.е. его производственную программу) на заданном интервале планирования [0, Т], чтобы максимизировать валовую прибыль предприятия.

Далее будем полагать, что валовая прибыль есть выручка, полученная от реализации продукции за вычетом условно-постоянных и переменных затрат. Иными словами, необходимо максимизировать целевую функцию вида:

(4)

где a_i — цена реализации продукции вида i;

b_i — переменные затраты на выпуск одной единицы продукции вида i;

Zp — условно постоянные затраты, которые будем предполагать независимыми от вектора х = (x₁,..., x_n).

При этом должны быть выполнены ограничения на объемы используемых материально-сырьевых ресурсов и время использования оборудования на интервале [0,T].

Обозначим через Lj(j = l,...,M) объем запасов материально-сырьевых ресурсов вида j, а через τ_k (k = 1,..., N) — время, в течение которого может быть использовано оборудование вида k. Известно потребление материально-сырьевых ресурсов вида j на выпуск одной единицы продукции вида i, которое обозначим через l_ij (i = 1,..., n; j = 1,...,М). Известно также t_ik — время загрузки одной единицы оборудования вида k изготовления одной единицы продукции вида i (i = 1,..., n; k = 1,..., N). Через m_k обозначим количество единиц оборудования вида k (k=l,...,N).

При введенных обозначениях ограничения на объем потребляемых материально-сырьевых ресурсов могут быть заданы таким образом:

 (j=1,…,M)(5)

Ограничения на производственные мощности задаются следующими неравенствами

 k=1,…,N(6)

Кроме того, переменные

x_i≥0 i=1,…,n (7)

Таким образом, задача выбора производственной программы, максимизирующей прибыль, заключается в выборе такого плана выпуск х = (х₁...,х_n), который удовлетворял бы ограничениям (5)-(7) и максимизировал бы функцию (4).

В некоторых случаях предприятие должно поставить заранее оговоренные объемы продукции Vt другим хозяйствующим субъектам и тогда в рассматриваемой модели вместо ограничения (1.7) может быть включено ограничение вида:

x_t> Vt i= 1, ...,n.

Задача о диете. Рассмотрим задачу составления душевого рациона питания минимальной стоимости, которое бы содержало определенные питательные вещества в необходимых объемах. Будем предполагать, что имеется известный перечень продуктов из n наименований (хлеб, сахар, масло, молоко, мясо и т.д.), которые мы будем обозначать буквами F₁,...,F_n. Кроме того, рассматриваются такие характеристики продуктов (питательные вещества), как белки, жиры, витамины, минеральные вещества и другие. Обозначим эти компоненты буквами N₁,...,N_m. Предположим, что для каждого продукта F_i известно (i = 1,...,n) количественное содержание в одной единице продукта указанных выше компонент. В этом случае можно составить таблицу, содержащую характеристику продуктов:

F₁,F₂,…F_j…F_n

_____________

N₁a₁₁a₁₂…a_1j…a_1N

N₂a₂₁a₂₂…a_2j…a_2N

N_ia_i1a_i2…a_ij…a_iN

N_ma_m1a_m2…a_mj…a_mN

Элементы этой таблицы образуют матрицу, имеющую m строк и n столбцов. Обозначим ее через A и назовем матрицей питательности. Предположим, что мы составили рацион х = (х₁,x₂,...,х_n) на некоторый период (например, месяц). Иными словами, мы планируем каждому человеку на месяц х, единиц (килограммов) продукта F₁,x₂ единиц продукта F₂ и т.д. Нетрудно вычислить, какое количество витаминов, жиров, белков и прочих питательных веществ получит человек за этот период. Например, компонента N₁ присутствует в этом рационе в количестве

a₁₁x₁+ a₁₂x_2+…+ a_1nx_n

поскольку согласно условию в x₁ единицах продукта F₁ согласно матрице питательности содержится a₁₁x₁ единиц компоненты N₁; к этому количеству добавляется порция а₁₂x₂ вещества N₁ из х₂ единиц продукта F₂ и т.д. Аналогично можно определить и количество всех остальных веществ N_i в составляемом рационе (х₁,..., х_n).

Допустим, что имеются определенные физиологические требования, касающиеся необходимого количества питательных веществ в N_i (i/ = 1,..., N) в планируемый срок. Пусть эти требования заданы вектором b = (b₁...,b_n), i-я компонента которого b_i указывает минимально необходимое содержание компонента N_i в рационе. Это означает, что коэффициенты x_i вектора х должны удовлетворять следующей системе ограничений:

a₁₁x₁+ a₁₂x_2+…+ a_1nx_n≥b₁

a₂₁x₁+ a₂₂x_2+…+ a_2nx_n≥b₂ (8)

a_m1x₁+ a_m2x_2+…+ a_mnx_n≥b_m

Кроме того, из содержательного смысла задачи очевидно, что все переменные х₁,...,х_n неотрицательны и поэтому к ограничениям (8) добавляются еще неравенства

x₁≥0; x₂≥0;… x_n≥0; (9)

Учитывая, что в большинстве случаев ограничениям (8) и (9) удовлетворяет бесконечно много рационов, выберем тот из них, стоимость которого минимальна.

Пусть цены на продукты F₁,...,F_n равны соответственно с₁,…,c_n

Следовательно, стоимость всего рациона х = (х₁..., х_n) может быть записана в виде

c₁x₁+ c₂x₂+…+ c_nx_n→min (10)

Окончательно формулировка задачи о диете заключается в том, чтобы среди всех векторов х = (x₁,...,х_n) удовлетворяющих ограничениям (8) и (9) выбрать такой, для которого целевая функция (10) принимает минимальное значение.

Транспортная задача. Имеется m пунктов S₁,..., S_m производства однородного продукта (угля, цемента, нефти и т.п.), при этом объем производства в пункте S_i равен a_i единиц. Произведенный продукт потребляется в пунктах Q₁...Q_n и потребность в нем в пункте Q_j составляет k_j единиц (j = 1,...,n). Требуется составить план перевозок из пунктов S_i (i = 1,...,m) в пункты Q_j(j = 1,..., n), чтобы удовлетворить потребности в продукте b_j, минимизировав транспортные расходы.

Пусть стоимость перевозок одной единицы продукта из пункта S_i в пункт Q_i равна c_ij. Будем далее предполагать, что при перевозке х_ij единиц продукта из S_i в Q_j транспортные расходы равны c_ijx_ij.

Назовем планом перевозок набор чисел х_ij c_i = 1,..., m; j = 1,..., n, удовлетворяющий ограничениям:

x_ij≥0, i=1,2,…,m; j=1,…,n (11)

Содержательный смысл уравнений (11) состоит в том, что из пункта S_i при плане х_ij вывозится во все пункты Q_j объем , который должен быть равен запасу a_i. В пункт Q_j поступает из всех пунктов S_i суммарное количество продукта, которое в точности должно быть равно потребности b_j.

При плане перевозок (х_ij) транспортные расходы составят величину

(12)

Окончательное формирование транспортной задачи таково: среди всех наборов чисел (х_ij), удовлетворяющих ограничениям (11), найти набор, минимизирующий (12).

2.2 Динамическое программирование   2.2.1 Модель динамического программирования

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

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

Дадим общее описание модели динамического программирования.

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

Состояние  системы после k-го шага (k=1,2,…,n) характеризуется параметрами , которые называют фазовыми координатами. Состояние  можно изобразить точкой s-мерного пространства, называемого фазовым пространством. Последовательное преобразование системы (по шагам) достигается с помощью некоторых мероприятий , которые составляют управление системой U=,

где  - управление на k-м шаге, переводящее систему из состояния  в состояние  (рис.1). Управление  на k-м шаге заключается в выборе значений определенных управляющих переменных .

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

(1.1)

Равенства (1.1) получили название уравнений состояний. Функции  полагаем заданными.

Варьируя управления U, получим различную «эффективность» процесса, которую будем оценивать количественно целевой функцией Z, зависящей от начального состояния системы  и от выбранного управления U:

(1.2)

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

(1.3)

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

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

Для единообразия формулировок (но не вычислительных процедур!) в дальнейшем будем говорить только о задаче максимизации, имея в виду, что если необходимо минимизировать Z, то заменив Z на Z’=-Z перейдем к максимизации Z’.

Начальное состояние и конечное состояние  могут быть заданы однозначно или могут быть указаны множество  начальных состояний и множество конечных состояний так, что . В последнем случае в задаче пошаговой оптимизации требуется определить совокупность допустимых управлений, переводящих систему из начального состояния  в конечное  и максимизирующих целевую функцию (1.3). Управление, при котором достигается максимум целевой функции (1.3) называется оптимальным управлением и обозначается через U*=.

Если переменные управления  принимают дискретные значения, то модель ДП называется дискретной. Если же указанные переменные изменяются непрерывно, то модель ДП называется непрерывной. В зависимости от числа параметров состояний (s) и числа управляющих переменных на каждом шаге (r) различают одномерные и многомерные модели ДП. Число шагов в задаче может быть либо конечным, либо бесконечным.

ДП применяется при оптимизации как детерминированных, так и стохастических процессов.

В некоторых задачах, решаемых методом ДП, процесс управления естественно разбивается на шаги. Например, при распределении на несколько лет ресурсов деятельности предприятия шагом естественно считать временной период; при распределении средств между n предприятиями номером шага естественно шага номер очередного предприятия. В других задачах разбиение на шаги вводится искусственно. Например, непрерывный управляемый процесс можно рассматривать как дискретный, условно разбив его на некоторые временные отрезки – шаги. Исходя из условий каждой конкретной задачи, длину шага выбирают таким образом, чтобы на каждом шаге получить простую задачу оптимизации и обеспечить требуемую точность вычислений.

2.2.2 Принцип оптимальности и уравнение Беллмана

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

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

С точки зрения интересов оптимизации только каждого ближайшего шага – выбора кратчайшего пути из данной точки в соседнюю – следует двигаться по маршруту, проходящему через точки А, А₁, А₃, А₂, А₄, В. Длина этого маршрута равна 34. Такой путь из А в В не является кратчайшим. Например, маршрут, проходящий через точки А, А₃, А₄, В имеет меньшую длину, равную 25. Решив эту задачу, мы убедимся, что второй путь также не является оптимальным.

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

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

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

Так, если система в начале k-го шага находится в состоянии и мы выбираем произвольное управление , то система придет в новое состояние , и дальнейшие управления  должны выбираться оптимальными относительно состояния . Последнее означает, что при этих управлениях максимизируется показатель эффективности на последующих до конца процесса шагах k+1,…,n, т.е. величина  Показатель, характеризующий суммарную эффективность от данного k-го до последнего n-го шага, будем обозначать через Z_k, т.е.  Задача оптимизации процесса, начиная с k-го до последнего n-го шага (рис.3), похожа на исходную при начальном состоянии системы , управлении  и показателе эффективности (аналогично (2)). Выбрав оптимальное управление U_k* на оставшихся n-k+1 шагах, получим величину , которая зависит только от , т.е.

(2.1)

Назовем величину  условным максимумом. Если теперь мы выберем на k-м шаге некоторое произвольное управление , то система придет в состояние . Согласно принципу оптимальности, какое бы  мы не выбрали, на последующих шагах управление  должно выбрать так, чтобы показатель эффективности Z_k+1 достигал максимального значения, равного . Остается выбрать управление . Его нельзя выбирать из условия локальной максимизации показателя эффективности на данном k-м шаге, лишь бы получить . Такой подход был бы недальновидным, поскольку от выбора  зависит новое состояние , а от последнего – максимально возможная эффективность, которая может быть достигнута в дальнейшем, т.е. величина . Поэтому необходимо выбирать управление  так, чтобы оно в совокупности с оптимальным управлением на последующих шагах (начиная с (k+1) – го) приводило бы к общему максимуму показателя эффективности на n-k+1 шагах, начиная с k-го до конца. Это положение в аналитической форме можно записать в виде следующего соотношения:

(2.2)

Получившего название основного функционального уравнения ДП, или уравнения Беллмана.

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

Соотношения (5) для определения последовательности функций  через  (k=n, n-1,…,1) получили название основных рекуррентных уравнений Беллмана.

Решая уравнения (2.2) для определения условного максимума показателя эффективности за n-k+1 шагов, начиная с k-го шага, определяем соответствующее оптимальное управление , при котором этот максимум достигается. Это управление также зависит от . Будем обозначать такое управление через  и называть условным оптимальным управлением на k-м шаге.

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

2.2.3 Общее описание процесса моделирования и построения вычислительной схемы динамического программирования

Общая задача оптимизации, чтобы ее можно было описать моделью ДП должна удовлетворять следующим условиям :

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

2. Структура задачи инвариантна относительно числа шагов п, т. е. должна быть определена для любого n и не зависеть от этого числа.

3. На каждом шаге состояние системы определяется конечным числом s параметров состояния и управляется конечным числом r переменных управления, причем s и r не зависят от числа шагов п.

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

Построение модели ДП сводится к следующим основным моментам:

1) выбирают способ деления процесса на шаги;

2) вводят параметры состояния  и переменные управления  на каждом шаге процесса;

3) записывают уравнение состояния

(3.1)

4) вводят показатели эффективности на k-м шаге  и суммарный показатель – целевую функцию

(3.2)

5) вводят в рассмотрение условные максимумы показателя эффективности от k-гo шага (включительно) до конца процесса и условные оптимальныеуправления на k-м шаге

6)  из ограничений задачи определяют для каждого шага множества D_k допустимых управлений на этом шаге;

7)  записывают основные для вычислительной схемы ДП функциональные уравнения Беллмана

(3.3)

(3.4)

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

1.  Решение уравнений (3.3) проводят последовательно, начиная с (3.4). Этот этап получил название условной оптимизации.

2.  В результате последовательного решения п частных задач на условный максимум определяют две последовательности функций:  —условные максимумы и соответствующие им —условные оптимальные управления.