Принципы динамического программирования и функциональные уравнения Беллмана

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

Введем след обозначения: - мн-ва всех состояний в кот может нах система перед шагом . В частности при -мн-во нач состояний; - мн-ыо управлений, кот могут быть выбраны на шаге и под воздейств каж их кот система переходит из сост принадлежащего мн-ву в сост, принадлежащее мн-ву - условно оптимальная значение цел ф-ции, если процесс рассм на инт от шага до шага N при усл, что перед шагом tсистема находилась в одном их сост мн-ва и на шаге tбыло выбрано управление из мн-ва , которое обеспечило цел ф-ции усл оптим значения; - значение целевой ф-ции на i–ом шаге для всех управлений их мн-ва при усл, что система нах-лась в одном их сост мн-ва . В принятых обозначениях принцип опт-ти можно записать в след форме: (1)

Ур-ние (1) наз функцион ур-нием ДП(функц Ур Беллмана). Для последнего шага Ур (1) приним вид: , т.к. ф-ции опред для , то . И тогда на посл шаге справ-во ур-ние: ,(2).Т.к. рассм система без последействия, то , то на основании ур (1)-(3) с учетом конкрет мн-в строится высислительная процедура МДП, кот разделяется на 2 этапа: 1. условную; 2. безусловную оптимизацию.

Усл опт-ция осуществляется путем обратного движения от последнего шага к первому. Из ур (2) находится такое упраление из мн-ва , кот для каж состояния принадлежащего мн-ву доставляет экстремум ф-ции и сисмема переходит в конечное состояние. Т.одля каждого состояния из мн-ва нах-ся условно-оптимальне знение целевй ф-ции и условно-оптим управление на последнем шаге. Далее из уравнения (1) нах-ся усл-оптим управление на (N-1) шаге и усл-оптим значение целевой ф-ции на 2-ух последних шагах. При этом для каждого состояния из мн-ва и управления из мн-ва по ф-ле (3) нах-ся соотв состояние из мн-ва и поэтому состоянию учетом разультатов, предшествующих расчетов определяется усл-оптим значение целевой ф-ции, начиная рассм шага до конечного. Процесс продолжается до 1-го шага. Безусл-оптим управление нах на этапе безусл оптимизации путем прямого движения от 1-го этапа к последнему.

Природа задачи, допускающая использование метода ДП не изменяется при изменении кол-ва шагов N. В этом смысле всякий конкрет процесс с задан кол-вом шагов оказывается как бы погруженным в сем-во подобных процессов и может рассм с позиции более широкого класса задач. В этом заключается 2-ой принцип ДП, наз-емый принципом погружения.В силу этого св-ва при реш задачи методом ДП получают более широкий спектр рез-тов чем в исх постановке. Заметим, что МДП при выборе решения на каж шаге учитывает интересы всего процесса, а не только интересы дан шага.

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

2. Основные формы задач ЛП. Правила сведения задачи ЛП к канонической форме. Геометрическая интерпретация задачи ЛП. Понятие угловой точки множества.

3. Критерий угловой точки множества (с док-вом). Пример.

4. Определение базиса угловой точки.Невырожденные угловые точки

5. Связь между переменными задачи ЛП.

6. Формула приращения целевой функции задачи ЛП.

7. Достаточное условие оптимальности в задаче ЛП. Достаточное условие неразрешимости задачи ЛП.

8. Итерация симплекс–метода.

9. Обоснование конечности симплекс – алгоритма.

10. Обоснование непустоты множества планов в ЗЛП. Пример.

11. Нахождение базиса угловой точки. Пример.

12. Постановка транспортной задачи (ТЗ). Построение нач.плана перевозок методом северо-западного угла, методом мин.элемента.

13. Определение закрытой модели ТЗ. Критерий сущ.решения ТЗ.

14. Исследование множества клеток транспортной таблицы.

15. Достаточное условие минимальности стоимости перевозок.

16. Классический метод решения задачи безусловной минимизации ф-ции многих переменных. Пример.

17. Метод исключения решения задачи на услов. минимум. Пример.

18. Обобщенное правило множителей Лагранжа в задаче оптимизации с ограничениями типа равенств.

19. Классическое правило множителей Лагранжа в задаче оптимизации с ограничениями типа равенств. Необходимые условия второго порядка в задаче оптимизации типа равенств.

20. Достаточные условия экстремума в задаче оптимизации с ограничениями типа равенств.

21. Определения выпуклого множества, выпуклой функции. Свойства выпуклых множеств. Сумма выпуклых функций.

22. Теорема о точках минимума выпуклой функции. Теорема о стационарной точке выпуклой функции.

23. Необходимые усл. минимума дифференцируемой ф-ции на выпуклом множестве, выраженные через скалярное произведение. Критерий мин. выпуклой диф. ф-ции на выпуклом мн-ве…..

24. Задача проектирования на выпуклое и замкнутое мн-во.Св-ва проекц

25. Критерий построения проекции на выпуклое замкнутое множество. Необходимые усл.миндиф. ф-ции на выпуклом мн-ве….

26. Теорема о седловой точке функции Лагранжа (достаточные условия оптимальности).

27. Критерий существования седловой точки функции Лагранжа для задачи выпуклого программирования.

28. Определение двойственной задачи к задаче математического программирования. Свойство двойственной задачи.

29. Связь между двойственной и прямой задачами матем. программир

30. Пример решения зад. оптимизации с помощью теории двойственности.

31. Основные определения в задаче одномерной минимизации.

32. Метод деления отрезка пополам реш.зад. одномерной минимиз.

33. Метод золотого сечения реш. зад. одномерной минимизации.

34. Обоснование метода ломаных решения задачи одномерной миним

35. Алгоритм и условия сходимости метода ломаных решения задачи одномерной минимизации. Пример.

36. Алгоритм метода скорейшего спуска решения задачи многомерной минимизации.

37. Алгоритмы метода условного градиента и метода проекции градиента решения задачи многомерной условной минимизации.

38. Алгоритм метода покоординатного спуска решения задачи многомерной минимизации. Геометрическая иллюстрация.

39. Сходимость метода скорейшего спуска.

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

41. Метод вариаций Лагранжа.

42. Уравнение Эйлера.

43. Случаи интегрируемости уравнения Эйлера. Примеры.

44. Задача вариационного исчисления с незакрепленными концами и фиксированным отрезком интегрирования.

45. Задача вариационного исчисления с незакрепленными концами и нефиксированным отрезком интегрирования.

46. Задача вариационного исчисления с движущимся по кривой концом

47. Примеры задач динамического программирования.

48. Принципы динамического программирования и функциональные уравнения Беллмана.

49. Постановка задачи оптимального быстродействия. Принцип макс.

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

51. Пример решения задачи оптимального быстродействия.

Поиск по сайту: