Bài giảng Tối ưu hóa trong thiết kế cơ khí - Chương 5: 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

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  f xTì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:  1 2 T nx x xx   0 1,2, , jg j m   x 3     20 0 1,2, , 1, 2, , j j j g g y j m j m                 x x     2, 0 1,2, , j j jG g y j m     x y x             1 1 2 1 2 1 2 , , , ; ; m j j j T T n m T m L f G x x x y y y           x y λ x x y x y λ 4 Giải hệ (n+2m) phương trình sau:                     1 2 , , ; 1.. 1 , , 2 0; 1.. 2 , , , 0; 1.. 3 m j j ji i i j j j j j j j gL f i n x x x L y j m y L G g y j m                             x y λ x x x y λ x y λ x y x 1 1 1 2 2 2; ; n m m x y x y x y                                                           x λ y 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ị.                          11 12 13 11 21 11 21 22 23 12 22 22 1 2 3 1 2 11 12 13 1 21 22 23 2 1 2 3 0 0 0 0 0 0 0 0 0 mn m mn m n m n m n m n m n m n m n m m n m n m n m m m m m n m L z L L L G G G L L z L L G G G L L L L z G G G G G G G G G G G G G G G                   m n+m m m n+m n+m n+m m Ma trận Hessian 6 Biến đổi: 11 12 13 1 11 21 1 21 22 23 2 12 22 2 1 2 3 1 2 1 1 2 2 11 12 13 1 1 21 22 23 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 2 0 0 0 0 0 0 0 2 0 0 2 0 0 0 0 0 0 0 2 0 0 2 2 0 0 0 0 0 0 2 n m n m n n n nn n n mn m m n n L z L L L g g g L L z L L g g g L L L L z g g g z y z y z y g g g g y g g g g y                    1 2 3 0 0 0 0 0 0 2 0 0 0m m m mn mg g g g y  m m m m n n n n m m m m       2 , , , , 1.. ; 1.., 1.. k ij kl i j l L g L g x x x k m l ni j n              x y λ x x y λ x  Đị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:   2 2 21 2 3 1 2 3 1 2, , 40 20 minf x x x x x x x x      Với các ràng buộc: 1 1 2 1 2 350; 100; 150x x x x x x      3 3 n m    Biến đổi lại các ràng buộc:             1 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 2 1 1 2 3 1 1 1 2 2 1 2 3 2 1 2 2 2 3 1 2 3 3 1 2 3 3 , , 50 0 , , 100 0 , , 150 0 , , , 50 0 , , , 100 0 , , , 150 0 g x x x x g x x x x x g x x x x x x G x x x y x y G x x x y x x y G x x x y x x x y                                       Hàm Lagrange:       3 1 2 3 1 2 3 1 , , , , , , ,j j j j L f x x x G x x x y   x y λ 8           2 2 2 2 1 2 3 1 2 1 1 1 2 2 2 1 2 2 3 1 2 3 3 , , 40 20 50 100 150 L x x x x x x y x x y x x x y                        x y λ Hệ PT (1)÷(3) tương đương 9 phương trình:             1 1 2 3 2 2 3 3 3 1 1 2 2 3 3 2 1 1 2 1 2 2 2 1 2 3 3 2 40 0 1 2 20 0 4 2 0 2 0 2 2 0 5 2 0 50 0 3 100 0 6 150 0 x x x y y y x y x x y x x x y                                                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: 1 2 3 1 1 2 3 2 2 3 3 3 2 1 1 2 1 2 2 2 1 2 3 3 0 0 0 2 40 0 2 20 0 2 0 50 0 100 0 150 0 x x x x y x x y x x x y                                                 Vô nghiệm 10 2) Hệ PT 2: 1 2 3 1 1 2 3 2 2 3 3 3 2 1 1 2 1 2 2 2 1 2 3 3 0 0 0 2 40 0 2 20 0 2 0 50 0 100 0 150 0 y x x x x y x x y x x x y                                                Vô nghiệm 11 3) Hệ PT 3: 1 2 3 1 1 2 3 2 2 3 3 3 2 1 1 2 1 2 2 2 1 2 3 3 0 0 0 2 40 0 2 20 0 2 0 50 0 100 0 150 0 y x x x x y x x y x x x y                                                Vô nghiệm 12 4) Hệ PT 4: 1 2 3 1 1 2 3 2 2 3 3 3 2 1 1 2 1 2 2 2 1 2 3 3 0 0 0 2 40 0 2 20 0 2 0 50 0 100 0 150 0 y y x x x x y x x y x x x y                                               Vô nghiệm 13 5) Hệ PT 5: 1 2 3 1 1 2 3 2 2 3 3 3 2 1 1 2 1 2 2 2 1 2 3 3 0 0 0 2 40 0 2 20 0 2 0 50 0 100 0 150 0 y x x x x y x x y x x x y                                                Vô nghiệm 14 6) Hệ PT 6: 1 2 3 1 1 2 3 2 2 3 3 3 2 1 1 2 1 2 2 2 1 2 3 3 0 0 0 2 40 0 2 20 0 2 0 50 0 100 0 150 0 y y x x x x y x x y x x x y                                               Vô nghiệm 15 7) Hệ PT 7: 1 2 3 1 1 2 3 2 2 3 3 3 2 1 1 2 1 2 2 2 1 2 3 3 0 0 0 2 40 0 2 20 0 2 0 50 0 100 0 150 0 y y x x x x y x x y x x x y                                               Vô nghiệm 16 8) Hệ PT 8: 1 2 3 1 1 2 3 2 2 3 3 3 2 1 1 2 1 2 2 2 1 2 3 1 1 2 2 1 2 3 3 33 0 0 0 2 40 0 2 20 0 2 0 50 0 100 0 150 20 20 1 50 50 50 00 0 0 0 0 y y y y y x x x x y x x x x x y x x x y y                                                                            Đâ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: 2 11 2 1 2 22 2 2 2 33 2 3 2 2 2 L L x L L x L L x                             2 2 2 2 1 2 3 1 2 1 1 1 2 2 2 1 2 2 3 1 2 3 3 1 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 , , 40 20 50 100 150 , , 50 , , 100 , , 150 L x x x x x x y x x y x x x y g x x x x g x x x x x g x x x x x x                                    x y λ 2 12 1 2 2 13 1 3 2 21 2 1 0 0 0 L L x x L L x x L L x x                2 23 2 3 2 31 3 1 2 32 3 2 0 0 0 L L x x L L x x L L x x                1 11 1 1 12 2 1 13 3 1 0 0 g g x g g x g g x              18 2 21 1 2 22 2 2 23 3 1 1 0 g g x g g x g g x               3 31 1 3 32 2 3 33 3 1 1 1 g g x g g x g g x                2 0 0 0 0 0 1 1 1 0 2 0 0 0 0 0 1 1 0 0 2 0 0 0 0 0 1 0 0 0 40 0 0 0 0 0 0 0 0 0 40 0 0 0 0 0 0 0 0 0 200 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 z z z z z z                                       1 2 3 1 2 3 50 50 50 20 20 100 x x x                                                x λ 1 2 3 0 0 0 y y y                       y Tính định thức của ma trận này 19 Tính định thức của ma trận Δ       2 40 0 det 40 200 0 40 0 200 0 z z                             Z 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 20 - Phương trình (3) để đảm bảo các điều kiện gj(x) ≤ 0 đượ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                     1 1 1 2 2 1 0; 1.. 4 0; 5 2 0; 6 p j j ji i j J j j j gf i n x x g j J g y j J                  x x x x 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):           1 2 1 2 1 1 2 2 ; 1.. 7 p p i i i i p p gg gf i n x x x x f g g g                            x x x x 22 Trong đó: 11 2 2 ; 1.. i i j n i n g xf x f x g x f g j p f x g x                                 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: 0; 1..T jg j p  S Hàm ràng buộc lồi Góc > 90° Hàm ràng buộc tuyến tính Góc = 90° Góc > 90° Hàm ràng buộc lõm Hàm lõm Góc > 90° Tích vô hướng < 0 thì góc giữa 2 véc tơ là góc tù 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ó:  1 1 2 2 8 T T Tf g g      S S S Xét trường hợp chỉ có 2 ràng buộc làm việc  p = 2    1 1 2 27 7f g g        Do S là hướng khả thi nên nó phải thỏa mãn các điều kiện: 1 2 0 0 T T g g       S S Nếu 0T f S Giá trị hàm f tăng khi di chuyển dọc theo hướng S Nếu 0T f 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               1 , 0; 1.. 8 0; 1.. 9 0; 1. 0; 1.. . 10 11j m j j ji i i j j j gL f i n x x x g j m g j m j m                          x λ x x               1 , 0; 1.. 8 0; 1.. 9 0; 1. 0; 1.. . 10 12j m j j ji i i j j j gL f i n x x x g j m g j m j m                          x λ x x 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:   2 2 21 2 3 1 2 3 1 2, , 40 20 minf x x x x x x x x      Với các ràng buộc: 1 1 2 1 2 350; 100; 150x x x x x x      3 3 n m    Biến đổi lại các ràng buộc:       1 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 , , 50 0 , , 100 0 , , 150 0 g x x x x g x x x x x g x x x x x x                  Hàm Lagrange:             3 1 2 3 1 2 3 1 2 2 2 1 2 3 1 2 1 1 2 1 2 3 1 2 3 , , , , , 40 20 50 100 150 j j j L f x x x g x x x x x x x x x x x x x x                          x λ 28 Điều kiện Karush-Kuhn-Tucker                 1 1 2 3 1 2 2 3 2 3 3 3 1 1 2 1 2 3 1 2 3 , 2 40 0 8 , 2 20 0 , 2 0 50 0 9 100 0 150 0 L x x L x x L x x x x x x x x                                               x λ x λ x λ     1 1 2 1 2 3 1 2 3 50 0 10 100 0 150 0 0 11 0 0 x x x x x x                      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: 1 2 3 1 1 2 3 2 2 3 3 3 1 1 2 1 2 3 1 2 3 0 0 0 2 40 0 2 20 0 2 0 50 0 100 0 150 0 0 0 0 x x x x x x x x x                                                     Vô nghiệm 30 2) Trường hợp 2: 1 2 3 1 2 3 1 1 2 3 2 2 3 3 3 1 1 2 1 2 3 1 2 3 0 0 150 0 2 40 0 2 20 0 2 0 50 0 100 0 150 0 0 0 0 g x x x x x x x x x x x x                                                         Vô nghiệm 31 3) Trường hợp 3: 1 2 1 2 3 1 1 2 3 2 2 3 3 3 1 1 2 1 2 3 1 2 3 0 100 0 0 2 40 0 2 20 0 2 0 50 0 100 0 150 0 0 0 0 g x x x x x x x x x x x                                                        Vô nghiệm 32 4) Trường hợp 4: 1 2 1 2 3 1 2 3 1 1 2 3 2 2 3 3 3 1 1 2 1 2 3 1 2 3 0 100 0 150 0 2 40 0 2 20 0 2 0 50 0 100 0 150 0 0 0 0 g x x g x x x x x x x x x x x x                                                            Vô nghiệm 33 5) Trường hợp 5: 1 1 2 3 1 1 2 3 2 2 3 3 3 1 1 2 1 2 3 1 2 3 50 0 0 0 2 40 0 2 20 0 2 0 50 0 100 0 150 0 0 0 0 g x x x x x x x x x x                                                       Vô nghiệm 34 6) Trường hợp 6: 1 1 2 3 1 2 3 1 1 2 3 2 2 3 3 3 1 1 2 1 2 3 1 2 3 50 0 0 150 0 2 40 0 2 20 0 2 0 50 0 100 0 150 0 0 0 0 g x g x x x x x x x x x x x x                                                           Vô nghiệm 35 7) Trường hợp 7: 1 1 2 1 2 3 1 1 2 3 2 2 3 3 3 1 1 2 1 2 3 1 2 3 50 0 100 0 0 2 40 0 2 20 0 2 0 50 0 100 0 150 0 0 0 0 g x g x x x x x x x x x x x                                                          Vô nghiệm 36 8) Trường hợp 8: 1 1 2 1 2 3 1 2 3 1 1 2 3 2 2 3 3 3 1 1 1 2 2 1 2 3 1 2 3 1 2 3 3 50 0 100 0 150 0 2 40 0 2 20 0 2 0 50 0 10 50 50 5 0 0 15 0 0 20 0 0 0 0 20 100 g x g x x g x x x x x x x x x x x x x x x                                                                                     Đâ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