Динамічне програмування

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

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

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

В основі обчислювальних алгоритмів динамічного програмування знаходиться наступний принцип оптимальності, сформульований Р. Белманом: яким би не був стан системи S в результаті і-1 кроків, управління на і-му кроці повинно обиратися так, щоб воно в сукупності з управлінням на всіх наступних кроках з (і+1)-го до N-го включно доставляло екстремум функції цілі.

Виробничі задачі, що вирішуються методом динамічного програмування.

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

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

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

Розподілити 100 млн. грош. од. кредиту між підприємствами об'єднання для забезпечення максимального приросту випуску продукції. Необхідні числові данні для чотирьох підприємств об`єднання наведені в таблиці.

F4(X3.U4)= Z4(X3.U4)

4- підприємство

F3(X2.U3)= Z3(X2.U3)+F4(X3)

3- підприємство

F2(X1.U2)=Z2(X1.U2)+F3(X2)

2- підприємство

F1(X0.U1)=Z1(X0.U1)+F2(X1)

1- підприємство

Отже, інвестиції в розмірі 100 необхідно розподілити таким чином:

1-му підприємству виділити - 0;

2-му підприємству виділити - 0;

3-му підприємству виділити - 40;

4-му підприємству виділити - 60.

Що забезпечить максимальний дохід, що дорівнює 77 млн. грош. од.

2. Задача про заміну обладнання

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

2023 - рік

2022 - рік

2021 - рік

2020 - рік

2019 - рік

2018 - рік

2017 - рік

2016 - рік

2015 - рік

2014 - рік

Теорії масового обслуговування

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

Метою теорії масового обслуговування є розробка математичних методів, за допомогою яких можна оцінити ефективність функціонування систем масового обслуговування, тобто їх якість при різних варіантах організації. До основних понять теорії масового обслуговування належать такі: система масового обслуговування (СМО), обслуговуюча система (система обслуговування), вимога на обслуговування, джерело вимог, система, що обслуговується, обслуговування, обслуговуючі апарати (канали), вхідний та вихідний потоки вимог, процеси обслуговування, час обслуговування, дисципліна та якість обслуговування. Розглянемо стисло зміст цих понять і наведемо необхідну термінологію.

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

Задачі теорії масового обслуговування

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

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

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

Цілі повністю збігаються або близько відповідають одна одній. Така відповідн...