Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

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



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

В качестве примера рассмотрим задачу о надежности некоторого устройства, состоящего из 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; Прочитано: 311 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.007 с)...