1626435584-7c6402f545ecf856225d6cf8d21519c9 (844233), страница 50
Текст из файла (страница 50)
Нетрудно подсчитать, что для ЭВМ типа БЭСМ-б простой перебор посилен только при гг! -' 15. 4. Симплекс-метод позволяет найти решение задачи линейного программирования за гораздо меньшее число действий. Изложим идею метода. Найдем какую-нибудь вершину многогранника и все ребра, выходящие из этой вершины. Пойдем вдоль того из ребер, по которому функция убывает. Придем в следующую вершину, найдем выходящие из нее ребра и повторим процесс. Когда мы придем в такую вершину, что вдоль всех выходящих нз нее ребер функция возрастает, то минимум достигнут.
Поскольку Е(х)— линейная функция, а многогранник условий выпуклый, то этот процесс всегда сходится к решению задачи, причем за конечное число шагов. При канонической форме записи многогранника условий из каждой его вершины исходит Ж вЂ” М ребер. Выбирая одно ребро, мы выбрасываем из рассмотрения в", пины, лежащие на остальных траекториях. Следовательно, за й шагов мы рассматриваем (Ж вЂ” М) "-ю часть вершин, проходя мимо остальных.
Нам надо найти искомую вершину среди См вершин многогранника. Приравнивая число вершин Смм мвелнчине (Ж вЂ” М)», получим, что минимум достигается примерно за й гу' шагов, т. е. достаточно быстро. Выведем формулы шага. Первую вершину находим по формуле (46). Чтобы найти ребро, надо одну из внебазисных переменных х, сделать положительной; тогда координаты точек ребра можно выразить через иее из (45) при помощи обратной матрицы Л! х;=х; — х, ~ а„а,„! ~ ! -М, х,=х,; (47) г= 1 МИНИМУМ В ОГРАНИЧЕННОЙ ОБЛАСТИ 221 следовательно, могут обратиться в нуль. Если все суммы Зп при данном 1 отрицательны, то это ребро неограниченное и весь многогранник условий — тоже.
Подставляя найденное х, в формулы (47), получим координаты новой вершины и вычислим в ней значение функции Е(х) = 1.! Поочередно меняя каждую внебазисную переменную, найдем все Л' — М ребер, выходящих из исходной вершины и проводящих в смежные вершины. Сравним все значения функции в смежных вершинах !н и выберем из них наименьшее. Если оно меньше, чем значение функции в исходной вершине Тм то переместимся в наинизшую из новых вершин и повторим процесс.
Если же ш1п1.!'-.:Е„то минимум уже достигнут в исходной вершине. Для всех неограниченных ребер, исходящих из вершины, надо проверять знак производной функции и м м !У Л! = — =с, — '5', с, ~Р' аца!!Г о! — '5' С,З!!. !!х! ю=! ! -! г= 1 Если эта величина отрицательна, то задача линейного программирования вообще не имеет решения (пнп Е (х) = — ОО). Если же она неотрицательна, то это ребро не ведет к минимуму, и оно нас не интересует. Нетрудно оценить, что для выполнения всех шагов и получения минимума требуется примерно до 10 Ф'М' арифметических действий.
Это уже приемлемо для крупных современных ЭВМ. Симплекс-метод является примером высоко специализированного метода. Он пригоден только для нахождения минимума линейной функции в многомерном выпуклом многограннике определенного вида — симплексе. Зато он позволяет решать задачи с огромным числом переменных. 5. Регуляризация линейного программирования. Задача линейного программирования часто оказывается плохо обусловленной. Так, себестоимость единицы продукции или норм расхода сырья на разных заводах не должна сильно отличаться.
Поэтому даже заметное перераспределение заказов между заводами слабо влияет на суммарную стоимость продукции. Соответственно малая вариация суммарной стоимости приводит к большой вариации распределения заказов. По тем же причинам небольшое изменение себестоимости или других показателей на отдельных заводах сильно меняет оптимальный план, так что решение очень чувствительно к вариациям коэффициентов. А сами эти коэффициенты не вполне точно известны. Поэтому на практике задача (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 = ~ (Ау(х) — ((х))ьр (х) Их, р (х) ) О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
