Математические методы в принятии решений

Эффективность каждой стадии процесса оценивается скалярной  величиной Q_ν (y_ν, u_ν), которая называется функцией полезности – критерием оптимальности

       (5.4, а)

с учетом (5,1) функциональная зависимость (5.4, а) может быть представлена как

       (5.4, б)

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

       (5.5)

Естественно, что критерий оптимальности Q зависит от совокупности управляющих воздействий на всех стадиях процесса (u₁, u₂, ..., u_m).

Таким образом, задачу оптимизации  многостадийного процесса можно  сформулировать как задачу отыскания  оптимальной стратегии u_опт = (u_1опт , u_2опт , ..., u_mопт ) , для которой критерий оптимальности Q принимает максимальное или минимальное значение.

Процедура применения принципа оптимальности для оптимизации m-стадийного процесса должна начинаться с последней стадии, для которой не существует последующих стадий, могущих повлиять на выбор управления u_m опт на этой стадии. После этого приступают к определению оптимального управления для предыдущей m – 1 стадии, для которой оптимальная стратегия на последующих стадиях, т.е. на последней m-й известна и т.д. В результате может быть найдена оптимальная стратегия управления для

всего многостадийного процесса, являющаяся функцией начального состояния  процесса um (y0).

При применении любой стратегии  управления величина критерия оптимальности Q зависит только от состояния входа первой стадии у₀ ( ) Q = Q _y0 .

Пусть оптимальное значение целевой функции (для определенности минимальное) на участке от ν до m будет B_ν^m(y_{ν −1}), и оно зависит от состояния на ν – 1 стадии

     (5.6)

Соответственно

        (5.7)

здесь оптимизация проводится по всем возможным управлениям, принадлежащим  области допустимых значений U, на всех стадиях процесса. Соотношение (5.7) по существу является математической формулировкой задачи оптимизации m-стадийного процесса, но не содержит указаний как нужно минимизировать критерий Q, чтобы получить оптимальную стратегию u_опт = (u_1опт , u_2опт , ..., u_mопт ).

Так как Q является аддитивной функцией критериев оптимальности отдельных стадий, то его можно представить в виде

      (5.8)

тогда (5.7) перепишется в  виде

    (5.9)

Выражение (5.9) может быть также переписано в виде

    (5.10)

где минимизация первого  слагаемого Q1 (y0, u1) проводится только по управлению u1, а второе минимизируется выбором управлений на всех стадиях, причем каждое слагаемое в (5.10) нельзя минимизировать в отдельности, так как они оба зависят от u1.

Минимизацию второго слагаемого в (5.10) можно рассматривать как  задачу оптимизации (m – 1) стадийного процесса с критерием оптимальности  Q_m−1( y₁) и оптимальной стратегией u_{m−1 опт} = (u_2опт, u_3опт, … ,u_mопт) . Таким образом, можно записать, что

      (5.11)

Выражение (5.9) с учетом (5.11) может быть представлено в виде

     (5.12)

Если математическое описание первой стадии y₁ = f₁(y₀ , u₁ ), то

    (5.13)

Последнее уравнение является математической формулировкой принципа оптимальности и называется рекуррентным соотношением Беллмана.

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

Уравнение (5.13) можно трактовать как оптимальные потери, причем Q₁ (y₀) , u₁ – потери на первом участке, а B_m–1 – оптимальные потери на всех последующих участках. Минимизируя сумму этих потерь, необходимо найти правильное соотношение между ними.

5.3 Общая процедура решения задач методом динамического программирования

 

Согласно общему подходу  к решению задач методом динамического  программирования определение оптимальных  управлений начинается с последней  стадии процесса, для которой рекуррентное соотношение Беллмана с учетом, что B₀ (y_m) = 0, записывается в виде

Для этой стадии можно построить  зависимость целевой функции Q_m от управления u_m для различных значений переменной состояния y_m–1 (рис. 5.2).

Эта зависимость позволяет  найти зависимость оптимального управления на последней стадии u_mопт от входной переменной этой стадии y_m–1 (рис. 5.3).

 

Одновременно определяется минимальное значение целевой функции B₁ данной стадии от ее входа, т.е. y_m–1 (рис. 5.4).

Таким образом можно получить зависимости оптимального управления на m-й стадии от входной переменной этой стадии u_mопт = u_m(y_m−1), а также критерия оптимальности на этой m-й стадии от ее входа B₁ = B₁(y_m−1). Кроме того, можно определить зависимость выходной переменной при оптимальном управлении от входной переменной  y_mопт = y_m (y_m−1) (рис. 5.5).

Для определения оптимального управления u_m–1 на (m – 1)-й стадии из всех полученных результатов необходима зависимость B₁(y_m–1), с учетом которой рекуррентное соотношение для (m – 1)-й стадии записывается как

Далее необходимо построить  зависимость (Qm-1 + B1) от управления u_m–1 для различных значений y_m–2 переменных состояний входа (m – 1) стадии (рис. 5.6).

Также как и для m-й стадии в результате минимального значения выражения (5.15) находятся зависимости u_m−1опт = u_m−1(y_m−2), B₂ = B₂(y_m−2), а также y_m−1опт = y_m−1(y_m−2 ), которые представлены соответственно на рис. 5.7, 5.8, 5.9.

Далее появляется возможность  записать рекуррентные соотношения  на (m – 2) стадии, и т.д. Продолжая процесс вычислений можно дойти до первой стадии, для которой также будут получены соотношения ( ) 1опт 1 0 u = u y , B_m= B_m(y₀), 1опт 1( 0). y = y y Возможный вид кривых для них представлен на рис. 5.10 –5.13.

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

На втором этапе решения  оптимальной задачи находятся оптимальные  управления всех стадий u_ν, ν = 1, m , для чего необходимо принять соответствующее значение состояния входа y₀. В том случае, если оно в постановке задачи не задано, его можно определить из условия минимума величины B_m как функции значения y₀ (рис. 5.12). В рассмотренном случае зависимость B_m от y₀ имеет минимум, что позволяет найти оптимальное значение состояния входа y₀ = a₀. Минимальное значение B_m может достигаться и на концах.

После определения переменной состояния входа из условия минимума функции B_m(y₀), преступают к определению оптимальных управлений для всех стадий процесса, соответствующих выбранной величине y₀ = a₀ (рис. 5.12). Вторым этапом решения задачи оптимального управления методом динамического программирования является определение оптимальных управлений для всех стадий. Здесь порядок расчета следующий.

Определяется оптимальное  управление на первой стадии (рис. 5.11) u_1опт = b₁ и значение выходной переменной этой стадии y_1опт = a₁ (рис. 5.13), отвечающее оптимальному управлению. После этого переходят ко второй стадии, и вся процедура повторяется и т.д. В результате решения задачи доходят до последней m-й стадии и имеют значения u_Vопт для всей рассматриваемой задачи по стадиям.

Динамическое программирование является одним из методов решения  задач оптимизации при принятии решений. Основные преимущества этого  метода: прежде всего, он позволяет  найти глобальное оптимальное решение; оптимизация ведется по одной  переменной; рекуррентная формула (уравнение) Беллмана удобна для программирования. Ограничением метода является размерность  задачи, так как приходится хранить  результаты оптимизации всех этапов. Но гораздо более серьезные затруднения возникают при применении метода динамического программирования для оптимизации многостадийных процессов, для которых размерности векторов состояния y_ν и управления u₀ велики, из-за сложности отыскания оптимальных управлений на каждой стадии. Поэтому следует стремиться, чтобы размерность стадии оптимизируемого объекта была по возможности невысокой.

5.4 Задачи, решаемые методом динамического программирования

 

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

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

Задача заключается в  распределении ресурсов таким образом, чтобы максимизировать общий  доход при следующих условиях: доходы, полученные от различных процессов  измеряются общей единицей; доход, полученный от рассматриваемого процесса, не зависит  от количества ресурсов, выделенных для  других процессов; общий доход получается как сумма доходов полученных от отдельных процессов.

Математическая формулировка задачи следующая.

Пусть имеется N различных процессов (ι = 1, 2, ..., N), каждому из которых соответствует функция полезности – целевая функция (доход) Qι, зависящая от количества выделенных ресурсов uι . Общий доход определяется аддитивной функцией

на количество ресурсов наложены ограничения, что общее их количество не должно превышать заданного u1 + u2 + ...+ uN = u, где uι ≥ 0.

Требуется максимизировать  целевую функцию Q (u₁, ..., u_N) при uι, удовлетворяющих соответствующим ограничениям.

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

Если uι – число отдельных предметов ι-го типа, Vι – вес отдельного предмета ι-го типа), Сι – стоимость отдельного предмета ι-го типа, z – максимальная грузоподъемность судна, N – количество различных типов, тогда ценность груза определяется линейной формой

и ограничение по грузоподъемности имеет вид 

Требуется максимизировать  целевую функцию Q (u) при ограничении на грузоподъемность и условиях Cι ≥ 0, Vι ≥ 0, uι = 0, 1, 2, ...

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

 

5.4.2 Транспортная  задача

В математической экономике  большое значение имеет задача наиболее эффективного перемещения ресурсов из одного пункта в другой. Это, так  называемая, транспортная задача.

Пусть ресурсы сосредоточены  на складах ι = 1, 2, ..., m (Dι), спрос на них имеется в пунктах потребления j = 1, 2, ..., N (Pj). Для простоты рассматривается один вид ресурса, его запасы на ι-м складе – uι, спрос на него в j-м пункте потребления – rj. Общий запас равен общему спросу .

Количество ресурсов, отправляемые из ι-го склада в j-й пункт потребления u_ιj, стоимость соответствующей перевозки Q_ιj (u_ιj ). Величины u_ιj должны быть неотрицательны, u_ιj ≥ 0. Кроме того, вводятся ограничения на запасы; общее количество ресурсов, отправляемое из любого склада, должно равняться запасам на этом складе ; и ограничение на спрос; общее количество ресурсов, отправляемое в любой пункт потребления, должно равняться спросу в этом пункте

Таким образом, требуется  определить количество перевозимых  ресурсов из ι-го склада в j-й пункт потребления u_ιj , чтобы общая стоимость перевозок была минимальна.

Эта задача обычно решается методом линейного программирования. Но, если функции стоимости Q_ιj ( u) нелинейные, то эти методы не применимы, и задача может быть решена методом динамического программирования.

Пусть для простоты имеется  два склада ι = 1, 2, и N пунктов потребления. Величина затрат при использовании оптимальной политики составляет BN (u₁, u₂) при N = 1, 2, ..., u₁ ≥ 0, u₂ ≥ 0.

Удовлетворяя первым спрос  в N-м пункте потребления, затраты в нем составят ( ) ( ) Q1N u1N + Q2N u2N и запасы ресурсов на складах уменьшатся до u₁ − u₁N и u₂ − u₂N . Согласно принципа оптимальности для N ≥2 рекуррентное соотношение Беллмана записывается в виде