Đây là bản xem thử. Phiên bản đầy đủ trong ứng dụng có bài tập, AI chấm ngay và theo dõi tiến độ học.
Bài học
Xưởng sản xuất bàn ghế: bài toán tối đa hóa lợi nhuận
Mục tiêu bài học
Sau bài này, em giải trọn vẹn một bài toán quy hoạch tuyến tính xuất phát từ tình huống sản xuất thực tế: từ đề bài bằng lời, em tự đặt ẩn, lập hệ bất phương trình ràng buộc, lập hàm mục tiêu lợi nhuận, rồi tìm phương án sản xuất cho lợi nhuận lớn nhất.
Kiến thức nền cần nhớ
Ba bài trước đã trang bị đủ ba mảnh ghép em cần: vẽ miền nghiệm của một bất phương trình (bài 1), tìm đỉnh của miền nghiệm một hệ bất phương trình (bài 2), và tìm GTLN của một hàm mục tiêu tuyến tính bằng cách so sánh giá trị tại các đỉnh (bài 3) — tất cả đều là same-grade bridge. Bài này không dạy kỹ thuật mới; nó dạy em cách đọc một đề bài bằng lời và tự dịch nó sang ngôn ngữ bất phương trình.
Khởi động
Một xưởng mộc mỗi ngày có một lượng gỗ và một số giờ công cố định để làm hai loại sản phẩm: bàn và ghế. Bàn bán lãi nhiều hơn ghế, nhưng cũng tốn nhiều gỗ và công hơn. Xưởng nên làm bao nhiêu bàn, bao nhiêu ghế mỗi ngày để lãi nhiều nhất, mà không vượt quá lượng gỗ và giờ công đang có?
Kiến thức trọng tâm
Trong thực tế, các ràng buộc của một bài toán quy hoạch tuyến tính thường đến từ bốn nguồn quen thuộc: nguyên liệu hay nguồn cung có hạn (gỗ, vải, hoá chất), thời gian hay nhân công có hạn (giờ máy, giờ công), vốn đầu tư có hạn, và giới hạn thị trường tiêu thụ (số lượng tối đa bán được). Khi đọc một đề bài, việc đầu tiên là xác định mỗi câu trong đề tương ứng với nguồn nào trong bốn loại này, vì mỗi nguồn luôn sinh ra đúng một bất phương trình dạng tổng mức tiêu thụ không vượt quá mức đang có.
Để giải một bài toán quy hoạch tuyến tính từ đề bài thực tế, em thực hiện bốn bước. Bước một, gọi ẩn: chọn $x, y$ đại diện cho số lượng cần tìm, nêu rõ đơn vị và điều kiện $x, y\ge0$ (thường còn là số nguyên, vì không thể sản xuất nửa cái bàn). Bước hai, lập hệ bất phương trình ràng buộc: mỗi nguồn lực hạn chế trong đề (nguyên liệu, giờ công, thị trường tiêu thụ...) sinh ra một bất phương trình theo $x, y$. Bước ba, lập hàm mục tiêu $F(x;y)=ax+by$ theo đại lượng cần tối ưu — thường là lợi nhuận hoặc chi phí. Bước bốn, áp dụng đúng kỹ thuật đã học ở hai bài trước: tìm các đỉnh của miền nghiệm, tính $F$ tại từng đỉnh, so sánh để kết luận phương án tối ưu.
Ví dụ
Xưởng mộc sản xuất bàn và ghế
1
Một xưởng mộc mỗi ngày làm bàn và ghế gỗ. Mỗi cái bàn cần 6 đơn vị gỗ và 3 giờ công; mỗi cái ghế cần 2 đơn vị gỗ và 2 giờ công. Xưởng có tối đa 90 đơn vị gỗ và 60 giờ công mỗi ngày. Lãi mỗi bàn là 900 nghìn đồng, mỗi ghế là 400 nghìn đồng. Xưởng nên làm bao nhiêu bàn, bao nhiêu ghế mỗi ngày để lãi lớn nhất?
2
Gọi $x$ là số bàn, $y$ là số ghế xưởng làm trong một ngày ($x, y$ là số tự nhiên).
3
Ràng buộc gỗ: $6x+2y\le90$, tức $3x+y\le45$. Ràng buộc giờ công: $3x+2y\le60$. Cùng điều kiện $x\ge0, y\ge0$, ta có hệ $\begin{cases}3x+y\le45\\3x+2y\le60\\x\ge0\\y\ge0\end{cases}$.
4
Lợi nhuận trong ngày (đơn vị nghìn đồng) là $F(x;y)=900x+400y$, cần tìm GTLN của $F$.
5
Giải từng cặp đường biên và kiểm tra với các bất phương trình còn lại: $x=0, y=0$ cho $(0;0)$; $y=0$ và $3x+y=45$ cho $x=15$, tức $(15;0)$ (thay vào $3x+2y\le60$: $45\le60$, thỏa); $3x+y=45$ và $3x+2y=60$: trừ hai phương trình được $y=15$, suy ra $x=10$, cho $(10;15)$; $x=0$ và $3x+2y=60$ cho $y=30$, tức $(0;30)$ (thay vào $3x+y\le45$: $30\le45$, thỏa). Miền nghiệm là tứ giác bốn đỉnh $(0;0), (15;0), (10;15), (0;30)$.
Đỉnh $(10;15)$ cho giá trị lớn nhất trong bốn giá trị vừa tính ($0, 13\,500, 15\,000, 12\,000$), và tọa độ $(10;15)$ đều là số tự nhiên nên phương án khả thi trong thực tế — không cần làm tròn.
8
Vậy xưởng nên làm 10 bàn và 15 ghế mỗi ngày để đạt lợi nhuận lớn nhất, bằng $15\,000$ nghìn đồng, tức 15 triệu đồng một ngày.
Đáng để kiểm tra lại đáp số bằng một phép tính ngược: nếu xưởng làm 10 bàn và 15 ghế, giờ công dùng hết là $3(10)+2(15)=60$ giờ — cũng vừa đúng giới hạn 60 giờ công, giống như gỗ cũng vừa dùng hết ở bước trên. Cả hai nguồn lực đều được dùng hết, không dư thừa — đây là dấu hiệu quen thuộc của một phương án tối ưu trong quy hoạch tuyến tính: tại đỉnh tối ưu, luôn có đúng hai ràng buộc đồng thời đạt dấu bằng, vì hai đường thẳng cắt nhau mới xác định được một điểm duy nhất trên mặt phẳng.
Đỉnh (10;15) — 10 bàn, 15 ghế — cho lợi nhuận lớn nhất trong bốn phương án ở đỉnh.Cột cao nhất ứng với phương án 10 bàn, 15 ghế — đúng bằng đỉnh tối ưu vừa tìm.
Bẫy thường gặp
Sai lầm thường gặp: khi tính hàm mục tiêu, nhiều bạn quên đổi đơn vị hoặc quên kiểm tra tọa độ đỉnh tối ưu có phải số tự nhiên hay không. Trong bài này, đỉnh $(10;15)$ may mắn là số nguyên nên phương án khả thi ngay; nhưng nếu đỉnh tối ưu lại là một cặp số thập phân — ví dụ do một hằng số trong đề khác đi — em phải xét thêm các điểm nguyên gần đỉnh đó nằm trong miền nghiệm, vì không thể sản xuất một số bàn hay ghế không nguyên.
Tóm lại, một bài toán quy hoạch tuyến tính thực tế luôn được giải theo đúng bốn bước: gọi ẩn, lập hệ ràng buộc, lập hàm mục tiêu, rồi tìm đỉnh và tính $F$ để kết luận. Việc khó nhất thường không nằm ở kỹ thuật toán học — vốn chỉ lặp lại hai bài trước — mà ở việc dịch đúng đề bài bằng lời sang các bất phương trình.
Bài toán xưởng mộc vừa rồi có hàm mục tiêu cần tối đa hóa và miền nghiệm bị chặn. Bài tiếp theo đặt em vào một tình huống khác: một bài toán vận chuyển hàng hóa với hàm mục tiêu cần tối thiểu hóa chi phí, trên một miền nghiệm không bị chặn — nơi các ràng buộc mang dấu $\ge$ thay vì $\le$. Quy trình bốn bước vẫn giữ nguyên; chỉ có cách đọc đề, dấu bất phương trình, và hình dạng miền nghiệm là mới, cùng với một bài toán sản xuất thứ hai để em luyện tập thêm chính quy trình vừa học ở bài này.
Ba bài trước đã trang bị đủ ba mảnh ghép em cần: vẽ miền nghiệm của một bất phương trình (bài 1), tìm đỉnh của miền nghiệm một hệ bất phương trình (bài 2), và tìm GTLN của một hàm mục tiêu tuyến tính bằng cách so sánh giá trị tại các đỉnh (bài 3) — tất cả đều là same-grade bridge. Bài này không dạy kỹ thuật mới; nó dạy em cách đọc một đề bài bằng lời và tự dịch nó sang ngôn ngữ bất phương trình.
Trong thực tế, các ràng buộc của một bài toán quy hoạch tuyến tính thường đến từ bốn nguồn quen thuộc: nguyên liệu hay nguồn cung có hạn (gỗ, vải, hoá chất), thời gian hay nhân công có hạn (giờ máy, giờ công), vốn đầu tư có hạn, và giới hạn thị trường tiêu thụ (số lượng tối đa bán được). Khi đọc một đề bài, việc đầu tiên là xác định mỗi câu trong đề tương ứng với nguồn nào trong bốn loại này, vì mỗi nguồn luôn sinh ra đúng một bất phương trình dạng tổng mức tiêu thụ không vượt quá mức đang có.
Để giải một bài toán quy hoạch tuyến tính từ đề bài thực tế, em thực hiện bốn bước. Bước một, gọi ẩn: chọn x,y đại diện cho số lượng cần tìm, nêu rõ đơn vị và điều kiện x,y≥0 (thường còn là số nguyên, vì không thể sản xuất nửa cái bàn). Bước hai, lập hệ bất phương trình ràng buộc: mỗi nguồn lực hạn chế trong đề (nguyên liệu, giờ công, thị trường tiêu thụ...) sinh ra một bất phương trình theo x,y. Bước ba, lập hàm mục tiêu F(x;y)=ax+by theo đại lượng cần tối ưu — thường là lợi nhuận hoặc chi phí. Bước bốn, áp dụng đúng kỹ thuật đã học ở hai bài trước: tìm các đỉnh của miền nghiệm, tính F tại từng đỉnh, so sánh để kết luận phương án tối ưu.
Gọi x là số bàn, y là số ghế xưởng làm trong một ngày (x,y là số tự nhiên).
Ràng buộc gỗ: 6x+2y≤90, tức 3x+y≤45. Ràng buộc giờ công: 3x+2y≤60. Cùng điều kiện x≥0,y≥0, ta có hệ ⎩⎨⎧3x+y≤453x+2y≤60x≥0y≥0.
Lợi nhuận trong ngày (đơn vị nghìn đồng) là F(x;y)=900x+400y, cần tìm GTLN của F.
Giải từng cặp đường biên và kiểm tra với các bất phương trình còn lại: x=0,y=0 cho (0;0); y=0 và 3x+y=45 cho x=15, tức (15;0) (thay vào 3x+2y≤60: 45≤60, thỏa); 3x+y=45 và 3x+2y=60: trừ hai phương trình được y=15, suy ra x=10, cho (10;15); x=0 và 3x+2y=60 cho y=30, tức (0;30) (thay vào 3x+y≤45: 30≤45, thỏa). Miền nghiệm là tứ giác bốn đỉnh (0;0),(15;0),(10;15),(0;30).
Đỉnh (10;15) cho giá trị lớn nhất trong bốn giá trị vừa tính (0,13500,15000,12000), và tọa độ (10;15) đều là số tự nhiên nên phương án khả thi trong thực tế — không cần làm tròn.
Vậy xưởng nên làm 10 bàn và 15 ghế mỗi ngày để đạt lợi nhuận lớn nhất, bằng 15000 nghìn đồng, tức 15 triệu đồng một ngày.
Đáng để kiểm tra lại đáp số bằng một phép tính ngược: nếu xưởng làm 10 bàn và 15 ghế, giờ công dùng hết là 3(10)+2(15)=60 giờ — cũng vừa đúng giới hạn 60 giờ công, giống như gỗ cũng vừa dùng hết ở bước trên. Cả hai nguồn lực đều được dùng hết, không dư thừa — đây là dấu hiệu quen thuộc của một phương án tối ưu trong quy hoạch tuyến tính: tại đỉnh tối ưu, luôn có đúng hai ràng buộc đồng thời đạt dấu bằng, vì hai đường thẳng cắt nhau mới xác định được một điểm duy nhất trên mặt phẳng.
Sai lầm thường gặp: khi tính hàm mục tiêu, nhiều bạn quên đổi đơn vị hoặc quên kiểm tra tọa độ đỉnh tối ưu có phải số tự nhiên hay không. Trong bài này, đỉnh (10;15) may mắn là số nguyên nên phương án khả thi ngay; nhưng nếu đỉnh tối ưu lại là một cặp số thập phân — ví dụ do một hằng số trong đề khác đi — em phải xét thêm các điểm nguyên gần đỉnh đó nằm trong miền nghiệm, vì không thể sản xuất một số bàn hay ghế không nguyên.
Tóm lại, một bài toán quy hoạch tuyến tính thực tế luôn được giải theo đúng bốn bước: gọi ẩn, lập hệ ràng buộc, lập hàm mục tiêu, rồi tìm đỉnh và tính F để kết luận. Việc khó nhất thường không nằm ở kỹ thuật toán học — vốn chỉ lặp lại hai bài trước — mà ở việc dịch đúng đề bài bằng lời sang các bất phương trình.
Bài toán xưởng mộc vừa rồi có hàm mục tiêu cần tối đa hóa và miền nghiệm bị chặn. Bài tiếp theo đặt em vào một tình huống khác: một bài toán vận chuyển hàng hóa với hàm mục tiêu cần tối thiểu hóa chi phí, trên một miền nghiệm không bị chặn — nơi các ràng buộc mang dấu ≥ thay vì ≤. Quy trình bốn bước vẫn giữ nguyên; chỉ có cách đọc đề, dấu bất phương trình, và hình dạng miền nghiệm là mới, cùng với một bài toán sản xuất thứ hai để em luyện tập thêm chính quy trình vừa học ở bài này.