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

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

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

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

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

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

Оптимальним розв’язком цієї задачі є управління що складається з сукупності оптимальних покрокових управлінь:

і уможливлює досягнення максимальної ефективності:

Як визначити статус ресурсів прямої задачі та інтервали стійкості двоїстих оцінок відносно змін запасів дефіцитних ресурсів?

Статус ресурсів можна визначати трьома способами. Перший — підстановкою значень вектора Х * (оптимального плану виробництва) у систему обмежень прямої задачі. Якщо обмеження виконується як рівняння, то відповідний ресурс дефіцитний, у іншому разі — недефіцитний.Другий спосіб — через додаткові змінні прямої задачі. Якщо додаткова змінна в оптимальному плані дорівнює нулю, то відповідний ресурс дефіцитний, а якщо більша від нуля — недефіцитний.Третій спосіб — за допомогою двоїстих оцінок. Якщо уі > 0, то зміна (збільшення або зменшення) обсягів і -го ресурсу приводить до відповідної зміни доходу підприємства, і тому такий ресурс є дефіцитним. Якщо ж уі = 0, то і -й ресурс недефіцитний. Для того щоб визначити інтервали стійкості необхідно: приріст (зміну) запасу ресурсу 1 позначити ∆ b 1: будуємо новий оптимальний план, враховуючи, що . До можливих нових оптимальних значень ставимо вимогу невід’ємності. Взагалі, нерівності виду: . , де, , визначають границі змін загальних обсягів ресурсів, у межах яких визначена оптимальним планом структура виробництва продукції залишається незмінною.

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

Суть методу Жордана-Гаусса.

Симплекс-метод — це ітераційна обчислювальна процедура, яка дає змогу, починаючи з певного опорного плану, за скінченну кількість кроків отримати оптимальний план задачі лінійного програмування. Визначення нових опорних планів полягає у виборі вектора, який слід ввести в базис, і вектора, який необхідно вивести з базису. Така процедура відповідає переходу від одного базису до іншого за допомогою методу Жордана—Гаусса - будь-який вектор, що не входить у базис, розкласти за базисними векторами, а потім визначити таке , для якого один з векторів виключається з базису.