Тема 9. Задачі динамічного програмування

Економічна сутність, деякі основні типи задач та моделі динамічного програмування (ДП).

Задачі про заміну основного капіталу підприємства.

Багатокроковий процес прийняття рішень та ДП.

Метод рекурентних співвідношень. Принцип оптимальності Беллмана.

Алгоритм Джонсона.

Тема 10. Моделі та методи стохастичного програмування

Слабоструктуровані прикладні економічні задачі і прийняття рішень в умовах невизначеності та ризику.

Загальна математична постановка задачі стохастичного програмування (СП). Класифікація задач СП. Творча складова та система гіпотез щодо формалізації задачі СП.

Деякі основні (прямі та непрямі) методи розв’язування задач СП.

Методи імітаційного моделювання щодо розв’язування задач СП.

Економічна сутність та основні типи одноетапних задач стохастичного програмування СП.

Математична постановка одноетапних статичних задач СП. Деякі основні методи розв’язування одноетапних статичних задач СП.

Стохастичні аналоги детермінованих моделей управління виробництвом.

Планування обсягу реалізації за невизначеного попиту.

Індикативне планування за невизначеності в ресурсах.

Аналіз розв’язку одноетапних статичних задач СП.

Двохетапні статичні задачі стохастичного програмування та деякі з основних методів їх розв’язування.

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

Адаптивність рішень в економіці.

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

Лінійні задачі двохетапного СП та основні методи їх розв’язування.

Задачі управління виробництвом з урахуванням перевезень у стохастичній постановці (виробничо-транспортна задача двохетапного СП).

Нелінійні двохетапні статичні задачі СП та методи їх розв’язування.

Якісний аналіз двохетапних стохастичних економічних моделей.

Маргінальні властивості стохастичних двоїстих оцінок.

Тема 11. Елементи теорії ігор

Основні поняття теорії ігор. Матричні ігри двох осіб. Платіжна матриця. Гра в чистих стратегіях. Мінімаксні стратегії. Сідлова точка. Змішані стратегії.

О

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

Розділ 2. Загальна задача лінійного програмування та методи її розв’язування

2.1. Загальна математична модель лінійного програмування

Загальна лінійна математична модель економічних процесів і явищ — так звана загальна задача лінійного програмування (ЛП) подається у вигляді:

знайти максимум (мінімум) функції (2.1)

або

за умов

(2.2)

. (2.3)

Отже, потрібно знайти значення змінних x₁, x₂, …, x_n, які задовольняють умови (2.2) і (2.3), тоді як цільова функція набуває екстремального (максимального чи мінімального) значення.

Задачу (2.1)—(2.3) легко звести до канонічної форми, тобто до такого вигляду, коли в системі обмежень (2.2) всі b_і (і = 1, 2, …, n) невід’ємні, а всі обмеження є рівностями.

Якщо якесь b_і від’ємне, то, помноживши і-те обмеження на (–1), дістанемо у правій частині відповідної рівності додатне значення. Коли і-те обмеження має вигляд нерівності , то останню завжди можна звести до рівності, увівши допоміжну зміннуx_n + 1: .

Аналогічно обмеження виду зводимо до рівності, віднімаючи від лівої частини допоміжну зміннух_n + 2, тобто

Приклад 2.1.

Записати в канонічній формі таку задачу ЛП:

max

за умов

.

Розв’язування. Помножимо другу нерівність на (–1) і введемо відповідно допоміжні змінні х₄ і х₅ для другого та третього обмеження:

Неважко переконатися, що допоміжні змінні, у цьому разі х₄ і х₅, є невід’ємними, причому їх уведення не змінює цільової функції.

Отже, будь-яку задачу ЛП можна записати в такій канонічній формі:

знайти максимум функції  max (2.4)

за умов

(2.5)

. (2.6)

Задачу (2.4)—(2.6) можна розв’язувати на мінімум, якщо цільову функцію помножити на (–1), тобто

.