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

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

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

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

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

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

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

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

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

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

Приріст випуску продукції на і-м підприємстві zi(ui)	Кошти, що надаються ui, млн. грош. од.
	20	40	60	80	100
z1(ui)	9	18	29	41	60
z2(ui)	8	19	30	47	58
z3(ui)	12	25	51	58	69
z4(ui)		15	52	59	60

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

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

X3	U4	Z4	U4
0	0	0	0
20	20	7	7
40	40	15	15
60	60	52	52
80	80	59	59
100	100	60	60

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

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

X2	U 3	X3 = X 2 - U 3	Z3	F 4	F 3 +F4	F 3
0	0	0	0	0	0	0
20	0	20	0	7	7	-
	20	0	12	0	12	12
40	0	40	0	15	15	-
	20	20	12	7	19	-
	40	0	25	0	25	25
60	0	60	0	52	52	52
	20	40	12	15	27	-
	40	20	25	7	32	-
	60	0	51	0	51	-
80	0	80	0	59	59	-
	20	60	12	52	64	64
	40	40	25	15	40	-
	60	20	51	7	58	-
	80	0	58	0	58	-
100	0	100	0	60	60	-
	20	80	12	59	71	-
	40	60	25	52	77	77
	60	40	51	15	66	-
	80	20	58	7	65	-
	100	0	68	0	69	-

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

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



X1	U 2	X2 = X1 - U 2	Z2	F 3	F 2 +F3	F 2
0	0	0	0	0	0	0
20	0	20	0	12	12	12
	20	0	8	0	8	-
40	0	40	0	25	25	25
	20	20	8	12	20	-
	40	0	19	0	19	-
60	0	60	0	52	52	52
	20	40	8	25	33	-
	40	20	19	12	31	-
	60	0	30	0	30	-
80	0	80	0	64	64	64
	20	60	8	52	60	-
	40	40	19	25	44	-
	60	20	30	12	42	-
	80	0	47	0	47	-
100	0	100	0	77	77	77
	20	80	8	64	72	-
	40	60	19	52	71	-
	60	40	30	25	55	-
	80	20	47	12	59	-
	100	0	58	0	58	-

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

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

X0	U 1	X1 = X0 - U 1	Z1	F 2	F 1 +F2	F 1
20	0	20	0	12	12	12
	20	0	9	0	9	-
40	0	40	0	25	25	25
	20	20	9	12	21	-
	40	0	18	0	18	-
60	0	60	0	52	52	52
	20	40	9	25	34	-
	40	20	18	12	30	-
	60	0	29	0	29	-
80	0	80	0	64	64	64
	20	60	9	52	61	-
	40	40	18	25	43	-
	60	20	29	12	41	-
	80	0	41	0	41	-
100	0	100	0	77	77	77
	20	80	9	64	73	-
	40	60	18	52	70	-
	60	40	29	25	54	-
	80	20	41	12	53	-
	100	0	60	0	60	-

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

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

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

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

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

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

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

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



2023 - рік

X9	U 10	Xn10	Z10	F 10
1	зберігання	1	8	8
	заміна	0	3	-
2	зберігання	2	7	7
	заміна	0	3	-
3	зберігання	3	6	6
	заміна	0	3	-
4	зберігання	4	5	5
	заміна	0	3	-
5	зберігання	5	4	4
	заміна	0	3	-
6	зберігання	6	2	-
	заміна	0	3	3
7	зберігання	7	2	-
	заміна	0	3	3
8	зберігання	8	1	-
	заміна	0	3	3

2022 - рік

X8	U 9	Xn9	Z9	X9	F 10	Z9 + F 10	F 9
1	зберігання	1	8	2	7	15	15
	заміна	0	3	1	8	11	-
2	зберігання	2	7	3	6	13	13
	заміна	0	3	1	8	11	-
3	зберігання	3	6	4	5	11	11
	заміна	0	3	1	8	11	-
4	зберігання	4	5	5	4	9	-
	заміна	0	3	1	8	11	11
5	зберігання	5	4	6	3	7	-
	заміна	0	3	1	8	11	11
6	зберігання	6	2	7	3	5	-
	заміна	0	3	1	8	11	11
7	зберігання	7	2	8	3	5	-
	заміна	0	3	1	8	11	11
8	зберігання	8	1	-	-	-	-
	заміна	0	3	1	8	11	11

2021 - рік

X7	U 8	Xn8	Z8	X8	F 9	Z8 + F 9	F 8
1	зберігання	1	8	2	13	21	21
	заміна	0	3	1	15	18	-
2	зберігання	2	7	3	11	18	18
	заміна	0	3	1	15	18	-
3	зберігання	3	6	4	11	17	-
	заміна	0	3	1	15	18	18
4	зберігання	4	5	5	11	16	-
	заміна	0	3	1	15	18	18
5	зберігання	5	4	6	11	13	-
	заміна	0	3	1	15	18	18
6	зберігання	6	2	7	11	13	-
	заміна	0	3	1	15	18	18
7	зберігання	7	2	8	11	12	-
	заміна	0	3	1	15	18	18
8	зберігання	8	1	-	-	-	-
	заміна	0	3	1	15	18	18

2020 - рік

X6	U 7	Xn7	Z7	X7	F 8	Z7 + F 8	F 7
1	зберігання	1	8	2	18	26	26
	заміна	0	3	1	21	24	-
2	зберігання	2	7	3	18	25	25
	заміна	0	3	1	21	24	-
3	зберігання	3	6	4	18	24	24
	заміна	0	3	1	21	24	-
4	зберігання	4	5	5	18	23	-
	заміна	0	3	1	21	24	24
5	зберігання	5	4	6	18	22	-
	заміна	0	3	1	21	24	24
6	зберігання	6	2	7	18	20	-
	заміна	0	3	1	21	24	24
7	зберігання	7	2	8	18	20	-
	заміна	0	3	1	21	24	24
8	зберігання	8	1	-	-	-	-
	заміна	0	3	1	21	24	24

2019 - рік

X5	U 6	Xn6	Z6	X6	F 7	Z6 + F 7	F 6
1	зберігання	1	8	2	25	33	33
	заміна	0	3	1	26	29	-
2	зберігання	2	7	3	24	31	31
	заміна	0	3	1	26	29	-
3	зберігання	3	6	4	24	30	30
	заміна	0	3	1	26	29	-
4	зберігання	4	5	5	24	29	29
	заміна	0	3	1	26	29	-
5	зберігання	5	4	6	24	28	-
	заміна	0	3	1	26	29	29
6	зберігання	6	2	7	24	26	-
	заміна	0	3	1	26	29	29
7	зберігання	7	2	8	24	26	-
	заміна	0	3	1	26	29	29
8	зберігання	8	1	-	-	-	-
	заміна	0	3	1	26	29	29



2018 - рік

X4	U 5	Xn5	Z5	X5	F 6	Z5 + F 6	F 5
1	зберігання	1	8	2	31	39	39
	заміна	0	3	1	33	36	-
2	зберігання	2	7	3	30	37	37
	заміна	0	3	1	33	36	-
3	зберігання	3	6	4	29	35	-
	заміна	0	3	1	33	36	36
4	зберігання	4	5	5	29	34	-
	заміна	0	3	1	33	36	36
5	зберігання	5	4	6	29	33	-
	заміна	0	3	1	33	36	36
6	зберігання	6	2	7	29	31	-
	заміна	0	3	1	33	36	36
7	зберігання	7	2	8	29	31	-
	заміна	0	3	1	33	36	36
8	зберігання	8	1	-	-	-	-
	заміна	0	3	1	33	36	36

2017 - рік

X3	U 4	Xn4	Z4	X4	F 5	Z4 + F 5	F 4
1	зберігання	1	8	2	37	45	45
	заміна	0	3	1	39	42	-
2	зберігання	2	7	3	36	43	43
	заміна	0	3	1	39	42	-
3	зберігання	3	6	4	36	42	42
	заміна	0	3	1	39	42	-
4	зберігання	4	5	5	36	41	-
	заміна	0	3	1	39	42	42
5	зберігання	5	4	6	36	40	-
	заміна	0	3	1	39	42	42
6	зберігання	6	2	7	36	38	-
	заміна	0	3	1	39	42	42
7	зберігання	7	2	8	36	38	-
	заміна	0	3	1	39	42	42
8	зберігання	8	1	-	-	-	-
	заміна	0	3	1	39	42	42

2016 - рік

X2	U 3	Xn3	Z3	X3	F 4	Z3 + F 4	F 3
1	зберігання	1	8	2	43	51	51
	заміна	0	3	1	45	48	-
2	зберігання	2	7	3	42	49	49
	заміна	0	3	1	45	48	-
3	зберігання	3	6	4	42	48	48
	заміна	0	3	1	45	48	-
4	зберігання	4	5	5	42	47	-
	заміна	0	3	1	45	48	48
5	зберігання	5	4	6	42	46	-
	заміна	0	3	1	45	48	48
6	зберігання	6	2	7	42	44	-
	заміна	0	3	1	45	48	48
7	зберігання	7	2	8	42	44	-
	заміна	0	3	1	45	48	48
8	зберігання	8	1	-	-	-	-
	заміна	0	3	1	45	48	48

2015 - рік

X1	U 2	Xn2	Z2	X2	F 3	Z2 + F 3	F 2
1	зберігання	1	8	2	49	57	57
	заміна	0	3	1	51	54	-
2	зберігання	2	7	3	48	55	55
	заміна	0	3	1	51	54	-
3	зберігання	3	6	4	48	54	54
	заміна	0	3	1	51	54	-
4	зберігання	4	5	5	48	53	-
	заміна	0	3	1	51	54	54
5	зберігання	5	4	6	48	52	-
	заміна	0	3	1	51	54	54
6	зберігання	6	2	7	48	50	-
	заміна	0	3	1	51	54	54
7	зберігання	7	2	8	48	50	-
	заміна	0	3	1	51	54	54
8	зберігання	8	1	-	-	-	-
	заміна	0	3	1	51	54	54

2014 - рік

X0	U 1	Xn1	Z1	X1	F 2	Z1 + F 2	F 1
0	зберігання	0	10	1	57	67	67
	-	-	-	-	-	-	-
1	зберігання	1	8	2	55	63	63
	заміна	0	3	1	57	60	-
2	зберігання	2	7	3	54	61	61
	заміна	0	3	1	57	60	-
3	зберігання	3	6	4	54	60	60
	заміна	0	3	1	57	60	-
4	зберігання	4	5	5	54	59	-
	заміна	0	3	1	57	60	60
5	зберігання	5	4	6	54	58	-
	заміна	0	3	1	57	60	60
6	зберігання	6	2	7	54	56	-
	заміна	0	3	1	57	60	60
7	зберігання	7	2	8	54	56	-
	заміна	0	3	1	57	60	60
8	зберігання	8	1	-	-	-	-
	заміна	0	3	1	57	60	60



X0	2014р	2015р	2016р	2017р	2018р	2019р	2020р	2021р	2022р	2023р
0	67
1	63	57	51	45	39	33	26	21	15	8
2	61	55	49	43	37	31	25	18	13	7
3	60	54	48	42	36	30	24	18	11	6
4	60	54	48	42	36	29	24	18	11	5
5	60	54	48	42	36	29	24	18	11	4
6	60	54	48	42	36	29	24	18	11	3
7	60	54	48	42	36	29	24	18	11	3
8	60	54	48	42	36	29	24	18	11	3

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

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

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

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

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

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

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

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

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

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

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

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

Задачі про СМО

а) Магазин отримує овочі і зелень. В середньому прибуває з товаром 3 автомашини в день. Підсобні приміщення і обладнання для підготовки овочів до продажу дозволяють обробити і зберігати товар не більше, ніж з 2 автомашин одночасно. В магазині працюють 5 груп фасувальників, кожна з яких може оброблювати товар з одної автомашини в середньому за 0.5дня.

- Визначити ймовірність обслуговування автомашини ;

- Визначити показники інтенсивності роботи СМО

m=5,

л=3

n=3,

tобс=0,5/дня

Інтенсивність потоку обслуговуванні:

Інтенсивність навантаження.

с = л * tобс = 2 * 0.5 = 1

Ймовірність, що канал вільний

Отже, 37.5% напротязі години канал будет незайнятим, час простою рівна tпр = 22.5 мин.

Ймовірність того що обслуговується:

зайнятий 1 канал:

p1 = с1/1! p0 = 11/1! * 0.375 = 0.375

зайнятий 2 канала:

p2 = с2/2! p0 = 12/2! * 0.375 = 0.188

зайнятий 3 канала:



p3 = с3/3! p0 = 13/3! * 0.375 = 0.0625

Ймовірність відмови

Значить, 6% із числа отриманих заявок не приймаються для обслуговування.

Ймовірність обслуговування поступаючих заявок

В системах з відмовами вимоги відмов і обслуговування складає повну групу подій, тому:

pобс = 1

Відносна пропускна здатність:

Q = pобс.

pобс = 1 - pотк = 1 - 0.0625 = 0.938

Отже, 94% із числа поступивших заявок будуть обслуговуванні. Прийнятний рівень обслуговування має бути вище 90%.

Середнє число каналів, зайнятих обслуговуванням

nз = с * pобс = 1 * 0.938 = 0.938.

Середнє число простоюючи каналів.

nпр = n - nз = 3 - 0.938 = 2.1 канала.

Коефіцієнт зайнятості каналів обслуговуванням.



Отже, система на 30% зайнята обслуговуванням.

Абсолютна пропускна здатність

A = pобс * л = 0.938 * 2 = 1.875 заявок/хв.

Середій час очікування в системі.

tпр = pотк * tобс = 0.0625 * 0.5 = 0.0312 хв.

Середнє число обслуговуванх заявок.

Тобс = с * Q = 1 * 0.938 = 0.938 ед.

Середній час перебування заявки в СМО

Число заявок, отримавши відмову напротязі часу: л * p1 = 0.125 заявок в хв. Номінальная продуктивність СМО: 3 / 0.5 = 6 заявок в хв. Фактична продуктивність СМО: 1.875 / 6 = 31% від номінальної продуктивності.

б) Міні - маркет з одним контролером - касиром обслуговує покупців, вхідний потік яких розподілений за законом Пуассона з параметром 20 покупців/год. Час обслуговування розподілений за показниковим законом з параметром 25 покупців/год. Визначити: ймовірність простою контролера - касира, середню довжину черги, середнє число покупців в міні - маркеті, середній час очікування обслуговування, середній час перебування покупців в міні - маркеті. Дати оцінку роботи міні - маркету і визначити всі характеристики СМО.

n=1;

л=20 покупців/годину;

tобс=25 покупця/годину

л=20 покупців/годину = =0,3

Середня кількість обслуговуваних покупців:

с= л· tобс=0,3·25=7,5>1

Середня кількість вимог, що в системі:

Nс===3покупці

Середня кількість вимог, що знаходиться в черзі:

Nоч==

Час перебування в черзі

tоч==7 хвилин

математичний планування розподілення обслуговування

Час перебування в системі

tс===10 хвилин.

Размещено на Allbest.ru