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
- 501. Загальна постановка задачі лінійного програмування. Приклади економічних задач лінійного програмування.
- 502. Модель задачі лінійного програмування в розгорнутому і скороченому вигляді, а також в матричній і векторній формах.
- 503. Властивості розв'язків задачі лінійного програмування. Геометрична інтерпретація задач лінійного програмування.
- 504. Означення планів задачі лінійного програмування (допустимий, опорний, оптимальний).
- 505. Побудова опорного плану задачі лінійного програмування, перехід до іншого опорного плану.
- Такому плану відповідає розклад
- 506. Теорема про оптимальність розв'язку задачі лінійного програмування симплекс-методом.
- Якщо розглядається задача на відшукання мінімального значення цільової функції, то формулюється така теорема.
- 507. Знаходження оптимального розв'язку задачі лінійного програмування. Алгоритм симплексного методу.
- 508. Симплексний метод із штучним базисом. Ознака оптимальності плану із штучним базисом.
- Взаємозв’язок між розв’язками початкової та розширеної задач лінійного програмування не є очевидним і визначається такою теоремою.
- 509. Двоїста задача. Правила побудови двоїстої задачі. Симетричні й несиметричні двоїсті задачі.
- 510. Економічний зміст двоїстої задачі й двоїстих оцінок.
- 511. Теореми двоїстості, їх економічна інтерпретація.
- 512. Застосування теорем двоїстості в розв’язуванні задач лінійного програмування.
- 513. Методи розв'язування двоїстої задачі лінійного програмування.
- 514. Аналіз розв'язків лінійних економіко-математичних моделей. Оцінка рентабельності продукції. Доцільність введення нової продукції.
- 515. Аналіз обмежень дефіцитних і недефіцитних ресурсів.
- 516. Аналіз коефіцієнтів цільової функції задач лінійного програмування.
- 517. Транспортна задача лінійного програмування. Економічна і математична постановка транспортної задачі.
- 518. Методи побудови опорних планів транспортної задачі. Випадок виродженості. Теорема про розв'язування транспортної задачі.
- 519. Двоїста задача до транспортної задачі. Метод потенціалів.
- 520. Розв'язування транспортної задачі методом потенціалів.
- 521. Відкриті транспортні задачі. Метод розв'язування.
- 522. Цілочислове програмування. Область застосування цілочислових задач в плануванні й управлінні виробництвом.
- 523. Геометрична інтерпретація задачі цілочислового програмування.
- 524. Метод Гоморі повністю цілочислових задач. Знаходження цілої й дробової частини числа. Алгоритм розв'язування задачі.
- 525. Постановка задачі нелінійного програмування, математична модель. Геометрична інтерпретація.
- 526. Графічний метод розв'язування задач нелінійного програмування.
- 527. Метод множників Лагранжа. Теорема Лагранжа. Алгоритм розв'язування задачі на безумовний екстремум.
- 528. Поняття про опуклі функції. Геометрична інтерпретація задачі опуклого програмування на площині.
- 529. Сідлова точка та необхідні і достатні умови її існування. Теорема Куна-Таккера.
- 530. Квадратична функція та її властивості.
- 531. Математична модель задачі опуклого програмування з сепарабельною цільовою функцією.
- 532. Постановка задачі квадратичного програмування та її математична модель.
- 533. Градієнтні методи розв'язання задач нелінійного програмування та їх класифікація.
- 534. Метод Франка-Вульфа. Алгоритм розв'язування задачі нелінійного програмування.
- 535. Сепарабельна функція та її властивості. Розв'язування задач нелінійного програмування методом кусково-лінійної апроксимації.
- 536. Математична постановка задачі динамічного програмування, її економічний зміст. Принцип оптимальності Беллмана.
- 537. Основні рекурентні співвідношення розв'язування задач динамічного програмування.
- 538. Методи розв'язування задач динамічного програмування. Основні кроки алгоритму розв'язування задачі динамічного програмування.
- 539. Математична постановка задачі стохастичного програмування і область їх застосування в управлінні виробничими системами.
- 540. 3Ведення розв'язання одноетапної статичної задачі стохастичного програмування до детермінованої задачі лінійного програмування.
- 541. Основні поняття теорії ігор. Гра двох гравців з нульовою сумою, правила гри, ціна гри, пара оптимальних стратегій для двох осіб.
- 542. Платіжна матриця. Основна теорема теорії ігор. Принцип мінімаксу.
- 543. Гра в чистих стратегіях. Поняття сідлової точки і її знаходження.
- 544. Гра2x2 взмішаних стратегіях. Алгоритм розв'язування задачі.
- 545. Зведення гри двох осіб до задачі лінійного програмування.
- 547. Основні числові характеристики випадкового процесу та їх властивості.
- 548. Кореляційна функція випадкового процесу та її властивості. Нормована кореляційна функція.
- 549. Поняття про оператор перетворення випадкового процесу. Лінійні однорідні перетворення. Нелінійні перетворення.
- 550. Визначення стаціонарного випадкового процесу, щільність ймовірностей для одного, k періодів.
- 551. Кореляційна функція, нормована кореляційна функція та їх властивості.
- 552. Ергодичні властивості стаціонарного випадкового процесу та його математична трактовка.
- 554. Стаціонарний випадковий процес із лінійною кореляційною функцією.
- 555. Стаціонарний випадковий процес із експоненціальною кореляційною функцією.
- 556. Пуассонівський процес та його математична модель.
- 557. Імовірні твірні функції.
- 558. Визначення ланцюга Маркова. Матриця однокрокового переходу. Однорідні ланцюги Маркова та їх класифікація.
- 559. Поглинаючі однорідні ланцюги Маркова та їх числові характеристики. Фундаментальна матриця.
- 560. Регулярні однорідні ланцюги Маркова та їх числові характеристики. Фундаментальна матриця для цих ланцюгів.