tailieunhanh - Bài giảng Tối ưu hóa: Chương 2 - ThS. Phạm Trí Cao

Chương 2 của bài giảng Tối ưu hóa trình bày về bài toán quy hoạch tuyến tính đối ngẫu. Chương này gồm có các nội dung chính như: Cách thành lập bài toán QHTT đối ngẫu, các định lý đối ngẫu. Mời bạn đọc cùng tham khảo. | ThS. Phạm Trí Cao Chương 2 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 X 2xọ 0x3 - 4x4 min 4x1 6xọ x3 x4 1680 X1 Xo - 5x3 2x4 2520 X1 2xo 2x3 3x4 2800 X1 0 x2 0 x3 0 x4 tùy ý 03 01 2014 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 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. Viết P dưới dạng ma trận f x 1 2 o 4 . x1 X2 X3 x4 min 1 1 6 1 2 1 - 5 2 2 3 J -v2 x3 r1680 2520 2800 X1 0 X2 o Xa 0 X4 tùy ý Bài toán đôi ngẫu P f y 1680 2520 28OO . yi y2 y3 max 6 1 1 1 - 5 2 2 2 3 2 3 ự 2 3j V 3 2 I-yi 0 y2 o ya tùy y r 1 2 2 o 4 1 ThS. Phạm Trí Cao Chương 2 Nhận xét Bài toán đốì ngẫu cũng là bài toán QHTT. Bài toán góc P có patư là x 21270 92 924 và fniin -3484 bài toán đô i ngẫu P có patư là y 47 70 -Tin -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 Quy tắc lập bài toán đốì ngẫu Qua 2 ví dụ trên ta có quy tắc lập bt đô i ngẫu như sau Hàm mục tiêu của bài toán gốc min max hàm mục tiêu của bài toán đối ngẫu max min . Véc tơ hệ số hàm mục tiêu của bài toán gốc trở thành véc tơ hệ số vế phải ràng buộc chung của bài toán đối ngẫu. Véc tơ hệ số vế phải ràng buộc chung của bài toán gốc trở thành véc tơ hệ số hàm mục tiêu của bài toán đối ngẫu. Ma trận hệ số của bài toán gốc lấy chuyển vị trở thành ma trận hệ số của bài toán đối ngẫu. 03 01 2014 Bài toán gốc 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 đốì 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 đốì ngẫu. Cách nhớ bạn đọc nên thuộc lòng 2 câu thần chú Bài toán gốc min ràng buộc chung cùng dấu ràng buộc biến trái dấu. Bài toán gốc max ràng buộc chung trái dấu ràng Qbuộc biến cùng dấu. 2 ThS. Phạm Trí Cao Chương 2 Quỵ tắc về dấu được cho trong bảng sau Gốc min ĐỐINGẪU max Ràng buộc chung 1 II II A V II 0 0 tùy ý .