Công thức và chứng minh định lý Kuhn-Tucker. Khái niệm điểm yên ngựa. Định lý Kuhn-Tucker

F(x)-F(x tùy chọn)<0.

Hãy chọn hai loại tăng xj dọc theo j tọa độ thứ

Δx j =x j -x jopt >0,

Δx j =x j -x jopt<0.

Chuyển các quan hệ này tới giới hạn tại Δ xj→ 0, chúng tôi nhận được:

Từ những mối quan hệ này suy ra rằng

(3.6.1)

Một mối quan hệ tương tự có thể thu được cho trường hợp hàm tối thiểu. Như vậy, sự cần thiết của các điều kiện (3.6.1) để đạt được tại điểm x bán buôn hàm tối đa hoặc tối thiểu f(x), tức là nếu có một cực trị thì điều kiện (3.6.1) được thỏa mãn. Nhưng đẳng thức bằng 0 của mọi đạo hàm tại điểm x bán buôn vẫn chưa đảm bảo sự tồn tại của cực trị trong đó, tức là các điều kiện (3.6.1) là không đủ. Về mặt hình học, điều này có nghĩa là trong trường hợp đạo hàm bằng 0 của hàm một biến, có thể có một điểm uốn chứ không phải cực đại (hoặc cực tiểu), và trong trường hợp hàm hai biến, một điểm yên, và không phải là cực trị, v.v. Do đó, các điểm x bán buôn, trong đó các quan hệ (3.6.1) được thỏa mãn được gọi là dừng.

Lưu ý rằng điều kiện (3.6.1) đạt được nhờ khả năng gán biến X số gia của hai dấu, đó là nơi xuất hiện hai bất đẳng thức tại và tại . Nếu phạm vi hợp lệ X giới hạn ở các giá trị không âm X≥0 thì nằm trong vùng nơi X> 0, điều kiện (3.6.1) vẫn hợp lệ vì cho phép tăng cả hai dấu ở đó. Ở ranh giới của khu vực X≥ 0, trong đó X= 0, chỉ cho phép tăng dương Δ X>0, chúng ta chỉ có thể nói về đạo hàm một phía, và từ (3.6.1) điều kiện cần thiết sau để đạt cực đại như sau:

Theo đó, điều kiện cần để có cực tiểu tại ranh giới của vùng xj= 0 sẽ được viết là

b) Bài toán cực trị có điều kiện

Khi xác định cực trị có điều kiện hàm khi bạn cần xác định giá trị lớn nhất (hoặc nhỏ nhất) của hàm F(x)ở điều kiện giới hạn:

g i (x) = b i , i = 1, ..., m,

f(x)=max;

g tôi (x)=b tôi ;

Phương pháp nhân tử Lagrange cũng được sử dụng, giống như trong trường hợp phép tính biến phân cổ điển, bao gồm việc giới thiệu hàm Lagrange

(3.6.2)

trong đó λ i là các số nhân Lagrange không xác định.

Giả sử hàm số là trường hợp đặc biệt của hàm số, ta thu được các điều kiện cần cho cực trị được tìm bằng đạo hàm trực tiếp của quan hệ (3.6.2) và được viết dưới dạng

Nếu chúng ta giới thiệu các vectơ

quan hệ (17-8) và (17-9) sẽ được viết lại thành

cấp Φ = cấp F - λ cấp φ = 0; (3.6.6)

trong đó đẳng thức của vectơ bằng 0 được hiểu theo từng thành phần.

Hình 3.6.1 - Giải thích bài toán cực trị có điều kiện

Khi N= 2 và tôi= 1, bài toán hình học tìm cực trị có điều kiện được rút gọn (Hình 17-6) thành tìm điểm tiếp tuyến A của đường cong φ = bđến một trong những đường cong mức không đổi f= hằng số.

Định lý 7.2.Đối với bài toán quy hoạch lồi (7.4)–(7.6), tập hợp các nghiệm khả thi có tính chất chính quy, một phương án là phương án tối ưu khi và chỉ khi tồn tại một vectơ sao cho
– điểm yên của hàm Lagrange.

Giả sử hàm mục tiêu
và chức năng là liên tục và khả vi, khi đó định lý Kuhn-Tucker có thể được bổ sung bằng các biểu thức giải tích xác định điều kiện cần và đủ cho điểm
là điểm yên của hàm Lagrange, tức là là lời giải cho bài toán quy hoạch lồi. Các biểu thức này có dạng sau:

Ở đâu Và là các giá trị đạo hàm riêng tương ứng của hàm Lagrange tính tại điểm yên ngựa.

Định lý Kuhn-Tucker chiếm vị trí trung tâm trong lý thuyết quy hoạch phi tuyến. Nó cũng đúng cho cái gọi là các bài toán quy hoạch bậc hai, tức là hàm mục tiêu ở đâu
với những hạn chế:

.

Trong trường hợp tổng quát giải các bài toán quy hoạch phi tuyến để xác định cực trị toàn cục của bài toán, không có phương pháp tính toán hiệu quả nào nếu không biết cực trị cục bộ nào cũng là cực trị toàn cục. Như vậy, trong bài toán quy hoạch lồi và bậc hai, tập nghiệm khả thi là tập lồi, khi đó nếu hàm mục tiêu là lõm thì mọi cực đại cục bộ cũng có tính toàn cục.

Ví dụ 7.3. Sử dụng định lý Kuhn-Tucker chúng ta tìm được
dưới những hạn chế

Chúng tôi giải quyết bằng đồ họa (Hình 7.2) và tìm thấy:
;
;
(xem giải pháp bên dưới để biết thêm chi tiết). Hãy chứng minh rằng có một vectơ Y 0 0, tại đó điều kiện Kuhn-Tucker được thỏa mãn ở điểm tối ưu. Hãy soạn hàm Lagrange:

Giải pháp
chúng tôi tìm thấy từ hệ thống:
. Từ phương trình thứ hai
thay thế vào phương trình đầu tiên của hệ thống. Phân biệt bằng :
. Trong biểu thức Và thay thế các giá trị
Và
. Ta có các giá trị đạo hàm riêng lớn hơn 0 và theo điều kiện chúng phải bằng 0 thì =0 Và = 0. Mặt khác, có thể không chấp nhận giá trị 0, bởi vì
từ đây
; Tất cả
những thứ kia. điều kiện Kuhn-Tucker được thỏa mãn nên điểm này là điểm cực trị.

Hình.7.2. Giải pháp đồ họa cho vấn đề phi tuyến

ví dụ lập trình 7.3

Điều kiện cần để tối ưu cho một bài toán quy hoạch phi tuyến có thể được phát biểu như sau. Cho phép
là nghiệm tối ưu của bài toán (7.4)–(7.6), và hàm
,
,
có thể phân biệt được ở thời điểm này Nếu như
là điểm không suy biến của tập bài toán chấp nhận được (7.4)–(7.6), thì nó là điểm Kuhn-Tucker của bài toán này.

Vì vậy, nếu một tập hợp được chấp nhận
bài toán (7.4)-(7.6) không có điểm kỳ dị và hàm số F(M),g Tôi (M), (
) khả vi tại mọi điểm
, thì giải pháp tối ưu cho vấn đề này nên được tìm kiếm trong số các điểm Kuhn-Tucker.

Như đã biết từ phân tích toán học, điểm đặc biệt tập hợp nghiệm có thể chấp nhận được của hệ phương trình tuyến tính và bất phương trình dạng

tức là tập hợp các giải pháp khả thi

nếu tại thời điểm
độ dốc của các hàm đó phụ thuộc tuyến tính
, trong đó biến thành . Ví dụ,
- điểm kỳ dị của tập hợp

Thật sự,

Vì vậy, nó là một hệ thống phụ thuộc tuyến tính.

Hàm chuyển màu
là một vectơ có tọa độ tương ứng bằng các giá trị đạo hàm riêng của hàm số
tại điểm M 0 . Vectơ này cho thấy hướng tăng trưởng nhanh nhất của hàm.

Điều kiện tối ưu cần thiết ít được sử dụng để giải hầu hết các bài toán quy hoạch phi tuyến, bởi vì Chỉ trong một số trường hợp hiếm hoi mới có thể tìm thấy tất cả các điểm Kuhn-Tucker của một bài toán quy hoạch phi tuyến.

Điều kiện đủ để tối ưuđối với bài toán quy hoạch phi tuyến: nếu
là điểm yên của hàm Lagrange của bài toán (7.4)–(7.6), khi đó
là giải pháp tối ưu cho vấn đề này.

Điều kiện này không cần thiết trong trường hợp tổng quát: hàm Lagrange có thể không có điểm yên, đồng thời bài toán quy hoạch phi tuyến ban đầu có nghiệm tối ưu.

Nhiều phương pháp khác nhau đã được biết đến cho phép người ta tìm ra giải pháp tối ưu cho bài toán quy hoạch phi tuyến một cách gần đúng. Tuy nhiên, những phương pháp này chỉ cung cấp một xấp xỉ khá tốt cho bài toán quy hoạch lồi, trong đó mọi cực trị cục bộ cũng là toàn cục. Nhìn chung, dưới dốc các phương thức hiểu các phương thức trong đó việc chuyển động đến điểm tối ưu của hàm trùng với hướng gradient của hàm này, tức là. bắt đầu từ một điểm nào đó
quá trình chuyển đổi tuần tự được thực hiện tới một số điểm khác cho đến khi xác định được giải pháp chấp nhận được vấn đề ban đầu. Trong trường hợp này, các phương pháp gradient có thể được chia thành 2 các nhóm.

ĐẾN Đầu tiên Nhóm này bao gồm các phương pháp trong đó các điểm đang nghiên cứu không vượt quá phạm vi các giải pháp khả thi cho vấn đề. Phổ biến nhất trong số các phương pháp này là phương pháp Frank-Wolf (Sói). Các phương pháp như vậy bao gồm phương pháp độ dốc Rosen dự kiến, phương pháp hướng dẫn hợp lệ của Zeutendijk.

Công ty thứ hai Nhóm này bao gồm các phương pháp trong đó các điểm đang nghiên cứu có thể thuộc hoặc không thuộc vùng của các giải pháp khả thi. Tuy nhiên, do việc thực hiện quá trình lặp lại, một điểm trong vùng các giải pháp khả thi được tìm thấy để xác định một giải pháp có thể chấp nhận được.

Trong các phương pháp này, phương pháp được sử dụng phổ biến nhất là chức năng phạt hoặc phương pháp Mũi tên-Hurwitz.

Khi tìm giải pháp cho các bài toán bằng phương pháp gradient, bao gồm cả các phương pháp nêu trên, quá trình lặp được thực hiện cho đến khi khoảng khắc đó, trong khi độ dốc của hàm
tại điểm tiếp theo
sẽ không trở thành bằng 0 hoặc cho đến khi
, Ở đâu – một số dương khá nhỏ đặc trưng cho độ chính xác của lời giải thu được.

Việc giải các bài toán lập trình phi tuyến phức tạp bằng phương pháp gradient đòi hỏi một lượng lớn phép tính và chỉ nên sử dụng máy tính.

Bằng một ví dụ, chúng tôi sẽ chỉ ra ý nghĩa chung của các phương pháp gradient để giải các bài toán quy hoạch phi tuyến.

Giả sử có hàm hai biến
. Đặt giá trị ban đầu của các biến là
, và giá trị của hàm
. Nếu như
không phải là cực trị thì giá trị mới đó của biến được xác định
Và
sao cho giá trị tiếp theo của hàm
hóa ra gần với mức tối ưu hơn so với trước đó.

Kích thước của số gia tăng được xác định như thế nào? Và ? Để làm được điều này, tại các điểm Và Hướng thay đổi của hàm về phía cực trị được xác định bằng cách sử dụng gradient. Làm sao nhiều giá trị hơnđạo hàm riêng thì hàm số thay đổi về cực trị càng nhanh. Do đó số gia tăng Và được chọn tỷ lệ thuận với giá trị của đạo hàm riêng Và tại các điểm
Và
. Như vậy,
Và
, Ở đâu – một giá trị được gọi là bước, đặt ra thang đo thay đổi Và .

Ví dụ 7.4.

Hãy để nó là cần thiết để tối đa hóa chức năng

(tối đa tại điểm (3;2))

.

Tại điểm
,
Tại
chúng ta có

;
,

Hãy thực hiện thêm một lần lặp nữa. Tại điểm
,
Tại
chúng ta có

;
,

Hình.7.3. Giải thích hình học của hai bước

phương pháp gradient ví dụ 7.4

Trong bộ lễ phục. 7.3 cho thấy sự chuyển động dọc theo gradient, được thực hiện trong trong ví dụ này. Thái độ cho biết chiều thay đổi của hàm số theo hướng cực đại. Nếu chúng ta lấy gradient bằng dấu trừ thì chúng ta sẽ tiến về mức tối thiểu.

Một vấn đề cụ thể với phương pháp gradient là việc lựa chọn kích thước bước t. Nếu chúng ta thực hiện từng bước nhỏ, chúng ta sẽ tìm kiếm điều tối ưu trong một thời gian rất dài. Nếu bạn chọn giá trị của nó quá lớn thì giá trị tối ưu có thể bị “vượt qua”. Vấn đề trung gian trong việc chọn kích thước bước tối ưu được giải quyết bằng các phương pháp thích hợp. Nếu bước tđược xác định gần đúng, thì theo quy luật, chúng không rơi vào mức tối ưu mà rơi vào vùng của nó. Các phương pháp gradient cung cấp việc xác định tối ưu cục bộ. Khi tìm kiếm mức tối ưu toàn cục bằng cách sử dụng gradient, thường có nghi ngờ rằng mức tối ưu tìm được có tính chất tối ưu toàn cục. Đây chính là nhược điểm của phương pháp này khi giải các bài toán quy hoạch không lồi.

Câu hỏi tự kiểm tra

Phát biểu bài toán quy hoạch phi tuyến.

Quá trình tìm lời giải cho một bài toán lập trình phi tuyến bằng cách sử dụng diễn giải hình học của nó.

Thuật toán phương pháp Lagrange giải bài toán quy hoạch phi tuyến.

Ứng dụng phương pháp Lagrange để giải bài toán quy hoạch phi tuyến trong trường hợp điều kiện kết nối là bất đẳng thức.

Các định nghĩa và định lý bổ trợ cần thiết để xem xét định lý trung tâm của quy hoạch phi tuyến - định lý Kuhn-Tucker.

Định lý Kuhn-Tucker.

Điều kiện tối ưu cần và đủ cho bài toán quy hoạch phi tuyến.

Ý nghĩa chung của phương pháp gradient trong giải pháp gần đúng của các bài toán quy hoạch phi tuyến.

Các nhóm phương pháp gradient để giải gần đúng các bài toán quy hoạch phi tuyến.

Định lý Kuhn-Tucker. Để phương án X 0 là lời giải của bài toán (1) – (4), điều cần và đủ là tồn tại một vectơ λ 0 ≥ 0 sao cho cặp (X 0 ,λ 0) với mọi X ≥ 0 và λ ≥ 0.
L(X, λ 0) ≤ L(X 0 ,λ 0) ≤ L(X 0 ,λ)

Mục đích của dịch vụ. Một máy tính trực tuyến được sử dụng để tìm cực trị của hàm số thông qua hệ số nhân Lagrange trong chế độ online bằng cách kiểm tra lời giải trong MS Excel. Trong trường hợp này, các nhiệm vụ sau được giải quyết:

1. hàm Lagrange L(X) được biên dịch dưới dạng tổ hợp tuyến tính của hàm F(X) và các ràng buộc g i(x);
2. đạo hàm riêng của hàm Lagrange được tìm thấy, ∂L/∂x i , ∂L/∂λ i ;
3. một hệ phương trình (n+m) được biên soạn, ∂L/∂x i = 0.
4. các biến x i và số nhân Lagrange α i được xác định.

Để hàm số hai vectơ biến (4) có điểm yên thì cần và đủ thỏa mãn điều kiện sau: điều kiện Kuhn-Tucker:
(5)
(6)
(7)
(8)

Nếu vấn đề được giải quyết giảm thiểu, khi đó sẽ có một điểm yên ngựa (X 0 , Y 0) nếu các quan hệ được thỏa mãn
L(X, λ 0) ≤ L(X 0, Y 0) ≤ L(X 0, Y)
Điều kiện tồn tại Kuhn-Tucker điểm yên ngựa các hàm Lagrange sẽ thay đổi dấu trong (5) và (7) ngược lại.

Ví dụ. Kiểm tra sự thỏa mãn điều kiện Kuhn-Tucker. Tìm điểm tối ưu của bài toán quy hoạch tuyến tính có ràng buộc:
f(x) = x 1 2 -x 2 → phút
g 1 (x) = x 1 - 1 ≥ 0
g 2 (x) = 26 - x 1 2 -x 2 2 ≥ 0
h 1 (x) = x 1 + x 2 - 6 = 0

Giải pháp:
Hàm Lagrange: L(X, λ) = x 1 2 -x 2 - λ 1 (1-x 1) + λ 2 (26-(x 1 2 +x 2 2)) + λ 3 (6-(x 1 +x 2))
Điều kiện cần để đạt cực trị của hàm Lagrange là sự bằng 0 của đạo hàm riêng của nó đối với các biến x i và yếu tố không xác định λ.
Chúng ta hãy kiểm tra sự thỏa mãn các điều kiện Kuhn-Tucker. Hãy tính ma trận của đạo hàm bậc hai hàm mục tiêu và các hàm ràng buộc.

Ma trận Hessian H f là nửa xác định dương cho mọi giá trị của x, do đó f(x) là hàm lồi.
Ràng buộc g 1 (x) – hàm tuyến tính, vừa lồi vừa lõm.
Ma trận Hessian của hàm g 2 (x) có dạng:

Δ1 = -2, Δ2 = 4.
Vì ma trận H g 2 là ma trận xác định âm nên g 2 (x) là ma trận lõm.
Hàm h 1(x) được đưa vào ràng buộc tuyến tính ở dạng đẳng thức. Do đó, các điều kiện (a), (b) và (c) của Định lý 1 được thỏa mãn. Bây giờ chúng ta hãy tìm điểm tối ưu x*.
Chúng ta có:


Phương trình có dạng sau:

Với j=1 và j=2 tương ứng, có thể thu được các biểu thức sau:
j=1, 2x 1 -μ 1 + 2x 2 μ 2 + λ 1 = 0
j=2, -1 + 2x 2 μ 2 + λ 1 = 0
Do đó, điều kiện Kuhn-Tucker cho ví dụ của chúng ta như sau:
2x 1 -μ 1 + 2x 2 μ 2 + λ 1 = 0
-1 + 2x 2 μ 2 + λ 1 = 0
x 1 + x 2 – 6=0
μ 1 (x 1 -1) = 0
μ 2 (26 - x 1 2 – x 2 2) = 0
μ 1 , μ 2 ≥ 0

Từ phương trình thứ ba ta tìm được: x 1 = 6-x 2. Thay giá trị x 1 vào các phương trình còn lại, ta được:
2(6-x 2) - μ 1 + 2μ 2 (6-x 2)
-1 + 2x 2 μ 2 + λ 1 = 0
μ 1 (6-x 2 -1) = 0 → x 2 = 5, x 1 = 1
μ 2 (26 – (6-x 2) 2 – x 2 2) = 0
Thay x 2 = 5 vào phương trình thứ nhất và thứ hai:

Từ phương trình thứ hai, chúng ta biểu thị λ và thay thế nó vào phương trình thứ nhất:
3 - μ 1 - 8μ 2 = 0
Cho μ 1 = 0,1 ≥ 0 thì μ 2 = 2,2 ≥ 0. Như vậy điểm x * = là điểm cực tiểu.

Vị trí trung tâm trong lý thuyết quy hoạch phi tuyến là định lý Kuhn-Tucker. Cho bài toán quy hoạch phi tuyến:

tìm giá trị lớn nhất của hàm số Z=f(x 1, x 2, ..., x n) có hạn chế

Hãy soạn hàm Lagrange cho bài toán này:

(4.2)

Nếu điều kiện chính quy được thỏa mãn (có ít nhất một điểm X, mà tôi(X)>0 cho mọi người Tôi), thì định lý sau đây đúng.

Định lý. Vectơ X(0) nếu và chỉ khi giải pháp tối ưu Bài toán (4.1), khi có vectơ Λ (0) sao cho cho tất cả

Chấm ( X (0),Λ (0)) được gọi là Yên xeđiểm cho chức năng F(X,Λ), và định lý được gọi là định lý điểm yên ngựa. Hãy chứng minh đủ điều kiện (4.3).

Bằng chứng. Cho phép X(0) >0 và Λ (0) >0 - điểm yên của hàm số F(X,Λ). Nếu trong (4.3) thay vào đó F(X,Λ) thay giá trị của nó (4.2), ta được

Tại .

Bất đẳng thức đúng có giá trị với mọi , do đó

Khi đó từ bất đẳng thức bên trái ta có

Vì trong trường hợp này

Cái đó f(X (0))>f(X).

Vì vậy, điểm X (0) thỏa mãn (4.1) và tại tất cả các điểm khác thỏa mãn (4.1), hàm số nhận giá trị nhỏ hơn tại X (0).

Tuyên bố này đưa lời giải của bài toán NLP đến việc tìm các điểm yên của hàm Lagrange F(X,Λ).

Việc chứng minh sự cần thiết của điều kiện (4.3) không được xem xét do tính phức tạp của nó.

Nếu như f(X) Và tôi(X)-các hàm khả vi thì điều kiện (4.3) tương đương với các điều kiện Kuhn-Tucker cục bộ sau:

Sự biểu lộ

có nghĩa là giá trị đạo hàm riêng của hàm Lagrange được lấy tại điểm ( X (0), Λ (0)), trong đó

X (0)=(x 1 (0) , x 2 (0) , ..., x n(0)), Λ (0) =(λ 1 (0) , λ 2 (0) , ..., λ N (0)).

Những điều kiện này có thể được viết dưới dạng vector:

Ví dụ. Tìm tối đa Z=-x 1 2 -x 2 2 có hạn chế

Hãy chứng minh rằng tồn tại Λ (0) 0 thỏa mãn điều kiện Kuhn-Tucker (4.4), (4.5) cho hàm số tại điểm tối ưu F(X,Λ):

F(X,Λ)=- x 1 2 -x 2 2 +λ 1 (2 x 1 +x 2 -2)+λ 2 (8-2 x 1 -x 2)+λ 3 (6- x 1 -x 2).

Theo điều kiện (4.5), λ 2 và λ 3 phải lấy giá trị bằng 0, vì, thay thế x 1 = 0,8 và x 2 = 0,4 trong biểu thức

chúng ta có các giá trị lớn hơn 0 và theo điều kiện

Theo điều kiện, λ 1 có thể nhận giá trị khác 0, vì

Theo (2.16), đạo hàm

phải lấy giá trị bằng 0, vì tọa độ của vectơ X (0) khác với số không. Chúng tôi tìm thấy λ 1 = 0,8. Do đó, tại điểm ( X (0),Λ (0)) điều kiện Kuhn-Tucker được thỏa mãn và nó thực sự là một điểm cực trị.

Hãy xem xét các điều kiện Kuhn-Tucker ở một dạng hơi khác.

Chúng ta có một bài toán tối ưu hóa với các ràng buộc ở dạng đẳng thức:

z= f(x 1 , x 2 , …, xn) → phút

trong những điều kiện:

g 1 ( x 1 , x 2 , ... , xn) = 0,

g 2 ( x 1 , x 2 , ... , xn) = 0,

g N(x 1 , x 2 , . . . , xn) = 0.

Điểm tối thiểu có điều kiện của hàm f trùng với điểm yên của hàm Lagrange:

Trong trường hợp này, điểm yên ngựa phải cung cấp mức tối thiểu cho các biến của nó. x tôi và tối đa trên các biến λ j.

Điều kiện cần cho một điểm dừng là đạo hàm riêng cấp một đối với mọi biến đều bằng 0:

Lưu ý rằng phương trình thứ hai ngụ ý rằng chỉ những điểm hợp lệ mới thỏa mãn các điều kiện cần thiết.

Để có điều kiện đủ cho sự tồn tại cực tiểu, cần thêm yêu cầu Hessian của hàm mục tiêu phải xác định dương.

Hãy xem xét tổng quan vấn đề lập trình toán học:

Z= f(X) → phút,

trong những điều kiện:

Các ràng buộc bất đẳng thức có thể được chuyển đổi thành các ràng buộc đẳng thức bằng cách thêm vào từng ràng buộc đó suy yếu biến

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

Khi đó điều kiện tối thiểu cần thiết có dạng:

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. Ta thu được các ràng buộc của bài toán ban đầu. Phương trình thứ ba có thể được nhân với ui/2 và thay thế các biến suy yếu bằng cách biểu thị chúng từ phương trình thứ hai của hệ.

Còn một điều kiện nữa phải được đáp ứng ở mức tối thiểu. Điều kiện này: λ Tôi= 0, đó là hệ quả của việc phân tích ý nghĩa vật lý các hệ số của hàm Lagrange.

Nó có thể được hiển thị rằng

Hệ số Lagrange tại điểm cực tiểu;

f* - giá trị tối ưu chức năng.

Rõ ràng, khi b tăng Tôi vùng chấp nhận được mở rộng, có nghĩa là giá trị tối thiểu chỉ có thể giảm, tức là đạo hàm phải âm (không dương). Do đó, tại điểm tối thiểu có điều kiện

Cuối cùng chúng ta thu được điều kiện cần thiết cho điều kiện tối thiểu:

Các biểu thức ở dòng thứ hai đảm bảo rằng điểm tối ưu là hợp lệ.

Dòng thứ ba chứa các thông tin sau: Nếu ràng buộc có hiệu lực (tức là biểu thức trong ngoặc bằng 0), thì hệ số Lagrange tương ứng hoàn toàn dương. Độ dương của hệ số Lagrange có nghĩa là ràng buộc tương ứng đang hoạt động, tức là. Thực tế là hạn chế này còn thiếu là nguyên nhân ngăn cản sự cải thiện hơn nữa của chức năng mục tiêu. Nếu ràng buộc không có hiệu lực (tức là biểu thức trong ngoặc không bằng 0), thì hệ số Lagrange tương ứng sẽ là bằng 0, I E. Hạn chế này không phải là thiếu sót; nó không ảnh hưởng đến việc cải thiện hơn nữa chức năng mục tiêu.

Đối với điểm cực đại có điều kiện, các hệ số Lagrange đổi dấu ngược lại (vì giá trị tối ưu của hàm mục tiêu tại điểm cực đại có điều kiện sẽ tăng).

Các điều kiện trên là tương đương Định lý Kuhn-Tucker và thường được gọi giống nhau.

Đủ điều kiện với giá trị nhỏ nhất (tối đa) là độ lồi (lõm) của hàm mục tiêu tại một điểm đứng yên. Điều này có nghĩa là Hessian phải xác định dương (âm).

Một bản tóm tắt của tài liệu trong chương này có thể được xem trong hai bài trình bày:

tập tin “Lập trình phi tuyến”;

tập tin "Định lý Kuhn-Tucker".

Các slide 10-14 của bài thuyết trình “Định lý Kuhn-Tucker” trình bày một ví dụ về cách giải bài toán Kuhn-Tucker.

4.5. Câu hỏi kiểm soát

(Được phát triển bởi Afanasyev M.Yu. và Suvorov B.P.)

Câu hỏi 1. Cho một hàm thực f(X S= . Cho phép X 1 và X 2 - điểm của phân khúc này và 0 £ l £ 1.

Bất đẳng thức nào sau đây là điều kiện của hàm số lồi?

Câu trả lời có thể:

Câu hỏi 2. Cho một hàm thực f(x), được xác định trên đoạn số thực S=. Cho phép x 1 và x 2 là các điểm của đoạn này và 0 £ l £ 1.

Bất đẳng thức nào sau đây là điều kiện để hàm số lõm chặt?

Câu trả lời có thể:

Câu hỏi 3. Chức năng

1) lồi;

2) lồi chặt;

3) lõm;

4) lõm hoàn toàn;

5) lồi và lõm.

Câu hỏi 4. Chức năng

3) lõm; 4) lõm hoàn toàn;

5) lồi và lõm.

Câu hỏi 5. Chức năng

1) lồi; 2) không lồi cũng không lõm;

3) lồi chặt; 4) lõm:

5) lồi và lõm.

Câu hỏi 6. Người mẫu mới xe máy tốc độ cao “Ốc” được công ty bán với giá (30 – 2 x) nghìn đô la mỗi mảnh, trong đó X- số lượng xe máy đã bán. Chi phí sản xuất biến đổi là 6.000 USD mỗi đơn vị và chi phí cố định là 30.000 USD. Hãy tối đa hóa lợi nhuận kinh doanh của bạn trong tuần.

Giả sử sự thay đổi về thuế suất bán hàng dẫn đến thuế bán hàng tăng thêm 4.000 USD cho mỗi chiếc xe máy được bán.

Sản lượng xe máy tối ưu sẽ thay đổi như thế nào so với tình hình ban đầu?

(Giải bằng hàm Lagrange.)

Câu trả lời có thể:

1) sẽ tăng thêm 2 ; 2) sẽ giảm đi 2 ;

3) sẽ không thay đổi; 4) sẽ tăng thêm 1 ;

5) sẽ giảm đi 1 .

Câu hỏi 7. Giả sử bạn có 2 tuần (14 ngày) kỳ nghỉ ở Quần đảo Canary và Nice. Hãy để hàm tiện ích của bạn có dạng 2 KN – 3K 2 – 4N2,Ở đâu ĐẾN Và N- số ngày bạn ở Quần đảo Canary và Nice tương ứng.

Bạn nên dành bao nhiêu ngày ở Nice để tối đa hóa chức năng tiện ích của mình?

(Để giải, hãy sử dụng hàm Lagrange. Làm tròn kết quả đến số nguyên gần nhất. Kiểm tra xem các điều kiện tối ưu Kuhn-Tucker có đáp ứng hay không.)

Câu trả lời có thể:

1) 3 ; 2) 4 ; 3) 5 ; 4) 6 ; 5) 7 .

Câu hỏi 8.Đối với bài toán ở Câu hỏi 7, hãy tìm giá trị ước lượng kép của ràng buộc.

(Làm tròn kết quả đến số nguyên gần nhất.)

Câu trả lời có thể:

1) 41 ; 2) 34; 3) 29 ; 4) 39 ; 5) 44 .

Câu hỏi 9. Nhà độc quyền lên kế hoạch sản xuất và bán hàng cho giai đoạn tiếp theo. Giá: R 1 = 14 – 0,25x 1 (mỗi sản phẩm 1); R 2 = 14 – 0,5X 2 (mỗi sản phẩm 2), trong đó x 1 và X 2 - doanh số bán sản phẩm. Giả sử rằng tất cả các sản phẩm sản xuất ra đều được bán. Tổng khối lượng bán hàng tối đa là 57.

Việc phát hành sản phẩm 2 tối ưu là gì?

Câu trả lời có thể:

1) 36,4 ; 2) 30,7 ; 3) 26,3 ; 4) 20,6 ; 5) 41,8 .

Câu hỏi 10. Chủ một doanh nghiệp nhỏ có 100 nghìn rúp cho tháng tiếp theo, số tiền này anh ta có thể chi để tăng tài sản cố định ĐẾN(mua thiết bị) với mức giá 1 nghìn rúp mỗi chiếc hoặc để mua thêm lao động L với mức giá 50 rúp./giờ. Tăng số lượng thành phẩm có thể bán được với giá 10 nghìn rúp. trên mỗi đơn vị, được xác định bởi hàm sản xuất F(K, L)= L 2/7 K 2/5.

Cần chi bao nhiêu tiền để tăng tài sản cố định?

Câu trả lời có thể:

1) 74,36 nghìn chà.; 2) 58,33 nghìn rúp.; 3) 63,44 nghìn rúp.;

4) 45,66 nghìn rúp.; 5) 39,77 nghìn rúp.

Câu trả lời cho các câu hỏi:

1 -4,2 - 1,3 -4,4 - 5,

5 -2, 6 -5,7- 4,8- 2,9- 4,10- 2.