Bài giảng Tối ưu hóa trong thiết kế cơ khí - Chương 6: Tối ưu hàm nhiều biến số với ràng buộc tổng quát - Phương pháp cổ điển

Trường Đại học Công nghiệp thành phố Hồ Chí Minh Khoa Công nghệ Cơ khí CHƯƠNG 06: TỐI ƯU HÀM NHIỀU BIẾN SỐ VỚI RÀNG BUỘC TỔNG QUÁT: 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 tổng quát  f xTìm cực trị (Optimum) của hàm nhiều biến sau: Với m điều kiện ràng buộc bất đẳng thức: Với:  1 2 T nx x xx   0 1,2, , jg j m   x Với p điều kiện ràng buộc đẳng thức:   0 1,2, , lh l p   x 3 Điều kiện Karush-Kuhn-Tucker             1 1 1 2 1 2 1 2 , , ; ; pm j j l l j l TT T n m p L f g h x x x                     x λ η x x x x λ η                             1 1 , , 0; 1.. 1 0; 1.. 2 0; 1.. 3 0 min ; 1.. 4 0 max 0; 1.. 5 pm j l j j j li i i i j j j j j l g hL f i n x x x x g j m g j m f j m f h l p                                       x λ η x x x x x x x x 4 Điều kiện Karush-Kuhn-Tucker (Tiếp) 11 1 22 2; ; pn m x x x                                                   x λ η Giải hệ (1)÷(5) với (n+m+p) ẩn, ta có: Kiểm tra J1 véctơ Gradient của hàm bất đẳng thức ràng buộc g tại điểm cực trị và p véc tơ Gradient của hàm đẳng thức ràng buộc h tại điểm cực trị x*, phải là không phụ thuộc tuyến tính với nhau. Nếu vậy thì x*, λ*, η* sẽ là điểm cực trị.    1 0 j j g j J     x   1.. lh l p   x và KHÔNG PHỤ THUỘC TUYẾN TÍNH Không phụ thuộc/phụ thuộc tuyến tính 5 Cho M = J1+p véc tơ:             1 1 2 1 2 1 1 1 1 1 2 1 2, , , , , , , pJ J J J J pg g g h h h               v v v v v v x x x x x x Với:  1 2 T nx x xx Xây dựng ma trận A:   1 1 1 11 2 1 2 x M 1 ; J J J J p N M J p N n           A v v v v v v Trường hợp 1: Khi M > N  Các véc tơ sẽ luôn phụ thuộc tuyến tính Trường hợp 2: Khi M = N Ta tính det(A). Nếu det(A) = 0 thì phụ thuộc tuyến tính, ngược lại thì không phụ thuộc tuyến tính. Trường hợp 3: Khi M < N, Ta tính rank(A). Nếu rank(A)=M tức là bằng số lượng véc tơ thì hệ độc lập tuyến tính. Nếu khác rank(A)≠M thì hệ phụ thuộc tuyến tính. 6 Không phụ thuộc/phụ thuộc tuyến tính   1 2 1 1 1 1 2 2 2 2 2 1 2 1 2 1 1 1 1 2 2 2 2 x 1 2 ; ; ; M M M M N N N M M N M M N N N a a a a a a a a a a a a a a a a a a                                                          1v v v A Xác định M véc tơ v sau đây là độc lập tuyến tính hay phụ thuộc tuyến tính Đưa về dạng bậc thang Xác định hạng Rank(A) 7   1 2 1 1 1 1 2 2 2 2 x 1 2 M M N M M N N N a a a a a a a a a              A 1) Nếu Rank(A)=M  Các véc tơ v là độc lập tuyến tính 2) Nếu Rank(A)<M  Các véc tơ v là phụ thuộc tuyến tính Do Rank(A)≤N, nên nếu N < M thì Rank(A)<M, có nghĩa là nếu N<M thì các véc tơ v sẽ luôn phụ thuộc tuyến tính Không phụ thuộc/phụ thuộc tuyến tính 8 Không phụ thuộc/phụ thuộc tuyến tính Xác định 3 véc tơ v sau đây là độc lập tuyến tính hay phụ thuộc tuyến tính 1 2 3 2 4 6 6 3 9 ; ; ; 2 2 4 2 0 1                                       v v v   Gaussian Elimination 4 62 4 6 2 96 3 9 0 9 2 2 4 0 0 3 2 0 1 0 0 0                       A 4 3 N M    Rank(A)=3=M Kết luận: 3 véctơ v là độc lập tuyến tính 9 Tối ưu hàm nhiều biến với ràng buộc tổng quát Tìm cực trị hàm sau:   2 21 2 3 1 2 1 3, , 2 30 16 min/ maxf x x x x x x x     Với 2 ràng buộc bđt: 1 2 3 36 3 0; 0x x x x    3 2 1 n m p      Với 1 ràng buộc đt: 1 2 35 3 4 20 0x x x            2 2 1 2 1 3 1 1 2 3 2 3 1 1 2 3 , , 2 30 16 6 3 5 3 4 20 L x x x x x x x x x x x                  x λ η      1 2 3 1 2 1; ; T T T x x x     x λ η 10                         1 1 1 1 2 1 1 2 1 2 1 3 1 1 2 3 2 3 1 2 3 3 1 2 1 2 3 2 30 5 0 1 4 6 3 0 2 16 3 4 0 3 6 3 0 4 0 5 6 3 0 6 0 7 0 8 0 9 5 3 4 20 0 10 L x x L x x L x x x x x x x x x x x x                                                         Giải hệ PT tìm 6 ẩn Hệ PT (4) và (5) sẽ tương đương với 4 trường hợp con như sau: 11 1) Trường hợp 1: 1 1 1 2 1 1 1 2 1 1 2 1 2 3 3 1 2 1 2 3 1 2 1 1 2 3 2 30 5 0 4 6 3 0 16 3 4 0 0 0 6 3 0 0 0 0 5 3 4 20 0 0 4 3 1 0 5 x x x x x x x x x x x x                                                                   Đây là điểm dừng  f = - 123 12 2) Trường hợp 2: 1 1 1 2 1 1 1 2 1 1 3 1 2 3 3 1 2 1 2 3 1 2 3 1 2 1 2 30 5 0 4 6 3 0 16 3 4 0 0 0 6 3 0 0 0 0 5 3 4 20 0 220 5 335 59 165 59 0 0 64 0 59 9 x x x x x x x x x x x x x                                                                      Đây là điểm dừng, có khả năng là cực đại địa phương  f = - 7225/59 13 3) Trường hợp 3: 1 1 1 2 1 1 1 2 1 1 2 3 2 1 2 3 3 1 2 1 1 2 3 1 1 2 2 3 2 30 5 0 4 6 3 0 16 3 4 0 6 3 0 0 6 3 0 0 0 0 5 3 4 20 0 1695 947 1641 947 3847 947 1280 4748 94 0 947 7 0 x x x x x x x x x x x x x x x                                                                                Đây là điểm dừng, có khả năng là cực đại địa phương  f = - 103681/947 14 4) Trường hợp 4: 1 1 1 2 1 1 1 2 1 1 2 3 3 1 2 3 3 1 2 1 2 1 1 3 1 2 3 2 2650 1089 769 2 30 5 0 4 6 3 0 16 3 4 0 6 3 0 0 6 3 0 0 0 0 44 5 3 4 20 40 11 20 33 0 20 1 4 1 0 90 8 089 x x x x x x x x x x x x x x x x                                                                              Đây là điểm dừng, có khả năng là cực đại địa phương  f = - 103600/1089 15 Tính Gradient của các hàm ràng buộc gj và hl:       1 2 1 1 1 2 1 2 2 2 1 2 3 3 1 1 1 1 2 1 3 1 0 6 ; 0 ; 3 1 5 3 4 g g x x g g g g x x g g x x h x h h h h x                                                                                             x x x x x x 16      1 2 1 1 0 5 6 ; 0 ; 3 3 1 4 g g h                                          x x x x x x 1) Trường hợp 1: Do λ1 = 0 và λ2 = 0 nên    1 5 3 4 A h               x x Trường hợp này không xét 2 grandient của g vì các λ của chúng = 0. Grandient của h đứng 1 mình nên không phụ thuộc tuyến tính với ai. 2) Trường hợp 2: Do λ1 = 0 nên      2 1 0 5 0 3 1 4 A g h                  x x Có 2 định thức thành phần khác 0 nên 2 véctơ này không phụ thuộc tuyến tính. Đây là cực trị 17 3) Trường hợp 3: Do λ2 = 0      1 1 1 5 6 3 3 4 A g h                  x x Cả 3 định thức thành phần khác 0 nên 2 véc tơ này không phụ thuộc tuyến tính. Đây là cực trị. 4) Trường hợp 4:           1 2 1 1 0 5 6 0 3 3 1 4 det 33 0 A g g h A                         x x x 3 véctơ trên không phụ thuộc tuyến tính nên trường hợp 4 cũng là cực trị địa phương. Điểm dừng ở trường hợp 1 là điểm cực tiểu với giá trị nhỏ nhất. 3 trường hợp còn lại là cực đại địa phương. Trường hợp 4 là điểm cực đại toàn cục. 18 Bài toán tối ưu hóa các hàm lồi Nếu hàm mục tiêu f(x) cùng các hàm ràng buộc gj(x), hl(x) là những hàm số lồi thì bài toán gọi là các bài toán tối ưu hàm lồi (convex programming problem)  Khi đó nếu các λj ≥ 0 thì các hàm Lagrange L cũng sẽ là những hàm lồi  Khi đó thì tại các điểm dừng x* cũng sẽ chính là điểm cực tiểu tuyệt đối (toàn cục)  Điều kiện KKT sẽ trở thành điều kiện cần và đủ để tìm min toàn cục  Nếu bài toán tối ưu là tìm cực tiểu các hàm lồi, thì sẽ không có điểm dừng cũng như các cực đại địa phương. Tuy nhiên những bài toán kỹ thuật thực tế rất khó xác định được các hàm số là lồi hay không. 19 Tối ưu hàm nhiều biến với ràng buộc tổng quát Tìm cực trị hàm sau:   21 2 3 1 2 3, , 6 2 4 minf x x x x x x     Với 2 ràng buộc bđt: 1 2 3 22 2 0; 0x x x x    3 2 1 n m p      Với 1 ràng buộc đt: 21 2 32 4 0x x x            2 1 2 3 1 1 2 3 2 2 2 1 1 2 3 , , 6 2 4 2 2 2 4 L x x x x x x x x x x                  x λ η      1 2 3 1 2 1; ; T T T x x x     x λ η 20                         1 1 1 1 2 1 2 3 1 1 3 3 1 1 2 3 2 2 1 2 3 2 1 2 2 1 2 3 6 2 2 0 1 2 2 4 0 2 8 2 0 3 2 2 0 4 0 5 2 2 0 6 0 7 0 8 0 9 2 4 0 10 L x L x L x x x x x x x x x x x x x x                                                        Giải hệ PT tìm 6 ẩn Hệ PT (4) và (5) sẽ tương đương với 4 trường hợp con như ví dụ trước. 21 1) Trường hợp 1:     1 1 1 2 1 3 1 1 3 1 2 1 2 3 2 1 2 2 1 2 3 6 2 2 0 1 2 2 4 0 2 8 2 0 0 0 2 2 0 0 0 0 2 4 0 x x x x x x x x x                                             Vô nghiệm 22 2) Trường hợp 2:     1 1 1 2 1 3 1 1 3 1 2 1 2 3 2 1 2 2 1 2 3 6 2 2 0 1 2 2 4 0 2 8 2 0 0 0 2 2 0 0 0 0 2 4 0 x x x x x x x x x x                                            Vô nghiệm 23 3) Trường hợp 3:     1 1 1 2 1 3 1 1 3 1 2 3 2 1 2 3 2 1 2 2 1 1 2 1 2 3 2 1 3 6 2 2 0 1 2 2 4 0 2 8 2 0 2 2 0 0 2 2 0 0 0 0 2 4 5 3 185 1536 55 15 4 3 0 36 5 16 0 x x x x x x x x x x x x x x x                                                                            Đây là điểm dừng  f = -25/96 24     1 1 1 2 1 3 1 1 3 1 2 3 2 1 2 3 2 1 2 2 1 2 3 6 2 2 0 1 2 2 4 0 2 8 2 0 2 2 0 0 2 2 0 0 0 0 2 4 0 x x x x x x x x x x x x x                                             Vô nghiệm 4) Trường hợp 4: 25 Tính Gradient của các hàm ràng buộc gj và hl:         1 2 1 1 1 2 1 2 2 2 1 2 3 3 1 1 1 1 1 2 3 1 3 2 0 2 ; 1 ; 1 0 2 2 4 4 2 5 8 g g x x g g g g x x g g x x h x h h h h x h x                                                                                                    x x x x x x     26 Ta chỉ có 1 trường hợp có nghiệm với λ2=0      1 1 2 2 2 4 1 5 8 A g h                       x x Có 3 định thức thành phần khác 0 nên 2 véctơ này không phụ thuộc tuyến tính. Đây là cực trị Đây là điểm cực tiểu   1 2 3 185 1536 55 1536 25 96 5 16 x x x f                    x 27 Giải hệ phương trình phi tuyến bằng MATLAB   11 2 2 2 1 2 sin 0 2 x x x e x x x        digits(32); [x1,x2] = solve('sin(x1+x2) - exp(x1)*x2 = 0','x1^2 - x2 = 2')