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

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

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ «ГРОДНЕНСКИЙ

ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ ЯНКИ КУПАЛЫ»

ФАКУЛЬТЕТ МАТЕМАТИКИ И ИНФОРМАТИКИ

Кафедра системного программирования и компьютерной безопасности

Курсовая работа по предмету «Ситуационный анализ и моделирование управленческих решений»

ПРИМЕНЕНИЕ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ ДЛЯ МОДЕЛИРОВАНИЯ ПРОЦЕССОВ ПРИНЯТИЯ РЕШЕНИЙ

Авторы работы

Студентка 3 курса 8 группы

Д. Ю. Шашко

Студентка 3 курса 7 группы И. В. Тройко

Руководители

Доцент каф. СПиКБ С. А. Зайкова

Гродно, 2014



РЕЗЮМЕ

Тема курсовой работы

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

Работа содержит: 45 страниц, 8 рисунков, 12 таблицы, 9 использованных источников.

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

Цель: применить метод динамического программирования для оптимального распределения ресурсов и инвестиций конкретного предприятия.

Объектами исследования являются: предприятия Гродненского региона: ООО «СТРОЙКРОВЛЯ», ОАО «БелТАПАЗ», ПТК «Химволокно» и ОАО «Гродненская обувная фабрика «Неман».

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



ТЕХНИЧЕСКОЕ ЗАДАНИЕ

от "18" сентября 2014г.

Название проекта: Применение динамического программирования для моделирования процессов принятия решений.

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

Факультет математики и информатики, 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.

6. Этапы проекта:

Наименование этапов	Сроки выполнения	Ожидаемые результаты
1	3	4
1. Разработка тематики курсовой работы, определение основной проблемы. Составление плана-графика работы.	18.09.2014-28.09.2014	Тема курсовой работы. План-график. (Шашко Д.Ю., Тройко И.В)
2. Предварительный анализ проблемы. Определение информации, необходимой для анализа ситуации (назначение, вид, тип, источники, шкалы ее измерения).	24.09.2014-30.09.2014	Исходная информация для анализа, предварительный анализ проблемной ситуации. (Шашко Д.Ю., Тройко И.В)
3. Формулировка задачи принятия решений. Определение цели принятия решения, критерия (или нескольких), множества возможных альтернатив.	01.10.2014-05.10.2014	Формулировка задачи, критерий, альтернативы. (Шашко Д.Ю., Тройко И.В)
4. Составление математической модели проблемной ситуации (определение перечня показателей, характеризующих состояние системы, управляющих воздействий и неуправляемых факторов, взаимосвязи между ними).	06.10.2014-20.10.2014	Математическая модель. (Шашко Д.Ю., Тройко И.В)
5. Получение исходных данных, установление способов измерения альтернатив.	21.10.2014-01.11.2014	Исходные данные, способы измерения альтернатив. (Шашко Д.Ю., Тройко И.В)
6. Математическая обработка исходной информации, ее уточнение и модификация в случае необходимости.	02.11.2014-17.11.2014	Результаты обработки информации. (Шашко Д.Ю., Тройко И.В)
7. Анализ и интерпретация полученных результатов, Написание выводов и оформление курсовой работы. Подготовка презентации для защиты. Написание листа самооценки.	18.11.2014-22.12.2014	Курсовая работа с приложениями. Презентация. Доклад к защите курсовой работы. (Шашко Д.Ю., Тройко И.В)

Исполнители:

____________________________/Шашко Д.Ю., Тройко И.В./

Согласовано с преподавателем: __________________/Зайкова С.А./



СОДЕРЖАНИЕ

ВВЕДЕНИЕ

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

1.1 Предмет динамического программирования

1.2 Метод динамического программирования и его основные этапы

1.3 Общая постановка задачи математического программирования

1.4 Примеры задач динамического программирования

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

2.1 Оптимальная стратегия замены оборудования

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

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

3. ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ МЕТОДА ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

3.1 Оптимальное распределение ресурсов в ООО «СТРОЙКРОВЛЯ»

3.2 Оптимальное распределение инвестиций в ОАО «БелТАПАЗ», ПКТ «Химволокно», ОАО «Гродненская обувная фабрика «НЕМАН»

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ



ВВЕДЕНИЕ

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

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

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



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

1.1 Предмет динамического программирования

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

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

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

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

1.2 Метод динамического программирования и его основные этапы

В основе метода динамического программирования лежит принцип оптимальности, впервые сформулированный в 1953 г. американским математиком Р. Э. Беллманом: каково бы ни было состояние системы (S) в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая выигрыш на данном шаге. При решении задачи на каждом шаге выбирается управление, которое должно привести к оптимальному выигрышу. Если считать все шаги независимыми, тогда оптимальным управлением будет то управление, которое обеспечит максимальный выигрыш именно на данном шаге. [1, c.10]

Метод динамического программирования включает три основных этапа:

Предварительный этап.

Этап условной оптимизации.

Этап безусловной оптимизации.

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

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

	(1.1)

в соответствии с которой максимум выбирается из всех возможных значений , причем

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

	(1.2)

Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления X.

Безусловная оптимизация. После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый, осуществляется третий этап решения задачи, называемый безусловной оптимизацией. Пользуясь тем, что на первом шаге (k = 1) состояние системы известно - это ее начальное состояние , можно найти оптимальный результат за все n шагов и оптимальное управление на первом шаге которое этот результат доставляет. После применения этого управления система перейдет в другое состояние , зная которое, можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге , и так далее до последнего n-го шага. Вычислительную схему динамического программирования можно строить на сетевых моделях, а также по алгоритмам прямой прогонки (от начала) и обратной прогонки (от конца к началу). [1, c.20]

Порядок расчетов в методе динамического программирования может быть проиллюстрирован схемой (табл. 1.1), в которой точками обозначены состояния системы.

Таблица 1.1

Порядок расчетов в методе динамического программирования

Этапы метода динамического программирования	Номера шагов процесса 1 2 … N
Предварительный	. … …
Условной оптимизации
Безусловной оптимизации

1.3 Общая постановка задачи математического программирования

Имеется некоторая физическая система (S), которая с течением времени меняет свое состояние, т.е. в системе S происходит какой-то процесс. Мы можем управлять этим процессом, т.е. тем или иным способом влиять на состояние системы. Такая система (S) - управляемая, а способ воздействия на нее - управление (U - не какая-то одна величина, а целая совокупность величин, векторов или функций, характеризующих управление).

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

Выигрыш зависит от уравнения [2, с.70]:

	(1.3)

Мы хотим найти такое уравнение (оптимальное) [2, c.71]:

	(1.4)

при котором выигрыш максимален [2, c.71]:

	(1.5)

Запись читается «максимум по 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.1 Стадии решения задачи.

Функциональные уравнения, основанные на принципе оптимальности, имеют вид:

	(1.6)
	(1.7)



Уравнение (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 различных предприятий.

Сформулированную задачу можно записать в математической форме:

	(1.8)

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

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

Обозначим через количество ресурса, используемого k-м способом (0 ? ? х), тогда для (k-1) способов остается величина ресурсов, равная (). Наибольший доход, который получается при использовании ресурса () от первых (k - 1) способов, составит ().

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

	(1.9)
	(1.10)

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

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

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

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

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

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

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

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

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

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

	(1.11)

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

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



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

2.1 Оптимальная стратегия замены оборудования

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

производительность используемого оборудования;

затраты, связанные с содержанием и ремонтом;

стоимость приобретаемого и заменяемого оборудования.

К началу текущего пятилетнего периода на предприятии установлено новое оборудование. Зависимость производительности этого оборудования от времени его использования предприятием, а также зависимость затрат на содержание и ремонт оборудования при различном времени его использовании заданы в табл. 2.1.

Таблица 2.1

Зависимость производительности оборудования от времени его использования предприятием и зависимость затрат на содержание и ремонт при различном времени его использовании.

	Время t в течение которого используется оборудование, годы
	0	1	2	3	4	5
Годовой выпуск продукции R(t) в стоимостном выражении, тыс. ден. ед.	80	75	65	60	60	55
Ежегодные затраты Z(t), связанные с содержанием и ремонтом оборудования, тыс. ден. ед.	20	25	30	35	45	55

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

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

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

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

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

	(2.1)

В этом случае основное функциональное уравнение Беллмана имеет вид

	(2.2)

Этап 1. Используя уравнение Беллмана, найдём условно оптимальные решения для последнего (пятого) года, для чего определяем множество допустимых состояний оборудования к началу этого года. Поскольку в начале пятилетнего периода имеется новое оборудование (=0) возраст оборудования к началу пятого года может составлять 1, 2, 3 и 4 года. Поэтому допустимые состояния системы на данный период времени таковы:

.

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

	(2.3)

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

Полученные результаты вычислений сведём в табл. 2.2.

Таблица 2.2

Условно оптимальное решение и соответствующее значение функции .

Возраст оборудования , Годы	Значение функции дохода , тыс. ден. ед.	Условно оптимальное решение
1	50	С
2	35	С
3	25	С
4	20	З

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

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

Полученные результаты вычислений сведём в табл. 2.3.

Таблица 2.3

Условно оптимальное решение и соответствующее значение функции

Возраст оборудования , годы	Значение функции дохода , тыс. ден. ед.	Условно оптимальное решение
1	85	С
2	70	С
3	70	З

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

В соответствии с основным функциональным уравнением Беллмана, данными табл. 2.1, 2.3 получим:

Полученные результаты вычислений сведём в табл. 2.4.



Таблица 2.4

Условно оптимальное решение и соответствующее значение функции

Возраст оборудования , годы	Значение функции дохода , тыс. ден. ед.	Условно оптимальное решение
1	120	С
2	105	З

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

Наконец, так как к началу пятилетнего периода установлено новое оборудование (), то

Этап 2. Рассмотрим полученные результаты в обратном порядке.

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

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

При таком возрасте оборудование следует заменить. После замены оборудования его возраст к началу четвёртого года составит один год. Как видно из табл. 2.3, при таком возрасте оборудования его менять не следует.

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

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

Максимальная прибыль предприятия равна 215 тыс. ден. ед. Общая схема возможных состояний системы и управлений за пятилетний период изображена на рис. 2.1. [5, c.212]

Таблица 2.5

Оптимальный план замены оборудования.

	Годы пятилетнего периода
	1	2	3	4	5
Оптимальное Решение	Сохранить оборудование	Сохранить оборудование	Произвести замену оборудования	Сохранить оборудование	Сохранить оборудование

Рисунок 2.1 Общая схема возможных состояний и управлений за пятилетний период: С - сохранение оборудования; З - замена оборудования

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

Инвестор выделяет средства в размере 5 тыс. ден. ед., которые должны быть распределены между тремя предприятиями.

Требуется, используя принцип оптимальности Беллмана, построить план распределения инвестиций между предприятиями, обеспечивающий наибольшую общую прибыль, если каждое предприятие при инвестировании в него средств x тыс. ден. ед. приносит прибыль тыс. ден. ед. (i=1, 2 и 3) по следующим данным:

Таблица 2.7

Данные для построения плана распределения инвестиций

Инвестирование средств (тыс. ден. ед.)	Прибыль (тыс. ден. ед.)
X
1	3,22	3,33	4,27
2	3,57	4,87	7,64
3	4,12	5,26	10,25
4	4	7,34	15,93
5	4,85	9,49	16,12

Решение. Составим математическую модель задачи.

Число шагов равно 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) шаге оптимальное управление соответствует количеству средств, имеющихся в наличии, а выигрыш равен доходу, приносимым последним предприятием:

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

	(2.4)

Проведем пошаговую оптимизацию, по результатам которой заполним таблицу.

Таблица 2.8

Пошаговую оптимизация

S	i=3	i=2	i=1
1	1	4.27	0	4.27
2	2	7.64	0	7.64
3	3	10.25	1	10.97
4	4	15.93	0	15.93
4	5	16.12	1	19.26	0	19.26

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

На шаге i=2 основное функциональное уравнение имеет вид:



	(2.5)

Поэтому для проведения оптимизации на этом шаге заполним таблицу для различных состояний s при шаге i=3.

Таблица 2.9

Различные состояния системы на шаге i=3

S	x	s-x
1	0	1	0	4.27	4.27	4.27
	1	0	3.33	0	3.33
2	0	2	0	7.6	7.64	7.64
	1	1	3.33	4.27	7.6
	2	0	4.87	0	4.87
3	0	3	0	10.25	10.25	10.97
	1	2	3.33	7.64	10.97
	2	1	4.87	4.27	9.14
	3	0	5.26	0	5.26
4	0	4	0	15.93	15.93	15.93
	1	3	3.33	10.25	13.59
	2	2	4.87	7.6	12.51
	3	1	5.26	4.27	9.53
	4	0	7.34	0	7.34
5	0	5	0	16.12	16.12	19.26
	1	43	3.33	15.93	19.26
	2	2	4.87	10.25	15.12
	3	1	5.26	7.64	12.9
	4	0	7.34	4.270	11.61
	5		9.9		9.49

На шаге i=1 основное функциональное уравнение имеет вид:

	(2.6)



А состояние системы перед первым шагом s=5, поэтому для проведения оптимизации на этом шаге заполним таблицу.

Таблица 2.10

Различные состояния системы при шаге i=1

S	x	s-x
5	0	5	0	19.26	19.26	19.26
	1	4	3.22	15.93	19.15
	2	3	3.57	10.97	14.54
	3	2	4.12	7.64	11.76
	4	1	4	4.27	8.27
	5	0	4.85	0	4.85

Видно, что наибольшее значение выигрыша составляет 19,26. При этом оптимальное управление на первом шаге составляет , на втором шаге , и на третьем шаге .

Это означает, что (0, 1, 4) - оптимальный план распределения инвестиций между предприятиями.

Таким образом, для получения наибольшей общей прибыли в размере 19,26 тыс. ден. ед., необходимо вложить 1 тыс. ден. ед. во второе предприятие и 4 тыс. ден. ед. в третье предприятие. [5, c.218]

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

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

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

Таблица 2.11

Значения функции затрат

x	1	2	3	4	5
	11	18	35	51	76
	10	19	34	53	75
	9	20	36	54	74

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

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

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

,	(2.7)

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

	(2.7)

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

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

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

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

	(2.8)

Найдем :

Вычислим :

Найдем:

Определим :

Вычислим :

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

	(2.9)

Найдем :

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

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

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



3. ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ МЕТОДА ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

3.1 Оптимальное распределение ресурсов в ООО «СТРОЙКРОВЛЯ»

Общество с ограниченной ответственностью «СТРОЙКРОВЛЯ», специализирующаяся на кровельных работах, использует большое количество металлочерепицы (около 35 000 кв. м в год). При небольших закупках, на одну кровлю ( кв. м), один метр черепицы стоит $10.2. При заказе 900 кв. м и более цена 1 кв. м снижается на $0.5. При крупных заказах свыше 3000 кв. м скидка составляет уже 7.5% за кв. м и наконец при заказе партии в 8000 кв. м поставщик устанавливает цену в $9.3 за кв. м, т.к. это количество составляет ровно 1 контейнер и поставщику не приходится самому формировать заказ. Издержки по оформлению заказа и его доставке составляют $500.

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

Проблемы, которые следует решить:

Какой план заказов самый оптимальный в этой ситуации?

Каковы были бы издержки в этом случае?

Решение задачи.

Q - объем заказа, количество единиц;

EOQ - экономический размер заказа;

n - число заказов в год;

D - годовой спрос, количество единиц;

S - издержки заказа;

C - стоимость единицы товара, изделия;

H - затраты хранения в год, процентов от стоимости;

Т - время выполнения заказа, доставки.

Организация задачи на листе Excel

Рисунок 3.1

Рисунок 3.2

Выберем наименьшие издержки в последней строке таблицы. Эти издержки - $327688 - соответствуют размеру заказа 8000 кв. м. Таким образом выгоднее всего заказывать каждый раз по 8000 кв. м.

Однако если посмотреть на число заказов в год для этой величины заказа, мы увидим, что оно не целое 4.4 заказа. На практике это означает, что в двух годовых периодах из пяти будет сделано 5 заказов, а в оставшихся трех - 4 заказа. Если поделить число дней в году на 4.4, то мы найдем, что промежуток между заказами составляет 83 дня. Обычно это не создает никаких проблем. Но в этой задаче поставлено условие - переноса остатка на другой год быть не должно. Для нас это значит, что число заказов в год должно быть целым.

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

Рассмотрим другие варианты заказов. Во-первых, можно заметить, что на в одном из четырех рассмотренных нами случаев число заказов не получилось целым. Наиболее близким к целому числу получилось количество заказов при покупке металлочерепицы по цене $9.44. Если заказывать не по 4973 кв. м, как советует теория, а по 5000, то как раз и получится ровно 7 заказов в год. Причем общие издержки в этом случае то же невелики и не могут сильно вырасти при столь незначительном отклонении от EOQ.

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

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

В-третьих, вовсе не обязательно выбирать равное по размеру заказы. Т.к. заказ партиями по 8000 кв. м выгоднее всего, то можно попробовать сделать 4 заказа по 8000 кв. м и 1 заказ на 3000 кв. м или 3 по 8000 кв. м и 2 по 5500 кв. м.

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

Рисунок 3.3

Рисунок 3.4



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

Третий вариант представляет систему неравных заказов, поэтому при расчете по прежней схеме мы получаем два значения годовых издержек: издержки $333744 соответствуют тому, что мы делаем в течение года равные заказы размером 5500 кв. м, а издержка $327 688 - тому, что делаем в течение года заказы размером 8000 кв. м. Но ведь на самом деле это не так. На деле какую-то часть года мы делаем заказы по 5500, а остальное время - по 8000. Можно даже точно сказать, как распределяться эти доли, пологая, что расход материала равномерный. Т.к. по системе заказов по 5500 кв. м мы получим 11000 кв. м черепицы, а по системе заказов по 8000 кв. м - 24000 кв. м, резонно будет сделать вывод, что 11/35 года делались заказы по 5500, а 24/35 года - по 8000 кв. м. Оказывается, что для вычисления годовых расходов при неравных заказах, суммы расхода, полученные в строке T+TC, нужно просто взвесить с весами, пропорциональными времени действия каждого размера заказа. Таким образом и получено число в строке «Итог» для третьего варианта выбора заказов: 329591 = 11/35*333744 + 24/35*327688 Вывод: третий вариант оказался лучше первого, но хуже второго.

В четвертом варианте, так же с неравными заказами, периоды действия заказов по 3000 кв. м равны 3/35 и 32/35 года соответственно. Взвешивание годовых расходов из строки T+TC дает итоговую сумму издержек $328 222 - так же очень хороший результат. Однако вариант 2 остался чуть более выгодным.

Вывод: в результате получилось, что кроме очевидного варианта заказа 7 раз по 5000 кв. м нашлось еще 3 возможных варианта, и все они выгоднее первого, но самый оптимальный вариант заказа под номером два.

3.2 Оптимальное распределение инвестиций в ОАО «БелТАПАЗ», ПКТ «Химволокно», ОАО «Гродненская обувная фабрика «НЕМАН»

ОАО «Гродненский завод токарных патронов «БелТАПАЗ» выпускает самоцентрирующие токарные патроны, которые предназначены для установки на универсальные токарные, револьверные, внутришлифовальные станки, делительные головки и различные приспособления.

С целью расширения номенклатуры конкурентоспособных токарных патронов, соответствующих международным стандартам по безопасности и уменьшения материалоемкости деталей и узлов энергонасыщенных тракторов, планируется реализация проекта по техническому перевооружению ОАО «Гродненский завод токарных патронов «БелТАПАЗ». динамическое программирование оптимальная инвестиция

Продукция, планируемая к выпуску:

Токарные патроны Ж 500 мм и Ж 630 мм;

Детали и узлы к тракторам «Беларус» (заказ ПО «Минский тракторный завод»).

ПТК «Химволокно» ОАО «Гродно Азот» является крупным производителем полиамидных и полиэфирных нитей и волокон, а также полиамида-6 (ПА-6) и полимерных композиционных материалов на его основе. Каждый из основных видов продукции производится в широком ассортименте с различными физико-механическими свойствами и показателями качества в зависимости от области применения. Основным стратегическим направлением в развитии ПТК «Химволокно» является повышение конкурентоспособности выпускаемой продукции за счет улучшения качества и снижения издержек, а также ориентация производства на более глубокую и эффективную переработку сырья. В результате реализации одного из важнейших инвестиционных проектов в ПТК «Химволокно», увеличилось производство полиамида 6. С целью углубления переработки полиамида 6 и увеличения объема производства востребованных на рынке полимерных композиционных материалов на основе полиамида 6, планируется наращивание мощностей по производству полимерных композиционных материалов за счет закупки и введения в эксплуатацию комплектной линии по производству композиционных материалов. 

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

Открытое акционерное общество «Гродненская обувная фабрика «Неман» является одним из крупных предприятий легкой промышленности Республики Беларусь. На предприятии постоянно ведется целенаправленная работа по улучшению качества и внешнего вида обуви, чему способствует применение современных натуральных и искусственных материалов производства Италии, Голландии, Польши, России, Турции, внедрение нового оборудования и новых технологий, проведение кадровой политики, направленной на привлечение наиболее грамотных специалистов и повышение профессиональной компетентности собственных сотрудников. Описание инвестиционного проекта:

«Техническое перевооружение участка по производству обуви строчечно-литьевого метода крепления ОАО «Гродненская обувная фабрика «Неман». Цель инвестиционного проекта - организация участка по производству мужской, женской и детской обуви строчечно-литьевого метода крепления. По проекту необходимо приобрести 13 единиц технологического оборудования, в том числе 1 карусельный автомат для прямого прилива двухслойной подошвы мод. D 622/18-E/LDM фирмы «Desma» Германия, которое позволит внедрить новые прогрессивные технологии в производство обуви, значительно улучшить качество и внешний вид производимой продукции, будет способствовать повышению конкурентоспособности продукции предприятия как на внутреннем, так и на внешнем рынках, получение высокой добавленной стоимости.

Проблема, которую следует решить:

На рассмотрении находятся 3 инвестиционных проекта (n=3):

«Техническое перевооружение производства ОАО «БелТАПАЗ»;

«Увеличение объема производства композиционных материалов на ПТК «Химволокно»;

«Техническое перевооружение участка по производству обуви строчечно-литьевого метода крепления ОАО «Гродненская обувная фабрика «Неман».

Общая сумма капиталовложений равна 400 млн. руб., zi(x) - прирост годовой прибыли при вложении инвестиций в объёме х млн. руб. (значения функций zi(x) приведены в таблице 3.1)

Таблица 3.1

Прирост годовой прибыли при вложении инвестиций в объёме х млн. руб.

X	0	100	200	300	400
z1(x)	0	20	34	46	53
z2(x)	0	18	29	45	62
z3(x)	0	25	41	52	74

Найти такое распределение инвестиций между предприятиями, которое максимизирует прирост на всех предприятиях.

Решение задачи.

Организация задачи на листе Excel.

Прежде всего заполняется таблица на рисунке 3.5. Для каждого x = 0, 100, …, 400 рассматриваются все возможные значения управления u2 = 0, 100, …, x, и значения F1(x-u2)=z1(x-u2) складываем со значениями z2(u2) на диагонали находится наибольшее число (выделено цветом) и указывается соответствующее значение u2*(x).

Рисунок 3.5

Затем заполняется таблица на рисунке 3.6.

Рисунок 3.6

В таблице на рисунке 3.7 заполняется только одна диагональ для значения x = 400. Наибольшее число на этой диагонали:

Третьему предприятию необходимо выделить:



Рисунок 3.7

На долю остальных двух предприятий остается 200 млн. дол.

Тогда для второго предприятия инвестиции составят:

И первому останется:

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

Оно обеспечивает наибольший возможный прирост прибыли 79 млн. руб.



ЗАКЛЮЧЕНИЕ

В работе представлены общие характеристики задач дискретного программирования, приведено общее описание процесса моделирования метода динамического программирования, решена проблема предприятия ООО «СТРОЙКРОВЛЯ», связанная с минимизацией расходов по закупке строительных материалов, а также решена проблема распределения инвестиций между предприятиями: ОАО «БелТАПАЗ», ПТК «Химволокно» и ОАО «Гродненская обувная фабрика «Неман», которое максимизирует прирост годовой прибыли на всех предприятиях.

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

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

Задача оптимальной замены оборудования;

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

При написании курсового проекта нами была изучена специальная литература, включающая в себя статьи и учебники по динамическому программированию, описаны теоретические аспекты и раскрыты ключевые понятия исследования, рассмотрено практическое применение динамического программирования в решении проблем предприятий ООО «СТРОЙКРОВЛЯ», ОАО «БелТАПАЗ», ПТК «Химволокно» и ОАО «Гродненская обувная фабрика «Неман».



СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

Беллман, Р. Динамическое программирование / Р. Беллан; под редакцией Н.Н. Воробьева - Москва: Издательство иностранной литературы, 1960. - 549 с.

Лежнев, А.В. Динамическое программирование в экономических задачах: учеб. пособие / Лежнев А.В. - Москва: Бином, 2010. - 176 с.

Динамическая задача определения оптимальной производственной программы / А.В. Мищенко, Е.В. Джамай // Менеджмент в России и за рубежом - 2009 - №4 - C.55-59.

Красс, М.С. Основы математики и ее приложения в экономическом анализе: учеб. пособие/ М.С. Красс, Б.П. Чупрынов - 3-е издание - Москва: Дело, 2002. - 500 с.

Интрилигатор, М. Математические методы оптимизации и экономическая теория / М. Интрилигатор: под ред. А.А. Конюса - Москва: Прогресс, 1975. - 600 с.

Косоруков, О.А. Исследование операций / О.А. Косоруков, А.В. Мищенко; под ред. Н.П. Тихомирова - Москва: Экзамен, 2003. - 599 с.

Алгоритмы: построение и анализ / Т. Кормен [ и др.]; под ред. Красикова И.В. -2-е изд. - Москва: Вильямс, 2005. - 1296 с.

Элементы динамического программирования в экстремальных задачах маршрутизации / А. А. Ченцов [и др.] // Проблемы управления - 2013 - №2 - C.11-18.

Локальные вставки на основе динамического программирования в задаче маршрутизации с ограничениями / А. А. Петунин [и др.] // Вестник Удмуртского ун-та. Математики. Механики. Компьютерной науки - 2014 - №1 - C. 32-39.



ЛИСТ САМООЦЕНКИ

Имя: Шашко Дарья Юрьевна

Дата: 10.12.2014

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

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

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

Оригинальность моей работы состоит в том, что объектом исследования является реальный проект, предложенный в настоящее время для г. Гродно.

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

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

Для внедрения (развития) темы следует ознакомить руководство предприятия с результатами полученными в данной курсовой работе в ходе решения проблемы предприятия ООО «СТРОЙКРОВЛЯ», связанной с оптимизацией расходов по закупке строительных материалов.

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