Phương pháp nhân tử không xác định Lagrange pdf. Phương pháp nhân tử không xác định Lagrange

Nó được sử dụng để giải các bài toán có biểu thức giải tích theo tiêu chí tối ưu và khi có các hạn chế về tính độc lập biến kiểu bằng Để có được Giải pháp phân tích yêu cầu các hạn chế phải có dạng phân tích. Việc sử dụng các hệ số nhân Lagrange không xác định cho phép chúng ta giảm bớt bài toán tối ưu hóa có ràng buộc đối với một bài toán được giải bằng các phương pháp nghiên cứu hàm phân tích cổ điển. Trong trường hợp này, thứ tự của hệ phương trình giải để tìm cực trị của tiêu chuẩn tối ưu tăng theo số ràng buộc. Phương pháp này có hiệu quả khi số lượng biến là ba hoặc ít hơn. Phương pháp này cũng được sử dụng khi số lượng biến lớn hơn ba, nếu quá trình được mô tả bằng phương trình hữu hạn.

Cần tìm cực trị của hàm số phụ thuộc vào n biến, các biến này được kết nối bởi các mối quan hệ. Điểm cực trị mà một hàm đạt được, có tính đến việc đáp ứng các điều kiện, được gọi là tương đối hoặc có điều kiện. Nếu số biến bằng số quan hệ (), thì ẩn số chưa biết được tìm bằng cách giải hệ phương trình mô tả bởi quan hệ. Việc giải quyết vấn đề tối ưu hóa liên quan đến việc kiểm tra giá trị của các biến được tìm thấy theo cách này so với các hàm. Vì vậy, bài toán cực trị có thể được giải quyết bằng cách liệt kê các biến thỏa mãn điều kiện.

Nếu như tôi< n , thì từ phương trình truyền thông ta có thể tìm được sự phụ thuộc tôi biến từ n - m các biến còn lại, tức là

Hàm có thể thu được bằng cách thay thế các biến kết quả vào hàm. Khi đó nó sẽ chỉ phụ thuộc vào các biến không liên quan điều kiện bổ sung. Do đó, bằng cách loại bỏ các hạn chế, có thể giảm kích thước vấn đề ban đầu tối ưu hóa. Thường thì vấn đề không thể được giải quyết bằng phương pháp phân tích theo cách này. Vì vậy, để giải bài toán tìm cực trị của hàm số nhiều biến người ta thường sử dụng phương pháp Lagrange của nhân tử không xác định.

Khi giới thiệu các biến mới gọi là hệ số nhân Lagrange không xác định, có thể đưa ra một hàm mới

những thứ kia. chức năng m+n các biến, trong đó các hạn chế do hệ thống hàm áp đặt được đưa vào như một phần không thể thiếu.

Giá trị cực trị của hàm trùng với giá trị cực trị của hàm nếu điều kiện ràng buộc được đáp ứng. Điều kiện cần để đạt cực trị của một hàm nhiều biến là vi phân của hàm này tại điểm cực trị bằng 0, tức là.

Để biểu thức này được thỏa mãn đối với bất kỳ giá trị nào của vi phân độc lập, điều cần thiết là các hệ số của các vi phân này phải bằng 0, điều này sẽ đưa ra hệ phương trình

Trong trường hợp này, những cái độc lập mới được xác định từ điều kiện

Có thể thu được sự kết hợp của hệ (4.3.1) và (4.3.2)

Như vậy, bài toán ở dạng (4.3.3) rút gọn thành nhiệm vụ: tìm

Riêng biệt, cần lưu ý rằng trong trường hợp chung Phương pháp nhân tử Lagrange cho phép chúng ta chỉ tìm được những điều kiện cần thiết sự tồn tại cực trị có điều kiện cho các hàm liên tục có đạo hàm liên tục. Tuy nhiên, từ ý nghĩa vật lý bài toán đang được giải thường biết chúng ta đang nói về cực đại hay cực tiểu của hàm; ngoài ra, theo quy luật, trong các bài toán thiết kế, hàm trên đoạn đang xem xét là một phương thức. Do đó, trong các bài toán thiết kế, không cần thiết phải kiểm tra giá trị của các biến tìm được khi giải các hệ phương trình cực trị đã xét bằng cách sử dụng phân tích đạo hàm bậc cao.

Định lý 1. Gọi điểm là điểm cực trị có điều kiện của hàm số khi các phương trình kết nối (3) được thỏa mãn. Khi đó tồn tại các số thỏa mãn điều kiện tại điểm

Kết quả. Chúng ta hãy đặt

đâu là những con số được chỉ định trong định lý. Hàm (8) được gọi là hàm Lagrange. Nếu một điểm là điểm cực trị có điều kiện của một hàm thì nó là điểm dừng của hàm Lagrange, tức là tại thời điểm này

Chứng minh định lý. Gọi là điểm cực trị có điều kiện của hàm và thỏa mãn điều kiện (4) tại điểm này để xác định. Khi đó điểm là điểm cực trị thông thường của hàm số, do đó tại điểm

từ đó, sử dụng tính bất biến của dạng vi phân thứ nhất, cho điểm chúng ta có

Thay (5) vào (3) và lấy vi phân đồng nhất thức thu được trong một lân cận nhất định của điểm, và do đó tại chính điểm đó, chúng ta thu được

Trong công thức (11), cũng như trong công thức (10), vi phân là vi phân của các biến độc lập và vi phân là vi phân của hàm số.

Dù là con số nào, nhân đẳng thức (11) tại điểm của hàm với rồi cộng chúng lại với nhau và với đẳng thức (10), chúng ta nhận được

Đã chọn sao cho sự bình đẳng giữ ở điểm

Điều này luôn có thể xảy ra, vì (13) là hệ phương trình tuyến tính theo định thức

không bằng không.

Với sự lựa chọn này chúng ta có

Ở đây, tất cả vi phân là vi phân của các biến độc lập và do đó, bản thân chúng là các biến độc lập có thể nhận bất kỳ giá trị nào. Lấy và tất cả các vi phân khác có trong công thức (14), bằng 0, chúng tôi nhận được

Như vậy, chúng ta đã chứng minh được sự tồn tại sao cho điều kiện (13) và (15) được thỏa mãn, tức là. điều kiện (7).

Định lý đã được chứng minh.

Thuật toán tìm cực trị của hàm số bằng phương pháp nhân tử Lagrange

Cần tìm cực trị của hàm số n biến f(x 1 ,x 2 ,…,x n) với điều kiện các biến x 1 ,x 2 ,…,x n có liên hệ bởi các quan hệ (ràng buộc)

trong đó số m ràng buộc đẳng thức nhỏ hơn số n biến và số lượng r ràng buộc đẳng thức có thể tùy ý.

Để tìm các giá trị (x 1 ,x 2 ,…,x n )=X, nhất thiết phải cung cấp cực trị của hàm f(X), bạn có thể sử dụng phương pháp Lagrange của số nhân không xác định:

• 1. Ràng buộc bất đẳng thức g(X)0 được rút gọn về dạng (X)0, trong đó (X) = - g(X).
• 2. Thu được các hạn chế về bất bình đẳng

lần lượt, được giảm xuống các ràng buộc đẳng thức bằng cách đưa ra các biến bổ sung +r

Do đó, bài toán tìm cực trị có điều kiện sẽ có dạng chính tắc:

trong đó mối quan hệ m++r< n++r указывает на возможность получения множества допустимых решений, а значит, и нахождения среди них тех, которые доставляют экстремум f(X).

3. Hàm Lagrange được biên dịch:

Ф(x 1 ,…,x n , 1 ,…, m++r) = f(x 1 ,x 2 ,…,x n)+ 1 q 1 + 2 q 2 +…+ m++r q m++r ,

trong đó các biến bổ sung ( 1 ,…, m++r )= được gọi là hệ số nhân Lagrange không xác định.

Đối với hàm Lagrange được xây dựng, chúng ta có thể đặt ra bài toán tìm cực trị vô điều kiện

kết quả của lời giải sẽ trùng với lời giải mong muốn của bài toán ban đầu là tìm cực trị có điều kiện.

4. Với hàm Ф(Х,), rút ​​ra điều kiện cần để tồn tại cực trị:

5. Hệ phương trình thu được Ф(Х,) = 0 được giải và kết quả là tìm được các giá trị

thỏa mãn điều kiện cần thiết cho sự tồn tại của cực trị.

6. Để giải bài toán tại các điểm tìm được có cực đại hay cực tiểu, cần sử dụng đủ điều kiện tồn tại cực trị mà để hàm trơn Ф() được biểu diễn như sau:

nếu tại một điểm nào đó ma trận đạo hàm bậc hai xác định dương thì cực tiểu của hàm f(X) nằm tại điểm phân tích;

Lý thuyết tóm tắt

Phương pháp nhân tử Lagrange là một phương pháp cổ điển để giải các bài toán lập trình toán học (đặc biệt là các bài toán lồi). Thật không may, khi ứng dụng thực tế Phương pháp này có thể gặp phải những khó khăn tính toán đáng kể, thu hẹp phạm vi sử dụng của nó. Chúng tôi xem xét phương pháp Lagrange ở đây chủ yếu vì nó là một công cụ được sử dụng tích cực để chứng minh các phương pháp số hiện đại khác nhau được sử dụng rộng rãi trong thực tế. Còn đối với hàm Lagrange và bộ nhân Lagrange, chúng đóng vai trò độc lập và cực kỳ quan trọng trong lý thuyết cũng như ứng dụng không chỉ của lập trình toán học.

Hãy xem xét một vấn đề tối ưu hóa cổ điển:

Trong số các hạn chế của bài toán này, không có bất đẳng thức nào, không có điều kiện nào cho tính không âm của các biến, tính rời rạc của chúng và các hàm số là liên tục và có đạo hàm riêng ít nhất là bậc hai.

Cách tiếp cận cổ điển để giải bài toán cung cấp một hệ phương trình (điều kiện cần) phải được thỏa mãn bởi điểm cung cấp cho hàm cực trị cục bộ trên tập hợp các điểm thỏa mãn các ràng buộc (đối với bài toán lập trình lồi, điểm tìm được cũng sẽ là điểm cực trị toàn cục).

Giả sử tại một điểm hàm (1) có cực trị điều kiện cục bộ và hạng của ma trận bằng . Khi đó điều kiện cần sẽ được viết dưới dạng:

có hàm Lagrange; - Các nhân đấu Lagrange.

Ngoài ra còn có đủ điều kiện để nghiệm hệ phương trình (3) xác định được điểm cực trị của hàm số. Câu hỏi này được giải quyết dựa trên việc nghiên cứu dấu vi phân bậc hai của hàm Lagrange. Tuy nhiên, điều kiện đủ chủ yếu được quan tâm về mặt lý thuyết.

Bạn có thể chỉ định quy trình sau để giải bài toán (1), (2) bằng phương pháp nhân tử Lagrange:

1) soạn hàm Lagrange (4);

2) tìm đạo hàm riêng của hàm Lagrange đối với tất cả các biến và đánh đồng chúng

số không. Do đó, sẽ thu được một hệ (3), bao gồm các phương trình. Giải hệ kết quả (nếu điều này có thể thực hiện được!) và do đó tìm được tất cả các điểm dừng của hàm Lagrange;

3) từ các điểm dừng lấy không có tọa độ, chọn các điểm mà tại đó hàm số có cực trị cục bộ có điều kiện khi có các ràng buộc (2). Sự lựa chọn này được thực hiện, ví dụ, bằng cách sử dụng các điều kiện đủ cho một cực trị địa phương. Thông thường việc nghiên cứu sẽ được đơn giản hóa nếu sử dụng các điều kiện cụ thể của vấn đề.

Ví dụ về giải pháp vấn đề

Nhiệm vụ

Công ty sản xuất hai loại hàng hóa với số lượng và . Hàm chi phí hữu ích được xác định bởi mối quan hệ. Giá của những hàng hóa này trên thị trường là ngang nhau và tương ứng.

Xác định mức lợi nhuận tối đa đạt được ở mức sản lượng nào và lợi nhuận đó bằng bao nhiêu nếu tổng chi phí không vượt quá

Bạn gặp khó khăn trong việc hiểu tiến trình của một quyết định? Website cung cấp dịch vụ Giải quyết vấn đề bằng các phương pháp giải tối ưu để đặt hàng

Giải pháp của vấn đề

Mô hình kinh tế và toán học của bài toán

Hàm lợi nhuận:

Hạn chế về chi phí:

Chúng ta có được mô hình kinh tế và toán học sau:

Ngoài ra, theo ý nghĩa của nhiệm vụ

Phương pháp nhân Lagrange

Hãy soạn hàm Lagrange:

Ta tìm đạo hàm riêng bậc 1:

Hãy lập và giải hệ phương trình:

Kể từ đó

Lợi nhuận tối đa:

Trả lời

Vì vậy, cần phải giải phóng thức ăn. hàng hóa loại 1 và đơn vị. hàng loại 2. Trong trường hợp này, lợi nhuận sẽ tối đa và lên tới 270.
Một ví dụ về giải bài toán quy hoạch lồi bậc hai bằng phương pháp đồ họa được đưa ra.

Giải bài toán tuyến tính bằng phương pháp đồ thị
Được xem xét phương pháp đồ họa giải quyết vấn đề lập trình tuyến tính(ZLP) với hai biến. Một ví dụ về nhiệm vụ được đưa ra miêu tả cụ thể dựng bản vẽ và tìm cách giải.

Mô hình quản lý hàng tồn kho của Wilson
Lấy ví dụ giải bài toán, xem xét mô hình cơ bản của quản lý tồn kho (mô hình Wilson). Các chỉ số mô hình sau đây đã được tính toán: kích thước tối ưu số lượng đặt hàng, chi phí lưu kho hàng năm, khoảng thời gian giao hàng và điểm đặt hàng.

Ma trận tỷ lệ chi phí trực tiếp và ma trận đầu vào-đầu ra
Lấy ví dụ về việc giải một bài toán, hãy xem xét mô hình liên ngành của Leontiev. Trình bày ma trận hệ số chi phí nguyên vật liệu trực tiếp, ma trận đầu vào-đầu ra, ma trận hệ số chi phí gián tiếp, vectơ tiêu dùng cuối cùng và tổng sản lượng.

Phương pháp Lagrange─ đây là một phương pháp giải quyết vấn đề tối ưu hóa có điều kiện, trong đó các ràng buộc, được viết dưới dạng hàm ẩn, được kết hợp với hàm mục tiêu dưới dạng một phương trình mới gọi là Lagrange.

Hãy xem xét trương hợp đặc biệt nhiệm vụ chung lập trình phi tuyến:

Cho hệ phương trình phi tuyến (1):

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

Tìm giá trị nhỏ nhất (hoặc lớn nhất) của hàm số (2)

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

nếu không có điều kiện để các biến không âm và f(x1,x2,…,xn) và gi(x1,x2,…,xn) là các hàm số liên tục cùng với đạo hàm riêng của chúng.

Để tìm lời giải cho bài toán này, bạn có thể áp dụng phương pháp sau: 1. Nhập tập hợp các biến λ1, λ2,…, λm, gọi là bộ nhân Lagrange, soạn hàm Lagrange (3)

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

2. Tìm đạo hàm riêng của hàm Lagrange theo các biến xi và λi và cho chúng bằng 0.

3. Giải hệ phương trình, tìm điểm cực trị của hàm mục tiêu của bài toán.

4. Trong số các điểm nghi ngờ không phải là cực trị, hãy tìm những điểm đạt đến cực trị và tính giá trị của hàm tại các điểm này .

4. So sánh các giá trị thu được của hàm f và chọn giá trị tốt nhất.

Theo kế hoạch sản xuất, công ty cần sản xuất 180 sản phẩm. Những sản phẩm này có thể được sản xuất theo hai cách công nghệ. Khi sản xuất sản phẩm x1 bằng phương pháp I, chi phí là 4*x1+x1^2 rúp và khi sản xuất sản phẩm x2 bằng phương pháp II, chi phí là 8*x2+x2^2 rúp. Xác định số lượng sản phẩm sẽ được sản xuất bằng mỗi phương pháp sao cho tổng chi phí sản xuất là tối thiểu.

Giải: Công thức toán học của bài toán bao gồm việc xác định giá trị nhỏ nhất của hàm hai biến:

f = 4*x1+x1^2 +8*x2 +x2^2, với điều kiện x1 +x2 = 180.

Hãy soạn hàm Lagrange:

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

Hãy tính đạo hàm riêng của nó theo x1, x2, λ và cho chúng bằng 0:

Hãy di chuyển λ sang vế phải của hai phương trình đầu tiên và đánh đồng vế trái của chúng, chúng ta nhận được 4 + 2*x1 = 8 + 2*x2, hoặc x1 − x2 = 2.

Giải phương trình cuối cùng với phương trình x1 + x2 = 180, ta tìm được x1 = 91, x2 = 89, tức là ta thu được nghiệm thỏa mãn điều kiện:

Hãy tìm giá trị hàm mục tiêu f cho các giá trị biến này:

F(x1, x2) = 17278

Điểm này đáng nghi ngờ đối với một điểm cực đoan. Sử dụng đạo hàm riêng bậc hai, chúng ta có thể chỉ ra rằng tại điểm (91,89) hàm f có giá trị cực tiểu.

Xét một bài toán tối ưu hóa có ràng buộc chỉ chứa các ràng buộc ở dạng đẳng thức

phút

bị hạn chế

,
.

Về nguyên tắc, vấn đề này có thể được giải như một vấn đề tối ưu hóa không bị ràng buộc thu được bằng cách loại bỏ m biến độc lập khỏi hàm mục tiêu bằng cách sử dụng các đẳng thức đã cho. Sự hiện diện của các ràng buộc dưới dạng đẳng thức thực sự có thể làm giảm kích thước của bài toán ban đầu. Nhiệm vụ mới có thể được giải quyết bằng phương pháp tối ưu hóa không bị ràng buộc phù hợp.

Ví dụ. Cần giảm thiểu chức năng

khi bị hạn chế

Bằng cách loại bỏ biến sử dụng phương trình, chúng ta thu được bài toán tối ưu hóa với hai biến không hạn chế:

giảm thiểu,

có thể được giải quyết bằng cách sử dụng một trong các phương pháp tối ưu hóa vô điều kiện.

Tuy nhiên, phương pháp loại bỏ biến chỉ được áp dụng trong trường hợp các phương trình biểu diễn các ràng buộc có thể giải được đối với một tập biến nhất định. Nếu có một số lượng lớn các ràng buộc dưới dạng đẳng thức, quá trình loại bỏ các biến sẽ trở thành một quy trình tốn rất nhiều công sức. Ngoài ra, có thể có những tình huống mà phương trình không thể giải được đối với một biến. Trong trường hợp này, nên sử dụng phương pháp nhân tử Lagrange.

Sử dụng phương pháp nhân tử Lagrange, các điều kiện cần thiết về cơ bản được thiết lập để cho phép xác định các điểm tối ưu trong các bài toán tối ưu hóa có ràng buộc đẳng thức.

Hãy xem xét vấn đề

phút

bị hạn chế

,
.

Từ khóa học phân tích toán học Người ta biết rằng điểm tối thiểu có điều kiện của hàm trùng với điểm yên của hàm Lagrange:

,

trong đó điểm yên ngựa phải cung cấp tối thiểu các biến và thông số tối đa . Những tham số này được gọi là hệ số nhân Lagrange. Phương trình đạo hàm riêng của hàm số Qua và bởi về 0, chúng ta thu được các điều kiện cần thiết cho một điểm đứng yên:

,
,

,
.

Giải pháp hệ thống
phương trình xác định điểm dừng của hàm Lagrange. Ngoài những điều kiện nêu trên, các điều kiện đủ để tồn tại cực tiểu của bài toán ban đầu còn chứa tính xác định dương của ma trận Hessian của hàm mục tiêu.

4.2. Điều kiện coon-tucker

Chúng ta hãy xem xét một bài toán quy hoạch phi tuyến với các ràng buộc ở dạng bất đẳng thức

phút

dưới những hạn chế

,
.

Chúng ta hãy giảm các ràng buộc dưới dạng bất bình đẳng thành các ràng buộc đẳng thức bằng cách thêm các biến suy yếu vào mỗi chúng ,
:

.

Hãy xây dựng hàm Lagrange:

Khi đó điều kiện cần để đạt cực tiểu có dạng

,
;

,
;

,
.

Bạn có thể nhân phương trình cuối cùng với và thay thế các biến suy giảm bằng cách biểu thị chúng từ phương trình thứ hai. Phương trình thứ hai có thể được biến đổi bằng cách loại bỏ các biến suy giảm và chuyển sang ràng buộc bất đẳng thức. Cần thêm một điều kiện nữa
, phải được đáp ứng tại điểm tối thiểu có điều kiện.

Cuối cùng, chúng ta thu được các điều kiện cần thiết để tồn tại tối thiểu một bài toán quy hoạch phi tuyến với các ràng buộc bất đẳng thức, được gọi là các điều kiện Kuhn-Tucker:

,
; (1)

,
; (2)

,
; (3)

,
. (4)

Hạn chế bất bình đẳng
được gọi là hoạt động tại một điểm , nếu nó trở thành đẳng thức
, và được gọi là không hoạt động nếu
. Nếu có thể phát hiện, trước khi trực tiếp giải quyết vấn đề, các ràng buộc không hoạt động ở điểm tối ưu, thì những ràng buộc này có thể được loại trừ khỏi mô hình và do đó làm giảm kích thước của mô hình.

Phương trình (3) có nghĩa là
, hoặc
. Nếu như
, Cái đó
và ràng buộc đang hoạt động và thể hiện một ràng buộc bình đẳng. Mặt khác, nếu ràng buộc là một bất đẳng thức nghiêm ngặt
, thì số nhân Lagrange sẽ có dạng
những thứ kia. giới hạn
không hoạt động và có thể được bỏ qua. Tất nhiên, người ta không biết trước những hạn chế nào có thể được bỏ qua.