3 часть (1081356), страница 56
Текст из файла (страница 56)
17. Методы оптимизации 386 8 4. Нелинейное программирование 1. Задачи, сводящиеся к линейному программированию. В наиболес общей постановке задача келинекного программирования формулируется следующим образом: /(х) -~ пй(п, д(х) =Ьо 1=1,2, ...,1, д,(х) < Ьо ~=1+1,..., т, (2) (3) где /(х), д;(х), 1 = 1, ..., ят, — заданные (не обязательна линейные) функции я переменных.
Отметим, что условие неотрицательностн переменных х, > О, у = 1, ..., я, входящее в постановки многих задач нелинейного программирования, можно записать в виде неравенств (3), положив д (х) = — х., Ь = О. 17.251. /(х) = х1 — 10хз -+ пшц Зх~ + хз ~( 12, — 8х1 + Зхз ( 24, ху>0, хгЕУ 17.252. /(х) = — х1 — хз — ~ ппп, х1+2хг (4, 2х1+ хз ( 4, ху>0, х1ЕК. 17.253. /(х) = — х1 — 4хз -+ ш1п, хг + хз = 7/2, х|+ хг + х4 = 7, — х1+ хт+ ха — — 2, ху > О, х1 Е Е. 17.254. /(х) = 10х1 + 5хг + 7хз — Зх4 -+ пип, — х1 — 2хт + Зхз + Зх4 = 3/2, х1 + хз + 7хз + 2х4 = 7/2, 2х1 + 2хт + 8хз + х4 — — 4, ху~)0, хыхзЕЖ.
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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
