МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ

„КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”

Дзюбан І. Ю.

Жиров О. Л.

Охріменко М. Г.

МЕТОДИ

ДОСЛІДЖЕННЯ ОПЕРАЦІЙ

Затверджено Методичною радою НТУУ „КПІ”

як навчально-методичний посібник для студентів вищих навчальних закладів

Київ 2005

УДК 519.8(075.8)

ББК 65вбя73

Д43

Рецензент:

Г. П. Донець,

доктор фізико-математичних наук, професор,

завідувач відділу економічної кібернетики

Інституту кібернетики ім. В. М. Глушкова НАНУ

Рецензент:

Ф. А. Шевченко,

директор головного центру інформаційних систем КНЕУ,

професор кафедри інформаційного менеджменту

Дзюбан І. Ю., Жиров О. Л., Охріменко М. Г.

Д43 Методи дослідження операцій: навч.-метод. посіб./ І. Ю.Дзюбан, О. Л. Жиров, М. Г. Охріменко – К.: ІВЦ „Видавництво «Політехніка »”, 2005. – 108 с.: іл. – Бібліограф.: с. 104

ISBN 966-622-186-1

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

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

Для студентів, аспірантів і викладачів вищих навчальних закладів.

УДК 519.8(075.8)

ББК 65вбя73

ISBN 966-622-186-1

Зміст

Вступ 4

5

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

2. Математична модель операції 7

8

3. Модель «затрати-випуск» В. В. Леонтьєва 9

4. Модель розподілу ресурсів 16

17

5. Загальний вигляд задачі 18

лінійного програмування 18

6. Графічний метод розв’язання задачі лінійного програмування 19

7. Алгоритм розв’язання задачі лінійного програмування за допомогою симплекс-методу 23

8. Спряжені (двоїсті) задачі лінійного програмування. Основні властивості 34

9. Економічна інтерпретація основної та спряженої задач лінійного програмування 39

10. Задачі транспортного типу 42

45

11. Знаходження опорного плану задачі транспортного типу 46

12. Поліпшення плану перевезень 48

13. Задачі транспортного типу з неправильним балансом 59

14. Розв’язання задач лінійного програмування в цілих числах 66

15. Виробничо-транспортна задача 74

16. Динамічна модель оптимального керування. 83

Принцип максимуму Л. С. Понтрягіна 83

17. Оптимізація розподілу ресурсів в умовах кризи. Оптимальність за Парето 94

Список використаної 97

та рекомендованої літератури 97

Вступ

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

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

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

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

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

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

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

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

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

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

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

Для розуміння тексту студентові достатньо володіти основами математичного аналізу, лінійної алгебри та аналітичної геометрії

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

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

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

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

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

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

Основне завдання дослідження операцій – попереднє кількісне обґрунтування оптимальних рішень.

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

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

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

2. Математична модель операції

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

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

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

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

Математичні моделі, які використовують у задачах ДО, можна грубо розділити на два види: аналітичні та статистичні.

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

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

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

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

Видатний фахівець з ДО Т. Л. Сааті в книзі [6] дав таке іронічне визначення: „дослідження операцій – мистецтво давати погані відповіді на ті практичні питання, на які даються ще гірші відповіді іншими методами”.

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

Перейдемо до аналізу найпростіших аналітичних моделей економіки.