mở đầu, gọi x và y lần lượt là số kilôgam sản phẩm loại I và loại II cần sản xuất. a) Ki hiéu F(x; y) la lợi nhuận của xí nghiệp khi sản xuất x kg sản phẩm loại I và y kg sản phẩm loại II. Viết biểu thức tinh F(x; y) theo x va y. b) Lập hệ bắt phương trình bậc nhát hai ẳn ràng buộc x va y thoả mãn yêu cầu của bài toán.
c) Biểu diễn trên mặt phẳng toạ độ đề tháy rằng miền nghiệm của hệ bát phương trình tìm được trong ý b là một miền tứ giác. Tìm toạ độ các đỉnh của miền tứ giác này. d) Tinh giá trị của F(x; y) tại các đỉnh của miền tứ giác tìm được trong ý b, từ đó dự đoán về mức lợi nhuận cao nhát. Trong thực tiễn, ta thường gặp bài toán sau: Tìm giá trị lớn nhát (tương ứng, giá trị nhỏ nhát) của biểu thức F(x; y) = Ax + By trên miền nghiệm S của một hệ bắt phương trình bậc nhát hai an: ax+by<c, a,x +b,y Sc, Se (1) a,X+b,y<c, ở đó A, B là hai số thực cho trước, không đồng thời bằng 0.
Các bài toán như vậy gọi là bài toán quy hoạch tuyến tính hai biến. Biểu thức F(x; y) & trên gọi là hàm mục tiêu. Chúý a) Mỗi bát phương trình trong hệ (1) gọi là một ràng buộc. Nếu (xạ; ⁄¿) là một nghiệm của hệ (1) thì ta nói h8) là một phương án chấp nhận được hoặc phương án khả thi của bài toán.
Tập các phương án cháp nhận được còn gọi là miền chấp nhận được. Nếu F(; y) đạt giá trị lớn nhất (tương ứng, giá trị nhỏ nhát) trên miền nghiệm S tại (x;;Vo) thì cặp (x;;ya) gọi là một phương án tối ưu của bài toán và giá trị F(xạ,y„) gọi là giá trị tối ưu. b) Bài toán quy hoạch tuyến tính trên được kí hiệu như sau: F(x:y) = Ax + By > max (min) với các ràng buộc ax+by<c, a,X+b,y <c, a,X+b,y <C,. c) Trong hệ (1), một số ràng buộc có thể được viết dưới dạng ax + by > c.
Một công ty sản xuất hai loại thực phẩm X, Y. Nguyên liệu để sản xuất gồm ba loại là bột, đường và dâu thực vật, với lượng dự trữ tương ứng là 15 tắn, 12 tắn, 10 tắn. Để sản xuất: + 1 tấn thực phẩm loại X cần 0,5 tấn bột, 0,5 tán đường, 0,2 tấn dầu thực vật; + _† tấn thực phẩm loại Y cần 0,6 tan bột, 0,3 tán đường, 0,5 tán dầu thực vật. Giá bán một tấn thực phẩm X là 100 triệu đồng, giá bán một tấn thực phẩm Y là 112 triệu đồng.
Hỏi cần sản xuất mỗi loại thực phẩm bao nhiêu tắn dé có doanh thu lớn nhất? Gọi x và y lần lượt là số tán thực phẩm X và Y cần sản xuát. a) Viết biểu thức F(x; y) biểu thị số tiền bán thực phẩm thu được theo x và y. b) Lập hệ bát phương trình bậc nhát hai an x va y biểu thị các ràng buộc của bài toán. c) Biểu diễn miền nghiệm của hệ bát phương trình tìm được trong ý b.
Tìm toạ độ các đỉnh của miền nghiệm và tính giá trị của F(x; y) tại các điểm đó. Giải a) F(x,y) =100x +112y triệu đồng. b) Số tấn bột để sản xuất x tắn thực phẩm X và y tắn thực phẩm Y là 0,5x +0,6y. Số tán đường để sản xuất x tán thực phẩm X và y tắn thực phẩm Y là 0,5x +0,3y.
Số tán dầu thực vật để sản xuất x tán thực phẩm X và y tắn thực phẩm Y là 0,2x + 0,5y. Vì lượng nguyên liệu sử dụng không vượt quá lượng dự trữ nên ta có hệ: 0,5x+0,6y <15 0,5x+0,3y <12 0,2x+0,5y <10 x>0,y>0. c) Tập các phương án cháp nhận được là miền ngũ giác tô màu trong Hình 2. Các đỉnh của miền nghiệm là: 0(0.
Xét bài toán: F(x;y)= 3x+ 2y — min với các ràng buộc x-y<†1 x+y>3 x20. a) Biểu diễn tập nghiệm của hệ các ràng buộc trên mặt phẳng toạ độ. b) Gọi A, B là giao điểm của đường thẳng d: x + y= 3 với đường thẳng đ“ x - y = 1 và trục Oy. Tinh gia tri F(x;y) tai các điểm A và B.
Giải a) Tập nghiệm của hệ các ràng buộc là miền không bị chặn được tô màu như trong Hình 2. b) Toạ độ giao điểm A của hai đường thẳng d và đ' là A(2; 1). Toạ độ giao điểm B của đường thẳng d và trục Oy là B(0; 3).2 + Trong Ví du 2, các điểm A, B cũng được gọi là “đỉnh” của miễn nghiệm S. + _ Nếu phương án chấp nhận được (xạ; yạ) là một đỉnh của miền nghiệm thì (xạ; yạ) được gọi là một điểm cực biên hoặc phương án cực biên.
Người ta dự định dùng hai loại nguyên liệu để chiết xuất ít nhát 140 kg chất X và 9 kg chất Y. Từ mỗi tấn nguyên liệu loại I giá 4 triệu đồng có thẻ chiết xuất được 20 kg chất X và 0,6 kg chất Y. Từ mỗi tắn nguyên liệu loại II giá 3 triệu đồng, có thể chiết xuất được 10 kg chat X và 1,5 kg chất Y. Cơ sở cung cấp nguyên liệu chỉ có thể cung cấp không quá 10 tán nguyên liệu loại I và không quá 9 tán nguyên liệu loại II.
Phải dùng bao nhiêu tắn nguyên liệu mỗi loại để chi phí mua nguyên liệu là ít nhất mà vẫn đáp ứng được các yêu cầu đặt ra ở trên? a) Dat an và viết bài toán quy hoạch tuyến tính diễn tả yêu cầu của bài toán trên. b) Biểu diễn tập các phương án chấp nhận được và tìm các phương án cực biên. BÃI TOÂN QUY HOẠCH TUYÊN TÍNH VỚI MIỄN CHÂP NHẬN ĐƯỢC LÀÂ MIỂN ĐA GIAC y `} u02. Ta giải bài toán trong Tình huống mở đầu.
Từ HĐ1 ta có bài toán quy hoạch tuyến tính sau: F(x;y) = 40x + 30y — max với các ràng buộc Phương án tối ưu x+2y <100 2x+y<80 x>0,y>0. Miền chấp nhận được S của bài toán là miền tứ giác tô màu trong Hình 2. a) Tìm tập hợp các điểm M(x; y) thoả mãn F(x;y) = 40x + 30y = 1 200. Hình 23 b) Với mỗi số thực m xét đường thang d,, :40x +30y =m.
Từ hình vẽ, tìm điều kiện của m để d„ ¬ S z Ø. c) Từ phần b suy ra giá trị lớn nhát của F(x; y) trên miền S, từ đó suy ra lời giải của bài toán. Nhận xét Xét bài toán quy hoạch tuyến tính với tập các phương án chấp nhận được S. Người ta chứng minh được rằng: + Néu S=@ thi bài toán không có phương án tối ưu.
-_ Nếu $Ø và là miền đa giác thì bài toán luôn có phương án tối ưu và phương án tối ưu là một trong các phương án cực biên. Các bước giải bài toán quy hoạch tuyến tính với miền cháp nhận được là miền đa giác: Bước 1. Xác định hàm mục tiêu. Xác định hệ bắt phương trình bậc nhát gồm tắt cả các ràng buộc của bài toán.
Biểu diễn tập các phương án cháp nhận được. Tìm các phương án cực biên. Tính giá trị của hàm mục tiêu tại các điểm cực biên, từ đó suy ra giá trị lớn nhất và giá trị nhỏ nhát của hàm mục tiêu rồi kết luận. (Bài toán vitamin) Một nhà khoa học đã nghiên cứu về tác động phối hợp của hai loại vitamin A và B đối với cơ thể con người.
Kết quả như sau: j)_ Một người mỗi ngày cần từ 400 đến 1 000 đơn vị vitamin ca A lẫn B; ii) Trong một ngày mỗi người có thẻ tiếp nhận không quá 600 đơn vị vitaminA và không quá 500 đơn vị vitamin B; iii) Do tác động phối hợp của hai loại vitamin trên, nên mỗi ngày, một người sử dụng số đơn vị vitamin B không ít hơn một nửa số đơn vị vitamin A nhưng không nhiều hơn ba làn số đơn vị vitamin A. Biết rằng mỗi đơn vị vitamin A có giá 90 đồng và mỗi đơn vị vitamin B có giá 75 đồng. Tìm phương án dùng hai loại vitamin A và B thoả mãn các điều kiện ở trên sao cho chỉ phí rẻ nhất. Gọi x và y lần lượt là số đơn vị vitamin A và B mà một người dùng mỗi ngày.
Chi phi mua vitamin là F(x; y) = 90x + 75y đồng. Hệ bắt phương trình ràng buộc x và y là 0<x<800 0<y<500 400 < x + y <1000 4 2x<y<3%x =Xx<y<3x. Miền nghiệm của hệ bát phương trình này Ay là miền lục giác MNPQS trong Hình 2. 41000 Các điểm cực biên là: M(100; 300) , nS 500), P(500; 500), 800 400 Q(600; 400), R(600; 300), si |, là Bước 5.
Bài toán yêu cầu tìm giá trị nhỏ nhát của IR F(x; y) tren miền lục giác MNPQRS. Ta biết rằng F(x; y) đạt giá trị nhỏ nhát tại một trong các đỉnh của lục giác. Tính giá trị của F(x; y) tại các đỉnh của lục pa 6001 Su giác ta được: 500 Hình 24 F(100; 300) = 31 500; ri" 500 = 52500; F(500; 500)= 82500; F(600; 400) = 84000; F(600; 300) = 76500; F: `) =34000. Giá trị nhỏ nhát của F(x, y) bằng 31 500 tại (100; 300).
Phương án tối ưu là (100; 300). Vậy chi phí mua vitamin nhỏ nhát là 31 500 đồng khi x = 100 va y = 300. Bây giờ ta sẽ xét một tình huống mà phương án tối ưu của bài toán đạt được tại vô số điểm trên miền chấp nhận được. Một công ty sơn sản xuất hai loại sơn là sơn nội that và sơn ngoài trời.
Nguyên liệu để sản xuất gồm hai loại X và Y với trữ lượng lần lượt là 6 tần và 8 tan. Để sản xuất một tan sơn nội thất cần 2 tắn nguyên liệu X và 1 tắn nguyên liệu Y. Để sản xuất một tấn sơn ngoài trời cần 1 tán nguyên liệu X và 2 tan nguyên liệu Y. Qua nghiên cứu thị trường, công ty thấy rằng nhu cầu sơn nội thát không nhiều hơn sơn ngoài trời quá 1 tắn và nhu cầu cực đại của sơn nội thất là 2 tắn.
Giá bán một tắn sơn nội thất là 60 triệu đồng, một tắn sơn ngoài trời là 30 triệu đồng. Công ty cần sản xuất mỗi loại sơn bao nhiêu tán để doanh thu lớn nhát? Giải Bước 1. Gọi x và y lần lượt là số tắn sơn nội thất và sơn ngoài trời công ty cần sản xuất. Doanh thu của công ty là: F(x;y) =60x + 30y (triệu đồng).
Hệ bắt phương trình bậc nhát ràng buộc x và y là 0<x<2 y>0 2x+y<6 x+2y<8 x<y*t. Miền nghiệm của hệ bắt phương trình này là miền lục giác OABCDE trong Hình 2. Các điểm cực biên là: O(0, 0), A(1, 0), B(2; 1), C(2; 2), n{5: >}, E(0; 4).