341_3- Сборник задач по математике для втузов. В 4-х ч. Ч.3_ (ред) Ефимов А.В, Поспелов А.С_2002 -576с (987779), страница 55
Текст из файла (страница 55)
17.255. Решить задачу 17.182 об оптимальном составе сплава, предполагая, что сырье второго вида приобретается в количествах, кратных 1 кг, а сырье первого вида — в произвольных количе- ствах. 17.256. Решить задачу 17.199 в предположении, что: а) товар А1 выпускается в количествах, кратных 1 кг, а товар Аг — в произвольных количествах; б) товар А1 выпускается в произвольных количествах, а товар Аг — в количествах, кратных 1 кг. 3 4.
Нелинейное программирование 387 Некоторые задачи нелинейного программирования сводятся к задачам линейного программирования, методы решения которых описаны в з 3. Рассмотрим зада юу дробно-линейного прогринюиироеанил и Е ох,+со у(х) = д ю, + с(о з=! (4) -л ппп, абх, =б;, !=1, ...,1, Е (5) абх, <6!, л=(+1, ...,т, т=! (6) ,у(у) = ~ ~с,уу -л шшю и а;.у ,ю=! а! у у=! юю ~, 'дю1 ю=о у, >О, Ьуо=О, т=1,...,1, Ьлуо(О, л=1+1ю...,юп, (8) у = О,..., я, х.
>О, у=1,...,я. (7) Будем считатля что во внутренних точках допустимого мноьчсства У задачи (4) — (7) знаменатель целевой функции из (4) не обращается в нуль и, следовательно, сохраняет знак. Если зтот анамснатсль отрицателен, то умногким числитель и знаменатель дроби из (4) на — 1 и будем в дальнейшем считать, что ~ д х + до > О для всех х б ь'. ,! = ! юю ° .
ю.=ю/ ~ю,*,юю) ! ° »,ю. ю.р юю! ° 1=1 введем новые персменныс у. = уох„д = 1, ..., я. В новых переменных у„у = О, 1, ..., я, задача (4) — (7) принимает следуюшнй вид; Гл. 17, Методы оптимизации 388 т.е. преврашается в задачу линейного программирования (см. г 3). Отметим, что требование уо > О, включенное в условие задачи (8), не ограничивает возможного изменения переменной уо, так как уо > О при х б ьГ. Найдем решение у" = (уо, ..., У„*), /' задачи линейного программирования (8) и, используя равенства х = -~-, 2 =1, ...,п, /' =пнп/(х) =/', (9) получим решение исходной аадачи дробно-линейного программирования (4)-(7).
Если уо = О, то допустимое множество (/ задачи (4)-(7) не ограни- чено и минимум целевой функции /(х) на нем не достигается. Решить задачи дробно-линейного программирования 17.257- 17.266: 17.257. Дх) = -2х1+ хг -+ шш, х1 + 2х2 + 1 х1 — 2хг ( 2, 2х1+ х2+ хз = 6, хг > О, у = 1, 2, 3. ° г Знаменатель х1 + 2хг + 1 целевой функции положителен при всех х из допустимого множества (/, так как хм хг > О. Вводя пеРеменные Уо — — 1/(х1+ 2хг + 1), У.
= Уох,, У' = 1, 2, 3, получим следуюшую задачу линейного программйрования: /(у) = — 2У1 + уг -1 ппп, у1 — 2уг — 2уо ( О, 2р1 — уз + рз — буа = О уг + 2уг + Уо = 1, у,>О, у=о, ",3. Приведя эту задачу к каноническому виду и решив ее симплекс- методом, находим уо — — 1/3, у,* = 2/3, уг = О, уэ = 2/3, /* = — 4/3, от- куда, используя формулы (9), получаем решение исходной задачи; х' = = (2; О; 2), /* = — 4/3. > 17.258. /(х) = — 1 ппп, 4х1+ Зхг 2х1+ хг х1 + 2хг ( 16, х1 + хг ( 10, х1 ( 6, хг (7, х1, х2 ~ ЭО. Гл. 17. Методы оптимизации 390 1 у(х) = -(Ях, х) + (г, х) — л шш, 2 (10) а„х. (6„1= 1, ..., т, з=! (11) х >О, у=1,...,п.
(12) Здесь Ц = (90) — симметричная матрица размера п х п, г = = (гы ..., г„) — заданный вектор. Напомним, гго сели матрица 1„У положительно определена, то квадратичнап функции у(х) нз (10) является выпуклой в Еи. На основании известной теоремы Куна — Таккера [1] точка минимума х* = (х*,, ..., х„*) целевой функции У(х) из (10) на допустимом множестве (У (11), (12) мои~от быть найдена как решение следуюшсй системы уравнений с дополнительными псрел~свнымц Лн хини 1 = 1,..., т; д з у=1 . п: и П1 амх,+г,+ , 'Ла„.— ул,=О,,у=1,...,п, (13) абхз + хи+, — — б„л = 1,..., т, Е (14) Лиг„л, —— О, 1= 1, ..., т; цухг = О, г = 1, ..., п, (15) удовлетворлюшее условию неотрицательности х > О, ул > О, ,у = 1, ..., п:, Л, > О, л = 1, ..., т. (16) Длл решении системы (13)-(16) мохсно использовать лгетод искусственного базиса (см.
г 3), позволиюший найти одну из угловых точек множества, заданного ограничснинлги (13), (14), (16). Так как эта точка ху — 2хг + 3 17.266. у'(х) = — л шш, хг+ 2 х1+ хг — хз = 5, — ху+2хг ~ )1, — Зхг+хг+ха = 1, — Зх~ + 2хг + ха = 11, х > О, у = 1, ..., 4. Другой важный класс задач нелинейного программировании, реше- ние которых можно найти методами линейного программирования, обра- зуют задачи квадрагппчноео прюера мироаания, в ко~орых требуется минимизировать выпуклую функцию (см.
З 2) на допустимом множе- стве, заданном линсйнымн ограничениями, т.с. 3 4. Нелинейное программирование 391 принадлежит указанному множеству, то она удовлетворяет перечисленным ограничениям. При реализации метода искусственного базиса следует учитывать и условия (15), т. е. не включать в базисные одновременно переменные Л; и хл ы с одним и тем же индексом ! и переменные х., р с одинаковым номером у. П р и и е р 1. Решить задачу квадратичного программирования /(х) = хз + 2х2 2— 2х1хт — 2х! — бх2 †! ппп, х1+х2 ((2, — х1+х2 (2, х1,хт >О.
< Матрица л7 = ~ 2 4 ) квалратичной функции /(х) положительно г 2 — 21 определена (проверьте самостоятельно!). Система (13)-(16) в данном случае принимает вид (17) 2х1 — 2хт + Л! — Лт — р! = 2, (18) — 2хг + 4хт+ Л! + 2Л2 — рт = 6, х1+хт+ха = 2, — х! + 2х2 + х4 — — 2, р1х! = ц2х2 = Л!хз = Л2х4 = О, Х1,..., Х4 3 О; рг, рт ) О; Л1, Л2 3 О. (19) (20) (21) Будем искать угловую точку множества, определнсмого втой системой, методом искусственного базиса.
При атом, так как уравнения (19) и (20) легко разрешаются относительно переменных хз и х4, длк уменьшенил раамера симплекс-таблиц дополнительные переменные (хл и хе) вводим только в уравнения (17) и (18), считал базисными переменными начальной угловой точки хз,х4,хл и хв. Вспомогательную пелевую функцию /(х) = хв + ха выразим через свободныс переменные х1, хт, Л1, Лт, р! и 142 с помошью уравнений (17) и (18): /(х) = — 2х! — 2Л! — Лт + р1+ р2 + 8. Последовательность симплекс-таблиц, приводлших к решению задачи, приведена ниже. Рамками обведены опорные злсменты, а те свободные переменные, которые на данном шаге нельзя переводить в базисные из-за условий (21), обведены кружками.
В последней таблице злел1енты нижней строки неотрипательны, следовательно, минимум вспомогательной целевой функции /" = 0 достигается в угловой точке, соответствуюшсй атой таблице. Позтолзу искомос решение задачи квадратичного программирования имсет вид х* = (4/5, 6/5), / = /(х*) = 36/5. Гл. 17.
Методы оптимизации 392 Замечание. Если задача квадратичного программирования наряду с ограничениями-неравенствами (11) содержит и равенства ~~ а„.х, = ~=1 = б„то для преобразования их к виду (11) следуег выразить из зтих равенств какие-либо базисные переменные через остальные и записать условие неотрицательности для базисных переменных. Например, преобразуем ограничения-равенства Зх~ +ха+ ха+ха = 16, — хл + Зхз — ха +х4 = 4 к виду (11). Разрешив ит относительно хз и хл, находим хз = 6— — 2х~ + хт, х4 = 10 — хл — 2хз. Учит1овая условие неотрипательности хз > О, х4 > О, получим ограничения-неравенства (11): 2х~ — хз < 6, хл + 2хт < 10. Решить задачи квадратичного программирования 17.267- 17.276: Гл.
17. Методы оптимизации 394 Минимизировать в многоугольнике с вершинами (О, О), (О, 4), (5, 8), (10, 4), (б, 0) следующие функции: 17.277. )'(~) = хг + хг г— 4хь — бхг. 17.278. )'(х) =.тгь + хг 20хь — 1бхг. 17.279. г (х) = хг(+ 2хг г— 10хь — 32хг. 17.280. у(х) = 2хгь + Зхгг — 40хь — 48хг. 2. Методы возможных направлений. Основная идея этой группы методов решения задач нелинейного программирования заключается в построении последовательных приближений к точке минимума х' целевой функции г(х) на допустимом множестве с): х(ь+') = х(ь) +сьье("), .)с = О, 1,..., х(о) б У, аь > О. (22) 1(х) -э пцп, (23) а„х, <бь ), ь=1,...,.пь, Е э ь=ь (24) (25) г = 1, ..., п.
х >О, Опишем выбор вектора е(ь) = (е(; ...; е„) из (22), определяющего (ь) (/с) возможное направление убывания функции г"(х) в точке х("). Рассмотрим возможные сл) ьаи. э) Если среди этих ограничений есть равенства, то преобразовать их к аиду (24) можно описанным выше саособом (см. замечание ка с. 392). Эти методы напоминают безусловную минимизацию у(х) градиентными методами (см.г 2).
Вектор е("), определяющий направление перемещения (22) из точки х(") в точку х("+'), должен удовлетворять следующим двум требованиям: 1. Для достаточно малых оь > 0 точка х("+') из (22) принадлежит множеству (у (т.е. е(ь) задает возльожиае направление). 2. Для достаточно малых аь > 0 выполняется неравенство г'(х("+') ) < < г'(х(ь)) (т.е. ейй определяет иаправлекие убсчеакил )'(х)). Первое условие означает, в частности, что для граничных точек х(") допустимого множества Гг вектор е(ь) направлен внутрь У. Величина пь > 0 в (22) выбирается из условия наибольшего убывания целевой функции в направлении е( ') с учетом требования х(ь+') Е (ь'.
Рассмотрим сначала метод возможных направлений решения задачи минимизации выпуклой дифференцируемой нелинейной функции у(х) на допустимом множестве ГГ, заданном линейными ограничениями 2 4. Нелинейное программирование 395 1. Пусть в точке хрб все неравенства (24) и (25) выполняются как строгио. Это означает, что х(») — внутренняя точка допустимого множества У. Тогда е( ) = — Г'(х( )), (26) и 1» = г(~~ аых ) =Ь;,,4=(Ях ' =0).
(27) у=1 Представим поьипоненты е, вектора е(») для у ф 1» в виде (») (») (») )' (») а\ е, = е — е, ), (28) где е, если с, > О, (»] (») (») О, если е <0; (») О, если еу > О, (») (») (») — е, если е. < О. Очевидно, е,, е, > О, и е ед = 0 лля всех 1 ф,У». (»)-(- (») — (»)-(. (»)— ) Такое представление ллп е( , 1 ф з», позволяет находить вектор е(») как (») решение задачи линейного программирования, содержащей условие неотрицательности перел»сивых, несмотря на то, что его компоненты могут быть отрицательными. Лля 1 Е з» представление (28) не используетсв, так как у вевтора е( ), опрсде(») (м лающего воаможное направление, вомпонснты е с номерами 1 Е,У» нс могут быть отрицательными.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
