Н.Н. Калиткин - Численные методы (1133437), страница 49
Текст из файла (страница 49)
Регуляризация линейного программирования. Задача линейного программирования часто оказывается плохо обусловленной. Так, себестоимость единицы продукции или норм расхода сырья на разных заводах не должна сильно отличаться. Поэтому даже заметное перераспределение заказов между заводами слабо влияет на суммарную стоимость продукции. Соответственно малая вариация суммарной стоимости приводит к большой вариации распределения заказов. По тем же причинам небольшое изменение себестоимости или других показателей на отдельных заводах сильно меняет оптимальный план, так что решение очень чувствительно к вариациям коэффициентов.
А сами эти коэффициенты не вполне точно известны. Поэтому на практике задача (41) нередко оказывается настолько плохо обусловленной, что не удается даже проверить, совместна ли система дополнительных условий, т. е. может ли существовать решение поставленной задачи. ПОИСК МИНИМУМА !гл уп Для регуляризации задачи линейного программирования воспользуемся тем же способом, что и для решения плохо обусловленных линейных систем (см.
главу Ч, З 1). Будем искать нормальное решение х, т. е. наименее уклоняющееся от некоторого заданного вектора х,. Обычно в качестве х, берут ранее составленный план. Тогда регуляризованное решение будет почти не уступать оптимальному по величине й(х) и в то же время мало отличаться от старого плана, так что перестройка планов будет небольшой. Возьмем исходную задачу в канонической форме (44) н рассмотрим формулы регуляризации. Надо минимизировать положительную функцию Е(х) или, что то же самое, функцию ь'(х). Дополнительным условием служит система уравнений Ах=Ь с прямоугольной матрицей. Поскольку коэффициенты системы известны не точно, то достаточна найти приближенное решение.
Тогда требование приближенного соблюдения этих условий эквивалентно введению штрафной функции р!!Ах — Ы!', т. е. постановке следующей задачи: 1Р (х)+ р!!Ах — Ы!з = пнп, р) О. (50) Здесь норму будем определять, как !!у!!'=(у,у); тогда все минимизируемые выражения будут квадратичными функциями х, что облегчит вычисления. Заметим, что пока мы не учитывали требования неотрицательности компонент решения. Условием близости решения к заданному вектору можно считать малость величины !!х — х,!! или, в более общем виде, малость величины ь) [х] = ~ч~ р, (х1 — х1О)', р; -> О. (51) 1=.
1 Зту величину также можно считать штрафом и прибавлять в качестве дополнительного слагаемого в левую часть (50); тогда получаем регулярнзованную задачу М[х) =ЕР(х)+р!!Ах — Ы!'+Х(2 [х) = ш!п, рХ) О. (52) Отклонение регуляризованного решения от х, не должно быть большим. Но х, есть некоторый план; следовательно, его компоненты неотрицательны. Значит, если у решения, найденного из условия (52), и будут отрицательные компоненты, то небольшие по абсолютной величине, что в итоге несущественно. Поэтому при решении регуляризованной задачи (52) условия неотрицательности (44б) обычно можно не принимать во внимание.
Величина М [х1 является квадратичной формой, так что нахождение ее минимума .(путем обычного дифференцирования по координатам) сводится к решению системы линейных уравнений. Поскольку задача регуляризована, то полученная линейная система 223 $4! минимизлция Фэнкциоиллл будет хорошо обусловлена; тогда ее решение даже при большом числе неизвестных )У 200 легко вычислить методом исключения Гаусса.
Более сложен вопрос о выборе параметров регуляризации р и Х. Величину р подбирают так, чтобы для найденного регуляризованного решения выполнялось условие зАх — Ьз = 1~6Ь!(, где 6Ь— допустимая погрешность вектора Ь, связанная с тем, что его компоненты и коэффициенты матрицы А известны неточно. Аналогичным образом величину Х связывают с погрешностями коэффициентов с; и с допустимыми отклонениями функции г, (х) от своего минимального значения. При численном решении задачи (52) приходится. находить серию регуляризованных решений, соответствующих разным значениям параметров р и Х, и выбирать оптимальные параметры. Несмотря на это, общий объем вычислений в описанном методе, по-видимому, не больше, чем в симплекс-методе для нерегуляризованной задачи (44).
й 4. Минимизация функционала 1. Задачи на минимум функционала. Если каждой функции у (х) из некоторого множества функций У сопоставлено число Ф [у (х)), то говорят, что на миожестве У задан функционал. Задача минимизации функционала формулируется так: найти функцию у (х) г- :У, на которой функционал достигает своей точной нижней грани на этом множестве: Ф [у (х)) = 1п( Ф [у (х)], у (х), у (х) ~ У. (53) Иногда эту задачу называют минимизацией функционала по аргументу, а просто минимизацией называют нахождение числа Ф = (и( Ф [у (х)1, когда не требуется определять функцию, минимизирующую этот функционал. Не всякий функционал и не на всяком множестве имеет минимум. Например, решения задачи (53) не существует, если функционал не ограничен снизу на заданном множестве: решения может также не существовать, если множество не компактно в себе, или функционал разрывен и т.
д. (хотя условия непрерывности или компактности не являются, вообще говоря, необходимыми). Но мы не исследуем постановки задач и дальше будем предполагать, что конкретные решаемые нами задачи типа (53) корректно поста влеиы. Дадим несколько примеров задач на минимум функционала. Пусть требуется решить операторное уравнение Ау(х)=((х), а--.х~Ь. (54) !гл. тп поиск минимтмь Составим функционал ь Ф(у (х)1 = ~ (Ау(х) — ((х))ьр (х) Их, р (х) ) О.
(55) а Очевидно, он равен нулю при А у(х) =((х) и положителен, если Ау(х)~~(х) на сколь угодно малом, ио конечном интервале Лх. Таким образом, найдя функцию у(х), на которой функционал (55) достигает своего абсолютного минимума, мы получим решение уравнения (54). Заметим, что этот функционал ограничен снизу на любом множестве функций и непрерывно зависит от Ау(х). Описанный способ решения операторных уравнений называется методом наименьших квадратов.
Если задача (54) некорректно поставлена (например, неустойчива по правой части), то наиболее употребительным общим методом регуляризации является замена исходной задачи иа задачу минимизации функционала Л. Н. Тихонова: ь М(у(х),а!=г)(Ау(х) — г(х))'р(х) дх+аь! !у(х)1= гпш, а~О, (56) й где так называемый стабилизатор й [у(х)1 — специально подобранный положительный функционал, обладающий свойствами нормы; он несколько напоминает штрафную функцию.
В главе Х!Ч будет показано, что для стабилизаторов типа ьь (у(х)! = ~ (р (х) уь (х)+ д(х) у" (х)) Нх, р(х),у (х) ~0, (57) О решение задачи (56) непрерывно зависит от г(х), причем при правильном подборе а оно одновременно достаточно близко в чебышевской норме к решению у(х) уравнения (54). Уравнение (54) может привести и к другим функционалам. Пусть оператор А аддитивен, положителен и симметричен, так что (у, Ау))0 при у4=0 и (г, Ау) =(Ах, у), где под скалярным произведением подразумевается интеграл от произведения функций. Рассмотрим функционал Ф (у (х) ! = (у, Ау) — 2 (у,~), (58) где (у, г) = ~ у (х) г (х) дх.
а Покажем, что задача на минимум этого функционала эквивалентна задаче решения операторного уравнения (54). минимизация функционала %и В самом деле, запишем произвольную функцию у(х) в следующем виде: у(х) =у (х)+),г (х). (59) Подставляя это выражение в правую часть формулы (58), получим Ф (у (х)] = Ф [у (х)]+ 2Х (г, Ау — () + ).з (г, А г). (бО) Если р (х) есть решение уравнения (54), то второе слагаемое в правой части (60) обращается в нуль; последний же член в правой части неотрицателен благодаря положительности оператора А. Значит, Ф[у]=[п[Ф[у], т. е.
функционал (58) достигает минимума на решении операторного уравнения (54). Наоборот, если у(х) в представлении (59) есть функция, на которой функционал (58) достигает минимума, то первая вариация функционала на этой функции равна нулю. Следовательно, (г[ФУг[))к=о=О, каково бы ни было г(х). Применяя это условие к (бО) и одновременно полагая г(х) =Ау(х) — ((х), получим (Ад — ), Ау — )) =О, Классическим примером применения описанного приема является краевая задача — — [ р (х) — [ + о (х) у (х) =7 (х), У Г бу1 йх ~ бх! р (х) ) О, Ч (х) ) О, у ( — оо) =у (+ со) = О.
(61) Интегриронанием по частям легко убедиться в симметричности и положительности дифференциального оператора и получить следующее выражение для функционала (68): +ОЭ гэ [у(х)[= ] ]р(х) ~---~ +Ч(х)уз(х) — 2[(х)у(х)~г[х. (62) г'ау 'Л Отметим, что оператор А включает в себя не только дифференциальное (или интегральное) уравнение, но также краевые условия, если последние имеются. Краевые условия должны некоторым образом войти в функционал, соответственно изменив его вид.
Например, для задачи на ограниченном о~резке с краевыми условиями третьего рода — „— ~ р (х) „— ~+Ч (х) у (х) =((х), р(х), Ч(х) Э» О, (63а) аеу (а)-[-ссгу' (а) =сг, [[еу (Ь)+[[ту' (Ь) = 6, (63б) что выполняется только при Ау (х) =((х). Это означает, что функция, иа которой функционал (58) достигает минимума, является решением операторного уравнения (54). Утверждение доказано. поиск минимума [гл. цм надо мивимиэировать в классе достаточно гладких функций функционал Ф [у (х)] = ~ ) р (х) ( — ') + д (х) ую (х) — 2) (х) у (х)~ ах+ ю + — [2ар [а) — ссюую (о)] + — [[)аюую [Ь) — 2[)у (Ь)].
(64) р (а) р (Ь) сют рт От функцнй, минимиэиручоьцих этот функционал, уже не надо требовать удовлетворения краевым условиям — они автоматически будут им удовлетворять. В теоретической физике встречаются функционалы более сложные, чем квадратичные. Например, в статистической модели атома Томаса — Ферми при температуре абсолютного нуля энергия выражается через электронную плотность следующим образом: [ ( )1= ~ ю[ ) )Олю "'р н(П) — —,'р(П)+-"2 р~") ~ ~~я ~Д. (~6) р Поскольку при нулевой температуре и заданном объеме энергия минимальна, то нахождение электронной плотности сводится к задаче на условный экстремум для этого функционала (дополнительное условие заключается в том, что полное число электронов равно заряду ядра). К еще более сложным функционалам приводят задачи. оптпимального управления, в которых ищется минимум функционала Ф[у (х)1, причем функция у(х) является решением задачи'Коши для дифференциального уравнения -„-=Р(х, у(х), и(х)), у(0) =у,.
Трепа буется найти такую управляющую функцию и(х), при которой заданный функционал минимален. К задачам оптимального управления относится, например, определение оптимального режима расхода горючего и(ю) прн запуске ракеты, приводящего к максимальной высоте подъема Ф прн заданном начальном количестве горючего. 2. Метод пробных функций. Общая схема численного решения заключается в сведении задачи (53) к поиску минимума функции многих переменных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
