Н.Н. Калиткин - Численные методы (1133437), страница 48
Текст из файла (страница 48)
С математической точки зрения условия (41б) и (41г) однотипны; ио по традиции их записывают указанным образом. Условия типа равенств (41в) выделяют из и-мерного пространства (и — т)-мерную Задачу (39) на безусловный экстремум удобнее всего решать методом случайного поиска со спуском по сопряженным направлениям: здесь естественно задана область, где надо выбирать случайные точки. При малых значениях р согласно оценке (40) точность может быть плохой. Но при большом р благодаря дополнительным членам в (39) вблизи границы области появляются глубокие овраги и крутые откосы, так что методы спуска сходятся медленно.
Полезен следующий прием, заметно ускоряющий сходимость. Сначала берут небольшое р, и легко находят соответствующий минимум х,. Затем берут большее значение р,, а значение х, используют в качестве начального приближения для спуска; поэтому спуск будет не длинный, и новый минимум х, определится быстро. Эту процедуру повторяютдо тех пор, пока «штраф«в фигурная скобка в (39) — не станет достаточно малым. Тогда можно считать, что точка ххл близка к границе области 6 и хорошо аппроксимирует минимум х. Метод штрафных функций медленный и ие слишком надежный. Он применим только при небольшом числе переменных п(10.
Но существенно более хороших методов для общей нелинейной задачи (38) пока нет. Перспективным кажется метод штрафных оценок, являющийся комбинацией описанного метода и метода неопределенных множителей Лагранжа; однако он еще мало изучен. 3. Линейное программирование. При оптимизации экономических планов возникают задачи на минимум линейной функции п переменных при наличии линейных дополнительных условий трех типов: 21В ПОИСК МИНИМУМА [Гл, уи плоскость.
Ее пересечение с областью г дает выпуклый (и — и)- мерный многогранник 6; наша задача состоит в том, чтобы найти минимум линейной функции (41а) в этом многограннике 6. Примером такой задачи является распределение производства однотипной продукции по разным заводам. Пусть х! — выпУскземое 1-и заводом количество продукции (оно должно быть неотрицательным), с1 — сЕбестоимостью одного изде. ЛИЯ НВ ЭТОМ ЗаВОДЕ, ау! ПРИ 1) т — РаСХОД СЫРЬЯ 1-ГО ВИДа И ал ПРИ 2~)~т — расход заработной платы и других аналогичных показателей Его аида при выпуске единицы продукции на данном заводе. Положим а,1=1; тогда Ь, будет суммарным выпуском продукции по всем заводам, Ь~, 2(1( ~ т, — полной заработной платой и аналогичными данными по воен отрасли, суммы (4!г) — расходом сырья по всем заводам, а 1.— себестоимостью общей продукции.
Требуется, чтобы себестоимость продукции была минимальной, выпуск продукции, расход заработной платы н т, д.— заданными, в фонды сырья Ьу, т ~ й не перерасходовались. Нас интересует, как распределить неотрицательные плановые задания х; по заводам тзк, чтобы удовлетворить всем этим требованиям. Отметим терминологию, установившуюся в экономике. Вектор х, удовлет. воряющий всем дополнительным условиям, называют аланом; если он, к тому же, соответствует вершине многогранника 6, то олорным ллаиоли Решение экстремальной задачи 141) называют антил!альным аланом, столбцы прямогольной матрицы А — векторами условий, з столбец Ь вЂ” вектором ограничении. задачах экономики обычно все коэффициенты а, Ь, с= О, хотя для последующего изложении это несущественно. Многогранник условий 6 — выпуклый (он может быть и неограниченным) Поэтому внутри него линейная функция ь (х) не может достигать минимума.
Ее минимум (если он су1цествует) достигается обязательно в какой-нибудь вершине многогранника. При вырождении он может достигаться во всех точках ребра или даже р-мерной ограничивающей плоскости (р и — пт). Поэтому теоретически задача линейного программирования проста. Достаточно вычислить значения функции в конечном числе точек— в вершинах многогранника и найти среди этих значений наименьшее. Сложность заключается в другом.
Типичное в экономике число переменных — это сотни и даже тысячи. При этом число вершин многогранника 6 становится астрономическим. Для того чтобы оценить это число, рассмотрим способ нахождения вершин. Находить вершины самого многогранника 6 неудобно. Лучше преобразовать задачу к канонической форме, не содержацтей условий третьего типа. Для этого введем в качестве новых переменных невязки условий третьего типа: х1=Ь1+ — У, 'азэ жехч- О, п(1(й(, )))=п+М вЂ” т. (42) В=т Доопределим коэффициенты экстремальной задачи (41) следующим образом: с!=О, а!1=бд!эм н пРи п<1=Л/, 1<1(М.
(43) 219 МИНИМУМ В ОГРАНИЧЕННОН ОБЛАСТИ Тогда задача линейного программирования примет каноническую фОрму: Т. (х) — )~ с,х! = пип, С=! х!~0, 1~!~У (44а) (44б) 'У', ау!х1=ЬИ 1(у~М (М«- й(). (44 в) Многогранник новых канонических условий образован пересечением новой (!у' — М)-мерной плоскости условий с первым координатным углом. Значит, все его .вершины лежат на координатных гиперплоскостях, т. е. у каждой вершины часть координат- нули, а остальные координаты положительны. Будем считать, что строки новой матрицы А линейно-независимы: в противном случае или одно условие лишнее, или система условий, несовместна. Тогда ранг этой прямоугольной матрицы равен М, и среди ее столбцов найдется по крайней мере один набор из М линейно-независимых столбцов.
Все линейно-независимые наборы столбцов матрицы А соответствуют точкам пересечения плоскости условий с координатными гиперплоскостями. Чтобы найти вершину, яодьмем один такой набор столбцов. Для удобства записи перслумеруем переменные так, чтобы первыми стояли столбцы, соответствующие этому набору (базису).
Перепишем условия второго типа (44в) в следующем виде: м м атх!=Ь; — ~ а!!х!, 1(1(М. (45) м х,= ~ и!!Ьм 1 =- ! < М, М ( ! ~ У. (45) Если найденные координаты неотрицательны, точка пересечения принадлежит первому координатному углу, т. е. является вершиной многогранника канонических условий. Если хотя бы одно х, «- О, эту точку надо отбросить и исследовать другой набор столбцов матрицы А. Если мы забракуем все точки, это Обозначим через а!1, 1=/, ! =М, элементы матрицы, обратной к базисной квадратной матрице, стоящей в левой части системы (45). Приравнивая внебазисные координаты нулю и решая эту систему, получим координаты точки пересечения плоскости условий с координатной гиперплоскостью 220 ПОИСК МИНИМУМА ~гл.
уп остальные внебазисные координаты остаются равными нулю. Будем увеличивать х, до тех пор, пока одна из базисных координат не обратится в нуль. Это будет при м Х,= Ш!П ( — -) О!! = ~Ч~ ~ацгап) О; /х! '! !«м !О!гг, г= ! (48) минимум ищется только среди тех индексов », для которых 8!г) О, ибо только эти координаты вдоль данного ребра уменьшаются и, означает, что условия первого и второго рода образуют несовместную систему. Различные столбцы матрицы А могут образовать См наборов.
М Поэтому в самом неблагоприятном случае (М-г( й!) Многогранник условий может иметь до См — 2 вершин. Если У 100, мм, м то это число настолько велико, что простой перебор вершин невозможен. Нетрудно подсчитать, что для ЭВМ типа БЭСМ-б простой перебор посилен только при гг! -' 15. 4. Симплекс-метод позволяет найти решение задачи линейного программирования за гораздо меньшее число действий. Изложим идею метода. Найдем какую-нибудь вершину многогранника и все ребра, выходящие из этой вершины. Пойдем вдоль того из ребер, по которому функция убывает.
Придем в следующую вершину, найдем выходящие из нее ребра и повторим процесс. Когда мы придем в такую вершину, что вдоль всех выходящих нз нее ребер функция возрастает, то минимум достигнут. Поскольку Е(х)— линейная функция, а многогранник условий выпуклый, то этот процесс всегда сходится к решению задачи, причем за конечное число шагов. При канонической форме записи многогранника условий из каждой его вершины исходит Ж вЂ” М ребер.
Выбирая одно ребро, мы выбрасываем из рассмотрения в", пины, лежащие на остальных траекториях. Следовательно, за й шагов мы рассматриваем (Ж вЂ” М) "-ю часть вершин, проходя мимо остальных. Нам надо найти искомую вершину среди См вершин многогранника. Приравнивая число вершин Смм мвелнчине (Ж вЂ” М)», получим, что минимум достигается примерно за й гу' шагов, т.
е. достаточно быстро. Выведем формулы шага. Первую вершину находим по формуле (46). Чтобы найти ребро, надо одну из внебазисных переменных х, сделать положительной; тогда координаты точек ребра можно выразить через иее из (45) при помощи обратной матрицы Л! х;=х; — х, ~ а„а,„! ~ ! -М, х,=х,; (47) г= 1 МИНИМУМ В ОГРАНИЧЕННОЙ ОБЛАСТИ 221 следовательно, могут обратиться в нуль. Если все суммы Зп при данном 1 отрицательны, то это ребро неограниченное и весь многогранник условий — тоже. Подставляя найденное х, в формулы (47), получим координаты новой вершины и вычислим в ней значение функции Е(х) = 1.! Поочередно меняя каждую внебазисную переменную, найдем все Л' — М ребер, выходящих из исходной вершины и проводящих в смежные вершины. Сравним все значения функции в смежных вершинах !н и выберем из них наименьшее. Если оно меньше, чем значение функции в исходной вершине Тм то переместимся в наинизшую из новых вершин и повторим процесс.
Если же ш1п1.!'-.:Е„то минимум уже достигнут в исходной вершине. Для всех неограниченных ребер, исходящих из вершины, надо проверять знак производной функции и м м !У Л! = — =с, — '5', с, ~Р' аца!!Г о! — '5' С,З!!. !!х! ю=! ! -! г= 1 Если эта величина отрицательна, то задача линейного программирования вообще не имеет решения (пнп Е (х) = — ОО).
Если же она неотрицательна, то это ребро не ведет к минимуму, и оно нас не интересует. Нетрудно оценить, что для выполнения всех шагов и получения минимума требуется примерно до 10 Ф'М' арифметических действий. Это уже приемлемо для крупных современных ЭВМ. Симплекс-метод является примером высоко специализированного метода. Он пригоден только для нахождения минимума линейной функции в многомерном выпуклом многограннике определенного вида — симплексе. Зато он позволяет решать задачи с огромным числом переменных. 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
