560. Регулярні однорідні ланцюги Маркова та їх числові характеристики. Фундаментальна матриця для цих ланцюгів.

Регулярні ланцюги Маркова є частинним випадком ергодичних ланцюгів.

Регулярний ланцюг — це такий ланцюг, для якого за деякого значення k (кількість кроків) у матриці не буде нульових елементів. А це означає, що перехід системи з будь-якого стану до будь-якого іншого стану здійсниться за k кроків.

1. Визначення стаціонарних (фінальних) імовірностей

Нехай задано перехідну матрицю  регулярного ланцюга Маркова. Тоді виконуються такі умови:

1) для будь-якого ймовірнісного вектора вектор прямує до вектора за

2) — єдиний вектор, який має властивість

3)

Перша умова означає, що незалежно від імовірнісного вектора (це може бути початковий вектор станів системи) для регулярних ланцюгів Маркова, які моделюються певною матрицею , виконується рівність

Вектор називають вектором стаціонарних (фінальних) імовірностей. Його компоненти задовольняють умову

2. Знаходження фундаментальної матриці

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

Нехай  — однокрокова матриця ймовірностей переходу системи з одного стану до іншого, а W — її гранична матриця.

Розглянемо матрицю і, урахувавши, що для граничної матриці W виконується рівність дістанемо

Оскільки то (нульова матриця). Зі сказаного випливає, що матриця має обернену, адже

Таким чином, доведено, що коли  є однокроковою матрицею ймовірностей переходу для регулярного ланцюга Маркова, то матриця

є фундаментальною для цього ланцюга.

Зміст:

Аналіз коефіцієнтів цільової функції задач лінійного програмування. 516

Аналіз обмежень дефіцитних і недефіцитних ресурсів.515

Аналіз розв'язків лінійних економіко-математичних моделей. Оцінка рентабельності продукції. Доцільність введення нової продукції. 514

Білий шум. 553

Визначення випадкового процесу. Поняття перерізу, закону розподілу ймовірностей випадкового процесу. 546

Визначення ланцюга Маркова. Матриця однокрокового переходу. Однорідні ланцюги Маркова та їх класифікація.558

Визначення стаціонарного випадкового процесу, щільність ймовірностей для одного, k періодів. 550

Відкриті транспортні задачі. Метод розв'язування. 521

Властивості розв'язків задачі лінійного програмування. Геометрична інтерпретація задач лінійного програмування. 503

Геометрична інтерпретація задачі цілочислового програмування. 523

Гра в чистих стратегіях. Поняття сідлової точки і її знаходження. 543

Гра2x2 взмішаних стратегіях. Алгоритм розв'язування задачі. 544

Градієнтні методи розв'язання задач нелінійного програмування та їх класифікація. 533

Графічний метод розв'язування задач нелінійного програмування. 536

Двоїста задача до транспортної задачі. Метод потенціалів.519

Двоїста задача. Правила побудови двоїстої задачі. Симетричні й несиметричні двоїсті задачі. 509

Економічний зміст двоїстої задачі й двоїстих оцінок. 510

Ергодичні властивості стаціонарного випадкового процесу та його математична трактовка. 552

Загальна постановка задачі лінійного програмування. Приклади економічних задач лінійного програмування.501

Застосування теорем двоїстості в розв’язуванні задач лінійного програмування. 512

Зведення гри двох осіб до задачі лінійного програмування.545

3ведення розв'язання . одноетапної статичної задачі стохастичного програмування до детермінованої задачі лінійного програмування. 540

Знах-ня опт. роз-ку задачі лін. прогр. Алгоритм симпл. методу. 507

Імовірні твірні функції. 557

Квадратична функція та її властивості. 530

Кореляційна функція випадкового процесу та її властивості. Нормована кореляційна функція. 548

Кореляційна функція, нормована кореляційна функція та їх властивості. 551

Математична модель задачі опуклого програмування з сепарабельною цільовою функцією. 531

Математична постановка задачі динамічного програмування, її економічний зміст. Принцип оптимальності Беллмана. 536

Математична постановка задачі стохастичного програмування і область їх застосування в управлінні виробничими системами. 539

Метод Гоморі повністю цілочислових задач. Знаходження цілої й дробової частини числа. Алгоритм розв'язування задачі. 524

Метод множників Лагранжа. Теорема Лагранжа. Алгоритм розв'язування задачі на безумовний екстремум.527

Метод Франка-Вульфа. Алгоритм розв'язування задачі нелінійного програмування. 534

Методи побудови опорних планів транспортної задачі. Випадок виродженості. Теорема про розв'язування транспортної задачі. 518

Методи розв'язування двоїстої задачі лінійного програмування.513

Методи розв'язування задач динамічного програмування. Основні кроки алгоритму розв'язування задачі динамічного програмування. 538

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

Означення планів задачі лінійного програмування (допустимий, опорний, оптимальний). 504

Основні поняття теорії ігор. Гра двох гравців з нульовою сумою, правила гри, ціна гри, пара оптимальних стратегій для двох осіб. 541

Основні рекурентні співвідношення розв'язування задач динамічного програмування. 537

Основні числові характеристики випадкового процесу та їх властивості. 547

Платіжна матриця. Основна теорема теорії ігор. Принцип мінімаксу. 542

Побудова опорного плану задачі лінійного програмування, перехід до іншого опорного плану. 505

Поглинаючі однорідні ланцюги Маркова та їх числові характеристики. Фундаментальна матриця. 559

Поняття про оператор перетворення випадкового процесу. Лінійні однорідні перетворення. Нелінійні перетворення. 549

Поняття про опуклі функції. Геометрична інтерпретація задачі опуклого програмування на площині. 528

Постановка задачі квадратичного програмування та її математична модель. 532

Постановка задачі нелінійного програмування, математична модель. Геометрична інтерпретація. 525

Пуассонівський процес та його математична модель. 556

Регулярні однорідні ланцюги Маркова та їх числові характеристики. Фундаментальна матриця для цих ланцюгів. 560

Розв'язування транспортної задачі методом потенціалів.520

Сепарабельна функція та її властивості. Розв'язування задач нелінійного програмування методом кусково-лінійної апроксимації. 535

Симплексний метод із штучним базисом. Ознака оптимальності плану із штучним базисом. 508

Сідлова точка та необхідні і достатні умови її існування. Теорема Куна-Таккера. 529

Стаціонарний випадковий процес із експоненціальною кореляційною функцією. 555

Стаціонарний випадковий процес із лінійною кореляційною функцією. 554

Теорема про оптимальність розв'язку задачі лінійного програмування симплекс-методом. 506

Теореми двоїстості, їх економічна інтерпретація. 511

Транспортна задача лінійного програмування. Економічна і математична постановка транспортної задачі. 517

Цілочислове програмування. Область застосування цілочислових задач в плануванні й управлінні виробництвом. 522