Bài giảng Tối ưu hóa trong thiết kế cơ khí: Chương 7 - ĐH Công nghiệp TP.HCM

Chia sẻ: Minh Vũ | Ngày: | Loại File: PDF | Số trang:37

Thêm vào BST

Báo xấu

63
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Tối ưu hóa trong thiết kế cơ khí - Chương 7: Phương pháp đồ thị để giải bài toán tối ưu hóa có 2 tham biến" cung cấp cho người học các kiến thức: Phương pháp đồ thị, tìm giá trik k đẻ hai đường cong tiếp xúc nhau,... Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Tối ưu hóa trong thiết kế cơ khí: Chương 7 - ĐH Công nghiệp TP.HCM

Trường Đại học Công nghiệp thành phố Hồ Chí Minh Khoa Công nghệ Cơ khí CHƯƠNG 07: PHƯƠNG PHÁP ĐỒ THỊ ĐỂ GIẢI BÀI TOÁN TỐI ƯU HÓA CÓ 2 THAM BIẾN Thời lượng: 3 tiết
2 Đặt vấn đề Trong rất nhiều bài toán thiết kế, kỹ thuật phức tạp, số lượng các hàm ràng buộc (bất đẳng thức) là rất lớn, tuy nhiên hàm mục tiêu và các ràng buộc chỉ có 2 tham biến. Với những bài toán này, nhiều khi áp dụng phương pháp đồ thị sẽ đem lại hiệu quả tốt, đồng thời đưa ra một lời giải trực quan và dễ hiểu. Hơn nữa, trong 1 số trường hợp khi lời giải cần tìm phải là số nguyên, thì phương pháp đồ thị trong trường hợp này lại giúp tìm ra kết quả dễ dàng mà không cần sử dụng những kỹ thuật phức tạp khác. 3 bước Cơ bản của phương pháp này là: - Vẽ đồ thị các hàm ràng buộc - Xác định miền lời giải hợp lệ (vùng diện tích được giới hạn bởi các đường cong ràng buộc) - Vẽ các đường cong đồng mức của hàm mục tiêu để xác định cực trị ở trong miền hợp lệ Chú ý: Đi theo hướng của Gradient đến điểm cực trị nhưng phải trong khuôn khổ miền hợp lệ
3 Phương pháp đồ thị Cực đại hóa hàm số sau: f  x1 , x2   400 x1  600 x2  max x1 x2 x1 x2 Với các ràng buộc: x1  x2  16;   1;   1; x1  0; x2  0 28 14 14 24 Bước 1: Kẻ hệ trục tọa độ x1x2 Nhìn vào các ràng buộc để dự đoán một cách tương đối về khoảng giá trị của các tham biến. Ví dụ ở đây ta có thể lấy [0;25]. Trong nhiều trường hợp khoảng giá trị trên các trục chỉ có thể xác định sau khi vẽ các đồ thị. Bước 2: Vẽ các đường ràng buộc bất đẳng thức Xét ràng buộc đầu tiên, ta bỏ dấu bất đẳng thức ≤ để vẽ đồ thị đường: x1  x2  16  0
4 Bước 3: Phân định miền bất đằng thức: Dựa vào tọa độ của 1 điểm thuận tiện không nằm trên đường cong ràng buộc thuộc 1 trong 2 miền. Từ đó xác định được dấu của 2 miền 2 phía đường cong. Không hợp lệ Hợp lệ
5 Bước 4: Vẽ các đường cong ràng buộc còn lại và xác định miền hợp lệ: Làm tương tự bước 3 cho các đường cong ràng buộc còn lại  g 4  x1  0 G x1 x2  g3   1 14 24 F  g1  x1  x2  16 E D x1 x2 Miền  g2   1 28 14 ABCDE C hợp lệ A  g5  x2  0 B J H
6 Bước 5: Vẽ các đường đồng mức của hàm mục tiêu x1 x2  g3   1 Tính Gradient của hàm số để biết 14 24 hướng độ dốc khiến hàm số tăng. Trên hình các mũi tên đều song song với véc tơ , chúng sẽ vuông góc với các E đường đồng mức của hàm f. Ta D  g1  x1  x2  16 vẽ hàng loạt đường thẳng song song nhau và vuông góc với véc tơ Gradient vì đường đồng mức x1 x2  g 2    1 của f là các đường thẳng (hàm f C 28 14 bậc 1 với 2 biến). Để hàm f đạt giá trị ngày càng A lớn thì đường đồng mức cần đi theo hướng mũi tên của B Gradient, nhưng cần phải có một  400   2  đường đồng mức xa nhất mà vẫn f  x       “chạm” vào miền hợp lệ. Trên  600   3  hình ta thấy là điểm D.
7 Bước 6: Tìm tọa độ điểm D là điểm mà ta nhận thấy hàm f đạt cực đại mà vẫn thỏa mãn miền hợp lệ. Dễ dàng nhận thấy D là giao điểm của 2 đường cong ràng buộc g1 và g2. Tọa độ giao điểm này chính là nghiệm của hệ phương trình:  x1  x2  16     1 4  2   400  4  600 12  8800 x    x1 x2     f x , x  28  14  1  x2  12 1 Kết luận: Cực đại của hàm f = 8800 với x1*=4, x2*=12
8 Phương pháp đồ thị Khi hàm ràng buộc song song với hàm mục tiêu, chúng ta sẽ có tình huống nhiều lời giải. Cực tiểu hóa hàm số sau: f  x1 , x2    x1  0.5 x2  min Với các ràng buộc: 2 x1  3 x2  12; 2 x1  x2  8;  x1  0;  x2  0 Do hàm mục tiêu f song song với ràng buộc g2=2x1+x2-8 nên ta thấy lời giải có thể là cả đoạn thằng BC do đường đồng mức của hàm f sẽ trùng với đoạn BC giúp f đạt giá trị nhỏ nhất có thể khi xét tới các ràng buộc.
9 Phương pháp đồ thị Khi ta bỏ sót các ràng buộc hoặc phát biểu sai bài toán tối ưu Cực tiểu hóa hàm số sau: f  x1 , x2    x1  2 x2  min Với các ràng buộc: 2 x1  x2  0;  2 x1  3 x2  6;  x1  0;  x2  0 Do miền hợp lệ mở rộng đến vô cùng bên phải, nên không có lời giải tối ưu hữu hạn. Cần xem lại phát biểu bài toán tối ưu.
10 Phương pháp đồ thị Khi các ràng buộc mâu thuẫn nhau khiến cho miền lời giải rỗng Cực tiểu hóa hàm số sau: f  x1 , x2   x1  2 x2  min Với các ràng buộc: 3 x1  2 x2  6; 2 x1  3 x2  12; x1 , x2   0;5 Miền hợp lệ phải là giao của 2 miền OAG và HDEF. Và 2 miền này hoàn toàn không có 1 khoảng chung nên giao của nó là 1 tập rỗng. Như vậy bản thân các ràng buộc đã mâu thuẫn nhau nên không tồn tại vùng H tìm kiếm hợp lệ. Bài toán vô nghiệm  Xem lại đề bài
11 Phương pháp đồ thị Cực tiểu hóa hàm số sau: f  x1 , x2   2.4608 105 x1 x2  min Với các ràng buộc: 107  248 10  0;10  6 7  3   207  10 9  x 3 1 x2  0; x1  0; x2  0 2 x1 x2 455 Miền hợp lệ là miền màu vàng. Hàm mục tiêu có xu hướng tăng giá trị theo hướng chỉ của véctơ Gradient. Chính vì vậy điểm A là điểm mà đường đồng mức của hàm f có thể đạt được giá trị nhỏ nhất. Vậy ta cần tìm tọa độ của A, nó là giao của 2 đường cong g1, g2. 107 g1   248  106 2 x1 x2 x1  0.1558137545 A  3   207 109  x13 x2 x2  0.0411872369 g 2  10  7 455 f   1579.227756
12 Phương pháp đồ thị Cực tiểu hóa hàm số sau: f  x1 , x2    x1  1.5    x2  1.5   min 2 2 Với các ràng buộc: x1  x2  2; x1  0; x2  0 Miền hợp lệ là tam giác OBC. Các vòng tròn là đường đồng mức của hàm mục tiêu f. Các véctơ Gradient túa ra từ điểm tâm (1.5;1.5) có nghĩa là giá trị của hàm f sẽ tăng theo chiều C của các mũi tên Gradient đó. Như vậy ta thấy giá trị nhỏ nhất (gần tâm nhất) có thể mà vẫn A thuộc miền hợp lệ chính là tiếp Miền hợp lệ điểm A của đường đồng mức B mầu đỏ với cạnh BC. Cũng như điểm xa tâm nhất thuộc miền hợp lệ chính là gốc tọa độ O, đó cũng chính là tọa độ giá trị lớn nhất của hàm f (vòng tròn xanh)
13 Cách 1: Tìm k để 2 đường cong f  x1 , x2 , k   0 và g  x1 , x2 , k   0 tiếp xúc với nhau tại 1 điểm và tìm tọa độ giao điểm đó Ý tưởng nằm ở chỗ: Tìm k để sao cho hệ phương trình sau có nghiệm duy nhất: f  x1 , x2 , k   0 1 g  x1 , x2 , k   0  2 Đưa hệ phương trình về phương trình đại số rồi đặt điều kiện để nó chỉ có 1 nghiệm duy nhất. Ví dụ nếu là phương trình bậc 2 thì Δ=0, thì đó có thêm 1 phương trình (3), kết hợp với (1) và (2) ta sẽ có hệ 3 phương trình với 3 ẩn là x1, x2, k.
14 Cách 2: Tìm k để 2 đường cong f  x1 , x2 , k   0 và g  x1 , x2 , k   0 tiếp xúc với nhau tại 1 điểm và tìm tọa độ giao điểm đó 1) Trước hết ta có 2 phương trình sau: f  x1 , x2 , k   0 1 g  x1 , x2 , k   0  2 2) Tính đạo hàm riêng theo 1 trong 2 biến x1 (hoặc x2) của 2 phương trình đường cong, ví dụ theo biến x1:  df dx2  dx  x1 , x2 , k   0  dx  h  x1 , x2 , k   1 1   dg  x , x , k   0  dx2  l  x , x , k   dx1 1 2 dx1 1 2  h  x1 , x2 , k   l  x1 , x2 , k   3 3) Giải hệ phương trình (1),(2),(3) để tìm x1, x2, k
15 dg  x2  dg  x2  dx2 dx2 1    g   x2   dx1 dx2 dx1 dx1 d df  x1  dg  x2  2  f  x1   g  x2     dx1 dx1 dx1 d dx2   f  x1   g  x2    f  x1   g  x2     dx1 dx1 d df  x1  dg  x2  3  f  x1  g  x2     g  x2   f  x1   dx1 dx1 dx1 d dx2   f  x1  g  x2    f   x1   g  x2   f  x1   g   x2   dx1 dx1 d m 1 dx2 4  x1 x2   n  x1  x2  x1  m  x2  n m n 1 m n dx1 dx1
16 Cách 3: Tìm k để 2 đường cong f  x1 , x2 , k   0 và g  x1 , x2 , k   0 tiếp xúc với nhau tại 1 điểm và tìm tọa độ giao điểm đó Ý tưởng nằm ở chỗ: Khi 2 đường cong f và g tiếp xúc với nhau tại 1 điểm (a,b) thì 2 véctơ pháp tuyến (Gradient) của 2 đường cong này sẽ song song (hoặc trùng) nhau. Do đó ta có hệ phương trình sau:   f x , x ,k  0 1  1 2  g  x1 , x2 , k   0  2  f  x  / / g  x   f x1  f x2  3  g x1 g x2 Giải hệ phương trình (1),(2),(3) để tìm x1, x2, k
17 Phương pháp đồ thị Tìm tọa độ điểm cực tiểu A: Tìm k để đường đồng mức (x1- 1.5)2+(x2-1.5)2=k tiếp xúc với đường thẳng x1+x2-2=0, tức là hệ có 1 nghiệm duy nhất. Cách 1:  x1  1.5 2   x2  1.5 2  k 2  8 x2   5  2k   0 Có 1 nghiệm   4 x 2 duy nhất  x1  x2  2  0 1  x1  1    4  2k  1  0  k    2  x2  1  x1  1 1    f min   x2  1 2 Tìm tọa độ điểm cực đại O là (0;0). Khi đó fmax=4.5
Cách 2: 1) Trước hết ta có 2 phương trình sau: 18 f  x1 , x2 , k    x1  1.5    x2  1.5   k 1 2 2 g  x1 , x2 , k   x1  x2  2  0  2 2) Tính đạo hàm riêng theo biến x1 của 2 phương trình đường cong:  df dx2 dx2 dx2 3  2 x1  dx  2 x1  3  2 x2 dx  3 dx  0  dx  2 x  3  1 1 1 1 2   dg  1  dx2  0  dx2  1  dx1 dx1 dx1 3  2 x1   1  3 2 x2  3 3) Giải hệ phương trình (1),(2),(3) để tìm x1, x2, k  x1  1   x2  1 k  0.5 
19 Phương pháp đồ thị Cực trị hóa hàm số sau: f  x1 , x2   x12  x22  3x1 x2  min& max Với ràng buộc: x12  x22  6  0 Chiều hàm f tăng - Điểm A, B là 2 điểm giá trị nhỏ nhất có thể - Điểm C, D là 2 điểm giá trị C A lớn nhất có thể - O là điểm yên ngựa B D Phải đi tìm được tọa độ những điểm này Chiều hàm f tăng
20 Phương pháp đồ thị Tìm tọa độ điểm A, B, C, D bằng cách Tìm k để đường đồng mức (x1)2+(x2)2-3x1x2=k tiếp xúc với đường cong (x1)2+(x2)2-6=0, tức là hệ có 1 nghiệm duy nhất. Cách 1:  x1  x2  3x1 x2  k 1 2 2 k  2 Có 1 nghiệm duy nhất  x1 x2  2   3  x1  x2  6  0 2  2 3  2k  2   2   3   x1  x1   10  3  0  k  15 2   2   2   3   x  x 2  2  2k  0  k  3  1 1 3  2k  2k  x1  x1   10   x1  x1   2   3 & 3 Có 1 nghiệm  x x  2  k x x  2  k duy nhất  1 2 3  1 2 3