TAILIEUCHUNG - 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. | Chương 4. BÀI TOÁN QUY HOẠCH TUYEN TÍNH ĐỐI NGẪU VÀ THUẬT TOÁN ĐÌN HÌNH ĐỐI NGẪU . Bài toán quy hoạch tuyến tính đối ngẫu Định nghĩa Bài toán đối ngẫu . Cho các bài toán quy hoạch tuyến tính f x CTx min Áị x bi i 2 M1 AT x 6 bi i 2 M2 a ATx bi i 2 M3 8 xj 0 j 2 N1 xj 6 0 j 2 N2 xj 2 R j 2 N3 g x bTy max yi 0 i 2 M1 yi 6 0 i 2 M2 b yi 2 R i 2 M3 yTAJ 6 Cj j 2 N1 yTAJ Cj j 2 N2 yTAJ Cj j 2 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. 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àng buộ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ều của bất đẳng thức có quan hệ với nhau thể hiện ở bảng sau Góc min max Đối ngẫu bi 2 R Ràng buộc bi 0 Biến bi 0 0 Ci Biến 0 Ci Ràng buộc 2 R Ci Ví dụ . 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 f x X1 x2 3x3 min g y 5yi 6y2 4y3 max xi 3x2 5 a 2x1 x2 3x3 6 x3 6 4 y2 0 y3 6 0 -yi 2y2 6 1 b 3yi -y2 1 3y2 y3 3 X1 0 x2 6 0 Nhận xét . Quan hệ đối ngẫu giữa các bài toán quy hoạch tuyến tính có tính chất đối xứng. Định lý Đối ngẫu yếu . Nếu X y lần lượt là phương án của bài toán quy hoạch tuyến tính gốc và đối ngẫu thì g y f x . Chứng minh. Ta đặt Ui yi AT x - bi i 1 . m . Tj 4X1 Vj Cj - y Aj xj j 1 . n Theo định nghĩa bài toán đối ngẫu thì yi và ATx bi cùng dấu Cj yTAj và xj cùng dấu. Do đó ui 0 và Vj 0 với mọi i j. Ta có m X Ui yTAx - yTb i 1 n X Vj CT x yT Ax j i Do đó 0 6 P Ui P Vj cTX - yTb f x - g y g y 6 f x Hệ quả . Giả sử X y là phương án của bài toán gốc và đối ngẫu. Nếu f x g y thì X y lần lượt là phương án tối ưu của bài toán gốc và đối ngẫu. Chứng minh. Đối với mọi X y là phương án bài toán gốc và đối ngẫu thì g y f x g y f x . Chứng tỏ tính tối ưu của X ỹ. Định lý Đối ngẫu mạnh . Một cặp bài toán đối ngẫu nếu bài toán này có phương án tối ưu thì bài toán kia cũng có phương án tối ưu và giá tri tối ưu của .

• Toán học
• thuật toán đơn hình đối ngẫu
• vấn đề tìm phương án cực biên
• vấn đề hậu tối ưu
• bài tập quy hoạch tuyến tính
• tài liệu học đại học
• Bài giảng Quy hoạch tuyến tính
• Quy hoạch tuyến tính
• Bài toán đối ngẫu
• Thành lập bài toán đối ngẫu
• Định lý đối ngẫu
• Bài toán quy hoạch tuyến tính
• Tập phương án tối ưu
• Phương pháp đơn hình
• Quy hoạch tuyến tính đối ngẫu
• Thuật toán thế vị
• Bài toán vận tải và thuật toán thế vị
• Thuật toán đơn hình
• Bài toán vận tải
• Bài giảng Tính toán khoa học
• Khoa học máy tính
• Tính toán khoa học
• Lý thuyết đối ngẫu
• Bài giảng Tính toán khoa học chương 8
• Giải thuật đơn hình
• Ứng dụng quy hoạch tuyến tính
• ôn thi cao đẳng
• Đề thi thử đại học môn toán năm 2012
• đề thi toán đại học
• tài liệu luyện thi đại học
• bài tập trắc nghiệm
• cấu trúc đề thi đại học
• ngân hàng đề thi trắc nghiệm
• tài liệu ôn thi đại học
• bộ đề thi đại học
• đề thi thử đại học
• tuyển sinh đại học cao đẳng
• các đề thi đại học