Xem mẫu
- Chương IV
BÀI TOÁN VẬN TẢI
§1 MÓ HÌNH TOÁN HỌC CỦA BÀI TOÁN VẬN TẢI
Tìm mn sô thực 'X,)} thoả mãn các điểu kiện sau:
m n
Zj5LC‘JXU ~► min(max) (4.1)
i=l J = 1
= 3ị,i = l,ni (4.2)
j=l
ỉxu =bpj = l,n
(4.3)
1=1
X.Ị > 0. i = l,m; j - l.n (4.4)
ỉa- =Ẻbi
(4.5)
1-1 ,j = l
Nhận xét Bài toán vận tải là một bài toán'quy hoạch
tuyến tính dạng chính tác, vì vậy các định nghĩa , các định
lý đối với bài toán quy hoạch tuyến tính đều có thê áp dụng
cho bài toán vận tải và đương nhiên có thể giải nổ bàng
phương pháp đơn hình. Nhưng do cấu tạo đặc biệt của bài
toán vận tải, người ta đã xây dựng một số phương pháp
khác đê giải nó đơn giản và tiện lợi hơn.
Ta có thể mô tả bài toán vận tải dưói dạng bản như sau:
Ta xây dựng một bảng gồm m hàng, n cột. Mỗi hàng
đặc trưng cho một trạm phát, còn mỗi cột đặc trưng cho
một trạm thu.
182
- - Hàng trên cùng ghi tên các trạm thu B,và nhu cẩu b,
tương ứng (i = l.w).
- Cột đầu ghi tên các trạm phát A, và khả năng cung
cấp a, tương ứng (i - ỉ.m ).
- Trong bảng, giao của hàng i và cột j gọi là ô (i, j) - đặc
trưng cho đoạn đường nối trạm phát A, tới trạm thu Bj, nên
ở góc trên bên trái mỗi ô này ta ghi c,j (tính theo km hoặc
cước phí vận chuyển một đơn vị hàng hoá từ trạm phát A,
đến trạm thu Bj). Mỗi ô (i,j) còn tương ứng với một biến X,J
(lượng hàng cần xác định để vận chuyển từ Aj đến Bj ),
đồng thời tương ứng VỚI một vectơ Aị/hệ sô của biến Xịj)
trong hệ ràng buộc (4.2) và (4.3). Như vậy mọi dữ liệu của
bài toán vận tải đều được thể hiện trên bảng 4.1, gọi là
bảng vận tải.
Bảng 4.1
\^Thu B, B, B„ 1
hát (b|) (bj) (b) 1
(b„)
A, (ã,) c„ c,2 Cũ c,n
X,, x12 x,i x,„
A2 (a2) C21 C22 C2j C'2n
X’2I x.„ x,i x2u
A, (a,) cu Cl2 Cu Cịn
Xi, x12 x.i Xin
A,„ (a,„) c
v III1 C|,|2 c Hi.l r
X
Xrnl ___ xm. ____________ ±1X111
Ta ký hiệu A là ma trận hệ số của các ẩn trong hệ (4.2)
và (4.3), thì A có dạng:
- .1
11..
.1
11..
.1
11..
A=
1 1 1
1 1 1
1 1 1
Véc tơ A,J - hệ số của Xịj có thành phần thứ i và (m+j)
bằng 1, còn (m + n - 2) thành phần còn lại đều bằng 0.
0
0
0
0
0
§2. CÁC TÍNH CHÁT cơ BÀN CỦA BÀI TOÁN VẬN TÀI
Ngoài những tính chất chung của bài toán quy hoạch
tuyến tính, bài toán vận tải còn có những tính chất riêng
sau đây;
Dịnh lý 4.1. Bài toán vận tải cần bằng thu phát bao
giò cũng có phương án cực biên tôi ưu.
184
- DỊnh lý 4.2. Ma trận hệ sô A cùa hệ ràng buộc (4.2) va
(4.3) có hạng bằng (m+n-1).
Nóị cách khác hệ (4.2) và (4.3) có m-ì- n- 1 ráng buộc
độc lập tuyên tính.
Từ đây liên hệ với phương án cực biên của bài toán quy
hoạch tuyến tính ta suy ra:
- Phương án cực biên của bài toán vận tải có không quá
(m + n - 1) thành phấn dương.
- Phương án cực biên của bài toán vận tải gọi là không
suy biến nếu nó có dũng (ni+n-1) thành phần dương và gọi
là suy biến nếu nó cỏ it hơn (m+n-1) thành phần dương.
- Mỗi phương rán cực biên đểu ứng vơi ít nhất một cơ sở
gồm (m+n-1) véctơ A„ độc lập tuyến tính. Nếu X = {x,jl là
phương án cực biên không suy biến, thì chi’ có một cơ sở
duy nhất, đó là hệ |A,.:Xij > OỊ gồm (m+n-l) vec tơ độc lập
tuyên tính.
Trò' lại bảng vận tải, ta tháy giữa các ô (1. j) và các véctơ
A„ của an xi; có sự tương ứng (1-1)
- O(i,j) dược gọi là ớ chọn nếu có lượng hàng phân phối
x„ > (ì và gọi la ô loại nếu xh = 0. Như vậy một'phương án
cực biên có không quá (m+n-1) ó chọn.
- Phương án cực bièn dược gọi là không suy biến nếu nó
có dũng (m+n-1) ô chọn và là suy biến nếu nó có ít hơn
(m+n-1) ỏ chọn.
Đê thay rỏ hơn tinh dộc lập hay phụ ihuộc của hệ véctơ
|A„| gắn với sự phan bò cùa các ô tương ứng với chúng
trong bảng vặn tải. ta xét hệ vec tơ:
trong (16 tất ca các chi số thứ nhất (chí hàng) và các chỉ
sô thứ hai (chi cột) chi xuất hiện đúng 2 lần.
185
- Nếu ta nôi những ô tương ứng cúa báng vơi hệ véctơ trên
bơi những đoạn nằm ngang và thang đứng, chúng ta sẽ
nhận ra được một chu trình khép kín hay còn gọi là vòng.
Một sô ví dụ về vòng được chỉ ra trên hình 4.1,2,3
Hình 4.1 Hình 4.2 Hình 4.3
đứng trưốc nó. đồng thòi nằm cùng cột (cùng hàng) chỉ vói
một ô đứng sau nó.
Từ dinh nghĩa trên ta thấy: Một hàng hoặc một cột mà
vòng đi qua bao giờ cũng chỉ có hai ô thuộc vòng. Do đó
tổng sô ô trên vòng là một sô chẵn và ít nhất là bôn ô.
Định lý 4.3. Điêu kiện cần và đủ để một tập hợp ô đà
cho có chứa vòng là hệ vec tơ {AijỊ tương ứng phụ thuộc
tuyến tính.
Hệ quả 4.1. Một tập hợp gồm (m+n) ô của bảng vận tải
bao giò cũng chứa vòng.
Hệ quả 4.2. Một phương án của bài toán vận tải là
phương án cực biên khi và chỉ khi tập hợp ô chọn của nó
không chứa vòng.
Định lý 4.4. Một phương án cực biên của bài toán vận
tài có đủ sô tôì đa (m+n-1) ô chọn, thì một ô loại bất kỳ sẽ
tạo nên một vòng duy nhất vâi một sô ô chọn.
186
- §3. XÂY DỰNG PHƯƠNG ÁN cực BIÊN
I. PHƯƠNG PHÁP GIÁ CƯỚC BÉ NHẤT
Nguyên tắc phân phối: ưu tiên phân phôi hàng vối mức
tôi đa vào ô có giá cưâc c,j nhỏ nhất trong phạm vi các ô
còn xét.
Ban đầu tất cả các ô (i,j) trong bảng đều thuộc vào các ô
còn xét. Giả sử c,.k = min {Cự V(i,j), ta phân cho ô (r,k) một
lượng x,.k lớn nhất có thể được, tức là xrk = min {a,., bk}.
- Nếu x,.k = bk thì nhu cầu của trạm Bk được thỏa mãn,
ta loại các ô ở cột Bk ra khỏi phạm vi các ô còn xét và sửa
lại khả năng của trạm phát A,:
a’r = ar - x,.k = a, - bk > 0
- Nếu x,.k = a,., thì ở trạm A,. đã phát hết hàng, ta loại
các ô trên hàng A,. ra khỏi phạm vi các ô còn xét và sửa lại
nhu cầu của trạm thu Bk:
b’k = bk-x,.k = bk - a, > 0.
- Nếu xkl = a,. = bk thì loại các ô của hàng A,. và cột Bk ra
khỏi phạm vi câc ô còn xét .
Vổi các ô còn xét mới này, ta lại tiến hành như trên. Cứ
như thê tiếp tục cho đến khi tất cả các hàng và các cột của
bảng vận tải bị loại khỏi phạm vi các ô còn xét. Tất nhiên
khi đó mọi trạm phát dều phát hết hàng và nhu cầu của
mọi trạm thu đều được thoả mãn (do giả thiết bài toán
dạng cân bằng thu phát). Khi đó các ô được phân phối có
xM>0. ta có x„= 0 đối vỏi những ô không được phân phôi.
Người ta chứng minh được rằng: Hệ thống sô
X = ix,,Ị (/= l.m; / = l.n) xây dựng theo phương pháp
giá cước bé nhất là một phương án cực biên.
187
- 2. PHƯƠNG 1 HÁP PHỎGHEN
Ta gọi hiện c,r cùa ô có giá cước thấp nhi và ô có giá cứức
thấp nhất cùa một hàng (cột) là giá cữỏc chênh lệch cua
hàng (cột) ày.
Nguyên tắc phàn phối: Phân vào ô có giá cưởc thấp
nhất của hàng hay cột có giá cước chênh lệch lớn nhất và
phân với lượng tôi đa có thể. Sau khi phân vào một ô. ta
tính lại giá cước chênh lệch của các hàng và các cột trong
phạm vi còn xét để phân phối tiếp. Khi tất cả các hàng và
các cột đều thoả mãn, ta được một phương án cực biên.
Chú ý: Nếu dùng một trong hai phương pháp trẽn (lê
tìm phương án cực biên xuất phát mà sô ô chọn (ứng VÓI x„
>Ó) chưa đủ số tối đa (m+n-1) ô. thì ta phải bô sưng thêm
cho đủ (m+n-1) ô vôi điều kiện các õ ấy không tạo vòng.
Những ô bô sung thêm, ta ghi lượng hàng phân phôi bằng
0 và được gọi là ô chọn bô sung. Tất nhiên có nhiều cách
chọn ô chọn bỏ sung, nhưng thõng í hường í a chọn những ô
có giá cước thấp .
§4 PHƯƠNG PHÁP THỂ VỊ GIẢI BÀI TOÁN VẬN TẢI
l. TIÊU CHUẨN TỐI ƯU
Xét bài toán
ni 11
«X)=EXciixii ^min (4.1)
i=l .1 = 1
n ______
Exu =ai,i = l,m (4.2)
_i=l
ni _____
Exu =bi,j = l,n (4.3)
t-1
188
- X „ > 0, i = 1, m; j = 1, n (4.4)
ỉa.=£b,
(4.5)
1-1 1-1
Nếu ta ký hiệu Uị (i = 1,111),Vj(j = 1,11) là những biến
đối ngẫu ứng với hệ ràng buộc (4.2) và (4.3), u = {u}, V =
ịv}, G (U,V) là hàm mục tiêu cua bãi toán đối ngầu.
Khi đó bài toán đối ngẫu có dạng:
G(U,V) = ^a,Uị + ^bJvJ —>max (4.6)
1~1 Í--1
u, 4-v, 0 và U| + V, < Cỹ.(i = l,m;j = l,n)
Theo định lý đối ngẫu hai. thì điều kiện cần và đủ để
hai phương án X = iXịị} và (U, V) = (Uị, Vị} của cặp bài toán
đôi ngẫu tương, ứng tốt nhất là: nếu X|j > 0 thì u,.+ Vị = Cjj
hoặc nếu u, + Vị< C.ịthì Xịj - 0, (i = l,m;j = l,n)
Từ đó ta có the suy ra tiêu chuẩn tôi ưu sau:
Định lý 4.5. Điều kiện cẩn và đủ dể phương án X = {x,,}
của bài toán vận lải tối ưu là tồn tại hệ thông sô ỊU,. V,}
thoả mãn.
a. u, + V, < cir V (i.j)
b. Uj + V, = c„ nếu Xjj > 0
2. THUẬT TOÁN CỦA PHƯƠNG PHÁP THẾ VỊ
Gia sừ bằng phương pháp gia cước bé nhất hav phương
I 'ú'- ĩ'11'ghen ta có một phương án t.ưc biên X - ỊXị)} có đủ
1 • )-
- Bước 1. Xâ> dựng hệ thông thê vị.
Xét hệ phương trình:
Uị + Vj = c„ vôi (i,j) là các ô chọn (4.8)
' Hệ này gồm m+n-1 phương trình độc lập với m+n ẩn,
nên hệ vô định. Vì vậy ta có thể cho bất cứ ẩn nào làm ẩn
tự do.
Quả trình xây dựng hệ thống thế vị được thực hiện như
sạu:
Cho một hàng hay một cột nào đó một thê vị tuỳ ý (tức
là chọn u, hay Vj tương ứng làm ân tự do) chẳng hạn cho
hàng i một thế vị u, = 0. Sau đó ta xác định thê vị của các
hàng, cột khác theo điều kiện b) của tiêu chuẩn tối ưu, tức
•là
1 Vị = Cjj - u, vởi u, đã biết, (4.9)
u, = c,) - Vj với Vj đã biết, (4.10)
đối với (i,j) là các ô chọn.
Thê vị u, ghi ở bên phải hàng i, thê vị Vị ghi phía dưới cột j.
Vì hệ (4.8) gồm(m-t-n-l) phương trình độc lập, nên ta
tính được (m+n-1) thế vị khác nhau theo (4.9),và (4.10).
cùng vâi thê vị u, cho trưởc, ta được toàn bộ thê vị của câc
hàng, cột.
Sau đó ta chuyển sang bưóc hai.
Bước 2. Kiểm tra tiêu chuẩn tối ưu.
Hệ thông kê vị xây dựng ở bước 1 đã thoả mãn điểu
kiện b) của tiêu chuẩn tôi ưu, nên ta chỉ cần kiểm tra điều
kiện a) đôi vói các ô loại.
- Nếu u, + V, < Cu đôi với mọi ô loại, thì phương án
đang xét X tương ứng là tôi ưu.
190
- - Nếu tồn tại ít nhất một ô loại mà u, + Vj> c,|, thì
phương án X chưa tối ưu. Ta gọi những ô này là những ô vi
phạm. Tính Ajj = Uị+v,- c,j đôi với tất cả những ô vi phạm
(hiển nhiên Aịj >0). Chuyển sang bưổc 3.
Bước 3. Điều chỉnh phương án.
Giả sử maxAij = Ark, (Aij > 0) ta gọi (r,k) là ô điểu chỉnh.
Theo định lý 4.3, ô loại (r,k) sẽ tạo nến một vòng duy
nhất với một số ô chọn. Phát hiện vòng này, rồi đánh dấu
lẻ, chẵn cho các ô trên vòng bắt đầu từ ô điểu chỉnh.
Gọi 0 = min {Xij} đối vói (i,j) là các ô chẵn trên vòng.
Điều.chỉnh từ X sang phương án mới X' như sau:
Xịj - 0 với (i, j)là ô chẵn trê n vòng
X ii + 6 với (i, j)là ô lẻ trê n vòng (4.11)
X d với (i, j) không thuộc vòng
Như vậỵ ô điều chỉnh (r.k) trở thành ô chọn với x’lk= 0
còn ô chẵn trên vòng có X,) =0, sẽ trở thành ô loại với x’,) = 0.
Nếu có nhiều ô chẵn trên vòng cùng có Xij = 0, thì
ta chỉ đưa một trong các ô đó làm ô loại, còn các ô khác
vẫn xem là'ô chọn mặc dầu x’,j = 0. Làm như vậy X' =
{x\jỉ vẫn có đủ (m+n-1) ô chọn.
Ta có các khẳng định sau:
1. X' ={x’ij} là phương án cực hiên có đủ (m+n-1) ô chọn.
2. f(X')= f(X) - GArk. Như vậy từ X chuyển sang X' thì
giá trị của hàm f(X) giảm đi một lượng 0.Ark>0 nếu 0 > 0.
Đôi với phương án cực biên mới X', ta quay lại bước 1
và lặp lại quá trình.
3. Nếu bài toán vận tải không suy biến (tức là mọi
phương án cực biên của nó đều không suy biến), thì áp
191
- dụng phương pháp thê vị sau một sô hữu hạn bước lập, ta
sẽ nhận được phương án tôi ưu của bài toán.
Một sô chú ý:
1. JỚ mỗi bước lặp, nếu có nhiều ô loại vi phạm tiêu
chuẩn tối ưu, tức là Ajj >0 ở nhiều ô loại. Đối với mỗi ô vi
phạm có thể tính tích Aij0(ij) tương ứng và chọn max Aịj0"J-
Ark.0, thì ô (r, k) được chọn là ô điều chỉnh. Khi đó hàm
mục tiêu sẽ giảm nhanh hơn.
2. Trường hợp bài toán suy biến thì 0 có thể bằng 0.
Khi 6 = 0, ta vẫn thực hiện thuật toán một cách bình
thường,, nghĩa là ô điều chỉnh sẽ trở thành ô chọn với lượng
hàng bằng 0, còn ô ứng với Xjj = 0 ở trên vòng sẽ trở thành ô
loại trong phương án mởi. Tuy nhiên kết quả điều chỉnh
không làm thay đổi phương án cực biên mà chỉ thay đổi tập
véctơ cơ sở ứng với phương án cực biên.
Dấu hiệu xuất hiện phương án cực biên suy biến là:
Trong quá trình điều chỉnh 0 đạt tại nhiều ô khác nhau,
những ô này đều có thể loại khỏi tập ô chọn. Nhưng theo
chuật toán, khi đó ta có thể chỉ loại một trong những ô ứng
với 0 theo qui tắc ngẫu nhiên, những ô còn lại ứng với 0
vẫn nằm trong tập ô chọn. Vối tư cách là các ô chọn bô
sung ( với x\j = 0 trong phương án cực biên mới).
3. Khi phương án cực biên X không suy biến thoả mãn
tiêu chuẩn tối ưu:
Ui+Vj < Cij đối với mọi ô loại.
thì phương án tối ưu X tìm được là duy nhất.
Còn nếu u, + Vj = Cịj đối với ít nhất một ô loại, thì
phương án tốì ưu tìm được không duy nhất. Trong trường
hợp này, nếu cần thiết ta có thể tìm các phương án cực
biên tối ưu khấc và cả tập phương án tối ưu.
192
- Ví dụ 4.1. Giải bài toán vận tải sau:
Bảng 4.2
X. Thu
20 60 40 25 45
Phát\^
50 7 4 14 11 10
35 10 13 15 18 16
50 4 2 6 10 9
55 9 7 9 15 8
Kết luận vể phương ản tối ưu. Nếu không duy nhất,
hãy chỉ ra một phương án cực biên tối ưu khác và xây dựng
tập phương ản tối ưu.
Giải. Dùng phương pháp giá cước bé nhất xây dựng
phương án cực biên xuất phát. Đó là phương án cực biên
không suy biến cho ở bảng 4.3
Bảng 4.3
Thu
20 60 .40 25 45
Phát
7 4 14 11 10
50
[20] [10] [20]
10 13 15 18 16
35
+4 [30] [5]
4 2 6 10 9
50
ị +1 [50]
9 7 9 15 8
55
u [10] [45]
Vj 7 4 8 11 7
193
- Cho U| = 0. lần lượt tính câc thê vị hàng và cột khác
theo (4.9) và (4.10). Kiểm tra tiêu chuẩn tốì ưu đôi vâi các ô
loại. Đối vói các ô vi phạm, tính Ay = új + Vj - c,) >0 và ghi
nó vào ô tương ứng với dấu + ở phía trước, cụ thể A21 = +4,
A31 = +1, max Ajj = A2l = +4 (Ad> 0).
0 (2,1) được chọn là ô điểu chỉnh. Vòng tạo bởi ô điểu
chỉnh vối các ô chọn đó là (2,1), (1,1), (1,4), (2,4). ở đây 0
= min {40,10} = 10. Thực hiện phép biến đổi (4.11) cho các
ô trên vòng, kết quả thu được phương án cực biên mới ghi
trong bảng 4.4
Bảng 4.4
Thu
20 60 40 25 45
PhÉưX^
7 4 14 11 10
50
[15] Ĩ1ỌJ [25] +1
10 13 15 18 16
35
[5] [30]
4 2 6 10 9
50
+1 [50] +4
9 7 9 15 8
55
i [10] [45]
7 4 12 11 11
Có ba ô Vi phạm tiêu chuẩn tối ưu vói A|5 = +1, A3l = +1,
A33 = +4, max Aij = +4 (Ajj > 0). ộ (3,3) là ô điều chỉnh. Vòng
tạo bởi ô điều chỉhh Và cảc ô chọn đi qùa các ô (3,3), (3,2),
(1,2), (1,1), (2,1), (2,3). ở đây G = min {30, 50, 15} = lõ.
Sau khi điều chỉnh, ta được phương án cực biên mới ở
bảng 4.5
194
- Bảng 4.5
\Thu
Phál~'\ 20 60 40 25 45
7 4 14 11 10
50 [25] 0
[25]
10 13. 15 18 16
35 [20] +0 7
[15]
4 2 6 10 9
50 [35] -2
[15]
9 7 9 15 8
55 1
[10] [45]
3 4 8 11 7
Kiểm tra tiêu chuẩn tối ưu ta thấy:
Ui + Vj < Cịj V (i,j)
nên phương án cực biên ở bảng 4.5 là tôì ưu. Phương án
tối ưu tìm được khôngduy nhất vì A21 = 0 với (2,4) là ô loại.
Để tìm một phương án cực biên khác, ta chọn ô (2,4)
làm ô,điều chỉnh. Vòng tạo bỏi ô (2,4) và cảc ô chọn đi qua
các ô: (2,4), (1,4), (1,2), (3,2),(3,3), (2,3). Ở đây e = min {25,
35, 15} = 15. Điều chỉnh vòng này ta được phương án cực
biên toi ưu mới cho ờ bảng 4.6.
Bâng 4.6
\Thu
Phát^\ 20 60 40 25 45
7 4 14 11 10
50 [40] [10]
10 13 15 18 16
35 [20] [15]
4 2 6 10 9
50 [20] [30]
9 7 9 15 8
55 [10] [45]
195
- Vì bài toán chỉ có hai phương án cực biên tôi ưu, nên
tập phương án tổì ưu có dạng:
25 + d 0 25-d
0 15-d d
với 0 < d < 15
35-d 15 + d 0
0 10 0
f(X) = 1410
§5. CÁC TRƯỜNG HỢP ĐẶC BIỆT
I. BÀÌ TOÁN KHÔNG CÂN BANG thu phát.
1. Trưòng hợp
/=1 7=1
Để chuyển về bài toán cần bằng thư phát, ta đưa, vào
một trạm thu giả Bn^ với nhu cầu bnT, = ■ dây
chính là lượng hàng còn tồn lại ở các trạm phất' sau khi
thoả mãn nhu cầu của tất cả các trạm thu. Lượng hàng
này không vận chuyển đi nên cước phí vận chuyển bằng 0.
Do đó trong bảng vận tải khi đã đưa thêm trạm thu giả
B11+1 ta ghi ci l)+1=o ơ = !,/») ”
2. Trường hợp ^aì <
»=1 7=1
Để đưa vê bài toán cân bằng thu phát, ta thêm vào
một trạm phát^iả A,ll+1 với khả năng cụng cấp:
a„„ì = - đây là tổng lượng yêu cầu không nhận
được ở cầc trạtìl thu, nên ta ghi Clll+lj=0 ( / = l,n) vì thực
chất không có vận chuyển hàng từ trạm phát giả đến các
trạm thu.
196
- BÀI TOÁN CÓ DẠNG cực ĐẠI
Mô hình bài toán có dạng:
f(X) = Èẳcijxu ->max
(4.12)
i=i )=I
ẳxij =
(4.13)
j=l
£x„ =bj,j = l,n (4.14)
i=l
X ii > 0,i = 1, m; j = 1, ĩĩ (4.15)
(4.16)
1=1 i=l
Để giải bài toán này ta có thể chuyển vê giải bài toán
min vôi hàm z = - f -> min hoặc có thể giải trực tiếp.
+ Đe xây dựng phương án cực biên xuất phát, ta có thể
dùng phương pháp "C,) lớn nhất", nghĩa là ưu tiên phàn
phối với mức tôi đa vào ô có hiệu quả lớn nhất trong phạm
vi các ô đang xét.
+ Việc xây dựng hệ thống thê VỊ giông như đôi với bài toán
min bằng cách giải hệ: u+v, = Cjj đối với (m+n-1) ô chọn
+ Kiểm tra tiêu chuẩn tốì ưu:
Ui + Vj > Cịj đối với các ô loại.
- Nếu thoả mãn với mọi ô loại thì thuật toán dừng.
- Nếu chưa thoả mãn, tức là tồn tại ít nhất một ô loại
(i,j) mà Uị+V) < c„ hay Ajj = Uị + Vj - Cij
- III. BÀI TOÁN CỒ Ò CẤM VÀ CÁC GIÁ THIẾT PHỤ
Trong thực tê ta có thể gặp các bài toán vận tải, trong
dó có cấm vận ở một sô nơi, nghĩa là do những điều kiện
thực tê đặt ra mà hàng từ A, khống chuyển tới Bj khi đó gọi
ô (i,j) là ô cấm.
Sau đâv ta xét một sô trường hợp và cách xử lý.
1. Nếu A, không chuyển hàng cho B,, thì trong bảng vận
tải ở ô(i,j) thay cho cước phí co ta ghi cước phí cấm M
(trong đó M là một số dương lớn tuỳ ý khi cần so sánh).
Làm như vậy khác nào ta đánh cước rất nặng ở ô (i, j),
khiến cho trong phương án tối ưu ô (i,j) không thể được
phân phối hàng.
2. Nếu Xịị > a (0 < a
- là lượng hàng vận chuyển tiếp từ A, đến B, không vượt quá
(P - à).
5. Nếu X,, = a. tức là A, chuyên cho B, đúng lượng a.
Trước khi lập bảng, ta trừ trước vào khả nàng phát và
thu của hai trạm Aj, Bj một lượng a. Trong bảng vận tải ta
ghi cựâc phí cấm M và ô (i,j) tương ứng.
tu II
6. Khi >5>,. có thêm giả thiết: ở một sô trạm
phát không'được cíe hàng tồn kho (cần giải phóng kho
do yêu cầu ), thì trong bảng ta ghi cưóc phí cấm M vào
các ô tương ứng giữa các trạm phát cẩn giải phóng kho
và trạm thu giả Bll+|.
7. > ^hị mà Ai chỉ được chuyển đi từ a đến p, tức
là '
a
- 9. Khi > mà A, chuyển đi ít nhất a. Như vậy
lượng còn lái' (a, - đ) vẫn có thể chuyển cho các trạm thu
thật hoặc tồn kho. Vì vậy trong bảng ta tách A, thành hai
trạm: A’, vói khả năng phát a và A”, vởi khả năng phát (a, -
a). Ta ghi cưâc phí cấm M vào ô tương ứng giữa A’, và thu
giả Bn+I, cước ghí 0 giữa A”i và B11+1.
10. Khi nià lượng hàng A, để tồn kho
nằm trong kirốảng ['à1, p], tức là
a < xi H^ < [3 0 < X i,n+ĩ -a< p -a
-ta trở về trường hợp 3. Như vậy sau khi đã bớt đi một
lượng a mà chắc chắn Aị phải để tồn kho, trong bảng ta
tách Aj thành hai trạm: A’i vói khả năng phát (a, - P) và A”i
với khả năng phát (P - a). ta ghi cước phí cấm M vào ô
tương ứng giữa A’i và Bn+l.(/cưỏc phí 0 giữa A” và BI1+|.
Tương tự khi mà có thêm các giá thiết
sau:'
a. Bj được ưu tiên nhận đủ hàng.
b. B, nhận được từ Pi đến p.j đơn vị hàng
/=l
c. B) nhận được đúng một lượng bằng p.
d. Bj nhận được ít nhất một lượng a.
e. Lượng hàng mà Bj nhận thiếu nằm trong khoảng
[a.pi
(a < x„iHj < P) thì cách xử lý hoàn toàn tương tụ như
trên.
Chú ý.
200
- - Khi xuất hiện các giả thiết, thì ta phải xử lý các giả
thiết trước khi tính tông lượng phát và thu để chuyển vể
bài toán cân bằng thu phát.
- Đối vối bài toán f(X) -> max, khi xuất hiện ô cấm, ta
ghi cước phí cấm - M (với M là một số dương lớn tuỳ ý).
- Khi -xây dựng phương án cực biên xuất phát, ta nên
tránh phân vào ô cấm, để hy vọng bớt bưóc lặp trong thuật
toán.
Ví dụ 4.2. Cho bài toán vận tải dạng bảng (cưóc phí
tính theo đơn vị nghìn đồng/tấn)
Thu
Phát/^^L 320 400 300
180 30 70 20
220 50 10 20
360 50 lõ 35
140 40 45 15
Biết rằng B:i nhận tối đa 260 tấn, B^được ưu-tiên nhận
đủhàng, Bị nhận thiếu không quá 20 tấn.
Hãy tìm phương án vận chuyển tối ưu và tính tông chi
phí tương ứng.
GIẢI
Xử lý giả thiết:
- Vì B2 được ưu tiên nhân đủ hàng, nên trong bảng ta
ghi cước phí cấm M vào ô tương ứng giữa phát giả A5 và B2.
- Bị nhận tôi đa 260, nên trong bảng ta thay nhu cầu
của B; bởi 260.
201
nguon tai.lieu . vn
