Реферат на тему:
Дослідження операцій. Задачі та моделі заміни. Динамічне програмування
План :
Загальна характеристика задач заміни.
Принцип оптимальності.
Метод функціональних рівнянь.
Динамічні моделі управління запасами. Однопродуктова динамічна модель.
Динамічна модель заміни обладнання..
КЛЮЧОВІ ПОНЯТТЯ ТА ТЕРМІНИ
динамічне програмування
адитивність
оптимальна стратегія
керований процес
мультипликативність
проблема розмірності
декомпозиція процесу
критерій якості
вектор стану процесу
стан процесу
функціональні рівняння
траєкторія руху системи
принцип оптимальності
однопродуктова динамічна
модель
змінні стану
післядія
рекурентні співвідношення
керовані змінні
1. Загальна характеристика задач заміни.
В задачах лінійного та нелінійного програмування розглядаються статичні
процеси, і оптимальний розв’язок знаходиться лише на один етап
планування, одномоментно. Такі задачі називаються однокроковими.
В задачах динамічного програмування процес залежить від часу, і тому
розв’язування зводиться до багатоетапного або багатостадійного процесу
прийняття рішень.
Розв’язання задач динамічного програмування дозволяє виробити оптимальну
стратегію дій, в той час як статичні задачі дозволяють отримати
розв’язок, оптимальний з точки зору умов, що склалися, тобто тактичний.
Однак ця межа не є чітко визначеного, тому що широкі класи динамічних
задач в принципі можна звести до однокрокових, але цей факт має скоріше
теоретичний інтерес, тому що розв’язати такі зведені задачі внаслідок
надзвичайно великого зростання розмірності просто неможливо. З іншого
боку, деякі статичні задачі можна представити у вигляді багатокрокових і
розв’язувати методом динамічного програмування.
Таким чином, динамічне програмування (ДП) є математичним апаратом, що
дозволяє здійснити оптимальне планування багагокрокових керованих
процесів та процесів, які залежать від часу.
Процес називається керованим, якщо наявна можливість виливу на перебіг
його розвитку.
Керуванням називатимемо сукупність розв’язків, що приймаються на кожному
з етапів з метою впливу на хід процесу.
Випуск продукції підприємством – це керований процес, що визначається
змінами попиту ринку, складу обладнання, величиною попереднього
прибутку, тенденціями розвитку, відсотком коштів, що спрямовуються у
виробництво та наукову діяльність і ін. Сукупність рішень, що
приймаються на початку кожного з відрізків певного періоду (тижнів
місяця, місяців року та ін.) з питань забезпечення сировиною,
обладнанням, розмірами фінансування, є керуванням. Планування на місяць
здійснюється з врахуванням того, що на кінець року повинні бути
досягнуті певні цілі.
Багатоетапні керовані процеси мають наступні спільні риси:
1. Процес може бути підданий декомпозиції, тобто розбитий на складові
елементи – кроки або етапи. Якщо процес розглядається в часі, то
природним є розбиття за періодами часу. Виробничі процеси можуть бути
розбиті за стадіями відповідно до їх технологічних особливостей, ресурси
можуть бути розподілені між споживачами і т. ін.
2. Кожний етап характеризується станом, який визначається значеннями
факторів, або змінних, кількість яких для кожного з етапів може бути
різною.
3. З загального числа змінних виділяються керовані, тобто ті, значення
яких можна спрямовано змінювати і цими змінами впливати на стан процесу,
та змінні стану.
4. На кожному кроці існує залежність між керованими змінними, змінними
стану та функцією мети, яка представляється за допомогою рівняння,
системи рівнянь або таблично. За допомогою динамічного програмування для
кожного кроку встановлюються такі значення керованих змінних, які
забезпечують екстремальне значення функції мети для процесу загалом.
5. Критерій оптимальності повинен бути адитивним (або
мультипликативним), тобто значення функції мети для всього керованого
процесу повинно складатися з елементарних значень цієї функції,
отриманих для кожного окремого етапу.
Таким чином, за допомогою методу динамічного програмування здійснюється
оптимізація багатоетапних процесів, виходячи з інтересів системи
загалом, а не кожної її стадії як окремого елементу, тому розв’язок на
кожному кроці повинен відповідати вимогам оптимізації процесу загалам.
В загальному вигляді постановка задачі динамічного програмування
формулюється наступним чином.
Нехай деяка фізично керована система S знаходиться в початковому стані
s0 . Під дією керування иі на кожному і -му кроці вона переходить через
послідовність проміжних станів в остаточний стан sn :
S0 S1 S2
Sn-1 Sn
…
u1 u2 u3
un
Рис. 1. Траєкторія руху динамічної системи
При відомому керуванні на і -му кроці стан sі ,- визначається як
(1)
Критерій якості
(2)
,
то загальний виграш (значення функції мети для процесу загалом), згідно
з вимогою адитивності, становитиме:
.
(3)
Принцип оптимальності.
Виникає природне запитання: яким чином потрібно діяти, щоб при побудові
стратегії врахувати на кожному кроці вимоги процесу загалом і які вимоги
висуваються до постановки задачі багатокрокового керування? Задача для
того, щоб можна було для її розв’язування застосувати метод динамічного
програмування, повинна відповідати двом наступним вимогам:
функція мети повинна бути адитивною (мультипликативною);
в процесі руху системи повинна бути відсутня післядія: стан sі , в який
перейшла система, залежить лише від значення попереднього стану sі-1 та
від управління uі і не залежить від того, яким шляхом система потрапила
в стан sі-1 .
.
Метод динамічного програмування ґрунтується на принципі оптимальності Р.
Белмана, що визначає порядок покрокового розв’язування задачі, яка може
бути піддана декомпозиції, за допомогою рекурентних обчислювальних
процедур.
Принцип оптимальності формулюється наступним чином .
Оптимальне керування має наступну основоположну властивість: яким не
були би початковий стан та прийняте початкове рішення, наступні рішення
повинні утворювати оптимальне керування відносно стану, що виник в
результаті попереднього рішення.
, і = 1,2,…, n-1 .
Таким чином, динамічне програмування є поетапним плануванням
багатокрокового процесу з оптимізацією на один крок , яке враховує на
кожному кроці розвиток процесу загалом, тобто при прийнятті рішення
враховується майбутнє. Безпосередньо це зробити неможливо, і власне
принцип оптимальності дає нам можливість це зробити. В кожному процесі є
останній, п -й крок, прийняття рішення на якому не залежить від
майбутнього. Здійснивши планування цього кроку, до нього можна приєднати
(n – 1) -й крок, до яких в свою чергу ( п – 2 ) -й, приходячи таким
чином до початкового стану s0 . Процес динамічного програмування
розгортається з кінця до початку – від останнього стану до початкового.
Для того ж, щоб спланувати п -й крок, необхідно знати стан системи на (n
-1) -му кроці. Якщо стан системи на (п -1) -му кроці невідомий (а так є
завжди), то, виходячи з характеристик процесу, роблять припущення про
можливі стани системи на цьому кроці. Для кожного припущення визначаємо
оптимальне керування на останньому, п -му кроці. Таке оптимальне
керування називається умовно-оптимальним (за умови певного значення
стану на попередньому кроці). Аналогічно діємо на (n – 2) -му кроці, але
умовно-оптимальні керування обираємо, враховуючи вже обрані
умовно-оптимальні керування на (n -1) -й крок.
Для першого кроку (на відміну від інших) припущень про можливий стан
системи не робимо – стан s0 відомий, і знаходимо оптимальне керування з
врахуванням всіх умовно-оптимальних керувань, знайдених для другого
кроку. І, нарешті, проходячи від s0 до s в прямому напрямку виконання
процесу, отримуємо оптимальне керування для процесу загалом. У
динамічному програмуванні існує проблема розмірності (або прокляття
розмірності за словами Р.Белмана), суть якої полягає в наступному.
змінних, які утворюють вектор стану. Збільшення кількості змінних
викликає зростання числа можливих варіантів розв’язування, асоційованих
з кожним з етапів.
Це особливо помітно при проведенні обчислень з використанням таблиць.
Оскільки при розв’язуванні задач динамічного програмування зазвичай
використовуються відповідні комп’ютерні програми, зростання кількості
змінних стану не лише збільшує час обчислень, але й може викликати
переповнення пам’яті комп’ютера.
Якщо ж говорити про складність задачі, то вона належить до класу NP
-повних задач, оскільки її складність експоненційно залежить від
складності задачі, S = аеn , де n розмірність задачі. З іншого боку,
кількість варіантів є значно меншою, ніж у випадку повного перебору.
Метод функціональних рівнянь.
При застосуванні методу функціональних рівнянь знаходження оптимального
розв’язку (стратегії) багатокрокового процесу отримується шляхом
розв’язування функціональних рівнянь.
Проілюструємо основні ідеї методу функціональних рівнянь на прикладі
простого багатоетопного процесу розподілу.
ph
&
&
B
j
”
3/4
TH
??
–
@
B
h
j
’
”
1/4
3/4
Ue
TH
”
$
V
X
v
x
|
„
I
?
$
X
x
z
|
~
?
??
??
??
????
??
???засобів, то для 2-го залишиться (х0 – у0 ) засобів.
При цьому будуть отримані відповідні доходи g (yQ ) та h (х0 – у0) .
Необхідно розподілити засоби х (тобто обрати величину у) таким чином,
щоб максимізувати загальний дохід від вкладення х одиниць засобів, тобто
. (4)
. Тоді максимальне значення Q існує завжди та визначає максимальне
значення доходу в одноетапному процесі.
Розглянемо двохетапний процес.
. Аналогічно для отримання доходу h (х – у) кількість первісних засобів
(х0 -у0 ) зменшиться до значення b (x0 – y0) , тобто
.
Таким чином, після завершення 1 -го етапу залишок засобів становитиме
. (5)
Повторимо процес розподілу сумарного залишку на другому кроці:
.
(6)
При цьому дохід на другому кроці становитиме g (у1 ) + h (х1- у1) .
Таким чином повний дохід за два кроки становитиме
,
, (7)
.
Розповсюджуючи отримані результати на N кроків, отримаємо:
, (8)
.
Співставивши з загальною постановкою задачі, отримаємо:
Рис. 2. Співставлення розподільчої задачі з загальною задачею
динамічного програмування
,
. (9)
Застосуємо принцип оптимальності Белмана дая розв’язування цієї задачі.
На N-му кроці розподілу підлягає значення:
,
(10)
визначається зі співвідношення (оскільки немає майбутнього !!!)
. (11)
За два останні етапи найбільший прибуток визначиться, як:
,
, (12)
,
звідки
. (13)
Таким чином, оптимальний сумарний прибуток з і -го по N -й крок
визначиться, як:
, (14)
або
(15)
Динамічні моделі управління запасами. Однопродуктова динамічна модель.
В цій моделі припускається, що хоча й попит достовірно відомий, він може
змінюватися від етапу до етапу. Рівень запасу контролюється періодично.
Хоч запізнення поставки (відображене в фіксованому числі періодів)
припустиме, в моделі вважається, що збільшення запасу проходить миттєво
на початку етапу. Нарешті, дефіцит не припускається.
Побудова динамічної детермінованої моделі зводиться до дослідження
скінченого проміжку часу. Це пояснюється тим, що для отримання
чисельного розв’язку відповідних задач потрібно використовувати метод
динамічного програмування, який в цьому випадку можна практично
застосовувати на кінцевому етапі (кроці). Однак це не є важливою
перешкодою, так як попит в майбутньому суттєво не впливає на рішення,
прийняті для скінченого проміжку часу, що розглядається. Крім цього,
зазвичай, не має сенсу припускати, що продукція буде зберігатися в
вигляді запасу безмежно довго.
Визначимо для етапу і , і = 1,2,,,., N , наступні величини:
Zi — кількість замовленої продукції (розмір замовлення);
— потреба в продукції (попит);
Хi – початковий запас (на момент початку етапу і );
hi – витрати на зберігання одиниці запасу, що надходить з етапу і в
етап і+1;
Кі – витрати на оформлення замовлення;
сі – (Zі) – функція граничних витрат, пов’язаних з купівлею
(виробництвом) при заданому значенні Zi .
Нехай
(16)
Функція ci(Zi) нас цікавить лише тоді, коли витрати на купівлю одиниці
продукції змінюються з часом або існують розриви ціни.
Так як дефіцит не допускається, то потрібно знайти оптимальне значення
Zi , мінімізувавши загальні витрати на оформлення замовлень, купівлі і
зберігання на всіх N етапах. Витрати на зберігання вважаються
пропорційними величині
.
(17)
.
Побудова моделі динамічного програмування спрощується, коли представити
задачу схематично, як показано на рис. 1. Кожний етап відповідає одному
кроку. Використовуючи зворотнє рекурентне рівняння, визначимо стан
системи на кроці і як об’єм вихідного запасу хі .
Z1 Z2
Zi Zi+1 ZN
X1 X2
Xi Xi+1 XN XN+1=0
…………..
……….
Рис. 3. Схематичне зображення динамічної моделі управління запасами
Нехай fi(хi) – мінімальні витрати на етапах і , і +1,…, N .
Рекурентне рівняння має вигляд:
,
(18)
,
Пряме рекурентне рівняння можна отримати, визначивши стан на кроці і як
об’єм запасу на кінець етапу i . На рис. 3. ці стани задані величинами
xi+1 . На будь-якому кроці на величини xi+1 накладені наступні
обмеження:
. (19)
Таким чином, в найгіршому випадку об’єм замовленої продукції Zi на етапі
і може бути настільки великий, що запас xi+1 задовольняє попит на всіх
наступних етапах.
– мінімальні загальні витрати па етапах 1, 2,,.., і при заданій
величині запасу xi+1 на кінець етапу i . Тоді рекурентне рівняння буде
мати вигляд:
,
, (20)
Пряма і зворотня постановки задачі з обчислювальної точки зору
еквівалентні. Але прямий алгоритм (алгоритм прямого проходження)
ефективніший при аналізі важливого часткового випадку розглянутої вище
моделі. У наведеному прикладі для ілюстрації обчислюваної процедури
використовується прямий алгоритм.
Модель відновлення при нескінченній кількості кроків.
У моделях цього типу система функціонує не протягом скінченого числа
дискретних періодів, а протягом такого відрізку часу, що прямує до
нескінченості.
У цих задачах момент відновлення настає у той момент часу, коли система
переходить у початковий стан. Тут керуючими змінними є послідовні
інтервали між моментами заміни.
Розглянемо загальну модель задачі відновлення.
5.Динамічна модель заміни обладнання.
Скінченний плановий період.
, де N– кількість відрізків часу між сусідніми моментами відновлення.
інтегральні дисконтні затрати (ІДЗ) для оптимальної стратегії
відновлення, при якій один з альтернативних варіантів має бути обраний
за n відрізків до кінця планового періоду.
,
і ми приходимо до наступного рекурентного співвідношення:
(21)
Нескінченний плановий період
, приходимо до співвідношення
.
Це функціональне рівняння має однозначний розв’язок виду:
.
Література
Карлин С. Математические методы в теории игр, программировании и
экономике. -М.: Мир, 1964.
Вентцель Е.С. Введение в исследование операций. Сов. радио, 1964.
Пономаренко О.І., Пономаренко В.О. Системні методи в економіці, бізнесі
й менеджменті. -К.: Либідь, 1995.
Пономаренко О.І., Перестюк М.О., Бурим В.М. Основи математичної
економіки. -К.: Інформтехніка, 1995.
Горелик В.А., Ушаков М.А. Исследование операций. -М.: Машиностроение,
1986.
PAGE
PAGE 13
Нашли опечатку? Выделите и нажмите CTRL+Enter
