Chương 1: Bài toán quy hoạch tuyến tính - bài 2

Tài liệu tham khảo về bài toán quy hoạch toán tính...
Nội dung trích xuất từ tài liệu:
Chương 1: Bài toán quy hoạch tuyến tính - bài 2 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 2. CÁC KHÁI NIỆM CƠ BẢN 1. Định nghĩa BTQHTT nn f ( x )   cii xii  max (min) (1) ii11  nn        a ijij x ii    b jj ( j  1, m ) (2)  ii11        0   x   0  ( i  1, n ) (3)  ii     tuy y   1 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 2. CÁC KHÁI NIỆM CƠ BẢN 2. Các khái niệm liên quan @ Phương án của bài toán @ Tập phương án @ Thoả mãn chặt @ Thoả mãn lỏng @ Phương án cơ bản 2 1 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 2. CÁC KHÁI NIỆM CƠ BẢN 2. Các khái niệm liên quan @ Phương án tối ưu @ Phương án cơ bản tối ưu @ Bài toán giải được @ Bài toán không giải được 3 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 2. CÁC KHÁI NIỆM CƠ BẢN 2. Các khái niệm liên quanVd 1: f ( x)  2 x  x  3x  x  max 1 2 3 4  x1  2 x2  x3  4 2 x  x  3 x  4  1 2 4   x2  2 x3  x4  1  x1 , x2 , x3 , x4  0 4 2 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 2. CÁC KHÁI NIỆM CƠ BẢN 2. Các khái niệm liên quanGiải hệ ràng buộc của bài toán, ta có tập phương án:  29 7 5 2 1    29 X    ,  ,  ,   0,   12 6 6 3 12 6   14  29 5 1  LÀKHÔNG PACB & LÀ PACB   0 x 0   , , , 0  SUY BẾN  12 6 12   1 13 5  LÀ PA NHƯNG  2 x*   , , , 2 KHÔNG LÀ PACB  12 6 12  5 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 2. CÁC KHÁI NIỆM CƠ BẢN 2. Các khái niệm liên quanVới tập phương án X, ta có hàm mục tiêu như sau: 65 7   29  f (x)    max  0,   12 6   14  65 7 65  29 f ( x)     f ( x0 )   0, 12 6 12  14  65 x0 là PACB tối ưu; f ( x )  là giá trị tối ưu; 0 12 6 3 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 2. CÁC KHÁI NIỆM CƠ BẢN 2. Các khái niệm liên quan Câu hỏi: Hãy xét & nhận xét các PA ứng với các giá trị:  1   3/ 2 7 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 2. CÁC KHÁI NIỆM CƠ BẢN 2. Các khái niệm liên quan Vd2: Xét bài toán (F) trên nhưng không có hệ ràng buộc dấu, tức là các ẩn có dấu tuỳ ý. Khi đó, tập phương án của bài toán sẽ là:  29 7 5 2 1   X    ,  ,  ,    12 6 6 3 12 6  65 7 f (x)    max 12 6     f (x )   BT KHÔNG CÓ PATU BT KHÔNG GIẢI ĐƯỢC 8 4 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 2. CÁC KHÁI NIỆM CƠ BẢN 3. Tính chất cơ bản của BTQHTT Tính chất 1: Nếu có PA thì sẽ có PACB & số PACB là hữu hạn. Tính chất 2: @ Nếu f(x)max có PA & f(x) bị chặn trên thì có PATU. @ Nếu f(x)min có PA & f(x) bị chặn dưới thì có PATU. Tính chất 3: Nếu có PATU thì có PACBTU Tính chất 4: Nếu có hơn 1 PATU thì có vô số PATU. x  x0  (1   ) x*;  0, 1 9 5 ...