.

Теорія ігор, теорія графів і сіткове планування (реферат)

Язык: украинский
Формат: реферат
Тип документа: Word Doc
15 10681
Скачать документ

Реферат на тему:

Теорія ігор, теорія графів і сіткове планування

Зміст

1. Основні поняття та класифікація ігор

2. Застосування апарату теорії ігор в економіці

3. Теорія графів і сіткове планування

Список використаної літератури

Основні поняття та класифікація ігор

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

Гравці в теорії ігор — це учасники (суб’єкти) конфлікту. Вони
відрізняються іменами або номерами. Можливі дії кожної зі сторін мають
назву стратегії, або ходів.

Інтереси сторін представляються функціями виграшу (платежу)для кожного з
гравців.

Гра — це модель, яка формалізує змістовний опис конфлікту.

Теорія ігор уперше була системно викладена Дж. фон Нейманом і О.
Монгерштерном у 1944 р. В роки Другої світової війни і після неї теорія
ігор привернула увагу військових як апарат для дослідження стратегічних
рішень. Проте основним застосуванням теорії ігор стала економіка. У 1994
р. Нобелівську премію з економіки одержалиДжон Неш (США), Джон Харсаньї
(США), Рейнхард Зельтен (Німеч-чина) за праці у сфері теорії ігор.

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

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

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

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

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

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

Припустімо, кожен гравець має дві стратегії: “Так” або “Ні”. Ці
стратегії можуть являти економічний вибір, наприклад, підвищувати або
знижувати ціну та політичний вибір, наприклад, приймати або не приймати
закон. Кожному гравцю у кожній ситуації приписують число, яке виражає
ступінь задоволення його інтересів. Це число називається виграшем
гравця. Відповідність між набором ситуацій і виграшем гравця називається
функцією виграшу. У випадку скінченої гри двох осіб функції виграшу
кожного з гравців зручно представляти за допомогою матриці виграшів, де
рядки зображують стратегії одного гравця, стовпці — стратегії другого
гравця. В клітинках матриці вказують виграші кожного з гравців у кожній
з утворених ситуацій. Платіжна матриця відображає виграш кожного гравця
за кожної комбінації стратегій, що вибираються. Якщо гравці вибирають
однакові стратегії, тобто говорять “Так” або “Ні”, то виграш одного
гравця дорівнює одиниці, а програш другого гравця дорівнює мінус
одиниці.

Матриця виграшів першого гравця має вигляд:

Матриця виграшів другого гравця має вигляд:

Для наочності матрицю виграшів для обох гравців можна об’єднати в одну:

Розглянемо приклад задания матриці виграшів для гри з ненульовою сумою,
яка має назву дилеми ув’язнених. Суть гри така: двох ув’язнених —
співучасників злочину допитують в окремих кімнатах. У кожного з них є
вибір: або зізнатись у злочині і тим самим вплутати іншого, або
заперечувати свою причетність до злочину. Якщо зізнається лише один з
ув’язнених, його звільнять, і звинуваченим буде другий, якого позбавлять
волі на термін до 5 років. Якщо обидва злочинці будуть заперечувати свою
причетність до злочину, обох протримають у в’язниці до одного року, якщо
обидва зізнаються, обох ув’язнять на термін до 3 років.

Платіжна матриця цієї гри має вигляд:

Основним припущенням у теорії ігор є те, що кожен гравець праг-не
забезпечити для себе максимально можливий виграш за будь-яких дій
партнера. Припустімо, що є скінченна антагоністична гра з матрицею
виграшів першого гравця А і, відповідно, матриця виграшу другого гравця
мінус A. Гравець 1 вважає, що яку б стратегію він не обрав, гравець 2
обере стратегію, яка максимізує його виграш і тим самим мінімізує виграш
гравця 1. Оптимальна стратегія гравця 1, яка забезпечить йому найбільший
з можливих виграшів поза стратегією, яку обере суперник, буде полягати у
виборі стратегії з найвищим з таких платежів. Таким чином, гравець 1
обирає І-ту стратегію, яка є розв’язанням задачі:

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

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

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

Якщо верхня та нижня ціна гри збігаються:

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

Приклад. Розглянемо гру, в якій гравець 1 володіє трьома стратегіями, а
гравець 2 — чотирма. Матриця виграшів А гравця 1 має вигляд:

Матриця виграшів другого гравця буде дорівнювати –А. Визнач-те верхню та
нижню ціну гри та вкажіть максимінну та мінімаксну стратегії.

Знаходимо мінімальні значення в кожному рядку:

1-й рядок min (2, 4, 5, 1) = 1; 2-й рядок min (3, 5, 6, 4) = 3;

3-й рядок min (4, 1, 2, 7) = 1.

Шукаємо максимум з одержаних відповідей max (1,3,1) = 3.

Отже, нижня ціна гри дорівнює 3.

Верхня ціна гри — це:

min (max(2, 3, 4); max(4, 5, 1); max(5, 6, 2); max(1, 4, 7)) = max(4, 5,
6, 7) = 4.

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

Застосування апарату теорії ігор в економіці

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

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

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

Припустімо, ринок поділяють між двома фірмами-олігополістами: фірмою А
та фірмою В. Якщо б обидві фірми могли співпрацю-вати, то, скоротивши
випуск і призначивши монопольно високі ціни, вони одержали б і високий
прибуток по 100 грн за одиницю продукції. Однак фірми діють як
конкуренти. Тому вони можуть порушити негласну угоду всупереч
очікуванням суперника понизити ціниі захопити частину його ринку,
одержавши ще більший прибуток у140 грн за одиницю. Тоді прибуток
суперника ще більше скоротиться і становитиме, наприклад, 20 грн.
Спробуючи переграти суперника, кожен гравець вибере низькі ціни, та
обидві фірми одержать прибуток по 60 грн замість 140. Варіанти прибутків
залежно від вибору цін зображені у платіжній матриці.

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

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

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

Якщо фірма В приймає рішення призупинити виробництво, то попит повністю
задовольняється випуском фірми А. Обсяг виробництва, який максимізує
прибуток, буде визначатись з умови збігання граничного доходу і
граничних витрат. Якщо фірма В буде виробляти максимальну кількість
товару, то фірма А відреагує на це зупинкою виробництва. Якщо позначити
на графіку зміни випуску фірми А залежно від зміни випуску фірми В,
одержимо криву реакції фірмиA: Ra. Стосовно фірми В одержимо криву
реакції фірми В: Rb. Перетин кривих реагування цих двох фірм (точка Е)
показує рівновагу Курно: кожна фірма вірно передбачає поведінку
конкурента і приймає оптимальне для себе рішення.

Рівновага Курно

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

Окрім моделі Курно, дуополію можна розглядати за моделямиБертрана,
Еджуорта і Штакельбергера.

Теорія графів і сіткове планування

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

Поштовх до розвитку теорія графів одержала на межі ХІХ–ХХ ст.,коли різко
зріс інтерес до праць у галузі топології та комбінаторики. Як окрема
дисципліна теорія графів уперше була розглянута у праці угорського
математика Кьоніга у 30-ті роки XX ст. Графи ефективно використовуються
в теорії планування та управління, соціології, лінгвістиці, економіці,
медицині.

Сітки стали зручним знаряддям для опису та аналізу складних проектів.
Сіткові моделі складних комплексів робіт були розроблені і почали
використовуватись у 50-ті роки XX ст. Сіткова модель застосовувалась у
США при створенні балістичних ракет “Поларіс”,призначених для оснащення
атомних підводних човнів американського військово-морського флоту. У
комплексі робіт брало участь понад 6000 фірм, роботи виконувались на
території 48 штатів, а сітковий графік містив більше 10 тисяч подій.

Перша система планування й управління в США має назву ПЕРТ. Успіхи в її
застосуванні досить значні. Це підтверджує обов’язкове її застосування у
будівництві. Тривалість економічного процесу із застосуванням системи
скорочується на одну третину.

У СРСР найпоширенішими були системи планування та управління СПУ. В
основі цих систем лежать сіткові графіки. Системи СПУ з успіхом
застосовувались під час спорудження ТЕЦ у Лисичанську, при
реконструюванні доменної печі “Запоріжсталі”, при будівництві метромосту
через Дніпро в Києві.

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

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

Позначимо граф буквою G. Відрізки, які з’єднують точки графа, можуть
бути лінійними та нелінійними. Довжини відрізків і розташування точок є
довільними.

Приклади зображення графів

Точки графа називаються вершинами, відрізки — ребрами графа. Граф на
рис. 6.2, а, в має чотири вершини і чотири ребра. Граф нарис. 6.3, а має
5 вершин і 3 ребра, на рис. 6.3, 6— 4 вершини і 6 ребер.

Рис. 3. Приклади зображення графів

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

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

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

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

Ступінь вершини — кількість ребер графа, яким належить ця вершина.

На рис. 6, а і б зображені графи зі ступенем вершин: 2 та 0 відпо-відно.
У графа на рис. 6, в ступені вершин є різними. Вершина А маеступінь 2.
Вершини В та С мають ступінь 1.

Якщо ступінь вершини — непарне число, то вершина називається непарною, і
навпаки.

Шляхом графа від вершини А1 до вершини Аn називається послідовність
ребер від А1 до An, в якій кожні два сусідніх ребра мають спільну
вершину і кожне ребро зустрічається лише один раз. Вершина А1
називається початком шляху. Вершина Аn — кінцем шляху. Зазначенням
вершини шляху можуть повторюватись.

Шлях від A 1 до Аn називається простим, якщо він проходить через кожну
вершину графа тільки один раз.

Приклад. Знайти шляхи між вершинами графа А1 та А4. Який шлях є простим?

Шляхи між вершинами є простими:

1. (A1,A4);

2. (А1,А2), (А2,А3), (А3,А4).

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

За прикладом циклом у графі є шлях (A1, A2), (А2, А3), (А3, А4),(А4,А1).

Довжиною шляху називається кількість ребер цього шляху.

Довжиною циклу називається кількість ребер у цьому циклі.

Приклад. Визначити довжину шляху від вершини А1 до вершини А5.

Довжина шляху від А1 до А5:

1. (A1,A5) = 1;

2. (А1, А2), (А2, А3), (А3, А5) = 3.

3. (А1, А2), (А2, А3), (А3, А4), (А4, А5) = 4.

Дві вершини A j та Ап називаються зв’язаними, якщо в графі існує шлях з
кінцями A j та Ап, і незв’язаними, якщо в графі не існує жодного шляху,
що пов’язує їх.

Деревом називається будь-який зв’язаний граф, який не має циклів.

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

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

Наприклад, проект написання випускної дипломної роботи магістра містить:

1. Підбір літератури з обраної тематики або роботу з каталогом.

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

3. Робота з періодичними виданнями. Огляд статей і публікацій.

4. Ознайомлення з WEB-сторінками. Підбір потрібних адрес.

5. Складання плану дипломної роботи.

6. Обробка матеріалу на комп’ютері.

7. Групування та аналіз статистичних даних.

8. Набір роботи на комп’ютері.

9. Редагування тексту та оформлення роботи відповідно до вимог.10. Здача
дипломної роботи на рецензію.

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

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

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

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

Роботу поділяють на види: 1) реальна робота — будь-який трудовий процес,
що потребує витрат праці, часу і матеріальних ресурсів;2) очікування —
пасивний процес; 3) фіктивна робота.

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

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

Тривалість шляху в сітковому графіку — час, необхідний для виконання
всіх робіт, що лежать на шляху L. Тривалість повного шляху t(L).

Шлях, який має найбільшу тривалість, — це критичний шлях.

Визначаємо шляхи даного графа та їх тривалість.L1(0, 1, 2, 7); t(L1) =
10 + 4 + 6 = 20; L2(0, 3, 1, 2, 7);t(L2) = 5 + 7 + 4 + 6 = 22;

L3(0, 3, 4, 7); t(L3) = 5 + 2 + 10 = 17; L4(0, 5, 6, 7); t(L4) = 3 + 2 +
8 = 13.Тривалість найдовшого шляху становить 22 (доби, тижні,
години).Проект не може бути реалізований менш ніж за 22 (доби, тижні,
години).

Список використаної літератури

1. Березина Л. Ю. Графы и их применение. — М.: Просвещение, 1979.

2. Дубров А. М., Лагоша Б. А., Хрустаже Е. Ю. Моделирование рисковых
ситуаций в экономике и бизнесе: Учеб. пособие. —М.: Финансы и
статистика, 2000.

3. Замков О. О., ЧеремныхЮ. А., Толстопятенко А. В. Математические
методы в экономике: Учебник. — 2-е изд. — М.:Изд-во МГУ; Дело и сервис,
1999.

4. Мэнкъю Н. Г. Принципы экономике. — СПб.: Питер Ком, 1999.

5. Нуреев Р. М. Курс микроэкономики: Учеб. для вузов. — М.:НОРМА, 2000.

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение

Ответить

Курсовые, Дипломы, Рефераты на заказ в кратчайшие сроки
Заказать реферат!
UkrReferat.com. Всі права захищені. 2000-2020