31. Класифікація задач стохастичного програмування. Методи розв’язування задач стохастичного програмування(прямі, непрямі), приклади їх реалізації.

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

Методи розв’язування стохастичних задач поділяють на дві групи — прямі та непрямі.Прямі методи використовують для розв’язування задач стохастичного програмування, коли існують способи побудови функцій і на базі інформації щодо параметра ω. Непрямими є методи зведення стохастичної задачі до задачі лінійного чи нелінійного програмування, тобто перехід до детермінованого аналога задачі стохастичного програмування. Приклад Нехай потрібно зробити запас з n товарів у обсягах , на які є випадковий попит . За нестачі одиниці j-го товару застосовується штрафна санкція у розмірі , тобто , а затрати на зберігання одиниці відповідної продукції, яку не вдалося збути, задаються вектором Розв’язання. Функція збитків, що відповідає розв’язку Х, має вигляд: де — штраф за незадоволення попиту по j-му виду продукції; — витрати на зберігання j-ої продукції. Для знаходження оптимального розв’язку цієї задачі необхідно мати функцію розподілу ймовірностей випадкової величини ω. Якщо така функція розподілу невідома, тобто її немож¬ливо відшукати, то допускають, що випадкова величина розподілена рівномірно. В такому разі необхідно пам’ятати, що саме таке припущення може призвести до прийняття неправильного рішення.

28. Економічний зміст, деякі типи задач та моделі динамічного програмування. Алгоритм методу динамічного програмування.

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

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

2)Поділяють процес на етапи (кроки), які, як правило, відповідають певним періодам планування динамічних процесів, або окремим об’єктам у разі підготовки рішень стосовно керування ними. 3)Формулюютьперелік управлінь для кожного кроку і відповідні обмеження щодо них. 4)Визначають ефект, який забезпечує управління на j–му кроці, якщо перед тим система була у стані S, у вигляді функції ефективності: . 5)Визначають, як змінюється стан S системи під впливом управління на j-му кроці, тобто як здійснюється перехід до нового стану: .

6)Будують рекурентну залежність задачі динамічного програмування, що визначає умовний оптимальний ефект починаючи з j–го кроку і до останнього, через вже відому функцію . 7)Використовують умовну оптимізацію останнього n-го кроку, визначаючи множину станів S, з яких можна за один крок дійти до кінцевого стану. Умовно-оптимальний ефект на n-му кроці обчислюють за формулою:

8)Проводять умовну оптимізацію -го, -го та інших кроків за рекурентними залежностями і визначають для кожного кроку умовно-оптимальне управління: 9)Проводять безумовну оптимізацію управління у «зворотному» напрямку від початкового стану до кінцевого. Для цього з урахуванням визначеного оптимального управління на першому кроці змінюють стан системи згідно з пунктом 5. Потім для цього нового стану знаходять оптимальне управління на другому кроці і аналогічно ці дії повторюють до останнього етапу (кроку).В результаті знаходять оптимальне покрокове управління , що забезпечує максимальну ефективність Z*.

32. Основні поняття теорії ігор. Приклади ігрових задач в економіці та менеджменті.За умов ринкової економіки все частіше мають місце конфлікт¬ні ситуації, коли два або більше колективів (індивідуумів) мають протилежні цілі та інтереси, причому результат дії кожної із сторін залежить і від дії супротивника. Класичним прикладом конфліктної ситуації в економіці є відношення продавець — покупець. Складніші ситуації виникають, коли в суперечці інтересів беруть участь об’єднання чи коаліції. Однак не завжди учасники ігрової ситуації мають протилежні цілі. Наприклад, дві фірми, які надають однакові послуги, можуть об’єднуватися з метою спільного протистояння більшому супернику. Теорія ігор — це математичний апарат, що розглядає конфлікт¬ні ситуації, а також ситуації спільних дій кількох учасників. Завдання теорії ігор полягає у розробленні рекомендацій щодо раціональної поведінки учасників гри.

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

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

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

Оскільки гра з нульовою сумою, то

Тоді в разі, якщо то Отже, мета гравця А — максимізувати величину , а гравця В — мінімізувати її. Нехай тобто маємо матрицю А:

де рядки відповідають стратегіям Аі, а стовпці — стратегіям Bj.Матриця А називається платіжною, а також матрицею гри. Елемент цієї матриці aij — це виграш гравця А, якщо він вибрав стратегію Ai, а гравець В — стратегію Bj.Із багатьох критеріїв, які пропонуються теорією ігор для вибирання раціональних варіантів рішень, найпоширенішим є песимістичний критерій мінімаксу-максиміну. Суть цього критерію у наступному.Нехай гравець А вибрав стратегію Ai, тоді у найгіршому разі він отримає виграш, що дорівнює min aij, тобто навіть тоді, якщо гравець В і знав би стратегію гравця А. Передбачаючи таку можливість, гравець А має вибрати таку стратегію, щоб максимізувати свій мінімальний виграш, тобто,Така стратегія гравця А позначається і має назву максимінної, а величина гарантованого виграшу цього гравця називається нижньою ціною гри.Гравець В, який програє суми у розмірі елементів платіжної матриці, навпаки має вибрати стратегію, що мінімізує його максимально можливий програш за всіма варіантами дій гравця А. Стратегія гравця В позначається через і називається мінімакс¬ною, а величина його програшу — верхньою ціною гри, тобто,Оптимальний розв’язок цієї задачі досягається тоді, коли жод¬ній стороні невигідно змінювати вибрану стратегію, оскільки її супротивник може у відповідь вибрати іншу стратегію, яка забезпечить йому кращий результат. Якщо то гра називається цілком визначеною. В такому разі виграш гравця А (програш гравця В) називається значенням гри і дорівнює елементу матриці . Цілком визначені ігри називаються іграми з сідловою точкою, а елемент платіжної матриці, значення якого дорівнює виграшу гравця А (програшу гравця В) і є сідловою точкою. В цій ситуації оптимальним рішенням гри для обох сторін є вибір лише однієї з можливих, так званих чистих стратегій — максимінної для гравця А та мінімаксної для гравця В, тобто якщо один із гравців притримується оптимальної стратегії, то для другого відхилення від його оптимальної стратегії не може бути вигідним.

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

для гравця А — вектор де

для гравця В — вектор де

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

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

Нехай маємо скінченну матричну гру з платіжною матрицею

Оптимальні змішані стратегії гравців А і В за теоремою визначають вектори і , що дають змогу отримати виграш:

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

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

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

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

Отже, мета гравця А — максимізувати величину , а гравця В — мінімізувати її. Нехай , тобто маємо матрицю А:

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

1. Економіка як об'єкт математичного моделювання. Особливості та принципи математичного моделювання економіки.Економіко-математичне моделювання є спробою формалізувати процес прийняття рішення, тобто застосувати під час цього процесу точні математичні методи. За висловлюванням К. Маркса: «Наука досягає досконалості коли їй вдається користуватися математикою».Мета дисципліни - дати основні відомості про математичні методи та моделі дослідження економічних об’єктів, а також показати, як за допомогою цих методів можна, не вдаючись до вартісних економічних експериментів, оцінити різні варіанти економічної політики, передбачити в загальних рисах зміни у кон’юнктурі ринку або наслідки прийнятих рішень. Практичним завданням економіко-математичного моделю¬вання є:по-перше, аналіз економічних об'єктів і процесів; який дає поглиблене вивчення об'єкту дослідження і також спрямоване на отримання нових знань про цей об’єкт.по-друге, передбачення розвитку еконо¬мічних процесів та прогнозування наслідків від тих чи інших заходів (про¬гнозувати доходи та видатки, науково обґрунтувати необхідні зміни у фіскальній по¬літиці);по-третє, вироблення управлінських рішень на всіх рівнях господарської ієрархії управління.

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

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

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

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

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

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

Математичне програмування - математична дисципліна, що вивчає теорію й методи розв’язування задач про знаходження екстремумів функцій на множинах скінченновимірного векторного простору, обумовлених лінійними й нелінійними обмеженнями (рівностями і нерівностями). У процесі проектування ставиться, звичайно, задача визначення найкращих, у деякому значенні, структури або значення параметрів об'єктів. Така задача називається оптимізаційною. Якщо оптимізація пов'язана з розрахунком оптимальних значень параметрів при заданій структурі об'єкта, то вона називається параметричною. Задача вибору оптимальної структури є структурною оптимізацією.Стандартна математична задача оптимізації формулюється в такий спосіб. Серед елементів χ, що утворюють множину Χ, знайти такий елемент χ* , що надає мінімальне значення f(χ*) заданій функції f(χ). Для того щоб коректно поставити задачу оптимізації необхідно задати:Допустиму множину —множину ;Цільову функцію — відображення ;Критерій пошуку (max або min).Тоді вирішити задачу означає одне з:Показати, що .Показати, що цільова функція не обмежена знизу.Знайти .Якщо , то знайти .Якщо мінімізована функція не є опуклою, то часто обмежуються пошуком локальних мінімумів і максимумів: точок таких, що всюди в деякому їхньому околі для мінімуму й для максимуму.Якщо допустима множина , то така задача називається задачею безумовної оптимізації, в іншому разі — задачею умовної оптимізації.Приклади задач математичного програмування в економіці, менеджменті:1)Задача визначення оптимального плану виробництва: для деякої виробничої системи необхідно визначити план випуску кожного виду продукції за умови найкращого способу використання наявних ресурсів. Критерії оптимальності: максимум прибутку, максимум товар¬ної продукції, мінімум витрат ресурсів.

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

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