Trường Đại học Công nghiệp thành phố Hồ Chí Minh

Khoa Công nghệ Cơ khí

CHƯƠNG 05: TỐI ƯU HÀM NHIỀU BIẾN SỐ VỚI RÀNG BUỘC BẤT ĐẲNG THỨC: PHƯƠNG PHÁP CỔ ĐIỂN Thời lượng: 3 tiết

2

Tối ưu hàm nhiều biến với ràng buộc bất đẳng thức

Tìm cực trị (Optimum) của hàm nhiều biến sau:

Với các điều kiện ràng buộc bất đẳng thức:

Với:

3

4

Giải hệ (n+2m) phương trình sau:

5

Tính định thức sau. Tìm nghiệm của phương trình định thức = 0. Nếu tất cả các nghiệm đều mang dấu – hoặc 1 số = 0 thì lời giải là cực đại, nếu tất cả nghiệm mang dấu + hoặc 1 số = 0 thì lời giải là cực tiểu. Nếu 1 vài nghiệm mang dấu –, một số còn lại mang dấu + thì đó không phải là cực trị.

Ma trận Hessian

m

n+m

n+m

n+m

m

m

n+m

m

6

n

m

Biến đổi: m

n

n

m

m

m

m

m

m

n

 Định thức này là 1 hàm đa thức bậc n có tối đa n nghiệm

7

Cực tiểu hàm số sau:

Với các ràng buộc:

Biến đổi lại các ràng buộc:

Hàm Lagrange:

8

Hệ PT (1)÷(3) tương đương 9 phương trình:

Giải hệ PT tìm 9 ẩn

9

Hệ PT (5) sẽ tương đương với 8 tình huống. Mỗi tình huống sẽ kết hợp với hệ phương trình (4) và (6). Ta sẽ được 8 hệ phương trình như sau:

1) Hệ PT 1:

Vô nghiệm

10

2) Hệ PT 2:

Vô nghiệm

11

3) Hệ PT 3:

Vô nghiệm

12

4) Hệ PT 4:

Vô nghiệm

13

5) Hệ PT 5:

Vô nghiệm

14

6) Hệ PT 6:

Vô nghiệm

15 15

7) Hệ PT 7:

Vô nghiệm

16 16

8) Hệ PT 8:

Đây là điểm dừng, cần kiểm tra điều kiện đủ để biết về cực trị

17

Tính ma trận Δ như slide 6:

18

Tính định thức của ma trận này

19

Tính định thức của ma trận Δ

Cực tiểu tại ràng buộc

Kết luận: Cực tiểu của hàm f = 10500 với x1*=50, x2*=50, x3*= 50

- Phương trình (3) để đảm bảo các điều kiện gj(x) ≤ 0

20

được thỏa mãn

- Phương trình (2) cho ra kết quả hoặc là λj = 0, hoặc là

yj = 0

- Nếu λj = 0 thì có nghĩa là ràng buộc thứ j không cần

dùng tới và nó có thể được bỏ qua

- Nếu yj = 0 thì có nghĩa là ràng buộc gj(x)=0 hoạt động

tại ngay điểm cực trị

 Ta có thể chia các ràng buộc ra 2 tập hợp con:  Tập hợp j ϵ J1 khi yj = 0 (ràng buộc hoạt động ngay

điểm cực trị, λj ≠ 0 )

 Tập hợp j ϵ J2 khi λj = 0 (ràng buộc được bỏ qua)

21

Hệ phương trình (4)÷(6) thể hiện n+p+(m-p) = n+m phương trình với n+m ẩn số: xi (i=1..n), λj (jϵJ1 hay j=1..p), yj (jϵJ2 hay j=(p+1)..(m-p)). Với p – số ràng buộc làm việc.

Giả sử p ràng buộc đầu tiên làm việc, phương trình (4):

22

Trong đó:

Phương trình (7) có ý nghĩa rằng: giá trị đối của độ dốc của hàm mục tiêu f có liên hệ tuyến tính với độ dốc của các ràng buộc làm việc tại điểm cực trị.

23

Hướng khả thi (Feasible Direction) Véctơ S được gọi là hướng khả thi từ điểm x nếu có thể tiến một bước nhỏ dọc theo S mà không rời khỏi ngay lập tức khỏi vùng hợp lệ. Với các bài toán có các bề mặt ràng buộc đủ mịn ta có điều kiện sau:

Hàm ràng buộc lồi

Hàm ràng buộc tuyến tính

Hàm ràng buộc lõm

Góc = 90°

Hàm lõm

Góc > 90°

Góc > 90°

Góc > 90°

Tích vô hướng < 0 thì góc giữa 2 véc tơ là góc tù

Xét trường hợp chỉ có 2 ràng buộc làm việc  p = 2

24

Gọi S là hướng khả thi tại điểm cực trị. Nhân cả 2 vế của (7’) cho ST, Ta có:

Do S là hướng khả thi nên nó phải thỏa mãn các điều kiện:

Nếu Nếu

Giá trị hàm f tăng khi di chuyển dọc theo hướng S Giá trị hàm f giảm khi di chuyển dọc theo hướng S

Tìm cực tiểu (min)  λj ≥ 0 (j=1..p) Tìm cực đại (max)  λj ≤ 0 (j=1..p)

Ý nghĩa của điều này giúp chúng ta tìm thẳng cực tiểu hay cực đại bằng cách chọn thông qua dấu của các λj

25

Điều kiện Karush-Kuhn-Tucker

26

Điều kiện Karush-Kuhn-Tucker

1. Luôn xuất phát từ hệ phương trình (9). Sẽ có 2m trường hợp con, tương ứng 2m hệ phương trình 9’. Ví dụ, ta sẽ có hệ phương trình 9.1, 9.2, …, 9.2m. Mỗi hệ phương trình sẽ có m phương trình.

2. Với mỗi hệ phương trình 9.i (i=1.. 2m), ta ghép với các hệ phương & bất phương trình (8), (10) và (11) khi tìm cực tiểu / (12) khi tìm cực đại, để tìm toàn bộ các nghiệm x* và λ* thỏa mãn

27

Điều kiện Karush-Kuhn-Tucker

Cực tiểu hàm số sau:

Với các ràng buộc:

Biến đổi lại các ràng buộc:

Hàm Lagrange:

28

Điều kiện Karush-Kuhn-Tucker

Hệ số (9) sẽ tương đương với 23=8 trường hợp con như sau:

29

1) Trường hợp 1:

Vô nghiệm

30

2) Trường hợp 2:

Vô nghiệm

31

3) Trường hợp 3:

Vô nghiệm

32

4) Trường hợp 4:

Vô nghiệm

33

5) Trường hợp 5:

Vô nghiệm

34

6) Trường hợp 6:

Vô nghiệm

35

7) Trường hợp 7:

Vô nghiệm

36

8) Trường hợp 8:

Đây là điểm cực tiểu. Không cần kiểm tra lại điều kiện đủ (Định thức Δ)  fmin = 10500