Принцип оптимальности Беллмана

Водный обмен у растений различных экологических групп

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

- ксерофиты. Произрастают в местностях с жарким и сухим климатом и хорошо приспособлены к перенесению атмосферной и почвенной засухи. Имеют мощную кутикулу на поверхности листьев и хорошо развитую корневую систему.

- гигрофиты. Произрастают в условиях повышенной влажности. Плохо переносят почвенную и атмосферную засуху.

- мезофиты. Занимают промежуточное положение. Способны к регуляции устьичной и кутикулярной транспирации.

- гидрофиты. Это водные растения, не имеющие механизмов регуляции транспирации.

Необходимые условия применения метода ДП:

Ø объект исследования - управляемая сис­тема с заданными допустимыми состояниями и управлениями;

Ø задача может интерпретироваться как многошаговый процесс, каждый шаг включает принятие реше­ния о выборе одного из управлений;

Ø состояние, в котором оказывается система пос­ле выбора решения на k -м шаге, зависит только от данного решения и состояния к началу k- гошага. Это свойство называется отсутствием последействия.

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

Более строго это положение формулирует принцип оптимальности Беллмана, лежащий в основе метода ДП:

Каково бы ни было состояние системы S перед очередным шагом, надо выбирать управление на этом шаге так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным.

Важно, что среди всех шагов есть один, который можно планировать без учета его последствий. Это - последний шаг, который может быть выбран так, чтобы он принес наибольшую выгоду.

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

После определения условно оптимальных управлений на всех шагах определяется оптимальное управление для всего процесса.

Алгоритм метода ДП:

1. Процесс управления представляется в виде набора шаговых управлений ;

2. Определяется эффект управления (“функция выигрыша”) на i -м шаге управления (), если перед этим система находилась в состоянии :

3. Определяется, как изменяется состояние системы под влиянием управления на i-м шаге

(переход системы из состояния в состояние ; при этом задаются «функции изменения состояния» (5));

4. Записывается основное рекуррентное соотношение ДП (уравнение Беллмана), выражающее условный оптимальный выигрыш (начиная с -го шага и до конца) через уже известную функцию :

Этому выигрышу соответствует условное оптимальное управление на i-м шаге;

5. Производится условная оптимизация последнего (-го шага) по формуле

и определяется соответствующее условное оптимальное управление;

6. Производится условная оптимизация ()-го, ()-го, и т.д. шагов по формуле (6) при и т.д. и для каждого из шагов определяется условное оптимальное управление;

7. Производится безусловная оптимизация путем перемещения в прямом направлении – от первого шага к последнему

Рассмотрим использование метода ДП на примере.

Пример 1. Под влиянием управления возможен переход системы из любого состояния в одно из двух соседних состояний. Переходы требуют некоторых затрат. Требуется перевести систему из начального состояния в конечное при минимальных совокупных затратах (Рис. 1).

Рис. 1.

Любой полный путь включает 5+7=12 шагов. Состояние системы задается двумя координатами – “восточной” и “северной”. Для каждого состояния нужно найти условное оптимальное управление (перемещаться “на север” или “на восток”). Управление выбирается так, чтобы стоимость всех оставшихся до конца шагов (включая данный) была минимальна.

Произведем оптимизацию последнего 12 шага (Рис. 1). После 11 шага система может находиться в состоянии . Для состояния выбор отсутствует – требуется “идти на восток”, что потребует 10 д.е. Запишем число 10 в соответствующем кружке и обозначим оптимальное управление стрелкой. Для точки управление также вынужденное и требует 14 д.е. Таким образом, проведена условная оптимизация последнего шага и найден условный оптимальный выигрыш для состояний и .

Оптимизируем предпоследний (11-й шаг). После 10-го шага система может оказаться в состоянии . Найдем для каждого из них условное оптимальное управление и выигрыш. Для состояния С₁ управление вынужденное и требует 21 д.е. (11+10).

Для состояния С₂ управление не вынужденное – имеется два варианта, с затратами 28 д.е. (14+14) и 23 д.е. (13+10) соответственно. Т.е. для состояния С₂ условное оптимальное управление – “идти на север”. Для С₃ управление - вынужденное и требует 22 д.е. (8+14).

По аналогии, найдем для каждого состояния условное оптимальное управление и выигрыш, записывая его в кружки. Расход на каждом шаге складывается с уже оптимизированным расходом, записанным в кружке, куда ведет стрелка. Таким образом, на каждом шаге оптимизируется только этот шаг, а следующие за ним уже оптимизированы. Конечный результат показан на Рис. 2.

Рис. 2.

По окончании условной оптимизации понятно, как проводить процесс управления (по стрелке) и во что обойдется путь до конечного состояния (число в кружке). Для примера общие минимальные затраты равны 118 д.е.

Чтобы определить безусловное оптимальное управление – траекторию, требующую минимальных затрат и ведущую из начального в конечное состояние, достаточно двигаться вдоль стрелок.

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

Если решать задачу, последовательно выбирая самое выгодное управление для этого шага, то получим затраты 128 д.е. (10+12+8+10+11+13+15+8+10+9+8+14), что превосходит 118.

Дата добавления: 2013-12-13