Chương 2: Bài toán đối ngẫu - bài 2

Tham khảo tài liệu chương 2: bài toán đối ngẫu - bài 2, khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Chương 2: Bài toán đối ngẫu - bài 2 CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 2: CÁCH GIẢI BÀI TOÁN ĐỐI NGẪU Ý NGHĨA VÀ MỘT SỐ ỨNG DỤNG CỦA BTĐNDựa vào các định lý và hệ quả nêu ở bài 1, ta có:@ Nếu P có hay không có PATU thì D cũng có hay khôngcó PATU và ngược lại.@ Nếu có PATU thì giá trị HMT tối ưu của 2 BT bằng nhau.1. Cách tìm lời giải bài toán đối ngẫu (D) từ BT (P)+ Thế PATU x0 của P vào các ràng buộc bấtđẳng thức trong các cặp ràng buộc đối ngẫu. Nếuràng buộc nào thoả mãn lỏng thì ràng buộc đốingẫu của nó trong D sẽ thoả mãn chặt và khi đóta lập được một hệ phương trình tuyến tính theocác ẩn của bài toán D. 1 CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 2: CÁCH GIẢI BÀI TOÁN ĐỐI NGẪU Ý NGHĨA VÀ MỘT SỐ ỨNG DỤNG CỦA BTĐN1. Cách tìm lời giải bài toán đối ngẫu (D) từ BT (P)+ Giải hệ phương trình tuyến tính trên để tìmnghiệm tương ứng.+ Thay nghiệm của hệ phương trình trên vào cácràng buộc còn lại của bài toán D. Khi đó, nhữngnghiệm của hệ phương trình tối ưu thoả mãn cácràng buộc còn lại của bài toán D chính là tậpphương án tối ưu của bài toán D. 2 1 CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 2: CÁCH GIẢI BÀI TOÁN ĐỐI NGẪU Ý NGHĨA VÀ MỘT SỐ ỨNG DỤNG CỦA BTĐNVí dụ: Cho bài toán P như sau: f ( x )  3 x1  x 2  2 x 3  x 4  max  x1  2 x 2  4 x 3  3 x 4  9 3 x  x  2 x  9  1 2 3  2 x  x  3 x  5 x  10  1 2 3 4   x  0 i  1,5  i a) Giải bài toán P.b) Viết BTDN D tương ứng và tìm nghiệm của D dựa vàonghiệm của P.c) Giải BTDN D tương ứng bằng PPĐH và nhận xét. 3 CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 2: CÁCH GIẢI BÀI TOÁN ĐỐI NGẪU Ý NGHĨA VÀ MỘT SỐ ỨNG DỤNG CỦA BTĐNa) Đưa bài toán P về BT “M” dạng chuẩn với 2 ẩn phụ x5và x6; 2 ẩn giả x7 và x8 như sau: f (x)  3x1  x2  2x3  x4  Mx7  Mx8 max x1  2x2  4x3  3x4  x5  x7  9 3x  x  2x  x  9  1 2 3 6 2x  x  3x  5x  x 10  1 2 3 4 8  x  0 i 1,8 i Hệ ẩn CB: x6, x7 và x8.PACB XP của BT “M”: x M  0, 0, 0, 0, 0, 9, 7, 10 4 2 CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 2: CÁCH GIẢI BÀI TOÁN ĐỐI NGẪU Ý NGHĨA VÀ MỘT SỐ ỨNG DỤNG CỦA BTĐN 5 CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 2: CÁCH GIẢI BÀI TOÁN ĐỐI NGẪU Ý NGHĨA VÀ MỘT SỐ ỨNG DỤNG CỦA BTĐN 6 3 CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 2: CÁCH GIẢI BÀI TOÁN ĐỐI NGẪU Ý NGHĨA VÀ MỘT SỐ ỨNG DỤNG CỦA BTĐNTại bước lặp thứ 5, ta có tất cả các HSUL của các ẩn củaBT “M” đều không âm cho nên BT “M” có PATU là  27 22 2  x *M   , , , 0, 0, 0, 0, 0   7 7 7 với trị số HMT đạt được là f(x*M) = 9 và do các ẩn giả đềunhận giá trị 0 cho nên BT gốc P có PATU là  27 22 2  x*   , , , 0  với trị số HMT đạt được  7 7 7  là f(x*) = 9. 7 CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 2: CÁCH GIẢI BÀI TOÁN ĐỐI NGẪU Ý NGHĨA VÀ MỘT SỐ ỨNG DỤNG CỦA BTĐNb) Bài toán đối ngẫu D của P được viết như sau: g ( y )  9 y1  9 y2  10 y3  min  y1  3 y2  2 y3  3 2 y  y  y  1  1 2 3  4 y1  2 y2  3 y3  2 3 y  5 y  1  1 3  y1  0, y2  0 8 4 CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 2: CÁCH GIẢI BÀI TOÁN ĐỐI NGẪU Ý NGHĨA VÀ MỘT SỐ ỨNG DỤNG CỦA BTĐN Các cặp ràng buộc đối ngẫu:x1  0 & y1  3 y 2  2 y3  3x2  0 & 2 y1  y 2  y3  1x3  0 &  4 y1  2 y 2  3 y3  2x4  0 & 3 y1  5 y3  1x1  2 x2  4 x3  3 x4  9 & y1  03 x1  x2  2 x3  9 & y2  0 9 CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 2: CÁCH GIẢI BÀI TOÁN ĐỐI NGẪU Ý NGHĨA VÀ MỘT SỐ ỨNG DỤNG CỦA BTĐNDựa vào định lý độ lệch bù yếu: 27x1   0  y1  3 y2  2 y3  3 7  y1  0 22 x2   0  2 y1  y2  y3  1   y 2  1 7 y  0 2x3   0   4 y1  2 y2  3 y3  2  3 7Vậy, PATU của BTĐN D là y* = (0, 1, 0) với trịsố hàm mục tiêu đạt được là g(y*) = 9. 10 5 CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 2: CÁCH GIẢI BÀI TOÁN ĐỐI NGẪU Ý NGHĨA VÀ MỘT SỐ ỨNG DỤNG CỦA BTĐNc) Giải bài toán D bằng phương pháp đơn hình: Đưa bài toán D về bài toán “M” dạng chuẩn như sau:g ( y )  9 y 1 9 y2  10 y3a  10 y b33  My8  My9  min y 1 3 y2  2 y 3a3  2 y3b  y4  y8  32 y 1  y2  y 33  y3  y5  1 a b4 y 1 2 y2  3 y 33  3 y3  y6  y9  2 a b3 y 1 5 y 33  5 y3  y7  1 a b  yi  0 i  1,9  11 CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 2: CÁCH GIẢI BÀ ...