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

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

Thêm vào BST

Báo xấu

49
lượt xem 9
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 8: Quy hoạch tuyến tính" cung cấp cho người học các kiến thức: Đặt vấn đề, vấn đề 1 dẫn đến bài toán QHTT, các dạng của bài toán QHTT, phương pháp hình học,... 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 8 - Đ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 08: QUY HOẠCH TUYẾN TÍNH (Linear Programming) Thời lượng: 3 tiết
2 Đặt vấn đề 1. Quy hoạch tuyến tính (QHTT, 1930) là các bài toán tối ưu hóa mà ở đó hàm mục tiêu và toàn bộ các ràng buộc đều là hàm bậc 1 của các biến số. 2. Các biểu thức ràng buộc có thể ở dạng đẳng thức (phương trình) hoặc bất đẳng thức (bất phương trình) tuyến tính. 3. Các lĩnh vực ứng dụng của Quy hoạch tuyến tính: - Tối ưu hóa chế độ dinh dưỡng - Tối ưu hóa danh mục đầu tư - Bài toán sản xuất và vận chuyển - Bài toán viễn thông - Bài toán nhân viên bán dịch vụ du lịch - Trong kỹ thuật ngành cơ khí, thì QHTT giúp giải các bài toán thiết kế và sản xuất. Điển hình là các bài toán tối ưu hóa hình dạng (Shape Optimization), ví dụ như hình dáng khí động học của máy bay để giảm lực cản. Các ràng buộc có thể bao gồm hệ số nâng, độ dày tối đa tương đối, bán kính mũi, góc cạnh, v.v…
3 Vấn đề 1 dẫn đến bài toán QHTT Trong các kết cấu khung thép, cần tính toán để tránh xuất hiện các “khớp dẻo”, là những điểm mà kết cấu có thể mất đi độ cứng và bị bẻ gãy dẻo như một khớp xoay. Khi mà số lượng các khớp dẻo tăng thì kết cấu sẽ có nguy cơ trở thành cơ cấu bị sụp gãy (a collapse mechanism). Để khắc phục vấn đề này, người ta cần phải làm tăng MÔMEN KHÁNG DẺO. Mômen kháng dẻo của một mặt cắt: M d  Zd  c Zd – Môđun mặt cắt dẻo, σc – giới hạn chảy của vật liệu
Ví dụ mômen kháng dẻo của mặt cắt dầm hình chữ nhật với chiều 4 cao h, bề rộng b là:  bh  2 Md     c  4  Như vậy để tăng mô men kháng dẻo của mặt cắt thì hoặc là thay đổi vật liệu cứng hơn (làm tăng σc ), hoặc là tăng kích thước mặt cắt (b hoặc h hoặc cả 2). Nhưng điều này sẽ làm tăng khối lượng của kết cấu, tăng chi phí cho vật liệu. Chính vì vậy mà bài toán đặt ra là làm sao thiết kế được một kết cấu mà mômen kháng dẻo của nó đủ để giữ vững kết cấu không cho bị biến dạng dẻo, nhưng khối lượng của nó lại nhỏ nhất có thể. Kết cấu được cho là an toàn nếu khả năng hấp thụ năng lượng (thế năng đàn hồi U) của khung lớn hơn Công của ngoại lực (E) Thế năng biến dạng đàn hồi (U) sẽ được tính thông qua mômen kháng dẻo tại các điểm khớp dẻo.
5 Vấn đề 1 dẫn đến bài toán QHTT Cho khung phẳng cấu tạo từ 2 cột và 1 dầm ngang chịu tải như hình. Tìm giá trị mômen khớp dẻo của cột (Mc) và dầm (Mb) để kết cấu đủ an toàn với khối lượng nhỏ nhất. P1=3 kN, P2=1 kN, h=8 m, l=10 m.  Có 4 khả năng khung biến dẻo 1 2 E  P1    P1  h    24 E  P2    P2  l    10 U  4 M c Do có 4 khớp vị trí khớp dẻo của cột (Column) U  4 M b
3 4 6 E  P1  1  P2   2   Ph 1  P2l     34 E  P1    P1  h    24 U   2M c  4M b  U   2M c  2M b  Hàm mục tiêu của bài toán: Cực tiểu hóa khối lượng khung gồm khối lượng của 2 cột và dầm ngang: ρ – khối lượng riêng của khung theo f  M c , M b     2lM b  2hM c   min chiều dài và mômen kháng dẻo Các ràng buộc xuất phát từ điều kiện U ≥ E ở 4 trường hợp: Mc  6 M b  2.5 2 M b  M c  17 M b  M c  12
7 Gọi Mc=x1, Mb=x2, ta thu được mô hình toán: f  x   20 x1  16 x2  min Bài toán QHTT g1  2 x2  x1  17 Các hàm ràng buộc gi có hạng tử g 2   x1  x2  12 bậc 0 ở bên kia dấu bất đẳng thức. Khác với việc trước đây đưa về g3   x1  6 dạng gi ≤0. g 4   x2  2.5 Bài toán có 1 lời giải khi dùng phương pháp điều kiện KKT: 0 16   6  x*    ; λ *    ; f min  216 6  4   0
8 Vấn đề 2 dẫn đến bài toán QHTT Một xí nghiệp có thể sản xuất ra một loại sản phẩm theo 3 phương pháp khác nhau, k{ hiệu là PP1, PP2, PP3. Các loại nguyên liệu để sản xuất k{ hiệu là N1, N2, N3. Biết rằng số nguyên liệu hiện có, định mức tiêu hao các loại nguyên liệu và số lượng sản phẩm sản xuất ra trong một giờ theo các phương pháp cho ở bảng dưới: Nguyên Số lượng Định mức tiêu hao trong một giờ liệu hiện có (đv) PP1 PP2 PP3 N1 250 4 5 3 N2 350 2 4 1 N3 450 3 6 4 Sản lượng (đv/giờ) 10 12 9 Hãy tìm kế hoạch sản xuất tối ưu: Tìm số giờ sản xuất theo PP1, PP2, PP3 để tổng sản lượng do cả 3 phương pháp sản xuất được lớn nhất có thể.
9 Vấn đề 2 dẫn đến bài toán QHTT Gọi x1, x2, x3 lần lượt là số giờ sản xuất theo PP1, PP2, PP3 tương ứng. Số nguyên liệu được sử dụng để sản xuất của 3 phương pháp là: - Nguyên liệu 1: 4 x1  5 x2  3 x3 Không vượt quá số lượng hiện có là 250 - Nguyên liệu 2: 2 x1  4 x2  x3 Không vượt quá số lượng hiện có là 350 - Nguyên liệu 3: 3 x1  6 x2  4 x3 Không vượt quá số lượng hiện có là 450 Tổng sản lượng do 3 phương pháp sản xuất được là: 10 x1  12 x2  9 x3 f  10 x1  12 x2  9 x3  max Bài toán QHTT g1  4 x1  5 x2  3 x3  250 Các hàm ràng buộc gi có hạng tử Mô hình toán: g 2  2 x1  4 x2  x3  350 bậc 0 ở bên kia dấu bất đẳng g3  3 x1  6 x2  4 x3  450 thức. Khác với x j  0  j  1, 2,3 việc trước đây đưa về dạng gi ≤0.
10 Vấn đề 3 dẫn đến bài toán QHTT Một xí nghiệp may mặc cần sản xuất 2000 chiếc quần và tối thiểu 1000 cái áo. Về mặt l{ thuyết, mỗi 1 tấm vải có thể cắt ra được 1 số lượng quần và áo theo 6 cách khác nhau, như trong bảng dưới đây: Cách cắt Quần Áo 1 90 35 2 80 55 3 70 70 4 60 90 5 120 0 6 0 100 Hãy tìm kế hoạch sản xuất tối ưu: Tìm số tấm vải cắt theo từng cách để sao cho tổng số vải sử dụng là ít nhất
11 Vấn đề 3 dẫn đến bài toán QHTT Gọi xj, (j=1..6) lần lượt là số tấm vải cắt theo cách thứ j, khi đó ta có: Do tổng số quần cần sản xuất là 2000 nên ta có phương trình: 90 x1  80 x2  70 x3  60 x4  120 x5  2000 Do tổng số áo cần sản xuất tối thiểu là 1000 nên ta có điều kiện: 35 x1  55 x2  70 x3  90 x4  100 x6  1000 6 Tổng số tấm vải cần sử dụng là: x j 1 j 6 f  x    x j  min j 1 Mô hình toán: g1  90 x1  80 x2  70 x3  60 x4  120 x5  2000 g 2  35 x1  55 x2  70 x3  90 x4  100 x6  1000 x j  0, x j  N  j  1..6 
12 Vấn đề 4 dẫn đến bài toán QHTT Một nhà đầu tư có 70 tỉ đồng muốn đầu tư vào các loại hình sau: - Tiết kiệm không kz hạn với lãi suất 6.5% - Tiết kiệm có kz hạn với lãi suất 8.5% - Mua trái phiếu chính phủ với lãi suất 10% - Cho tư nhân vay với lãi suất 13% Thời gian đáo hạn được cho là như nhau. Các loại hình đầu tư này đều có rủi ro và do đó người đầu tư muốn làm theo các chỉ dẫn sau của nhà tư vấn: 1. Không cho tư nhân vay quá 20% số vốn 2. Số tiền mua trái phiếu không nên vượt quá tổng số tiền đầu tư vào 3 lĩnh vực kia 3. Ít nhất 30% số tiền đầu tư phải thuộc tiết kiệm có kz hạn và trái phiếu 4. Tỷ lệ tiền tiết kiệm không kz hạn trên tiền tiết kiệm có kz hạn không vượt quá 1/3 Người này cần đầu tư mỗi khoản như thế nào với toàn bộ số tiền này để lợi nhuận thu được là tối đa?
1) Xác định các biến số. Gọi: 13 - x1 là số tiền gửi tiết kiệm không kz hạn - x2 là số tiền gửi tiết kiệm có kz hạn. - x3 là số tiền mua trái phiếu - x4 là số tiền cho tư nhân vay 2) Xác định hàm mục tiêu: Tổng lợi nhuận người đó thu được: 0.065 x1  0.085 x2  0.1x3  0.13 x4 3) Xác định các ràng buộc: Mô hình toán: [1]: x4  14 tỷ f  0.065 x1  0.085 x2  0.1x3  0.13x4  max [2]: x3  x1  x2  x4 g1  x1  14 g 2  x1  x2  x3  x4  0 [3]: x2  x3  21 tỷ g3  x2  x3  21 x1 1 [4]:  1 g 4  x1  x2  0 x2 3 3 [5]: x1  x2  x3  x4  70 g5  x1  x2  x3  x4  70 x j  0, x j  N  j  1..4 
14 Vấn đề 5 dẫn đến bài toán QHTT Để nuôi một loại gia súc trong 24 giờ cần có khối lượng tối thiểu các chất tương ứng là: - 90 gr Protit - 130 gr Gluxit - 10 gr chất khoáng Tỷ lệ % theo khối lượng của các chất trên có trong 3 loại thức ăn A, B, C như sau: Chất dinh dưỡng Thức ăn Protit Gluxit Khoáng A 10 30 2 B 20 40 1 C 30 20 3 Giá 1 kg thức ăn A, B, C lần lượt là 3000 đ, 4000 đ, 5000 đ Xác định khối lượng (đơn vị gr) thức ăn A, B, C cần mua trong ngày sao cho tổng chi phí để mua các loại thức ăn là thấp nhất.
1) Xác định các biến số. Gọi x1, x2, x3 lần lượt là số gram thức ăn A, 15 B, C cần mua  xj ≥ 0 (j=1..3) 2) Xác định các ràng buộc: Lượng chất dinh dưỡng có trong toàn bộ khẩu phần thức ăn cần mua: - Proteit: 0.1 x1 + 0.2 x2 + 0.3 x3 tối thiểu là 90 gr - Gluxit: 0.3 x1 + 0.4 x2 + 0.2 x3 tối thiểu là 130 gr - Khoáng: 0.02 x1 + 0.01 x2 + 0.03 x3 tối thiểu là 10 gr 3) Xác định hàm mục tiêu: Tổng chi phí cho khẩu phần thức ăn trong ngày là: 3 x1 + 4 x2 + 5 x3 (đồng) Mô hình toán: f  x   3 x1  4 x2  5 x3  min g1  0.1x1  0.2 x2  0.3x3  90 g 2  0.3x1  0.4 x2  0.2 x3  130 g3  0.02 x1  0.01x2  0.03x3  10 x j  0  j  1..3
16 Vấn đề 6 dẫn đến bài toán QHTT Tại sân bay Tân Sân Nhất có nhu cầu vận chuyển 1200 hành khách và 120 tấn hàng bằng máy bay. Giả sử có 2 loại máy bay có thể sử dụng với khả năng vận chuyển của mỗi loại như sau: - Máy bay loại A: Mỗi máy bay có thể chở 150 hành khách và 20 tấn hàng với chi phí là 240 triệu đồng - Máy bay loại B: Mỗi máy bay có thể chở 180 hành khách và 16 tấn hàng với chi phí là 220 triệu đồng Hãy tìm phương án sử dụng số máy bay mỗi loại sao cho thỏa mãn yêu cầu vận chuyển với tổng chi phí là ít nhất.
17 1) Xác định các biến số. Gọi xj, (j=A, B) lần lượt là số lượng máy bay loại j cần sử dụng  xj ≥ 0 (j=A, B), xj ϵ N (j=A, B) 2) Xác định hàm mục tiêu: Tổng chi phí vận chuyển là: 240 xA + 220 xB (triệu đồng) 3) Xác định các ràng buộc: - Tổng cộng 1200 hành khách cần phải chở: g1 = 150 xA + 180 xB = 1200 - Tổng cộng 120 tấn hàng cần phải chở: g2 = 20 xA + 16 xB = 120 Mô hình toán: f  x   240 x A  220 xB  min g1  150 x A  180 xB  1200 g 2  20 x A  16 xB  120 x j  0, x j  N  j  A, B 
18 Các dạng của bài toán QHTT n Tìm x   x1 , x2 , , xn  sao cho: f  x    c j x j  min max 1 j 1 Với điều kiện:  n   a x  b i  1..m  ij j i    2  j 1    x j  0  j  1..n1  ; x j  0  j   n1  1 ..n2 ; n2  n   3    (1) là hàm mục tiêu (2) Có m phương trình/bất phương trình ràng buộc (3) Ràng buộc về dấu (đối với ẩn số)  Bài toán QHTT gọi là giải được nếu có ít nhất 1 phương án tối ưu
19 Các dạng của bài toán QHTT n Tìm x   x1 , x2 , , xn  sao cho: f  x    c j x j  min max 1 j 1 Với điều kiện:  n  aij x j  bi  i  1..m   4  j 1  x  0  j  1..n   5  j Bất kz bài toán QHTT tổng quát nào cũng đều có thể đưa về dạng chính tắc nhờ các phép biến đổi tương đương sau:
20  n • Nếu ràng buộc có dạng ≤ n  aij x j  xn 1  bi thì cộng thêm 1 ẩn phụ  aij x j  bi   j 1 không âm j 1  xn 1  0   n • Nếu ràng buộc có dạng ≥ n  aij x j  xn 1  bi thì trừ đi 1 ẩn phụ không  aij x j  bi   j 1 âm j 1  xn 1  0   Khi đó thì hệ số của các ẩn phụ xn+1 trong hàm mục tiêu sẽ = 0 • Nếu biến xj ≤ 0 được thay  x j   xj xj  0   bằng:  xj  0 • Nếu biến xj không có ràng x j  xj  xj buộc về dấu thì được thay  xj  0 xj   bằng hiệu của 2 biến  xj  0 không âm 