Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Все решаемые выше задачи имели критерий в виде аддитивной функции. Теперь возьмем задачу с иной целевой функцией и покажем применимость метода ДП для ее решения.
В качестве примера рассмотрим задачу о надежности некоторого устройства, состоящего из N последовательно соединенных блоков. Повышение надежности устройства обеспечивается включением дублирующих элементов в отдельные блоки. В общем случае ограничивающими факторами могут выступать затраты на дублирование, вес и/или объем устройства, надежность переключательных схем и др. Пусть основным ограничением являются затраты на дублирование Q и, кроме того, известны Сj - стоимость одного дублирующего элемента для блока j и jj (mj) - вероятность безотказной работы j -го блока с mj дублирующими элементами. Задача состоит в определении оптимальной стратегии дублирования в пределах выделенных средств.
Очевидно, что в качестве критерия следует взять вероятность безотказной работы всего устройства P, которая при последовательном соединении блоков равна произведению вероятностей этих блоков. Поэтому модель задачи будет иметь вид
, (9.25)
. (9.26)
В этой модели целевая функция является мультипликативной, что, однако, не мешает применению метода ДП. Действительно, и в критерии, и в ограничении можно выделить составляющие их функции, описывающие отдельные блоки, хотя операторы, примененные к этим частным функциям в (9.25) и (9.26), разные. Поэтому задача представима как многошаговая, а шагом является определение числа дублирующих элементов для одного блока. В последовательности шагов расположение блоков может не соответствовать реальной схеме их соединения в устройстве. Порядок расположения фиксируется исходя из соображений, которые были приведены в разделе 9.3.
Пронумеруем шаги, как и ранее, справа налево. Очевидно, что для принятия решения нужно знать свои возможности, которые в данной задаче определяются средствами на дублирование. Поэтому в качестве параметра состояния следует взять допустимый уровень затрат на дублирование q, который на любом шаге может принимать любые значения из диапазона [0, Q].
Теперь можно ввести последовательность функций { fk (q)}, k =1, N. Каждая функция имеет смысл максимальной вероятности безотказной работы k оставшихся блоков при допустимом уровне затрат на дублирование q:
. (9.27)
Для получения функционального уравнения рассмотрим k блоков, на дублирование которых можно затратить q средств. Если в k -й блок включить m k дублирующих элементов, а оставшиеся после этого средства (q-Сkmk) использовать оптимально на дублирование k -1 блоков, то с учетом (9.27) и последовательного соединения k -го блока с остальными k -1 блоками вероятность безотказной работы k блоков будет равна
[ jk (mk) fk -1(q-Сkmk)]. Максимизируя это выражение по m k, приходим к искомому рекуррентному соотношению
(9.28)
где [ q / Сk ] означает целую часть от q / Сk.
Условная оптимизация начинается с вычисления первой функции последовательности
и затем продолжается по формуле (9.28). Безусловная оптимизация проводится в обратном порядке, то есть от fN к f 1, с исходного состояния qN =Q и последующим пересчетом по уравнению состояния
qk -1 = qk - Сkmk.
Таким образом, мультипликативность целевой функции не изменяет процедуру динамического программирования. Отличие от ранее рассмотренных задач лишь в том, что выражение в правой части рекуррентного соотношения не аддитивное, а мультипликативное. Очевидно, что мультипликативность ограничения или одновременно ограничения и целевой функции также не вызовет осложнений.
Дата публикования: 2015-01-23; Прочитано: 313 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!