Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only Chương QUY HO CH M NG (NETWORKS PROGRAMMING) CHƯƠNG QUY HO CH M NG (NET-NETWORKS PROGRAMMING) * M C TIÊU H C T P Sau hoàn t t h c t p chương 5, sinh viên s có kh năng: Mơ t thu t ng m ng Nh n bi t d ng toán b n quy ho ch m ng S d ng cơng c tin h c đ gi i tốn quy ho ch m ng GI I THI U M ng xu t hi n nhi u b i c nh dư i nhi u d ng khác nhau: + Các m ng lư i đư ng giao thông v n t i, m ng lư i dây n m ng thông tin liên l c… + S n xu t, phân ph i, l p k ho ch d án, qu n lý ngu n tài nguyên, b trí thi t b Bài toán quy ho ch m ng: m t d ng đ c bi t c a toán quy ho ch n tính Ví d : Bài tốn giao thơng v n t i, tốn phân cơng cơng vi c Trong chương này, ba tốn quan tr ng c a quy ho ch m ng s đư c trình bày: + Bài tốn tìm đư ng ng n nh t (Shorest-Route Problem); + Bài toán đư ng dây m c loa (Minimal-Spanning Tree); + Bài toán c c đ i lưu lư ng (Maximal Flow Problem) Trong xây d ng, mơ hình c a quy ho ch m ng có th dùng đ gi i quy t m t s toán quy ho ch b trí bình đ cơng trư ng T t c ví d mơ t lo i toán quy ho ch m ng chương tương đ i nh đơn gi n so v i toán th c t GV ThS Nguy n Thanh Phong- Trư ng Đ i h c M Tp HCM 403 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only Chương QUY HO CH M NG (NETWORKS PROGRAMMING) nh m giúp b n đ c d hi u áp d ng thu t toán Đ i v i nh ng quy ho ch m ng nh đơn gi n, có th tìm ngày l i gi i t i ưu b ng cách xem xét tr c quan suy đoán Đ i v i nh ng toán quy ho ch m ng l n ph c t p có hàng trăm, hàng ngàn nút, s g p khó khăn vi c tìm l i gi i b ng tr c giác Vì v y, ph i áp d ng thu t tốn đư c trình bày chương đ gi i quy t v n đ dù gi i b ng tay hay máy tính CÁC THU T NG C A M NG M ng (Network): bao g m m đư ng n i m l i v i + Các m đư c g i Nút (Node) • Nút cung Nút c p: có đ c m lư ng chuy n t i kh i nút l n lư ng vào nút • Nút c u: lư ng nh n vào l n lư ng chuy n t i kh i nút • Nút trung tính: lư ng vào kh i nút b ng + Các đư ng n i nút đư c g i cung/nhánh (Arc) • Cung có hư ng: Cho phép t nút A đ n nút B không cho phép theo hư ng ngư c l i (ký hi u AB) • Cung vơ hư ng: cho phép di chuy n theo c hai hư ng a) Cung có hư ng AB b) Cung vơ hư ng AB Hình 5.1 Cung có hư ng cung vơ hư ng + M ng có hư ng: ch bao g m cung có hư ng + M ng vô hư ng: bao g m cung vô hư ng GV ThS Nguy n Thanh Phong- Trư ng Đ i h c M Tp HCM 404 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only Chương QUY HO CH M NG (NETWORKS PROGRAMMING) Tuy n: n i gi a hai nút có th bao g m nhi u cung khác + Tuy n có hư ng t nút i đ n nút j m t chu i cung có hư ng t i sang j, cho phép t i sang j + Tuy n vô hư ng t nút i sang nút j m t chu i cung vô hư ng t i đ n j GV ThS Nguy n Thanh Phong- Trư ng Đ i h c M Tp HCM 405 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only Chương QUY HO CH M NG (NETWORKS PROGRAMMING) Ví d : Tuy n OT, đư ng t O sang T có th qua cung OB BD - DT (O → B → D → T) Hình 5.2 Ví d + Lưu ý r ng n có hư ng th a mãn u ki n c a n vô hư ng, u ngư c l i không Liên thông: hai nút đư c g i liên thông n u t n t i nh t m t n vô hư ng gi a chúng M ng liên thông: m ng mà t t c c p nút đ u liên thông M ng nhánh cây: bao g m t t c nút không đư c n i thành vịng Ví d : Xét m ng lư i Hình 8.3 sau, đó: + xij = lư ng chuy n t i t nút i đ n nút j; + cij = chi phí chuy n t i đơn v t nút i đ n nút j GV ThS Nguy n Thanh Phong- Trư ng Đ i h c M Tp HCM 406 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only Chương QUY HO CH M NG (NETWORKS PROGRAMMING) Hình 8.3 Sơ đ m ng BÀI TỐN TÌM ĐƯ NG ĐI NG N NH T 3.1 Đ nh nghĩa Bài tốn tìm đư ng ng n nh t (Shortest-Route/ Shortest- Path Problem) tốn tìm l trình di chuy n (c a ngư i, xe máy hay hàng hóa) t m t đ a m đ n m t đ a m khác h th ng nhi u đư ng giao thơng có s n cho t ng chi u dài đư ng ng n nh t Nói cách khác, tìm đư ng ng n nh t xu t phát t m ngu n ban đ u đ n m t chu i m đích khác Ví d : + Tìm đư ng ng n nh t t nhà máy cung c p bê tông tươi đ n cơng trư ng xây d ng + Tìm đư ng ng n nh t đ v n chuy n cơng nhân, máy móc thi t b t công ty xây d ng đ n công trư ng xây d ng + Tìm đư ng ng n nh t t m t thành ph đ n m t thành ph khác h th ng đư ng giao thơng + Tìm đư ng ng n nh t t nhà máy s n xu t đ n nhà kho ch a hàng + Tìm đư ng ng n nh t (th i gian nh t) t nhà máy s n xu t đ n nơi tiêu th s n ph m Th v c a nút: kho ng cách bé nh t t nút đ u (Nút 1) đ n nút đó: { u j = ui + dij i } Trong đó: + uj = Kho ng cách ng n nh t t nút đ n nút j v i u1 = 0; + ui = Kho ng cách ng n nh t t nút đ n nút i + dij = Kho ng cách gi a nút j nút i trư c GV ThS Nguy n Thanh Phong- Trư ng Đ i h c M Tp HCM 407 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only Chương QUY HO CH M NG (NETWORKS PROGRAMMING) 3.2 Các gi i thu t cho tốn tìm đư ng ng n nh t Gi i thu t t ng quát: + Gi i thu t ti n; + Gi i thu t Dijkstra; + Gi i thu t Floyd Gi i thu t đ quy: Gi i thu t ch dùng cho m ng có hư ng, khơng m ch vịng Gi i theo toán QHTT nguyên Chú ý: M t s ng d ng c a tốn tìm đư ng ng n nh t liên quan đ n tiêu chu n th i gian ho c chi phí thay kho ng cách Do đó, ta có d ng toán sau: 1- C c ti u quãng đư ng 2- C c ti u t ng chi phí c a m t chu i thao tác 3- C c ti u lư ng th i gian c a m t chu i thao tác B i tốn tìm đư ng ng n nh t toán c c ti u hóa nên khơng th áp d ng gi i thu t nêu có giá tr n u toán cung âm M c dù th c t , giá tr cung có th chi phí âm (t c l i nhu n dương) Chúng ta c n gi i thu t nâng cao đ gi i toán d ng 3.3 Gi i thu t ti n cho tốn Tìm đư ng ng n nh t - Bư c 1: + Tìm nút n m g n nút g c (nút xu t phát/ nút ngu n) nh t + Ghi giá tr (kho ng cách, th i gian, chi phí) t nút xu t phát đ n nút g n nh t (L p l i bư c v i n=1,2,3…cho đ n nút th n n m g n nh t nút đích.) - Bư c 2: Thành l p t p nút kh o sát (permanent set) g m nút g c nút g n nút g c nh t xác đ nh bư c GV ThS Nguy n Thanh Phong- Trư ng Đ i h c M Tp HCM 408 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only Chương QUY HO CH M NG (NETWORKS PROGRAMMING) - Bư c 3: Xác đ nh t t c nút chưa kh o sát n m g n t p nút kh o sát T p nút kh o sát (permanent set) đư c n i tr c ti p đ n ho c nhi u nút chưa kh o sát s cung c p m t ng viên cho nút g n nh t th n - Bư c 4: Tìm nút n m g n t p nút kh o sát (permanent set) nh t, ghi kho ng cách ng n nh t đ n nút t nút g c (giá tr g i th v c a nút) Lưu ý: V i m i nút kh o sát ng viên c a nó, c ng kho ng cách gi a chúng kho ng cách ng n nh t t nút g c đ n nút kh o sát Nút có kho ng cách ng n nh t s nút g n nh t th n n đư ng ng n nh t s n đư ng t o kho ng cách - Bư c 5: L p l i bư c 4: + Ti p t c l p l i trình xác đ nh th v c a nút m ng (b ng cách c ng th v c a nút g n nh t kho ng cách gi a nút) theo công th c: { } u j = u i + d ij ) i + Giá tr th v ghi nút cu i kho ng cách ng n nh t t nút xu t phát đ n nút cu i 3.4 Gi i b ng QHTT Nguyên Xét m ng g m: + m nút; + n cung có hư ng; + cij: chi phí t ng cung (i, j) Hãy tìm chi phí nh nh t đ t nút đ n nút m? Chi phí đư ng t ng chi phí t ng đo n t o nên đư ng Gi i: GV ThS Nguy n Thanh Phong- Trư ng Đ i h c M Tp HCM 409 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only Chương QUY HO CH M NG (NETWORKS PROGRAMMING) 0 đường nối từ nút i đến nút j 1 có đường nối từ nút i đến nút j G i x ij =  xij = (n u ij đư c ch n đư ng ng n nh t) Hàm m c tiêu: Min Z = ∑∑ cij * x ij i j Ràng bu c: 1 i =  • ∑ x ij − ∑ x ki = 0 neáu i = 2,m − j k −1 i = m  • xij = hay cho m i i j • cij ngun Chú ý r ng tốn đư ng ng n nh t trư ng h p đ c bi t c a toán c c ti u chi phí m ng lưu thơng T ta s xét tốn ma tr n trư ng (ma tr n đ nh hư ng cung - nút) t ng mô đun đ ng nh t có th thay ràng bu c xij = hay b ng x ij ≥ Khi tốn tr thành: Hàm m c tiêu: Min ∑∑ cij * x ij i j Ràng bu c: 1 i =  • ∑ x ij − ∑ x ki = 0 neáu i = 2,m − j k −1 neáu i = m  • x ij ≥ 3.5 Gi i thu t Đ Quy * Phương pháp đ quy: G i uj = kho ng cách ng n nh t t nút đ n nút j v i u1 = Các giá tr c a uj, j = 1,2 , n đư c tính tốn đ quy dùng cơng th c sau: { u j = u i + d ij i } GV ThS Nguy n Thanh Phong- Trư ng Đ i h c M Tp HCM 410 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only Chương QUY HO CH M NG (NETWORKS PROGRAMMING) Trong đó: + uj = Kho ng cách ng n nh t t nút đ n nút j v i u1 = 0; + ui = Kho ng cách ng n nh t t nút đ n nút i + dij = Kho ng cách gi a nút j nút i trư c Lưu ý: uj ch đư c tính sau ui đư c tính Nhãn c a nút j [uj, n] v i n nút j t o kho ng cách ng n nh t: { } u j = ui + d ij = un + dnj i Lưu ý: Gi i thu t ch dùng cho tốn khơng có vịng (Acyclic) 3.6 Gi i thu t Dijkstra cho tốn Tìm đư ng ng n nh t 3.6.1 Gi i thi u Gi i thu t Dijkstra đư c s d ng đ tìm đư ng ng n nh t t nút ngu n nút khác m ng, dùng cho c tốn có hay khơng có m ch vịng Gi i thu t có th áp d ng cho tốn m ng có vòng (Cyclic) Gi i thu t Dijkstra s d ng quy trình g n nhãn đ c bi t, cịn có tên g i gi i thu t g n nhãn G i: + ui kho ng cách ng n nh t t nút đ n nút i; + dij ≥ chi u dài cung (i, j); + i th hi n nút trư c đư ng t nút đ n nút j; ⇒ Nhãn c a nút j đư c đ nh nghĩa là: [uj, i] = [ ui + dij, i] v i dij ≥ Nhãn dùng gi i thu t Dijkstra có lo i: + Nhãn t m th i (Temporary/Tentative Label): nhãn có th b thay th b i m t nhãn khác n u t n t i đư ng ng n đ n nút kh o sát GV ThS Nguy n Thanh Phong- Trư ng Đ i h c M Tp HCM 411 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only Chương QUY HO CH M NG (NETWORKS PROGRAMMING) Ký hi u nhãn t m th i: [uj, i] hay (uj, i) + Nhãn c đ nh (Permanent Label): khơng tìm đư c đư ng ng n n a nhãn t m th i đư c chuy n thành nhãn c đ nh Ký hi u nhãn c đ nh: [uj, i]* hay [uj, i] 3.6.2 Gi i Thu t Dijkstra Gi s có m t m ng g m n nút Gi i thu t Dijkstra s tìm đư ng ng n nh t t nút ngu n đ n nút khác m ng sau: - Bư c 1: G n cho nút ngu n nhãn c đ nh [0, -]* ho c [0, S]* Gán i = Trong đó: + S th hi n kho ng cách t nút đ n + D u – (hay ch S) th hi n nút nút ngu n (nút xu t phát – starting node) - Bư c 2: + N u i =1: Tính nhãn t m th i (d1j, 1) c a nút j mà t nút có th đ n đư c, bi t r ng j nút chưa đư c g n nhãn c đ nh nút nút ngu n, d1j giá tr kho ng cách t nút đ n nút j + Nêu i > 1: Tính nhãn t m th i (uj + dij, i) c a nút j mà t nút i có th đ n đư c, bi t r ng j nút chưa đư c g n nhãn c đ nh i nút g n nhãn c đ nh Nút j cho giá tr kho ng cách uj + dij nh nh t s nút đư c g n nhãn c đ nh [uj + dij, i] + N u nút j đư c g n nhãn t m th i (uj, k) đ n t nút k đó, n u kho ng cách đ n t nút i ui + dij < uj (kho ng cách đ n t nút k), thay th nhãn t m th i (uj, k) b ng (ui + dij, i) GV ThS Nguy n Thanh Phong- Trư ng Đ i h c M Tp HCM 412 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only Chương QUY HO CH M NG (NETWORKS PROGRAMMING) b 150 c 200 d 50 e T t c đ u sai 14 Thu t tốn tìm đư ng ng n nh t có th đư c s d ng đ a Quy ho ch n đư ng cho m t kỳ ngh du l ch b ng xe b Quy ho ch n đư ng cho xe buýt trư ng h c c Xác đ nh đư ng cho tài x xe t i c n v n chuy n hàng g p d T t c đ u e T t c đ u sai 15 Thu t tốn tìm đư ng ng n nh t có th đư c s d ng đ a Tìm kho ng cách dài nh t đ gi a hai m b Tìm th i gian ng n nh t đ gi a hai m c Tìm n đư ng có c nh quan đ p nh t chuy n du l ch xuân d N i t t c nút c a m t m ng lư i v i cho c c ti u t ng s đư ng e T t c đ u sai 16 Tìm chi u dài đư ng ng n nh t t nút đ n nút T Đ n Kho ng cách (m) 250 150 200 50 150 150 100 150 a 200 GV ThS Nguy n Thanh Phong- Trư ng Đ i h c M Tp HCM 453 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only Chương QUY HO CH M NG (NETWORKS PROGRAMMING) b 350 c 250 d 450 e T t c đ u sai 17 N u mu n đánh giá xem m t m ng máy tính có b q t i hay khơng, có th s d ng thu t tốn a Tìm đư ng ng n nh t b C c đ i lưu lư ng c Đư ng dây m c loa d T t c đ u e T t c đ u sai 18 M t m ng nh đơn gi n có th đư c gi i d a vào a Phương pháp đơn hình b s suy đốn c Các k thu t tính tốn nâng cao d T t c đ u sai 19 Trong toán đư ng dây m c loa, n u có hay nhi u nút li n k có kho ng cách đ n nút đư c n i li n, a L i gi i b dư ràng bu c b Có nhi u l i gi i t i ưu c Khơng có l i gi i kh thi d Có nh t l i gi i t i ưu khác t n t i e T t c đ u sai A2- D ng tr c nghi m ho c sai Các cơng ty d ch v truy n hình cáp thư ng s d ng tốn tìm đư ng ng n nh t đ b trí h th ng đư ng dây cáp k t n i t t c h nhà cá nhân Bài toán đư ng dây m c loa ln ln có m t l i gi i t i ưu nh t GV ThS Nguy n Thanh Phong- Trư ng Đ i h c M Tp HCM 454 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only Chương QUY HO CH M NG (NETWORKS PROGRAMMING) Tiêu chu n d ng c a toán đư ng dây m c loa l p l i bư c c a thu t toán cho đ n t t c nút đư c n i li n Trong toán c c đ i lưu lư ng, đo n đư ng đư c th hi n b i s n i li n gi a nút b ng đo n th ng Bài toán c c đ i lưu lư ng có th đư c s d ng b i Hi p h i khoa h c đ nghiên c u lưu lư ng dòng nư c ch y nh m đ gi m thi u m i nguy hi m t lũ l t Bài tốn tìm đư ng ng n nh t có th đư c s d ng đ c c ti u chi u dài di chuy n vi c l p k ho ch m t chuy n ngh b ng xe Bài toán c c đ i lưu lư ng có th đư c s d ng b i k sư giao thông đ nghiên c u tác đ ng c a chu i đèn tín hi u u n giao thơng khác lên hành vi giao thông m t thành ph Trong toán c c đ i lưu lư ng, s lưu thơng có th theo c hai hư ng chi u ho c ngư c chi u m ng Các m m t đư c g i cung 10 Trong toán c c đ i lưu lư ng, c n ph i bi t kh lưu thông đ n m i nút, ch không c n bi t kh lưu thông xu t phát t nút 11 Trong tốn tìm đư ng ng n nh t, m c tiêu ph i tìm đư c n đư ng t m t m ngu n đ n m t m đích cho s lư ng nút qua nh t 12 Khi l i gi i t i ưu tìm đư c toán c c đ i lưu lư ng, m i nút s đư c k t n i v i nh t m t nút khác A3- D ng tr c nghi m n vào ch tr ng Trong gi i toán , b t đ u b ng cách ch n m t nút b t kỳ m ng a C c đ i lưu lư ng b Tìm đư ng ng n nh t GV ThS Nguy n Thanh Phong- Trư ng Đ i h c M Tp HCM 455 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only Chương QUY HO CH M NG (NETWORKS PROGRAMMING) c Đư ng dây m c loa d C c ti u lưu lư ng e Tìm đư ng dài nh t Công ty d ch v truy n hình cáp thư ng s d ng thu t tốn a Đư ng dây m c loa b Tìm đư ng ng n nh t c C c đ i lưu lư ng d Phương pháp sơ đ m ng minimax e Tìm kh lưu thơng Thu t tốn đư ng dây m c toán liên quan đ n vi c xác đ nh đư ng n i m (nút) m ng l i v i cho t ng chi u dài (kho ng cách n i li n gi a nút) nh nh t a Hai b H u h t c T t c d Nhi u nh t có th e Ít nh t có th GV ThS Nguy n Thanh Phong- Trư ng Đ i h c M Tp HCM 456 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only Chương QUY HO CH M NG (NETWORKS PROGRAMMING) Trong thu t toán , k t qu trung gian có th có giá tr a C c đ i lưu lư ng b Tìm nút g n nh t c Đư ng dây m c loa d Tìm đư ng ng n nh t e Tìm đư ng dài nh t Trong ba tốn (tìm đư ng ng n nh t, đư ng dây m c loa c c đ i lưu lư ng), ch có tốn có m t l i gi i nh t a Đư ng dây m c loa b Tìm đư ng ng n nh t c C c đ i lưu lư ng d T t c đ u e T t c đ u sai Bư c đ u tiên thu t tốn tìm đư ng ng n nh t a Ch n m t đư ng b Tìm nút n m g n nút g c nh t c Ch n m t nút b t kỳ đ b t đ u d Tìm đư ng có kh lưu thơng nh nh t e N i li n t t c nút chưa đư c k t n i Trong toán c c đ i lưu lư ng, vi c lưu thơng có th _ a Ch theo hư ng ngư c dòng b Ch theo hư ng xi dịng c M t cách b t kỳ b t k hư ng GV ThS Nguy n Thanh Phong- Trư ng Đ i h c M Tp HCM 457 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only Chương QUY HO CH M NG (NETWORKS PROGRAMMING) d Hư ng đư ng chéo e Theo c hai hư ng ngư c dịng xi dịng Trong tốn tìm đư ng ng n nh t, giá tr kho ng cách đư c ghi h p c nh m i node th hi n đư ng _ đ n nút a Ng n nh t b Dài nh t c Dài trung bình d T t c đ u e t t c đ u sai Trong ba toán (tìm đư ng ng n nh t, đư ng dây m c loa c c đ i lưu lư ng), ch có tốn có th lưu thơng theo c hư ng c a m t đư ng a Tìm đư ng ng n nh t b Đư ng dây m c loa c C c đ i lưu lư ng d T t c đ u e T t c đ u sai 10 Tiêu chu n d ng c a toán c c đ i lưu lư ng l p l i cá bư c c a thu t toán cho đ n khơng cịn _ a Gi m, nút b Gi m, kho ng cách c Tăng, cung d Tăng, lưu lư ng e Tăng, đư ng 11 M ng bao g m a cung, nút GV ThS Nguy n Thanh Phong- Trư ng Đ i h c M Tp HCM 458 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only Chương QUY HO CH M NG (NETWORKS PROGRAMMING) b Các ph n t , đư ng c Các cung, đư ng th ng d Đư ng tròn, đư ng cong b c ba e Các nút, module 12 toán tìm l trình di chuy n (c a ngư i, xe máy hay hàng hóa) t m t đ a m đ n m t đ a m khác h th ng nhi u đư ng giao thơng có s n cho t ng chi u dài đư ng ng n nh t a Đư ng dây m c loa b C c đ i lưu lư ng c Tìm đư ng ng n nh t d T t c đ u e T t c đ u sai 13 Bài tốn tìm lưu lư ng t i đa (kh i lư ng hàng t ng c ng, s đoàn xe, s toa tàu) có th lưu thơng đư c m t m ng lư i đư ng m t kho ng th i gian quy đ nh đư c g i toán a Đư ng dây m c loa b C c đ i lưu lư ng c Tìm đư ng ng n nh t d T t c đ u e T t c đ u sai 14 toán xác đ nh đư ng n i t t c m (nút) m ng l i v i cho t ng chi u dài (kho ng cách n i li n gi a nút) nh nh t a Đư ng dây m c loa b C c đ i lưu lư ng c Tìm đư ng ng n nh t d T t c đ u e T t c đ u sai GV ThS Nguy n Thanh Phong- Trư ng Đ i h c M Tp HCM 459 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only Chương QUY HO CH M NG (NETWORKS PROGRAMMING) 15 N u b n mu n v sơ đ b trí văn phòng m t tòa nhà l n, thu t tốn _ có th h u d ng a Đư ng dây m c loa b C c đ i lưu lư ng c Tìm đư ng ng n nh t d T t c đ u e T t c đ u sai 16 Trong thu t toán _, ph i l p l i bư c u ch nh kh lưu thông đư ng a Tìm đư ng ng n nh t b C c đ i lưu lư ng c Đư ng dây m c loa d T t c đ u e T t c đ u sai 17 Các hi p h i khoa h c k thu t thư ng d báo kh x y lũ l t nh dùng thu t toán _ a C c đ i lưu lư ng b Tìm đư ng ng n nh t c Đư ng dây m c loa d T t c đ u e T t c đ u sai A4- D ng tr c nghi m liên k t m nh đ phù h p 1.1 Đư ng dây m c loa a Các đư ng m ng 1.2 Thu t toán c c đ i lưu lư ng b Đư ng dây m c loa 1.3 Tìm đư ng ng n nh t c Các m m ng 1.4 Ch n m t nút b t kỳ đ b t d Kho ng cách di chuy n đ u 1.5 Các nút e Kh lưu thông t i đa c a GV ThS Nguy n Thanh Phong- Trư ng Đ i h c M Tp HCM 460 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only Chương QUY HO CH M NG (NETWORKS PROGRAMMING) xe c m t m ng lư i đư ng giao thông 1.6 Các cung f Công ty l p đ t đư ng dây n tho i 1.7 Các k t qu trung gian có ý g C c đ i lưu lư ng nghĩa h Tìm đư ng ng n nh t GV ThS Nguy n Thanh Phong- Trư ng Đ i h c M Tp HCM 461 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only Chương QUY HO CH M NG (NETWORKS PROGRAMMING) B- Ngân hàng câu h i t lu n: Nêu tên mơ hình quy ho ch m ng thư ng đư c s d ng đ tìm l i gi i t i ưu cho tốn khác Mơ t tốn đư ng dây m c loa Mơ t tốn c c đ i lưu lư ng Trình bày thành ph n c u t o nên m ng Trình bày gi i thu t ti n cho tốn Tìm đư ng ng n nh t Trình bày bư c đ gi i tốn c c đ i lưu lư ng Trình bày bư c gi i toán đư ng dây m c loa Trình bày cách th c xác đ nh l i gi i t i ưu khác s d ng thu t toán đư ng dây m c loa Trình bày cách th c xác đ nh l i gi i t i ưu khác s d ng thu t toán tìm đư ng ng n nh t 10 Mơ t lý t i toán c c đ i lưu lư ng ch có nh t m t l i gi i C- Ngân hàng t p & tình hu ng th o lu n: Công ty s n xu t n i th t Phương Nam Hàng ngày công ty s n xu t n i th t Phương Nam ph i v n chuy n s n ph m n i th t (bàn, gh , t …) t nhà máy s n xu t đ n nhà kho ch a hàng B n giúp ông Nam, giám đ c cơng ty tìm đư ng ng n nh t t nhà máy s n xu t (nút 1) đ n nhà kho (nút 6) Cho bi t sơ đ m ng lư i đư ng giao thông đư c th hi n hình sau (v i chi u dài n đư ng tính theo đơn v km) GV ThS Nguy n Thanh Phong- Trư ng Đ i h c M Tp HCM 462 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only Chương QUY HO CH M NG (NETWORKS PROGRAMMING) Hình Sơ đ n đư ng giao thơng t nhà máy đ n nhà kho Công ty Stagecoach Shipping c n ph i v n chuy n cam b ng xe t i t thành ph Los Angeles đ n nơi tiêu th t i thành ph khác phía Tây Trung Tây c a nư c M Cho bi t kho ng cách th i gian (tính b ng gi ) đ i v i xe t i di chuy n t Angeles đ n thành ph khác đư c th hi n thành ph Los hình v sau Hình H th ng đư ng giao thông t Los Angeles đ n thành ph GV ThS Nguy n Thanh Phong- Trư ng Đ i h c M Tp HCM 463 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only Chương QUY HO CH M NG (NETWORKS PROGRAMMING) B n giúp giám đ c công ty mu n xác đ nh đư ng ng n nh t (nghĩa ph i t i thi u th i gian v n chuy n cam) c a xe t i t m ngu n (thành ph Los Angeles) đ n nơi th Cơng ty xây d ng An Bình Cơng ty xây d ng An Bình tri n khai thi công xây d ng m t d án khu h cao c p thành ph Nha Trang Ơng Bình, giám đ c k thu t c a công ty, mu n xác đ nh h th ng đư ng ng ng n nh t n i li n h n m r i rác khu v c cho chi phí xây d ng h th ng đư ng ng thoát nư c c a khu h cao c p nh t Cho bi t m ng lư i th hi n kho ng cách (đơn v 100m) c a h d án đư c th hi n hình sau: Hình Sơ đ m ng lư i tìm h th ng đư ng ng thoát nư c ng n nh t Đ thi t l p d án xây d ng phát tri n h th ng đư ng giao thông c a thành ph Vi n Đông, công ty tư v n xây d ng Vinh Quang c n xác đ nh s lư ng xe máy t i đa có th lưu thơng n đư ng t phía Tây sang phía Đông c a thành ph Cho bi t sơ đ m ng lư i đư ng s lư ng xe máy (100 chi c/gi ) đư c th hi n hình sau GV ThS Nguy n Thanh Phong- Trư ng Đ i h c M Tp HCM 464 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only Chương QUY HO CH M NG (NETWORKS PROGRAMMING) Hình/ H th ng m ng lư i đư ng kh lưu thông t ng n đư ng c a thành ph Vi n Đông B n giúp ông Quang, giám đ c công ty, xác đ nh s lư ng xe máy t i đa có th lưu thơng n đư ng t phía Tây sang phía Đơng GV ThS Nguy n Thanh Phong- Trư ng Đ i h c M Tp HCM 465 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only Chương QUY HO CH M NG (NETWORKS PROGRAMMING) SÁCH VÀ WEBSITE THAM KH O 7.1 Sách tham kh o [1] Nguy n Th ng, Cao Hào Thi, Trư ng đ i h c Bách Khoa TP HCM, 1998 Phương pháp đ nh lư ng qu n lý, Nhà xu t b n Th ng Kê [2] Lê Văn Ki m, Ph m H ng Luân, 2005 Nh ng toán t i ưu qu n lý kinh doanh xây d ng, Nhà xu t b n Đ i h c Qu c Gia TP H Chí Minh [3] Huỳnh Trung Lương, Trương Tôn Hi n Đ c, 2003 Phương pháp Đ nh lư ng qu n lý v n hành, Nhà xu t b n Khoa h c K Thu t [4] Bernard W Taylor III, Virginia Polytechnic Institute and State University, 2007 Introduction to Management Science, 9th Edition, Prentice Hall International, Inc [5] Anderson, Sweeney, Williams, University of Cincinnati, 1997 An introduction to management science: Quantitative approaches to decision making, 8th Edition, West Publishing Company [6] Barry Render, Ralph M.Stair Jr., Michael E Hanna, Florida State University, 2008 Quantitative Analysis for Management, 10th Edition, Prentice Hall International [7] Hamdy A.Taha, University of Arkansas, Fayetteville, 2007 Operations research: An introduction, th Edition, Pearson Prentice Hall [8] Hillier, Lieberman, Stanford University, 2001 Introduction to Operations Research, 8th Edition, McGraw-Hill Companies 7.2 Website tham kh o http://elearning.ou.edu.vn http://highered.mcgraw-hill.com/sites/007299066x/student_view0/ GV ThS Nguy n Thanh Phong- Trư ng Đ i h c M Tp HCM 466 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only Chương QUY HO CH M NG (NETWORKS PROGRAMMING) http://highered.mcgrawhill.com/sites/0073129038/information_center_view0/ GV ThS Nguy n Thanh Phong- Trư ng Đ i h c M Tp HCM 467 ... 100 Nút 1-2 150 Nút 2-3 190 Nút 3 -5 290 Nút 5- 6 {1} 1 1-2 100 1-3 200 1-3 200 2-3 100+ 50 = 150 2-4 100+200=300 2 -5 100+100=200 2-4 300 2 -5 200 3 -5 150 +40=190 2-4 300 5- 4 190+ 150 =3401 5- 6 90+100=290... t p t p nút kh o sát (xu t phát t nút 5) Có đư ng xu t phát t t p nút kh o sát (nút 1, , 5) đ n nút n đư ng 2-4 5- 4 56 Kho ng cách ng n nh t l trình 1-3 - 5- 6 (190 + 100 = 290 km) Vì v y, nút s... lưu thông t i đa t nút đ n nút 50 0 chi c/gi bao g m: + Tuy n đư ng 1-2 -6 200 chi c/gi ; + Tuy n đư ng 1-2 - 4-6 100 chi c/gi ; + Tuy n đư ng 1-3 - 5- 6 200 chi c/gi B ng 5. 2 Tóm t t l i gi i c a toán