1. Екстремум функції f(x) в точці X=(x1, x2, …xn). Поняття про строгий та не строгий максимум(мінімум) функції. Нехай ф-я f(x) визначена на проміжку [a;b] і x0—внутрішня точка проміжку. Ф-я f(x) в точці x0 має максимум, якщо існує окіл точки x0, що для всіх х (х ?x0), цього околу виконується нерівність f(x)? f(x0). Саме значення f(x0) наз-ть максимумом(локальним)ф-ції f(x) в точці x0. Ф-я f(x) в точці x0 має мінімум, якщо існує окіл точки x0, що для всіх х (х ?x0), цього околу виконується нерівність f(x)?f(x0). Саме значення f(x0) наз-ть мінімумом(локальним)ф-ції f(x) в точці x0. Максимум і мінімум функції в точці об(єднує спільний термін — екстремум (локальний екстремум) функції в точці. Якщо для х не=х0 у данному околі точки х0 f(x)< f(x0) (f(x)> f(x0)), функція f(x) має строгий максимум(мінімум). 2. Стохастична одноканальна модель теорії масового обслуговування з надійним приладом. В загальному випадку моделі масового обслуговування досліджують системи, що складаються з 3 частин: потоку вимог, черги, яку утворює потік вимог та каналу обслуговування. Припускають, шо потік вимог є Пуасонівським. Каналів в системі може бути від 1 до ?. Якщо лише один канал, то система називається одноканальною. Розглянемо найпростішу систему з одним обслуговуючим приладом, до якої надходить один пуассонівський потік вимог із інтенсивністю (. Час обслуговування вимоги є випадковою величиною, що розподілена за експоненціальним законом із параметром (. При цьому кількість вимог, які можуть перебувати в системі, не обмежується. У стаціонарному режимі роботи система подається ймовірнісною моделлю такого виду:
Основні числові характеристики для системи визначаються за формулами: імовірність того, що система простоюватиме (відсутні вимоги), така: ; імовірність того, що система зайнята обслуговуванням вимог, становить математичне сподівання кількості вимог, що перебувають у системі: М=?/(1-?) Для систем обслуговування розглядуваного класу визначаємо такі числові характеристики: середню кількість вимог потоку, що перебуває в черзі: L=M-? середній час перебування вимог у системі: T=M/?=?/? середній час перебування вимоги в черзі: T*=L/? 3. Поняття про задачі на екстремум. Екстремальна точка. Абсолютний та відносний максимум(мінімум) функції. Нехай задано графік функції: В точці хі буде максимум, якщо f(xі+?xі)<f(xі). Якщо f(xі+?xі)> f(xі), то в точці буде мінімум. Екстремальними точками будуть точки х1, х2, х3, х4,х5,х6,х7, при чому max f(xі) буде в точках хі=(х1, х3,х5, х7), а min буде в точках хі=(х2,х4,х6). При цьому в точках х1, х3, х7 будуть локальні максимуми, а в точці х5—глобальний(або абсолютний). Аналогічно абсолютний мінімум буде в точці х2. 4. Транспортна задача та її загальний запис. Перший опорний план. Транспортна задача – це специфічна задача лінійного програмування, застосовувана для визначення найекономнішого плану перевезення однорідної продукції від постачальників до споживачів. Нехайта . Причому, аi , вj >0; Матриця вартостей має такий вигляд В загальному випадку Cji – вартість перевозки з j пункту в і-й; в – складські приміщення, а - пункт призначення. Перший розподіл являється першим опорним планом. Для цього будується транспортна таблиця. А1 А2 Аm
В1 Х11 Х12 Х1m
В2 Х21 Х22 Х2m
...
Вк Xk1 Xk2 Xkm
5. Градієнт функції f(x) та його використання для дослідження на екстремум функції. Градієнтом від функції f(x)=f(x1,x2, ...xn) буде вектор, компонентами якого є частинні похідні по кожній компоненті. Градієнт позн-ся . Послідовність дослідження функції на екстремум з використанням градієнта: f(x)>max(min), 1)q(x)=0, q(x)=(q1(x), q2(x)…qm(x)) 2) розбиваємо х на у і z 3)знаходимо матрицю Якобі і управляючу матрицю
4) знаходиться добуток J-1 *С 5) знаходиться стаціонарна точка , і значення х підставляється у рівняння 6) якщо <0, то максимум, а якщо >0, то мінімум. 6. Описати алгоритм знаходження першого опорного плану. Нехай та . Причому, аi , вj >0; В загальному випадку в – складські приміщення, а - пункт призначення. Для побудови першого опорного плану слід побудувати таблицю такого вигляду А1 А2 Аm
В1
В2
...
Вк
Далі необхідно заповнити комірки за такими правилами: 1) якщо а1>в1, то комірка Х11 заповнюється значенням в1, після чого в комірках Х1m ставиться прочерк, а залишок (а1- в1) порівнюють із значенням в2 за аналогічною схемою. Сума по першому стовпчику має дорівнювати а1. 3) якщо а1<в1, то в комірку Х11 записується значення а1, а вниз по вертикалі у комірках ставляться прочерки. Різниця (в1 –а1) розноситься по горизонтальним коміркам першого рядка, причому сума по рядку має дорівнювати в1. Аналогічні перетворення слід виконати для кожного елемента матриць а та в. Після цього отримаємо таблицю, в якій деякі комірки будуть заповнені, а деякі—ні. Отримаємо так званий перший розподіл, який і являється першим опорним планом. 7. Стаціонарна точка. Матриця Гессе та її використання для дослідження функції f(x) на екстремум. Нехай дана ф-я f(x), х=(х1, х2, ...хn).Матриця Гесе в загальному випадку має вигляд Елементи матриці будуть симетричними відносно головної діагоналі. Алгоритм знаходження екстремуму з використанням матриці Гесе: Знаходимо стаціонарну точки Будується матриця Гесе Н=() і знаходиться Н в стаціонарній точці Досліджують матрицю на екстремум (якщо матриця Гесе буде додатньовизначеною, то в точці буде мінімум, а якщо від’ємно— то максимум. 8. Цільова функція для транспортної задачі та умови яким мають задовольняти змінні хij Цільова функція (відображає сукупні витрати для певного плану перевезень):
Цільова функція мінімальна при оптимальному опорному плані. Зміст транспортної задачі полягає в знаходженні множини змінних Хij(0, i= 1,m j= 1,n, що задовольняють умовам:
Xij(0 і таких, при яких цільова функція досягає мінімуму. 9. Метод приведенного градієнта (Метод Якобі). Метод Якобі застосовується у випадках, коли слід дослідити f(x) >min(max), де х=(х1,х2,…хn) при обмеженнях q(x)=0, де q=(q1,q2…qm). Послідовність дослідження функції на екстремум за методом Якобі: f(x)>max(min), 1)q(x)=0, q(x)=(q1(x), q2(x)…qm(x)) 2) розбиваємо х на у і z 3)знаходимо матрицю Якобі і управляючу матрицю
4) знаходиться добуток J-1 *С 5) знаходиться стаціонарна точка
і значення х підставляється у рівняння 6) якщо <0, то максимум, а якщо >0, то мінімум. 10. Описати алгоритм подвійного симплекс-методу. Якщо; то обернена задача записується так
Здійснивши ці перетворення, необхідно побудувати симплексну таблицю, яка має такий вигляд
x1 xn b Qi
X11 X1n b1
X21 X2n в2
?j L -c1 -cn
Далі знаходимо розрахунковий стовпчик по найменшому значенню С. Знаходимо розрахунковий рядок. Для цього в ділимо на коефіцієнти і беремо з них найменше. Всі решта елементів (крім розрахункового елемента) розрахункового стовпчика = 0, а елементи рядка ділимо на розрахунковий елемент. Далі використовуємо метод Дж. Гаусса Процес проходить доки елементи рядка стануть + (а коли досліджуємо на min то -) або=0. 11. Використання теореми Тейлора для визначення максимуму (мінімуму) функції F(x). 12. Графічний метод розв’язання задач на екстремум для лінійних моделей.
Точка в якій входить вектор – буде min. 13. Лінійні моделі. Цільова функція та обмеження в загальному вигляді. Для дослідження лінійних моделей на оптимальний розв’язок (максимум, мінімум) використовують симплексний метод. Більшість задач, що вирішуються методами дослідження операцій, можуть бути сформульовані так: Максимізувати f (x1,…,xn) при обмеженнях g1 (x1 , …, xn ) ?b1;g2 (x1 , …, xn ) ?b2; gm (x1 , …, xn ) ? bm. Де f (x1,…,xn) – цільова функція або ефективність системи; х=(х1 , ...., хn) – варіюючи параметри; g1 ,....gm – функції, які задають обмеження на наявні ресурси. В загальному випадку задачі симплексного методу записуються так:
Де L(x) – функція цілі При таких обмеженнях
14. Класифікація ланцюгів Маркова: регулярні, поглинаючі, та циклічні. Дати визначення та навести приклади. Поглинаючі. Якщо серед можливих станів системи знаходиться хоча б 1-н стан, при якому система попавши в стан, там і залишається, то ця матриця наз. поглинаючою.
Імовірний граф цієї матриці:
Циклічні. Ланцюги називаються циклічними, якщо вони послідовно переходять з 1-го стану в інший і мають такий вигляд:
Регулярні. Ланцюг Маркова називається регулярним, якщо існує таке ціле число k(k > 0), що перехід системи з будь-якого можливого стану в інший може здійснитися за А кроків.
Граф для цієї матриці:
15. Необхідні та достатні умови існування екстремуму функції.
Якщо , то функцію можна представити в вигляді ряду
В точці х, де похідна = 0, якщо , то буде min, якщо , то буде max. ----ряд Тейлора для функції n-змінних - квадратична форма
Достатня умова екстремуму. Якщо Н додатньо визначена, то в точці буде min, і навпаки. 16. Пуасонівський потік подій та його властивості. Вивести формулу для обчислення ймовірності Рm(t). Випадкові збудники, які викликають перехід з одного стану в інший утворюють Пуассонівський потік. Послідовність подій, які відбуваються в випадкові моменти часу утворюють потік. Потік подій назив Пуассонівський, якщо йому притаманні такі властивості: стаціонарність, відсутність післядії, ординарність. Потік подій наз стаціонарним, якщо ймовірність появи того чи іншого числа подій на проміжку часу t не залежить від того де цей відрізок часу знаходиться по відношенню до поч. Відліку часу. Потік подій наз потоком з відсутністю післядії, якщо ймовірність не залежить від того скільки подій відбулося до початку проміжку t. Потік подій наз ординарним, якщо ймовірність появи однієї події за малий відрізок часу ?t пропорційна довжині відрізку з точністю P1 (?t)=
За проміжок часу ?t може відбутися або одна подія або не одної.
Ймовірність того, що за час t відбудеться к подій обч.:
17. Функція Лагранжа. Множники Лагранжа. Метод множників Лагранжа дає змогу відшукати максимум(мінімум) функції при обмеженнях. Основна ідея методу полягає у переході від задачі на умовний екстремум до задачі відшукання безумовного екстремуму деякої побудованої функції Лагранжа. Нехай задано задачу: мінімізувати f (х1, х2...хn) при обмеженнях h1 (х1, х2...хn)=0, h2 (х1, х2...хn)=0, hm (х1, х2...хn)=0. Припустимо, що усі функції f, h1, h2, hm – диференційовні. Введемо набір змінних (число яких дорівнює числу обмежень), які мають назву множників Лагранжа, і складемо функцію Лагранжа:
18. Області допустимих розв’язків для графічного методу та їх класифікація. Розв’язком системи нерівностей може бути: замкнута множина ? незамкнута множина ? порожня множина ? 1-а точка
19. Аналіз чутливості за допомогою методу Якобі. Коефіцієнт чутливості дозволяє визначити реакцію цільової функції на незначні зміни аргумента. Для визначення коефіцієнта чутливості використовується така система
20. Описати алгоритм симплекс-методу. Z = С1x1 +С2x2+…+С nxn N
..
Qi
x11 x12 .. x1n b1
x21 x22 .. x2n b2
... ... .. ...
xn1 xn2 .. xnn bn
?j L -C1 -C2 .. -Cn
Коефіцієнти при L мають обернені знаки. 1. Знаходимо розрахунковий стовпчик по найменшому значенню С. 2. Знаходимо розрахунковий рядок: для цього Коефіцієнти ділимо на вільний член обраного стовпчика(берем лише додатні) і обираємо найменший з них. 3. Всі елементи розрахункового стовпчика крім розрішаю чого елемента замінюємо на нулі, а всі елементи розрахункового рядка ділимо на розрішаючий елемент. 4. Далі розв’язуємо за методом Джордана-Гаусса. Розв’язання продовжується до тих пір поки всі коефіцієнти при L не стануть додатними або рівними 0. В цьому випадку: Якщо Cij>0 > max Якщо Cij<0 > min Якщо Cij=0 > mx=min 21. Метод множників Лагранжа. В загальному випадку задається функція f(X)>max(min) Задаються обмеження:
1. Будуємо функцію Лагранжа.
2. Знаходимо стаціонарні точки.
3. Розв’язуємо систему рівнянь. Та будуємо окантовану матрицю Гессе НВ 4.Знайдемо координати точки стаціонарностей Х0=(х01, х02, х03,.... х0n) 22. Подвійний симплекс-метод. Загальний запис задачі для подвійного симплекс-методу. Подвійний симплекс метод полягає в пошуку оптимального плану двоїстої задачі шляхом переходу від одного її опорного плану до іншого. Якщо пряма задача має вигляд:
Таким чином загальний запис непрямої задачі такий:
min L(X)=max L(Y). 23. Розкрити суть компонентів векторів a і b та матриці С для транспортної задачі. Вектор а – запаси продукції у постачальників (скільки одиниць продукції виробляє кожний постачальник). Вектор в – попит на продукцію споживачів (скільки одниць спроможний купити кожний споживач). Матриця С – матриця транспортних витрат (скільки коштує перевезення продукції від відповідного постачальника до відповідного споживача). Вектори а і в використовуються для перевірки задачі на збалансованість (?аі = ?bj, i= 1,m j= 1,n), що є необхідною і достатньою умовою існування розвязку. 24. Пуасонівський потік подій та його числові характеристики. Формула. Потік подій називається пуасонівським, якщо йому притаманні такі вл-сті: -- стаціонарність; -- відсутність післядії; -- ординарність Потік подій називають стаціонарним, коли ймовірність того, що за проміжок часу ?Т відбудеться те чи інше число подій, залежить лише від довжини цього проміжку і не залежить від того, де міститься ?Т щодо початку відліку часу. Потік дій називається потоком з відсутністю післядії, якщо ця ймовірність не залежить від того, скільки подій здійснилося до початку часу ?Т. Потік дій називається ординарним, якщо ймовірність того, що за малий проміжок часу ?t відбудеться одна подія, наближено пропорційна довжині цього відрізку: Р1 (?t) = ??t + ?1(?t) а ймовірність, що відбудеться k>1 подій, є величиною нескінченно малою порівняно з ?t: PK>1(?t) = ?K(?t) P0(?t) = 1 - ??t + ?0 (?t) Для виведення осн. числових х-к Пуассонівського потоку необхідно спочатку вивести с-му однорідних нескінченних диференціальних рівнянь: P0’(t) = -?P0(t) – це перше диференціальне рівняння Проінтегрувавши його: P0(t) = e-? t Після багатьох ітерацій визначимо, яка ймовірність того, що відбудеться m подій за час t і отримаємо систему однорідних нескінченних диференціальних рівнянь: P’m(t) = - ?* Pm(t) + ?* Pm-1(t) Для розв’язування систем диференціальних рівнянь такого типу використовується метод ймовірних твірних функцій. Ймовірна твірна функція А(х, t) – це збіжний степеневий ряд такого вигляду: A(x,t) = ?xm * Pm(t) При чому A(1,t) = ?Pm(t) = 1 (утворюють повну групу) Після деяких ітерацій: A(x, t) = e? (x-1) t якщо ?*t = a, то A(x, t) = ea (x -1) Скориставшись відомими визначеннями основних числових характеристик, тобто мат.сподівання, дисперсії та середнього квадратичного відхилення, через цю ймовірну твірну функцію, визначимо: 1. M(X) = A’(1) = (ea (x -1) )’X = 1 = (a* ea (x -1) )X = 1 = a M(X) = a = n*p. 2. A’’(1) = … = a2 D(X) = A’’(1) + A’(1) – (A’(1))2 = a2 + a – a2 = a D(X) = a 3. ? (X) = va Отже для Пуассонівського потоку M(X) = D(X) = a. Вихідною інформацією для отримання формули Пуассона є система однорідних нескінченних диференціальних рівнянь: P’0(t) = - ?* P0(t) P’m(t) = - ?* Pm(t) + ?* Pm -1 (t) Для розв’язування систем диференціальних рівнянь такого типу використовується метод ймовірних твірних функцій. Ймовірна твірна функція А(х, t) – це збіжний степеневий ряд такого вигляду: A(x,t) = ?xm * Pm(t) При чому A(1,t) = ?Pm(t) = 1 (утворюють повну групу) P1(t) = A’(0, t) Pm(t) = (1/ m! )* A(m) (0, t) Pm(t) = A(m) (0, t) / m! Помножимо друге рівняння системи однорідних диференціальних рівнянь на xm , отримаємо: ?xm* P’m(t) = ?*x* ?xm* Pm(t) - ? ?xm* Pm(t) A’(x, t) = ?*x* A(x, t) – ?* A(x, t) A’(x, t) = ?*(x – 1)* A(x, t) Проінтегрувавши цей вираз: A(x, t) = e? (x – 1) t Pm(t) = ((?t)m / m!) * e-?t - формула Пуассона для найпростішого потоку подій ? – це інтенсивність потоку, а саме середнє число подій, що може відбутися за одиницю часу. Якщо позначити ?*t = a, то: Pm(t) = ( am / m!) * e-a 25. Коефіцієнт чутливості. Коефіцієнт чутливості дозволяє визначити реакцію цільової функції на незначні зміни аргумента. Для визначення коефіцієнта чутливості використовується така система
26. Метод потенціалів для транспортної задачі. Суть методу. Метод потенціалів дозволяє, виходячи з деякого опорного плану перевезень, побудувати за скінчене число ітерацій рішення транспортної задачі шляхом послідовного переходу від опорного плану до оптимального. Загальна схема методу така. У даному початковому опорному плані кожному пункту ставлять у відповідність деяке число, яке називається його попереднім потенціалом. Попередні потенціали обирають так, щоб їх різниця для будь-якої пари пунктів Аi и Вj, пов’язаних основною комунікацією, дорівнювала сij. Якщо відбудеться так, що різниця попередніх потенціалів для всіх інших комунікацій не перевищує сij, то даний план перевезень – оптимальне рішення задачі. У противному випадку вказують спосіб покращення опорного плану транспортної задачі. 27. Описати алгоритм знаходження першого опорного плану для транспортної задачі. Нехай та . Причому, аi , вj >0; В загальному випадку в – складські приміщення, а - пункт призначення. Для побудови першого опорного плану слід побудувати таблицю такого вигляду А1 А2 Аm
В1
В2
...
Вк
Далі необхідно заповнити комірки за такими правилами: 1) якщо а1>в1, то комірка Х11 заповнюється значенням в1, після чого в комірках Х1m ставиться прочерк, а залишок (а1- в1) порівнюють із значенням в2 за аналогічною схемою. Сума по першому стовпчику має дорівнювати а1. 3) якщо а1<в1, то в комірку Х11 записується значення а1, а вниз по вертикалі у комірках ставляться прочерки. Різниця (в1 –а1) розноситься по горизонтальним коміркам першого рядка, причому сума по рядку має дорівнювати в1. Аналогічні перетворення слід виконати для кожного елемента матриць а та в. Після цього отримаємо таблицю, в якій деякі комірки будуть заповнені, а деякі—ні. Отримаємо так званий перший розподіл, який і являється першим опорним планом. 28. Матриця однокрокового переходу системи із одного стану в інший. Властивості елементів. Розглянемо систему, яка може перебувати в одному із несумісних станів wi де і= 1,N. Тоді перехід системи із б-я стану в інший в момент часу t описується ймовірною матрицею одно крокового переходу, яка має такий вигляд
Для кожного рядка матриці виконується рівність , де і= 1,N так як події утворюють повну групу. 29. Однорідні ланцюги Маркова. Матриця ? та властивості її елементів. Якщо рij(t) не залежить від часу, то ланцюг Маркова називають однорідним і тоді рij(t) =рij= const. А тому для однорідних ланцюгів Маркова матриця однокрокового переходу набуває такого вигляду
Для кожного рядка матриці виконується рівність
30. Описати алгоритм методу потенціалів.] Алгоритм методу потенціалів складається з таких етапів: 1) визначення типу транспортної задачі (відкрита чи закрита). 2) побудова першого опорного плану транспортної задачі. 3) перевірка плану транспортної задачі на оптимальність. 4) якщо умова оптимальності виконується, то маємо оптимальний розв’язок транспортної задачі. Якщо ж умова оптимальності не виконується, необхідно перейти до наступного опорного плану. 5) новий план знову перевіряють на оптимальність, тобто повторюють дії п.3 і далі. Розглянемо докладно кожний етап цього алгоритму: 1) перевірка збалансованості – загальна кількість продукції постачальників повинна дорівнювати загальному попиту всіх споживачів, тобто ?аi = ?bj , то таку задачу називають збалансованою або закритою. Якщо під час перевірки виявилося, що транспортна задача є відкритою, то її необхідно звести до закритого типу шляхом введення фіктивного умовного постачальника або споживача. 2) для побудови початкового опорного плану транспортної задачі існує кілька методів: мінімальної вартості; подвійної переваги. Побудову опорного плану зручно подавати у вигляді таблиці, в якій постачальники продукції є рядками, а споживачі – стовпчиками. 3) опорний план перевіряють на оптимальність за допомогою потенціалів ui та vj відповідно постачальників та споживачів. Потенціали опорного плану визначаються із системи рівнянь ui + vj = cij , які записують для всіх заповнених клітинок транспортної таблиці. 4) за допомогою розрахованих потенціалів перевіряють умову оптимальності ui + vj <= cij для порожніх клітинок таблиці. Якщо хоча б для однієї клітинки ця умова не виконується, тобто ui + vj > cij , то поточний план є неоптимальним і від нього необхідно перейти до нового опорного плану шляхом заповнення клітинки, для якої порушено умову оптимальності, будуючи для вибраної порожньої клітинки цикл перерахування. 5) новий опорний план перевіряють на оптимальність згідно з п.3 алгоритму. 31. Окантована матриця Гессе. Окантована матриця Гессен має такий вигляд де О – нульова матриця. Порядок матриці(m*n); (’ – транспонована матриця (; Н – звичайна матриця Гессе
32. Стаціонарні ймовірності для регулярних ланцюгів Маркова. Регулярний ланцюг — це такий ланцюг, для якого за деякого значення k (кількість кроків) у матриці ( (k) не буде нульових елементів. А це означає, що перехід системи з будь-якого стану до будь-якого іншого стану здійсниться за k кроків. Для регулярних ланцюгів Маркова існують стаціонарні ймовірності Визначення стаціонарних імовірностей Нехай задано перехідну матрицю ( регулярного ланцюга Маркова. Тоді виконуються такі умови: 1)для будь-якого ймовірнісного вектора а вектор а* ( (k) прямує до вектора W за k>? 2) W — єдиний вектор, який має властивість W* ?=W 3) Перша умова означає, що незалежно від імовірнісного вектора a для регулярних ланцюгів Маркова, які моделюються певною матрицею (, виконується рівність
Вектор W називають вектором стаціонарних імовірностей. Його компоненти задовольняють умову
33. .Зв’язок між Пуасонівським потоком подій та експоненціальним законом розподілу. Для визначення зв’язку між Пуассонівським потоком та експоненціальним законом розподілу необхідно спочатку записати вигляд Пуассонівського потоку та експоненціального закону розподілу: Pk(t) = ( (?t)k / k!) * e-? t - це Пуассонівський потік подій P0(t) = e-? t 0, t <= 0 ?(t) = ?e-? t, t > 0 - це експоненціальний закон розподілу 0, t < 0 F(t) = 1 – e-? t , t >= 0 Згідно Пуассонівського потоку P1(?t) + P0(?t) = 1. Розглядаючи експоненціальний закон розподілу: P( t < T) + P(t > T) = 1 P(t > T) = P0(t) = e-? t P(t < T) = F(t) = 1 – P(t > T) = 1 – e-? t F(t) = 1 – e-? t ?(t) = ?e-? t Інтервал часу між двома випадковими подіями є випадкова величина, яка має експоненціальний закон розподілу ймовірностей. 34. Матриця Якобі. Матриця управління. Загальна постановка задачі f(x)>max(min) де х= (х1, х2 ...хn) при обмеженнях q(x)=0, де обмеження складається із m рівнянь q=(q1, q2,… qm). Якщо m<n, тоді у векторі х=(х1, х2, ...хm, xm+1, … xn) позначимо х1, х2, ...хm=y, а xm+1, … xn=z тоді x=(y,z), де у – залежні змінні, z - незалежні змінні. (f(y,z)=((yf, (zf) (q(y,z)=((yq, (zq) Матриця Якобі матиме вигляд:
Матриця вартостей має вигляд:
35. Використання регулярних ланцюгів Маркова для моделювання екологічної ситуації регіону.
в загальному випадку Рij значить що Wi переходить у Wj.
m=(m1, m2, … mN) – початковий рівень забруднення; ( - перенос часток забруднення з одного місця у друге; f=(f1, f2, … fN) – управляючий вектор;
q=(q1, q2, … qN) – цільовий вектор 36. Лінійні моделі. Цільова функція та її характеристики. Обмеження в загальному вигляді. Лінійні моделі – це система лінійних рівнянь або нерівностей. Векторно-матричний запис лінійних рівнянь, нерівностей: Ax=b, Ax(b, Ax(b, де
Для дослідження лінійних моделей на оптимальний розв’язок(min, max) використовується симплексний метод. Загальний запис задач симплексного методу:
L(x) – функція цілі задана при таких обмеженнях:
або у векторно-матричній формі:
37. Використання ланцюгів Маркова для моделювання грошової ситуації в регіоні. Розглядається деяка країна (регіон), в якій є N міст. У певний момент часу — назвемо його початковим моментом — у кожному з Wi(i=1,2, …,N) міст перебуває в обігу певна кількість грошей. Ці гроші утворюють потоки, що циркулюють між містами. Поводження зазначених потоків має контролювати уряд. Отже, потрібно визначити умову, за якої уряд досягне своєї мети, а також установити, яка кількість грошової маси має надходити до того чи іншого міста в кожний період часу. Основним припущенням у цій моделі є те, що ззовні до країни гроші не надходять, але частина їх може «зникнути» в місті протягом певного часу. Потокова модель із втручанням уряду у грошову ситуацію кожного міста Побудуємо три вектори: m=(m1, m2, … mN), де mi - кількість грошей, які в певний момент часу перебувають у місті Wi(i=1,2, …,N); f=(f1, f2, … fN) де fi - кількість грошей, що їх уряд додає місту Wi або забирає в нього (i=1,2, …,N); компоненти цього вектора можуть бути додатними, від’ємними, а також дорівнювати нулю; q=(q1, q2, … qN), де qi - , що саме має на меті уряд: через певну кількість періодів грошей у місті Wi має бути не менш ніж qi коли грошові потоки між містами стабілізуються. Нехай pij — частка грошей міста Wi яка перейде до міста Wj протягом одного періоду часу. Тоді, оскільки 0(pij(1 то значення pij можна розглядати як відповідні ймовірності зазначеного переходу. Отже, можна скористатися теорією ланцюгів Маркова, станами яких є грошові ситуації в містах регіону (країни). Якщо pij >0 то це означає, що між містами Wi та Wj існує грошовий потік, за pij=0 — такого потоку немає. Загальна картина грошових потоків між містами описується матрицею
Повинна виконуватись умова:
38. Градієнт функції f(x) та його використання. Градієнтом від функції f(x)=f(x1,x2, ...xn) буде вектор, компонентами якого є частинні похідні по кожній компоненті. Градієнт позн-ся . Послідовність дослідження функції на екстремум з використанням градієнта: f(x)>max(min), 1)q(x)=0, q(x)=(q1(x), q2(x)…qm(x)) 2) розбиваємо х на у і z 3)знаходимо матрицю Якобі і управляючу матрицю
4) знаходиться добуток J-1 *С 5) знаходиться стаціонарна точка , і значення х підставляється у рівняння 6) якщо <0, то максимум, а якщо >0, то мінімум. 39. Цільовий вектор q в потокових моделях. Описати алгоритм знаходження . - компоненти q інформують про те, що саме має на меті уряд: через певну кількість періодів грошей у місті Wi має бути не менш ніж q коли грошові потоки між містами стабілізуються (при грошовій ситуації, а в загалі планова ситуація).
R – матриця вартості, Пі – імовірнісна матриця переходів. Діагональні елементи складають вектор q. 40. Алгоритм симплекс-методу Z = С1x1 +С2x2+…+С nxn N
..
Qi
x11 x12 .. x1n b1
x21 x22 .. x2n b2
... ... .. ...
xn1 xn2 .. xnn bn
?j L -C1 -C2 .. -Cn
Коефіцієнти при L мають обернені знаки. 1. Знаходимо розрахунковий стовпчик по найменшому значенню С. 2. Знаходимо розрахунковий рядок: для цього Коефіцієнти ділимо на вільний член обраного стовпчика(берем лише додатні) і обираємо найменший з них. 3. Всі елементи розрахункового стовпчика крім розрішаю чого елемента замінюємо на нулі, а всі елементи розрахункового рядка ділимо на розрішаючий елемент. 4. Далі розв’язуємо за методом Джордана-Гаусса. Розв’язання продовжується до тих пір поки всі коефіцієнти при L не стануть додатними або рівними 0. В цьому випадку: Якщо Cij>0 > max Якщо Cij<0 > min Якщо Cij=0 > mx=min 41. Використання регулярних ланцюгів Маркова для оцінки ефективності роботи системи. Матриця вартостей. S – система, що розглядається, і також перебуває в одному з несумісних станів W1? W2, ....Wn, за певний проміжок часу може переходити в інший із станів, що описується регулюючою матрицею R – матриця вартості
Rij – означає, що при переході з і-го стану в j- - можна отримати прибуток (r>0) чи збиток (r<0), або нічого не отримати(r=0). Вводимо вектор V(k) за к кроків
що за к-кроків система опиниться в іншому стані, то отримає прибуток чи збиток, якщо спочатку Стохастична модель в загальному випадку має такий векторно-матричний вигляд Компоненти вектора q – елементи головної діагоналі . 42. Приведений градієнт функції. Загальна постановка задачі f(x)>max(min) де х= (х1, х2 ...хn) при обмеженнях q(x)=0, де обмеження складається із m рівнянь q=(q1, q2,… qm). Якщо m<n, тоді у векторі х=(х1, х2, ...хm, xm+1, … xn) позначимо х1, х2, ...хm=y, а xm+1, … xn=z тоді x=(y,z), де у – залежні змінні, z - незалежні змінні. Ўf(y,z)=( Ўyf, Ўzf) Ўq(y,z)=( Ўyq, Ўzq) Матриця Якобі матиме вигляд:
Матриця вартостей має вигляд:
Ўf(y,z)= ЎYf Dy + ЎZf Dz Ўq(y,z)= ЎYq Dy + ЎZq Dz=0 I Dy + C Dz=0 -> Dy=-I-1 C Dz Dy/Dz=-I-1 C Df(x)=Df(y,z)= ЎYf Dy + ЎZ f Dz Df(y,z)= -ЎYf I-1 C Dz + ЎZ f Dz Df(y,z)= (ЎYf - ЎYf I-1 C) Dz Df/Dz=ЎZ f=ЎYf - ЎYf I-1 C – приведений градієнт. ЎZ f > 0 – min ЎZ f <0 – max 43. Описати алгоритм знаходження першого опорного плану для транспортної задачі. Нехай та . Причому, аi , вj >0; В загальному випадку в – складські приміщення, а - пункт призначення. Для побудови першого опорного плану слід побудувати таблицю такого вигляду А1 А2 Аm
В1
В2
...
Вк
Далі необхідно заповнити комірки за такими правилами: 1) якщо а1>в1, то комірка Х11 заповнюється значенням в1, після чого в комірках Х1m ставиться прочерк, а залишок (а1- в1) порівнюють із значенням в2 за аналогічною схемою. Сума по першому стовпчику має дорівнювати а1. 3) якщо а1<в1, то в комірку Х11 записується значення а1, а вниз по вертикалі у комірках ставляться прочерки. Різниця (в1 –а1) розноситься по горизонтальним коміркам першого рядка, причому сума по рядку має дорівнювати в1. Аналогічні перетворення слід виконати для кожного елемента матриць а та в. Після цього отримаємо таблицю, в якій деякі комірки будуть заповнені, а деякі—ні. Отримаємо так званий перший розподіл, який і являється першим опорним планом. 44. Стохастична модель одноканальної системи масового обслуговування в стаціонарному режимі та її основні числові характеристики. У більшості систем обслуговування одна або декілька змінних підпорядковуються закону ймовірностей. Моделі, побудовані для таких систем обслуговування, повинні включати випадкові величини. Такі моделі називають стохастичними. Якщо середня швидкість вхідного потоку ? менша ніж середня швидкість обслуговування ?, то система обслуговування з часом ввійде в стаціонарний режим. Після довгого проміжку часу розподіл довжини черги стане стаціонарним, тобто незалежним від t. Стохастична модель для СМО з одним обслуговуючим каналом в стаціонарному режимі (не залежить від t): 0 = - ?Ро(t) + ?P1(t) 0 = - (?+?) P1(t) + ?Po(t) + ? P2(t) 0 = - (?+?) P2(t) + ?P1(t) + ? P3(t) ................................. 0 = - (?+?) Pк-1(t) + ?Pк-2(t) + ? Pк+1(t) 0 = - ?Pк(t) + ?Pк-1(t) 1= ?PK Де к – довжина черги. До основних числових характеристик СМО належать: 1)довжина черги в різні моменти часу; 2)загальна тривалість перебування вимоги в системі обслуговування. 3)час, протігом якого обслуговуючий приад був вільним. 4)коефіцієнт навантаження системи (?). 5)Середнє число вимог у черзі (L); 6)Математичне сподівання кількості вимог інформації (М). 7)Середнє значення часу очікування вимоги в черзі до початку свого обслуговування приладом (tc =M/L). 45. Стохастична модель системи масового обслуговування із k каналами. У більшості систем обслуговування одна або декілька змінних підпорядковуються закону ймовірностей. Моделі, побудовані для таких систем обслуговування, повинні включати випадкові величини. Такі моделі називають стохастичними. Стохастична модель для СМО з багатьма обслуговуючими каналами: Ро’(t) = - ?Ро(t) + ?P1(t) P1’(t) = - (?+?) P1(t) + ?Po(t) + 2? P2(t) P2’(t) = - (?+2?) P2(t) + ?P1(t) + 3? P3(t) .............................. Pк-1’(t) = - (?+m?) Pк-1(t) + ?Pк-2(t) + m? Pк+1(t) Pк’(t) = - ?Pк(t) + ?Pк-1(t) Де к – довжина черги, m – кількість каналів обслуговування. 46. Загальний запис задачі для подвійного симлекс-методу. Описати його алгоритм. Подвійний симплекс метод полягає в пошуку оптимального плану двоїстої задачі шляхом переходу від одного її опорного плану до іншого. Якщо пряма задача має вигляд:
Таким чином загальний запис непрямої задачі такий:
min L(X)=max L(Y). Якщо; то обернена задача записується так
Здійснивши ці перетворення, необхідно побудувати симплексну таблицю, яка має такий вигляд
x1 xn b Qi
X11 X1n b1
X21 X2n в2
?j L -c1 -cn
Далі знаходимо розрахунковий стовпчик по найменшому значенню С. Знаходимо розрахунковий рядок. Для цього в ділимо на коефіцієнти і беремо з них найменше. Всі решта елементів (крім розрахункового елемента) розрахункового стовпчика = 0, а елементи рядка ділимо на розрахунковий елемент. Далі використовуємо метод Дж. Гаусса Процес проходить доки елементи рядка стануть + (а коли досліджуємо на min то -) або=0. 47. Розкрити суть ординарності, відсутності післядії та стаціонарності Пуасонівського потоку. Потік подій називається Стаціонарним, якщо ймовірність появи того чи іншого числа подій на проміжку часу не залежить від того де цей відрізок часу знаходиться по відношенню до початку відліку часу. Поток з відсутністю післядії (потік без наслідків), якщо ця ймовірність того чи іншого числа подій на проміжку часу Т не залежить від того скільки подій відбулося до початку проміжку Т. Потік називається ординарним, якщо ймовірність появи однієї події за малий відрізок часу Т пропорційна довжині цього відрізку P(?t) = ? ?t + ? ?t , ? ->0. За проміжок часу ?t може відбутися або одна або жодної. 48. Алгоритм симплекс-методу. Z = С1x1 +С2x2+…+С nxn N
..
Qi
x11 x12 .. x1n b1
x21 x22 .. x2n b2
... ... .. ...
xn1 xn2 .. xnn bn
?j L -C1 -C2 .. -Cn
Коефіцієнти при L мають обернені знаки. 1. Знаходимо розрахунковий стовпчик по найменшому значенню С. 2. Знаходимо розрахунковий рядок: для цього Коефіцієнти ділимо на вільний член обраного стовпчика(берем лише додатні) і обираємо найменший з них. 3. Всі елементи розрахункового стовпчика крім розрішаю чого елемента замінюємо на нулі, а всі елементи розрахункового рядка ділимо на розрішаючий елемент. 4. Далі розв’язуємо за методом Джордана-Гаусса. Розв’язання продовжується до тих пір поки всі коефіцієнти при L не стануть додатними або рівними 0. В цьому випадку: Якщо Cij>0 > max Якщо Cij<0 > min Якщо Cij=0 > mx=min 49. Транспортна задача. Метод потенціалів. Транспортна задача – це специфічна задача лінійного програмування, застосовувана для визначення найекономнішого плану перевезення однорідної продукції від постачальників до споживачів. Нехайта . Причому, аi , вj >0; Матриця вартостей має такий вигляд В загальному випадку Cji – вартість перевозки з j пункту в і-й; в – складські приміщення, а - пункт призначення. Перший розподіл являється першим опорним планом. Метод потенціалів дозволяє, виходячи з деякого опорного плану перевезень, побудувати за скінчене число ітерацій рішення транспортної задачі шляхом послідовного переходу від опорного плану до оптимального. Загальна схема методу така. У даному початковому опорному плані кожному пункту ставлять у відповідність деяке число, яке називається його попереднім потенціалом. Попередні потенціали обирають так, щоб їх різниця для будь-якої пари пунктів Аi и Вj, пов’язаних основною комунікацією, дорівнювала сij. Якщо відбудеться так, що різниця попередніх потенціалів для всіх інших комунікацій не перевищує сij, то даний план перевезень – оптимальне рішення задачі. У противному випадку вказують спосіб покращення опорного плану транспортної задачі. 50. Рівняння „народження-загибелі.” Одним із найважливіших напрямів застосування процесів Маркова є моделювання процесу народження і загибелі, що може відбуватися як із дискретними, так і з неперервними змінами часу t. При цьому головною умовою, котра неодмінно має виконуватися, є така: переходи процесу можливі лише до сусідніх станів. При цьому припускається, що процес народження певної кількості одиниць організмів моделюється пуассонівським процесом (потоком) із параметром ?К, що є інтенсивністю народження k-го організму, а загибель — експоненціальним законом розподілу з параметром ??к де ?к — інтенсивність загибелі k-го організму. Такі припущення добре узгоджуються з реальними процесами народження і загибелі, які відбуваються в певному обмеженому просторі популяції. Для процесу народження та загибелі, як уже наголошувалося, можливі лише переходи зі стану ?к до стану ?к-1 або ?к+1. Нехай обсяг популяції дорівнює k одиницям, а отже, процес перебуває у стані ?к. Перехід процесу зі стану ?к до стану ?к+1 відповідає випадковій події — народження з певною ймовірністю однієї одиниці організму, а перехід процесу зі стану ?к до стану ?к-1 відповідатиме такій випадковій події: загибель із певною ймовірністю однієї одиниці організму. Три можливі переходи процесу розмноження та загибелі, де відсутні переходи процесу до несусідніх станів, унаочнює рис. На основі наведених щойно міркувань дістанемо таку систему рівнянь: При цьому: . Враховуючи, що , після перетворень маємо систему рівнянь: Зосередивши увагу, наприклад, на стані ?к побачимо, що перейти до цього стану можна лише зі станів ?к-1 або ?к+1 і навпаки, залишаючи стан ?к , можна потрапити лише в стан ?к-1 або ?к+1. Такі процеси називають процесами розмноження і загибелі. 51. Потокова модель, яка моделює грошову ситуацію в регіоні при наявності поглинаючих станів. Матриця Q та її властивості. 52. Метод приведенного градієнта. Метод Якобі застосовується у випадках, коли слід дослідити f(x) >min(max), де х=(х1,х2,…хn) при обмеженнях q(x)=0, де q=(q1,q2…qm). Послідовність дослідження функції на екстремум за методом Якобі: f(x)>max(min), 1)q(x)=0, q(x)=(q1(x), q2(x)…qm(x)) 2) розбиваємо х на у і z 3)знаходимо матрицю Якобі і управляючу матрицю
4) знаходиться добуток J-1 *С 5) знаходиться стаціонарна точка
і значення х підставляється у рівняння 6) якщо <0, то максимум, а якщо >0, то мінімум. 53. Суть елементів матриці матриці ? потокової моделі, що описує грошову ситуацію в регіоні. Розглянемо систему, яка може перебувати в одному із несумісних станів wi де і= 1,N. Тоді перехід системи із б-я стану в інший в момент часу t описується ймовірною матрицею одно крокового переходу, яка має такий вигляд
Для кожного рядка матриці виконується рівність , де і= 1,N так як події утворюють повну групу. Суть елементів Pij - перехід фінансових коштів із точки і в j. 54. Окантована матриця Гессе та її використання для аналізу стаціонарної точки. Окантована матриця Гессе складається з 4 блоків і має такий вигляд: , де 0 – нульова матриця; - матриця
; H – звичайна матриця Гессе ; - транспонована матриця . Аналіз стаціонарної точки полягає в тому, що її координати Х=(х1, х2, ...,хn,) підставляються в окантовану матрицю Гессен, якщо головні мінори будуть від’ємні або чередуватись то в цій точці буде max. 55. Суть елементів матриці матриці П потокової моделі, що описує екологічну ситуацію в регіоні. Функція управління вектора f. Регіон складається з N міст з різним рівнем забруднення, рівень забруднення яких змінюються. Зміни в екологічній ситуації регіону описуються ланцюгом Маркова. Матриця ( - характеризує змікну забруднення.
Суть рij в загальному випадку означає перенос часток забруднення з одного місця в інше у відносних числах. Відомій вектор m який визначає початковий стан екологічної ситуації в регіоні. mі – рівень забруднення в і-му місці регіону. Вводимо управляючий вектор f – заходи регулювання забруднення. Вектор q означає допустимий рівень забруднення. 56. Цільова функція для транспортної задачі та умови яким повинні задовольняти елементи xij. Цільова функція (відображає сукупні витрати для певного плану перевезень): m n L=? ? cij*хij(min i=1 j=1 Цільова функція мінімальна при оптимальному опорному плані. Зміст транспортної задачі полягає в знаходженні множини змінних Хij(0, i= 1,m j= 1,n, що задовольняють умовам: n ? Xij =ai (i= 1,m) j=1 m ? Xij =bj (j= 1,n) i=1 і таких, при яких цільова функція досягає мінімуму. 57. =51. Потокова модель, яка моделює грошову ситуацію в регіоні при наявності поглинаючих станів. 58. Описати алгоритм подвійного симплекс-методу. Якщо; то обернена задача записується так
Здійснивши ці перетворення, необхідно побудувати симплексну таблицю, яка має такий вигляд
x1 xn b Qi
X11 X1n b1
X21 X2n в2
?j L -c1 -cn
Далі знаходимо розрахунковий стовпчик по найменшому значенню С. Знаходимо розрахунковий рядок. Для цього в ділимо на коефіцієнти і беремо з них найменше. Всі решта елементів (крім розрахункового елемента) розрахункового стовпчика = 0, а елементи рядка ділимо на розрахунковий елемент. Далі використовуємо метод Дж. Гаусса Процес проходить доки елементи рядка стануть + (а коли досліджуємо на min то -) або=0. 59. Вектори m, f, q потокової моделі, суть їх компонентів. Розглянемо ці вектори на прикладі моделі, що описує грошову ситуацію в регіоні. Вектор-рядок компоненти інформують про кількість грошей, які в певний момент часу перебувають у місті ; Вектор-рядок компоненти якого інформують про кількість грошей, що їх уряд додає місту або забирає в нього ; за побудовою компоненти цього вектора можуть бути додатними, від’ємними, а також дорівнювати нулю, коли уряд не втручається у грошову ситуацію міста; Вектор-рядок компоненти якого інформують про те, що саме має на меті уряд: через певну кількість періодів грошей у місті має бути не менш ніж коли грошові потоки між містами стабілізуються. 60. Описати алгоритм знаходження першого опорного плану для транспортної задачі. Нехай та . Причому, аi , вj >0; В загальному випадку в – складські приміщення, а - пункт призначення. Для побудови першого опорного плану слід побудувати таблицю такого вигляду А1 А2 Аm
В1
В2
...
Вк
Далі необхідно заповнити комірки за такими правилами: 1) якщо а1>в1, то комірка Х11 заповнюється значенням в1, після чого в комірках Х1m ставиться прочерк, а залишок (а1- в1) порівнюють із значенням в2 за аналогічною схемою. Сума по першому стовпчику має дорівнювати а1. 3) якщо а1<в1, то в комірку Х11 записується значення а1, а вниз по вертикалі у комірках ставляться прочерки. Різниця (в1 –а1) розноситься по горизонтальним коміркам першого рядка, причому сума по рядку має дорівнювати в1. Аналогічні перетворення слід виконати для кожного елемента матриць а та в. Після цього отримаємо таблицю, в якій деякі комірки будуть заповнені, а деякі—ні. Отримаємо так званий перший розподіл, який і являється першим опорним планом. 61. Марківські процеси. Ланцюги Маркова. Матриця П та її властивості. Марківський ланцюговий процес – це певна система S , яка може змінювати свої стани у випадкові моменти часу. Випадковий процес Х(t) називають марковським, якщо за будь-якого можливого значення часу t=t1 значення випадкової величини x(t1) не залежить від того, яких значень ця величина набувала для t<t1, тобто, процес у момент часу t=t1 не залежить від його поведінки в більш ранні моменти часу t <t1. Нехай Х(t) — однорідний марковський процес із обмеженим, або зліченним, числом можливих станів i = 0, 1,2, 3,..., п,... Якщо аргумент і набуває лише значення 0, 1, 2, 3, ..., то в цьому разі матимемо послідовність переходів х(0) —> х(1) ->х(2)->х(3)->..... Такий процес послідовностей переходів називають ланцюгом Маркова. При розробленні теорії ланцюгів Маркова дотримуються ще такої термінології: розглядається певна фізична система S, яка в кожний момент часу може перебувати в одному з несумісних станів а1, а2, Аз, ..., Аk, ... і змінювати свій стан лише в моменти часу t1, t2, t3, ..., tk, — Процес переходу систем S утворює ланцюг Маркова, якщо ймовірність перейти в стан Аj в момент часу t (tk< t < tk+1) залежить лише від того, в якому стані система перебувала в момент часу t’(tk-1<t’< tk), і не залежить від стану системи в більш ранішні моменти часу. Імовірності переходу зі стану А, в стан аj в момент часу t позначають через Pij(t). Повна ймовірна картина всіх можливих переходів систем із одного стану в інший за умови, що число всіх станів дорівнює N, безпосередньо описується матрицею ймовірностей переходу
Якщо рij(t) не залежить від часу, то ланцюг Маркова називають однорідним і тоді рij{t) =рij= const. А тому для однорідних ланцюгів Маркова матриця ймовірностей переходу набуває такого вигляду
Для кожного рядка матриць (584), (585) виконується рівність
Це свідчить про те, що, перебуваючи в будь-якому можливому стані Ai, у фіксований момент часу t, система обов'язково перейде з певною ймовірністю в будь-який інший можливий стан Аj або залишиться в цьому самому стані. А ці події є несумісними й утворюють повну групу. 62. Описати алгоритм графічного розв’язку для знаходження максимуму(мінімуму) функції. L(x) = ?CiXi = C1X1 + C2X2 ?ai xi ? bi n = (C1 , C2) 1) знайти розв’язки системи нерівностей
2) Побудувати прямі 3) підставити координати точок в рівняння і знайти максимум і мінімум. 64. Система масового обслуговування та її складові частини. Причини виникнення черг. Поняття про пріоритетність у обслуговуванні вимог. В загальному випадку моделі теорії масового обслуговування досл. такі системи які скл. з трьох частин: 1) потік вимог; 2) черга(потоки вимог які надходять в систему утворюють „чергу”); 3) канал обслуговування. Припускається що потік вимог є Пуасонівським, тому вони (потоки вимог) поступають в систему випадково в будь-який момент часу. Якщо в системі є 1 канал обслуговування – то він називається одноканальним, якщо більше 1 – то багатоканальним. Якщо в систему надходить декілька потоків вимог, то з’являється „черга”, і між потоками встановлюється пріоритетність. За приорітетністю вимоги поділяють: 1) простий; 2) відносний пріоритет; 3) абсолютний пріоритет. 67. Метод Якобі. Метод Якобі застосовується у випадках, коли слід дослідити f(x) >min(max), де х=(х1,х2,…хn) при обмеженнях q(x)=0, де q=(q1,q2…qm). Послідовність дослідження функції на екстремум за методом Якобі: f(x)>max(min), 1)q(x)=0, q(x)=(q1(x), q2(x)…qm(x)) 2) розбиваємо х на у і z 3)знаходимо матрицю Якобі і управляючу матрицю
4) знаходиться добуток J-1 *С 5) знаходиться стаціонарна точка
і значення х підставляється у рівняння 6) якщо <0, то максимум, а якщо >0, то мінімум. 63. Експоненціальний закон розподілу та його числові характеристики. Зв’язок між Пуасонівським потоком подій та експоненціальним законом розподілу. Експоненціальним законом розподілу називається гамма-розподіл, в якого параметр Отже, маємо
Основні числові характеристики цього закону такі: . Для визначення зв’язку між Пуассонівським потоком та експоненціальним законом розподілу необхідно спочатку записати вигляд Пуассонівського потоку та експоненціального закону розподілу: Pk(t) = ( (?t)k / k!) * e-? t - це Пуассонівський потік подій P0(t) = e-? t 0, t <= 0 ?(t) = ?e-? t, t > 0 - це експоненціальний закон розподілу 0, t < 0 F(t) = 1 – e-? t , t >= 0 Згідно Пуассонівського потоку P1(?t) + P0(?t) = 1. Розглядаючи експоненціальний закон розподілу: P( t < T) + P(t > T) = 1 P(t > T) = P0(t) = e-? t P(t < T) = F(t) = 1 – P(t > T) = 1 – e-? t F(t) = 1 – e-? t ?(t) = ?e-? t Інтервал часу між двома випадковими подіями є випадкова величина, яка має експоненціальний закон розподілу ймовірностей. 65. Стохастична модель одноканальної системи масового обслуговування з ненадійним приладом. Основні числові характеристики системи В одноканальну систему обслуговування надходить пуассонівський потік вимог із інтенсивністю (, час обслуговування яких є випадковою величиною, що має експоненціальний закон розподілу з параметром (. Канал (прилад) обслуговування з деяких причин виходить із ладу. При цьому поломка каналу як подія відбувається у випадкові моменти часу, утворюючи пуассонівський потік із параметром (0. Час, що витрачається на відновлення каналу до роботоздатного стану, розглядається як випадкова величина, що має експоненціальний закон розподілу із параметром (0. Позначимо pk(t) імовірність того, що в момент часу t в системі перебуває k вимог і канал перебуває в роботоздатному стані; Rk(t)— імовірність того, що в системі перебуває k вимог і канал перебуває у стані ремонту. При цьому, у стані ремонту каналу, до системи продовжують надходити нові вимоги. Імовірнісна модель має такий вигляд:
В результаты перетворень , маємо: - імовірність того, що система перебуває у роботоздатному стані: А1(1)= ? - імовірність того, що система перебуває у стані ремонту: А2(1)= КГ ?0 , де КГ = 1/(1+ ?0) Умова нормування: , Для визначення математичного сподівання кількості вимог, що перебувають у системі, необхідно знайти :
Отже, одержали:. Тут ; ; . 66. Знаходження оптимального плану методом потенціалів. Транспортна задача – це специфічна задача лінійного програмування, застосовувана для визначення найекономнішого плану перевезення однорідної продукції від постачальників до споживачів. Нехайта . Причому, аi , вj >0; Матриця вартостей має такий вигляд В загальному випадку Cji – вартість перевозки з j пункту в і-й; в – складські приміщення, а - пункт призначення. Перший розподіл являється першим опорним планом. Метод потенціалів дозволяє, виходячи з деякого опорного плану перевезень, побудувати за скінчене число ітерацій рішення транспортної задачі шляхом послідовного переходу від опорного плану до оптимального. Загальна схема методу така. У даному початковому опорному плані кожному пункту ставлять у відповідність деяке число, яке називається його попереднім потенціалом. Попередні потенціали обирають так, щоб їх різниця для будь-якої пари пунктів Аi и Вj, пов’язаних основною комунікацією, дорівнювала сij. Якщо відбудеться так, що різниця попередніх потенціалів для всіх інших комунікацій не перевищує сij, то даний план перевезень – оптимальне рішення задачі. У противному випадку вказують спосіб покращення опорного плану транспортної задачі. 68. Алгоритм подвійного симплекс методу. Якщо; то обернена задача записується так
Здійснивши ці перетворення, необхідно побудувати симплексну таблицю, яка має такий вигляд
x1 xn b Qi
X11 X1n b1
X21 X2n в2
?j L -c1 -cn
Далі знаходимо розрахунковий стовпчик по найменшому значенню С. Знаходимо розрахунковий рядок. Для цього в ділимо на коефіцієнти і беремо з них найменше. Всі решта елементів (крім розрахункового елемента) розрахункового стовпчика = 0, а елементи рядка ділимо на розрахунковий елемент. Далі використовуємо метод Дж. Гаусса Процес проходить доки елементи рядка стануть + (а коли досліджуємо на min то -) або=0. 69. Транспортна задача. Алгоритм першого опорного плану. Транспортна задача – це специфічна задача лінійного програмування, застосовувана для визначення найекономнішого плану перевезення однорідної продукції від постачальників до споживачів. Нехайта . Причому, аi , вj >0; Матриця вартостей має такий вигляд В загальному випадку Cji – вартість перевозки з j пункту в і-й; в – складські приміщення, а - пункт призначення. Перший розподіл являється першим опорним планом. Для цього будується транспортна таблиця. А1 А2 Аm
В1 Х11 Х12 Х1m
В2 Х21 Х22 Х2m
...
Вк Xk1 Xk2 Xkm
70. Рівняння „народження-загибелі” та його використання в задачах системи масового обслуговування Одним із найважливіших напрямів застосування процесів Маркова є моделювання процесу народження і загибелі, що може відбуватися як із дискретними, так і з неперервними змінами часу t. При цьому головною умовою, котра неодмінно має виконуватися, є така: переходи процесу можливі лише до сусідніх станів. При цьому припускається, що процес народження певної кількості одиниць організмів моделюється пуассонівським процесом (потоком) із параметром ?К, що є інтенсивністю народження k-го організму, а загибель — експоненціальним законом розподілу з параметром ??к де ?к — інтенсивність загибелі k-го організму. Такі припущення добре узгоджуються з реальними процесами народження і загибелі, які відбуваються в певному обмеженому просторі популяції. Для процесу народження та загибелі, як уже наголошувалося, можливі лише переходи зі стану ?к до стану ?к-1 або ?к+1. Нехай обсяг популяції дорівнює k одиницям, а отже, процес перебуває у стані ?к. Перехід процесу зі стану ?к до стану ?к+1 відповідає випадковій події — народження з певною ймовірністю однієї одиниці організму, а перехід процесу зі стану ?к до стану ?к-1 відповідатиме такій випадковій події: загибель із певною ймовірністю однієї одиниці організму. Три можливі переходи процесу розмноження та загибелі, де відсутні переходи процесу до несусідніх станів, унаочнює рис. На основі наведених щойно міркувань дістанемо таку систему рівнянь: При цьому: . Враховуючи, що , після перетворень маємо систему рівнянь: Зосередивши увагу, наприклад, на стані ?к побачимо, що перейти до цього стану можна лише зі станів ?к-1 або ?к+1 і навпаки, залишаючи стан ?к , можна потрапити лише в стан ?к-1 або ?к+1. Такі процеси називають процесами розмноження і загибелі. 71. Алгоритм симплекс-методу. Z = С1x1 +С2x2+…+С nxn N
..
Qi
x11 x12 .. x1n b1
x21 x22 .. x2n b2
... ... .. ...
xn1 xn2 .. xnn bn
?j L -C1 -C2 .. -Cn
Коефіцієнти при L мають обернені знаки. 1. Знаходимо розрахунковий стовпчик по найменшому значенню С. 2. Знаходимо розрахунковий рядок: для цього Коефіцієнти ділимо на вільний член обраного стовпчика(берем лише додатні) і обираємо найменший з них. 3. Всі елементи розрахункового стовпчика крім розрішаю чого елемента замінюємо на нулі, а всі елементи розрахункового рядка ділимо на розрішаючий елемент. 4. Далі розв’язуємо за методом Джордана-Гаусса. Розв’язання продовжується до тих пір поки всі коефіцієнти при L не стануть додатними або рівними 0. В цьому випадку: Якщо Cij>0 > max Якщо Cij<0 > min Якщо Cij=0 > mx=min 72. Описати суть компонентів m, f та елементів матриці П, які використовуються в потоковій моделі, що описує екологічну ситуацію. Регіон складається з N міст з різним рівнем забруднення, рівень забруднення яких змінюються. Зміни в екологічній ситуації регіону описуються ланцюгом Маркова. Матриця ( - характеризує змікну забруднення.
Суть рij в загальному випадку означає перенос часток забруднення з одного місця в інше у відносних числах. Відомій вектор m який визначає початковий стан екологічної ситуації в регіоні. mі – рівень забруднення в і-му місці регіону. Вводимо управляючий вектор f – заходи регулювання забруднення. Вектор q означає допустимий рівень забруднення. 73. Матриця Гессе Матриця Гессе має місце, коли задана функція f(Х), де Х=(х1, х2, … , хN ) і позначається Н. В загальному випадку матриця Гессе має вигляд: Елементи матриці будуть симетричними відносно головної діагоналі. 74. Пуасонівський потік подій та експоненціальний закон розподілу Для пуассонівського потоку ймовірність появи випадкової події k раз протягом проміжку часу t обчислюється за формулою: де — інтенсивність потоку. Визначимо основні числові характеристики цього розподілу. Математичне сподівання
звідки Дисперсія Для визначення дисперсії знаходимо: або Тоді 75. Окантована матриця, її структура та використання для аналізу стаціонарних точок. Окантована матриця Гессе складається з 4 блоків і має такий вигляд: , де 0 – нульова матриця; ? - матриця ; H – звичайна матриця Гессе ; ?’ - транспонована матриця ?. Аналіз стаціонарної точки полягає в тому, що її координати Х=(х1, х2, ...,хn,) підставляються в окантовану матрицю Гессен, якщо головні мінори будуть від’ємні або чередуватись то в цій точці буде max, інакше min. 76. Метод потенціалів для транспортної задачі. Суть методу. Метод потенціалів дозволяє, виходячи з деякого опорного плану перевезень, побудувати за скінчене число ітерацій рішення транспортної задачі шляхом послідовного переходу від опорного плану до оптимального. Загальна схема методу така. У даному початковому опорному плані кожному пункту ставлять у відповідність деяке число, яке називається його попереднім потенціалом. Попередні потенціали обирають так, щоб їх різниця для будь-якої пари пунктів Аi и Вj, пов’язаних основною комунікацією, дорівнювала сij. Якщо відбудеться так, що різниця попередніх потенціалів для всіх інших комунікацій не перевищує сij, то даний план перевезень – оптимальне рішення задачі. У противному випадку вказують спосіб покращення опорного плану транспортної задачі. 80. Графічний метод.
Точка в якій входить вектор – буде min. 77. Стохастична модель одноканальної системи масового обслуговування. Стаціонарна ймовірність для цієї системи. Розглядається система обслуговування з пуассонівським потоком вимог, що надходять до системи, і експоненціальний закон розподілу часу обслуговування цих вимог. При цьому система має один обслуговуючий прилад. Дисципліна черги не регламентована, але кількість вимог у системі, розміщуваних у спеціальному блоці, де вони очікують своєї черги на обслуговування, має не перевищувати числа N. Отже, максимальна довжина черги становитиме N – 1. Це свідчить, що за наявності в системі N вимог жодна із додаткових заявок не буде прийнята в блок очікування. Джерело заявок при цьому необмежене. Імовірнісна модель процесу, що відбувається в цій систе-мі, подається системою диференціально-різницевих рівнянь для 0 ? k ? N: Система описує роботу системи в динаміці. Розв’язуючи практичні задачі цікавляться, як правило, числовими характеристиками системи у стаціонарному режимі. Тому для стаціонарного процесу, який здійсниться теоретично за t>? система набирає такого вигляду: З огляду на те, що запишемо систему в такому вигляді: Отже, дістали однорідну систему лінійних рівнянь відносно розв’язуючи яку відносно p0, визначаємо:
Згідно з умовою нормування маємо: (оскільки ). 78. Градієнтний метод. Метод Якобі застосовується у випадках, коли слід дослідити f(x) >min(max), де х=(х1,х2,…хn) при обмеженнях q(x)=0, де q=(q1,q2…qm). Послідовність дослідження функції на екстремум за методом Якобі: f(x)>max(min), 1)q(x)=0, q(x)=(q1(x), q2(x)…qm(x)) 2) розбиваємо х на у і z 3)знаходимо матрицю Якобі і управляючу матрицю
4) знаходиться добуток J-1 *С 5) знаходиться стаціонарна точка
і значення х підставляється у рівняння 6) якщо <0, то максимум, а якщо >0, то мінімум. 79.Коефіцієнт чутливості. Коефіцієнт чутливості дозволяє визначити реакцію цільової функції на незначні зміни аргумента. Для визначення коефіцієнта чутливості використовується така система
81. Поняття градієнта та матриці Гессе. Градієнтом від функції f(x)=f(x1,x2, ...xn) буде вектор, компонентами якого є частинні похідні по кожній компоненті. Градієнт позн-ся Ўf(x) = . Матриця Гессе має місце, коли задана функція f(Х), де Х=(х1, х2, … , хN ) і позначається Н. В загальному випадку матриця Гессе має вигляд: Елементи матриці будуть симетричними відносно головної діагоналі. 82. Метод Джордана-Гаусса. Метод Джордана-Гауса застосовується для розв’язування системи лінійних рівнянь. В загальному випадку метод має вигляд: Дана СЛР: далі будуємо матрицю вигляду: після цього ділим перший стовпець на а11:
прицьому всі наступні елементи матриці знаходимо за формулою:
В результаті перетворень отримуємо матрицю вигляду: Звідси 1. Екстремум функції f(x) в точці X=(x1, x2, …xn). Поняття про строгий та не строгий максимум(мінімум) функції. 2. Стохастична одноканальна модель теорії масового обслуговування з надійним приладом. 3. Поняття про задачі на екстремум. Екстремальна точка. Абсолютний та відносний максимум(мінімум) функції. 4. Транспортна задача та її загальний запис. Перший опорний план. 5. Градієнт функції f(x) та його використання для дослідження на екстремум функції. 6. Описати алгоритм знаходження першого опорного плану. 7. Стаціонарна точка. Матриця Гессе та її використання для дослідження функції f(x) на екстремум. 8. Цільова функція для транспортної задачі та умови яким мають задовольняти змінні х та q. 9. Метод приведенного градієнта (Метод Якобі). 10. Описати алгоритм подвійного симплекс-методу. 11. Використання теореми Тейлора для визначення максимуму(мінімуму) функції F(x). 12. Графічний метод розв’язання задач на екстремум для лінійних моделей. 13. Лінійні моделі. Цільова функція та обмеження в загальному вигляді. 14. Класифікація ланцюгів Маркова: регулярні, поглинаючі, та циклічні. Дати визначення та навести приклади. 15. Необхідні та достатні умови існування екстремуму функції. 16. Пуасонівський потік подій та його властивості. Вивести формулу для обчислення ймовірності Рm(t). 17. Функція Лагранжа, Множники Лагранжа. 18. Області допустимих розв’язків для графічного методу та їх класифікація. 19. Аналіз чутливості за допомогою методу Якобі. 20. Описати алгоритм симплекс-методу. 21. Метод множників Лагранжа. 22. Подвійний симплекс-метод. Загальний запис задачі для подвійного симплекс-методу.
23. Розкрити суть компонентів векторів а і b та матриці С для транспортної задачі. 24. Пуасонівський потік подій та його числові характеристики. Формула. 25. Коефіцієнт чутливості. 26. Метод потенціалів для транспортної задачі. Суть методу. 27. Описати алгоритм знаходження першого опорного плану для транспортної задачі. 28. Матриця однокрокового переходу системи із одного стану в інший. Властивості елементів. 29. Однорідні ланцюги Маркова. Матриця П та властивості її елементів. 30. Описати алгоритм методу потенціалів. 31. Окантована матриця Гессе. 32. Стаціонарні ймовірності для регулярних ланцюгів Маркова. 33.Зв’язок між Пуасонівським потоком подій та експоненціальним законом розподілу. 34. Матриця Якобі. Матриця управління. 35. Використання регулярних ланцюгів Маркова для моделювання екологічної ситуації регіону. 36. Лінійні моделі. Цільова функція та її характеристики. Обмеження в загальному вигляді. 37. Використання ланцюгів Маркова для моделювання грошової ситуації в регіоні. 38. Градієнт функції f(x) та його використання. 39. Цільовий вектор q в потокових моделях. Описати алгоритм знаходж q. 40. Алгоритм симплекс-методу. 41. Використання регулярних ланцюгів Маркова для оцінки ефективності роботи системи. Матриця вартостей. 42. Приведений градієнт функції. 43. Описати алгоритм знаходження першого опорного плану для транспортної задачі. 44. Стохастична модель одноканальної системи масового обслуговування в стаціонарному режимі та її основні числові характеристики. 45. Стохастична модель одноканальної системи масового обслуговування із k каналами. 46. Загальний запис задачі для подвійного симлекс-методу. Описати його алгоритм. 47. Розкрити суть ординарності, відсутності післядії та стаціонарності Пуасонівського потоку. 48. Алгоритм симплекс-методу. 49. Транспортна задача. Метод потенціалів. 50. Рівняння „народження-загибелі.” 51. Потокова модель, яка моделює грошову ситуацію в регіоні при наявності поглинаючих станів. Матриця Q та її властивості. 52. Метод приведенного градієнта. 53. Суть елементів матриці матриці П потокової моделі, що описує грошову ситуацію в регіоні. 54. Окантована матриця Гессе та її використання для аналізу стаціонарної точки. 55. Суть елементів матриці матриці П потокової моделі, що описує екологічну ситуацію в регіоні. Функція управління вектора f. 56. Цільова функція для транспортної задачі та умови яким повинні задовольняти елементи xij. 57. Потокова модель, яка моделює грошову ситуацію в регіоні при наявності поглинаючих станів. 58. Описати алгоритм подвійного симплекс-методу. 59. Вектори m, f, q потокової моделі, суть їх компонентів. 60. Описати алгоритм знаходження першого опорного плану для транспортної задачі. 61. Марківські процеси. Ланцюги Маркова. Матриця П та її властивості. 62. Описати алгоритм графічного розв’язку для знаходження максимуму(мінімуму) функції. 63. Експоненціальний закон розподілу та його числові характеристики. Зв’язок між Пуасонівським потоком подій та експоненціальним законом розподілу. 64. Система масового обслуговування та її складові частини. Причини виникнення черг. Поняття про пріоритетність у обслуговуванні вимог. 65. Стохастична модель одноканальної системи масового обслуговування з ненадійним приладом. Основні числові характеристики системи. 66. Знаходження оптимального плану методом потенціалів. 67. Метод Якобі. 68. Алгоритм подвійного симплекс методу. 69.Транспортна задача. Алгоритм першого опорного плану. 70. Рівняння „народження-загибелі” та його використання в задачах системи масового обслуговування. 71. Алгоритм симплекс-методу. 72. Описати суть компонентів m, f та елементів матриці П, які використовуються в потоковій моделі, що описує екологічну ситуацію. 73. Матриця Гессе. 74. Пуасонівський потік подій та експоненціальний закон розподілу. 75. Окантована матриця, її структура та використання для аналізу стаціонарних точок. 76. Метод потенціалів для транспортної задачі. Суть методу. 77. Стохастична модель одноканальної системи масового обслуговування. Стаціонарна ймовірність для цієї системи. 78. Градієнтний метод. 79. Коефіцієнт чутливості. 80. Графічний метод. 81. Поняття градієнта та матриці Гессе. 82. Метод Джордана-Гаусса.
