Метод динамического программирования для знп с мультипликативной целевой функцией. Задача о надёжности.
Пусть имеется оптимизационная задача вида:
(1)
(2)
(3)
-задан (4)
З десь предполагается, что Fj(xj,yj)>0 для всех допустимых значений xj,yj. В этом случае для решения задачи (1)-(4) рекуррентные соотношения Беллмана имеют вид:
(5)
, (6)
При j=1 величина y1 задана, поэтому в этом случае решается только одна задача максимизации.
В результате решения оптимизационных задач в соответствии (5) и (6) получим условные точки максимума и функции , . Далее, делая обратный ход алгоритма, находим окончательное решение задачи и .
Также можно записать аналог рекуррентных уравнений, если известно не начальное, а конечное состояние объекта, т. е. задано значение . В качестве примера рассмотрим
Задачу о надежности.
Пусть конструируется электронный прибор, состоящий из трех основных компонентов. Все компоненты соединены последовательно, поэтому выход из строя одной из них приводит к отказу всего прибора. Надежность (вероятность безотказной работы) прибора можно повысить путем дублирования каждого компонента. Конструкция прибора позволяет использовать запасных блоков для каждого j-того компонента, т.е. каждый компонент может содержать до блоков, соединенных параллельно. Общая стоимость прибора не должна превышать С долларов. Если j-тый компонент имеет штук соединенных параллельно блоков, то его надежность составляет и стоимость . Требуется определить количество блоков в каждом j-том компоненте , при котором надежность прибора максимальна, а стоимость прибора не превышает заданной величины С.
Построение ММ. По определению, надежность F прибора, состоящего из N последовательно соединенных компонентов, каждый из которых включает параллельно соединенных блоков, равна произведению надежности компонент. Тогда ММ имеет вид:
(7)
(8)
, (9)
Из физического смысла задачи следует, что , >0 для всех допустимых .
Введем дополнительную переменную - количество средств, израсходованных на дублирование компонент 1,2,… j-1.Тогда можно записать:
(10)
(11)
Из (10) следует: . Тогда с учетом (9) область допустимых значений будет иметь вид , а рекуррентные соотношения Беллмана принимают вид:
(12).
(13)
Покажем применение рекуррентных соотношений Беллмана для решения задачи (7)-(9), решаемых в порядке . Проводя преобразования, аналогичные преобразованиям задачи о загрузке рюкзака, получим:
Здесь , есть область изменения при фиксированном .