Применение динамического программирования для моделирования процессов принятия решений - Экономико-математическое моделирование курсовая работа

Главная

Экономико-математическое моделирование
Применение динамического программирования для моделирования процессов принятия решений

Метод динамического программирования и его основные этапы. Оптимальная стратегия замены оборудования. Минимизация затрат на строительство и эксплуатацию предприятий. Оптимальное распределение ресурсов в ООО "СТРОЙКРОВЛЯ" и инвестиций ПКТ "Химволокно".


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ
УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ «ГРОДНЕНСКИЙ
ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ ЯНКИ КУПАЛЫ»
Кафедра системного программирования и компьютерной безопасности
Курсовая работа по предмету «Ситуационный анализ и моделирование управленческих решений»
ПРИМЕНЕНИЕ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ ДЛЯ МОДЕЛИРОВАНИЯ ПРОЦЕССОВ ПРИНЯТИЯ РЕШЕНИЙ
Студентка 3 курса 7 группы И. В. Тройко
«Применение динамического программирования для моделирования процессов принятия решений»
Работа содержит: 45 страниц, 8 рисунков, 12 таблицы, 9 использованных источников.
Ключевые слова: математическое программирование, динамическое программирование, принцип оптимальности, условная оптимизация, безусловная оптимизация, оптимальная стратегия, максимальная прибыль.
Цель: применить метод динамического программирования для оптимального распределения ресурсов и инвестиций конкретного предприятия.
Объектами исследования являются: предприятия Гродненского региона: ООО «СТРОЙКРОВЛЯ», ОАО «БелТАПАЗ», ПТК «Химволокно» и ОАО «Гродненская обувная фабрика «Неман».
Предметом изучения является метод динамического программирования и его многошаговые оптимальные решения.
Название проекта: Применение динамического программирования для моделирования процессов принятия решений.
Научный руководитель: Светлана Алексеевна Зайкова, доцент кафедры системного программирования и компьютерной безопасности, кандидат физико-математических наук, доцент.
Факультет математики и информатики, 3 курс, 7 и 8 группы, специальность - Управление информационными ресурсами.
Сроки выполнения: 18.09.2014 - 22.12.2014
Цель, задачи и исходные данные для выполнения проекта:
Цель: применить один из методов математического программирования для моделирования процессов принятия решений. Задача - применить динамическое программирование как метод нахождения оптимальных решений в конкретной экономической задаче с многоэтапной структурой.
Исходные данные для выполнения проекта:
1. Беллман Р., Динамическое программирование / Р.Беллман; под редакцией Н.Н. Воробьева -, Москва: Издательство иностранной литературы, 1960
2. Динамическая задача определения оптимальной производственной программы / А.В. Мищенко, Е.В. Джамай // Менеджмент в России и за рубежом - 2009 - №4 - C.55-59.
3. Локальные вставки на основе динамического программирования в задаче маршрутизации с ограничениями / А. А. Петунин [и др.] // Вестник Удмуртского ун-та. Математики. Механики. Компьютерной науки - 2014 - №1 - C. 32-39.
4. Элементы динамического программирования в экстремальных задачах маршрутизации / А. А. Ченцов [и др.] // Проблемы управления - 2013 - №2 - C.11-18.
1. Разработка тематики курсовой работы, определение основной проблемы. Составление плана-графика работы.
Тема курсовой работы. План-график. (Шашко Д.Ю., Тройко И.В)
2. Предварительный анализ проблемы. Определение информации, необходимой для анализа ситуации (назначение, вид, тип, источники, шкалы ее измерения).
Исходная информация для анализа, предварительный анализ проблемной ситуации. (Шашко Д.Ю., Тройко И.В)
3. Формулировка задачи принятия решений. Определение цели принятия решения, критерия (или нескольких), множества возможных альтернатив.
Формулировка задачи, критерий, альтернативы. (Шашко Д.Ю., Тройко И.В)
4. Составление математической модели проблемной ситуации (определение перечня показателей, характеризующих состояние системы, управляющих воздействий и неуправляемых факторов, взаимосвязи между ними).
Математическая модель. (Шашко Д.Ю., Тройко И.В)
5. Получение исходных данных, установление способов измерения альтернатив.
Исходные данные, способы измерения альтернатив. (Шашко Д.Ю., Тройко И.В)
6. Математическая обработка исходной информации, ее уточнение и модификация в случае необходимости.
Результаты обработки информации. (Шашко Д.Ю., Тройко И.В)
7. Анализ и интерпретация полученных результатов, Написание выводов и оформление курсовой работы. Подготовка презентации для защиты. Написание листа самооценки.
Курсовая работа с приложениями. Презентация. Доклад к защите курсовой работы. (Шашко Д.Ю., Тройко И.В)
____________________________/Шашко Д.Ю., Тройко И.В./
Согласовано с преподавателем: __________________/Зайкова С.А./
1.1 Предмет динамического программирования
1.2 Метод динамического программирования и его основные этапы
1.3 Общая постановка задачи математического программирования
1.4 Примеры задач динамического программирования
2. РЕШЕНИЕ ЭКОНОМИЧЕСКИХ ЗАДАЧ С ПОМОЩЬЮ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
2.1 Оптимальная стратегия замены оборудования
2.2 Оптимальное распределение ресурсов
2.4 Минимизация затрат на строительство и эксплуатацию предприятий
3. ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ МЕТОДА ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
3.1 Оптимальное распределение ресурсов в ООО «СТРОЙКРОВЛЯ»
3.2 Оптимальное распределение инвестиций в ОАО «БелТАПАЗ», ПКТ «Химволокно», ОАО «Гродненская обувная фабрика «НЕМАН»
Для решения многих задач оптимизации, включающих большое число переменных и ограничений в виде неравенства, классический аппарат математики оказался непригодным. И в результате пришла идея разбивать задачу большой размерности на подзадачи, включающих всего по несколько переменных, и последующего решения общей задачи по частям. Именно эта идея стала основой при создании метода динамического программирования.
Оптимизационные задачи встречаются почти во всех отраслях науки, техники и хозяйства. С ними приходится иметь дело в промышленной технологии, в организации производства, в экономическом планировании, в различных вопросах физики, биологии и военного дела. Поэтому круг применения динамического программирования широк.
Актуальность данной темы состоит в том, что в современной экономике широко используются оптимизационные методы, которые составляют основу математического программирования.
1.1 Предмет динамического программирования
Динамическое программирование представляет собой математический аппарат, который подходит к решению некоторого класса задач путем их разложения на части, небольшие и менее сложные задачи. При этом отличительной особенностью является решение задач по этапам, через фиксированные интервалы, промежутки времени, что и определило появление термина динамическое программирование. Планирование каждого шага должно проводиться с учетом общей выгоды, получаемой по завершении всего процесса, что и позволяет оптимизировать конечный результат по выбранному критерию.
Таким образом, динамическое программирование в широком смысле представляет собой оптимальное управление процессом, посредством изменения управляемых параметров на каждом шаге, и, следовательно, воздействуя на ход процесса, изменяя на каждом шаге состояние системы.
Динамическое программирование является одним из разделов оптимального программирования. Методами динамического программирования решаются вариантные оптимизационные задачи с заданными критериями оптимальности, с определенными связями между переменными и целевой функцией, выраженными системой уравнений или неравенств. Динамическое программирование можно использовать как для решения задач, связанных с динамикой процесса или системы, так и для статических задач, связанных, например, с распределением ресурсов. Это значительно расширяет область применения динамического программирования для решения задач управления. А возможность упрощения процесса решения, которая достигается за счет ограничения области и количества, исследуемых при переходе к очередному этапу вариантов, увеличивает достоинства этого комплекса методов.
Вместе с тем динамическому программированию свойственны и недостатки. Прежде всего, в нем нет единого универсального метода решения. Практически каждая задача, решаемая этим методом, характеризуется своими особенностями и требует проведения поиска наиболее приемлемой совокупности методов для ее решения. Кроме того, большие объемы и трудоемкость решения многошаговых задач, имеющих множество состояний, приводят к необходимости отбора задач малой размерности либо использования сжатой информации.
1.2 Метод динамического программирования и его основные этапы
В основе метода динамического программирования лежит принцип оптимальности, впервые сформулированный в 1953 г. американским математиком Р. Э. Беллманом: каково бы ни было состояние системы (S) в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая выигрыш на данном шаге. При решении задачи на каждом шаге выбирается управление, которое должно привести к оптимальному выигрышу. Если считать все шаги независимыми, тогда оптимальным управлением будет то управление, которое обеспечит максимальный выигрыш именно на данном шаге. [1, c.10]
Метод динамического программирования включает три основных этапа:
Предварительный этап проводится с целью уменьшения вычислительной работы на последующем этапе решения и, по существу, заключается в нахождении всех допустимых значение управлений и фазовых переменных . Иными словами, на данном этапе отбрасываются все заведомо неподходящие, нереализуемые значения фазовых и управляющих переменных. Проводится предварительный этап в естественном порядке от первого шага к последнему: i = 1, 2, … , N, а опираются соответствующие расчеты на уровне процесса
Этап условной оптимизации. На данном этапе решения задачи, называемом условной оптимизацией, определяются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем, n-м шаге, оптимальное управление - определяется функцией Беллмана (1.1):
в соответствии с которой максимум выбирается из всех возможных значений , причем
Дальнейшие вычисления производятся согласно рекуррентному соотношению, связывающему функцию Беллмана на каждом шаге с этой же функцией, но вычисленной на предыдущем шаге. В общем виде это уравнение имеет вид:
Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления X.
Безусловная оптимизация. После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый, осуществляется третий этап решения задачи, называемый безусловной оптимизацией. Пользуясь тем, что на первом шаге (k = 1) состояние системы известно - это ее начальное состояние , можно найти оптимальный результат за все n шагов и оптимальное управление на первом шаге которое этот результат доставляет. После применения этого управления система перейдет в другое состояние , зная которое, можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге , и так далее до последнего n-го шага. Вычислительную схему динамического программирования можно строить на сетевых моделях, а также по алгоритмам прямой прогонки (от начала) и обратной прогонки (от конца к началу). [1, c.20]
Порядок расчетов в методе динамического программирования может быть проиллюстрирован схемой (табл. 1.1), в которой точками обозначены состояния системы.
Порядок расчетов в методе динамического программирования
Этапы метода динамического программирования
1.3 Общая постановка задачи математического программирования
Имеется некоторая физическая система (S), которая с течением времени меняет свое состояние, т.е. в системе S происходит какой-то процесс. Мы можем управлять этим процессом, т.е. тем или иным способом влиять на состояние системы. Такая система (S) - управляемая, а способ воздействия на нее - управление (U - не какая-то одна величина, а целая совокупность величин, векторов или функций, характеризующих управление).
Предположим, что с процессом связана какая-то наша заинтересованность, выражающая численно величиной W, которую мы будем называть «выигрышем». Мы хотим управлять процессом таким образом, чтобы выигрыш был максимален.
Выигрыш зависит от уравнения [2, с.70]:
Мы хотим найти такое уравнение (оптимальное) [2, c.71]:
при котором выигрыш максимален [2, c.71]:
Запись читается «максимум по U» и означает: «максимальное из всех значений W(U) при всех возможных управления U». То из управлений, при котором достигается этот максимум, и есть оптимальное уравнение u.
Таким образом, поставлена общая задача оптимизации управления физической системой. Однако она поставлена еще не полностью. Обычно в таких задачах должны быть учтены некоторые условия, накладываемые на начальное состояние системы и конечное состояние .
Общая задача оптимального управления формулируется следующим образом:
Из множества возможных управлений U найти такое оптимальное управление и, которое переводит физическую систему S из начального состояния в конечное состояние так, чтобы при этом W обращалось в максимум.[2, c.73]
1.4 Примеры задач динамического программирования
Оптимальная стратегия замены оборудования
Одной из важных экономических проблем является определение оптимальной стратегии в замене старых станков, агрегатов, машин на новые.
Старение оборудования включает его физический и моральный износ, в результате чего растут производственные затраты по выпуску продукции на старом оборудовании, увеличиваются затраты на его ремонт и обслуживание, снижаются производительность и ликвидная стоимость.
Наступает время, когда старое оборудование выгоднее продать, заменить новым, чем эксплуатировать ценой больших затрат; причем его можно заменить новым оборудованием того же вида или новым, более совершенным.
Оптимальная стратегия замены оборудования состоит в определении оптимальных сроков замены. Критерием оптимальности при этом может служить прибыль от эксплуатации оборудования, которую следует оптимизировать, или суммарные затраты на эксплуатацию в течение рассматриваемого промежутка времени, подлежащие минимизации.
r(t) - стоимость продукции, производимой за один год на единице оборудования возраста t лет;
u(t) - ежегодные затраты на обслуживание оборудования возраста t лет;
s(t) - остаточная стоимость оборудования возраста t лет;
Рассмотрим период N лет, в пределах которого требуется определить оптимальный цикл замены оборудования.
Обозначим через fN(t) максимальный доход, получаемый от оборудования возраста t лет за оставшиеся N лет цикла использования оборудования при условии оптимальной стратегии.
Возраст оборудования отсчитывается в направлении течения процесса. Так, t = 0 соответствует случаю использования нового оборудования. Временные же стадии процесса нумеруются в обратном направлении по отношению к ходу процесса. Так, N = 1 относится к одной временной стадии, остающейся до завершения процесса, а N = N - к началу процесса (рис. 1.1).
На каждом этапе N-стадийного процесса должно быть принято решение о сохранении или замене оборудования. Выбранный вариант должен обеспечивать получение максимальной прибыли.
Функциональные уравнения, основанные на принципе оптимальности, имеют вид:
Уравнение (1.6) описывает N-стадийный процесс, а (1.7) - одностадийный. Оба уравнения состоят из двух частей: верхняя строка определяет доход, получаемый при сохранении оборудования; нижняя - доход, получаемый при замене оборудования и продолжении процесса работы на новом оборудовании.
В уравнении (1.6) функция r(t) - u(t) есть разность между стоимостью произведенной продукции и эксплуатационными издержками на N-й стадии процесса.
Функция fN-1 (t + 1) характеризует суммарную прибыль от (N - 1) оставшихся стадий для оборудования, возраст которого в начале осуществления этих стадий составляет (t + 1) лет.
Нижняя строка (1.6) характеризуется следующим образом: функция s(t)-Р представляет чистые издержки по замене оборудования, возраст которого t лет.
Функция r(0) выражает доход, получаемый от нового оборудования возраста 0 лет. Предполагается, что переход от работы на оборудовании возраста t лет к работе на новом оборудовании совершается мгновенно, т.е. период замены старого оборудования и переход на работу на новом оборудовании укладываются в одну и ту же стадию.
Последняя функция fN-1 в (1.6) представляет собой доход от оставшихся N-1 стадий, до начала осуществления которых возраст оборудования составляет один год.
Аналогичная интерпретация может быть дана уравнению для одностадийного процесса. Здесь нет слагаемого вида f0(t + 1), так как N принимает значение 1, 2, ... , N. Равенство f0(t) = 0 следует из определения функции fN(t).
Уравнения (1.6) и (1.7) являются рекуррентными соотношениями, которые позволяют определить величину fN(t) в зависимости от fN-1(t + 1). Структура этих уравнений показывает, что при переходе от одной стадии процесса к следующей возраст оборудования увеличивается с t до (t + 1) лет, а число оставшихся стадий уменьшается с N до (N-1).
Расчет начинают с использования уравнения (1.6). Уравнения (1.6) и (1.7) позволяют оценить варианты замены и сохранения оборудования, с тем чтобы принять тот из них, который предполагает больший доход. Эти соотношения дают возможность не только выбрать линию поведения при решении вопроса о сохранении или замене оборудования, но и определить прибыль, получаемую при принятии каждого из этих решений. [3, c.56]
Пусть имеется некоторое количество ресурсов х, которое необходимо распределить между п различными предприятиями, объектами, работами и т.д. так, чтобы получить максимальную суммарную эффективность от выбранного способа распределения.
Введем обозначения: - количество ресурсов, выделенных i-му предприятию ;
функция полезности, в данном случае это величина дохода от использования ресурса , полученного i-м предприятием;
- наибольший доход, который можно получить при использовании ресурсов х от первых k различных предприятий.
Сформулированную задачу можно записать в математической форме:
Для решения задачи необходимо получить рекуррентное соотношение, связывающее и .
Обозначим через количество ресурса, используемого k-м способом (0 ? ? х), тогда для (k-1) способов остается величина ресурсов, равная (). Наибольший доход, который получается при использовании ресурса () от первых (k - 1) способов, составит ().
Для максимизации суммарного дохода от k-гo и первых (k - 1) способов необходимо выбрать таким образом, чтобы выполнялись соотношения
Минимизация затрат на строительство и эксплуатацию предприятий
Задача по оптимальному размещению производственных предприятий может быть сведена к задаче распределения ресурсов согласно критерию минимизации с учетом условий целочисленности, накладываемых на переменные.
Пусть задана потребность в пользующемся спросом продукте на определенной территории. Известны пункты, в которых можно построить предприятия, выпускающие данный продукт. Подсчитаны затраты на строительство и эксплуатацию таких предприятий.
Необходимо так разместить предприятия, чтобы затраты на их строительство и эксплуатацию были минимальные.
x - количество распределяемого ресурса, которое можно использовать п различными способами,
количество ресурса, используемого по i-му способу ();
функция расходов, равная, например, величине затрат на производство при использовании ресурса по i-му способу;
наименьшие затраты, которые нужно произвести при использовании ресурса х первыми k способами.
Необходимо минимизировать общую величину затрат при освоении ресурса x всеми способами:
Экономический смысл переменных состоит в нахождении количества предприятий, рекомендуемого для строительства в i-м пункте. Для удобства расчетов будем считать, что планируется строительство предприятий одинаковой мощности. [4, c.312]
2. РЕШЕНИЕ ЭКОНОМИЧЕСКИХ ЗАДАЧ С ПОМОЩЬЮ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
2.1 Оптимальная стратегия замены оборудования
Для осуществления своей эффективной деятельности производственные объединения и предприятия должны периодически проводить замену используемого ими оборудования. При этой замене учитываются:
производительность используемого оборудования;
затраты, связанные с содержанием и ремонтом;
стоимость приобретаемого и заменяемого оборудования.
К началу текущего пятилетнего периода на предприятии установлено новое оборудование. Зависимость производительности этого оборудования от времени его использования предприятием, а также зависимость затрат на содержание и ремонт оборудования при различном времени его использовании заданы в табл. 2.1.
Зависимость производительности оборудования от времени его использования предприятием и зависимость затрат на содержание и ремонт при различном времени его использовании.
Время t в течение которого используется оборудование, годы
Годовой выпуск продукции R(t) в стоимостном выражении, тыс. ден. ед.
Ежегодные затраты Z(t), связанные с содержанием и ремонтом оборудования, тыс. ден. ед.
Зная, что затраты, связанные с приобретением и установкой нового оборудования, идентичного с установленным, составляют 40 тыс. ден. ед., а заменяемое оборудование списывается, составить такой план замены оборудования в течение пяти лет, при котором общая прибыль за данный временной период максимальна.
Решение. В качестве системы S выступает оборудование. Состояния этой системы к началу k-го года определяются фактическим временем использования оборудования (его возрастом) . В качестве управлений выступают решения о замене или сохранности оборудования, применяемые в начале каждого года.
Обозначим через С решение о сохранении оборудования, а через З - решение о замене оборудования. Тогда задача состоит в нахождении такой стратегии управления, определяемой решениями, применяемыми к началу каждого года, при которой общая прибыль предприятия за пять лет является максимальной.
Следует отметить, что задача обладает свойствами аддитивности и отсутствия последействия. Решая задачу методом динамического программирования, на первом этапе при движении от начала пятого года к началу первого года для каждого допустимого состояния оборудования найдём условное оптимальное управление, а на втором этапе при движении от начала первого года к началу пятого года из условных оптимальных решений для каждого года составим оптимальный план замены оборудования на пять лет.
Пусть управления, применяемые в начале каждого года, - прибыль предприятия за k-й год. Очевидно, что
В этом случае основное функциональное уравнение Беллмана имеет вид
Этап 1. Используя уравнение Беллмана, найдём условно оптимальные решения для последнего (пятого) года, для чего определяем множество допустимых состояний оборудования к началу этого года. Поскольку в начале пятилетнего периода имеется новое оборудование (=0) возраст оборудования к началу пятого года может составлять 1, 2, 3 и 4 года. Поэтому допустимые состояния системы на данный период времени таковы:
Для каждого из этих состояний найдём условно оптимальное решение и соответствующее значение функции .
Подставляя в полученную формулу вместо его значения и учитывая данные табл. 2.1, находим:
Полученные результаты вычислений сведём в табл. 2.2.
Условно оптимальное решение и соответствующее значение функции .
Значение функции дохода , тыс. ден. ед.
Рассмотрим теперь возможные состояния оборудования к началу четвертого года. Очевидно, допустимыми состояниями являются
Для каждого из них определяем условно оптимальное решение и соответствующее значение функции . С этой целью воспользуемся данными табл. 2.1 и 2.2, а также основным функциональным уравнением Беллмана.
Полученные результаты вычислений сведём в табл. 2.3.
Условно оптимальное решение и соответствующее значение функции
Значение функции дохода , тыс. ден. ед.
Определим теперь условно оптимальное решение для каждого из допустимых состояний оборудования к началу третьего года. Очевидно, такими состояниями являются:
В соответствии с основным функциональным уравнением Беллмана, данными табл. 2.1, 2.3 получим:
Полученные результаты вычислений сведём в табл. 2.4.
Условно оптимальное решение и соответствующее значение функции
Значение функции дохода , тыс. ден. ед.
Далее, к началу второго года возраст оборудования может быть равен только одному году, поэтому
Наконец, так как к началу пятилетнего периода установлено новое оборудование (), то
Этап 2. Рассмотрим полученные результаты в обратном порядке.
Для первого года решение единственно - следует сохранить оборудование, следовательно, возраст оборудования к началу второго года равен одному году.
В этом случае оптимальным решением для второго года является решение о сохранении оборудования. Реализация такого решения приводит к тому, что возраст оборудования к началу третьего года становится равным двум годам.
При таком возрасте оборудование следует заменить. После замены оборудования его возраст к началу четвёртого года составит один год. Как видно из табл. 2.3, при таком возрасте оборудования его менять не следует.
В соответствии с этим возраст оборудования к началу пятого года составит два года, а значит, согласно табл. 2.2, оборудование менять нецелесообразно.
Таким образом, получается следующий оптимальный план замены оборудования (табл. 2.5).
Максимальная прибыль предприятия равна 215 тыс. ден. ед. Общая схема возможных состояний системы и управлений за пятилетний период изображена на рис. 2.1. [5, c.212]
Оптимальный план замены оборудования.
Рисунок 2.1 Общая схема возможных состояний и управлений за пятилетний период: С - сохранение оборудования; З - замена оборудования
2.2 Оптимальное распределение ресурсов
Инвестор выделяет средства в размере 5 тыс. ден. ед., которые должны быть распределены между тремя предприятиями.
Требуется, используя принцип оптимальности Беллмана, построить план распределения инвестиций между предприятиями, обеспечивающий наибольшую общую прибыль, если каждое предприятие при инвестировании в него средств x тыс. ден. ед. приносит прибыль тыс. ден. ед. (i=1, 2 и 3) по следующим данным:
Данные для построения плана распределения инвестиций
Инвестирование средств (тыс. ден. ед.)
Решение. Составим математическую модель задачи.
Пусть s - количество средств, имеющихся в наличии перед данным шагом, и характеризующих состояние системы на каждом шаге.
Управление на i-ом шаге (i=1,2,3) выберем - количество средств, инвестируемых в i-ое предприятие.
Выигрыш на i-ом шаге - это прибыль, которую приносит i-ое предприятие при инвестировании в него средств . Если через выигрыш в целом обозначить общую прибыль W, то
Если в наличии имеются средства в количестве s тыс. ден. ед. и в i-ое предприятие инвестируется x тыс. ден. ед, то для дальнейшего инвестирования остается (s-x) тыс. ден. ед. Таким образом, если на i-ом шаге система находилась в состоянии s и выбрано управление x, то на (i+1)-ом шаге система будет находится в состоянии (s-x), и, следовательно, функция перехода в новое состояние имеет вид: .
На последнем (i=3) шаге оптимальное управление соответствует количеству средств, имеющихся в наличии, а выигрыш равен доходу, приносимым последним предприятием:
Согласно принципу оптимальности Беллмана, управление на каждом шаге нужно выбирать так, чтобы оптимальной была сумма выигрышей на всех оставшихся до конца процесса шагах, включая выигрыш на данном шаге. Основное функциональное уравнение примет вид:
Проведем пошаговую оптимизацию, по результатам которой заполним таблицу.
В первой колонке таблицы записываются возможные состояния системы, в верхней строке - номера шагов с оптимальным управлением и выигрышем на каждом шаге, начиная с последнего. Так как для последнего шага i=3 функциональное уравнение имеет вид , то две колонки таблицы, соответствующие i = 3, заполняются автоматически по таблице исходных данных.
На шаге i=2 основное функциональное уравнение имеет вид:
Поэтому для проведения оптимизации на этом шаге заполним таблицу для различных состояний s при шаге i=3.
Различные состояния системы на шаге i=3
На шаге i=1 основное функциональное уравнение имеет вид:
А состояние системы перед первым шагом s=5, поэтому для проведения оптимизации на этом шаге заполним таблицу.
Различные состояния системы при шаге i=1
Видно, что наибольшее значение выигрыша составляет 19,26. При этом оптимальное управление на первом шаге составляет , на втором шаге , и на третьем шаге .
Это означает, что (0, 1, 4) - оптимальный план распределения инвестиций между предприятиями.
Таким образом, для получения наибольшей общей прибыли в размере 19,26 тыс. ден. ед., необходимо вложить 1 тыс. ден. ед. во второе предприятие и 4 тыс. ден. ед. в третье предприятие. [5, c.218]
2.3 Минимизация затрат на строительство и эксплуатацию предприятий
В трех районах города предприниматель планирует построить пять предприятий одинаковой мощности по выпуску хлебобулочных изделий, пользующихся спросом.
Необходимо разместить предприятия таким образом, чтобы обеспечить минимальные суммарные затраты на их строительство и эксплуатацию. Значения функции затрат приведены в табл. 2.10.
В данном примере - функция расходов в млн р., характеризующая величину затрат на строительство и эксплуатацию в зависимости от количества размещаемых предприятий в i-м районе;
- наименьшая величина затрат в млн. р., которые нужно произвести при строительстве и эксплуатации предприятий в первых k районах.
Решение. Решение задачи проводим с использованием рекуррентных соотношений: для первого района:
1-й этап. Если все предприятия построить только в первом районе, то
минимально возможные затраты при х = 5 составляют 76 млн р.
2-й этап. Определим оптимальную стратегию при размещении предприятий только в первых двух районах по формуле:
3-й этап. Определим оптимальную стратегию при размещении пяти предприятий в трех районах по формуле:
Минимально возможные затраты при х = 5 составляют 46 млн р.
Определены затраты на строительство предприятий от 1-го до 3-го этапа. Вернемся 3-го к 1-му этапу. Минимальные затраты в 46 млн р. на 3-м этапе получены как 9 + 37, т.е. 9 млн р. соответствуют строительству одного предприятия в третьем районе (см. табл. 6 ). Согласно 2-му этапу 37 млн р. получены как 19 + 18, т.е. 19 млн р. соответствуют строительству двух предприятий во втором районе. Согласно 1-му этапу 18 млн р. соответ
Применение динамического программирования для моделирования процессов принятия решений курсовая работа. Экономико-математическое моделирование.
Оценка Защиты Курсовой Работы
Отчет По Практике Отдела Продаж
Реферат по теме Великое переселение народов
Реферат По Физкультуре Тема Баскетбол
Получение Водорода Лабораторная Работа
Икт В Горном Деле Реферат
Реферат: SameSex Marriages Essay Research Paper SameSex Marriages
Контрольная работа по теме Динамика численности населения России
Реферат: Устойчивость линейной системы авторегулирования
Сочинение Ялтинская Дача Чехова Стояла Почти
Система Ключевых Показателей Эффективности Курсовая
Анализ Защиты Реферата
Контрольная Работа На Тему Контроль За Средствами Распространения Рекламы
Импедансный Метод Дипломная Работа Pdf
Курсовая работа по теме Влияние рационального питания на здоровье студентов
Контрольная работа по теме Анализ экономического потенциала машиностроения и металлообработки
Реферат: Rocking Horse Winner By Lawrence Essay Research
Чрезвычайные Ситуации Чс Природного Характера Реферат
Характеристика На Практиканта Педагогической Практики В Доу
Реферат: Нужны ли нам витамины
Разработка и технология производства рекламного плаката (на примере сети магазинов "Детский мир") - Маркетинг, реклама и торговля курсовая работа
Технология изготовления билета учащегося - Производство и технологии дипломная работа
Рынок ценных бумаг. Фондовый рынок Украины - Финансы, деньги и налоги курсовая работа