Економічний сенс множників Лагранжа. Метод множників Лагранжа

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

Розглянемо класичне завдання оптимізації

max (min) z=f(x) (7.20)

Це завдання виділяється із завдання (7.18), (7.19) тим, що серед обмежень (7.21) немає нерівностей, немає умов невід'ємності змінних, їх дискретності, і функції f(x) і безперервні і мають приватні похідні Крайній мірідругого порядку.

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

Припустимо, що у точці х* функція (7.20) має локальний умовний екстремумі ранг матриці дорівнює. Тоді необхідні умови запишуться у вигляді:

(7.22)

є функція Лагранжа; - множники Лагранжа.

Існують також і достатні умови, при виконанні яких розв'язання системи рівнянь (7.22) визначає точку екстремуму функції f(x). Це питання вирішується виходячи з дослідження знака другого диференціала функції Лагранжа. Однак достатні умови становлять головним чином теоретичний інтерес.

Можна вказати наступний порядок розв'язання задачі (7.20), (7.21) методом множників Лагранжа:

1) скласти функцію Лагранжа (7.23);

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

3) зі стаціонарних точок, взятих без координат , вибрати точки, у яких функція f(x) має умовні локальні екстремуми за наявності обмежень (7.21). Цей вибір здійснюється, наприклад, із застосуванням достатніх умов локального екстремуму. Часто дослідження спрощується, якщо використати конкретні умови завдання.

Приклад 7.3. Знайти оптимальний розподілобмеженого ресурсу в a од. між n споживачами, якщо прибуток, одержуваний при виділенні j-го споживача x j одиниць ресурсу, обчислюється за формулою .

Рішення.Математична модель завдання має такий вигляд:

Складаємо функцію Лагранжа:

.

Знаходимо приватні похідні функції Лагранжа та прирівнюємо їх нулю:

Вирішуючи цю систему рівнянь, отримуємо:

Таким чином, якщо j-му споживачеві буде виділено од. ресурсу, то сумарна прибуток досягне максимальної величини і становитиме ден. од.

Ми розглянули метод Лагранжа стосовно класичної задачі оптимізації. Можна узагальнити цей метод у разі, коли змінні неотрицательны і деякі обмеження задані у вигляді нерівностей. Однак це узагальнення має переважно теоретичне значення та не призводить до конкретних обчислювальних алгоритмів.

На закінчення дамо множникам Лагранжа економічну інтерпретацію. Для цього звернемося до найпростішого класичного завдання оптимізації.

max (min) z=f(x 1 , х 2); (7.24)

𝜑(x 1, х 2) = b. (7.25)

Припустимо, що умовний екстремум досягається у точці . Відповідне екстремальне значення функції f(x)

Допустимо, що в обмеженнях (7.25) величина bможе змінюватися, тоді координати точки екстремуму, а отже, і екстремальне значення f*функції f(x) стануть величинами, що залежать від b, тобто. ,, а тому похідна функції (7.24)

an(t)z(n)(t) + an − 1(t)z(n − 1)(t) + ... + a1(t)z"(t) + a0(t)z(t) = f(t)

полягає у заміні довільних постійних ck у загальному рішенні

z(t) = c1z1(t) + c2z2(t) + ...

Cnzn(t)

відповідного однорідного рівняння

an(t)z(n)(t) + an − 1(t)z(n − 1)(t) + ... + a1(t)z"(t) + a0(t)z(t) = 0

на допоміжні функції ck(t), похідні яких задовольняють лінійній системі алгебри

Визначником системи (1) служить вронскіан функцій z1,z2,...,zn, що забезпечує її однозначну роздільну здатність щодо .

Якщо - первісні для , взяті при фіксованих постійних значеннях інтегрування, то функція

є рішенням вихідного неоднорідного лінійного диференціального рівняння. Інтегрування неоднорідного рівнянняза наявності загального розв'язання відповідного однорідного рівняння зводиться таким чином до квадратур.

Метод Лагранжа (метод варіації довільних постійних)

Метод отримання загального рішення неоднорідного рівняння, знаючи загальне рішення однорідного рівняння без перебування приватного решения.

Для лінійного однорідного диференціального рівняння n-го порядку

y(n) + a1(x) y(n-1) + ... + an-1(x) y" + an(x) y = 0,

де y = y(x) – невідома функція, a1(x), a2(x), ..., an-1(x), an(x) – відомі, безперервні, справедливо: 1) існують n лінійно незалежних рішень рівняння y1(x), y2(x), ..., yn(x); 2) за будь-яких значень констант c1, c2, ..., cn функція y(x)= c1 y1(x) + c2 y2(x) + ... + cn yn(x) є рішенням рівняння; 3) для будь-яких початкових значень x0, y0, y0,1, ..., y0, n-1 існують такі значення c * 1, c * n, ..., c * n, що рішення y * (x) = c*1 y1(x) + c*2 y2(x) + ... + c*n yn(x) задовольняє при x = x0 початковим умовам y*(x0)=y0, (y*)"(x0) = y0,1, ..., (y *) (n-1) (x0) = y0, n-1.

Вираз y(x)= c1 y1(x) + c2 y2(x) + ... + cn yn(x) називається загальним рішеннямлінійного однорідного диференціального рівняння n-го порядку

Сукупність n лінійно незалежних рішень лінійного однорідного диференціального рівняння n-го порядку y1(x), y2(x), ..., yn(x) називається фундаментальною системою рішень рівняння.

Для лінійного однорідного диференціального рівняння з постійними коефіцієнтамиІснує простий алгоритм побудови фундаментальної системи рішень. Шукатимемо рішення рівняння у вигляді y(x) = exp(lx): exp(lx)(n) + a1exp(lx)(n-1) + ... + an-1exp(lx)" + anexp(lx) = = (ln + a1ln-1 + ... + an-1l + an)exp(lx) = 0, тобто число l є коренем характеристичного рівняння ln + a1ln-1 + ... + an-1l + an = 0. Ліва частина характеристичного рівняння називається характеристичним багаточленом лінійного диференціального рівняння: P(l) = ln + a1ln-1 + ... + an-1l + an. Таким чином, завдання про рішення лінійного однорідного рівняння n-го порядку з постійними коефіцієнтами зводиться до розв'язання рівня алгебри.

Якщо характеристичне рівняння має n різних дійсних коренів l1№ l2 № ... № ln, то фундаментальна система рішень складається з функцій y1(x) = exp(l1x), y2(x) = exp(l2x), ..., yn (x) = exp (lnx), і загальне рішення однорідного рівняння має вигляд: y (x) = c1 exp (l1x) + c2 exp (l2x) + ... + cn exp (lnx).

ундаментальна система рішень та загальне рішення для випадку простих дійсних коренів.

Якщо якесь із дійсних коренів характеристичного рівняння повторюється r разів (r-кратний корінь), то в фундаментальній системі рішень йому відповідають r функцій; якщо lk=lk+1 = ... = lk+r-1, то фундаментальну системурішень рівняння входять r функцій: yk(x) = exp(lkx), yk+1(x) = xexp(lkx), yk+2(x) = x2exp(lkx), ..., yk+r-1( x) = xr-1 exp (lnx).

ПРИКЛАД 2. Фундаментальна система рішень та загальне рішення для випадку кратного дійсного коріння.

Якщо характеристичне рівняння має комплексне коріння, то кожній парі простих (мають кратність 1) комплексного коріння lk,k+1=ak ± ibk у фундаментальній системі рішень відповідає пара функцій yk(x) = exp(akx)cos(bkx), yk+ 1(x) = exp(akx)sin(bkx).

ПРИКЛАД 4. Фундаментальна система рішень та загальне рішення для випадку простих комплексних коренів. Уявне коріння.

Якщо ж комплексна пара коренів має кратність r, то такий парі lk=lk+1 = ... = l2k+2r-1=ak ± ibk, у фундаментальній системі рішень відповідають функції exp(akx)cos(bkx), exp(akx )sin(bkx), xexp(akx)cos(bkx), xexp(akx)sin(bkx), x2exp(akx)cos(bkx), x2exp(akx)sin(bkx), ........ ........ xr-1exp(akx)cos(bkx), xr-1exp(akx)sin(bkx).

ПРИКЛАД 5. Фундаментальна система рішень та загальне рішення для випадку кратного комплексного коріння.

Таким чином, для віднайдення загального рішення лінійного однорідного диференціального рівняння з постійними коефіцієнтами слід записати характеристичне рівняння; знайти всі коріння характеристичного рівняння l1, l2, ..., ln; записати фундаментальну систему розв'язків y1(x), y2(x), ..., yn(x); записати вираз для загального рішення y(x) = c1 y1(x) + c2 y2(x) + ... + cn yn(x). Для вирішення задачі Коші потрібно підставити вираз для загального рішення в початкові умови та визначити значення постійних c1,..., cn, які є рішеннями системи лінійних алгебраїчних рівнянь c1 y1(x0) + c2 y2(x0) + ... + cn yn(x0) = y0, c1 y"1(x0) + c2 y"2(x0) + ... + cn y"n(x0 ) =y0,1, ......... , c1 y1(n-1)(x0) + c2 y2(n-1)(x0) + ... + cn yn(n-1)( x0) = y0,n-1

Для лінійного неоднорідного диференціального рівняння n-го порядку

y(n) + a1(x) y(n-1) + ... + an-1(x) y" + an(x) y = f(x),

де y = y(x) - невідома функція, a1(x), a2(x), ..., an-1(x), an(x), f(x) - відомі, безперервні, справедливо: 1) якщо y1(x) та y2(x) - два розв'язки неоднорідного рівняння, то функція y(x) = y1(x) - y2(x) - розв'язання відповідного однорідного рівняння; 2) якщо y1(x) розв'язання неоднорідного рівняння, а y2(x) - розв'язання відповідного однорідного рівняння, то функція y(x) = y1(x) + y2(x) - розв'язання неоднорідного рівняння; 3) якщо y1(x), y2(x), ..., yn(x) - n лінійно незалежних рішень однорідного рівняння, а yч(x) - довільне рішеннянеоднорідного рівняння, то будь-яких початкових значень x0, y0, y0,1, ..., y0,n-1 існують такі значення c*1, c*n, ..., c*n, що рішення y*(x )=c*1 y1(x) + c*2 y2(x) + ... + c*n yn(x) + yч(x) задовольняє при x = x0 початковим умовам y*(x0)=y0, ( y*)"(x0)=y0,1, ...,(y*)(n-1)(x0)=y0,n-1.

Вираз y(x)= c1 y1(x) + c2 y2(x) + ... + cn yn(x) + yч(x) називається загальним рішенням лінійного неоднорідного диференціального рівняння n-го порядку.

Для пошуку приватних рішень неоднорідних диференціальних рівняньз постійними коефіцієнтами з правими частинами виду: Pk(x)exp(ax)cos(bx) + Qm(x)exp(ax)sin(bx), де Pk(x), Qm(x) - багаточлени ступеня k і m відповідно, простий алгоритм побудови приватного рішення, званий методом підбору.

Метод підбору, чи метод невизначених коефіцієнтів, ось у чому. Розв'язання, що шукається, записується у вигляді: (Pr(x)exp(ax)cos(bx) + Qr(x)exp(ax)sin(bx))xs, де Pr(x), Qr(x) - багаточлени ступеня r = max(k, m) з невідомими коефіцієнтами pr, pr-1, ..., p1, p0, qr, qr-1, ..., q1, q0. Співмножник xs називають резонансним помножувачем. Резонанс має місце у випадках, коли серед коренів характеристичного рівняння є корінь l=a±ib кратності s. Тобто. якщо серед коренів характеристичного рівняння відповідного однорідного рівняння є такий, що його дійсна частина збігається з коефіцієнтом у показнику ступеня експоненти, а уявна - з коефіцієнтом в аргументі тригонометричної функції у правій частині рівняння, і кратність цього кореня s, то в шуканому приватному рішенні змішувач xs. Якщо такого збігу немає (s=0), то резонансний співмножник відсутній.

Підставивши вираз для приватного рішення в ліву частину рівняння, отримаємо узагальнений багаточлен того ж виду, що багаточлен у правій частині рівняння, коефіцієнти якого невідомі.

Два узагальнених многочлена рівні тоді і лише тоді, коли рівні коефіцієнти при співмножниках виду xtexp(ax)sin(bx), xtexp(ax)cos(bx) з однаковими ступенями t. Прирівнявши коефіцієнти при таких співмножниках, отримаємо систему 2(r+1) лінійних рівнянь алгебри щодо 2(r+1) невідомих. Можна показати, що така система є спільною і має єдине рішення.

Коротка теорія

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

Розглянемо класичне завдання оптимізації:

Серед обмежень цього завдання немає нерівностей, немає умов невід'ємності змінних, їх дискретності, функції і безперервні і мають приватні похідні принаймні другого порядку.

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

Припустимо, що у точці функція (1) має локальний умовний екстремум і ранг матриці дорівнює . Тоді необхідні умови запишуться у вигляді:

є функція Лагранжа; – множники Лагранжа.

Існують також і достатні умови, при виконанні яких розв'язання системи рівнянь (3) визначає точку екстремуму функції. Це питання вирішується виходячи з дослідження знака другого диференціала функції Лагранжа. Однак достатні умови становлять головним чином теоретичний інтерес.

Можна вказати наступний порядок розв'язання задачі (1), (2) методом множників Лагранжа:

1) скласти функцію Лагранжа (4);

2) знайти приватні похідні функції Лагранжа за всіма змінними і прирівняти їх

нулю. Тим самим буде отримана система (3, що складається з рівнянь. Вирішити отриману систему (якщо це виявиться можливим!) і знайти таким чином усі стаціонарні точки функції Лагранжа;

3) зі стаціонарних точок, взятих без координат, вибрати точки, в яких функція має умовні локальні екстремуми за наявності обмежень (2). Цей вибір здійснюється, наприклад, із застосуванням достатніх умов локального екстремуму. Часто дослідження спрощується, якщо використати конкретні умови завдання.

Приклад розв'язання задачі

Умова задачі

Фірма виробляє товар двох видів у кількостях та . Функція корисних витрат визначена співвідношенням. Ціни цих товарів на ринку рівні та відповідно.

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

Зазнаєте складнощів з розумінням ходу рішення? На сайті діє послуга Розв'язання задач за методами оптимальних рішень на замовлення

Рішення задачі

Економіко-математична модель задачі

Функція прибутку:

Обмеження на витрати:

Отримуємо наступну економіко-математичну модель:

Крім того, за змістом завдання

Метод множників Лагранжа

Складемо функцію Лагранжа:

Знаходимо приватні похідні 1-го порядку:

Складемо і розв'яжемо систему рівнянь:

Оскільки , то

Максимальний прибуток:

Відповідь

У такий спосіб необхідно випускати од. товару 1-го виду та од. товару 2-го виду. При цьому прибуток буде максимальним і складе 270.
Наведено зразок розв'язання задачі опуклого квадратичного програмування графічним методом.

Розв'язання лінійного завдання графічним методом
Розглянуто графічний методрозв'язання задачі лінійного програмування (ЗЛП) із двома змінними. На прикладі задачі наведено докладний описпобудови креслення та знаходження рішення.

Модель управління запасами Вілсона
На прикладі розв'язання задачі розглянуто основну модель управління запасами (модель Вілсона). Обчислено такі показники моделі як оптимальний розмірпартії замовлення, річні витрати на зберігання, інтервал між поставками та точка розміщення замовлення.

Матриця коефіцієнтів прямих витрат та матриця "Витрати-випуск"
На прикладі розв'язання задачі розглянуто міжгалузеву модель Леонтьєва. Показано обчислення матриці коефіцієнтів прямих матеріальних витрат, матриці «витрати-випуск», матриці коефіцієнтів непрямих витрат, векторів кінцевого споживання та валового випуску.

Метод Лагранжа─ це метод вирішення завдання умовної оптимізації, при якому обмеження, що записуються як неявні функції, поєднуються з цільовою функцією у формі нового рівняння, що називається лагранжіаном.

Розглянемо окремий випадок спільного завдання нелінійного програмування:

Дана система нелінійних рівнянь (1):

(1) gi(x1,x2,…,xn)=bi (i=1..m),

Знайти найменше (або найбільше) значення функції (2)

(2) f (х1, х2, ..., хn),

якщо відсутні умови невід'ємності змінних і f(х1, х2, ..., хn) і gi (x1, x2, ..., xn) - функції, безперервні разом зі своїми приватними похідними.

Щоб знайти розв'язання цього завдання, можна застосувати наступний метод: 1. Вводять набір змінних λ1, λ2,…, λm, які називаються множниками Лагранжа, складають функцію Лагранжа (3)

(3) F(х1,х2,…,хn, λ1,λ2,…,λm) = f(х1,х2,…,хn)+ λi.

2. Знаходять приватні похідні від функції Лагранжа за змінними xi та λi та прирівнюють їх нулю.

3. Вирішуючи систему рівнянь, знаходять точки, в яких цільова функціяЗавдання може мати екстремум.

4. Серед точок, підозрілих не екстремум, знаходять такі, в яких досягається екстремум, і обчислюють значення функції в цих точках .

4. Порівняти отримані значення функції f та вибрати найкраще.

За планом виробництва продукції підприємству необхідно виготовити 180 виробів. Ці вироби можуть бути виготовлені двома технологічними методами. При виробництві х1 виробу I способом витрати дорівнюють 4*х1+х1^2 руб., а при виготовленні х2 виробів II способом вони становлять 8*х2+х2^2 руб. Визначити скільки виробів кожним із способів слід виготовити, так щоб загальні витрати на виробництво продукції були мінімальними.

Рішення: Математична постановка завдання полягає у визначенні найменшого значенняфункції двох змінних:

f = 4*x1+x1^2 +8*x2 +x2^2, за умови x1 +x2 = 180.

Складемо функцію Лагранжа:

F(x1,x2,λ) = 4*x1+x1^2+8*x2+x2^2+λ*(180-x1-x2).

Обчислимо її похідні по х1,х2, λ і прирівняємо їх до 0:

Перенесемо в праві частини перших двох рівнянь і прирівняємо їх ліві частини, отримаємо 4 + 2*x1 = 8 + 2*x2, або x1 − x2 = 2.

Вирішуючи останнє рівняння спільно з рівнянням x1 + x2 = 180, знаходимо x1 = 91, x2 = 89, тобто отримали рішення, що задовольняє умовам:

Знайдемо значення цільової функції f при цих змінних значеннях:

F(x1, x2) = 17278

Ця точка є підозрілою на екстремум. Використовуючи другі приватні похідні, можна показати, що у точці (91,89) функція f має мінімум.

Спосіб визначення умовного екстремуму починається з побудови допоміжної функції Лагранжа, яка в області допустимих рішень досягає максимуму для тих же значень змінних x 1 , x 2 , ..., x n що і цільова функція z . Нехай вирішується завдання визначення умовного екстремуму функції z = f(X) при обмеженнях φ i ( x 1 , x 2 , ..., x n ) = 0, i = 1, 2, ..., m , m < n

Складемо функцію

яка називається функцією Лагранжа. X , - Постійні множники ( множники Лагранжа). Зазначимо, що множникам Лагранжа можна надати економічного сенсу. Якщо f (x 1 , x 2 , ..., x n ) - дохід, що відповідає плану X = (x 1 , x 2 , ..., x n ) , а функція φ i (x 1 , x 2 , ..., x n ) - Витрати i-го ресурсу, що відповідають цьому плану, то X - ціна (оцінка) i-го ресурсу, що характеризує зміну екстремального значення цільової функції залежно від зміни розміру i-го ресурсу (маргінальна оцінка). L(Х) - функція n+m змінних (x 1 , x 2 , ..., x n , λ 1 , λ 2 , ..., λ n ) . Визначення стаціонарних точок цієї функції призводить до розв'язання системи рівнянь

Легко помітити, що . Таким чином, завдання знаходження умовного екстремуму функції z = f(X) зводиться до знаходження локального екстремуму функції L(X) . Якщо стаціонарну точку знайдено, питання про існування екстремуму у найпростіших випадках вирішується виходячи з достатніх умов екстремуму - дослідження знака другого диференціала d 2 L(X) у стаціонарній точці за умови, що змінні збільшення Δx i - пов'язані співвідношеннями

отриманими шляхом диференціювання рівнянь зв'язку.

Вирішення системи нелінійних рівнянь із двома невідомими за допомогою засобу Пошук рішення

Налаштування Пошук рішеннядозволяє знаходити розв'язання системи нелінійних рівнянь із двома невідомими:

де
- нелінійна функція від змінних x і y ,
- Довільна постійна.

Відомо, що пара ( x , y ) є рішенням системи рівнянь (10) тоді і лише тоді, коли вона є рішенням наступного рівняння з двома невідомими:

Зз іншого боку, рішення системи (10) - це точки перетину двох кривих: f ] (x, y) = C і f 2 (х, у) = С 2 на площині ХОY.

З цього випливає метод знаходження коріння системи. нелінійних рівнянь:

Визначити (хоча б приблизно) інтервал існування рішення системи рівнянь (10) або рівняння (11). Тут необхідно враховувати вид рівнянь, що входять до системи, область визначення кожного їх рівняння тощо. Іноді застосовується підбір початкового наближення рішення;

Протабулювати рішення рівняння (11) по змінним x та y на вибраному інтервалі, або побудувати графіки функцій f 1 (x, y) = З, і f 2 (х,у) = С 2 (Система (10)).

Локалізувати передбачувані коріння системи рівнянь - знайти кілька мінімальних значень таблиці табулювання коренів рівняння (11), або визначити точки перетину кривих, що входять до системи (10).

4. Знайти коріння для системи рівнянь (10) за допомогою надбудови Пошук рішення.