Chương II: BÀI TOÁN ĐỐI NGẪU .I. Định toán đối ngẫu của bài toán chính bài toán QHTT (P) sau :. (1) f ( x ) = c1 x1 + c2 x2 + + cn xn min. a11 x1 + a12 x2 + + a1n xn = b1. a21 x1 + a22 x2 + + a2n xn = b2. (2). am1 x1 + am2 x2 + + amn xn = bm. (3) x j 0 j = 1, toán đối ngẫu của bt(P) là bt(Q) sau .đây: ( y ) = b y + b y + + b y. g m ax. 1 1 2 2 m m a11 y1 + a21 y2 + + am1 yn c1. a12 y1 + a22 y2 + + am2 yn c2. a1n y1 + a2n y2 + + amn yn cn. yi �R, i = 1, dụ: Thiết lập bt đối ngẫu của bt sau .đây:. f ( x) = x1 + 6 x2 + 9 x3 min. x1 + 2 x3 = 6. + x2 + x3 = 8. xj 0, j = 1, 2,. Bài toán đối ngẫu của bài toán . tổng quát. Bảng đối ngẫu (xem giáo trình):Bài toán gốc Chỉ số Bài toán đối ngẫu. f ( x ) = c, x min g ( y ) = ��. b, y max. n. aij x j bi i I1 yi 0. j =1. i I2. n. aij x j bi yi 0. j =1. n. aij x j = bi i I3 yi ﾡ. j =1. m. xj 0 j J1 aij yi cj. i =1. m. xj 0 j J2 aij yi cj. i =1. m. xj ﾡ j J3 aij yi = c j. i =1*PP ghi nhớ bảng đối ngẫu bằng cách sử . dụng cặp bài toán chuẩn sau đây:. f ( x ) min g ( y ) max. AX B, Y 0. X 0 AY nhớ bt chuẩn: .hàm mục tiêu bé thì ràng buộc lớn; .hàm muc tiêu lớn thì ràng buộc bé; .ẩn của 2 bài toán chuẩn đều không dùng: . mỗi một ràng buộc của bt này tương .ứng với một ẩn của bt kia và ngược lại, . mỗi một ẩn của bt này tương ứng với .một ràng buộc của bt kia và ngược lại;. Mỗi dấu hiệu của bt này ngược với .chuẩn thì tương ứng dấu hiệu của bt kia .cũng ngược với dụ: Viết bài toán đối ngẫu(Q) của bài .toán(P) sau đây: . f ( x) = 4 x1 + 3 x2 − 7 x3 min. 12 x1 + 5 x2 − 3 x3 5 (1). x1 − x3 2 (2). 2 x1 + x2 + x3 = 1 (3). x1 ; x2 ; x3 0 (4)2. Mối quan hệ giữa bài toán gốc và .bài toán đối lý 1. Với cặp bài toán (P)(Q) chỉ có .thể xảy ra ba khả năng sau:. + Cả 2 bt đều không có PA thì cả 2 bt .đều không có PATƯ +Một bt có PA còn bt kia không có PA .thì bt có PA sẽ không có PATƯ +Cả 2 bt đều có PA thì cả 2 bt đều có .PATƯ, hơn nữa GTTƯ của 2 bt là bằng . lý (Định lý độ lệch bù). Điều kiện .cần và đủ để x0, y0 lần lượt là PATƯ của .bt gốc và bt đối ngẫu là. �n �. � aij x j 0 − bi � i 0 = 0, i = 1, m. y. �=1. j �. m. � �. � aij yi 0 − c j � j 0 = 0. x j = 1, n �=1. i �Ví dụ 1: Cho bài toán QHTT. f ( x ) = x1 − 2 x2 + 2 x3 + 0 x4 min. x1 + x2 + 4 x4 = 6. ( P). + 2 x2 + x3 + 5 x4 = 8. xj 0, j = 1, 2,3, 4; x = (2, 4,0,0). phương án tối ưu là
