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

Динамічне програмування являє собою математичний апарат, що дає змогу здійснювати планування багатокрокових керованих процесів, а також процесів, які розвиваються у часі. До задач динамічного програмування належать такі, що пов’язані з оптимальним розподілом капіталовкладень, розподілом продукції між різними регіонами, визначенням найкоротшого шляху завезення товарів споживачам, задачі щодо заміни устат­кування, оптимального управління запасами, також такі задачі, що стосуються резервування ресурсів, розподілу ресурсів із вкладенням доходів у виробництво, марківські моделі прийняття рішень тощо

 

47. Які ви знаєте методи побудови опорного плану?

Допустимий план називається опорним планом задачі лінійного програмування, якщо він задовольняє не менш ніж m лінійно-незалежним обмеженням системи у вигляді рівностей. Опорний план називається не виродженим, якщо він містить точно m додатних змінних: Х*=(х1*, х2*, … хn*). Опорний план представляється вектором за яким цільова функція досягає максимального або мінімального значення називається оптимальним розв’язком. Задачу л.п. можна звести до канонічної форми, тобто до такого вигляду, коли в системі обмежень всі значення в правій частині невід’ємні, а всі обмеження є рівностями. Для цього, якщо bi – від’ємне, то помноживши i-те обмеження на (-1) отримаємо додатнє значення в правій частині. Коли i-те обмеження має вигляд нерівності, то його можна звести до рівності, увівши додаткову змінну. Скорочену форму можна подати за допомогою знака сігма за умов:

Ще компактнішим є запис задачі лінійного програмування у векторно-матричному вигляді:max(min) Z = CX

за умов:

АХ = А 0;

Х ≥ 0,де

є матрицею коефіцієнтів при змінних;

— вектор змінних; — вектор вільних членів;

С = (с1, с2, …, сп) — вектор коефіцієнтів при змінних у цільовій функції.

Часто задачу лінійного програмування зручно записувати у векторній формі: max(min) Z = CX за умов:

A 1 x 1 + A 2 x 2 + … + Anxn = A 0;

X ≥0,

де

є векторами коефіцієнтів при змінних.

Для побудови транспортної задачі використовуються наступні методи побуди опорного плану: метод північно-західного кута, метод мінімальної вартості, метод подвійної переваги, метод апроксимації Фогеля. Для побудови симплекс-таблиці – метод Жордана Гауса.

Для задачі на призначення – угорський метод. Для задач динамічного програмування, використовується метод рекурентних співвідношень, формула Белмана. Для задач цілочислових – метод Гоморі, метод гілок та меж, метод вектора спаду.

 

48. Який опорний план називається не виродженим?

Вектор Х = (х 1, х 2, …, хn), координати якого задовольняють систему обмежень та умови невід’ємності змінних, називається допустимим розв’язком (планом) задачі лінійного програмування.

Допустимий план Х = (х 1, х 2, …, хn) називається опорним планом задачі лінійного програмування, якщо він задовольняє не менше, ніж m лінійно незалежних обмежень системи у вигляді рівностей, а також обмеження щодо невід’ємності змінних.

Опорний план Х = (х 1, х 2, …, хn), називається невиродженим, якщо він містить точно m додатних змінних, інакше він вироджений.

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