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

Tài liệu tham khảo về bài toán đối ngẫu...
Nội dung trích xuất từ tài liệu:
Chương 2: Bài toán đối ngẫu - bài 1 CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 1.1 BTDN (D) của BT gốc (P) dạng chính tắc: 1 CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 1. Định nghĩa bài toán đối ngẫuVí dụ: Viết BTDN D của BTQHTT (P) sau: f ( x )  3 x1  2 x2  5 x3  x4  min2 x1  4 x2  3 x3  7 x4  9x  2x  4x  5x  5 1 2 3 43 x1  x2  2 x3  2  x  0 i  1,4 i  2 1 CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 1. Định nghĩa bài toán đối ngẫuBài toán D được viết như sau:f ( x )  3 x1  2 x2  5 x3  x4  min2 x1  4 x2  3 x3  7 x4  9x  2x  4x  5x  5 1 2 3 4 g ( y )  9 y1  5 y2  2 y3  max3 x1  x2  2 x3  2  x  0 i  1,4 i  2 y1  y2  3 y 3  3   4 y1  2 y2  y3  2  3 y1  4 y2  2 y3  5  7 y1  5 y2  1 3 CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 1. Định nghĩa bài toán đối ngẫuBài toán D được viết như sau: g ( y )  9 y1  5 y 2  2 y 3  max 2 y1  y 2  3 y 3  3 4 y  2 y  y  2 1 2 3 3 y1  4 y 2  2 y 3  5  7 y1  5 y 2  1 4 2 CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 1.2 BTDN (D) của BT gốc (P) ở dạng tổng quát bất kỳ:Ví dụ: Viết bài toán đối ngẫu của bài toán sau:f ( x)  2 x1  12 x2  7 x3  3 x4  min2 x1  4 x2  3 x3  7 x4  9x  2 x  4 x  5x  5 1 2 3 43 x1  x2  2 x3  2 x1 , x3  0; x4  0 5 CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 1.2 BTDN (D) của BT gốc (P) ở dạng tổng quát bất kỳ:  x2  x2a  x2b   x4   x4 *  a b *  x2 , x2 , x4  0 6 3 CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 1.2 BTDN (D) của BT gốc (P) ở dạng tổng quát bất kỳ:f (x)  2x1 12xa2 12x2b  7x3  3x*4  0.x5  0.x6 min2x1  4xa2  4x2b  3x3  7x*4  x5  9x1  2x2  2x2  4x3  5x4  x6  5 a b *  3x1  x2  x2  2x3  2 a b  xi  0 i 1,3,5,6; x2 , x2 , x4  0 a b * 7 CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 1.2 BTDN (D) của BT gốc (P) ở dạng tổng quát bất kỳ:g ( y )  9 y11  5 y 22  2 y33  max2 y11  y 22  3 y 33 2 4 y  2 y  y  12 g ( y )  9 y11  5 y 22  2 y33  max 11 22 33 2 y11  y 22  3 y 33 24 y11  2 y 22  y33  12 4 y  2 y  y  12  11 22 333 y11  4 y 22  2 y33  7 3 y11  4 y 22  2 y33  7 7 y  5 y  3  7 y11  5 y 22  3 11 22 y11  0  y11  0  y 22  0  y 22  0 8 4 CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN2. Cách lập bài toán đối ngẫu 9 CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN2. Cách lập bài toán đối ngẫu 10 5 CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN2. Cách lập bài toán đối ngẫu“Câu thần chú”:Max  Min Ràng D cùng dấu hoặc “bằng” ẩn P; Ẩn D thì trái ràng P hoặc tuỳ.Min  Max Ràng D thì trái hoặc “bằng” ẩn P; Ẩn D cùng dấu ràng P hoặc tuỳ. 11 CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN2. Cách lập bài toán đối ngẫuVí dụ: Lập bài toán đối ngẫu của bài toán sau: f ( x)  4 x2  3 x3  x5  max 2 x1  3 x2  x3  x4  8 5 x  x  2 x  x  5  2 3 4 5  x  4 x  3x  5 x  6  2 3 4 5   x  0 i  1,5  i  12 6 CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 2. Cách lập bài toán đối ngẫuCách 1: Đưa bài toán trên về dạng chính tắc: f ( x)  0 x1  4 x2  3x3  0 x4  x5  0 x6  max2 x1  3x2  x3  x4  85 x  x  2 x  x  5 2 3 4 5 x  4 x  3x  5 x  x  6 2 3 4 5 6  x  0 i  1,6 i  13 CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC K ...