ID: 11775

Название работы: Предмет та задачі дослідження операцій

Категория: Реферат

Предметная область: Информатика, кибернетика и программирование

Описание: Предмет та задачі дослідження операцій Предмет та історія виникнення дослідження операцій ДО. Основні поняття ДО та етапи операційного дослідження Пряма та обернена задачі ДО. Детерміновані задачі ДО. Проблема вибору розвязків в умовах невизначеності. ...

Язык: Украинкский

Дата добавления: 2013-04-11

Размер файла: 165 KB

Работу скачали: 35 чел.

1.  Предмет та задачі дослідження операцій
2.  Предмет та історія виникнення дослідження операцій (ДО).
3.  Основні поняття ДО та етапи операційного дослідження
4.  Пряма та обернена задачі ДО. Детерміновані задачі ДО.
5.  Проблема вибору розв’язків в умовах невизначеності.
6.  Основні класи задач дослідження операцій.
   1.  Предмет та історія виникнення дослідження операцій

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

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

Початки ДО, що виявлялися в науковому мисленні, близькому до операційного, з’явилися досить давно. Першою ігровою задачею, відомою з літератури, була задача про справедливий розподіл ставки між двома гравцями в кості, поставлена в кінці XV-го століття італійським математиком Лукою Пачіолі (1445—1514, відомий як винахідник двійкової системи числення) на прохання відомого гравця кавалера де Мере. Ця задача була розв’язана в частковому вигляді через 150 років  французьким математиком та фізиком Блезом Паскалем (1623—1662). Через три роки голандський вчений Христіян Ґюйґенс (1629—1695) незалежно від  Блеза Паскаля розв’язує цю задачу в загальному вигляді.

В 1838р. була опублікована книга французького економіста Антуана Курно (1801—1847) “Дослідження математичних принципів теорії багатства”, в якій вперше були сформульовані умови економічної конкурентної рівноваги. Леон Вальрас в книзі “Елементи чистої політичної економії, або теорія суспільного багатства” багато в чому повторив висновки Курно.

В 1906 році італійський математик та соціолог, інженер за освітою Альфредо Парето (1848—1923) видав в Мілані “Підручник політичної економії” та математичний додаток до нього, в якому викладено основні положення аналітичної теорії ігор. Подальший значний внесок в розвиток ігрових моделей був зроблений в 1937-му році вченим-еміґрантом з Угорщини Дж. фон Нейманом, який працював у США.

Термін “Дослідження операцій” виник в роки 2-ї світової війни. В 1935-му р. в Великобританії розпочалася розробка системи виявлення літаків (радіолокаційної системи), що було пов’язане з загрозою з боку військово-повітряних сил Німеччини. На протязі наступних трьох років підтвердилася технічна працездатність розвинутих засобів виявлення та створені практичні методи слідкування за літаком і повідомлення про його появу. Однак з метою підвищення ефективності операцій перехоплення британська винищувальна авіація відчувала потребу в системі супроводу та наведення літаків-перехоплювачів. Тому незалежно (внаслідок секретності)  від робіт зі створення системи виявлення на початку 1936-го – в кінці 1937-го р. були початі експерименти з виявлення моделей ворожих літаків та з іншого боку, відслідковування та наведення власних літаків-перехоплювачів.

До кінця 1937-го р. обидві системи —  виявлення та супроводу одиночного атакуючого літака суперника та система супроводу та наведення взаємодіючих перехоплювачів —  почали розроблятися сумісно, що було викликане необхідністю забезпечення узгоджених операцій всіх учасників бойових дій в повітрі та на землі. В цей же час (1938р.) в групі дослідників, що керувалася А. Раувом, почав вживатися термін “операційне дослідження”. В 1942-му р., коли в війну вступили США, аналогічна ґрупа була створена й там (керівником був Ф. Морз —  фізик з МТІ — а керівником дослідницької ґрупи був призначений Уільям Шоклі з Bell Telephone Laboratories, який в подальшому отримав Нобелівську премію як винахідник транзистора). Аналоґічний відділ був сформований і в Канаді. Загальна кількість таких вчених в часи 2-ї світової війни налічувала у вищезгаданих країнах біля 700 осіб. В той же час держави осі Берлін-Рим-Токіо не застосовували методи дослідження операцій.

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

В 1938-1939рр. ленінґрадський математик (в подальшому академік) Л. В. Канторович в результаті аналізу багатьох проблем орґанізації та планування виробництва сформулював клас умовно-екстремальних лінійних задач  та запропонував методи їх розв’язування, що поклало початок лінійному проґрамуванню.

В 1947-му р. незалежно від Канторовича симплекс-метод для розв’язування задач лінійного проґрамування запропонував Дж. Данціґ, який пізніше визнав пріоритет Канторовича. В 1975-му р. Л.В. Канторович отримав Нобелівську премію за видатний внесок в розробку теорії оптимального використання ресурсів в економіці.

Одночасно з розвитком лінійного програмування велика увага приділялася задачам нелінійного програмування, у яких або функція мети, або обмеження, або те й інше нелінійні.  У 1951 р. була опублікована робота Куна і Таккера, у якій наведені необхідні і достатні умови оптимальності для  розв’язання нелінійних задач.  Ця робота послужила основою для наступних досліджень в області нелінійного програмування.  Чарнес і Лемке (1954 р.) розглянули наближений метод розв’язання задач із сепарабельными опуклими функціями цілі і лінійними обмеженнями.  Починаючи з 1955р. опубліковано багато робіт, присвячених квадратичному програмуванню (роботи Франка і Вулфа, Баранкіна і Дорфмана, Марковича, Хілдрета й ін.).  У роботах Деніса, Розена і Зойтендейка розроблені градієнтні методи рішення задач нелінійного програмування.  В даний час відомі методи розв’язання вузького класу задач нелінійного програмування.

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

У багатьох задач лінійного і нелінійного програмування процес залежить від часу — від декількох періодів (етапів). При розв’язанні таких задач (вони називаються багатоетапними) необхідно враховувати поетапний розвиток процесу. Це, наприклад, задача розподілу ресурсів між підприємствами за роками планованого періоду.  Метод розв’язання задач такого типу складає сутність динамічного програмування. Таким чином, динамічне програмування визначається як математична теорія пошуку оптимального розв’язання багатоетапних задач. Динамічне програмування як самостійна дисципліна сформувалася в п'ятидесятих роках. Великий внесок у його розвиток вніс американський математик Р. Белман.  Подальший розвиток динамічне програмування одержало в працях Дрейфуса, Робертса, Ланге, Карра, Хоува й ін.

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

Таким чином ДО сформувалося як науковий підхід до розв`язку задач орґанізаційного управління.

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

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

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

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

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

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

1.  Основні поняття ДО та етапи операційного дослідження

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

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

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

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

 Стратеґії оперуючої сторони – це припустимі способи використання нею активних засобів.

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

Стан операції – це сукупність характеристик операції в певний момент часу.

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

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

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

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

Процес ДО включає ряд етапів, основними з яких є наступні.   

1. Визначення мети дослідження.

2. Ідентифікація та формулювання проблеми.

3. Побудова моделі операції.

4. Синтез обчислювального методу та розв’язання поставленої задачі за допомогою моделі.

5. Перевірка адекватності моделі.

6. Реалізація результатів дослідження.

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

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

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

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

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

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

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

1.  Пряма та обернена задачі ДО. Детерміновані задачі ДО

Рішення прямої задачі ДО відповідає на питання: “Що буде, якщо при заданих умовах ми оберемо конкретний розв’язок з множини припустимих розв’язків ?” і являє собою математичну модель критерію ефективності в залежності від керованих змінних  .   

Обернена задача покликана дати відповідь на питання: “Яке значення  необхідно обрати, щоб ?” Для розв’язання оберненої задачі спочатку необхідно розв’язати пряму.

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

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

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

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

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

Приклад:

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

2. Проектується система споруд, які охоронятимуть район від повеней. Ні моменти повеней, ні їх розміри невідомі.

3. Розробляється план озброєнь на декілька років наперед; невідомі ні конкретний супротивник, ні його озброєння в майбутньому.

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

В загальному розрізняється два основні види невизначеності:

“доброякісна” – коли невідомі фактори підкоряються законам теорії ймовірності і дослідникам відомі значення та вид законів розподілу цих факторів (стохастичні задачі);

“погана” – коли фактори не підкоряються законам ймовірності, або параметри законів невідомі.

Приклад доброякісної невизначеності.

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

Шляхи розв'язування стохастичних задач є наступні:

заміна випадкових факторів значеннями середніх та розв'язування задачі як детермінованої:  ;

пошук екстремуму середнього значення критерію ефективності: ;

введення стохастичних обмежень.

Слід мати на увазі, що перші два  прийоми не завжди виправдані. Як приклад можна розглянути проблематику створення інформаційної системи (ІС) швидкої допомоги. Необхідно розробити такий алгоритм роботи ІС, щоб служба швидкої допомоги функціонувала найефективніше.  В принципі логічним здається вибір критерію – час очікування допомоги. Однак в такій постановці задача не має сенсу, оскільки величина  є випадковою. Мінімізація середнього часу в цьому випадку приведе до того, що довгий час чекання в одному випадку компенсуватиметься коротким часом в іншому, і ситуація нагадуватиме ситуацію “середньої температури хворих в лікарні” – 36.6, в той час як пацієнти можуть мати як високу (41 , так і низьку (32.2температуру. Тому величина  не повинна бути більшою, ніж гранично припустима  . Однак безпосередньо таке обмеження ввести в задачу неможливо, так як  – випадкова величина. Обминути цю складність можна у випадку, коли ми задамо рівень граничної ймовірності того, що величина   не буде більшою, ніж — .

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

Гірша ситуація виникає в тому випадку, коли невизначені фактори не можуть бути вивчені та описані статистичними методами, а саме:

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

розподіл ймовірностей не існує.

Приклади:

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

“Погана невизначеність” – який одяг будуть одягати жінки через декілька років —  розглядаються всі альтернативи, і відкидаються ті, які в будь -якому випадку будуть гіршими — множина розв’язків звужується та знаходяться такі компромісні розв’язки, які є відносно стійкими.

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

1.  Основні типи задач дослідження операцій.

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

За цією ознакою розрізняють наступні типи задач:

задачі розподілу ресурсів;

задачі транспортування продуктів (вибору маршрутів);

задачі планування та керування на мережах;

задачі календарного та об’ємно-календарного планування;

задачі планування та розміщення;

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

задачі масового обслуговування.

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

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

Задачі планування та керування на мережах є моделями процесів планування та управління складними проектами, що включають до свого складу певну множину напіввпорядкованих робіт, для виконання яких необхідно використати певні об’єми ресурсів різних типів. З одного боку, при відсутності інформації про споживані ресурси, можливе планування часових характеристик, з іншого — набагато цікавішого з практичної точки зору — тривалість кожної з робіт проекту залежить від кількості вкладеного ресурсу (ресурсів), і необхідно визначити такий розподіл ресурсів між роботами з врахуванням відношення передування чи слідування на множині робіт, щоб загальна тривалість виконання комплексу робіт (проекту) була мінімальною. Для розв’язування цих практично важливих задач існують ряд відомих програмних пакетів (наприклад Time Line фірми Borland та Microsoft Project фірми Microsoft).

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

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

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

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