Bài giảng Quy hoạch tuyến tính: Chương 2 - ĐH Tôn Đức Thắng

Nội dung chính của chương 2 Lý thuyết đối ngẫu thuộc bài giảng Quy hoạch tuyến tính nhằm trình bày về 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; chương pháp đơn hình đối ngẫu, mời các bạn tham khảo bài giảng để hiểu sâu hơn về lý thuyết đối ngẫu.
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 - Đ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 MaMH: 501014 Chương 2: ...