Bài toán vận tải hỏi: có vài kho với lượng hàng sẵn có, vài điểm nhận với nhu cầu đã biết, cước chở một đơn vị trên mỗi tuyến khác nhau; nên chở bao nhiêu trên mỗi tuyến để đáp ứng đủ nhu cầu mà tổng cước nhỏ nhất. Đây là một dạng quy hoạch tuyến tính có cấu trúc đặc biệt, đặc biệt đến mức có cách giải riêng làm được trên giấy bằng một bảng ô vuông.
Bài này dùng ví dụ hai kho, ba cửa hàng để đi qua ba bước: lập phương án ban đầu theo hai cách khác nhau, kiểm phương án đã tối ưu chưa bằng phương pháp thế vị, và xử lý khi cung không bằng cầu. Phần cuối nói rõ mô hình này bỏ qua điều gì, và cách nhờ AI giải mà vẫn kiểm được kết quả.
Phát biểu bài toán và vì sao nó đặc biệt
Ví dụ giả định: một nhà phân phối có kho K1 chứa 50 thùng hàng và kho K2 chứa 70 thùng. Ba cửa hàng A, B, C cần lần lượt 30, 40 và 50 thùng. Cước chở một thùng (nghìn đồng) như sau: từ K1 đến A là 4, đến B là 6, đến C là 9; từ K2 đến A là 5, đến B là 3, đến C là 7. Tổng cung 120 bằng tổng cầu 120, ta gọi là bài toán cân bằng.
Gọi x với chỉ số là lượng chở trên mỗi tuyến, có sáu biến. Mỗi kho có một ràng buộc: tổng chở đi bằng lượng sẵn có. Mỗi cửa hàng có một ràng buộc: tổng nhận về bằng nhu cầu. Hàm mục tiêu là tổng cước, tức tổng của cước từng tuyến nhân lượng chở. Bạn hoàn toàn có thể đưa nó vào trình giải quy hoạch tuyến tính thông thường.
Điểm đặc biệt là mọi hệ số trong ràng buộc đều bằng 1 và mỗi biến chỉ xuất hiện trong đúng hai ràng buộc, một của kho và một của cửa hàng. Nhờ cấu trúc này, nếu cung và cầu là số nguyên thì luôn có đáp án tối ưu là số nguyên, không có chuyện chở 12,7 thùng. Cũng nhờ nó mà có phương pháp giải tay gọn hơn phương pháp đơn hình rất nhiều. Trong bảng của bài toán cân bằng với m kho và n cửa hàng, một phương án cơ sở có đúng m + n trừ 1 ô được dùng; với ví dụ này là 4 ô.
Phương án ban đầu: góc tây bắc và cước nhỏ nhất
Bước đầu tiên là tìm một phương án chấp nhận được, chưa cần tốt. Phương pháp góc tây bắc bắt đầu ở ô trên cùng bên trái, chở tối đa có thể, rồi đi sang phải hoặc xuống dưới. Phương pháp cước nhỏ nhất thì luôn chọn ô có cước rẻ nhất còn lại. Bảng dưới so sánh hai phương án (số thùng trên từng tuyến).
| Tuyến | Cước một thùng | Góc tây bắc | Cước nhỏ nhất |
|---|---|---|---|
| K1 đến A | 4 | 30 | 30 |
| K1 đến B | 6 | 20 | 0 |
| K1 đến C | 9 | 0 | 20 |
| K2 đến A | 5 | 0 | 0 |
| K2 đến B | 3 | 20 | 40 |
| K2 đến C | 7 | 50 | 30 |
| Tổng cước (nghìn đồng) | 650 | 630 |
Góc tây bắc: K1 chở A 30 thùng (A đủ), K1 còn 20 chở B; B còn thiếu 20, K2 chở B 20; K2 còn 50 chở C 50. Tổng 120 cộng 120 cộng 60 cộng 350 bằng 650 nghìn đồng. Phương pháp này không nhìn vào cước nên thường cho phương án kém.
Cước nhỏ nhất: ô rẻ nhất là K2 đến B (cước 3), chở 40 thùng, B đủ, K2 còn 30. Ô rẻ tiếp theo là K1 đến A (cước 4), chở 30, A đủ, K1 còn 20. Ô K2 đến A và K1 đến B đã đủ hàng nên bỏ qua; tiếp theo là K2 đến C (cước 7), chở 30, K2 hết; cuối cùng K1 đến C chở 20. Tổng 120 cộng 120 cộng 210 cộng 180 bằng 630 nghìn đồng. Cả hai phương án đều dùng đúng 4 ô.
Kiểm tối ưu bằng phương pháp thế vị
Có phương án rồi, làm sao biết đã tốt nhất chưa? Phương pháp thế vị (sách tiếng Anh gọi là MODI hoặc phương pháp u–v) gán cho mỗi kho một số u và mỗi cửa hàng một số v sao cho với mọi ô đang dùng, cước bằng u cộng v. Sau đó tính "cước rút gọn" cho mỗi ô chưa dùng bằng cước trừ (u cộng v). Nếu mọi cước rút gọn đều không âm, phương án đã tối ưu; nếu có ô âm, đưa ô đó vào sẽ giảm tổng cước.
Áp dụng cho phương án cước nhỏ nhất. Bốn ô đang dùng: K1–A (4), K1–C (9), K2–B (3), K2–C (7). Đặt u của K1 bằng 0. Từ K1–A: v của A bằng 4. Từ K1–C: v của C bằng 9. Từ K2–C: u của K2 bằng 7 trừ 9 bằng âm 2. Từ K2–B: v của B bằng 3 trừ âm 2 bằng 5.
Cước rút gọn của hai ô chưa dùng: K1–B là 6 trừ (0 cộng 5) bằng 1; K2–A là 5 trừ (âm 2 cộng 4) bằng 3. Cả hai đều dương, nên phương án 630 nghìn đồng là tối ưu. Con số 1 ở ô K1–B còn có nghĩa thực tế: nếu ép chở một thùng qua tuyến đó, tổng cước sẽ tăng khoảng 1 nghìn đồng.
Với phương án góc tây bắc, làm tương tự sẽ thấy ô K1–C có cước rút gọn âm 1. Đưa ô đó vào theo một vòng điều chỉnh (cộng ở ô này, trừ ở ô kia, xen kẽ quanh một chu trình trong bảng) với lượng 20 thùng, tổng cước giảm 20 nghìn đồng, về đúng 630. Hai đường đi khác nhau gặp nhau ở cùng một đáp án, đó là một phép kiểm chéo tốt.
Cung không bằng cầu và các tình huống đặc biệt
Cung lớn hơn cầu. Thêm một cửa hàng giả có nhu cầu bằng phần dư, cước đến đó bằng 0. Lượng "chở" đến cửa hàng giả chính là hàng nằm lại kho. Nếu giữ hàng ở mỗi kho có chi phí khác nhau, đặt cước đến cửa hàng giả bằng chi phí đó.
Cầu lớn hơn cung. Thêm một kho giả có lượng hàng bằng phần thiếu. Lượng chở từ kho giả đến cửa hàng nào là phần nhu cầu của cửa hàng đó không được đáp ứng. Có thể đặt "cước" từ kho giả bằng mức thiệt hại khi thiếu hàng ở từng nơi, để mô hình ưu tiên đáp ứng nơi thiệt hại lớn.
Tuyến bị cấm. Nếu một tuyến không chạy được, chẳng hạn cầu yếu không cho xe tải qua, đặt cước tuyến đó bằng một số rất lớn để trình giải tránh nó, hoặc bỏ hẳn biến đó khỏi mô hình.
Phương án suy biến. Đôi khi phương án dùng ít hơn m + n trừ 1 ô, do một bước làm cùng lúc hết hàng ở kho và đủ hàng ở cửa hàng. Khi đó không tính được đủ u, v. Cách xử lý trong sách là đánh dấu một ô trống như đang chở 0 đơn vị để giữ đủ số ô.
Đọc kết quả bằng ngôn ngữ của người quản lý
Đáp án tối ưu của ví dụ nói rằng kho K2 nên dồn toàn bộ 40 thùng cho B và 30 thùng cho C, còn kho K1 lo A và phần còn lại của C. Diễn giải bằng lời: K2 có lợi thế rõ ở tuyến đến B (cước 3 so với 6 từ K1), nên B được giao trọn cho K2; A gần K1 hơn nên K1 phục vụ A. Cửa hàng C xa cả hai kho, nhận hàng từ cả hai.
Các giá trị thế vị cũng kể một câu chuyện. Hiệu v của C trừ v của A bằng 5, nghĩa là trong phương án tối ưu, mỗi thùng giao đến C "đắt" hơn một thùng giao đến A khoảng 5 nghìn đồng ở mức biên. Nếu cửa hàng C muốn tăng thêm 10 thùng và cửa hàng A giảm 10 thùng, người quản lý có thể ước tính ngay tổng cước tăng chừng 50 nghìn đồng mà chưa cần giải lại, miễn là thay đổi đủ nhỏ để các ô đang dùng vẫn giữ nguyên.
Cách đọc này giúp bài toán không dừng ở bảng số. Khi trình bày cho người ra quyết định, hãy nói tuyến nào nên ưu tiên, tuyến nào đang gần ngưỡng đổi phương án (cước rút gọn nhỏ như ô K1–B), và thay đổi nào trong nhu cầu sẽ làm chi phí tăng mạnh nhất.
Mô hình này bỏ qua những gì
Bài toán vận tải cổ điển coi cước tỉ lệ thuận với số thùng. Thực tế, cước thường tính theo chuyến xe: chở 1 thùng hay 50 thùng trên một xe tải nhỏ có thể tốn gần như nhau. Khi đó cần mô hình có biến nguyên đếm số chuyến, thuộc nhóm quy hoạch nguyên và khó hơn nhiều.
Mô hình cũng không quan tâm thứ tự giao hàng. Nếu một xe đi vòng qua nhiều cửa hàng trong một chuyến, câu hỏi chuyển thành bài toán định tuyến xe, một họ bài toán tổ hợp mà với số điểm lớn thì không có cách giải nhanh nào bảo đảm tối ưu, người ta dùng thuật toán gần đúng. Bài toán đường đi ngắn nhất giữa hai điểm trên mạng lưới đường lại là một chủ đề khác, nằm ở danh mục toán rời rạc của trang.
Cuối cùng, cước và nhu cầu được coi là biết trước. Khi nhu cầu dao động, người lập kế hoạch thường chạy mô hình với vài kịch bản nhu cầu, hoặc dùng mô phỏng. Dù vậy, bài toán vận tải cổ điển vẫn là điểm khởi đầu tốt cho kế hoạch phân bổ hàng theo tuần hay theo tháng, và là bài tập đẹp để hiểu cấu trúc của quy hoạch tuyến tính.
Dùng AI và bảng tính để giải và kiểm
Gợi ý một quy trình làm việc với chatbot và bảng tính cho bài vận tải cỡ vừa:
- Câu lệnh mẫu: "Giải bài toán vận tải sau bằng phương pháp cước nhỏ nhất rồi kiểm bằng phương pháp thế vị. Trình bày bảng phân phối, giá trị u, v và cước rút gọn của từng ô chưa dùng. Nếu chưa tối ưu, chỉ rõ chu trình điều chỉnh."
- Kiểm tổng hàng: tổng mỗi hàng của bảng phải bằng lượng hàng ở kho, tổng mỗi cột bằng nhu cầu cửa hàng. Đây là lỗi chatbot hay mắc nhất khi bảng lớn.
- Đếm số ô dùng; với bài cân bằng, phương án cơ sở phải có m + n trừ 1 ô.
- Nhập bài vào trình giải tối ưu của bảng tính, so tổng cước với đáp án của chatbot. Hai con số phải bằng nhau; phương án cụ thể có thể khác nếu bài có nhiều đáp án tối ưu.
- Tên khách hàng, địa chỉ cửa hàng và bảng cước thương lượng với nhà xe là thông tin kinh doanh; thay bằng ký hiệu và số làm tròn khi đưa vào chatbot.
Với bài tập trên lớp, hãy tự làm phần thế vị bằng tay ít nhất một lần. Phần đó giúp bạn hiểu cước rút gọn là gì, thứ mà bảng kết quả của mọi phần mềm tối ưu đều in ra nhưng ít người đọc.
Câu hỏi thường gặp
Bài toán vận tải có phải là quy hoạch tuyến tính không?
Có. Nó là quy hoạch tuyến tính với cấu trúc đặc biệt: mỗi biến chỉ nằm trong ràng buộc của một kho và một điểm nhận, hệ số đều bằng 1. Cấu trúc này cho phép giải bằng bảng trên giấy và bảo đảm có đáp án nguyên khi cung cầu là số nguyên.
Phương pháp góc tây bắc có dùng được trong thực tế không?
Chủ yếu dùng để có nhanh một phương án ban đầu chấp nhận được, vì nó không nhìn vào cước. Phương án đó sau đó được cải thiện bằng phương pháp thế vị. Phương pháp cước nhỏ nhất hoặc phương pháp Vogel thường cho điểm xuất phát tốt hơn.
Cước rút gọn âm có nghĩa là gì?
Nghĩa là đưa ô đó vào phương án, điều chỉnh các ô khác theo một chu trình để giữ cân bằng, sẽ làm tổng cước giảm. Mỗi đơn vị chuyển qua ô đó giảm đúng bằng giá trị tuyệt đối của cước rút gọn, cho đến khi một ô khác về 0.
Khi tổng cung khác tổng cầu thì giải thế nào?
Thêm một điểm nhận giả hoặc một kho giả để bù phần chênh, với cước bằng 0 hoặc bằng chi phí lưu kho, chi phí thiếu hàng tuỳ ý nghĩa. Sau đó giải như bài cân bằng bình thường.
Bài toán vận tải khác bài toán định tuyến xe thế nào?
Bài toán vận tải chỉ quyết định chở bao nhiêu trên mỗi tuyến nguồn đến đích, coi mỗi tuyến độc lập. Định tuyến xe quyết định thứ tự các điểm một xe ghé trong một chuyến, khó hơn nhiều và thường giải gần đúng.
Có nên tin đáp án chatbot đưa ra cho bài vận tải lớn?
Không nên tin ngay. Kiểm tổng hàng theo hàng và cột, đếm số ô dùng, và so tổng cước với trình giải tối ưu trong bảng tính. Chatbot hay sai phép cộng trong bảng lớn dù cách trình bày nghe hợp lý.