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 (Linear programming)

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: d d cM Z   Zd – Môđun mặt cắt dẻo, σc – giới hạn chảy của vật liệu 4 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 cao h, bề rộng b là: 2 4 d c bh M         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 1 24 4 c E P P h U M            Do có 4 khớp vị trí khớp dẻo của cột (Column) 1 2 2 2 10 4 b E P P l U M            6 3 4     1 1 2 2 1 2 34 2 4c b E P P Ph P l U M M                  1 1 24 2 2c b E P P h U M M             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:    , 2 2 minc b b cf M M lM hM   ρ – khối lượng riêng của khung theo 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: 6 2.5 2 17 12 c b b c b c M M M M M M       7 Gọi Mc=x1, Mb=x2, ta thu được mô hình toán:   1 2 1 2 1 2 1 2 3 1 4 2 20 16 min 2 17 12 6 2.5 f x x g x x g x x g x g x                      x Bài toán QHTT Bài toán có 1 lời giải khi dùng phương pháp điều kiện KKT: min 0 6 16 ; ; 216 6 4 0 f                   * * x λ Các hàm ràng buộc gi có hạng tử bậc 0 ở bên kia dấu bất đẳng thức. Khác với việc trước đây đưa về dạng gi ≤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 liệu Số lượng hiện có (đv) Định mức tiêu hao trong một giờ 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: - Nguyên liệu 2: - Nguyên liệu 3: 1 2 34 5 3x x x  1 2 32 4x x x  1 2 33 6 4x x x  Không vượt quá số lượng hiện có là 250 Không vượt quá số lượng hiện có là 350 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à: 1 2 310 12 9x x x  Mô hình toán:   1 2 3 1 1 2 3 2 1 2 3 3 1 2 3 10 12 9 max 4 5 3 250 2 4 350 3 6 4 450 0 1,2,3j f x x x g x x x g x x x g x x x x j                   Bài toán QHTT Các hàm ràng buộc gi có hạng tử bậc 0 ở bên kia dấu bất đẳng thức. Khác với 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: 1 2 3 4 590 80 70 60 120 2000x x x x x     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: 1 2 3 4 635 55 70 90 100 1000x x x x x     Tổng số tấm vải cần sử dụng là: 6 1 j j x   Mô hình toán:     6 1 1 1 2 3 4 5 2 1 2 3 4 6 min 90 80 70 60 120 2000 35 55 70 90 100 1000 0, 1..6 j j j j f x g x x x x x g x x x x x x x j                   x N 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? 13 1) Xác định các biến số. Gọi: - 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: 1 2 3 40.065 0.085 0.1 0.13x x x x   3) Xác định các ràng buộc: [1]: [2]: [3]: [4]: [5]: 4 14x  tỷ 3 1 2 4x x x x   2 3 21x x  tỷ 1 2 1 3 x x  1 2 3 4 70x x x x      1 2 3 4 1 1 2 1 2 3 4 3 2 3 4 1 2 5 1 2 3 4 0.065 0.085 0.1 0.13 max 14 0 21 1 0 3 70 0, 1..4j j f x x x x g x g x x x x g x x g x x g x x x x x x j                          N Mô hình toán: 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: Thức ăn Chất dinh dưỡng 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. 15 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, 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)     1 2 3 1 1 2 3 2 1 2 3 3 1 2 3 3 4 5 min 0.1 0.2 0.3 90 0.3 0.4 0.2 130 0.02 0.01 0.03 10 0 1..3j f x x x g x x x g x x x g x x x x j                   x Mô hình toán: 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     1 2 240 220 min 150 180 1200 20 16 120 0, , A B A B A B j j f x x g x x g x x x x j A B             x N Mô hình toán: 18 Các dạng của bài toán QHTT Tìm  1 2, , , nx x xx sao cho:     1 min max 1 n j j j f c x   x Với điều kiện:           1 1 1 2 2 1.. 2 0 1.. ; 0 1 .. ; 3 n ij j i j j j a x b i m x j n x j n n n n                   (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 Tìm  1 2, , , nx x xx sao cho:     1 min max 1 n j j j f c x   x Với điều kiện:         1 1.. 4 0 1.. 5 n ij j i j j a x b i m x j n          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 1 1 1 1 0 n n ij j n i jij j i j n a x x b a x b x               • Nếu ràng buộc có dạng ≥ thì trừ đi 1 ẩn phụ không âm  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 bằng: 0 0 j j j j x x x x        • Nếu biến xj không có ràng buộc về dấu thì được thay bằng hiệu của 2 biến không âm 0 0 j j j jj j x x x xx x           1 1 1 1 0 n n ij j n i jij j i j n a x x b a x b x               • Nếu ràng buộc có dạng ≤ thì cộng thêm 1 ẩn phụ không âm 21   1 2 3 1 2 3 1 2 3 1 2 3 1 3 3 2 min 3 2 17 2 4 12 4 3 8 10 0; 0 f x x x x x x x x x x x x x x                    x 3 3 3 3 2 2 2 2 2 2 0 0 0; 0 x x x x x x x x x x                                      1 2 2 3 1 2 2 3 4 1 2 2 3 1 2 2 3 5 2 3 2 min 3 2 17 2 4 12 4 3 8 10 0 1,4,5 ; 0 2,3 ; 0j j f x x x x x x x x x x x x x x x x x x x j x j x                                          x     1 2 3 4 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 3 3 2 min 3 2 0 17 2 4 4 0 0 12 4 3 3 8 0 10 0 1..6j f x x x x x x x x x x x x x x x x x x x x x x x j                              x 22 Các dạng của bài toán QHTT Là trường hợp đặc biệt của bài toán dạng chính tắc. Khi ma trận hệ số của (4) chứa một ma trận đơn vị cấp m (có thể đưa về ma trận đơn vị bằng cách đổi chỗ các cột cho nhau) và bi ≥ 0 (i=1..m). Tìm  1 2, , , nx x xx sao cho:     1 min max 1 n j j j f c x   x Với điều kiện:             , 1 1.. 6 0 1.. 7 0 1.. 5 n m i i m k m k i k i j x a x b i m b i m x j n                 23 1, 1 1, 2, 1 2, , 1 , 1 0 0 0 1 0 0 0 1 m n m n m m m n a a a a A a a                   , 1 6 1.. n m i i i m k m k k x b a x i m         xi – ẩn cơ bản (i=1..m) xm+k – ẩn không cơ bản [k=1..(n-m)] • Một phương án mà các ẩn không cơ bản bằng 0 được gọi là phương án cơ bản (hay phương án cực biên) • Một phương án cơ bản có ít nhất 1 ẩn cơ bản bằng 0 gọi là phương án cơ bản suy biến • Một bài toán có ít nhất 1 phương án cơ bản suy biến gọi là bài toán suy biến 24 Ẩn cơ bản, phương án cơ bản     2 5 1 2 3 4 3 1 2 3 4 5 1 2 3 4 5 min 0 0 2 1 0 3 0 3 0 2 0 2 0 1..5j f x x x x x x x x x x x x x x x x x x j                        x    2 5 1 2 3 2 3 5 2 4 5 min 2 1 3 3 2 2 0 1..5j f x x x x x x x x x x x x j                   x 1 1 0 0 2 1 0 3 1 0 1 3 0 2 0 1 1 2 A            Ma trận hệ số Cột 1, 3, 4 tạo thành ma trận đơn vị cấp 3 Các ẩn x1, x3, x4 lần lượt là các ẩn cơ bản của các ràng buộc 1, 2, 3 1 0 3 2 0                0x PA cơ bản ban đầu   0f 0x 25 Mọi bài toán QHTT đều có thể đưa về dạng chính tắc tương ứng. Có 1 vài tính chất quan trọng với bài toán dạng chính tắc như sau, giả thiết m ràng buộc độc lập tuyến tính và m<n: 1) Tính chất 1: (Sự tồn tại phương án cơ bản PACB) Nếu bài toán có phương án thì có phương án cơ bản 2) Tính chất 2: (Sự tồn tại phương án cơ bản tối ưu) Nếu bài toán có phương án tối ưu PATƯ thì có phương án cơ bản tối ưu PACBTƯ 3) Tính chất 3: (Tính hữu hạn của số phương án cơ bản) Số phương án cơ bản khác nhau trong mỗi bài toán là hữu hạn 4) Tính chất 4: (Sự tồn tại phương án tối ưu) Nếu bài toán có phương án và trị số hàm mục tiêu bị chặn dưới (trên) trên tập phương án khi f(x)  min (max) thì bài toán có phương án tối ưu. 26 Phương pháp hình học Trong trường hợp bài toán QHTT có 2 biến thì ta có thể giải bằng phương pháp hình học. Áp dụng các ứng dụng sau đây: 1) Đường thẳng ax1 + bx2 = c chia mặt phẳng tọa độ thành 2 miền: Một miền là tập hợp tất cả các điểm M(x1,x2) thỏa mãn bất phương trình ax1 + bx2 > c , một miền là tập hợp tất cả các điểm M(x1,x2) thỏa mãn bất phương trình ax1 + bx2 < c. 1x 2x 1 2ax bx c   1 2,M x x thỏa mãn 1 2ax bx c     1 2,M x x thỏa mãn 1 2ax bx c    27 Phương pháp hình học 2) Họ đường thẳng cx1 + dx2 = m (m ϵ R) là tập hợp các đường thẳng song song với nhau mà ta gọi là đường đồng mức (tương ứng với giá trị mức m). Nếu ta di chuyển một đường thẳng trong họ (một đường đồng mức) đến một đường thẳng khác trong họ theo hướng của véctơ Gradient (c,d) thì giá trị tương ứng của m tăng, còn theo hướng ngược lại thì giá trị tương ứng của m giảm. 1x 2x 1 2 4cx dx m   ,c dc 1 2 1cx dx m  1 4m m Độ dốc (Hướng tăng mức giá trị m) 28 ax1 + bx2 = c 1 2 1 2 1 x x ax bx c c c a b                  1x 2x 1 2ax bx c  c a       c b       29 Phương pháp hình học 1) Vẽ các đường thẳng ràng buộc trong mặt phẳng tọa độ x1Ox2 2) Xác định các nửa mặt phẳng hợp lệ 3) Xác định miền lời giải đa giác hợp lệ 4) Vẽ véc tơ Gradient (c,d) chỉ hướng tăng của hàm mục tiêu 5) Dịch chuyển đường thẳng hàm mục tiêu theo hướng véctơ Gradient hoặc ngược lại đến các đỉnh ngoài cùng để tìm giá trị lớn nhất hoặc nhỏ nhất của hàm mục tiêu. 6) Tính tọa độ các điểm cực trị và giá trị hàm mục tiêu trong điểm cực trị đó 30 Phương pháp hình học   1 2 1 2 1 2 1 2 max 7 3 0 4 2 5 f x x x x x x x x               x max 4 2 2f         maxx 2 5 31 Phương pháp hình học   1 2 1 2 1 2 1 2 2 2 min 2 1 1 2 1 4 f x x x x x x x x              x min min 1 2 1 4 3 2 f          x 32 Phương pháp hình học   1 2 1 2 1 2 1 2 1 2 3 4 max 3 4 18 3 3 2 0 5 0 6 f x x x x x x x x x x                    x max 1 max max max 2 1 max 26 2 7 9 3 2 4 18 x x x f                 x 33 Phương pháp hình học   1 2 1 2 1 2 1 2 1 2 3 4 min 3 4 18 3 3 2 0 5 0 6 f x x x x x x x x x x                   x min 1 min min min 2 1 min 26 2 7 9 3 2 4 18 x x x f                x 34 Phương pháp hình học   1 2 1 2 1 2 1 2 1 2 max 4 1 3 2 3 2 , 0 f x x x x x x x x x x               x max 1 max max max 2 1 max 10 7 1 1 x x x f             x 35 Phương pháp hình học   1 2 1 2 1 2 1 2 1 2 3 min 24 1 1 3 3 2 9 2 , 0 f x x x x x x x x x x                  x min 1 min min min 2 1 min 2 3 3 3 x x x f           x 36 Phương pháp hình học   1 2 1 2 1 2 1 2 1 2 max 3 2 1 3 1 4 5 1 4 , 0 f x x x x x x x x x x                  x maxf   37 Phương pháp hình học   1 2 1 2 1 2 1 2 2 min 3 1 5 4 6 3 0 1 2 f x x x x x x x x               x minf   38 Phương pháp hình học   1 2 1 2 1 2 1 2 max/ min 1 1 0 1 0 f x x x x x x x x              x min/max min/max 1 0 1f         x 39 Phương pháp hình học   1 2 1 2 1 2 1 2 1 2 max/ min 3 5 32 4 3 12 8 7 3 , 0 f x x x x x x x x x x              x Không tồn tại miền hợp lệ (tập hợp rỗng). Vì thế hàm không có cực đại cũng như cực tiểu. 40 Phương pháp đơn hình Theo các tính chất của bài toán QHTT, để tìm PATƯ của bài toán ta chỉ cần xét các PACB. Xuất phát từ một phương án cơ bản ban đầu x0 nào đó, tìm cách đánh giá nó. Nếu nó chưa phải là PATƯ thì tìm cách chuyển sang một PACB mới x1 tốt hơn. Quá trình này được lặp lại chừng nào còn có khả năng thực hiện sự di chuyển ấy. Vì số PACB là hữu hạn nên sau một số hữu hạn bước lặp hoặc sẽ thu được PATƯ của bài toán, hoặc sẽ kết luận bài toán không giải được vì hàm mục tiêu không bị chặn. Vì cần xuất phát từ các PACB nên ta phải đưa bài toán về dạng chuẩn 41 Phương pháp đơn hình Đầu tiên phải đưa bài toán về dạng chuẩn: Tìm  1 2, , , nx x xx sao cho:     1 min max 1 n j j j f c x   x Với điều kiện:             , 1 1.. 6 0 1.. 7 0 1.. 5 n m i i m k m k i k i j x a x b i m b i m x j n                   01 2 1 , , , ,0, ,0 m m i i in m b b b f c b f             0 0x x Phương án cơ bản 42 Xét 1 phương án x’ bất kz của bài toán:         0 , 1 1 1 1 1 1 , 1 1 1 1 , ; m k n m n m m n m n m j j i i m k m k i i i m