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

Tham khảo tài liệu 'chương 1: bài toán quy hoạch tuyến tính - bài 5', 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ả | CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH Nội dung cơ bản của pp đơn hình 1 2 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH O BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH Xét BT QHTT dạng chuẩntắcnhư sau n f x V cixi max min n m __ _ Xk Vv bk k 1 tmj 1 n - m j 1 xi 0 bk 0 i 1n k 1 m m n 1 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 1. Ướclượng của ẩn PACB xpL x x0 x xm 0 - 0 hay x b ỉ m .J0 VớihệẩnCB x1 x2 . xm m __ Ai sckaki -ci m 1n k Đượcgọi làhệ sôướclượng của ẩnx. 3 2 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH O BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 2. Dấuhiệutối ưucủa bài toán A i f x cixi max f x cixi min A l 0 Vl í m 1 n Có PATU Al 0 Vl e m 1 n Có PATU Chú ý Khi có dấuhiệutối ưumàtồntạiítnhấtl hệ số ước lượng bằng 0 của ẩn không cơ bản thì bài toán có thể có nhiềuhơn1 phương án tối ưu. 4 2 2 chương I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 3. Định lý cơ bản Nếu trong 1 phương án cơ bảncủa bài toán mà3A 0 đốivới bài toán cực đại hay Ạ 0 đốivới bài toán cựctiểu của ẩn không cơ bảnthì sẽ xảy ra 1 trong hai trường hợp sau a Nếucómộthệ sốướclượng mà mọi akỉ 0thì bài toán không giải được. b Nếuvớimỗihệ sốướclượng mà tồntạiítnhấtmột ữfcl 0 thì bài toán có phương án cơ bảnmớitốthơn. 5 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HINH 4. Thuậttoán đơnhìnhgiải BTQHTT dạng chuẩntắc ÀrGiảiBT cực đại a Bướclặpthứ nhất Xác định ẩn CB PACB xuất phát x0 và giá trị f x0 của hàm mụctiêutại PACB này. Lậpbảng đơnhình BDH xuất phát như sau Hệ Ấn cơ Phương X1 x2 . xm Xm 1 Xn số bản án cơ bản C1 c2 -111 -111 1 cn C1 X1 bi 1 0 . . 0 alm l am c2 x2 b2 0 1 . . 0 a 2111 1 211 . 0 -111 Xm bm 0 0 . . 1 amm l a mn f x f x 0 0 . . 0 A 11 - A 6