Динамическое программирование. (Лекция 3)
1. Понятие о динамическом программировании. Динамическое программирование – метод оптимизации, приспособленный к операциям, в которых процесс принятия решения может быть разбит на этапы (шаги). (Р.Беллман (1920) – американский математик). Операция – управляемое мероприятие, направленное на достижение некоторой цели Рассматривается некоторый управляемый процесс. В результате управления система (объект управления) S переводится из начального состояния S0 в конечное состояние S*. Управление можно разбить на n шагов, то есть решение принимается последовательно на каждом шаге. S0 S1 S2 Sn-1 S* y1 y2 y3 yn-1 yn … Пусть yk- управление на k-м шаге (k=1,2,…,n; yk- число, точка в n-мерном пространстве, функция, качественный признак и т.д.). Пусть Y=(y1,y2,…,yn) – управление, переводящее систему из состояния S0 в состояние S*. Показатель эффективности – целевая функция, зависит от начального состояния и управления Основные предположения: 1.Состояние Sk системы в конце k-го шага зависит только от предшествующего состояния Sk-1 и управления на k-м шаге yk (отсутствие последействия). 2.Целевая функция является аддитивной от показателя эффективности каждого шага, т.е. если показатель эффективности k-го шага равен то Задача. Определить такое допустимое управление Y, переводящее систему S из состояния S0 в состояние S*, при котором целевая функция принимает наибольшее (наименьшее) значение. Такое управление называют оптимальным.