Chương 4: Bài toán quy hoạch tuyến tính đối ngẫu và thuật toán đơn hình đối ngẫu

Thuật toán đơn hình đối ngẫu là thuật toán đơn hình áp dụng vào giải toán đối ngẫu của quy hoạch tuyến tính đã cho nhưng các bước tiến hành lại được diễn tả trên bài toán gốc. Sau đây ta tìm hiểu nội dung của thuật toán đơn hình đối ngẫu.
Nội dung trích xuất từ tài liệu:
Chương 4: Bài toán quy hoạch tuyến tính đối ngẫu và thuật toán đơn hình đối ngẫuQuy ho ch tuy n tính Trư ng ĐHSP Đ ng ThápChương 4.BÀI TOÁN QUY HO CH TUY NTÍNH Đ I NG U VÀ THU T TOÁNĐƠN HÌNH Đ I NG U4.1. Bài toán quy ho ch tuy n tính đ i ng uĐ nh nghĩa 4.1.1 (Bài toán đ i ng u). Cho các bài toán quy ho ch tuy n tính: f (x) = cT x → min g (x) = bT y → max    AT x bi ; i ∈ M1 0 , i ∈ M1  yi i        AT x b ;i ∈ M 0, i ∈ M y i 2 i 2 i     T (a)  Ai x = bi ; i ∈ M3 (b)  yi ∈ R , i ∈ M3     y T AJ 0 ; j ∈ N1 cj , j ∈ N1  xj         y T AJ 0 ; j ∈ N2 cj , j ∈ N2 xj       y T AJ = cj , j ∈ N3   xj ∈ R; j ∈ N3  Ngư i ta g i bài toán (a) là bài toán g c và (b) là bài toán đ i ng u. Trong đó AT là véc tơ dòng i c a ma tr n A, Aj là véc tơ c t j c a ma tr m A. i M i ràng bu c b t đ ng th c c a bài toán này ng v i m t bi n trong ràngbu c v d u c a bài toán kia, g i là c p ràng bu c đ i ng u. Đ ng th i các chi uc a b t đ ng th c có quan h v i nhau th hi n b ng sau: 42Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp Góc min max Đ i ng u ∈R = bi Ràng bu c ≤ bi ≤0 Bi n ≥ bi ≥0 ≥0 ≤ ci ≤0 ≥ ci Ràng bu c Bi n ∈R = ciVí d 4.1.2. Xét quy ho ch tuy n tính bên trái và bài toán đ i ng u bên ph i,các bài toán sau: g (y ) = 5y1 + 6y2 + 4y3 → max f (x) = x1 + x2 + 3x3 → min    −x1 +3x2  −y1 +2y2 =5 1        (a) (b) −x2 − y2 2x1 +3x3 6 3y1 1       x3 4 3y2 +y3 = 3  ...