vận trù học 10

l Kế toán là việc thu thập, xử lý, kiểm tra, phân tích và cung cấp thông tin kinh tế, tài chính dưới hình thức giá trị, hiện vật và thời gian lao động. Để cung cấp thông tin về kinh tế tài chính thực sự hữu dụng về một doanh nghiệp, cần có một số công cụ theo dõi những hoạt động kinh doanh hàng ngày của doanh nghiệp, trên cơ sở đó tổng hợp các kết quả thành các bản báo cáo kế toán. Những phương pháp mà một doanh nghiệp sử dụng để ghi chép và tổng...
Nội dung trích xuất từ tài liệu:
vận trù học 10là m t lu ng ch p nh n ñư c sao cho giá tr v c a lu ng ñ t ñư c là l n nh t. Các kháini m này ñư c ñ nh nghĩa tương t trong trư ng h p t ng quát. Bài toán tìm lu ng c c ñ i trên ñây ñư c gi i b ng thu t thích h p v i k t qucác bư c l p ñư c t ng h p trong b ng III.24: B ng III.24. Các bư c gi i bài toán lu ng c c ñ i Bư c Tìm ñư ng Giá tr tăng Các t i năng c a các cung trên lu ng hi n Giá tr tăng lu ng lu ng t i (lu ng ch p nh n ñư c) lu n g xij = 0 ∀ cung (i, j) Bư c kh i 0 to 1→2→5 x12 = x25 = 20, xij = 0 ∀ cung (i, j) khác Bư c l p 1 20 20 1→3→5 x12 = x25 = 20, x13 = x35 = 10, xij = 0 ∀ cung Bư c l p 2 10 30 (i, j) khác 1→4→5 Bư c l p 3 15 x12 = x25 = 20, x13 = x35 = 10, x14 = x45 = 15, 45 xij = 0 ∀ cung (i, j) khác Gi i thích Trư c h t t i bư c kh i t o c n tìm m t lu ng ch p nh n ñư c, t c là m t véc tơ maxlu ng (x12, x13, x14, x24, x25, x34, x35, x45), xij ∈[ 0, x ij ] ∀ cung (i, j) và tho mãn: ∑ x ki = ∑ x ih ∀ nút i trên m ng, trong ñó v trái là t ng các t i năng c a các cungk∈I(i) h∈O(i)ñi vào nút i, còn v ph i là t ng các t i năng c a các cung ñi kh i nút i. Trong b ng trên,chúng ta xu t phát b i véc tơ lu ng trùng véc tơ 0 v i giá tr lu ng b ng 0. T i bư c l p 1 chúng ta tìm ñư c m t ñư ng tăng lu ng 1 → 2 → 5 t nút 1 t i nút5 b ng cách th c hi n th t c ñánh d u. Th t c ñánh d u Bư c kh i t o. G i I là t p nút ñã ñư c ñánh d u I, ban ñ u ñ t I = {nút ngu n}. Các bư c l p. Bư c 1: N u I ch a nút hút ho c I = ∅ thì v bư c k t thúc. N u trái l i, ch n nútb t kì i ∈ I ñ quét (ñ ng th i ñưa nó ra kh i t p I), t c là xét t t c các nút j c nh i, nóicách khác, xét m i cung ti n có d ng (i, j) là cung trên m ng ñư ng ñi m t chi u ñã chovà tương ng v i nó là cung lùi (j, i). Bư c 2: Xét các cung ti n (i, j) mà có j chưa ñư c ñánh d u (không n m trong t p I)thì ta ñưa j vào t p I v i ñi u ki n xij (hi n có) < x ij ax , còn n u xét các cung lùi thì ñi u mki n ñó là xij (hi n có) > 0 và quay tr l i bư c 1. Chú ý m t khi nút hút ñư c ñưa vàot p I thì cũng v ngay bư c k t thúc. Bư c k t thúc. Tìm ñư ng tăng lu ng P (xem gi i thích ngay sau ñây) và d ng.Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........90 Xét bư c l p 1 trong b ng III.24. T i bư c 1, ta quét nút 1 (và ñưa nút 1 ra kh i t pI) ñ có các nút 2, 3, 4 c nh nút 1 chưa ñư c ñánh d u và có I = {2, 3, 4}. T i bư c 2,ch n quét nút 2 (ñ ng th i ñưa nút 2 ra kh i t p I) thì ñư c thêm nút c nh nút 2 là nút 5(nút hút) nên chuy n sang bư c k t thúc. ð tìm ñư ng tăng lu ng, ta ñi ngư c t nút 5v nút 2 (vì nút 5 ñư c ñưa vào ñánh d u khi quét nút 2) và sau ñó v nút 1 (vì nút 2 ñãñư c ñưa vào ñánh d u khi quét nút 1). Như v y t i bư c l p 1 ta ñư c ñư ng tănglu ng 1 → 2 → 5 v i giá tr tăng lu ng là   ( ) max ∆(P) = Min  min x ij − x ij , min x ij  = Min{min(20 −0, 28−0)} = 20. (i, j)∈C+ (i, j)∈C −  Trong bi u th c trên, kí hi u C+ ñ ch t p cung ti n, còn kí hi u C− ñ ch t p cunglùi n m trên ñư ng tăng lu ng. Tương t , các bư c l p 2 và 3 ta tìm ñư c các ñư ngtăng lu ng v i các giá tr tăng lu ng tương ng là 10 và 15. Lu ng c c ñ i có giá tr làt ng các giá tr tăng lu ng và giá tr c a lu ng xu t phát: 20 + 10 + 15 = 45. T ví dtrên, chúng ta có th phát bi u thu t toán Ford − Fulkerson gi i bài toán lu ng c c ñ i. Thu t toán Ford − Fulkerson Bư c kh i t o. Tìm m t lu ng ch p nh n ñư c. Các bư c l p. Bư c 1: Tìm m t ñư ng tăng lu ng b ng th t c ñánh d u. N u không có thìchuy n v bư c k t thúc. Còn n u có thì xét giá tr tăng lu ng tương ng ∆(P). Bư c 2: N u ∆(P) < +∞ thì ñ y thêm ∆(P) ñơn v t i năng d c theo ñư ng tănglu ng P ñ ñư c lu ng ch p nh n ñư c m i r i quay v bư c 1. N u trái l i, ∆(P) = +∞thì v bư c k t thúc. Bư c k t thúc. Tìm lu ng c c ñ i v i giá tr h u h n ho c k t lu n bài toán có lu ngch p nh n ñư c v i giá tr v = + ∞. Ví d 6. Trư ng h p khi ñư ng tăng lu ng có ch a cung lùi (xem b ng III.25, hàng3): Xét l i bài toán trong ...