четверг, 18 июня 2015 г.

Студентам 5-го курсу спеціальності "БІКС"

Консультація з дисціплини "Математичне моделювання ..." відбудеться в п’ятницю 19 червня о 17 год. в 11 корпусі.

понедельник, 15 июня 2015 г.

"МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ПРОЦЕСІВ ТА СИСТЕМ" питання до іспиту для 5 курсу


  1. Загальне поняття математичної моделі. Механіка Арістотеля порівняння з ньютонівською.
  2. Компонентне моделювання. Концепція «віртуального стенду». Слідкуючий диференціатор.
  3. Типи моделей. Схема моделювання нелінійних динамічних систем.
  4. Неперервні системи керування. Принцип суперпозиції, лінійна ланка. Моделі у просторі сигналів. Перетворення Лапласу та передаточні функції.
  5. Імпульсні, перехідні характеристики та передаточні функції, частотні характеристики.
  6. ВІВО-стійкість, критерії стійкості.
  7. Критерій Михайлова, ознага чергування коренів.
  8. Алгебра передаточних функцій: з’єднання та перетворення. Принцип однонаправленністі.
  9. Структурні схеми, сигнальні графи. Визначник графу, формула Мейсона.
  10. Фізична реалізуємість передатних функцій. Схеми з підсилювачами та інтеграторами. Фізична реалізуємість та причинність.
  11. Задача реалізації для передатних функцій. Канонічна форма спостережуємості.
  12. Задача реалізації для передатних функцій. Канонічна форма керованості.
  13. Модель системи керування у просторі станів. Реалізація у просторі станів. Канонічні нормальні форми у просторі станів.
  14. Загальна схема зв’язків між моделями лінійних систем.
  15. Дискретизація та відновлення сигналів. Теорема Котельникова, формула відновлення.
  16. Причинні методи відновлення, ZOH і FOH, помилкі відновлення.
  17. Кінцеві автомати. Типи синхронізації.
  18. Асинхронні автомати.
  19. Мережі Петрі. Неформальне визначення.
  20. Мережі Петрі. Формальне визначення.
  21. Мережі Петрі, процедура сінхронізації. Можливі та сумісно можливі події. Стійкість МП.
  22. Експеримент з натурной, аналітичной та імітаційной моделлю. Статистичний експерімент (метод Монте-Карло). Приклад (площа кола).
  23. Методи генерації випадкових чисел. Вимоги до генераторів.
  24. Генерація випадкових чисел з визначеним розподілом.
  25. Квазінеперервність та псевдовипадковість для випадкових чисел.
  26. Моделювання випадкових подій та величин.
  27. Системи масового обслуговування. Система М/М/1 та ії властивості.
  28. Планування модельних експериментів. Основні поняття теорії планування: факторний простір, рівні, центр плана, проміжок варіювання, спостерігаєма, дисперсія відтворюваності.
  29. Стратегічне планування експеріментів. Засоби побудови стратегічного планування. Факторний експерімент.


1. Бусленко Н.П. Моделирование сложных систем. -М.: Наука. -1978. -400 с.
2. Гультяев А. Визуальное моделирование в среде MATLAB: учебный курс. -СПб: Питер. -2000. -430 с.
3. Филлипс Ч., Харбор Р. Системы управления с обратной связью. –М.: Лаборатория Базовых Знаний. -2001. -616 с.
4. Бенькович Е.С., Колесов Ю.Б., Сениченков Ю.Б. Практическое моделирование динамических систем. –СПБ.: БХВ-Петербург. -2002. -464 с.

суббота, 13 июня 2015 г.

Екзамен з ММПР

14 та 15 червня відбудеться у 9 год. ранку в 202/11

пятница, 12 июня 2015 г.

Студентам 3 курсу спеціальності "Прикладна математика"

Консультація з дисціплини "МОДЕЛІ ТА МЕТОДИ ПРИЙНЯТТЯ РІШЕНЬ" відбудеться в суботу 13 червня о 17 год. в 11 корпусі.

среда, 10 июня 2015 г.

Глоссарій для ММПР



ГЛОСАРІЙ З ТЕОРІЇ ПРИЙНЯТТЯ РІШЕНЬ

(головні визначення та результати за курсом)
  1. Процес прийняття рішення (ППР).
Прийняття рішення — це вибір найкращого варіанту з множини наявних варіантів (альтернатив).
  1. Cуб’єкти ППР, їх ролі та функції.
ОПР (особа що приймає рішення) це людина (або колективний орган), що має ціль, яка мотивує постановку задачі ПР (ЗПР) та пошук її розв'язання. ОПР визначає які засоби є допустимими для досягнення мети, та несе повну відповідальність за наслідки реалізації прийнятого рішення.
Консультантами називають фахівців із прийняття рішень. Вони організовують процес прийняття рішення, розробляють та застосовують модели ЗПР, відповідні процедури прийняття рішень.
Експерт – це фахівець у предметній галузі, що володіє спеціальною інформацією про ЗПР, але не несе прямої відповідальності за результати її розв'язання, тільки за якість власних оцінок. Експерти приймають участь у ППР на всіх стадіях постановки й розв'язання ЗПР.
  1. Вподобання, бінарні відношення, зв’язок з ПР.
Бінарним відношенням R на множині Ω називається довільна підмножина R декартового добутку Ω×Ω (нагадаймо, що декартовим добутком двох множин A і B називається множина пар елементів (a, b), де a , ). БВ представляє вподобання на множині альтернатив, та результат парного порівняння як вибору з двох альтернатив.
  1. Завдання БВ матрицею, графом, перетином, їх значення для ПР. Головні властивості та операції з БВ.

1.Перелік елементів

, Х- множина альтернатив
Наприклад, якщо
тоді і т.п.

2.Матриця БВ

Перетин рядка з стовпчиком містить 1 – означає, , інакше

3.Граф



  1. Поняття критерію. Багатокритерійна оптимізація.
Критерій – функція, яка дозволяє співставити порівнювальну оцінку кожної альтернативі:
– шкала. Зазвичай це множина дійсних чисел. Будь - яка функція може виступати в якості критерію, бо вона відображає уподобання ОПР – не можна накладати будь-яких обмежень на волю ОПР. Найважливішою особливістю ЗПР є їх багатокритерійність. ЗПР з одним критерієм відносяться до задач дослідження операцій. Для їх розв’язання використовують методи оптимізації.
  1. Метод лінійної згортки (вагових коефіцієнтів).
Суть методу полягає в тому, щоб із багатокритеріальної задачі зробити однокритеріальну
шляхом обчислення лінійної комбінації початкових критеріїв з призначеними коефіцієнтами, що задовольняють умовам λi 0, ∑ λi = 1 ,та звуться вагами.
  1. Домінування за Парето багатокритерійних альтернатив.
Альтернатива А домінує альтернативу В за Парето, якщо по всім критеріям оцінки альтернативи А не гірше , ніж оцінки альтернативи В, і хоча б за одним критерієм оцінка альтернативи А краща.
  1. Множина Парето її властивості.
Множина Парето Par – це множина недомінованих альтернатив.
. Парето-оптимальні альтернативи (що містяться у цій множині) є непорівнюваними за Парето.
  1. Домінування за Слейтером багатокритерійних альтернатив. Множина Слейтера та множина Парето.
Альтернатива А домінує альтернативу В за Слейтером, якщо вона краща ніж В за всіма критеріями.
Множина Слейтера Sle містить альтернативи недоміновані за Слейтером.
Порівняння Sle & Par
Альтернатива, яка домінована по Слейтеру, автоматично домінована по Парето.
aRSb => aRPb. Альтернатива, яка недомінінована по Парето, недомінована по Слейтеру. aRSb => aRPb
Критерій доминування по Слейтеру більш строгий, а це значить, що множина домінованих по Слейтеру альтернатив вужча, ніж множина домінованих по Парето. Тобто множина недомінованих по Слейтеру альтернатив ширша, ніж множина недомінованих по Парето альтернатив .
  1. Функції вибору.
Функція вибору C(Х) – це відображення, що зіставляє пред’явленню - кожній підмножині X Ω , її власну підмножину , тобто , для X Ω. ФВ визначаеться правилом, за яким відбіраються найкращі альтернативи з представлених до вибору. Повна ФВ задана на всіх можливих пред’явленнях.
  1. ФВ та БВ, комбінаторні оцінки їх числа. 
, пред’явлення з п альтернатив
Кількість нормальних функцій вибору
  1. Скалярний оптимізаційний механізм.
f(x) – критерій;
x
  1. Умовно-екстремальний механізм.
f(x) – критерій; обмеження
  1. Сукупно-екстремальний механізм.
  1. Паретовський механізми.
критерій
  1. Вибір за блокуванням та домінуванням.
Оптимізаційний механізм домінування
Маємо БВ R
- вибір домінуючих.
Оптимізаційний механізм блокування
- вибір недомінованих.
  1. Лексікографічна оптимізація, проста та з поступками.
Головна ідея лексикографічного підходупослідовна оптимізація. Критерії впорядковуються за важливістю, далі оптимізуються по черзі.
Якщо відповідно вектора критеріїв вводиться вектор поступок
– вектор критеріїв,
– вектор поступок, послідовна оптимізація проводиться з точністю до
Формується ланцюг вкладених множин:
, остання множина і буде Слго(Х).
  1. Мажоритарний механізм.
Механізм вибора за більшістю. Якщо маємо набір критеріїв (типа вподобань виборців)
- мажорітарний вибір.
Якщо альтернатива за більшістю критеріїв краща, ніж довільна інша, то вона обирається.
  1. Слабкодомінантні механізми.
Слабодомінантний механізм домінування
Слабодомінантниий механізм блокування
  1. Сильнодомінантні механізми.
Сильнодомінантний механізм домінування
Розглянемо БВ R і воно вибирається так
, тобто R , де
,
Сильнодомінанатний механізм блокування
  1. Гіпердомінантні механізми.
Гіпердомінантний механізм домінування:
Гіпердомінантний механізм блокування:
  1. Головні властивості ФВ:
1.Наслідування
2.Відкидання
3. Узгодження
4.Суматорність
  1. ,
5.Умова Плота
6.Мультиплікаторність
7.Монотонність
  1. Характеристичні властивості ФВ за Айзерманом і Малишевскім, класи ФВ.
Класи функцій:
1) Властивість наслідування – Н (наследования):
2) Властивість узгодження – С (согласия):
3) Властивість відкидання – О (отбрасывание):
4) Строге наслідування – К (строгое наследование, константность):
  1. Теорема про зв’язки класів.
1.Характеристичні властивості наслідування (Н), узгодження (С) і відкидання (О) незалежні в в сукупності.
2.Властивість константності:
3.В : , – функції, які володіють властивостями наслідування (Н), узгодження (С), відкидання (О), при цьому володіють однозначністю.

Незалежність Н, С і О в сукупності означає: те що виконується або не виконується одна із умов, не залежить від того чи виконується будь-яка іх комбінація. Ці відношення зручно відображаються у вигляді діаграми (трилистник):
  1. Турнірний механізм та його властивості.
Звичайно переможці в турнірах визначаються за парними порівняннями з вибуванням. Але існують також турніри кругові – наприклад, шахматний турнір: кожен зустрічається з кожним, за каждую гру отримують бали. Кращий той, у кого більше балів. Тобто повинно бути деяке бінарне відношення . Задамо шкалу, яка буде визначати бали:
Кількість балів гравця буде сумою всіх результатів порівнянь:
ФВ турнірного механізму не належить ніяким характеристичним класам.

  1. Зв’язки між характеристичними властивостями та механізмами вибору.
  • породжується сильнодомінантним механізмом домінування
  • породжується слабодомінантним механізмом домінування
  • породжується гіпердомінантним механізмом домінування
  • породжується БВ слабкого порядку
  • реалізується скалярним оптимізаційним механізмом
  • породжується паретовським механізмом
  • породжується сукупно - екстремальним механізмом
  1. Декомпозиція функцій вибору з класу Н.
Всяка ФВ з класу наслідування може бути представлена теоретико-множинною лінійною комбінацією ФВ, породжених скалярним оптимізаційним механізмом:
Наслідок:
  1. Декомпозиція функцій вибору з класу Σ0 з мажоритарною операцією.
Будь-яка функція вибору із може бути представлена в мажоритарною операцією від суперпозиції функцій вибору, породжуваних довільними бінарними відношеннями (нормальними функціями вибору).
  1. Декомпозиція функцій вибору з класу Σ0 з матричною операцією.
Де функція вибору породжується слабкими порядками, тобто це функції із – класу функцій, які реалізовані скалярним оптимізаційним механізмом.
: рівень, індекс
  1. Нормальні ФВ. Теорема про непорожність нормального вибору.
CR(X) – оптимізаційний механізм блокування;
CR(X) – оптимізаційний механізм домінування.
Теорема про непорожність нормального вибору.
БВ R породжує за механізмом блокування на кінцевій множині альтернатив, тоді та тількі тоді, коли R ациклічне .
  1. Структура та властивості нормального вибору.
Твердження 1
Якщо елемент не обирається на пред’явлені X, то він не обирається і на будь-якому його розширенні.
Твердження 2
Значення НФВ на будь-якому пред’явленні визначається її значеннями на одно- і на двоелементних пред’явленнях.
Твердження 3
Якщо C(X) НФВ, то C(X) = Èi Çj C({xi,xj})
  1. Функція корисності. Задача теорії корисності.
Поняття функції корисності (ФК) та критерію дуже близьки – ФК також є функцією вида f : A→S, але для неї повинно бути задано бінарне відношення несторої переваги, узгоджено з нею наступним чином:      a,b A, aRb ⇒ f(a) f(b).



Тверження



Якщо f : A→S функції корисності, та φ:R→Rмонотонно 


зростаюча функція, тоді φ(f)також функції корисності.

  1. Теорема Фон-Неймана про існування функції корисності.
Аксіоми:
1. Існує бінарне відношення нестрогої переваги , то повинно бути
Pвідношення строгої переваги;
I – відношення байдужості(еквівалентності);
2. Для R виконуються дві умови:
- Зв’язність
- Транзитивність
3. Бінарне відношення визначається на A (множина детермінованих результатів, функцію корисності треба будувати на A* (розширена множина ).
4. Аксіома стиснення результатів
5. Аксіома середньої ціни
Наприклад, якщо є можливість виграти 1 монету з ймовірністю , є ймовірність виграти 3 монети з такою ж ймовірністю, то в середньому виграш буде складати 2 монети, які якраз знаходяться між експериментальними результатами.
6. Якщо знаходиться у відношенні строгої переваги з , а той в свою чергу строго кращий , то існує ймовірність така, що з її допомогою можна створити еквівалентну лотерею
При цьому називають детермінованим еквівалентом лотереї ЕЛ)

Теорема Фон-Неймана

При виконанні всіх вищезгаданих аксіом


Остання формула – формула очікуваної корисності
  1. Дерево рішень, алгоритм згортання дерева.
Дерева рішень - це спосіб представлення правил в ієрархічно послідовної структурі, де кожному об'єкту відповідає лише один кінцевий вузол, що надає відповідь.
Під правилом розуміють логічну конструкцію, надана у вигляді «Якщо А, тоді Б»
  1. Парадокс Алле.
Існує соціологічно достовірні ситуації, вибір в якіх здійснюється не відповідно функції корисності.
  1. Дилема генерала.
Суть в тому, що якщо задачу вибору формулювати в термінах виграшу чи в термінах втрат, результат може залежати від способу формулювання.
  1. Причини нераціональної поведінки.
1) нестача інформації у ЛПР в процесі вибору;
2) недостатній досвід ЛПР: він знаходиться в процесі навчання і тому змінюють свої вподобання;
3) ЛПР намагається найти рішення, оптимальне з точки зору сукупності критеріїв (цілей), строго впорядкованих по важливості, але не може його знайти;
4) різниця між об’єктивно необхідним часом для реалізації планів и суб’єктивним горизонтом планування ЛПР.
  1. Задача колективного вибору. Профіль вподобань, агрегування індивідуальних вподобань.
  2. Теорема Мея.
Всі анонімні монотонні нейтральні виборчі системи - це такі і тільки такі, в яких обирається кандидат, який набрав найбільше число голосів, або обидва кандидата, якщо вони набрали рівне число голосів.
  1. Переможець за Кондорсе.
За Кондорсе переможцем оголошується той кандидат, що перемагає всіх інших у попарних порівняннях.
  1. Парадокс Кондорсе.
Розв’язуюче правило вибору переможця за Кондорсе не є ациклічним.
Тобто можливі циклічні колективні вподобання за Кондорсе.
  1. Переможець за Борда.
Результати голосування виражаються у вигляді балів, набраних кожним з кандидатів. Нехай число кандидатів рівно n. Тоді за перше місце присуджується n балів, за друге - (n-1), далі знімаємо по одиниці, за останнє місце - один бал. Результат визначається сумою балів за всіма місцями, переможець має максимальний.
  1. Змістовні за Кондорсе розв’язуючи правила.
Правила Компленда, Сімпсона та Шульце - змістовні за Кондорсе, тобто завжди підтверджують перемогу за Кондорсе.
  1. Переможець за Коплендом.
Переможцем Копленда (переможцем за Коплендом) називається кандидат (кандидати) з найвищою оцінкою за Коплендом. Нехай K(а,х) число виборців, для яких кандидат а кращий за х, a ≠ x. При порівнянні кандидата a із іншим кандидатом x вважаємо K(а,х)=+1 , якщо для більшості виборців a кращий за x, інакше K(а,х)=-1 ; та K(а,х)=0 при рівності. Оцінкою Копленда кандидата a є сума всіх оцінок його парних порівнянь К(а)= .
  1. Переможець за Сімпсоном.
Аналогічно S(a,x) число виборців, для яких кандидат a кращий за x, a ≠ x . Оцінкою Сімпсона кандидата a називається число S(a)= . Переможцем Сімпсона називається кандидат з найвищою оцінкою Сімпсона.
  1. Переможець за Шульце.
Той хто перемагає всіх останніх з точки зору сили впливів (з врахуванням непрямих впливів).
  1. Парадокс Фішберна.
Існує профіль переваги для якого переможець по Борда з використанням будь-якої строгої шкали Борда відрізняються від переможця по Кондорсе.
  1. Аксіоми Ерроу, теорема про неможливість.
А1- (універсальна): рішаючи правило ефективно на будь-якій перевазі виборців;
А2-(одноголосність): рішаючи правило підтверджує єдиноголосність вибору виборців;
А3-(незалежність від незв'язаних альтернатив): результат попарного порівняння не залежить від третіх кандидатів;
А4-(повноти): будь-яка пара кандидатів повинна бути порівнювальна;
А5-(транзитивність): транзитивність нестрогого бінарного відношення колективного вподобання: А В С А С.
Теорема про неможливість: існує лише одне розв’язуюче правило колективного вибору, що задовільняє аксіомам А1-А5, диктаторське.
  1. Послаблення аксіом, олігархичне правило.
Серед виборців існує група “олігархів”. Переможець той, хто одноголосно обирається цією групою. Наслідок послаблення вимоги транзитивності лише на строгу компоненту колективного вподобання.
  1. Колективні функції корисності, утилітарна та егалітарна позиції.
Формально задача колективного прийняття рішень формулюється так:
max{и(... ,ui (x), ...) | xX En} , i N = {1,…n}, де ui – функція корисності і-го агента, и — колективна функція корисності, X – множина альтернатив.
Агрегування u(x)=mini uі(x) називається егалітарною позицією.
Утилітарною позицією називається агрегування и(х)=
  i uі(x) .
.Визначені функції колективної корисності мають відповідні назви. При утілітарному підході колективна корисність є сумою індивідуальніх, при егалітарному є корисністю найслабшого індивіда.