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

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




НазваI. Предмет І задачі дослідження операцій
Сторінка1/6
Дата06.09.2012
Розмір1.09 Mb.
ТипКонспект
  1   2   3   4   5   6

УДК 519.85


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

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

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

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

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

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

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

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

^ Ціль дослідження операцій - попереднє кількісне обгрунтування оптимальних рішень.

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

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

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

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

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

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

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

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


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

Задача дослідження операцій діляться на два класи: прямі і зворотні.

Прямі задачі відповідають на запитання: що буде, якщо в заданих умовах буде прийняте рішення ЗОКРЕМА, чому буде дорівнює, при даному рішенні х, обраний показник ефективності L(х).

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

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

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

У загальному виді задача математичного програмування може бути записана в такий спосіб:

знайти максимум або мінімум функції багатьох перемінних

(1.1 )

при обмеженнях

(1.2 )

(1.3.)

Функція L(х1, х2, ... , хn) називається цільовою функцією, вона характеризує ефективність досліджуваної моделі. Обмеження (1.2) і (1.3) визначають область припустимих значень вектора невідомий змінних

х=/ х1, х2, ... , хn/.

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




Мал. 1.1

До задач лінійного програмування відносяться ті, у яких цільова функція f(x) лінійно залежить від невідомих х1, х2, ... , хn, а обмеження, що накладаються на ці невідомі мають вид лінійних рівностей або нерівностей. У лінійному програмуванні існують класи задач, структура яких дозволяє розробити для їхнього рішення більш прості спеціальні методи. Так у лінійному програмуванні з'явилися поділи транспортних задач і задач про призначення.

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

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

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

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

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


^ II. Лінійне програмування

2.1. Задача лінійного програмування

Приклад 1. Фірма “Сатурн” виготовляє два види продукції П1 і П2, реалізація яких з обліком виробничих можливостей фірми необмежена. Для виробництва використовуються ресурси трьох типів: трудові, матеріальні, фінансові. Відомо кількість ресурсів, що є в розпорядженні фірми, а також витрати кожного виду ресурсів для виготовлення одиниці продукції П1 і П2. Відома також прибуток на одиницю кожного виду продукції. Ці дані подані в таблиці 2.1.

Таблиця 2.1

Ресурси

Витрати на

одиницю продукції

Наявність




П1

П2

ресурсів

Трудові

2

8

28

Матеріальні

1

3

32

Фінансові

12

4

50

Прибуток на одиницю продукції

3

5





Необхідно скласти план розподілу ресурсів.

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

  • який критерій оптимальності планування необхідний для даної задачі? (що характеризує ефективність досліджуваної моделі?)

  • які обмеження існують при рішенні даної задачі.

Для розглянутої задачі планування невідомими є плани випуску продукції П1 і П2.

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

Природними є обмеження на використовувані ресурси, що не можуть перевищувати їхньої наявності.

Після відповіді на ці питання будується математична модель.

  1. Перемінні (шукані розміри) даної задачі зазначимо через х1 - план випуску продукції П1 і х2 - план випуску продукції П2.

  2. Цільова функція (прибуток) повинна бути максимізована

L = 3x1+5x2  max.

  1. Обмеження на що витрачаються ресурси можна записати в такий спосіб

2х1+8х2 28;

х1+3х2 32;

12х1+4х2 50.

Крім того, природні обмеження полягають у тому, що плани випуску продукції П1 і П2 не можуть бути негативними, тобто необхідно ввести обмеження на їхній знак:

х1 0;

х2 0.

Таким чином, ми одержали математичну модель розглянутої задачі: знайти такі х1 і х2, що забезпечать

max L = 3x1+5x2,

при обмеженнях







Дана модель є лінійної, тому що вхідні в неї функції (цільова функція й обмеження) лінійні. Лінійність припускає наявність двох властивостей - пропорційність і адитивність.

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

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

Приклад 2. Фірма “Альтаір” розташовує двома видами верстатів, із них N1 верстатів типу 1 і N2 верстатів типу 2. Верстати можуть робити трьох виду продукції: П1; П2; П3, але з різною продуктивністю. Дані аij продуктивності верстатів дані в таблиці 2.2.

Кожна одиниця продукції П1 приносить фірмі прибуток С1, продукції П2 - С2; продукції П3 - С3. Фірма має ліцензію, відповідно до якого вона повинна робити на місяць не більш Фірма вже одержала замовлення, відповідно до яких вона повинна робити на місяць не менше b1 одиниць продукції П1; не менше b2 продукції П2 і не менше b3 продукції П3.

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

Таблиця 2.2







Продуктивність




Наявність

Тип верстата




Вид продукції




верстатів




П1

П2

П3




1

а11

а12

а13

N1

2

a21

a22

a23

N2

Ліцензія










Замовлення










Прибуток

С1

С2

С3





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

х11, х12, х13,

х21, х22, х23,

де хij - кількість верстатів i-го виду (i=1,2), зайнятих виготовленням продукції Пj (j=1,3). Запишемо спочатку обмеження, що накладаються на перемінні хij.

Для забезпечення замовлення необхідно, щоб







Для дотримання плану, обумовленого ліцензією, необхідно, щоб







Обмеження, зв'язані з наявністю верстатів





Природні обмеження

хij 0, i=1,2; j=1,2,3.

Цільова функція повинна бути дорівнює сумарному прибутку від виробництва усіх видів продукції:




2.2. Стандартна форма задачі лінійного програмування

Будь-яку задачу лінійного програмування можна звести до стандартної (канонічного) формі, що формулюється так: знайти позитивні значення перемінних х1, х2, ... , хn, що задовольняли б умовам - рівністю

(1.4 )

де і звертали б у максимум лінійну функцію цих перемінних

(1.5)

Дійсно, якщо в деяких задачах у вихідній постановці потрібно цільову функцію L мінімізувати, те зрадивши знак L на зворотний, приходимо до задачі максимізації (max -L),і навпаки. Наприклад, мінімізація функції



еквівалентна максимізації функції



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

Вихідне обмеження, записане у виді нерівності, можна представити у виді рівності, збільшуючи залишкову перемінну до лівої частини обмеження, коли знак нерівності <, або віднімаючи надлишкову перемінну, коли знак нерівності >.

Наприклад, при вихідній нерівності

2х1+7х2 9,

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

2х1+7х2 3=9, х30.

Якщо вихідне обмеження визначає витрата деякого ресурсу, то перемінну х3 варто інтепретувати як залишок, або невикористану частину, даного ресурсу.
  1   2   3   4   5   6

Схожі:

I. Предмет І задачі дослідження операцій iconТематичнийпла н по видах занять з курсу "Дослідження операцій"
Операція, основні поняття І якості. Прямі та зворотні задачі. Управління операцією, оцінка якості. Математичні моделі операцій. Допустимі...
I. Предмет І задачі дослідження операцій iconПитання з дисциплини «дослідження операцій»
Розподіл капіталовкладень між підприємствами; постановка задачі, функціональні рівняння
I. Предмет І задачі дослідження операцій iconТести по дисциплині “дослідження операцій”
В методі вирішення транспортної задачі, фактично, використовиваються кроки сімплекс-метода
I. Предмет І задачі дослідження операцій iconКонтрольні питання з курсу «Дослідження операцій»
Визначення дифіцитних І недифіцитних ресурсів в задачі лп на основі її графічного рішення. Приклад
I. Предмет І задачі дослідження операцій icon«Математичні методи оптимізації та дослідження операцій»
Це так звані задачі математичного програмування, які виникають в різних областях людської діяльності, зокрема в економічних дослідженнях,...
I. Предмет І задачі дослідження операцій iconЗа вимогами кредитно-модульної системи
С другої сторони, цей курс має свої цілі, задачі та предмет дослідження, яких студенти не вивчали у названих курсах І тому являється...
I. Предмет І задачі дослідження операцій iconЗатверджено на засіданні приймальної комісії Львівського національного університету імені Івана Франка
...
I. Предмет І задачі дослідження операцій iconТематичнийпла н по видах занять з курсу "Математичне програмування"
Операція, основні поняття І якості. Прямі та зворотні задачі. Управління операцією, оцінка якості. Математичні моделі операцій. Допустимі...
I. Предмет І задачі дослідження операцій icon2. Двоїста задача лінійного програмування Тема Транспортна задача
Операція, основні поняття І якості. Прямі та зворотні задачі. Управління операцією, оцінка якості. Математичні моделі операцій. Допустимі...
I. Предмет І задачі дослідження операцій iconЗатверджую
Предмет, мета І задачі логопедії як розділу корекційної педагогіки. Теоретичні та практичні задачі логопедії, їх взаємозв’язок. Міжпредметні...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи