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

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

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

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

здесь

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

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

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

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

Таблица 1.

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

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

Вектор X₁ доминирует над вектором X₂, если вероятность нехватки элементов

или вероятность нехватки элементов

Вектор X₁ строго доминирует над вектором X₂, если одно из перечисленных неравенств будет строгим.

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

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