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 f (x) = cii xii  max (min) (1) iii=1    aiiiijjjj xiiii  bjjjjj ( j = 1,m) (2) iiiii=1 =   0  xiiiii  0  (i = 1,n) (3)  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 quan Vd 1: f (x)=2x + x2 −3x3 + x4 max x1 + 2x2 − x3 = 4 2x1 − x2 +3x4 = 4 x2 + 2x3 − 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 quan Giải hệ ràng buộc của bài toán, ta có tập phương án: X = 12− 6 ,6+ 3 ,12+ 6, ∈0, 14 + = 0 0  29 12 5, 1 LÀ PACB & LÀ PACB KHÔNG SUY BẾN 12  + =2 x* =12, 13 5 6 12 2 LÀ PA NHƯNG KHÔNG LÀ PACB 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 quan Với tập phương án X, ta có hàm mục tiêu như sau: f(x)=12− 6 max ∈0,, 29 14 65 7 65 0 12 6 12 ∀∈0, 29 14 x0 là PACB tối ưu; f (x0 ) = 65là giá trị tối ưu; 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à: X = 12 − 7 ,6 + 2 ,12 +  , f (x) = 65 − 76  max  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=x00 +((1−))x**;; ∈ 0,, 1 9 5 ... - tailieumienphi.vn