Лабораторна робота № 1

Тема: Прийняття рішень в аналізі та аудиті на основі моделей динамічного програмування

1. Призначення і ціль лабораторної роботи

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

Ціль роботи: Набуття навиків поділу процесу управління на частини і зображення його у вигляді динамічної послідовності та інтерпретації у вигляді покрокової програми, розгорнутої у часі, з використанням табличного процесора Excel 2000.

2. Загальні поняття

Динамічне програмування є математичним апаратом, що підходить для розв’язання деякого класу задач шляхом їх поділу на частини, невеликі і менш складні задачі. При цьому відмінною особливістю є розв’язання задач за етапами, через фіксовані інтервали, проміжки часу, що і визначило появу терміну “динамічне програмування”.

Розв’язання задач методами динамічного програмування базується на сформульованому Р.Е. Белманом принципі оптимальності: “Оптимальна поведінка має ту властивість, що яким би не був початковий стан системи і початкове розв’язання, наступне розв’язання повинно визначати оптимальну поведінку відносно стану, одержаного в результаті початкового розв’язання”.

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

Отже, динамічне програмування є оптимальним управлінням процесом за допомогою зміни керованих параметрів на кожному кроці і змінюючи таким чином стан системи.

Важливою економічною проблемою є своєчасне оновлення устаткування, котре належить до основних засобів підприємства. Старіння устаткування включає фізичний і моральний знос, внаслідок чого зростають витрати на ремонт і обслуговування, зменшується продуктивність праці і ліквідаційна вартість. Задача заключається у визначенні оптимальних термінів заміни старого устаткування. Критерієм оптимальності є прибуток від експлуатації устаткування (задача максимізації) або сумарні витрати на експлуатацію протягом планового періоду (задача мінімізації).

Допустимо, що планується експлуатація устаткування протягом деякого періоду часу тривалістю n років. Устаткування має тенденцію з плином часу старіти і приносити все менший прибуток r(t) (t – вік устаткування). При цьому є можливість на початку будь-якого року продати застаріле устаткування за ціною s(t), яка також залежить від віку t, і купити нове устаткування за ціною P. Під віком устаткування розуміється період експлуатації устаткування після останньої заміни, визначений в роках. Необхідно знайти оптимальний план заміни устаткування з тим, щоб сумарний прибуток за всі n років бум би максимальним, враховуючи, що до початку експлуатації вік устаткування становив t₀ років.

Вхідними даними в задачі є дохід r(t) від експлуатації протягом одного року устаткування віком t років, залишкова вартість s(t), ціна нового устаткування P та початковий вік устаткування t₀.

t	0	1	…	n
r	r(0)	r(1)	…	r(n)
s	s(0)	s(1)	…	s(n)

При складанні динамічної моделі вибору оптимальної стратегії оновлення устаткування заміна розглядається як n-крокова, тобто період експлуатації розбивається на n кроків.

Виберемо за крок оптимізацію плану заміни устаткування з k-го до n-го року.

Очевидно, що прибуток від експлуатації устаткування за ці роки буде залежати від віку устаткування до початку розглядуваного кроку, тобто з k-го кроку.

Оскільки оптимізація здійснюється з останнього кроку (k = n), то на k-му кроці невідомо, в які роки з першого до (k-1)-го повинна здійснюватися заміна і відповідно невідомий вік устаткування до початку k-го року. Вік устаткування, котрий визначає стан системи, позначимо через t. На величину t накладається таке обмеження:

1 < = t <= t₀ + k – 1 (1)

Вираз (1) свідчить про те, що t не може перевищувати віку устаткування за (k-1) рік його експлуатації з врахуванням віку до початку першого року, що становить t₀ років, і не може бути меншим за одиницю (цей вік устаткування буде мати до початку k-го року, якщо його замінено на початку попереднього (k-1) року).

Отже, змінна t в даній задачі є змінною стану системи на k-му кроці.

Змінною управління на k-му кроці є логічна змінна, яка може приймати одне з двох значень: зберегти (с) або замінити (з) устаткування на початку k-го року:

с , якщо устаткування зберігається;

F_k(t) = (1)

з, якщо устаткування замінюється

Функцію Белмана F_k(t) визначають як максимально можливий дохід від експлуатації устаткування за роки з k-го до n-го, якщо до початку k-го вік устаткування становив t років. Застосовуючи те чи інше управління, система переходить в новий стан. Так, наприклад, якщо на початку k-го року устаткування зберігається, то до початку (k+1)-го року його вік збільшиться на одиницю (стан системи стане t+1), у разі заміни старого устаткування нове досягне до початку (k+1)-го року віку t₁ = 1 рік.

На цій основі можна записати рівняння, яке дозволяє рекурентно обчислити функції Белмана, опираючись на результати попереднього кроку. Для кожного варіанта управління дохід визначається як сума двох складових – безпосереднього результату управління і його наслідків.

Якщо на початку кожного року зберігається устаткування, вік якого t років, то дохід за цей рік становитиме r(t). До початку (k+1)-го року вік устаткування сягне (t+1) і максимально можливий дохід за роки, що залишилися (з (k+1)-го до n-го), становитиме F_k+1(t+1). Якщо на початок k-го року прийняте рішення про заміну устаткування, то продається старе устат­кування віком t років за ціною s(t), купується нове за P одиниць, а експлуатація його протягом k-го року нового устаткування принесе прибуток r(0). До початку наступного року вік устаткування становитиме 1 рік і за всі решту роки з (k+1)-го до N-го максимально можливий дохід буде F_k+1(1). З двох можливих варіантів управління вибирається той, котрий приносить максимальний дохід. Отже, рівняння Белмана на кожному кроці управління матиме вигляд

r(t) + F_k+1(t+1), (с)

F_k(t) = max (2)

s(t) – P + r(0) + F_k+1(1), (з)

Функція F_k(t) розраховується на кожному кроці управління для всіх 1 < = t <= t₀ + k – 1. Управління, за якого досягається максимум прибутку, є оптимальним.

Для першого кроку умовної оптимізації при k = n функція прибутку за останній n-й рік:

r (t), (с)

F_n(t) = max (3)

s(t) – P + r(0), (з)

Значення функції F_n(t), визначені F_n-1(t), F_n-2(t) аж до F₁(t), F₁(t₀), є можливими прибут­ками за всі роки. Максимум прибутку досягається за деякого управління, застосовуючи яке на першому році, ми визначаємо вік устаткування до початку другого року. Для даного віку устат­кування вибирається управління, за якого досягається максимум прибутку за роки з другого до n-го тощо. У результаті на етапі безумовної оптимізації визначаються роки, на початку яких слід замінити устаткування.