срс. принцип оптимальности беллмана. Самостоятельная работа сатыбалдиев Т. Студент 2 курса гр. Мт(дот)120 приняла преподаватель Эсенгулова Ж. Ш

• Название: Самостоятельная работа сатыбалдиев Т. Студент 2 курса гр. Мт(дот)120 приняла преподаватель Эсенгулова Ж. Ш
• Дата: 02.06.2022
• Размер: 1.23 Mb.
• Имя файла: принцип оптимальности беллмана.rtf
• Тип: Самостоятельная работа; #564143

Министерство образования и науки Кыргызской Республики

Кыргызский национальный университет им. Ж.Баласагына

Факультет управления и бизнеса
САМОСТОЯТЕЛЬНАЯ РАБОТА

ВЫПОЛНИЛ: Сатыбалдиев Т.

Студент 2 курса гр. МТ(дот)-1-20

ПРИНЯЛА: преподаватель

Эсенгулова Ж.Ш.

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

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

- независимые переменные – они могут изменяться, но это внешние величины, не зависящие от проходящих в системе процессов;

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

- управляемые (управляющие) переменные - те, значения которых могут изменяться исследователем;

- эндогенные переменные – их значения определяются в ходе деятельности компонент системы (т.е. «внутри» системы);

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

При построении любой модели процесса принятия решения желательно придерживаться следующего плана действий:

1) Сформулировать цели изучения системы;

2) Выбрать те факторы, компоненты и переменные, которые являются наиболее существенными для данной задачи;

3) Учесть тем или иным способом посторонние, не включенные в модель факторы;

4) Осуществить оценку результатов, проверку модели, оценку полноты модели.

Модели можно делить на следующие виды:

1) Функциональные модели - выражают прямые зависимости между эндогенными и экзогенными переменными.

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

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

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

С другой стороны, модели можно делить на управляемые и прогнозные. Управляемые модели отвечают на вопрос: “Что будет, если ...?”; “Как достичь желаемого?”, и содержат три группы переменных: 1) переменные, характеризующие текущее состояние объекта; 2) управляющие воздействия - переменные, влияющие на изменение этого состояния и поддающиеся целенаправленному выбору; 3) исходные данные и внешние воздействия, т.е. параметры, задаваемые извне, и начальные параметры.

В прогнозных моделях управление не выделено явно. Они отвечают на вопросы: “Что будет, если все останется по-старому?”

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

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

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

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

где - переменная отклика;

- факторы, от которых зависит ;

- коэффициенты, которые характеризуют взаимодействие между и ;

- отражают взаимодействие между и ;

- ошибка модели,

i – номер наблюдения (измерения, опыта, анализа, испытания), i= 1, 2, n

j – номер фактора (независимой переменной), j = 1,2,…, k.

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

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

В различных источниках приводятся разные варианты классификации математических моделей. Далее приводится наиболее удачная на наш взгляд классификация математических моделей, взятая из учебного пособия Л.Э. Хазанова «Моделирование экономических процессов» см. рис. 1 с некоторыми авторскими дополнениями.

математический программирование планирование оптимальность



Рис. 1.

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

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

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

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

- модели стохастического программирования, в которых либо в целевую функцию, либо в ограничения входят случайные величины;

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

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

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

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

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

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

В общем виде задача линейного программирования ставится следующим образом.
(2.1)
при ограничениях:

где x_i, j= - управляющие переменные или решения задачи (2.1)-(2.4),

b_i, а_ij, i= , j= - параметры,

f - целевая функция или критерий эффективности задачи.

Функция (2.1) – линейная, ограниченная (2.2)-(2.4) - линейные. В данной формулировке задача линейного программирования содержит n переменных и m ограничений.

Решить задачу линейного программирования – это значит найти значения управляющих переменных x_i, j= , удовлетворяющих ограничениями (2.2)-(2.4), при которых целевая функция (2.1) принимает минимальное или максимальное значение.

В зависимости от вида целевой функции (2.1) и ограничений (2.2)-(2.4) можно выделить несколько типов задач линейного программирования или линейных моделей: общая линейная задача, транспортная задача, задача о назначениях.

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

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

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

Продукты Компоненты	Р1	Р2	Р3	….	Рn-1	Pn
k1	a11	a12	a13	….	a1n-1	an
k2	a21	a22	a23	….	a2n-1	a2n
…..	….	….	….	….	….	….
km-1	am-11	am-12	am-13	….	am-1n-1	am-1n
km	am1	am2	am3	….	amn-1	amn

Таким образом, величина a_ij есть количество i-го компонента, содержащегося в единице веса j-го продукта. Матрица , называется матрицей питательности.

Рацион кормления должен указать, какое количество х_i i-го продукта должно быть скормлено животному за определенный срок (скажем, за месяц). Он означает, что за этот срок животное должно получить единиц первого продукта x₁, единиц второго продукта – х₂, ….., единиц n-го продукта – х_n.

Рассмотрим, какие требования предъявляются к рациону. Во-первых, должны быть выполнены определенные медицинские требования, которые заключаются в том, что за указанный срок животное должно получить не менее определенного количества каждого компонента (не менее определенного количества белков, жиров, витаминов и т.д.). Обозначим через b_j то минимальное количество j-го компонента, которое должно получить животное. Тогда рацион кормления должен удовлетворять ограничениям:
(2.5)
Кроме того очевидно, что все переменные x_i неотрицательны, т.е.
x_10, x_20, ... x_n0 (2.6).
Пусть стоимость единицы веса i-го продукта равна с_i. Тогда весь наш рацион будет стоить: с₁х₁ + с₂х₂ + …..+ с_n-1x_n-1 + c_nx_n.

Целесообразно понести минимальные затраты на содержание животных. Поэтому задача о рациональном кормлении животных приобретает вид: найти рацион минимальной стоимости при выполнении медицинских ограничений (2.5) и естественных ограничений (2.6). Математически формулировка задачи выглядит следующим образом:
(2.7)
Для решения задач линейного программирования общего вида, в том числе и сформулированной выше, можно использовать:

- графический метод (для решения задач размерностью не более 3),

- симплекс-метод,

- современные пакеты прикладных программ – Mathcad, пакет «Поиск решения» табличного процессора MS Excel и другие.

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

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

В общем виде задача нелинейного программирования формулируется следующим образом:


при ограничениях:
(2.8)
где х_j – управляющие переменные или решения задачи нелинейного программирования, ,

b_i – фиксированные параметры, ,

f, g_i, - заданные нелинейные функции n переменных.

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

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

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

, (2.9)

то можно найти оптимальное решение задачи методом динамического программирования.

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

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

Управлением процесса в целом Х называется последовательность шаговых управлений Х = (x₁, х₂,..., х_i ,..., х_m).

Оптимальным управлением х* считают такое значение управления х, при котором значение W(x*) является максимальным (или минимальным, если требуется уменьшить проигрыш): W* = W(x*) = max {W(x)}, xX, где Х – область допустимых решений. Оптимальное управление х* определяется последовательностью оптимальных шаговых управлений х*=(х₁*, х₂*, …, х_m*).

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

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

Другой момент, который следует учитывать при выборе управления на данном шаге, — это возможные варианты окончания предыдущего шага. Эти варианты определяют состояние процесса. Таким образом, при выборе шагового управления необходимо учитывать: 1) возможные исходы предыдущего шага и 2) влияние управления на все оставшиеся до конца процесса шаги.

В задачах динамического программирования первый пункт учитывают, делая на каждом шаге условные предположения о возможных вариантах окончания предыдущего шага и проводя для каждого из вариантов условную оптимизацию. Выполнение второго пункта обеспечивается тем, что в задачах динамического программирования условная оптимизация проводится от конца процесса к началу. Сперва оптимизируется последний m-й шаг, на котором не надо учитывать возможные воздействия выбранного управления х_m на все последующие шаги, так как эти шаги просто отсутствуют. Делая предположения об условиях окончания (m-1)-го шага, для каждого из них проводят условную оптимизацию m-го шага и определяют условное оптимальное управление х_m. Аналогично поступают для (m-l)-ro шага, делая предположения об исходах окончания (m-2)-ro шага и определяя условное оптимальное управление на (m-1)-м шаге, приносящее оптимальный выигрыш на двух последних шагах — (m-1)-м и m-м. Так же действуют на всех остальных шагах до первого. На первом шаге, как правило, не надо делать условных предположений, так как состояние системы перед первым шагом обычно известно.

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

Для написания математической постановки задачи динамического программирования введём следующие обозначения:

s — состояние процесса;

S_j — множество возможных состояний процесса перед i-м шагом;

W_i — выигрыш с i-го шага до конца процесса, . Можно определить следующие основные этапы составления математической модели задачи динамического программирования.

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

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

3). Определение множества шаговых управлений х_i, и налагаемых на них ограничений, т.е. области допустимых управлений X.

4). Определение выигрыша  (s, x_i), который принесёт на i-м шаге управление x_i, если система перед этим находилась в состоянии s.

5). Определение состояния s', в которое переходит система из состояния s под влиянием управления х_i: ,

где f_i— функция перехода на i-м шаге из состояния s в состояние s'.

6). Составление уравнения, определяющего условный оптимальный выигрыш на последнем шаге, для состояния s моделируемого процесса:

.

7). Составление основного функционального уравнения динамического программирования, определяющего условный оптимальный выигрыш для данного состояния s с i-го шага и до конца процесса через уже известный условный оптимальный выигрыш с (i+1)-го шага и до конца:

(2.10)

В уравнении (2.10) в уже известную функцию W_i+1(s), характеризующую условный оптимальный выигрыш с (i+1)-го шага до конца процесса, вместо состояния s подставлено новое состояние s' = f_i(s, x_i), в которое система переходит на i-м шаге под влиянием управления х_i.

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

Основными метода решения задач динамического программирования является метод комбинаторного перебора возможных вариантов решений и аналогичный по идеологии – метод ветвей и границ.

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

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