Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Перш ніж сформулювати задачі про потік на мережі, наведемо деякі означення. Орієнтованим графом називається впорядкована пара , де – непорожня множина вершин, – множина впорядкованих пар, що називаються дугами. При цьому вершина i дуги називається її початком, а j – її кінцем. Неорієнтованим графом називається впорядкована пара , де – множина вершин, а – множина невпорядкованих пар, що називаються ребрами. Ребра зображуються лініями, що з'єднують відповідні вершини. Геометрично граф зображується точками (множина вершин I) та лініями зі стрілками (множина дуг U), що з'єднують деякі пари цих точок. На рис. 1.1 зображено граф, для якого Граф g називається скiнченним, якщо скiнченними є множини I та U. Шляхом на графі g називається послідовність дуг (), початок кожної з яких, починаючи з другої, співпадає з кінцем попередньої, тобто , . Зрозуміло, що шлях, який з'єднує вершини та можна задати послідовністю вершин, через які він проходить. На рис. 1.1 послідовність дуг (1,2), (2,4), (4,5) формує шлях, що з'єднує вершини 1 та 5. Цей же шлях можна задати послідовністю вершин (1,2,4,5). Ланцюгом на графі g називається послідовність ребер (), в якій у кожного ребра, починаючи з другого, одна з вершин співпадає з однією з вершин попереднього, а друга – з якою-небудь вершиною наступного ребра. На рис. 1.1 ребра [1,3], [3,4], [4,5] утворюють ланцюг, який можна задати i послідовністю вершин [1,3,4,5]. Якщо початкова вершина шляху (ланцюга) співпадає з кінцевою, то маємо контур (цикл). Мережею називається граф, елементам якого поставлені у відповідність деякі параметри. Елементами графа вважаються його вершини, дуги, або більш складні конструкції, утворені з вказаних елементарних. Побудуємо мережу таким чином:
1) кожній вершині поставимо у відповідність число , що називається її інтенсивністю. Вершина i називається джерелом, якщо , стоком, якщо , i нейтральною, якщо ;
2) кожній дузі поставимо у відповідність числа та , що називаються, відповідно, функцією пропускної спроможності та функцією вартості.
На практиці величини часто інтерпретуються як об'єми виробництва () або споживання () деякого однорідного продукту в пункті (вершині) i. Величина визначає пропускну спроможність дуги (комунікації) (i,j), а величина , наприклад, собівартість транспортних перевезень по дузі (i,j). Потоком (однорідним) в одержаній мережі називається сукупність величи , (i,j)U, що задовольняють умовам:
(1.1)
. (1.2)
Співвідношення (1.1) називаються рівняннями збереження, або рівняннями неперервності. Фізично вони означають, що різниця між величиною потоку, що виходить з вершини i та величиною потоку, що входить до неї, дорівнює її
інтенсивності (рис. 1.2). Нехай . Множина U(V) дуг (i,j) таких, що iV, jV, називається розрізом мережі, тобто U(V) = {(i,j) U: iV, jV}.
Величина називається пропускною спроможністю розрізу U(V).
Загальні умови існування потоку на мережі встановлюються такою теоремою, яку ми приводимо без доведення.
Теорема 1.1. Для того, щоб на мережі існував потік, необхідно i достатньо, щоб i для довільної множини виконувалась умова , де . Іншими словами, потік на мережі існує тоді i лише тоді, коли сумарна інтенсивність всіх вершин мережі дорівнює нулю, а сумарна інтенсивність будь-якої підмножини вершин не перевищує пропускної спроможності розрізу мережі, що породжується цією підмножиною.
Приклад: Перевірити чи допускає мережа (рис. 1.3) потік.
Розв’язування. Визначаємо розріз, який формується вершиною (це множина всіх дуг, які виходять з вершини : ): , – умова теореми не виконується, отже мережа не допускає потік. Кожному потоку поставимо у відповідність цільову функцію . Лінійна задача на мережі (або задача про оптимальний потік на мережі) полягає у пошуку допустимого потоку x на мережі, що мiнiмiзує цільову функцію L(x), тобто
(1.3)
Допустимий потік x називається оптимальним, якщо він доставляє мінімальне значення функції L(x).
Очевидно, що задача про оптимальний потік на мережі є частинним випадком ЗЛП i, отже, може бути розв'язана загальними методами лінійного програмування. Зрозуміло, що специфіка цієї задачі може суттєво використовуватися при розробці частинних, більш ефективних методів її розв'язування.
Легко бачити, що з врахуванням введеного вище означення мережі можемо дати іншу інтерпретацію транспортної задачі. Дійсно нехай пункти виробництва (відправлення) є джерелами з інтенсивностями , а пункти споживання (призначення) є стоками з інтенсивностями . Тоді величини є обмеженнями пропускних здатностей комунікацій (рис. 1.4).
Граф, що визначатиме відповідну мережу побудуємо так, щоб кожен пункт відправлення був з’єднаний з кожним пунктом призначення відповідною дугою (див. рис. 1.3). Визначивши на цьому графі функції вартості , в результаті отримаємо деяку задачу на мережі. Отже, розглянута раніше транспортна задача з обмеженими пропускними здатностями комунікацій (ТЗО) є частковим випадком лінійної задачі на мережі.
Розглянемо мережу, що визначається графом g, з означеною на U функцією вартості . Розглянемо також дві фіксовані вершини , графа g та довільний шлях, що з'єднує та (1.4) де .
Розглянемо функцію , (1.5)
яка інтерпретується або як собівартість перевезення вантажу по шляху l, або як довжина шляху l. В останньому випадку – довжина дуги (i,j)U.
Задача про найкоротший шлях (про вибір найбільш економного шляху) полягає в пошуку шляху (1.4), що мiнiмiзує цільову функцію (1.5). Шуканий шлях називається найкоротшим (оптимальним).
З формальної точки зору сформульована задача є частинним випадком задачі про оптимальний потік. Для цього розглядається мережа, вершина якої є джерелом одиничної інтенсивності, вершина – стоком одиничної інтенсивності, решта вершин – нейтральні. Дугам приписуються необмежені пропускні спроможності, а собівартість перевезення по дузі дорівнює її довжині. Для потоку у побудованій мережі
Задача зводиться до знаходження потоку, що мiнiмiзує цільову функцію .
Легко зрозуміти, що для оптимального потоку величини будуть рівними 1 або 0 в залежності від того, входить чи ні дуга (i,j) до найкоротшого шляху. Тому дорівнює довжині найкоротшого шляху, що з'єднує вершини та .
Для розв'язання задачі про найкоротший шлях розроблені методи, що враховують її специфіку. Одним з них є метод Мiнтi (метод позначок). Згідно цього методу процес розв'язування задачі складається із скiнченного числа елементарних кроків, на кожному з яких позначаються вершини мережі та виділяються деякі її дуги.
4. Алгоритм методу Мiнтi.
Крок 1. Позначається вершина (коренева вершина) позначкою , – множина позначених вершин. Нехай після виконання r кроків є множина позначених вершин , кожній з яких поставлена у відповідність позначка .
Крок (r+1). Розглянемо множину непозначених вершин : , , , . Для кожної з таких дуг знаходимо суму ,
виділяємо ті дуги, для яких ця сума мінімальна. При цьому з декількох дуг, що підлягають виділенню i закінчуються в одній i тій же вершині, виділяється лише одна (рис. 1.5).
Позначаємо кінці виділених дуг числом, що дорівнює мінімальному значенню . За рахунок позначених вершин множина розширюється до множини .
Вказаний процес продовжується до тих пір, поки серед позначених не з'явиться вершина , або подальше позначення неможливе. За побудовою в кожній з позначених вершин (крім кореневої) закінчується одна виділена дуга. Тому рух від вершини вздовж виділених дуг у напрямку, протилежному їх орієнтації, реалізується однозначно. Крім того, початок виділеної дуги позначається раніше її кінця. Отже, послідовність виділених дуг, утворена в процесі руху від вершини , утворює деякий шлях з початком в та кінцем в .
Теорема 1.2. Побудований методом Мiнтi шлях є найкоротшим, що з'єднує вершини та , причому .
Зауваження.
1. Сформульований вище алгоритм методу Мiнтi розрахований на знаходження єдиного найкоротшого шляху, що з'єднує вершини та . Щоб знайти всю множину найкоротших шляхів, на кожному кроці слід виділяти всі дуги з мінімальним показником , навіть якщо декілька з них закінчуються в одній i тій же вершині. А при зворотному русі з вершини вздовж виділених дуг у кожній з вершин слід розглядати всі можливі продовження.
2. Насправді метод Мiнтi розв'язує більш загальну задачу: він знаходить найкоротший шлях з кореневої в кожну з позначених вершин.
3. Якщо процес позначення вершин методом Мiнтi продовжувати до тих пір, поки не припиниться розширення множини позначених вершин, то буде розв'язана задача знаходження найкоротшого шляху з початкової вершини у кожну позначену. Якщо при цьому деяка вершина мережі не попала до числа позначених, то немає шляху з в .
Ця задача, як i задача про найкоротший шлях, є частинним випадком задачі про оптимальний потік. Із задачею про максимальний потік тісно пов'язана задача про мінімальний розріз мережі. Наведемо формулювання цих задач.
Розглянемо мережу, що визначається графом g, яка має єдине джерело s, єдиний стік t та означену на множині U функцію пропускної спроможності . Нехай інтенсивність джерела . За теоремою існування потоку на мережі інтенсивність стоку має бути рівною . Допустимий потік для розглядуваної мережі визначається співвідношеннями: (1.8)
Задача про максимальний потік полягає у знаходженні максимального значення інтенсивності d, при якому в розглядуваній мережі існує потік. Потік , що відповідає максимальному значенню інтенсивності, називається максимальним потоком, а – величиною цього потоку.
Розглянемо описану вище мережу. Розрізом мережі, що відокремлює s від t, називається множина дуг , де C – деяка множина вершин () мережі, така, що . Нагадаємо, що пропускна спроможність цього розрізу визначається звичайним чином: .
Зрозуміло, що для кожної конкретної мережі вибір множини C повністю визначає пропускну спроможність розрізу. Розріз, що має найменшу пропускну спроможність, називається мінімальним. Задача пошуку такого розрізу називається задачею про мінімальний розріз.
Виявляється, що сформульовані задачі є двоїстими i, як слід чекати, їх розв'язки тісно пов'язані між собою.
Теорема 1.3. (Форда-Фалкерсона). Величина максимального потоку із s в t дорівнює пропускній спроможності мінімального розрізу, що відокремлює s від t.
Наслідок. Якщо дуга (i,j) входить до мінімального розрізу, то величина максимального потоку по цій дузі дорівнює її пропускній спроможності . При цьому кажуть, що потік насичує дугу.
Для розв'язування задачі про максимальний потік Фордом та Фалкерсоном був розроблений метод, що носить їх ім'я.
Згідно теореми про максимальний потік та мінімальний розріз за відомим максимальним потоком легко побудувати мінімальний розріз (див. співвідношення (1.9)). Крім того, якщо потік не є максимальним, то можливе його збільшення шляхом зміни потоку вздовж певного ланцюга. Ці факти лежать в основі методу Форда-Фалкерсона, що являє собою рекурентну процедуру, на кожному кроці якої позначаються вершини або будується потік більшої величини. Алгоритм Форда-Фалкерсона розпочинає роботу з будь-якого допустимого потоку (зокрема нульового) величини . Згідно (1.9) для цього потоку визначається множина . Якщо , то потік є максимальним, в іншому випадку можна знайти та новий потік величини . Для нового потоку цей цикл операцій повторюється i т. д. Процеси визначення та об'єднуються в один процес “розставлення позначок” вершин. Позначка (i) довільної вершини i складається з двох чисел та . Ці числа означають, що вздовж деякого ланцюга, останнім ребром якого є , можна додатково доставити одиниць потоку з вершини s до вершини i. Дамо детальний виклад алгоритму, вважаючи, що відомий допустимий потік x (зокрема нульовий).
Алгоритм методу Форда-Фалкерсона.
Крок 1 (процес розставлення позначок). На цьому кроці кожна з вершин належить до одного з трьох типів: – непозначена, – позначена i непроглянута – позначена i проглянута. Спочатку всі вершини непозначені. Позначимо вершину s позначкою , що означає: можна послати потік з вершини s у саму себе необмеженої величини. Тепер вершина s позначена i непроглянута. Взагалі, нехай j – позначена i непроглянута вершина, або – її позначка. Розглядаємо ще непозначені вершини k: i . Кожній з таких вершин приписуємо позначку , де . Розглядаємо ще непозначені вершини k: i . Кожна з таких вершин одержує позначку , де . Всі вершини k, які одержали позначки, тепер позначені i непроглянутi, а вершина j – позначена i проглянута. Продовжуємо приписувати позначки непозначеним вершинам до тих пір, поки або вершина t виявиться позначеною, або не можна буде позначити жодної вершини i вершина t виявиться непозначеною. У другому випадку існуючий потік x – максимальний, а множина позначених вершин визначає мінімальний розріз мережі. У першому випадку існуючий потік x на кроці 2 можна збільшити. Крок 2 (збільшення потоку). Нехай або – позначка вершини t. Це означає, що існуючий потік з s в t можна збільшити на величину . Для цього в першому випадку замінюємо на , у другому – замінюємо на . Переходимо до вершини k i виконуємо аналогічні операції, змінюючи величину потоку на ту ж величину . Продовжуємо ці дії, поки не досягнемо вершини s. Після цього ліквідовуємо позначки всіх вершин i переходимо до кроку 1.
Приклад. Знайти максимальний потік з вершини 1 у вершину 7 на мережі, зображеній на рис. 1.8. Процес розв’язування задачі продовжено на рис. 1.9-11.
Відповідь: , .
Під час будівництва різноманітних споруд, виготовлення технічних виробів, підготовки і проведення наукових і практичних експериментів доводиться виконувати велику кількість робіт. Виконання їх пов'язане в часі: розпочати одні роботи (за винятком початкової) можна лише тоді, коли виконано одну або кілька інших, підготовчих до них робіт. Інформацію про взаємозв'язок і порядок виконання всіх робіт якогось проекту найчастіше подають за допомогою орієнтованого графа, який доповнюють певними числовими даними, такими, наприклад, як кількість часу, потрібного для завершення конкретних робіт, час початку певної роботи, номери вершин графа тощо. Такий орграф називають сітковим графом (скорочено СГ) даного проекту. На СГ дугами зображають процеси виконання робіт, або просто роботи, а вершинами – відповідні події, які настають в результаті виконання однієї або кількох робіт. Під роботою розуміють будь-який процес, дію, за допомогою якої досягають певних результатів. Наприклад, при спорудженні будинку можна назвати такі види робіт: 1) виготовлення проекту, 2) одержання дозволу на будівництво, 3) доставка потрібних будівельних матеріалів тощо.
Подіями називають результати виконання однієї або кількох робіт. Перелічені вище роботи приводять до таких подій: 1) проект виготовлено, 2) дозвіл на будівництво будинку одержано, 3) потрібні будівельні матеріали доставлено, тощо. В СГ виділяють дві вершини: V1, яка є початком, і Vn, що є завершенням усього проекту, всі інші вершини називають проміжними. Не існує єдиного загального методу, користуючись яким можна побудувати сітковий графік для реалізації будь-якого проекту. Сітковий графік подає розгорнуту картину всього процесу реалізації конкретного проекту з його індивідуальними деталями і особливостями, які потрібно вміти виявляти і враховувати. Тому до складання СГ залучають досвідчених інженерів, економістів та інших спеціалістів. Щоб можна було однозначно розуміти усі СГ і застосовувати до них математичні методи дослідження, СГ повинні мати загальну структуру незалежно від конкретного змісту, будуватися за загальними правилами.
Найважливіші правила побудови СГ:
1.Скласти список робіт, які потрібно виконати для реалізації проекту (такі списки можуть бути або деталізованими або укрупненими).
2.Відповідно до списку робіт скласти список подій.
3.Якщо подія, яка є завершенням операцій D1, D2, ...,Dn, дає можливість розпочати операції Q1, Q2, ..., Qm, то на СГ це зображається так, як показано на рис. 2.1.
4.Якщо операція D3 йде за операціями D1 і D2, а D4 йде лише за D2, причому завершення операцій D1 і Dz дає подію Р, то вводять додаткову подію Р і фіктивну операцію D (рис. 2.2). Роботу називають фіктивною .якщо її виконання не вимагає затрати часу. У нашому випадку робота D полягає в тому, що за допомогою додаткової події Р' відображають той факт, що D4 не залежить від D1 a D3 залежить від D1 і D2.
Рис. 2.1. Рис. 2.2. Рис. 2.3.
5.Якщо між подіями Р1 і Р2 виконуються дві паралельні операції D1 і D2, то використовують одну допоміжну подію і фіктивну операцію (рис. 2.3). Якщо виконуються кілька паралельних операцій, то вводять відповідну кількість допоміжних подій і фіктивних операцій.
6.В СГ не повинно бути так званих тупикових подій, тобто таких проміжних подій, які не дають початку ніякій роботі. Наприклад, на рис. 2.4 такою подією P5.
Рис. 2.4.
7.В СГ не повинно бути так званих хвостових подій, тобто таких проміжних подій, яким не передує ніяка робота. Такою на рис. 2.4 є подія Р3.
8.В СГ не повинно бути циклів, бо в такому разі створилася б практично неможлива ситуація, коли кожна операція з циклу фактично ніколи не могла б початися: її початок залежав би від виконання інших операцій цього циклу.
У процесі аналізу і розрахунків на СГ нумерувати вершини зручно так, щоб для кожної дуги (r,s), виконувалось співвідношення r<s. Розглянемо один із способів нумерації вершин, який називають способом викреслювання дуг. Для цього вершини спочатку розбивають на ранги, а потім нумерують. Розбиття на ранги проводять так. Вершини, в які не заходять ніякі дуги, називають вершинами рангу 0. В СГ це – єдина початкова вершина. Після цього викреслюють всі дуги, які виходять з вершин рангу 0. Ті вершини, в які не заходить, крім цих, жодна дуга, називають вершинами першого рангу. Така вершина знайдеться хоч одна, бо в СГ немає циклів. Далі з усіх вершин першого рангу викреслюють усі дуги, які виходять з них. Вершинам, які мають вхідні дуги лише розглянутих двох видів, присвоюють ранг 2. Через відповідну кількість кроків усі вершини будуть розбиті на ранги. Нумерацію вершин тепер проводять так. Вершині рангу 0 присвоюють номер 0. Потім у довільному порядку нумерують усі вершини рангу 1, і т.д.
СГ реальних проектів часто містять велику кількість робіт і подій, і тому важливо виділити таку невелику кількість робіт і подій, стежачи за виконанням яких можна тримати в полі зору хід виконання всього проекту. Так приходять до поняття критичного шляху в СГ. Критичний шлях – це найдовший в часі ланцюг робіт, які ведуть від початкової до завершальної події. Щоб проект було виконано в строк, потрібно, щоб усі події на критичному шляху настали не пізніше запланованих строків. Затримка будь-якої події на критичному шляху призводить до затримки виконання всього проекту. Щоб мати уявлення про хід виконання всього проекту, достатньо стежити за виконанням подій на критичному шляху. Строки появи подій, які визначають розглянутим способом, називають мінімальними строками. Мінімальний строк – це найбільш ранній строк, коли дана подія може наступити. Мінімальний строк для події і позначатимемо через . Якщо під довжиною деякого шляху ланцюга в СГ розуміти суму часу виконання всіх робіт на цьому шляху, то є максимальною з довжин усіх шляхів, які ведуть від початкової вершини до вершини i. Максимальним строком настання події називають такий строк, перевищення якого спричинить відповідну затримку завершення всього проекту. Позначатимемо його через для події і. Різницю називають резервом часу для події і. Величини обчислюють так. Для початкової 0 і завершальної s подій покладаємо ==0, =, що обумовлено смислом величин та . Обчислення величин проводимо від завершальної події до почат. Можуть трапитися два випадки:
1) від події і, для якої обчислюємо значення ,відходить одна дуга(наприклад, до події j);
2) від неї відходять дві (наприклад, до подій r та k) і більше дуг (коли кількість дуг більша за дві, обчислення проводиться аналогічно). Через позначатимемо час виконання роботи від події і до події j, який записується в СГ на дугах.
У першому випадку матимемо , тобто максимальний строк події і дорівнює різниці між максимальним строком події j і часом виконання роботи вздовж дуги (і,j). У другому випадку обчислюємо , і мінімальне з цих значень приймаємо за , тобто .
Заповнивши так усі вершини СГ, ми легко обчислюємо резерви часу для всіх подій і знаходимо критичний шлях: він проходить через ті вершини, для яких резерв часу дорівнює нулю. Це найкращий спосіб знаходити критичний шлях, особливо коли СГ містить багато вершин і дуг. СГ може містити кілька критичних шляхів.
Приклад.
Рис. 2.5.
Припустимо, що ми не володіємо інформацією про ймовірності появи кожного стану середовища чи не можемо її застосувати. У цьому випадку головний метод прийняття рішень – це введення гіпотези про поведінку середовища, що дає можливість оцінити наслідки для кожної альтернативи. Мінімаксний критерій. Припускається, що середовище поводить себе найгіршим чином для ОПР. При такій гіпотезі використовують оціночну функцію, яка відповідає позиції найбільшої обережності
; . (3.4)
Використання цього критерію виправдано, коли:
– про можливість появи станів середовища нічого не відомо;
– рішення реалізується лише один раз;
– потрібно виключити будь-який ризик, ні за яких умов не отримати гірший результат.
Критерій мінімаксного ризику Севіджа. Використовується оцінка значень наслідків тих станів, які в результаті вибору відповідного розподілу ймовірностей мають однаковий вплив на рішення. ОПР посідає позицію відносного песимізму. Має вигляд
; . (3.5)
Для розуміння цього критерію, величину можна інтерпретувати як максимальний додатковий виграш, який досягається, коли у стані замість альтернативи вибрати іншу, оптимальну для цього стану альтернативу. Для ситуації прийняття рішень ставляться ті самі вимоги, що й для попереднього випадку. Критерій Гурвіца. Згідно з цим критерієм найкращою вважається та альтернатива, якій відповідає найбільша зважена сума оцінки Байда і необґрунтованого максимуму:
; . (3.6)
Цей критерій ставить перед ситуацією прийняття рішень такі вимоги:
– про можливість появи станів середовища нічого не відомо;
– рішення реалізується невелику кількість разів;
– припускається деякий ризик.
У цьому разі виконуються умови застосування апарату теорії ймовірностей і відомі ймовірності: появи станів середовища . Критерій Байєса-Лапласа. Кожна альтернатив оцінюється математичним сподіванням числової оцінки її наслідків при всіх станах середовища, яке максимізується: . (3.1)
При цьому припускається, що ситуація, в якій приймається рішення характеризується такими обставинами:
– ймовірності появи станів середовища відомі;
– рішення реалізується (теоретично) безліч разів;
– для невеликої кількості реалізацій допускається деякий ризик.
При виборі такого критерію при великій кількості реалізацій середнє значення стабілізується. Тому при повній (нескінченній) реалізації будь-який ризик виключається.
Критерій мінімізації дисперсії оцінок. Цей критерій використовують, коли особа, яка приймає рішення (ОПР), зацікавлена в отриманні “стійкого” щодо станів середовища рішення і відомо, що ймовірності станів середовища мають нормальний розподіл. При виборі цього критерію кожна альтернатива оцінюється дисперсією числової оцінки її наслідків при всіх станах середовища, яка мінімізується:
; , . (3.2)
Інші умови такі самі, як і для попереднього критерію.
Модальний критерій. Суть його полягає у виборі альтернативи, виходячи з найбільш імовірного стану середовища. Припустимо, що існує одне значення . При використанні цього критерію ОПР вважає, що середовище знаходиться у стані і вибирає альтернативу з умови . (3.3)
Хоча цей критерій є песимістичним, він має певні переваги:
– достатньо виділити лише найбільш імовірний стан середовища й не потрібно знати точне кількісне значення ймовірності його виникнення;
– збільшується швидкість обчислень, оскільки розрахунки ведуться лише для найбільш імовірного стану середовища.
Природа задачі управління запасами визначається неодноразовим розміщенням і одержанням замовлень заданих обсягів продукції (надалі – запасів, що зберігаються) у визначені моменти часу. З цього погляду стратегія управління запасами повинна дати відповіді на наступні два запитання. 1. Яку кількість запасу, що зберігатиметься варто замовити? 2. Коли замовляти?
Відповідь на перше запитання визначає економічний розмір замовлення шляхом мінімізації наступної функції витрат.
Усі ці вартості повинні бути виражені як функції шуканого обсягу замовлення й інтервалу часу між замовленнями.
1. Витрати на придбання визначаються вартістю одиниці продукції, яка купується, (запасу, що зберігається). Ця вартість може бути постійною або зі знижкою, що залежить від обсягу замовлення.
2. Витрати на оформлення замовлення представляють собою постійні витрати, пов'язані з його розміщенням (для виготовлення продукції) на інших виробництвах. Ці витрати не залежать від обсягу замовлення.
3. Витрати на збереження запасу представляють собою витрати утримання запасу на складі. Цей вид витрат включає як відсоток на інвестований капітал, так і вартість збереження, утримання і догляду.
4. Втрати від дефіциту запасу – це витрати, зумовлені відсутністю запасу необхідної продукції. Вони включають як потенційні втрати прибутку, так і більш суб'єктивну вартість, пов'язаною із втратою довіри клієнтів.
Відповідь на друге питання (коли замовляти?) залежить від типу системи управління запасами, з якою ми маємо справу. Якщо система передбачає періодичний контроль стану запасу (наприклад, щотижня або щомісяця), момент надходження нового замовлення збігається з початком періоду. Якщо ж у системі передбачений неперервний контроль стану запасу, нові замовлення розміщаються тоді, коли рівень запасу знижується до заздалегідь визначеного значення, який називають точкою поновлення замовлення. Моделі управління запасами, що розглядаються у цій главі, охоплюють два типи детермінованих моделей: статичні і динамічні. У статичних моделях розглядаються ситуації, коли обсяг попиту на продукцію, що зберігається (запас) є постійним у часі. У динамічних моделях обсяг попиту є функцією часу.
Класична задача економічного розміру замовлення
Найпростіші моделі управління запасами характеризуються постійним у часі попитом, миттєвим поповненням запасу і відсутністю дефіциту. Введемо позначення:
y – обсяг замовлення (кількість одиниць продукції),
D – інтенсивність попиту (вимірюється в одиницях продукції на одиницю часу),
– тривалість циклу замовлення (вимірюється в часових одиницях).
Рівень запасу змінюється відповідно до функції, показаної на рис. 5.1, де використані наведені вище позначення. Замовлення обсягу y одиниць розміщується і поповнюється миттєво, коли рівень запасу дорівнює нулеві. Потім запас рівномірно витрачається з постійною інтенсивністю попиту D. Тривалість циклу замовлення для цього прикладу дорівнює одиниць часу.
Середній рівень запасу визначається співвідношенням середній рівень запасу = одиниць. Для побудови функції витрат потрібно два вартісних параметри.
K – витрати на оформлення, які пов'язані з розміщенням замовлення,
h – витрати на збереження (витрати на одиницю складованої продукції в одиницю часу).
Сумарні витрати в одиницю часу (позначається TCU1) можна представити як функцію від y у наступному вигляді.
1 TCU – скорочення від Total Cost per Unit time, тобто сумарні витрати в одиницю часу.
Оптимальне значення обсягу замовлення y визначається шляхом мінімізації по y функції TCU(y). Припускаючи, що y є неперервною змінною, одержимо необхідну умову мінімуму (у вигляді рівняння), з якого можна знайти оптимальне значення y
.
Ця умова є також і достатньою, оскільки функція TCU(y) опукла. Розв’язок даного рівняння визначає економічний обсяг замовлення .
.
Оптимальна стратегія управління запасами для розглянутої моделі формулюється таким чином: Замовляти одиниць продукції через кожні одиниць часу.
Представлена далі модель управління запасами відрізняється від розглянутої вище тільки тим, що продукція може бути придбана зі знижкою, якщо обсяг замовлення y перевищує деякий фіксований рівень q, таким чином, що вартість одиниці продукції c визначається як де . Отже, витрати на придбання продукції в одиницю часу Використовуючи позначення з розділу 5.3.1, запишемо загальні витрати в одиницю часу так.
Графіки функцій і представлені на рис. 5.3. Оскільки значення цих функцій відрізняються тільки на сталу величину, то точки їх мінімуму збігаються і знаходяться в точці .
Графік функції витрат TCU(y), якщо йти від мінімальних значень аргументів, збігається з графіком функції до точки , у якій змінюється ціна продукції, а потім збігається з графіком функції . Рис. 5.3 показує, що визначення оптимального обсягу замовлення залежить від того, де знаходиться точка розриву ціни q стосовно до зазначених на рисунку зон I, II і III, які визначені як інтервали , і відповідно. Величина визначається з рівняння .
Рис. 5.4 показує, як визначається оптимальне значення .
Рис. 5.4
Алгоритм визначення можна сформулювати в наступному вигляді.
Крок 1. Обчислюємо . Якщо q попадає в зону I, кладемо . У протилежному випадку переходимо до кроку 2.
Крок 2. Знаходимо Q з рівняння і визначаємо зони II і III. Якщо q знаходиться в зоні II, кладемо . Інакше q знаходиться в зоні III, тоді .
Ця модель розглядає задачу управління запасами n різних товарів, що зберігаються на одному складі обмеженої місткості. Характер зміни запасу кожного товару окремо визначається функцією, показаною на рис. 5.1; припускаємо, що дефіцит відсутній. Відмінність від раніше розглянутих моделей полягає в тому, що товари конкурують між собою за обмежений складський простір. Визначимо для товару i, i=1,2,...,n наступні параметри. – інтенсивність попиту, – вартість розміщення замовлення, – вартість збереження одиниці товару в одиницю часу, – обсяг замовлення, – необхідний простір для збереження одиниці товару, A – максимальний складський простір для збереження товарів n видів. При відсутності дефіциту математична модель сформульованої задачі має такий вигляд. Мінімізувати
при обмеженнях , . Алгоритм розв’язання цієї задачі можна описати таким чином.
Крок 1. Обчислюються оптимальні обсяги замовлень без обліку обмеження по місткості складу: .
Крок 2. Здійснюється перевірка, чи задовольняють знайдені значення обмеженню по місткості складу. Якщо "Так", обчислення закінчуються, при цьому значення , є оптимальними. У протилежному випадку варто перейти до кроку 3.
Крок 3. Обмеження по місткості складу повинно задовольнятися у формі рівності. Використовується метод множників Лагранжа для визначення оптимальних обсягів замовлення для задачі з обмеженням. На кроці 3 будується функція Лагранжа
, де – множник Лагранжа1.
1 Застосування методу в даному випадку є коректним, тому що тут функція TCU(y1,y2,…,yn) опукла, задача має єдине лінійне обмеження і, отже, опуклий простір розв’язків. Метод може виявитися некоректним при інших обмеженнях або при наявності більш ніж одного обмеження. Оскільки функція Лагранжа є опуклою, оптимальні значення і знаходяться з наступних рівнянь, що представляють собою необхідні умови екстремуму функції Лагранжа. , .
Друге рівняння показує, що обмеження по місткості складу в оптимальній точці повинно задовольнятися у формі рівності. З першого рівняння випливає, що
Отримана формула показує, що залежить від оптимального значення множника Лагранжа. Крім того, при значення є розв’язком задачі без обмеження. Значення може бути знайдене таким чином. Оскільки за визначенням у поставленій вище задачі мінімізації , ми послідовно зменшуємо на досить малу величину і використовуємо її в даній формулі для обчислення відповідного значення . Шукане значення приводить до значень , , що задовольняють обмеженню по місткості складу у формі рівності.
У цій моделі розглядається задача календарного планування виробництва розрахована на n рівних періодів. Можливі обсяги виробництва кожного з періодів обмежені, однак вони можуть включати кілька рівнів (наприклад, два можливих обсяги виробництва можуть визначатися звичайним режимом роботи і понаднормових робіт відповідно). Протягом поточного періоду можуть вироблятися вироби для наступних періодів, але в цьому випадку повинні враховуватися витрати на їх збереження. Основні припущення моделі полягають у наступному.1. Відсутність витрат на оформлення замовлення в будь-який період планування. 2.Відсутність (неприпустимість) дефіциту. 3. Вартість виробництва одиниці продукції в будь-який період або є постійною, або має зростаючі граничні витрати (функція витрат є опуклою).4. Вартість збереження одиниці продукції кожного періоду є постійною величиною. Припущення про відсутність дефіциту означає, що попит на продукцію протягом поточного періоду не може бути задоволений за рахунок її виробництва в наступні періоди. Це припущення принаймні вимагає, щоб сумарні можливості виробництва за періоди 1,2,...,i були рівні сумарному попитові на продукцію за цей же час. На рис. 5.6 показано, коли виробничі витрати на одиницю продукції зростають зі збільшенням рівня виробництва. Наприклад, при двох можливих обсягах виробництва, що визначаються звичайним режимом роботи і понаднормовими роботами, вартість виробництва одиниці продукції, виробленої в понаднормовий час, вища, ніж при звичайному режимі роботи. Рис. 5.6 Розглянуту задачу n-етапного планування можна сформулювати у вигляді транспортної задачі (див. главу 5) з kn пунктами виробництва і n споживачами, де k – кількість можливих рівнів виробництва протягом періоду (наприклад, якщо протягом кожного періоду використовуються регулярний і надточний режими роботи, то k=2). Виробничі можливості кожного з kn пунктів виробництва визначають обсяги постачань. Обсяги споживання визначаються обсягом попиту для кожного періоду. Собівартість "перевезення" від пункту виробництва до пункту призначення визначається сумою витрат використовуваного виробничого процесу і вартості збереження одиниці продукції. Оптимальний розв’язок такої транспортної задачі визначить обсяги виробництва продукції для кожного виробничого рівня, що мінімізують сумарні витрати на виробництво і збереження. Цю задачу можна розв’язати без використання методу розв’язання транспортних задач. Обґрунтованість нового методу розв’язання, показаного далі, випливає зі згаданих припущень про відсутність дефіциту й опуклості функції витрат на виробництво. Приклад 5.4-1 Компанія виробляє спеціальні витяжки, що використовуються в домашніх камінах у період із грудня по березень. На початку опалювального сезону попит на цю продукцію низький, у середині сезону він досягає свого піка і зменшується до кінця сезону. З огляду на популярність продукції, компанія може використовувати понаднормові роботи для задоволення попиту на свою продукцію. Наступна таблиця містить дані про виробничі потужності компанії й обсяги попиту протягом чотирьох місяців.
|
Місяць |
Можливості виробництва |
Попит (одиниці) |
|
|
Звичайний режим роботи (одиниці) |
Понаднормові (одиниці) |
||
|
1 2 3 4 |
90 100 120 110 |
50 60 80 70 |
100 190 210 160 |
Вартість виробництва одиниці продукції дорівнює 6 доларів в умовах звичайного режиму роботи і 9 доларів при понаднормових роботах. Вартість збереження одиниці продукції протягом місяця дорівнює 0.10 долара. Щоб гарантувати допустимість розв’язку при відсутності дефіциту, потрібно, щоб сумарна пропозиція продукції (можливості виробництва) до початку кожного місяця щонайменше дорівнювало сумарному попитові. Про це свідчить наступна таблиця.
|
Місяць |
Сумарна пропозиція |
Сумарний попит |
|
1 |
90+50=140 |
100 |
|
2 |
140+100+60=300 |
100+190=290 |
|
3 |
300+120+80=500 |
290+210=500 |
|
4 |
500+110+70=680 |
500+160=660 |
У табл. 5.1 подані дані, що відносяться до розглянутої задачі, і її розв’язку. Тут і відповідають рівням виробництва у звичайному і понаднормовому режимі роботи протягом періоду i, i=1,2,3,4. Оскільки сумарна пропозиція в четвертому періоді перевищує сумарний попит, то введений фіктивний пункт споживання (надлишок), щоб збалансувати модель (це показано в табл. 5.1). Усі "транспортні" маршрути з попередніх у поточний період заблоковані, тому що дефіцит відсутній. Собівартості "перевезень" продукції обчислюються у вигляді суми витрат на виробництво і збереження. Наприклад, відповідна собівартість від до першого періоду дорівнює лише вартості виготовлення в 6 доларів, собівартість від до четвертого періоду – вартості виготовлення плюс вартість збереження від першого періоду до четвертого, тобто 9+(0.1+0.1+0.1)=9.30 долара. Нарешті, собівартість перевезення до фіктивного пункту споживання (надлишок) дорівнює нулеві. Таблиця 5.1.
|
1 |
2 |
3 |
4 |
Надлишок |
|||||||
|
R1 |
6 |
6.1 |
6.2 |
6.3 |
0 |
90 |
|||||
|
90 |
|||||||||||
|
O1 |
9 |
9.1 |
9.2 |
9.3 |
0 |
50 |
|||||
|
10 |
30 |
10 |
|||||||||
|
R2 |
6 |
6.1 |
6.2 |
0 |
100 |
||||||
|
100 |
|||||||||||
|
O2 |
9 |
9.1 |
9.2 |
0 |
60 |
||||||
|
60 |
|||||||||||
|
R3 |
6 |
6.1 |
0 |
120 |
|||||||
|
120 |
|||||||||||
|
O3 |
9 |
9.1 |
0 |
80 |
|||||||
|
80 |
|||||||||||
|
R4 |
6 |
0 |
110 |
||||||||
|
110 |
|||||||||||
|
O4 |
9 |
0 |
70 |
||||||||
|
50 |
|||||||||||
|
100 |
190 |
210 |
160 |
20 |
Оптимальний розв’язок отримується за один прохід, починаючи з першого стовпця у напрямку до стовпця "Надлишок". Для кожного перспективного стовпця попит задовольняється з використанням найдешевшого маршруту. Починаючи з першого стовпця маршрут (,1) має саму дешеву собівартість перевезення, і ми призначаємо перевезення максимально можливого обсягу, а саме min(90,100)=90 одиниць, що залишає 10 одиниць незадоволеного попиту в першому стовпці. Далі ми переходимо до наступного по собівартості маршруту (,1) першого стовпця і визначаємо перевезення min(50,10)=10 одиниць, що тепер цілком задовольняє попит для першого періоду. Після задоволення попиту для першого періоду ми переходимо до другого стовпця. Визначення перевезень у цьому стовпці здійснюється таким чином: 100 одиниць по маршруту (,2), 60 одиниць по маршруту (,2) і 30 одиниць по маршруту (,2). Цим маршрутам відповідають собівартості "перевезень" у 6, 9 і 9.10 доларів. При цьому маршрут (,2), транспортні витрати на одиницю продукції для якого рівні 6.10 доларів, не розглядається, тому що весь запас був витрачений для першого періоду. Продовжуючи аналогічним чином, ми задовольняємо попит для третього, а потім і четвертого стовпців. Оптимальний розв’язок, виділений жирним шрифтом у табл. 5.1, інтерпретується таким чином.
Період 1 (звичайний режим роботи). Виготовити 90 одиниць продукції для першого періоду.
Період 1 (понаднормовий режим роботи). Виготовити 40 одиниць продукції: 10 для періоду 1, 30 для періоду 2 і 10 для періоду 3.
Період 2 (звичайний режим роботи). Виготовити 100 одиниць продукції для другого періоду.
Період 2 (понаднормовий режим роботи). Виготовити 60 одиниць продукції для періоду 2.
Період 3 (звичайний режим роботи). Виготовити 120 одиниць продукції для третього періоду.
Період 3 (понаднормовий режим роботи). Виготовити 80 одиниць продукції для періоду 3.
Період 4 (звичайний режим роботи). Виготовити 110 одиниць продукції для четвертого періоду.
Період 4 (понаднормовий режим роботи). Виготовити 50 одиниць продукції для періоду 4; залишилася невикористаною виробнича потужність на 20 одиниць продукції.
Відповідні сумарні витрати при цьому рівні
У розглядуваній моделі передбачається, що дефіцит не допускається і витрати на оформлення замовлення враховуються кожного разу, коли починається виробництво нової партії продукції. Тут будуть розглянуті два методи розв’язання цієї задачі: точний метод динамічного програмування й евристичний. Дана задача управління запасами схематично представлена на рис. 5.7. На цьому рисунку використані позначення наступних величин, визначених для кожного етапу i, i=1,2,...,n. – кількість замовленої продукції (обсяг замовлення), – потреба в продукції (попит), – обсяг запасу на початок етапу i.
Рис. 5.7 Вартісні елементи в задачі, що розглядається визначаються так: – витрати на оформлення замовлення, – витрати на збереження одиниці продукції, що переходить з етапу i в етап i+1 Відповідна функція виробничих витрат для етапу i задається формулою
де –функція граничних виробничих витрат при заданому значенні
Алгоритм динамічного програмування із загальною функцією вартості. Оскільки дефіцит не допускається, задача управління запасами зводиться до знаходження значень , що мінімізують сумарні витрати, які пов'язані з розміщенням замовлень, закупівлею і збереженням продукції протягом n етапів. Витрати на збереження на i-му етапі для простоти вважаються пропорційними величині , яка представляє собою обсяг запасу, що переходить з етапу i в етап i+1. Для побудови моделі динамічного програмування можна скористатися рекурентними співвідношеннями процедури прямої або зворотної прогонки. Ми скористаємося рекурентними співвідношеннями процедури прямої прогонки, оскільки вони більш ефективні при аналізі важливого часткового випадку розглянутої задачі, пов'язаного з незростаючими граничними витратами. Для рекурентного рівняння процедури прямої прогонки стан на етапі (періоді) i визначається як обсяг запасу на кінець етапу, де, як випливає з рис. 5.7, . Ця нерівність означає, що в граничному випадку запас може задовольнити попит на всіх наступних етапах. Нехай – мінімальні загальні витрати на етапах 1,2,...,i при заданій величині запасу на кінець етапу i. Тоді рекурентне рівняння алгоритму прямої прогонки буде записано таким чином. , .
Приклад 5.4-2 Потрібно знайти оптимальну стратегію в трьохетапній системі управління запасами, що формулюється нижче. Початковий запас дорівнює одиниці продукції. Передбачається, що граничні витрати на придбання продукції складають 10 доларів за кожну одиницю для перших трьох одиниць і 20 доларів – за кожну додаткову одиницю.
|
Період i |
Попит, (одиниці) |
Витрати на оформлення замовлення, ($) |
Витрати на збереження, ($) |
|
1 |
3 |
3 |
1 |
|
2 |
2 |
7 |
3 |
|
3 |
4 |
6 |
2 |
Функція виробничих витрат для періоду i дорівнює для , де
Етап 1. .
|
Оптимальний розв’язок |
||||||||||
|
3 |
4 |
5 |
6 |
7 |
8 |
|||||
|
33 |
53 |
73 |
93 |
113 |
133 |
|||||
|
0 |
0 |
23 |
23 |
2 |
||||||
|
1 |
1 |
34 |
34 |
3 |
||||||
|
2 |
2 |
55 |
55 |
4 |
||||||
|
3 |
3 |
76 |
76 |
5 |
||||||
|
4 |
4 |
97 |
97 |
6 |
||||||
|
5 |
5 |
118 |
118 |
7 |
||||||
|
6 |
6 |
139 |
139 |
8 |
Оскільки , мінімальне значення дорівнює . Етап 2. .
|
Оптимальний розв’язок |
||||||||||
|
1 |
2 |
3 |
4 |
5 |
6 |
|||||
|
17 |
27 |
37 |
57 |
77 |
97 |
|||||
|
0 |
0 |
0+55=55 |
17+34=51 |
27+23=50 |
50 |
2 |
||||
|
1 |
3 |
3+76=79 |
20+55=75 |
30+34=64 |
40+23=63 |
63 |
3 |
|||
|
2 |
6 |
6+97=103 |
23+76=99 |
33+55=88 |
43+34=77 |
63+23=86 |
77 |
3 |
||
|
3 |
9 |
9+118=127 |
26+97=123 |
36+76=112 |
46+55=101 |
66+34=100 |
86+23=109 |
100 |
4 |
|
|
4 |
12 |
12+139=151 |
29+118=147 |
39+97=136 |
49+76=125 |
69+55=124 |
89+34=123 |
109+23=132 |
123 |
5 |
Етап 3. .
|
Оптимальний розв’язок |
||||||||
|
1 |
2 |
3 |
4 |
|||||
|
16 |
26 |
36 |
56 |
|||||
|
0 |
0 |
0+123=123 |
16+100=116 |
26+77=103 |
36+63=99 |
56+50=106 |
99 |
3 |
Оптимальний розв’язок визначається наступними значеннями шуканих змінних: , і . При цьому загальні витрати складають 99 доларів.
Деякі фахівці намагалися адаптувати детерміновану модель економічного розміру замовлення для урахування імовірнісної природи попиту, використовуючи при цьому наближений метод, що припускає існування постійного буферного запасу протягом усього планового періоду. Розмір резерву встановлюється таким чином, щоб імовірність виснаження запасу протягом періоду виконання замовлення не перевищувала наперед заданої величини. Уведемо наступні позначення.
L – термін виконання замовлення, тобто час від моменту розміщення замовлення до його постачання; – випадкова величина, що представляє величину попиту протягом терміну виконання замовлення; – середня величина попиту протягом терміну виконання замовлення; – середньоквадратичне відхилення величини попиту протягом терміну виконання замовлення; B – розмір резервного запасу; – максимально можливе значення імовірності виснаження запасу протягом терміну виконання замовлення.
Основним припущенням при побудові моделі є те, що величина попиту протягом терміну виконання замовлення L є нормально розподіленою випадковою величиною із середнім і стандартним відхиленням , тобто має розподіл .
На рис. 6.1 показана залежність між розміром резервного запасу B і параметрами детермінованої моделі економічного розміру замовлення, що включає термін виконання замовлення L, середню величину попиту протягом терміну виконання замовлення й економічний розмір замовлення . Зазначимо, що L повинно дорівнювати ефективному часові виконання замовлення. Імовірнісна умова, що визначає розмір резервного запасу B, має вигляд . За визначенням випадкова величина є нормованою нормально розподіленою випадковою величиною, тобто має розподіл N(0,1). Отже, . На рис. 6.2 показана величина , що визначається з таблиці стандартного нормального розподілу, так що .
Отже, розмір резервного запасу повинен задовольняти нерівності
Рис. 6.1 Рис. 6.2
Величина попиту протягом терміну виконання замовлення L звичайно описується щільністю розподілу імовірностей, віднесеної до одиниці часу (наприклад, до дня або тижня), з якої можна визначити розподіл попиту протягом періоду L. Зокрема, якщо попит за одиницю часу є нормально розподіленою випадковою величиною із середнім D і стандартним відхиленням , то загальний попит протягом терміну виконання замовлення L буде мати розподіл , де і . Формула для , отримана на підставі того, що значення L є цілим числом (або ж округлене до цілого числа).
Немає підстав думати, що розглянута вище модель економічного розміру замовлення визначить оптимальну політику управління запасами. Підтвердженням цього є те, що істотна інформація, яка має відношення до імовірнісної природи попиту, при цьому підході спочатку не враховується, а використовується лише незалежно на останньому етапі обчислень. Щоб виправити цей недолік, розглянемо більш точну модель, у якій імовірнісна природа попиту враховується безпосередньо в постановці задачі.
На відміну від попереднього випадку у цій моделі допускається незадоволений попит, як це показано на рис. 6.3. У розглянутій моделі замовлення розміром y розміщається тоді, коли обсяг запасу досягає рівня R. Як і в детермінованому випадку, рівень R, при якому знову розміщається замовлення, є функцією періоду часу між розміщенням замовлення і його виконанням. Оптимальні значення y і R визначаються шляхом мінімізації очікуваних витрат системи управління запасами, віднесених до одиниці часу, що включають як витрати на розміщення замовлення і його збереження, так і втрати, пов'язані з незадоволеним попитом. У розглянутій моделі прийняті три припущення.
1. Незадоволений протягом терміну виконання замовлення попит накопичується.
2. Дозволяється не більше одного невиконаного замовлення.
3. Розподіл попиту протягом терміну виконання замовлення є незмінним у часі.
Для визначення функції, що відображає сумарні витрати, віднесені до одиниці часу, уведемо наступні позначення. – щільність розподілу попиту x протягом терміну виконання замовлення;
D – очікуване значення попиту в одиницю часу;
h – питомі витрати на збереження (на одиницю продукції за одиницю часу); p – питомі втрати від незадоволеного попиту (на одиницю продукції за одиницю часу); K – вартість розміщення замовлення. Ґрунтуючись на цих визначеннях, обчислимо компоненти функції витрат.
1. Вартість розміщення замовлень. Наближене число замовлень в одиницю часу дорівнює , так що вартість розміщення замовлень в одиницю часу дорівнює .
2. Очікувані витрати на збереження. Середній рівень запасу дорівнює .
Отже, очікувані витрати на збереження за одиницю часу рівні . Наведена формула отримана в результаті усереднення очікуваних запасів на початку та в кінці часового циклу, тобто величин і відповідно. При цьому ігнорується випадок, коли величина може бути від’ємною, що є одним із допущень, які спрощують розглядувану модель.
3. Очікувані втрати, які пов'язані з незадоволеним попитом. Дефіцит виникає при . Отже, очікуваний дефіцит за одиницю часу дорівнює .
Оскільки в моделі передбачається, що p пропорційне лише обсягові дефіциту, очікувані втрати, які пов'язані з незадоволеним попитом, за один цикл дорівнюють . Оскільки одиниця часу містить циклів, то очікувані втрати, зумовлені дефіцитом, складають за одиницю часу. Результуюча функція загальних втрат за одиницю часу TCU має такий вигляд. .
Оптимальні значення і визначаються з представлених нижче рівнянь.
, .
Отже, маємо , (1) . (2)
Оскільки з рівнянь (1) і (2) і не можна визначити в явному вигляді, для їх знаходження використовується чисельний алгоритм, запропонований Хедлі й Уайтін (Hadley, Whitin). Доведено, що алгоритм збігається за скінченне число ітерацій при умові, що допустимий розв’язок існує. При останні два рівняння відповідно дають наступне. , .
Якщо , тоді існують єдині оптимальні значення для y і R. Обчислювальна процедура визначає, що найменшим значенням є , яке досягається при S=0. Алгоритм складається з наступних кроків.
Крок 0. Приймаємо за початковий розв’язок і вважаємо . Кладемо i=1 і переходимо до кроку i.
Крок i. Використовуємо значення для визначення з рівняння (2). Якщо , обчислення припиняють; за оптимальний розв’язок приймаємо і . В іншому випадку, використовуючи значення з рівняння (1) знаходимо . Кладемо i=i+1 і повторюємо крок i.
Одноетапні моделі управління запасами відображають ситуацію, коли для задоволення попиту протягом визначеного періоду продукція замовляється тільки один раз. Наприклад, у модний сезонний товар застаріває до кінця сезону, і, отже, замовлення на нього можуть не відновлюватись. Будемо використовувати наступні позначення. c – вартість закупівлі (або виробництва) одиниці продукції; K – вартість розміщення замовлення; h – питомі витрати на збереження одиниці продукції протягом розглянутого періоду; p – питомі втрати від незадоволеного попиту (на одиницю продукції за розглянутий період); D – величина випадкового попиту за розглянутий період; f(D) – щільність імовірності попиту за розглянутий період; y – обсяг замовлення; x – наявний запас продукції перед розміщенням замовлення. Модель визначає оптимальний обсяг замовлення y, що мінімізує сумарні очікувані витрати, які пов'язані із закупівлею (або виробництвом), збереженням і незадоволеним попитом. При відомому оптимальному значенні y (позначається ) оптимальне управління запасами полягає у розміщенні замовлення обсягом , якщо , у протилежному випадку замовлення не розміщається. Модель при відсутності витрат на оформлення замовлення У цій моделі приймається наступне. 1.Попит задовольняється миттєво на початку періоду безпосередньо після одержання замовлення. 2.Витрати на розміщення замовлення відсутні. Рис. 6.4 ілюструє стан запасу після задоволення попиту D. Якщо , запас y–D зберігається протягом періоду. Якщо ж , виникає дефіцит обсягом D–y.
Очікувані витрати M{C(y)} за період виражаються наступною формулою.
.
Можна показати, що функція M{C(y)} є опуклою по y і, таким чином, має єдиний мінімум. Отже, обчислюючи першу похідну функції M{C(y)} по y і прирівнюючи її до нуля, одержимо або .
Звідси маємо . Права частина останньої формули відома як критичне відношення. Значення визначиться тільки за умови, якщо критичне відношення є невід’ємним, тобто . Випадок, коли , є безглуздим, оскільки це означає, що вартість закупівлі одиниці продукції вища втрати від незадоволеного попиту. Раніше передбачалося, що попит D є неперервною випадковою величиною. Якщо ж D є дискретною величиною, то щільність розподілу імовірностей f(D) визначена лише в дискретних точках і функція витрат визначається відповідно до формули . Необхідними умовами оптимальності є нерівності и
Ці умови в даному випадку є достатніми, оскільки функція M{C(y)} опукла. Використовуючи ці умови, після деяких алгебраїчних перетворень приходимо до наступних нерівностей для визначення . .
Приклад 6.3–1 Власник газетного кіоску повинен визначити кількість екземплярів газети USA Now, які повинні бути в продажі на початку кожного дня. Він купує екземпляр газети за 30 центів, а продає за 75 центів. Продаж газети звичайно відбувається з 7.00 до 8.00 годин ранку. Екземпляри газети, що залишилися до кінця дня, повторно виставляються для продажу за ціною 5 центів за екземпляр. Скільки екземплярів газети повинен закупити власник щоранку, якщо денний попит описується одним з наступних імовірнісних розподілів.
1. Нормальним розподілом з математичним сподіванням 300 екземплярів і стандартним відхиленням 20 екземплярів.
2. Дискретною щільністю розподілу f(D), заданої у вигляді наступної таблиці.
|
D |
200 |
220 |
300 |
320 |
340 |
|
f(D) |
0.1 |
0.2 |
0.4 |
0.2 |
0.1 |
Вартості збереження і втрати, які обумовлені дефіцитом, у цій ситуації не визначені в явному вигляді. Однак дані задачі свідчать про те, що кожен непроданий екземпляр газети обходиться власникові в 30–5=25 центів і що втрати, пов'язані з виснаженням запасу газет, дорівнюють 75 центів за екземпляр. Отже, у термінах, прийнятих у моделі управління запасами, ми можемо припускати, що c=30 центів за екземпляр, h=25 центів за екземпляр, p=75 центів за екземпляр у день. Спочатку визначаємо критичне відношення
Випадок 1. Попит D розподілений по нормальному закону N(300,20). Визначимо нормовану нормально розподілену випадкову величину (із законом розподілу N(0,1))
. Тоді . З таблиці стандартного нормального розподілу знаходимо . Отже, оптимальний обсяг замовлення дорівнює (або приблизно 298) екземплярів.
Випадок 2. Попит D описується дискретною щільністю розподілу f(D). Спочатку знайдемо функцію розподілу .
|
y |
200 |
220 |
300 |
320 |
340 |
|
0.1 |
0.3 |
0.7 |
0.9 |
1.0 |
Для обчисленого критичного відношення 0.45 маємо нерівності .
Звідси випливає, екземплярів.
Перед тим як викласти деталі даного методу, розглянемо приклад, що демонструє спосіб, за допомогою якого оцінюються різні альтернативні рішення.
Приклад 4.1 Максим Петренко – випускник-відмінник середньої школи, що одержав запрошення на навчання від трьох університетів: А, В и С. З метою вибору університету Максим сформулював два основних критерії: місцезнаходження університету і його академічна репутація. Будучи відмінним учнем, він оцінює академічну репутацію університету в п'ять разів вище, ніж його місцезнаходження. Це приводить до того, що репутації університету приписується вага приблизно 83%, а його місцезнаходженню – 17%. Далі Максим використовує системний аналіз (сутність його викладається нижче) для оцінки трьох університетів з погляду їхнього місцезнаходження і репутації. Проведений аналіз дає наступні оцінки.
|
Університет |
|||
|
А |
B |
C |
|
|
Місцезнаходження Репутація |
12.9% 54.5% |
27.7% 27.3% |
59.4% 18.2% |
Структура задачі прийняття рішень приведена на рис. 4.1. Задача має єдиний ієрархічний рівень із двома критеріями (місцезнаходження і репутація) і три альтернативних рішення (університети А, В и С). Оцінка трьох університетів ґрунтується на обчисленні комбінованого вагового коефіцієнта для кожного з них.
Університет А: 0.170.129+0.830.545=0.4743.
Університет В: 0.17(0.277+0.83(0.273=0.2737.
Університет С: 0.17(0.594+0.83(0.182=0.2520.
На основі цих обчислень університет А одержує найвищу комбіновану вагу і, отже, є найбільш оптимальним вибором Максима.
Рис. 4.1
Загальна структура методу аналізу ієрархій може включати декілька ієрархічних рівнів зі своїми критеріями. Припустимо у прикладі 4.1, що сестра-близнюк Максима Дарина також одержала повну стипендію від трьох університетів. Однак їхні батьки ставлять умову, що діти повинні учитися в одному університеті, тоді вони зможуть користуватися одним автомобілем. На рис. 4.2 наведена структура задачі вибору рішення, що тепер включає два ієрархічних рівні зі своїми критеріями. Величини p і q (приблизно рівні) на першому ієрархічному рівні являють собою вагові коефіцієнти, що приписуються точці зору Максима і Дарини щодо процесу вибору, відповідно. Другий ієрархічний рівень використовує ваги і для відображення індивідуальних точок зору Максима і Дарини щодо критеріїв місцезнаходження й академічної репутації кожного університету. Інша частина структури ухвалення рішення може бути інтерпретована аналогічно попередньому прикладові. Відмітимо, що , , , , , , . Визначення комбінованої ваги для університету А, представлене на рис. 4.2, де демонструється, як обчислюються ці показники.
Рис. 4.2.
20.Визначення вагових коефіцієнтів.
Складність методу аналізу ієрархій полягає у визначенні відносних вагових коефіцієнтів (таких, які використані в прикладі 4.1) для оцінки альтернативних рішень. Якщо маємо п критеріїв на заданому рівні ієрархії, то відповідна процедура створює матрицю А розмірності , яку називають матрицею парних порівнянь, яка відображає судження особи, що приймає рішення, щодо важливості різних критеріїв. Парне порівняння виконується так, що критерій у рядку i (i=1,2,...,n) оцінюється щодо кожного з критеріїв, представлених n стовпцями. Позначимо через елемент матриці А, який знаходиться на перетинанні i-го рядка і j-го стовпця. Відповідно до методу аналізу ієрархій для опису згаданих оцінок використовуються цілі числа від 1 до 9. При цьому означає, що i-й і j-й критерії однаково важливі, відображає думку, що i-й критерій значно важливіший, ніж j-й, а вказує, що i-й критерій надзвичайно важливіший j-го. Інші проміжні значення між 1 і 9 інтерпретуються аналогічно. Узгодженість таких позначень забезпечується наступною умовою: якщо , то автоматично . Крім того, усі діагональні елементи матриці А повинні бути рівні 1, тому що вони виражають оцінку критеріїв щодо самих себе.
Приклад 4.2 Покажемо, як визначається матриця порівняння А для задачі вибору Максима з прикладу 4.1. Почнемо з головного ієрархічного рівня, що має справу з критеріями академічної репутації університету і його місцезнаходження. З погляду Максима академічна репутація університету значно важливіше його місцезнаходження. Отже, він приписує елементові (1,2) матриці А значення 5, тобто . Це автоматично означає, що . Позначивши через R і L критерії репутації університету і його місцезнаходження, можна записати матрицю порівняння так. .
Відносні ваги критеріїв R і L можуть бути визначені шляхом ділення елементів кожного стовпця на суму елементів цього ж стовпця. Отже, для нормалізації матриці А ділимо елементи першого стовпця на величину 1+1/5=1.2, елементи другого – на величину 5+1=6. Шукані відносні ваги і критеріїв обчислюються тепер у вигляді середніх значень елементів відповідних рядків нормалізованої матриці А. Отже, Середні значення елементів рядків
У результаті обчислень одержали і , тобто ті ваги, які показані на рис. 4.1. Стовпці матриці N однакові, що має місце лише у випадку, коли особа, що приймає рішення, виявляє ідеальну узгодженість у визначенні елементів матриці А. Ця теза детальніше обговорюється нижче. Відносні ваги альтернативних рішень, що відповідають університетам А, В и С, обчислюються в межах кожного критерію R і L з використанням наступних двох матриць порівняння. ,
Сума елементів стовпців =[1.83, 3.67, 5.5],
Сума елементів стовпців = [8, 3.5, 1.7]. Елементи матриць і визначені на основі суджень Мартіна, що стосуються відносної важливості трьох університетів. При діленні елементів кожного стовпця матриць і на суму елементів цих же стовпців одержуємо наступні нормалізовані матриці.
Середні значення елементів рядків
Величини дають відповідні ваги для університетів А, В и С з точки зору академічної репутації. Аналогічно величини є відносними вагами, що стосуються місцезнаходження університетів.
21.Узгодженість матриці порівнянь.
У прикладі 4.2 ми відзначали, що всі стовпці нормалізованих матриць N і ідентичні, а стовпці матриці такими не є. Однакові стовпці вказують на те, що результуючі відносні ваги зберігають ті самі значення незалежне від того, як виконується порівняння. У цьому випадку говорять, що вихідні матриці порівняння А и є узгодженими. Отже, матриця не є такою. Узгодженість означає, що рішення буде узгоджено з визначеннями парних порівнянь критеріїв або альтернатив. З математичної точки зору узгодженість матриці А означає, що для всіх i, j і k. Наприклад, у матриці з прикладу 4.2 і . Властивість узгодженості вимагає лінійної залежності стовпців (і рядків) матриці А. Зокрема, стовпці будь-якої матриці порівнянь розмірністю 22 є залежними, і, отже, така матриця завжди є узгодженою. Не всі матриці порівнянь є узгодженими. Дійсно, приймаючи до уваги, що такі матриці будуються на основі людських суджень, можна чекати деякий ступінь неузгодженості, і до неї варто відноситися терпимо за умови, що вона не виходить за визначені "допустимі" рамки.
Щоб з'ясувати, чи є рівень узгодженості "допустимим", необхідно визначити відповідну кількісну міру для матриці порівнянь А. У прикладі 4.2 ми бачили, що ідеально погоджена матриця А породжує нормалізовану матрицю N, у якій усі стовпці однакові.
Звідси випливає, що матриця порівнянь А може бути отримана з матриці N шляхом ділення елементів i-го стовпця на , (це процес, зворотний до знаходження матриці N з А). Отже, одержуємо наступне. Використовуючи наведене визначення матриці А, маємо .
У компактній формі умова узгодженості матриці А формулюється так. Матриця А буде узгодженою тоді і тільки тоді, коли , де w – вектор-стовпець відносних ваг , i=1,2,...,п. Коли матриця А не є узгодженою, відносна вага , – апроксимується середнім значенням n елементів i-го рядка нормалізованої матриці N (див. приклад 4.2). Позначивши через обчислену оцінку (середнє значення), можна показати, що
де . У цьому випадку, чим ближче до n, тим більш узгодженою є матриця порівняння А. У результаті відповідно до методу аналізу ієрархій обчислюється коефіцієнт узгодженості у вигляді , де – коефіцієнт узгодженості матриці A, – стохастичний коефіцієнт узгодженості матриці A.
Стохастичний коефіцієнт узгодженості визначається емпіричним шляхом як середнє значення коефіцієнта для великої вибірки генерованих випадковим чином матриць порівняння А.
Коефіцієнт узгодженості CR використовується для перевірки узгодженості матриці порівняння А в такий спосіб. Якщо , рівень неузгодженості є прийнятним. У протилежному випадку рівень неузгодженості матриці порівняння А є високим і особі, що приймає рішення, рекомендується перевірити елементи парного порівняння матриці А в цілях одержання більш узгодженої матриці.
Значення обчислюється на основі матричного рівняння , при цьому неважко помітити, що i-те рівняння цієї системи має вигляд: .
Оскільки , легко перевірити, що .
Це означає, що величину можна визначити шляхом обчислення вектора-стовпця з наступним підсумовуванням його елементів.
Приклад 4.3 У прикладі 4.2 матриця є неузгодженою, тому що стовпці матриці неоднакові. Потрібно дослідити узгодженість матриці . Обчислимо значення . З даних прикладу 4.2 маємо , , .
Отже, .
Звідси одержуємо .
Отже, для n=3 маємо , , .
Оскільки , рівень неузгодженості матриці є прийнятним.
Основними елементами моделі масового обслуговування є клієнт (заявка або вимога на обслуговування або просто "об'єкт обслуговування") і сервіс (обслуговуючий пристрій, засіб обслуговування і т.п.). Клієнти надходять у систему обслуговування з джерела. Надійшовши в сервіс, вони можуть відразу ж потрапити на обслуговування або очікувати в черзі, якщо сервіс зайнятий. Після завершення процедури обслуговування сервіс автоматично "вибирає" з черги (якщо вона існує) одного з клієнтів для того, щоб приступити до його обслуговування. Якщо ж черга відсутня, то сервіс стає незайнятим до прибуття нового клієнта. Надходження клієнтів у систему обслуговування характеризується інтервалом між їх послідовними надходженнями, а обслуговування – часом обслуговування клієнта. У загальному випадку ці параметри можуть бути як випадковими, так і детермінованими. В аналізі систем обслуговування важливу роль відіграє довжина черги, яка може бути скінченною і нескінченною. Важливим фактором є дисципліна черги або принцип побудови черги, що визначає порядок, відповідно до якого вибираються клієнти з черги для обслуговування. Найбільш розповсюджений принцип побудови черги грунтується на правилі "першим прийшов – першим обслуговується" (це правило часте позначається абревіатурою FIFO – від англійського First-In-First-Out). Серед інших правил можна вказати правило "останнім прийшов – першим обслуговуєшся" (звичайно позначається як LIFO– від англійського Last-In-First-Out) і дисципліну черги, зумовлену випадковим правилом добору клієнтів. Крім того, клієнти можуть вибиратися з черги відповідно до заданого пріоритету. Інший важливий фактор – поведінка клієнта. Вони при наявності паралельного обслуговування можуть перейти з однієї черги в іншу в надії скоротити тривалість чекання, можуть відмовитися від чекання в черзі, або залишити чергу. Структура обслуговуючої системи може включати один або кілька сервісів, що працюють паралельно. Крім того, сервіси можуть бути розташовані послідовно. Джерело, що генерує "клієнтів" може мати скінченну або нескінченну потужність. Джерело скінченної потужності обмежує число клієнтів, що надходять на обслуговування. Навпаки, джерело нескінченної потужності завжди має клієнтів в достатній кількості. Варіюючи перераховані вище операційні характеристики систем, можна побудувати множину моделей систем масового обслуговування.
23. Експонентний розподіл у системах масового обслуговування
У більшості систем масового обслуговування надходження клієнтів відбувається випадковим чином. Це означає, що настання події (наприклад, надходження клієнта або завершення обслуговування) не залежить від часу, що пройшов з моменту настання попередньої події. При цьому час між послідовними надходженнями клієнтів і час їх обслуговування при моделюванні систем масового обслуговування кількісно описуються експонентним розподілом, щільність імовірності якого має вигляд ,
де .
Експонентний розподіл є абсолютно випадковим і володіє так званою властивістю відсутності післядії або відсутності пам'яті, яка математично формулюється так. Нехай час t настання якої-небудь події розподілено за експонентним законом з функцією щільності f(t). Якщо S – час, що пройшов з моменту настання попередньої події, то властивість відсутності післядії виражається співвідношенням .
При заданій інтенсивності надходжень клієнтів у систему обслуговування і досить малому інтервалі часу h>0 випливає, що .
Тобто на досить малому часовому інтервалі h>0 може настати не більше однієї події (надходження клієнта). Отже, при h→0 .
Цей результат показує, що імовірність надходження клієнта протягом інтервалу h прямо пропорційна h з коефіцієнтом пропорційності, рівним інтенсивності надходжень .
Позначимо через імовірність надходження n клієнтів протягом часу t. Отже, при досить малому h>0 маємо наступне. , .
З першого рівняння випливає, що надходження n клієнтів протягом часу t+h можливе в двох випадках: якщо є n надходжень протягом часу t і немає надходжень за час h або є n–1 надходжень за час t і одне надходження за час h. Будь-які інші комбінації неможливі. Відповідно до умови незалежності стаціонарних приростів до правої частини рівняння застосуємо закон множення імовірностей. В другому рівнянні відсутність надходжень клієнтів протягом інтервалу t+h може мати місце лише у випадку, коли немає надходжень клієнтів за час h.Перегруповуючи члени і переходячи до границі при h→0, одержуємо наступне. , ,
де – похідна по t функції . Розв’язок приведених вище різницево-диференціальних рівнянь має такий вигляд: .
У даному випадку нами отримано дискретну щільність імовірності розподілу Пуассона з математичним сподіванням надходжень за час t. Дисперсія розподілу Пуассона також дорівнює t. Отриманий результат означає, що усякий раз, коли часові інтервали між моментами послідовних надходжень заявок розподілені за експонентним законом з математичним сподіванням , число надходжень заявок в інтервалі, рівному t одиниць часу, характеризується розподілом Пуассона з математичним сподіванням t. Вірним є і зворотне твердження.
У даній моделі передбачається, що система починає функціонувати, коли в момент часу 0 у ній є N клієнтів і не допускається жодного нового надходження клієнта. Клієнти після завершення їх обслуговування вибувають із системи з інтенсивністю клієнтів в одиницю часу. Нехай – імовірність того, що після t часових одиниць у системі залишається n клієнтів. Для одержання різницево-диференціальних рівнянь відносно звичайно додержуються логіки міркувань, використаних у моделі чистого народження (розділ 7.4-1). Тому маємо , , .
Ці рівняння мають розв’язки ,
які називаються усіченим розподілом Пуассона.
Розглянемо загальні системи масового обслуговування, у яких існує як вхідний потік клієнтів, так і вихідний потік обслужених клієнтів. Час між послідовними надходженнями клієнтів і час обслуговування є експонентно розподіленими випадковими величинами. При розгляді загальних систем масового обслуговування передбачається, що система функціонує протягом досить великого інтервалу часу, після закінчення якого в її роботі настає стаціонарний режим. Цей режим функціонування обслуговуючої системи протиставляється перехідному (або невстановленому) режимові, що превалює в самий початковий період функціонування системи. У розглянутій нижче загальній моделі системи масового обслуговування передбачається, що і інтенсивність надходження клієнтів, і інтенсивність вихідного потоку залежать від стану системи, що означає їх залежність від числа клієнтів у системі обслуговування. Введемо наступні позначення. n – число клієнтів у системі обслуговування (у черзі і на обслуговуванні), – інтенсивність надходження в систему клієнтів за умови, що в системі вже знаходиться n клієнтів, – інтенсивність вихідного потоку обслужених клієнтів за умови, що в системі знаходиться n клієнтів, – імовірність того, що в системі знаходиться n клієнтів. У загальній моделі системи масового обслуговування встановлюється функціональна залежність імовірностей від і . Ці імовірності використовуються потім при визначенні функціональних характеристик обслуговуючої системи, таких як середня довжина черги, середній час очікування і середній коефіцієнт використання сервісів. Імовірності визначаються з діаграми інтенсивностей переходів, представленої на рис. 7.3. Обслуговуюча система знаходиться в стані n, якщо в ній є n клієнтів. З аксіом пуассонівського процесу випливає, що імовірність появи більше одного нового клієнта протягом малого проміжку часу h прямує до нуля при h→0. Це означає, що при n>0 стан n може бути змінений в двох можливих напрямках: n–1, коли з інтенсивністю обслужений клієнт вибуває із системи, і n+1, коли має місце надходження клієнта з інтенсивністю . Стан 0 може змінитися лише до стану 1, коли має місце надходження клієнта з інтенсивністю . Зазначимо, що не визначене, оскільки не може відбуватися вибування клієнтів з порожньої системи обслуговування.
Рис. 7.3.
При виконанні умов стаціонарності очікувані інтенсивності вхідного і вихідного потоків у стані n (n>0) повинні бути рівні. Оскільки стан n може змінюватися лише до станів n–1 і n+1, то звідси випливає . Аналогічно,
Звідси, прирівнюючи ці дві інтенсивності, одержимо наступне рівняння балансу. . Як видно з рис. 7.3, рівняння балансу, що відповідає n=0, має вигляд . Рівняння балансу розв’язується рекурентно, послідовно виражаючи імовірності через наступним чином: для n=0 маємо . Далі, для n=1 одержимо .
Підставляючи сюди і спрощуючи отриманий вираз, маємо (перевірте!) . Методом індукції можна показати, що .
Значення визначається з рівняння
27. Спеціалізовані системи обслуговування з пуассонівським розподілом
На рис. 7.4 схематично представлена спеціалізована система обслуговування пуассонівського типу, у якій паралельно функціонують c ідентичних сервісів (засобів обслуговування). Клієнт, що очікує, вибирається з черги для обслуговування на першому вільному сервісі. Інтенсивність надходження клієнтів у систему дорівнює клієнтів в одиницю часу. Усі паралельні сервіси є ідентичними; це означає, що інтенсивність обслуговування кожного сервісу дорівнює клієнтів в одиницю часу. Число клієнтів, що знаходяться в системі обслуговування, включає тих, хто вже обслуговується, і тих, хто знаходиться в черзі. Позначення, які найбільш підходять для характеристик системи обслуговування (рис. 7.4), мають наступну структуру: , де
a – тип розподілу моментів часу надходження клієнтів у систему,
b – тип розподілу часу між появою елементів вихідного потоку (часу обслуговування),
c – кількість паралельно працюючих сервісів (=1,2,...,),
d – дисципліна черги,
e – максимальна ємність (скінченна або нескінченна) системи (кількість клієнтів у черзі плюс число клієнтів, прийнятих на обслуговування сервісами),
f – ємність (скінченна або нескінченна) джерела, що генерує клієнтів.
Рис. 7.4.
Стандартними позначеннями для типів розподілів вхідного і вихідного потоків (символи а і b) є наступні. M – марковский (або пуассонівський) розподіл моментів надходження клієнтів у систему або їх вихід з неї (або еквівалентний експонентний розподіл інтервалів часу між моментами послідовних надходжень або тривалостей обслуговування клієнтів),
D – детермінований (фіксований) інтервал часу між моментами послідовних надходжень у систему клієнтів або детермінована (фіксована) тривалість обслуговування клієнтів,
– розподіл Ерланга, або гамма-розподіл інтервалів часу (або, що те ж саме, розподіл суми незалежних випадкових величин, що мають експонентний розподіл), GI – довільний (загальний) тип розподілу моментів надходження клієнтів на обслуговування, G – довільний (загальний) тип розподілу тривалості обслуговування клієнтів.
Для дисципліни черги (символ d) використовуються наступні позначення. FCFS – першим прийшов – першим обслуговуєшся, LCFS – останнім прийшов – першим обслуговуєшся, SIRO – випадковий відбір клієнтів, GD – довільний (загальний) тип дисципліни. Для ілюстрації розглянемо структуру системи обслуговування, яка відповідає моделі (M/D/10):(GD/N/). Відповідно до прийнятих позначень тут мова йде про систему (і, відповідно, модель) масового обслуговування з пуассонівським вхідним потоком (або експонентним розподілом інтервалів часу між моментами послідовних надходжень клієнтів), фіксованим часом обслуговування і десятьма паралельно функціонуючими сервісами. При цьому дисципліна черги не регламентована, і максимальна кількість клієнтів, що допускаються в систему, дорівнює N. Нарешті, джерело, що породжує клієнтів, має необмежену ємність. В якості історичної довідки зазначимо, що перші три елементи (а/b/c) розглянутого позначення були введені Кендаллом (D.G. Kendall) у 1953 році, і в літературі по теорії масового обслуговування вони фігурують як позначення Кендалла. Пізніше в 1966 році Лі (А.М. Lee) додав до них символи d і e. Автором цієї книги в 1968 році був введений останній символ прийнятих позначень – f. Перед детальним розглядом системи обслуговування пуассонівського типу покажемо, як за допомогою отриманих у розділі 7.5 імовірностей , що відповідають стаціонарному режимові, можна одержати функціональні характеристики системи.
Найбільш уживаними функціональними характеристиками систем масового обслуговування є наступні. – середнє число клієнтів, що знаходяться в системі, – середнє число клієнтів у черзі, – середня тривалість перебування клієнта в системі, – середня тривалість перебування клієнта в черзі, – середня кількість зайнятих засобів обслуговування (сервісів ). Нагадаємо, що система включає як чергу, так і засіб обслуговування. Покажемо, як перераховані функціональні характеристики отримуються (прямо або побічно) з імовірностей – імовірностей того, що в системі знаходиться n клієнтів. Зокрема, маємо наступне. , . Залежність між і (а також між і ) відома в літературі з теорії масового обслуговування як формула Літтла і має вигляд , . Ці співвідношення справедливі при досить загальних умовах. Параметр представляє собою ефективну інтенсивність надходження клієнтів у систему обслуговування. Він дорівнює (вихідній) інтенсивності надходження клієнтів , коли всі прибуваючі клієнти мають можливість потрапити в обслуговуючу систему. Якщо ж деякі клієнти не мають такої можливості з тієї причини, що вона заповнена, то . Пізніше ми покажемо, як обчислюється . Існує також пряма залежність між величинами і . За визначенням
. Математично це записується в наступному вигляді . Тепер можна одержати формулу, яка пов'язує і , помноживши обидві частини останнього співвідношення на і використовуючи формулу Літтла. У результаті одержимо .За визначенням різниця між середнім числом клієнтів, що знаходяться в системі, і середнім числом клієнтів у черзі дорівнює середній кількості зайнятих вузлів обслуговування. Отже, маємо . Тому відсоток використання вузлів обслуговування обчислюється як
Рис. 7.5
Ефективну інтенсивність надходження клієнтів у систему обслуговування можна обчислити з використанням принципової схеми (рис. 7.5), відповідно до якої клієнти з джерела надходять з інтенсивністю . Прибуваючий клієнт може надійти у систему обслуговування з інтенсивністю , або відмовитись від обслуговування з інтенсивністю , тобто . Клієнт не може потрапити на обслуговування, якщо там уже зайняті усі сервіси. Це означає, що частина клієнтів, які не зможуть потрапити на обслуговування, пропорційна . Отже, , .
Розглянемо дві моделі обслуговуючої системи з одним засобом обслуговування (тобто c=1). Передбачається, що клієнти надходять з постійною інтенсивністю . Інтенсивність обслуговування також постійна і дорівнює клієнтів в одиницю часу. Перша модель не встановлює обмежень на місткість системи, у другій моделі передбачається, що місткість системи є обмеженою. У цих двох моделях джерело, що "породжує" клієнтів, має необмежену ємність. Розглянуті тут моделі обслуговуючих систем є окремими випадками систем обслуговування загального виду, розглянутих раніше. Оскільки виведення виразу для і усіх функціональних характеристик обслуговуючої системи виконано незалежно від конкретної дисципліни черги, у позначеннях будемо використовувати символ GD (дисципліна черги не регламентована). Модель (М/М/1): (GD//). Використовуючи позначення загальної моделі, маємо і для всіх n=0,1,2,.... Оскільки відсутні обмеження на ємність черги і, отже, усі прибуваючі клієнти можуть потрапити в систему обслуговування, то і . Позначимо . Тоді вираз для імовірності в загальній моделі приймає наступний вид: .Для визначення величини використовується тотожність Припускаємо, що <1, тоді геометричний ряд має скінченну суму , тому .
Отже, загальна формула для має вигляд .
При виведенні формули для передбачалося, що <1. Це означає, що для досягнення системою стаціонарного режиму функціонування необхідно, щоб інтенсивність надходження клієнтів була строго менше інтенсивності обслуговування . Якщо , геометричний ряд є розбіжним, і, отже, імовірності стаціонарного стану не існує. У цьому випадку система обслуговування буде функціонувати в нестаціонарному режимі, коли довжина черги згодом необмежено зростає. Середнє число клієнтів , що знаходяться в системі обчислюється за формулою:
.
Оскільки в розглянутій моделі , то інші функціональні характеристики обслуговуючої системи обчислюються з використанням розглянутих вище співвідношень, які приводить до наступних результатів. , , , . Розподіл часу чекання в моделі (M/M/1):(FCFS//). Виведення формули для імовірностей у загальній моделі системи обслуговування, розглянутої в розділі 7.5, повністю не залежить від дисципліни черги. Це означає, що математичні сподівання усіх функціональних параметрів , , , і справедливі для системи з будь-якою дисципліною черги. Хоча середній час очікування в системі обслуговування не залежить від дисципліни черги, щільність імовірності його розподілу залежить від дисципліни черги. Проілюструємо це твердження шляхом побудови щільності імовірності часу очікування для моделі (М/М/1) з дисципліною черги FCFS ("першим прийшов – першим обслуговуєшся"). Позначимо через кількість часу, яку тільки що прибулий клієнт проведе в системі від моменту прибуття до завершення обслуговування. Виходячи з дисципліни черги FCFS, якщо в системі вже знаходиться n клієнтів, які надійшли в систему раніше тільки що прибулого, то , де – час, необхідний для завершення обслуговування клієнта, який вже знаходиться в засобі обслуговування системи, а – інтервали часу, що будуть потрібні для обслуговування n–1 клієнтів, що знаходяться в черзі. Величина являє собою час обслуговування тільки що прибулого клієнта. Позначимо через умовну щільність імовірності , де умовою служить наявність в обслуговуючій системі n клієнтів на момент прибуття нового. Оскільки час обслуговування в системі розподілений по експонентному закону, у силу властивості відсутності післядії цього розподілу величина також розподілена за експонентним законом. Отже, являє собою суму n+1 незалежних випадкових величин, кожна з яких підкоряється тому самому експонентному розподілові. Як відомо з теорії імовірностей, функція буде щільністю імовірності гамма-розподілу з параметрами і n+1. Звідси випливає, що
Таким чином показано, що випадкова величина має експонентний розподіл з математичним сподіванням . Модель (М/М/1): (GD/N/). Ця модель відрізняється від розглянутої вище тільки тим, що система вміщає не більш N клієнтів (максимальна довжина черги дорівнює N–1). Ситуація тут така, що як тільки число клієнтів у системі досягає N, жоден з додаткових клієнтів на обслуговування не приймається. З цієї умови випливає, що
Використовуючи позначення , маємо
Значення імовірності визначається з рівняння , що приймає наступний вид:
Звідси одержуємоОтже,
Відмітимо, що в цій моделі значення параметра не обов'язково повинне бути менше одиниці, оскільки надходження клієнтів у систему контролюються максимальною ємністю системи N. Це означає, що в даному випадку як інтенсивність надходження клієнтів скоріше виступає , ніж . Оскільки клієнти будуть загублені в тому випадку, коли в системі знаходиться N клієнтів, тоді , .
Варто очікувати, що буде менше . Середнє число клієнтів у системі обчислюється по формулі
При (перевірте!). Використовуючи значення і , можна також одержати вираз для , і .
Розглянемо тепер моделі систем масового обслуговування з декількома паралельно працюючими засобами обслуговування (сервісами). Модель (М/М/с): (GD//). Ця модель передбачає роботу с паралельних засобів обслуговування. Інтенсивність вхідного потоку клієнтів дорівнює , а інтенсивність обслуговування клієнтів – для кожного сервісу. Оскільки відсутні обмеження на кількість клієнтів у системі, то . Результатом використання с паралельних сервісів є пропорційне збільшення інтенсивності обслуговування клієнтів системою до n, якщо , і до c якщо n>с. Отже, у термінах загальної моделі системи обслуговування і визначаються таким чином. , Отже,
Значення імовірності визначається з рівняння . Позначивши і припускаючи, що , приходимо до наступної формули для : . Вираз для можна знайти так.
.
Оскільки , то ; значення для і можна знайти шляхом ділення на значень і . Модель (М/М/с): (GD/N/), с≤N. Ця модель обслуговуючої системи відрізняється від моделі (М/М/с):(GD//) тим, що ємність системи обмежена зверху значенням N (тоді максимальна довжина черги дорівнює N–с). Інтенсивності надходження і обслуговування клієнтів рівні і відповідно. Ефективна інтенсивність надходження заявок у систему обслуговування менше у силу обмеженості ємності системи значенням N. Параметри і загальної моделі обслуговуючої системи в даній моделі визначаються таким чином:
Підставляючи й у загальний вираз для і використовуючи позначення , одержуємо де
Далі обчислюємо для випадку, коли :
Можна також показати, що для випадку, коли , вираз для має такий вигляд:
. Для визначення і, отже, і необхідно одержати вираз для . Оскільки жоден клієнт не може потрапити в систему після того, як досягнуто ліміт N за її місткістю, то , .
Модель самообслуговування (М/М/): (GD//). У цій моделі кількість сервісів є необмеженою, оскільки клієнт виступає одночасно і у ролі сервісу. Передбачається, що інтенсивність надходження клієнтів є постійною. Інтенсивність обслуговування також є постійною. Скориставшись загальною моделлю, маємо Отже, З рівності випливає, що . У результаті одержуємо Ці імовірності збігаються з імовірностями розподілу Пуассона з математичним сподіванням . Як і слід було очікувати, тут (унаслідок принципу самообслуговування) .