Опорний конспект з курсу Моделювання систем для спеціальності Інтелектуальні системи прийняття рішень, НУДПСУ
« Назад
ДЕРЖАВНА ПОДАТКОВА АДМІНІСТРАЦІЯ УКРАЇНИНАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ДЕРЖАВНОЇ ПОДАТКОВОЇ СЛУЖБИ УКРАЇНИКафедра інтелектуальних систем прийняття рішеньЗатвердженона засіданні Вченої ради університету протокол №___від___________200_ р. ОПОРНИЙ КОНСПЕКТ З КУРСУ«МОДЕЛЮВАННЯ СИСТЕМ»для підготовки бакалаврівза напрямом 0804 «Комп'ютерні науки»спеціальності 6.080400 «Інтелектуальні системи прийняття рішень»денної форми навчання статус дисципліни: нормативна Ірпінь – 2009 Навчально-методичний комплекс дисципліни «Моделювання систем» містить: робочу навчальну програму, опорний конспект лекцій, методичні вказівки до проведення практичних занять, методичні вказівки до проведення індивідуальних та самостійних робіт, контрольні питання з дисципліни, література. Автор: А. О. Антонюк Розглянуто і схвалено на засіданні кафедри інтелектуальних систем прийняття рішень, протокол № ____ від «___»___________200_ р. Зав. кафедрою __________________ С.П.Ріппа, д.е.н., професор Погоджено: На засіданні вченої ради факультету економіки та оподаткування, протокол № _____ від «___»__________200_ р. Голова вченої ради факультету ______________Г.М. Калач, к.е.н., доцент Завідувач навчально-методичного відділу ____________ О.О. Бойко Реєстраційний № ________
ЗМІСТ Лекція 1. Загальна характеристика управління проектами. Обґрунтування доцільності проекту 1.1. Сутність проектної діяльності 1.2. Управління проектами як специфічна галузь менеджменту 1.3. Цілі і процеси в управлінні проектами 1.4. Функції проектного менеджменту 1.5. Характеристика моделі управління проектами 1.6. Процедури в управлінні проектами Лекція 2. Організаційні структури управління проектами 2.1. Базові засади створення організаційної структури проекту 2.2. Основні форми проектних структур 2.3. Переваги і проблеми матричної структури 2.4. Внутрішні організаційні структури у великих проектах Лекція 3. Загальні підходи до планування й контролю проектів 3.1. Місце і функції планування та контролю в управлінні проектами 3.2. Види планів 3.3. Сучасні тенденції в плануванні та контролю проектів Лекція 4. СТРУКТУРИЗАЦІЯ ПРОЕКТУ 4.1. Сутність і функції структуризації проекту 4.2. Односпрямована структуризація – створення робочої структури проекту 4.3. Двостпрямована структуризація та кодування проекту 4.4. Трьохспрямована структура проекту Лекція 5. СІТКОВЕ Й КАЛЕНДАРНЕ ПЛАНУВАННЯ ПРОЕКТУ 5.1. Загальна характеристика і види сіткових графікив 5.2. Графіки передування: порядок побудови і показники 5.3. Особливості стрілчастих графіків 5.4. Переваги і додаткові можливості графіків передування 5.5. Сіткове планування в умовах невизначеності 5.6. Методи скорочення тривалості виконання проекту 5.7. Календарне планування проектів Лекція 6. ПЛАНУВАННЯ РЕСУРСІВ І ВИТРАТ. СКЛАДАННЯ ПРОЕКТНОГО БЮДЖЕТУ 6.1. Оцінка і планування ресурсів 6.2. Побудова ресурсних гістограм 6.3. Моделювання і календарне планування ресурсів 6.4. Планування витрат Лекція 7. КОНТРОЛЬ ВИКОНАННЯ ПРОЕКТУ 7.1. Модель планування і контролю проекту 7.2. Методи аналізу виконанання проекту 7.3. Прогнозування остаточних витрат 7.4. Звітування і контроль за змінами Лекція 8. Управління проектними ризиками 8.1. Поняття ризику та невизначеності. Класифікація проектних ризиків 8.2. Причини виникнення та наслідки проектних ризиків 8.3. Методи аналізу й оцінки ризиків інвестиційних проектів 8.4. Управління проектними ризиками Лекція 9. УПРАВЛІННЯ ЯКІСТЮ ПРОЕКТІВ 9.1. Поняття якості в контексті проектного менеджменту 9.2. Система управління якістю проекту 9.3. Витрати на забезпечення якості проекту Лекція 10. ОРГАНІЗАЦІЯ ПРОВЕДЕННЯ ТОРГІВ ЗА ПРОЕКТАМИ 10.1. Основні положення 10.2. Класифікація торгів 10.3. Функції учасників торгів 10.4. Порядок проведення підрядних торгів Лекція 11. ФРМУВАННЯ Й РОЗВИТОК ПРОЕКТНОЇ КОМАНДИ 11.1. Лідерство. Роль менеджера проекту 11.2. Команда проекту 11.3. Мотивація персоналу Лекція 12. ПРОГРАМНЕ ЗАБЕЗПЕЧЕННЯ ПРОЦЕСУ УПРАВЛІННЯ ПРОЕКТАМИ 12.1. Загальна характеристика автоматизованих систем управління проектами 12.2. Microsoft Project 12.3. Open Plan Professional 12.4. Spider Project 12.5. Sure Trek Project Manager і Primavera Project Planner (P3) ПРЕДМЕТНИЙ ПОКАЖЧИК СПИСОК ЛІТЕРАТУРИ перЕДМОВАМоделювання як одну з найважливіших категорій процесу пізнання неможливо відокремити від розвитку людства. Ще з дитинства людина пізнає світ, спочатку через іграшки та ігри, і відображає, або моделює, дійсність. Згадаємо комп'ютерні ігри, в яких ми, сидячи в літаку або космічному кораблі, здійснюємо політ так, нібито дійсно знаходимося там. З роками людина використовує більш складні моделі, що дають можливість «програвати» будь-які життєві та виробничі ситуації й отримувати такі рішення, що дозволяють знайти найкращий спосіб вирішення проблеми. У таких випадках є можливість аналізувати за допомогою моделі будь-які ситуації, включаючи ті, за яких реальна система вийшла б із ладу. Це дозволяє моделювати катастрофи, рідкісні випадки, та навіть такі явища і процеси, яких не існує насправді, тобто віртуальну реальність. Методи комп'ютерного моделювання широко застосовуються в усіх сферах діяльності людини – від конструювання моделей технічних, технологічних та організаційних систем до вирішення проблем розвитку людства та всесвіту. Класичними об'єктами моделювання є інформаційні, виробничі, транспортні та інші логістичні системи, які в більшості випадків застосовуються для розв'язання задач проектування, реконструкції та довгострокового планування, а також використання моделей у контурі керування, тобто в реальному масштабі часу. Найважливішим завданням моделювання є оцінка показників функціонування таких систем. Коли слід використовувати комп'ютерне моделювання? Завжди, як тільки ми ставимо запитання: «Що буде, якщо...?», тобто для прийняття рішень. У розвинених країнах перед інвестуванням коштів у будь-який проект можливості його реалізації перевіряються на імітаційних моделях. Практично всі транснаціональні компанії мають моделі розвитку виробництва, більш того, вони вкладають значні кошти у дослідження цих моделей. Наприклад, щодо автомобільної промисловості Німеччини існує рішення до 2005 року приймати до розгляду технічну документацію тільки за умови її відповідності концепції Digitale Fabrik (комп'ютерне виробництво). Важливу роль у цій концепції відіграють ЗБ-моделі всіх елементів виробничого процесу, що замінюють собою звичайні CAD-креслення. У вигляді ЗБ-моделей повинні зображуватись усі засоби виробництва: устаткування і робочі місця, окремі цехи і підприємство в цілому, а також вироблена продукція – готові вироби з їх докладною технічною документацією. Зрозуміло також, що демонстрація будь-яких динамічних процесів можлива лише за умови, що ними керуватимуть відповідні імітаційні моделі. Треба чітко уявляти собі, що поряд із традиційними для імітаційного моделювання моделями процесів із дискретними подіями існують кінематичні ЗБ-моделі устаткування і робочих місць, ергономічні ЗБ-моделі, моделі типу Digital MockUp тощо. Моделювання як технологія розв'язання задач усередині специфічного середовища широко застосовується під час аналізу і проектування інформаційних систем для перевірки вимог до їх ефективності, до використаних ресурсів і оцінки пропускної спроможності систем. Однак розробка і застосування імітаційних моделей інформаційних систем - це не прості завдання. Етап формулювання абстрактної моделі та етап конструювання моделі часто включають тривалі й дорогі процедури. Абстрактна модель інформаційної системи звичайно створюється фахівцем із моделювання, який може отримувати знання у потрібній галузі від проектувальників і аналітиків. Модель може мати математичний характер (наприклад, системи формування черг, ланцюги Маркова або мережі Петрі), але для того щоб вона підлягала аналізу, навіть за допомогою комп'ютера, при її формулюванні роблять деякі узагальнення. Програмна реалізація моделі потім здійснюється фахівцями з моделювання, які можуть використовувати універсальну мову програмування (типу C++ або Java) або спеціалізовані засоби моделювання (такі як GPSS або iThink). Для цього часто залучаються програмісти, які є проміжною ланкою між аналітиком і людиною, що приймає рішення. Наявність такої ланки може призводити до появи помилок і неточностей не тільки під час побудови моделі, але й під час програмування. Моделювання – складний процес, що потребує багато часу, незважаючи на те, йде мова про окремого фахівця з моделювання чи цілої групи фахівців, впродовж роботи якої потрібні постійний зв'язок і координація. Зазначені причини виправдовують зусилля, докладені для розробки методів, що допомагають прискорити процес моделювання шляхом автоматизації деяких процесів. Сучасні програмні засоби моделювання використовують графічний інтерфейс і дво- або тримірну анімацію, що значно полегшує сприйняття результатів моделювання неспеціалістом. Програми реалізації моделей взагалі складно писати й налагоджувати. Для того щоб перевірити правильність і достовірність імітаційної моделі та її відповідність цілям моделювання, необхідно мати вичерпну інформацію щодо області застосування системи, методології моделювання і мови програмування. Таку роботу зазвичай виконує експерт. У якісній моделі повинні враховуватися всі можливі варіанти вихідних даних, і починати моделювання можна лише, отримавши позитивні результати. Після огляду числових результатів моделювання може виникнути потреба у внесенні деяких змін в абстрактну модель і (або) програмну реалізацію моделі, що може призвести до повторного виконання деяких або всіх операцій на різних етапах моделювання. Таким чином, жоден серйозний проект з моделювання не може бути успішно реалізований без участі експерта. Великі за обсягом моделі створює, як правило, команда розробників, і хоча б один з її членів має виконувати при цьому роль експерта. Експерт повинен:
Для того щоб стати досвідченим експертом і професіоналом, необхідно також мати досвід роботи в проектах з моделювання. З 1952 року існує всесвітнє добровільне товариство міжнародного комп'ютерного моделювання – SCS (www.scs.org), основними завданнями якого є вивчення, розповсюдження, використання й удосконалення методів комп'ютерного моделювання для вирішення реальних проблем, що існують у світі. До SCS входять професіонали, діяльність яких пов'язана з розробленням методології та застосуванням сучасних технологій і методів моделювання. Регіональні ради SCS існують у США, Канаді, країнах Європи (www.scs-europe.net), включаючи Східну Європу, в Китаї, Мексиці та інших країнах. Щороку SCS проводить конференції з проблем моделювання, публікує доповіді та випускає журнали (www.scsorg/pubs/pubsinfo.html). В Європі існує федерація європейських товариств моделювання – EUROSIM (www.eurosim.info), товариство моделювання та технології імітації – EUROSIS (http://biomath.rug.ac.be/ ~eurosis/index.html), а також інститути науки моделювання – McLeod. Комп'ютерне моделювання активно застосовується у дослідницьких центрах в усьому світі. Тільки у Великій Британії існує близько десяти груп дослідників в університетах, що працюють у цій галузі,— в Лондонській школі економіки, Імперіал-коледжі, Університеті Варвік, Університеті Ланкастера, Саутамптонському університеті тощо. Американське і європейські товариства моделювання регулярно проводять конференції та публікують їх матеріали. Добре відомі праці з імітаційного моделювання Р. Шеннона, Дж. Шрайбера, Дж. Клейнена, А. Прицкера, надруковані російською мовою. Протягом більш ніж 15 років не було перекладено жодної книжки іноземного автора відповідної тематики ні в Росії, ні в Україні, хоча тільки в США щорічно видається або перевидається чимало таких книжок. Серед останніх слід відзначити монографії, які широко використовуються в учбовому процесі багатьох університетів: А. М. Law, W. D. Kelton. Simulation Modeling and Analysis (y 2004 році перекладена російською мовою); J. Banks, J. S. Carson, B. L. Nelson. Discrete-Event System Simulation. На жаль, активне застосування методів імітаційного моделювання за кордоном не викликало поки що значного його поширення у нас в країні, незважаючи на проведення Інститутом кібернетики НАН України фундаментальних робіт у цій галузі. Пояснити те, що відбувається, мабуть, можна двома причинами: по-перше, пануванням у певні часи принципу витратної економіки, за якої імітаційні моделі були не потрібні; по-друге, необхідністю перебудови стереотипу мислення у процесі розробки імітаційних моделей, який суттєво відрізняється від процесу проектування традиційних програмних засобів для автоматизації систем управління. У зв'язку з розвитком ринкової економіки та переходом до ринкових моделей ситуація почала змінюватись. Це підтверджує і поява в мережі Інтернет за останні два роки портала www.simulation.org.ua в Україні, www.gpss.ru – в Росії та сайта www.gpss-forum.narod.ru в Росії. Призначення цієї книги — подати всебічне і сучасне трактування всіх важливих аспектів моделювання, включаючи формальні моделі систем масового обслуговування, системної динаміки та мереж Петрі, технологію і програмне забезпечення моделювання, перевірку достовірності та правильності моделей, методи моделювання випадкових чисел, величин і процесів, планування експериментів й аналіз результатів моделювання з наступним прийняттям рішень. У підручнику узагальнено більш ніж двадцятип'ятирічний досвід роботи автора у галузі імітаційного моделювання та практичного використання систем АЛСИМ, СТАМ-КЛАСС, GPSS, CSS для трьох поколінь комп'ютерів, починаючи з БЕСМ, ЄС ЕОМ та закінчуючи персональними комп'ютерами, а також досвід розробки власних систем моделювання ІСІМ'95, ISS 2000 і викладання дисципліни «Моделювання систем» на кафедрі автоматизованих систем обробки інформації та управління в Національному технічному університеті України «Київський політехнічний інститут». З усіх видів моделювання – а це перш за все математичне і графічне – в підручнику основна увага приділяється імітаційному моделюванню. Огляд науково-дослідницьких робіт показує, що імітаційне моделювання є чи не найпопулярнішим, за використанням на практиці його випереджають лише методи математичного програмування. Головна цінність імітаційного моделювання полягає в тому, що в основу його покладена методологія системного аналізу. Вона дозволяє досліджувати проектовану або аналізовану систему методами операційного аналізу, який включає такі взаємопов'язані етапи: змістовна постановка задачі, розробка концептуальної моделі, розробка та програмна реалізація імітаційної моделі, перевірка адекватності моделі та оцінка точності результатів моделювання, планування і проведення експериментів та прийняття рішень. Завдяки цьому можна застосовувати імітаційне моделювання як універсальний підхід під час прийняття рішень в умовах невизначеності та врахування у моделях тих факторів, які важко формалізувати, а також використовувати основні принципи системного підходу для виконання практичних завдань. Упровадження імітаційних моделей обробки даних висвітлило низку проблем, з якими доводиться мати справу як розробникам моделей, так і користувачам. Іноді навіть кваліфіковані фахівці в галузі традиційного програмування не можуть засвоїти прийоми роботи з системами моделювання через нерозуміння прихованого механізму роботи моделюючої програми. З подібними серйозними труднощами стикаються і студенти на початковому етапі вивчення методів імітаційного моделювання, а потім і під час переходу від розробки програм на традиційних мовах програмування до розробки імітаційних програм. Тому було поставлено за мету, базуючись на системному підході, розкрити суть імітаційного моделювання ззовні (з боку користувача) та зсередини (з боку розробника моделей). У підручнику зроблена спроба відповісти на традиційне, дискусійне питання щодо вибору засобів програмування для реалізації імітаційної моделі. Під час побудови складних імітаційних моделей не може йтися про алгоритмічні процедурні мови як основу моделі, бо в цьому разі доводиться відтворювати весь прихований механізм мов моделювання. Останні служать для навчальних та «іграшкових» моделей, що ілюструють можливості імітаційного моделювання. Для складних моделей використовуються спеціалізовані засоби моделювання, які дозволяють автоматизувати процеси створення моделі. Особлива увага приділяється мові дискретно-подійного імітаційного моделювання GPSS, яку, незважаючи на її солідний вік (понад 40 років), досі застосовують для програмних реалізацій моделей. Ця мова проста й ефективна при розробленні більшості простих моделей, навчитися будувати які можна за дуже короткий час. Розглядаючи принципи побудови алгоритмів для реалізації блоків і керуючої програми моделювання мови GPSS, можна легко зрозуміти, яким чином будуються складні імітаційні системи. Тому в багатьох розділах книги розглядаються приклади, пов'язані з цією мовою. Більш того, аналіз застосування мов моделювання для проведення практичних, лабораторних занять і курсового проектування у вищих навчальних закладах України і країн СНД (www.gpss.ru) підтверджує популярність мови GPSS. Враховуючи те, що моделювання систем — прикладна наука, поданий у книжці матеріал має практичну спрямованість, і наведені математичні формулювання і докази не завжди є строгими. Особливо це стосується теорії масового обслуговування, яка викладається з позицій операційного аналізу. Імітаційне моделювання неперервних систем і пов'язаних з ними комбінованих систем моделювання у книжці не висвітлене в повній мірі. Це пояснюється тим, що в галузі інформатики, економіки, обробки інформації та автоматизованих систем управління неперервні системи використовуються тільки на рівні управління потоками (матеріальними, фінансовими та ін.). В останніх розділах посібника описується технологія автоматизації проектування імітаційних моделей та проведення експериментів, а також прискорення процесу моделювання, наведені приклади побудови складних імітаційних проектів. У книжці розглянуто сучасний стан засобів моделювання та тенденції їх розвитку; серед них на особливу увагу заслуговують засоби автоматизації створення моделей, а саме візуальне середовище моделювання, яке дозволяє будувати імітаційні моделі за принципом «що бачу, те і відображаю у моделі». Для успішного засвоєння матеріалу книги необхідно мати базові знання з теорії ймовірностей та математичної статистики, основ дискретної математики, лінійної алгебри або теорії матриць і програмування. Книга призначена для студентів, які навчаються за програмою бакалаврів з напряму «Комп'ютерні науки», магістрам, що навчаються за спеціальностями «Інформаційні управляючі системи та технології», «Прикладна математика», «Інформаційні системи у менеджменті», крім того, вона буде корисною аспірантам і усім, хто цікавиться проблемами імітаційного і комп'ютерного моделювання та його застосуванням на практиці. Від видавництва Ваші зауваження, пропозиції та запитання надсилайте за адресою електронної пошти pg@bhv.kiev.ua та за адресою http://www.osvita.info. На цьому ж сайті ви познайомитеся з детальною інформацією про інші видання серії «Інформатика». Інформацію про книжки Видавничої групи BHV ви можете знайти на сайті http ://www. bhv. kiev.ua.
Лекція 1. ПОНЯТТЯ Системи
План 1. Термін система. 2. Структура системи. Середовище. 3. Відкриті та закриті системи. 4. Рівні опису системи. 5. Теоретико-множинне визначення системи. 6. Об’єкти, атрибути та відношення системи. 7. Топологічні абстрактні ситеми. 8. Динамічні системи. 9. Основна задача теорії систем.
Основними поняттями в теорії і практиці моделювання об’єктів, процесів і явищ є «система» та «модель». У перекладі з грецької «systema» – ціле, яке складається із частин; об’єднання. Термін «система» існує вже більш ніж два тисячоліття, проте різні дослідники визначають його по-різному. На сьогодні існує понад 500 визначень терміну «система». Однак, використовуючи будь-яке з них, у першу чергу потрібно мати на увазі ті завдання, які ставить перед собою дослідник. Системою може бути і один комп’ютер, і автоматизована лінія або технологічний процес, в яких комп’ютер є лише одним із компонентів, і все підприємство або кілька різних підприємств, які функціонують як єдина система в одній галузі промисловості. Те, що один дослідник визначає як систему, для іншого може бути лише компонентом більш складної системи. Для всіх визначень системи загальним є те, що система – це цілісний комплекс взаємопов’язаних елементів, який має певну структуру і взаємодіє із зовнішнім середовищем. Структура системи – це організована сукупність зв’язків між її елементами. Під таким зв’язком розуміють можливість впливу одного елемента системи на інший. Середовище – це сукупність елементів зовнішнього світу, які не входять до складу системи, але впливають на її поведінку або властивості. Система є відкритою, якщо існує зовнішнє середовище, яке впливає на систему, і закритою, якщо воно відсутнє або з огляду на мету досліджень не враховується. Одне з перших визначень системи (1950 рік) належить американському біологу Л. фон Берталанфі, згідно з яким система складається з деякої кількості взаємопов’язаних елементів. Оскільки між елементами системи існують певні взаємозв'язки, то мають бути структурні відношення. Таким чином, система – це щось більше, ніж сукупність елементів. Аналізуючи систему, потрібно враховувати оцінку системного (синергетичного) ефекту. Властивості системи відмінні від властивостей її елементів, і залежно від властивостей, якими цікавляться дослідники, та ж сама сукупність елементів може бути системою або ні. Багато дослідників визначають систему як цілеспрямовану множину взаємопов’язаних елементів будь-якої природи. Згідно з цим визначенням система функціонує для досягнення деякої мети. Це визначення є правильним для соціологічних і технічних систем, але не підходить для систем навколишньої природи (наприклад, біологічних), мета функціонування яких не завжди відома. Одне з важливих визначень системи пов’язане з абстрактною теорією систем, у рамках якої, на відміну від інших рівнів опису систем, використовуються такі рівні абстрактного опису:
Найвищий рівень абстрактного опису систем – лінгвістичний; ґрунтуючись на ньому, можна одержати всі інші рівні. На цьому рівні вводиться поняття предметної області, для опису якої застосовуються алгебричні моделі, з якими пов’язана деяка мова. Для опису предметної області цією мовою використовуються два рівні формальних мов, за допомогою яких будують логіко-алгебричну модель предметної області. На цій моделі підтверджуються методи дослідження за допомогою формального апарату, яким можуть бути теорії, побудовані у вигляді істинних висловлювань з усієї множини висловлювань. Таким чином, система – це окремий випадок теорії, описаний формальною мовою, яка уточнюється до мови об’єктів. Для визначення деякого поняття використовують певні символи (алфавіт) і встановлюють правила оперування ними. Сукупність символів і правил користування ними утворює абстрактну мову. Поняття, висловлене абстрактною мовою, означає будь-яке речення (формулу), побудоване за граматичними правилами цієї мови. Припускають, що таке речення містить варійовані змінні, так звані конституенти, які, маючи тільки певні значення, роблять дане висловлювання істинним. Якщо існує множина висловлювань G, але лише V із них істинні, то вважають, що має місце теорія L відносно множин G. Якщо припустити, що конституенти в цих висловлюваннях є формально визначеними величинами, то такі висловлювання називаються правильними. Тоді, за визначенням М.Месаровича, система – це множина правильних висловлювань. Всі висловлювання поділяються на два типи: терми, які вказують на предмети (об’єкти), і функтори, які визначають відношення між термами (об’єктами). Використання термів і функторів дає змогу показати, як, базуючись на лінгвістичному рівні, можна утворити інші рівні абстрактного опису системи. Наприклад, за допомогою термів і функторів можна показати, як із лінгвістичного рівня абстрактного опису системи виникає теоретико-множинний, якщо вважати, що терми – це множини Хs, за допомогою яких перелічують елементи або, інакше, підсистеми досліджуваних систем, а функтори встановлюють характер відношень між задіяними в описі множинами. Під час подальшого викладення змісту цієї книги будемо користуватись теоретика-множинним визначенням системи (А.Холл і Р.Фейджін та Ф.Фейджін), згідно з яким система – це множина об’єктів, між якими існують певні відношення, та їх атрибути. Під об’єктами розуміють компоненти системи. Це, наприклад, підсистеми (тобто може існувати ієрархія підсистем) або окремі об’єкти системи. Атрибути – це властивості об’єктів. Відношення задають певний закон, за яким визначається деяке відображення в одній і тій самій множині об’єктів. За цим визначенням поняття множина та елемент є аксіоматичними. Таким чином, система S задається парою елементів: S = (Xs, Rs), де Xs, Rs – множини відповідно елементів і відношень між ними. Відношення визначають взаємодію між об’єктами. У загальному випадку n – відношення Rn у множинах Х1, Х2,..., Хn є деякою підмножиною декартового добутку Х1´Х2´...´Хn, який зіставлено з n-вимірних наборів (кортежів) виду (x1, х2,..., хn), де хiÎXi, і = 1, 2, ..., n. Декартовим добутком множин А´В називається сукупність будь-яких пар виду (а, b), така що А´В = {(а, b) | аÎA, bÎВ}. Якщо відношення Rn в окремому випадку задається, наприклад, деякою функцією, що визначає зв'язок між певним елементом хÎX і певною підмножиною Y, то f: X®Y, тобто вважаємо, що функція f перетворює значення із множини X у значення підмножини Y. Для функції f множина X – це область визначення, а підмножина Y – область значень функції. Функцію f можна подати як множину впорядкованих пар елементів (х, у). Що стосується атрибутів системи, то вони подібні до функцій, визначених у підмножині об’єктів. Відмінність атрибутів від функцій полягає в тому, що два різних атрибути з погляду на поняття функції можуть бути однаковими. Атрибут А задається парою елементів – (і, f), де і – ім’я атрибута, а f – функція, визначена на підмножині об’єктів. У динамічних об'єктів атрибут також може бути функцією від часу t. Наприклад, у разі дослідження пропускної здатності ділянок доріг об'єктами системи можуть бути перехрестя, розв’язки, поворот і прямолінійні ділянки доріг (статичні об’єкти) та автомобілі (динамічні об’єкти). Властивості (атрибути) динамічних об’єктів, на відміну від властивостей статичних, змінюються в часі. Наприклад, гальмовий шлях автомобіля змінюється залежно від швидкості руху та погодних умов, а прискорення може бути додатним (під час розгону) або від’ємним (під час гальмування). Відношення в цій системі задаються згідно з правилами дорожнього руху. Вивчаючи систему більш глибоко, усвідомлюємо, що вона може складатися з підсистем або бути однією з елементів більшої системи, тобто може існувати ієрархія систем. Наприклад, двигун є підсистемою автомобіля, який у свою чергу є підсистемою транспортного потоку магістралі. На теоретико-множинному рівні абстрактного опису системи можна отримувати досить загальні відомості про реальні системи, а для конкретніших цілей потрібні інші моделі, які давали б змогу більш детально аналізувати різні властивості реальних систем. Для цього потрібні нижчі рівні абстрактного опису систем, які є окремими випадками опису теоретико-множинного рівня. Так, якщо зв’язки між елементами розглядуваних множин установлюються за допомогою деяких однозначних функцій, що відображають елементи множини в саму відправну множину, то має місце абстрактно-алгебричний рівень опису систем. У таких випадках вважають, що між елементами множин встановлено нульарні, унарні, бінарні, тернарні та інші відношення. Якщо ж на множинах, які розглядаються, визначено деякі багатозначні функції, то мають місце топологічні абстрактні моделі, записані мовою загальної топології або її гілок, які називаються гомологічною топологією, алгебричною топологією тощо. Вибір потрібного рівня абстрактного опису під час вивчення тієї або іншої реальної системи є завжди найвідповідальнішим і найважчим кроком у теоретико-системних побудовах. Цей процес майже не піддається формалізації і багато в чому залежить від досвіду та знань дослідника, його фахової належності, цілей дослідження тощо. Можна показати, як від систем із топологічним рівнем опису перейти до узагальнених динамічних. Щоб дати строге математичне визначення поняттю динамічна система, її наділяють властивістю мати «входи» й «виходи», тобто визначають як структурований об’єкт, куди в певні моменти часу можна вводити речовину, енергію та інформацію, а в інші моменти – виводити їх. Динамічні системи можна зобразити і як системи, де процеси відбуваються неперервно, і як системи, в яких усі процеси протікають лише в дискретні моменти часу. Інші абстрактні рівні опису систем пов’язані з розвитком інформаційних і програмних систем, а також систем штучного інтелекту. Елементи системи і зв'язки між ними в різних випадках можуть мати різну природу (фізичну, інформаційну, технологічну, біологічну, соціальну), тому аналізом систем займаються представники різних галузей науки і техніки. Науковий напрям під назвою загальна теорія систем, який з’явився наприкінці 50-х – на початку 60-х років XX сторіччя, пов’язаний із розробленням сукупності філософських, методологічних, наукових і прикладних методів аналізу та синтезу систем довільної природи. Ця теорія є загальною, оскільки має дедуктивний характер, об’єднує інші теорії, а саме: теорії керування, самоорганізації, навчання тощо, і розроблена для вивчення поведінки абстрактних систем. Основне її призначення – пояснити, яким чином з окремих елементів утворюється складна єдність цілого, нова сутність. Загальна теорія систем тісно пов’язана з формальною і є певною мірою математичною. Основна процедура теорії систем і системного аналізу – побудова моделі системи, яка відображала б усі фактори, взаємозв’язки і реальні ситуації. Займаються цим спеціалісти із системного аналізу – системотехніки або системні аналітики.
Контрольні запитання 1. Що таке система? Як впливає на систему зовнішнє середовище? Чому існує багато визначень системи? 2. Назвіть кілька статичних і динамічних об’єктів, дій, процесів, атрибутів, подій та змінних станів для таких систем: а) станція технічного обслуговування автомобілів; б) магазин самообслуговування; в) станція швидкої допомоги; г) кафе; д) таксомоторний парк. 3. Яким чином динамічна поведінка системи пов’язана з поняттям стану системи? 4. Що розуміють під абстрактною системою? 5. Що розуміють під моделлю? У яких відношеннях перебувають об’єкт моделювання та модель? Чи може система бути моделлю? 6. Яку роль відіграють поняття стану та процесу в моделюванні? Опишіть роботу банку з двома касирами, до яких стоїть одна черга. Виділіть основні стани цієї системи. 7. Наведіть приклади задач, які можна розв’язати за допомогою моделювання. В яких випадках задачі можна розв’язати лише у такий спосіб? 8. Виконайте критичний аналіз різних видів класифікацій моделей та видів моделювання. Чому неможлива єдина класифікація? Запропонуйте іншу класифікацію моделей. 9. Порівняйте числовий метод розв’язання задачі про водопостачання з методом імітаційного моделювання. Що є між ними спільного? 10. Сформулюйте завдання ідентифікації в широкому та вузькому розумінні для задачі про водопостачання. 11. Яким чином задається час моделювання в задачах про водопостачання? Чи можливо так задати час моделювання для цієї задачі, щоб він залежав від деяких подій? Наведіть приклади моделювання таких подій. 12. Дайте ситуаційний опис переходу пішоходом дороги. Розгляньте всі можливі ситуації.
Лекція 2. ПОНЯТТЯ МОДЕЛІ
План 1. Теорія подібності. 2. Термін модель. 3. Два основних типи моделей. 4. Співвідношення між моделлю та системою. 5. Класифікація моделей. 6. Вимоги до моделей. 7. Основні види моделювання.
Науковою основою моделювання як методу пізнання і дослідження різних об’єктів і процесів є теорія подібності, в якій головним є поняття аналогії, тобто схожості об’єктів за деякими ознаками. Подібні об’єкти називаються аналогами. Аналогія між об’єктами може встановлюватись за якісними і (або) кількісними ознаками. Основним видом кількісної аналогії є математична подібність, коли об'єкти описуються за допомогою рівнянь і функцій. Функції та незалежні змінні називаються схожими, якщо вони співпадають з точністю до деякої константи. Окремими видами математичної подібності є геометрична подібність, яка встановлює подібність геометричних образів, і часова, що визначає подібність функції часу, для якої константа часу (масштаб) показує, в яких відношеннях знаходяться параметри функцій, такі як період, часова затримка тощо. Іншим видом кількісної аналогії, який слід відзначити, є фізична подібність. Критерії фізичної подібності можна отримати, не маючи математичного опису об’єктів, наприклад на основі значень фізичних параметрів, які характеризують досліджуваний процес у натурі й на моделі. За типом процесу розрізняють види подібності, для яких розроблено відповідні критерії – гідравлічні, електричні, аеродинамічні та ін. Вивчення переходу від властивостей реальних об’єктів до властивостей системи є найважливішим завданням теорії систем. У загальній теорії систем визнається об’єктивність їх існування. Згідно з цією теорією, якщо реально існують взаємозв’язки між об’єктами, то існують і системи, які їм відповідають. Ця теорія ґрунтується на постулаті функціонально-структурного ізоморфізму об’єктів і явищ природи. Якщо структура однієї системи і зовнішні функції її елементів ізоморфні структурі іншої системи і зовнішнім функціям її елементів, то зовнішні властивості цих систем не розрізняються в області їх ізоморфізму. У теорії систем цей постулат має не менше значення, ніж закони збереження матерії у фізиці або аксіоми в математиці. Разом з іншими постулатами він є підґрунтям для логічного, доказового розгортання теорії і дає можливість пояснити єдність закономірностей природи для об’єктів, які здаються несхожими і незалежними один від одного. Ізоморфізм реальних систем є основою і логічним наслідком вищезазначеного постулату. У теорії систем існує ще один важливий для моделювання постулат, який визначає, що описом структури і функцій деякої системи може бути інша ізоморфна стосовно неї система. Ця ізоморфність (подібність) двох систем стосується структур систем і функцій їх елементів. Одна з таких систем є моделлю іншої (оригіналу) і навпаки. Таких ізоморфних систем може бути безліч. Виникає проблема вибору або побудови системи, яка може бути моделлю досліджуваної системи. Теорія подібності дає змогу встановити відношення еквівалентності (відповідності, схожості) між двома розглядуваними системами за деякими ознаками. Будь-яка з цих систем може існувати реально або бути абстрактною. Якщо система існує реально, то її можна вивчати, досліджуючи, яким чином пов'язані вхідні впливи з виходами системи. На основі результатів досліджень будується деяка абстрактна система, де відношення еквівалентності визначають тільки ті істотні властивості та аспекти поведінки, які у вихідній та абстрактній системах мають бути однаковими. М.Месарович відзначає, що, базуючись на спостереженнях і дослідженнях однієї системи, можна робити висновки про властивості та поведінку іншої. Здебільшого на практиці абстрактна система простіша за вихідну, якщо не враховувати тих аспектів, що визначають відношення еквівалентності. Таким чином, можна перейти до визначення терміна «модель». У філософській літературі терміном «модель» позначають «деяку реально існуючу систему або ту, що представляється в думках, яка, заміщаючи і відображаючи в пізнавальних процесах іншу систему-оригінал, знаходиться з нею у відношенні схожості (подібності), завдяки чому вивчення моделі дає змогу отримати нову інформацію про оригінал». У цьому визначенні закладено генетичний зв’язок моделювання з теорією подібності, принципом аналогії. Таким чином, моделлю можна називати систему, яку використовують для дослідження. Термін «модель» походить від латинського слова «modulus», тобто зразок, пристрій, еталон. У широкому значенні – це будь-який аналог (уявний, умовний: зображення, опис, схема, креслення тощо) певного об'єкта, процесу, явища («оригіналу» даної моделі), що використовується як його «замінник». Цей термін можна застосовувати також для позначення системи постулатів, даних і доведень, формального опису деякого явища або стану речей. Словник Вебстера визначає модель як «спрощений опис складного явища або процесу». У сучасній теорії керування використовуються моделі двох основних типів. Для технологічних об’єктів цей поділ відповідає «феноменологічним» і «дедуктивним» моделям. Під феноменологічними моделями розуміють переважно емпірично поновлені залежності вихідних даних від вхідних, як правило, з невеликою кількістю входів і виходів. Дедуктивне моделювання передбачає з’ясування та опис основних фізичних закономірностей функціонування всіх компонентів досліджуваного процесу і механізмів їх взаємодії. За допомогою дедуктивних моделей описується процес у цілому, а не окремі його режими. Перший тип моделей – моделі даних, які не потребують, не використовують і не відображають будь-яких гіпотез про фізичні процеси або системи, з яких ці дані отримано. До моделей даних належать усі моделі математичної статистики. Останнім часом ця сфера моделювання пов’язується з експерементально-статистичними методами і системами, що істотно розширює методологічну базу для прийняття рішень під час розв'язання завдань аналізу даних і керування. Другий тип моделей – системні моделі, які будуються в основному на базі фізичних законів і гіпотез про те, як система структурована і, можливо, як вона функціонує. Використання системних моделей передбачає можливість працювати в технологіях віртуального моделювання – на різноманітних тренажерах і в системах реального часу (операторські, інженерні, біомедичні інтерфейси, різноманітні системи діагностики і тестування тощо). Саме системні моделі будуть ядром моделювання на сучасному етапі. Таким чином, модель є абстракцією системи і відображає деякі її властивості. Цілі моделювання формулює дослідник. Значення цілей моделювання неможливо переоцінити. Тільки завдяки їм можна визначити сукупність властивостей модельованої системи, які повинна мати модель, тобто від мети моделювання залежить потрібний ступінь деталізації моделі. З огляду на вищеописане модель – це абстракція; вона відображає лише частину властивостей системи, і мета моделювання – визначення рівня абстрактного опису системи, тобто рівня детальності її подання. Модель і система знаходяться в деяких відношеннях, від яких залежить ступінь відповідності між ними. На міру відповідності між системою та моделлю вказують поняття ізоморфізму та гомоморфізму. Система та модель є ізоморфними, якщо існує взаємооднозначна відповідність між ними, завдяки якій можна перетворити одне подання на інше. Строго доведений ізоморфізм для систем різної природи дає можливість переносити знання з однієї галузі в іншу. За допомогою теорії ізоморфізму можна не тільки створювати моделі систем і процесів, але й організовувати процес моделювання. Однак існують і менш тісні зв’язки між системою та моделлю. Це так звані гомоморфні зв’язки, які визначають однозначну відповідність лише в один бік – від моделі до системи. Система та модель є ізоморфними тільки в разі спрощення системи, тобто скорочення множини її властивостей (атрибутів) і характеристик поведінки, які впливають на простір станів системи. Зазвичай модель простіша за систему. На рис. 1.1 схематично зображено різницю ізоморфної та гомоморфної залежностей між системою та моделлю для простору станів системи Zs і моделі Zm. Множину станів моделі Zm визначають з огляду на мету моделювання та обраний рівень абстрактного опису. Отже, аналогія, абстракція та спрощення – це основні поняття, які використовуються під час моделювання систем. Розглянемо відношення між системою та моделлю, враховуючи, що ці відношення відповідають цілям моделювання та обмеженням досліджуваної системи. Під час використання поняття множини можливих станів системи Zs і моделі Zm розрізняють такі типи відношень. 1. Детерміновані відношення, коли стан системи однозначно визначає стан моделі: P[Zs = Zsi,| Zm = Zmj] = P[Zm = Zmj| Zs = Zsi] = 0˅1, де Р – ймовірність; Zsi, Zmj — конкретні стани відповідно системи та моделі для скінченної множини значень і, j. У цьому разі розглядається детермінована дискретна модель зі скінченною множиною можливих станів. Прикладом реалізації такої моделі може бути скінченний автомат або мережа Петрі. 2. Імовірнісні відношення зі скінченною множиною станів. У цьому випадку стан системи однозначно визначає стан моделі, але стан моделі визначає стан системи лише з деякою ймовірністю. Зазначені відношення для конкретних станів Zsi, Zmj можна подати в такому вигляді: P[Zs = Zsi,| Zm = Zmj] = 0˅1, P[Zm = Zmj| Zs = Zsi] ≤ 1, тобто розглядається дискретна стохастична модель зі скінченною множиною можливих станів. Прикладом реалізації подібної моделі може бути ймовірнісний автомат. 3. Імовірнісні відношення з нескінченною множиною станів, коли стани системи та моделі визначають стани одне одного лише з деякою ймовірністю: P[Zs = Zsi,| Zm = Zmj] ≤ 1, P[Zm = Zmj| Zs = Zsi] ≤ 1. Це так звані стохастичні моделі, до яких, наприклад, належать марківські моделі та моделі систем масового обслуговування. Розглянемо питання класифікації моделей. Для того щоб визначити види моделей, перш за все потрібно окреслити ознаки класифікації. У сучасній літературі описано сотні визначень поняття «модель» та їх класифікацій. Одну з перших, досить повних, класифікацій моделей було запропоновано Дж. Форрестером у 1961 році. Відомі інші класифікації, але в жодній з них немає відомостей про ознаки, за якими їх складено. Якщо враховувати, що моделювання – це метод пізнання дійсності, то основною ознакою класифікації можна назвати спосіб подання моделі. За цією ознакою розрізняють абстрактні та реальні моделі (рис. 1.2). Під час моделювання можливі різні абстрактні конструкції, проте основною є віртуальна (уявна) модель, яка відображає ідеальне уявлення людини про навколишній світ, що фіксується в свідомості через думки та образи. Вона може подаватись у вигляді наочної моделі за допомогою графічних образів і зображень. Наочні моделі залежно від способу реалізації можна поділити на дво- або тримірні графічні, анімаційні та просторові. Графічні та анімаційні моделі широко використовуються для відображення процесів, які відбуваються в модельованій системі. Графічні моделі застосовуються в системах автоматизованого проектування (computer-aided design, CAD). Для відтворення тримірних моделей за допомогою комп'ютера існує багато графічних пакетів, найбільш поширені з яких Corel DRAW, 3D Studio Max i Maya. Графічні моделі є базою всіх комп’ютерних ігор, а також застосовуються під час імітаційного моделювання для анімації. Щоб побудувати модель у формальному вигляді, створюють символічну, або лінгвістичну, модель, яка відповідала б найвищому рівню абстрактного опису, як це було зазначено вище. На базі неї отримують інші рівні опису. Основним видом абстрактної моделі є математична модель. Математичною називається абстрактна модель, яка відображає систему у вигляді математичних відношень. Як правило, йдеться про систему математичних співвідношень, що описують процес або явище, яке вивчається; у загальному розумінні така модель є множиною символічних об’єктів і відношень між ними. Оскільки, зазвичай, йдеться про аналіз величин і зв’язків між ними, які описуються за допомогою рівнянь та систем рівнянь, то і математична модель звичайно розглядається як система рівнянь, в якій конкретні величини замінюються математичними поняттями, постійними і змінними величинами, функціями. Як правило, для цього застосовуються диференціальні, інтегральні та алгебричні рівняння. Розвиток нових розділів математики, пов’язаних з аналізом нечислових структур, досвід їх використання під час проведення досліджень свідчать, що потрібно розширювати уявлення про мову математичних моделей. Тоді математична модель визначатиметься як будь-яка математична структура, де об’єкти, а також відношення між ними можна буде інтерпретувати по-різному, наприклад як функції або функціонали. На відміну від абстрактних, реальні моделі існують у природі, й з ними можна експериментувати. Реальні моделі – це такі, в яких хоча б один компонент є фізичною копією реального об’єкта. Залежно від того, в якому співвідношенні знаходяться властивості системи та моделі, реальні моделі можна поділити на натурні та макетні. Натурні (фізичні) моделі – це існуючі системи або їх частини, на яких провадяться дослідження. Натурні моделі повністю адекватні реальній системі, що дає змогу отримувати високу точність і достовірність результатів моделювання. Суттєві недоліки натурних моделей – це неможливість моделювання критичних і аварійних режимів їх роботи та висока вартість. Макетні моделі – це реально існуючі моделі, які відтворюють модельовану систему в певному масштабі. Іноді такі моделі називаються масштабними. Параметри моделі та системи відрізняються між собою. Числове значення цієї різниці називається масштабом моделювання, або коефіцієнтом подібності. Ці моделі розглядаються в рамках теорії подібності, яка в окремих випадках передбачає геометричну подібність оригіналу й моделі для відповідних масштабів параметрів. Найпростіші макетні моделі – це пропорційно зменшені копії існуючих систем,, які відтворюють основні властивості системи або об’єкта залежно від мети моделювання. Макетні моделі широко використовуються під час вивчення фізичних та аеродинамічних процесів, гідротехнічних споруд і багатьох інших технічних систем. За можливістю змінювати в часі свої властивості моделі поділяються на статичні та динамічні. Статичні моделі, на відміну від динамічних, не змінюють своїх властивостей у часі. Динамічні моделі також називаються імітаційними. Залежно від того, яким чином відтворюються в часі стани моделі, розрізняють дискретні, неперервні й дискретно-неперервні (комбіновані) моделі. За відношеннями між станами системи й моделі розрізняють детерміновані й стохастичні моделі. Останні, на відміну від детермінованих моделей, враховують імовірнісні явища й процеси. Які вимоги слід ураховувати під час побудови моделей? У загальному випадку під час побудови моделі потрібно враховувати такі вимоги:
Оскільки модель створюється для вирішення конкретних завдань, розробник моделі має бути впевненим, що не отримає абсурдних результатів, а всі одержані результати відображатимуть необхідні для дослідника характеристики та властивості модельованої системи. Модель повинна дати можливість знайти відповіді на певні запитання, наприклад: «що буде, якщо ...», оскільки вони є найбільш доцільними під час глибокого вивчення проблеми. Не варто забувати, що системні аналітики використовують модель для прийняття рішень і пошуку найкращих способів створення модельованої системи або її модернізації. Завжди потрібно пам’ятати, що користувачем інформації, отриманої за допомогою моделі, є замовник. Недоцільно розробляти модель, якщо її не можна буде використовувати. Більш того, робота з моделлю має бути автоматизованою для замовника до такого ступеня, щоб він міг працювати з нею в межах своєї предметної області. Таким чином, між моделлю і користувачем повинен бути розвинутий інтерфейс, який звичайно створюється за допомогою системи меню, налагодженої на застосування моделі в певній галузі. Ступінь деталізації моделі потрібно вибирати з огляду на цілі моделювання, можливості отримання необхідних вхідних даних для моделі та з урахуванням наявних ресурсів для її створення. Відсутність кваліфікованих фахівців може звести роботи зі створення моделі нанівець. З іншого боку, чим детальніше розроблено модель, тим вона стійкіша до вхідних впливів, які не були передбачені під час проектування, і на більшу кількість запитань може дати правильні відповіді. Єдина класифікація видів моделювання неможлива через багатозначність поняття моделі в науці, техніці, суспільстві. Широко відомими видами моделювання є комп’ютерне, математичне, імітаційне та статистичне. На жаль, різні джерела по-різному трактують ці поняття. Комп’ютерне моделювання визначимо як реалізацію моделі за допомогою комп’ютера. Особливістю комп’ютерного моделювання є його інтерактивність, що дає змогу користувачу втручатися в процес моделювання та впливати на результати завдяки узгодженості дій користувача і моделі, яка відтворює об’єкти реального середовища або гіпотетичні події та процеси. Під час комп’ютерного моделювання може бути задіяно реальні об’єкти (наприклад, кабіна пілота), віртуальні об’єкти, згенеровані комп’ютером, які відтворюють реальні об’єкти (наприклад, потоково-конвеєрна лінія для збирання автомобілів). Інтерактивне комп’ютерне моделювання широко застосовується в навчальних системах, наприклад для побудови тренажерів і в ситуаційних іграх. Що стосується математичних моделей, або математичного моделювання, то слід відзначити, що під час їх використання багато чого залежить від способу подання як моделі, так і результатів моделювання. Розглянемо простий приклад. Нехай на деякому підприємстві для водопостачання використовується резервуар, об’єм якого становить W тисяч літрів. Рівень споживання – Vп a тисяч літрів, а швидкість наповнення резервуара – Vз тисяч літрів за добу. Необхідно знайти час Т, за який буде заповнено резервуар. Схему цієї системи зображено на рис. 1.3, де резервуар позначено прямокутником, а вхідний і вихідний потоки – стрілками з «вентилями», які регулюють ці потоки. Хмарки позначають необмежені потоки. Такі ідеограми широко використовуються під час побудови моделей неперервних процесів. Знайдемо час заповнення резервуара: Ця математична модель процесу наповнення резервуара є надто ідеалізованою, тому що всі її параметри вважаються незмінними в часі, зовнішні впливи на систему не враховуються. Завдяки такій ідеалізації маємо дуже просту модель, яка дає змогу розв’язати задачу аналітично. Однак за допомогою такої моделі можна отримати відповідь тільки на одне конкретне запитання – за який час буде заповнено резервуар. Якщо задачу наблизити до практики, то, будуючи модель, необхідно враховувати, що потреби підприємства у водопостачанні постійно змінюються, більш того, можливі перебої в роботі насосів під час подавання води. Розв’язок задачі в частково замкнутому вигляді можна записати як W = (Vз – Vп)T. За рахунок неявного запису отримано більш придатну для дослідження та аналізу реальних процесів математичну модель. Час заповнення резервуара об'ємом W залежить від параметрів моделі Vз, Vп. Використання цієї моделі дає можливість вивчити відношення між величинами Vп і Vз, якщо задавати різні початкові значення для них, і побудувати графік наповнення резервуара (рис. 1.4). Реалізувати цю модель можна за допомогою і чисельних методів. Змінюючи у останній формулі значення t від 0 з деяким кроком Dt до такого, що буде виконуватись рівність, отримаємо динамічну характеристику заповнення резервуара. Чим менший крок Dt, тим точніший отримаємо результат, але тим довше буде вирішуватись задача моделювання. Термін «моделювання» відповідає англійському слову «modeling», тобто побудові моделі та її аналізу. Англійський термін «simulation» відповідає прийнятому терміну «імітаційне моделювання», але часто вони використовуються разом, коли йдеться про технологічні або системні етапи моделювання, пов’язані з прийняттям рішень за допомогою моделей. Імітаційне моделювання – це метод конструювання моделі системи та проведення експериментів. Однак під таке визначення підпадають майже всі види моделювання. Тому потрібно виділити суттєві особливості імітаційного моделювання. Перш за все слід подати в моделі структуру системи, тобто загальний опис елементів і зв’язків між ними, потім визначити засоби відтворення в моделі поведінки системи. Здебільшого поведінку системи описують за допомогою станів і моментів переходів між ними. Стан системи в момент часу t визначають як безліч значень певних параметрів системи у цей самий момент часу t. Будь-яку зміну цих значень можна розглядати як перехід до іншого стану. І врешті-решт, імітаційна модель має відобразити властивості середовища, в якому функціонує досліджувана система. Зовнішнє середовище задають вхідними впливами на модель. Вся інформація про імітаційну модель загалом має логіко-математичний характер і подається у вигляді сукупності алгоритмів, які описують процес функціонування системи. Отже, здебільшого імітаційною моделлю є її програмна реалізація на комп’ютері, а імітаційне моделювання зводиться до проведення експериментів з моделлю шляхом багаторазового прогону програми з деякою множиною даних – середовищем системи. Під час імітаційного моделювання може бути задіяно не тільки програмні засоби, але й технічні засоби, люди та реальні системи. З математичної точки зору імітаційну модель можна розглядати як сукупність рівнянь, які розв’язують з використанням чисельних методів у разі кожної зміни модельного часу. Окремі рівняння можуть бути простими, але їх кількість і частота розв’язання – дуже великими. Розв’язання таких рівнянь під час імітаційного моделювання означає встановлення хронологічної послідовності подій, які виникають у системі і відображають послідовність її станів. Отже, імітаційна модель функціонує так само, як система. Якщо повернутись до процесу наповнення резервуара (рис. 1.5), то за допомогою імітаційної моделі весь процес можна відтворити з використанням останнього рівняння. Позначимо через Wі поточний стан резервуара, який відтворюється в певні моменти модельного часу, що змінюється з постійним кроком Dt: Wі = (Vз – Vп)tі, де tі = tі-1 + Dt, (і = 1, 2, ...), t0 = 0. Така модель є детермінованою. Процес моделювання закінчується, якщо на деякому кроці виконується умова W ≤ Wі, тобто розв'язок отримуємо за один прогін імітаційної моделі. Точність результату буде залежати від значення Dt. За наявності в моделі випадкових факторів виникає необхідність статистичного оцінювання результатів моделювання, що виконується за допомогою методу статистичного моделювання (методу Монте-Карло). Статистичне моделювання є самостійним видом моделювання, яке включається в імітаційне моделювання тільки за необхідності моделювання ймовірнісних систем і процесів. Побудуємо більш реальну модель системи, яка розглядалась вище. Припустимо, що рівень споживання води на підприємстві має імовірнісний характер і змінюється згідно з рівномірним розподілом імовірності в межах Vп ± DVп. Тоді значення Vп у деякий момент часу tі будемо визначати як 2DVпrі + Vп – DVп де rі – випадкове число, рівномірно розподілене в інтервалі [0,1]. Результати роботи імітаційної моделі наведено на рис. 1.6. У цьому випадку після кожного прогону моделі отримаємо випадкові значення Тj, де j – кількість прогонів, j = 1, 2, 3,… Для кожного прогону потрібно задавати свою послідовність випадкових чисел rі. Як видно на рис. 1.6, отримані значення Тj будуть відрізнятись від середнього значення Т, знайденого за допомогою детермінованої моделі. Таким чином, щоб оцінити час Т наповнення резервуара, потрібно задати точність оцінювання e = DТ і рівень довіри α. Звичайно беруть α = 0,95, тобто є гарантія, що в 95 випадках із 100 середнє значення часу Т буде знаходитись у межах Т ± DТ. Контрольні запитання
Лекція 3. Формальні методи побудови моделей
План 1. Основні цілі застосування моделей. 2. Етапи створення моделі. 3. Кібернетичний підхід створення моделі. 4. Системна динаміка. 5. Теоретико-множинний підхід.
Розглядаючи сфери застосування моделей, можна констатувати, що за допомогою моделі можна досягти двох основних цілей: описової, якщо модель призначена для пояснення і кращого розуміння об’єкта, або приписуючої, коли модель дає змогу передбачити або відтворити характеристики об’єкта або визначити його поведінку. Таким чином, модель є описовою, якщо вона призначена зображувати поведінку (функціонування) або властивості існуючої або типової системи (наприклад, масштабна модель або письмовий опис, що дає змогу знайомити потенційних покупців із фізичними і робочими характеристиками комп’ютера). Протилежність – приписуюча модель, яка відображає необхідну поведінку або властивості запропонованої системи (наприклад, масштабна модель або письмовий опис, представлений постачальнику комп’ютерів, з фізичними і робочими характеристиками потрібного замовнику комп’ютера). Приписуюча модель може бути описовою, але не навпаки. Тому існує різний ступінь корисності моделей, які використовуються в технічних і соціальних науках. Це значною мірою залежить від методів, і засобів, застосовуваних під час побудови моделей, а також від кінцевої мети. У соціальних науках моделі призначено для пояснення існуючих систем, а в техніці вони є допоміжними засобами для створення нових або більш досконалих моделей. Модель, що придатна для досягнення цілей розроблення системи, має також пояснювати її. Під час побудови моделей застосовуються фундаментальні закони природи, варіаційні принципи, аналога, ієрархічні ланцюжки. Процес створення моделі включає такі етапи. 1. Словесно-смисловий опис об’єкта або явища – формулювання описової моделі, призначеної для сприяння кращому розумінню об’єкта моделювання. 2. Числове вираження модельованої реальності для виявлення кількісної міри і границь відповідних якостей; з цією метою провадиться математико-статистична обробка емпіричних даних, пропонується кількісне формулювання якісно встановлених фактів і узагальнень. 3. Перехід до вибору або формулювання моделей явищ і процесів (варіаційного принципу, аналогії тощо) і його запису у формалізованій формі; це рівень структурних теоретичних схем, таких як системи масового обслуговування, мережі Петрі, скінченні або ймовірнісні автомати, діаграми фонд-потік тощо. 4. Завершення формулювання моделі її «оснащенням» – задання початкового стану і параметрів об’єкта. 5. Вивчення моделі за допомогою доступних методів (у тому числі із застосуванням різних підходів і обчислювальних методів). У результаті дослідження моделі досягається поставлена мета. У цьому разі має бути встановлена всіма можливими способами (шляхом порівняння з практикою, порівняння з іншими підходами) її адекватність – відповідність об’єкта сформульованим припущенням. Систему можна вивчати та аналізувати, змінюючи вхідні впливи і спостерігаючи за виходами. Це кібернетичний підхід, згідно з яким система розглядається як «чорну скриньку». Метод «чорної скриньки» широко використовується під час моделювання систем, коли для дослідника важливо отримати інформацію про поведінку системи, а не про її будову. Дослідник не може зробити однозначний висновок про структуру «чорної скриньки», спостерігаючи тільки за його входами та виходами, бо поведінка модельованої системи нічим не відрізняється від поведінки ізоморфних ш систем. Таким чином, вхідні впливи X перетворюються у виходи системи Y за допомогою рівнянь, і саму систему S можна подати у вигляді «чорної скриньки», зображеної на рис. 1.7, де зовнішні відношення пов'язують елементи системи із зовнішнім середовищем за допомогою входів системи. Під час проведення досліджень системи можна впливати на її входи та спостерігати за її виходами. Вхідні змінні, які дослідник може змінювати, проводячи експерименти, називаються змінними, якими керують, а ті, що неможливо змінювати, – змінними, за якими спостерігають. Під час моделювання звичайно можна змінювати всі вхідні змінні. Входи X, якими керують Входи X, за якими спостерігають Для побудови моделі використовуються методи теорії ідентифікації. У загальному випадку завдання ідентифікації формулюється так: на основі результатів спостереження за вхідними та вихідними змінними системи потрібно побудувати оптимальну в деякому розумінні математичну модель. Основними етапами ідентифікації є такі: 1. Вибір класу і структури моделі та мови її опису. 2. Вибір класу і типів вхідних впливів X. 3. Обгрунтування критеріїв подібності системи та моделі. 4. Вибір методу ідентифікації та розроблення відповідних алгоритмів оцінювання параметрів системи. 5. Перевірку адекватності отриманої в результаті ідентифікації моделі. Залежно від обсягу апріорної інформації про клас і структуру системи вирізняють завдання ідентифікації в широкому та вузькому розумінні. Завдання ідентифікації у широкому розумінні виконується в умовах апріорної невизначеності структури моделі системи («чорна скринька»). Клас і структура математичної моделі вибираються на основі результатів теоретичного аналізу з використанням загальних закономірностей процесів, які протікають у системі, або на основі загальної інформації про подібні системи. У цьому випадку для побудови математичної моделі можна використовувати непараметричні методи. їх розроблено для тих ситуацій, які досить часто виникають на практиці, коли дослідник нічого не знає про параметри досліджуваної системи (звідси і назва методів – непараметричні). Завдання ідентифікації у вузькому розумінні полягає в оцінюванні параметрів і станів системи, якщо відома структура моделі («сіра скринька»). Завданням ідентифікації є кількісне оцінювання певних параметрів. Для цього використовується параметрична ідентифікація математичної моделі. Прикладами таких моделей можуть бути диференціальні та різницеві рівняння, моделі типу «вхід-стан-вихід». На рис. 1.9 зображено загальну схему ідентифікації системи. Вхідні впливи X на систему та модель однакові, виходи системи Ys і моделі Ym у загальному випадку відрізняються. Для їх порівняння потрібно сформувати критерій подібності та мінімізувати його, тобто налагодити модель. Входи X '"—!> Система 5 1 --з Модель М і \ Виходи Ys Виходи Y Формування критерію подібності НалагоДЖЄННЯ Мінімізація критерію подібності моделі Прикладами моделей, створених на основі експериментальних даних, можуть бути моделі авторегресії різних порядків, ковзного середнього та моделі типу «вхід-вихід», побудовані за допомогою методу найменших квадратів. Для формального представлення моделей неперервних систем Дж. Форрестер у 1960 році запропонував ще один підхід, названий системною динамікою, який дає змогу будувати моделі динамічних взаємопов'язаних систем за допомогою причинних діаграм циклів і схем виду «фонд-потік». Він же запропонував для числового моделювання таких систем мову Динамо. Модель будується як система диференціально-різницевих рівнянь, а мова Динамо дає можливість автоматизувати процес їх написання. Практично всі сучасні засоби неперервного та неперервно-дискретного моделювання базуються на цій мові для побудови моделей. На відміну від математичного розв'язання системи таких рівнянь у замкненому вигляді використовується числове розв'язання з дискретним кроком часу, що дає змогу моделювати на деякому проміжку часу динамічні зміни фондів, пов'язаних з точкою часу і потоків. Фонди та потоки пов'язані між собою через змінні. Фонд можна трактувати як деяку кількість чого-небудь, що виміряється в певних одиницях (наприклад, фізичних, грошових та ін.). Фонди можуть акумулювати одиниці фонду. Найкраще їх уявляти як резервуари, ресурси або буфери. Фонди поповнюються через вхідні потоки та спорожнюються через вихідні. Як буфер фонд може використовуватись для забезпечення балансування швидкості накопичення та витрачання (наприклад, у задачі про водопостачання, яка розглядалась раніше. Потік – це процес, що протікає неперервно в часі, оцінити який можна в деяких кількісних одиницях за певний проміжок часу. Залежно від характеристики використання потоки поділяються на обмежені та необмежені, одно- та двоспрямовані, конвертовані та неконвертовані. Потік, як правило, обмежується фондом. Потоком можна керувати, тобто збільшувати або зменшувати його інтенсивність за допомогою деяких алгебричних виразів. Існує багато різних способів зв'язувати у динамічних моделях причини та наслідки, не розглядаючи конкретні методи. В їх основі лежить кілька підходів. Перший підхід полягає в тому, що наслідок виникає з причини і взаємозв'язок між різними причинами відсутній. Такий підхід, наприклад, використовують бухгалтери під час розрахунків. Як правило, для цього застосовують статичні та статистичні моделі. Другий підхід передбачає, що між причинами та наслідками існує лінійний зв'язок у вигляді ланцюжка. Такий підхід підтримують інженери та науковці, які вважають, що всі події у всесвіті залежать одна від одної. Маючи достатню кількість інформації, можна побудувати залежності в часі для всіх подій у майбутньому. Системні мислителі, які застосовують цю парадигму, користуються діаграмами впливу та моделями лінійних рівнянь і вважають, що завжди можна логічно прослідкувати, «що є на вході і що буде на виході». Згідно з третім підходом всесвіт розглядається як система зі зворотними зв'язками, тобто ланцюжки причин і наслідків циклічно пов'язані між собою. Таке уявлення підтримують кібернетики, прихильники нелінійної динаміки та хаосу. Вони вважають, що всесвіт значною мірою хаотичний, і передбачити майбутнє з огляду на його минуле неможливо. Ці системні мислителі використовують циклічні причинні моделі, нелінійні рівняння в кінцевих різницях. Часто поведінка таких моделей далека від реальності та інтуїтивного уявлення і може бути дещо несподіваною для дослідника. На рис. 1.11 зображено найпростішу причинну циклічну модель для деякої популяції, яка має два цикли. Лівий цикл, позитивний, свідчить про приріст популяції в разі збільшення народжуваності, що у свою чергу збільшує народжуваність. Правий цикл, негативний, свідчить про зменшення популяції у випадку збільшення смертності, що у свою чергу зменшує смертність. Такі пари причинних циклів можуть використовуватись під час побудови більш складних динамічних моделей. Народжуваність Популяція Смертність Рис. 1.11. Найпростіша причинна модель циклу популяції Побудова складних динамічних моделей з використанням причинних циклів включає такі етапи. 1. Абстрагування від фізичної структури. 2. Концентрація на процесах для визначення траєкторій, за якими система починає та закінчує працювати. 3. Використання простих диференціально-різницевих рівнянь для опису процесів у системі: ♦ dx/dt = kx — показова функція, яка визначає швидкість зміни фонду в часі, де х — фонд (для прикладу з водопостачанням — це швидкість наповнення бака); ♦ dx/dt = ах - Ьхг — сигмаїдальна, або логістична, крива, або 5-крива; або системи рівнянь: ♦ dx/dt = k^x - k2x2 - кзу (наприклад, х — кількість травоїдних тварин); ♦ dx/dt = k^y -kgy2 -k&c (наприклад, у — кількість хижаків). Такі системи рівнянь відомі як рівняння Ланкастера. їх можна використовувати для дослідження складних взаємозв'язків, конкуренції або конфліктів. За допомогою комп'ютерів подібні рівняння можна подати в числовому вигляді. Для цього використовують прості рівняння рекурсії: dx r, ч Tt=Kx)' \х(п + ї)-х(п)] ,, . чч — j(—— = /(*(»»)). х(п + 1) = dtf(x(ri)) + х(гі). Якщо описати дані рівняння словами, то наступний рівень дорівнюватиме попередньому плюс невеличка зміна протягом короткого проміжку часу. Таким способом можна будувати складні динамічні моделі за допомогою створення простих блоків у вигляді відношень і рівнів Причинні діаграми циклів дають змогу провадити якісне моделювання, а діаграми «фонд-потік» – кількісне. Щоб пояснити явище, потрібно знайти «причини» його виникнення. Припустимо, що таку причину визначено і наслідок може спостерігатись кожного разу, коли ця причина присутня. Якщо описують ці концепції системного мислення звичайними словами, то використовують слова або фрази «тому що», «завдяки тому, що», «якщо ..., то» та ін. З погляду математики, якщо розглядають функціональну концепцію з однією незалежною змінною, ця змінна – причина, а залежна змінна – наслідок. У разі кількісного моделювання таких систем модельовані об'єкти – це об'єкти, параметри яких можна виміряти і між якими існують функціональні залежності. Якщо розглядати систему «хижаки-зайці», то в кількісній моделі знищення хижаками деяких зайців — це не знищення тварин, а зменшення їх кількості. Тобто в системі є суттєва різниця між зайцями як тваринами та їх кількістю. Наприклад, вовк може знищити зайців, але кількість вовків не може знищити дещо, а може тільки вплинути на кількість зайців. Вищенаведені моделі динамічних систем широко використовуються для побудови спеціальних засобів моделювання – мов і пакетів неперервного та неперервно-дискретного імітаційного моделювання. Згідно з теоретико-множинним підходом формальна модель динамічної системи має такий вигляд: M=(T,X,Y,Z,z(t),P), A.7) де Т – модельний час; X, Y – множина відповідно вхідних і вихідних змінних; Z — простір станів моделі; z(t) — функція станів, t є Т; Р — множина процесів, яка визначається як множина впорядкованих у часі пар елементів (х, z[x, t)), де t є Т, а т — початковий момент модельного часу для процесу р є Р. Таке визначення задає модель системи у вигляді схеми процесів, у якій множини процесів можуть існувати паралельно в модельному часі Т. Вважається, що деяка подія з множини подій С зумовлює зміну стану системи, якщо починається певний процес р, є Р або закінчується деякий процес pj є Р. У протилежному випадку стан системи не змінюється. Тоді можна задати подійну схему моделі: M=(T,X,Y,Z,z(t),C), A.8) де С — множина подій, що визначається як множина впорядкованих у часі пар елементів (j, d [x, tj]), де с є С, d [т, £■] — функція дії для процесу pj є P;t є Т, а т — початковий момент модельного часу Т. У цій схемі процес моделювання описується як послідовність подій, що відбуваються в моделі. Припустимо, що завдяки виконанню деякої умови и з множини U почне виконуватись певна дія d [т, tj] з множини D для деякого процесу pj є Р. Тоді можна задати модель системи у вигляді схеми дій: M-(T,X,Y,Z,z (t), D >. A.9) У цій схемі процес моделювання описується як перевірка всіх умов у разі кожної зміни модельного часу t є Т, щоб знайти умову, яка почне певну дію з множини D. Зміна часу t може відбуватись з постійним або змінним від події до події кроком. Схеми моделей A.7)—A.9) широко застосовуються під час побудови алгоритмів моделювання і мов дискретного імітаційного моделювання. Якщо припустити, що виконання деякої множини процесів Р може призвести до зміни станів z є Z і виникнення нових процесів, що спричинить появу деякої множини ситуацій L, тобто z(t) : Pz -> L, то отримаємо ситуаційну або причинно-наслідкову схему: M = (T,X,Y,Z,z(t),L), A.10) в якій потрібно описати множину ситуацій та множину правил (алгоритмів), за якими визначають процес, що має виконуватись. Поведінка моделі в таких системах зображується у вигляді ланцюга {ситуація} -> {правило} -> {процес}. Якщо модель здатна конструювати нові правила на основі існуючих, то вона перетворюється на модель зі штучним інтелектом. Під час ситуаційного моделювання, як правило, повний опис усіх можливих ситуацій замінюється деякою множиною узагальнених ситуацій, кожна з яких з певною мірою ймовірності відтворює один із можливих станів системи. Для кожної ситуації існує набір правил дії. Вибір того або іншого правила може здійснюватись за деяким критерієм або за допомогою таблиць прийняття рішень, а в простіших випадках – згідно із заданою ймовірністю. Моделювання виконується шляхом програвання різних ситуацій за певним сценарієм, яким у окремому випадку може бути алгоритм моделювання. Таким чином створюють різні ігри, наприклад ділові, військові, економічні, розважальні. Гра – це спрощене відтворення реального процесу, яке здебільшого використовується для навчання, прийняття рішень, проведення досліджень або розваг. Визначити систему можна не тільки як сукупність елементів, але і як сукупність відношень, спостерігаючи за їх змінами. Перш за все це стосується взаємодії між різними динамічними системами, кожна з яких досить складна. Прикладом можуть бути екологічні та соціальні системи. Під час вивчення таких систем дослідник, базуючись на системному аналізі, вивчає та описує впливи однієї системи на іншу. Контрольні запитання 1. Для яких цілей використовуються моделі? 2. Подайте основні етапи створення моделей. 3. В чому полягає основна ідея кібернетичного підходу? 4. Сформулюйте завдання ідентифікації в широкому та вузькому розумінні для задачі про водопостачання. 5. Суть підходу – системна динаміка. 6. Які підходи використовуються у динамічних моделях для зв’язку причин та наслідків? 7. В чому суть теоретико-множинного підходу?
Лекція 4. Принципи побудови моделей
План 1. Принципи побудови моделей. 2. Технологія моделювання. 3. Верифікація моделі. 4. Валідація моделі.
Розглянемо коротко основні принципи моделювання, які відображають достатньо багатий досвід, накопичений на даний час у галузі розроблення і використання моделей.
Потреба в моделюванні виникає як на етапі проектування систем для оцінювання правильності прийнятих рішень, так і на етапі експлуатації – для оцінювання наслідків внесення змін у системи. У цьому випадку на різних етапах проектування (технічний або робочий проект) з уточненням вихідних даних і виявленням нових суттєвих факторів ступінь деталізації процесу в системі зростає, що має відобразитись у моделі. Отже, у моделі можуть водночас знаходитись блоки з різним ступенем деталізації, які моделюють одні й ті самі компоненти проектованої системи. Іншими словами, під час побудови моделі потрібно застосовувати методологію ітераційного багаторівневого моделювання. Розроблення моделі доцільно починати зі створення простої вихідної моделі, яку в процесі уточнення вхідних даних і характеристик системи ускладнюють і коригують, тобто адаптують до нових умов. Водночас модель має залишатись досить наочною, тобто її структура має відповідати структурі модельованої системи, а рівень деталізації моделі повинен вибиратись з урахуванням мети моделювання, ресурсних обмежень (наприклад, час, кваліфіковані людські ресурси і кошти, виділені на проектування) і можливості отримання вхідних даних. Отже, модель має бути багаторівневою, адаптивною, наочною, цільовою, розвиватись ітераційним способом, ускладнюватись і коригуватись у процесі утворення, що можливо тільки за умови побудови її блоковим (модульним) способом. Програмування та налагодження моделі доцільно провадити поетапно, з наступним збільшенням програмних модулів. Один із способів підвищення ефективності моделювання полягає в тому, щоб не будувати заново модель для кожної нової системи, а вирізняти окремі класи систем і створювати уніфіковані програмні моделі для класів у цілому. Узагальнені програмні моделі дають змогу моделювати будь-яку систему із заданого класу без додаткових витрат на програмування. Така методологія забезпечує єдиний системний підхід до розроблення програмних реалізацій моделей і використовується під час об'єктно-орієнтованого програмування у вигляді бібліотеки класів моделей. Розглянутий підхід можна реалізувати також у вигляді спеціалізованої мови або пакета моделювання, що дає змогу створювати узагальнені моделі шляхом уведення засобів розмноження підмоделей, реорганізації зв'язків між ними та їх параметричного налагодження. Цей спосіб орієнтовано на фахівців, добре обізнаних з мовою моделювання. Інший спосіб реалізації цього підходу полягає в розробленні діалогових інтелектуальних систем моделювання з використанням банку моделей та бази знань, які користувач може налагоджувати на конкретну реалізацію. У цьому разі етап програмування можна повністю виключити під час програмної реалізації імітаційної моделі завдяки використанню ефективних методів взаємодії з базами даних і застосуванню засобів генерації моделей. Основою моделювання є методологія системного аналізу. Це дає змогу досліджувати систему, яка проектується або аналізується, за технологією операційного дослідження, включаючи такі взаємопов'язані етапи: 1. Формулювання проблеми та змістове поставлення задачі. 2. Розроблення концептуальної моделі. 3. Розроблення програмної реалізації моделі (зазвичай застосовується комп'ютерна модель), яка включає: а) вибір засобів програмування, за допомогою яких буде реалізовано модель; б) розроблення структурної схеми моделі та складання опису її функціонування; в) програмна реалізація моделі. 4. Перевірка адекватності моделі. 5. Організація та планування проведення експериментів, яке включає оцінювання точності результатів моделювання. 6. Інтерпретація результатів моделювання та прийняття рішень. 7. Оформлення результатів дослідження. На першому етапі замовник формулює проблему. Організовуються зустрічі керівника проекту із замовником, аналітиками з моделювання та експертами з проблеми, яка вивчається. Визначаються цілі дослідження та спеціальні питання, відповіді на які буде одержано за результатами дослідження; встановлюються критерії оцінювання роботи, які використовуватимуться для вивчення ефективності різних конфігурацій системи; розглядаються такі показники, як масштаб моделі, період дослідження і необхідні ресурси; визначаються конфігурації модельованої системи, а також потрібне програмне забезпечення. На цьому ж етапі провадиться цілеспрямоване дослідження модельованої системи, залучаються експерти з проблеми, що вирішується, які володіють достовірною інформацією. Збирається інформація про конфігурацію системи і способи експлуатації для визначення параметрів моделі і вхідних розподілів імовірностей. На другому етапі розробляється концептуальна модель – абстрактна модель, яка дає змогу виявити причинно-наслідкові зв'язки, властиві досліджуваному об'єкту в межах, визначених цілями дослідження. По суті, це формальний опис об'єкта моделювання, який відображає концепцію (погляд дослідника на проблему). Вона включає в явному вигляді логіку, алгоритми, припущення й обмеження. Згідно з цілями моделювання визначаються вихідні показники, які потрібно збирати під час моделювання, ступінь деталізації, необхідні вхідні дані для моделювання. Рівень деталізації моделі залежить від таких чинників: цілі проекту; критерії оцінювання показників роботи; доступність даних; достовірність результатів; комп'ютерні можливості; думки експертів з проблеми, що вирішується; обмеження, пов'язані з часом і фінансуванням. Провадиться структурний аналіз концептуальної моделі, пропонується опис допущень, які обговорюються із замовником, керівником проекту, аналітиками та експертами з проблеми, яка вирішується. Розробляються моделі вхідних даних, провадиться їх статистичний аналіз, за результатами якого визначають розподіли ймовірностей, регресійні, кореляційні та інші залежності. На цьому етапі для попереднього аналізу даних широко застосовують різні статистичні пакети (наприклад, Statistica). Для динамічних систем провадиться поопераційний аналіз функціонування модельованої системи з детальним описуванням роботи елементів системи. За результатами такого аналізу можна з'ясувати, чи можна вирішити проблему без застосування засобів моделювання. Детально опрацьована концептуальна модель дає змогу замовнику з іншого боку поглянути на роботу системи та, наприклад, визначити вузькі місця системи, які спричиняють зниження її пропускної здатності. Одна з найскладніших проблем, з якою має справу аналітик моделювання, полягає у визначенні, чи адекватна модель системі. Якщо імітаційна модель «адекватна», її можна використовувати для прийняття рішень щодо системи, яку вона представляє, тобто ніби вони приймались на основі результатів проведення експериментів з реальною системою. Модель складної системи може тільки приблизно відповідати оригіналу, незалежно від того, скільки зусиль затрачено на її розроблення, тому що абсолютно адекватних моделей не існує. Оскільки модель завжди має розроблятись для певної множини цілей, то модель, яка є адекватною для однієї мети, може не бути такою для дослідження іншої. Слід відзначити, що адекватна модель не обов'язково є достовірною, і навпаки. Модель може бути достовірною, але, в цьому разі, не використовуватись для прийняття рішень. Наприклад, достовірна модель не може бути адекватною з політичних або економічних причин. Під час розроблення програмної реалізації моделі визначаються засоби для програмування, тобто мови програмування або пакети. Наприклад, можуть використовуватись мови програмування загального призначення, такі як С чи PASCAL, або спеціалізовані засоби для моделювання (наприклад, Arena, AutoMod, Extend, GPSS, iThink). Перевага використання мов програмування полягає в тому, що, як відомо, вони мають невисоку закупівельну вартість, і на виконання моделі з їх допомогою затрачається менше часу. Натомість використання програмного забезпечення моделювання сприяє зменшенню тривалості програмування і вартості всього проекту. Серед спеціалізованих пакетів для моделювання слід відзначити MATLAB з інтерактивним модулем Simulink. Пакет MATLAB є всесвітньо визнаним універсальним відкритим середовищем, і мовою програмування водночас, в якому інтегровані засоби обчислень, візуалізації, програмування та моделювання. Здійснюється програмування моделі та її налагодження, виконуються тестові прогони моделі на основі контрольних даних, провадиться аналіз чутливості, щоб визначити, які фактори в моделі суттєво впливають на робочі характеристики системи і мають моделюватись дуже точно. Після кожного з вищезазначених етапів перевіряється достовірність моделі. Перевірку умовно можна розділити на два етапи: перевірка правильності створення концептуальної моделі, тобто задуму – валідація; перевірка правильності її реалізації – верифікація. Під час перевірки достовірності потрібно відповісти на запитання про відповідність моделі модельованій системі, тобто визначити, наскільки ізоморфні система та модель. Як правило, у разі моделювання вимога ізоморфізму об'єкта та моделі надмірна, бо в цьому разі складність моделі має відповідати складності об'єкта. Через те будують гомоморфні моделі, в яких виконується вимога однозначної відповідності моделі об'єкту. На етапі верифікації розглядають, чи правильно перетворено концептуальну модель (модельні припущення) на комп'ютерну програму, тобто виконують налагодження програми моделювання. Це складне завдання, оскільки може існувати безліч логічних шляхів. Етап перевірки правильності реалізації моделі включає перевірку еквівалентності перетворення моделі на кожному з етапів її реалізації та порівняння станів. У цьому разі модель зазнає таких змін: концептуальна модель–математична модель–алгоритм моделювання- програмна реалізація моделі. Валідація – це процес, який дає змогу встановити, чи є модель (а не комп'ютерна програма) точним відображенням системи для конкретних цілей дослідження. Розробляється план проведення експериментів з моделлю для досягнення поставлених цілей. Основна мета планування експериментів – вивчення поведінки модельованої системи при найменших витратах під час експериментів. Зазвичай провадять такі експерименти:
Проведення експериментів планують для пошуку незначущих факторів. У випадку оптимізації якого-небудь числового критерію формулюють гіпотези щодо вибору найкращих варіантів структур модельованої системи або режимів її функціонування, визначають діапазон значень параметрів (режимів функціонування) моделі, у межах якого знаходиться оптимальне рішення. Визначають кількість реалізацій та час прогону моделі кожної реалізації. Провадять екстремальний експеримент, за результатами якого знаходять оптимальне значення критерію і відповідні значення параметрів. Для оцінювання точності стохастичних моделей будують довірчі інтервали для одержуваних вихідних змінних. Далі аналізують та оцінюють результати. Наводять результати комп'ютерних експериментів у вигляді графіків, таблиць, роздруківок, а також визначають якісні і кількісні оцінки результатів моделювання. Для унаочнення моделі використовують анімацію. Обговорюють процес створення моделі та її достовірність, щоб підвищити рівень довіри до неї. За отриманими результатами формулюють висновки з проведених досліджень і визначають рекомендації щодо використання моделі й прийняття рішень. Вищенаведені етапи моделювання взаємопов'язані, а сама процедура створення моделі ітераційна. Це пояснюється тим, що після виконання кожного етапу перевіряється правильність і достовірність моделі та в разі невідповідності моделі об'єкту здійснюється повернення до попередніх етапів з метою коригування та підстроювання моделі. Залежно від характеру внесених змін повертаються безпосередньо до попереднього етапу або до більш ранніх етапів. Детальніше технологія моделювання розглядається в наступних розділах. На останньому етапі моделювання документально оформлюють усі результати дослідження і готують програмну документацію для використання їх під час розроблення поточних і майбутніх проектів. Контрольні запитання 1. Прокоментуйте суть кожного з принципів побудови моделей. 2. Подайте основні етапи за технологією операційного дослідження. 3. Що таке верифікація моделі? 4. Що таке валідація моделі? 5. Яким чином задається час моделювання в задачі про водопостачання? 6. Чи можливо так задати час моделювання для цієї задачі, щоб він залежав від деяких подій? Наведіть приклади моделювання таких подій. 7. Дайте ситуаційний опис переходу пішоходом дороги. Розгляньте всі можливі ситуації.
Лекція 5. Моделі систем масового обслуговування
План 1. Характеристики систем масового обслуговування. 2. Вхідний потік вимог. 3. Організація черги. 4. Правила обслуговування вимог. 5. Вихідний потік вимог. 6. Режими роботи систем масового обслуговування.
У теорії і практиці моделювання систем важливе місце посідають моделі систем масового обслуговування (СМО). Такі системи зустрічаються нам щоденно. Це процеси обслуговування в черзі на заправній станції, у магазині, бібліотеці, кафе, також різні служби ремонту і медичної допомоги, транспортні системи, аеропорти, вокзали тощо. Черги виникають і за потреби скористатись телефонним зв'язком або передати повідомлення по Інтернету. Більше того, будь-яке виробництво також можна подати як послідовність таких систем. Особливого значення СМО набули в інформатиці. Це передусім комп'ютерні системи, мережі передавання інформації, бази і банки даних. Існує розвинутий математичний апарат теорії масового обслуговування (науковці західних країн цю теорією називають теорією черг), що дає змогу аналізувати ефективність функціонування СМО певних типів і визначати залежність між характеристиками потоку вимог, кількістю каналів (пристроїв для обслуговування), їх продуктивністю, правилами роботи СМО та її ефективністю. Перші теоретичні результати внаслідок вирішення проблем, пов'язаних із функціонуванням систем обслуговування, було отримано датським ученим, співробітником Копенгагенської телефонної компанії А. К. Ерлангом у період 1908-1922 років. Ці результати стосувались практичних завдань підвищення якості обслуговування абонентів і визначення кількості телефонних ліній. У подальшому з'ясувалось, що отримані теоретичні результати є настільки загальними, що їх можна використовувати для визначення оптимальної кількості кас і продавців на торговельних підприємствах, для розрахунків запасів у магазинах, достатніх для їх безперебійної роботи, тощо. Однак більшість результатів було отримано для систем, в яких процеси надходження та обслуговування вимог є марківськими або напівмарківськими. У цьому разі завдання аналізу СМО можна описати звичайними диференціальними рівняннями і в явному вигляді обчислити основні характеристики системи. На практиці часто виникають задачі, пов'язані з чергами, які неможливо розв'язати із застосуванням існуючих методів теорії масового обслуговування. Це зумовило інтенсивний розвиток методів дослідження СМО за допомогою засобів імітаційного моделювання. У цьому випадку характеристики СМО оцінюються наближено шляхом обробки результатів моделювання системи. У подальшому при розгляді обох підходів до аналізу СМО основна увага зосереджується на методах імітаційного моделювання. Функціонування будь-якої СМО полягає в обслуговуванні потоку вимог, які одна за одною або групами надходять до неї в деякі, як правило, випадкові моменти часу. Вимоги, які надійшли до СМО, обробляються протягом певного часу, після чого залишають систему. У будь-якій системі обслуговування передбачена наявність пристроїв для обслуговування (інші назви: прилади для обслуговування, сервери, канали) і вимог (інші назви: заявки, виклики, клієнти), які потребують обслуговування. Правила або алгоритми взаємодії пристроїв і вимог називатимемо дисциплінами поставлення в чергу та обслуговуванням. Для кожної СМО задається режим роботи. Слід відзначити, що для вимоги може бути потрібно кілька обслуговувань одним або кількома пристроями. Звичайно термін «пристрій для обслуговування» (англійською – «server») використовується для відносно простих моделей, в яких кожна вимога може обслуговуватись тільки одним пристроєм. Якщо ж вимоги обслуговуються кількома пристроями в певній послідовності, переміщаючись за заданим маршрутом, то має місце «мережа обслуговування» (англійською – «queueing network»). Іншими словами, мережа – це складна СМО. Зазвичай за допомогою методів теорії масового обслуговування розв'язують задачі з проектування та експлуатації однотипних елементів обслуговування – наприклад, розраховують кількість контрольно-пропускного обладнання, місць для ремонту, бензоколонок, обслуговуючого персоналу, ліній зв'язку, одиниць обладнання обчислювальної техніки тощо. Окремим типом завдань у теорії масового обслуговування є визначення місць накопичування вимог у системі обслуговування, наприклад визначення місць на стелажах на складі або в багатоповерховому гаражі, кількості пристроїв введення-виведення інформації комп'ютера, кількості місць у палатах госпіталю та ін. Найчастіше ефективність функціонування будь-якої СМО визначається за такими показниками:
Щоб визначити ці параметри, потрібно охарактеризувати СМО, тобто описати та задати такі характеристики:
Розглянемо ці характеристики більш детально. Для визначення вхідного потоку вимог потрібно зазначити моменти часу їх надходження до системи (закон надходження) і кількість вимог, які можуть надійти одночасно. Закон надходження може бути детермінованим (наприклад, вимога або вимоги надходять до системи у фіксовані моменти часу) або ймовірнісним (проміжки часу між моментами надходження вимог до системи мають рівномірний, експоненціальний або інший заданий закон розподілу). У загальному випадку вхідний потік вимог описується розподілом імовірностей проміжків часу між моментами надходження до системи двох сусідніх вимог. Здебільшого припускається, що ці проміжки часу є незалежними і мають однаковий розподіл випадкових величин і, таким чином, вимоги утворюють стаціонарний вхідний потік. У класичній теорії масового обслуговування, як правило, розглядається так званий пуассонівський (найпростіший) потік вимог, в якому кількість вимог k для будь-якого проміжку часу t має розподіл Пуассона: Ж0 = ^еЛ k>0, t>0, B.1) де X – інтенсивність потоку вимог (кількість вимог, які надійшли до системи за одиницю часу). Дисципліни постановки вимог у чергу та вибору вимог із неї для обслуговування визначають порядок, за яким вимоги стають у чергу, якщо пристрій для обслуговування зайнятий, та порядок їх виходу з черги для обслуговування – якщо пристрій для обслуговування вільний. Найпростіша дисципліна обслуговування передбачає поставлення вимог у чергу за порядком їх надходження. Вона має назву перший прийшов – першим обслужили (ПППО), в англомовній літературі – FIFO (First In First Out). Прикладом черги з такою дисципліною може бути черга до телефону-автомата. Існує також інший спосіб організації черги, коли для обслуговування вибираються останні в черзі вимоги (останній прийшов – першим обслужили (ОПІЮ)), в англомовній літературі – LIFO (Last In First Out)). Цей спосіб також називається стеком або «магазином». Прикладом черги з такою дисципліною обслуговування може бути паром, на якому перевозять авто, – автомобіль, який заїхав на паром перший, виїжджає з нього останнім. Що стосується правила вибору вимог із черги, то вибір може бути випадковим (в англомовній літературі – RANDOM), наприклад вибір куль із барабана для гри в лото. Під час вибору вимог із черги може враховуватись їх пріоритет. Черга може мати обмеження за довжиною або за часом перебування вимог у ній. Наприклад, якщо в черзі знаходиться більше трьох вимог, то нова вимога, яка надійшла, залишає систему, або вимога залишає систему, якщо час перебування її в черзі становить понад 2 хв. Прикладом черги з обмеженою кількістю місць є бункер, в який надходять заготовки, перш ніж їх буде оброблено верстатом. Буфери даних широко використовуються в комп'ютерній техніці. Під час обміну інформацією між пристроями, які мають різну швидкість обробки даних, інформація накопичується в буфері, а потім використовується пристроєм, що має меншу швидкість. Такі буфери організовуються в системах введення-виведення даних і мультиплексорах. У комп'ютерних мережах буфери створюють для організації черг повідомлень або пакетів. Правила обслуговування вимог характеризуються часом обслуговування (розподілом часу обслуговування), кількістю вимог, які обслуговуються одночасно, і дисципліною обслуговування. Обслуговування може бути організоване за допомогою одного або кількох ідентичних пристроїв. У першому випадку система називається одноканальною, у другому – багатоканальною. Час обслуговування вимог може бути детермінованим або заданим за ймовірнісним законом розподілу. Якщо пристрої для обслуговування об'єднані в ланцюжок, то система називається багатофазовою, тому що вимоги в ній послідовно проходять кілька фаз обслуговування (наприклад, складальний конвеєр автомобільного заводу). Дисципліна обслуговування визначає, за яких умов припиняється обслуговування вимог, як обирається для обслуговування наступна вимога, а також що станеться із частково обслуженою вимогою. Розрізняють безпріоритетні і пріоритетні дисципліни обслуговування. У разг безпріоритетного обслуговування порядок обслуговування визначається за дисципліною вибору вимоги з черги, наприклад ПППО. До безпріоритетних належить циклічна дисципліна обслуговування, яка часто використовується в комп'ютерних системах. Вимога (програма) багаторазово використовує пристрій для обслуговування (процесор) перед тим, як його залишити. Після закінчення кожного циклу обслуговування вимога знову надходить до черги для додаткового обслуговування. Під час пріоритетного обслуговування для кожної вимоги задається деякий числовий параметр, значення якого визначає її пріоритет. Значення пріоритету може бути незмінним (статичний пріоритет) або являти собою функцію, яка залежить від часу перебування вимоги в системі (динамічний пріоритет). Пріоритет може бути також відносним або абсолютним. Відносний пріоритет передбачає, що надходження вимоги з вищим пріоритетом не перериває обслуговування менш пріоритетної вимоги (обслуговування без переривання). Вимоги з однаковими пріоритетами можуть утворювати черги. Якщо в системі задається абсолютний пріоритет, то поява вимоги з більш високим пріоритетом перериває обслуговування менш пріоритетної вимоги (обслуговування з перериванням). У таких системах можуть утворюватися вкладені переривання, коли обслуговування вимоги, яка витиснула менш пріоритетну, буде перервано більш пріоритетною вимогою і т. д. Іноді в таких системах обмежують глибину переривання. Перервані вимоги можуть або залишати систему, або знову ставати в чергу для додаткового обслуговування. Зрозуміло, що дисципліни обслуговування з абсолютними пріоритетами можуть використовуватись тільки для систем з одним пристроєм для обслуговування. Вихідний потік – це потік вимог, які залишають систему, до того ж вони можуть бути як обслуженими, так і необслуженими. Структура формування потоку вихідних вимог більш важлива для багатофазових систем, де вихідний потік одного пристрою для обслуговування (фази обслуговування) є вхідним для іншого. Ймовірнісні характеристики розподілу вимог вихідного потоку в часі залежать від щільності вхідного потоку та параметрів роботи пристроїв для обслуговування. З теорії масового обслуговування відомо, що вихідний потік вимог СМО з М пристроями з очікуванням для найпростішого вхідного потоку з параметром λ і експоненціального розподілу часу обслуговування з параметром μ є найпростішим потоком з параметром λІ = min{λ, Mμ}. Це дає можливість аналізувати багатофазові системи і мережі СМО, в яких вихідний потік вимог одних систем обслуговування є вхідним для інших. У всіх інших випадках розподіл імовірності вихідних потоків вимог СМО має складнішу ймовірнісну природу і може вивчатись тільки шляхом спостереження за функціонуванням цих СМО під час моделювання. На практиці часто доводиться вивчати режими роботи СМО, за допомогою яких описується деякий виробничий процес або система обробки інформації. Якщо в системі пристрої для обслуговування час від часу виходять з ладу, то вводиться поняття режим відмови. Під час дослідження деяких систем треба брати до уваги ще один режим – блокування обслуговування, пов'язаний з тимчасовим перериванням або сповільненням процесу обслуговування. Зміна режиму роботи СМО може бути зумовлена зовнішнім впливом (наприклад, тимчасовою відсутністю деталей у технологічному процесі, ремонтом обладнання тощо) або виходом із ладу деякого пристрою системи (наприклад, блока живлення в комп'ютері). Контрольні запитання 1. Розгляньте потік Ерланга r-го порядку. Як розподіляються проміжки часу між сусідніми вимогами? Поясніть, чому. До якого розподілу буде наближатись розподіл Ерланга у разі збільшення параметра r? Який розподіл матиме час надходження вимог, якщо r прямує до нескінченності? 2. Розгляньте К незалежних джерел вимог, для кожного з яких проміжки часу між сусідніми вимогами розподілені за експоненціальним законом з параметром lk, тобто кожне джерело є пуассонівським. Розгляньте сумарний потік від усіх джерел і доведіть, що цей потік теж є пуассонівським з параметром L = Slk. 3. Розгляньте об’єднаний потік вимог із попереднього завдання і припустіть, що тепер його потрібно розбити на кілька потоків. Нехай р – це ймовірність того, що деяка вимога з об’єднаного потоку буде віднесена до підпотоку з номером k. Якщо інтенсивність сумарного потоку дорівнює L вимог за одиницю часу і ймовірності р вибираються довільно, то кожний з підпотоків створює пуассонівський процес з інтенсивністю lp. Покажіть це.
Лекція 6. ТИПИ МОДЕЛЕЙ СИСТЕМ МАСОВОГО ОБСЛУГОВУВАННЯ
План 1. Типи моделей систем масового обслуговування. 2. Формула Литтла. 3. Одноканальні системи масового обслуговування. 4. Багатоканальні системи масового обслуговування.
У теорії систем масового обслуговування розглядаються тільки такі СМО, параметри ефективності яких можна отримати аналітично в замкненому або числовому вигляді. Для позначення таких моделей СМО часто використовують запис, запропонований Канделом - X/Y/Z, де X - розподіл часу прибуття надходження вимог, Y— розподіл часу обслуговування, a Z — кількість пристроїв для обслуговування. Найпоширенішою моделлю, яка розглядається в теорії масового обслуговування, є модель типу М/М/1. Ця модель має тільки один пристрій для обслуговування (цифра 1), і в ній процеси розподілу часу надходження (перша буква М) та обслуговування (друга буква М) є марківськими. Для такої моделі час між двома надходженнями вимог до системи і час їх обслуговування мають експоненціальні розподіли. Модель типу М/М/1 може використовуватися, наприклад, для моделювання роботи однопроцесорної системи або стандартного пристрою для введення-виведення інформації (магнітного диска, принтера тощо). Модель типу D/D/1 - детермінована, а модель D/M/1 - змішана. Якщо відомостей про систему мало, її модель позначають як G/G/m — модель з будь-якими розподілами ймовірностей випадкових величин і т пристроями для обслуговування. У теорії масового обслуговування аналітичні результати отримано тільки для моделей типів D/D/1, М/М/1 і М/G/l. Для визначення характеристик моделей з іншими значеннями параметрів СМО потрібно використовувати методи імітаційного моделювання. У реальних системах не завжди можна описати закони розподілу вхідних потоків вимог і часу їх обслуговування. Для їх визначення потрібно вміти оцінювати характер робочого навантаження системи. Зокрема, у разі моделювання комп'ютерної системи треба знати, коли до системи надходять нові завдання, скільки часу потрібно для виконання процесором кожного з них, як часто програма звертається до пристроїв для введення-виведення інформації. Для цього треба розробити діаграму роботи системи, на якій можна зобразити потоки вхідних завдань у систему, ресурси, до яких вони направляються, а також час обслуговування завдань на цих ресурсах. Якщо графік робочого навантаження має періодичній характер, то під час спостереження за роботою комп'ютера є можливість отримати представницьку вибірку, яку можна застосовувати для аналізу показників ефективності СМО. Проте моделювання з використанням такого опису робочого навантаження (сценарію) дасть змогу відтворити тільки результати роботи комп'ютерної системи в минулому. На підставі цього не можна визначити, як працюватиме система в майбутньому. Для того щоб спрогнозувати поведінку системи в майбутньому, потрібно виявити закономірності та визначити один або кілька розподілів імовірностей, а не використовувати необроблені дані, отримані шляхом вимірювання. Якщо для визначення робочого навантаження на систему використовуються розподіли ймовірності, а для аналізу результатів моделювання — відповідні статистичні методи, то отримані результати можна поширити на більший діапазон робочих навантажень, ніж під час використання визначеного сценарію. У теорії масового обслуговування важливе значення має формула Литтла (закон збереження стаціонарної черги), яка дозволяє обчислювати середню кількість вимог, що знаходяться в системі. Щоб отримати формулу Литтла, розглянемо СМО загального виду, яку зображено на рис. 2.5 у вигляді «чорної скриньки», і будемо спостерігати за її вхідними та вихідними потоками вимог. Процес a(t) — деякий випадковий процес надходження вимог до системи за проміжок часу @, t). Процес b(t) визначає вихідний потік вимог із системи на цьому ж проміжку. Відобразимо обидва випадкових процеси у вигляді графіків, наведених на рис. 2.6. Кількість вимог, що знаходяться в системі в будь-який момент часу t, можна знайти як N(t) = a(t) - b(t). Заштрихована площа між двома кривими y(t) визначає загальну роботу (добуток кількості вимог на час перебування їх у СМО) на проміжку часу @, t), яка вимірюється у вимогах за секунду. Інтенсивність надходження вимог до СМО за час спостереження @, і) можна визначити як а середній час перебування вимог у системі за той же проміжок часу як Середня кількість вимог, що перебували в системі за проміжок часу @, і), Використовуючи вирази B.2)-B.4), отримаємо таку формулу: Nt = \Tt. B.5) Для того щоб СМО була в стані рівноваги, потрібно, щоб середній час перебування вимог у системі був більшим за середній час їх. обслуговування. Припустимо, що для СМО, яка розглядається, X = lim X, і Т = lim Tt, де X — інтенсивність надходження, аГ- середній час перебування вимог у системі. У цьому випадку існує також межа для середньої кількості вимог, які знаходяться в системі, тобто N = limNt. Тоді з формули B.5) отримаємо формулу Литтла у такому вигляді: N =ХТ. Отже, для будь-якого закону розподілу проміжків часу між двома моментами надходження вимог і будь-якого розподілу часу їх обслуговування, кількості пристроїв для обслуговування та дисципліни обслуговування середню кількість вимог, що знаходяться в СМО, визначають через інтенсивність надходження та середній час перебування вимог у системі. Інтуїтивне доведення формули Литтла базується на тому, що кількість вимог N у системі в момент надходження нової вимоги, буде такою ж, як і в момент, коли вимога залишає систему. Це свідчить про те, що СМО перебуває в стані рівноваги або сталому стані, тобто вимоги не можуть знаходитись у системі нескінченно довго і завжди залишають її. Як бачимо, під час виведення формули Литтла ніяких обмежень на тип СМО немає. Можна, наприклад, вважати, що СМО складається тільки з однієї черги або з одного пристрою для обслуговування. Контрольні запитання
Лекція 7. Дискретно-подійне моделювання систем масового обслуговування
План 1. Основні означення. 2. Простір станів систем масового обслуговування. 3. Приклад побудови моделі системи масового обслуговування. 4. Алгоритм моделювання систем масового обслуговування. 5. Мережі систем масового обслуговування. Контрольні запитання 1. Опишіть, яким чином потрібно змінити роботу алгоритмів моделювання, описаних у попередньому розділі, щоб урахувати: а) обмеження, накладені на довжину черги; б) обмеження, накладені на час перебування в черзі; в) наявність m однакових пристроїв для обслуговування вимог. Під час реалізації алгоритму для третього варіанта розгляньте визначення одного із вільних пристроїв у порядку наданих їм номерів 1,2,...,m і у випадковому порядку. Поясніть, чому для першого способу визначення вільних приладів їх завантаження буде різним. 2. Продовжіть моделювання процесів обслуговування в магазині методом, описаним у попередній лекції, до 20 вимог, задавши довільне значення часу надходження та часу обслуговування вимог. Побудуйте за допомогою програми Excel або пакета STATISTICA гістограму часу перебування вимог у черзі. 3. У якому випадку потік вимог з мережі буде пуассонівським? Поясніть чому. 4. Які складності виникають під час розрахунків мереж СМО? 5. Для розрахунків яких систем можна застосовувати операційний аналіз? 6. Сформулюйте гіпотезу про баланс потоків у мережі СМО. Поясніть, як її можна використовувати під час розрахунків різних СМО. 7. Деяка виробнича дільниця має L верстатів, які працюють 24 год на добу Н діб. Будь-який з верстатів може вийти з ладу в будь-який час. Якщо верстат зламався, його замінюють іншим, резервним, а зламаний направляють для ремонту в майстерню. Відремонтований верстат повертають до роботи. У майстерні є три спеціалізовані дільниці для ремонту верстатів. Технологічний цикл ремонту починається на дільниці діагностики, де визначаються причина виходу з ладу верстатів та необхідний вид ремонту. Діагностика триває А1 ± В1 год (розподіл – рівномірний). Ремонт виконується в механічних і електричних майстернях. За статистичними даними, отриманими за результатами аналізу виходу з ладу верстатів, 75% випадків становить відмова електричного обладнання верстатів, а 25% – механічного. Діагностикою зайнято m1 робітників, ремонтом механічного обладнання – m2, а ремонтом електричного обладнання – m3 робітників. Досвід експлуатації свідчить, що на діагностику витрачається А1 ± В1 і год, на ремонт електричного обладнання верстата – А2 ± В2 год, а на ремонт механічного обладнання – А3 ± В3 год (розподіл – рівномірний). Якщо верстат використовується у виробництві, час напрацювання на відмову має експоненціальний розподіл з параметром Т год. Час для перевезення верстатів із цеха в майстерню та в зворотному напрямку незначний, і його не враховують. Між робітниками в майстерні немає ніяких відмінностей, як і між верстатами. Керівнику необхідно визначити, скільки робітників треба найняти для роботи в майстерні на кожній дільниці, щоб мінімізувати час ремонту обладнання. Час спостереження за системою – Н діб. Необхідні дані наведено в табл. Таблиця. Параметри моделювання роботи майстерні
8. У касовому залі з продажу квитків на літаки працює 20 касирів, кожний за своїм терміналом. Термінали підключено до двохпроцесорного кластерного сервера, який обробляє запити клієнтів на будь-якому з двох процесорів. Середній час обробки запиту процесором становить 10 с. Кожний касир працює із системою в режимі «запит-відповідь», тобто не посилає новий запит, доки не отримає відповідь на попередній. Середній час введення запиту касиром становить 30 с. До касирів постійно є черга клієнтів. Знайдіть середній час відповіді системи на запит клієнтів. Побудуйте залежність цього часу від кількості працюючих касирів, яка може змінюватись від 1 до 20 чоловік.
Лекція 8. МЕРЕЖІ ПЕТРІ
План 1. Мережі Петрі – математична модель. 2. Прості мережі Петрі. 3. Розмітка мережі Петрі. 4 Формальне визначення мереж Петрі.
Мережі Петрі – це математична модель, яка широко використовується для моделювання динамічних систем багатьох типів. Мережі Петрі запропонував Карл Адам Петрі у своїй дисертації в 1962 році, і з часом вони стали однією з найбільш зручних математичних конструкцій для представлення моделей складних причинно-наслідкових систем. За допомогою мереж Петрі досить легко будувати моделі будь-яких асинхронних, паралельних і розподілених систем. Високий рівень формалізації мереж Петрі дає змогу легко будувати на їх основі алгоритми і програми моделювання. Як математичний інструмент мережі Петрі можна використовувати для опису рівнянь станів, алгебричних рівнянь та інших математичних моделей, що керують поведінкою систем. Крім того, вони є досить зручним інструментом для аналізу та автоматизації побудови програм імітаційного моделювання. В Європі існує два провідних центри, де займаються проблемами моделювання систем на основі мереж Петрі, – у Данії та Німеччині. У центрах провадять теоретичні дослідження, розробляють програмні засоби моделювання, а також впроваджують стандарти стосовно використання мереж Петрі (http://www.daimi.au.dk/ PetriNets/standard/). Ознайомитися з базою інструментальних засобів моделювання мереж Петрі можна в Інтернеті на сайті http://www.daimi.au.dk/ PetriNets/tools/ quick.html. Мережа Петрі є орієнтованим дводольним графом, який має чотири базових елементи: вузли, або місця (places), переходи (transitions), дуги (arcs) і маркери (tokens). Нагадаємо, що дводольним називається граф, який має дві множини вузлів і не має ребер, з'єднуючих вузли однієї множини. Вузли позначаються кружками і визначають стан, в якому може знаходитись мережа або її частина. Переходи – це активні елементи мережі, які позначають дії, виконувані під час спрацювання переходів. Для того щоб перехід міг спрацювати, необхідне виконання певних умов, які визначаються наявністю маркерів у вузлах мережі, з'єднаних з переходом. Якщо умови настання подій виконано, то вважають, що перехід збуджений. Переходи позначаються короткими вертикальними або горизонтальними лініями. Вузли та переходи з'єднуються орієнтованими ребрами (дугами). Вузли, з яких виходять дуги до певного переходу, називаються вхідними вузлами переходу, а вузли, до яких ведуть дуги з певного переходу, - вихідними. Два вузли або два переходи з'єднуватись дугами не можуть. Кожний перехід може бути з'єднаним з вузлом тільки однією дугою (вхідною або вихідною). Функціонування мережі Петрі можна описати різними способами. Наприклад, можна розглядати вузли як певні умови, а переходи – як події. Таким чином, стан мережі в кожний момент часу задається системою умов. Для зручності задання умов у мережі Петрі вводяться маркери (фішки), які зображуються крапками всередині вузлів. Виникнення певної комбінації маркерів у вузлах приводить до настання деякої події, яка у свою чергу викликає зміну стану умов мережі. Стан маркування або стан мережі Петрі визначається сукупністю маркерів кожного окремого вузла мережі. На рис. 3.1 зображено просту мережу Петрі з одним переходом, трьома вузлами, два з яких містять маркери. Перехід, в якого всі вхідні вузли містять маркери, називається збудженим (рис. 3.1). Збуджений перехід може спрацювати, після чого всі маркери із вхідних вузлів переходу перемістяться у вихідні (рис. 3.2). Таким чином, настає подія, яка змінює стан мережі. Якщо одночасно збуджуються кілька переходів мережі, виникає невизначеність, тому одночасне спрацювання кількох переходів у мережі Петрі неможливе, тобто переходи спрацьовують послідовно, миттєво. Незважаючи на те, що маркери змінюють своє положення у вузлах, прості мережі Петрі – це статичні моделі, в яких не враховується динаміка в часі (зміна станів мережі не залежить від моментів часу). Для того щоб за допомогою мережі Петрі відтворити динаміку роботи деякої детермінованої динамічної системи в часі, необхідно зазначати моменти спрацьовування переходів. Такі можливості мають тільки розширення мереж Петрі, в яких спрацювання переходів здійснюється в задані моменти модельного часу з деяким постійним кроком Dt. Розмітка М мережі Петрі – це функція, яка ставить у відповідність маркерам вузлів цілі додатні числа. Суть розмітки полягає в приписуванні кожному вузлу певної кількості маркерів. Наприклад, якщо позначити через N саму мережу Петрі, через Р – множину вузлів у мережі N, через n(Р) – кількість вузлів, то кожному вузлу цієї мережі можна поставити у відповідність число із послідовності {1, 2,..., n(Р)}. Таким чином, розмітку М можна зобразити за допомогою вектора з n(Р) елементів, в якому і-й елемент визначає кількість маркерів у і-му вузлі. У загальному випадку кількість маркерів у вузлі може бути більшою за одиницю. На рис. 3.3 зображено мережу Петрі, яка може перейти в такий стан, коли жоден з переходів не буде збудженим. Мережа в такому стані називається заблокованою. Розмітка заблокованої мережі задається такими елементами: М = [2, 0, 0]; Р = {1, 2, 3}; n(Р) = 3; a, b, c, d – переходи. Переходи а, b можуть бути збудженими, а переходи с, d – ні. У результаті збудження та спрацьовування переходу а отримуємо розмітку М1 = [1,1, 0], за якої збуджуються переходи a, b і с. У разі спрацювання переходу с отримуємо мережу з новою розміткою М2 = [2, 0, 0]. У мережах Петрі паралельне спрацювання переходів обмежується тільки кількістю маркерів у вузлах, тобто для спрацьовування переходів мають бути маркери у всіх вхідних вузлах. При початковій розмітці мережі, яку зображено на рис. 3.3, переходи а і b можуть збуджуватись одночасно. Однак збудження двох переходів в один і той же момент часу не означає, що вони можуть одночасно спрацьовувати. Наприклад, переходи а і b мережі з розміткою М = [1, 0, 0] можуть одночасно тільки збуджуватись, але не спрацьовувати. Причина в тому, що в разі спрацювання як переходу а, так і переходу b повинні одночасно зникнути обидва маркери з першого вузла, що неможливо. Перехід, в якого немає жодного вхідного вузла, завжди є збудженим і може видавати (генерувати) маркери. Генерування маркерів можна розглядати як послідовне виконання функції розмітки М, тобто послідовність зміни розміток М0, М1, М2,..., де Мi+1 отримане із Мi у результаті збудження деякого переходу. Тут М0 – початкова розмітка мережі Петрі. Перехід, який не має жодної вихідної дуги і має тільки одну вхідну дугу, збуджений завжди тільки в тому випадку, якщо вхідний вузол містить маркер. Такий перехід може знигцувати маркери. У загальному випадку для заданої мережі N з початковою розміткою М0 є багато можливих послідовностей спрацювання переходів. Мережа Петрі знаходиться в «живому» стані (живуча розмітка), коли кожний з переходів може збуджуватись нескінченну кількість разів. Мережа Петрі знаходиться в «мертвому» стані (заблокована), якщо вона не має жодного збудженого переходу. Заблокована мережа є стійкою, тобто її маркери не можуть змінювати свої позиції у вузлах. На рис. 3.3 зображено мережу з початковою розміткою М0 = [2, 0, 0]. У разі спрацювання переходів а і Ь початкова розмітка замінюється на розмітку М2 = [0, 1, 1]. Мережа з такою розміткою стане заблокованою, і жодний з переходів не зможе бути збудженим. Отже, розмітка М0 не є живучою. Дійсно, для цієї мережі не існує живучих розміток. Незалежно від кількості маркерів у вузлі 1 переходи а і b будуть спрацьовувати доти, доки всі маркери не перейдуть у вузли 2,3. Коли у вузлі 1 не залишиться маркерів, мережа заблокується. Вважають, що два переходи конфліктують, якщо вони не можуть бути збудженими одночасно. Незважаючи на те, що умови конфлікту формально точно не визначені, зрозуміло, що суть конфлікту тісно пов'язана з типом тупикової ситуації, яка мала місце в мережі, зображеній на рис. 3.3, де переходи с і d конфліктують при розмітці М0. Теорем, якими задаються умови блокування та скінченності мереж Петрі, не існує. Подібні теореми доведено тільки для розмічених графів, які є простішими за мережі Петрі. Для графів тільки певних типів доведено, що перехід, який не може бути збудженим, існує лише в тому випадку, якщо в графі існує орієнтований цикл без маркерів. Для мереж Петрі аналогічного твердження довести не вдалось. У розміченому графі, зображеному на рис. 3.4, перехід а мертвий, оскільки дуги 1 і 2 створюють орієнтований цикл, який не має маркерів. Існує кілька способів формального опису мереж Петрі, які відрізняються способами задання елементів і зв'язків. Згідно з працею [26] будемо визначати мережу Петрі трьома елементами: (Р, Т, F), дe P – непорожня множина елементів мережі, названих вузлами; Т – непорожня множина елементів мережі, названих переходами; F – функція інцидентпностпі, що задає зв'язок між елементами множин Р і Т. Для мережі Петрі, визначеної елементами (Р, Т, F), повинні виконуватись такі умови. 1. Р u T = 0, тобто множини вузлів і переходів не перетинаються. 2. (F ≠ 0) л (Vх є Р п Т, 3 у є Р u T.xFy v yFx), тобто будь-який елемент мережі інцидентний хоча б одному елементу іншого типу. 3. Якщо для довільного елемента мережі х є X позначити через *х множину його вхідних елементів, а через х* – множину його вихідних елементів, то УРі> Рі еР'(*Рі =*Р2)лІР*і = Р*2)=> ІРі = рг)> тобто мережа не міститиме пари вузлів, які інциденті до тієї ж множини переходів. На основі поняття мережі Петрі, яка описує тільки статичну топологію модельованого процесу або системи, вводяться динамічні мережні структури, в яких вузлам приписуються спеціальні розмітки для моделювання виконання умов. З мережею пов'язують поняття її функціонування, яке описується зміною її розмітки (умови) у результаті спрацювання переходів. До динамічних мереж відносяться мережі Петрі та їх різні узагальнені варіанти. Таким чином, мережа Петрі не є динамічною системою, в якій стан моделі змінюється в часі, він змінюється тільки в раз; спрацювання переходів і зміни розмітки. Зміну позицій маркерів у вузлах можна визначити, якщо задати мережу Петрі як структуру PN = (Р, Т, F, М0>, де (Р, T,F) – скінченна мережа (множини Р і Т скінченні), а М0 – початкова розмітка мережі, яка ставить у відповідність будь-якому вузлу Рі є Р деяке число М0 (р) = п. Функціонування мережі Петрі описується за допомогою множини послідовностей спрацьовувань і множини досяжних у мережі розміток. Ці поняття визначаються через правила спрацювання переходів мережі. Розмітка мережі PN є функцією M:P=>N(N – множина натуральних чисел). Якщо припустити, що всі вузли мережі строго впорядковані деяким чином, тобто Р = (рі,Р2, —>Рп)<то розмітку М мережі (у тому числі і початкову розмітку) можна задати як вектор чисел М = [тп^, тп2, ..., тп„] такий, що для будь-якого і A < і < п) ті = М(рі). Якщо Р' = (рц,Рі2, -:Pik) ~ підмножина вузлів з Р, то умовимося через МІР") позначати множину розміток {М(рп), ..., М(р^)}. Якщо Р' представити як вектор Р' = ■ (pih ..., р^), то М(Р') позначає вектор проекції розмітки М на Р'. Перехід t є Т може спрацювати при деякій розмітці М мережі Р, якщо \/р є є *tM(p) > F(p, t), тобто кожний вхідний вузол р переходу t має розмітку, не меншу, ніж кратність дуги, що з'єднує р і t. Цю умову можна записати як М > *F(p, t). Для ординарної мережі Петрі (тобто мережі, в якій дуги мають кратність, рівну одиниці) умова спрацьовування переходу означає, що будь-який вхідний вузол цього переходу містить хоча б один маркер, тобто має ненульову розмітку. Спрацьовування переходу t розміткою М породжує розмітку М за таким правилом: \/р є Р : М(р) - М(р) - Fip, t) + Fit, p), тобто М = M-*Fit) + F*it). На множині розміток уводять відношення [> безпосереднього проходження розміток: М [> М <=> 3 t є Т:ІМ > *Fit)) &ІМ =М-*F(f) + F* it)), тобто розмітка М безпосередньо отримана за розміткою М, якщо знайдеться такий перехід t, який може спрацювати в разі розмітки М, і розмітка М є результатом спрацьовування цього переходу в разі розмітки М. Розмітка М досяжна від розмітки М, якщо існує послідовність розміток М, М1, М2, ..., М і слово т = t\t2 ... 4 в алфавіті Т такі, що M[tt >Ml[t2 >M2... [tk>M. Слово т у цьому випадку називається послідовністю перемикань, які ведуть від М до М. Множину розміток, досяжних у мережі PN від розмітки М, позначимо через /?(Pjv, M). Якщо RiPx) = RiPw М0), то множину всіх розміток, досяжних у мережі Рц від початкової розмітки М°, називають множиною досяжних розміток мережі. Властивості мережі Петрі визначають, досліджуючи можливі послідовності спрацьовувань переходів і множини досяжних у мережі розміток.
Контрольні запитання 1. Побудуйте просту мережу Петрі для роз’вязання задачі про філософів, що обідають. 2. Технологічна лінія на виробництві створює напівфабрикат з визначених матеріалів і працює періодично. На початку кожного періоду завантажується певна кількість матеріалів, після чого починається основний процес – виробництво, під час якого може виникнути збій. Тоді матеріали, які знаходились у лінії (завантажені на початку періоду) вилучаються з технологічного процесу. Завантажується нова порція матеріалів, і основний процес починається спочатку. На рисунку наведено модель цього процесу в термінах мережі Петрі. Пріоритети переходів Т2, ТЗ вважати рівними. Задайте функцію початкової розмітки М0 цієї мережі (Р, Т, F, М0} і вагу зазначених дуг (J, К, Н). Варіанти відповіді: 1) М0 = [1, 0, 1, 0, 0, 1, 0], (J = 1, К = 2, Н = 1); 2) М0 = [1, 1, 2, 0, 0, 2, 2], (J = 1, K = 1, Н = 2); 3) М0 = [1, 1, 2, 0, 0, 1, 1], (J = 1, К = 1, Н = 2); 4) М0 = [1, 1, 1, 0, 0, 2, 2], (J = 1, K = 1, Н = 1). 3. Розглянемо процес, який є прикладом «нецікавої» гри. Дехто сидить у кімнаті, в який є закрита ваза і відкрита скринька, в обох містяться чорні і червоні кулі. Швидко взявши будь-які дві кулі з вази, він звіряє їх кольори: якщо вони різні, то кладе їх у скриньку, інакше кулі повертаються у вазу і туди ж зі скриньки додається куля того ж кольору, що і дві попередні. Процес повторюється доти, доки в одній із ємностей не буде вистачати куль для продовження гри. На рисунку наведено модель цього процесу в термінах мереж Петрі. Введені позначення: R – червона куля, В – чорна куля. Необхідно встановити вагу дуг Fі, і = 1,…,5. Варіанти відповіді: F1 = R, F2 = B, F3 = R, F4 = 2В, F5 = 2В, F6 = 2R; F1 = B, F2 = R, F3 = B, F4 = 2В, F5 = 2R, F6 = 2В; F1 = B, F2 = R, F3 = B, F4 = 2R, F5 = 3В, F6 = 3R; F1 = R, F2 = B, F3 = B, F4 = 2R, F5 = 3В, F6 = 3R.
Лекція 9. МОДЕЛЮВАННЯ СИСТЕМ ЗА ДОПОМОГОЮ МЕРЕЖ ПЕТРІПлан 1. Розширення простих мереж Петрі. 2. Формалізоване зображення моделі за допомогою мережі Петрі. 3. Розширення можливостей вузлів під час моделювання. 4. Розширення можливостей дуг під час моделювання. 5. Розширення можливостей переходів під час моделювання.
Прості мережі Петрі містять лише три основних елементи: вузли, переходи та маркери. Тому побудова за їх допомогою моделей складних динамічних систем, в яких протікає велика кількість взаємодіючих паралельних і асинхронних процесів та існує багато інформаційних і матеріальних потоків, стає досить складною та громіздкою процедурою. Це помітно звужує клас моделей систем, які можна побудувати на основі простих мереж Петрі. У таких випадках застосовують розширення простих мереж Петрі, які дають можливість значно спростити побудову складних моделей і їх графічне зображення. Розширення мережі Петрі — це така їх модифікація, яка збільшує можливості мережі стосовно опису та моделювання систем. Існують різні розширення мереж Петрі, орієнтовані на моделювання систем різних типів: стохастичних, динамічних, предикатних та ін. Кольорові мережі Петрі дають змогу значно зменшити розміри мереж, які використовуються, наприклад, для опису моделей складних паралельних обчислювальних систем. Необхідність дослідження динаміки ресурсних потоків у системах змусила шукати шляхи включення до мереж Петрі в явному вигляді часових параметрів. Крім того, у деяких моделях необхідно розрізняти порядок надходження маркерів до вузлів та вибору маркерів з них, що дає змогу впорядкувати події в часі. На практиці широко використовуються проблемно-орієнтовані розширення мереж Петрі, серед яких найбільш відомі £-мережі, комбі-мережі, FIFO-мережі, М-мережі та ін. Нижче наведено класифікацію та коротку характеристику деяких розширень мереж Петрі, які часто використовуються для формалізації опису обчислювальних комплексів, систем і мереж. Більшість матеріалу, викладеного в цьому розділі, базується на документації користувача системи POSES++, розробленої німецькою компанією GPC mbH (http://www.gpc.de/), і містить опис засобів, які розширюють можливості мереж Петрі в разі моделювання складних розподілених і паралельних систем. У простих мережах Петрі допускається наявність у вузлі лише одного маркера, тоді як у розширених мережах кожний вузол може містити кілька маркерів (наприклад, вузол 1 на рис. 3.3). Кількість маркерів у вузлі позначає число поряд з вузлом. Відповідно для цих вузлів змінюються і правила маркування: ♦ перехід збуджується тільки тоді, коли число, яке визначає кількість маркерів у кожному вхідному вузлі, більше або дорівнює одиниці; ♦ якщо збуджений перехід спрацьовує, то число маркерів у всіх вхідних вузлах, які містять маркери, зменшується на одиницю, а в усіх вихідних вузлах — збільшується на одиницю. Певна річ, кількість маркерів не може бути від'ємним значенням. Мереж Петрі достатньо для опису причинно-наслідкових подій, які виникають у системах, однак мережі не забезпечують повну спільність з логічними операціями. Зрозуміло, що проста мережа Петрі відтворює роботу тільки логічного елемента «І» («AND»), тому за допомогою цієї мережі не можна змоделювати збудження переходу, коли вхідний вузол не має маркерів (логічний оператор заперечення «НІ»). Для цього в розширених мережах уводяться дуги заперечення, які зображуються лініями з кружечком на кінці замість стрілки (рис. 3.5) і не мають дугової ваги (дугова вага визначає пропускну здатність дуги). Дуги, визначені раніше, розглядаються як позитивні. Вони завжди направлені від деякого вузла до переходу і не можуть мати зворотного напрямку. Наявність дуги заперечення змінює правила маркування на такі: ♦ перехід збуджується лише тоді, коли число, яке визначає кількість маркерів кожного вхідного вузла з позитивною дугою, більше або дорівнює одиниці, та коли кількість маркерів кожного вхідного вузла з дугою заперечення дорівнює нулю; ♦ якщо збуджений перехід спрацьовує, то число маркерів усіх вхідних вузлів з позитивною дугою зменшується на одиницю, у той час як кількість маркерів вхідних вузлів з дугами заперечення залишається незмінною. Кількість маркерів усіх вихідних вузлів збільшується на одиницю. Рис. 3.5. Введення дуги заперечення Для кожної позитивної дуги можна задати певний ваговий коефіцієнт (або вагу), рівний одиниці або більший за неї (рис. 3.6). За замовчуванням ваговий коефіцієнт дуги дорівнює одиниці. Тоді збудження та спрацьовування переходу відбувається за такими правилами: ♦ перехід збуджується тільки тоді, коли кількість маркерів у кожному вхідному вузлі більше ваги дуги або дорівнює їй, а для дуги заперечення дорівнює нулю; ♦ у разі перемикання переходу кількість маркерів кожного вхідного вузла зменшується на відповідну вагу вхідної дуги та залишається незмінною для дуг заперечень. Кількість маркерів кожного вихідного вузла збільшується на вагу відповідної вихідної дуги. 3.2.2. Формалізоване зображення моделі за допомогою мережі Петрі Один із найскладніших етапів створення моделі — це вибір методу її формалізації. Зазвичай існує кілька підходів до зображення моделі системи і мережі Петрі. Продемонструємо на прикладах, як перейти від змістовної постановки задачі до формальної моделі. Приклад 3.1 Покажемо, як за допомогою мережі Петрі можна синхронізувати кілька асинхронних обчислювальних процесів, що виконуються в пам'яті комп'ютера. Розглянемо роботу комп'ютерної системи, в якій два обчислювальні процеси, Я, і Я2, намагаються одночасно записати дані в область пам'яті (Я,) і зчитати з неї дані (Я2). Проблема, яку потрібно вирішити — синхронізація доступу процесів до пам'яті. Щоб запобігти суперечності, необхідно заборонити одночасний доступ процесів до одної і тої ж області пам'яті. Це означає, що активним може бути тільки один процес, який виконує операцію доступу до пам'яті. Контрольні запитання 4. Клініка має відділення хірургії, де на зміні працює один хірург і три медсестри. Коли з’являється пацієнт, якому роблять операцію, у ній бере участь весь присутній персонал. Після проведення операції пацієнт розміщується в палаті реабілітації, де його доглядає одна з медсестер. Періодично його оглядають один хірург і одна медсестра, доки не з’явиться новий пацієнт. На рис. 3.25 наведено модель даного процесу в термінах мереж Петрі. Введені позначення: S — хірург, N — медсестра, Р — пацієнт. Необхідно встановити вагу дуг Xj, і = 0, 5. Варіанти відповіді: Х0 = {Р}, Х1 = {S, N], X2 = {S, 3N], ХЗ = {S, N], X4 = {N}, X5 = {N}; Х0 = {2Р}, Х1 = {S, 2N], Х2 = {S, 3N], ХЗ = {S, N], X4 - {N}, X5 - {N}; Х0 = {2Р}, Х1 - {S, N], Х2 = {S, 3N), ХЗ = {S, 2N), Х4 = {2N}, Х5 - {2N}; Х0 = {Р}, Х1 = {S, 2N], Х2 = {S, 2N), ХЗ = {S, 2N], Х4 = {2N}, Х5 = {N}. Чи правильно вибрано функцію початкової розмітки Af° цієї мережі [Р, Т, F, Л/°] згідно з рис. 3.25? 5. Розглянемо процес організації конференції. Спочатку учасників повідомляють, що їм необхідно представити матеріали для реєстрації. Після цього (або в той же час) починається процес прийому матеріалів різних авторів, який триває лише певний період часу. Потім матеріали реєструються. У кожному конкретному випадку приймається рішення про запрошення автора. Можна прийняти лише 80% матеріалів для доповідей. Яка з моделей цього процесу, зображених на рис. 3.26, а-в в термінах мереж Петрі, є правильною?
Лекція 10. ОРГАНІЗАЦІЯ ПРОВЕДЕННЯ ТОРГІВ ЗА ПРОЕКТАМИ
План 1. Основні положення. 2. Класифікація торгів. 3. Функції учасників торгів. 4. Порядок проведення підрядних торгів. 10.1. Основні положенняРеалізація проектів в умовах ринкової економіки зводиться, по суті, до серії взаємозалежних і скоординованих закупівель ресурсів проекту в найширшому розумінні слова, у тому числі: машин та устаткування, матеріалів, ліцензій і «ноу-хау», будівельних, монтажних і пусконалагоджувальних робіт (ген- і субпідрядників), консультаційних послуг з розробки проектно-кошторисної документації (проектувальники), проведення торгів, нагляду за роботами, підготовки персоналу тощо. Поняття «закупівлі» у закордонній практиці управління проектами має набагато більш глобальний характер порівняно з його традиційним вітчизняним розумінням як етапу матеріально-технічного забезпечення проекту. Основна відмінність полягає у більш широкому розумінні терміна «ресурси проекту», що означає не тільки традиційні матеріально-технічні й трудові ресурси, а й увесь необхідний спектр робіт і послуг за проектом. Об’єднуючим елементом ресурсів проекту є основний спосіб їхньої закупівлі – через конкурсні торги (тендери). Контрольні запитання
Лекція 11. ФРМУВАННЯ Й РОЗВИТОК ПРОЕКТНОЇ КОМАНДИ
План 1. Лідерство. Роль менеджера проекту. 2. Команда проекту. 3. Мотивація персоналу. 4. Порядок проведення підрядних торгів. 11.1. Лідерство. Роль менеджера проектуБез «людської системи» всі інші системи управління проектом не працюватимуть. Основу сучасної концепції управління персоналом у проектах становить зростаюча роль особистості працівника, знання його мотивацій, уміння їх формувати і спрямовувати відповідно до завдань, які стоять перед проектною командою. Контрольні запитання
а) люди схильні чинити опір розглядові нових пропозицій; б) люди схильні до самозахисту; в) функціональні працівники більше прагнуть зосереджуватися на поточній діяльності, ніж працювати на перспективу; г) як функціональні працівники, так і персонал команди частіше очікують на індивідуальне, ніж на групове визнання.
Лекція 12. ПРОГРАМНЕ ЗАБЕЗПЕЧЕННЯ ПРОЦЕСУ УПРАВЛІННЯ ПРОЕКТАМИ
План 1. Загальна характеристика автоматизованих систем управління проектами. 2. Microsoft Project. 3. Open Plan Professional. 4. Spider Project. 5. Sure Trek Project Manager і Primavera Project Planner (P3). Контрольні запитання
Лекція 13. ПРОГРАМНЕ ЗАБЕЗПЕЧЕННЯ ПРОЦЕСУ УПРАВЛІННЯ ПРОЕКТАМИ
План 1. Загальна характеристика автоматизованих систем управління проектами. 2. Microsoft Project. 3. Open Plan Professional. 4. Spider Project. 5. Sure Trek Project Manager і Primavera Project Planner (P3). Контрольні запитання
Лекція 14. ПРОГРАМНЕ ЗАБЕЗПЕЧЕННЯ ПРОЦЕСУ УПРАВЛІННЯ ПРОЕКТАМИ
План 1. Загальна характеристика автоматизованих систем управління проектами. 2. Microsoft Project. 3. Open Plan Professional. 4. Spider Project. 5. Sure Trek Project Manager і Primavera Project Planner (P3). Контрольні запитання
Лекція 15. ПРОГРАМНЕ ЗАБЕЗПЕЧЕННЯ ПРОЦЕСУ УПРАВЛІННЯ ПРОЕКТАМИ
План 1. Загальна характеристика автоматизованих систем управління проектами. 2. Microsoft Project. 3. Open Plan Professional. 4. Spider Project. 5. Sure Trek Project Manager і Primavera Project Planner (P3). Контрольні запитання
Лекція 16. ПРОГРАМНЕ ЗАБЕЗПЕЧЕННЯ ПРОЦЕСУ УПРАВЛІННЯ ПРОЕКТАМИ
План 1. Загальна характеристика автоматизованих систем управління проектами. 2. Microsoft Project. 3. Open Plan Professional. 4. Spider Project. 5. Sure Trek Project Manager і Primavera Project Planner (P3). Контрольні запитання
Лекція 17. ПРОГРАМНЕ ЗАБЕЗПЕЧЕННЯ ПРОЦЕСУ УПРАВЛІННЯ ПРОЕКТАМИ
План 1. Загальна характеристика автоматизованих систем управління проектами. 2. Microsoft Project. 3. Open Plan Professional. 4. Spider Project. 5. Sure Trek Project Manager і Primavera Project Planner (P3). Контрольні запитання
Лекція 18. ПРОГРАМНЕ ЗАБЕЗПЕЧЕННЯ ПРОЦЕСУ УПРАВЛІННЯ ПРОЕКТАМИ
План 1. Загальна характеристика автоматизованих систем управління проектами. 2. Microsoft Project. 3. Open Plan Professional. 4. Spider Project. 5. Sure Trek Project Manager і Primavera Project Planner (P3). Контрольні запитання
ПРЕДМЕТНИЙ ПОКАЖЧИКАвтоматизовані системи управління проектами 207 Аналіз відхилень 133 Балансова матриця 50 Бананоподібна крива 128 Види планів 40 – проектів 11 Вимога на зміну 141 Витрати на забезпечення якості проекту 158 Внутрішня організаційна структура проекту 58 Гібридна організаційна структура 54 Графік Гантта 108 Графіки контролю, або контрольні карти 155 – передування 85 – потоків 151 Дивізіональна організаційна структура 62 Діаграма Парето 156 Життєвий цикл проекту 18 Забезпечення якості проекту 153 Затратна структура проекту 79 Згладжування ресурсних гістограм 117 Зовнішня організаційна структура проекту 47 Інструменти управління проектами 33 Календарний графік 107 Класифікація ризиків 165 Команда проекту 198 Контрактна матриця 53 Контроль за змінами 139 – проекту 131 Параметри сіткового графіка 86 – проектними ризиками 173 – якістю проекту 147 Учасники проекту 31 Федеральна організаційна структура 63 Форма проектної команди 48 Форми організаційної структури проекту 45 Функціональна матриця 49 Якість проекту 145 CTR-словник 78 S-подібні криві 136 СПИСОК ЛІТЕРАТУРИ1. Бурков В. Н., Новиков Д. А. Как управлять проектами: Науч.-практ. издание. — Сер.: Инфляция в России на пороге XXI века. — М.: СИНТЕГ–ГЕО, 1997. 2. Бушуев С. Д., Морозов В. В. Динамическое лидерство в управлении проектами. — К.: УАУП, 1999. — 311 с. 3. Воропаев В. И. Управление проектами в России: Основные понятия. История. Достижения. Перспективы. — М.: Аланс, 1998. — 230 с. 4. Мир управления проектами: Основы, методы, организация, применения / Пер. с англ.; под ред. Х. Решке, Х. Шепле. — М.: Аланс, 1994. — 304 с. 5. Управление программами и проектами: (Модульная программа для менеджеров) / М. Л. Разу и др. — М.: ИНФРА—М., 2000. — 320 с. 6. Управление проектами: Зарубежный опыт / А. И. Кочетков и др. — СПб.: Два-Три, 1993. — 446 с. 7. Управление проектами: Справочник для профессионалов / И. И. Мазур, В. Д. Шапиро, С. А. Титов и др. — М.: Высш. шк., 2001. — 875 с. 8. Управление проектами: Толковый англо-русский словарь-справочник / Ред. В. Д. Шапиро. — М.: Высш. шк., 2000. — 379 с. 9. Управление проектами: Учебник для вузов / Под ред. В. Д. Шапиро. — СПб.: Два-Три, 1996. — 610 с. 10. A Guide to the Project Management Body of Knowledge. Project Management Institute, PMI Publishing Division, 1996. 11. Celeland D. Project Management: Strategic Design and Implementation. — N. Y., 1989. 12. Harrison, Advanced. Project Management. — Gawer Publishing, 1992. 13. Kerzner H. Project Management, 2-nd Ed. — Van Nastrand Reinhold Company, 1992. 14. Lach, Dennis. Project Management. — Gawer Publishing Co Ltq., 1988. 15. Turner, J. Rodney. The Handbook of Project-Based Management. New York. — N.Y.: McGraw-Hill, 1992. З повагою ІЦ “KURSOVIKS”! |