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

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

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

Оптимальними називаються рішення, які, з тих чи інших міркувань, краще інших.

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

Поряд з основним завданням - обґрунтуванням оптимальних рішень –До галузі дослідження операцій відносяться й інші завдання:

Порівняльна оцінка різних варіантів організації операції,

Оцінка впливу на операцію різних параметрів,

Вивчення «вузьких місць», тобто. елементів, порушення роботи яких особливо сильно позначається успіху операції, тощо.

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

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

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

Послідовність процесів у дослідженні операцій.

1. Формулюється мета дослідження та розробляється постановка задачі.

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

3. Після побудови моделі на ній одержують результати

4. Вони інтерпретуються в термінах оригіналу та переносяться на оригінал.

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

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

При проектуванні та експлуатації АСУ часто виникають завдання, пов'язані з аналізом як кількісних, так і якісних закономірностей їх функціонування, визначенням їх оптимальної структури і т.д.

Безпосереднє експериментування на об'єктах на вирішення цих завдань має низку істотних недоліків:

1. Порушується встановлений режим роботи.

2. У натурному експерименті неможливо проаналізувати всі альтернативні варіанти побудови системи та ін.

Ці завдання доцільно вирішувати на моделі, відокремленій від об'єкта та реалізується на ЕОМ.

При моделюванні інформаційних систем знаходять широке застосування математичні моделі.

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

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

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

Можна виділити 4 основні етапи моделювання систем на ЕОМ:

Побудова концептуальної моделі системи та її формалізація;

Алгоритмізація моделі системи та розробка моделюючої програми;

Отримання та інтерпретація попередніх результатівмоделювання;

Перевірка адекватності моделі та системи; коригування моделі

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

Лекція 3. Основні поняття методу експертних оцінок. Формування експертних груп. Процедури опитування. Методи ранжирування, парних порівнянь, оцінювання у відносній шкалі.

1. Предмет та завдання дослідження операцій в економіці. Основні поняття теорії дослідження операцій.

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

Мета дослідження операцій - кількісне обґрунтування прийнятих рішень щодо управління організаціями

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

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

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

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

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

Параметри, сукупність яких утворює рішення, називають елементами рішення.

Багато допустимих рішень називаються задані умови, які фіксовані і не можуть бути порушені.

Показник ефективності - кількісна міра, що дозволяє порівнювати різні рішення щодо ефективності.

2. Поняття про мережеве планування та управління. Модель процесу і її елементи.

Метод роботи з мережевими графіками – мережне планування – базується на теорії графів. У перекладі з грецького граф (grafpho – пишу) представляє систему точок, деякі з них з'єднані лініями – дугами (або ребрами). Це топологічна (математична) модель взаємодіючих систем. З допомогою графів можна вирішувати як завдання мережного планування, а й інші завдання. Метод мережного планування застосовується під час планування проведення комплексу взаємозалежних робіт. Він дозволяє наочно уявити організаційно-технологічну послідовність виконання робіт та встановити взаємозв'язок між ними. Крім цього, він дозволяє забезпечити координацію операцій різного ступеня складності та виявити операції, від яких залежить тривалість усієї роботи (тобто організаційного заходу), а також зосередити увагу на своєчасному виконанні кожної операції.

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

Основні поняття мережевої моделі:

Подія, робота, шлях.

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

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

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

3. Побудова та впорядкування мережного графіка.

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

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

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

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

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

У мережевому графіку застосовуються тимчасові, вартісні та інші характеристики робіт.

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

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

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

Якість, надійність та інші показники робіт є додатковими характеристиками робіт.

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

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

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

2 При побудові мережі вирішуються питання:

Які роботи (роботу) необхідно виконати, щоб розпочати цю роботу;

Які роботи доцільно виконувати паралельно із цією роботою;

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

4 Форма графіка повинна бути простою і візуально легко сприймається.

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

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

4. Критичний шлях мережного графіка. Резерви часу. Ранні та пізні терміни подій та робіт у мережевому графіку.

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

Критичний шлях позначається на мережевому графіку потовщеними чи подвійними лініями (стрілками).

Особливого значення при складанні мережного графіка мають два поняття:

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

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

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

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

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

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

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

5. Динамічне програмування. Принцип оптимальності та управління Беллмана.

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

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

Головним недоліком методу є, висловлюючись словами Беллмана, «прокляття розмірності» - його складність катастрофічно зростає зі збільшенням розмірності завдання.

6. Завдання щодо розподілу коштів між підприємствами.

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

7. Постановка задачі лінійного програмування.

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

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

Критерієм є MAX ціна чергового продукту з групи, що цікавиться f.

Керованими змінними величинами є ціни всіх товарів групи f.

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

a) система нерівностей (обмеження раціональності поведінки споживача) (див. 4.2. Прогнозування у межах узагальненого непараметричного методу);

б) вимога невід'ємності керованих змінних (у нашій задачі прогнозування ми вимагаємо, щоб ціни на продукти групи f не опустилися нижче 80% від значень цін в останній тимчасовій точці) ;

в) бюджетне обмеження як рівності - вимога сталості суми витрат за купівлю товарів із групи f (з урахуванням 15% інфляції, наприклад).

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

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

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

Знайти мінімальне значення функції

(2.1) Z = С1х1 + С2х2

a11x1 + a22x2 b1

(2.2) a21x1 + a22x2 b2

aM1x1 + aM2x2 bM

(2.3) х1 0, х2 0

Припустимо, що система (2.2) за умови (2.3) спільна та її багатокутник рішень обмежений. Кожна з нерівностей (2.2) і (2.3), як зазначалося вище, визначає напівплощину з граничними прямими: ai1x1 + ai2x2 + ai3x3 = bi, (i = 1, 2, ..., n), х1 = 0, х2 = 0 . Лінійна функція (2.1) при фіксованих значеннях Z є рівнянням прямої лінії С1х1 + С2х2 = const. Побудуємо багатокутник розв'язків системи обмежень (2.2) та графік лінійної функції (2.1) при Z = 0 (рис. 2.1). Тоді поставленої задачі лінійного програмування можна дати таку інтерпретацію. Знайти точку багатокутника розв'язків, у якій пряма С1х1 + С2х2 = const опорна та функція Z при цьому досягає мінімуму.

Значення Z = С1х1 + С2х2 зростають у напрямку вектора N = (С1, С2), тому пряму Z = 0 пересуваємо паралельно самої собі у напрямку вектора Х. З рис. 2.1 слід, що пряма двічі стає опорною по відношенню до багатокутника рішень (у точках А і С), причому мінімальне значення набуває в точці А. Координати точки А (х1, х2) знаходимо, вирішуючи систему рівнянь прямих АВ та АЕ.

Якщо багатокутник рішень є необмежену багатокутну область, то можливі два випадки.

Випадок 1. Пряма С1х1 + С2х2 = const, пересуваючись у напрямку вектора N або протилежно йому, постійно перетинає багатокутник рішень і в жодній точці не є опорною до нього. У цьому випадку лінійна функція не обмежена багатокутнику рішень як зверху, так і знизу (рис. 2.2).

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

9. Симплекс-метод.

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

Цей метод є універсальним, застосовним до будь-якої задачі лінійного програмування у канонічній формі. Система обмежень тут - система лінійних рівнянь, у якій кількість невідомих більша за кількість рівнянь. Якщо ранг системи дорівнює r, ми можемо вибрати r невідомих, які виразимо через інші невідомі. Для певності припустимо, що обрані перші, що йдуть поспіль, невідомі X1, X2, ..., Xr. Тоді наша система рівнянь може бути записана як

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

10. Постановка транспортного завдання. Методи визначення опорних планів.

Є m пунктів відправлення («постачальників») та n пунктів споживання («споживачів») деякого однакового товару. Для кожного пункту визначено:

ai – обсяги виробництва i-го постачальника, i = 1, …, m;

вj - попит j-го споживача, j = 1, ..., n;

сij - вартість перевезення однієї одиниці продукції з пункту Ai-i-го постачальника, пункт Вj - j-го споживача.

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

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

Під планом перевезень розуміють обсяг перевезень, тобто. кількість товару, яку необхідно перевезти від i-го постачальника до j-го споживача. Для побудови математичної моделі завдання необхідно ввести m·n штук змінних хij, i= 1,…, n, j= 1, …, m, кожна змінна хij означає обсяг перевезень з пункту Ai до пункту Вj. Набір змінних X = (xij) і буде планом, який потрібно знайти, виходячи з постановки задачі.

Це умова на вирішення закритих і відкритих транспортних завдань (ЗТЗ).

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

Якщо ця нерівність виконується суворо, то завдання називається «відкритою» або «незбалансованою», якщо ж , то задача називається «закритою» транспортним завданням, і матиме вигляд (2):

Умова збалансованості.

Це умова на вирішення закритих транспортних завдань (ЗТЗ).

11. Алгоритм розв'язання транспортного завдання.

Застосування алгоритму вимагає дотримання ряду передумов:

1. Повинна бути відома вартість перевезення одиниці товару з кожного пункту виробництва на кожен пункт призначення.

2. Запас продуктів у кожному пункті виробництва має бути відомим.

3. Потреби у продуктах у кожному пункті споживання мають бути відомі.

4. Загальна пропозиція має дорівнювати загальному попиту.

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

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

Етап 2. Перевірка отриманого розподілу ресурсів на оптимальність

Етап 3. Якщо отриманий розподіл ресурсів є оптимальним, то ресурси перерозподіляються, знижуючи вартість транспортування.

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

Цей ітеративний процес повторюється доти, доки не буде отримано оптимальне рішення.

12. Моделі керування запасами.

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

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

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

детермінованими;

імовірнісними.

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

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

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

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

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

процес поповнення запасу. Можливо миттєвим чи розподіленим у часі;

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

13. Системи масового обслуговування (СМО) та показники їх ефективності.

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

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

Системи масового обслуговування можуть бути одноканальними або багатоканальними.

Кожна СМО призначена для обслуговування (виконання) деякого потоку заявок (вимог), що надходять на вхід системи переважно не регулярно, а випадкові моменти часу. Обслуговування заявок, у разі, також триває не постійний, заздалегідь відомий час, а випадковий час, що залежить від багатьох випадкових, часом невідомих нам, причин. Після обслуговування заявки канал звільняється та готовий до прийому наступної заявки. Випадковий характер потокозаявок та часу їх обслуговування призводить до нерівномірної завантаженості СМО: в інший час на вході СМО можуть накопичуватися необслужені заявки, що призводить до перевантаження СМО, а іноді при вільних каналах на вході СМО заявки не буде, що призводить до недовантаження СМО, т. тобто. до простоювання її каналів. Заявки, що накопичуються на вході СМО, або «стають» у чергу, або через неможливість подальшого перебування в черзі залишають СМО необслуженими.

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

14. Рівняння динаміки для імовірнісних станів (рівняння Колмогорова). Граничні ймовірності станів.

Формально диференціюючи рівняння Колмогорова-Чепмена по s при s = 0 отримуємо пряме рівняння Колмогорова:

Формально диференціюючи рівняння Колмогорова - Чепмена по t при t = 0 отримуємо зворотне рівняння Колмогорова

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

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

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

Припустимо, що ця умова виконана, і, отже, граничні ймовірності існують:

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

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

15. Процес загибелі та розмноження.

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

Потоками розмноження λi(t) називатимемо пуассонівські потоки, що ведуть до збільшення функції X(t). Відповідно μi(t) - потоки загибелі, що ведуть зменшення функції X(t).

Складемо за графом рівняння Колмогорова:

Якщо потік із кінцевим числом станів:

Система рівнянь Колмогорова для процесу загибелі та розмноження з обмеженою кількістю станів має вигляд:

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

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

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

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

Слід зазначити, що в даному випадку кількість каналів дорівнює 1(). Цей канал приймає пуассонівський потік заявок, інтенсивність якого дорівнює . Час впливає на інтенсивність:

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

17. Системи масового обслуговування з очікуванням.

Заявка, що надійшла в момент, коли канал зайнятий, стає в чергу і чекає на обслуговування.

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

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

-канал вільний;

-канал зайнятий, черги немає;

- канал зайнятий, одна заявка стоїть у черзі;

-канал зайнятий, k - 1 заявок стоять у черзі;

- канал зайнятий, т заявок стоять у черзі.

18. Методи прийняття рішень за умов конфлікту. Матричні ігри. Чисті та змішані стратегії ігор.

Матрична гра - це кінцева гра двох гравців з нульовою сумою, в якій задається виграш гравця 1 у вигляді матриці (рядок матриці відповідає номеру стратегії гравця 2, стовпець - номеру стратегії гравця 2; на перетині рядка і стовпця матриці знаходиться виграш гравця 1 відповідний застосовуваним стратегіям).

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

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

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

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

Кожна стратегія гравця i =; j = часто називається чистою стратегією.

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

Таким чином, якщо гравець 1 має m чистих стратегій 1,2,...,m, то його змішана стратегія x- це набір чисел x = (x1,..., xm), що задовольняють співвідношенням

xi³ 0 (i= 1,m), =1.

Аналогічно для гравця 2, який має n чистих стратегій, змішана стратегія y – це набір чисел

y = (y1, ..., yn), yj ³ 0, (j = 1,n), = 1.

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

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

19. Геометричний метод розв'язання матричної гри.

Вирішення ігор розміру 2xn або nx2 допускає наочну геометричну інтерпретацію. Такі ігри можна вирішувати графічно.

На площині XY по осі абсцис відкладемо одиничний відрізок A1A2 (рис. 5.1). Кожній точці відрізка поставимо у відповідність деяку змішану стратегію U = (u1, u2). Причому відстань від деякої проміжної точки U до правого кінця цього відрізка – це ймовірність u1 вибору стратегії A1, відстань до лівого кінця – ймовірність u2 вибору стратегії A2. Точка А1 відповідає чистій стратегії А1, точка А2 – чистої стратегії А2.

У точках А1 і А2 відновимо перпендикуляри і відкладатимемо на них виграші гравців. На першому перпендикулярі (збігається з віссю OY) покажемо виграш гравця А при використанні стратегії А1, на другому – при використанні стратегії A2. Якщо гравець А застосовує стратегію A1, його виграш при стратегії B1 гравця B дорівнює 2, а за стратегії B2 він дорівнює 5. Числам 2 і 5 на осі OY відповідають точки B1 і B2. Аналогічно на другому перпендикулярі знайдемо точки B"1 та B"2 (виграші 6 і 4).

З'єднуючи між собою точки B1 і B"1, B2 і B"2 отримаємо дві прямі, відстань від яких до осі OX визначає середній виграш при будь-якому поєднанні відповідних стратегій.

Наприклад, відстань від будь-якої точки відрізка B1B"1 до осі OX визначає середній виграш гравця A за будь-якого поєднання стратегій A1 і A2 (з ймовірностями u1 і u2) і стратегії B1 гравця B.

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

Координати точки M знайдемо як координати точки перетину прямих B1B"1 і B2B"2.

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

Складемо рівняння прямих для нашого завдання.

Пряма B1B"1: = або y = 4x + 2.

Пряма B2B2: = або y = -x + 5.

Отримаємо систему: y = 4x + 2,

Розв'яжемо її: 4x + 2 = -x + 5,

x = 3/5, y = -3/5 + 5 = 22/5.

Таким чином, U = (2/5, 3/5), v = 22/5.

20. Біматричні ігри.

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

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

21. Статистичні ігри. Принципи та критерії прийняття рішень в умовах повної та часткової невизначеності.

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

невизначеність цілей;

невизначеність наших знань про навколишню обстановку та фактори, що діють у даному явищі (невизначеність природи);

невизначеність дій активного чи пасивного партнера чи супротивника.

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

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

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

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

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

Іншим крайнім випадком можливо невизначеність нестохастичного виду (за висловом Е.С.Вентцель - " погана невизначеність " ), коли він ніяких припущень про стохастичної стійкості немає. Зрештою, можна говорити про проміжний тип невизначеності, коли рішення приймається на підставі будь-яких гіпотез про закони розподілу випадкових величин. При цьому ЛПР повинен мати на увазі небезпеку розбіжності його результатів з реальними умовами. Ця небезпека розбіжності формалізується за допомогою коефіцієнтів ризику.

Ухвалення рішень в умовах ризику може бути засноване на одному з наступних критеріїв:

критерій очікуваного значення;

комбінації очікуваного значення та дисперсії;

відомого граничного рівня;

найбільш вірогідні події в майбутньому.

1. Основні поняття ІВ

ІВ – наук дисц-на, займається розробкою і практ застосуванням методів найбільш ефективного упр-я різними орг сис-мами.

ІО включає наступні розділи:

1) математичне прогр. (обґрунтування планів, програм господарської діяльності); воно включає розділи: лінійне прогр, нелінійне прогр, динамічне прогр

2) теорію масового обслуговування, що спирається на теорію випадкових процесів;

3) теорію ігор, що дозволяє обґрунтовувати рішення, що приймаються в умовах неповноти інф-ції.

При вирішенні конкретного завдання управління застосування методів ІВ передбачає:

Побудова економічних та математичних моделей для завдань прийняття рішення у складних ситуаціях або в умовах невизначеності;

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

Основні поняття та визначення ІВ.

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

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

Модель операції – це досить точне опис операції з допомогою математичного апарату (різного роду функцій, рівнянь, систем рівнянь і нерівностей тощо.). Складання моделі операції вимагає розуміння сутності описуваного явища та знання математичного апарату.

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

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

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

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

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

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

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

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

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

2. Загальне завдання лінійного прогр. Оптим реш-е

Економіко-математична модель

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

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

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

Загальна схема формування моделі: I

1) вибір деякого числа змінних величин, завданням - числових значень яких однозначно визначається один із можливих станів досліджуваного явища;

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

3) кількісне вираження обраного критерію оптимальності у формі цільової функції; I

4) математичне формулювання завдання, як завдання відшукання екстремуму цільової функції за умови виконання обмежень, що накладаються на змінні.

Загальне завдання лінійного програмуваннямає вигляд:

Дана система т лінійних рівнянь і нерівностей зі змінними

та лінійна функція

Необхідно знайти таке рішення системи X = (x1, x2, ..., xj, ..., xn), де при якому лінійна функція F приймає оптимальне (тобто максимальне або мінімальне) значення.

Система (1) називається системою обмежень, а функція F – лінійною функцією, лінійною формою, цільовою функцією чи функцією мети.

Коротше загальне завдання лінійного програмування можна у вигляді:

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

Оптимальним рішенням (або оптимальним планом)Завдання ЛП називається рішення X = (x1, x2, ..., xj, ..., xn), системи обмежень (1), що задовольняє умові (3), при якому лінійна функція (2) набуває оптимального (максимальне або мінімальне) значення.

За умови, що всі змінні невід'ємні, система обмежень (1) складається лише з одних нерівностей – таке завдання лінійного програмування називається стандартним (симетричним); якщо система обмежень складається з одних рівнянь, то завдання називається канонічною.

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

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

4 . Елементи лінійної алгебри

Система m лінійних рівнянь із n змінними має вигляд

або в короткому записі

Будь-які m змінних системи m лінійних рівнянь із n змінними (m< n) называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля. Такой определитель часто называют базисным минором матрицы А. Тогда остальные m–n переменных называются неосновными (или свободными).

Для вирішення системи (2.1) за умови m< n сформулируем утверждение.

Твердження 2.1. Якщо для системиmлінійних рівнянь зnзмінними (m < n) ранг матриці коефіцієнтів при змінних дорівнює т, тобто. Існує хоча б одна група основних змінних, то ця система є невизначеною, причому кожному довільному набору значень неосновних змінних відповідає одне рішення системи.

Рішення X=(x1,x2,…,xn) системи (2.1) називається допустимим, якщо вона містить лише неотрицательные компоненти, тобто. xj>=0 будь-яких j=1,n. Інакше рішення називається неприпустимим.

Серед нескінченної множини рішень системи виділяють так звані базисні рішення.

Базовим рішеннямСистеми т лінійних рівнянь з n змінними називається рішення, в якому всі n-m неосновних змінних дорівнюють нулю.

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

Випуклі множини точок

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

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

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

Серед точок опуклої множини можна виділити внутрішні, граничні та кутові точки.

Точка множини називається внутрішньоюякщо в деякій її околиці містяться точки тільки даної множини.

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

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

На рис. 2.4 наведено приклади різних точок багатокутника: внутрішньої (точки М), граничної (точка N) та кутових (точки А, В, С, D, Е). Точка А – кутова, тому що для будь-якого відрізка, що повністю належить багатокутнику, наприклад, відрізка АР, вона не є внутрішньою; точка А - внутрішня для відрізка KL, але цей відрізок не належить багатокутнику.

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

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

Геометричний сенсрозв'язків нерівностей, рівнянь та їх систем

Розглянемо розв'язання нерівностей.

Твердження 1. Безліч рішень нерівності з двома змінними a11x1+a12x2<=b1 является одной из двух полуплоскостей, на которые вся плоскость делится прямой a11x1+a12x2=b1 , включая и эту прямую, а другая полуплоскость с той же прямой есть множество решений неравен­ства a11x1+a12x2>= b1.

Для визначення шуканої напівплощини (верхньої або нижньої) рекомендується задати довільну контрольну точку, що не лежить на її межі – побудованій прямій. Якщо нерівність виконується в контрольній точці, воно виконується і у всіх точках напівплощини, що містить контрольну точку, і не виконується у всіх точках іншої напівплощини. І навпаки, у разі невиконання нерівності в контрольній точці, вона не виконується у всіх точках напівплощини, що містить контрольну точку, і виконується у всіх точках іншої напівплощини. Як контрольну точку зручно взяти початок координат (0;0), що не лежить на побудованій прямій.

Розглянемо безліч розв'язків систем нерівностей.

Твердження 2. Безліч рішень спільної системит лінійних нерівностей із двома змінними є опуклим багатокутником (або опуклою багатокутною областю).

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

Координати кутових точок – вершин багатокутника знаходять як координати точок перетину відповідних прямих.

При побудові областей розв'язків систем нерівностей можуть трапитися інші випадки: безліч рішень – опукла багатокутна область (рис. 2.9, а); одна точка (рис. 2.9 б); порожнє безліч, коли система нерівностей несумісна (рис. 2.9, в).

5 . Геометричний метод розв'язання задач ЛП

оптимальне вирішення задачі ЛП

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

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

Наступна теорема присвячена аналітичному методу знаходження кутових точок.

Теорема 2. Кожному допустимому базисному рішенню задачі ЛП відповідає кутова точка багатогранника рішень, і навпаки, кожній кутовій точці багатогранника рішень відповідає допустиме базове рішення.

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

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

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

Розглянемо завдання у стандартній формі з двома змінними (п = 2).

Нехай геометричним зображенням системи обмежень є багатокутник ABCDE(Рис. 4.1). Необхідно серед точок цього багатокутника знайти таку точку, у якій лінійна функція F=c1x1+c2x2 набуває максимального (або мінімального) значення.

Розглянемо так звану лінію рівня лінійної функції F, тобто. лінію, вздовж якої ця функція набуває одного і того ж фіксованого значення а, тобто. F = а,або c1x1+c2x2=a.

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

Рівняння лінії рівня функції c1x1+c2x2=a є рівняння прямої лінії. При різних рівнях алінії рівня паралельні, тому що їх кутові коефіцієнти визначаються лише співвідношенням між коефіцієнтами c1 та c2 і, отже, рівні. Таким чином, лінії рівня функції F – це своєрідні "паралелі", розташовані зазвичай під кутом до осей координат.

Важлива властивість лінії рівня лінійної функції полягає в тому, що при паралельному зміщенні лінії в один бік рівень тільки зростає, а при зміщенні в інший бік лише убуває. Вектор c=(c1,c2), що виходить із початку координат, вказує напрямок якнайшвидшого зростання функції F. Лінія рівня лінійної функції перпендикулярна вектору c=(c1,c2).

Порядок графічного розв'язання задачі ЛП:

1.Побудувати багатокутник рішень.

2.Побудувати вектор c = (c1, c2), і перп-но йому провести лінію рівня лінійної функції Fнаприклад, F=0.

3. Паралельним переміщенням прямої F=0 у напрямку вектора c(-c) знайти точку Amax(Bmin), у якій F досягає максимуму (мінімуму).

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

2. Обчислити Fmax (Fmin).

Зауваження.Точка мінімуму – це точка «входу» до багатокутника рішень, а точка максимуму – це точка «виходу» із багатокутника.

6. Загальна ідея симплекс-метода. Геометрична інтерпретація

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

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

Нехай область допустимих рішень є багатокутником ABCDE. Припустимо, що його кутова точка Авідповідає вихідному допустимому базисному рішенню. При безладному переборі довелося б випробувати п'ять допустимих базисних рішень, що відповідають п'яти кутовим точкам багатокутника. Однак із креслення видно, що після вершини Авигідно перейти до сусідньої вершини В,а потім – до оптимальної точки З.Замість п'яти перебрали лише три вершини, послідовно покращуючи лінійну функцію.

Ідея послідовного покращення рішення лягла в основу універсального методу вирішення задач лінійного програмування – симплексного методу або методу послідовного покращення плану.

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

Вперше симплексний метод було запропоновано американським ученим Дж. Данцигом у 1949 р., проте ще 1939 р. ідеї методу розробили російським ученим Л.В. Канторович.

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

Для реалізації симплексного методу – послідовного покращення рішення – необхідно освоїти три основні елементи:

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

правило переходу на краще (точніше, не гіршому) рішенню;

критерій перевірки оптимальності знайденого рішення.

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

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

7 . Алгоритм симплекс-метода.

Розглянемо рішення ЗЛП симплекс-методом і викладемо її стосовно завдання максимізації.

1. За умовою завдання складається її математична модель.

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

3. Канонічна модель завдання записується у формі симплекс-таблиці так, щоб усі вільні члени були невід'ємними. Якщо початковий опорний план виділено, переходять до пункту 5.

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

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

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

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

а) якщо у F–рядку немає негативних елементів (крім вільного члена), то план оптимальний. Якщо при цьому немає нульових, то оптимальний план єдиний; якщо ж є хоча б один нульовий, то оптимальних планів безліч;

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

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

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

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

У пункті 3 алгоритму передбачається, що це елементи стовпця вільних членів неотрицательны. Ця вимога не обов'язково, але якщо вона виконана, то всі наступні симплексні перетворення виробляються тільки з позитивними роздільними елементами, що зручно при розрахунках. Якщо стовпці вільних членів є негативні числа, то вирішальний елемент вибирають так:

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

2) складають відношення елементів стовпця вільних членів до відповідних елементів роздільного стовпця, що мають однакові знаки (симплексні відносини);

3) із симплексних відносин вибирають найменше. Воно і визначить роздільну здатність. Нехай нею буде, наприклад, р-Рядок;

4) на перетині дозвільних стовпця та рядки знаходять роздільний елемент. Якщо роздільною здатністю виявився елемент y-рядка, то після симплексного перетворення вільний член цього рядка стане позитивним. Інакше на наступному кроці знову звертаються до t-рядка. Якщо завдання можна вирішити, то через кілька кроків у стовпці вільних членів не залишиться негативних елементів.

8. Метод зворотної матриці

Розглянемо ЛП виду:

A-матриця обмежень;

C=(c1,c2,…,cn)–вектор–рядок;

X = (x1, x2, ..., xn) - змінні;

- Вектор правої частини.

Вважаємо, що це рівняння лінійно незалежні, тобто. rang(a)=m. І тут базис – це мінор порядку матриці A. Т.е. Існує принаймні одна така підматриця B порядку m, що |B|<>0. Усі невідомі, відповідні B, називаються базисними. Решта вільними.

Нехай B-деякий базис. Тоді перестановкою стовпців матриці A завжди можна привести до виду A=(B|N),

де N - підматриця, що складається зі стовпців матриці A, що не належать до базису. Так само можливе розбиття вектора x на – вектор базисних змінних і.

Будь-яке рішення задачі (1) задовольняє умові A*x=b, і, отже, система набуває такого вигляду:

Т.к. |B|<>0, існує зворотна матриця. Помножуємо ліворуч на зворотну, отримуємо:

- спільне рішення.

Базовим рішенням (щодо базису B) називається приватне рішення задачі (2), отримане за умови. Тоді визначається однозначно.

Базове рішення називається реалізованимякщо.

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

У загальному рішенні закладено всі рішення, які є. Повернемося до цільової функції. Вводимо Cb - коефіцієнти перед базовими змінними, Cn - інші.

Отже, отримуємо. Підставляємо із загального рішення:

Твердження. Критерій оптимальності базового рішення.

Допустимо. Тоді базисне рішення оптимальне. Якщо, то базове рішення не оптимальне.

Док-во:Нехай. Розглянемо базове рішення, .

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

Нехай є інше рішення: (Xb, Xn).

Тоді дивимось

Т.ч, базове рішення саме min. Нехай, навпаки, не виконується, тобто. існує.

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

Нехай відповідає вільної змінної Xi:Xj надаємо значення і вводимо її в базис, а іншу змінну виводимо і називаємо її вільною.

Як визначити? Усі вільні змінні, крім, як і рівні 0, а.

Тоді в загальному рішенні, Де.

Винесемо: -необхідна умова.

Базове рішення називається регулярним, якщо. Змінну виводимо з базису. За нового рішення цільова функція зменшується, т.к.

Алгоритм:

1. Завдання ЛП у стандартній формі.

2. Залишаємо лінійно незалежні рівняння.

3.Знаходимо матрицю B, таку що |B|<>0 та базисне рішення.

Обчислюємо:

якщо, то оптимальне рішення є - базове рішення;

якщо, то знаходимо компоненту, надаємо таким чином знайдемо інше рішення; – у якому одне з базисних змінних =0. Цю змінну викидаємо з базису, вводимо xi. Отримали новий базис B2, пов'язаний з базисом B1. Потім знову обчислюємо.

1.Если є оптимальне рішення, через кінцеве число кроків ми його отримаємо.

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

9. Економічна інтерпретація задачі, двоїстої задачі про використання ресурсів

Завдання.Для виготовлення двох видів продукції P1 та P2 використовують чотири види ресурсів S1, S2, S3, S4. Дано запаси ресурсів, число одиниць ресурсів, що витрачаються на виготовлення одиниці продукції. Відома прибуток, що отримується від одиниці продукції P1 та P2. Необхідно скласти такий план виробництва, у якому прибуток від її реалізації буде максимальною.

ЗавданняI(вихідна):

F=c1x1+c2x2+…+CnXn->max при обмеженнях:

та умови невід'ємності x1>=0, x2>=0,…,Xn>=0

Скласти такий план випуску продукції X=(x1,x2,…,Xn), у якому прибуток (виручка) від продукції буде максимальної за умови, що споживання ресурсів у кожному виду продукції не перевищить наявних запасів

ЗавданняII(двійна)

Z=b1y1+b2y2+…+BmYm->min

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

та умови невід'ємності

y1> = 0, y2> = 0, ..., yn> = 0.

Знайти такий набір цін (оцінок) ресурсів Y = (y1, y2, ..., yn), за якого загальні витрати на ресурси будуть мінімальними за умови, що витрати на ресурси при виробництві кожного виду продукції будуть не менше прибутку (виручки) від реалізації цієї продукції

У наведеній моделі bi(i=1,2,…,m) означає запас ресурсу Si; aij - число одиниць ресурсу Si, споживаного під час виробництва одиниці виробленої продукції Pj(j=1,2,…,n); cj- прибуток (виручка) від одиниці продукції Pj (або ціна продукції Pj) .

Припустимо, певна організація вирішила закупити ресурси S1,S2,…,Sm підприємства міста і необхідно встановити оптимальні ціни ці ресурси y1,y2,…,ym. Очевидно, що організація, що купує, зацікавлена ​​в тому, щоб витрати на всі ресурси Z у кількостях b1,b2,…,bm за цінами відповідно y1,y2,…,ym були мінімальні, тобто. Z=b1,y1+b2y2+...+bmym->min.

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

На виготовлення одиниці продукції P1 витрачається a11 одиниць ресурсу S1, a21 одиниць ресурсу S2,…., aj1 одиниць ресурсу Si1,……, am1 одиниць ресурсу Sm за ціною відповідно y1,y1,…,yi,…,ym. Тому задоволення вимог продавця витрати на ресурси, що споживаються при виготовленні одиниці продукції P1 повинні бути не менше її ціни c1, тобто. a11y1+a21y2+…+am1ym>=c1.

Аналогічно можна скласти обмеження як нерівностей по кожному виду продукції P1,P2,…Pn. Економіко-математична модель та змістовна інтерпретація отриманої таким чином двоїстої задачі II наведені у правій частині таблиці.

Ціни ресурсів y1,y1,…,yi,…,ym в економічній літературі отримали різні назви: облікові, неявні, тіньові . Сенс цих назв у тому, що це умовні , "несправжні" ціни. На відміну від "зовнішніх" цін c1,c2,…,cn на продукцію, відомих, як правило, до початку виробництва, ціни ресурсів y1,y2,…,ym є внутрішніми , бо вони задаються не ззовні, а визначаються безпосередньо в результаті вирішення задачі, тому їх чаші називають оцінками ресурсів.

10.Взаємно двоїсті завдання ЛП та їх властивості

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

Обидві завдання мають наступні властивостями:

1.В одному завданні шукають максимум лінійної функції, в іншому – мінімум.

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

3.Кожне із завдань задане в стандартній формі, причому в задачі максимізації всі нерівності виду<=", а в задаче минимизации – все неравенства вида ">=".

4.Матриці коефіцієнтів при змінних системах обмежень обох завдань є транспонованими друг до друга.

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

6.Умови невід'ємності змінних зберігаються в обох задачах.

Зауваження.Якщо на j-ю зміннувихідного завдання накладено умову невід'ємності, то j-е обмеженнядвоїстої задачі буде нерівністю, якщо ж j-я змінна може приймати як позитивні, так і негативні значення, то j-е обмеження двоїстої задачі буде рівнянням; аналогічно пов'язані між собою обмеження вихідного завдання та змінні двоїстої.

Дві задачі I і II лінійного програмування, що мають зазначені властивості, називаються симетричними взаємно двоїстими завданнями. Надалі для простоти називатимемо їх просто двоїстими завданнями.

Кожному завданню ЛП можна поставити у відповідність подвійне їй завдання.

11. Алгоритм складання двоїстої задачі:

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

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

3. Знайти матрицю, транспоновану до матриці A .

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

12. Перша теорема двоїстості

Зв'язок між оптимальними рішеннями двоїстих завдань встановлюється за допомогою теорем подвійності.

Достатня ознака оптимальності.

Якщо X*=(x1*,x2*,…,xn*) і Y*=(y1*,y2*,…,ym*) – допустимі рішення взаємно двоїстих завдань, для яких виконується рівність,

то – оптимальне рішення вихідної задачі I, а – двоїстої задачі II.

Крім достатньої ознаки оптимальності взаємно двоїстих завдань існують інші важливі співвідношення між рішеннями. Насамперед виникають питання: чи завжди кожної пари двоїстих завдань є одночасно оптимальні рішення; чи можлива ситуація, коли одне з двоїстих завдань має рішення, а інше немає. Відповідь ці питання дає наступна теорема.

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

Fmax = Zmin або F(X*)=Z(Y*) .

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

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

Економічний сенс першої теореми двоїстості.

План виробництва X*=(x1*,x2*,…,xn*) та набір цін (оцінок) ресурсів Y*=(y1*,y2*,…,ym*) виявляються оптимальними тоді і лише тоді, коли прибуток (виручка) від продукції, знайдена при "зовнішніх" (відомих заздалегідь) цінах c1, c2, ..., cn, дорівнює витратам на ресурси за "внутрішніми" (визначаються тільки з вирішення задачі) цінами y1 ,y2,…,ym. Для всіх інших планів Хі Yобох завдань прибуток (виручка) від продукції завжди менший (або дорівнює) витрат на ресурси.

Економічний сенс першої теореми двоїстості можна інтерпретувати і так: підприємству байдуже, чи виробляти продукцію за оптимальним планом X*=(x1*,x2*,…,xn*) і отримати максимальний прибуток (виторг) Fmax або продавати ресурси за оптимальними цінами Y* =(y1*,y2*,…,ym*) та відшкодувати від продажу рівні їй мінімальні витрати на ресурси Zmin.

13. Друга теорема двоїстості

Нехай дані два взаємно двоїсті завдання. Якщо кожну з цих задач вирішувати симплексним методом, необхідно привести їх до канонічного виду, навіщо в систему обмежень завдання I (у короткому запису) слід запровадити тневід'ємних змінних, а систему обмежень задачі II () – n неотрицательных змінних, де i(j) – номер нерівності, куди введена додаткова змінна.

Системи обмежень кожної із взаємно двоїстих завдань набудуть вигляду:

Встановимо відповідність між початковими змінними однієї з двоїстих завдань та додатковими змінними іншого завдання (таблиця).

Теорема. Позитивним (ненульовим) компонентам оптимального розв'язання однієї з взаємно двоїстих завдань відповідають нульові компоненти оптимального розв'язання іншого завдання, тобто. для будь-яких i=1,2,…,m u j=1,2,…,n: якщо X*j>0, то; якщо , то, і аналогічно,

якщо то ; якщо то.

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

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

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

14. Об'єктивно обумовлені оцінки та їх зміст

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

Додаткові змінні вихідної задачі I, що представляють різницю між запасами ресурсів bi S1,S2,S3,S4 та їх споживанням, виражають залишки ресурсів , а додаткові змінні двоїстої задачі II, що становлять різницю між витратами на ресурси для виробництва з них одиниці продукції та цінами cj продукції P1,P2 , висловлюють перевищення витрат за ціною.

Т.ч., об'єктивно обумовлені оцінки ресурсів визначають ступінь дефіцитності ресурсів: за оптимальним планом виробництва дефіцитні (тобто повністю використовувані) ресурси одержують ненульові оцінки, а недефіцитні – нульові оцінки. Розмір y*i є оцінкою i-го ресурсу. Що значення оцінки y*i, то вище дефіцитність ресурсу. Для недефіцитного ресурсу y * i = 0.

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

Третя теорема двоїстості . Компоненти оптимального вирішення двоїстої задачі дорівнюють значенням приватних похідних лінійної функції Fmax(b1, b2,…, bm)за відповідними аргументами, тобто.

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

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

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

1. Показником дефіцитності ресурсів та продукції.

2.Показником впливу обмежень на значення цільової функції.

3.Показником ефективності виробництва окремих видів продукції з позицій критерію оптимальності.

4.Інструментом зіставлення сумарних умовних витрат і результатів.

15. Постановка транспортного завдання за критерієм вартості.

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

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

Найпростіше формулювання ТЗ за критерієм вартості таке: тпунктах відправлення A1,…,Am знаходиться відповідно a1,…,am одиниць однорідного вантажу (ресурси), який має бути доставлений nспоживачам B1, ..., Bn у кількостях b1,…,bn одиниць (потреби). Відомі транспортні витрати Cij перевезень одиниці вантажу з i-го пункту відправлення в j-й пункт споживання.

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

Для наочності умови ТЗ представимо у вигляді таблиці, що називається розподільчою .

Постачальник	Споживач			Запас вантажу
Потреба

Тут кількість вантажу, що перевозиться з i-го пункту відправлення в j-й пункт призначення, дорівнює xij, запас вантажу в i-му пунктівідправлення визначається величиною ai>=0, а потреба j-го пункту призначення у вантажі дорівнює bj>=0. Передбачається, що це xij>=0.

Матриця називається матрицею тарифів (Витрат або транспортних витрат).

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

Загальні сумарні витрати, пов'язані з реалізацією плану перевезень, можна уявити цільовою функцією

Змінні xij повинні задовольняти обмеження щодо запасів, споживачів та умов невід'ємності:

– обмеження щодо запасів (2);

– обмеження щодо споживачів (2);

- Умови невід'ємності (3).

Таким чином, математично транспортне завдання формулюється в такий спосіб. Дано систему обмежень (2) за умови (3) та цільову функцію (1). Потрібно серед множини рішень системи (2) знайти таке невід'ємне рішення, яке мінімізує функцію (1).

Система обмежень задачі (1) – (3) містить m+n рівнянь з тnзмінними. Передбачається, що сумарні запаси дорівнюють сумарним потребам, тобто.

16. Ознака дозвільності транспортного завдання

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

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

Відкриту модель можна перетворити на закриту. Так, якщо, то в математичну модель транспортного завдання вводиться фіктивний (n+1) пункт призначення. Для цього в матриці завдання передбачається додатковий стовпець, для якого потреба дорівнює різниці між сумарною потужністю постачальників та фактичним попитом споживачів:

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

Якщо ж, то вводиться фіктивний (m+1) пункт відправлення, якому приписують запас вантажу, рівний.

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

Для транспортного завдання важливе значення має така теорема.

Теорема. Ранг матриці транспортного завдання на одиницю меншу за кількість рівнянь, тобто. r ( a )= m + n -1.

З теореми слід, кожен опорний план повинен мати (m-1)(n-1) вільних змінних, рівних нулю, і m+n-1 базисних змінних.

План перевезень транспортного завдання відшукуватимемо у розподільчій таблиці. Приймемо, що якщо змінна xij набуває значення, то відповідну клітину (I,j) будемо записувати це значення, якщо ж xij=0, то клітину (I,j) залишимо вільною. З урахуванням теореми про ранг матриці у розподільчій таблиці опорний план має містити m+n-1 зайнятих клітин, А інші будуть вільні.

Зазначені вимоги до опорного плану є єдиними. Опорні плани повинні задовольняти ще одну вимогу, пов'язану з циклами.

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

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

З набором клітин циклу пов'язані такі важливі властивості планів транспортного завдання:

1) допустимий план транспортної задачі є опорним тоді і лише тоді, коли із зайнятих цим планом клітин не можна утворити жодного циклу;

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

17. Побудова вихідного опорного плану

Правило «північно-західного кута».

Для складання вихідного плану перевезень зручно користуватися правилом «північно-західного кута», яке полягає у наступному.

Заповнюватимемо, починаючи з лівого верхнього, умовно званого «північно-західним кутом», рухаючись далі по рядку вправо або по стовпцю вниз. Занесемо в клітку (1; 1) менше чисел a1 і b1, тобто . Якщо, то перший стовпець «закритий», т. е. попит першого споживача задоволений повністю. Це означає, що для всіх інших клітин першого стовпця кількість вантажу для .

Якщо, то аналогічно «закривається» перший рядок, тобто для . Переходимо до заповнення сусідньої клітини (2; 1), яку заносимо.

Заповнивши другу клітинку (1; 2) або (2; 1), переходимо до заповнення наступної третьої клітини за другим рядком або другим стовпцем. Продовжуватимемо цей процес доти, доки на якомусь етапі не вичерпаються ресурси am та потреби bn. Остання заповнена клітина виявиться що лежить в останньому n-му стовпці і останньої m-їрядку.

Правило "мінімального елемента".

Вихідний опорний план, побудований за правилом «північно-західного кута», зазвичай виявляється дуже далеким від оптимального, тому що при його визначенні не враховуються величини витрат cij. Тож у подальших розрахунках потрібно багато ітерацій задля досягнення оптимального плану. Число ітерацій можна скоротити, якщо вихідний план будувати за правилом "мінімального елемента". Сутність його полягає в тому, що на кожному кроці здійснюється максимально можливе переміщення вантажу в клітину з мінімальним тарифом cij. Заповнення таблиці починаємо із клітини, якій відповідає найменший елемент cij матриці тарифів. У клітку з найменшим тарифом поміщають менше чисел ai або bj . Потім із розгляду виключають рядок, що відповідає постачальнику, запаси якого повністю витрачені, або стовпець, який відповідає споживачеві, попит якого повністю задоволений. Може виявитися, що слід виключити рядок і стовпець одночасно, якщо повністю витрачені запаси постачальника і задоволений попит споживача. Далі з клітин таблиці, що залишилися, знову вибирають клітину з найменшим тарифом і процес розподілу запасів продовжують доти, поки всі вони не будуть розподілені, а попит задоволений.

18. Метод потенціалів

Загальний принцип визначення оптимального плану транспортного завдання методом потенціалів аналогічний принципу розв'язання задачі ЛП симплексним методом, а саме: спочатку знаходять опорний план транспортного завдання, а потім його послідовно покращують до отримання оптимального плану.

Сутність методу потенціалів ось у чому. Після того як знайдено вихідний опорний план перевезень, кожному постачальнику (кожному рядку) ставимо у відповідність деяке число, зване потенціалом постачальника Ai , а кожному споживачеві (кожному стовпцю) – деяке число зване потенціалом споживача.

Ціна тонни вантажу в пункті дорівнює вартості тонни вантажу до перевезення + витрати на її перевезення: .

Щоб вирішити транспортне завдання методом потенціалів, необхідно:

1. Побудувати опорний план перевезень за одним із викладених правил. Число заповнених клітин має бути m+n-1.

2. Обчислити потенціали і постачальників і споживачів (для зайнятих клітин): . Число заповнених клітин – m+n-1, а кількість рівнянь – m+n. Т.к. число рівнянь на одиницю менше від числа невідомих, то одне з невідомих виявляється вільним і може набувати будь-якого числового значення. Наприклад, . Інші потенціали для даного опорного рішення визначаться однозначно.

3. Перевірити оптимальність, тобто. для вільних клітин обчислити оцінки. Якщо, то перевезення є доцільним і план X оптимальний – ознака оптимальності. Якщо хоча б одна різниця, то переходять до нового опорного плану. За своїм економічним змістом величина характеризує ту зміну у сумарних транспортних витратах, що відбудеться через здійснення одиничного постачання i-м постачальником j-му споживачеві. Якщо, то одиничне постачання призведе до економії транспортних витрат, а якщо – до збільшення їх. Отже, якщо серед вільних напрямів поставок немає напрямків, що заощаджують транспортні витрати, то отриманий план оптимальний.

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

а) Кожній із клітин, пов'язаних циклом з цією вільною клітиною, приписують певний знак, причому цій вільній клітині «+», а решті клітин (вершинам циклу) – по черзі знаки «–» і «+». Будемо називати ці клітини мінусовими та плюсовими.

б) У мінусових клітинах циклу знаходимо мінімальне постачання, яке позначимо через. У цю вільну клітину переносять менше чисел xij, що стоять у мінусових клітинах. Одночасно це число додають до відповідних чисел, що стоять у клітинах зі знаком «+», і віднімають із чисел, що стоять у мінусових клітинах. Клітина, яка раніше була вільною, стає зайнятою та входить до опорного плану; а мінусова клітина, в якій стояло мінімальне з чисел xij, вважається вільною і виходить із опорного плану.

Т.ч., визначили новий опорний план. Описаний вище перехід від одного опорного плану до іншого називається зсувом циклу перерахунку. При зрушенні за циклом перерахунку число зайнятих клітин залишається незмінним, саме залишається рівним m+n-1. При цьому якщо в мінусових клітинах є два або більше однакових числа xij, то звільняють лише одну з таких клітин, інші залишають зайнятими з нульовими поставками.

5. Отриманий опорний план перевіряють оптимальність, тобто. повторюють усі дії з п.2.

19. Поняття динамічного програмування.

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

Зазвичай методами ДП оптимізують роботу деяких керованих систем, ефект якої оцінюється. адитивний, або мультиплікативний, цільової функції. Адитивнийназивається така функція кількох змінних f(x1,x2,…,xn), значення якої обчислюється як сума деяких функцій fj, що залежать лише від однієї змінної xj: . Доданки адитивної цільової функції відповідають ефекту рішень, що приймаються на окремих етапах керованого процесу.

Принцип оптимальності Р. Беллмана.

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

1. об'єктом дослідження має служити керована система (об'єкт) із заданими допустимими станами та допустимими управліннями;

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

3. завдання має залежати від кількості кроків і бути визначеною кожному з них;

4. стан системи кожному кроці має описуватися однаковим (за складом) набором параметрів;

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

Розглянемо питання застосування моделі динамічного програмування у узагальненому вигляді. Нехай стоїть завдання управління деяким абстрактним об'єктом, який може перебувати у різних станах. Поточний стан об'єкта ототожнюється з деяким набором параметрів, який позначається надалі S і називається вектором стану. Передбачається, що встановлено безліч S всіх можливих станів. Для об'єкта визначено також безліч допустимих управлінь(керуючих впливів) X,яке, не применшуючи спільності, можна вважати числовим безліччю. Керуючі впливи можуть здійснюватися в дискретні моменти часу, причому управлінське Рішенняполягає у виборі одного з управлінь. Планомзавдання або стратегією управлінняназивається вектор x = (x1, x2, ..., xn-1), компонентами якого служать управління, вибрані на кожному кроці процесу. Зважаючи на передбачуване відсутності післядіїміж кожними двома послідовними станами об'єкта Sk і Sk+1 існує відома функціональна залежність, що включає також обране управління: . Тим самим завдання початкового стану об'єкта та вибір плану ходнозначно визначають траєкторію поведінкиоб'єкт.

Ефективність керування на кожному кроці kзалежить від поточного стану Sk, вибраного керування xk і кількісно оцінюється за допомогою функцій fk(xk,Sk), що є складовими адитивної цільової функції , характеризує загальну ефективність управління об'єктом. (Зазначимо , що визначення функції fk(xk,Sk) включається область допустимих значень xk , і ця область зазвичай залежить від поточного стану Sk). Оптимальне керування , при заданому початковому стані S1 зводиться до вибору такого оптимального плану x* , при якому досягається максимум суми значень fk на відповідній траєкторії

Основний принцип динамічного програмування у тому, що у кожному кроці слід прагнути немає ізольованої оптимізації функції fk(xk,Sk), а вибирати оптимальне управління x*k у припущенні оптимальності всіх наступних кроків. Формально вказаний принцип реалізується шляхом відшукання на кожному кроці k умовних оптимальних управлінь , Що забезпечують найбільшу сумарну ефективність починаючи з цього кроку, припущення, що поточним є стан S.

Позначимо Zk(s) максимальне значення суми функцій fk протягом кроків від kдо п(одержуване за оптимального управління на даному відрізку процесу), за умови, що об'єкт на початку кроку kзнаходиться в стані S. Тоді функції Zk(s) повинні задовольняти рекурентному співвідношенню:

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

Оптимальна стратегія управління повинна задовольняти таку умову: який би не був початковий стан sk на k-му кроціта обране на цьому кроці керування xk, подальші управління (управлінські рішення) повинні бути оптимальними щодо cocmo янію ,що отримується в результаті рішення, прийнятого на кроці k .

Основне співвідношення дозволяє знайти функції Zk(s) тільки впоєднанні з початковою умовою,яким у нашому випадку є рівність.

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

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

20. Поняття про ігрові моделі.

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

Для кожної формалізованої гри вводяться правила , тобто. система умов, визначальна: 1) варіанти дій гравців; 2) обсяг інформації кожного гравця щодо поведінки партнерів; 3) виграш, якого призводить кожна сукупність действий. Як правило, виграш (або програш) може бути заданий кількісно; наприклад, можна оцінити програш банкрутом, виграш – одиницею, а нічию – 1/2. Кількісна оцінка результатів гри називається платежем .

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

Гра називається грою з нульовою сумою, або антагоністичне ський , якщо виграш однієї з гравців дорівнює програшу іншого, тобто. сума виграшів обох сторін дорівнює нулю. Для повного завдання гри достатньо вказати величину одного з них . Якщо позначити а- Виграш одного з гравців, b – виграш іншого, то для гри з нульовою сумою b = –атому досить розглядати, наприклад а.

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

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

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

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

Одним із основних понять теорії ігор є поняття стратегії .

Стратегією гравця називається сукупність правил, що визначають вибір його дії при кожному особистому ході залежно від ситуації, що склалася. Зазвичай, у процесі гри при кожному особистому ході гравець робить вибір залежно від конкретної ситуації. Проте в принципі можливо, що всі рішення прийняті гравцем заздалегідь (у відповідь на будь-яку ситуацію, що склалася). Це означає, що гравець вибрав певну стратегію, яка може бути поставлена ​​у вигляді списку правил або програми. (Так можна здійснити гру за допомогою ЕОМ). Гра називається кінцевою , якщо у кожного гравця є кінцева кількість стратегій, та нескінченною .– в іншому випадку.

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

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

Метою теорії ігор є визначення оптимальної стратегії кожного гравця.

21. Платіжна матриця. Нижня та верхня ціна гри

Кінцева гра, в якій гравець Амає тстратегій, а гравець В – пстратегій називається грою m×n.

Розглянемо гру m×n двох гравців Аі В(«Ми» і «противник»).

Нехай гравець Амає в своєму розпорядженні тособистими стратегіями, які позначимо A1, A2, ..., Am. Нехай у гравця Вє nіндивідуальних стратегій, позначимо їх B1, B2, ..., Bn.

Нехай кожна сторона вибрала певну стратегію; нам це буде Ai, для противника Bj. Через війну вибору гравцями будь-якої пари стратегій Ai і Bj() однозначно визначається результат гри, тобто. виграш aij гравця А(позитивний або негативний) та програш (-aij) гравця Ст.

Припустимо, що значення aij відомі будь-якої пари стратегій (Ai,Bj) . Матриця P=aij , елементами якої є виграші, що відповідають стратегіям Ai та Bj, називається платіжною матрицею або матрицею гри. Рядки цієї матриці відповідають стратегіям гравця А,а стовпці – стратегіям гравця B. Ці стратегії називають чистими.

Матриця гри m×n має вигляд:

Розглянемо гру m×n з матрицею та визначимо найкращу серед стратегій A1,A2,…,Am . Вибираючи стратегію Ai гравець Аповинен розраховувати, що гравець Ввідповість на неї тією зі стратегій Bj для якої виграш для гравця Амінімальний (гравець Впрагне "нашкодити" гравцеві A).

Позначимо через найменший виграш гравця Апри виборі стратегії Ai для всіх можливих стратегій гравця В(найменше в i-й рядку платіжної матриці), тобто.

Серед усіх чисел () оберемо найбільше: .

Назвемо нижньою ціною гри, або максимальним виграшем (максміном). Це гарантований виграш гравця А за будь-якої стратегії гравця В. Отже,

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

Серед усіх чисел виберемо найменше

і назвемо верхньою ціною гри або мінімаксним виграшем(Мінімаксом). Його гарантований програш гравця В. Отже,

Стратегія, що відповідає мінімаксу, називається мінімаксною стратегією.

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

Теорема. Нижня ціна гри завжди не перевищує верхню ціну гри .

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

Якщо один із гравців (наприклад А)дотримується своєї оптимальної стратегії, а інший гравець (В)буде будь-яким способом відхилятися від своєї оптимальної стратегії, для гравця, який припустився відхилення, це ніколи не може виявитися вигідним;таке відхилення гравця Вможе у разі залишити виграш незмінним. а в найгіршому випадку – збільшити його.

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

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

Гра, для якої , називається грою із силовою точкою. Елемент, що має цю властивість, силовою точкою матриці.

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

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

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

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

22. Рішення гри у змішаних стратегіях.

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

Змішаною стратегією Sa гравця A називається застосування чистих стратегій A1,A1,…,Ai,…,Am з ймовірностями p1,p2,…pi,…pm, причому сума ймовірностей дорівнює 1: . Змішані стратегії гравця A записуються як матриці

або у вигляді рядка Sa = (p1, p2, ..., pi, ..., pm).

Аналогічно змішані стратегії гравця B позначаються:

Або Sb = (q1, q2, ..., qi, ..., qn),

де сума можливостей появи стратегій дорівнює 1: .

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

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

Де α та β – нижня та верхня ціни гри.

Висловлене твердження становить зміст так званої основний теореми теорії ігор.Ця теорема була вперше доведена Джоном фон Нейманом у 1928 р. Відомі докази теореми порівняно складні; тому наведемо лише її формулювання.

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

З основної теореми випливає, кожна кінцева гра має ціну.

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

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

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

Ця теорема має велике практичного значення – вона дає конкретні моделі знаходження оптимальних стратегій за відсутності сідлової точки.

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

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

Для того, щоб їх знайти, скористаємося теоремою про активні стратегії. Якщо гравець Адотримується своєї оптимальної стратегії , то його середній виграш дорівнюватиме ціні гри vЯкою б активною стратегією не користувався гравець Ст.Для гри 2х2 будь-яка чиста стратегія супротивника є активною, якщо відсутня сервісна точка. Виграш гравця А(програш гравця В)- Випадкова величина, математичне очікування (середнє значення) якої є ціною гри. Тому середній виграш гравця А(оптимальна стратегія) дорівнюватиме vі для 1-ї, і для 2-ї стратегії супротивника.

Нехай гра задана платіжною матрицею.

Середній виграш гравця А,якщо він використовує оптимальну змішану стратегію, а гравець В –чисту стратегію B1 (це відповідає 1-му стовпцю платіжної матриці Р),дорівнює ціні гри v: .

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

Вирішуючи цю систему, отримаємо оптимальну стратегію

та ціну гри.

Застосовуючи теорему про активні стратегії при відшуканні – оптимальної стратегії гравця В,отримуємо, що за будь-якої чистої стратегії гравця А (A1 або A2) середній програш гравця Вдорівнює ціні гри v, тобто.

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

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

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

Якщо всі елементи i-го рядка матриці менші за відповідні елементи k-ого рядка, то i-а стратегія для гравця Аневигідна (виграш менший).

Якщо всі елементи r-го стовпця матриці більші за відповідні елементи j-го стовпця, то для гравця В r-а стратегія невигідна (програш більше).

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

23. Геометрична інтерпретація гри 2×2

Рішення гри 2×2допускає наочну геометричну інтерпретацію.

Нехай гра задана платіжною матрицею P = (aij), i, j = 1,2.

По осі абсцис (мал.) відкладемо одиничнийвідрізок A1A2; точка A1 ( х=0) зображує стратегію A1, точка A2 ( х=1) зображує стратегію A2, а всі проміжні точки цього відрізка – змішані стратегії Sa першого гравця, причому відстань від Sa до правого кінця відрізка – це ймовірність p1 стратегії A1 , відстань до лівого кінця – ймовірність p2 стратегії A2 .

Проведемо через точки A1 та A2 два перпендикуляри до осі абсцис: вісь I-I та вісь II-II. На осі I-Iвідкладатимемо виграші при стратегії A1; на осі II-II – виграші за стратегії A2.

Якщо гравець A застосовує стратегію A1, то його виграш за стратегії B1 гравця B дорівнює a11, а при стратегії B2 він дорівнює a12. Числам a11 та a12 на осі I відповідають точки B1 та B2.

Якщо гравець A застосовує стратегію A2, його виграш при стратегії B1 гравця B дорівнює a21, а за стратегії B2 він дорівнює a22. Числам a21 та a22 відповідають точки B1 та B2 на осі II.

З'єднуємо між собою точки B1(I) та B1(II); B2 (I) та B2 (II). Отримали дві прямі. Пряма B1B1 - якщо гравець Азастосовує змішану стратегію (будь-яке поєднання стратегій A1 і A2 з ймовірностями p1 і p2) і гравець В стратегію B1. Виграшу гравця Авідповідає деяка точка, що лежить на цій прямій. Середній виграш, що відповідає змішаній стратегії, визначається за формулою a11p1+a21p2 та зобразиться точкою M1 на прямий B1B1.

Аналогічно будуємо відрізок B2B2, що відповідає застосуванню другим гравцем стратегії B2. При цьому середній виграш визначається за формулою a12p1+a22p2 та зобразиться точкою M2 на прямий B2B2.

Нам потрібно знайти оптимальну стратегію S*a, тобто таку, для якої мінімальний виграш (при будь-якій поведінці В)звертався б у максимум. Для цього збудуємо нижній кордон виграшу при стратегіях B1B2 , т. е. ламану B1NB2 відзначену на рис. жирною лінією. Ця нижня межа виражатиме мінімальний виграш гравця Аза будь-яких його змішаних стратегій; точка, крапкаN , в якій цей мінімальний виграш досягає максимуму і визначає рішення (оптимальну стратегію) і ціну гри. Ордината точки Nє ціна гри v. Координати точки Nзнаходимо як координати точок перетину прямих B1B1 та B2B2. У разі рішення гри визначалося точкою перетину стратегій. Однак, це не завжди буде так.

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

Якщо платіжна матриця містить негативні числа, то графічного розв'язання завдання краще перейти до нової матриці з неотрицательными елементами; для цього до елементів вихідної матриці достатньо додати відповідне додатне число. Рішення гри при цьому не зміниться, а ціна гри збільшиться на це число. Графічний метод можна застосовувати під час вирішення гри 2×n, m×2.

24. Приведення матричної гри до завдання лінійного програмування

Гра m×n у випадку немає наочної геометричної інтерпретації. Її рішення досить трудомістке за великих ті n, проте принципових труднощів немає, оскільки то, можливо зведено до вирішення завдання лінійного програмування. Покажемо це.

Нехай гра m×n задана платіжною матрицею . Гравець Амає стратегії A1,A2,..Ai,..Am , гравець В –стратегіями B 1,B 2,..B i,.. B n. Необхідно визначити оптимальні стратегії та, де – ймовірність застосування відповідних чистих стратегій Ai,Bj,

Оптимальна стратегія задовольняє наступну вимогу. Вона забезпечує гравцю Асередній виграш, не менший, ніж ціна гри v, за будь-якої стратегії гравця Ві виграш, рівний ціні гри v, за оптимальної стратегії гравця Ст.Без обмеження спільності вважаємо v> 0; цього можна досягти, зробивши всі елементи . Якщо гравець Азастосовує змішану стратегію проти будь-якої чистої стратегії Bj гравця В,то він отримує середній виграш , або математичне очікування виграшу (тобто елементи j-гoстовпця платіжної матриці почленно множаться на відповідні ймовірності стратегій A1,A2,..Ai,..Am та результати складаються).

Для оптимальної стратегії всі середні виграші не менші за ціну гри vтому отримуємо систему нерівностей:

Кожну з нерівностей можна розділити на число. Введемо нові змінні: . Тоді система набуває вигляду

Мета гравця А -максимізувати свій гарантований виграш, тобто. ціну гри v.

Розділивши на рівність, отримуємо, що змінні задовольняють умові: . Максимізація ціни гри vеквівалентна мінімізації величини , тому завдання може бути сформульована таким чином: визначити значення змінних , maдо, щоб вони задовольняли лінійним обмеженням(*) та при цьому лінійна функція (2*) зверталася до мінімуму.

Це завдання лінійного програмування. Вирішуючи задачу (1*)–(2*), отримуємо оптимальне рішення та оптимальну стратегію .

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

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

Якщо позначити (4*) , то отримаємо систему нерівностей:

Змінні задовольняють умову.

Гра звелася до наступного завдання.

Визначити значення змінних , які задовольняють системі нерівностей (5*)і максимізують лінійну функцію

Розв'язання задач лінійного програмування (5*), (6*) визначає оптимальну стратегію. При цьому ціна гри. (7*)

Склавши розширені матриці для завдань (1*), (2*) та (5*), (6*), переконуємось, що одна матриця вийшла з іншої транспонуванням:

Таким чином, завдання лінійного програмування (1*), (2*) та (5*), (6*) є взаємно-двійними. Вочевидь, щодо оптимальних стратегій у конкретних завданнях слід вибрати ту із взаємно-двійних завдань, розв'язання якої менш трудомістке, а розв'язання іншого завдання знайти з допомогою теорем двоїстості.

При вирішенні довільної кінцевої гри розміру m×n рекомендується дотримуватися наступної схеми:

1. Виключити з платіжної матриці свідомо невигідні стратегії проти іншими стратегіями. Такими стратегіями для гравця А

Дослідження операцій

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

Дослідження операцій – застосування математичних, кількісних методів для обґрунтування рішень у всіх галузях цілеспрямованої людської діяльності. Дослідження операцій починається тоді, коли для обґрунтування рішень застосовується той чи інший математичний апарат. Операція- будь-який захід (система дій), об'єднаний єдиним задумом і спрямований на досягнення якоїсь мети (напр., заходи задач 1-8, вказаних нижче, будуть операціями). p align="justify"> Операція завжди є керованим заходом, тобто залежить від людини, яким способом вибрати параметри, що характеризують її організацію (у широкому сенсі, включаючи набір технічних засобів, що застосовуються в операції). Рішення(вдале, невдале, розумне, нерозумне) - всякий певний набір залежних від людини властивостей. Оптимальне- рішення, яке за тими чи іншими ознаками краще інших. Мета дослідження операцій- попереднє кількісне обґрунтування оптимальних рішень із опорою на показник ефективності. Саме прийняття рішення виходить за рамки дослідження операцій та належить до компетенції відповідальної особи (осіб). Елементи розв'язання- Параметри, сукупність яких утворює рішення: числа, вектори, функції, фізичні ознаки і т. д. Якщо елементами рішення можна розпоряджатися в певних межах, то задані («дисциплінуючі») умови (обмеження) фіксовані відразу і порушені бути не можуть (вантажопідйомність) , Розміри, вага). До таких умов відносяться кошти (матеріальні, технічні, людські), якими людина має право розпоряджатися, та інші обмеження, що накладаються рішення. Їхня сукупність формує безліч можливих рішень.

Приклади: Складається план перевезень вантажів з пунктів відправлення А 1, А 2, …, А m в пункти призначення В 1, В 2, …, В n. Елементи рішення - числа x ij , що показують, скільки вантажу буде відправлено з i-го пункту відправлення А i в j-й пункт призначення j . Рішення - сукупність чисел x 11 , x 12 , …, x m1 , x m2 , …, x mn

Не до кінця ясно майбутнє співвідношення між ІО та теорією (складних) систем.

Типові завдання

Взято з різних областей практики

1. План постачання підприємств
2. Будівництво ділянки магістралі
3. Продаж сезонних товарів
4. Снігозахист доріг
5. Протичовневий рейд
6. Вибірковий контроль продукції
7. Медичне обстеження
8. Бібліотечне обслуговування

Деякі приклади формулювань завдань, що стосуються ІО:

• Завдання складання розкладу, диспетчеризаціїтакі як Open Shop Scheduling Problem, Flow Shop Scheduling Problem, Job Shop Scheduling Problem ( англ. en:Job shop scheduling ) і т.д.

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

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

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

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

Історія

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

Після закінчення Другої світової війни групи фахівців з дослідження операцій продовжили свою роботу в Збройних силахСША та Великобританії. Публікація низки результатів у відкритій пресі викликала сплеск суспільного інтересу до цього напряму. Виникає тенденція до застосування методів дослідження операцій у комерційній діяльності, з метою реорганізації виробництва, переведення промисловості на мирні рейки. На розвиток математичних методів дослідження операцій на економіці асигнуються мільйони доларів.

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

У США впровадження методів дослідження операцій у практику управління економікою відбувалося дещо повільніше - але і там багато концернів незабаром стали залучати фахівців такого роду для вирішення проблем, пов'язаних з регулюванням цін, підвищенням продуктивності праці, прискоренням доставки товарів споживачам та ін. методів управління належало авіаційної промисловості, яка не могла не йти в ногу з зростаючими вимогами до ВПС. У 1950-1960-ті роки на Заході створюються товариства та центри дослідження операцій, що випускають власні наукові журнали, більшість західних університетів включає цю дисципліну у свої навчальні плани.

Найбільший внесок у формування та розвиток нової наукизробили Р. Акоф , Р. Беллман , Дж. Данциг, Г. Кун, Т. Сааті (Англ.)російськ. , Р. Чермен (США), А. Кофман, Р. Форд (Франція) та ін.

Важлива роль у створенні сучасного математичного апарату та розвитку багатьох напрямів дослідження операцій належить Л. В. Канторовичу, Б. В. Гнєденко, М. П. Бусленко, В. С. Михалевичу, Н. М. Мойсеєву, Ю. М. Єрмолаєву, Н. З. Шору та ін.

За визначний внесок у розробку теорії оптимального використання ресурсів в економіці академіку Л. В. Канторовичу разом із професором Т. Купмансом(США) у 1975 році присвоєно Нобелівська преміяв економіці.

Див. також

Примітки

Література

• Хемді А. Таха.Введення у дослідження операцій = Operations Research: An Introduction. – М.: Вільямс, 2007. – 912 с. - ISBN 0-13-032374-8
• Дегтярьов Ю. І.Дослідження операцій: підручник для вузів за спеціальністю АСУ. – М.: вища школа, 1986.
• Грешілов А. А.Математичні методи прийняття рішень. – М.: МДТУ ім. н.е. Баумана, 2006. – 584 с. - ISBN 5-7038-2893-7

Посилання

• Дослідження операційу каталозі посилань Open Directory Project ( dmoz).

Wikimedia Foundation. 2010 .

Дивитися що таке "Дослідження операцій" в інших словниках:

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

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

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

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

ДОСЛІДЖЕННЯ ОПЕРАЦІЙ- метод вивчення, аналізу та оцінки операцій, їх кількісних та якісних показників. Досліджує хід та результат операцій з урахуванням прийнятих рішень, кількісних та якісних характеристик співвідношення сил та засобів, способів бойового… Війна та мир у термінах та визначеннях

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

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

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

ДОСЛІДЖЕННЯ ОПЕРАЦІЙ- напрям в економіко-математичних методах, заснований на моделюванні математичних процесівта явищ. В.о. передбачає системний підхід, що полягає у пошуку суттєвих взаємодій при оцінці діяльності або стратегії будь-якої частини. Великий економічний словник

ДОСЛІДЖЕННЯ ОПЕРАЦІЙ- напрям у дослідженні та проектуванні СЧМ, заснований на математичному моделюванні процесів та явищ. В. о. передбачає системний підхід, що полягає у пошуку існуючих взаємодій при оцінці діяльності або стратегії будь-якої частини. Енциклопедичний словник з психології та педагогіки.