10. ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ С МУЛЬТИПЛИКАТИВНЫМ КРИТЕРИЕМ
До сих пор мы рассматривали только такие задачи динамического программирования, в которых выигрыш (критерий, или показатель эффективности) складывался из суммы выигрышей 
на отдельных шагах:
т. e. был аддитивен.
Иногда возникают задачи, в которых величина W представляет собой не сумму, апроизведение:
где 
— выигрыш на 
шаге (предполагается, что все 
положительны). Такой показатель или критерий эффективности называется мультипликативным.
Нетрудно убедиться, что любая задача с мультипликативным критерием может быть сведена к задаче с аддитивным критерием. Для этого достаточно, например, прологарифмировать выражение (10.2) и искать решение, обращающее в максимум логарифм величины W. Так как логарифм — возрастающая функция, то максимум логарифма соответствует максимуму величины W.
Однако для решения задач с мультипликативным критерием нет прямой надобности непременно логарифмировать его. Вся процедура динамического программирования может быть для этого случая построена непосредственно. В основу ее кладется такой выбор условного оптимального управления на каждом шаге, при котором обращается в максимум выигрыш на всех оставшихся шагах, равный произведению выигрыша на данном шаге и уже оптимизированного выигрыша на всех последующих шагах.
Основное функциональное уравнение динамического программирования для этого случая будет иметь вид:
а условие оптимальности последнего шага сохранится в том же виде, как при аддитивном критерии:
Вся процедура динамического программирования с мультипликативным критерием ничем не отличается от обычной, кроме того, что под знаком максимума стоит не сумма, а произведение.
Рассмотрим одну из типичных задач динамического программирования с мультипликативным критерием.
Распределение средств для повышения надежности технического устройства
Имеется техническое устройство S, состоящее из 
элементов, или узлов 
(см. рис. 3.39). Безотказная работа каждого элемента безусловно необходима для работы устройства S в целом.
Элементы могут отказывать (выходить из строя), причем независимо один от другого. Надежность (вероятность безотказной работы) всего устройства равна произведению надежностей всех элементов:
где 
— надежность 
элемента.
В нашем распоряжении имеются некоторые средства 
(в денежном, весовом или ином выражении), которые можно употребить на повышение надежностей элементов.
Рис. 3.39
Количество средств X, вложенное в приспособления, повышающие надежность 
элемента, доводит ее до значения
Все функции 
— неубывающие.
Требуется определить оптимальное распределение средств по элементам, Приводящее к наибольшей надежности устройства в целом.
Задача решается методом динамического программирования. Перед нами — задача с мультипликативным критерием. Выигрыш на 
шаге 
где управление 
— количество средств, вложенное в 
элемент.
Основное функциональное уравнение имеет вид:
где 
— условный оптимальный выигрыш, т. е. максимальная надежность устройства, составленного из всех элементов, начиная с 
и до 
если после 
шага, т. е. после обеспечения средствами предыдущих 
элементов, в нашем распоряжении остались средства К. Условное оптимальное управление на 
шаге 
— то количество средств, при котором достигается этот максимум.
Как и во всех задачах распределения ресурсов, где средства расходуются до конца, а выигрыш — неубывающая функция, оптимальное управление на последнем шаге состоит в том, чтобы выделить на этот шаг все оставшиеся средства:
При этом достигается условный оптимальный выигрыш, равный
Последовательным применением формулы (10.7) для 
как всегда, находим условные оптимальные управления
и условные оптимальные выигрыши
Первый шаг в данном случае оптимизируется не условно, а безусловно, так как исходное количество средств 
задано:
(10.10)
То управление
при котором достигается максимум (10.10), и есть безусловное оптимальное управление на первом шаге, а 
— безусловный опти мальный выигрыш, т. е. максимально достижимая данными средствами надежность устройства. Далее оптимальное управление строится по схеме:
