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

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.
Nội dung trích xuất từ tài liệu:
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ápChương 5.BÀI TOÁN V N T I VÀ THU TTOÁN TH V5.1. Bài toán v n t iTrong 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á đ cbi 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 =1là 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. 68Quy 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 ). Tacũ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 i5.2.1 Chu trìnhM 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 ô kti 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ênm 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 chutrì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 ithì 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 mdòng và n c t thì t p ô không ch a chu trình có t i đa là n + m − 1 ô. 69Quy 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à nc 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 ngkhô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 pg 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 iho 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ư ngGi 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ánv 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 chutrì ...