Лагранжийн үржүүлэгчийн арга бол жишээ шийдэл юм. Лагранжийн үржүүлэгчийн арга

Өнөөдөр хичээл дээр бид олж сурах болно нөхцөлтэсвэл тэднийг бас нэрлэдэг шиг, харьцангуй туйлшралхэд хэдэн хувьсагчийн функцууд бөгөөд юуны түрүүнд бид нөхцөлт экстремумын талаар ярих болно. хоёр функцТэгээд гурван хувьсагч, сэдэвчилсэн асуудлын дийлэнх хэсэгт байдаг.

Та яг одоо юу мэдэж, юу хийж чадах ёстой вэ? Энэ нийтлэл нь сэдвийн "захын талд" байгаа хэдий ч материалыг амжилттай эзэмшихийн тулд тийм ч их зүйл шаардагддаггүй. Энэ үед та үндсэн зүйлийг мэдэж байх ёстой орон зайн гадаргуу, олох боломжтой хэсэгчилсэн дериватив (дор хаяж дундаж түвшинд)мөн, өршөөлгүй логикийн заасан шиг, ойлгох болзолгүй туйлшрал. Хэдийгээр та бэлтгэл багатай байсан ч орхих гэж бүү яараарай - дутагдаж буй бүх мэдлэг, ур чадвараа "замын дагуу" олж авах боломжтой бөгөөд ямар ч цаг зовоолгүй.

Эхлээд үзэл баримтлалд дүн шинжилгээ хийж, хамгийн нийтлэг зүйлийг хурдан давтъя гадаргуу. Тэгэхээр нөхцөлт экстремум гэж юу вэ? ...Энд байгаа логик нь үүнээс дутахгүй өршөөлгүй =) Функцийн нөхцөлт экстремум нь ердийн утгаараа экстремум бөгөөд тодорхой нөхцөл (эсвэл нөхцөл) хангагдсан тохиолдолд хүрдэг.

Дурын "ташуу" гэж төсөөлөөд үз дээ онгоцВ Декарт систем. Байхгүй экстремумэнд ямар ч ул мөр байхгүй. Гэхдээ энэ бол одоохондоо. Ингээд авч үзье эллипс цилиндр, энгийн байхын тулд - тэнхлэгтэй зэрэгцээ төгсгөлгүй дугуй "хоолой". Энэ "хоолой" нь манай онгоцноос "тасрах" нь тодорхой эллипс, үүний үр дүнд дээд цэгтээ дээд тал нь, доод цэг дээр хамгийн бага байх болно. Өөрөөр хэлбэл, хавтгайг тодорхойлох функц нь туйлдаа хүрдэг үүнийг өгсөнтүүнийг өгөгдсөн дугуй цилиндрээр гаталж байсан. Яг "болгосон"! Энэ хавтгайг огтолж буй өөр нэг эллипс цилиндр нь өөр өөр хамгийн бага ба хамгийн их утгыг гаргах нь гарцаагүй.

Хэрэв энэ нь тийм ч тодорхой биш бол нөхцөл байдлыг бодитоор загварчлах боломжтой (урвуу дарааллаар): сүх аваад гудамжинд гараад огтол... үгүй ​​ээ, Гринпис дараа чамайг уучлахгүй - ус зайлуулах хоолойг нунтаглагчаар таслах нь дээр =). Нөхцөлт хамгийн бага ба нөхцөлт дээд хэмжээ нь ямар өндөрт, ямар дор байхаас хамаарна (хэвтээ бус)зүсэлт нь өнцгөөр хийгдсэн байдаг.

Тооцооллыг математикийн хувцастай хувцаслах цаг болжээ. Ингээд авч үзье эллипс параболоид, байгаа үнэмлэхүй хамгийн багацэг дээр. Одоо экстремумыг олъё үүнийг өгсөн. Энэ онгоцтэнхлэгтэй зэрэгцэн оршдог бөгөөд энэ нь параболоидоос "таслах" гэсэн үг юм парабол. Энэ параболын дээд хэсэг нь нөхцөлт минимум байх болно. Түүнээс гадна, онгоц нь координатын гарал үүслээр дамждаггүй тул цэг нь хамааралгүй хэвээр байх болно. Зураг өгөөгүй юм уу? Холбоосыг нэн даруй дагана уу! Энэ нь олон удаа, олон удаа шаардагдах болно.

Асуулт: Энэ нөхцөлт экстремумыг хэрхэн олох вэ? Шийдвэрлэх хамгийн энгийн арга бол тэгшитгэлийг ашиглах явдал юм (үүнийг - нөхцөлэсвэл холболтын тэгшитгэл) жишээ нь: – илэрхийлж, функцэд орлуулна:

Үр дүн нь параболыг тодорхойлох нэг хувьсагчийн функц бөгөөд оройг нь нүдээ аниад "тооцоодог". Олъё чухал цэгүүд:

- чухал цэг.

Дараагийн ашиглах хамгийн хялбар зүйл бол экстремумын хувьд хоёр дахь хангалттай нөхцөл:

Ялангуяа: энэ нь функц цэг дээр хамгийн багадаа хүрнэ гэсэн үг юм. Үүнийг шууд тооцоолж болно: , гэхдээ бид илүү академик чиглэлийг баримтлах болно. "Тоглоомын" координатыг олъё:
,

нөхцөлт хамгийн бага цэгийг бичиж, энэ нь үнэхээр хавтгайд байгаа эсэхийг шалгаарай (холбох тэгшитгэлийг хангана):

функцийн нөхцөлт минимумыг тооцоолно:
үүнийг өгсөн ("нэмэлт" шаардлагатай!!!).

Энэ аргыг практикт ямар ч эргэлзээгүйгээр ашиглаж болно, гэхдээ энэ нь хэд хэдэн сул талуудтай. Нэгдүгээрт, асуудлын геометр нь үргэлж тодорхой байдаггүй, хоёрдугаарт, холболтын тэгшитгэлээс "x" эсвэл "y" -ийг илэрхийлэх нь ихэвчлэн ашиггүй байдаг. (ямар нэгэн зүйлийг илэрхийлэх арга байвал). Одоо бид нөхцөлт экстремумыг олох бүх нийтийн аргыг авч үзэх болно Лагранжийн үржүүлэгчийн арга:

Жишээ 1

Аргументуудын холболтын заасан тэгшитгэл бүхий функцийн нөхцөлт туйлыг ол.

Та гадаргууг таних уу? ;-) ...Чиний аз жаргалтай царайг хараад баяртай байна =)

Дашрамд хэлэхэд, энэ асуудлыг томъёолсноор нөхцөл байдлыг яагаад нэрлэсэн нь тодорхой болно холболтын тэгшитгэл- функцын аргументууд холбогдсоннэмэлт нөхцөл, өөрөөр хэлбэл олдсон экстремум цэгүүд нь дугуй цилиндрт хамаарах ёстой.

Шийдэл: эхний алхамд та холболтын тэгшитгэлийг хэлбэрээр танилцуулж, зохиох хэрэгтэй Лагранж функц:
, Лагранж гэж нэрлэгддэг үржүүлэгч хаана байна.

Манай тохиолдолд болон:

Нөхцөлт экстремумыг олох алгоритм нь "ердийн"-ийг олох схемтэй маш төстэй юм. туйлшрал. Олъё хэсэгчилсэн деривативЛагранжийн функцууд нь "ламбда"-г тогтмол гэж үзэх ёстой:

Дараах системийг зохиож шийдье.

Орооцолдол нь стандарт байдлаар тайлагдсан:
Эхний тэгшитгэлээс бид илэрхийлдэг ;
Хоёр дахь тэгшитгэлээс бид илэрхийлдэг .

Холболтуудыг тэгшитгэлд орлуулж, хялбаршуулъя:

Үүний үр дүнд бид хоёр суурин цэгийг олж авдаг. Хэрэв бол:

хэрэв бол:

Хоёр цэгийн координат нь тэгшитгэлийг хангаж байгааг харахад хялбар байдаг . Шударга хүмүүс мөн бүрэн шалгалт хийж болно: үүний тулд та орлуулах хэрэгтэй системийн эхний ба хоёр дахь тэгшитгэлд оруулаад дараа нь олонлогтой ижил зүйлийг хий . Бүх зүйл "хамтдаа" байх ёстой.

Олдсон суурин цэгүүдэд хангалттай экстремум нөхцөлийн биелэлтийг шалгая. Би энэ асуудлыг шийдэх гурван аргыг авч үзэх болно.

1) Эхний арга нь геометрийн үндэслэл юм.

Хөдөлгөөнгүй цэг дээрх функцийн утгыг тооцоолъё.

Дараа нь бид ойролцоогоор дараах агуулга бүхий хэллэгийг бичнэ: дугуй цилиндрээр хийсэн хавтгайн хэсэг нь дээд оройд дээд цэгтээ хүрсэн эллипс, доод орой дээр хамгийн багадаа хүрдэг. Тиймээс том утга нь болзолт дээд хэмжээ, бага утга нь болзолт минимум юм.

Боломжтой бол энэ аргыг ашиглах нь илүү дээр юм - энэ нь энгийн бөгөөд энэ шийдвэрийг багш нар тооцдог (том давуу тал нь та асуудлын геометрийн утгыг ойлгосон явдал юм). Гэсэн хэдий ч, аль хэдийн дурьдсанчлан, юу, хаана огтлолцох нь үргэлж тодорхой байдаггүй бөгөөд дараа нь аналитик баталгаажуулалт аврах ажилд ирдэг.

2) Хоёрдахь арга нь хоёр дахь дарааллын дифференциал тэмдгийг ашиглахад суурилдаг. Хэрэв хөдөлгөөнгүй цэг дээр функц нь дээд цэгтээ хүрдэг бол хамгийн багадаа хүрдэг.

Олъё хоёрдугаар эрэмбийн хэсэгчилсэн дериватив:

мөн энэ дифференциалыг үүсгэ:

Хэзээ , энэ нь функц цэг дээр дээд цэгтээ хүрнэ гэсэн үг юм;
at , энэ нь функц цэг дээр хамгийн багадаа хүрдэг гэсэн үг юм .

Энэ арга нь маш сайн боловч зарим тохиолдолд 2-р дифференциалын тэмдгийг тодорхойлох бараг боломжгүй байдаг сул талтай. (ихэвчлэн энэ нь болон/эсвэл өөр шинж тэмдэг байвал тохиолддог). Дараа нь "хүнд их буу" аврах ажилд ирнэ.

3) Холболтын тэгшитгэлийг "X" ба "Y"-ээр ялгаж үзье.

мөн дараах зүйлийг зохио тэгш хэмтэй матриц:

Хэрэв хөдөлгөөнгүй цэг дээр байвал функц тэнд хүрнэ ( анхаарал!) хамгийн бага, хэрэв - дараа нь хамгийн их.

Утга болон харгалзах цэгийн матрицыг бичье.

Үүнийг тооцоод үзье тодорхойлогч:
, ингэснээр функц цэг дээр хамгийн их утгатай байна.

Үүний нэгэн адил үнэ цэнэ, цэгийн хувьд:

Тиймээс функц нь цэг дээр хамгийн бага утгатай байна.

Хариулт: өгөгдсөн бол:

Материалыг сайтар шинжилсний дараа би танд өөрийгөө шалгах хэд хэдэн ердийн даалгаврыг санал болгохоос өөр аргагүй юм.

Жишээ 2

Хэрэв аргументууд нь тэгшитгэлээр хамааралтай бол функцийн нөхцөлт туйлыг ол

Жишээ 3

Нөхцөл өгөгдсөн функцийн экстремумыг ол

Дахин хэлэхэд, би даалгаврын геометрийн мөн чанарыг ойлгохыг зөвлөж байна, ялангуяа сүүлийн жишээнд хангалттай нөхцөл байдлын аналитик баталгаажуулалт нь бэлэг биш юм. Юуг санаарай 2-р захиалгын шугамтэгшитгэлийг тогтоодог ба юу гадаргууЭнэ шугам нь орон зайд үүсдэг. Цилиндр нь хавтгайг аль муруйгаар огтолж, энэ муруйн хаана хамгийн бага, хамгийн их нь хаана байгааг шинжилнэ үү.

Хичээлийн төгсгөлд шийдэл, хариултууд.

Энэ асуудлыг янз бүрийн салбарт, тухайлбал бид хол явахгүй - геометрийн салбарт өргөн хэрэглэгддэг. Хагас литрийн лонхны тухай хүн бүрийн дуртай асуудлыг шийдье (Өгүүллийн 7-р жишээг үзнэ үүХэт их сорилтууд ) хоёр дахь арга:

Жишээ 4

Цилиндр хэлбэртэй лаазны хэмжээ ямар байх ёстой вэ, ингэснээр лаазны эзэлхүүн нь тэнцүү бол лааз хийхэд хамгийн бага материал зарцуулагдах болно.

Шийдэл: хувьсах суурийн радиус, хувьсах өндрийг авч үзээд лаазны нийт гадаргуугийн талбайн функцийг бичнэ үү.
(хоёр бүрээсийн талбай + хажуугийн гадаргуугийн талбай)

Лагранжийн үржүүлэгчийн арга.

Лагранжийн үржүүлэгчийн арга нь шугаман бус програмчлалын асуудлыг шийдвэрлэх боломжийг олгодог аргуудын нэг юм.

Шугаман бус програмчлал нь шугаман бус зорилгын функц бүхий экстремаль бодлогуудыг шийдвэрлэх аргууд, шугаман бус хязгаарлалтаар тодорхойлогдсон хэрэгжих боломжтой шийдлүүдийн мужийг судалдаг математик програмчлалын салбар юм. Эдийн засгийн шинжлэх ухаанд энэ нь үр дүн (үр ашиг) нь нөөц ашиглалтын цар хүрээний өөрчлөлттэй (эсвэл үйлдвэрлэлийн цар хүрээний хувьд) пропорциональ бусаар нэмэгдэж, буурч байгаатай тохирч байна: жишээлбэл, үйлдвэрлэлийн зардлыг хуваахтай холбоотой. Аж ахуйн нэгжүүдийг хувьсах болон хагас тогтмол болгон хуваах; дараагийн нэгж бүрийг өмнөхөөсөө илүү борлуулахад хэцүү байх үед барааны эрэлт ханалт гэх мэт.

Шугаман бус програмчлалын асуудал нь тодорхой зорилгын функцийн оновчтойг олох асуудал юм

F(x 1 ,…x n), Ф (x) → хамгийн их

нөхцөл хангагдсан үед

g j (x 1 ,…x n)≥0, g (x) ≤ б , x ≥ 0

Хаана x-шаардлагатай хувьсагчийн вектор;

Ф (x) -объектив функц;

g (x) - хязгаарлалтын функц (тасралтгүй дифференциал);

б - хязгаарлалтын тогтмолуудын вектор.

Шугаман бус програмчлалын асуудлын шийдэл (дэлхийн хамгийн их эсвэл хамгийн бага) нь зөвшөөрөгдөх багцын хил эсвэл дотоод хэсэгт хамаарах боломжтой.

Шугаман програмчлалын бодлогоос ялгаатай нь шугаман бус програмчлалын бодлогод хамгийн оновчтой нь хязгаарлалтаар тодорхойлогдсон бүсийн хил дээр байх албагүй. Өөрөөр хэлбэл, өгөгдсөн функцийн хамгийн их (эсвэл хамгийн бага) түвшинд хүрэх тэгш бус байдлын хэлбэрийн хязгаарлалтын тогтолцооны дагуу хувьсагчийн сөрөг бус утгыг сонгох даалгавар юм. Энэ тохиолдолд зорилгын функц болон тэгш бус байдлын аль алиных нь хэлбэрийг заагаагүй болно. Өөр өөр тохиолдол байж болно: зорилгын функц нь шугаман бус, харин хязгаарлалт нь шугаман; зорилгын функц нь шугаман, хязгаарлалтууд (дор хаяж нэг нь) шугаман бус; зорилгын функц ба хязгаарлалт хоёулаа шугаман бус байна.

Шугаман бус програмчлалын асуудал нь байгалийн ухаан, инженерчлэл, эдийн засаг, математик, бизнесийн харилцаа, засгийн газарт байдаг.

Жишээлбэл, шугаман бус програмчлал нь эдийн засгийн үндсэн асуудалтай холбоотой. Тиймээс, хязгаарлагдмал нөөцийг хуваарилах асуудалд үр ашиг, эсвэл хэрэглэгчийг судалж байгаа бол нөөцийн хомсдолын нөхцлийг илэрхийлсэн хязгаарлалт байгаа тохиолдолд хэрэглээг дээд зэргээр нэмэгдүүлдэг. Ийм ерөнхий томъёололд бодлогын математик томъёолол нь боломжгүй байж болох ч тусгай хэрэглээнд бүх функцийн тоон хэлбэрийг шууд тодорхойлж болно. Тухайлбал, аж үйлдвэрийн үйлдвэр хуванцар бүтээгдэхүүн үйлдвэрлэдэг. Энд үйлдвэрлэлийн үр ашгийг ашгаар хэмждэг бөгөөд хязгаарлалтыг ажиллах хүч, үйлдвэрлэлийн талбай, тоног төхөөрөмжийн бүтээмж гэх мэтээр тайлбарладаг.

Зардлын үр ашгийн арга нь шугаман бус програмчлалын схемд бас нийцдэг. Энэ аргыг засгийн газрын шийдвэр гаргахад ашиглах зорилгоор боловсруулсан. Үр ашгийн нийтлэг үүрэг бол халамж юм. Энд шугаман бус програмчлалын хоёр асуудал гарч ирдэг: эхнийх нь хязгаарлагдмал зардлаар үр нөлөөг нэмэгдүүлэх, хоёрдугаарт, үр нөлөө нь тодорхой доод түвшнээс дээш байх тохиолдолд зардлыг багасгах явдал юм. Энэ асуудлыг ихэвчлэн шугаман бус програмчлалын тусламжтайгаар сайн загварчилсан байдаг.

Шугаман бус програмчлалын асуудлыг шийдсэний үр дүн нь засгийн газрын шийдвэр гаргахад тустай. Үүний үр дүнд гарсан шийдлийг мэдээж санал болгож байгаа тул эцсийн шийдвэр гаргахын өмнө шугаман бус програмчлалын асуудлын таамаглал, үнэн зөвийг шалгах шаардлагатай.

Шугаман бус асуудлууд нь нарийн төвөгтэй байдаг бөгөөд тэдгээрийг ихэвчлэн шугаман асуудлууд руу хөтөлж хялбаршуулдаг. Үүнийг хийхийн тулд тодорхой газар нутагт зорилгын функц нь бие даасан хувьсагчдын өөрчлөлттэй пропорциональ хэмжээгээр нэмэгдэж эсвэл буурдаг гэж үздэг. Энэ аргыг хэсэгчилсэн шугаман ойртуулах арга гэж нэрлэдэг боловч энэ нь зөвхөн зарим төрлийн шугаман бус асуудалд хамаарна.

Тодорхой нөхцөлд шугаман бус асуудлуудыг Лагранжийн функцийг ашиглан шийддэг: түүний эмээлийн цэгийг олсноор асуудлын шийдлийг олно. Шинжлэх ухааны судалгааны тооцооллын алгоритмуудын дунд градиент аргууд ихээхэн байр эзэлдэг. Шугаман бус асуудлыг шийдэх бүх нийтийн арга байдаггүй бөгөөд тэдгээр нь маш олон янз байдаг тул тийм биш байж магадгүй юм. Multiextremal асуудлууд ялангуяа шийдвэрлэхэд хэцүү байдаг.

Тэгшитгэлийн системийг шийдэхийн тулд шугаман бус програмчлалын асуудлыг багасгах боломжийг олгодог аргуудын нэг бол тодорхойгүй үржүүлэгчийн Лагранжийн арга юм.

Лагранжийн үржүүлэгчийн аргыг ашиглан тэгш байдлын хязгаарлалт бүхий оновчлолын асуудлын оновчтой цэгүүдийг тодорхойлоход шаардлагатай нөхцөлүүдийг үндсэндээ бүрдүүлдэг. Энэ тохиолдолд хязгаарлагдмал бодлого нь Лагранжийн үржүүлэгч гэж нэрлэгддэг зарим үл мэдэгдэх параметрүүдийг агуулсан ижил төстэй болзолгүй оновчлолын бодлого болж хувирдаг.

Лагранжийн үржүүлэгчийн арга нь нөхцөлт экстремум дээрх асуудлуудыг туслах функцийн болзолгүй экстремум дээрх асуудал болгон багасгахад оршино. Лагранжийн функцууд.

Функцийн экстремумын асуудлын хувьд е(x 1, x 2,..., x n) нөхцөлд (хязгаарлалтын тэгшитгэл) φ би(x 1 , x 2 , ..., x n) = 0, би= 1, 2,..., м, Лагранж функц нь хэлбэртэй байна

L(x 1, x 2… x n,λ 1, λ 2,…λm)=f(x 1, x 2… x n)+∑ i -1 m λ i φ i (x 1, x 2… x n)

Үржүүлэгч λ 1 , λ 2 , ..., λмдуудсан Лагранжийн үржүүлэгч.

Хэрэв утгууд x 1 , x 2 , ..., x n , λ 1 , λ 2 , ..., λmЛагранжийн функцийн суурин цэгүүдийг тодорхойлдог тэгшитгэлийн шийдлүүдийн мөн чанар, тухайлбал дифференциалагдах функцүүдийн хувьд тэгшитгэлийн системийн шийдлүүд юм.

тэгвэл нэлээд ерөнхий таамаглалаар x 1 , x 2 , ..., x n нь f функцийн экстремумыг өгнө.

Нэг хязгаарлалтад хамаарах n хувьсагчийн функцийг тэгш байдлын хэлбэрээр багасгах асуудлыг авч үзье.

f(x 1, x 2… x n)-ийг багасгах (1)

хязгаарлалт дор h 1 (x 1, x 2… x n)=0 (2)

Лагранжийн үржүүлэгчийн аргын дагуу энэ асуудлыг дараахь хязгаарлалтгүй оновчлолын бодлого болгон хувиргав.

багасгах L(x,λ)=f(x)-λ*h(x) (3)

L(x;λ) функцийг Лагранжийн функц гэж нэрлэдэг.

λ нь үл мэдэгдэх тогтмол бөгөөд үүнийг Лагранжийн үржүүлэгч гэж нэрлэдэг. λ тэмдэгтэнд тавигдах шаардлага байхгүй.

Өгөгдсөн λ=λ 0 утгын хувьд L(x,λ) функцийн x-тэй харьцах болзолгүй минимум нь x=x 0 цэгт хүрэх ба x 0 нь h 1 (x 0)=0 тэгшитгэлийг хангана. . Дараа нь харахад хялбар байхаар x 0 нь (1)-ийг (2) харгалзан багасгадаг, учир нь x-ийн бүх утгуудын хувьд (2), h 1 (x)=0 ба L(x,λ)=min. f(x).

Мэдээжийн хэрэг, болзолгүй минимум x 0 цэгийн координат нь тэгш байдлыг (2) хангахын тулд λ=λ 0 утгыг сонгох шаардлагатай. Хэрэв λ-г хувьсагч гэж үзвэл λ функц хэлбэрээр (3) функцийн болзолгүй минимумыг олж, дараа нь тэгш байдал (2) хангагдах λ-ийн утгыг сонговол үүнийг хийж болно. Үүнийг тодорхой жишээгээр тайлбарлая.

f(x)=x 1 2 +x 2 2 =0-ийг багасга

хязгаарлалтын дор h 1 (x)=2x 1 +x 2 -2=0=0

Харгалзах хязгаарлалтгүй оновчлолын асуудлыг дараах байдлаар бичнэ.

багасгах L(x,λ)=x 1 2 +x 2 2 -λ(2x 1 +x 2 -2)

Шийдэл. L градиентийн хоёр бүрэлдэхүүн хэсгийг тэгтэй тэнцүүлж, бид олж авна

→ x 1 0 =λ

→ x 2 0 =λ/2

Х°-ийн хөдөлгөөнгүй цэг нь хамгийн багатай тохирч байгаа эсэхийг шалгахын тулд х-ийн функц гэж үзсэн L(x;u) функцийн Гессийн матрицын элементүүдийг тооцоолно.

эерэг тодорхой болж хувирдаг.

Энэ нь L(x,u) нь х-ийн гүдгэр функц гэсэн үг юм. Улмаар x 1 0 =λ, x 2 0 =λ/2 координатууд нь дэлхийн хамгийн бага цэгийг тодорхойлно. λ-ийн оновчтой утгыг x 1 0 ба x 2 0 утгыг 2x 1 + x 2 =2 тэгшитгэлд орлуулах замаар олно, үүнээс 2λ+λ/2=2 эсвэл λ 0 =4/5 байна. Иймээс нөхцөлт минимум нь x 1 0 =4/5 ба x 2 0 =2/5 үед хүрч, min f(x) = 4/5-тай тэнцүү байна.

Жишээн дээрх асуудлыг шийдвэрлэхдээ бид L(x;λ)-ийг x 1 ба x 2 гэсэн хоёр хувьсагчийн функц гэж үзсэн ба үүнээс гадна λ параметрийн утгыг сонгосон тул хязгаарлалтыг хангасан гэж үзсэн. Хэрэв системийн шийдэл

J=1,2,3,…,n

λ-ийг тодорхой функц хэлбэрээр олж авах боломжгүй бол n+1 үл мэдэгдэх n+1 тэгшитгэлээс бүрдэх дараах системийг шийдэж x ба λ-ийн утгыг олно.

J=1,2,3,…,n., h 1 (x)=0

Өгөгдсөн системийн бүх боломжит шийдлүүдийг олохын тулд та тоон хайлтын аргуудыг (жишээлбэл, Ньютоны арга) ашиглаж болно. Шийдэл () бүрийн хувьд бид х-ийн функц гэж тооцогддог L функцийн Гессийн матрицын элементүүдийг тооцоолж, энэ матриц нь эерэг тодорхой (локал минимум) эсвэл сөрөг тодорхой (орон нутгийн максимум) эсэхийг олж мэдэх хэрэгтэй. ).

Лагранжийн үржүүлэгчийн аргыг асуудал нь тэгш байдлын хэлбэрээр хэд хэдэн хязгаарлалттай тохиолдолд өргөтгөж болно. Шаардлагатай ерөнхий асуудлыг авч үзье

f(x)-г багасгах

хязгаарлалтын дор h k =0, k=1, 2, ..., K.

Лагранж функц нь дараах хэлбэртэй байна.

Энд λ 1 , λ 2 , ..., λk-Лагранжийн үржүүлэгч, i.e. утгыг тодорхойлох шаардлагатай үл мэдэгдэх параметрүүд. L-ийн x-ийн хэсэгчилсэн деривативуудыг тэгтэй тэнцүүлэхдээ n үл мэдэгдэх n тэгшитгэлийн дараах системийг олж авна.

Хэрэв дээрх системийн шийдлийг λ векторын функц хэлбэрээр олоход хэцүү бол тэгш байдлын хэлбэрээр хязгаарлалтуудыг оруулах замаар системийг өргөжүүлж болно.

n + K үл мэдэгдэх n + K тэгшитгэлээс бүрдэх өргөтгөсөн системийн шийдэл нь L функцийн суурин цэгийг тодорхойлно. Дараа нь тооцооллын үндсэн дээр хамгийн бага эсвэл максимумыг шалгах процедурыг хэрэгжүүлдэг. Х-ийн функц гэж үзсэн L функцийн Гессийн матрицын элементүүд нь нэг хязгаарлалттай бодлогын үед хийгдсэнтэй төстэй. Зарим асуудлын хувьд n+K үл мэдэгдэх n+K тэгшитгэлийн өргөтгөсөн систем шийдэлгүй байж болох ба Лагранжийн үржүүлэгчийн аргыг хэрэглэх боломжгүй болж хувирдаг. Гэсэн хэдий ч практик дээр ийм даалгавар нэлээд ховор байдаг гэдгийг тэмдэглэх нь зүйтэй.

Хязгаарлалтын систем нь зөвхөн тэгшитгэлийг агуулдаг, хувьсагчдын сөрөг бус байх нөхцөл байхгүй, мөн ба тэдгээрийн хэсэгчилсэн деривативын хамт тасралтгүй функцүүд байна гэж үзвэл шугаман бус програмчлалын ерөнхий асуудлын тусгай тохиолдлыг авч үзье. Тиймээс (7) тэгшитгэлийн системийг шийдсэнээр бид (6) функц нь туйлын утгатай байж болох бүх цэгүүдийг олж авдаг.

Лагранжийн үржүүлэгчийн аргын алгоритм

1. Лагранж функцийг зохио.

2. x J ,λ i хувьсагчдад хамаарах Лагранжийн функцийн хэсэгчилсэн деривативуудыг олж, тэгтэй тэнцүүл.

3. Бид (7) тэгшитгэлийн системийг шийдэж, асуудлын зорилгын функц нь экстремумтай байж болох цэгүүдийг олно.

4. Экстремумын сэжигтэй цэгүүдээс бид экстремумд хүрсэн цэгүүдийг олж, эдгээр цэгүүдэд (6) функцийн утгыг тооцоолно.

Жишээ.

Анхны өгөгдөл:Үйлдвэрлэлийн төлөвлөгөөний дагуу 180 нэр төрлийн бүтээгдэхүүн үйлдвэрлэх шаардлагатай. Эдгээр бүтээгдэхүүнийг технологийн хоёр аргаар үйлдвэрлэж болно. 1-р аргаар х 1 бүтээгдэхүүн үйлдвэрлэхэд 4х 1 +х 1 2 рубль, 2-р аргаар х 2 бүтээгдэхүүн үйлдвэрлэхэд 8х 2 + х 2 2 рубль байна. Үйлдвэрлэлийн зардал хамгийн бага байхын тулд арга тус бүрийг ашиглан хичнээн бүтээгдэхүүн үйлдвэрлэх ёстойг тодорхойл.

Тодорхойлсон асуудлын зорилгын функц нь хэлбэртэй байна
® миннөхцөлд x 1 + x 2 =180, x 2 ≥0.
1. Лагранж функцийг зохио
.
2. Бид x 1, x 2, λ-тэй холбоотой хэсэгчилсэн деривативуудыг тооцоолж, тэгтэй тэнцүүлнэ.

3. Үүссэн тэгшитгэлийн системийг шийдэж x 1 =91,x 2 =89 болно

4. Х 2 =180-х 1 зорилгын функцийг орлуулсны дараа бид нэг хувьсагчийн функцийг олж авна, тухайлбал f 1 =4x 1 +x 1 2 +8(180-x 1)+(180-x 1) ) 2

Бид тооцоолно эсвэл 4x 1 -364=0 ,

Эндээс бид x 1 * =91, x 2 * =89 байна.

Хариулт: Эхний аргаар үйлдвэрлэсэн бүтээгдэхүүний тоо x 1 =91, хоёр дахь аргаар x 2 =89, харин зорилгын функцийн утга нь 17,278 рубльтэй тэнцүү байна.

Аргын тайлбар

Үндэслэл

Лагранжийн үржүүлэгчийн аргын дараах үндэслэл нь түүний хатуу нотолгоо биш юм. Энэ нь аргын геометрийн утгыг ойлгоход туслах эвристик санаануудыг агуулдаг.

Хоёр хэмжээст хэрэг

Түвшингийн шугам ба муруй.

Тэгшитгэлд заасан нөхцлийн дагуу хоёр хувьсагчийн зарим функцийн экстремумыг олох шаардлагатай байг. . Бид бүх функцийг тасралтгүй ялгах боломжтой гэж үзэх бөгөөд энэ тэгшитгэл нь гөлгөр муруйг тодорхойлдог Сонгоцонд. Дараа нь асуудал нь функцийн экстремумыг олох хүртэл буурдаг емуруй дээр С. Үүнийг бид бас таамаглах болно Сградиент байгаа цэгүүдээр дамждаггүй е 0 болж хувирна.

Хавтгай дээр функцын түвшний шугамуудыг зуръя е(энэ нь муруй). Геометрийн үүднээс авч үзвэл функцийн экстремум нь тодорхой байна емуруй дээр СЗөвхөн шүргэх цэгүүд байж болно Сба харгалзах түвшний шугам давхцаж байна. Үнэхээр, хэрэв муруй бол Стүвшний шугамыг давна ехөндлөн цэг дээр (өөрөөр хэлбэл тэгээс өөр өнцгөөр), дараа нь муруй дагуу хөдөлнө Сцэгээс бид илүү том утгатай тохирох түвшний шугам руу хүрч чадна е, ба түүнээс бага. Тиймээс ийм цэг нь экстремум цэг байж болохгүй.

Тиймээс манай тохиолдолд экстремумын зайлшгүй нөхцөл бол шүргэгчийн давхцал байх болно. Үүнийг аналитик хэлбэрээр бичихийн тулд энэ нь функцүүдийн градиентийн параллелизмтэй тэнцүү гэдгийг анхаарна уу. еградиент вектор нь түвшний шулууны шүргэгчтэй перпендикуляр тул өгөгдсөн цэг дээр ψ байна. Энэ нөхцлийг дараах хэлбэрээр илэрхийлнэ.

Энд λ нь тэгээс өөр тоо бөгөөд энэ нь Лагранжийн үржүүлэгч юм.

Одоо авч үзье Лагранж функц, λ-аас хамаарч:

Түүний экстремумын зайлшгүй нөхцөл бол градиент тэгтэй тэнцүү байх явдал юм. Ялгах дүрмийн дагуу маягтаар бичнэ

Бид системийг олж авсан бөгөөд эхний хоёр тэгшитгэл нь орон нутгийн экстремум (1) шаардлагатай нөхцөлтэй тэнцэх, гурав дахь нь тэгшитгэлтэй тэнцүү байна. . Та үүнээс олж болно. Түүнээс гадна, өөрөөр хэлбэл функцийн градиент ецэг дээр алга болдог , энэ нь бидний таамаглалтай зөрчилдөж байна. Ийм аргаар олдсон цэгүүд нь нөхцөлт экстремумын хүссэн цэгүүд биш байж магадгүй гэдгийг тэмдэглэх нь зүйтэй - авч үзсэн нөхцөл нь зайлшгүй шаардлагатай боловч хангалттай биш юм. Туслах функц ашиглан нөхцөлт экстремумыг олох ЛЭнд хоёр хувьсагчийн хамгийн энгийн тохиолдлоор хэрэглэгдэх Лагранжийн үржүүлэгчийн аргын үндэс болдог. Дээрх үндэслэлийг дурын тооны хувьсагч, нөхцөлийг тодорхойлсон тэгшитгэлийн тохиолдолд нэгтгэж болно.

Лагранжийн үржүүлэгчийн аргад үндэслэн нөхцөлт экстремумын зарим хангалттай нөхцөлийг батлах боломжтой бөгөөд энэ нь Лагранжийн функцийн хоёр дахь деривативын шинжилгээг шаарддаг.

Өргөдөл

• Лагранжийн үржүүлэгчийн аргыг олон салбарт (жишээлбэл, эдийн засагт) үүсдэг шугаман бус програмчлалын асуудлыг шийдвэрлэхэд ашигладаг.
• Өгөгдсөн дундаж битийн хурдаар аудио болон видео өгөгдлийг кодлох чанарыг оновчтой болгох асуудлыг шийдвэрлэх гол арга (гажуудлыг оновчтой болгох - Англи хэл. Rate-Distortion оновчлол).

Мөн үзнэ үү

Холбоосууд

• Зорих В.А.Математик анализ. 1-р хэсэг. - ред. 2-р, илч. болон нэмэлт - М.: ФАЗИС, 1997.

Викимедиа сан.

2010 он.

Бусад толь бичгүүдээс "Лагранж үржүүлэгчид" гэж юу болохыг хараарай:Лагранжийн үржүүлэгч - сонгодог аргуудын аль нэгийг, үржүүлэгчийг шийдвэрлэх аргыг ашиглан гүдгэр програмчлалын (ялангуяа шугаман програмчлалын) зорилгын функцийг өөрчлөх нэмэлт хүчин зүйлүүд ... ...

Эдийн засаг-математикийн толь бичигЛагранжийн үржүүлэгч - Сонгодог аргуудын аль нэг нь үржүүлэгчийг шийдвэрлэх аргыг (Лагранжийн арга) ашиглан шийдвэрлэхдээ экстремаль гүдгэр програмчлалын (ялангуяа шугаман програмчлалын) зорилтын функцийг хувиргах нэмэлт хүчин зүйлүүд ... ...

Техникийн орчуулагчийн гарын авлага Механик. 1) Лагранжийн 1-р төрлийн тэгшитгэл, механик хөдөлгөөний дифференциал тэгшитгэл. Тэгш өнцөгт координатын тэнхлэгт проекцоор өгөгдсөн системүүд гэж нэрлэгддэг системийг агуулдаг. Лагранжийн үржүүлэгч. 1788 онд Ж.Лагранж олж авсан.Голономик системийн хувьд ... ...

Физик нэвтэрхий толь бичиг Механикийн хөдөлгөөнийг дүрсэлсэн 2-р эрэмбийн ердийн дифференциал тэгшитгэлүүд. тэдгээрт хэрэглэсэн хүчний нөлөөн дор системүүд. Л.у. J. Lag хүрээг хоёр хэлбэрээр тогтоосон: L. u. 1-р төрөл буюу декарт координат дахь тэгшитгэлүүд ... ...

1) гидромеханик дахь шингэний (хийн) хөдөлгөөний тэгшитгэл нь орчны координат болох Лагранжийн хувьсагчид. Франц хэлээр хүлээн авсан эрдэмтэн Ж.Лагранж (ойролцоогоор 1780). L. u. орчны хөдөлгөөний хууль нь хамаарлын хэлбэрээр тодорхойлогддог... ... Механик. 1) Лагранжийн 1-р төрлийн тэгшитгэл, механик хөдөлгөөний дифференциал тэгшитгэл. Тэгш өнцөгт координатын тэнхлэгт проекцоор өгөгдсөн системүүд гэж нэрлэгддэг системийг агуулдаг. Лагранжийн үржүүлэгч. 1788 онд Ж.Лагранж олж авсан.Голономик системийн хувьд ... ...

Лагранжийн үржүүлэгчийн арга нь f(x) функцийн нөхцөлт экстремумыг олох арга бөгөөд m хязгаарлалттай харьцуулахад i нь нэгээс m хооронд хэлбэлздэг. Агуулга 1 Аргын тайлбар ... Википедиа

Олон хувьсагч ба функциональ функцүүдийн нөхцөлт экстремумын асуудлыг шийдвэрлэхэд ашигладаг функц. L. f-ийн тусламжтайгаар. нөхцөлт экстремум дээрх асуудлыг оновчтой болгоход шаардлагатай нөхцөлүүдийг бичнэ. Энэ тохиолдолд зөвхөн хувьсагчийг илэрхийлэх шаардлагагүй... Механикийн хөдөлгөөнийг дүрсэлсэн 2-р эрэмбийн ердийн дифференциал тэгшитгэлүүд. тэдгээрт хэрэглэсэн хүчний нөлөөн дор системүүд. Л.у. J. Lag хүрээг хоёр хэлбэрээр тогтоосон: L. u. 1-р төрөл буюу декарт координат дахь тэгшитгэлүүд ... ...

Нөхцөлт экстремумын асуудлыг шийдвэрлэх арга; L.M.M нь эдгээр асуудлуудыг туслах функцийн болзолгүй экстремум гэж нэрлэхэд хүргэдэг. Лагранжийн функцууд. f (x1, x2,..., xn) функцийн экстремумын бодлогод... ...

Нөхцөлт экстремум дээрх асуудлыг судлахдаа Лагранжийн функцийг бүтээдэг хувьсагчид. Шугаман аргууд ба Лагранжийн функцийг ашиглах нь нөхцөлт экстремумтай холбоотой асуудлуудад шаардлагатай оновчтой нөхцлийг нэг төрлийн аргаар олж авах боломжийг олгодог ... Механикийн хөдөлгөөнийг дүрсэлсэн 2-р эрэмбийн ердийн дифференциал тэгшитгэлүүд. тэдгээрт хэрэглэсэн хүчний нөлөөн дор системүүд. Л.у. J. Lag хүрээг хоёр хэлбэрээр тогтоосон: L. u. 1-р төрөл буюу декарт координат дахь тэгшитгэлүүд ... ...

1) гидромеханикийн хувьд шингэний орчны хөдөлгөөний тэгшитгэлийг орчны бөөмсийн координат болох Лагранжийн хувьсагчаар бичнэ. L. u. орчны бөөмсийн хөдөлгөөний хууль нь координатын цаг хугацааны хамаарлын хэлбэрээр тодорхойлогддог ба тэдгээрээс... ... Зөвлөлтийн агуу нэвтэрхий толь бичиг

Лагранжийн арга─ нь далд функцээр бичигдсэн хязгаарлалтуудыг зорилгын функцтэй шинэ тэгшитгэлийн хэлбэрээр нэгтгэсэн хязгаарлагдмал оновчлолын асуудлыг шийдвэрлэх арга юм. Лагранжян.

Шугаман бус програмчлалын ерөнхий бодлогын тусгай тохиолдлыг авч үзье.

Шугаман бус тэгшитгэлийн системийг өгөгдсөн (1):

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

Функцийн хамгийн бага (эсвэл хамгийн том) утгыг ол (2)

(2) f (x1,x2,…,xn),

хэрэв хувьсагчид сөрөг биш байх нөхцөл байхгүй бөгөөд f(x1,x2,…,xn) ба 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 нэр төрлийн бүтээгдэхүүн үйлдвэрлэх шаардлагатай. Эдгээр бүтээгдэхүүнийг технологийн хоёр аргаар үйлдвэрлэж болно. I аргаар х1 бүтээгдэхүүн үйлдвэрлэхэд зардал нь 4*x1+x1^2 рубль, II аргаар х2 бүтээгдэхүүн үйлдвэрлэхэд 8*x2+x2^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).

Түүний x1, x2, λ-д хамаарах хэсэгчилсэн деривативуудыг тооцоод 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 функц хамгийн багатай болохыг харуулж чадна.

ЛАГРАНЖИЙН АРГА

1759 онд Ж.Лагранжийн заасан квадрат хэлбэрийг квадратуудын нийлбэр болгон багасгах арга. Өгчихье

x 0 хувьсагчдаас , x 1 ,..., x х. талбайн коэффициентүүдтэй кшинж чанарууд Энэ хэлбэрийг каноник хэлбэрт оруулах шаардлагатай. оюун ухаан

хувьсагчийн доройтдоггүй шугаман хувиргалтыг ашиглан. L. m нь дараахь зүйлсээс бүрдэнэ. (1) хэлбэрийн бүх коэффициентүүд тэгтэй тэнцүү биш гэж бид үзэж болно.

Тиймээс хоёр тохиолдол байж болно. 1) Зарим хүмүүсийн хувьд g,

диагональ Дараа нь f 1 (x) хэлбэр нь хувьсагч агуулаагүй байна x g . 2) Хэрэв бүх зүйл бол Гэхдээ

Тэр f 2 (x) хэлбэр нь хоёр хувьсагч агуулаагүй байна x g Тэгээдх ч.

(4)-д байгаа дөрвөлжин тэмдгийн доорх хэлбэрүүд нь шугаман бие даасан байна. (3) ба (4) хэлбэрийн хувиргалтыг хийснээр (1) хэлбэрийг хязгаарлагдмал тооны алхмын дараа шугаман бие даасан шугаман хэлбэрийн квадратуудын нийлбэр болгон бууруулна. Хэсэгчилсэн дериватив ашиглан (3) ба (4) томъёог хэлбэрээр бичиж болноГэрэл. : Г а н т м а х э р Ф.Р., Матрицын онол, 2-р хэвлэл, М., 1966; К у р о ш А. Г., Дээд алгебрийн курс, 11-р хэвлэл, М., 1975; Александров П.С., Аналитик геометрийн лекцүүд..., М., 1968.

I.V. Проскуряков.Математикийн нэвтэрхий толь бичиг. - М .: Зөвлөлтийн нэвтэрхий толь бичиг

.

I. M. Виноградов.- Лагранжийн арга нь Лагранжийн функцийн эмээлийн цэгийг (x*, λ*) олох замаар математикийн програмчлалын хэд хэдэн ангиллын бодлогыг шийдвэрлэх арга бөгөөд энэ функцийн хэсэгчилсэн деривативуудыг тэгтэй тэнцүүлэх замаар олж авдаг. ... ... - сонгодог аргуудын аль нэгийг, үржүүлэгчийг шийдвэрлэх аргыг ашиглан гүдгэр програмчлалын (ялангуяа шугаман програмчлалын) зорилгын функцийг өөрчлөх нэмэлт хүчин зүйлүүд ... ...

I. M. Виноградов.- Лагранжийн функцийн эмээлийн цэгийг (x*, ?*) олох замаар математикийн програмчлалын хэд хэдэн ангиллын бодлогуудыг шийдвэрлэх арга бөгөөд энэ функцийн xi ба?i-ийн хэсэгчилсэн деривативуудыг тэгтэй тэнцүүлэх замаар олж авдаг. . Лагранжийг үзнэ үү. )