Uploaded byTrang Thuy Pham Show 0% found this document useful (0 votes) 3K views 26 pages Copyright© Attribution Non-Commercial (BY-NC) Available FormatsPPT, PDF, TXT or read online from Scribd Share this documentDid you find this document useful?Is this content inappropriate?0% found this document useful (0 votes) 3K views26 pages Bài toán đối ngẫuUploaded byTrang Thuy Pham Jump to Page You are on page 1of 26 Search inside document Reward Your CuriosityEverything you want to read. Anytime. Anywhere. Any device. No Commitment. Cancel anytime.  Chương 2.BÀI TOÁN ĐỐI NGẪU 2.1 Giới thiệu bài toán QHTT đối ngẫu Bài toán mở đầu. Các sinh viên thường mua thức ăn nhẹ ở một cửa hàng gần trường đại học. Cửa hàng gần trường cung cấp hai loại thức ăn nhẹ là bánh hạnh nhân socola và kem socola. Mỗi bánh hạnh nhân có giá 2 đô và mỗi cây kem có giá 1 đô. Mỗi bánh hạnh nhân chứa 4 ounces socola và 3 ounces đường, mỗi cây kem chứa 3 ounces socola và 2 ounces đường. Nhu cầu dinh dưỡng tối thiểu của mỗi sinh viên là 8 ounces socola và 11 ounces đường. Xác định số lượng bánh hạnh nhân và số lượng cây kem mà mỗi sinh sẽ mua để đáp ứng nhu cầu dinh dường tối thiểu và chi phí là thấp nhất (xem Ví dụ 3). Gọi x1; x2lần lượt là số bánh và kem cần mua. Bài toán trên được mô hình toán thành bài toán qui hoạch tuyến tính như sau: (P) : f(x) \= 2x1+x2!min 8 < : 4x1+ 3x28 3x1+ 2x211 x10; x20: Bài toán trên có thể được giải bằng phương pháp đơn hình (mở rộng) sau khi đã bài toán đã được chuyển về dạng chuẩn. Tuy nhiên, với thông tin từ đề bài ta có thể xét một bài toán qui hoạch tuyến tính đối ngẫu của bài toán trên. Các thông tin về phương án tối ưu và giá trị tối ưu của bài toán đối ngẫu sẽ cho phép ta suy ra phương án tối ưu và giá trị tối ưu của bài toán ban đầu. Với thông tin về giá trị dưỡng chất và giá bán mỗi bánh hạnh nhân và cây kem ở trên, nhà cung cấp nguyên liệu cần xác định giá bán mỗi ounce socola và mỗi ounce đường là bao nhiêu để doanh thu đạt lớn nhất nhưng vẫn đảm bảo chủ cửa hàng bán bánh và kem theo giá đã định? Khi đó, nhà cung cấp nguyên liệu sản xuất bánh và kem cần lập mô hình bài toán qui hoạch tuyến tính cho bài toán doanh thu đạt cực đại như sau: Gọi y1; y2lần lượt là giá bán mỗi ounce socola và đường Hàm mục tiêu sẽ là: g(y) \= 8y1+ 11y2!max Chi phí để tạo ra một bánh hạnh nhân phải dưới 2 đôla, nếu không chủ cửa hàng sẽ không mua nguyên liệu từ nhà cung cấp, vì chủ cửa hàng có nguy cơ thua lỗ nếu sinh viên mua bánh hạnh nhân. Do đó, ta có ràng buộc chính thứ nhất: 4y1+ 3y22. Tương tự, chi phí để tạo một muỗng kem sôcôla phải có giá dưới 1 đô la ta nên có thêm ràng buộc chính thứ hai: 3y1+ 2y21. Khi đó, ta có bài toán qui hoạch tuyến tính (cho nhà cung cấp nguyên liệu) như sau (D) : g(y) \= 8y1+ 11y2!max 8 < : 4y1+ 3y22 3y1+ 2y21 y10; y20: Cặp bài toán (P) và (D) ở trên được gọi là được gọi là cặp bài toán đối ngẫu. Cặp bài toán trên có thể được mở rộng cho trường hợp nhiều biến như sau: (P) : f(x) \= c1x1+::: +cnxn!min (D) : g(y) \= b1y1+::: +bmym!max a11x1+a12 x2+::: +a1nxnb1a11y1+a21 y2+::: +am1ymc1 a21x1+a22 x2+::: +a2nxnb2a12y1+a22 y2+::: +am2ymc2 ::::::::::::::::::::::::::::: ::::::::::::::::::::::::::::: am1x1+am2x2+::: +amnxnbma1ny1+a2ny2+::: +amnyncn xj0; j \= 1; n: yi0; i \= 1; m: 1 Why is this page out of focus?This is a Premium document. Become Premium to read the whole document. Why is this page out of focus?This is a Premium document. Become Premium to read the whole document. |
