Главная  Методы условной оптимизации 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [ 61 ] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

труднения со сходимостью. Они оказались настоящим сюрпризом, поскольку применялся весьма эффективный алгоритм, от которого ждали, что он будет сходиться квадратично. Чтобы определить источник затруднений, одну и ту же задачу решили с нескольких начальных приближений: всякий раз получался новый набор {hi), {Sih } и {/in }, но все комплекты {pj,j } оказались одинаковыми. Это заставило внимательно проанализировать формулировку задачи, и выяснилось, что она сильно вырождена. Из (7.20) видно, что величина Pijj, не изменится, если, например, hi и gjk заменить иа а/у и gjbfa, где а - некоторое ненулевое число. Оказалось, что Офаничения тоже инвариантны к подобным заменам. Поэтому все системы уравнений для расчета направлений поиска получались линейно зависимыми, и не будь используемый алгоритм так надежен, он вообще не справился бы с задачей. После того как все это было обнаружено, вырождение легко было устранено дополнительными нормировочными условиями типа 2/fi~-

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

7.6.2. ИСПОЛЬЗОВАНИЕ ОГРАНИЧЕНИЙ С ДОПУСКАМИ Ограничения-равенства в оптимизационных задачах бывают разного происхождения. Нередко они вытекают из самого смысла переменных; например, если [xt) суть какие-то доли или вероятности, то по определению должно быть х- 1. В таких случаях говорят об

«истинных» равенствах, подчеркивая тем самым, что в искомом численном решении их надо соблюсти с максимально возможной точностью. Однако иногда в виде равенств формулируют ограничения, которые можно было бы ставить и не столь жестко, т. е., по существу, эти равенства точно выполнять ие обязательно (скажем, известно, что описываемые связи включают некую неопределенность). Фактически ими заменяют «узкополосные» двусторонние неравенства, которые принято называть ограничениями с допусками. Так, например, требуют, чтобы было

ох=Ь,

хотя в действительности достаточно удовлетворить условиям

Ь-8j<oxsgb+E„ (7.21)

где е, и - малые, но все же ощутилю отличные от нуля папожи-тельные величины (сказанное применимо и к нелинейному случаю).

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

Приведенные соображения и некоторые полезные преобразования мы проиллюстрируем на примере несколько упрощенной (ради наглядности) постановки задачи, которая возникла при проектировании конвертера выхлопных газов автомобильного двигателя. Требовалось решать систему уравнений, описывающих химические реакции в конвертере. Она распадается на две подсистемы: нелинейные уравнения для скоростей реакций и линейные уравнения балансов масс. Всего рассмотрим 13 уравнений (восемь нелинейных и пять линейных).

Переменными {х, ., х„) являются парциальные давления следующих газов: пропана, угарного газа, окиси азота, окиси углерода, кисюрода, водяного пара, а:дата и водорода. Естественно, что они должны быть неотрицате1Ьнымн, т. е. в разумном решении должно получаться XtO, i = l, . .., 8. Восемь нелинейных уравнении с параметрами {Ki, .. , К,}, имеющими смысл констант реакций, таковы:

-А:,=Л(х)=0, (7.22)

XlAe

i?-:.=f.()=o,

-K, = f,M = 0, -/<. = f, (x) = 0.

(7.23) (7.24)

(7.25) (7.26) (7.27) (7.28) (7.29)

Хг Vb

Линейные балансовые уравнения с параметрами {а,-, ..., а,}, представляющими собой парциальные давления реагентов на выходе из двигателя, выглядят следующим образом:

Баланс кислорода х, + х, + 2х, + 2х„ + х„-а,-а,-2а,-2а-а. = /, (х) = 0. (7.30)

Баланс углерода

Зх,-Ьх,-1-х.-Зс,-о,-о. = Ло (•«) = 0. (7.31)



Баланс водорода

Sxi + 2х, + X, - 8а,-2с-а, == „ М = О- <7.32) Баланс азота

Хз + 2х,-а,-2й,=Л.М = 0. (7.33)

Общий баланс

Jx,-o,=/„(x)-0. (7.34)

Обычный метод решения переопределенной системы уравнений - искать минимум суммы квадратов их невязок. В нашем случае он

приводит к задаче

найти min 2 R(x),

*eS1- . = 1

(7.35)

в которой разнородные уравнения (7.22)-(7.34) «свалены в одну

7 o/°P°™-. •"" естественно разделить их. например заменить (7.35) задачей

найти min 2 f] (х)

(7.36)

при ограничениях Д.(х) = 0, 19..... 13.

Однако н ее нельзя признать удачной. Дето в том, что восемью описанными реакциями отнюдь не исчерпывается их полный список (около 30 второстепенных процессов отброшены), и поэтому настаивать на точном соблюдении равенств (7.30)-(7.34) рискованно: можно получить бессмысленное решение с отрицательными компонентами. Чтобы избежать этого, следовало бы вместо (7,30)-(7.34) поставить соответствующие ограничения с допусками, отражающими «материалоемкость» неучтенных процессов.

В некоторых случаях ослабление ограничений-равенств дает удовлетворительную постановку задачи и больше никаких преобразований не требуется. Рассматриваемый же пример сложнее и требует дополнительного масштабирования. Прежде всего оно необходимо из-за огромного разброса констант реакций [Ki} (в частности, Ki имеет порядок 10»°). Один нз приемов, который может помочь,- заменить /j(x), i=l, .. ., 8, функциями

fi=ln(/i(x)-l-Ki)-ln Ki и минимизировать сумму fl(x). Однако всех проблем это преобразование не решает. Остается еще как-то избавиться от чрезмерной чувствительности целевой функции к ма-пым вариациям переменных в окрестности нуля - ведь оно сильно меняется, скажем, при переходе от Xi=10~ к х,=10~", ВТО время как для любого стандартного алгоритма такие значения наверняка будут «эквивалентными».

Чтобы получить менее чувствительную функцию, необходимо сделать нелинейную замену переменных, т. е. приходится терять линейность ограничений (7.30)-(7.34). К счастью, эту утрату удается скомпенсировать тем, что линейными станут функции f j. Для этого надо взять

х, = еЧ (7.37)

Заметим, что попутно автоматически обеспечивается неотрицательность Xj.

Проиллюстрируем эффект замены (7.37) на функциях f, и /,,. Первая преобразуется в

а вторая в новых переменных будет выглядеть так:

L (у) = 6еУ + 2еУ + еУ-Ь,=:0.

Аналогичная (7.36) задача теперь формулируется следующим образом:

найти min Е /1 Ш)

(7.38)

при ограничениях Fi(y)=0, t=l,..., 8.

Важно подчеркнуть, что в решении (7.38) (еслн оно существует) [ (у), вообще говоря, будут ненулевыми, и поэтому, если требуется точное соблюдение равенств (7.30)-(7.34), такая постановка не подходит.

Ограничения задачи (7.38) представляют собой систему из восьми лит{ейных уравнений с восьмью неизвестными, причем ее матрица вырождена. На совместность таких уравнений прн оцениваемых экспериментально и, следовательно, неточных константах {Ki) рассчитьшать нельзя. "Поэтому их надо заменить ограничениями с допусками, подбираемыми в соответствии с оценками погретпностей измерения {Ki)- Интересно отметить, что при «слегка» ошибочных {Ki} уравнения в (7.38) тоже будут лишь «слегка» несовместными.

Замечания и избранная библиография к разделу 7.6

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

.Питература по применению методов оптимизации в конкретных исследованиях слишком обширна, чтобы сколько-нибудь полно цитировать ее здесь. Выборочные сведения читатель найдет у Брак-кена и Мак-Кормика (1968), а также в сборниках конспектов статей



ПОД редакцией Авриия, Рейкарта и Уайлда (1973), Балинского и Лемарешаля (1978), Авриеля и Дембо (1979). Вопросы численного моделирования, возникающие в контексте технической оптимизации, хорошо изложены в книге Уайлда (1978).

7.7. ЗАДАЧИ С ДИСКРЕТНЫМИ И ЦЕЛОЧИСЛЕННЫМИ ПЕРЕМЕННЫМИ

Среди прикладных задач нередко встречаются такие, в которых наряду с условиями вида равенств и неравенств ставится требование, чтобы значения некото];ых (или всех) переменных принад-лежалн конечным множествам. Эти переменные называют дискретными или целочисленными. Примеров можно привести сколько угодно; в частности, х может иметь смысл характеристики конструкции (типа мощности насоса, размера балки и т. д.), выпускаемой в определенной номенклатуре, или служить каким-то счеч-чиком (скажем, числа поездок коммивояжера).

Непосредственным применением стандартных методов минимизации к задаче с дискретными переменными ее, как правило, не решить (исключение составляет ряд особых случаев, когда оптимальные значения переменных, освобожденных от требования целочисленности, удовлетворяют ему автоматически). Здесь используется своя техника. Наиболее развит аппарат решения целочисленных задач, целевые функции и функции ограничений которых линейны; больишя часть соответствующих методов опирается на схему «ветвей и фаниц». Для некоторых других специальных задач удается успешно применять мето.ты динамического профаммирования. Мы, однако, не будем касаться ни первых, ни вторых, а офаничимся кратким обсуждением общего случая с нелинейными офаниченнями и смесью непрерывных дискретных переменных.

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

7.7.1. ПСЕВДОДИСКРЕТНЫЕ ПЕРЕМЕННЫЕ

Рассмотрим задачу проектирования городской сети сброса дождевых вод. Содержательная постановка такова; иа некой площади известным обра;юм размещены сточные люки (размещение диктуется потребностями доступа и геофафней улиц); они связываются между собой прямолинейными трубами; к каждому люку подходит несколько входных труб (идущих от вышераспо.южснных точек) и одна выходная; никаких насосов не предусматрииается, т е. вода будет течь только под действием си.пы тяжести. Надо подобрать характеристики сети гак, чтобь! обеспечить ей опреде-

ленную пропускную способность и при этом условии минимизировать затраты на ее строительство.

Перейдем теперь к описанию математической постановки задачи. Переменными являются диаметры трубопроводов и углы их наклонов к гори.зонтали. Офаничения таковы: угол наклона каждого трубопровода должен лежать в заданных пределах (определяемых в соответствии с топографией поверхности и желаемой пропускной способностью); при движен}Ш «сверху вниз» вдоль каждой ветви сети диаметр последующего трубопровода должен быть не меньше диаметра предыдутцего; интенсивности потоков в трубопроводах при некоторой расчетной «стационарной» нафузке на сеть (нелинейные функции диаметров и углов) должны иметь значения из фиксированных диапазонов. При этих ограничениях минимизируется сумма стоимостей труб и затрат нв рытье траншей (прочие издержки строительства относительно малы, и ими можно пренебречь). Следует отметить, что указанные стоимости и затраты являкл-ся взаимодополняющими: чем меньше диаметры труб, тем они дешевле, но тем большие углы и соответственно тем более глубокие траншеи понадобятся, чтобы обеспечить требуемую пропускную способность.

Казалось бы, поставленная задача относится к классу нелинейных задач на условный экстремум с непрерывными переменными. Однако на самом деле это не так: промышленность производит трубы определенных диаметров, и поэтому значения отвечающих им переменных должны выб41раться из конечного мнояе-ства. В данном случае можно говорить о псевдодискретности - задача имеез- вполне осмысленное решение и в непрерывной постановке. Просто оно не реализуемо по чисто внешним причинам.

Методы, применяете к задачам с псевдодискретными переменными, исходят из предположения, что требование дискретности не сильно сказывается на решении. В частности, в примере с проектированием сточной сети скорее всего так и будет (поскольку номенклатура выпускаемых труб достаточно широка). Близость же «непрерывного» оптимума к «дискретному» позволяет опереться на стандартный аппарат минимизации.

Поиск X* в задаче с псевдодискретиыми переменными можно начать с решения ее «непрерь[вного аналога». Это даст точку х, для которой F(xXf(x*). Если значение х, в действительности должно выбираться среди di, ds, . . ., d, и d,<xf<dj+j, то затем естественно зафиксировать Xi на d,, или dg+i (обычно берут ближайшую к xJ величину), найти минимум F по переменным Хе, . . ., х„, считая их непрерывными, выбрать значение счедую-щей дискретной переменной и т. д. При этом каждая последующая минимизация будет фебовать меньше усилий, чем предыдущая (хотя бы потому, что понижается размерность). В конце концов будут зафиксированы значения всех дискретных переменных и определится некая допустимая точка исходной задачи х.



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [ 61 ] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

0.001