- •Розділ 10 імовірнісні моделі динамічного програмування
- •Задача розподілу зусиль
- •Проблема поліпшення якості продукції та дерево рішень
- •Елементарна модель управління запасами
- •10.5. Задача визначення оптимального розміру партії
- •10.6. Задача складання комерційного прогнозу
- •10.7. Стохастична модель відновлення
Елементарна модель управління запасами
Задача фірми є досить простою, тому що стан системи на будь-якому відрізку t залежить практично тільки від того, чи продовжується процес формування рішення аж до t-гo відрізка, або, іншими словами, від того, чи рекламувалися удосконалені установки для кондиціонування повітря фірмою або її конкурентами на попередніх відрізках. Перемінна стану в приведеному нижче прикладі відповідає тому, що вже розглядалося раніше у представлених детерміністичних задачах.
Цей приклад являє собою імовірнісний аналог задачі планування виробництва і управління запасами фірми.
У детерміністичному варіанті задачі фірми були прийняті наступні припущення щодо даних, що фігурують у моделі:
- попит D = 3; обсяг виробництва х ≤ 5;
- рівень запасів j на кінець відрізка (що є частиною планового періоду) задовольняє умові j ≤ 4. (1)
Сума витрат, пов’язаних з виробництвом і збереженням, дорівнює (2)
де х и j – ненегативні цілі числа, а
С(0) = 0, С(1) = 15, С(2) = 17, С(3) = 19, С(4) = 21, С(5) = 23, h = l,
для усіх відрізків (всередині планового періоду). Таким чином, параметри моделі стаціонарні у часі. Перемінною стану системи є рівень запасів на початок відрізка планового періоду; рівень запасів був позначений через i (i = 0, 1, ..., 4). Рекурентне співвідношення динамічного програмування у цьому випадку має такий вигляд:
(4)
при
(5)
причому в (4) , а мінімізація здійснюється над множиною тільки таких цілочисельних значень перемінної х, що знаходяться в інтервалі .
Припустимо тепер, що рівень попиту приймає одне з двох незалежних і рівноімовірнісних значень:
(6)
так що Е [D] = 3 для усіх відрізків планового періоду. Щоб зробити аналіз даної стохастичної моделі порівнянним з аналізом відповідної детермінованої задачі, необхідно прийняти ряд додаткових допущень. По-перше, припустимо, що наприкінці планового періоду складські запаси не приймаються до уваги й не приводять до витрат на збереження (у детерміністському випадку рівень запасів наприкінці планового періоду прийняли рівним нулю). По-друге, допустимо, що обсяг виробництва достатній для того, щоб запаси ніколи не закінчувалися (не приймали негативних значень), що приводить до наступного обмеження:
Обсяг запасів на початок відрізка +
+ Обсяг виробленої продукції ≥ 4. (7)
Оскільки найменше значення для рівня попиту дорівнює 2, а рівень запасів наприкінці відрізка не може перевищувати 4 одиниці, то повинна задовольнятися також наступна умова:
Обсяг запасів на початок відрізка +
+ Обсяг виробленої продукції ≤ 6. (8)
Найбільш важливим є та обставина, що перемінна, що характеризує стан у даній стохастичній моделі, як і раніше являє собою рівень запасів на початок відрізка. Чим це поснюється? Оскільки випадкові величини, що характеризують рівень попиту, повністю незалежні, єдиним пов’язаним з минулим показником для моменту часу, в якому до кінця планового періоду залишається п відрізків, є наявний обсяг запасів. Припускаючи, що задача полягає в мінімізації значення цільової функції, що представляє собою математичне чекання сумарних (за плановий період) витрат, можна інтерпретувати як очікувані витрати на реалізацію оптимальної стратегії при заданому значенні i для рівня запасів на початок відрізка, коли до кінця планового періоду залишається п відрізків.
У випадку коли п = 1, прості обчислення приводять до наступної формули: (9)
Для більших значень п при заданому рівні запасів i очікувані витрати при реалізації оптимальної стратегії можуть бути визначені за допомогою наступної схеми міркувань. По-перше, потрібно врахувати витрати С(х), пов’язані з виробництвом х одиниць продукції. По-друге, необхідно включити очікувані витрати на збереження продукції (за станом на кінець розглянутого відрізка, тобто в обсязі i + х – D). Нарешті, варто взяти до уваги витрати, що будуть мати місце у наступні відрізки планового періоду. Ці витрати являють собою ні що інше, як , де D характеризується розподілом імовірностей, обумовленим співвідношеннями (6). Таким чином, при п = 2, 3, ... рекурентне співвідношення динамічного програмування для розглянутої стохастичної моделі має такий вигляд:
(10)
де i = 0, 1, ..., 4, а мінімізація робиться над множиною тільки таких ненегативних цілочисельних значень х, що знаходяться в інтервалі .
Помітимо, що головна відмінність рекурентного співвідношення (4), що має місце у випадку детерміністичної моделі, від рекурентного співвідношення (10) для стохастичної задачі полягає в тому, що в останньому випадку необхідно зробити додаткові обчислення, пов’язані з кількісним визначенням. У табл. 10.1 поряд приведені оптимальні значення для обсягів виробництва для п = 1, 2, ..., 5. Можна довести, що стратегія, оптимальна для п = 3, є оптимальною також і для всіх п ≥ 3.
Таблиця 10.1
Стохастичний варіант моделі управління запасами
Рівень запасів на початок відрізку і |
n = 1 |
n = 2 |
n = 3 |
n = 4 |
n = 5 |
Необмежений плановий період |
||||||
x1(i) |
f1(i) |
x2(i) |
f2(i) |
x3(i) |
f3(i) |
x4(i) |
f4(i) |
x5(i) |
f5(i) |
x∞(i) |
||
0 |
4 |
21 |
4 |
41 |
5 |
57,5 |
5 |
72,25 |
5 |
93 |
5 |
|
1 |
3 |
19 |
5 |
34,5 |
5 |
52,25 |
5 |
70,00 |
5 |
87,43 |
5 |
|
2 |
2 |
17 |
4 |
32,5 |
4 |
50,25 |
4 |
68,00 |
4 |
85,43 |
4 |
|
3 |
1 |
15 |
3 |
30,5 |
3 |
48,25 |
3 |
66,00 |
3 |
83,43 |
3 |
|
4 |
0 |
0 |
0 |
20 |
0 |
37,75 |
0 |
54,87 |
0 |
72,62 |
0 |