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

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

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

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

здесь

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

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

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

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

Таблица 1.

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

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

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

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

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

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

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

Дата добавления: 2015-04-30