Bài giảng Tối ưu hóa trong thiết kế cơ khí - Chương 2: Tối ưu hàm một biến số

Trường Đại học Công nghiệp thành phố Hồ Chí Minh Khoa Công nghệ Cơ khí CHƯƠNG 02: TỐI ƯU HÀM MỘT BIẾN SỐ Thời lượng: 3 tiết 2 Cực trị địa phương (tương đối) và toàn cục 3 Điều kiện cần của cực trị địa phương Nếu hàm số f(x) được xác định trên đoạn [a,b] và có cực trị địa phương tại x=x* (a<x*<b) và nếu đạo hàm f’(x) tồn tại dưới dạng một số hữu hạn tại x=x* thì f’(x*) = 0 Đạo hàm f’(x*) không tồn tại khi mà:         0 0 lim lim h h f x h f x f x h f x m m h h                 Độ dốc m- Độ dốc m+ Tại điểm đầu (x=a) và cuối đoạn (x=b) giới hạn trên chỉ tồn tại với h<0 hoặc h>0, nên đạo hàm là không xác định tại các điểm đầu và cuối đoạn. 4 Điều kiện đủ của cực trị địa phương            1 0n nf x f x f x f x         n là số chẵn n là số lẻ Điểm uốn (Inflection Point)     0nf x      0nf x  Cực tiểu Cực đại Điểm dừng 5 Điểm dừng (Stationary point) Điểm dừng, f’(x)=0 6 Bài tập ví dụ 1 Cho hàm đa thức 1 biến số. Yêu cầu: 1. Tìm tọa độ các điểm dừng (Stationary point). 2. Xác định trong số các điểm dừng, đâu là cực tiểu, đâu là cực đại và đâu là điểm uốn 3. Vẽ đồ thị hàm số 1) Tính Đạo hàm f’(x), giải phương trình f’(x) = 0 để tìm các điểm dừng:       4 3 2 2 2 260 180 120 60 3 2 60 1 2f x x x x x x x x x x            1 2 3 0 0 1 2 x f x x x             2) Tính Đạo hàm bậc hai f”(x), xét giá trị và dấu của f”(x*) của các điểm dừng vừa tìm được 7           4 3 2 3 2 2 60 3 2 60 4 9 4 60 4 9 4 f x x x x f x x x x x x x                 2 2 2 1 1 60 1 4 1 9 1 4 60 0 x f x                 2 là số chẵn và f”(x2*)<0 x2* là cực đại địa phương  2 12f x       3 2 3 2 2 60 2 4 2 9 2 4 240 0 x f x                2 là số chẵn và f”(x3*)>0  x3* là cực tiểu địa phương  3 11f x        1 2 1 0 3 60 0 4 0 9 0 4 0 x f x               Do f”(x1*)=0  Phải tính tiếp f”’(x)           3 2 2 2 60 4 9 4 60 12 18 4 120 6 9 2 f x x x x f x x x x x                 1 2 1 0 4 120 6 0 9 0 2 240 0 x f x              3 là số lẻ và f”’(x1*)≠0  x1* là điểm yên  1 5f x  8 https://rechneronline.de/function-graphs/ Vẽ đồ thị hàm số 9 Các phương pháp số để tìm cực trị hàm 1 biến Các phương pháp dựa trên độ dốc. Tức là dựa trên việc giải phương trình f’(x)=0 Việc tính đạo hàm f’(x) cũng được tính bằng phương pháp số gần đúng 10 NHƯ VẬY 11 THỐNG NHẤT VỀ CÁCH TÍNH GẦN ĐÚNG ĐẠO HÀM BẬC 1 VÀ 2               2 0.001 0.001 ; 0.002 0.002 2 0.002 0.002 f x f x f x f x f x f x f x            Thống nhất công thức tính gần đúng đạo hàm bậc 1 và bậc 2 trong các phương pháp như sau khi giải các bài tập trên lớp cũng như bài tập về nhà: 12 Phương pháp chia đôi đoạn (Bisection)  f x Vùng tìm kiếm 1 Vùng tìm kiếm 2 Vùng tìm kiếm 3 Vùng tìm kiếm 4 Vùng tìm kiếm 5 13 Phương pháp chia đôi đoạn (Bisection) 14 Bài tập ví dụ 2 Tìm điểm cực trị của hàm số f(x) trong khoảng [a, b] bằng pp chia đôi đoạn với 5 vòng lặp      0.2 0.85 1.25 2 ; , 3,4x xf x e e x a b                      , 2 1 3,4 0.2686 0.18478 3.5 0.047057348 3.144776 1 2 3.5,4 0.047057348 0.18478 3.75 0.067212957 3.147233919 0.5 3 3.5,3.75 0.047057348 0.067212957 3.625 0.009707888 3.142434525 0.25 4 3.5,3.625 0.04 a b SVL a b f a f b m f m f m b a               7057348 0.009707888 3.5625 0.018761715 3.142718393 0.125 3.5625,3.6255 0.018761715 0.009707888 3.59375 0.004549358 3.142354042 0.0625 6 0.004549358 0.009707888 3.609375 0.002573567 3.142338591 0.031253.59375,3.625                                  0.001 0.001 0.002 f x f x f x      15 Sử dụng trang web online vẽ đồ thị https://rechneronline.de/function-graphs/ 1 2 3 4 16 Sử dụng trang web online vẽ đồ thị 1 2 17 1 2 3 4 5 18 19 Vì do khoảng x như nhau, còn khoảng y khác nhau, nên giá trị biên bên trái của y ta lấy giá trị nhỏ nhất của 2 đồ thị, giá trị biên bên phải của y ta lấy giá trị lớn nhất của 2 đồ thị 20 0.047 0.2686 0.18478 0.067213 0.0097 0.01876 Đồ thị minh họa các vòng lặp 21 Phương pháp Newton–Raphson  y f x    1 i i i i f x x x f x      Xuất phát từ 1 điểm x0 đầu tiên, kẻ đường thẳng đứng cắt với đường cong y tại 1 điểm. Dựng tiếp tuyến với y tại điểm đó. Đường tiếp tuyến sẽ cắt trục hoành tại điểm x1. Với điểm x1 ta lại làm như ở bước x0 lúc đầu. Cứ như vậy đến khi nào cách biệt giữa xi+1 và xi nhỏ hơn một sai số cho phép. 22 Phương pháp Newton–Raphson 23 Bài tập ví dụ 3 Tìm điểm cực trị của hàm số f(x) bằng pp Newton Raphson với x0:       0.2 0.8 05 1.25 2 ; 15; , 5,15 x xf x e e x x a b                    2 0.001 0.001 ; 0.002 0.002 2 0.002 0.002 f x f x f x f x f x f x f x                 1 1 15 18.08553 4.01711 10.49787 70.42769 4.50212 10.49787 6.16248 1.63272 6.72352 19.81805 3.77436 6.72352 1.83243 0.7711 4.34713 5.74397 2.37639 4.34713 0 1 . 2 35466 0.50181 3.64036 3. 3 27204 0.74 0 i i i i i i iSVL x f x f x x f x x x         676 3.64036 0.01673 0.45769 3.6038 3.14264 0.03656 3.6038 3.1758E-5 0.45597 3.60373 3.14233 6.96493E- 5 6 5                            1 i i i i f x x x f x      24 1x2x 18.08553 6.16248 3x 1.83243 4x 0.35466 Đồ thị minh họa các vòng lặp 25 Các trường hợp pp Newton–Raphson khó hội tụ  f x  f x  f x   f x 26 Phương pháp cát tuyến (Secant Method) a 0x b  y f x f a  f c  f b x1 x c 2x x 0x a b 1x c 2x  f a  f c  f b  y f x Nếu     0 1 0 x b f a f c x c        Nếu     0 1 0 x a f a f c x c                        0 0 1 0 0 1 k k k f b b a c b f b f a f x x x x x f x f x                   Công thức: 27 Bài tập ví dụ 4 Tìm điểm cực trị của hàm số f(x) bằng pp Secant với [a,b]:      0.2 0.85 1.25 2 ; , 2,6x xf x e e x a b           0 0 1 0.71007 1.31189 3.40472 0.089882 6 6 1.31189 3.40472 a b f a f b c f c x f x x          1) Bước 1: Xác định điểm x0 2) Bước 2: Các vòng lặp     1 1.31189 4.61087 3.40472 0.08988 3.1513 2.59528 3.57113 0.01484 3.14257 0.16641 3.5983 0.00248 3.14234 0.02717 3.60283 0.00041 3.14233 0.00452 3.60358 6.91421E-05 3.14233 0.0007 0 6 6 1 2 3 4 55 k k k k kk x f x f x x x                                            0 0 1 0 0 1 k k k f b b a c b f b f a f x x x x x f x f x                   28 Đồ thị minh họa các vòng lặp 0x 1x c 2x 1.31189 0.08988 29 Hàm số đơn phương thức (Unimodal function) a bx a x  b a b x  Cho hàm số f xác định trên khoảng [a,b]. Giả sử rằng trong khoảng giá trị này tồn tại một điểm cực tiểu địa phương duy nhất x*, mà tại đó hàm f nghịch biến khi x≤x* và đồng biến khi x≥x*. Hàm số f như vậy gọi là hàm đơn phương thức chặt chẽ. Có 3 trường hợp vị trí của x* trong khoảng [a,b]: - x* nằm giữa [a,b] - x* trùng với a - x* trùng với b (a) (b) (c) 30 a x b1x 2x 3x x Ta thấy hàm số f ở trên không liên tục tại các điểm x1, x2, x3 (3 điểm gián đoạn của hàm) nhưng hàm vẫn là đơn phương thức chặt chẽ và có 1 điểm cực tiểu địa phương duy nhất x* 31 a 1x  b 2x  x Cho hàm số f xác định trên khoảng [a,b]. Giả sử rằng trong khoảng giá trị này tồn tại một điểm cực tiểu địa phương duy nhất x*, mà tại đó hàm f nghịch biến khi x≤x1* , không đổi trong khoảng [x1*, x2*] và đồng biến khi x≥x2*. Hàm số f như vậy gọi là hàm đơn phương thức không chặt chẽ, hay hàm đơn phương thức nói chung. 32 Hàm số đơn phương thức (Unimodal function) Nếu với mọi x thuộc [a,b] thoãn mãn điều kiện f’’(x) > 0 thì hàm số f(x) đơn phương thức trong khoảng [a,b] Ví dụ: xét hàm số sau trên các khoảng [-4,-3] và [0,1]           3 23 1 6 0 4; 3 0;1 x x x f x x x e f x x e f x x e x                     4; 3   0;1 33 a x b x   Mệnh đề 1.1: Giả sử hàm f(x) đơn phương thức trong khoảng [a,b] và ta có a≤α<γ<β≤b, thì: Nếu f(α)≤ f(β) thì x* thuộc [a,β] a x b x   Mệnh đề 1.2: Nếu f(α)≥ f(β) thì x* thuộc [α,b] a x b x   Mệnh đề 1.3: Nếu f(α)≥f(γ) và f(β)≥f(γ) thì x* thuộc [α,β] 34 Các phương pháp trực tiếp Một loạt các phương pháp dựa trên việc so sánh giá trị của hàm số f tại các điểm x1, x2, , xN. Những phương pháp này thường được gọi là các phương pháp tìm trực tiếp. Còn các điểm xi là các điểm thử. Tìm tìm điểm x+ xấp xỉ với điểm cực tiểu x* của hàm đơn phương thức trên đoạn [a,b]. Giả sử rằng số lượng điểm thử N cho trước và x+ là một trong số những điểm thử đó. 35 x a bkx1kx  1kx 1x 2x Nx1Nx  Tìm điểm x+ xấp xỉ với điểm cực tiểu x* của hàm đơn phương thức trên đoạn [a,b]. Giả sử ta chia đều đoạn thành N+1 đoạn, suy ra số lượng điểm thử là N và xk là một trong số những điểm thử đó, thỏa mãn điều kiện f(xk)=minf(xi); i=1..N Phương pháp tìm kiếm bị động (EXHAUSTIVE SEARCH) Như vậy, phương pháp tìm kiếm bị động là 1 trong số các phương pháp trực tiếp, trong đó các điểm thử được xây dựng bằng cách chia đều đoạn khảo sát. 36 Tìm điểm cực trị của hàm số f(x) trong khoảng [0;1]:   3 xf x x x e   37 Phương pháp tìm kiếm tuần tự Giả sử để giải bài toán tối ưu hóa đã cho ta lần lượt tính giá trị của hàm f tại N điểm x1, x2, , xN. Trong đó việc xác định giá trị xk ta có thể sử dụng thông tin về giá trị hàm số trong tất cả các điểm trước đó là x1, x2, , xk-1 Phương pháp tìm kiếm tuần tự (sequential search methods) 38 Nếu hàm số f đơn phương thức trong khoảng [a;b] thì nó sẽ đơn phương thức trong bất kz khoảng [c;d] nào nằm trong [a;b] x a bc d 39 Phương pháp chia đôi đoạn x  0 a  0b   0 0 2 a b      0 0 0 2 a b           0 0 0 2 a b      Nếu:    0 0 f f         thì            1 1 0 0 1 0 ; ;x a b a x             Nếu:    0 0 f f         thì            1 1 0 0 1 0 ; ;x a b b x                  1 1 1 b a   40 1) Bước 1: Cho sai số dừng vòng lặp là ε 2) Bước 2: Chọn độ rộng khoảng chia đôi δ (≤ε/2) 3) Bước 3: Tính                   ; ; 2 2 k k k k k k k k ka b a b b a             4) Bước 4: Tính    k kf f        và Nếu:    k k f f         thì                   1 1 1 1 1 1 ; ; ; k k k k k k k k k a a b x b a               Nếu:    k k f f         thì                   1 1 1 1 1 1 ; ; ; k k k k k k k k k a b b x b a               5) Bước 5: Nếu  1k   thì dừng, còn không thì tiếp tục Phương pháp chia đôi đoạn 41 Tìm điểm cực trị của hàm số f(x) trong khoảng [0;1]:   3 xf x x x e   ε=0.01; δ=0.001 42 Phương pháp Fibonacci Số Fibonacci: 1 2n n nF F F   n≥2 Ví dụ 20 số đầu tiên của dãy Fibonacci: Phương pháp chia đôi đoạn đòi hỏi trong mỗi bước lặp k phải tính 2 giá trị mới của hàm số bởi vì các giá trị mà tìm được ở bước lặp trước tại các điểm α(k-1) và β(k-1) sẽ không được sử dụng tiếp tục nữa. Tuy nhiên, một trong số 2 điểm này lại là nghiệm x(k+1) và nó lại nằm giữa đoạn [a(k);b(k)]. Như vậy, từ nay sự rút gọn đoạn [a(k);b(k)] có thể được thực hiện bằng cách tính thêm giá trị hàm số tại một điểm mới. Phát hiện này sẽ đưa ta đến các phương pháp mới, đòi hỏi trong mỗi bước lặp (ngoại trừ bước đầu tiên) chỉ cần tính một giá trị mới của hàm số f. Và một trong số đó là phương pháp Fibonacci. 43 Phương pháp Fibonacci 1) Bước 1: Cho sai số dừng vòng lặp là ε 2) Bước 2: Tính số bước lặp N dựa vào điều kiện FN+1 > (b0-a0)/ε 3) Bước 3: Tính                  1 1 1 ; ; k k k k k k k k kN k N k N k N k F F b a a a F F                  4) Bước 4: Tính    k kf f        và Nếu:    k k f f         thì                 1 1 1 1 ; ; ; k k k k k k k k a a b x             Nếu:    k k f f         thì                 1 1 1 1 ; ; ; k k k k k k k k a b b x             k=0..(N-2) 44 Tìm điểm cực trị của hàm số f(x) trong khoảng [0;1]:   3 xf x x x e   ε=0.01  N=11 Có N-1 = 10 bước lặp 45 Phương pháp mặt cắt vàng 1 1.6180 4 5 2 3 a b a a b          46 a b  1 5 1 5 ; 2 2 b a b b a a b a a b                         2 3 5 2 1 5 a b a a b a           47 1) Bước 1: Cho sai số dừng vòng lặp là ε 2) Bước 2: Tính 3) Bước 3: Tính    k kf f        và Nếu:    k k f f         thì                 1 1 1 1 ; ; ; k k k k k k k k a a b x             Nếu:    k k f f         thì                 1 1 1 1 ; ; ; k k k k k k k k a b b x             Phương pháp mặt cắt vàng                  2 2 ; ; 3 5 1 5 k k k k k k k k k b a a a            48 Tìm điểm cực trị của hàm số f(x) trong khoảng [0;1]:   3 xf x x x e   ε=0.01