Предмет та історія виникнення дослідження операцій

Тема 1. Предмет та задачі дослідження операцій

1. Предмет та історія виникнення дослідження операцій (ДО).

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

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

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

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

Предмет та історія виникнення дослідження операцій

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

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

Початки ДО, що виявлялися в науковому мисленні, близькому до операційного, з’явилися досить давно. Першою ігровою задачею, відомою з літератури, була задача про справедливий розподіл ставки між двома гравцями в кості, поставлена в кінці 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. Системність. При реалізації операційного підходу важливе значення має системність досліджень, які проводяться, тобто будь-яка задача повинна розглядатися всебічно з різних точок зору, виходячи з ефек­тивності функціонування системи, в яку входить задача, загалом.

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

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

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

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