Bài toán vận tải là phương pháp để hoạch định năng lực sản xuất

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

Giả sử có m kho hàng A 1 , . . , A m {\displaystyle A_{1},..,A_{m}}   cùng chứa một loại hàng hóa, kho A i {\displaystyle A_{i}}   chứa a i {\displaystyle a_{i}}   tấn hàng. Cần vận chuyển số hàng trên đến n cửa hàng B 1 , . . . , B n {\displaystyle B_{1},...,B_{n}}  , cửa hàng B i {\displaystyle B_{i}}   cần số hàng b i {\displaystyle b_{i}}  . Cước phí vận chuyển một tấn hàng từ kho A i {\displaystyle A_{i}}   đến cửa hàng B j {\displaystyle B_{j}}   là c i j {\displaystyle c_{ij}}  . Hãy lập phương án vận chuyển sao cho tổng chi phí vận chuyển là nhỏ nhất.

Các kho hàng được gọi là các điểm phát, các cửa hàng được gọi là các điểm thu. Ví dụ: Có 3 điểm phát và 4 điểm thu, số hàng ở các điểm phát, nhu cầu ở các điểm thu, cước phí vận chuyển cho trong bảng sau:

Bảng trê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 = [ x i j ] {\displaystyle \left[x_{ij}\right]}  , trong đó x i j {\displaystyle x_{ij}}   là số hàng hóa chuyển từ Ai đến Bj. [ x i j ≥ 0 {\displaystyle x_{ij}\geq 0}  ]

Chi phí vận chuyển của phương án X là:

Hệ ràng buộc

Để một phương án thực sự là chấp nhận được cho bài toán vận tải, các giá trị x i , j {\displaystyle x_{i,j}}   phải thỏa mãn các ràng buộc đối với các điểm phát [ràng buộc dòng] là

và các ràng buộc với các điểm thu [ràng buộc cột]

Như vậy bài toán vận tải là bài toán QHTT dạng chính tắc với m × {\displaystyle \times }  n biến, hàm mục tiêu G[X] cần cực tiểu và m+n ràng buộc.

Cân bằng cung cầu

• Tổng số hàng dự trữ ở m điểm phát [cung] là ∑ i = 1 m a i {\displaystyle \sum _{i=1}^{m}a_{i}}  , tổng số nhu cầu của n điểm thu [cầu]là ∑ j = 1 n b j {\displaystyle \sum _{j=1}^{n}b_{j}}  . Nếu "cung" và "cầu" bằng nhau ta nói rằng cân bằng cung cầu.
• Nếu cung nhiều hơn cầu ∑ i = 1 m a i > ∑ j = 1 n b j {\displaystyle \sum _{i=1}^{m}a_{i}\,>\,\sum _{j=1}^{n}b_{j}}   thì một số hàng hóa sẽ được để lại ở các điểm phát. Ta biểu diễn việc này bằng cách bổ sung một điểm thu giả B n + 1 {\displaystyle B_{n+1}}   với cước phí c i , n + 1 = 0 {\displaystyle c_{i,n+1}=0}   với mọi i=1,...,n.
• Nếu cầu nhiều hơn cung ∑ i = 1 m a i < ∑ j = 1 n b j {\displaystyle \sum _{i=1}^{m}a_{i}\, 0 {\displaystyle x_{i,j}>0}  , các ô đó được gọi là các ô chọn, một số ô khác có x i , j = 0 {\displaystyle x_{i,j}=0}   được gọi là các ô tự do. Nếu viết lại hệ ràng buộc của bài toán vận tải như với bài toán quy hoạch tuyến tính tổng quát, các ô chọn trong các phương án ban đầu ứng với các ẩn cơ sở. Nếu phương án là không suy biến thì các ô tự do đều ứng với các ẩn tự do, nếu phương án là suy biến có thể có những ô tự do ứng với các ẩn cơ sở. Khi viết bài toán vận tải 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ạng của hệ ràng buộc của BTVT m điểm phát, n điểm thu là r=m+n-1. Do vậy khi không suy biến một phương án [cơ sở] tạo ra từ một trong các phương pháp trên có đúng m+n-1 ô chọn là ô cơ sở, các ô còn lại là ô tự do.

  Chu trình trong bảng vận tải

  Ta xem xét việc điều chỉnh một phương án cơ sở sẽ mang lại "lợi" hay "hại" cho giá thành vận chuyển. Giả sử trong một điều chỉnh nào đó một ô tự do [ i 0 , j 0 ] {\displaystyle [i_{0},j_{0}]}   được tăng thêm một lượng hàng h. Khi đó trong dòng i 0 {\displaystyle i_{0}}   phải có một ô [ i 0 , j 1 ] {\displaystyle [i_{0},j_{1}]}   nào đó giảm đi lượng h để tổng hàng hoá trong dòng không đổi, tiếp theo, hàng trong cột j 1 {\displaystyle j_{1}}   giảm đi tại [ i 0 , j 1 ] {\displaystyle [i_{0},j_{1}]}   thì phải tăng trong cùng cột j 1 {\displaystyle j_{1}}   tại dòng i 1 {\displaystyle i_{1}}   cùng cột ngiã là tại ô [ i 1 , j 1 ] {\displaystyle [i_{1},j_{1}]}  ,... sau một số hữu hạn bước, mỗi bước chuyển từ đi theo hàng sang đi theo cột ta quay về gặp ô cùng cột với ô đầu tiên, ô [ i k , j 0 ] {\displaystyle [i_{k},j_{0}]}   để giảm lượng hàng ở đó đi một lượng đúng bằng h, nghĩa là ta có một chu trình.

  Định nghĩa

   

  Ví dụ hai chu trình trong bảng vận tải, mỗi chu trình là một đường đi khép kín luôn rẽ một góc vuông tại mỗi bước của nó, những ô nằm trên đường thẳng mà nó đi qua không nằm trong chu trình

  Một chu trình trong bảng vận tải là một dãy các ô trong đó ô đầu tiên và ô thứ hai nằm trên cùng một dòng, hai ô liên tiếp hoặc nằm trên cùng một dòng, hoặc cùng nằm trên một cột, ba ô liên tiếp không nằm trên cùng một hàng hoặc một cột, ô đầu tiên và ô cuối cùng nằm trên cùng một cột. Có thể viết dãy các ô trong chu trình như sau

  [ i 0 , j 0 ] , [ i 0 , j 1 ] , [ i 1 , j 1 ] , [ i 1 , j 2 ] , . . . , [ i k , j 0 ] {\displaystyle [i_{0},\;j_{0}],[i_{0},\;j_{1}],[i_{1},\;j_{1}],[i_{1},\;j_{2}],...,[i_{k},\;j_{0}]}  

  Có thể hình dung chu trình là một đường đi khép kín qua các ô của bảng vận tải trong đó cứ mỗi lần qua một ô nó lại rẽ một góc 90 0 {\displaystyle 90^{0}}  .

  Tính chất

  1. Một phương án là phương án cơ sở khi và chỉ khi trong tập các ô chọn của nó sở không có chu trình.
  2. Mỗi ô tự do trong một phương án cơ sở tạo với các ô cơ sở một chu trình duy nhất được gọi là chu trình điều chỉnh của ô tự do.
  3. Khi điều chỉnh tăng số lượng hàng hoá h≥ 0 vào ô tự do lượng hàng hàng phân phối cho các ô trong chu trình xen kẽ tăng giảm một lượng bằng h. Lượng hàng h tối đa có thể tăng 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 {\displaystyle v_{i_{0},\;j_{0}}}   là tổng đại số của các cước phí c i , j {\displaystyle c_{i,\;j}}   với các dấu cộng trừ xen kẽ tương ứng với các ô được cộng và trừ đi trong chu trình điều chỉnh của ô tự do [ i 0 , j 0 ] {\displaystyle [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 tăng [hoặc giảm] đi h ∗ v i , j {\displaystyle h*v_{i,\;j}}   tuỳ theo giá của ô đó v i , j {\displaystyle v_{i,\;j}}   là dương hay âm.

  Tiêu chuẩn tối ưu

  Phương án cơ sở của BTVT là tối ưu khi và chỉ khi nó không có ô tự do với giá trị âm.

  Phương pháp thế vị tính giá của ô tự do

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

  Đưa thêm m+n ẩn p 1 , p 2 , . . . , p m {\displaystyle p_{1},\;p_{2}\;,...,\;p_{m}}   và q 1 , q 2 , . . . , q n {\displaystyle q_{1},\;q_{2}\;,...,\;q_{n}}  .

  Hệ m+n-1 phương trình p i + q j = c i , j {\displaystyle p_{i}+q_{j}=c_{i,j}}   với m+n-1 ô cơ sở có thể giải dễ dàng nhờ cho một ẩn, chẳng hạn p 1 = 0 {\displaystyle p_{1}=0}  . Khi đó giá của các ô tự do [i, j] được tính bằng công thức v i , i = p i + q j {\displaystyle v_{i,i}=p_{i}+q_{j}}  .

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

1. ^ G. Monge. Mémoire sur la théorie des déblais et des remblais. Histoire de l’Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année, pages 666–704, 1781.