Chương 5: Bài toán vận tải và thuật toán thế vị

Chia sẻ: Hoang Nam | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

1.065
lượt xem 200
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Dưới đây ta nêu ra ba phương pháp, đó là phương pháp góc tây Bắc, phương pháp cực tiểu theo bảng và phương pháp Vaugen. Đối với bảng vận tải gồm m dòng và n cột, việc tìm tập ô chọn gồm m + n -1 ô không chứa chu trình được tiến hành bằng phương pháp quy nạp.

Chủ đề:

Bình luận(2) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chương 5: Bài toán vận tải và thuật toán thế vị

Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp Chương 5. BÀI TOÁN V N T I VÀ THU T TOÁN TH V 5.1. Bài toán v n t i Trong m c 1.1., ta đã nêu d ng t ng quát c a bài toán v n t i là m n → min cij xij (1) i=1 j =1 n xij = ai , (i = 1, 2, . . . , m) (2) j =1 m xij = bj , (i = 1, 2, . . . , n) (3) i=1 xij ≥ 0, (i = 1, 2, . . . , m, j = 1, 2, . . . , n) (4) trong đó ai > 0, (i = 1, 2, . . . , m, bj > 0, (j = 1, 2, . . . , n). Đó là bài toán quy ho ch tuy n tính d ng chính t c nhưng có c u trúc khá đ c bi t mà ta g i nó là bài toán v n t i c đi n . m n Đ ta= ai , b = bj . N u a = b thì bài toán v n t i (1),(2),(3),(4) đư c g i i=1 j =1 là bài toán cân b ng thu phát.. Kí hi u A là ma tr n ràng bu c và x = (x11 , . . . , x1n , . . . , x21 , . . . , x2n , . . . , xm1 , . . . , xmn ) ∈ Rmn (5.1.1) c = (c11 , . . . , c1n , . . . , c21 , . . . , c2n , . . . , cm1 , . . . , cmn ) ∈ Rmn (5.1.2) Thì bài toán v n t i đư c vi t l i dư i d ng f (x) =t cx → min Ax = A0 x ≥ 0. 68
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp Trong bài toán v n t i, h Ax = A0 g m m + n phương trình v i n × m n, trong đó ch có m + n − 1 phương trình đ c l p tuy n tính, m i phương trình là h qu c a các phương trình còn l i. Sau này m i phương án ta vi t dư i d ng ma tr n c m × n : x = (xij ). Ta cũng có ma tr n cư c phí c m × n : c = (cij ). Như v y, bài toán v n t i đư c coi là đã cho n u bi t vectơ lư ng phát a = (a1 , a2 , . . . , am ), vectơ lư ng thu b = (b1 , b2 , . . . , bn ) và ma tr n cư c phí c = (cij ). Ta kí hi u bài toán v n t i đó là a, b, c . Đ nh lý 5.1.1 (Đi u ki n có phương án t i ưu). Đ bài toán v n t i (1),(2),(3),(4) có phương án t i ưu, đi u ki n c n và đ là có đi u ki n cân b ng thu phát a = b. 5.2. Các Tính ch t c a bài toán v n t i 5.2.1 Chu trình M t dãy ô có d ng (i1 , j1 ), (i1 , j2 ), (i2 , j2 ), · · · , (ik , jk ), (ik , j1 ) hay (i1 , j1 ), (i2 , j1 ), (i2 , j2 ), · · · , (ik , jk ), (i1 , jk ) đư c g i là m t chu trinh (hai ô k ti p cùng m n trong m t dòng hay m t c t, ba ô liên ti p không cùng m n trên m t dòng hay m t c t, ô đ u tiên và ô cu i cùng cũng đư c coi là hai ô liên ti p). Như v y s ô trong m t chu trình là m t s ch n không nh hơn 4. T p ô Γ ⊂ U = {(i, j ) : i = 1, 2, . . . , m; j = 1, 2, . . . , n} đư c g i là ch a chu trình n u như t các ô c a Γ có th l p đư c ít nh t m t chu trình. N u trái l i thì ta nói Γ không ch a chu trình. Đ nh lý 5.2.2 (Đi u ki n không ch a chu trình). Đi u ki n c n và đ đ t p ô Γ ⊂ U không ch a chu trình là h vectơ tương ng v i nó, t c là h {Aij : (i, j ) ∈ Γ}, đ c l p tuy n tính. H qu 5.2.3 (S ô t i đa không ch a chu trình). N u b ng v n t i g m m dòng và n c t thì t p ô không ch a chu trình có t i đa là n + m − 1 ô. 69
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp Đ nh lý 5.2.4 (Chu trình duy nh t). Gi s b ng v n t i g m m dòng và n c t, E là t p ô g m m + n − 1 ô không ch a chu trình, (i, j ) là m t ô c a b ng không thu c E . Khi đó F = E ∪ {i, j } có m t chu trình duy nh t qua ô (i, j ). Đ nh lý 5.2.5 (D u hi u t p không ch a chu trình). Gi s F là m t t p g m m + n ô ch a chu trình duy nh t V và (i, j ) ∈ V . Khi đó t p ô E = F \ {(i, j )} s không ch a chu trình. Đ nh lý 5.2.6 (Đi u ki n c c biên). Phương án x = (xij ) c a bài toán v n t i (1),(2),(3),(4) là phương án c c biên khi và ch khi t p ô ch n tương ng v i nó, t c là t p ô H (x) = {(i, j ) : xij > 0} (5.2.3) không ch a chu trình. Đ nh lý 5.2.7 (Đi u ki n ch a ít nh t m t chu trình). T p ô không r ng Γ ⊂ U s ch a ít nh t m t chu trình n u trong m i dòng và m i c t c a b ng v n t i ho c là không có ô nào c a Γ, ho c có ít nh t hai ô c a Γ. 5.3. V n đ tính các ư c lư ng Gi s b ng cách nào đó ta đã tìm đư c phương án c c biên x = (xij ) c a bài toán v n t i v i t p ô ch n H (x) g m m + n − 1 ô (k c ô ch n-không) không ch a chu trình. Theo thu t toán đơn hình đ xét tính t i ưu c a x ta ph i tìm đư c các ư c lư ng ∆ij ng v i m i vectơ Aij ngoài cơ s c a x, t c là ng v i m i ô lo i (i, j ). Chúng ta d dàng ch ng minh đư c cij − ∆ij = cij (5.3.4) c (i,j )∈V l (i,j )∈V trong đó, V c và V l theo th t là t p h p các ô mang s hi u ch n l c a V . Ví d 5.3.1. Bài toán v n t i và phương án c c biên x ban đ u c a nó đư c cho b i b ng 70
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp trong đó các cư c phí ghi góc trên bên trái m i ô, các thành ph n cơ s c a phương án c c biên x ban đ u đư c ghi góc đ i di n (các thành ph n phi cơ s b ng 0). Có 9 ô lo i là các ô (1, 3), (1, 4), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (4, 2), (4, 4). Ta hãy l p b ng tính ∆ij v i Aij ngoài cơ s , t c là v i các ô lo i (i, j ). Trư c h t ta hãy tính ∆32 . T p ô g m ô (3, 2) và các ô ch n ch a chu trình duy nh t g m 6 ô, đư c th hi n b i đư c th hi n b i đư ng nét đ t trên b ng. Các ô này cùng v i s hi u c a nó và cư c phí tương ng là Ô trong chu trình (3,2) (3,4) (2,4) (2,1) (1,1) (1,2) S hi u 1 2 3 4 5 6 cij 30 16 18 68 40 15 Theo công th c (5.3.4) ta có ∆32 = 16 − 18 + 68 − 40 + 15 − 30 = 11 71
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp Tương t ta cũng tính đư c ∆13 = 40 − 30 + 13 − 35 = −12, ∆14 = 40 − 68 + 18 − 100 = −100, ∆22 = 68 − 40 + 15 − 51 = −8, ∆23 = 68 − 30 + 13 − 53 = −2 ∆31 = 16 − 18 + 68 − 120 = −54 ∆33 = 16 − 18 + 68 − 30 + 13 − 150 = −101 ∆42 = 30 − 40 + 15 − 54 = −49 ∆44 = 30 − 68 + 18 − 80 = −100 Vi c tính các ư c lư ng theo công th c (5.3.4) là khá đơn gi n nh hình nh tr c quan c a khái ni m chu trình, nhưng s đơn gi n hơn n u ta ng d ng đ nh lý dư i đây Đ nh lý 5.3.2 (Phương pháp đơn gi n xác đ nh các ư c lư ng). N u ta thay ma tr n cư c phí c = (cij ) b i ma tr n c = (cij ), trong đó cij = cij + ri + sj , t c m i ô c a dòng i v i cùng m t s ri , c ng vào cư c là n u ta c ng vào cư c phí m i ô c a c t j v i cùng m t s sj thì s đư c m t bài toán v n t i m i phí tương đương v i bài toán v n t i ban đ u (theo nghĩa hai bài toán có chung t p t p phương án t i ưu). Đ nh lý 5.3.3 (D u hi u t i ưu). Gi s x = (xij ) là m t phương án c c biên c a bài toán v n t i v i t p ô ch n H (x) và cij = 0 v i m i ô (i, j ) ∈ H (x) (t c là đã quy-không các ô ch n). (a) N u cij ≥ 0 v i m i ô (i, j ) ∈ H (x) thì x là phương án t i ưu c a bài toán. / (b) N t n t i ô (i, j ) ∈ H (x) sao cho cij < 0 thì ta có th xây d ng đư c phương / án c c biên x t t hơn x, n u x không suy bi n (nói chung x không x u hơn x). 72
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp 5.4. Mts phương pháp xây d ng phương án c c biên ban đ u Dư i đây ta nêu ra ba phương pháp, đó là phương pháp góc tây b c, phương pháp c c ti u theo b ng và phương pháp Vaugen. Đ i v i b ng v n t i g m m dòng và n c t, vi c tìm t p ô ch n g m m + n − 1 ô không ch a chu trình đư c ti n hành b ng phương pháp quy n p theo m + n là t ng s dòng và c t c a b ng v n t i. N u m + n = 2 thì b ng g m m t ô duy nh t. Do đi u ki n cân b ng thu phát nên a1 = b1 . Đ i v i c ba phương pháp y đi u ch n ô (1,1) và đ t x11 = a1 . Đó là phương án c c biên vì A11 = 0và rõ ràng có n + m − 1 = 1 ô ch n không ch a chu trình. Gi s đã bi t cách xây d ng phương án c c bi n ban đ u theo c ba phương pháp v i b ng có m + n ≤ k − 1, khi đó đ i v i b ng mà m + n = k ta s ti n hành như sau: N u as ≤ bt thì xst = as và xóa ngay dòng s; bt đư c thay b i bt = bt − as . N u as > bt thì xst = bt và xóa ngay c t t; as đư c thay b i as = as − bt . Sau khi xóa đi, ta đư c b ng m i g m m + n = k − 1, trên đó đã xây d ng đư c phương án c c biên (theo gi thuy t qui n p) v i t p ô ch n H g m n + m − 1 = k − 2 ô. D th y r ng H ∪ {s, t} là t p g m k − 1 ô ch n (đ i v i b ng m i) không ch a chu trình, b i vì n u trái l i thì chu trình t ph i qua ô (s,t) nhưng đi u này không th đư c vì dòng s c t t đã b xóa. Như v y, v i b ng mà m + n = k ta xây d ng đư c phương án c c biên v i t p ô ch n H ∪ {s, t} g m k − 1 ô. Như v y, m i b ng hình thành trong quá trình phân ph i (k c b ng đ u tiên) sau khi phân ph i t i đa vào ô (s,t) nào đó ta xóa ch m t dòng ho c m t c t đ đư c m t b ng m i. Vi c ch n ô (s, t) là ng u nhiên, nhưng ta thư ng dùng các phương pháp sau: (1) Phương pháp góc tây b c : (s,t) là góc trên bên trái c a b ng ( m i bư c). (2) Phương pháp c c ti u theo b ng (s, t) là ô sao cho cst = min cij trong đó c c ti u đư c ch n theo ô (i,j) c a b ng ( m i bư c). 73
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp B ng 5.4.1: Phương pháp tây b c B ng 5.4.2: Phương pháp Vaugen (3) Phương pháp Vaugen V i m i dòng và m i c t ta đi u tính hi u c a cư c phí th p th nhì và th p th nh t (ta g i hi u đó là đ chênh l ch c a dòng hay c t đó). Ch n dòng (hay c t) có đ chênh l ch l n nh t. Trên dòng (hay c t) đã ch n ta s ch n ô (s,t) có cư c phí th p nh t. Ví d 5.4.1. Dư i đây là các phương án c c biên ban đ u tìm đư c b ng phương pháp góc tây b c và phương pháp Vaugen. 74
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp 5.5. Thu t toán th v Phương pháp đã nêu trên đây đ tìm phương án t i ưu c a bài toán v n t i v i các bư c c th sau đây đư c g i là thu t toán th v . Bư c 1. Tìm phương án c c biên ban đ u x = (xij ). Bư c 2. Quy-không các ô ch n. N u cij ≥ 0 v i m i ô (i, j ) c a b ng thì k t thúc vi c tính toán và k t lu n x là phương án t i ưu. N u trái l i, t c là t n t i ô (i,j) sao cho cij < 0 thì ch n cst = min{cij : cij < 0} và chuy n sang bư c 3. Bư c 3. L p chu trình V đi qua ô (s,t) và s ô xác đ nh nào đó c a H (x). Tính θ = min{xij : ij ∈ V c }. (5.5.5) chuy n sang bư c 4. Bư c 4. Xây d ng x = (xij ) theo công th c  n u(i, j ) ∈ V l  xij + θ      xij = (5.5.6) n u(i, j ) ∈ V c xij − θ    n u(i, j ) ∈ V  x  ij cho x đóng vai trò c a x và quay l i bư c 2. Ví d 5.5.1. Gi i bài toán v n t i a, b, c v i vectơ lư ng phát a = (100, 400, 230) vectơ lư ng thu b = (320, 180, 110, 120) và ma tr n cư c phí   5 3 16 9   c = 5 3 7 8     1 8 12 10 Gi i B ng phương pháp góc tây b c ta thu đư c phương án c c biên đ u tiên suy bi n, trong đó có m t ô-ch n-không, đó là ô (2,3) (sau khi phân ph i t i đa l n th bao v i x22 = 180, n u xóa dòng 2 thì ô-ch n-không là ô (3,2)). 75
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp 76
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp T đó ta có phương án t i ưu   0 100 0 0 x∗ =  90   80 110 120     230 0 0 0 v i giá tr t i ưu c a hàm m c tiêu là f ∗ = 110.3 + 90.5 + 80.3 + 110.7 + s120.8 + 230.1 = 2950. 5.6. Tiêu chu n t i ưu. Bài toán đ i ng u c a bài toán v n t i 5.6.1 Tiêu chu n t i ưu Gi s x = (xij ) là m t phương án c a bài toán v n t i (1),(2),(3),(4). Theo 4.1.6 thì đi u ki n c n và đ đ phương án x là phương án t i ưu c a bài toán v n t i là t n t i vectơ y = (u, v ) = (u1 , . . . , um , v1 , . . . , vm ) ∈ Rm+n (5.6.7) 77
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp sao cho y t Aij ≤ cij n u xij = 0 y t Aij = xij xij > 0 Do tính ch t đ c bi t c a vectơ Aij nên ta có y t Aij = ui + vj (i = 1, 2, . . . , m; j = 1, 2, . . . , n) (5.6.8) T đó suy ra r ng: Đi u ki n c n và đ đ phương án x = (xij ) là phương án t i ưu c a bài toán (1),(2),(3),(4) là t n t i các s ui v i i = 1, 2, . . . , m và vj v i j = 1, 2, . . . , n sao cho ui + vj ≤ cij xij = 0 ui + vj = cij xij > 0 N u x là phương án t i ưu c a bài toán v n t i (1),(2),(3),(4) thì y = (u, v ) là phương án t i ưu c a bài toán đ i ng u. 5.6.2 Bài toán đ i ng u c a bài toán v n t i Bài toán v n t i là bài toán quy ho ch tuy n tính d ng chính t c. Chú ý đ n (5.6.8), bài toán đ i ng u c a nó d ng m n bj vj → max ai ui + i=1 j =1 ui + vj ≤ cij (i = 1, 2, . . . , m, j = 1, 2, . . . , n) T đi u ki n c n và đ đ bài toán v n t i (1),(2),(3),(4) nh n phương án x làm phương án t i ưu nêu trên, ta rút ra k t lu n: N u (r, s) = (r1 , . . . , rm , s1 , . . . , sn ) là m t h th ng th v ng v i phương án t i ưu thì (−r, −s) = (−r1 , . . . , −rm , −s1 , . . . , −sn ) là phương án t i ưu c a bài toán đ i ng u. 78