Назвіть методи розв’язування задач динамічного програмування.

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

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

В задачах динамічного програмування (ДП) розв’язок шукається в декілька етапів. До таких задач відносяться задачі розподілу інвестицій, капіталовкладень підприємства, заміни устаткування, повноваження запасів, оптимальне переміщення по мережі, перевезення вантажу з максим. користністю (вартістю) і т.д. Всі ці задачі та їх розв’язки залежать від фактору часу; розглядається оптимальне керування процесу. Припустимо, що маємо систему в стані , за допомогою керування  вона переведена в і т.д. . X={x1,…,xn}. Послідовністю керування х система переводиться із стану  в стан . Необхідно знайти такі керування системою, щоб перевести систему з початкового стану в останній з найбільшим ефектом найкращим чином. Станам системи відповідають параметри системи. Стан системи від двох або більше параметрів: розглядається цільова функція . Припускається, що система розглядається без оберненого зв’язку, і слідуючий стан залежить від попереднього. Принцип оптимальності Беллмана: В якому б стані не була система, треба вибрати таке оптимальне керування, щоб разом з оптимальними керуваннями на слідуючих кроках отримати найкращий розв’язок. Задачі ДП розв’язуються з кінця:

                  

                  

                  .....................................................................

                  

- Рівняння Беллмана. На останньому етапі знаходимо оптимальне керування

                                          і і... .

Мережева задача: Припустимо заданий граф (мережа),який достатньо зв’язаний

Задачу розв’язують методом ДП починаючи з кінця, останньому пункту даємо характеристику „0”, і знаходимо характеристику відповідних значень . Після цього знаходяться характеристики пунктів, сусідних з  і т.д. При знаходженні -ої характеристики, вказуємо напрямок переміщення, як тільки знаходяться характеристики менші від раніше знайдених, старі характеристики викреслюються і ставляться нові. Якщо міняється характеристика проробленого пункту з галочкою, то треба міняти характеристики сусідних пунктів з ними і так може бути кілька варіантів. Знаходять оптимальний шлях від усіх пунктів до останнього. В кінці пишеться відповідь, в якій вказуються ланки стрілочками і витрати(відстані) від усіх пунктів до останнього. Узагальнюється задача від усіх пунктів до усіх.

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

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

28. За яких умов задача лінійного програмування з необмеженою областю допустимих планів має розв’язок?

. Задача лінійного програмування має оптимальний план за необмеженої області допустимих розв’язків (рис. 2.9 і 2.10). На рис. 2.9 у точці В маємо максимум, на рис. 2.10 у точці А — мінімум, на рис. 2.11 зображено, як у разі необмеженої області допус­тимих планів цільова функція може набирати максимального чи мінімального значення у будь-якій точці променя.

                                                                                                                                                                                                                

                                                    Рис. 2.9                                                                                        Рис. 2.10

 

Рис 11

Задача лінійного програмування не має оптимальних планів: якщо цільова функція необмежена згори (рис. 2.7) або система обмежень задачі несумісна (рис. 2.8).

Рис 7                                                                                                                                              рис. 8