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

     

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

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

Mục lục1. Nghệ thuật Lagrange2. So sánh 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 trở nên $color#0c7f99f(mathbfx)$ thoả mãn điều kiện hàm đa biến hóa $color#bc2612g(mathbfx)=c$ cùng 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 thực hiện kỹ thuật Lagrange như sau:

Bước 1: Thêm một đổi thay nhân tử Lagrange $color#0d923flambda$ và định nghĩa 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 vào các nghiệm $(mathbfx^* , extcolor#0d923flambda^* )$ kiếm được ở trên, thay vào hàm $color#0c7f99f(mathbfx)$ rồi lựa chọn giá trị lớn nhất (nhỏ nhất) là ta được giá trị nên 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$$

Nếu bạn để ý một chút thì phương trình ở cách 2 tương tự 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à sống đây, khi giải bằng tay chúng ta cũng có thể làm ngơ hàm $mathcalL(mathbfx, extcolor#0d923flambda)$ nhưng vẫn giải tốt. Tuy nhiên, việc biểu diễn qua hàm Lagrangian này sẽ giúp đỡ ta dễ dàng sài luôn được những cách giải phổng thông khác và những chương trình máy tính xách tay có sẵn.

1.3. Ví dụ minh họa

Bài toán:Giả sử bên máy của doanh nghiệp sản suất trang bị phụ tùng bằng thép. Túi tiền nhân công mỗi giờ là $$20$ với giá 1 tấn thép là $$170$. Roi $R$ được quy mô hoá như sau:

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

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

Hãy tính lợi nhuận to nhất rất có thể thu được nếu khiếp phí của người tiêu dùng là $$20,000$.

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

Để có cái nhìn rõ ràng hơn về bài bác toán, ta thử trình diễn nó qua đồ vật thị như sau:


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

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

Cái nhìn trực quan liêu là thế, còn tiếng ta vẫn giải bằng phương pháp nhân tử Lagrange để tối ưu hoá hàm $color#0c7f99R(h,s)$ ràng buộc bởi vì đẳng thức $color#bc2612B(h,s)=20,000$. Theo so với ở bên trên ta sẽ 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 bao gồm 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, để đã có được lợi nhuận lớn nhất ta đề xuất 667 tiếng lao động với 39 tấn thép với lợi nhận hoàn toàn có thể đạt được buổi tối đa là $$51,777$.

2. So sánh Lý thuyết

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

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

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

Xem thêm: Hướng Dẫn Vẽ Tranh Về Đề Tài "Góc Học Tập Của Em", Tranh Vẽ Đề Tài Học Tập Đẹp

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


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

Nhìn vào biểu vật dụng trên ta có thể thấy 2 điểm cực trị là vấn đề tiếp xúc của 2 mặt đường đồng nút của 2 hàm kim chỉ nam 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 thế nhé, vì nó còn phụ thuộc vào vào dạng của hàm sẽ là gì. Ví dụ như $color#0c7f99f(mathbfx)=2x^2+sqrt5y$ thì con đường đồng mức đã là:
Đường đồng nấc của f(x,y) và g(x,y). Source: khanacademyĐường đồng mức của f(x,y) cùng g(x,y). Source: khanacademy

Nhưng dù cầm cố nào đi nữa, trường hợp $k$ là điểm cực trị của hàm $color#0c7f99f$ thì đường đồng mức $color#0c7f99f(x,y)=k$ sẽ luôn luôn tiếp xúc với đường đồng nút của $color#bc2612g(mathbfx)=c$ trên đ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 tại đ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 mặt đường đồng mức. Source: khanacademy

Như vậy, trường hợp 2 đườ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à tuy vậy song cùng với nhau.

Nói giải 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 quan hệ nam nữ gradient của bọn 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à một hằng số như thế nào đó. Qua phép màn biểu 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 cùng hoàn toàn có thể giải được rất giản đơn 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ẽ cho ta được kết quả mong muốn.

Xem thêm: Tỷ Lệ Bản Vẽ Trong Autocad Và Các Tỉ Lệ Trong Bản Vẽ Kỹ Thuật

2.2. Tụ lại thành 1 hàm

Từ hệ phương trình trên, Lagrange tụ 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$ chủ yếu bằng đk 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 sẽ có:$$ abla extcolor#0c7f99f(x,y)= extcolor#0d923flambda abla extcolor#bc2612g(x,y)$$

Như vậy, bài toán của ta đã được biến đổi thành dạng buổi 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 đương 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 trình diễn như trên ta trả toàn có thể tổng quát cho trường hợp có khá nhiều đẳng thức ràng buộc, lúc ấy hàm $mathcalL$ được tư tưởng 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à các đẳng thức ràng buộc, còn $color#0d923flambda_i$ là các hằng số thành phần tương xứng với từng đẳng thức. Việc tối ưu hàm $color#0c7f99f(x,y)$ cũng biến thành được giải loạ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 giác từ việc tiếp xúc của những đường đồng mức với gradient của chúng. Để tối ưu 1 hàm với buộc ràng là những đẳng thức, ta rất có thể thực hiện theo kỹ thuật Lagrange như sau:

Bước 1: thêm một véc-to 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#0d923flambda^intercalig( 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 vào các nghiệm $(mathbfx^* , extcolor#0d923flambda^* )$ kiếm được ở trên, cố kỉnh vào hàm $color#0c7f99f(mathbfx)$ rồi lựa chọn giá trị lớn nhất (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$$

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