Vấn đề vận tải

Trong toán học, Vấn đề vận tải (tiếng Anh: transportation problem) là một dạng bài toán quy hoạch tuyến tính. Vấn đề này có thể được mô tả bằng đồ thị hai phía, có thể là có hướng hoặc không có hướng. Nó có nhiều ứng dụng thực tiễn và thuật toán đơn hình giải quyết bài toán này cũng đơn giản hơn. Bài toán này lần đầu tiên được chính thức hóa bởi nhà toán học người Pháp Gaspard Monge vào năm 1781.

Bài toán

Giả sử có m kho hàng $A_1,..,A_m$ và n cửa hàng $B_1,..,B_n$. Kho $A_i$ có $a_i$ tấn hàng và cửa hàng $B_i$ cần $b_i$ tấn hàng. Cước phí để vận chuyển một tấn hàng từ kho $A_i$ đến cửa hàng $B_j$ là $c_{ij}$. Mục tiêu là tìm ra phương án vận chuyển sao cho tổng chi phí là nhỏ nhất.

Các kho hàng được gọi là các điểm cung cấp, trong khi các cửa hàng được gọi là các điểm tiêu thụ. Ví dụ: Có 3 điểm cung cấp và 4 điểm tiêu thụ, số lượng hàng ở các điểm cung cấp, nhu cầu ở các điểm tiêu thụ, và cước phí vận chuyển được trình bày trong bảng dưới đây:

Bảng này được gọi là bảng vận tải.

Phương án vận chuyển

Mỗi phương án vận chuyển là một ma trận X = $\left[x_{ij}\right]$, trong đó $x_{ij}$ đại diện cho số lượng hàng hóa được chuyển từ A_i đến B_j. ($x_{ij}\ge <!--\; \ge \; -->0$)

Chi phí vận chuyển của phương án X được tính như sau:

$G\left(X\right)=\underset{i=1}{\overset{m}{\sum <!--\; \sum \; -->}}\underset{j=1}{\overset{n}{\sum <!--\; \sum \; -->}}{c}_{ij}.x_{ij}$

Ràng buộc hệ thống

Để phương án trở nên hợp lệ cho bài toán vận tải, các giá trị $x_{i,j}$ phải đáp ứng các ràng buộc tại các điểm cung cấp (ràng buộc theo hàng) là

$\underset{j=1}{\overset{n}{\sum <!--\; \sum \; -->}}{x}_{ij}=a_i$ đối với mọi i=1,..,m.

và các điều kiện đối với các điểm tiếp nhận hàng (ràng buộc cột)

$\underset{i=1}{\overset{m}{\sum <!--\; \sum \; -->}}{x}_{ij}=b_j$ với mọi j=1,..,n.

Do đó, bài toán vận tải có dạng bài toán Quy hoạch Tuyến tính chuẩn với m$\times <!--\; \times \; -->$n biến số, với mục tiêu tối ưu hóa hàm G(X) và có m+n điều kiện ràng buộc.

Đảm bảo cân bằng cung và cầu

• Tổng lượng hàng tồn kho tại m điểm cung cấp là $\underset{i=1}{\overset{m}{\sum <!--\; \sum \; -->}}{a}_i$, tổng nhu cầu của n điểm tiếp nhận là $\underset{j=1}{\overset{n}{\sum <!--\; \sum \; -->}}{b}_j$. Nếu tổng cung và tổng cầu bằng nhau, thì hệ thống được coi là cân bằng cung cầu.
• Nếu tổng cung lớn hơn tổng cầu $\underset{i=1}{\overset{m}{\sum <!--\; \sum \; -->}}{a}_i>\underset{j=1}{\overset{n}{\sum <!--\; \sum \; -->}}{b}_j$, thì sẽ có một số hàng hóa dư thừa ở các điểm cung cấp. Điều này được giải quyết bằng cách thêm một điểm tiếp nhận giả $B_{n+1}$ với cước phí $c_{i,n+1}=0$ cho mọi i=1,...,n.
• Nếu tổng cầu lớn hơn tổng cung , thì sẽ có một số nhu cầu không được đáp ứng ở các điểm tiếp nhận. Điều này được giải quyết bằng cách thêm một điểm cung cấp giả $A_{m+1}$ với nhu cầu $d_{m+1}=0$ và cước phí $c_{m,n+1}=0$ cho mọi j=1,...,m.

Thuật toán

Thuật toán giải quyết bài toán vận tải cũng là một dạng của thuật toán đơn hình. Quy trình bắt đầu bằng việc chọn một giải pháp khởi đầu và sau đó liên tục cải thiện nó cho đến khi đạt được kết quả tối ưu.

Tìm giải pháp khởi đầu

Có nhiều phương pháp để xác định giải pháp khởi đầu.

Phương pháp này bắt đầu bằng cách phân bổ số lượng hàng lớn nhất có thể vào ô đầu tiên ở góc Tây-Bắc, tức là ô (1,1), bằng cách đặt $x_{11}=min(a_1,b_1)$. Sau đó, nếu điểm cung cấp $A_1$ hết hàng hoặc điểm tiêu thụ $B_1$ đáp ứng đủ nhu cầu, ta có thể loại bỏ điểm cung cấp $A_1$ hoặc điểm $B_1$ ra khỏi bảng, sau đó tiếp tục phân bổ hàng hóa cho ô Tây-Bắc trong phần còn lại của bảng.

Với ví dụ trên, ta có

Các số nhỏ ghi ở góc trên mỗi ô biểu thị cước phí vận chuyển cho mỗi đơn vị hàng hóa từ điểm cung cấp thứ i đến điểm tiêu thụ thứ j.

Vì vậy, tổng chi phí vận chuyển cho phương án này là:

3×50 + 5×100 + 1×50 + 3×150 + 4×50 + 2×50 = 1450

Đây vẫn chưa phải là phương án tối ưu nhất.

Chúng ta cũng sẽ phân phối hàng vào các ô như trước, nhưng lần này ưu tiên chọn ô có cước phí thấp nhất trong những ô còn trống.

Trong ví dụ này

Tổng chi phí vận chuyển theo phương án này là:

3×50 + 2×100 + 1×150 + 3×100 + 7×50 = 1150

Tiêu chuẩn tối ưu và điều chỉnh chi phí

Sau khi áp dụng một trong các phương pháp lập phương án ban đầu (cùng với một số phương pháp khác ngoài hai phương pháp đã nêu), trong các phương án thu được, chúng ta có một số ô (i, j) có giá trị $x_{i,j}>0$, được gọi là các ô chọn. Các ô khác có giá trị $x_{i,j}=0$ được gọi là các ô tự do. Khi chuyển hệ ràng buộc của bài toán vận tải sang dạng bài toán quy hoạch tuyến tính tổng quát, các ô chọn tương ứng với các biến cơ sở. Trong trường hợp không suy biến, tất cả các ô tự do là biến tự do, còn nếu bài toán suy biến thì có thể có một số ô tự do vẫn là biến cơ sở. Dưới dạng bài toán QHTT tổng quát với điều kiện cân bằng cung cầu, hệ ràng buộc có hạng là m+n-1. Do đó, trong một phương án cơ sở không suy biến, số lượng ô chọn là đúng m+n-1, các ô còn lại sẽ là ô tự do.

Xem xét việc điều chỉnh một phương án cơ sở và ảnh hưởng của nó đến chi phí vận chuyển. Giả sử ta tăng thêm một lượng hàng h vào một ô tự do $(i_0,j_0)$. Để duy trì tổng số hàng trong dòng i 0 {\displaystyle i_{0}} , phải giảm lượng hàng đi h ở một ô $(i_0,j_1)$. Trong cột $j_1$, lượng hàng giảm tại ô $(i_0,j_1)$ và phải tăng tại ô $j_1$ tại dòng $i_1$. Sau một số bước hữu hạn, khi chuyển từ hàng này sang cột khác, ta trở lại ô cùng cột với ô đầu tiên, ô $(i_k,j_0)$, để giảm lượng hàng tại đó đi h, tạo thành một chu trình.

Khái niệm

Một chu trình trong bảng vận tải bao gồm một dãy các ô, trong đó ô đầu tiên và ô thứ hai nằm trên cùng một hàng hoặc cột, các ô tiếp theo phải nằm trên cùng một hàng hoặc cột và không đồng hàng hoặc cột với ba ô liên tiếp. Ô đầu tiên và ô cuối cùng phải nằm trên cùng một cột.

$(i_0,j_0),(i_0,j_1),(i_1,j_1),(i_1,j_2),...,(i_k,j_0)$

Chu trình có thể được hình dung như một con đường khép kín qua các ô của bảng vận tải, với mỗi lần đi qua một ô, đường đi sẽ rẽ một góc ${90}^0$.

Đặc điểm

1. Một phương án được coi là cơ sở nếu và chỉ nếu trong tập hợp các ô chọn của nó không chứa chu trình nào.
2. Mỗi ô tự do trong phương án cơ sở tạo thành một chu trình duy nhất với các ô cơ sở, gọi là chu trình điều chỉnh của ô tự do đó.
3. Khi điều chỉnh số lượng hàng hóa h≥ 0 vào ô tự do, lượng hàng phân phối cho các ô trong chu trình sẽ tăng giảm xen kẽ một lượng bằng h. Lượng hàng tối đa h có thể thêm vào ô tự do bằng số nhỏ nhất trong các ô trên chu trình bị trừ đi.
4. Gọi giá của ô tự do $v_{i_0,j_0}$ là tổng đại số của các cước phí $c_{i,j}$ với các dấu cộng và trừ xen kẽ tương ứng với các ô được cộng và trừ trong chu trình điều chỉnh của ô tự do $(i_0,j_0)$. Khi đó, với lượng điều chỉnh h thêm vào các ô tự do, tổng chi phí vận chuyển sẽ tăng (hoặc giảm) đi $h\ast <!--\; \ast \; -->v_{i,j}$ tùy thuộc vào giá trị của ô đó $(i_0,j_0)$.

Phương án cơ sở trong bài toán vận tải được coi là tối ưu nếu và chỉ nếu không còn ô tự do nào có giá trị âm.

Phương pháp xác định giá của ô tự do

Giá của các ô tự do có thể được tính bằng phương pháp thế vị như sau:

Thêm vào đó m+n biến ẩn $p_1,p_2,...,p_m$ và $q_1,q_2,...,q_n$.

Hệ phương trình gồm m + n - 1 phương trình $p_i+q_j=c_{i,j}$ với m + n - 1 ô cơ sở có thể được giải bằng cách sử dụng một ẩn, ví dụ như $p_1=0$. Khi đó, giá của các ô tự do (i, j) được tính theo công thức $v_{i,i}=p_i+q_j$.

Các loại bài toán khác

• Bài toán người bán hàng

Tài liệu tham khảo