Методы оптимизации в экономике, страница 6

Цена процесса равна сумме всех оценок: Ф- 1 Х ~Г»(х»,и») + Г~(хл,) ~ »=р И~(х ) = шах и , ..., и,„ , Р Максимальная цена в исходной задаче равна функции Беллмана Й'(х) . Выведем уравнение Беллмана. Для этого в правой части (5.2) выдели~ слагаемое Г (х,,и ): М-1 Й' (х„) = шах ~ Г (х,и ) + Х Г»(х»,и») + Г,,(х~,,) 40 М-1 Г= Х Г»(х»,и )+Г (х ).

(5.2) »=О Задача оптимального управления дискретным многошаговым процессом состоит в том, чтобы для заданного начального состояния хо процесса, который определен своими уравнениями состояний х»+1 —— Д» (х», и») и множествами возможнык состояний и управлений, найти управления ио, и1, ..., и~ 1, при которых качество процесса Г оптимально (максимально или минимально). Найденное управление ио, и1, ..., и~ 1 называют оптимальным управлением. Для решения задачи Р.Беллман использовал принцип оптимальности: каково бы ни было сос~ояние и управление процесса до момента времени р, последующее управление должно быть Оптимально от- НОСИТЕЛЬНО СОСТОЯНИЯ В МОМЕНТ ВРЕМЕНИ Р. Введем в рассмотрение функцию Беллмана, равную максимальной цене процесса, начинающегося в момент р из начального состояния х~ .

Учтем, что х, а Следовательно, и Р (х, и ) не зависят От последующикуправлений и ~, ...,н~ 1, и вынесем Р' (х,п ) зазнакоперации нахождения максимума по и 1 ... ) иу И'(х ) = шах 1'(х„,и )+ И М- 1 + а" ( ~ ~а(ха "в) + )ж(хм) Убедившись„что второе слагаемое в праной части равенства равно функции Беллмана Вр+ ~ (х +1), получим И' (х ) = шах~К (х,и ) +И',(х,) ~. (5.4) я Полученное выражение (5.4) Является рекуррентным соотношением для определения функции Беллмана на шаге р по ее значению на шаге р+1 и называется уравнением Беллмана. Для того чтобы найти решение уравнения Беллмана, нужно определить значение функции Беллмана на последнем шаге.

По определению функция Беллмана И',~(х,,) равна максимальной цене процесса, начинающегося и заканчивающегося в момент Ж с состоянием х~. Качество такого процесса не зависит От предшествующего состояния и управления и равно Г~„(х~) . Следовательно„ И'~,(хл,) = Г~~(х,ч) . . (5.5) Метод решения задачи оптимального управления дискретным многошаговым процессом на основе функционального уравнения Беллмана состоит из двух этапов. На первом этапе находят значения функции Беллмана И' (х ) по уравнению (5.4) для всех возможных состояний х из множества Х в предпоследний моментвремени р = Ф вЂ” 1, используя граничное условие (5.5); затем в момент р = Ж вЂ” 2, используя найденное значение И~~ 1, и так далее, справа налево по шкале дискретного времени до начального момента р = О.

Оптимальное управление и (х ) Определяется одновременно с вычислением функции Беллмана при нахождении максимума правой части уравнения (5.4). Оптимальное управление может быть определено неоднозначно, После окончания первого этапа можно указать оптимальную цену процесса для любого начального ус- ловия и Оптимальное управление ДлЯ любого состояния В любой дискретный момен~ ~ремен~.

На ВторОм этапе находят оптимальный процесс для заданнОГО на- чальнОГО условиЯ хо . Зная хо, Определяют Оптимальное управление и (хо ) . которое было найдено на первом этапе, и по уравнению состояний (5.1) вычисляют х| . Затем, зная х1, определяют оптимальное управление и~ (х~ ), которое было найдено на первом этапе, и по уравнению состояний (5.1) вычисляют хз.

И так далее, слева направо, вычисляют все значения состояния оптимального процесса до х~. Таким образом, для того чтобы поставить задачу Опт -ы чьного управления дискретным многошаговым процессом, нужно указать: 1. Дискретный отрезок времени. 2. Множество возможных состояний. 3. Множество возможных управлений. 4.

Уравнение состояний. 5. Начальное состояние. б. Показатель качества. Для того, чтобы паынть аадачу оптиыального управлания диоаратным мнОГОшаГОВым процессом, нужно: 1. Составить уравнение Беллмана. 2. Записать граничное условие для функции Беллмана. 3. Найти значение функции Беллмана и оптимальное управление (справа налево). 4. Найти качество оптимального процесса для заданного начального состояния. 5. Построить оптимальный процесс (слева направо).

5.2. Задача замены оборудования Применим метод динамического программирования к задаче замены оборудования. Фирма использует оборудование, срок работы которого не может превышать трех лет. Замена оборудования может производиться в конце календарного года. Прибыль От эксплуатации оборудования Р и затраты на его ремонт Я зависят от срока его эксплуатации и даны в табл.

5.1 в условных единицах. Таблица 51 Стоимость покупки и установки оборудования составляет 4О условных единиц. Требуется составить план замены оборудования, при котором суммарная прибыль за три года будет максимальной, если: а) оборудование новое; б) оборудование проработало 1 год. Составим математическую модель задачи. Замену оборудования представим как дискретный процесс с дискретным временем Ж 6,1,2,3: 1-й год 2-й год 3 -й год Годы работы Фирмы а" О и 1 Дискретное»рема хй + 1, если ий = «староеэ, х О ~если и й = «новое э . Начальное состояние: а) хо = О; б) хо = 1. Множество возможных состояний Х = ( О,1,2 ); множество возможных управлений У = («новое», «староеэ ). При х = 2 управление а = «старое» является недопустимым, так как в этом случае на последующем шаге х станет равным 3 и выйдет из множества допустимых управлений.

2 Качество плана Р = Х ( Р (хй ) — К (хй ) — В ( ий ) 1-> шах . й-о Значения Р и К даны в табл.5.1, ~ О, если ий = «старое», В(и )= ~ 40, если и й — — «новое» . (5.7) 43 За состояние процесса в момент к примем число лет, которое к моменту Й проработало оборудование. Управление в момент Й(и = «новоеэ) состоит в замене оборудования или отказе от замены (и = «староеэ) в конце текущего года. Уравнение состояния имеет вид Уравнение Беллмана в задаче замены оборудования: Я' (х ) шах ~Р (х ) -Я(х )-В(и ) + й' 1(х„~ ) ~ ~ «старое», Р ~ «но»ое» с граничным условием ~з(хз) (5.9) 3 а и е ч а н и е. Формула (5.8) справедлива для х О и Р х 1. При х 2 допустимым является только управление и «но- Р вое» и, следовательно, и;(2)- Р(2) — Л(2) — 40+ 1~„,(О) .

(5.10) Применим метод динамического программирования. Найдем значения функции Беллмана $Г(х ) и оптимальное управление и (х ) . Этап 1*по (5*9) имеем ~3(0) = 3(1) - 3( )- Найдем значения функции Беллмана И~ (х ) и оптимальное управление и (х ) на шаге 2. Длях О их 1: (Р(х) — В (х) — В(«новое») + Я~;(0) ), ( Р (х ) — Я (х ) — В ( «старое») + $Кз (х + 1 ) 1 (Р(х) — Я(х) — 40 + 01, (Р(х) — Я(х) — 0 + О) Следовательно, В~(х) = Р(х) — Я(х) и из(х) = «старое». З м б .

52 И2(О) = 70 и ~,(О) =« рое», И~(1) = 40 и и~(1) =«старое». Значения И'2 (2) = -30 и и~ (2) = «новое» определим по (5.10). Найдем значения функции Беллмана й'(х ) и оптимальное управление и (х ) на шаге 1. Для х=О их 1: ( Р ( х ) — К ( х ) — В ( «новое») + й~~ ( О ) 1, (Р(х) — Я (х) — В(«старое»)+ Из(х + 1 )1,~ 180 — 10 — 40 * 70 ),1 АР ~" Ф$ 1 ~ и 180 — 10 — 0 + 401 170 — ЗΠ— 40 + 701, 70 1 70 — ЗΠ— Π— 301 И~~ (1) шах )~(х) п(«новое' ) + И'о(0)1 (Р(х ) — Я ( ) — В ( «старое») $Ко ( 1 ) ) 180 — 10 — 40 + 1101, 180 — 10 — О + 701 В'о(0) шах Следовательно, Ио(О) = 140 при ио(0) =«старое» и ио(0) «новое».

170 — ЗΠ— 40 + 1101, 110 170 — За — а + 401 Следовательно, И~о(1) = 110 при ио(1) =«новое», Значения Ио(2) = 80 и ио(2) = «новое» определим по (5,10). Результаты запишем в табл. 5.2. Следовательно, Й'~ (1) 70 при и1 (1) = «новое». Значение И~~ (2) 40 и и1(2) «новое» определим по (5.10). Найдем значения функции Беллмана $Р(х ) и оптимальное управление и (х ) на шаГе О.

Длях О их=1: Таблица 52 Этап 2. а) определим оптимальный процесс для хо = О. Оптимальное управление и (О) не единственно. Позтому в случае а) получаем два оптимальных процесса. Процесс 1. хо О; выбираем ио ( О ) =«новое»; тогда на следующем шаге х~ = 0 (по 5.8); по табл. 5.2 определяем, что и1(0) «старое»; тогда на следующем шаге х~ О, по табл. 5.2 определяем, что из(1) = «старое»; тогда на последнем шаге хз = 2. Процесс 2. хо = О; выбираем ио(О) =«старое»; тогда на сл,едующем шаге х~ 10 (по 5.8); по табл. 5.2 определяем, что и1 ( О ) = «старое»; тогда на следующем шаге х = 1, по табл.

5.2 определяем, что и~ ( 0 ) =«старое»; тогда на последнем шаге хз — — 1. Оптимальным планом замены оборудования будет любой из двух планов: 1. «В конце первого года оборудование не менять, в конце второго года оборудование заменить, в конце третьего года оборудование не менять». 2. «В конце первого года оборудование заменить, в конце второго года оборудование не менять, в конце третьего года оборудование не менять». План 1 соответствует процессу 1.

План 2 соответствует процессу 2. Суммарная прибыль равна 140 условным единицам. Аналогично решаем для хо = 1. Оптимальным планом замены оборудования будет план:"В конце первого года оборудование заменить, в конце второго года оборудование не менят~, в конце третьего года оборудование не менять". План соответствует проц.ссу хо = 1, ио = еновое~',х~ ~ м, и~=Фстароеэ, х~ 1, и~=~старое», х~ = 2. Суммарная прибыль равна 110 условным единицам. 5.3.