Bài giảng Quy hoạch tuyến tính - Chương 2: Lý thuyết đối ngẫu (ĐH Tôn Đức Thắng)

Bài giảng "Quy hoạch tuyến tính - Chương 2: Lý thuyết đối ngẫu" cung cấp cho người học các kiến thức: Bài toán đối ngẫu quy hoạch tuyến tính (xây dựng bài toán đối ngẫu, các định lý đối ngẫu), phương pháp đơn hình đối ngẫu. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Quy hoạch tuyến tính - Chương 2: Lý thuyết đối ngẫu (ĐH Tôn Đức Thắng) Chương 2 LÝ THUYẾT ĐỐI NGẪU20/6/2012 MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 1 NỘI DUNG1. Bài toán đối ngẫu quy hoạch tuyến tính 1.1 Xây dựng bài toán đối ngẫu 1.2 Các định lý đối ngẫu2. Phương pháp đơn hình đối ngẫu20/6/2012 MaMH: 501014 Chương 2: Lý thuyết đối ngẫu 2 Bài toán đối ngẫu QHTT1. Xây dựng bài toán đối ngẫu QHTTXét bài toán n f ( x ) = ∑ c j x j → min j =1 n ∑ aij x j ≥ bi , i = 1, m (P )  j =1  x ≥ 0, j = 1, n.  j20/6/2012 MaMH: 501014 Chương 2: Lý thuyết đối ngẫu 3 Bài toán đối ngẫu QHTTBài toán đối ngẫu của bài toán trên là m g ( y ) = ∑ bi y i → max i =1 m ∑ aij y i ≤ c j , j = 1, n (D )  i =1  y ≥ 0, i = 1, m.  i20/6/2012 MaMH: 501014 Chương 2: Lý thuyết đối ngẫu 4 Bài toán đối ngẫu QHTTNhận xét:• Cả hai bài toán đều ở dạng chuẩn tắc;• Một bài toán min, một bài toán max;• Số biến của bài toán này là số ràng buộc của bài toán kia và ngược lại;• c j và bi đổi vai trò cho nhau.20/6/2012 MaMH: 501014 Chương 2: Lý thuyết đối ngẫu 5 Bài toán đối ngẫu QHTTVí dụ 1 Lập bài toán đối ngẫu của bài toán sau f ( x ) = 3 x1 + 2 x2 + 5 x3 → min −2 x1 + x2 + 4 x3 ≥ 6   x1 − 5 x2 + 2 x3 ≥ 8  x ≥ 0, j = 1,2,3  j20/6/2012 MaMH: 501014 Chương 2: Lý thuyết đối ngẫu 6 Bài toán đối ngẫu QHTTf ( x ) = 3 x1 + 2 x2 + 5 x3 → min −2 x1 + x2 + 4 x3 ≥ 6  (P )  x1 − 5 x2 + 2 x3 ≥ 8  x ≥ 0, j = 1,2,3  j 1,2, 3 g ( y ) = 6 y1 + 8 y 2 → max −2y1 + y 2 ≤ 3   y1 − 5 y 2 ≤ 2 (D )   4 y1 + 2y 2 ≤ 5  y ≥ 0, y ≥ 0  1 220/6/2012 MaMH: 501014 Chương 2: Lý thuyết đối ngẫu 7 Bài toán đối ngẫu QHTTQuy tắc lập bài toán đối ngẫuBài toán gốc (đối ngẫu) Bài toán đối ngẫu (gốc)Biến: x1, x 2 ,..., x n Biến: y 1, y 2 ,..., y mHàm mục tiêu: Hàm mục tiêu: n m f ( x ) = ∑ c j x j → min g ( y ) = ∑ bi y i → max j =1 i =1Ràng buộc: Dấu của biến: ≥ bi , i ∈ I1 ≥ 0, i ∈ I1 n ∑a x j =1 ij j = bi , i ∈ I2 y i ∈ ℝ, i ∈ I2 ≤ bi , i ∈ I3 ≤ 0, i ∈ I3 20/6/2012 MaMH: 501014 Chương 2: Lý thuyết đối ngẫu 8 Bài toán đối ngẫu QHTTQuy tắc lập bài toán đối ngẫu (tt)Bài toán gốc (đối ngẫu) Bài toán đối ngẫu (gốc)Dấu của biến: Ràng buộc: ≥ 0, j ∈ J1 ≤ c j , j ∈ J1 m x j ∈ ℝ, j ∈ J 2 ∑a y i =1 ij i = c j , j ∈ J2 ≤ 0, j ∈ J3 ≥ c j , j ∈ J3 20/6/2012 MaMH: 501014 Chương 2: Lý thuyết đối ngẫu 9 Bài toán đối ngẫu QHTTVí dụ 2 Lập bài toán đối ngẫu của bài toán sau f ( x ) = 2 x1 + x2 + 7 x3 → min 3 x1 + 5 x2 − 4 x3 ≥ 1   2 x1 − x2 + 2 x3 = 4 (P )   x1 + 2 x2 + 6 x3 ≤ 8  x ≥ 0, x ≤ 0, x ∈ ℝ  1 2 320/6/2012 MaMH: 501014 Chương 2: Lý thuyết đối ngẫu 10Bài toán đối ngẫu của bài toán trên: g ( y ) = y1 + 4 y 2 + 8 y 3 → max  3 y1 + 2y 2 + y 3 ≤ 2   5 y1 − y 2 + 2 y 3 ≥ 1 (D )   −4 y 1 + 2 y 2 + 6 y 3 = 7  y ≥ 0, y ∈ ℝ, y ≤ 0  1 2 320/6/2012 MaM ...