Giáo trình tin học trong quản lý xây dựng - Chương 5

Tài liệu tham khảo Giáo trình điện tử môn học tin học trong quản lý xây dựng ( GV. ThS. Nguyễn Thanh Phong - Khoa kỹ thuật và công nghệ ) - Chương 5 Quy hoạch mạng
Nội dung trích xuất từ tài liệu:
Giáo trình tin học trong quản lý xây dựng - Chương 5 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only.Chương 5. QUY HO CH M NG (NETWORKS PROGRAMMING) CHƯƠNG 5 QUY HO CH M NG (NET-NETWORKS PROGRAMMING)* M C TIÊU H C T PSau khi hoàn t t h c t p chương 5, sinh viên s có kh năng: 1. Mô t các thu t ng chính trong m ng. 2. Nh n bi t 3 d ng bài toán cơ b n trong quy ho ch m ng. 3. S d ng các công c tin h c đ gi i bài toán quy ho ch m ng.1. GI I THI U M ng xu t hi n trong nhi u b i c nh và dư i nhi u d ng khácnhau: + Các m ng lư i đư ng giao thông v n t i, m ng lư i dây đi n và 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: là m t d ng đ c b i t c a các b ài toánquy ho ch tuy n tính. Ví d : Bài toán giao thông v n t i, bài toánphân công công vi c. Trong chương này, ba bài toán quan tr ng c aquy ho ch m ng s đ ư c trình bày: + Bài toán tìm đư ng đi 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, 3 mô hình c a quy ho ch m ng có th d ùng đgi i quy t m t s bài toán trong quy ho ch và b trí bình đ côngtrư ng. T t c các ví d mô t các lo i bài toán quy ho ch m ng trongchương này tương đ i nh và đơn gi n hơn so v i các bài toán th c tGV. 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 5. QUY HO CH M NG (NETWORKS PROGRAMMING)nh m giúp b n đ c d hi u và áp d ng các thu t toán. Đ i v i nh ngquy ho ch m ng nh và đơn gi n, chúng ta có th tìm ra ngày l i gi it i ưu b ng cách xem xét tr c quan và suy đoán. Đ i v i nh ng bàitoán quy ho ch m ng l n và ph c t p có hàng trăm, hàng ngàn nút,chúng ta s g p khó khăn trong vi c tìm l i gi i b ng tr c giác. Vìv y, chúng ta ph i áp d ng các thu t toán đư c trình bày trong chươngnày đ gi i quy t v n đ dù gi i b ng tay hay trên máy tính.2. CÁC THU T N G C A M NG M ng (Network): bao g m các đi m và các đư ng n i các đi mnày l i v i nhau. + Các đi m này đư c g i là các Nút (Node).• Nút cung Nút c p: có đ c đi m là lư ng chuy n t i ra kh i nút đól n hơn lư ng đi vào nút đó.• Nút c u: lư ng nh n vào l n hơn lư ng chuy n t i ra kh i nút.• Nút trung tính: lư ng đi vào và đi ra kh i nút b ng nhau. + Các đư ng n i các nút đư c g i là các cung/nhánh (Arc).• Cung có hư ng: Cho phép đi t 1 nút A đ n nút B và không chophép đi 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 và cung vô hư ng + M ng có hư ng: ch bao g m các cung có hư ng. + M ng vô hư ng: bao g m các 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 5. QUY HO CH M NG (NETWORKS PROGRAMMING) Tuy n: n i gi a hai nút và có th bao g m nhi u cung khác nhau. + Tuy n có hư ng t nút i đ n nút j là m t chu i các cung có hư ng t i sang j, do đó cho phép đi t i sang j. + Tuy n vô hư ng t nút i sang nút j là m t chu i các cung vô hư ng t i đ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 5. QUY HO CH M NG (NETWORKS PROGRAMMING)V í d : Tuy n OT, đư ng đi t O sang T có th đ i qua các cung OB -BD - DT (O → B → D → T) Hình 5.2. Ví d + Lưu ý r ng tuy n có hư ng th a mãn đi u ki n c a tuy n vô hư ng, nhưng đi u ngư c l i không đúng Liên thông: hai nút đư c g i là liên thông n u t n t i ít nh t m ttuy n vô hư ng gi a chúng. M ng liên thông: là m ng mà t t c các c p nút đ u liên thông. M ng nhánh cây: bao g m t t c các nút nhưng không đư c n ithành vòng.V í d : Xét 1 m ng lư i như trong Hình 8.3 như sau, trong đó: + 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 jGV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 406 Generated by Foxit PDF Creator © Foxit Soft ...