Виды математических моделей, используемых в экономике

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

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

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

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

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

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

2.1 Задача о минимизации затрат на строительство и эксплуатацию предприятий

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ



ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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



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

1.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 предприятиями номером шага естественно шага номер очередного предприятия. В других задачах разбиение на шаги вводится искусственно. Например, непрерывный управляемый процесс можно рассматривать как дискретный, условно разбив его на некоторые временные отрезки - шаги. Исходя из условий каждой конкретной задачи, длину шага выбирают таким образом, чтобы на каждом шаге получить простую задачу оптимизации и обеспечить требуемую точность вычислений.

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

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

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

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

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

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

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

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

(2.1)

Назовем величину условным максимумом. Если теперь мы выберем на k-м шаге некоторое произвольное управление , то система придет в состояние . Согласно принципу оптимальности, какое бы мы не выбрали, на последующих шагах управление должно выбрать так, чтобы показатель эффективности Zk+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. Общее описание процесса моделирования и построения вычислительной схемы динамического программирования

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

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) из ограничений задачи определяют для каждого шага множества Dk допустимых управлений на этом шаге;

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

(3.3)

(3.4)

динамическое программирование уравнение беллман

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

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

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

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

4. После выполнения первого этапа (условной оптимизации) приступают ко второму этапу -- безусловной оптимизации.

а) Если начальное состояние задано ,
то непосредственно определяют максимум целевой
функции

(3.5)

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

(3.6)

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

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

(3.7)

откуда находят , а затем, как и в п. а), по цепочке (3.6) --безусловное оптимальное управление.

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

(3.8)

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

(3.9)

(3.10)

В результате решения этих уравнений получим последовательности

(3.11)

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

(3.12)

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

(3.13)



2.1 Минимизация затрат на строительство и эксплуатацию предприятий

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

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

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

Введем обозначения:

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

xi -- количество ресурса, используемого по i-му способу (i = );

gi(xi) -- функция расходов, равная, например, величине затрат на производство при использовании ресурса xi по i-му способу;

цk(x) -- наименьшие затраты, которые нужно произвести при использовании ресурса х первыми k способами.

Необходимо минимизировать общую величину затрат при освоении ресурса x всеми способами:

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



Экономический смысл переменных xi состоит в нахождении количества предприятий, рекомендуемого для строительства в i-м пункте. Для удобства расчетов будем считать, что планируется строительство предприятий одинаковой мощности.

Рассмотрим конкретную задачу по размещению предприятий.

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

Необходимо разместить предприятия таким образом, чтобы обеспечить минимальные суммарные затраты на их строительство и эксплуатацию. Значения функции затрат gi(x) приведены в табл. 29.4.

В данном примере gi(х) -- функция расходов в млн р., характеризующая величину затрат на строительство и эксплуатацию в зависимости от количества размещаемых предприятий в i-м районе;

цk(x) -- наименьшая величина затрат в млн. р., которые нужно произвести при строительстве и эксплуатации предприятий в первых k районах.

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



для остальных районов

Задачу будем решать в три этапа.

1-й этап. Если все предприятия построить только в первом районе, то

минимально возможные затраты при х = 5 составляют 76 млн р.

2-й этап. Определим оптимальную стратегию при размещении предприятий только в первых двух районах по формуле

Найдем ц2(l):

g2(1) + ц1(0) = 10 + 0 = 10,

g2(0) + ц1(l)= 0 +11 = 11,

ц2(l) = min (10, 11) = 10.

Вычислим ц2(2):

g2(2) + ц1(0) = 19 + 0 = 19,

g2(l) + ц1(l) = 10 + 11 = 21,

g2(0) + ц1 (2) = 0 + 18 = 18,

ц2(2) = min (19, 21, 18) = 18.

Найдем ц2(3):

g2(3) + ц1 (0) = 34 + 0 = 34,

g2(2) + ц1(l) = 19 + 11 = 30,

g2(1) + ц1(2) = 10 + 18 = 28,

g2(0) + ц1(3) = 0 + 35 = 35,

ц2(3) = min (34, 30, 28, 35) = 28.

Определим ц2(4):

g2(4) + ц1(0) = 53 + 0 = 53,

g2(3) + ц1(l) = 34 + 11 = 45,

g2(2) + ц1(2) = 19 + 18 = 37,

g2(l) + ц1(3) = 10 + 35 = 45,

g2(0) +ц1(4) = 0 + 51 = 51,

ц2(4) = min (53, 45, 37, 45, 51) = 37.

Вычислим ц2(5):

g2(5) + ц1(0) = 75 + 0 = 75,

g2(4) + ц1(l) = 53 + 11 = 64,

g2(3) + ц1(2) = 34 + 18 = 52,

g2(2) + ц1(3) = 19 + 35 = 54,

g2(1) + ц1(4) = 10 + 51 = 61,

g2(0) + ц1(5) = 0 + 76 = 76,

ц2(5) = min (75, 64, 52, 54, 61, 76) = 52.

3-й этап. Определим оптимальную стратегию при размещении пяти предприятий в трех районах по формуле

ц3(x) = min{g3(x3) + ц2(x - х3)}.

Найдем ц3(5):

g3(5) + ц2(0) = 74 + 0 = 74,

g3(4) + ц2(1) = 54 + 10 = 64,

g3(3) + ц2(2) = 36 + 18 = 54,

g3(2) +ц2(3) = 20 + 28 = 48,

g3(1) + ц2(4) = 9 + 37 = 46,

g3(0) + ц2(5) = 0 + 52 = 52,

ц3(5) = min (74, 64, 54, 48, 46, 52) = 46.

Минимально возможные затраты при х = 5 составляют 46 млн р.

Определены затраты на строительство предприятий от 1-го до 3-го этапа. Вернемся 3-го к 1-му этапу. Минимальные затраты в 46 млн р. на 3-м этапе получены как 9 + 37, т.е. 9 млн р. соответствуют строительству одного предприятия в третьем районе (см. табл. 29.4). Согласно 2-му этапу 37 млн р. получены как 19 + 18, т.е. 19 млн р. соответствуют строительству двух предприятий во втором районе. Согласно 1-му этапу 18 млн р. соответствуют строительству двух предприятий в первом районе.

Ответ. Оптимальная стратегия состоит в строительстве одного предприятия в третьем районе, по два предприятия во втором и первом районах, при этом минимальная стоимость строительства и эксплуатации составит 46 ден. ед.

Нахождение рациональных затрат при строительстве трубопроводов и транспортных артерий

Требуется проложить путь (трубопровод, шоссе) между двумя пунктами А и В таким образом, чтобы суммарные затраты на его сооружение были минимальные.

Решение. Разделим расстояние между пунктами А и В на шаги (отрезки). На каждом шаге можем двигаться либо строго на восток (по оси X), либо строго на север (по оси Y). Тогда путь от А в В представляет ступенчатую ломаную линию, отрезки которой параллельны одной из координатных осей. Затраты на сооружение каждого из отрезков известны (рис. 29.2) в млн р.

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

Найдем условную оптимизацию последнего шага (рис. 29.3).

В точку В можно попасть из B1 или В2. В узлах запишем стоимость пути. Стрелкой покажем минимальный путь.

Рассмотрим предпоследний шаг (рис. 29.4).

Для точки В3 условное управление -- по оси X, а для точки B5 -- по оси Y. Управление для точки В4 выбираем как

т.е. по оси Y.

Условную оптимизацию проводим для всех остальных узловых точек (рис. 29.5).

Получим

где с -- север, в --восток.

Минимальные затраты составляют

Если решать задачу исходя из оптимальности на каждом этапе, то решение будет следующим:

Затраты составят 10 +12 + 11 + 10 + 9 + 13 +10 = 75 > 71.

Ответ. Прокладывать путь целесообразно по схеме: с, с, в, с, в, в, в, при этом затраты будут минимальные и составят 71 млн р.



ЗАКЛЮЧЕНИЕ

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

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

Для построения моделей выбраны три задачи:

· Задача оптимального распределения ресурсов;

· Задача об оптимальном управлении запасами;

· Задача о замене.

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



СПИСОК ЛИТЕРАТУРЫ

1. Вавилов В.А., Змеев О.А., Змеева Е.Е. Электронное пособие “Исследование операций”

2. Калихман И.Л., Войтенко М.А. “Динамическое программирование в примерах и задачах”, Москва ”Высшая школа”, 1979

3. Косоруков О.А., Мищенко А.В. “Исследование операций”, Москва, 2003

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