5. Пример решения задачи оптимизации методом динамического программирования

В качестве примера применения подхода динамического программирования к многошаговым задачам оптимизации, в которых требуется найти набор из неотрицательных чисел максимизируем сепарабельную функцию (функция называется сепарабельной, если она представляет собой сумму функций, каждая из которых зависит только от одной переменной), при условии, что сумма этих чисел равна фиксированном числу .

Постановка задачи.

Найти ,

при ограничениях

Решение:

Будем решать данную задачу методом динамического программирования. В данной задаче можно интерпретировать постоянную как общий уровень имеющихся ресурсов и рассматривать ее в качестве параметра задачи. Обозначим через – функцию оптимального поведения для процесса развертывания в момент времени с общим запасам ресурсов .

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

.

Для одношагового процесса заканчивающегося в , при этом надо распределять ресурсы между огласно принципу оптимальности

Общее рекуррентное соотношение имеет вид

Решение задачи отыскивается с помощью общего рекуррентного соотношения, последовательно начиная с граничного условия , вплоть до шага (длина шага ) (C).

6. Задача распределения ресурсов

Постановка задачи.

Задана функция

.

Н айти максимум этой функции при ограничениях:

Будем решать эту задачу методом динамического программирования. Для этой задачи рекуррентное соотношение имеет вид

,

где

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

7. Алгоритм решения задачи

1. ,

2. 

3. 

4. 

5. 

6. 

7. ?, если условие выполняется, то переход к пункту 8, иначе переход к пункту 9.

8. 

9. 

10. , если условие выполняется, то переход к пункту 11, иначе к пункту 6.

11. ,

12. 

13. , если условие выполняется, то переход к пункту 14, иначе переход к пункту 4.

14. Вывод и

15. Перенос блока

16. 

17. , если условие выполняется, то переход к пункту 18, иначе переход к пункту 3.

18. 

19. 

20. 

21. Печать и

22. 

23. 

24. , если условие выполняется, то переход к пункту 25, иначе переход к пункту 20.

25. Stop.

Проиллюстрируем изложенный алгоритм на следующей тестовой задаче:

Максимизировать

при условиях

Сформулированная задача часто встречается в различных экономических приложениях и характеризует процесс распределения ресурсов.

Пусть необходимо распределить однотипных автомобилей для выполнения перевозок у клиентов. Считаются известными вероятности выполнения требуемых объемов перевозок одним автомобилем у каждого из клиентов и относительно важности этих перевозок.

Пусть - количество автомобилей , выделяемые - му клиенту, тогда вероятность выполнения всех перевозок -го клиента составляет

,

а математическое ожидание выполненного объема перевозок с учетом их важности у всех клиентов будет

Требуется распределить автомобили так, что бы максимизировать математическое ожидание .