Основні характеристики моделей завдань УЗ

Загальні відомості

ДИНАМІЧНЕ ПРОГРАМУВАННЯ

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

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

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

Перші завдання, які привели до появи методу, були динамічними задачами управління запасами.

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

Елементами задачі УЗ є:

1) система постачання; 2) попит на предмети постачання; 3) можливість поповнення запасів; 4) функції витрат; 5) обмеження; 6) прийнята стратегія управління запасами.

Розглянемо детальніше кожний з елементів.

Системи постачання бувають: децентралізовані (однокаскадні) і централізовані (багатокаскадные).

Попит на предмети постачання може бути: стаціонарний або нестаціонарний; детермінований або випадковий.

Розрізняють способи поповнення запасів: миттєва поставка; затримка поставок на фіксований інтервал часу; затримка поставок на випадковий інтервал часу.

Функції витрат становлять в сукупності критерій ефективності прийнятої стратегії управління запасами й враховують витрати на зберігання, вартість поставок, витрати, пов'язані із замовленням кожної нової партії, витрати на штрафи.

Приведемо можливі варіанти складові функції витрат.

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

Вартість поставки буває: пропорційною обсягу поставки; постійною; пропорційною числу номенклатур; пропорційною необхідному приросту інтенсивності виробництва.

Штрафи бувають таких видів: пропорційні середній позитивній недостачі за період; пропорційні позитивній недостачі до кінця періоду; постійні; нелінійні функції від середньої недостачі й тривалості її існування.

Обмеження в ЗУЗ накладаються: на максимальний обсяг запасів; максимальну вагу; максимальну вартість; середню вартість; число поставок у заданому інтервалі часу; обсяг поставки; імовірність недостачі.

Формально задача динамічного програмування має вигляд:

Знайти max Z =

при умовах a_j >0, x_j 0.

Цільова функція задачі є сумою функцій від однієї змінної. Така функція називається аддитивною. Якщо всі f_і(х_і), i=1,n, — випуклі (увігнуті), то для рішення може бути застосований метод множників Лагранжа. Однак, якщо є багато локальних максимумів, то цей метод дає лише одне з таких рішень. У випадку, якщо потрібно знайти глобальний максимум, використається наступний метод.

Передбачається, що всі {а_j), j=1,...,n I b — цілі числа, а змінні {x_j} можуть приймати тільки цілочисельні значення.

Приклад задача динамічного програмування. Є х — кількість капітальних вкладень, які необхідно розподілити між двома галузями. Кількість капітальних засобів у, вкладене в першу галузь, за рік приносить прибуток g(у) = 0,8y. Частка капітальних засобів x-y, вкладених у другу галузь, приносить за рік доход h(x-y) =0,5(x-y). Під кінець року засоби, вкладені в першу галузь, складуть а(у) = 0,3у, а для другої галузі ця величина складе b(x-y) = 0,6(x-y). Після закінчення кожного року капітальні вкладення, що залишилися, заново розподіляються між галузями. Необхідно встановити розподіл таким чином, щоб сумарний прибуток за три роки був максимальним.

Отже, спочатку шукають величину у₂ — кількість засобів, вкладених у третій рік, потім y₁ й у₀ (відповідно для другого й першого років). Відповідно до принципу оптимальності, незалежно від величин у₁ та у₀, а також х₂ — кількість ресурсів, отриманих до початку третього етапу, необхідно щонайкраще використати доступну кількість ресурсів, тобто вирішити задачу

0у₂х₂

або

.

0у₂х₂ 0у₂х₂

Очевидно, max можливий при х₂=у₂.

Отже, всі ресурси на останньому етапі потрібно направити в першу галузь. При цьому буде отриманий прибуток f₁ (х₂)=0,8х₂.

Тепер знайдемо у₁. Розглянемо двокроковий процес - останній і передостанній етапи.

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

.

0у₁х₁

Тут — прибуток на передостанньому етапі при y₁, a — максимальний прибуток на останньому етапі при тій же умові.

Необхідно вибрати y₁[0,х₁] таке, щоб у дужках одержати максимум.

По відомому f₁ отримуємо

0у₁х₁

0у₁х₁

_.

0у₁х₁

Звідси f(x₁)=1,04x₁ та y₁=x₁.

Виходить, на передостанньому етапі також всі капітальні вкладення повинні бути спрямовані в першу галузь.

Аналогічно, для першого етапу

0у₀х₀

0у₀х₀

0у₀х₀

Тут максимум досягається при у = 0. Отже, найбільший сумарний доход за всі етапи складе f₃(x)= 1,124.

На першому етапі всі ресурси необхідно направити в другу галузь: у = 0.

Значить: Оптимальна стратегія

Уо=0, y₁=х₁, у₂=х₂.

I етап: всі ресурси — у другу галузь і прибуток становитиме h(x) = 0,5x.

Залишиться під кінець року b(х) — 0,6х капітальних вкладень, які будуть спрямовані в першу галузь і дадуть прибуток g(0,6х) =0,8*0,6х =0,48х.

Залишок ресурсів при цьому складе а(0,6х) = 0,3*0,6х = 0,18х.

Прибуток на третьому етапі: g(0,18х) =0,8*0,18х =0,144х,

А сумарній прибуток рівний 0,5х+0,48х+0,144х=1,124х

Продемонструємо процес рішення завдання в наймі робітників на конкретному прикладі:

Для функціонування деякого підприємства протягом чотирьох місяців (пронумерованих від 1 до 4) по нормах потрібні наступні кількості працівників однакової кваліфікації,:

причому перед початком першого місяця (у нульовому місяці) фактично є співробітника. Адміністрація планує наприкінці кожного місяця k (крім останнього) коректувати число працюючих на величину x_k, , х₄=0. На прийом одного співробітника необхідно затратити 9 у.е., а на звільнення - 6 у.е. Передбачається, що витрати на утримання надлишкового працівника становлять 8 у.е., а у випадку недостачі персоналу доводиться нести витрати в розмірі 12 у.е. за кожне вакантне місце.

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

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

Оцінки ефективності керування на кожному кроці приймають вигляд:

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

(5-22)

і функції мінімальних витрат у залежності від поточного стану

(5-23)

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

Ітерація 1. Візьмемо, що k = 4. На даному етапі функція стану може бути знайдена безпосередньо, якщо врахувати, що =0 і и( 0) = 0:

Таблиця значень даної функції й умовні оптимальні керування мають вигляд

Ітерація 2. Приймаємо, що k = 3. Попередньо заповнимо таблицю значень функції для досить великої кількості аргументів відповідно до формули:

							-1
	-2	-1		-3	-2	-1	-4	-3	-2

Вибираючи мінімальні по х ₃ значення , складемо таблицю і відповідні значення умовних оптимальних управлінь :

				-1	-2	-3

Ітерація 3. Приймемо, що k = 2. Так само, як на попередній ітерації, заповнимо таблицю значень функції відповідно до формули:

							-1
	-1			-1			-1

Вибираючи мінімальні по х ₂ значення , складемо таблицю і відповідні значення умовних оптимальних керувань:

Ітерація 4. Приймаємо, що k = 1. Аналогічно попередньому, заповнимо таблицю значень функції відповідно до формули:

				-1

Вибираючи мінімальні по х ₁ значення , складемо таблицю і відповідні значення умовних оптимальних керувань :

Ітерація 5. На останній ітерації, у зв'язку з наявністю початкової умови, досить обчислити

і знайти як точку мінімуму . Прості обчислення показують, що мінімум

досягається при (2) = 1.

Отже, , після чого зворотним ходом послідовно обчислюються оптимальні керування й оптимальні стани (оптимальна траєкторія):

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

Лінійне програмування

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

Вираз для цільової функції в загальному вигляді може бути представлений так;

(j=1,2,…n), (2.10)

Де - задані постійні коефіцієнти.

Вираз (2,10) називається лінійною формою. На вибір оптимальних значень змінних накладаються допоміжні умови, які встановлюють зв'язок між оптимізуючими змінними (вони можуть включати в себе як рівність, так і нерівність):

(2,11)

Коефіцієнти в (2,10) і у виразі (2,11) являються дійсними числами і можуть позитивними та негативними, серед них можуть бути і рівні нулю. Число обмеженого типу рівнянь не повинно перевищувати загального числа оптимізуючих змінних в лінійній формі. Число нерівностей може бути будь-яким.

В задачах лінійного програмування пропонують, що оптимізуючі змінні позитивні,

>0, j=1,2,….n. Також вважають, що всі величини у виразі (2,11) відрізняються від нуля і позитивні. Якщо якесь значення буде позитивним, то, перемножуючи ліву і праву частини відповідного рівняння на -1, його приводять до вигляду, коли права частина приймає позитивне значення. Якщо якесь значення буде дорівнювати нулю, то в ліву і праву частини відповідного виразу (2,11) добавимо доданок , що робить величину більшою від нуля. При цьому вважають що добавлений доданок увійшов лінійну форму (2,10), але з нульовим коефіцієнтом , що не змінило вираз для цільової функції.

Для скорочення виразу (2,11) може бути представлено у вигляді…

, і=1,2,…m, j=1,2,….n (2,11а)

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

Вважають, що оптимум досягається при максимальному значенні лінійної форми. Випадок, коли необхідно знайти мінімальне значення лінійної форми, може бути приведено до задачі максимізації шляхом зміни знаків у всіх коефіцієнтах (j=1,2,…n).

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

Розглядається вираз в якому n=2, c1=1, x1,x2 тип рівності

(б)

Та нерівність

(в)

У виразі (б) згідно (2,11)

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

На малюнку 2,10 лінії, обмежуючі розглянуту область Х, заштриховані з зовнішньої сторони.

У відповідності зі структурою лінійної форми (2,10) та (а) похідні від критерію оптимальності по оптимізуючи змінним постійні, неперервні та не перетворюються в області Х в нуль:

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

На рис(2,10) ця лінія зображена для значення l=0,4. Якщо її переміщувати на площині () паралельно самій собі в напрямку, указаною стрілкою, то значення l, а відповідно, і величина цільової функції будуть збільшуватись.

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

Підставивши отримані значення оптимізуючи змінних (д) в рівнянні лінійної форми (а) дозволяє визначити максимальне значення цільової функції

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

Якщо для умови попереднього прикладу при обмеженнях +=1, +=1, 0, 0 цільова функція буде мати вигляд R = +, то максимум функції буде мати місце по лінії АК (див. мал. 2.10). В цьому випадку рівняння для лінії lмає вигляд

l= += 0,4. Оскільки обмеження типу рівність залишилися незмінними, значення та також не змінилися, максимальне значення цільової функції буде , причому це значення цільової функції може бути досягнуто при всіляких поєднаннях та , які задовольняють відрізок АК.

У розглянутому прикладі система обмежень описує замкнуту область можливих значень оптимізуючих змінних. Інколи система обмежень може визначити і незамкнену область. Так, якщо обмеження описуються виразами , , 0, 0 (мал. 2.11), то цільова функція виду досягне максимуму при нескінченно великих значеннях та , так як можливості переміщення лінії l = +(l = 0,25) у напрямку збільшення R не обмежені.

В той же час, при незамкненій області зміни змінних максимум цільової функції може лежати і не у нескінченності. Якщо при перерахованих вище обмеженнях цільова функція має вигляд R = , то переміщення лінії lобмежено. Розв’язуючи систему рівнянь , можна обчислити значення ,та визначити максимальне значення цільової функції

В загальному випадку випадкового числа п оптимізуючих змінних геометрична інтерпретація задачі неможлива. Область допустимих значень змінних у п – мірному просторі являється багатогранником, обмеженим гіперплощиною, зрівнювання яких задаються обмеженнями (2.11); Поверхня, вздовж якої критерій оптимальності має постійне значення, буде представляти собою також гіперплощиною, яка визначається конкретним видом виразів (2.10).

Основні поняття для вивчення СМО

- потік заявок;

- система обслуговування;

- час обслуговування;

- порядок обслуговування;

- черга;

- критерій оцінки системи.

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

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

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

Для цього потоку ймовірність надходження за проміжок часу τ рівно k вимог визначається формулою Пуассона

Інтенсивність цього потоку, тобто математичне очікування числа вимог, що надійшли в одиницю часу, дорівнює величині параметра X. -

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

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

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

де? - величина, зворотна середнього часу обслуговування.

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

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

При оцінці систем масового обслуговування найчастіше розглядають сталий процес, формули для якого не дають істотних помилок при загальній тривалості розглянутого процесу не менше ніж (2-3)μ.

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

Найважливішими критеріями систем масового обслуговування є:

· імовірність пропуску (затримки в обслуговуванні) заявки;

· математичне очікування числа пропущених (затриманих) заявок за фіксований час;

· математичне очікування числа зайнятих каналів;

· математичне очікування довжини черги.

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

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

Дата добавления: 2013-12-14