10. ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ С МУЛЬТИПЛИКАТИВНЫМ КРИТЕРИЕМ

До сих пор мы рассматривали только такие задачи динамического программирования, в которых выигрыш (критерий, или показатель эффективности) складывался из суммы выигрышей на отдельных шагах:

т. e. был аддитивен.

Иногда возникают задачи, в которых величина W представляет собой не сумму, апроизведение:

где — выигрыш на шаге (предполагается, что все положительны). Такой показатель или критерий эффективности называется мультипликативным.

Нетрудно убедиться, что любая задача с мультипликативным критерием может быть сведена к задаче с аддитивным критерием. Для этого достаточно, например, прологарифмировать выражение (10.2) и искать решение, обращающее в максимум логарифм величины W. Так как логарифм — возрастающая функция, то максимум логарифма соответствует максимуму величины W.

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

Основное функциональное уравнение динамического программирования для этого случая будет иметь вид:

а условие оптимальности последнего шага сохранится в том же виде, как при аддитивном критерии:

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

Рассмотрим одну из типичных задач динамического программирования с мультипликативным критерием.

Распределение средств для повышения надежности технического устройства

Имеется техническое устройство S, состоящее из элементов, или узлов (см. рис. 3.39). Безотказная работа каждого элемента безусловно необходима для работы устройства S в целом.

Элементы могут отказывать (выходить из строя), причем независимо один от другого. Надежность (вероятность безотказной работы) всего устройства равна произведению надежностей всех элементов:

где — надежность элемента.

В нашем распоряжении имеются некоторые средства (в денежном, весовом или ином выражении), которые можно употребить на повышение надежностей элементов.

Рис. 3.39

Количество средств X, вложенное в приспособления, повышающие надежность элемента, доводит ее до значения

Все функции — неубывающие.

Требуется определить оптимальное распределение средств по элементам, Приводящее к наибольшей надежности устройства в целом.

Задача решается методом динамического программирования. Перед нами — задача с мультипликативным критерием. Выигрыш на шаге где управление — количество средств, вложенное в элемент.

Основное функциональное уравнение имеет вид:

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

Как и во всех задачах распределения ресурсов, где средства расходуются до конца, а выигрыш — неубывающая функция, оптимальное управление на последнем шаге состоит в том, чтобы выделить на этот шаг все оставшиеся средства:

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

Последовательным применением формулы (10.7) для как всегда, находим условные оптимальные управления

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

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

(10.10)

То управление

при котором достигается максимум (10.10), и есть безусловное оптимальное управление на первом шаге, а — безусловный опти мальный выигрыш, т. е. максимально достижимая данными средствами надежность устройства. Далее оптимальное управление строится по схеме: