Задача о защите поверхности

Вернемся еще раз к рассмотренной ранее (см. разд. 2.4.4 и 3.8.2) задаче о покрытии каждого из ш элементов поверхности одним из п материалов. Будем считать заданными матрицу затрат с элементами Су и матрицу потерь dy, а также допустимые суммарные потери D_max. Мы не будем вводить целочисленные переменные ху, как в разд. 3, и сводить задачу к линейному программированию, а постараемся уменьшить размерность задачи.

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

Рис. 4.19. Ценовой график для i-го элемента

Забудем о том, что у нас только несколько способов покрытия, и будем рассматривать зависимость Ci(dj) как кусочно-линейную. Это монотонно убывающая функция.

В качестве неизвестных выберем d, (i = 1,2, ..., m), то есть потери на i-м элементе. Для каждого элемента известны пределы изменения d_i? что дает простые ограничения dj¹ < dj < dj². Дополнительно имеем ограничение на суммарные потери

Других ограничений нет.

Целевая функция задачи

Здесь i = 1,2, ..., m номер элемента, a Cj(dj) — затраты при защите его избранным способом. Получили задачу нелинейного программирования, в которой не ш х п, а только ш переменных (по числу элементов). Простой вид ограничений позволяет легко вычислять проекцию градиента и решать вопрос об исключении ограничений из активного набора (см. разд. 4.4.2.1, примеры 1, 2 построения проекции). Целевая функция не имеет локальных минимумов, и в зависимости от конкретных данных с ней можно работать по-разному. Во-первых, можно рассматривать ее как кусочно-линейную и с помощью параболической аппроксимации сколь угодно точно приблизить все Cj(dj) функциями, имеющими непрерывные производные (см. разд. 4.7, рис. 4.18). Во-вторых, можно подобрать гладкие функции, аппроксимирующие Cj(dj) сначала на всем интервале dj¹ < dj < dj², а затем, по мере приближения к минимуму, на все более малых интервалах.

Рассмотрим более подробно применение методов нелинейного программирования для решения этой задачи. Прежде всего отметим, что функции Ci(dj) не обязательно кусочно-линейные. Если предполагается защита j-ro элемента некоторым материалом переменной толщины, то Cj(dj) — заданная гладкая монотонно убывающая функция. Рассматривая только конкурентоспособные способы защиты каждого элемента, приходим к выводу о том, что график зависимости Ci(dj) для произвольного элемента может состоять из нескольких гладких участков и в любом случае его с достаточной точностью можно представить в виде ломаной.

Ограничение заменим на

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

что усложняет задачу.

Матрица исходной системы линейных ограничений имеет следующий вид

Первая строка соответствует ограничению на сумму неизвестных, блок m х m, в котором по главной диагонали стоят —1, а все остальные элементы равны 0, соответствует ограничению на минимальные значения, а аналогичный блок с элементами, равными + 1, соответствует ограничению на максимальные значения неизвестных. Всего в матрице 2m + 1 строк и m столбцов.

Если рассматривать только активные ограничения, то для любого допустимого набора неизвестных остается первая строка и дополнительно не более одного элемента в каждом столбце, так как dj¹ < dj² для всех i.

Предположим, что мы вычислили g-антиградиент целевой функции и займемся построением его проекции р на граничное многообразие. Пусть ни одна из переменных в рассматриваемой итерационной точке не принимает предельного значения, то есть активно только ограничение на сумму переменных. Тогда, как показано в разделе 4.4.2.1, пример 2, для построения проекции нужно из каждой компоненты вектора g вычесть среднее арифметическое его компонент.

В точке минимума все компоненты проекции антиградиента равны нулю. Значит, все компоненты антиградиента равны между собой. Геометрически это означает, что если ни одна из переменных не равна минимальному или максимальному значению, то на ценовых графиках q (dj) нужно найти такие точки, чтобы все касательные были параллельны, а сумма абсцисс этих точек была равна D_max. Только такие точки, если они есть, дают решение задачи. Если таких точек нет, то неизбежно некоторые переменные в точке минимума примут минимальное (на пологих графиках) или максимальное (на крутых графиках) значение. Если предположить, что все ценовые графики линейны (и, конечно, не параллельны), то по крайней мере m — 1 переменная принимает предельное значение. Этот вывод согласуется с теорией линейного программирования, так как при линейных ценовых графиках мы имеем задачу линейного программирования и ее решение достигается в вершине допустимой области. При непараллельных ценовых графиках это решение единственно.

Предположим теперь, что в некоторой итерационной точке некоторые из переменных приняли предельное значение. Например, Ck = dk¹ и c_r = d_r². В этом случае матрица активных ограничений имеет следующий вид.

В этой матрице три строки и ш столбцов. В первой строке все элементы равны единице, во второй строке все нули, кроме —1 в к-м столбце, и в третьей строке все нули, кроме +1 в г-м столбце. Как построить проекцию р антиградиента g в этом и подобных случаях?

Очевидно, рк = 0 и р_г = 0, а сумма всех прочих компонент вектора р равна нулю, так как проекция принадлежит граничному многообразию. Поэтому нормаль п к граничному многообразию имеет следующую структуру.

И эта нормаль может быть представлена в виде линейной комбинации нормалей к соответствующим граничным линейным многообразиям с коэффициентами а, (3 и у. N = ani + рпг + упз. В силу этого имеем:

Складывая все равенства и учитывая, что сумма всех компонент вектора р равна нулю, получим Но

Поэтому Далее

. В левой части равенства в сумму не входят g_k и g_r. соответственно a = ^'gj/(m — 2), то есть среднему арифметическому всех компонент антиградиента, соответствующих переменным, которые не приняли предельных значений (неактивные ограничения). Для всех ненулевых Pj имеем pj = gj — a = gj — g'_cp. Получаем простое правило построения проекции в самом общем случае: компоненты, соответствующие предельным значениям переменных, обнулить, вычислить g'_cp — среднее арифметическое остальных компонент антиградиента и вычесть эту величину из соответствующих компонент антиградиента. Формула pj = gj — g_cp справедлива при любом числе переменных, принявших предельные значения. Из нее следует, что при использовании проекции антиградиента в качестве направления спуска на тех ценовых графиках, где «крутизна больше средней «точка смещается вправо, а где меньше — влево, при этом меняется и «средняя крутизна». Процесс останавливается, когда некоторые (возможно, и все) переменные примут предельные значения (минимальные или максимальные), а на всех остальных графиках касательные параллельны. При этом сумма переменных принимает заданное значение D_max. Остается рассмотреть вопрос: как исключать ограничения из активного набора? Ограничение можно исключить, если соответствующий ему коэффициент разложения нормали (разности антиградиента и проекции) по нормалям к граничным гиперплоскостям отрицателен. В нашем случае эти коэффициенты есть a, J3 и

у. Все компоненты антиградиента неотрицательны, следовательно, и среднее значение а > 0. Другими словами, ограничение на сумму переменных всегда должно выполняться как равенство, что ясно по смыслу задачи. Для переменных, принимающих минимальное значение, [3 = ос — gk- Условие (3 < 0 означает, что такое ограничение можно исключить из активного набора, если соответствующая компонента антиградиента больше среднего значения его компонент, соответствующих непредельным переменным. Для переменных, принимающих максимальное значение, у = g_r - а и такое ограничение можно исключить, если соответствующая компонента антиградиента меньше этого среднего значения. Заметим, что исключать несколько ограничений одновременно, вообще говоря, нельзя. Наиболее важно не «застревать» в левых точках ценовых графиков, так как им соответствуют максимальные затраты. Поэтому, вычислив соответствующие им величины (3, целесообразно (но не обязательно) найти «самую отрицательную» из них и строить проекцию так, как если бы соответствующая переменная не приняла минимальное значение. На следующей итерации эта переменная увеличится. Полученное правило исключения ограничений из активного набора фактически получено из системы A^Tu = g — р, где и — вектор, составленный из коэффициентов (а, (3, у) разложения нормали g-p по нормалям к граничным гиперплоскостям.

Если ценовые графики кусочно-линейные, то параллельные касательные могут получаться вблизи вершин ломаных, где требуется аппроксимация с непрерывной касательной (см. разд. 4.7).

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

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

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

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

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

Экспериментально установлено, что при числе элементов m = 400 и числе способов защиты каждого из них п = 45 использование алгоритма проекции градиента дает решение примерно за то же время, что и применение алгоритма динамического программирования и близкие результаты (по целевой функции 244.71 вместо 244.80).

Можно ожидать, что и при увеличении шипна порядок время счета будет вполне приемлемо даже при использовании таких процессоров, как PENTIUM 2, на котором проводились расчеты.

Мы подробно рассматривали задачу о защите поверхности для того, чтобы на ней продемонстрировать возможности и особенности различных методов.

Еще раз подчеркнем, что рассмотренная модель соответствует любой задаче оптимизации при наличии ограничений на каждую переменную в отдельности и на их сумму. К этой модели сводятся многие практические задачи, в частности задачи распределения ресурса одного типа между претендентами с различной эффективностью.