Bài giảng Tối ưu hóa trong thiết kế cơ khí - Chương 4: Tối ưu hàm nhiều biến số với ràng buộc đẳ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 04: TỐI ƯU HÀM NHIỀU BIẾN SỐ VỚI RÀNG BUỘC ĐẲ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 đẳng thức Tìm cực tiểu (Minimum) của hàm nhiều biến sau: Với các điều kiện ràng buộc đẳng thức:   0 1,2, , jg j m   x Với:  1 2 T nx x xx Điều kiện: m ≤ n  Nếu m > n bài toán sẽ không có lời giải. Có 3 phương pháp giải: 1. Phương pháp thế trực tiếp (direct substitution) 2. Phương pháp biến đổi ràng buộc (constrained variation) 3. Phương pháp nhân tử Lagrange (Lagrange multipliers)  f x 3 Phương pháp thế trực tiếp Từ m ràng buộc đẳng thức, ta biến đổi và thu được các biểu thức tính m biến số thông qua (n-m) biến số còn lại (trong số n biến số tất cả). Từ đó thế vào biểu thức hàm f ban đầu. Như vậy hàm f sẽ trở thành hàm có (n-m) biến số nhưng không còn ràng buộc nào hết. Ta quay trở về bài toán tối ưu không ràng buộc.             1 1 1 2 2 2 1 2 2 1 2 1 , , , 0 , , , 1.. , , , , , m , in n m n m j n n m n m n m m m n x h x x x g x h x x x j m x h xf x x x f x x                       x x  1 2 1 2 T n m n m n m nx x x x x x    x (n-m) tham biến cơ sở m tham biến cần triệt tiêu trong f Từ: Hàm (n-m) biến số 4 Phương pháp thế trực tiếp Tối ưu hàm số sau:  1 2 3 1 2 3, , 8f x x x x x x Với ràng buộc: 2 2 21 2 3 1x x x   3 1 n m   Tìm biểu thức liên hệ của 1 tham biến vào 2 tham biến còn lại: 2 2 2 2 2 1 2 3 3 1 21 1x x x x x x       Thế vào hàm f ban đầu:     2 21 2 3 1 2 1 2 1 2, , , 8 1f x x x f x x x x x x    Tối ưu hàm 2 biến không ràng buộc Giải hệ phương trình Gradient = 0: 5       2 2 2 1 2 2 2 2 2 1 21 1 2 2 22 2 1 21 1 2 2 22 1 2 1 2 3 8 2 1 1 2 1 0 0 2 1 08 2 1 1 1 1 3 3 x x x f x xx x x f f x xx x x x x x x x x                                                  x Tính ma trận Hessian tại điểm dừng:                   2 2 4 2 2 4 2 2 1 2 1 2 1 1 2 2 1 22 2 3 3 2 2 2 22 22 1 2 1 21 1 2 2 2 4 2 2 4 2 2 2 2 1 1 2 2 1 2 1 2 1 2 2 3 3 2 1 2 2 2 2 22 2 1 2 1 2 8 2 3 3 8 2 3 2 3 3 1 1 1 8 2 3 2 3 3 1 8 2 3 3 1 1 x x x x x x x x x x f f x x x xx x x f f x x x x x x x x x x x x x x x x x                                                      H 1 2 32 16 32 03 3 3 16 32 256 0 3 3 A A                     Điểm dừng Điểm cực đại Vậy cực đại của hàm ban đầu là:   1 1 1 8 max 3 3 3 3 3 T f          * * x x 6 Phương pháp thế trực tiếp có vẻ đơn giản về mặt lý thuyết, nhưng trên thực tế lại có những hạn chế khi sử dụng. Đó chính là những biểu thức hàm ràng buộc gi(x) thường là các hàm phi tuyến phức tạp nên khó có thể rút ra được biểu thức biểu diễn tham biến qua các tham biến khác từ những hàm phức tạp này. Chính vì vậy, chúng chỉ có thể áp dụng ở một số trường hợp hàm gi(x) đơn giản. Phương pháp thế trực tiếp 7 Vi phân bậc r của hàm f Nếu tất cả các đạo hàm riêng của hàm f với bậc r ≥ 1 tồn tại và liên tục tại điểm x*, thì đa thức sau đây được gọi là vi phân bậc r của hàm f tại điểm x*:   1 2, , , , nf x x xx x     1 2 1 2 1 2 1 1 1 r r r r n n n r i i i i i i i i i f d f dx dx dx x x x               * * x x Trong đó: 1 2, , , ; ; 1.. ; 1.. k k k n i i i k x x x dx x x i n k r           x Có nr hạng tử 8 Vi phân bậc r của hàm f   1 2 1 2; , ; ,f x x x x    x x x       1 1 2 1 2 ; ; 1..2i i i f f d f dx dx x x dx x x i          * * * x x x n=2, r=1  Có 21 =2 hạng tử                 2 2 2 2 2 2 2 1 2 1 2 2 12 2 1 2 1 2 2 1 2 2 2 2 2 1 2 1 22 2 1 2 1 2 2 ; 1..2i i i f f f f d f dx dx dx dx dx dx x x x x x x f f f dx dx dx dx x x x x dx x x i                            * * * * * * * * x x x x x x x x n=2, r=2  Có 22 = 4 hạng tử 9 Vi phân bậc r của hàm f   1 2 3 1 2 3; , , ; , ,f x x x x x x     x x x         1 1 2 3 1 2 3 ; ; 1..3i i i f f f d f dx dx dx x x x dx x x i             * * * * x x x x n=3, r=1  Có 31 = 3 hạng tử                           2 2 2 2 2 2 2 2 2 1 2 3 1 2 2 12 2 2 1 2 3 1 2 2 1 2 2 2 2 1 3 3 1 2 3 3 2 1 3 3 1 2 3 3 2 2 2 2 2 2 2 1 2 32 2 2 1 2 3 2 f f f f f d f dx dx dx dx dx dx dx x x x x x x x f f f f dx dx dx dx dx dx dx dx x x x x x x x x f f f dx dx dx x x x                                             * * * * * * * * * * * * * x x x x x x x x x x x x x      2 2 2 1 2 2 3 3 1 1 2 2 3 3 1 2 2 ; 1..3i i i f f f dx dx dx dx dx dx x x x x x x dx x x i               * * * x x x n=3, r=2  Có 32 = 9 hạng tử 10 Dãy TAYLOR của hàm f(x) quanh điểm x*                         1 2 3 1 1 2 1 2 1 1 1 , 2! 3! ! 1 , 1 ! 0 1 N N N N T n T n f f f d f d f d f d f R N R d f N x x x x x x                                       * * * * * * * * * * * x x dx x x x x x x dx x dx x dx dx x x x x dx x x 11 Dãy TAYLOR của hàm f(x) quanh điểm x* Tìm biểu thức dãy Taylor xấp xỉ bậc 2 cho hàm f quanh điểm x*:      321 2 3 2 3 1, , ; 1 0 2 Tx f f x x x x x x e    *x x Ta có:        1 2 1 2! f f d f d f  * *x x x x                     3 3 2 1 1 2 3 1 2 3 2 1 2 3 2 2 1 3 2 2 1 2 3 1 2 2 1 3 1,0, 2 2 0 x x f f e f f f d f dx dx dx x x x e dx x x dx x x e dx e dx dx e dx d f e dx e dx                               ** * * * * * xx x * x x x x x x 12                           3 3 2 2 2 2 2 2 2 2 1 2 3 1 22 2 2 1 2 3 1 2 2 2 2 3 3 1 2 3 3 1 2 2 2 1 3 2 1 3 1 2 2 2 3 3 1 2 2 2 2 2 3 3 1 2 2 2 2 0 2 2 0 2 2 2 4 2 x x f f f f d f dx dx dx dx dx x x x x x f f dx dx dx dx x x x x dx x dx x e dx dx dx x dx dx e dx dx dx e dx e dx dx d                                       * ** * * * * * * * * x xx x x x x x x x x     2 2 2 22 3 3 14 2f dx e dx e dx dx    *x Vậy, biểu thức dãy Taylor xấp xỉ bậc 2 cho hàm f quanh điểm x* có dạng:        2 2 2 2 2 21 3 2 3 3 1 1 4 2 2 f f e e dx dx dx e dx e dx dx               * x x dx 13 Phương pháp biến đổi ràng buộc Ý tưởng chính của phương pháp này nằm ở chỗ đi tìm một biểu thức dạng đóng* cho vi phân bậc 1 của hàm số (tức là 1 biểu thức của df) tại tất cả các điểm mà ở đó các biểu thức ràng buộc gi(x)=0 được thỏa mãn. Khi đó thì các điểm cực trị cần tìm sẽ thu được bằng cách giải phương trình df=0. 14 Phương pháp biến đổi ràng buộc Tìm cực trị hàm số sau:  1 2,f x x Với 1 ràng buộc:  1 2, 0g x x  2 1 n m   Điều kiện cần để hàm f có cực trị tại điểm x* = (x1*, x2*) là vi phân bậc 1 của hàm f phải bằng 0 tại đó. Ta có biểu thức:  1 2 1 2 0 1 f f df dx dx x x           *x Do vì g(x1*, x2*)=0 tại điểm cực trị, nên mọi biến thể dx1, dx2 xung quanh điểm x* được gọi là các biến thể được chấp nhận (admissible variations) nếu những điểm có tọa độ (x1*+dx1, x2*+dx2) cũng nằm trên đường cong ràng buộc g(x1, x2)=0. 15  1 2: ,x x *x A là điểm cực trị của hàm f mà nằm trên đường cong g(x1, x2)=0. B và C là các điểm biến thể (gần với A) được chấp nhận vì chúng nằm trên đường cong g(x1, x2)=0. D là điểm biến thể (gần với A) không được chấp nhận vì nó không nằm trên đường cong g(x1, x2)=0. 16 Với các điểm biến thể được chấp nhận (B và C), ta sẽ có:  1 1 2 2, 0g x dx x dx    Ta lại sử dụng dãy Taylor bậc 1 cho hàm g:                 1 2 1 1 2 2 1 2 1 2 1 2 0 1 2 1 2 , , 0 0 0 2 x x dg g x dx x dx g x x g g g g dx dx x x g g dg dx dx x x                                 * * * * x x x x x x Giả sử    12 1 2 2 0 3 g g x dx dx gx x          * * x x 17 Thế (3) vào (1), ta thu được:  1 1 1 2 2 1 2 2 1 0 4 0 g xf f df dx gx x x f g f g x x x x                            * * x x Biến thể ràng buộc của hàm f Điều kiện cần để tồn tại cực trị của hàm f(x1,x2) với ràng buộc g(x1,x2) =0:   1 2 2 1 0 5 f g f g x x x x           18 Phương pháp biến đổi ràng buộc Tìm cực trị hàm số sau:  1 2 2 1 2 , k f x x x x  Với 1 ràng buộc:   2 2 21 2 1 2, 0g x x x x a    2 1 n m   Sử dụng phương trình (5):   2 2 1 1 2 12 2 2 1 2 12 2 3 1 2 1 2 3 2 2 1 2 1 1 2 32 5 2 2 0 2 2 2 3 2 f k x x x ag xx x k k x x x x f k x x x x a x x x x g x x                                         19 Phương pháp biến đổi ràng buộc Trong trường hợp tổng quát hàm có n biến số và m ràng buộc, phương pháp này rất phức tạp nên khó áp dụng khi giải các bài toán thực tế. Vì vậy phổ biến hơn cả sẽ là phương pháp nhân tử Lagrange 20 Phương pháp nhân tử Lagrange Tìm cực trị hàm số sau:  1 2,f x x Với 1 ràng buộc:  1 2, 0g x x  2 1 n m   Từ (4), ta có:    1 21 1 2 1 1 2 2 4 : 0 0 6 g f x xf f f g df dx g gx x x x x x                                  * *x x Đặt: 2 2 f x g x        *x Nhân tử Lagrange   2 2 0 7 f g x x           *x   1 1 0 8 f g x x           *x Kết hợp với phương trình:    1 2, 0 9g x x   21 Phương pháp nhân tử Lagrange Như vậy ta có hệ 3 phương trình để tìm x1*, x2* và λ       1 2 1 2 1 1 , 2 2 , 1 2 0 0 , 0 x x x x f g x x f g x x g x x                                 Nếu theo hệ phương trình này thì ít nhất 1 trong 2 đạo hàm riêng của g phải khác 0 tại điểm cực trị 1 2 0 0 g x g x         * * x x Vì vậy để thoát khỏi điều kiện trên, ta có phương pháp sử dụng hàm Lagrange 22 Phương pháp nhân tử Lagrange        1 2 1 2 1 2 1 2 0 , , , , ,L x x f x x g x x f x x       Cực trị hàm L cũng là cực trị hàm f Do hàm L có 3 biến nên điều kiện cần để có cực trị là:               1 2 1 2 1 11 1 2 1 2 1 2 2 22 1 2 , , 0 , , 0 ; 0 , T f x x g x xL x xx f x x g x xL L x x x xx L g x x                                                   x x 23 Phương pháp nhân tử Lagrange      1 2 0; 1.. extr : j T n g j m f x x x       x x x            1 2 1 2 1 1 2 2, , ,.., , , ,.., ...n m m mL L x x x f g g g          x λ x x x x Giải hê (n+m) phương trình sau:   1 0; 1.. 0; 1.. m j j ji i i j j gL f i n x x x L g j m                     x Tìm ra (n+m) nghiệm: 1 1 2 2; n m x x x                                        x λ 24 Phương pháp nhân tử Lagrange 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 – thì lời giải là cực đại, nếu tất cả nghiệm mang dấu + 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ị. Trong đó:       2 , , , 1.. 1.. ; 1.. ij i j k kl l L L x x i j n g g x k m l n              x λ x x λ x n m n n m m n m  Định thức này là 1 hàm đa thức bậc (n-m)có tối đa (n-m) nghiệm   25 Phương pháp nhân tử Lagrange Xác định kích thước của hình trụ kín để thể tích của nó lớn nhất có thể, trong khi tổng diện tích bề mặt của nó bằng 24π 1x 2x Xây dựng mô hình toán (Phát biểu mô hình toán)     2 1 2 1 2 2 2 1 1 2 1 2 1 1 2 1 2 , max 2 2 24 , 12 0, 0 V V x x x x A x x x g x x x x x x x                 Hàm số Lagrange:    2 21 2 1 2 1 1 2, , 12L x x x x x x x      2 1 n m    Điều kiện cần: Giải hệ 3 phương trình sau:     1 2 1 2 1 12 1 1 2x1 1x1 2 2 2 1 1 2 2 2 0 2 0 ; 2 4 12 0 L x x x x x xL x x x x L x x x                                             x λ 26 Phương pháp nhân tử Lagrange Điều kiện đủ: Xác định định thức 3x3 11 12 11 21 22 12 11 21 0 L z L g L L z g g g               2 11 22 , 1 2 12 21 1 , 1 2 2 22 2 2 11 1 2 1 12 21 1 2 2 2 8 4 4 2 4 2 2 0 2 8 2 L L x x L L L x x x L L x g g x x x g g g x x                                                  x λ x λ x Trong đó:  det 68 48 0 12 0 17 z z          Cực đại: max 16V  4 2 8 2 2 8 2 0 z z              