vận trù học 8

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

Thêm vào BST

Báo xấu

51
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 8', 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 8

Chú ý: M i cung có mũi tên là m t ho t ñ ng, nhưng có th bao g m nhi u ho t ñ ng nh khác. Nói cách khác, b n thân t ng ho t ñ ng c a d án có th l i là m t m ng PERT nh . Xác ñ nh ho t ñ ng găng, ñư ng găng Ho t ñ ng găng là ho t ñ ng mà LST - EST = LFT - EFT = 0, hay [EST, EFT] ≡ [LST, LFT] EST = LST Slack = LST − EST = 0 ⇔ ⇔ (ñ tr cho phép b ng 0). EFT = LFT Slack = LFT − EFT = 0 Gi i thích: Slack ≡ ñ n i l ng (ñ tr ). Trong ví d ñang xét, các ho t ñ ng găng là: C → J → K → L (xem b ng II.14) và t o thành ñư ng găng (Critical Path). Vì v y, phương pháp m ng PERT còn có tên là phương pháp ñư ng găng (CPM − Critical Path Method). Xác ñ nh ñư ng găng b ng ph n m m Lingo ð xác ñ nh ñư ng găng b ng ph n m m Lingo, ta có th s d ng các bài toán m u b ng cách nh n vào bi u tư ng Lingo và th c hi n các l nh File > Open > Pert.lng ñ vào bài toán PERT m u. Sau ñó nh p các s li u ñ u vào c a bài toán c n gi i vào thay các s li u c a bài toán m u, ch ng h n như s li u c a ví d ñã cho (xem hình III.6). Hình III.6. Nh p s li u cho bài toán PERT Sau ñó chúng ta th c hi n LINGO > Solve, k t qu tính toán s hi n trên màn hình (xem hình III.7). Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........70
Hình III.7. K t qu tìm cung găng c a bài toán PERT 2.2. Sơ ñ PERT v i s li u ng u nhiên Th i gian th c hi n t ng ho t ñ ng c a d án nói chung là m t lư ng bi n ñ ng khó d ñoán trư c, chúng ta gi thi t chúng là các bi n ng u nhiên. Gi s ta có các s li u ư c tính v th i gian th c hi n các ho t ñ ng c a d án (xem b ng III.14) a, m, b. Lúc ñó th i gian trung bình và ñ l ch chu n th i gian th c hi n các ho t ñ ng ñư c a + 4m + b ư c tính theo công th c t = . 6 B ng III.14. S li u ư c tính v th i gian th c hi n các ho t ñ ng Th i gian ư c tính Ho t Ho t ñ ng σ a m b t ñ ng k tr ư c (s m (nhi u kh năng x y (mu n (th i gian (ñ l ch tiêu chu n, nh t) ra nh t) nh t) trung bình) ñ bi n thiên) − A 1 2 3 2 1/3 − B 1 2 3 2 1/3 − C 1 2 3 2 1/3 D 1 2 9 3 4/3 A E 2 3 10 4 4/3 A F 0 0 0 0 0 E G 3 6 15 7 2 B H 2 5 14 6 2 B I 1 4 7 4 1 D, F J 4 9 20 10 8/3 C K 1 2 9 3 4/3 H, J L 4 4 4 4 0 G, I, K
Bư c ti p theo là l p sơ ñ m ng cho d án v i các th i gian trung bình t và tìm ñư ng găng. ðư ng găng là C → J → K → L bao g m các ho t ñ ng găng C, J, K và L. Các ho t ñ ng này có ñ tr cho phép b ng 0, hay nói cách khác, không cho phép s ch m tr nào. ðây là các ho t ñ ng c n h t s c chú tr ng, vi c ch m th c hi n b t c m t ho t ñ ng nào trong s này ñ u kéo theo s ch m tr trong ti n ñ c a c d án. T Critical Path (ti ng Anh) ñư c d ch sang ti ng Vi t là ñư ng găng vì lí do ñó. Th i gian th c hi n d án là m t lư ng ng u nhiên tính theo công th c: T = TC + TJ + TK + TL. Ta tìm kì v ng c a T (th i gian trung bình th c hi n d án) theo công th c: m = mT = tC + tJ + tK + tL = 2 + 10 + 3 + 4 = 19 (tu n). Tính ñ l ch chu n c a th i gian th c hi n d án: 2 2 2 σ = σT = σC + σ J + σ K + σ L = (1/ 3) 2 + (8 / 3)2 + (4 / 3) 2 + 0 = 3. 2 Ta coi T (th i gian th c hi n d án) là bi n ng u nhiên tuân theo lu t chu n N(m = 19; σ = 3). ð th hàm m t ñ xác su t c a T cho trên hình III.8. ð tính P, xác su t th c hi n d án trong vòng (không vư t quá) 19 tu n, ta ph i quy T v bi n ng u nhiên v i phân ph i chu n t c N(0, 1) như cho trong ph l c 1. Lúc ñó:  T − m 19 − 19  P(T ≤ 19) = P   = P(Z ≤ 0) = 0,5 (hay 50%), ≤ σ 3 ñây Z = (T - m)/σ là bi n ng u nhiên tuân theo phân ph i N(0, 1). 75% 19 21 t Hình III.8. ðư ng cong m t ñ chu n Tương t , xác su t th c hi n d án trong vòng (không vư t quá) 21 tu n ñư c tính như sau: Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........72
 T − m 21 − 19  P(T ≤ 21) = P   = P (Z ≤ 0,666) = 75%. ≤ σ 3 Ta chuy n sang xem xét v n ñ v ñ tin c y c a th i gian hoàn thành d án. Ch ng h n chúng ta mu n tr l i câu h i sau: Mu n th i gian th c hi n d án có ñ tin c y 90% thì th i gian t i thi u (tính theo s tu n) là bao nhiêu? ð t P (T ≤ t) = 90%. Tra b ng phân ph i chu n t c N(0, 1), tìm ñư c z = 1,28. Vì z = (t − 19)/3 = 1,28 nên t = 19 + 3. 1,28 ≈ 23 (tu n). Như v y, d án ñang xem xét có kh năng hoàn thành v i ñ tin c y t i 90% trong vòng (không vư t quá) 23 tu n. 2.3. ði u ch nh d án khi k ho ch m t s ho t ñ ng b phá v Ví d 4: ðôi khi trong quá trình th c hi n d án, k ho ch c a m t s ho t ñ ng b phá v . Chính vì v y, khi phát hi n d án ñang b ch m so v i k ho ch ñ ra ta c n ñ nh l i th i gian th c hi n (th i gian rút g n) m t s ho t ñ ng trong giai ño n t i. Xét các d ki n cho trong hình III.9 và b ng III.15. C 2 4 E A 1 5 B D 3 Hình III.9. Sơ ñ m ng PERT d án c n ñi u ch nh B ng III.15. S li u ñi u ch nh khi k hoach b phá v Ho t Th i gian ñ nh Th i gian rút Kinh phí b sung/1ñơn v th i gian rút g n (tri u ñ ng mc gn ñ ng) A 6 4 2 B 4 3 3 C 3 2 1 D 8 6 1,5 E 7 4 0,5 Sau khi có th i gian ñ nh m c cho các ho t ñ ng như trong b ng II.18, d dàng tìm ñư c th i gian t i thi u c n thi t ñ hoàn thành k ho ch là 16 (tu n). Tuy nhiên do yêu c u m i, c n rút g n th i gian hoàn thành d án trong vòng (không vư t quá) 10 (tu n). Mu n v y ta th c hi n các ñi m sau: − Tìm th i gian t i thi u d ñ nh th c hi n d án (16 tu n) và tìm ñư ng găng. − Ư c tính th i gian rút g n t i ña (c t 3, b ng III.15).
− Khi rút g n th i gian trên ñư ng găng cũng ph i chú tr ng ñ ng th i các cung ñư ng khác. Trên hình III.9, ta th y c n th c hi n A, C và E v i th i gian rút g n t i ña (4, 2, 4 ñ t ng các th i gian th c hi n các ho t ñ ng găng là 10 tu n), ñ ng th i rút g n các ho t ñ ng B và D m c cho phép: − Phương án 1: rút b t th i gian th c hi n ho t ñ ng B m t tu n và rút b t D m t tu n. − Phương án 2: không rút b t B và rút b t D hai tu n. V y khi c n ñi u ch nh th i gian th c hi n d án ta c n thay ñ i k ho ch c a m t s ho t ñ ng theo các bư c ñã nêu trên. Tuy có nhi u phương án ñi u ch nh d án, nhưng trong vi c phá v k ho ch các ho t ñ ng c a d án ñ ñáp ng ti n ñ m i c n chú ý v khía c nh chi phí gia tăng ñ có m t phương án t i ưu ñ m b o rút g n ñư c th i gian th c hi n v i chi phí nh nh t. ð i v i ví d trên ta ch n phương án 2. Có th áp d ng phương pháp t ng quát ñ ñi u ch nh d án theo các m c tiêu trên (phương pháp ñơn hình cho BTQHTT ñơn và ña m c tiêu) như s ñư c trình bày sau ñây. 2.4. Tính th i gian rút g n t i ưu b ng phương pháp ñơn hình ð tính th i gian rút g n b ng phương pháp ñơn hình (có th s d ng các ph n m m máy tính thích h p), ta ph i ñưa ra ñư c mô hình toán h c, hay cách khác, c n phát bi u ñư c BTQHTT (ñơn hay ña m c tiêu). Trư c h t, c n xác ñ nh các bi n quy t ñ nh. G i x1, x2, x3, x4, x5 là các th i ñi m mà các ho t ñ ng x y ra (t i các nút); yA, yB, yC, yD, yE là th i gian c n rút b t cho các ho t ñ ng ñ yêu c u m i v ñ y nhanh ti n ñ ñư c tho mãn. Ta có BTQHTT ña m c tiêu sau (c n c c ti u hóa c th i gian th c hi n d án l n t ng chi phí gia tăng): M c tiêu 1: z1 = x5 → Min M c tiêu 2: z2 = 2yA + 3yB + yC + 1,5yD + 0,5yE → Min v i các ràng bu c: Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........74
 x 2 ≥ 6 − y A + x1   x 4 ≥ 3 − yC + x 2  x 3 ≥ 4 − y B + x1  x5 ≥ 7 − yE + x 4  x5 ≥ 8 − yD + x3  x ≥ 0,i = 1, 2, 3, 4, 5 i  y j ≥ 0, j = A, B,C, D, E   y A ≤ 2, y B ≤ 1, y C ≤ 1, y D ≤ 2, y E ≤ 3  x ≤ x + 10. (*) 5 1 Có 2 cách gi i mô hình: − Chuy n m c tiêu 1 thành ràng bu c (*). N u lúc ñó BTQHTT không có phương án kh thi thì ph i n i l ng d n (*): ch ng h n thay (*) b i x5 ≤ x1 + 11. − ð nguyên c hai m c tiêu ñ gi i theo phương pháp BTQHTT ña m c tiêu. 2.5. Áp d ng m ng PERT trong phân tích chi phí và qu n lí tài chính d án Trong giai ño n ñ u ng d ng PERT và CPM, các phương pháp này thư ng ñư c áp d ng cho bài toán tìm th i gian t i thi u th c hi n d án, tìm các ho t ñ ng găng. Chúng ít khi ñư c áp d ng ñ phân tích chi phí, m c dù trong các d án thì vi c phân tích chi phí (bao g m chi phí tr c ti p, gián ti p và chi phí ti n ích) cũng r t quan tr ng. Tuy nhiên ngày nay, PERT và CPM ñư c áp d ng r t r ng rãi cho các bài toán d ng này. Ví d 5: Chúng ta xem xét d án v i các d ki n cho trong b ng III.16 và hình III.10. D th y, th i gian t i thi u ñ hoàn thành d án là 15 (tháng). B ng III.16. D ki n cho bài toán PERT chi phí Ho t Th i gian th c T ng chi phí Chi phí/m t tháng (tri u EST LST ñ ng hi n (tháng) (tri u ñ ng) ñ ng) A 0 0 3 30 10 B 0 8 2 200 100 C 3 9 1 40 40 D 3 3 4 20 5 E 7 7 5 75 15 F 4 10 2 100 50 G 4 10 1 75 75 H 12 12 3 18 6 I 5 11 4 240 60
D 4 E 2 A C H 5 F B 1 3 8 I G 6 Hình III.10. M ng PERT cho bài toán phân tích chi phí Nguyên t c ñi u hành tài chính m t d án là: − Lu ng kinh phí ph i ñư c ñưa vào d n d n sao cho ñáp ng ñư c ti n ñ d án. − N u kinh phí ñưa vào th a ho c thi u (theo ti n ñ ) thì ph i k p th i ñi u ch nh. C n n m b t ñư c: nh ng ho t ñ ng nào không dùng h t kinh phí d ki n, nh ng ho t ñ ng nào s d ng kinh phí nhi u hơn d ki n ñ có s ñi u ch nh thích h p. − Các báo cáo ñ nh kì cho phép ki m soát ñư c d án v ti n ñ và lu ng kinh phí. Mu n v y, trư c h t c n l p b ng theo dõi kinh phí cho d án t tháng 1 ñ n tháng 15 (xem b ng III.17). Ph n trên c a t ng ô ng v i các ho t ñ ng gi i ngân s m nh t, ph n dư i ng v i gi i ngân mu n nh t. Hai hàng cu i b ng dành cho kinh phí trong t ng tháng và t ng kinh phí c ng d n cho t i tháng ñó tương ng v i ho t ñ ng gi i ngân s m nh t và gi i ngân mu n nh t. B ng III.17. D ki n cho bài toán PERT chi phí T. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A 10 10 10 10 10 10 B 100 100 100 100 C 40 40 D 5 5 5 5 5 5 5 5 E 15 15 15 15 15 15 15 15 15 15 F 50 50 50 50 Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........76
G 75 75 H 6 6 6 6 6 6 I 60 60 60 60 60 60 60 60 Σ 110 110 10 45 130 115 65 75 75 15 15 15 6 6 6 10 10 10 5 5 5 5 15 115 155 140 125 66 66 66 Σ+ 110 220 230 275 405 520 585 660 735 750 765 780 786 792 798 10 20 30 35 40 45 50 65 180 335 475 600 666 732 798 D a vào b ng III.17, có th v ñư c ñ th mi n kinh phí kh thi như trên hình III.11. N u ti n ñ gi i ngân n m ngoài mi n kinh phí kh thi thì c n g p rút ñưa ra các bi n pháp ñi u ch nh ti n ñ gi i ngân. Ngoài ra, cũng có th ñi u ch nh kinh phí các ho t ñ ng c a d án d a vào b ng III.17. ñư ng gi i ngân s m nh t mi n kinh phí kh thi ñư ng gi i ngân mu n nh t Hình II.11. ð th mi n kinh phí kh thi Chú ý: Các v n ñ cơ b n c n gi i quy t khi áp d ng phương pháp PERT hay CPM trong theo dõi và ñánh giá d án là: − Xác ñ nh ñư c sơ ñ m ng PERT c a d án. − Tìm ñư c ñư ng găng và các ho t ñ ng găng. − Tính ñư c ñ tin c y ng v i các m c th i h n hoàn thành d án khi s li u là ng u nhiên.
− Bi t cách ñi u ch nh th i gian rút g n khi ti n ñ th c hi n d án là ch m so v i k ho ch. − Phân tích chi phí và ñi u hành kinh phí d án. 3. M T S MÔ HÌNH M NG KHÁC 3.1. Bài toán cây khung t i thi u Bài toán cây khung t i thi u ñư c nghiên c u và ng d ng trong nhi u lĩnh v c (Công ngh thông tin, ði n l c, Quy ho ch thu l i,...). V n ñ ñ t ra là c n xác ñ nh m t m ng ñư ng ñi t i m i nút c a m ng xu t phát t m t nút nào ñó trong m ng, sao cho t ng ñ dài các cung ñư ng này là ng n nh t. Phương pháp t t nh t gi i bài toán cây khung t i thi u (minimal spanning tree) thu c v R. Prim s ñư c trình bày trong m c này. Ví d 1: M c cáp truy n hình trong khu v c dân cư t tr m phát ñ n ñư c 7 h gia ñình v i chi phí ñư ng dây là bé nh t. Sơ ñ kho ng cách t tr m phát t i các h gia ñình như trên hình III.12. Bài toán ñ t ra là ph i phát tri n ñư c cây khung hay ñư ng ñi t i thi u sao cho t ng chi u dài các cung ñư ng là bé nh t. ð gi i ta l p b ng III.18 (chi u dài các cung ñư ng ñư c quy g n), trong ñó M là kí ki u m t s ≈ +∞, bi u th cung ñư ng không th x y ra trên th c t . M i hàng hay m i c t c a b ng ñ u bi u th các nút, ch ng h n ô n m trên giao c a hàng 2 và c t 7 (cũng gi ng như ô n m trên giao c a hàng 7 và c t 2) ñ u ch a s 9, là kho ng cách gi a hai nút 2 và 7. M t hàng và m t c t ñư c nói là liên thông v i nhau n u ô n m trên giao c a hàng và c t này ch a giá tr khác M. 6 4 300 1000 200 3 500 100 800 Nguån 600 5 ®iÖn (1) 400 1100 7 900 2 Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........78
Hình III.12. Sơ ñ kho ng cách t ngu n ñi n t i các xã B ng III.18. B ng kho ng cách các cung ñư ng √ √ (Nút Nút (c t) hàng) 1 2 3 4 5 6 7 √ 1 0 11 1 3 6 10 4 2 11 0 M M M M 9 √ 3 1 M 0 M 5 M M √ 4 3 M M 0 M 7 M 5 6 M 5 M 0 2 M … 6 10 M M 7 2 0 8 √ 7 4 9 M M M 8 0 Thu t gi i Prim Bư c kh i t o. L p b ng kho ng cách gi a các nút m ng. Trong b ng trên, ch n c t b t kì (ví d c t 1, t c là ta ch n nút 1 ñ b t ñ u), g ch b c t v a ch n ra kh i b ng. Các bư c l p Bư c 1: ðánh d u vào hàng tương ng (hàng cùng ch s ) v i c t v a ch n. Trên các hàng ñã ñư c ñánh d u tìm ô có giá tr nh nh t. Bư c 2: Ch n c t tương ng v i ô v a tìm ñư c (c t 3 bi u di n nút ch n m i, ghi cung ñư ng v a tìm ñư c 1 → 3), r i g ch b nó ñi (g ch b c t 3). N u trong b ng v n còn các c t chưa g ch b h t thì quay v bư c 1, n u trái l i chuy n sang bư c k t thúc. Bư c k t thúc. N u t t c các c t ñã b g ch b h t thì d ng v i t t c các cung ñư ng liên thông tìm ñư c t o nên cây khung t i thi u. Chú ý: Nh ng câu in nghiêng minh ho cho bư c kh i t o và bư c l p ñ u tiên. Sau 6 bư c l p, quá trình gi i k t thúc v i các cung ñư ng sau: 1 → 3, 1 → 4, 1 → 7, 3 → 5, 5 → 6 và 7 → 2. T ng ñ dài các cung ñư ng c a cây khung t i thi u là ∑ = 1 + 3 + 4 + 5 + 2 + 9 = 24. Ngoài ra, có th ch n nút kh i t o là b t c nút nào. Thu t toán Prim có th ñư c tóm t t như sau: G i N0 là t p nút ñã cho v i các kho ng cách gi a các nút ñã bi t. T i m i bư c l p, t m t t p nút N ñã ñư c l a ch n t N0 và m t t p cung ñư ng T ñã có bư c trư c, c n tìm ñư c nút ti p theo trong t p N0\N sao cho kho ng cách ng n nh t t nút ñó t i các nút trong t p N là bé nh t so v i kho ng cách ng n nh t t m t nút b t kì khác trong t p N0\N t i các nút trong t p N. Nút ch n ñư c như v y ñư c ñưa vào t p N, còn kho ng cách ng n nh t tìm ñư c tương ng v i m t cung ñư ng ñư c ñưa vào t p T. Quá trình ñư c ti p t c cho t i khi t p N trùng v i t p N0, cây khung t i thi u chính là t p T thu ñư c. Thu t toán Prim còn ñư c
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