Загальні відомості про дослідження операцій

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

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

Як самостійний науковий напрямок дослідження операцій оформилося на початку 40-х років. Перші публікації з досліджень операцій з'явилися у 1939-1940 pp. А на період Другої світової війни США використовували науковців, які давали поради військовим щодо прийняття рішень при аналізі та дослідженні військових операцій. Звідси і виникла назва дисципліни.

Пізніше принципи і методи дослідження операцій (ДО) стали використовуватися у цивільній сфері: у промисловості, для управління фінансами, у сільському господарстві та ін.

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

Головні етапи дослідження операцій:

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

Етап 2. Формалізація задачі у вигляді математичної моделі.

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

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

- лінійне програмування, якщо F_i = f (Χ, Υ) та g i (Χ, Υ) £ b i - лінійні функції відносно Χ, Υ;

- нелінійне програмування, якщо F_i = f (Χ, Υ) або g i (Χ, Υ) £ b i, нелінійні функції відносно Χ, Y;

- динамічного програмування, якщо F_i = f (Χ, Υ) с адитивною або мультиплікативною функцією від змінних (Χ, Υ);

- дискретного програмування, якщо на змінні Χ, Υ накласти умови дискретності (наприклад - цілочислового рішення);

- стохастичного програмування, якщо Υ - випадкова величина, а замість функції мети F_i = f (Χ, Υ) розглядають її математичне очікування.

Етап 4. Перевірка та коригування моделі. Перевірка виконується порівнянням поведінки моделі з фактичним її поводженням.

Етап 5. Реалізація на практиці.

Отримане на базі дослідження операцій рішення має свої особливості:

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

2. Системний підхід: будь-яка задача розглядається з точки зору її впливу на критерії функціонування всієї системи.

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

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

У своїй сукупності методи ДО вміщують цілий арсенал математичних засобів:

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

-  теорію ігор;

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

- прийняття рішень в умовах нечіткої інформації;

- теорію експертних систем;

- теорію ефективності та ін.

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

 

Теорія черг

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

                                                         

 

 

Рис. 3.2. Модель n - канальної СМО

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

Таким чином, СМО має дві головні ознаки: обслуговуючий пристрій і чергу.

СМО розрізняються:

1. За конструкцією обслуговуючого пристрою: Одноканальна, багатоканальна.

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

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

Для отримання математичної моделі СМО потрібно знати:

- конструкцію СМО;

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

- математичний опис обробки замовлень.

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

Основні рівняння СМО

Закон Бернуллі. В основі аналізу СМО лежить біноміальний закон Бернуллі, який дозволяє розраховувати ймовірність появи події "А" точно К разів при n незалежних спостереженнях (тільки для дискретних випадкових взаємно несумісних незалежних подій):

         (3.5)

                                             (3.6)

де  - кількість незалежних спостережень;

- ймовірність появи подій "А" точно К разів при  незалежних спостереженнях;

 - ймовірність появи однієї події "A";

- ймовірність протилежної події (не появи події "А");

 К - кількість появи події "А" при n спостереженнях;

- сполучення по К елементів із n спостережень.

Властиво­сті сполучення:

У принципі закон Бернуллі (і закони Лапласа та Пуассона, що з нього випливають) може використовуватись для визначення конструк­ції СМО - кількості каналів обслуговування та середнього терміну об­слуговування одного замовлення.

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

                            (3.7)

Формула Лапласа. Подальші перетворення формули Бернуллі дозволяють отримати формулу Лапласа:

                          (3.8)

де,

Із формули Лапласа випливає, що при або при (тут - найімовірніша кількість подій "А") отримуємо:

            (3.9)

і ймовірність найімовірнішого числа подій К0 дорівнює:

                       (3.10)

З точністю до (тобто з ймовірністю 0,997) можна вважати, що всі події відбудуться, якщо виконується умова , або .

Диференційні рівняння СМО

Стан Si СМО визначається:

- в одноканальній СМО з очікуванням - довжиною черги і;

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

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

Для побудови диференційного рівняння СМО для деякої і-ї вершини графа використовують правило Колмогорова для і -го стану  з імовірністю існування :

Граф станів СМО описується диференційними рівняннями:

………………………………………………

………………………………………………

з якої випливає інша система рівнянь:

………………………………………………

……………………………………………….

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

                      ………………………………………….….

………………….

де,

Рішення цієї системи рівнянь для статики має вигляд:

Звідси отримуємо ймовірність простоювання СМО:

3.2.2. n-канальна система масового обслуговування з відмовами

Розглянемо множину станів системи:  - усі канали вільні, жодне замовлення не обслуговується;  - зайнятий лише один канал (який не важливо), обслуговується одне замовлення; …; - зайнято (які саме – не важливо), обслуговується замовлень; …; - зайнято  каналів, обслуговується замовлень

Ймовірність перебування СМО у - стані (одночасної роботи каналів) знаходимо за формулою:

               (3.12)

де,

Ймовірність відсутності замовлень P₀ знаходиться з виразу суми ймовірностей для повної групи взаємно несумісних подій

                                      (3.13)

 (3.14)

Ймовірність обслуговування замовлень

Ймовірність відмови в обслуговуванні визначається ймовірністю того, що зайняті всі n каналів (і = n):

                                     (3.15)

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

                   (3.16)

 

3.2.3. Одноканальна СМО з очікуванням

Під станом таких СМО розуміють загальну кількість замовлень (сумісно у черзі та у каналі обслуговування). Інтенсивність надходжен­ня замовлень const та обслуговування замовлень const не залежить від ста­ну СМО

Ймовірність перебування СМО у - стані знаходимо за формулою:

               (3.17)

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

                 (3.18)

Тут ми використовуємо відоме з математики рівняння:

                  (3.19)

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

Ймовірність обслуговування замовлення  

Відмови в обслуговуванні немає, бо черга може бути нескінченно великою.

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

                      (3.20)

При великій величині  значення:

                                 (3.21)

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

            (3.22)

Середня довжина черги .

Середній час очікування обслуговування  (тому що середній термін обслуговування однієї вимоги дорівнює

 

3.2.4. Багатоканальна СМО з очікуванням

Потік замовлень до СМО має постійну інтенсивність const, а інтенсивність обслуговування замовлень - канальної CMC

Система зберігає працездатність, якщо (див. нижче)

Рис. 3.7 - канальна СМО з очікуванням

Ймовірність знаходження СМО у - стані знаходимо за форму­лами для двох варіантів:

1. Для  (стан  визначається кількістю зайнятих каналів обслуговування)

           (3.23)

де,

2. Для

(3.24)

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

Ймовірність відсутності вимог  знаходиться з виразу суми ймовірностей для повної групи взаємно несумісних подій з врахуван­ням двох можливих варіантів станів СМО

(3.25)

де - загальна максимально можлива кількість станів СМО (звичайно вважається, що

якщо , то використовується попередній аналіз багатоканальної СМО без черг);

- загальна максимально можлива величина черги (якщо то і черга нескінченна).

Якщо  то для знайдених співвідношення  приймає вигляд:    (3.26)

Вважаємо, що

               

і тоді:

                 (3.27)

Ймовірність обслуговування зам овлень

Відмови в обслуговуванні немає, бо черга може бути нескінченно великою.

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

                    (3.28)

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

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

                      (3.29)

Середня довжина черги:

                  (3.30)

Середній час очікування обслуговування (тому що середній термін обслуговування одного замовлення дорівнює ).

Теорія ігор.