WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаЕкономічна теорія → Теорія ігор, теорія графів і сіткове планування - Реферат

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

програм легко реалізуються та використовуються.
Граф - це непуста множина точок і множина відрізків, обидва кінці яких належать заданій множині точок.
Позначимо граф буквою 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.
Loading...

 
 

Цікаве