Задача выбора оптимальной комплектации

Рассмотрим ту же задачу повышения надёжности системы из N элементов, но не путём резервирования, а путём выбора наилучшей комплектации. Итак, пусть имеется возможность выбора каждого элемента Xi системы из нескольких вариантов его изготовления (приобретения). Каждому варианту соответствует заданная вероятность отказа p(xi), стоимость (вес, объём, энергопотребление) или другая характеристика fi(xi). Требуется подобрать такую комплектацию системы, чтобы вероятность её отказа была минимальна, а суммарная стоимость не превышала заданной величины R. Другими словами: найти минимум Р(х), где x(xi,X2,...,xn) неизвестный вектор, компоненты которого Xi= 1,2,... ,Xi удовлетворяют ограничению

Целевая функция имеет вид

Задача может быть решена по методу динамического программирования с использованием множеств Парето. Если предположить, что все pi(xi)«l и пренебречь произведением вероятностей в (5.9), то получим задачу (5.1, 5.2) с целевой функцией

Эта задача может решаться как и задача (5.1, 5.2) с использованием комбинированного алгоритма, в котором для определения нижней и верхней границ оптимума применяется новый алгоритм спуска - подъёма.

Анализируя задачу (5.1, 5.2), видим, что перемена местами функций fi(xi) и g(xi) не меняет математической сущности задачи. Поэтому рассмотренные в разделах 5.3 и 5.4 задачи на минимум вероятности отказа системы при ограничении на её стоимость (вес, объём и т.д.) могут быть переформулированы как задачи минимизации стоимости (веса, объёма и т.д.) при обеспечении заданной надёжности. В любом случае задача рассматривается как двухкритериальная и ведётся по-шаговое построение одних и тех же паретовских множеств с последующим удалением части бесперспективных паретовских точек.

Большой объём сопоставительных расчётов при решении задачи (5.1,5.2) с использованием различных алгоритмов позволяет сделать следующие выводы.

  • 1. Для решения задач рассматриваемого класса классические алгоритмы динамического программирования можно рассматривать как устаревшие.
  • 2. Наиболее перспективным из рассмотренных является комбинированный алгоритм, в котором следует для построения двусторонних оценок оптимума использовать новый алгоритм спуска- подъёма, (разд. 5.2, программа П4).
  • 3. При использовании комбинированного алгоритма для решения задач большой размерности целесообразно искать приближённые решения, прекращая счёт при малости относительной ошибки поиска минимума е. Для этого можно задать её приемлемое значение. Но вместо этого для решения задач большой размерности можно задать заведомо малое 8, вывести на экран по-шаговые значения рекорда Е, нижней границы Н и относительную ошибку (Е-Н)/Н и прекращать счёт с учётом текущих результатов и затраченного времени.
  • 4. При росте значений ресурса R и числа его потребителей п возможно как увеличение, так и уменьшение времени счёта. Фактически алгоритм П4, если и не преодолевает полностью «проклятие размерности», то делает его действие избирательным.

Задача (5.1, 5.2) и сводящиеся к ней задачи обеспечения надёжности и управления запасами, рассмотренные выше, показывают, что алгоритмы, использующие множества Парето, хотя и не универсальные, как и динамическое программирование в целом, но могут найти широкое практическое применение.

В комбинированных методах алгоритм спуска-подъёма можно использовать вместо алгоритма спуска в различных схемах, предложенных в [1] для решения задачи (5.1,5.2) при наличии нескольких ограничений вида (5.2).

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >