I. Tổng quan bài toán vận tải khi tổng cung và cầu không bằng nhau
Trong lĩnh vực vận trù học (Operations Research) và quản trị chuỗi cung ứng, bài toán vận tải là một mô hình quy hoạch tuyến tính cổ điển. Mục tiêu chính là tìm ra phương án vận chuyển hàng hóa từ nhiều nguồn cung cấp (trạm phát) đến nhiều điểm tiêu thụ (trạm thu) sao cho tổng chi phí là thấp nhất, đồng thời thỏa mãn các ràng buộc về khả năng cung cấp và nhu cầu. Tuy nhiên, mô hình lý tưởng thường giả định tổng cung bằng tổng cầu, được gọi là bài toán vận tải cân bằng. Trên thực tế, tình huống supply not equal to demand (cung không bằng cầu) xảy ra rất phổ biến. Đây chính là bài toán vận tải không cân bằng (unbalanced transportation problem), một dạng toán đòi hỏi phương pháp xử lý đặc biệt trước khi có thể áp dụng các thuật toán giải quyết tiêu chuẩn. Việc không nhận diện và xử lý đúng dạng bài toán này sẽ dẫn đến kết quả sai lệch, không thể tìm ra phương án tối ưu và gây lãng phí nguồn lực đáng kể cho doanh nghiệp. Như trong tài liệu nghiên cứu của Đại học UEH, sinh viên đã chỉ rõ: "Đây là bài toán thuộc dạng nguồn cung khác nguồn cầu (Supply ≠ Demand). Khác với dạng bài toán công thức, ta dùng dạng toán Module Transportation". Điều này nhấn mạnh sự cần thiết phải sử dụng một phương pháp tiếp cận chuyên biệt để đưa bài toán về dạng cân bằng, từ đó mới có thể tiến hành tối ưu hóa chi phí vận chuyển một cách chính xác và hiệu quả trong các hệ thống logistics và chuỗi cung ứng hiện đại.
1.1. Khái niệm cơ bản về bài toán vận tải trong vận trù học
Bài toán vận tải là một lớp bài toán đặc biệt của quy hoạch tuyến tính. Mô hình này được thiết lập để tối ưu hóa việc phân phối một loại sản phẩm từ một tập hợp các nguồn cung (ví dụ: nhà máy, kho hàng) đến một tập hợp các điểm đến có nhu cầu (ví dụ: nhà phân phối, cửa hàng bán lẻ). Các yếu tố cốt lõi của bài toán bao gồm: các nguồn cung với khả năng cung cấp nhất định, các điểm đến với nhu cầu xác định, và chi phí vận chuyển trên mỗi đơn vị sản phẩm từ mỗi nguồn đến mỗi điểm đến. Mục tiêu là xác định số lượng sản phẩm cần vận chuyển trên mỗi tuyến đường sao cho tổng chi phí vận chuyển là tối thiểu, trong khi vẫn đáp ứng đầy đủ nhu cầu tại các điểm đến và không vượt quá khả năng cung cấp của các nguồn. Đây là công cụ nền tảng trong vận trù học, giúp các nhà quản lý đưa ra quyết định chiến lược về logistics.
1.2. Phân biệt bài toán cân bằng và bài toán vận tải mất cân bằng
Sự khác biệt cơ bản giữa hai dạng bài toán này nằm ở mối quan hệ giữa tổng cung và tổng cầu. Một bài toán vận tải cân bằng là trường hợp lý tưởng khi tổng lượng hàng hóa có sẵn tại tất cả các nguồn cung cấp bằng chính xác tổng nhu cầu tại tất cả các điểm đến. Trong trường hợp này, các thuật toán như Phương pháp góc Tây-Bắc, Phương pháp chi phí nhỏ nhất, hoặc xấp xỉ Vogel có thể được áp dụng trực tiếp để tìm phương án ban đầu. Ngược lại, bài toán vận tải mất cân bằng (unbalanced transportation problem) xảy ra khi tổng cung lớn hơn tổng cầu (thừa cung) hoặc tổng cung nhỏ hơn tổng cầu (thiếu cung). Dạng bài toán này không thể giải trực tiếp bằng các thuật toán tiêu chuẩn và cần một bước xử lý trung gian để chuyển nó về dạng cân bằng trước khi tìm kiếm phương án tối ưu.
II. Thách thức khi Supply Demand Vấn đề của bài toán gốc
Khi tổng cung không khớp với tổng cầu, các thuật toán vận tải tiêu chuẩn không thể hoạt động. Lý do là các thuật toán này được xây dựng trên giả định rằng mọi đơn vị hàng hóa từ nguồn cung sẽ được phân phối hết đến các điểm đến. Sự mất cân bằng này tạo ra hai tình huống đầy thách thức: bài toán vận tải thừa cung và bài toán vận tải thiếu cung. Trong trường hợp thừa cung, sẽ có một lượng hàng hóa tồn kho không được phân phối, và mô hình cần phải xác định nguồn nào sẽ giữ lại lượng hàng này mà không phát sinh chi phí (hoặc chi phí thấp nhất). Ngược lại, trong trường hợp thiếu cung, một số nhu cầu sẽ không được đáp ứng, và mô hình cần một cơ chế để xử lý sự thiếu hụt này. Việc bỏ qua bước cân bằng hóa bài toán sẽ dẫn đến việc không thể thiết lập ma trận vận tải hợp lệ, khiến các phương pháp tìm kiếm giải pháp ban đầu và tối ưu hóa như phương pháp thế vị (MODI) trở nên vô hiệu. Đây là rào cản lớn nhất cần vượt qua để đảm bảo tính chính xác và khả thi của lời giải. Thách thức cốt lõi là làm thế nào để "hợp thức hóa" mô hình mà không làm thay đổi bản chất của bài toán gốc.
2.1. Phân tích trường hợp bài toán vận tải thừa cung Supply Demand
Khi tổng khả năng cung cấp của các trạm phát lớn hơn tổng nhu cầu của các trạm thu, ta đối mặt với bài toán vận tải thừa cung. Vấn đề nảy sinh là lượng hàng hóa dư thừa này sẽ được xử lý như thế nào. Nếu không có cơ chế xử lý, thuật toán sẽ không thể phân bổ hết lượng cung, dẫn đến vi phạm ràng buộc của mô hình. Trong thực tế, lượng hàng thừa này có thể được lưu kho tại các trạm phát. Để mô hình hóa điều này, một kỹ thuật phổ biến được sử dụng là tạo ra một điểm đến ảo. Điểm đến này sẽ "tiêu thụ" toàn bộ lượng hàng dư thừa. Thách thức là phải gán chi phí vận chuyển đến điểm đến ảo này một cách hợp lý, thường là bằng 0, để phản ánh đúng thực tế rằng hàng hóa không thực sự được vận chuyển đi đâu cả, mà chỉ là được giữ lại tại nguồn.
2.2. Xử lý tình huống bài toán vận tải thiếu cung Supply Demand
Ngược lại với trường hợp trên, bài toán vận tải thiếu cung xảy ra khi tổng nhu cầu vượt quá tổng khả năng cung cấp. Điều này có nghĩa là không thể đáp ứng tất cả các yêu cầu từ các trạm thu. Vấn đề chính ở đây là quyết định nhu cầu của trạm thu nào sẽ không được đáp ứng và mức độ thiếu hụt là bao nhiêu. Về mặt mô hình toán học, nếu không điều chỉnh, bài toán sẽ không có lời giải khả thi vì ràng buộc về nhu cầu không thể được thỏa mãn. Để giải quyết, người ta cần thêm vào một nguồn cung ảo để bù đắp cho sự thiếu hụt. Nguồn cung ảo này sẽ "cung cấp" chính xác lượng hàng còn thiếu để tổng cung mới bằng tổng cầu. Chi phí vận chuyển từ nguồn ảo này đến các trạm thu thường được đặt bằng 0, giả định rằng việc không nhận được hàng không phát sinh chi phí vận chuyển. Tuy nhiên, trong các mô hình phức tạp hơn, chi phí này có thể đại diện cho chi phí phạt hoặc mất mát do không đáp ứng được đơn hàng.
III. Phương pháp biến giả Chìa khóa giải bài toán không cân bằng
Để khắc phục tình trạng supply not equal to demand, phương pháp biến giả (Dummy Variable Method) là kỹ thuật tiêu chuẩn và hiệu quả nhất. Nguyên tắc cơ bản của phương pháp này là biến đổi bài toán vận tải không cân bằng thành một bài toán cân bằng tương đương bằng cách thêm vào các nguồn hoặc đích ảo (dummy). Các biến ảo này không tồn tại trong thực tế nhưng đóng vai trò quan trọng trong việc cân bằng mô hình toán học. Cụ thể, nếu tổng cung lớn hơn tổng cầu, một trạm thu giả (dummy destination) sẽ được thêm vào. Ngược lại, nếu tổng cầu lớn hơn tổng cung, một trạm phát giả (dummy source) sẽ được tạo ra. Lượng cung/cầu của các trạm giả này được xác định bằng đúng phần chênh lệch giữa tổng cung và tổng cầu ban đầu. Chi phí vận chuyển liên quan đến các trạm giả này thường được gán bằng 0, vì chúng chỉ đại diện cho việc hàng hóa không được vận chuyển hoặc nhu cầu không được đáp ứng. Sau khi thêm biến giả, bài toán trở nên cân bằng và sẵn sàng cho các bước giải tiếp theo, như tìm phương án xuất phát và tối ưu hóa bằng phương pháp thế vị (MODI). Đây là bước đệm không thể thiếu để áp dụng thành công các công cụ quy hoạch tuyến tính.
3.1. Kỹ thuật thêm trạm thu giả dummy destination khi cung thừa
Trong bài toán vận tải thừa cung, tổng cung (S) lớn hơn tổng cầu (D). Để cân bằng, ta tạo ra một trạm thu giả (dummy destination) với nhu cầu bằng đúng lượng chênh lệch: Nhu cầu giả = S - D. Trạm thu giả này sẽ được thêm vào ma trận vận tải như một cột mới. Chi phí vận chuyển từ tất cả các trạm phát thật đến trạm thu giả này được đặt bằng 0 (C_i,dummy = 0). Ý nghĩa của việc này là bất kỳ lượng hàng nào được "vận chuyển" đến trạm thu giả thực chất là lượng hàng còn tồn lại tại trạm phát tương ứng. Bằng cách này, toàn bộ lượng cung sẽ được phân bổ hết trên lý thuyết (một phần cho các trạm thu thật, phần còn lại cho trạm thu giả), làm cho tổng cung bằng tổng cầu mới. Bài toán lúc này đã trở thành dạng cân bằng và có thể giải được bằng các phương pháp thông thường.
3.2. Kỹ thuật thêm trạm phát giả dummy source khi cầu thừa
Trong bài toán vận tải thiếu cung, tổng cầu (D) lớn hơn tổng cung (S). Để giải quyết, ta giới thiệu một trạm phát giả (dummy source) với khả năng cung cấp bằng đúng lượng thiếu hụt: Cung giả = D - S. Trạm phát giả này được thêm vào ma trận vận tải như một hàng mới. Tương tự như trường hợp trên, chi phí vận chuyển từ trạm phát giả đến tất cả các trạm thu thật được đặt bằng 0 (C_dummy,j = 0). Lượng hàng được phân bổ từ dummy source đến một trạm thu nào đó đại diện cho lượng nhu cầu không được đáp ứng tại trạm thu đó. Kỹ thuật này giúp thỏa mãn tất cả các ràng buộc về nhu cầu trên giấy tờ, đưa bài toán về trạng thái cân bằng. Sau khi cân bằng hóa, mô hình đã sẵn sàng để tìm kiếm phương án tối ưu về chi phí cho lượng hàng thực sự có thể được vận chuyển.
IV. Hướng dẫn tìm phương án tối ưu cho bài toán vận tải hiệu quả
Sau khi bài toán đã được cân bằng hóa bằng phương pháp biến giả, quá trình tìm kiếm phương án tối ưu bao gồm hai giai đoạn chính. Giai đoạn đầu tiên là tìm một phương án phân phối ban đầu khả thi. Đây là một lời giải bất kỳ thỏa mãn tất cả các ràng buộc về cung và cầu. Có nhiều phương pháp để thực hiện việc này, chẳng hạn như Phương pháp góc Tây-Bắc (North-West Corner), Phương pháp chi phí nhỏ nhất (Least Cost Method), hoặc Phương pháp xấp xỉ Vogel (Vogel's Approximation Method - VAM). Trong đó, VAM thường cho kết quả ban đầu gần với phương án tối ưu nhất. Giai đoạn thứ hai, và cũng là quan trọng nhất, là kiểm tra và cải thiện phương án ban đầu để đạt được chi phí tối thiểu. Phương pháp thế vị (MODI - Modified Distribution Method), hay còn gọi là phương pháp u-v, là thuật toán hiệu quả nhất cho giai đoạn này. MODI tính toán các chi phí ẩn (opportunity costs) cho các ô không được sử dụng trong phương án hiện tại. Nếu tìm thấy một ô có chi phí ẩn âm, việc chuyển một lượng hàng vào ô đó sẽ giúp giảm tổng chi phí. Quá trình này được lặp lại cho đến khi tất cả các chi phí ẩn đều không âm, tại thời điểm đó, phương án tối ưu đã được tìm thấy.
4.1. Tìm phương án xuất phát ban đầu bằng các phương pháp phổ biến
Việc tìm một phương án xuất phát ban đầu là bước khởi động cho quá trình tối ưu hóa. Phương pháp góc Tây-Bắc là đơn giản nhất, bắt đầu phân bổ hàng từ ô trên cùng bên trái của ma trận chi phí mà không quan tâm đến chi phí. Phương pháp chi phí nhỏ nhất cải tiến hơn bằng cách luôn ưu tiên phân bổ vào ô có chi phí thấp nhất còn lại. Tuy nhiên, Phương pháp xấp xỉ Vogel (VAM) thường được ưa chuộng hơn vì tính hiệu quả. VAM tính toán "chi phí phạt" (penalty cost) cho mỗi hàng và cột, dựa trên sự chênh lệch giữa hai ô có chi phí nhỏ nhất. Sau đó, nó ưu tiên phân bổ vào hàng hoặc cột có chi phí phạt cao nhất, tại ô có chi phí thấp nhất. Cách tiếp cận này giúp đưa ra quyết định phân bổ thông minh hơn ngay từ đầu, giảm số lần lặp cần thiết trong giai đoạn tối ưu hóa sau đó.
4.2. Kiểm tra và cải thiện bằng phương pháp thế vị MODI
Khi đã có phương án ban đầu, phương pháp thế vị (MODI) được sử dụng để kiểm tra tính tối ưu. Thuật toán này gán một biến thế vị u_i cho mỗi hàng (nguồn cung) và v_j cho mỗi cột (điểm đến). Đối với các ô đang có lượng hàng phân bổ (ô cơ sở), ta có phương trình u_i + v_j = c_ij, với c_ij là chi phí vận chuyển. Từ hệ phương trình này, ta có thể giải ra giá trị của tất cả các biến thế vị. Tiếp theo, ta tính toán chỉ số cải thiện (hay chi phí ẩn) cho các ô chưa có hàng phân bổ (ô phi cơ sở) bằng công thức k_ij = c_ij - u_i - v_j. Nếu tất cả k_ij ≥ 0, phương án hiện tại là phương án tối ưu. Nếu tồn tại k_ij < 0, phương án có thể được cải thiện. Ta chọn ô có k_ij âm nhất, tạo một vòng lặp điều chỉnh và phân bổ lại lượng hàng để giảm tổng chi phí. Quá trình này tiếp tục cho đến khi không còn chỉ số cải thiện âm nào.
V. Ứng dụng quy hoạch tuyến tính giải bài toán vận tải thực tế
Lý thuyết về bài toán vận tải không cân bằng và các phương pháp giải được ứng dụng rộng rãi trong thực tế thông qua các công cụ phần mềm mạnh mẽ. Các doanh nghiệp không giải bài toán này bằng tay mà dựa vào các phần mềm chuyên dụng như LINGO, Gurobi, hoặc các công cụ tích hợp sẵn như Excel Solver và QM for Windows. Các công cụ này cho phép người dùng nhập trực tiếp dữ liệu về chi phí, khả năng cung cấp và nhu cầu, kể cả trong trường hợp supply not equal to demand. Phần mềm sẽ tự động áp dụng các thuật toán quy hoạch tuyến tính, bao gồm cả việc thêm các biến giả cần thiết, để tìm ra phương án tối ưu một cách nhanh chóng. Ví dụ điển hình được thể hiện trong dự án nghiên cứu của sinh viên Đại học UEH, nơi họ đã sử dụng cả Excel Solver và QM for Windows để giải quyết các tình huống vận tải thực tế của tập đoàn InnoTech. Bằng cách thiết lập đúng các biến, hàm mục tiêu và ràng buộc, các công cụ này đã xác định chính xác phương án phân bổ sản phẩm từ các nhà máy đến các điểm tiêu thụ sao cho tổng chi phí sản xuất và vận chuyển là thấp nhất. Điều này cho thấy tính ứng dụng cao của vận trù học trong việc giải quyết các vấn đề logistics phức tạp.
5.1. Phân tích tình huống từ dự án ERP SCM của Đại học UEH
Trong tài liệu gốc, sinh viên UEH đã giải quyết một unbalanced transportation problem cụ thể cho tập đoàn InnoTech. Tình huống đặt ra là 5 nhà máy với năng lực sản xuất khác nhau cần sản xuất 3 loại sản phẩm để đáp ứng nhu cầu thị trường. Tổng năng lực sản xuất của các nhà máy (tổng cung) lớn hơn tổng nhu cầu dự báo cho các sản phẩm (tổng cầu). Nhận diện đây là bài toán vận tải mất cân bằng, nhóm nghiên cứu đã sử dụng Module Transportation trong QM for Windows. Công cụ này tự động xử lý sự mất cân bằng bằng cách ngầm định thêm một trạm thu giả để hấp thụ lượng sản phẩm dư thừa, từ đó tìm ra phương án phân bổ sản xuất tối ưu với tổng chi phí là $85,800. Phân tích này là một minh chứng rõ ràng về cách áp dụng lý thuyết vào giải quyết vấn đề thực tiễn trong quản trị chuỗi cung ứng.
5.2. Vai trò của Excel Solver và QM for Windows trong tối ưu hóa
Excel Solver và QM for Windows là hai công cụ phổ biến trong giáo dục và doanh nghiệp vừa và nhỏ để giải các bài toán quy hoạch tuyến tính. Excel Solver là một add-in mạnh mẽ, cho phép người dùng xây dựng mô hình trực tiếp trên bảng tính quen thuộc. Người dùng định nghĩa các ô biến đổi (lượng hàng vận chuyển), ô mục tiêu (tổng chi phí) và các ràng buộc (cung, cầu). Solver sẽ sử dụng các thuật toán như Simplex LP để tìm lời giải. QM for Windows là một phần mềm giáo dục chuyên dụng, cung cấp các module được xây dựng sẵn cho nhiều loại bài toán vận trù học, bao gồm cả bài toán vận tải. Nó có giao diện trực quan, giúp người dùng nhập dữ liệu dễ dàng và nhận kết quả chi tiết, bao gồm cả các bước giải trung gian. Cả hai công cụ đều giúp tự động hóa quá trình tính toán phức tạp, giúp các nhà quản lý tập trung vào việc phân tích kết quả và ra quyết định.
VI. Tầm quan trọng của việc giải Unbalanced Transportation Problem
Việc nắm vững cách giải quyết Unbalanced Transportation Problem có tầm quan trọng chiến lược trong quản trị logistics và chuỗi cung ứng hiện đại. Trong một môi trường kinh doanh luôn biến động, sự mất cân bằng giữa cung và cầu là điều khó tránh khỏi. Khả năng mô hình hóa và giải quyết chính xác bài toán vận tải không cân bằng cho phép doanh nghiệp tối ưu hóa chi phí vận chuyển, giảm thiểu lãng phí do tồn kho thừa hoặc thiệt hại do thiếu hụt hàng hóa. Áp dụng các kỹ thuật như phương pháp biến giả không chỉ là một bài tập học thuật, mà còn là một công cụ thực tiễn giúp tăng cường hiệu quả hoạt động, cải thiện khả năng đáp ứng khách hàng và nâng cao năng lực cạnh tranh. Khi các chuỗi cung ứng ngày càng trở nên phức tạp và toàn cầu hóa, việc sử dụng các mô hình quy hoạch tuyến tính và các công cụ phần mềm hỗ trợ để tìm ra phương án tối ưu không còn là một lợi thế, mà đã trở thành một yêu cầu tất yếu để tồn tại và phát triển bền vững. Tương lai của ngành vận trù học sẽ tiếp tục phát triển các mô hình phức tạp hơn, tích hợp các yếu tố bất định và rủi ro, nhưng nền tảng xử lý các bài toán mất cân bằng vẫn sẽ là kiến thức cốt lõi.
6.1. Tóm tắt các bước chính để đạt hiệu quả logistics tối ưu
Để giải quyết hiệu quả một bài toán vận tải mất cân bằng, quy trình chuẩn bao gồm các bước sau: Đầu tiên, xác định rõ các nguồn cung, điểm đến, chi phí, khả năng cung cấp và nhu cầu. Thứ hai, kiểm tra điều kiện cân bằng bằng cách so sánh tổng cung và tổng cầu. Thứ ba, nếu có sự chênh lệch, áp dụng phương pháp biến giả: thêm trạm thu giả (dummy destination) nếu cung thừa hoặc trạm phát giả (dummy source) nếu cầu thừa. Thứ tư, sau khi bài toán đã cân bằng, tìm một phương án xuất phát ban đầu khả thi. Thứ năm, sử dụng một thuật toán tối ưu hóa như phương pháp thế vị (MODI) để lặp lại và cải thiện phương án cho đến khi đạt được tổng chi phí thấp nhất. Việc tuân thủ quy trình này đảm bảo một lời giải chính xác và đáng tin cậy.
6.2. Hướng phát triển của mô hình trong quản trị chuỗi cung ứng
Mô hình vận tải cổ điển đang liên tục được mở rộng để phản ánh sự phức tạp của chuỗi cung ứng hiện đại. Các hướng phát triển trong tương lai bao gồm: mô hình vận tải đa sản phẩm, mô hình có xét đến yếu tố thời gian (vận tải động), tích hợp các điểm trung chuyển (transshipment points), và đặc biệt là xử lý các yếu tố bất định như nhu cầu biến động hoặc chi phí không chắc chắn (quy hoạch ngẫu nhiên và mờ). Các thuật toán cũng được cải tiến để giải quyết các bài toán quy mô lớn với hàng ngàn nguồn cung và điểm đến. Mặc dù vậy, nguyên tắc cơ bản của việc cân bằng hóa bài toán thông qua các biến giả vẫn là nền tảng quan trọng, cho thấy giá trị bền vững của các khái niệm cốt lõi trong vận trù học.
