Processing math: 100%
Skip to main content
LibreTexts - Ukrayinska

14.8: Множники Лагранжа

  • Edwin “Jed” Herman & Gilbert Strang
  • OpenStax

Цілі навчання
  • Використовувати метод множників Лагранжа для вирішення задач оптимізації з одним обмеженням.
  • Використовувати метод множників Лагранжа для вирішення задач оптимізації з двома обмеженнями.

Розв'язування задач оптимізації функцій двох і більше змінних може бути аналогічним вирішенню таких задач в однозмінному численні. Однак методи боротьби з декількома змінними дозволяють нам вирішувати більш різноманітні задачі оптимізації, для яких нам потрібно мати справу з додатковими умовами або обмеженнями. У цьому розділі ми розглянемо один з найбільш поширених і корисних методів вирішення задач оптимізації з обмеженнями.

Мультиплікатори Лагранжа

У попередньому розділі була досліджена прикладна ситуація, яка передбачає максимізацію функції прибутку з урахуванням певних обмежень. У цьому прикладі обмеження включали максимальну кількість м'ячів для гольфу, які можуть бути вироблені і продані в1 місяць(x), і максимальну кількість рекламних годин, які можуть бути придбані на місяць(y). Припустимо, вони були об'єднані в єдине бюджетне обмеження20x+4y216, наприклад, що враховували як витрати на виробництво м'ячів для гольфу, так і кількість рекламних годин, придбаних на місяць. Мета все ж полягає в тому, щоб максимізувати прибуток, але зараз існує інший тип обмеження на значенняx іy. Це обмеження і відповідна функція прибутку

f(x,y)=48x+96yx22xy9y2

є прикладом задачі оптимізації, а функціяf(x,y) називається об'єктивною функцією. Даліf(x,y) йде графік різних кривих рівня функції.

Серія обертаються еліпсів, які стають все більшими. Найменша з них маркується f (x, y) = 400, а найбільша маркується f (x, y) = 150.
Малюнок14.8.1: Графік, що показує криві рівня функції,f(x,y)=48x+96yx22xy9y2 що відповідаютьc=150,250,350, і400.

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

Серія обертаються еліпсів, які стають все більшими. На найменшому еліпсі, який є червоним, є дотична лінія, позначена рівнянням 20x+ 4y = 216, яка, здається, торкається еліпса поблизу (10, 4).
Малюнок14.8.2: Графік кривих рівня функції,f(x,y)=48x+96yx22xy9y2 що відповідаєc=150,250,350, і395. Червоний графік - це функція обмеження.

Як вже говорилося раніше, максимальний прибуток виникає, коли крива рівня знаходиться якнайдалі вправо. Однак рівень виробництва, відповідний цьому максимальному прибутку, також повинен задовольняти бюджетному обмеженню, тому точка, в якій відбувається цей прибуток, також повинна лежати на (або ліворуч) червоній лінії на малюнку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=fxxs+fyys=(fxˆi+fyˆj)(xsˆi+ysˆ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 до задачі оптимізації, подібної до проблеми виробника м'ячів для гольфу, нам потрібна стратегія вирішення проблем.

Стратегія вирішення проблем: кроки для використання множників Лагранжа
  1. Визначтеf(x,y) цільову функцію та функцію обмеженняg(x,y). Чи передбачає задача оптимізації максимізації або мінімізації цільової функції?
  2. Налаштуйте систему рівнянь за наступним шаблоном:f(x0,y0)=λg(x0,y0)g(x0,y0)=0.
  3. Вирішити дляx0 іy0.
  4. Найбільша з значеньf при розв'язках, знайдених в кроці,3 максимізуєf; найменші з цих значень мінімізуютьсяf.
Приклад14.8.1: Using Lagrange Multipliers

Використовуйте метод множників Лагранжа, щоб знайти мінімальне значенняf(x,y)=x2+4y22x+8y підлягає обмеженнюx+2y=7.

Рішення

Давайте слідувати стратегії вирішення проблем:

1. Мета функції полягаєf(x,y)=x2+4y22x+8y. в тому, щоб визначити функцію обмеження, ми повинні спочатку відняти7 з обох сторін обмеження. Цеx+2y7=0. дає функцію обмеження дорівнює лівій стороні, так щоg(x,y)=x+2y7. Задача просить нас вирішити для мінімального значенняf, з урахуванням обмежень (рис.14.8.3).

Два обертаються еліпса, один всередині іншого. На найбільшому еліпсі, який позначений f (x, y) = 26, є дотична лінія, позначена рівнянням x + 2y = 7, яка, здається, торкається еліпса поблизу (5, 1).
Малюнок14.8.3: Графік кривих рівня функції,f(x,y)=x2+4y22x+8y що відповідаєc=10 і26. Червоний графік - це функція обмеження.

2. Потім ми повинні обчислити градієнти обохf іg:

f(x,y)=(2x2)ˆi+(8y+8)ˆjg(x,y)=ˆi+2ˆj.

Рівнянняf(x0,y0)=λg(x0,y0) стає

(2x02)ˆi+(8y0+8)ˆj=λ(ˆi+2ˆj),

які можна переписати як

(2x02)ˆi+(8y0+8)ˆj=λˆi+2λˆj.

Далі встановлюємо коефіцієнтиˆi іˆj рівні один одному:

2x02=λ8y0+8=2λ.

Рівнянняg(x0,y0)=0 стаєx0+2y07=0. Тому система рівнянь, яку потрібно розв'язати, є

2x02=λ8y0+8=2λx0+2y07=0.

3. Це лінійна система з трьох рівнянь в трьох змінних. Починаємо з вирішення другого рівняння дляλ і підстановки його в перше рівняння. Це даєλ=4y0+4, тому підставляючи це в перше рівняння дає2x02=4y0+4. Розв'язування цього рівняння дляx0 даєx0=2y0+3. Потім підставляємо це в третє рівняння:

(2y0+3)+2y07=04y04=0y0=1.

Так якx0=2y0+3, це даєx0=5.

4. Далі, ми оцінюємоf(x,y)=x2+4y22x+8y в точці(5,1),f(5,1)=52+4(1)22(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), з урахуванням заданого обмеження.

Вправа14.8.1

Використовуйте метод множників Лагранжа, щоб знайти максимальне значення

f(x,y)=9x2+36xy4y218x8y

за умови обмеження3x+4y=32.

Підказка

Використовувати стратегію розв'язання задач для методу множників Лагранжа.

Відповідь

Підлягає заданому обмеженню,f має максимальне значення976 в точці(8,2).

Давайте тепер повернемося до проблеми, поставленої на початку розділу.

Приклад14.8.2: Golf Balls and Lagrange Multipliers

Виробник м'ячів для гольфу Pro-T розробив модель прибутку, яка залежить відx кількості проданих м'ячів для гольфу на місяць (вимірюється тисячами) та кількості годин на місяць реклами y, відповідно до функції

z=f(x,y)=48x+96yx22xy9y2,

деz вимірюється тисячами доларів. Функція бюджетних обмежень, що стосуються витрат на виробництво тисяч м'ячів для гольфу та рекламних одиниць, дається20x+4y=216. Знайти значенняx іy які максимізувати прибуток, і знайти максимальний прибуток.

Рішення:

Знову ж таки, дотримуємося стратегії вирішення проблем:

  1. Мета функції полягаєf(x,y)=48x+96yx22xy9y2. в тому, щоб визначити функцію обмеження, ми спочатку віднімаємо216 з обох сторін обмеження, потім розділити обидві сторони на4, що дає5x+y54=0. функція обмеження дорівнює лівій стороні, томуg(x,y)=5x+y54. проблема просить нас вирішити для максимальне значенняf, з урахуванням цього обмеження.
  2. Отже, ми обчислюємо градієнти обохf іg:f(x,y)=(482x2y)ˆi+(962x18y)ˆjg(x,y)=5ˆi+ˆj. рівнянняf(x0,y0)=λg(x0,y0) стає(482x02y0)ˆi+(962x018y0)ˆj=λ(5ˆi+ˆj), яке можна переписати, як(482x02y0)ˆi+(962x018y0)ˆj=λ5ˆi+λˆj. Ми потім встановлюємо коефіцієнтиˆi іˆj рівні один одному:482x02y0=5λ962x018y0=λ. Рівнянняg(x0,y0)=0 стає5x0+y054=0. Тому система рівнянь, яку потрібно розв'язати, є482x02y0=5λ962x018y0=λ5x0+y054=0.
  3. Ми використовуємо ліву частину другого рівняння для заміниλ в першому рівнянні:482x02y0=5(962x018y0)482x02y0=48010x090y08x0=43288y0x0=5411y0. Тоді ми підставляємо це в третє рівняння:5(5411y0)+y054=027055y0+y054=021654y0=0y0=4. Оскількиx0=5411y0, це даєx0=10.
  4. Потім ми підставляємо(10,4) вf(x,y)=48x+96yx22xy9y2, який даєf(10,4)=48(10)+96(4)(10)22(10)(4)9(4)2=480+38410080144=540. Тому максимальний прибуток, який може бути досягнутий,$540,000 з урахуванням бюджетних обмежень, - це рівень виробництва м'ячів10,000 для гольфу та4 годин реклами, купленої на місяць. Давайте перевіримо, щоб переконатися, що це дійсно максимум. Кінцеві точки лінії, яка визначає обмеження,(10.8,0) і(0,54) Давайте оцінюємоf в обох цих точках:f(10.8,0)=48(10.8)+96(0)10.822(10.8)(0)9(02)=401.76f(0,54)=48(0)+96(54)022(0)(54)9(542)=21,060. Друге значення являє собою втрату, оскільки не виробляються м'ячі для гольфу. Жодне з цих значень не перевищує540, тому здається, що наш екстремум є максимальним значеннямf, з урахуванням заданого обмеження.
Вправа14.8.2: Optimizing the Cobb-Douglas function

Компанія визначила, що рівень її виробництва визначається функцією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.

Приклад14.8.3: Lagrange Multipliers with a Three-Variable objective function

Максимізувати функцію, щоf(x,y,z)=x2+y2+z2 підлягає обмеженнюx+y+z=1.

Рішення

1. Мета функції полягаєf(x,y,z)=x2+y2+z2. в тому, щоб визначити функцію обмеження, ми віднімаємо1 з кожної сторони обмеження:x+y+z1=0 що дає функцію обмеження якg(x,y,z)=x+y+z1.

2. Далі ми обчислюємоf(x,y,z) іg(x,y,z):f(x,y,z)=2x,2y,2zg(x,y,z)=1,1,1. Це призводить до рівнянь2x0,2y0,2z0=λ1,1,1x0+y0+z01=0, які можна переписати в наступному вигляді:2x0=λ2y0=λ2z0=λx0+y0+z01=0.

3. Оскільки кожне з перших трьох рівнянь маєλ на правій стороні, ми знаємо, що2x0=2y0=2z0 і всі три змінні рівні один одному. Підстановкаy0=x0 іz0=x0 в останнє рівняння дає3x01=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, ніж, приводячи нас до думки, що екстремум є мінімумом, з урахуванням даного обмеження.

Вправа14.8.3

Використовуйте метод множників Лагранжа, щоб знайти мінімальне значення функції

f(x,y,z)=x+y+z

за умови обмеженняx2+y2+z2=1.

Підказка

Використовувати стратегію розв'язання задач для методу множників Лагранжа з цільовою функцією трьох змінних.

Відповідь

Оцінкаf в обох точках, які ми отримали, дає нам,f(33,33,33)=33+33+33=3f(33,33,33)=333333=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)=λ1g(x0,y0,z0)+λ2h(x0,y0,z0)g(x0,y0,z0)=0h(x0,y0,z0)=0

Приклад14.8.4: Lagrange Multipliers with Two Constraints

Знайти максимальне і мінімальне значення функції

f(x,y,z)=x2+y2+z2

з урахуванням обмеженьz2=x2+y2 іx+yz+1=0.

Рішення

Давайте слідувати стратегії вирішення проблем:

  1. Мета функції полягаєf(x,y,z)=x2+y2+z2. в тому, щоб визначити функції обмеження, ми спочатку віднімаємоz2 з обох сторін першого обмеження, яке даєx2+y2z2=0, такg(x,y,z)=x2+y2z2. Друга функція обмеження:h(x,y,z)=x+yz+1.
  2. Потім ми обчислюємо градієнтиf,g, іh:f(x,y,z)=2xˆi+2yˆj+2zˆkg(x,y,z)=2xˆi+2yˆj2zˆkh(x,y,z)=ˆi+ˆjˆk. рівнянняf(x0,y0,z0)=λ1g(x0,y0,z0)+λ2h(x0,y0,z0) стає2x0ˆi+2y0ˆj+2z0ˆk=λ1(2x0ˆi+2y0ˆj2z0ˆ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+y0z0+1=0. Поєднання цих рівнянь з попередніми трьома рівняннями дає2x0=2λ1x0+λ22y0=2λ1y0+λ22z0=2λ1z0λ2z20=x20+y20x0+y0z0+1=0.
  3. Перші три рівняння містять зміннуλ2. Розв'язування третього рівняння дляλ2 і заміна в перше і друге рівняння зменшує кількість рівнянь до чотирьох:2x0=2λ1x02λ1z02z02y0=2λ1y02λ1z02z0z20=x20+y20x0+y0z0+1=0. Далі вирішуємо перше і друге рівняння дляλ1. Перше рівняння даєλ1=x0+z0x0z0, друге рівняння даєλ1=y0+z0y0z0. Ми ставимо праву частину кожного рівняння рівною один одному і перехресно множимо:x0+z0x0z0=y0+z0y0z0(x0+z0)(y0z0)=(x0z0)(y0+z0)x0y0x0z0+y0z0z20=x0y0+x0z0y0z0z202y0z02x0z0=02z0(y0x0)=0. Отже, абоz0=0 абоy0=x0. Якщоz0=0, то першим стає обмеження0=x20+y20. Єдиним реальним рішенням цього рівняння єx0=0 іy0=0, який дає впорядковану трійку(0,0,0). Цей момент не задовольняє другому обмеженню, тому він не є рішенням. Далі розглянемоy0=x0, що зменшує кількість рівнянь до трьох:y0=x0z20=x20+y20x0+y0z0+1=0. підставляємо перше рівняння в друге і третє рівняння:z20=x20+x20=x0+x0z0+1=0. Потім, вирішуємо друге рівняння дляz0, яке даєz0=2x0+1. Потім ми підставляємо це в перше рівнянняz20=2x20(2x20+1)2=2x204x20+4x0+1=2x202x20+4x0+1=0, і використовуємо квадратичну формулу для вирішення дляx0:x0=4±424(2)(1)2(2)=4±84=4±224=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(122,122,12).
  4. Ми підставляємо(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=(12+12)+(12+12)+(122+2)=642. Потім, ми підставляємо(122,1+22,1+2) вf(x,y,z)=x2+y2+z2, який даєf(122,1+22,1+2)=(122)2+(122)2+(12)2=(1+2+12)+(1+2+12)+(1+22+2)=6+42.6+42 максимальне значення і642 є мінімальним значеннямf(x,y,z), з урахуванням заданих обмежень.
Вправа14.8.4

Використовуйте метод множників Лагранжа, щоб знайти мінімальне значення функції

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)=λ1g(x0,y0,z0)+λ2h(x0,y0,z0)

g(x0,y0,z0)=0

h(x0,y0,z0)=0

Глосарій

обмеження
нерівність або рівняння за участю однієї або декількох змінних, яка використовується в задачі оптимізації; обмеження встановлює обмеження на можливі рішення задачі
множник Лагранжа
константа (або константи), що використовується в методі множників Лагранжа; у випадку однієї константи вона представлена змінноюλ
метод множників Лагранжа
метод розв'язання задачі оптимізації з урахуванням одного або декількох обмежень
об'єктивна функція
функція, яка повинна бути максимізована або мінімізована в задачі оптимізації
проблема оптимізації
обчислення максимального або мінімального значення функції декількох змінних, часто з використанням множників Лагранжа