[Toán Học Cao Cấp] Rút - Tối Ưu Phương Trình Phần 4

Theo tính chất 5 của cặp bài toán đối ngẫu, ta có phương án tối ưu của bài toán gốc là x 1 = 1, x ∗ = 2 với zmin = 7. 2Bảng III.6. Giải bài toán đối ngẫuHệ số hàm mục tiêu 0 0 uj Biến cơ sở y4 y5 Phương án 3 2 0 y3 y5 3/2 1/2 6 y3 y1 4/3 1/3 20/3 y3 y2 1 1 7 c1 = 4
Nội dung trích xuất từ tài liệu:
[Toán Học Cao Cấp] Rút - Tối Ưu Phương Trình Phần 4là, trước hết tìm cách giải bài toán đối ngẫu (chỉ với 5 biến), sau đó sẽ tìm được phương án tối ưucủa bài toán gốc. Bài toán đối ngẫu: Max u = 4y1+3y2+ 4y3với các ràng buộc ⎧ y 1 + y 2 + 2y 3 ≤ 3 ⎪ ⎨2y 1 + y 2 + y 3 ≤ 2 ⎪ y , y , y ≥ 0. ⎩1 2 3 Viết bài toán đối ngẫu dưới dạng chính tắc: Max u = 4y1+3y2+ 4y3 + 0y4 + 0y5với các ràng buộc ⎧ y 1 + y 2 + 2y 3 + y 4 = 3 ⎪ ⎨2y1 + y 2 + y 3 + y 5 = 2 ⎪ y , y , y , y , y ≥ 0. ⎩1 2 3 4 5 Cách 1. Giải bài toán đối ngẫu bằng phương pháp đơn hình. Kết quả được cho trong bảng ∗III.6. Theo tính chất 5 của cặp bài toán đối ngẫu, ta có phương án tối ưu của bài toán gốc là x 1 =1, x ∗ = 2 với zmin = 7. 2 Bảng III.6. Giải bài toán đối ngẫu c1 = 4 c2 = 3 c3 = 4 c4 = 0 c5 = 0 Hệ số Biến cơ sở Phương án hàm mục tiêu y1 y2 y3 y4 y5 0 y4 3 1 1 1 0 2 0 y5 2 2 1 1 0 1 uj 0 0 0 0 0 0 Δ / 4 3 4 0 0 j 4 y3 3/2 1/2 1/2 1 1/2 0 0 y5 1/2 1/2 0 – 1/2 1 3/2 uj 2 2 4 2 0 6 Δ / 2 1 0 –2 0 j 4 y3 4/3 0 1/3 1 2/3 – 1/3 4 y1 1/3 1 0 – 1/3 2/3 1/3 uj 4 8/3 4 4/3 4/3 20/3 Δ /j 0 1/3 0 – 4/3 – 4/3 4 y3 1 –1 0 1 1 –1 3 y2 1 3 1 0 –1 2 uj 5 3 4 1 2 7 Δ / –1 0 0 –1 –2 j Cách 2. Giải bài toán gốc bằng phương pháp đơn hình đối ngẫu.58 Trước hết đưa Bài toán gốc về dạng sau: Min z = 3x1+ 2x2 + 0x3 + 0x4 + 0x5với các ràng buộc ⎧−x 1 − 2x 2 + x 3 = −4 ⎪ ⎪−x 1 − x 2 + x 4 = −3 ⎨ ⎪−2x1 − x 2 + x 5 = −4 ⎪x , x , x , x , x ≥ 0. ⎩1 2 3 4 5 Nội dung tóm tắt của phương pháp đơn hình đối ngẫu: Trong phương pháp đơn hình,chúng ta dịch chuyển dần từ phương án khả thi, tức là xj ≥ 0, ∀j nhưng điều kiện Δj ≥ 0, ∀j chưađược thoả mãn, tới phương án tối ưu, tức là xj ≥ 0 và Δj ≥ 0, ∀j. Trong phương pháp đơn hình đốingẫu, chúng ta dịch chuyển dần từ phương án không khả thi (nhưng đối ngẫu khả thi), tức là điềukiện xj ≥ 0,∀j không được thoả mãn nhưng luôn có Δj ≥ 0, ∀j, tới phương án tối ưu, tức là có xj ≥0 và Δj ≥ 0, ∀j. Minh họa hình học của vấn đề này sẽ được trình bày ở mục 1, chương IV, trongphần phương pháp cắt Gomory giải BTQHTT nguyên. Quy trình giải bài toán gốc dạng chuẩn tắc trên đây bằng phương pháp đơn hình đối ngẫuđược mô tả trong bảng III.7. Bảng III.7. Giải bài toán gốc bằng phương pháp đơn hình đối ngẫu 3 2 0 0 0 Hệ số Biến cơ sở Phương án hàm mục tiêu x1 x2 x3 x4 x5 0 x3 –4 –1 –2 1 0 0 0 ...