Подходы к решению задачи оптимального резервирования

Прежде всего для решения задачи оптимального резервирования используется метод неопределенных множеств Лагранжа:

Необходимо найти:

— неопределенный множитель Лагранжа; — ограничение.

Решив систему уравнений, можно найти необходимое количество резервных элементов.

Метод не дает однозначного решения: аргументы будут нецелочисленными (надо округлять), ограничения заданы в виде строгого равенства, а надо больше или равно.

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

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

В литературе говориться, что данный метод может «застревать», когда линии уровня сильно вытянуты (см. рис. 4.2 б), т.е. пробные шаги во всех направлениях не приводят к уменьшению значения целевой функции, и процесс вычисления прерывается вдали от точки минимума.

a	б

Рис. 4.2 Поиск минимума функции двух переменных
методом покоординатного спуска

Но так как надо минимизировать функцию надежности системы

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

Для решения задачи оптимального резервирования также используется метод динамического программирования.

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

где переход в состояние с более высокой надежностью (или более низкой вероятностью отказа Q) происходит с минимальными затратами по стоимости C,

здесь - риск нехватки резервных элементов.

Доминирующая последовательность строится по следующему правилу

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

Рассматриваем две подсистемы из 1-го и 2-го типа элементов. Характеристики элементов 1-го типа записываются в заголовках столбцов, а характеристики 2-го типа - в заголовках строк. На пересечении каждой строки и каждого столбца записываются суммы стоимостей C и вероятностей нехватки элементов q. (табл. 1).

Таблица 1.

Вначале проводим анализ элементов таблицы по ограничениям . Вычеркиваем те элементы, которые имеют значение стоимости большее, чем ограничение по стоимости Co и, чем ограничение по вероятности нехватки элементов Qo.

Делаем анализ на доминирование: рассматриваются оставшиеся клетки и сравниваем последовательно со всеми элементами (клетками). Если для каких-то двух векторов выполняется условие строгого доминирования, то т худший вычеркивается.

Вектор X₁ доминирует над вектором X₂, если вероятность нехватки элементов P(X₁) ³ P(X₂), а стоимость С(X₁) £ С(X₂) или вероятность нехватки элементов Q(X₁) £ Q(X₂) и стоимость С(X₁) £ С(X₂). Вектор X₁ строго доминирует над вектором X₂, если одно из перечисленных неравенств будет строгим.

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

Всего будет S-1 таблица, на последнем шаге вычислений ищется оптимальный вектор, у которого и будет минимальная вероятность отсутствия резервных элементов.