vận trù học 9

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

Thêm vào BST

Báo xấu

52
lượt xem 7
download

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

Tham khảo tài liệu 'vận trù học 9', tài chính - ngân hàng, kế toán - kiểm toán phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

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

Lưu

Nội dung Text: vận trù học 9

ng d ng trong các bài toán xác ñ nh chi phí t i thi u nhi u d ng khác. Trong ví d trên, t p N0 qua các bư c l p ñư c phát tri n như sau: {1}, {1, 3}, {1, 3, 4, 7}, {1, 3, 4, 7, 5}, {1, 4, 3, 7, 5}, {1, 4, 3, 7, 5, 6}, {1, 4, 3, 7, 5, 6, 2}. 3.2. Bài toán tìm ñư ng ñi ng n nh t và quy ho ch ñ ng Bài toán tìm ñư ng ñi ng n nh t Trong bài toán tìm ñư ng ñi ng n nh t, chúng ta mu n xác ñ nh hành trình ng n nh t t m t ñ a ñi m xu t phát (ñi m g c) ñ ñi t i ñi m c n ñ n (ñi m ñích) trên m t m ng liên thông. ð cho d hi u, chúng ta xem xét ví d sau ñây. Ví d 2: Bài toán ngư i ñi du l ch. Có m t ngư i ñi du l ch, xu t phát t nút 1 và k t thúc hành trình nút 10 theo hành trình trên hình III.13. 300 200 2 6 9 400 100 100 200 275 150 175 1 4 5 10 250 150 175 200 275 350 125 3 7 8 Hình III.12. Sơ ñ hành trình ñư ng ñi Ngư i du l ch xu t phát t nút 1. Trong giai ño n ñ u anh ta ch ñư c quy n (và b t bu c) ch n m t trong ba nút (thành ph ) 2, 3, 4 ñ vào thăm quan. Giai ño n ti p theo, anh ta ch ñư c ch n m t trong ba nút 5, 6, 7 ñ du l ch. Trong giai ño n ti p n i, anh ta có quy n vào m t trong hai nút 8 ho c 9 trư c khi k t thúc hành trình t i nút 10. Như v y, trong m i giai ño n ngư i ñi du l ch ch ñư c quy n ñi vào m t thành ph (m i thành ph ñư c coi là m t tr ng thái c a giai ño n ñó). Hãy tìm cách xác ñ nh ñư ng ñi ng n nh t t nút 1 t i nút 10 tho mãn các ñi u ki n ñ t ra c a bài toán. Nguyên t c t i ưu Bellman trong quy ho ch ñ ng S d ng nguyên t c t i ưu Bellman trong quy ho ch ñ ng ñ gi i bài toán ngư i du l ch, chúng ta chia bài toán thành nhi u giai ño n, t c là thành nhi u bài toán nh . T i m i giai ño n ta c n tìm phương án t i ưu là các phương án t t nh t c a tình tr ng hi n có, xét trong m i quan h v i các phương án t i ưu ñã tìm ñư c c a các giai ño n trư c. Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........80
Ta có th gi i quy t bài toán d n theo t ng giai ño n theo cách tính toán ti n ho c tính toán lùi. ð gi i bài toán này, ta áp d ng cách tính toán lùi (backward computing) v i các kí ki u và d ki n cho trong b ng III.19. B ng III.19. Các giai ño n c a bài toán quy ho ch ñ ng Kho ng cách Giai ño n ð u vào ð u ra ðư ng ñi t i ưu t i ñích 8 → 10 8 10 150 Giai ño n I 9 → 10 9 10 100 5→8 5 400 8 6→9 Giai ño n II 6 300 9 7→8 7 275 2→6 2 5 600 3→5 Giai ño n III 3 6 600 4→6 4 7 500 1→2 2 700 1→3 Giai ño n IV 1 3 775 1→4 4 650 Gi i thích: S d ng nguyên t c t i ưu Bellman ñ tìm ñư ng ñi ng n nh t t nút 4 t i nút 10, chúng ta tìm ñư c phương án t i ưu là ñi t nút 4 t i nút 6 cho giai ño n III (lúc này d(4, 10) = d(4, 6) + Min d(6, 10) = 200 + 300 = 500). ði u này là do hai l a ch n khác là ñi t nút 4 t i nút 5 hay 7 thì ñ u cho kho ng cách t nút 4 t i ñích là nút 10 l n hơn (ch ng h n n u ñi qua nút 5 thì d(4, 10) = d(4, 5) + Min d(5, 10) = 175 + 400 = 575). Trong b ng III.19, t i giai ño n IV, ta th y kho ng cách ng n nh t t i ñích là 650. ði ngư c l i, t ñi m g c t i ñi m ñích ta xác ñ nh ñư c ñư ng ñi ng n nh t là: 1 → 4 → 6 → 9 → 10 v i t ng chi u dài là 650. Quy trình tính toán t ng quát − Trư c h t, c n ch n có các bi n tr ng thái (state variables) như mô t trong b ng III.20. B ng III.20. Các bi n tr ng thái c a bài toán quy ho ch ñ ng Giá tr có th x y ra c a Bi n S tr ng thái Các tr ng thái (nút) các bi n tr ng thái x4 ≡ 1 x4 1 1 x3 3 2, 3, 4 x3 = 2 ; x3 = 3; x3 = 4 x2 3 5, 6, 7 x2 = 5 ; x2 = 6; x2 = 7 x1 2 8, 9 x1 = 8 ; x1 = 9 x0 1 10 x0 = 10 Bi n tr ng thái mô t tr ng thái c a h th ng trong t ng giai ño n.
− Xác ñ nh hàm m c tiêu: ð t Fi(xi) là kho ng cách ng n nh t t i ñích tính t i giai ño n i. Theo b ng III.19, ta th y: 150 v i x1 = 8 F1(x1) =  100 v i x1 = 9  400 v i x2 = 5  v i x2 = 6 F2(x2) =  300  275 v i x2 = 7  M c ñích c a bài toán là c n tìm ñư c giá tr F4(x4) = F4(1). − L p hàm truy toán: Fi+1(xi+1) = Min [Fi(xi) + fi(ui)], Min tìm theo m i t h p thích h p xi và ui, trong ñó ui là bi n ñi u khi n ñ ñi u khi n chuy n tr ng thái t tr ng thái xi sang xi+1 và fi(ui) là hi u ng c a bi n ñi u khi n tác ñ ng lên hàm truy toán (và lên hàm m c tiêu, n u tính ñ n bài toán cu i cùng). Theo bi u th c c a hàm truy toán ta th y, n u Fi(xi) + fi (ui) là hàm phi tuy n thì ph i dùng kĩ thu t t i ưu thích h p ñ tìm ra Fi+1(xi+1). Sau ñây chúng ta ñi tìm các hàm truy toán Fi+1(xi+1) v i quy trình tính toán lùi ñ gi i bài toán theo t ng giai ño n, nh m cu i cùng tìm ra ñư c F4(x4) = F4(1). Giai ño n 1: Trong giai ño n này, mu n chuy n t nút 10 (x0 = 10) v nút 8 (x1 = 8) ch ng h n thì bi n ñi u khi n u0 ph i có giá tr 150 (u0 = 150). Hi u ng gây nên b i u0 là f(u0) = 150. ði u này có nghĩa là n u chuy n t nút 10 ngư c v nút 8 thì c n ñi quãng ñư ng có chi u dài là 150. F0 (x0) = 0 x0 = 1 0 u0 f0 (u0) F1 (x1 ) x1 = 8 + u0 = 150 150 150 150 x1 = 9 + u0 = 100 100 100 100 Chú ý: Không ph i bài toán nào ui cũng trùng v i hi u ng fi(ui) c a nó. Nói chung, bi n ñi u khi n ui có th gây ra hi u ng fi(ui) khác v i ui c v ñ l n cũng như ñơn v ño. Giai ño n 2: F1 (x1 ) + f1(u1 ) F2 (x2) = x2 x1 = 8 x1 = 9 Min[F1 (x1) + f1(u1 )] x1 = 8 x1 = 9 5 +u1 = 2 50 +u1 = 400 400 500 400 = 150 + 250 − − 6 +u1 = 200 300 300 = 100 + 200 − − 7 275 = 150 + 125 +u1 = 125 275 Giai ño n 3: x2 F2 (x2) + f2(u2 ) F3 (x3) = Min x3 [F2(x2) + f2(u2 )] 5 6 7 x2 = 5 x2 = 6 x2 = 7 Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........82
− − 2 u2 = 2 75 u2 = 300 675 600 600 − − 3 u2 = 2 00 600 600 u2 = 350 6 25 4 u2 = 1 75 575 500 u2 = 200 u2 = 275 500 550 Giai ño n 4: F3 (x3) + f3(u3 ) F4 (x4) = Min x4 x3 = 2 x3 = 3 x3 = 4 [F3 (x3) + f3(u3)] x3 = 2 x3 = 3 x3 = 4 1 u3 = 100 u3 =175 u3 =150 700 775 650 650 ðáp s : F4(x4) = F4(1) = 650 v i ñư ng ñi ng n nh t trên hình III.14. x0 =10 x3 = 4 x2 = 6 x1 = 9 x4 = 1 u2 = 2 00 u3 = 150 u0 = 100 u1 = 200 Hình III.14. ðư ng ñi ng n nh t 1 → 4 → 6 → 9 → 10 M ts ng d ng c a quy ho ch ñ ng Bài toán 1 C n phân ph i công su t t i ưu c a n nhà máy ñi n v i ph t i t n th t c ñ nh. Bi t chi phí c a các nhà máy là hàm fi(pi) ph thu c vào công su t pi, v i i = 1, 2,..., n. C n xác ñ nh các giá tr c a pi sao cho t ng chi phí là c c ti u. V y ta có bài toán t i ưu sau: Hàm m c tiêu: z = f1(p1) +....+ fn(pn) → Min v i các ràng bu c: p1 + p 2 + ... + p n = P  0 ≤ pi ≤ Pi,max , trong ñó P là t ng ph t i, Pi, max là công su t t i ña cho phép. Ch ng h n, v i n = 3 ta có BTQHTT (nguyên) sau ñây: z = 3p1 + 2p2 + p3 → Min p1 + p 2 + p3 = 15  0 ≤ pi ≤ 6; 0 ≤ p 2 ≤ 6; 0 ≤ p3 ≤ 8 n u ñã bi t:
f1 (p1 ) = 3p1  f 2 (p 2 ) = 2p 2 f (p ) = p . 3 3 3 Chúng ta xét phương pháp gi i bài toán này v i gi thi t các công su t pi là nguyên. ð t các bi n tr ng thái là x1, x2, x3; các bi n ñi u khi n là p1, p2, p3 v i quan h như sau: x1 = p1, x2 = p1 + p2, x3 = p1 + p2 + p3 = 15. Các hi u ng gây nên b i các bi n ñi u khi n là fi(pi) v i i = 1, 2, 3. x1 x0 = 0 x2 x3 Bi n ñi u khi n p1 p2 p3 Thi t l p hàm truy toán Fi+1 (xi+1) = Min [Fi(xi) + fi+1 (pi+1)]. ð t F0(x0) = 0, d th y: F1(x1) = Minf1(p1), F2(x2) = Min[f1(p1) + f2(p2)] và F3(x3) = Min[f1(p1) + f2(p2) + f3(p3)] = 3p1 + 2p2 + p3. M c tiêu cu i cùng là c c ti u hóa z = F3(x3). S d ng nguyên t c t i ưu Bellman ta chia bài toán ra các giai ño n sau ñây (v i quy trình tính toán ti n). Giai ño n 1: ch xét công su t p1; Giai ño n 2: ch xét công su t p1 và p2; Giai ño n 3: xét các công su t p1, p2 và p3. n 1: (Coi F0(x0) = 0) Giai ño x1 x0 = 0 f1(p1) = 3p1 F1(x1) = Min[F0(x0) + f1(p1)] 0 p1 = 0 0 0 1 p1 = 1 3 3 2 p1 = 2 6 6 3 p1 = 3 9 9 4 p1 = 4 12 12 5 p1 = 5 15 15 6 p1 = 6 18 18 Giai ño n 2: x1 F2 (x2) = F1(x1) + f2(p2) x2 Min[F1(x1) + 0 1 2 3 4 5 6 f2(p2)] p2 0 1 2 3 4 5 6 Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........84
− − − − − − − − − − − − 0 0 0 0 − − − − − − − − − − 1 0 3 1 2 2 − − − − − − − − 2 1 5 0 6 2 4 4 3 − − − − − − 2 7 1 8 3 0 9 6 6 4 3 9 − − − − 2 10 4 1 11 8 0 12 8 5 4 11 3 12 − − 5 2 13 10 1 14 0 15 10 6 5 13 4 14 6 3 15 12 2 16 1 17 0 18 12 − 6 15 5 16 7 4 17 15 3 18 2 19 1 20 − − − − 6 18 8 5 19 18 4 20 3 21 2 22 − − − − − − 9 6 21 21 5 22 4 23 3 24 − − − − − − − − 10 24 6 24 5 25 4 26 − − − − − − − − − − 11 27 6 27 5 28 − − − − − − − − − − − 12 30 6 30 Giai ño n 3: x2 F2(x2) + f3(p3) F3(x3) = Min x3 0 6 7 8 9 10 11 12 [F2(x2) + f3(p3)] p3 7 8 9 10 11 12 − − 15 8 7 6 5 4 3 23 25 27 29 31 33 23 ðáp s : T ng chi phí ñ t giá tr c c ti u là 23, v i p1 = 1, p2 = 6, p3 = 8. x0 = 0 x1 = 1 x2 = 7 x3 = 1 5 Bi n ñi u khi n p2 = 6 p3 = 8 p1 = 1 Chú ý. Các v n ñ cơ b n c n gi i quy t khi áp d ng phương pháp quy ho ch ñ ng theo nguyên t c Bellman là: − Chia bài toán thành nhi u giai ño n nh ñ gi i bài toán t i ưu cho t ng giai ño n. Các y u t c a bài toán quy ho ch ñ ng là bi n tr ng thái, bi n ñi u khi n, hàm truy toán và hàm m c tiêu. − Khi chuy n t m t tr ng thái nào ñó (trong m t giai ño n) sang tr ng thái khác (giai ño n khác) c n có bi n ñi u khi n. − M i giá tr c a bi n ñi u khi n gây ra m t hi u ng lên hàm m c tiêu. − Tuỳ theo các bài toán t i ưu phát sinh trong các giai ño n mà l a ch n phương pháp t i ưu thích h p. Trong ví d ñang xét, khi các hi u ng fi(pi) cho dư i d ng hàm tuy n tính v i các bi n pi nh n các giá tr r i r c/nguyên thì hàm truy toán Fi+1 (xi+1) = Min [Fi(xi) + fi+1
(pi+1)] s tính ñư c b ng thu t gi i d a trên b ng li t kê (như phương pháp gi i ñã trình bày). N u fi(pi) phi tuy n v i các bi n pi nh n các giá tr liên t c thì ñ tìm Fi+1(xi+1) = Min[Fi(xi) + fi+1(pi+1)] ta có hai cách: − Cách 1: r i r c hóa theo t ng m c. Ch ng h n n u p1 ∈ [0, 6] thì coi p1 ∈ {0, 1, 2, 3, 4, 5, 6}. − Cách 2: áp d ng phương pháp t i ưu thích h p v i bi n liên t c (xem chương I) cho hàm m c tiêu. Ch ng h n, trong ví d trên khi c n tìm F2(x2) = Min [F1(x1)+ f2(p2)] = Min[f1(p1) + f2(p2)] = Min [3p1 + 2p2] v i ñi u ki n ràng bu c: p1 + p2 ≤ 15 và 0 ≤ p1 ≤ 6, 0 ≤ p2 ≤ 6, có th áp d ng phương pháp ñơn hình. Bài toán 2 Xác ñ nh tuy n ñư ng ñi c a ñư ng dây truy n t i ñi n t ñi m A ñ n ñi m B, v i các chư ng ng i v t khác nhau, sao cho t ng chi phí là nh nh t. Các d ki n c a bài toán cho trên hình III.15. Như v y ñ thi t l p sơ ñ ñư ng truy n t i ñi n thì xu t phát t A ta có th ñ nh tuy n ñi c a ñư ng truy n t i ñi n trư c h t ph i qua m t trong hai ñi m sát g n, theo hư ng b c hay hư ng ñông, v i các chi phí là 15 và 12. T m t trong hai ñi m này, chúng ta l i ti p t c xác ñ nh tuy n ñi cho ñư ng truy n t i ñi n, v i các chi phí ñã bi t... V y ta có bài toán tìm ñư ng ñi v i chi phí nh nh t. 8 9 13 10 B 8 12 9 6 10 9 7 10 11 2 6 8 2 4 7 8 13 15 10 15 12 11 16 15 10 11 12 A Hình III.15. Sơ ñ tuy n ñi cho dây truy n t i ñi n Bài toán này hoàn toàn tương t v i bài toán ngư i du l ch ñã xét và có th gi i b ng phương pháp quy ho ch ñ ng (Hư ng d n: Chia bài toán thành nhi u giai ño n nh theo các ñư ng v i nét ñ t n i trên hình III.15). 3.3. Mô hình m ng trung chuy n hàng Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........86
Mô hình m ng v n t i có th ñư c xem xét dư i d ng mô hình m ng trung chuy n hàng (Transshipment Model), trong ñó m i ñi m cung ho c c u (ho c “lo i tr ”) ñư c coi là các nút trung chuy n hàng, t c là các nút cung c u k t h p: v a nh n hàng ñ n v a chuy n hàng ñi. Vi c xem xét như v y có ý nghĩa th c ti n hơn do vi c tính toán cư c phí v n chuy n gi a các nút trung chuy n ñư c th c hi n d dàng hơn. Ví d 3: Ta có 3 ñi m cung c p hàng A, B, C và 2 ñi m c u S, T v i lư ng hàng cung và c u t i m i ñi m cũng như cư c phí v n t i trên m t ñơn v hàng cho m i cung ñư ng như trong b ng III.21. B ng III.21. Các d li u c a bài toán v n t i Cư c phí v n chuy n/ñơn v hàng cij (USD) ñ n Nơi ñi S(2300) T(1400) A(1000) 80 215 B(1500) 100 108 C(1200) 102 68 C n xác ñ nh nên v n chuy n t m i ñi m cung t i m i ñi m c u bao nhiêu ñơn v hàng nh m tho mãn nhu c u cung c u ñ ng th i ñ t t ng chi phí v n t i là nh nh t. ð ñưa bài toán v n t i trên v bài toán trung chuy n hàng, ta coi các ñi m A, B, C, S và T v a là các nút trung chuy n: nh n hàng ñ n và chuy n hàng ñi. Do ñó c n thêm vào các cư c phí v n t i trên m t ñơn v hàng gi a hai nút b t kì c a m ng trung chuy n hàng (xem b ng III.22, ch ng h n, t A t i B cư c phí ñó là 130, t A t i S cư c phí là 80 như ñã cho, tuy nhiên t S t i A cư c phí l i là 79 trên ñư ng ñi theo chi u ngư c l i). T i m i nút, m t lư ng hàng hóa b t kì không vư t quá 3700 ñơn v có th ñư c trung chuy n. N u t i m i nút cung hay c u c a bài toán v n t i ban ñ u, chúng ta b sung thêm m t lư ng “d tr ñ m” là B ≥ 3700 ñơn v hàng thì hàng có th chuy n ñi trư c khi hàng ñ n. Ch n B = 3700, chúng ta s ñưa bài toán trung chuy n hàng v bài toán v n t i v i 5 nút cung ñ ng th i là 5 nút c u (có các lư ng cung/c u ph i ñư c tính toán l i), v i phương án v n chuy n t i ưu ñư c cho trong b ng III.22: T A v n chuy n t i S 1000 ñơn v hàng, t B t i C và S 200 và 1300 ñơn v hàng, t C t i T 1400 ñơn v hàng. B ng III.22. Phương án t i ưu c a bài toán trung chuy n hàng Cư c phí v n chuy n/ñơn v hàng cij (USD) ñ n Nơi ñi A B C S T 3700 3700 3700 6000 5100 A 0 80 130 90 215 1000+3700 3700 1000 B 135 0 101 100 108
1500+3700 3700 200 1300 C 0 68 95 105 102 1200+3700 3500 1400 S 110 0 79 99 205 3700 3700 T 0 200 107 72 205 3700 3700 Ví d 4: Gi i bài toán tìm ñư ng ñi ng n nh t (xem sơ ñ m ng ñư ng ñi trên hình III.16) b ng cách áp d ng mô hình m ng trung chuy n hàng. ð cho ñơn gi n chúng ta xét ñư ng ñi hai chi u, ch ng h n t nút 2 t i nút 5 và ngư c l i ñ u có ñư ng ñi v i cùng chi u dài là 500. 500 2 5 200 1100 800 600 1000 7 4 1 400 900 300 700 100 6 3 Hình III.16. Sơ ñ m ng ñư ng ñi ð gi i bài toán này chúng ta coi nút 1 là nút ñi ñóng vai trò ñi m cung duy nh t v i lư ng cung b ng 1 ñơn v , còn nút 7 là nút ñ n ñóng vai trò nút c u duy nh t v i lư ng c u là 1, các nút còn l i là các nút trung chuy n. Chi u dài các ñư ng ñi gi a các nút ñư c ñi n vào các ô tương ng, ñư c xem như cư c phí v n t i. N u không có ñư ng ñi thì ta coi cư c phí là M ≈ +∞. Lúc này bài toán ñư c ñưa v mô hình m ng trung chuy n hàng v i các d li u như mô t trong b ng III.23 và có th gi i ñư c b ng phương pháp phân ph i hay phương pháp th v như ñã bi t. B ng III.23. D li u c a bài toán ñư ng ñi ng n nh t. Nút ñi 2 3 4 5 6 7 là nút ñ n là nút 1 200 400 1000 M M M 1 2 0 M 1100 500 M M 0+B 3 M 0 300 M 100 M 0+B 4 1100 300 0 800 700 M 0+B 5 500 M 800 0 M 600 0+B Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........88
6 M 100 M M 0 900 0+B B=1 0+B 0+B 0+B 0+B 0+B 1 3.4. Bài toán tìm lu ng c c ñ i Ví d 5: Xét m ng ñư ng ñi có hư ng t nút 1 t i nút 5 v i các t i năng t i ña c a các cung ñư ng ñã bi t như mô t trên hình III.17 (ch ng h n t i năng x12 c a cung ñư ng n i các nút 1 và 2 ph i n m trong gi i h n t 0 t i 20). Bài toán ñ t ra là: C n xác ñ nh ñư c lu ng c c ñ i (Maximal Flow) gi a nút 1 (nút ngu n) và nút 5 (nút hút). 2 (5) (20) (28) (30) (15) 5 4 1 (10) (20) (15) 3 Hình III.17. Sơ ñ ñư ng ñi và thông lư ng Bài toán trên có ý nghĩa th c t như sau: Coi nút 1 là kho bơm/c p phát d u thô v i kh năng r t l n, các ñư ng ñi là các ng d n d u v i các t i năng (t n/ñơn v th i gian) ñã xác ñ nh, các nút 2, 3 và 4 là các tr m bơm/trung chuy n d u, còn nút 5 là kho nh n d u (ñ ñưa d u vào l c). C n xác ñ nh phương án bơm d u t i ưu v i các t i năng thích h p c a các cung ñư ng ñ bơm ñư c d u thô nhi u nh t (tính trên m t ñơn v th i gian) t nút 1 t i nút 5. ðó chính là phương án sau: Bơm 20 t n d u thô t nút 1 qua ñư ng ñi 1 → 2 → 5 t i nút 5, bơm 15 t n d u thô tr nút 1 qua ñư ng ñi 1 → 4 → 5 t i nút 5 và bơm 10 t n d u thô tr nút 1 qua ñư ng ñi 1 → 3 → 5 t i nút 5. Như v y lu ng c c ñ i có th chuy n t nút 1 ñ n nút 5 qua m ng ng d n d u trên có giá tr là 45 t n/m t ñơn v th i gian. C n chú ý là t ng lư ng d u ñi qua m i cung ñư ng ph i n m trong gi i h n cho phép c a t i năng. V m t toán h c, khái ni m lu ng c c ñ i có th ñư c xây d ng như sau ñây ñ i v i bài toán trên. Trư c h t, ta g i m t lu ng ch p nh n ñư c là m t véc tơ (x12, x13, max x14, x24, x25, x34, x35, x45), xij ∈[ 0, x ij ] ∀ cung (i, j) cho trên m ng ñư ng ñi có hư ng 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 k∈I(i) h∈O(i) c a các cung ñ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. D dàng ch ng minh ñư c r ng luôn có ∑ x1 j = ∑ x i5 = v. Lúc này, m t lu ng c c ñ i j∈O(1) i∈I(5)
là 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ái ni 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 qu cá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ơ max lu 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 cung k∈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út 5 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út b 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ói cá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 ñã cho và 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 m ki 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ào t 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