tailieunhanh - Chuong 2 Bg (Bai toan QHTT doi ngau)

| ThS. Phạm Trí Cao Chương 2 Bt QHTT đối ngẫu TC CHƯƠNG 2 BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐỐI NGAU Ví dụ Bài toán gốc P f x xx 2x2 0x3 - 4x4 - min 4xj 6x2 x3 x4 1680 X x2 5x3 2x4 2520 X 2x2 2x3 3x4 2800 xx 0 x2 0 x3 0 x4 tùy ý LƯU ý Biến tùy ý có thể không ghi ra 13 08 2015 I CÁCH THẬNH LẬP BÀI TOÁN QHTT ĐỐI NGẪU Để lập bài toán QHTT đô i ngẫu được đơn giản không bị sai về số và dấu ta nên chuyển bài toán về dạng ma trận bằng cách tách các giá trị số và biến riêng ra. Ịjẩu ý Viết bài toán đối ngẫu sai 1 con sô hoặc 1 dấu cũng là sai. Viết P dlfcfi dạng ma trận 1 ThS. Phạm Trí Cao Chương 2 Bt QHTT đối ngẫu TC Nhân xét Bài toán đối ngẫu cũng là bài toán QHTT. Bài toán gốc P có patư là x 212 0 92 924 và fmin -3484 bài toán đối ngẫu P có patư là y 47 70 -27 70 -91 70 và fmax -3484. Các cặp ràng buộc đốì ngẫu là các cặp ràng buộc có dạng bất đẳng thức. Viết các cặp ràng buộc đối ngẫu cho 13 08 2015 Cặp bài toán trên có 7 cặp ràng buộc trong đó có 5 cặp ràng buộc đối ngẫu dạng bất đẳng thức . 4x1 6x2 x3 x4 1680 - yx Q xx x9 - 5x3 2x4 2520 -o- y9 x1 0 Ì4y1 y2 y3 l x2 0 - 6yJ y2 2y3 2 x3 0 - yj-5yị 2yj 0 Các cặp ràng buộc đôi ngẫu 3x1 x2 7x3 20-o y 0 x ÕXọH- x3 oy2 0 X1 0 4 3y y2 4y 17 x3 0 - 7y3 y2 y3 4 Bài toán goc P có patưlà X 0 13 1 và fmax l 34- bài toán đốỉ ngẫu P có patư là v 1 10 0 33 10 và fjn 134. 2 ThS. Phạm Trí Cao Chương 2 Bt QHTT đối ngẫu TC Lưu ý Nếu ta coi P là bài toán gốc thì P là bài toán đôi ngẫu tương ứng. Nghĩa là đôi ngẫu của bài toán đôi ngẫu sẽ là bài toán gốc P p. Dấu một ràng buộc chung của bài toán gốc quy định dấu một ràng buộc biến tương ứng của bài toán đối ngẫu. Dấu một ràng buộc biến của bài toán gốc quy định dấu một ràng buộc chung tương ứng của bài toán đối ngẫu. Cách nhớ bạn đọc nên thuộc lòng 2 câu thần chú Bài tocin gốc min ràng buộc chung cùng dấu ràng buộc biến trciỉ dấu. Bài tocin gốc max ràng buộc chung trciỉ dấu ràng Q buộc biến cùng dâu. Ngược lại với bài toán min 13 08 2015 Quy tắc lập bài toán đốì ngẫu Qua 2 ví dụ trên