Многомерные задачи динамического программирования

Если размерность вектора S (число параметров состояния) больше 1, то говорят, что задача многомерна в смысле ДП. Многомерные задачи порождают определенные проблемы при реализации вычислительной схемы метода ДП.

Снижение размерности с помощью множителей Лагранжа

Введение множителей Лагранжа позволяет заменить исходную задачу рядом задач с меньшей размерностью вектора состояния.

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

12. Оптимизация надежности технических систем, систем распределения ресурсов.

Показатели надежности.

Для оценки надежности используют два вида показателей.

1. количественные показатели оценки надежности отдельных элементов;

2. комплексные показатели.

К количественным показателям оценки надежности относятся: безотказность, долговечность, ремонтопригодность, сохраняемость. Данные показатели позволяют проводить расчетно-аналитическую оценку количественных характеристик отдельных свойств.

Комплексные показатели используются при оценке и анализе в соответствии эксплуатационно-технических характеристик объектов заданным требованием. Все показатели надежности определяются как вероятностные характеристики. Соответственно, отказ будет являться случайным событием.

1. Вероятность безотказной работы.

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

Наработка на отказ – это величина, задаваемая и определяемая до запуска системы.

Фактическая наработка на отказ – это характеристика системы.

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

N₀ – число однотипных объектов, поставленных на испытание;

n(t) – число, отказавших объектов за время t.

На практике также применяются расчеты по вероятности отказов.

P(t)=1-Q(t)

- данная формула является статической оценкой вероятности отказа.

Кроме самой вероятности отказа используется плотность вероятности, которая определяет закон распределения заданной вероятности отказа объекта.

2. Плотность вероятности отказа – это производная вероятности отказа.

Плотность вероятности отказа зависит от закона распределения. Для расчетов используются следующие виды законов распределения:

1. – нормальное распределение

2 – экспоненциальное распределение

3 – β – распределение

3. Средняя наработка на отказ.

Наработка на отказ – это средняя продолжительность или объем работы объекта.

Понятие наработки отличается для восстанавливаемых и невосстанавливаемых объектов. Для невосстанавливаемых объектов наработка рассчитывается до первого отказа системы. Первый отказ является и последним. Для восстанавливаемых объектов наработка измеряется между двумя соседними по времени отказами. После каждого отказа производится восстановление системы.

В математическом виде средняя наработка на отказ – это математическое ожидание наработки объекта до первого отказа.

- для вероятности отказа

= >

Средняя наработка на отказ – это площадь, образованная кривой вероятности безотказной работы и системы координат.

Статическая оценка для средней наработки на отказ определяется по следующей формуле:

, где

N₀ – число однотипных не восстанавливаемых объектов;

t_j – наработка до отказа каждого объекта.

4. Интенсивность отказа условия, плотность вероятности возникновения отказов объекта.

Условие: до рассматриваемого момента времени отказ не наступил.

5. Статическая интенсивность отказов

, где

n(∆t_j) – число отказов однотипных объектов на интервале ∆t, для которого определяется λ;

N_срj – число работоспособных объектов в середине интервала ∆t_j

- вероятность безотказной работы на основе интенсивности отказов, получаемой в процессе экспериментального тестирования системы.

Пути повышения надежности.

1. Устранение влияния факторов, приводящих к снижению надежности аппаратуры.

2. Резервирование.

3. Сбор во время эксплуатации аппаратуры полных и достоверных данных об отказах и простоях аппаратуры.

Задача оптимизации надежности системы.

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

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

,

.

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

Классическим примером задачи распределения ресурсов является сбалансированная транспортная задача. С одной стороны, имеются поставщики с известными количествами груза, с другой - потребители с известными потребностями в грузе, при этом сумма потребностей равна сумме возможностей (баланс). Кроме того, для всех пар поставщик-потребитель даны затраты на перевозку единицы груза от поставщика к потребителю.