Лекції - Дослідження операцій - файл n1.doc

приобрести
Лекції - Дослідження операцій
скачать (592 kb.)
Доступные файлы (1):
n1.doc592kb.05.06.2012 07:14скачать
Победи орков

Доступно в Google Play

n1.doc

Тема 1.Предмет і метод дослідження операцій.
Дослідження операцій (ДО) – це наука, яка займається розробкою і транспортним застосуванням методів оптимального управління, організаційними системами.

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

Головний метод дослідження операцій – системний аналіз.

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


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

  2. командна форма проведення дослідження, заснована на спільній роботі спеціалістів різного профілю;

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

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


Пряма постановка дослідження операцій:
Що буде, якщо за заданих умов ми оберемо конкретний розв’язок із множини можливих.
Обернена задача
Яке значення (варіант) рішення необхідно обрати, щоб досягти певного результату.
;

;





Типові задачі дослідження операцій:


  1. розподільні (розподілення ресурсу);

  2. управління запасами;

  3. масового обслуговування;

  4. упорядкування й узгодження (задачі планування та управління на мережах і задачі формування розкладів);

  5. задачі маршрутизації;

  6. задачі ремонту або заміни обладнання;

  7. задачі пошуку;

  8. задачі прийняття рішень у конфліктних ситуаціях (теорія порядку);

  9. задачі розміщення;

  10. задачі змішаного типу.


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


  1. Постановка проблеми

    1. Виявлення проблеми (ідентифікація);

    2. Формування цілей і критеріїв;

    3. Аналіз проблеми та її повна якісна постановка, формування концептуальної моделі;

    4. Побудова математичної моделі.




  1. Пошук оптимальних рішень:

    1. Розв’язання математичної моделі з однією або декількома цільовими функціями;

    2. Синтез оптимального розв’язку.




  1. Прийняття та реалізація рішення:

    1. Оцінка оптимального результату;

    2. Корегування моделі;

    3. Ухвалення рішення;

    4. Впровадження прийнятого рішення.

Тема 2. Розподільчі задачі.

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

Загальна постановка задач.

Нехай убудь-якій економічній системі є в наявності: m видів ресурсів, які можуть бути використані для здійснення n видів операцій (робіт).

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

Розподільчу задачу легко представити у вигляді таблиці:



Види

ресурсів

Операція, яку необхідно виконати

О1

О2

...

Оn

Об’єм наявних ресурсів

R1

С11

С12

...

С1n

b1

R2

С21

С22

...

С2n

b2

Rm

Сm1

Сm2

...

Сmn

bm

Обсяг необхідних ресурсів

a1

a2

...

am

? bm
? am




- обсяг виконаної роботи;

- функція витрат і-го виду ресурсу на j-тий тип операції.



- результат від розподілу ресурсів за операціями.
Іноді, економічно-математична модель в розподільчому виді має вигляд:



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


  1. за визначеністю параметрів моделі:

- детерміновані;

- стохастичні;

  1. за урахуванням фактору часу:

- статичні;

- динамічні;

3) за видом функцій :

- лінійні;

- нелінійні;

4) за областю та множиною допустимих значень змінних:

- дискретні;

- неперервні ();

5) за кількістю ресурсів:

- однопродуктові;

- багатопродуктові;

6) за сферою використання:

- виробничі;

- транспортні;

- призначення;

- розміщення;

- маршрутизації та ін.

7) задача формування виробничої програми підприємства.

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

- види ресурсів;

- види продукції.

Відомі норми витрат на виготовлення одиниці продукції кожного виду

mxn

Для кожного виду продукції відома ціна реалізації Цj . Позначимо через Хj невідому величину, яка означає обсяг доцільного виробництва j-го виду продукції. При таких даних математична задача має вид. Необхідно знайти оптимальний обсяг роботи кожного виду, щоб сумарна вартість виготовленої продукції була найбільша:
ЦХ1 + ЦХ2 + ЦХ3 + ... + ЦпХп max

C11­Х1 + C12­Х2 + C13­Х3 + ... + C1nХп b1

C21­Х1 + C22­Х2 + C23­Х3 + ... + C2nХп b2

..................................................................

Cm1­Х1 + Cm2­Х2 + Cm3­Х3 + ... + CmnХп bm





(Ц,Х);

Сх

х



х=

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

Нехай існує m пунктів, де зосереджені запаси цієї продукції (пункт відправки постачання).

Нехай існує п споживачів цієї продукції, які розміщені в різних пунктах (пункт призначення споживання).


а1 1.

а2 2.

аm m.




Нехай задані величини - витрати на одиницю продукції, на перевезення з і-го пункту постачання до j-го пункту призначення. Визначимо змінні обсяги перевезення продукції із і-го пункту постачання до j-го пункту призначення:











В класичній транспортній задачі критерієм оптимальності може бути час перевезень, пункт перевезень.
Задача про призначення.
Нехай існує на деякому підприємстві m вакантних посад, на які претендує п кандидатів. Допустимо, що ми можемо оцінити ефективність будь-якої посади будь-яким кандидатом. - ефективність використання j-тим кандидатом і-тої посади.










0 або 1




Задача про розміщення виробничих потужностей.

Нехай розглядається m можливих пунктів для розміщення виробництва деякого виду продукції. Нехай аі – максимальна потужність в і-тому пункті. Продукція із можливих пунктів поставлення п-споживачам, для кожного з яких відома потреба bj. Необхідно знайти пункти виробництва та схеми перевезень. Позначимо Хі - доцільний обсяг виробництва в і-тому пункті, а - обсяги перевезень продукції від і-того виробника до j-того споживача.
;

;

;

;

.
Тема 3.Основи оптимального управління

запасами.

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

Запас – це будь-який ресурс, який використовується для задоволення поточної або майбутньої потреби.

Загальна постановка задачі в ОУЗ:

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

В класичній постановці задач ОУЗ критерієм оптимальності є мінімізація сукупних витрат, які складаються з трьох основних частин:

  1. Витрати, пов’язані із створенням і формуванням запасів.

  2. Витрати, пов’язані з утриманням або зберіганням запасів.

  3. Витрати з дефіцитом:

    • потенційні витрати;

    • витрати, пов’язані із створенням надлишкових запасів, коли обсяг запасів переважає обсяг споживання;

    • потенційна упущена вигода, коли обсяг запасів менший за обсяг споживання.





Класифікація задач управління запасами за ознаками:


  1. за фактором знаходження (часу):




  1. за кількістю видів ресурсів або запасів:

  1. за наявність обмежень:

  1. за типом попиту:

  1. за способом поповнення запасів:

  1. за функцією витрат:


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


  1. Найпростіша однопродуктова модель управління запасами без дефіциту. Модель Уілсона. Зробимо припущення:

  1. Поповнення запасів здійснюється однаковими партіями розміром .

  2. Витрати на формування запасів не залежать від розміру формування запасів і є сталою величиною К .

  3. Витрати на утримання запасів пропорційні обсягу наявних запасів – з коефіцієнтом пропорціїs - витрати на утримання одиниці запасу в одиниці часу.


Запаси



t

1 2 3 4


Витрати

С витрати зберігання
К

Запаси


Cцикл=;

Cпит=;

;

;


- модель Уілсона

;

;

;

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

Споживання здійснюється рівномірно ,



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

S=s * t


Модифікація моделі Уілсона
1. Узагальнена модель Уілсона без дефіциту с поступовим поповненням запасів (із затримкою):











- за винятком поповнення здійснюється дрібними партіями з іншим .

період накопичення запасів;

їх споживання.


2. Модель Уілсона з дефіцитом і з обміном незадоволених умов.

d - дефіцит





- дозволяється дефіцит запасів, витрати дефіциту.



3. Модель Уілсона з дефіцитом з обліком незадоволених вимог із затримкою поповнення.











- період накопичення запасів;

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

- період ліквідації;

- період накопичення дефіциту.
4. Модель з дефіцитними витратами незадовільних умов із затримкою поповнення.

5. Багатопродуктова модель Уілсона без дефіциту, роздільна оптимізація.

n,i,m

- нехай відомі інтенсивність споживання кожного виду ресурсу;

витрати на поставку кожного виду ресурсу;

- витрати на одиницю запасу.

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

,
- сукупні витрати.

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

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

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

Класифікація задач заміни обладнання:

  1. за характером заміни устаткування:




  1. за характером обліку витрат на устаткування:

  1. у разі виходу обладнання з ладу:

  1. за стратегіями заміни устаткування:

  1. За часом обліку витрат на устаткування:


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

Позначимо через:

S0 – купівельну ціну устаткування;

Ct – витрати на експлуатацію обладнання в t- му році;

- балансова вартість устаткування в t- му році.












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





Заміна устаткування з метою упередження відмов.

Позначимо :

витрати, пов’язані із відмовою обладнання, включаючи заміну;

витрати на заміну устаткування (попереджувальні).

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

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

Основною кількісною характеристикою безвідмовності є ймовірність безвідмовності роботи.



кількість обстеженого устаткування;

кількість справного устаткування.

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



Розрахунок середніх витрат за одиницю часу, при заміні устаткування віком :



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

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

Будь-яка система масового обслуговування представляє собою сукупність запитів або вимог на обслуговування, і об’єктів, що здійснюють обслуговування.

Об’єкт, що виконує вимоги обслуговування називається обслуговуючим апаратом, або каналом обслуговування.

Будь-яка система масового обслуговування складається з двох підсистем:


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

середня тривалість черги. Кількість вимог, які очікують обслуговування.

Вхідний потік – це поті вимог, що надходять до системи.

Вихідний потік – це той, що покидає систему. Вимоги, які ми задовольнили.
Класифікація систем масового обслуговування:

  1. за кількістю каналів обслуговування:

- одноканальні;

- багатоканальні.

  1. за реакцією системи на чергову вимогу, що надійшла в систему в момент, коли всі канали обслуговування зайняті:

  1. чисті системи масового обслуговування:

  1. за місцем знаходження джерела вимог:

  1. за потужністю:

  1. за дисципліною черги:


Ефективність систем масового обслуговування.

Основними показниками ефективності функціонування систем масового обслуговування є:

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

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

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

  1. системи масового обслуговування, які обслуговують з відмовами

- - кількість вимог, що отримали відмову в обслуговувані;

- - середня кількість каналів, що простоюють;

- коефіцієнт зайнятості;

- коефіцієнт постою.

;

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

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

Моделі системи масового обслуговування.

  1. вхідний потік вимог є стаціонарним, ординарним і в системі відсутня післядія;

  2. процес обслуговування є неперервним;

  3. вхідний потік вимог розраховується по закону Пуассона, а вихідний – по Показовому.

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



приведена інтенсивність, відносно вхідного до вихідного потоку.

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









система вільна.


всі канали зайняті


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

- коефіцієнт зайнятості.
Система масового обслуговування з обмеженою чергою









- довжина черги








; ; k – номер в черзі;



Тема 6. Основи теорії ігор.
Теорія ігор – це математична теорія конфліктних ситуацій, яка дозволяє розробити рекомендації, щодо найбільш раціонального способу дій будь-якого учасника конфліктної ситуації.

Конфліктна ситуація – це така ситуація, в якій зіштовхуються інтереси двох і більше сторін, що мають різні цілі.

Гра - це математична модель конфліктної ситуації, яка розвивається за певними правилами.

Гра – це певний набір правил, угод, або домовленостей, що визначають можливі дії учасників конфліктної ситуації.

Правила гри включають:

  1. порядок чергування дій учасників конфліктної ситуації (хід);

  2. правила виконання кожного ходу;

  3. кількісний результат гри (виграш або програш) до якого призводить вказана сукупність ходів;

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

Вибір одним із гравців своєї стратегії, називається ходом.

Партія – можлива реалізація правил гри.

Результат гри – значення деякої функції, яка може бути задана аналітично або таблично (матрично).

Класифікація задач теорії ігор.

  1. за кількістю сторін в конфлікті:

  1. за кількістю ходів:

  1. за кількістю стратегій:

  1. за кількісним результатом гри:

  1. за правилами гри і наявністю стратегії:

  1. за наявністю інформації:


Матричні ігри з нульовою сумою.

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





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



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

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

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

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

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

min max aij = - ціною гри для гравця А;

max min aij = - ціною гри для гравця В.

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

(i,j)aj = max min aij - оптимальні чисті стратегії гравців А і В.



Стр. А

1

2

3

4




1

5

3

4

3

5

2

3

2

2

4

4

3

4

4

5

2

5

max

3

2

2

2





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

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

умовам =
Змішаною стратегією


Числа та представляють собою імовірності вибору гравцем А чистої стратегії і

і, відповідно, гравцем B – чистої стратегії j.

Значення - оптимальні змішані стратегії гравців, якщо виконується умова:





aij

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

Тема 6. Критерії.


  1. Критерій Вальда (критерій крайнього песимізму) – оптимальною за Вальдом вважається така стратегія статистики, яка розрахована на основні припущення, що природа реалізує несприятливий для цього стан.



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



  1. Критерій Лапласа. Заснований на рівновеликості всіх ймовірностей. Для кожного рядка розраховують середнє значення і по максимальній величіні визначають оптимальну стратегію.

  2. Критерій оптимізму Гурвіца.




де К=0 ...1 – коефіцієнт оптимізму;

- мінімальне значення у і-му рядку;

- максимальне значення у і-му рядку;

крайній песимізм;

крайній оптимізм.

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















S1

5

6

8

S2

3

4

9

S3

7

2

6

S4

4

8

2

S5

5

7

4
;

;

;










S1

2

2

1

S2

4

4

0

S3

0

6

3

S4

3

0

7

S5

2

1

5


2

4

6

7

5
За Лапласом - ;

За Баєсом – 6;

За Вальдом – 5;

За Севіджом – 2.

- оптимальною є стратегія S1.

Тема 1 .Предмет і метод дослідження операцій
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации