Задача с мультипликативным критерием

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

В качестве примера рассмотрим задачу о надежности некоторого устройства, состоящего из N последовательно соединенных блоков. Повышение надежности устройства обеспечивается включением дублирующих элементов в отдельные блоки. В общем случае ограничивающими факторами могут выступать затраты на дублирование, вес и/или объем устройства, надежность переключательных схем и др. Пусть основным ограничением являются затраты на дублирование Q и, кроме того, известны С_j - стоимость одного дублирующего элемента для блока j и j_j (m_j) - вероятность безотказной работы j -го блока с m_j дублирующими элементами. Задача состоит в определении оптимальной стратегии дублирования в пределах выделенных средств.

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

, (9.25)

. (9.26)

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

Пронумеруем шаги, как и ранее, справа налево. Очевидно, что для принятия решения нужно знать свои возможности, которые в данной задаче определяются средствами на дублирование. Поэтому в качестве параметра состояния следует взять допустимый уровень затрат на дублирование q, который на любом шаге может принимать любые значения из диапазона [0, Q].

Теперь можно ввести последовательность функций { f_k (q)}, k =1, N. Каждая функция имеет смысл максимальной вероятности безотказной работы k оставшихся блоков при допустимом уровне затрат на дублирование q:

. (9.27)

Для получения функционального уравнения рассмотрим k блоков, на дублирование которых можно затратить q средств. Если в k -й блок включить m _k дублирующих элементов, а оставшиеся после этого средства (q-С_km_k) использовать оптимально на дублирование k -1 блоков, то с учетом (9.27) и последовательного соединения k -го блока с остальными k -1 блоками вероятность безотказной работы k блоков будет равна

[ j_k (m_k) f_{k -1}(q-С_km_k)]. Максимизируя это выражение по m _k, приходим к искомому рекуррентному соотношению

(9.28)

где [ q / С_k ] означает целую часть от q / С_k.

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

и затем продолжается по формуле (9.28). Безусловная оптимизация проводится в обратном порядке, то есть от f_N к f ₁, с исходного состояния q_N =Q и последующим пересчетом по уравнению состояния

q_{k -1} = q_k - С_km_k.

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