Quy hoạch tuyến tính là bài toán tìm giá trị lớn nhất hoặc nhỏ nhất của một biểu thức bậc nhất, trong khi các biến phải thoả một số bất đẳng thức bậc nhất gọi là ràng buộc. Nghe khô, nhưng đây là khuôn của rất nhiều quyết định thật: sản xuất bao nhiêu mỗi loại hàng khi nguyên liệu có hạn, phối trộn nguyên liệu sao cho rẻ nhất mà vẫn đủ tiêu chuẩn, chở hàng từ kho nào đến đâu.
Khi chỉ có hai biến, bạn giải được bằng cách vẽ hình trên giấy kẻ ô, và chính hình vẽ đó giải thích vì sao các phương pháp máy tính dùng cho hàng nghìn biến lại hoạt động. Bài này đi qua một ví dụ xưởng mộc tính tay đầy đủ, rồi đọc thêm hai thông tin mà người quản lý hay cần hơn cả đáp án: tài nguyên nào đang thiếu và một đơn vị tài nguyên thêm đáng giá bao nhiêu.
Lập mô hình: biến, hàm mục tiêu và ràng buộc
Ví dụ giả định: một xưởng mộc nhỏ làm hai loại sản phẩm là bàn và ghế. Mỗi chiếc bàn lãi 300 nghìn đồng, mỗi chiếc ghế lãi 200 nghìn đồng. Một chiếc bàn cần 2 đơn vị gỗ và 1 ngày công, một chiếc ghế cần 1 đơn vị gỗ và 1 ngày công. Trong tháng, xưởng có 100 đơn vị gỗ và 80 ngày công. Do giới hạn chỗ phun sơn, xưởng làm được tối đa 40 chiếc bàn. Câu hỏi: làm bao nhiêu bàn, bao nhiêu ghế để tổng lãi lớn nhất.
Gọi x là số bàn, y là số ghế. Đó là hai biến quyết định. Hàm mục tiêu là tổng lãi, tính theo trăm nghìn đồng cho gọn: Z = 3x + 2y, cần làm cho lớn nhất. Các ràng buộc: gỗ 2x + y nhỏ hơn hoặc bằng 100; ngày công x + y nhỏ hơn hoặc bằng 80; chỗ sơn x nhỏ hơn hoặc bằng 40; và x, y không âm vì không ai làm âm một chiếc bàn.
Chữ "tuyến tính" ở đây có nghĩa cụ thể: lãi tỉ lệ thuận với số lượng, lượng gỗ dùng tỉ lệ thuận với số lượng, không có chuyện làm càng nhiều càng rẻ hay càng đắt. Nếu thực tế có chiết khấu khi mua gỗ số lượng lớn, mô hình này đã đơn giản hoá. Một giả định nữa thường bị quên: mô hình coi x và y là số thực, nên đáp án có thể ra số lẻ. Trong ví dụ này đáp án tình cờ là số nguyên; khi không phải, cần một nhánh khác gọi là quy hoạch nguyên.
Vẽ miền chấp nhận được trên giấy
Miền chấp nhận được là tập hợp mọi cặp (x, y) thoả tất cả ràng buộc cùng lúc. Với hai biến, nó là một đa giác trên mặt phẳng. Các bước vẽ:
- Vẽ hệ trục, trục ngang là số bàn x, trục đứng là số ghế y, chỉ lấy góc phần tư không âm.
- Vẽ đường gỗ 2x + y = 100 qua hai điểm (50, 0) và (0, 100). Thử điểm gốc (0, 0): 0 nhỏ hơn 100, đúng, nên phần được phép là phía chứa gốc toạ độ.
- Vẽ đường ngày công x + y = 80 qua (80, 0) và (0, 80). Phần được phép cũng là phía chứa gốc.
- Vẽ đường thẳng đứng x = 40. Phần được phép là bên trái.
- Tô phần giao của tất cả: một đa giác năm đỉnh. Tìm toạ độ từng đỉnh bằng cách giải hệ hai phương trình của hai đường cắt nhau tại đó.
- Năm đỉnh là (0, 0), (40, 0), (40, 20), (20, 60) và (0, 80). Đỉnh (40, 20) là giao của x = 40 với đường gỗ: 2 nhân 40 cộng y bằng 100 cho y bằng 20. Đỉnh (20, 60) là giao của đường gỗ và đường ngày công: trừ hai phương trình được x bằng 20, thay vào được y bằng 60.
Kiểm lại từng đỉnh với mọi ràng buộc trước khi đi tiếp. Đỉnh (20, 60) dùng 2 nhân 20 cộng 60 bằng 100 đơn vị gỗ và 20 cộng 60 bằng 80 ngày công, vừa khít cả hai, và 20 bàn nhỏ hơn 40 nên không vi phạm chỗ sơn. Đỉnh (40, 20) dùng hết 100 gỗ nhưng chỉ 60 ngày công.
Vì sao đáp án luôn nằm ở một đỉnh
Định lý cơ bản của quy hoạch tuyến tính nói rằng nếu bài toán có nghiệm tối ưu thì luôn có ít nhất một nghiệm tối ưu nằm ở một đỉnh của miền chấp nhận được. Trực giác: các đường Z = hằng số là những đường thẳng song song; đẩy đường đó ra xa nhất có thể mà vẫn chạm miền, chỗ chạm cuối cùng là một đỉnh hoặc cả một cạnh. Vì vậy chỉ cần tính Z ở các đỉnh.
| Đỉnh (bàn, ghế) | Gỗ dùng | Ngày công dùng | Lãi Z (trăm nghìn đồng) |
|---|---|---|---|
| (0, 0) | 0 | 0 | 0 |
| (40, 0) | 80 | 40 | 120 |
| (40, 20) | 100 | 60 | 160 |
| (20, 60) | 100 | 80 | 180 |
| (0, 80) | 80 | 80 | 160 |
Đáp án: làm 20 bàn và 60 ghế, lãi 180 trăm nghìn, tức 18 triệu đồng trong tháng (ví dụ giả định). Điều thú vị là chiếc bàn lãi cao hơn ghế, nhưng làm tối đa bàn lại không phải phương án tốt nhất, vì bàn ngốn gấp đôi gỗ. Đây chính là loại kết luận trực giác dễ bỏ sót mà quy hoạch tuyến tính chỉ ra rõ ràng.
Phương pháp đơn hình mà George Dantzig công bố cuối thập niên 1940 làm đúng việc này cho hàng nghìn biến: đi từ đỉnh này sang đỉnh kề bên tốt hơn cho đến khi không còn đỉnh kề nào tốt hơn. Máy tính làm phần đi lại, còn ý tưởng chính là hình vẽ trên.
Giá bóng: một đơn vị tài nguyên thêm đáng bao nhiêu
Người quản lý xưởng thường hỏi tiếp: nếu mua thêm gỗ thì lãi tăng bao nhiêu, có đáng thuê thêm người không. Câu trả lời nằm ở khái niệm giá bóng, hay giá trị biên của một ràng buộc: lượng hàm mục tiêu tăng thêm khi nới ràng buộc đó thêm một đơn vị, các thứ khác giữ nguyên.
Tính tay cho ví dụ. Tại đáp án (20, 60), hai ràng buộc gỗ và ngày công đang dùng hết, gọi là ràng buộc chặt. Nếu có 101 đơn vị gỗ, giải lại hệ 2x + y = 101 và x + y = 80 được x = 21, y = 59, lãi Z = 63 + 118 = 181. Vậy thêm một đơn vị gỗ làm lãi tăng 1 trăm nghìn đồng. Nếu có 81 ngày công, giải 2x + y = 100 và x + y = 81 được x = 19, y = 62, lãi Z = 57 + 124 = 181, cũng tăng 1 trăm nghìn.
Còn ràng buộc chỗ sơn x nhỏ hơn hoặc bằng 40 thì sao. Đáp án chỉ dùng 20 bàn, còn dư 20 chỗ, nên nới thêm chỗ sơn không làm lãi tăng chút nào: giá bóng bằng 0. Thông tin này có ích ngay: đừng bỏ tiền mở rộng khu sơn tháng này.
Hai lưu ý để không hiểu sai. Thứ nhất, giá bóng chỉ đúng trong một khoảng; nới gỗ quá nhiều thì đến lúc ràng buộc khác chặn lại và giá bóng đổi. Thứ hai, giá bóng là mức tối đa đáng trả thêm cho một đơn vị, không phải giá thị trường. Nếu một đơn vị gỗ ngoài định mức có giá cao hơn 100 nghìn đồng so với giá đã tính trong lãi, mua thêm là lỗ.
Phân tích độ nhạy: lãi mỗi sản phẩm đổi thì sao
Lãi mỗi chiếc bàn là con số ước lượng, giá gỗ lên xuống là nó đổi. Câu hỏi hữu ích là lãi bàn phải thay đổi đến mức nào thì phương án tối ưu mới đổi. Thử với lãi bàn là 4 trăm nghìn: tại (20, 60) được 80 + 120 = 200, tại (40, 20) được 160 + 40 = 200. Hai đỉnh hoà nhau, nghĩa là mọi điểm trên cạnh nối chúng đều tối ưu. Nếu lãi bàn vượt 4 trăm nghìn, đáp án nhảy sang (40, 20): làm tối đa bàn.
Theo chiều ngược lại, khi lãi bàn giảm xuống 2 trăm nghìn, bằng lãi ghế, đỉnh (20, 60) và (0, 80) cùng cho 160. Vậy trong khoảng lãi bàn từ 2 đến 4 trăm nghìn, phương án 20 bàn 60 ghế giữ nguyên là tối ưu. Đó là một khoảng khá rộng, cho thấy kế hoạch này không dễ bị đảo lộn bởi biến động giá nhỏ.
Trên hình, phân tích này tương ứng với việc xoay đường mục tiêu: hệ số thay đổi làm độ dốc của đường Z thay đổi, và đáp án chỉ nhảy sang đỉnh khác khi độ dốc đó vượt qua độ dốc của một cạnh kề. Phần mềm giải tối ưu thường in sẵn bảng độ nhạy với các khoảng này; hiểu được hình vẽ hai biến giúp bạn đọc bảng đó không bị mơ hồ.
Dùng AI và bảng tính đúng cách
Nhờ AI lập mô hình từ mô tả bằng lời. Câu lệnh mẫu: "Lập mô hình quy hoạch tuyến tính cho bài toán sau, ghi rõ ý nghĩa và đơn vị từng biến, hàm mục tiêu, từng ràng buộc kèm lý do. Chưa giải." So từng ràng buộc với đề; lỗi hay gặp nhất là đảo chiều bất đẳng thức hoặc quên điều kiện không âm.
Dùng trình giải tối ưu có sẵn trong bảng tính. Nhiều phần mềm bảng tính có phần bổ trợ giải tối ưu: bạn đặt ô biến, ô mục tiêu, các ô ràng buộc và chọn phương pháp tuyến tính. Đặt kết quả cạnh bảng tính tay ở trên để đối chiếu. Tên và vị trí tính năng đổi theo phiên bản, nên kiểm tài liệu của phiên bản bạn đang dùng.
Kiểm đáp án bằng cách thay ngược. Bất kể đáp án đến từ chatbot hay phần mềm, thay vào từng ràng buộc xem có vi phạm không, rồi thử vài đỉnh khác xem có đỉnh nào cho Z cao hơn không. Chatbot đôi khi giải hệ phương trình sai một phép trừ và vẫn trình bày rất tự tin.
Che số liệu sản xuất thật. Định mức nguyên liệu, lãi từng sản phẩm của doanh nghiệp là thông tin nhạy cảm. Khi luyện tập hay nhờ chatbot dựng khung, dùng số giả định có cùng cấu trúc.
Câu hỏi thường gặp
Quy hoạch tuyến tính dùng được cho bài có nhiều hơn hai biến không?
Được, đó mới là ứng dụng chính. Phương pháp đồ thị chỉ vẽ được với hai biến, còn bài nhiều biến dùng phương pháp đơn hình hoặc các thuật toán khác chạy trên máy tính. Ý tưởng đáp án nằm ở đỉnh vẫn giữ nguyên.
Nếu đáp án ra số lẻ như 20,5 chiếc bàn thì làm sao?
Khi biến bắt buộc là số nguyên, đó là bài toán quy hoạch nguyên, khó hơn. Làm tròn đáp án lẻ có thể vi phạm ràng buộc hoặc không còn tối ưu, nên cần kiểm lại các phương án nguyên lân cận hoặc dùng trình giải hỗ trợ biến nguyên.
Giá bóng có giống giá thị trường của nguyên liệu không?
Không. Giá bóng cho biết hàm mục tiêu tăng bao nhiêu khi có thêm một đơn vị tài nguyên trong phạm vi hiện tại. Nó là mức tối đa đáng trả thêm cho đơn vị đó, còn mua hay không phải so với giá thật.
Khi nào bài toán quy hoạch tuyến tính không có nghiệm?
Khi các ràng buộc mâu thuẫn nhau thì miền chấp nhận được rỗng, không có phương án nào thoả hết. Khi miền không bị chặn theo hướng làm hàm mục tiêu tăng mãi, bài toán không có giá trị lớn nhất. Cả hai thường là dấu hiệu mô hình thiếu hoặc sai ràng buộc.
Có nên để chatbot giải luôn bài quy hoạch tuyến tính?
Có thể dùng để lập mô hình và gợi ý cách giải, nhưng luôn kiểm đáp án bằng cách thay vào ràng buộc và so với trình giải trong bảng tính. Với bài nộp lấy điểm, hãy tự làm theo yêu cầu của giảng viên.
Ai là người đặt nền cho quy hoạch tuyến tính?
Leonid Kantorovich đã nêu bài toán phân bổ sản xuất cuối thập niên 1930, và George Dantzig công bố phương pháp đơn hình cuối thập niên 1940. Kantorovich cùng Tjalling Koopmans nhận giải Nobel kinh tế năm 1975 cho đóng góp về phân bổ tối ưu tài nguyên.