Xem mẫu
- 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.
Biểu diễn đồ thị của bài toán vận tải
M ục lục
[ẩn]
1 Bài toán
•
o 1.1 Phương án vận chuyển
o 1.2 Hệ ràng buộc
o 1.3 Cân bằng cung cầu
2 Giải thuật
•
o 2.1 Tìm phương án ban đầu
2.1.1 Quy tắc góc Tây Bắc (northwest corner
rule)
2.1.2 Quy tắc cước phí nhỏ nhất
o 2.2 Tiêu chuẩn tối ưu và điều chỉnh giảm giá
2.2.1 Ô cơ sở và ô tự do
2.2.2 Chu trình trong bảng vận tải
2.2.3 Tiêu chuẩn tối ưu
3 Các bài toán biến thể
•
4 Liên kết ngoài
•
[sửa] Bài toán
Giả sử có m kho hàng A1,..,Am cùng chứa một loại hàng hóa, kho Ai chứa ai tấn hàng.
Cần vận chuyển số hàng trên đến n cửa hàng B1,...,Bn, cửa hàng Bi cần số hàng bi.
- Cước phí vận chuyển một tấn hàng từ kho Ai đến cửa hàng Bj là cij. 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 dữ liệu và phương án X[i, j] của bài toán vận tải
Bảng trên đây được gọi là bảng vận tải.
[sửa] Phương án vận chuyển
Mỗi phương án vận chuyển là một ma trận X = , trong đó xij là số hàng hóa
chuyển từ Ai đến Bj. ( )
Chi phí vận chuyển của phương án X là:
[sửa] 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ị xi,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ới mọi i=1,..,m.
và các ràng buộc với các điểm thu (ràng buộc cột)
với mọi j=1,..,n.
- 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 n biến, hàm mục
tiêu G(X) cần cực tiểu và m+n ràng buộc.
[sửa] Cân bằng cung cầu
Tổng số hàng dự trữ ở m điểm phát (cung) là , tổng số nhu cầu của n
•
điểm thu (cầu)là . 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 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ả Bn
+ 1 với cước phí ci,n + 1 = 0 với mọi i=1,...,n.
Nếu cầu nhiều hơn cung thì một số hàng hóa sẽ thiếu cho
•
các điểm thu. Ta biểu diễn việc này bằng cách bổ sung một điểm phát giả Am + 1
với cước phí cm + 1,j = 0 với mọi j=1,...,m.
Như vậy bài toán vận tải luôn được đưa về bài toán thỏa mãn điều kiện cân
•
bằng cung cầu.
[sửa] Giải thuật
Giải thuật giải bài toán vận tải cũng là thuật toán đơn hình. Nó xuất phát từ việc chọn
phương án đầu tiên rồi cải tiến dần cho đến khi đạt tối ưu.
[sửa] Tìm phương án ban đầu
Có một số phương pháp tìm phương án ban đầu.
[sửa] Quy tắc góc Tây Bắc (northwest corner rule)
Phương pháp này trước hết phân phối lượng hàng lớn nhất có thể được vào ô dầu tiên
ở góc tây-bắc, nghĩa là ô (1,1), bằng cách đặt x11 = min(a1,b1). Khi đó hoặc điểm phát
A1 hết hàng, hoặc điểm phát B1 hết nhu cầu, ta có thể loại điểm phát A1 hoặc điểm B1
ra khỏi bảng, rối lại tiếp tục phân phối cho ô tây bắc trong phần còn lại của bảng.
Với ví dụ cho ở trên ta có
- Phương án đầu tiên lập theo quy tắc góc tây bắc
Các số nhỏ ghi ở góc trên mỗi ô là cước phí vận chuyển mỗi đơn vị hàng hoá từ điểm
phát thứ i đến điểm thu thứ j.
Khi đó 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 chưa phải là phương án tối ưu.
[sửa] Quy tắc cước phí nhỏ nhất
Ta cũng lần lượt phân phối vào các ô như trên nhưng tiêu chuẩn ưu tiên là cước phí
nhỏ nhất trong những ô còn có thể phân phối.
Trong ví dụ trên
Phương án đầu tiên lập theo quy tắc ưu tiên cước phí nhỏ nhất
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
[sửa] Tiêu chuẩn tối ưu và điều chỉnh giảm giá
[sửa] Ô cơ sở và ô tự do
- Sau khi dùng một trong các phương pháp lập phương án ban đầu (ngoài hai phương
pháp trên còn có một số phương pháp khác), trong các phương án nhận được ta được
một số ô (i, j) có giá trị xi,j > 0, các ô đó được gọi là các ô chọn một số ô khác có xi,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.
[sửa] 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 (i0,j0) được tăng
thêm một lượng hàng h. Khi đó trong dòng i0 phải có một ô (i0,j1) 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 j1 giảm đi tại (i0,j1)
thì phải tăng trong cùng cột j1 tại dòng i1 cùng cột ngiã là tại ô (i1,j1),... 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, ô (ik,j0) để 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
- 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 900.
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 là tổng đại số của các cước phí 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 . 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 tuỳ theo giá của ô đó là
dương hay âm.
[sửa] 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 và .
Hệ m+n-1 phương trình pi + qj = ci,j với m+n-1 ô cơ sở có thể giải dễ dàng nhờ cho
một ẩn, chẳng hạn p1 = 0. Khi đó giá của các ô tự do (i, j) được tính bằng công thức vi,i
= pi + qj.
nguon tai.lieu . vn