Застосування основ теорії ігор та статистичних рішень і теорії масового обслуговування для вибору і обґрунтування управлінських рішень в умовах невизначено

Зміст

Вступ.

І. Елементи теорії статистичних рішень

1.1 Гра з природою

1.2 Критерії вибору рішення в умовах невизначеності

1.3 Критерій Гурвіца

1.4 Критерій Вальда

1.5 Вибір оптимального рішення

ІІ. Основи теорії масового обслуговування.

2.1 Класифікація систем масового обслуговування .

2.2 Основні характеристики СМО

2.3 Чиста СМО з відмовами

2.4 Багатоканальна СМО з відмовами

2.5 Розрахунок параметрів СМО

Висновки та рекомендації

Використана література

Вступ

Мета курсового проекту — застосування теоретичних та практичних знань основ теорії ігор та статистичних рішень і теорії масового обслуговування (ТМО) для вибору і обґрунтування управлінських рішень в умовах невизначеності.

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

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

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

Завдання

Умова. Ведеться будівництво автозаправочної станції. Залежно від прийнятого рішення — кількості запланованих колонок на станції х_{і {1,2,3,5}, та кількості колонок Пj {0,1,3,5,7}, що можуть задовольнити потреби клієнтів і залежать від випадкових факторів, які невідомі керівництву АЗС, складено таблицю щомісячних доходів. Витрати на будівництво однієї колонки та закупку пального складають В=30 тис.у.о. Максимальний дохід, що приносить одна колонка за місяць — Д=40тис.у.о. У разі перевищення попиту над пропозицією керівництво АЗС може підвищити ціну на пальне на 10%.Потік автомобілів, що надходить на заправку, є пуассонівський найпростіший. Середній інтервал прибуття автомобілів на АЗС складає =5 хв, середня тривалість обслуговування — експоненціальна, складає =4 хв.}

Потрібно:

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

2. Змоделювавши АЗС як СМО певного типу, розрахувати параметри та характеристики якості функціонування n-канальної системи, де кількість каналів n визначають за відповідним критерієм вибору рішення.

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

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

І. Елементи теорії статистичних рішень

1.1 Гра з природою

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

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

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

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

Елементи задачі гри з природою Постановка задачі:

гравець, А має m стратегій А₁, А₂, …, А_m;

умови проведення гри характеризуються станами П₁, П₂, …, П_n які називають стратегії природи (можливе позначення S — стратегії середовища);

виграш гравця, А при кожній парі стратегій (А_i, П_j), i=1,…, m; j=1,…, n позначають аij і задають матрицею виграшів (аij):

Задача: вибрати стратегію гравця А, що має перевагу над іншими стратегіями.

Побудова матриці виграшів:

Елемент матриці розраховуємо, як різницю між середнім доходом і затратами на обслуговування: a_ij=Д-В ??це прибуток, який одержує керівництво АЗС. Крім того враховуючи, що при перевиконанні попиту над пропозицією ціну керівництво АЗС може підвищити ціну на пальне на 10%, тобто використовуємо формулу aij=Д*1.1-В, що сприятиме збільшенню доходу Д.

Таблиця1

Матриця виграшів

a11=0*40−1*30=-30

a21=0*40−2*30=-60

a31=0*40−3*30=-90

a41=0*40−5*30=-150

a12=1*40−1*30=10

a22=1*40−2*30=-20

a32=1*40−3*30=-50

a42=1*40−5*30=-110

a13=1*40*1.1−1*30=14

a23=2*40*1.1−2*30=28

a33=3*40−3*30=30

a43=3*40−5*30=-30

a14=1*40*1.1−1*30=14

a24=2*40*1.1−2*30=28

a34=3*40*1.1−3*30=42

a44=5*40−5*30=50

a15=1*40*1.1−1*30=14

a25=2*40*1.1−2*30=28

a35=3*40*1.1−3*30=42

a45=5*40*1.1−5*30=70

1.2 Критерії вибору рішення в умовах невизначеності

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

Існує ряд критеріїв для вибору оптимальної стратегії .

1.3 Критерій Гурвіца

Критерій Гурвіца передбачає більш урівноважений вибір між позиціями крайнього оптимізму і крайнього песимізму. Вирішальне правило має вид:

H=max [б min + (1 — б) max ], (1.3.1)

i j j

де б — коефіцієнт довіри; 0 ? б ? 1;

[б max + (1 — б) min ]- елемент матриці Гурвіца. (1.3.2)

j j

Матрицю виграшів доповнюють стовпчиком значень елементів матриці Гурвіца — це сума середньозважених найбільшого і найменшого результатів для кожного рядка. Вибирають стратегію, у рядку якої стоїть найбільший елемент матриці Гурвіца.

Коефіцієнт довіри а характеризує стан природи. Природа знаходиться у найсприятливішому стані з імовірністю а, у найбільш несприятливому стані — з імовірністю (1-а). При а = 0 критерій Гурвіца перетворюється у критерій Вальда, а при а = 1 — у критерій здорового оптиміста (або азартного гравця), який вірить в удачу.

Можна користуватися іншою модифікацією критерію Гурвіца:

H=max [г min + (1 — г) max ], (1.3.3)

i j j

де г — коефіцієнт песимізму; 0 ? г ? 1;

Матрицю виграшів доповнюють стовпчиком значень елементів матриці Гурвіца — це сума середньозважених найменшого і найбільшого результатів для кожного рядка.

Вибирають стратегію, у рядку якої стоїть найбільший елемент матриці Гурвіца.

[ г min + (1 — л) max ]- елемент матриці Гурвіца (1.3.4)

j j

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

Ваговий коефіцієнт а (чи у) має важливе значення. В технічних задачах правильно вибрати цей коефіцієнт важко. Тому найчастіше значення а = 0,5 (чи у = 0,5) приймають без заперечень за деяку «середню» точку зору.

Критерій Гурвіца застосовують за таких обставин:

— нічого не відомо про можливість появи станів природи;

— доводиться рахуватися з появою різних станів природи;

— рішення реалізують лише декілька разів;

— допускається певний ризик.

а = 0.9

H1a=0.9*14+0.1*(-30)=12.6−3=9.6

H2a=0.9*28+0.1*(-60)=25.2−6=19.2

H3a=0.9*42+0.1*(-90)=37.8−9=28.8

H4a=0.9*70+0.1*(-150)=63−15=48

Таблиця 2

Матриця Гурвіца

Для зручності аналізу зведемо результати розрахунків до підсумкової таблиці.

1.4 Критерій Вальда

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

Оптимальна стратегія буде та, що гарантує виграш не менший, ніж «нижня ціна» гри з природою (це нагадує елементи теорії ігор). Вирішальне правило має вид:

W= max min a_{ij. (1.4.1)}

i j

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

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

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

нічого не відомо про можливість появи станів природи;

доводиться рахуватися з появою різних станів природи;

рішення реалізують лише один раз;

необхідно виключити будь-який ризик.

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

Таблиця 3

Критерій Вальда

За одержаними результатами можна надати такі рекомендації дирекції АЗС: при песимістичному підході до справи треба задіяти 1 заправку, тобто застосувати стратегію X₁ за критерієм Вальда.

1.5 Вибір оптимального рішення за моделлю гри з природою

Таблиця 4

За одержаними результатами можна надати такі рекомендації дирекції АЗС: при песимістичному підході до справи треба будувати стратегію А₁ за критерієм Вальда. Максимальні збитки можуть бути 30тис. у. о. Проте Гурвіц рекомендує стратегію А_4. При мінімальному ризику виграш буде становити 48 тис. у. о.

ІІ. Основи теорії масового обслуговування

2.1 Класифікація систем масового обслуговування

Відрізняють два основних види СМО: з відмовами та з чергою чекання.

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

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

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

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

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

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

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

В залежності від умов формування вхідного та вихідного потоків СМО діляться також на:

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

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

2.2 Основні характеристики СМО

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

При аналізі СМО з відмовами визначають і інші величини:

середнє число зайнятих каналів;

середній час простою системи в цілому і кожного окремого каналу.

Системи з очікуванням поділяють на системи з необмеженим очікуванням і системи з обмеженнями.

Наведемо показники ефективності СМО з очікуванням.

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

середнє число заявок у системі (в черзі та на обслуговуванні);

середнє число заявок у черзі;

середній час перебування заявки в системі;

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

Значний інтерес представляють імовірнісні характеристики. Для СМО з обмеженнями потрібно визначати як абсолютну та відносну пропускну здатність, так і характеристики очікування.

Для аналізу та оцінки процесів, що відбуваються в СМО, потрібно знати основні параметри системи:

n — число каналів;

— інтенсивність потоку заявок;

— продуктивність каналу (інтенсивність потоку звільнень);

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

2.3 Чиста СМО з відмовами Одноканальна СМО з відмовами

Система складається з одного каналу (п=1). До неї надходить пуассонівський потік заявок з інтенсивністю. Заявка, що застала канал зайнятий, одержує відмову і залишає систему. Обслуговування заявки продовжується протягом часу Т_{обс, розподіленого за експоненціальним законом з параметром :}

(2.3.1)

тобто потік обслуговувань — найпростіший, з інтенсивністю .

Єдиний канал обслуговування можна розглядати як фізичну систему S, яка може перебувати в одному з двох станів:

S_{0— канал вільний;}

S_{1— канал зайнятий.}

Розмічений граф станів системи представлено на рис. 1. Із стану S_{0 в стан S1 систему переводить потік заявок інтенсивністю, а з стану S1 в стан S0 — потік обслуговувань з інтенсивністю .}

Рис.1 Розмічений граф станів одноканальної СМО з відмовами

Відповідні імовірності станів і. Для будь-якого моменту t

p₀(t)+p₁(t)=1. (2.3.2)

Для одноканальної СМО з відмовами гранична імовірність p₀ визначає відповідну здатність q: p₀ — це імовірність того, що в момент часу t канал вільний, і заявка, що надійшла, буде обслугована; а значить, середнє відношення числа обслугованих заявок до числа заявок, що надійшли, також дорівнює p₀.

Формули розрахунку параметрів та показників якості функціонування СМО наведено в табл. 8. Слід визначити, що пропускна здатність каналу обслуговування визначається як величина, обернена до «чистого» часу обслуговування. Але на практиці канал деякий час буває вільний і обслуговування заявки не відбувається, тобто середній час обслуговування більше ніж «чистий», а значить, абсолютна пропускна здатність системи завжди менша за пропускну здатність каналу обслуговування.

2.4 Багатоканальна СМО з відмовами

Кількість каналів обслуговування n. Пронумеруємо стани системи за числом зайнятих каналів, або за числом заявок, пов’язаних з системою:

S₀ — усі канали вільні;

S₁ — зайнято один канал, решта вільні;

S₂ — зайнято два канали, решта вільні;

…

S_k — зайнято k каналів, решта вільні;

…

S_п — зайнято усі п каналів.

Розмічений граф станів системи представлено на рис. 2. Зліва направо систему переводить один і той же потік заявок інтенсивністю .. Якщо система перебуває у стані S_{k — зайнято каналів, і надійшла заявка, то система переходить у стан Sk+1 .}

Рис. 2 Розмічений граф станів багатоканальної СМО з відмовами

Справа наліво систему переводить потік звільнень з інтенсивністю ., помноженою на число зайнятих каналів. Нехай зайнято один канал, що відповідає стану S₁. Коли закінчиться обслуговування заявки у цьому каналі, система перейде до стану S₀, а потік обслуговувань, що переводить систему із стану S₁ у стан S₀, матиме інтенсивність.. Якщо обслуговуванням зайнято два канали, а не один, то потік обслуговувань, що переводить систему із S₂ у стан S₁, матиме вдвічі більшу інтенсивність 2. Якщо обслуговуванням зайнято k каналів, то інтенсивність потоку обслуговування буде k, і т.д.

Формули для розрахунку показників якості наведено в таблиці 5.

Таблиця 5

Одноканальна СМО з відмовами

Таблиця 6

Багатоканальна СМО з відмовами

2.5 Розрахунок параметрів СМО

Розрахуємо багатоканальну СМО з відмовами.

Визначимо вихідні умови для аналізу системи масового обслуговування з n каналами.

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

На вхід системи надходить найпростіший потік заявок з інтенсивністю

(авт/хв. або 12 авт/год)

Параметр обслуговування

(авт/хв. або 15 авт/год)

Приведена щільність заявок:

Z = / =0,2/0,25=0,8

За формулами Ерланга розраховуємо імовірності станів системи:

(2.5.1)

(2.5.2)

Імовірність відмови:

(2.5.3)

Відносна пропускна здатність (імовірнiсть обслуговування):

(2.5.4)

тобто 99% заявок буде обслуговано.

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

(2.5.5)

(авт/хв. або 12 авт/год)

Середнє число зайнятих каналів:

(2.5.6)

Тобто в усталеному режимі роботи заправки в середньому буде зайнятий один канал із п’яти, а інші будуть простоювати.

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

(2.5.7)

хв.

Рис.3 Розмічений граф станів багатоканальної СМО з відмовами

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

Імовірнiсть стану S₀ (імовірність обслуговування):

(2.5.8)

Імовірнiсть відмови (імовірнiсть стану S₁):

(2.5.9)

тобто 44% заявок, що надійшли, одержать відмову.

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

q = p0 (2.5.10)

q = 0,56

тобто в усталеному режимі АЗС обслуговуватиме 56% заявок.

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

(2.5.11)

тобто АЗС може здійснити в середньому 0,13 заправки автомобілів за хвилину.

Середній час обслуговування (з урахуванням можливого вільного стану системи):

(2.5.12)

Середній час перебування у системі:

(2.5.13)

Рис.4 Розмічений граф станів одно канальної СМО з відмовами

Звожу отримані результати до таблиці.

Таблиця 7

Характеристики функціонування АЗС як СМО при різних стратегіях керівництва

Висновки та пропозиції

З отриманих результатів можна зробити такі висновки: при використанні багатоканальної системи масового обслуговування імовірність відмови становитиме 0,0012%, а при застосуванні одноканальної СМО аж 44%. Коли на АЗС буде збудовано 5 колонок, то вона зможе обслуговувати 99,88% заявок, а коли ж буде лише одна колонка 56% заявок. При застосуванні багатоканальної СМО з відмовами АЗС буде здатна обслуговувати 12 автомобілів за годину, а при одноканальній СМО — 6,6 автомобілів за годину. Коли на АЗС будуть збудовані 5 колонок, то в середньому буде зайнята лише 1 колонка, а 4 інших будуть простоювати. І, нарешті, середній час перебування автомобілів на АЗС при застосуванні багатоканальної СМО складає 5 хвилини, а при одно канальній — 9,1 хвилин. Звісно, що такі умови будуть вигідними для водіїв і цілком їх влаштовуватимуть, адже, коли буде 5 колонок, їм не треба буде чекати в черзі, щоб заправити свій автомобіль, тому що, як видно з розрахунків, час скорочується майже вдвічі порівняно з тим, якщо буде одна колонка. Для керівництва АЗС, безперечно, побудувати 5 колонок коштуватиме більше, ніж одну. До того ж той факт, що 4 з них будуть простоювати, не надає оптимізму. Але, якщо АЗС буде дотримуватись показників, що розраховані в цій курсовій, то все буде гаразд. А це значить потрібно будувати АЗС з 5 колонками.

Використана література

1. Вентцель Е. С. Исследование операций.— М.: Советское радио, 1972.— 552 с.

2. Вентцель Е. С. Теория вероятностей. Гос. изд-во физ.-мат. лит.— М. 1962.—564 с.

3. Зайченко Ю. П. Исследование операций. Учеб. пособие для студентов вузов.— К.: ВШ, 1979.— 392 с.

4. Крушевский А. В. Теория игр.—К.: ВШ, 1977.—216 с.

5. Кудрявцев Е. М. Исследование операций в задачах, алгоритмах и программах.— М: Радио и связь, 1984.— 184 с.

6.Э. Мушак, П. Мюллер. Методы принятия технических решений. М.: Мир, 1990.—208 с.

7. Четверухін Б.М., Бакуліч О.О., Радкевич С. Д. Дослідження операцій в транспортних системах. Частина 2. Системи масового обслуговування. Навчальний посібник.— К.: НТУ, 2001.— 141 с.

8. Шарапов О. Д. та ін. Системний аналіз.— К.: ВШ, 1992. — 304 с.

9. Ігрові методи прийняття рішень. Методичні вказівки до вивчення дисципліни «Введення в дослідження операцій у транспортних системах» / Укл. Кунда Н. Т.— К.: НТУ, 2005.— 36с.

10. Лабораторний практикум-І з дисципліни «Введення в дослідження операцій у транспортних системах» /Укл. Кунда Н. Т. УГУ, 2000.— 52с.