14.8: Множники Лагранжа
- Використовувати метод множників Лагранжа для вирішення задач оптимізації з одним обмеженням.
- Використовувати метод множників Лагранжа для вирішення задач оптимізації з двома обмеженнями.
Розв'язування задач оптимізації функцій двох і більше змінних може бути аналогічним вирішенню таких задач в однозмінному численні. Однак методи боротьби з декількома змінними дозволяють нам вирішувати більш різноманітні задачі оптимізації, для яких нам потрібно мати справу з додатковими умовами або обмеженнями. У цьому розділі ми розглянемо один з найбільш поширених і корисних методів вирішення задач оптимізації з обмеженнями.
Мультиплікатори Лагранжа
У попередньому розділі була досліджена прикладна ситуація, яка передбачає максимізацію функції прибутку з урахуванням певних обмежень. У цьому прикладі обмеження включали максимальну кількість м'ячів для гольфу, які можуть бути вироблені і продані в1 місяць(x), і максимальну кількість рекламних годин, які можуть бути придбані на місяць(y). Припустимо, вони були об'єднані в єдине бюджетне обмеження20x+4y≤216, наприклад, що враховували як витрати на виробництво м'ячів для гольфу, так і кількість рекламних годин, придбаних на місяць. Мета все ж полягає в тому, щоб максимізувати прибуток, але зараз існує інший тип обмеження на значенняx іy. Це обмеження і відповідна функція прибутку
f(x,y)=48x+96y−x2−2xy−9y2
є прикладом задачі оптимізації, а функціяf(x,y) називається об'єктивною функцією. Даліf(x,y) йде графік різних кривих рівня функції.

На14.8.1 малюнку значенняc представляє різні рівні прибутку (тобто значення функціїf). У міруc збільшення значення крива зміщується вправо. Оскільки наша мета - максимізувати прибуток, ми хочемо вибрати криву якнайдалі вправо. Якби не було обмежень на кількість м'ячів для гольфу, які компанія могла б виробляти, або кількість доступних одиниць реклами, то ми могли б виробляти стільки м'ячів для гольфу, скільки хочемо, і не було б максимального прибутку для компанії. На жаль, у нас є бюджетне обмеження, яке моделюється нерівністю20x+4y≤216. Щоб побачити, як це обмеження взаємодіє з функцією прибутку, на малюнку14.8.2 показаний графік лінії,20x+4y=216 накладеної на попередній графік.

Як вже говорилося раніше, максимальний прибуток виникає, коли крива рівня знаходиться якнайдалі вправо. Однак рівень виробництва, відповідний цьому максимальному прибутку, також повинен задовольняти бюджетному обмеженню, тому точка, в якій відбувається цей прибуток, також повинна лежати на (або ліворуч) червоній лінії на малюнку14.8.2. Огляд цього графіка показує, що ця точка існує там, де пряма є дотичною до кривої рівняf. Проби і помилки виявляють, що цей рівень прибутку, здається395,y є навколо, колиx і обидва просто менше, ніж5. Повертаємося до вирішення цієї проблеми пізніше в цьому розділі. З теоретичної точки зору, в точці, де крива прибутку дотична до лінії обмеження, градієнт обох функцій, оцінених в цій точці, повинен вказувати в одному (або протилежному) напрямку. Нагадаємо, що градієнт функції більше однієї змінної є вектором. Якщо два вектора вказують в однакових (або протилежних) напрямках, то один повинен бути постійним кратним іншому. Ця ідея лежить в основі методу множників Лагранжа.
Теорема14.8.1:g Дозволятиf і бути функції двох змінних з неперервними частинними похідними в кожній точці деякої відкритої множиниf, що містить гладку кривуg(x,y)=0. Припустимоg(x,y)=0, що при обмеженні точками на кривій має локальний екстремум в точці(x0,y0) і що⇀∇g(x0,y0)≠0. Потім йде число,λ зване множником Лагранжа, для якого
⇀∇f(x0,y0)=λ⇀∇g(x0,y0).
Припустимо, що обмежений екстремум виникає в точці(x0,y0). Крім того, ми припускаємо, що рівнянняg(x,y)=0 можна плавно параметризувати як
x=x(s)andy=y(s)
деs - параметр довжини дуги з контрольною точкою(x0,y0) вs=0. Тому кількістьz=f(x(s),y(s)) має відносний максимальний або відносний мінімумs=0, і це означає, щоdzds=0 в цей момент. З ланцюгового правила,
dzds=∂f∂x⋅∂x∂s+∂f∂y⋅∂y∂s=(∂f∂xˆi+∂f∂yˆj)⋅(∂x∂sˆi+∂y∂sˆj)=0,
де всі похідні оцінюються наs=0. Однак першим фактором у точковому добутку є градієнтf, а другий коефіцієнт - вектор дотичної одиниці→T(0) до кривої обмеження. Оскільки точка(x0,y0) відповідаєs=0, то з цього рівняння випливає, що
⇀∇f(x0,y0)⋅⇀T(0)=0,
що означає, що градієнт є або нульовим вектором,⇀0 або він є нормальним для кривої обмеження при обмеженому відносному екстремумі. Однак крива обмеженняg(x,y)=0 є кривою рівня для функції,g(x,y) так що якщо⇀∇g(x0,y0)≠0 потім⇀∇g(x0,y0) є нормальним для цієї кривої на(x0,y0) Це випливає, то, що є деякі скалярніλ такі, що
⇀∇f(x0,y0)=λ⇀∇g(x0,y0)
◻
Щоб застосувати теорему14.8.1 до задачі оптимізації, подібної до проблеми виробника м'ячів для гольфу, нам потрібна стратегія вирішення проблем.
- Визначтеf(x,y) цільову функцію та функцію обмеженняg(x,y). Чи передбачає задача оптимізації максимізації або мінімізації цільової функції?
- Налаштуйте систему рівнянь за наступним шаблоном:⇀∇f(x0,y0)=λ⇀∇g(x0,y0)g(x0,y0)=0.
- Вирішити дляx0 іy0.
- Найбільша з значеньf при розв'язках, знайдених в кроці,3 максимізуєf; найменші з цих значень мінімізуютьсяf.
Використовуйте метод множників Лагранжа, щоб знайти мінімальне значенняf(x,y)=x2+4y2−2x+8y підлягає обмеженнюx+2y=7.
Рішення
Давайте слідувати стратегії вирішення проблем:
1. Мета функції полягаєf(x,y)=x2+4y2−2x+8y. в тому, щоб визначити функцію обмеження, ми повинні спочатку відняти7 з обох сторін обмеження. Цеx+2y−7=0. дає функцію обмеження дорівнює лівій стороні, так щоg(x,y)=x+2y−7. Задача просить нас вирішити для мінімального значенняf, з урахуванням обмежень (рис.14.8.3).

2. Потім ми повинні обчислити градієнти обохf іg:
⇀∇f(x,y)=(2x−2)ˆi+(8y+8)ˆj⇀∇g(x,y)=ˆi+2ˆj.
Рівняння⇀∇f(x0,y0)=λ⇀∇g(x0,y0) стає
(2x0−2)ˆi+(8y0+8)ˆj=λ(ˆi+2ˆj),
які можна переписати як
(2x0−2)ˆi+(8y0+8)ˆj=λˆi+2λˆj.
Далі встановлюємо коефіцієнтиˆi іˆj рівні один одному:
2x0−2=λ8y0+8=2λ.
Рівнянняg(x0,y0)=0 стаєx0+2y0−7=0. Тому система рівнянь, яку потрібно розв'язати, є
2x0−2=λ8y0+8=2λx0+2y0−7=0.
3. Це лінійна система з трьох рівнянь в трьох змінних. Починаємо з вирішення другого рівняння дляλ і підстановки його в перше рівняння. Це даєλ=4y0+4, тому підставляючи це в перше рівняння дає2x0−2=4y0+4. Розв'язування цього рівняння дляx0 даєx0=2y0+3. Потім підставляємо це в третє рівняння:
(2y0+3)+2y0−7=04y0−4=0y0=1.
Так якx0=2y0+3, це даєx0=5.
4. Далі, ми оцінюємоf(x,y)=x2+4y2−2x+8y в точці(5,1),f(5,1)=52+4(1)2−2(5)+8(1)=27. Щоб переконатися, що це відповідає мінімальному значенню на функцію обмеження, давайте спробуємо деякі інші точки на обмеження з обох сторін точки(5,1), такі як перехопленняg(x,y)=0, Які є(7,0) і(0,3.5).
Отримуємоf(7,0)=35>27 іf(0,3.5)=77>27.
Таким чином, виявляється, щоf має відносний27 мінімум at(5,1), з урахуванням заданого обмеження.
Використовуйте метод множників Лагранжа, щоб знайти максимальне значення
f(x,y)=9x2+36xy−4y2−18x−8y
за умови обмеження3x+4y=32.
- Підказка
-
Використовувати стратегію розв'язання задач для методу множників Лагранжа.
- Відповідь
-
Підлягає заданому обмеженню,f має максимальне значення976 в точці(8,2).
Давайте тепер повернемося до проблеми, поставленої на початку розділу.
Виробник м'ячів для гольфу Pro-T розробив модель прибутку, яка залежить відx кількості проданих м'ячів для гольфу на місяць (вимірюється тисячами) та кількості годин на місяць реклами y, відповідно до функції
z=f(x,y)=48x+96y−x2−2xy−9y2,
деz вимірюється тисячами доларів. Функція бюджетних обмежень, що стосуються витрат на виробництво тисяч м'ячів для гольфу та рекламних одиниць, дається20x+4y=216. Знайти значенняx іy які максимізувати прибуток, і знайти максимальний прибуток.
Рішення:
Знову ж таки, дотримуємося стратегії вирішення проблем:
- Мета функції полягаєf(x,y)=48x+96y−x2−2xy−9y2. в тому, щоб визначити функцію обмеження, ми спочатку віднімаємо216 з обох сторін обмеження, потім розділити обидві сторони на4, що дає5x+y−54=0. функція обмеження дорівнює лівій стороні, томуg(x,y)=5x+y−54. проблема просить нас вирішити для максимальне значенняf, з урахуванням цього обмеження.
- Отже, ми обчислюємо градієнти обохf іg:⇀∇f(x,y)=(48−2x−2y)ˆi+(96−2x−18y)ˆj⇀∇g(x,y)=5ˆi+ˆj. рівняння⇀∇f(x0,y0)=λ⇀∇g(x0,y0) стає(48−2x0−2y0)ˆi+(96−2x0−18y0)ˆj=λ(5ˆi+ˆj), яке можна переписати, як(48−2x0−2y0)ˆi+(96−2x0−18y0)ˆj=λ5ˆi+λˆj. Ми потім встановлюємо коефіцієнтиˆi іˆj рівні один одному:48−2x0−2y0=5λ96−2x0−18y0=λ. Рівнянняg(x0,y0)=0 стає5x0+y0−54=0. Тому система рівнянь, яку потрібно розв'язати, є48−2x0−2y0=5λ96−2x0−18y0=λ5x0+y0−54=0.
- Ми використовуємо ліву частину другого рівняння для заміниλ в першому рівнянні:48−2x0−2y0=5(96−2x0−18y0)48−2x0−2y0=480−10x0−90y08x0=432−88y0x0=54−11y0. Тоді ми підставляємо це в третє рівняння:5(54−11y0)+y0−54=0270−55y0+y0−54=0216−54y0=0y0=4. Оскількиx0=54−11y0, це даєx0=10.
- Потім ми підставляємо(10,4) вf(x,y)=48x+96y−x2−2xy−9y2, який даєf(10,4)=48(10)+96(4)−(10)2−2(10)(4)−9(4)2=480+384−100−80−144=540. Тому максимальний прибуток, який може бути досягнутий,$540,000 з урахуванням бюджетних обмежень, - це рівень виробництва м'ячів10,000 для гольфу та4 годин реклами, купленої на місяць. Давайте перевіримо, щоб переконатися, що це дійсно максимум. Кінцеві точки лінії, яка визначає обмеження,(10.8,0) і(0,54) Давайте оцінюємоf в обох цих точках:f(10.8,0)=48(10.8)+96(0)−10.82−2(10.8)(0)−9(02)=401.76f(0,54)=48(0)+96(54)−02−2(0)(54)−9(542)=−21,060. Друге значення являє собою втрату, оскільки не виробляються м'ячі для гольфу. Жодне з цих значень не перевищує540, тому здається, що наш екстремум є максимальним значеннямf, з урахуванням заданого обмеження.
Компанія визначила, що рівень її виробництва визначається функцієюf(x,y)=2.5x0.45y0.55 Кобба-Дугласа, якаx представляє загальну кількість робочих годин у1 році таy представляє загальний капітал для компанії. Припустимо1 одиницю витрат праці$40 і1 одиницю капітальних витрат$50. Використовуйте метод множників Лагранжа, щоб знайти максимальне значенняf(x,y)=2.5x0.45y0.55 підлягає бюджетному обмеженню$500,000 в рік.
- Підказка
-
Використовувати стратегію розв'язання задач для методу множників Лагранжа.
- Відповідь
-
З урахуванням даного обмеження, максимальний рівень виробництва13890 відбувається з5625 робочими годинами та$5500 загальним капіталом.
У випадку об'єктивної функції з трьома змінними та єдиною функцією обмеження можна також використовувати метод множників Лагранжа для розв'язання задачі оптимізації. Прикладом об'єктивної функції з трьома змінними може бути функція Кобба-Дугласа у Вправи14.8.2:f(x,y,z)=x0.2y0.4z0.4, деx представляє вартість робочої сили,y представляє вкладення капіталу таz представляє вартість реклами. Метод такий же, як і для методу з функцією двох змінних; рівняння, що підлягають розв'язанню
⇀∇f(x,y,z)=λ⇀∇g(x,y,z)g(x,y,z)=0.
Максимізувати функцію, щоf(x,y,z)=x2+y2+z2 підлягає обмеженнюx+y+z=1.
Рішення
1. Мета функції полягаєf(x,y,z)=x2+y2+z2. в тому, щоб визначити функцію обмеження, ми віднімаємо1 з кожної сторони обмеження:x+y+z−1=0 що дає функцію обмеження якg(x,y,z)=x+y+z−1.
2. Далі ми обчислюємо⇀∇f(x,y,z) і⇀∇g(x,y,z):⇀∇f(x,y,z)=⟨2x,2y,2z⟩⇀∇g(x,y,z)=⟨1,1,1⟩. Це призводить до рівнянь⟨2x0,2y0,2z0⟩=λ⟨1,1,1⟩x0+y0+z0−1=0, які можна переписати в наступному вигляді:2x0=λ2y0=λ2z0=λx0+y0+z0−1=0.
3. Оскільки кожне з перших трьох рівнянь маєλ на правій стороні, ми знаємо, що2x0=2y0=2z0 і всі три змінні рівні один одному. Підстановкаy0=x0 іz0=x0 в останнє рівняння дає3x0−1=0, такx0=13y0=13 і іz0=13 яке відповідає критичній точці на кривій обмеження.
4. Потім ми оцінюємоf в точці(13,13,13):f(13,13,13)=(13)2+(13)2+(13)2=39=13 Отже, можливий екстремум функції є13. Щоб переконатися, що це мінімум, виберіть інші точки, які задовольняють обмеженню з обох боків точки, яку ми отримали вище, і обчислитиf в цих точках. Наприклад,f(1,0,0)=12+02+02=1f(0,−2,3)=02++(−2)2+32=13. Обидва ці значення більше13, ніж, приводячи нас до думки, що екстремум є мінімумом, з урахуванням даного обмеження.
Використовуйте метод множників Лагранжа, щоб знайти мінімальне значення функції
f(x,y,z)=x+y+z
за умови обмеженняx2+y2+z2=1.
- Підказка
-
Використовувати стратегію розв'язання задач для методу множників Лагранжа з цільовою функцією трьох змінних.
- Відповідь
-
Оцінкаf в обох точках, які ми отримали, дає нам,f(√33,√33,√33)=√33+√33+√33=√3f(−√33,−√33,−√33)=−√33−√33−√33=−√3 так як обмеження є безперервним, ми порівнюємо ці значення і робимо висновок, щоf має відносний мінімум−√3 в точці(−√33,−√33,−√33), з урахуванням даного обмеження.
Проблеми з двома обмеженнями
Метод множників Лагранжа може бути застосований до задач з більш ніж одним обмеженням. В даному випадку об'єктивною функцією,w є функція трьох змінних:
w=f(x,y,z)
і вона підпорядковується двом обмеженням:
g(x,y,z)=0andh(x,y,z)=0.
Є два множника Лагранжа,λ1 іλ2, і система рівнянь стає
⇀∇f(x0,y0,z0)=λ1⇀∇g(x0,y0,z0)+λ2⇀∇h(x0,y0,z0)g(x0,y0,z0)=0h(x0,y0,z0)=0
Знайти максимальне і мінімальне значення функції
f(x,y,z)=x2+y2+z2
з урахуванням обмеженьz2=x2+y2 іx+y−z+1=0.
Рішення
Давайте слідувати стратегії вирішення проблем:
- Мета функції полягаєf(x,y,z)=x2+y2+z2. в тому, щоб визначити функції обмеження, ми спочатку віднімаємоz2 з обох сторін першого обмеження, яке даєx2+y2−z2=0, такg(x,y,z)=x2+y2−z2. Друга функція обмеження:h(x,y,z)=x+y−z+1.
- Потім ми обчислюємо градієнтиf,g, іh:⇀∇f(x,y,z)=2xˆi+2yˆj+2zˆk⇀∇g(x,y,z)=2xˆi+2yˆj−2zˆk⇀∇h(x,y,z)=ˆi+ˆj−ˆk. рівняння⇀∇f(x0,y0,z0)=λ1⇀∇g(x0,y0,z0)+λ2⇀∇h(x0,y0,z0) стає2x0ˆi+2y0ˆj+2z0ˆk=λ1(2x0ˆi+2y0ˆj−2z0ˆk)+λ2(ˆi+ˆj−ˆk), яке може бути переписано як2x0ˆi+2y0ˆj+2z0ˆk=(2λ1x0+λ2)ˆi+(2λ1y0+λ2)ˆj−(2λ1z0+λ2)ˆk. Далі, ми встановлюємо коефіцієнтиˆi іˆj рівні один одному:2x0=2λ1x0+λ22y0=2λ1y0+λ22z0=−2λ1z0−λ2. Два рівняння, що виникають з обмежень є z20=x20+y20іx0+y0−z0+1=0. Поєднання цих рівнянь з попередніми трьома рівняннями дає2x0=2λ1x0+λ22y0=2λ1y0+λ22z0=−2λ1z0−λ2z20=x20+y20x0+y0−z0+1=0.
- Перші три рівняння містять зміннуλ2. Розв'язування третього рівняння дляλ2 і заміна в перше і друге рівняння зменшує кількість рівнянь до чотирьох:2x0=2λ1x0−2λ1z0−2z02y0=2λ1y0−2λ1z0−2z0z20=x20+y20x0+y0−z0+1=0. Далі вирішуємо перше і друге рівняння дляλ1. Перше рівняння даєλ1=x0+z0x0−z0, друге рівняння даєλ1=y0+z0y0−z0. Ми ставимо праву частину кожного рівняння рівною один одному і перехресно множимо:x0+z0x0−z0=y0+z0y0−z0(x0+z0)(y0−z0)=(x0−z0)(y0+z0)x0y0−x0z0+y0z0−z20=x0y0+x0z0−y0z0−z202y0z0−2x0z0=02z0(y0−x0)=0. Отже, абоz0=0 абоy0=x0. Якщоz0=0, то першим стає обмеження0=x20+y20. Єдиним реальним рішенням цього рівняння єx0=0 іy0=0, який дає впорядковану трійку(0,0,0). Цей момент не задовольняє другому обмеженню, тому він не є рішенням. Далі розглянемоy0=x0, що зменшує кількість рівнянь до трьох:y0=x0z20=x20+y20x0+y0−z0+1=0. підставляємо перше рівняння в друге і третє рівняння:z20=x20+x20=x0+x0−z0+1=0. Потім, вирішуємо друге рівняння дляz0, яке даєz0=2x0+1. Потім ми підставляємо це в перше рівнянняz20=2x20(2x20+1)2=2x204x20+4x0+1=2x202x20+4x0+1=0, і використовуємо квадратичну формулу для вирішення дляx0:x0=−4±√42−4(2)(1)2(2)=−4±√84=−4±2√24=−1±√22. Відкликатиy0=x0, так що це вирішуєy0 також. Тоді,z0=2x0+1=2(−1±√22)+1=−2+1±√2=−1±√2. отжеz0=2x0+1, є два впорядкованих триплетних рішення:(−1+√22,−1+√22,−1+√2)and(−1−√22,−1−√22,−1−√2).
- Ми підставляємо(−1+√22,−1+√22,−1+√2) вf(x,y,z)=x2+y2+z2, який даєf(−1+√22,−1+√22,−1+√2)=(−1+√22)2+(−1+√22)2+(−1+√2)2=(1−√2+12)+(1−√2+12)+(1−2√2+2)=6−4√2. Потім, ми підставляємо(−1−√22,−1+√22,−1+√2) вf(x,y,z)=x2+y2+z2, який даєf(−1−√22,−1+√22,−1+√2)=(−1−√22)2+(−1−√22)2+(−1−√2)2=(1+√2+12)+(1+√2+12)+(1+2√2+2)=6+4√2.6+4√2 максимальне значення і6−4√2 є мінімальним значеннямf(x,y,z), з урахуванням заданих обмежень.
Використовуйте метод множників Лагранжа, щоб знайти мінімальне значення функції
f(x,y,z)=x2+y2+z2
з урахуванням обмежень2x+y+2z=9 і5x+5y+7z=29.
- Підказка
-
Використовувати стратегію розв'язання задач для методу множників Лагранжа з двома обмеженнями.
- Відповідь
-
f(2,1,2)=9є мінімальним значеннямf, з урахуванням заданих обмежень.
Ключові концепції
- Цільова функція в поєднанні з одним або декількома обмеженнями є прикладом задачі оптимізації.
- Для розв'язання задач оптимізації застосовується метод множників Лагранжа, використовуючи чотириступінчасту стратегію розв'язання задач.
Ключові рівняння
- Метод множників Лагранжа, одне обмеження
⇀∇f(x0,y0)=λ⇀∇g(x0,y0)
g(x0,y0)=0
- Метод множників Лагранжа, два обмеження
⇀∇f(x0,y0,z0)=λ1⇀∇g(x0,y0,z0)+λ2⇀∇h(x0,y0,z0)
g(x0,y0,z0)=0
h(x0,y0,z0)=0
Глосарій
- обмеження
- нерівність або рівняння за участю однієї або декількох змінних, яка використовується в задачі оптимізації; обмеження встановлює обмеження на можливі рішення задачі
- множник Лагранжа
- константа (або константи), що використовується в методі множників Лагранжа; у випадку однієї константи вона представлена змінноюλ
- метод множників Лагранжа
- метод розв'язання задачі оптимізації з урахуванням одного або декількох обмежень
- об'єктивна функція
- функція, яка повинна бути максимізована або мінімізована в задачі оптимізації
- проблема оптимізації
- обчислення максимального або мінімального значення функції декількох змінних, часто з використанням множників Лагранжа