- •«Системи та методи прийняття рішень»
- •Перелік практичних занять практичне заняття 1
- •Короткі теоретичні відомості
- •1 Постановка задачі прийняття рішень
- •2 Приклади задач прийняття рішень
- •3 Класифікація задач прийняття рішень
- •Розв’язування задач
- •1.3 Контрольні питання
- •2.2 Розв’язування задач
- •2.3 Контрольні питання
- •3.2 Розв’язування задач
- •Контрольні питання
- •Література: [2, 119-123; 4, 40-45]. Практичне заняття 4
- •4.1 Короткі теоретичні відомості
- •1 Розв’язання задач багатокритеріальної оптимізації
- •2 Принцип головного критерію
- •3 Функціонально-вартісний аналіз
- •4 Принцип послідовної оптимізації ( лексикографічного впорядкування)
- •4.2 Контрольні питання
- •2 Вимірювання та шкалування частинних критеріїв
- •3 Формування функції корисності частинних критеріїв
- •4 Перетворення дихотомічного якісного фактора
- •5 Перетворення багатозначного якісного фактора
- •5.2 Контрольні питання
- •2 Універсальна математична модель багатокритеріального оцінювання й оптимізації
- •3 Реалізація адитивної оцінки
- •4 Реалізація моделі послідовної оптимізації
- •5 Реалізація мінімаксної та максимінної оцінок
- •6.2 Розв’язування задач
- •6.3 Контрольні питання
- •Література: [14, 119-123; 17, 140-145].
- •7.1.2 Аналіз рішень в екстенсивній (узагальненій) формі
- •7.1.3 Аналіз рішень у нормальній формі
- •7.1.2 Критерії прийняття рішень в умовах стохастичної невизначеності
- •7.2 Розв’язування задач
- •7.3 Контрольні питання
- •8.2 Розв’язування задач
- •8.3 Контрольні питання
- •Література: [14, 119-123; 17, 140-145]. Практичне заняття 9
- •9.2 Розв’язування задач.
- •9.2 Розв'язування задач
- •9.3 Контрольні питання
- •Практичне заняття 10
- •10.2 Розв’язування задач.
- •10.1 Короткі теоретичні відомості
- •3 Критерій мінімаксного ризику Севіджа
- •10.2 Розв’язування задач
- •10.3 Контрольні питання
- •11.2 Розв’язування задач
- •11.3 Контрольні питання
- •Принцип оптимальности Беллмана
- •Задача о наборе высоты и скорости летательного аппарата.
- •Функциональное уравнение Беллмана.
- •Задача распределения ресурсов.
- •Распределение по неоднородным этапам.
- •Распределение ресурсов между тремя и более отраслями.
- •Распределение ресурсов с резервированием.
- •Распределение ресурсов «с вложением доходов в производство».
- •Учёт предыстории процесса.
- •Задача с мультипликативным критерием.
- •Література: [14, 119-123; 17, 140-145].
- •13.2 Розв’язування задач.
- •4.11. Применение метода динамического программирования для решения задачи управления запасами
- •13.3 Контрольні питання Література: [8, 119-123; 17, 140-145]. Список літератури
- •39614,М.Кременчук, вул. Першотравнева, 20
4.11. Применение метода динамического программирования для решения задачи управления запасами
Постановка задачи. Рассматривается функционирование предприятия в течение календарных этапов планирования. Каждый-й этап, характеризуется следующими параметрами:
- величина запаса, оставшаяся на предприятии после окончания предыдущего -го этапа;
- объем производства предприятия на -м этапе;
- величина спроса на продукцию предприятия на -м этапе.
Известна функция затрат , на-мэтапе функционирования предприятия. Эта функция завесит от объема производства и величины запасовкоторые должны храниться на складе в течение-го периода. Необходимо определить объем производства для каждого этапа планирования, при котором суммарные затраты, связанные с производством продукции и ее хранением, были бы минимальны, и в каждом периоде выполнялось ограничение на спрос продукции со стороны потребителей.
Критерий представляется как:
Ограничения имеют следующий вид:
удовлетворение спроса потребителей на продукцию в -м периоде
установление объема запаса в конце -го периода
.
Для решения этой задачи методом динамического программирования необходимо определить основные компоненты:
этапы - календарные периоды деятельности предприятия,;
состояния - объем запасов в конце-го периода;
управление - планируемый объем производствах на-м периоде;
локальный доход - затраты на -м этапе, связанные с хранением запасов и производством новой продукции:;
оператор перехода - устанавливает связь между объемом запасов в конце я - -го и-го этапов:.
Введем функцию
.
Тогда функциональное уравнение Беллмана имеет следующий вид:
Решение функционального уравнения Беллмана производится, начиная с первого этапа, та переменная последовательно полагается равной единице, двум, трем, ....
Рассмотрим решение уравнения Беллмана для случая, когда
где - затраты на производство продукции на-м этапе в объеме;-затраты на хранение продукции на-м этап, h - коэффициент;- начальный запас продукции;- затраты на производство начального запаса а объеме ;- затраты на хранение начального запаса в объеме.
Шаг 1. Соответствует первому этапу принятия решения, т.е. :
.
В полученном уравнении все величины являются известными. Для решения этого уравнения формируется табл. 4.27.
Алгоритм заполнения таблицы включает выполнение следующих действий:
столбцы таблицы соответствуют величине начального запаса, строки -объему производства на первом этапе . Каждая клетка таблицы делится на две части: в нижней части записываются значения состояния в конце первого этапа, т.е. значения для переменной:. В том случае, еслипринимает отрицательное значение, то такие состояния являются недопустимыми и исключаются из рассмотрения путем вычеркивания, В частности, для положительного спросаклетка дляиявляется отрицательной и недопустимой. Очевидно. что первым допустимым состоянием является значение;
в верхней части каждой из клеток записывается значение функции
Таблица 4.28 Результаты выполнения первого шага
Объем производства на первом этапе
|
Величина начального запаса | ||||
| |||||
|
|
|
... … |
|
|
|
|
|
... ... |
|
|
|
…. …. |
…. …. |
… … |
|
…. …. |
|
|
…. …. |
… … |
… … |
|
Среди допустимых клеток находятся клеши с одинаковыми значениями состояний, и о качестве оптимальной выбирается клетка, для которой принимает оптимальное значение. Такие оптимальные значения находятся для всех состояний, т.е.. Для каждого состояния фиксируется оптимальный объем производства. Результаты представляются в окончательной табл. 4.28 для первого шага: в первом столбце приводится перечень состояний, во втором — оптимальный объем производства для каждого из состояний; и третьем - оптимальные затраты на производство и хранение запаса для первого календарного периода. Максимальное значение состояния первого этапа ограничиваетсят.е.а минимальное -.
Таблица 4.28 Окончательная таблица первого шага
-
Величина запаса
Оптимальный объем производства
Оптимальная функция затрат
…
…
…
…
…
…
Шаг 2. Соответствует второму этапу принятия решений, т.е. =2. Функциональное уравнение Беллмана имеет следующий вид:
где - оптимальное значение функции затрат для предыдущего этапа;-исходные данные. Результаты выполнения второго шага представлены а табл. 4.29.
Таблица 4,29. Результаты выполнения второго шага
Объем производства на первом этапе
|
Величина начального запаса | ||||
|
|
| |||
|
|
|
... … |
|
|
|
|
|
... ... |
|
|
|
…. …. |
…. …. |
… … |
|
…. …. |
|
|
…. …. |
… … |
… … |
|
Аналогично предыдущему шагу каждая клетка разбивается на дне части, определяются клетки, соответствующие недопустимым состояниям, и они удаляются путем вычеркивания. Для допустимых клеток вычисляются значения состояний , которые записываются в нижней части каждой из клеток. В верхней части клетки указывается значение функции затрат:. Затем находятся одинаковые состояния, и для них вычисляется условно оптимальное значение функции затрат. Таким образом, после окончания второго этапа для каждого из допустимых состоянийдолжна быть определена функция затрат, а также значение объема производстваи запаса. Эти результаты представляються в окончательной таблице для второго этапа в табл. 4.30.
Таблица 4.30.
Величина запаса |
Оптимальный объем производства |
Оптимальная функция затрат |
…
…
|
…
…
|
…
…
|
Аналогичные действия выполняются для всех этапов, пока .
Пример. Методом динамического программирования определять оптимальный план производства предприятия для следующих исходных данных: количество интервалов планирования ; величина спроса на продукцию постоянна для всех этапов планирования:; затраты на производство и хранение продукции; затраты на формирование начального запаса; ограничение на производственные мощности; ограничение на предельный уровень запасок.
Шаг 1. Решение уравнения Беллмана производится в соответствии с алгоритмом прямой прогонки:
Для выполнения шага 1 формируется промежуточная табл. 4.3. Клетки таблицы, соответствующие недопустимым состоянием, отмечаются символом * . В качестве примера приведено вычисление ряда функций :
На основе промежуточном табл. 4.31 формируется окончательная табл. 4.32 для шага 1
Таблица 4.31 промежуточная таблица для шага 1
-
Объем производства
*
*
*
*
40
*
*
*
49
59
*
*
46
56
66
*
43
53
63
73
40
50
60
70
80
47
57
67
77
*
54
64
74
*
*
Таблица 4.32 Окончательная таблица для шага 1
-
Объем запаса
Объем производства
Функция затрат
Шаг 2. Рассматривается второй интервал функционирования предприятия, - 2. Уравнение Беллмана будет иметь вид:
Для решения уравнения формируются промежуточная и окончательная (табл. 4.33 и табл. 4.34.)
Таблица 4.33. Промежуточная тавблица для шага 2
-
Объем производства
*
*
*
*
78
*
*
*
86
97
*
*
82
93
104
*
81
99
100
111
80
88
96
107
118
87
95
103
114
*
94
102
110
*
*
Таблица 4.34. Окончательная таблица для шага 3
Объем запаса |
Объем производства |
Функция затрат |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Д
Л
Для нахождения оптимальных объемов производства и оптимальных уровней запаса, производиться решение задачи в обратном порядке: