Задача о защите поверхности.
Пусть имеется поверхность, разбитая на элементы Ai, Аг,..., А,п (или детали одного изделия), которые нужно покрыть (например, для защиты от коррозии или вообще от вредного воздействия внешней среды) одним из В1З2,..., Вп материалов (способов). Один и тот же материал (способ защиты) можно использовать для покрытия многих элементов, но на одном элементе используется только один материал (способ). Заметим, что вариант с использованием комбинации материалов на одном элементе можно рассматривать как новый материал (способ). Будем считать, что задана матрица затрат су, в которой m строк и п столбцов. Возможно любое соотношение между тип.
Решение этой задачи очевидно, если один из способов оказывается наиболее приемлемым среди всех других способов одновременно для всех элементов поверхности.
Для разных элементов (деталей) могут оказаться наиболее приемлемыми разные способы защиты. Кроме того, задача может осложняться, если каждый способ не даёт абсолютную защиту и с течением времени эксплуатационные качества изделия меняются (например, растёт вероятность выхода из строя). Если заданы для каждого элемента при каждом способе его защиты коэффициенты ру, учитывающие это обстоятельство, то появляется дополнительное ограничение на максимальную величину pjk, где jk- тот способ, который будет выбран для i- го элемента. Это условие шах /?ук <р, где величина р задана, означает, что в каждой строке матрицы неизвестных ху останутся только те, для которых это условие выполнено, так как с самого начала можно отбросить те способы защиты конкретного элемента, которые не соответствуют этому требованию. Выясняется, что такое дополнительное ограничение только упрощает задачу.
Но возможны и более сложные случаи. Например, ограничен не максимальный показатель потерь по каждому элементу, а сумма таких показателей. Возникает дополнительная связь между переменными, которая может быть записана в виде:
и все dy >0 заданные величины.
dij- показатель потерь при использовании j-oro способа для защиты i-oro элемента.
Ху =1, если для i-oro элемента используется j-ый способ, и х у =0 в противном случае. Dmax- максимальные (но допустимые) суммарные потери.
Рассмотрим эту задачу как задачу распределения ограниченного ресурса с целью применить метод динамического программирования. Ресурсом будем считать максимально допустимые суммарные потери Dmax, которые заданы. Задача аналогична уже рассмотренной в разд. 4.1, но имеет и особенности.
Этапы в нашей задаче соответствуют выбору способа защиты соответствующего элемента, причём как обычно нумерация элементов существенного значения не имеет. На каждом из этапов «система» может находиться в нескольких состояниях. Каждое состояние соответствует уже распределённому ресурсу, то есть уже допущенным потерям D из-за от неполной защиты всех уже рассмотренных элементов. Каждому состоянию соответствует и своё значение целевой функции, т.е. суммарная стоимость защиты уже рассмотренных элементов. Начальное состояние можно задать одной точкой, которой соответствуют нулевые потери D (ресурс не использован) и нулевые затраты. Состояния на каждом последующем этапе можно изобразить точками на вертикальных прямых (рис. 4.6)
Рис. 4.6. Схема выбора оптимального способа защиты
Поиск оптимального решения разобьём на следующие шаги.
1. На первой вертикали нижняя точка соответствует способу защиты первого элемента, при котором D (использованный ресурс) минимален, а верхняя точка соответствует способу, ведущему к максимальному D. При переходе снизу вверх от одной точки к другой потери D растут, а соответствующая стоимость защиты уменьшается. Если это не так, и существует способ защиты первого элемента, который стоит дороже, но даёт потери (требует ресурс) больше, чем один из рассмотренных, то такой способ защиты данного элемента должен быть исключён из рассмотрения, как неконкурентный, и соответствующая ему точка не получает своего места на первой вертикали.
Целесообразно предварительно для каждого элемента упорядочить способы его защиты по возрастанию D и исключить заведомо неконкурентные.
- 2. Далее, рассматриваем все возможности защиты второго элемента в комбинации с уже рассмотренными способами защиты первого элемента, то есть начинаем «заселять» вторую вертикаль. Для начала считаем, что выбрана нижняя точка на первой вертикали (самый дорогой способ защиты первого элемента) и рассматриваем в комбинации с ним все возможные способы защиты второго элемента. Получаем несколько точек на второй вертикали (состояний системы на втором этапе). Каждой точке соответствуют суммарные для двух элементов потери D и стоимость при соответствующих способах их защиты. Причём как и на первой вертикали при переходе снизу вверх потери растут, а стоимость (затраты) падает. Если для некоторой комбинации суммарные потери превышают допустимое значение Dmax, то такая комбинация исключается и соответствующая ей точка на вертикаль не помещается. Этого правила будем придерживаться при рассмотрении всех возможных комбинаций на всех последующих этапах.
- 3. Переходим к рассмотрению всех возможных способов защиты второго элемента в комбинации не с первым, а со вторым способом защиты первого элемента (пунктирные линии на рис. 4.6). Может оказаться, что суммарные потери для одной из таких комбинаций совпадают с суммарными потерями для одной из уже рассматривавшихся комбинаций (рис. 4.6, точка А на вертикали 2). Это означает, что одного и того же состояния на втором этапе система может достичь разными путями. Дальнейшее поведение системы при переходе из этого состояния не зависит от того, как она попала в это состояние. Дальнейшее поведение в нашей задаче это распределение оставшегося ресурса, то есть допустимых потерь при выборе способов защиты оставшихся элементов. На этот дальнейший выбор никак не может повлиять то, как были выбраны способы защиты первых двух элементов, если они привели к одним и тем же потерям, то есть привели систему в одно и то же состояние.
В полном соответствии с принципом оптимальности Р.Веллмана [3] из нескольких путей, приводящих систему в одно и то же состояние, в данной задаче можно оставить только один путь, для которого суммарные затраты (целевая функция) минимальны. Для каждой точки на вертикали 2 сделаем такой выбор и запомним соответствующую связь с вертикалью 1.
Если новая точка не совпадает ни с одной из уже имеющихся на вертикали 2 (на рис. 4.6 точка М между точками В и С), то получено новое состояние системы на втором этапе, и число таких состояний должно резко возрастать при переходе от этапа к этапу. Как следствие, редкие случаи отбраковки вариантов казалось бы должны привести к неэффективности алгоритма динамического программирования уже при числе элементов и способов их зашиты в несколько десятков. Но это не так.
Дело в том, что в данной задаче можно сравнивать и отбраковывать состояния системы, а не только пути достижения любого состояния. Другими словами, новая точка на вертикали 2 может не получить своего места или заменить одну (или даже несколько) точек, если она и не совпадает ни с одной из них. Рассматриваемой новой точке М на вертикали 2 соответствуют потери большие, чем точке В, но меньше, чем точке С. Если при этом суммарные затраты, соответствующие точке М, больше, чем затраты, соответствующие точке В, то это означает, что состояние М проигрывает состоянию В «по всем показателям». Возникает вопрос: а нужно ли вообще рассматривать такое состояние, может ли оно попасть в оптимальную траекторию или, другими словами, может ли комбинация способов защиты двух элементов, соответствующая точке М, конкурировать с другой комбинацией, соответствующей точке В? Очевидно нет и вот почему. Возьмём оптимальный путь из точки М до конца, то есть оптимальное распределение оставшегося ресурса при условии нахождения в точке М. Иначе говоря, рассмотрим оптимальный вариант защиты оставшихся элементов при условии, что для первых двух элементов выбраны способы защиты, такие, что суммарные потери соответствуют точке М. Но ничто не мешает взять точно такие же способы защиты оставшихся элементов при условии, что на первых двух элементах выбраны способы защиты, соответствующие попаданию в точку В. При этом и суммарные потери и затраты па оставшихся элементах одни и те же, что для точки М, что для точки В. Но на первых двух элементах путь в точку В имеет преимущество (и потери меньше и затраты меньше), поэтому в такой ситуации нет смысла запоминать точку М.
Предположим далее, что суммарные затраты Z на первых двух элементах для точки М меньше, чем для точки B(Zm 4. Аналогично поступаем при переходе на вертикаль 3, а затем и на все последующие вертикали. Это правило отбраковки заведомо неконкурентных состояний, конечно, сокращает и число состояний на каждом этапе и число запоминаемых связей. Однако в общем случае и оно не спасает от резкого роста числа состояний уже при числе элементов (этапов) в несколько десятков. Это означает, что на интервале допустимых потерь (от нуля до Dmax) накапливается большое число точек. Если это число достигает 10000 и более, то возникает вопрос, а нужно ли хранить столько точек, велика ли разница между соответствующими им состояниями? Как только эта разница в потерях (расстояние между соседними точками на вертикали) становится существенно меньше погрешности определения этих потерь, из двух смежных точек можно оставить одну. При достижении последней вертикали, то есть при завершении рассмотрения всех способов защиты последнего элемента в комбинации с уже рассмотренными способами защиты всех остальных элементов на последней вертикали будут помещены все возможные точки (состояния). Каждая из них не нарушает ограничение на D и соответствует суммарному значению потерь D и суммарным затратам при соответствующей комбинации способов защиты элементов. При этом верхней точке соответствует максимальные (но допустимые) суммарные потери и минимальные суммарные затраты. Эта точка и даёт решение задачи. Вторая сверху точка на последней вертикали даёт меньшие потери, но большие затраты, чем оптимальная (верхняя) точка. Это так называемое субоптимальное решение. С учётом всякого рода дополнительных соображений, это решение может быть признано лучшим, чем формальный оптимум. Например, разница в затратах незначительна, а по потерям весьма существенна, так что для оптимальной точки потери достигают допустимого максимума, а для субоптимальной точки имеется «запас прочности». Рассмотрим при каких исходных значениях числа элементов m и числа способов их защиты п может быть решена задача на современых доступных компьютерах с точки зрения требуемой памяти. Для каждой точки на каждой вертикали надо хранить 3 числа: суммарные потери на пройденных этапах, суммарные затраты и связь с предыдущей вертикалью (для восстановления траектории при обратном развороте), то есть всего порядка 3km чисел. Здесь к число точек на вертикали. На первой вертикали п точек, а далее это число растёт и определяется не только числом п, но и конкретными данными по затратам и потерям для различных элементов и способов их защиты. Будем рассматривать наихудший случай и примем число к равным максимальному числу точек на вертикали, определяемому требуемой точностью расчётов. Пусть к=1000. Тогда даже при т=1000 требования к оперативной памяти отнюдь не чрезмерные (не более 12 мегабайт), так что с этой точки зрения любое из чисел шик можно увеличить на порядок. Эта оценка справедлива, если при «отсеве» несовпадающих точек их различие по D столь мало, что из-за ошибок в исходных данных невозможно отдать предпочтение ни одной из них. Другими словами, дискретность существенно меньше погрешности исходных данных. Эта же оценка справедлива и при наличии «естественной дискретности», и соответствующей (меньшей) величине дискрета, используемого при отбраковке. Однако реально всё может быть несколько сложнее и мы вынуждены использовать более крупные значения дискрета для избежания непреодолимо быстрого роста числа точек и, как следствие, огромных затрат по памяти и времени счёта. Эта ситуация возникает из-за нелинейности соответствующих зависимостей, которая приводит к тому, что различным способам защиты соответствуют практически равные потери. В этом случае принять значение дискрета как минимальную разность потерь при защите конкретного элемента различными способами означает допустить быстрый рост количества состояний уже за 10-15 этапов до неприемлемых величин. Во избежание накопления ошибок и пропуска оптимального варианта отбраковка производится только в случае, когда в пределах заданного дискрета, который больше «естественного», находится не две, а три точки. При этом остаются крайние из них. Отслеживая на каждой вертикали достижимое минимальное и максимальное значение по D и поделив их разность на заданную точность поиска (дискрет), получаем число дискретов. Количество точек не более, чем вдвое превышает полученное (переменное) число дискретов. По нему и рассчитывается выделяемая память. Численные расчёты для задач, в которых m было несколько десятков и дискрет 0.000 Ютах показали высокую эффективность описанного алгоритма и с точки зрения времени счёта. При т=400, числе способов защиты n=45, Dmax =0.001 и дискрете 0.000 Шшах, т.е 0.0000001 задача решалась за 1.5 мин на компьютере с тактовой частотой 200 мГц. Сравнение состояний может выполняться не по потерям, а по затратам. Это особенно эффективно, если по затратам имеет место «естественная дискретность», тогда не приходится прибегать к каким либо допущениям и появляется возможность найти абсолютный оптимум. Отметим ещё одну важную особенность: в данной задаче сравнительно просто может быть найдено приближённое решение и тем самым оценка сверху минимальных затрат следующим образом. Теперь при рассмотрении комбинаций способов защиты элементов (при заполнении очередной вертикали) можно исключать те из них, для которых затраты больше, чем Стах (рис. 4.6). Кроме того, имеется возможность проведения расчётов в два этапа. Этот приём предложен Р.Беллманом [3,4] и состоит в том, что на первом этапе расчёты ведутся с использованием регулярной сетки с крупным шагом, а затем относительно полученного решения в узкой полосе разбивается регулярная сетка с мелким шагом. Известно, что при таком способе решения многоэкстремальных задач может быть пропущен глобальный экстремум [4]. Для нашей задачи эту идею без риска пропустить глобальный минимум можно использовать двумя путями. Во-первых, исходную поверхность сначала разбить на относительно малое число элементов. Решить задачу как изложено выше без использоания регулярной сетки состояний вообще. Затем полученное значение затрат использовать как Стах после разбиения поверхности на большее число элементов с применением того же алгоритма оптимизации для тех же способов защиты поверхности. Во-вторых, при однократном разбиении поверхности на большое число элементов определить ориентировочное значение Стах как указано выше посредством вычисления dcp- Dmax/m и соответствующих затрат для каждого элемента. Выполнить расчёт для крупного дискрета по D или по С, так чтобы в полосе от Стах до Dmax (см. рис. 4.6) находилось не более 10000 точек. Вокруг полученного решения не требуется разбивать какую-либо сетку, а просто повторить расчёт с уточнённой по результатам счёта оценкой Стах и мелким дискретом. Приведенные выше данные о расчётах для т=400 получены по программе, в которой ни один из изложенных приёмов сокращения используемой оперативной памяти и времени счёта не применялся. Однако эти приёмы позволяют в несколько раз сократить требуемую память и время счёта и реализовать расчёт при числе элементов несколько тысяч и числе способов защиты по каждому элементу в несколько сотен. Поэтому в дальнейшем программа была усовершенствована. Так, только использование приближённого решения (при равномерном распределении ресурса) позволило сократить время счёта в той же задаче при т=400, п=45 с 1.5 мин до 23 сек. Если средние потери меньше минимальных для некоторого элемента, то усредняются только максимально допустимые потери за вычетом суммарных минимальных потерь, после чего определяется приближённая оценка для Стах.
