Bài toán khẩu phần hỏi: trộn các nguyên liệu với lượng bao nhiêu để hỗn hợp đạt đủ mọi chỉ tiêu tối thiểu mà tổng chi phí thấp nhất. Nó là một bài quy hoạch tuyến tính, nhưng khác bài toán sản xuất ở chỗ ta tìm giá trị nhỏ nhất và các ràng buộc là "lớn hơn hoặc bằng". Cùng khuôn này xuất hiện ở công thức thức ăn chăn nuôi, phối trộn phân bón, pha trộn xăng dầu, trộn bê tông hay pha chế nước giải khát.
Bài này giải tay một ví dụ hai nguyên liệu, giải thích vì sao miền chấp nhận được lần này không bị chặn mà vẫn có đáp án, cách đọc giá bóng của từng chỉ tiêu, và một điều thú vị về bài toán đối ngẫu. Mọi con số dinh dưỡng và giá trong bài là ví dụ giả định để luyện toán, không phải công thức dùng cho trang trại hay khuyến nghị dinh dưỡng cho người.
Một bài toán có lịch sử: từ khẩu phần rẻ nhất đến phối trộn công nghiệp
Năm 1945, nhà kinh tế George Stigler đặt câu hỏi: chi phí tối thiểu để một người có khẩu phần đủ các chất dinh dưỡng thiết yếu là bao nhiêu, nếu chỉ được chọn trong danh sách vài chục loại thực phẩm thông dụng. Ông giải gần đúng bằng cách mò, vì lúc đó chưa có phương pháp hệ thống. Vài năm sau, khi phương pháp đơn hình ra đời, bài toán này trở thành một trong những ví dụ thử nghiệm kinh điển của quy hoạch tuyến tính.
Đáp án của những bài toán khẩu phần cho người thường rất kỳ quặc: vài loại thực phẩm rẻ với số lượng lớn, không ai muốn ăn thật. Lý do là mô hình chỉ biết các ràng buộc được viết ra; khẩu vị, sự đa dạng, văn hoá ăn uống không nằm trong đó. Đây là bài học về mô hình hoá đáng nhớ hơn cả kỹ thuật giải: thứ gì không thành ràng buộc thì mô hình coi như không tồn tại.
Trong sản xuất thì khác. Thức ăn chăn nuôi, phân bón hay vật liệu xây dựng có chỉ tiêu kỹ thuật đo được rõ ràng, và nguyên liệu đầu vào đổi giá liên tục. Phối trộn theo mô hình tối ưu là việc thường làm ở các nhà máy, với phần mềm chuyên dụng chạy hàng chục nguyên liệu và chỉ tiêu. Ví dụ dưới đây chỉ có hai nguyên liệu để bạn thấy được bên trong phần mềm đó làm gì.
Lập mô hình cho ví dụ hai nguyên liệu
Ví dụ giả định: cần trộn một mẻ hỗn hợp từ hai nguyên liệu, gọi là nguyên liệu N (giàu năng lượng, rẻ) và nguyên liệu K (giàu đạm, đắt hơn). Mỗi kilôgam N có giá 5 nghìn đồng, cung cấp 1 đơn vị đạm và 3 đơn vị năng lượng. Mỗi kilôgam K có giá 8 nghìn đồng, cung cấp 4 đơn vị đạm và 2 đơn vị năng lượng. Mẻ hỗn hợp cần tối thiểu 40 đơn vị đạm và 60 đơn vị năng lượng.
Gọi x là số kilôgam N, y là số kilôgam K. Hàm mục tiêu là tổng chi phí C = 5x + 8y nghìn đồng, cần nhỏ nhất. Ràng buộc đạm: x + 4y lớn hơn hoặc bằng 40. Ràng buộc năng lượng: 3x + 2y lớn hơn hoặc bằng 60. Cùng với x, y không âm.
Hãy dừng lại một chút ở đơn vị. Vế trái của ràng buộc đạm là (đơn vị đạm trên kilôgam) nhân kilôgam, ra đơn vị đạm, khớp với vế phải. Hàm mục tiêu là (nghìn đồng trên kilôgam) nhân kilôgam, ra nghìn đồng. Kiểm đơn vị nghe nhàm, nhưng khi bài thật có mười nguyên liệu với hàm lượng tính theo phần trăm, phần nghìn và kilôcalo, đây là chỗ lỗi chui vào nhiều nhất.
Một chi tiết của mô hình đáng chú ý: không có ràng buộc tổng khối lượng. Mô hình chỉ đòi đủ chỉ tiêu, không quan tâm mẻ nặng bao nhiêu. Trong thực tế thường có thêm điều kiện về khối lượng hoặc tỉ lệ tối đa của từng nguyên liệu; phần sau sẽ thêm một ràng buộc như vậy để xem đáp án đổi ra sao.
Giải bằng đồ thị: miền không bị chặn vẫn có đáp án
Vẽ đường đạm x + 4y = 40 qua (40, 0) và (0, 10); đường năng lượng 3x + 2y = 60 qua (20, 0) và (0, 30). Lần này phần được phép nằm phía xa gốc toạ độ, vì ràng buộc là "lớn hơn hoặc bằng". Miền chấp nhận được kéo dài vô hạn lên trên và sang phải. Nó không bị chặn, nhưng vì ta tìm chi phí nhỏ nhất và chi phí tăng khi đi ra xa, đáp án vẫn nằm ở một đỉnh phía trong.
| Đỉnh (N kg, K kg) | Đạm | Năng lượng | Chi phí (nghìn đồng) |
|---|---|---|---|
| (0, 30) | 120 | 60 | 240 |
| (16, 6) | 40 | 60 | 128 |
| (40, 0) | 40 | 120 | 200 |
Đỉnh giữa là giao của hai đường. Từ phương trình đạm, x = 40 trừ 4y; thay vào phương trình năng lượng được 120 trừ 12y cộng 2y bằng 60, suy ra y = 6 và x = 16. Chi phí tại đó là 80 cộng 48 bằng 128 nghìn đồng, nhỏ nhất trong ba đỉnh. Ở đỉnh (16, 6) cả hai chỉ tiêu vừa đủ, không thừa chút nào; ở hai đỉnh còn lại một chỉ tiêu bị dư rất nhiều, nghĩa là đang trả tiền cho thứ không cần.
Lưu ý nếu bài toán đổi thành tìm chi phí lớn nhất thì không có đáp án, vì cứ đổ thêm nguyên liệu là chi phí tăng mãi. Đây là ví dụ cho trường hợp "không bị chặn" mà các phần mềm giải tối ưu sẽ báo lỗi; gặp thông báo đó thường là bạn đã đặt sai chiều tối ưu hoặc thiếu ràng buộc.
Giá bóng của chỉ tiêu và bài toán đối ngẫu
Nâng chỉ tiêu đạm lên 41 đơn vị thì chi phí tăng bao nhiêu? Giải lại hệ x + 4y = 41 và 3x + 2y = 60: x = 41 trừ 4y, thay vào được 123 trừ 10y bằng 60, y = 6,3 và x = 15,8. Chi phí 79 cộng 50,4 bằng 129,4 nghìn đồng, tăng 1,4 nghìn. Làm tương tự với năng lượng 61 đơn vị: y = 5,9, x = 16,4, chi phí 82 cộng 47,2 bằng 129,2, tăng 1,2 nghìn. Vậy giá bóng của một đơn vị đạm là 1,4 nghìn đồng và của một đơn vị năng lượng là 1,2 nghìn đồng.
Giờ nhân giá bóng với chỉ tiêu: 1,4 nhân 40 cộng 1,2 nhân 60 bằng 56 cộng 72 bằng 128, đúng bằng chi phí tối ưu. Đây không phải trùng hợp. Mỗi bài quy hoạch tuyến tính có một bài toán đối ngẫu đi kèm, và định lý đối ngẫu mạnh nói rằng khi cả hai có nghiệm thì giá trị tối ưu của chúng bằng nhau.
Bài đối ngẫu ở đây có thể kể bằng lời: một nhà cung cấp muốn bán thẳng "đạm" và "năng lượng" dưới dạng chất bổ sung, đặt giá p cho mỗi đơn vị đạm và q cho mỗi đơn vị năng lượng. Để người trộn không quay lại mua nguyên liệu, giá trị dinh dưỡng trong một kilôgam N tính theo giá đó không được vượt 5 nghìn: p + 3q nhỏ hơn hoặc bằng 5; tương tự với K: 4p + 2q nhỏ hơn hoặc bằng 8. Nhà cung cấp muốn tối đa doanh thu 40p + 60q. Giải hệ p + 3q = 5 và 4p + 2q = 8 được p = 1,4 và q = 1,2, đúng bằng hai giá bóng vừa tính.
Hiểu đối ngẫu giúp bạn đọc được bảng kết quả của phần mềm tối ưu: cột "giá trị đối ngẫu" hay "giá bóng" chính là các con số p, q này, cho biết mỗi chỉ tiêu đang "đắt" đến mức nào trong công thức hiện tại.
Thêm ràng buộc thực tế và xem đáp án đổi
Giới hạn tỉ lệ một nguyên liệu. Giả sử vì lý do kỹ thuật, K không được quá 5 kilôgam mỗi mẻ. Ràng buộc y nhỏ hơn hoặc bằng 5 cắt bỏ đỉnh (16, 6). Đỉnh mới là giao của y = 5 với đường đạm: x = 40 trừ 20 = 20. Kiểm năng lượng: 60 cộng 10 bằng 70, đủ. Chi phí 100 cộng 40 bằng 140 nghìn đồng. Ràng buộc mới làm chi phí tăng 12 nghìn, và năng lượng bị dư 10 đơn vị.
Giá nguyên liệu đổi. Giữ giá K là 8 nghìn, phương án (16, 6) còn tối ưu chừng nào giá N nằm trong khoảng 2 đến 12 nghìn đồng. Ở giá 12 nghìn, đỉnh (16, 6) và (0, 30) cùng cho 240; ở giá 2 nghìn, đỉnh (16, 6) và (40, 0) cùng cho 80. Khoảng rộng cho thấy công thức này ổn định với biến động giá vừa phải.
Thêm nguyên liệu thứ ba. Khi có thêm nguyên liệu, bài toán thành ba biến, không vẽ trên mặt phẳng được nữa nhưng trình giải xử lý như thường. Mẹo kiểm nhanh: tính "giá trị" của nguyên liệu mới theo giá bóng hiện tại. Nếu hàm lượng của nó nhân với p, q lớn hơn giá bán, đưa nó vào công thức sẽ làm chi phí giảm.
Dùng AI cho bài toán phối trộn mà không bị dắt sai
Chatbot làm tốt phần lập mô hình và giải thích, nhưng có vài chỗ bạn phải tự giữ:
- Câu lệnh mẫu: "Lập mô hình quy hoạch tuyến tính tìm chi phí nhỏ nhất cho bài phối trộn sau. Ghi đơn vị từng hệ số. Giải bằng đồ thị, liệt kê toạ độ mọi đỉnh và chi phí tại mỗi đỉnh. Sau đó tính giá bóng của từng chỉ tiêu bằng cách nới chỉ tiêu thêm một đơn vị."
- Kiểm chiều bất đẳng thức: bài phối trộn dùng "lớn hơn hoặc bằng" cho chỉ tiêu tối thiểu. Chatbot chép nhầm sang "nhỏ hơn hoặc bằng" thì đáp án sẽ là trộn 0 kilôgam mọi thứ.
- Kiểm đáp án bằng cách thay ngược vào từng chỉ tiêu; chỉ tiêu nào vừa đủ, chỉ tiêu nào dư.
- Hàm lượng dinh dưỡng thật của nguyên liệu phải lấy từ phiếu phân tích của nhà cung cấp hoặc tài liệu chuyên ngành, không lấy từ trí nhớ của chatbot. Mô hình đúng mà số đầu vào sai thì đáp án vẫn sai.
- Công thức thức ăn cho vật nuôi hay khẩu phần ăn cho người có những yêu cầu ngoài toán học; quyết định cuối cùng cần người có chuyên môn trong ngành xem lại.
- Giá mua và công thức riêng của cơ sở sản xuất là bí mật kinh doanh; dùng số giả định khi nhờ chatbot dựng khung.
Câu hỏi thường gặp
Bài toán khẩu phần khác bài toán sản xuất thế nào?
Bài toán sản xuất thường tìm lợi nhuận lớn nhất với tài nguyên có hạn, ràng buộc dạng nhỏ hơn hoặc bằng. Bài toán khẩu phần tìm chi phí nhỏ nhất để đạt đủ chỉ tiêu, ràng buộc dạng lớn hơn hoặc bằng. Cả hai cùng là quy hoạch tuyến tính và thực ra là đối ngẫu của nhau theo một nghĩa nhất định.
Vì sao đáp án tối ưu thường làm các chỉ tiêu vừa đủ?
Vì mỗi phần dư là phần tiền trả cho thứ không cần. Ở đỉnh tối ưu, các ràng buộc chặt là những chỉ tiêu vừa đủ. Chỉ tiêu nào còn dư thì giá bóng của nó bằng không, nâng nó lên một chút không làm tăng chi phí.
Giá bóng của một chỉ tiêu dùng để làm gì?
Nó cho biết nâng chỉ tiêu đó thêm một đơn vị thì chi phí tăng bao nhiêu, trong phạm vi phương án hiện tại. Người quản lý dùng nó để cân nhắc có nên nâng tiêu chuẩn sản phẩm hay không, và để định giá một nguyên liệu mới.
Có thể dùng mô hình này để tự lên thực đơn ăn kiêng không?
Mô hình chỉ là công cụ toán học và đáp án thường kỳ quặc nếu thiếu ràng buộc về khẩu vị và sự đa dạng. Nhu cầu dinh dưỡng của mỗi người khác nhau, nên lên thực đơn cho sức khoẻ cần hỏi chuyên gia dinh dưỡng hoặc bác sĩ.
Chatbot giải sai bài phối trộn ở chỗ nào hay gặp nhất?
Hay gặp nhất là đảo chiều bất đẳng thức, nhầm đơn vị phần trăm với số tuyệt đối, và giải hệ phương trình sai một phép tính nhưng vẫn trình bày tự tin. Luôn thay đáp án ngược vào từng chỉ tiêu để kiểm.
Bài nhiều nguyên liệu thì giải bằng gì?
Dùng trình giải tối ưu trong bảng tính hoặc phần mềm chuyên dụng. Bạn vẫn cần tự lập mô hình đúng, nhập đúng hàm lượng và chiều ràng buộc, rồi đọc bảng độ nhạy để hiểu công thức nhạy với giá nguyên liệu nào.