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

[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]

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

В некоторых случаях фиксация одной дискретной переменной сильно сужает возможность варьирования других. К примеру, в задаче с сетью водосточных труб этот эффект возникает благодаря условию неубывания диаметров вдоль каждой ветви. Поэтому, скажем, равенством Xi=d,,., иногда однозначно определится х,.

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

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

7.7.2. ЦЕЛОЧИСЛЕННЫЕ ПЕРЕМЕННЫЕ

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

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

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

Рис. 7d. Слева изображена схема обычной ректификационной колонки; справа - схема ее непрерывной модели.

Условная схема обычной колонны изображена слева на рис. 7d. Внизу колонны имеются отверстия, через которые подается пар. Он поднимается вверх, частично конденсируясь. Конденсат стекает вниз и вновь попадает в испаритель.

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



На первый взгляд поставленная задача оптимизации по номеру ступени не имеет непрерывного аналога. Однако, если слегка переформулировать ее, такой аналог становится очевидньш. Надо для каждой ступени ввести свою целочисленную переменную со значениями {О, I}, имеющую смысл метки; если она равна единице, жидкость закачивается на этой ступени, если нулю - на другой. Потребовав, чтобы сумма новых переменных была единичной, мы получим задачу, эквивалентную исходной. При этом (-Ю целочисленную переменную Ki можно интерпретировать и как долю общего объема жидкости, поступающую на 1-ю ступень. Тем самым придается смысл непрерывной задаче, в которой условие цепочисленности х,-заменяется простыми ограничениями OXil, и если в ее решении при каком-то i окажется Xj==0.9, то скорее всего искомый номер равен I. На рис. 7е показана типичная картина распределения входного потока для непрерывной модели; наиболее вероятно, что оптимум в дискретной задаче достигается при Х4=1.

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

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

Рис. 7е. Типичное распределение входного потока по отсекам, получающееся из непрерывной модели.

ной F можно было бы добавить l/Sx?.

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

Желающим познакомиться с алгоритмами целочисленного линейного программирования мы рекомендуем обзорную статью Била (1977). Подробности программного воплощения схем дискретной оптимизации можно найти, в частности, в работах Джонсона (1978) и Джонсона и Пауэлла (1978).

Задача с ректификационной колонной решалась Сарджентом и Гаминибандарой (1976).

Когда дело доходит до разбора конкретных случаев,

все окажеется сложнее.

А.1ь6ер Камю. .The Notebooks: 1935-1942 (1963) Ты можешь ошибаться, адумать. что все правильно.

Джон Леннон и Пол Мак-Картни. «Wc can

work it out. (1965)

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

8.1. ПРИМЕНЕНИЕ БИБЛИОТЕЧНЫХ ПРОГРАММ

Б данном ра.зделе будут рассмотрены отдельные вопросы использования оптимизационного математического обеспечения в прикладных работах. Часто комментарии будут относиться к «гипотетической» библиотеке программ, включающей реализации всех методов нз гл. 4, 5, 6. По нашему мнению, она была бы «идеальной» иа современном уровне развития аппарата оптимизации, так что, говоря о ее применении, мы моделируем «идеальную» ситуа][ию. Существующие б11блн01еки бе;шее, и, хотя уже сегодня многие алгоритмы предыдущих глав доступны в виде хорошо документированных программных продуктов, возможности каждого отдельного поаьзователя, наверное, всегда останутся офаничен-иьши. Поэтому в главу включен разд. 8.1,5, где обсуждается, как использовать несовершенные средства.

8.1.1. ВЫБОР Л1ЕТ0ДА Когда оптимизационная задача поставлена, приходит черед выбирать метод ее решения. Прежде всего при эгом следует учесть основные характеристики целевой функЕЩИ и функций офаииче-ний. По ним все задачи разбираются на классы, каждому из которых отвечает своя фуппа предпочтительных алгоритмов (см, разд. 1.2). Однако речь идет именно о группе, так что проблема выбора остается и после определения класса задачи. На каком методе следует остановиться, зависит от того, какую информацию о производных можно предоставить, каков имеющийся объем ма-

13 п 2884

ПРАКТИЧЕСКИЕ ВОПРОСЫ



ШИННОЙ памяти и как соотносятся трудоемкости вычисления функций и алгебраических блоков сопоставляемых схем.

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

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

- модифицированные ньютоновские с вычислением вторых производных;

- модифицированные ньютоновские без вычисления вторых производных;

- квазиньютоновские с вычислением градиентов;

- квазиньютоновские без вычисления градиентов;

- методы сопряженных градиентов с вычислением первых производных;

- методы сопряженных градиентов без вычисления первых производных;

- метод многогранника.

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

Первенство держат ньютоновские методы (см. разд. 4.4 и 4.5.1). Использование информации второго поридка обеспечивает им высокие скорости сходимости и позволяет делать качественные выводы относительно найденного численного решения. Например, по соответствующей матрице Гессе можно провести анализ чувствительности (см. разд. 8.3.3). (Здесь уместно отметить, что квазиньютоновские схемы (см. разд. 4.5.2) аналогичных возможтюстей не предоставляют, поскольку не гарантируют точности вычисляемых приближений матриц вторых производных.) Еще одно важное преимущество модифицированных ньютоновских методов в том, что только они застрахован!,! от сходи.мости в седловые точки.

При переходе от аналитических значений вторых про!!зводных к их конечно-разностным оценка.м надежность ньютоновских методов и их эффективность в больш!!нсгве случаев практическ!! ие

ме!1яются. В основном сохраняется и состав вычислений. Иначе

дело обстоит с понижением порядка квазиньютоновских методов (см. разд. 4.6.2). Во-первых, даже хороший конечно-разностный квазиньютоновский метод может отказать в области малых g(,v). Во-в!орых, по составу вычисле!]нй он будет значительно отличаться от своего прототипа, рассчитанного на точные производ!1ые; в частности, в конечно-разностнь!х квазииыотоновских методах применяются своеобразнь!е процедуры одномерного поиска, критерии «существенного убывания» (см. разд. 4.3.2.1) и правила останова. Общие вопросы конечно-разностной аппроксимации первых производных подробно рассмотрены в разд. 8.6.

В приведенном ш,1ше списке самым.непритязательным в смысле требуемой информации относительно F является метод многогранника. Он же и самый ненадежнь!Й. Как уже бь!ло указано в разд. 4.2.1, этот и подобный ему методы следует использовать, только когда нет альтернативы.

На рис. 8а изображена схема выбора программы безусловной минимизации 1!3 типовой библиотеки математического обеспечения. Из нее видно, на чем следует остановиться в зависимости от характеристик F (доступности произ1юдных и размерности аргумента). Наряду с основными в схеме упоминаются и некие вспомогательные процедуры. О них речь пойдет в разд. 8.1.2.2.

Современный уровень развития аппарата поиска безусловного минимума при большом числе переменных не позвалиет давать столь четких рекомендаций по выбору методов, как дли задач малой размерности. В тех случаях, когда их удаегся применить, очень эффективными здесь оказь!ва!01СЯ дискретные ньютоновские методы (см. разд. 4.8.1). Знач!1тельно хуже своих обь!чнь!х аналогов работают квазиньютоновсктте схемь[ с сохранением слабой заполненности. Иногда удаегся успешно исполызовать технику сопряженных градиентов (особенно в сочетании с приемами предварительного улучшения обусловленности).

8.1.1.2. Выбор метода для задачи с линейными ограничениями. В основе каждого из рассмотреншлх в гл. 5 методов решения небольших задач с гладкими целевыми функциями и линейными ограничениями лежит какая-то из типовых стратегий поиска безусловного мнпи.мума. При хорошем воплощении метода именно она будет определять его качества. Поэтому здесь остается справедливой ранЖ!1ровка предыдущего раздела. Надо только отметить, что ди1Й)еренциацня становится более ощутимой. К примеру, присутствие в задаче простых ограничений на переменные для квазиньютоновских методов, как правило, не помеха, а о следующих за ними в списке методах сопряженных градиентов этого сказать уже нельзя.

Размер задачи. Существующие программы минимизации при линейных ограничениях распадакггся на две категории: одни рас-



[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.0008