1626435584-7c6402f545ecf856225d6cf8d21519c9 (844233), страница 49
Текст из файла (страница 49)
2. Метод штрафных функций. Рассмотрим задачу на абсолютный минимум во всем и-мерном пространстве для такой вспомогательной функции: Р (х) = — Ф (х) + ! '" Р !- ~$~ и ! ! + ~ !! ! ! ! ! — !! и ! !!) - ь, „ ~ о. !зв! !=- ! !.—..1 Прибавляемые к Ф(х) члены взяты таким образом, что они обращаются в нуль, если дополнительные условия в (38) выполнены. Если же условия нарушены, то эти члены положительны, т. е. они увеличивают Е(х), причем тем больше, чем сильнее нарушены дополнительные условия. Это своеобразный штраф за нарушение условий.
Если коэффициент штрафа р достаточно велик, то за границами области 6 функция Е (х) быстро возрастает. Значит, минимум Е(х) расположен или внутри области 6, или снаружи вблизи' ее границы. Если он лежит в области 6, то он совпадает с минимумом Ф(х), ибо там дополнительные члены в условии (39) обращаются в нуль. Если же минимум Е(х) лежит снаружи, то минимум х исходной функции лежит на границе; при разумных предположениях о свойствах функций Ф(х), !р; (х) и !р (х) доказано, что его отличие от минимума х„вспомогательной функции не превышает )х — х„)» ""', (40) где величина константы зависит от конкретных свойств функций (38). Поэтому если взять последовательность р, со и найти для нее минимумы х!, вспомогательной функции Е(х; р„), то х,- х. 2!7 МИНИМУМ В ОГРАНИЧЕННОИ ОБЛАСТИ Т, (х) — = ~ с!х! = пип, (41а) х!~0, 1~л(п, (416) (4! в) У', адх! =- Ь;, «=! 1~1(т, Х~ а,!х«(ЬИ т~)' М.
«=- ! (41г) Каждое из условий типа неравенств (41б) или (4!г) определяет полупростраиство, ограниченное гиперплоскостью; все эти условия вместе определяют выпуклый и-мерный многогранник (, являющийся пересечением соответствующих полупространств. С математической точки зрения условия (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~1~Ь( (44а) (44б) 'У', ау!х1=ЬИ 1(у~М (М«- й().
(44 в) Многогранник новых канонических условий образован пересечением новой (!у' — М)-мерной плоскости условий с первым координатным углом. Значит, все его .вершины лежат на координатных гиперплоскостях, т. е. у каждой вершины часть координат- нули, а остальные координаты положительны. Будем считать, что строки новой матрицы А линейно-независимы: в противном случае или одно условие лишнее, или система условий, несовместна. Тогда ранг этой прямоугольной матрицы равен М, и среди ее столбцов найдется по крайней мере один набор из М линейно-независимых столбцов.
Все линейно-независимые наборы столбцов матрицы А соответствуют точкам пересечения плоскости условий с координатными гиперплоскостями. Чтобы найти вершину, яодьмем один такой набор столбцов. Для удобства записи перслумеруем переменные так, чтобы первыми стояли столбцы, соответствующие этому набору (базису). Перепишем условия второго типа (44в) в следующем виде: м м атх!=Ь; — ~ а!!х!, 1(1(М. (45) м х,= ~ и!!Ьм 1 =- ! < М, М ( ! ~ У.
(45) Если найденные координаты неотрицательны, точка пересечения принадлежит первому координатному углу, т. е. является вершиной многогранника канонических условий. Если хотя бы одно х, «- О, эту точку надо отбросить и исследовать другой набор столбцов матрицы А. Если мы забракуем все точки, это Обозначим через а!1, 1=/, ! =М, элементы матрицы, обратной к базисной квадратной матрице, стоян!ей в левой части системы (45). Приравнивая внебазисные координаты нулю и решая эту систему, получим координаты точки пересечения плоскости условий с координатной гиперплоскостью 220 ПОИСК МИНИМУМА ~гл. уп остальные внебазисные координаты остаются равными нулю.
Будем увеличивать х, до тех пор, пока одна из базисных координат не обратится в нуль. Это будет при м Х,= Ш!П ( — -) О!! = ~Ч~ ~ацгап) О; /х! '! !«м !О!гг, г= ! (48) минимум ищется только среди тех индексов », для которых 8!г) О, ибо только эти координаты вдоль данного ребра уменьшаются и, означает, что условия первого и второго рода образуют несовместную систему. Различные столбцы матрицы А могут образовать См наборов. М Поэтому в самом неблагоприятном случае (М-г( й!) Многогранник условий может иметь до См — 2 вершин. Если У 100, мм, м то это число настолько велико, что простой перебор вершин невозможен.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
