PHƯƠNG PHÁP NHÂN TỬ LAGRANGE

     

Phương pháp nhân tử Lagrange (method of Lagrange multipliers) là một kỹ thuật rất kì có lợi để giải các bài toán buổi tối ưu gồm ràng buộc. Trong chuỗi bài viết này tối sẽ chia làm 2 phần: (1) ràng buộc là đẳng thức; (2) ràng buộc là bất đẳng thức. Bài viết đầu tiên này tôi sẽ triệu tập vào tối ưu có ràng buộc là đẳng thức.

Bạn đang xem: Phương pháp nhân tử lagrange

Mục lục1. Kỹ thuật Lagrange2. Phân tích Lý thuyết1. Chuyên môn Lagrange

1.1. Phạt biểu bài bác toán

Tìm rất trị của hàm số đa biến $color#0c7f99f(mathbfx)$ thoả mãn đk hàm đa biến đổi $color#bc2612g(mathbfx)=c$ với $c$ là hằng số:$$eginaligned extmaximize (or minimize)&color#0c7f99f(mathbfx)cr extsubject to:~&color#bc2612g(mathbfx) = cendaligned$$

1.2. Ứng dụng kỹ thuật nhân tử Lagrange

Để giải quyết bài toàn này, ta sử dụng kỹ thuật Lagrange như sau:

Bước 1: Thêm một biến nhân tử Lagrange $color#0d923flambda$ và tư tưởng một hàm Lagrangian $mathcalL$ như sau:$$mathcalL(mathbfx, extcolor#0d923flambda)= extcolor#0c7f99f(mathbfx)- extcolor#0d923flambdaig( extcolor#bc2612g(mathbfx)-cig)$$Bước 2: Giải đạo hàm (gradient) của $mathcalL$ bằng véc-to $mathbf0$:$$ ablamathcalL(mathbfx, extcolor#0d923flambda)=mathbf0$$Bước 3: phụ thuộc các nghiệm $(mathbfx^* , extcolor#0d923flambda^* )$ kiếm được ở trên, cụ vào hàm $color#0c7f99f(mathbfx)$ rồi lựa chọn giá trị lớn số 1 (nhỏ nhất) là ta giá tốt trị yêu cầu tìm (thực ra chỉ việc nghiệm $mathbfx^* $ là đủ):$$egincases extcolorbluef_min &= displaystylemin_mathbfx^* color#0c7f99f(mathbfx^* )cr extcolorredf_max &= displaystylemax_mathbfx^* color#0c7f99f(mathbfx^* )endcases$$

Nếu bạn để ý một chút thì phương trình ở cách 2 tương đương với hệ phương trình sau:$$egincases abla extcolor#0c7f99f(mathbfx) &= extcolor#0d923flambda abla extcolor#bc2612g(mathbfx)crcolor#bc2612g(mathbfx) &= color#bc2612cendcases$$

Bởi:$$ ablamathcalL(mathbfx, extcolor#0d923flambda)=eginbmatrixdfracpartialmathcalLpartialmathbfxcrcrdfracpartialmathcalLpartialmathbf extcolor#0d923flambdaendbmatrix=eginbmatrix abla extcolor#0c7f99f(mathbfx)- extcolor#0d923flambda abla extcolor#bc2612g(mathbfx)crcolor#bc2612g(mathbfx)-cendbmatrix$$

Tức là ngơi nghỉ đây, khi giải bằng tay chúng ta có thể làm ngơ hàm $mathcalL(mathbfx, extcolor#0d923flambda)$ mà vẫn giải tốt. Mặc dù nhiên, việc trình diễn qua hàm Lagrangian này để giúp đỡ ta thuận tiện sài luôn được các cách giải phổng thông không giống và những chương trình laptop có sẵn.

1.3. Lấy một ví dụ minh họa

Bài toán:Giả sử bên máy của khách hàng sản suất sản phẩm công nghệ phụ tùng bởi thép. Túi tiền nhân công mỗi giờ là $$20$ cùng giá 1 tấn thép là $$170$. Lợi tức đầu tư $R$ được quy mô hoá như sau:

$$R(h,s)=200h^2/3s^1/3$$Trong đó:

$h$ là số giờ làm cho việc$s$ là số tấn thép

Hãy tính lợi nhuận béo nhất hoàn toàn có thể thu được nếu gớm phí của chúng ta là $$20,000$.

Lời giải:Mỗi giờ làm việc tốn $$20$ và mỗi tấn thép tốn $$170$ phải tổng túi tiền tính theo $h$ cùng $s$ là:$$B(h,s)=20h+170s$$Do kinh phí đầu tư $B$ là $$20,000$ phải ta có ràng buộc:$$color#bc261220h+170s=20,000$$

Để có cái nhìn cụ thể hơn về bài bác toán, ta thử biểu diễn nó qua đồ thị như sau:


Đồ thị lợi nhuận cùng ràng buộc. Source: khanacademyĐồ thị lợi nhuận với ràng buộc. Source: khanacademy

Nhìn vào thiết bị thị trên ta hoàn toàn có thể thấy lợi nhuận (đường color xanh) đạt lớn số 1 với điều kiện ngân quỹ (đường màu sắc đỏ) trên điểm giao phía bên trái của 2 đường.

Cái quan sát trực quan lại là thế, còn tiếng ta vẫn giải bằng cách thức nhân tử Lagrange để tối ưu hoá hàm $color#0c7f99R(h,s)$ ràng buộc bởi đẳng thức $color#bc2612B(h,s)=20,000$. Theo so sánh ở bên trên ta đã có:$$egincases abla extcolor#0c7f99R(h,s) &= extcolor#0d923flambda abla extcolor#bc2612B(h,s)crcolor#bc2612B(h,s) &= color#bc261220,000endcases$$

Phân tích ra ta được:$$egincasescolor#0c7f99200cdotdfrac23h^-1/3s^1/3 &= 20 extcolor#0d923flambdacrcrcolor#0c7f99200cdotdfrac13h^2/3s^-2/3 &= 170 extcolor#0d923flambdacrcrcolor#bc261220h+170s &= color#bc261220,000endcases$$

Giải ra ta tất cả kết quả:$$egincases extcolor#0c7f99h &= dfrac2,0003 approx 667crcr extcolor#0c7f99s &= dfrac2,00051 approx 39crcrcolor#0d923flambda &= sqrt<3>dfrac8,000459 approx 2.593endcases$$

Thế vào cách làm tính lợi tức đầu tư ta có:$$R(667, 39)=200(667)^2/3(39)^1/3 approx fcolorboxredaqua51,777$$

Như vậy, để đạt được lợi nhuận lớn nhất ta cần 667 giờ lao rượu cồn với 39 tấn thép và lợi nhận có thể đạt được buổi tối đa là $$51,777$.

2. đối chiếu Lý thuyết

2.1. Cái nhìn hình học

Chiếu vật dụng hình của $color#0c7f99f(mathbfx)$ và $color#bc2612g(mathbfx)=c$ qua dạng mặt đường đồng mức (Contour Line). Đầu tiên ta hoàn toàn có thể thấy rằng quý hiếm cực trị của hàm $color#0c7f99f(mathbfx)$ bị ràng buộc bởi vì $color#bc2612g(mathbfx)=c$ đó là điểm xúc tiếp của đường đồng mức của chúng.

Đường đồng nấc của $f(x,y)$ là tập của tất cả các điểm $(x^* ,y^* )$ để $f(x^* ,y^* )=k$ cùng với $k$ là hằng số.

Xem thêm: Phim Ma Cương Thi Hài Lâm Chánh Anh Mới Nhất Full Hd Vietsub

Ví dụ, với $color#0c7f99f(mathbfx)=2x+y$, $color#bc2612g(mathbfx)=x^2+y^2$ với $color#bc2612c=1$, ta đang có mô hình đồ thị như sau.


Đồ thị của f(x,y) với g(x,y). Source: khanacademyĐồ thị của f(x,y) và g(x,y). Source: khanacademy
Đường đồng nút của f(x,y) với g(x,y). Source: khanacademyĐường đồng nấc của f(x,y) cùng g(x,y). Source: khanacademy

Nhìn vào biểu vật trên ta hoàn toàn có thể thấy 2 điểm cực trị là vấn đề tiếp xúc của 2 mặt đường đồng mức của 2 hàm phương châm và ràng buộc. Mặc dù nhiên, không phải lúc làm sao $color#0c7f99f(mathbfx)$ cũng trực tiếp tưng cố kỉnh nhé, vày nó còn phụ thuộc vào vào dạng của hàm sẽ là gì. Ví dụ $color#0c7f99f(mathbfx)=2x^2+sqrt5y$ thì con đường đồng mức đang là:
Đường đồng mức của f(x,y) với g(x,y). Source: khanacademyĐường đồng nấc của f(x,y) với g(x,y). Source: khanacademy

Nhưng dù vắt nào đi nữa, ví như $k$ là vấn đề cực trị của hàm $color#0c7f99f$ thì mặt đường đồng nấc $color#0c7f99f(x,y)=k$ sẽ luôn tiếp xúc với con đường đồng nấc của $color#bc2612g(mathbfx)=c$ tại điểm đó.

Mặt khác, gradient lại luôn luôn vuông góc với mặt đường đồng mức trên điểm tương ứng.
Gradient vuông góc với con đường đồng mức. Source: khanacademyGradient vuông góc với con đường đồng mức. Source: khanacademy

Như vậy, trường hợp 2 con đường đồng mức xúc tiếp nhau thì gradient tương ứng của chúng tại điểm tiếp xúc là song song cùng với nhau.

Nói biện pháp khác, giả sử điểm tiếp xúc chính là $(x_0,y_0)$ thì ta rất có thể biểu diễn tình dục gradient của chúng như sau:$$ abla extcolor#0c7f99f(x_0,y_0)= extcolor#0d923flambda_0 abla extcolor#bc2612g(x_0,y_0)$$

Trong kia $ extcolor#0d923flambda$ là 1 hằng số nào đó. Qua phép trình diễn này ta có thể quy được thành một hệ phương trình 3 ẩn 3 phương trình với hoàn toàn rất có thể giải được rất dễ dàng dàng:$$egincasescolor#bc2612g(x,y) = ccr abla extcolor#0c7f99f(x,y)= extcolor#0d923flambda abla extcolor#bc2612g(x,y)endcases$$

Nghiệm của hệ phương trình trên $(x_0,y_0, extcolor#0d923flambda_0)$ khi sửa chữa lại hàm $color#0c7f99f(x,y)$ sẽ mang đến ta được công dụng mong muốn.

Xem thêm: Kết Quả Xổ Số Tiền Giang Ngày 2 Tháng 1 Năm 2022 (Xstg 2/1), Xổ Số Tiền Giang Ngày 2 Tháng 1 Năm 2022

2.2. Gom lại thành 1 hàm

Từ hệ phương trình trên, Lagrange gom lại thành một phương trình Lagrangian duy nhất:$$mathcalL(x,y, extcolor#0d923flambda)= extcolor#0c7f99f(x,y)- extcolor#0d923flambdaig( extcolor#bc2612g(x,y)-cig)$$

Để ý rằng, đạo hàm riêng rẽ theo $ extcolor#0d923flambda$ thiết yếu bằng điều kiện ràng buộc:$$mathcalL_ extcolor#0d923flambda(x,y, extcolor#0d923flambda)= extcolor#bc2612g(x,y)-c$$Đạo hàm theo $x,y$ là:$$egincasesmathcalL_x(x,y, extcolor#0d923flambda)= extcolor#0d923flambda extcolor#bc2612g_x(x,y)crmathcalL_y(x,y, extcolor#0d923flambda)= extcolor#0d923flambda extcolor#bc2612g_y(x,y)endcases$$Gom lại ta đã có:$$ abla extcolor#0c7f99f(x,y)= extcolor#0d923flambda abla extcolor#bc2612g(x,y)$$

Như vậy, việc của ta vẫn được đổi khác thành dạng về tối ưu hàm $mathcalL$ không tồn tại điều khiếu nại ràng buộc. Việc này tương tự với giải phương trình gradient của nó bằng véc-to $mathbf0$:$$ ablamathcalL=mathbf0$$

2.3. Mở rộng

Từ phép màn biểu diễn như trên ta trả toàn rất có thể tổng quát cho trường hợp có nhiều đẳng thức ràng buộc, lúc ấy hàm $mathcalL$ được định nghĩa như sau:$$mathcalL(x,y, extcolor#0d923flambda)= extcolor#0c7f99f(x,y)-sum_i=1^n extcolor#0d923flambda_iig( extcolor#bc2612g_i(x,y)-c_iig)$$

Trong đó, $color#bc2612g_i(x,y)=c_i$ là những đẳng thức ràng buộc, còn $color#0d923flambda_i$ là các hằng số thành phần tương ứng với mỗi đẳng thức. Bài toán tối ưu hàm $color#0c7f99f(x,y)$ cũng sẽ được giải gián tiếp qua gradient của $mathcalL$:$$ ablamathcalL=mathbf0$$

3. Kết luận

Kỹ thuật Lagrange được lấy cảm hứng từ việc tiếp xúc của các đường đồng mức cùng gradient của chúng. Để tối ưu 1 hàm với buộc ràng là các đẳng thức, ta rất có thể thực hiện nay theo nghệ thuật Lagrange như sau:

Bước 1: thêm một véc-to nhân tử Lagrange $color#0d923flambda$ và khái niệm một hàm Lagrangian $mathcalL$ như sau:$$mathcalL(mathbfx, extcolor#0d923flambda)= extcolor#0c7f99f(mathbfx)- extcolor#0d923flambda^intercalig( extcolor#bc2612g(mathbfx)-cig)$$Bước 2: Giải đạo hàm (gradient) của $mathcalL$ bởi véc-to $mathbf0$:$$ ablamathcalL(mathbfx, extcolor#0d923flambda)=mathbf0$$Bước 3: nhờ vào các nghiệm $(mathbfx^* , extcolor#0d923flambda^* )$ tìm được ở trên, gắng vào hàm $color#0c7f99f(mathbfx)$ rồi chọn giá trị lớn số 1 (nhỏ nhất) là ta được giá trị bắt buộc tìm (thực ra chỉ cần nghiệm $mathbfx^* $ là đủ):$$egincases extcolorbluef_min &= displaystylemin_mathbfx^* color#0c7f99f(mathbfx^* )cr extcolorredf_max &= displaystylemax_mathbfx^* color#0c7f99f(mathbfx^* )endcases$$

Lưu ý rằng do có rất nhiều đẳng thức ràng buộc bắt buộc $color#bc2612g(mathbfx)-c$ là một véc-tơ bao gồm bậc là số đẳng thức và những nhân tử Lagrange tương ứng cũng là 1 trong những véc-to $color#0d923flambda$ bao gồm bậc tương đương.