12 trang
| Chia sẻ : ntt139
| Lượt xem: 6820
| Lượt tải: 2
Bạn đang xem nội dung tài liệu Giáo án môn toán – Chương 2 : Phương pháp đơn hình, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Chương 2 : PHƯƠNG PHÁP ĐƠN HÌNH Phương pháp đơn hình do G.B. Dantzig đề xuất kiến nghị năm 1947 cho đến lúc bấy giờ vẫn là chiêu thức được sử dụng nhiều nhất trong việc giải các bài toán quy hoạch tuyến tính. Đối với các bài toán cỡ lớn ( hoàn toàn có thể đến hàng nghìn biến và hàng trăm ràng buộc ) phải dùng đến máy tính, chiêu thức đơn hình cũng đã được kiểm nghiệm qua mấy chục năm vận dụng là rất hiệu suất cao, với thời hạn thống kê giám sát khá ngắn. § 1. CƠ SỞ CỦA PHƯƠNG PHÁP ĐƠN HÌNH Phương pháp đơn hình giải bài toán QHTT dựa trên hai đặc thù quan trọng sau đây của bài toán QHTT : a ) Nếu bài toán quy hoạch tuyến tính chính tắc có giải pháp tối ưu thì cũng có giải pháp cực biên tối ưu, nghĩa là có tối thiểu một đỉnh của miền ràng buộc là giải thuật của bài toán. b ) Mỗi điểm cực tiểu địa phương của hàm tuyến tính trên miền ràng buộc D ( một tập hợp lồi ) là một điểm cực tiểu tuyệt đối. Tính chất a ) được cho phép tìm giải pháp tối ưu trong số các giải pháp cực biên của bài toán ( số này là hữu hạn ). Tính chất b ) được cho phép khi kiểm tra tối ưu so với một giải pháp cực biên ( đỉnh ) chỉ cần so sánh nó với các đỉnh lân cận ( đỉnh kề ) là đủ. Vì thế, chiêu thức đơn hình khởi đầu từ một giải pháp cực biên nào đó ( tùy ý ) của bài toán ( tức là một đỉnh của miền ràng buộc ). Tiếp đó kiểm tra xem giải pháp hiện có đã phải là giải pháp tối ưu hay chưa, bằng cách so sánh giá trị hàm mục tiêu tại đỉnh đó với giá trị hàm mục tiêu tại các đỉnh kề với nó. Nếu đúng thì dừng quy trình giám sát. Trái lại, giải pháp sẽ cho cách tìm một giải pháp cực biên mới tốt hơn ( với giá trị hàm mục tiêu nhỏ hơn ) mà nó là một đỉnh kề với đỉnh trước đó. Quá trình này triển khai cho tới khi tìm được giải pháp tối ưu hoặc phát hiện bài toán đã cho không có giải thuật. Như vậy, giải pháp đơn hình thực thi khảo sát các đỉnh của miền ràng buộc để tìm ra đỉnh tối ưu. Mặc dù số đỉnh của bài toán nói chung rất lớn, nhưng trên thực tiễn giải pháp này chỉ yên cầu kiểm tra một phần tương đối nhỏ các đỉnh. Chính điều đó biểu lộ hiệu suất cao trong thực tiễn của giải pháp đơn hình. § 2. THUẬT TOÁN ĐƠN HÌNH Để giải bìa toán QHTT ( G ) bằng giải pháp đơn hình ta triển khai các bước dưới đây. Bước sẵn sàng chuẩn bị : Đưa ( G ) về dạng chính tắc chuẩn ( N ) nếu cần. Bước 1 : Xác định PACB xo xuất phát, chỉ ra các biến và các thông số cơ sở. ( Nếu bài toán dạng ( N ) thì một PACB được tìm thuận tiện từ ma trận con sơ cấp của A – trong bảng đơn hình ở bước 2, ma trận con sơ cấp được giả định là ma trận đơn vị chức năng cấp m tạo thành từ m dòng và m cột tiên phong, khi đó PACB xuất phát chính là x0 = ( b1, b2, , bm, 0, , 0 ) ). Bước 2 : Lập bảng đơn hình, tính giá trị của hàm mục tiêu và các số ước đạt Dj. Hệ số cơ sở Biến cơ sở PA CB x1 x2 xm xm + 1 xn c1 c2 cm cm + 1 cn c1 c2. .. cm x1 x2. .. xm b1 b2. .. bm 1 0 0 a1, m + 1 a1n 0 1 0 a2, m + 1 a2n. .. .. .. .. .. .. .. 0 0 1 am, m + 1 amn Bảng 1 f ( x0 ) 0 0 0 Dm + 1 Dn Ở đây f ( x0 ) = c1b1 + c2b2 + + cmbm ; Dj = 0 ( j = 1, , m ) ; Dj =. Bước 3 : Kiểm tra điều kiện kèm theo tối ưu ( Đối với bài toán MIN ) Nếu mọi giải pháp đang xét tối ưu ® STOP. Nếu sống sót mà mọi thì hàm mục tiêu không bị chặn, do đó bài toán đã cho vô nghiệm ® STOP. Nếu sống sót và với mỗi đều có tối thiểu một thì giải pháp đang xét chưa tối ưu ® Làm tiếp bước 4. Bước 4 : Cải tiến PACB đang xét để được PACB tốt hơn ( Đối với bài toán MIN ) Chọn biến cơ bản mới sao cho để đưa vào. Chọn biến cơ bản cũ sao cho để đưa ra. Tiếp theo chọn dòng thứ r làm dòng xoay, cột thứ v làm cột xoay, thành phần làm thành phần xoay rồi biến hóa sơ cấp để được bảng đơn hình mới với PACB mới tốt hơn. Cách đổi khác bảng đơn hình để nhận được bảng mới và PACB mới tốt hơn Đổi cột biến cơ sở : biến cơ sở mới là xv thay cho biến cơ sở cũ là xr ở dòng r. Đổi cột thông số cơ sở : thông số cv thay cho thông số cr ở dòng r. Biến đổi dòng xoay : Dòng mới = dòng cũ / thành phần xoay, Nghĩa là chia mỗi thành phần ở dòng xoay cho thành phần xoay ( arv > 0 ). Kết quả nhận được gọi là dòng chính ( số 1 Open ở vị trí của arv cũ ). Biến đổi các dòng khác theo quy tắc hình chữ nhật : Dòng mới = dòng cũ tương ứng – thành phần của nó trên cột xoay × dòng chính, nghĩa là Cột ≠ cột xoay Cột xoay ( cột v ) Dòng ≠ dòng xoay : a b a ’ = a – bc Dòng chính ( dòng r mới ) : c 1 Sau đó lặp lại các bước 2, 3, 4 cho đến khi được P.A.C.B tối ưu thì dừng và Kết luận về đáp số của bài toán đã cho Chú ý Ở bước 3 khi kiểm tra điều kiện kèm theo tối ưu so với bài toán MAX, ta làm như sau : Nếu mọi giải pháp đang xét tối ưu ® STOP. Nếu sống sót mà mọi thì hàm mục tiêu không bị chặn, do đó bài toán đã cho vô nghiệm ® STOP. Nếu sống sót mà với mỗi đều có tối thiểu một thì giải pháp đang xét chưa tối ưu ® Làm tiếp bước 4. Còn ở bước 4 khi nâng cấp cải tiến PACB so với bài toán MAX, ta làm như sau : Chọn biến cơ bản mới sao cho để đưa vào. Chọn biến cơ bản cũ sao cho để đưa ra. Tiếp theo chọn dòng thứ r làm dòng xoay, thành phần làm thành phần xoay rồi biến hóa sơ cấp để được bảng đơn hình mới. Cũng hoàn toàn có thể quy bài toán MAX về bài toán MIN hoặc ngược lại bằng cách đối dấu hàm mục tiêu. Dấu hiệu bài toán vô số nghiệm : Khi kiểm tra điều kiện kèm theo tối ưu ở bước 3, nếu mọi ( so với bài toán MIN ) hoặc ( so với bài toán MAX ) đồng thời sống sót một ứng với biến phi cơ sở thì bài toán có vô số nghiệm. Cách tìm hết toàn bộ các PATU của bài toán QHTT : Giả sử đã tìm ra một PATU. Khi đó giải hệ gồm phương trình và các ràng buộc ta sẽ được toàn bộ các PATU của bài toán đã cho. Ví dụ 1. Giải bài toán quy hoạch tuyến tính ( N ) sau đây f = x1 – x2 – 2×4 + 2×5 – 3×6 → min, với các điều kiện kèm theo x1 + x4 + x5 – x6 = 2, x2 + x4 + x6 = 12, x3 + 2×4 + 4×5 + 3×6 = 9, xj ≥ 0, j = 1, 2, …, 6. Cho x4 = x5 = x6 = 0 ta được giải pháp cực biên bắt đầu x0 = ( 2 ; 12 ; 9 ; 0 ; 0 ; 0 ) với trị tiềm năng f0 = – 10. Cơ sở của x0 là { A1, A2, A3 }, tức là J0 = { 1, 2, 3 }. Các biến cơ sở là x1, x2, x3. Các biến phi cơ sở là x4, x5, x6. Các thông số cơ sở c1 = 1, c2 = – 1, c3 = 0. Bảng đơn hình tiên phong như sau : Hệ số cơ sở Biến cơ sở PACB x1 x2 x3 x4 x5 x6 1 – 1 0 – 2 2 – 3 1 x1 2 1 0 0 1 1 – 1 2 – 1 x2 12 0 1 0 1 0 1 12 0 x3 9 0 0 1 2 4 3 9/2 Bảng 1 – 10 0 0 0 2 – 1 1 Trong dòng tiềm năng ( dòng cuối ) còn = 2 > 0, = 1 > 0 và trên mỗi cột chứa mỗi số ước lượn dương đó đều có những thông số dương nên giải pháp x0 ở bảng này chưa tối ưu. Ta cần biến hóa bảng để dược PACB mới tốt hơn. Biến cơ sở mới cần đưa vào là x4 ( ứng với = 2 lớn nhất ). Biến loại khỏi cơ sở là x1 ( ứng với = min { 2, 12, 9/2 } = 2 nhỏ nhất ). Phần tử xoay là a14 = 1 ( trong ô được tô bóng mờ ). Biến đổi bảng 1 theo các quy tắc đã nêu ta nhận được bảng 2 dưới đây. Hệ số cơ sở Biến cơ sở PACB x1 x2 x3 x4 x5 x6 1 – 1 0 – 2 2 – 3 – 2 x4 2 1 0 0 1 1 – 1 – 1 x2 10 – 1 1 0 0 – 1 2 5 0 x3 5 – 2 0 1 0 2 5 1 Bảng 2 – 14 – 2 0 0 0 – 3 3 Trong dòng cuối của bảng này còn thành phần D6 = 3 > 0 và trên cột chứa nó có hai thông số dương nên giải pháp ở bảng này vẫn chưa tối ưu. Ta cần biến hóa bảng để dược PACB mới tốt hơn. Biến cơ sở mới cần đưa vào x6 ( ứng với = 3 lớn nhất ). Biến loại khỏi cơ sở là x3 ( ứng với tỉ số nhỏ nhất = min { 5, 1 } = 1 ). Phần tử xoay là a36 = 5. Biến đổi bảng 2 ta nhận được bảng 3 dưới đây. Hệ số cơ sở Biến cơ sở PACB x1 x2 x3 x4 x5 x6 1 – 1 0 – 2 2 – 3 – 2 x4 3 3/5 0 1/5 1 7/5 0 – 1 x2 8 – 1/5 1 – 2/5 0 – 9/5 0 – 3 x6 1 – 2/5 0 1/5 0 2/5 1 Bảng 3 – 17 – 4/5 0 – 3/5 0 – 21/5 0 Trong bảng này mọi ≤ 0, nên giải pháp x * = ( 0 ; 8 ; 0 ; 3 ; 0 ; 1 ) là PATU với fmin = f ( x * ) = – 17. Ví dụ 2. Ví dụ sau cho thấy bài toán không có giải pháp tối ưu f = x2 – 3×3 + 2×5 → min, x1 + x2 – x3 + x5 = 7, – 4×2 + 4×3 + x4 = 12, – 5×2 + 3×3 + x5 + x6 = 10, xj ≥ 0, j = 1, 2, …, 6. Ta giải bài toán trên bằng chiêu thức đơn hình, xuất phát từ giải pháp cực biên x0 = ( 7, 0, 0, 12, 0, 10 ) với cơ sở là các véctơ cột đơn vị chức năng A1, A4, A6, tức là J0 = { 1, 4, 6 }. Lập bảng đơn hình rồi thự hiện các giám sát biến hóa theo thuật toán đơn hình ta được : Biến cơ sở Hệ số CB Phương án x1 x2 x3 x4 x5 x6 0 1 – 3 0 2 0 x1 0 7 1 1 – 1 0 1 0 x4 0 12 0 – 4 4 1 0 0 3 x6 0 10 0 – 5 3 0 1 1 10/3 Bảng 1 0 0 – 1 3 0 – 2 0 x1 0 10 1 0 0 1/4 1 0 x3 – 3 3 0 – 1 1 1/4 0 0 x6 0 1 0 – 2 0 – 3/4 1 1 Bảng 2 – 9 0 2 0 – 3/4 – 2 0 Trong bảng 2 có = 2 > 0 nhưng mọi thành phần ai2 ≤ 0 ( i = 1, 2, 3 ) nên bài toán trên không có PATU ( vì hàm mục tiêu của bài toán giảm vô hạn trong miền ràng buộc của nó ). Nói cách khác, bài toán QHTT đã cho không có giải thuật. Chú ý : Bài toán tìm g → max được thay bằng bài toán tìm f = – g → min. Ví dụ 3. Giải bài toán quy hoạch tuyến tính sau. f = 3×1 – x2 – 2×3 → max, – x1 + 3×2 + x3 + x4 = 7, 3×1 – 4×2 + 8×3 + x5 = 10, 4×1 – 2×2 + x6 = 12, xj ≥ 0, j = 1, 2, …, 6. Ta thay f bằng g = – f = – 3×1 + x2 + 2×3 → min với cùng các điều kiện kèm theo như trên. Xuất phát từ giải pháp cực biên x0 = ( 0, 0, 0, 7, 10, 12 ), ta giải bài toán bằng chiêu thức đơn hình ( các Bảng 1 – 3 ). Lời giải thu được là x * = ( 5, 4, 0, 0, 11, 0 ) với gmin = – 11. Từ đó fmax = 11. Biến cơ sở Hệ số CB Phương án x1 x2 x3 x4 x5 x6 – 3 1 2 0 0 0 x4 0 7 – 1 3 1 1 0 0 x5 0 10 3 – 4 8 0 1 0 10/3 x6 0 12 4 – 2 0 0 0 1 3 Bảng 1 0 3 – 1 – 2 0 0 0 x4 0 10 0 5/2 1 1 0 1/4 4 x5 0 1 0 – 5/2 8 0 1 – 3/4 x1 – 3 3 1 – 50% 0 0 0 1/4 Bảng 2 – 9 0 50% – 2 0 0 – 3/4 x2 1 4 0 1 2/5 2/5 0 1/10 x5 0 11 0 0 9 1 1 – 1/2 x1 – 3 5 1 0 1/5 1/5 0 3/10 Bảng 3 – 11 0 0 – 11/5 – 1/5 0 – 4/5 Ví dụ 4. Giả bài toán ( C ) : f ( x ) = 3×1 – 3×2 + x3 – x4 → min, – x1 + x2 + 2×3 + x4 = 2, x1 + x2 – x3 – x4 = 6, 3×1 + 2×2 – 6×3 + 3×4 = 9, x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0. Đưa vào ba biến giả x5, x6, x7 ≥ 0 với thông số giả M > 0 ( đủ lớn ) ta được bài toán ( N ) F = 3×1 – 3×2 + x3 – x4 + M ( x5 + x6 + x7 ) → min, – x1 + x2 + 2×3 + x4 + x5 = 2, x1 + x2 – x3 – x4 + x6 = 6, 3×1 + 2×2 – 6×3 + 3×4 + x7 = 9, xj ≥ 0 ( j = 1, 2, 3, 4, 5, 6, 7 ). Ta giải bài toán ( N ) bằng chiêu thức đơn hình, xuất phát từ giải pháp cực biên x0 = ( 0, 0, 0, 0, 2, 6, 9 ). Quá trình giải bài toán ( N ) được ghi tóm tắt trong các bảng sau ( Bảng 1 – 4 ). Biến cơ sở CB Phương án x1 x2 x3 x4 x5 x6 x7 θ 3 – 3 1 – 1 M M M x5 M 2 – 1 1 2 1 1 0 0 2 x6 M 6 1 1 – 1 – 1 0 1 0 6 x7 M 9 3 2 – 6 3 0 0 1 4.5 Bảng 1 17M 3M-3 4M + 3 < 0 3M + 1 0 0 0 x2 - 3 2 - 1 1 2 1 0 0 x6 M 4 2 0 - 3 - 2 1 0 2 x7 M 5 5 0 - 10 1 0 1 1 Bảng 2 9M-6 7M 0 < 0 < 0 0 0 x2 - 3 3 0 1 0 6/5 0 x6 M 2 0 0 1 - 12/5 1 2 x1 3 1 1 0 - 2 1/5 0 Bảng 3 2M-6 0 0 M-7 < 0 0 x2 - 3 3 0 1 0 6/5 x3 1 2 0 0 1 - 12/5 x1 3 5 1 0 0 - 23/5 Bảng 4 8 0 0 0 - 94/5 Ở Bảng 4 ta thấy ∆ k ≤ 0 với mọi k = 1, 2, 3, 4, nên giải pháp cho ở bảng này x = ( 5, 3, 2, 0, 0, 0, 0 ) là giải pháp tối ưu của bài toán ( M ). Vậy x * = ( 5, 3, 2, 0 ) là giải pháp tối ưu của bài toán bắt đầu với fmin = 8. § 4. VÍ DỤ GIẢI BÀI TOÁN QHTT DẠNG TỎNG QUÁT ( G ) Ví dụ 1. Giải bài toán sau bằng giải pháp đơn hình. f = 5x1 + 8x2 → max, x1 + 2x2 ≤ 1, x1 + x2 ≤ 2, x1 ≥ 0, x2 ≥ 0. Trước hết ta chuyển bài toán trên về bài toán tìm min và có dạng ( N ) bằng cách đưa vào các biến phụ x3, x4 ≥ 0. Ta được bài toán g = – 5x1 – 8x2 → min, x1 + 2x2 + x3 = 1, x1 + x2 + x4 = 2, xj ≥ 0, j = 1, 2, 3, 4. Ta giải bài toán này bằng giải pháp đơn hình, xuất phát từ giải pháp cực biên x0 = ( 0, 0, 1, 2 ). Cơ sở của x0 là { A3, A4 }. Quá trình giải như sau ( Bảng 1 - 3 ). Biến cơ sở CB Phương án x1 x2 x3 x4 - 5 - 8 0 0 x3 0 1 1 2 1 0 ½ x4 0 2 1 1 0 1 2 Bảng 1 0 5 8 0 0 x2 - 8 50% 50% 1 50% 0 1 x4 0 3/2 1/2 0 - 50% 1 3 Bảng 2 - 4 1 0 - 4 0 x1 - 5 1 1 2 1 0 x4 0 1 0 - 1 - 1 1 Bảng 3 - 5 0 - 2 - 5 0 Ở Bảng 3 mọi ∆ k ≤ 0 nên x * N = ( 1, 0, 0, 1 ) là giải pháp tối ưu của bài toán chính tắc với gmin = – 5. Từ đó suy ra giải thuật bài toán bắt đầu là x * = ( 1, 0 ) với fmax = – gmin = 5. Ví dụ 2. Giải bài toán sau f = – 3x1 + x2 – 2x3 → min, 2x1 + 4x2 – x3 ≤ 10, 3x1 + x2 + x3 ≥ 4, x1 – x2 + x3 = 2, xj ≥ 0, j = 1, 2, 3. Trước hết ta thêm vào hai biến phụ x4, x5 ≥ 0 để đưa bài toán về dạng chính tắc ( C ). Tiếp đó ta đưa vào hai biến giả x6, x7 ≥ 0 để được bài toán ( N ) như sau. fM = - 3x1 + x2 - 2x3 + M ( x6 + x7 ) → min, 2x1 + 4x2 - x3 + x4 = 10, 3x1 + x2 + x3 - x5 + x6 = 4, x1 - x2 + x3 + x7 = 2, xj ≥ 0, j = 1, 2, ..., 7. Ta giải bài toán ( N ) bằng chiêu thức đơn hình với M > 0 ( đủ lớn ). Quá trình giải ghi ở các bảng sau ( bỏ lỡ hai cột biến giả ). Biến cơ sở CB Phương án x1 x2 x3 x4 x5 – 3 1 – 2 0 0 x4 0 10 2 4 – 1 1 0 5 x6 M 4 3 1 1 0 – 1 4/3 x7 M 2 1 – 1 1 0 0 2 Bảng 1 60 4M + 3 – 1 2M + 2 0 – M x4 0 22/3 0 10/3 – 5/3 1 2/3 x1 – 3 4/3 1 1/3 1/3 0 – 1/3 4 x7 M 2/3 0 – 4/3 2/3 0 1/3 1 Bảng 2 2M / 3 – 4 0 < 0 2M / 3 + 1 0 M / 3 + 1 x4 0 9 0 0 0 1 3/2 6 x1 - 3 1 1 1 0 0 - 1/2 x3 - 2 1 0 - 2 1 0 50% 2 Bảng 3 - 5 0 0 0 0 1/2 x4 0 6 0 6 - 3 1 0 1 x1 - 3 2 1 - 1 1 0 0 x5 0 2 0 - 4 2 0 1 Bảng 4 - 6 0 2 - 1 0 0 x2 1 1 0 1 - 1/2 1/6 0 x1 - 3 3 1 0 1/2 1/6 0 x5 0 6 0 0 0 2/3 1 Bảng 5 - 8 0 0 0 - 1/3 0 Ở Bảng 5 mọi ∆ k ≤ 0 nên x = ( 3, 1, 0, 0, 6, 0, 0 ) là giải pháp tối ưu của bài toán ( N ). Từ đó suy ra giải thuật bài toán khởi đầu là x * = ( 3, 1, 0 ) với fmin = – 8. BÀI TẬP 1. Dùng chiêu thức đơn hình giải các bài toán dưới đây a ) f = – 50x1 – 60x2 ® min, x1 + 2x2 £ 8, x1 + x2 £ 5, 9x1 + 4x2 £ 36, x1 ³ 0, x2 ³ 0. b ) f = 2x1 + 5x2 + 4x3 + x4 – 5x5 ® min, x1 + 2x2 + 4x3 – 3x5 = 152, 4x2 + 2x3 + x4 + 3x5 = 60, 3x2 + x5 £ 36, xj ³ 0 ( j = 1,2, ..., 5 ). c ) f = 6x1 + x2 + x3 + 3x4 + x5 – 7x6 + 6x7 ® min, – x1 + x2 – x4 + x6 + x7 = 15, 2x1 – x3 + 2x6 + x7 = – 9, 4x1 + 2x4 + x5 – 3x6 = 2, xj ³ 0 ( j = 1, ..., 7 ). f = x1 – x2 ® min, x1 – x2 ³ – 1, 3x1 + 2x2 £ 6, – 3x1 – x2 ³ – 9, x1³ 0, x2 ³ 0. e ) f = 2x1 + x2 + x3 → min, x1 + x2 + x3 + x4 + x5 = 5, x1 + x2 + 2x3 + 2x4 + 2x5 = 8, x1 + x2 = 2, x3 + x4 + x5 = 3, xj ³ 0 ( j = 1, ..., 4 ). f ) ) f = – x1 – 2x2 – 3x3 + x4 ® min, x1 + 2x2 + 3x3 = 15, 2x1 + x2 + 5x3 = 20, x1 + 2x2 + x3 + x4 = 10, xj ³ 0 ( j = 1, ..., 4 ). g ) f = x1 + 2x2 – x3 ® max, – x1 + 4x2 – 2x3 £ 6, x1 + x2 + 2x3 ³ 6, 2x1 – x2 + 2x3 = 4, x1³ 0, x2 ³ 0, x3 ³ 0. . h ) f = – x1 – x2 + 1 ® max, x1 – x2 ³ – 1, 3x1 + 2x2 ³ 6, – 3x1 – x2 ³ – 9, x1³ 0, x2 ³ 0. 2. Giải các bài toán trong thực tiễn cho ở bài tập 1 ), 2 ) và 5 ) Chương 1 . Các file đính kèm theo tài liệu này :
- tailieu.doc
Source: https://vietsofa.vn
Category : Góc học tập
+ There are no comments
Add yours