›
›

Quy hoạch mạng (Networks Programming) - Nguyễn Thanh Phong

pdf 65 trang hapham 2770
Download
Bạn đang xem 20 trang mẫu của tài liệu "Quy hoạch mạng (Networks Programming) - Nguyễn Thanh Phong", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfquy_hoach_mang_networks_programming_nguyen_thanh_phong.pdf

Nội dung text: Quy hoạch mạng (Networks Programming) - Nguyễn Thanh Phong

  1. Generated by Foxit PDF Creator © Foxit Software 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ẬP Sau 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ác nhau: + 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 biệt của các bài toán quy hoạch tuyến tính. Ví dụ: Bài toán giao thông vận tải, bài toán phân công công việc. Trong chương này, ba bài toán quan trọng của quy 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ông trường. Tất cả các ví dụ mô tả các loại bài toán quy hoạch mạng trong chương này tương đối nhỏ và đơn giản hơn so với các bài toán thực tế GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 403
  2. Generated by Foxit PDF Creator © Foxit Software 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ững quy hoạch mạng nhỏ và đơn giản, chúng ta có thể tìm ra ngày lời giải tối ưu bằng cách xem xét trực quan và suy đoán. Đối với những bài toá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ương nà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 NGỮ CỦA MẠNG Mạng (Network): bao gồm các điểm và các đường nối các điểm nà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 cho phé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
  3. Generated by Foxit PDF Creator © Foxit Software 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
  4. Generated by Foxit PDF Creator © Foxit Software 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ột tuyế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ối thà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 j GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 406
  5. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) Hình 8.3. Sơ đồ mạng 3. BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT 3.1. Định nghĩa Bài toán tìm đường đi ngắn nhất (Shortest-Route/ Shortest- Path Problem) là bài 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 điểm này đến một địa điểm khác trên hệ thống nhiều đường giao thông có sẵn sao cho tổng chiều dài đường đi là ngắn nhất. Nói cách khác, nó tìm đường đi ngắn nhất xuất phát từ 1 điểm nguồn ban đầu đến một chuỗi các điểm đích khác nhau. Ví dụ: + Tìm đường đi ngắn nhất từ nhà máy cung cấp bê tông tươi đến các công trường xây dựng. + Tìm đường đi 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ác công trường xây dựng. + Tìm đường đi ngắn nhất từ một thành phố này đến một thành phố khác trên hệ thống đường giao thông. + Tìm đường đi ngắn nhất từ nhà máy sản xuất đến nhà kho chứa hàng. + Tìm đường đi ngắn nhất (thời gian ít nhất) từ nhà máy sản xuất đến nơi tiêu thụ sản phẩm. Thế vị của 1 nút: là khoảng cách bé nhất từ nút đầu (Nút 1) đến nút đó: uj= min u i + dij i { } Trong đó: + uj = Khoảng cách ngắn nhất từ nút 1 đến nút j với u1 = 0; + ui = Khoảng cách ngắn nhất từ nút 1 đến nút i + dij = Khoảng cách giữa nút j và nút i trước nó GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 407
  6. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) 3.2. Các giải thuật cho bài toán tìm đường đi 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 bài toán QHTT nguyên. Chú ý: Một số ứng dụng của bài toán tìm đường đi ngắn nhất liên quan đến tiêu chuẩn thời gian hoặc chi phí thay vì khoảng cách. Do đó, ta có các dạng bài toán như sau: 1- Cực tiểu quãng đường đi. 2- Cực tiểu tổng chi phí của một chuỗi các thao tác. 3- Cực tiểu lượng thời gian của một chuỗi các thao tác. Bởi vì bài toán tìm đường đi ngắn nhất là bài toán cực tiểu hóa nên chúng ta không thể áp dụng các giải thuật nêu ở trên nếu bài toán có giá trị ở các cung là âm. Mặc dù trong thực tế, giá trị trên các cung có thể là chi phí âm (tức lợi nhuận dương). Chúng ta cần các giải thuật nâng cao hơn để giải các bài toán dạng này. 3.3. Giải thuật tiến cho bài toán Tìm đường đi 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 này với n=1,2,3 cho đến khi nút thứ n nằm gần nhất là 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 và nút gần nút gốc nhất đã xác định ở bước 1. GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 408
  7. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) - Bước 3: Xác định tất cả cá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 1 hoặc nhiều nút chưa khảo sát nào đó 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, và ghi khoảng cách ngắn nhất đến nút này từ nút gốc (giá trị này gọi là thế vị của nút). Lưu ý: Với mỗi nút đã khảo sát và các ứng viên của nó, cộng khoảng cách giữa chúng và khoảng cách ngắn nhất từ nút gốc đến nút đã khảo sát đó. Nút nào có khoảng cách ngắn nhất sẽ là nút gần nhất thứ n và tuyến đường ngắn nhất sẽ là tuyến đường tạo ra khoảng cách này. - Bước 5: Lặp lại bước 3 và 4: + Tiếp tục lặp lại quá trình xác định thế vị của các nút trong mạng (bằng cách cộng thế vị của nút gần nhất và khoảng cách giữa 2 nút) theo công thức: uj= min u i + dij ) i { } + Giá trị thế vị ghi ở nút cuối cùng chính là khoảng cách ngắn nhất từ nút xuất phát đến nút cuối cùng. 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í trên từng cung (i, j). Hãy tìm chi phí nhỏ nhất để đi từ nút 1 đến nút m? Chi phí trên đường đi là tổng chi phí từng đoạn tạo nên đường đi đó. Giải: GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 409
  8. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) neáu khoâng coù ñöôøng noái töø nuùt i ñeán nuùt j ì0 Gọi xij = í neáu coù ñöôøng noái töø nuùt i ñeán nuùt j î1 xij = 1 (nếu ij được chọn là đường đi ngắn nhất) Hàm mục tiêu: Min Z= åå cij * x ij i j Ràng buộc: ì1 neáu i = 1 ï neáu i = · åxij- å x ki =í 0 2,m - 1 j k ï neáu i = m î-1 · xij = 0 hay 1 cho mỗi i và j · cij nguyên Chú ý rằng bài toán đường đi ngắn nhất là trường hợp đặc biệt của bài toán cực tiểu chi phí trên mạng lưu thông. Từ đó ta sẽ xét toán ma trận trường (ma trận định hướng cung - nút) là tổng mô đun đồng nhất và có thể thay ràng buộc xij = 0 hay 1 bằng xij ³ 0 . Khi đó bài toán trở thành: Hàm mục tiêu: Min ååcij *x ij i j Ràng buộc: ì1 neáu i = 1 ï neáu i = · åxij- å x ki =í 0 2,m - 1 j k ï neáu i = m î-1 · xij ³ 0 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 1 đến nút j với u1 = 0. Các giá trị của uj, j = 1,2 , n được tính toán đệ quy dùng công thức sau: uj= min u i + dij i { } GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 410
  9. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) Trong đó: + uj = Khoảng cách ngắn nhất từ nút 1 đến nút j với u1 = 0; + ui = Khoảng cách ngắn nhất từ nút 1 đến nút i + dij = Khoảng cách giữa nút j và nút i trước nó Lưu ý: uj chỉ được tính sau khi ui đã được tính. Nhãn của nút j là [uj, n] với n là nút j tạo ra khoảng cách ngắn nhất: uj= min u i + dij = un + dnj. i { } Lưu ý: Giải thuật này chỉ dùng cho các bài toán không có vòng (Acyclic). 3.6. Giải thuật Dijkstra cho bài toán Tìm đường đi ngắn nhất 3.6.1. Giới thiệu Giải thuật Dijkstra được sử dụng để tìm đường đi ngắn nhất từ nút nguồn và các nút khác trong mạng, dùng cho cả bài toán có hay không có mạch vòng. Giải thuật này có thể áp dụng cho các bài toán mạng có vòng (Cyclic). Giải thuật Dijkstra sử dụng 1 quy trình gắn nhãn đặc biệt, do đó nó còn có tên gọi là giải thuật gắn nhãn. Gọi: + ui là khoảng cách ngắn nhất từ nút 1 đến nút i; và + dij ³ 0 là chiều dài cung (i, j); + i thể hiện nút trước trên con đường từ nút 1 đến nút j; Þ Nhãn của nút j được định nghĩa là: [uj, i] = [ ui + dij, i] với dij ³ 0 Nhãn dùng trong giải thuật Dijkstra có 2 loại: + Nhãn tạm thời (Temporary/Tentative Label): nhãn này có thể bị thay thế bởi một nhãn khác nếu tồn tại 1 đường đi ngắn hơn đến nút đang khảo sát. GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 411
  10. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. 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): khi không tìm được 1 đường đi nào ngắn hơn nữa thì 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ử chúng ta có một mạng gồm n nút. Giải thuật Dijkstra sẽ tìm đường đi ngắn nhất từ nút nguồn 1 đến các nút khác trong mạng như sau: - Bước 1: Gắn cho nút nguồn 1 nhãn cố định [0, -]* hoặc [0, S]*. Gán i = 1. Trong đó: + Số 0 thể hiện khoảng cách từ nút 1 đến chính nó. + Dấu – (hay chữ S) thể hiện nút 1 là nút nguồn (nút xuất phát – starting node). - Bước 2: + Nếu i =1: Tính các nhãn tạm thời (d1j, 1) của các nút j mà từ nút 1 có thể đi đến được, biết rằng j là các nút chưa được gắn nhãn cố định và nút 1 là nút nguồn, d1j là giá trị khoảng cách từ nút 1 đến nút j. + Nêu i > 1: Tính các nhãn tạm thời (uj + dij, i) của các nút j mà từ nút i có thể đi đến được, biết rằng j là các nút chưa được gắn nhãn cố định và i là nút đã gắn nhãn cố định. Nút j cho chúng ta giá trị khoảng cách uj + dij nhỏ nhất sẽ là nút được gắn nhãn cố định [uj + dij, i]. + Nếu nút j đã được gắn 1 nhãn tạm thời (uj, k) đến từ 1 nút k nào đó, và nếu khoảng cách đến từ nút i là ui + dij < uj (khoảng cách đến từ nút k), chúng ta 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
  11. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) - Bước 3: + Nếu tất cả các nút đã được gắn nhãn cố định. Ta dừng và đọc kết quả tìm đường đi ngắn nhất từ nút 1 đến nút k bằng cách theo chiều ngược dòng. + Ngược lại, chọn 1 nút r nào đó chưa được gắn nhãn cố định [ur, s] có ur bé nhất trong các nút được gắn nhãn tạm thời. Gán i = r, lặp lại bước 2. Chú ý: - Chúng ta phải tính (n-1) vòng lặp để tìm khoảng cách ngắn nhất đến tất cả các nút. - Nếu chúng ta chỉ muốn tìm đường đi ngắn nhất từ nút nguồn 1 đến một nút k nào đó thì chúng ta có thể dừng khi nút k được gắn nhãn cố định . - Nếu chúng ta muốn tìm đường đi ngắn nhất từ một nút k bất kỳ đến các nút trong mạng thì chúng ta sẽ bắt đầu từ nút này bằng cách gán nó nhãn cố định [0, -]* hoặc [0, S]*. Sau đó, tiến hành các bước tiếp theo của giải thuật Dijkstra. 3.7. Ví dụ minh họa: 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 các 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. Ông Nam, giám đốc công ty, muốn tìm đường đi 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 như trong hình 8.4 sau đây (với chiều dài tuyến đường tính theo đơn vị km). GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 413
  12. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) Hình 5.4. Sơ đồ các tuyến đường giao thông từ nhà máy đến nhà kho Giải bài toán bằng Giải thuật tiến Cách 1: Giải bằng hình vẽ Quan sát hình 8.4, chúng ta thấy rằng nút nằm gần nút gốc (nút 1-nhà máy sản xuất) nhất là nút 2, với khoảng cách là 100 km. Như vậy, chúng ta có thể nối nút 1 và nút 2 và ghi vào giá trị 100. Khi đó, nút 2 sẽ là nút vào tập nút đã khảo sát. GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 414
  13. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) Hình 5.5. Vòng lặp thứ nhất Tiếp theo, chúng ta phải xác định tất cả các nút xuất phát từ tập nút đã khảo sát (nút 1 và nút 2). Đó chính là nút 3, 4 và 5. Chúng ta sẽ xác định đường đi ngắn nhất từ tập nút đã khảo sát (nút 1 và nút 2) đến nút 3, 4 và 5. Có 1 đường đi xuất phát từ nút 1 là tuyến đường 1-3; và 3 đường đi xuất phát từ nút 2 là tuyến đường 2-3, tuyến đường 2-4 và tuyến đường 2-5. Đường đi có khoảng cách ngắn nhất là theo tuyến đường 1-2-3 (100+50 = 150 km). Vì vậy, nút 3 sẽ trở thành nút vào trong tập nút đã khảo sát. Và ta ghi giá trị 150 là thế vị của nút 3. GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 415
  14. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) Hình 5.6. Vòng lặp thứ hai Tương tự, chúng ta lặp lại quá trình để xác định thế vị cho nút 4 và 5. Tập nút đã khảo sát lúc này gồm có nút 1, 2 và 3. Tiếp theo, ta phải xác định nút tiếp theo vào trong tập nút đã khảo sát. Lúc này, chúng ta có nút 4, 5 là các nút nằm gần tập tập nút đã khảo sát (xuất phát từ nút 2 và nút 3). Có 3 đường đi xuất phát từ tập nút đã khảo sát (nút 1, 2, và 3) đến các nút 4 và 5 là các tuyến đường 2-4, 2-5 và 3-5. Khoảng cách ngắn nhất là lộ trình 1-3- 5 (150 + 40 = 190 km). Vì vậy, nút 5 sẽ là nút tiếp theo vào trong tập nút đã khảo sát. GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 416
  15. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) Hình 5.7. Vòng lặp thứ ba Tập nút đã khảo sát lúc này gồm có nút 1, 2 , 3 và 5. Tiếp theo, ta phải xác định nút tiếp theo vào trong tập nút đã khảo sát. Lúc này, chúng ta có nút 4 và nút 6 là các nút nằm gần tập tập nút đã khảo sát (xuất phát từ nút 5). Có 3 đường đi xuất phát từ tập nút đã khảo sát (nút 1, 2 , 3 và 5) đến các nút 4 và 6 là các tuyến đường 2-4 5-4 và 5- 6. Khoảng cách ngắn nhất là lộ trình 1-3- 5-6 (190 + 100 = 290 km). Vì vậy, nút 6 sẽ là nút tiếp theo vào trong tập nút đã khảo sát. GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 417
  16. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) Hình 5.7. Vòng lặp thứ tư (cuối cùng) - Như vậy, đường đi có khoảng cách ngắn nhất từ nút 1 đến nút 6 là 290 km theo tuyến đường 1-3-5-6. Cách 2: Giải bằng cách lập bảng Bảng 5.1. Giải bài toán tìm đường đi ngắn nhất bằng cách lập bảng Tập nút Tuyến Tổng Nút Khoảng Nút Đoạ đã khảo sát đường khoảng cách chưa cách gần n n nối trực tiếp với khảo (Thế vị nút khảo ngắn nhất nút nút chưa khảo sát sát chưa khảo sát nhất thứ n nối sát) {1} 1 1 2 1-2 100 100 Nút 2 1-2 1 3 1-3 200 {1,2} 1 3 1-3 200 2 2 3 2-3 100+ 50=150 150 Nút 3 2-3 2 4 2-4 100+200=300 2 5 2-5 100+100=200 {1,2,3} 2 4 2-4 300 3 2 5 2-5 200 3 5 3-5 150+40=190 190 Nút 5 3-5 {1,2,3,5} 2 4 2-4 300 4 5 4 5-4 190+150=3401 5 6 5-6 90+100=290 290 Nút 6 5-6 3.7.1. Giải bằng giải Thuật Dijkstra (100, 1) GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 418
  17. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) [0, -] (200, 1) Hình 5.8a. Vòng lặp thứ nhất [100, 1] [0, -] (200, 1) Hình 5.8b. Vòng lặp thứ nhất GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 419
  18. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) [100, 1] (300, 2) [0, -] (150, 2) (200, 2) Hình 5.9a. Vòng lặp thứ hai GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 420
  19. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) [100, 1] (300, 2) [150, 2] (190, 3) Hình 5.9b. Vòng lặp thứ hai [100, 1] (300, 2) (290, 5) [150, 2] [190, 3] Hình 5.10. Vòng lặp thứ ba GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 421
  20. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) [100, 1] (300, 2) [290, 5] [150, 2] [190, 3] Hình 5.11. Vòng lặp thứ tư [100, 1] [300, 2] [290, 5] [150, 2] [190, 3] Hình 5.12. Vòng lặp thứ năm GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 422
  21. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) 3.8. Sử dụng các phần mềm để giải bài toán Tìm đường đi ngắn nhất (Shortest-Route Problem) Công ty Stagecoach Shipping cần phải vận chuyển cam bằng 6 xe tải từ thành phố Los Angeles đến nơi tiêu thụ tại 6 thành phố khác ở phía Tây và Trung Tây của nước Mỹ. Cho biết khoảng cách và thời gian (tính bằng giờ) đối với 1 xe tải di chuyển từ thành phố Los Angeles đến các thành phố khác được thể hiện ở hình vẽ sau. Hình. Hệ thống đường giao thông từ Los Angeles đến các thành phố Bạn hãy giúp giám đốc công ty muốn xác định đường đi ngắn nhất (nghĩa là phải tối thiểu thời gian vận chuyển cam) của các xe tải từ điểm nguồn (thành phố Los Angeles) đến các nơi tiêu thụ. GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 423
  22. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) 3.8.1. Phần mềm QM Bước 1. - Menu Module® chọn Networks: - Menu File-New- chọn 2. Shortest Route (Bài toán tìm đường đi ngắn nhất): - Hộp thoại Creat data set for Networks/ Shortest Route (Nhập dữ liệu cho Bài toán Tìm đường đi ngắn nhất) xuất hiện: GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 424
  23. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) - Title: Nhập tên Bài toán - Number of Branches: Nhập số đường đi (bằng cách kéo mouse sang phải) - Row names: chọn kiểu tên cho cung (đường đi) - Network type: + Undirected: Giá trị (Khoảng cách/Chi phí/Thời gian) đi và về trên các tuyến đường là như nhau (đường 2 chiều/không phải đường 1 chiều). + Directed: Đường 1 chiều Bước 2. Bảng nhập số liệu (Khoảng cách/Chi phí/Thời gian từ một nút đến một nút) sẽ xuất hiện. GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 425
  24. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) - Origin: chọn nút đầu tiên (nút nguồn). - Destination: Chọn nút cuối cùng (nút đích). - Khai báo thông số của đường đi: + Start node: nút đầu + End node: nút cuối + Distance: khoảng cách/thời gian/chi phí Bước 3. Bấm chọn (Giải bài toán) ® Bảng kết quả cho biết Đường đi ngắn nhất từ nút 1 đến nút 7 là 43 giờ với lộ trình 1-3-4-7 * Lưu ý: Ta có thể xác định đường đi ngắn nhất trong sơ đồ mạng lưới bởi 2 nút bất kỳ bằng cách lựa chọn Origin: chọn nút đầu tiên (nút nguồn) và Destination: Chọn nút cuối cùng (nút đích). Ví dụ như khoảng cách ngắn nhất từ nút 1 đến nút 5 sẽ có kết quả sau: GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 426
  25. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) 3.8.2. Phần mềm Win QSB Bước 1. Double Click vào biểu tượng NET (Network Modeling) Bước 2. Menu File® chọn New Problem® Hộp thoại NET Problem Specification xuất hiện: - Problem Type: chọn Shortest Path Problem (Bài toán Tìm đường đi ngắn nhất) - Objective Criterion: chọn Minimization (Cực tiểu hàm mục tiêu, mặc định đối với bài toán Tìm đường đi ngắn nhất) - Data Entry Format: + Spreadsheet Matrix Form: Nhập số liệu dạng ma trận (nên chọn) + Graphic Model Form: Nhập số liệu dạng đồ họa GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 427
  26. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) + Symmetric Arc Coeficients: Nếu chọn thì Giá trị (Khoảng cách/Chi phí/Thời gian) đi và về trên các tuyến đường là như nhau (đường 2 chiều/không phải đường 1 chiều). - Problem Title: Nhập tên Bài toán - Number of Nodes: Nhập số nút ® Click nút OK. Bước 3. Bảng nhập số liệu (Khoảng cách/Chi phí/Thời gian từ một nút đến 1 nút) sẽ xuất hiện. - Khi chọn Symmetric Arc Coeficients, ta chỉ cần nhập số liệu cho nửa ma trận phía trên đường chéo. Số liệu còn lại đối xứng qua đường chéo của ma trận sẽ tự động xuất hiện. - Nhập số nào xong ® bấm Enter liền. Bước 4. Chọn menu Solve and Analyze® chọn Solve the Problem® Hộp thoại Select Start and End Notes (Lựa chọn nút đầu và nút cuối) xuất hiện: + Click to select a start note: Nhấn phím chuột để chọn nút đầu; + Click to select an end note:Nhấn phím chuột để chọn nút cuối. ® Bấm nút Solve (Giải bài toán) ® Bảng kết quả cho biết Đường đi ngắn nhất từ nút 1 đến nút 7 là 43 giờ với lộ trình 1-3-4-7 GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 428
  27. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) 4. BÀI TOÁN ĐƯỜNG DÂY MẮC LOA (MINIMAL- SPANNING TREE PROBLEM) 4.1. Định nghĩa Bài toán đường dây mắc loa/Bài toán cây bao trùm tối thiểu (Minimal Spanning Tree Problem/Greedy Problem), là bài toán xác định đường đi nối tất cả các điểm (nút) trên mạng (mặt bằng) lại với nhau sao cho tổng chiều dài (khoảng cách nối liền giữa các nút) là nhỏ nhất. Ví dụ: + Khi các điểm (nút) là vị trí các hố ga thoát nước, thuật toán này được dùng để tìm ra cách bố trí hệ thống đường ống cống thoát nước sao cho tiết kiệm đường ống nhất. GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 429
  28. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) + Khi các điểm (nút) là vị trí các trụ đèn chiếu sáng, thuật toán này được dùng để tìm ra cách bố trí hệ thống đường dây dẫn điện sao cho tổng chiều dài đường dây là nhỏ nhất. + Khi các điểm (nút) là nơi lắp đặt điện thoại cố định, thuật toán này được dùng để tìm ra cách bố trí hệ thống đường dây cáp điện thoại của công ty viễn thông sao cho tổng chiều dài đường dây cáp là nhỏ nhất. Một số ứng dụng của bài toán đường dây mắc loa liên quan đến tiêu chuẩn thời gian hoặc chi phí thay vì khoảng cách. 4.2. Các bước giải bài toán đường dây mắc loa - Bước 1: Chọn một nút bất kỳ trong mạng. - Bước 2: Nối liền nút đã chọn với một nút liền kề gần nhất sao cho tổng khoảng cách giữa các nút là nhỏ nhất. Hai nút này được gọi là nút đã được kết nối (connected nodes), và các nút còn lại được gọi là các nút chưa được kết nối (unconnected nodes). - Bước 3: Xem xét tất cả các nút đã được nối liền, tìm và nối những nút này với một nút liền kề gần nhất chưa kết nối. Chú ý: Nếu như có 2 nút liền kề có khoảng cách như nhau đến các nút đã được nối liền, chúng ta có thể tùy ý chọn một nút bất kỳ để nối liền. Khi này, bài toán có thể có nhiều hơn một lời giải tối ưu. - Bước 4: Lặp lại bước 3 cho đến khi tất cả các nút đã được nối liền. Chú ý: Nếu mạng gồm n nút thì bài toán cây bao trùm phải có n-1 cung. 4.3. Ví dụ minh họa Công ty xây dựng An Bình đang triển khai thi công xây dựng một dự án khu căn hộ cao cấp ở thành phố Nha Trang. Ông Bình, giám đốc kỹ thuật của công ty, đang muốn xác định hệ thống đường ống ngắn nhất nối liền các căn hộ nằm rải rác trong khu vực sao cho chi phí xây dựng hệ thống đường ống thoát nước của khu căn hộ cao GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 430
  29. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) cấp là ít nhất. Cho biết mạng lưới thể hiện khoảng cách (đơn vị 100 m) của 8 căn hộ trong dự án được thể hiện ở hình 5.8 sau: Hình 5.8. Sơ đồ mạng lưới tìm hệ thống đường ống thoát nước ngắn nhất Giải: Chúng ta bắt đầu giải bài toán bằng cách chọn một nút bất kỳ trong mạng, giả sử là nút 1. Bởi vì nút 3 gần với nút 1 nhất với khoảng cách là 2 (100 m), chúng ta nối liền nút 1 và nút 3 như trong hình 5.9. GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 431
  30. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) Hình 5.9. Vòng lặp thứ nhất tìm hệ thống đường ống thoát nước ngắn nhất Xem xét các nút đã được nối liền lúc này là nút 1 và nút 3, chúng ta tiếp tục tìm nút gần nút 1 và nút 3 nhất. Nút được chọn là nút 4 nằm gần nút 3 nhất với khoảng cách là 2 (100m). Chúng ta nối liền các nút đã chọn với nhau như hình 5.10. GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 432
  31. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) Hình 5.10. Vòng lặp thứ hai tìm hệ thống đường ống thoát nước ngắn nhất Tương tự, chúng ta tiếp tục tìm nút chưa được kết nối nằm gần nút 1, nút 3 và nút 4 nhất. Nút được chọn là nút 2 hoặc nút 6 với cùng khoảng cách đến nút là 3 (100m). Chọn nút 2 và nối liền nút 2 và nút 3 như hình 5.11. Hình 5.11. Vòng lặp thứ ba tìm hệ thống đường ống thoát nước ngắn nhất Tương tự, chúng ta tiếp tục tìm nút chưa được kết nối nằm gần nút 1, nút 2, nút 3 và nút 4 nhất. Chúng ta lại có 2 nút liền kề có khoảng cách như nhau ngắn nhất đến các nút đã được nối liền là 3 (100m). Đó là từ nút 2 đến nút 5 và nút 3 đến nút 6. Lưu ý rằng khoảng cách giữa nút 1 và nút 2 cúng là 3 (100m).nhưng chúng ta không kể đến bởi vì cả hai nút này (nút 1 và nút 2) đã được nối liền. Chúng ta chọn tùy ý nút 5 và nối liền nút 2 với nút 5 như hình 5.12. GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 433
  32. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) Hình 5.12. Vòng lặp thứ tư tìm hệ thống đường ống thoát nước ngắn nhất Nút liền kề gần nhất với các nút đã được nối liền là nút 6, chúng ta nối liền nút 3 với nút 6 như hình 5.13. Hình 5.13. Vòng lặp thứ năm tìm hệ thống đường ống thoát nước ngắn nhất GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 434
  33. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) Sau 5 vòng lặp, đến thời điểm hiện nay, chúng ta chỉ còn 2 nút chưa được kết nối là nút 7 và nút 8. Chúng ta nối liền nút 8 với nút 6 vì nút 8 gần nút 6 nhất với khoảng cách là 1 (100m) như hình 5.14. Hình 5.14. Vòng lặp thứ sáu tìm hệ thống đường ống thoát nước ngắn nhất Sau đó nối liền nút 7 còn lại cuối cùng với nút 8 như trong hình 5.15. GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 435
  34. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) Hình 5.14. Vòng lặp thứ bảy tìm hệ thống đường ống thoát nước ngắn nhất Như vậy, lời giải của bài toán được thể hiện ở vòng lặp thứ bảy (vòng lặp cuối cùng). Khi đó, tất cả các nút trong mạng đã được nối liền với nhau với tổng chiều dài ngắn nhất là = 2 + 2 + 3 + 3 + 3 + 1 + 2 = 16 (100m). 4.4. Sử dụng các phần mềm để giải Bài toán đường dây mắc loa (Minimal Spanning Tree Problem) 4.4.1. Phần mềm QM Bước 1. - Menu Module® chọn Networks: - Menu File-New- chọn 2. Shortest Route (Bài toán tìm đường đi ngắn nhất): GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 436
  35. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) - Hộp thoại Creat data set for Networks/ Shortest Route (Nhập dữ liệu cho Bài toán Tìm đường đi ngắn nhất) xuất hiện: - Title: Nhập tên Bài toán - Number of Branches: Nhập số đường đi (bằng cách kéo mouse sang phải) - Row names: chọn kiểu tên cho cung (đường đi) Bước 2. Bảng nhập số liệu (Khoảng cách/Chi phí/Thời gian từ một nút đến một nút) sẽ xuất hiện. GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 437
  36. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) - Khai báo thông số của đường đi: + Start node: nút đầu + End node: nút cuối + Cost: Giá trị khoảng cách/thời gian/chi phí Bước 3. Bấm chọn (Giải bài toán) ® Bảng kết quả cho biết tổng chiều dài ngắn nhất là 16 (100m) nối liền các nút 1, 2, 3, 4, 5, 6, 7 và 8. GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 438
  37. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) 4.4.2. Phần mềm WinQSB Bước 1. Double Click vào biểu tượng NET (Network Modeling) Bước 2. Menu File® chọn New Problem® Hộp thoại NET Problem Specification xuất hiện: - Problem Type: chọn Minimal Spanning Tree (Bài toán Đường dây mắc loa) - Objective Criterion: chọn Minimization (Cực tiểu hàm mục tiêu, mặc định đối với bài toán Đường dây mắc loa) - Data Entry Format: GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 439
  38. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) + Spreadsheet Matrix Form: Nhập số liệu dạng ma trận (nên chọn) + Graphic Model Form: Nhập số liệu dạng đồ họa + Symmetric Arc Coeficients: Nếu chọn thì Giá trị (Khoảng cách/Chi phí/Thời gian) đi và về trên các tuyến đường là như nhau (đường 2 chiều/không phải đường 1 chiều). - Problem Title: Nhập tên Bài toán - Number of Nodes: Nhập số nút ® Click nút OK. Bước 3. Bảng nhập số liệu (Khoảng cách/Chi phí/Thời gian từ 1 nút đến 1 nút) sẽ xuất hiện. - Khi chọn Symmetric Arc Coeficients, ta chỉ cần nhập số liệu cho nửa ma trận phía trên đường chéo. Số liệu còn lại đối xứng qua đường chéo của ma trận sẽ tự động xuất hiện. - Nhập số nào xong ® bấm Enter liền. Bước 4. Menu Solve and Analyze® chọn Solve the Problem® Bảng kết quả cho biết tổng chiều dài ngắn nhất là 16 (100m) nối liền các nút 1, 2, 3, 4, 5, 6, 7 và 8. GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 440
  39. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) 5. BÀI TOÁN CỰC ĐẠI LƯU LƯỢNG (MAXIMAL FLOW PROBLEM) 5.1. Định nghĩa Bài toán cực đại lưu lượng (Maximal Flow Problem) 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 trên một mạng lưới đường trong một khoảng thời gian quy định. Ví dụ: Xác định số lượng xe cộ (xe gắn máy, xe ô tô, xe tải ) có thể lưu thông trên một mạng lưới đường giao thông từ một địa điểm đến một địa điểm. 5.2. Các bước để giải bài toán cực đại lưu lượng - Bước 1: Chọn một tuyến đường bất kỳ đi từ nút nguồn (nút xuất phát) đến nút đích (nút cuối cùng). Nếu không có tuyến đường nào tồn tại lưu lượng thì lời giải tối ưu đã được tìm thấy. - Bước 2: Tìm đoạn đường trên tuyến đường này (đã chọn ở bước 1) có khả năng lưu thông nhỏ nhất C (Capacity). C chính là lưu lượng cực đại (khả năng lưu thông tối đa) trên tuyến đường đó. - Bước 3: Đối với mỗi nút trên tuyến đường này, trừ (giảm) khả năng lưu thông cùng chiều một lượng C và cộng (tăng) khả năng lưu thông ngược chiều một lượng C. - Bước 4: Lặp lại các bước này cho đến khi sử dụng hết lưu lượng (khả năng lưu thông) trên tất cả các tuyến đường đi từ nút nguồn (nút xuất phát) đến nút đích (nút cuối cùng). 5.3. Ví dụ minh họa Để thiết lập dự án xây dựng và 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 Phương Nam cần xác định số lượng xe máy tối đa có thể lưu thông trên các tuyến đường chính từ phía Tây sang phía Đông của thành phố. Cho GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 441
  40. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) biết sơ đồ mạng lưới đường và số lượng xe máy (100 chiếc/giờ) được thể hiện ở hình 5.15. Hình 5.15. Hệ thống mạng lưới đường và khả năng lưu thông trên từng tuyến đường của thành phố Viễn Đông Các đoạn đường được thể hiện bằng nút đầu và nút cuối. Các con số ghi cạnh các nút trên mỗi đoạn đường thể hiện khả năng lưu thông (số lượng xe máy, đơn vị 100 chiếc/giờ) trên đoạn đường đó. Tổng quát, con số được ghi ở cạnh nút thứ i thể hiện khả năng lưu thông theo hướng xuất phát từ nút i. Ví dụ: + Xét đoạn đường đi từ nút 1 đến nút 3: Con số 10 cạnh nút 1 thể hiện khả năng lưu thông đi từ nút 1 đến nút 3 là 10 (tức là 1000 chiếc xe máy/giờ); con số 0 cạnh nút 3 cho thấy không thể lưu thông từ nút 3 về nút 1, nghĩa là đoạn đường 1-3 là đoạn đường 1 chiều từ nút 1 đến nút 3. + Xét đoạn đường đi từ nút 1 đến nút 2: Con số 3 cạnh nút 1 thể hiện khả năng lưu thông đi từ nút 1 đến nút 2 là 3 (tức là 300 chiếc xe máy/giờ). Các con số 1, 1, và 2 cạnh nút 2 thể hiện khả năng lưu thông đi từ nút 2 đến nút 1, nút 4 và nút 6 lần lượt là 1 GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 442
  41. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) (tức là 100 chiếc xe máy/giờ), 1 (tức là 100 chiếc xe máy/giờ) và 2 (tức là 200 chiếc xe máy/giờ). Chúng ta bắt đầu giải bài toán bằng cách chọn một tuyến đường bất kỳ đi từ phía Tây (nút 1) sang phía Đông (nút 6) là tuyến đường 1- 2-6 (tuyến nằm trên cùng của mạng lưới đường). Khả năng lưu thông tối đa của tuyến đường này từ phía Tây (nút 1) sang phía Đông (nút 6) là bao nhiêu? Câu trả lời là 2 (100 chiếc/giờ) vì khả năng lưu thông trên đoạn đường 2-6 chỉ là 2 (100 chiếc/giờ). Vậy khả năng lưu thông trên một tuyến đường là giá trị thể hiện khả năng lưu thông nhỏ nhất của một đoạn nằm trên tuyến đường đó. Khi đã tận dụng khả năng lưu thông của tuyến đường là 2 (100 chiếc/giờ) thì khả năng lưu thông còn lại của các đoạn đường của tuyến đường 1-2-6 sẽ bằng khả năng lưu thông ban đầu trừ đi 2 (100 chiếc/giờ) đối với các đoạn đường cùng chiều (từ Tây sang Đông) và cộng thêm 2 (100 chiếc/giờ) đối với các đoạn đường ngược chiều (từ Đông sang Tây). Như vậy khả năng lưu thông trên đoạn đường 1-2 còn 1 2 (100 chiếc/giờ), khả năng lưu thông trên đoạn 2-6 bằng 0. Kết quả tính toán được thể hiện như trong hình 5.16. GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 443
  42. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) Hình 5.16. Vòng lặp thứ nhất xác định khả năng lưu thông tối đa trên tuyến đường 1-2-6 của thành phố Viễn Đông Bây giờ chúng ta lặp lại quá trình bằng cách chọn một tuyến đường bất kỳ khác đi từ nút 1 đến nút 6 để xem xét khả năng lưu thông còn lại. Tuyến đường được chọn là tuyến 1-2-4-6. Ta có khả năng lưu thông của đoạn đường 1-2 trên tuyến đường này còn lại 1 (100 chiếc/giờ) và khả năng lưu thông trên đoạn 2-4 và 4-6 cũng là 1 (100 chiếc/giờ). Vì vậy khả năng lưu thông tối đa của tuyến đường này từ phía Tây (nút 1) sang phía Đông (nút 6) là 1 (100 chiếc/giờ). Lưu ý rằng khả năng lưu thông trên đoạn đường 1-2 chỉ là 1 (100 chiếc/giờ) bởi vì đã có 2 (100 chiếc/giờ) được lưu thông trong mạng lưới đường giao thông. Chúng ta cũng lấy giá trị khả năng lưu thông ban đầu trừ đi 1 (100 chiếc/giờ) đối với các đoạn đường cùng chiều (từ Tây sang Đông) và cộng thêm 1 (100 chiếc/giờ) đối với các đoạn GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 444
  43. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) đường ngược chiều (từ Đông sang Tây). Kết quả tính toán được thể hiện như trong hình 5.17. Hình 5.17. Vòng lặp thứ hai xác định khả năng lưu thông tối đa trên tuyến đường 1-2-4-6 của thành phố Viễn Đông Như vậy, cho đến thời điểm hiện tại chúng ta đã có lưu lượng là 300 chiếc xe máy/ giờ: 200 chiếc/giờ lưu thông theo tuyến đường 1-2- 6 và 100 chiếc/giờ lưu thông trên tuyến đường 1-2-4-6. GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 445
  44. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) Hình 5.18. Mạng lưới đường giao thông sau vòng lặp thứ hai Chúng ta lặp lại quá trình bằng cách chọn một tuyến đường bất kỳ khác đi từ nút 1 đến nút 6 chưa tận dụng hết khả năng lưu thông. Tuyến đường được chọn là tuyến 1-3-5-6. Ta có khả năng lưu thông tối đa của tuyến đường này từ phía Tây (nút 1) sang phía Đông (nút 6) là 2 (100 chiếc/giờ) bởi vì khả năng lưu thông tối đa trên đoạn đường 3-5 là 2 (100 chiếc/giờ). Chúng ta cũng lấy giá trị khả năng lưu thông ban đầu trừ đi 2 (100 chiếc/giờ) đối với các đoạn đường cùng chiều (từ Tây sang Đông) và cộng thêm 2 (100 chiếc/giờ) đối với các đoạn đường ngược chiều (từ Đông sang Tây). Kết quả tính toán được thể hiện như trong hình 5.18. GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 446
  45. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) Hình 5.19. Vòng lặp thứ ba (cuối cùng) xác định khả năng lưu thông tối đa trên tuyến đường 1-3-5-6 của thành phố Viễn Đông Lúc này tất cả các tuyến đường đi từ nút 1 đến nút 6 đã tận dụng hết khả năng lưu thông mặc dù vẫn còn một số đoạn đường chưa sử dụng hết khả năng lưu thông. Khả năng lưu thông tối đa đi từ nút 1 đến nút 6 là 500 chiếc/giờ bao gồm: + Tuyến đường 1-2-6 là 200 chiếc/giờ; + Tuyến đường 1-2-4-6 là 100 chiếc/giờ; + Tuyến đường 1-3-5-6 là 200 chiếc/giờ. Bảng 5.2. Tóm tắt lời giải của bài toán Tuyến đường Khả năng lưu thông (xe máy/giờ) 1-2-6 200 1-2-4-6 100 1-3-5-6 200 Tổng 500 GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 447
  46. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) 6. ĐÁNH GIÁ KẾT THÚC CHƯƠNG Phần A- Ngân hàng câu hỏi trắc nghiệm: A1- Dạng trắc nghiệm nhiều lựa chọn (Chọn câu đúng nhất) 1. Thuật toán nào sau đây được sử dụng để nối liền tất cả các điểm của một mạng lưới với nhau sao cho tổng khoảng cách nối liền giửa chúng là nhỏ nhất? a. Cực đại lưu lượng b. Cực tiểu lưu lượng c. Đường dây mắc loa d. Tìm đường đi ngắn nhất e. Tìm đường đi dài nhất 2. Bước đầu tiên để giải bài toán đường dây mắc loa là a. Chọn nút có khoảng cách giữa nó và các nút khác lớn nhất b. Chọn nút có khoảng cách giữa nó và các nút khác lớn nhất c. Chọn nút gần nút gốc nhất d. Chọn bất kỳ tuyến đường nào nối liền bởi 2 nút e. Chọn một nút bất kỳ GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 448
  47. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) 3. Bước đầu tiên để giải bài toán cực đại lưu lượng là a. Chọn một nút bất kỳ b. Chọn một tuyến đường bất kỳ đi từ nút nguồn đến nút đích c. Chọn tuyến đường có lưu lượng cực đại d. Chọn tuyến đường có lưu lượng cực tiểu e. Chọn tuyến đường có lưu lượng đi vào mỗi nút lớn hơn lưu lượng đi ra tại nút đó 4. Thuật toán nào trong quy hoạch mạng phải nối một nút liền kề gần nhất chưa kết nối với tất cả các nút đã được nối liền trong lời giải đang có? a. Cực đại cây b. Tìm đường đi ngắn nhất c. Đường dây mắc loa d. Cực đại lưu lượng e. Cực tiểu lưu lượng 5. Điều chỉnh khả năng lưu thông có thể có trên một tuyến đường là một bước quan trọng của bài toán? a. Cực đại lưu lượng b. Cực tiểu lưu lượng c. Cực đại đường dây mắc loa d. Đường dây mắc loa e. Tìm đường đi ngắn nhất 6. Một thành phố lớn đang có dự án nâng cấp đường giao thông để giải quyết vấn đề kẹt xe vào giờ cao điểm. Hàng tuần, ước tính có khoảng 160.000 xe máy lưu thông trên đường từ trung tâm thành phố đi về thị trấn ở hướng Tây cách thành phố khoảng 15 km. Thuật toán nào sau đây sẽ giúp các cho cán bộ hoạch định dự án xác định các tuyến đường nào không đủ khả năng lưu thông khi kẹt xe? a. Đường dây mắc loa GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 449
  48. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) b. Cực đại lưu lượng c. Tìm đường đi ngắn nhất d. Tất cả đều đúng e. Tất cả đều sai 7. Trung tâm tin học trường đại học Mở Tp. HCM muốn lắp đặt đường dây cáp quang mới để phục vụ hệ thống mạng máy tính trong trường. Thuật toán nào sau đây có thể được sử dụng để xác định cách bố trí hệ thống đường dây cáp cho gần 20 Khoa và Phòng ban trong trường sao cho tổng chiều dài đường dây cáp là nhỏ nhất? a. Đường dây mắc loa b. Cực đại lưu lượng c. Tìm đường đi ngắn nhất d. Tất cả đều đúng e. Tất cả đều sai 8. Trong bài toán đường dây mắc loa, lời giải tối ưu được tìm thấy khi a. Nút đầu và nút cuối đã được nối liền bởi một tuyến đường liên tục b. Lưu lượng đi ra từ nút đầu bằng lưu lượng đi vào nút cuối c. Tất cả các đoạn đường được lựa chọn phải là một phần của cây (đường dây mắc loa). d. Tất cả các nút đã được nối liền là một phần của cây (đường dây mắc loa). 9. Thuật toán đường dây mắc loa được sử dụng tốt nhất trong bài toán a. Thiết kế các hành lang giữa các văn phòng của một tòa nhà mới xây dựng bởi một kiến trúc sư. b. Thiết kế mạng lưới đường dây cáp điện thoại trong một ngôi nhà mới bởi công ty viễn thông c. Xác định các tuyến đường bay của hãng hàng không d. Tất cả đều sai e. Tất cả đều đúng GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 450
  49. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) 10. Bảng sau đây cho biết khoảng cách giữa các nút trong một mạng. Tìm khoảng cách ngắn nhất nối liền các nút? Từ Đến Khoảng cách (m) 1 2 200 1 3 300 1 5 400 2 3 300 2 4 400 3 4 200 3 5 200 4 5 100 4 6 300 5 6 400 a. 1000 b. 800 c. 700 d. 1100 e. Tất cả đều sai 11. Bảng sau đây cho biết khoảng cách giữa các nút trong một mạng. Tìm khoảng cách ngắn nhất nối liền các nút? Từ Đến Khoảng cách (m) 1 2 100 1 3 50 2 3 200 2 5 300 1 4 50 3 4 350 3 5 400 3 6 400 GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 451
  50. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) 4 5 450 4 6 350 5 6 200 a. 900 b. 1200 c. 1100 d. 800 e. Tất cả đều sai 12. Thuật toán cực đại lưu lượng có thể dùng để a. Thiết kế các lề đường dành cho hành khách đi bộ từ một nhà ga này đến một nhà ga khác ở sân bay b. Thiết kế hệ thống giao thông tại một sân bay c. Thiết kế các đường giao thông giới hạn khả năng lưu thông qua một khu vực ở sân bay d. Tất cả đều đúng e. Tất cả đều sai. 13. Hệ thống đường ống thoát nước được cho như bảng sau đây. Hãy xác định lưu lượng tối đa từ nút 1 đến nút 4. Từ Đến Lưu lượng 1 3 200 3 1 0 1 2 150 2 1 50 2 3 100 3 2 100 3 4 150 4 3 50 a. 100 GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 452
  51. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) b. 150 c. 200 d. 50 e. Tất cả đều sai. 14. Thuật toán tìm đường đi ngắn nhất có thể được sử dụng để a. Quy hoạch các tuyến đường cho một kỳ nghỉ du lịch bằng xe b. Quy hoạch các tuyến đường cho xe buýt trường học c. Xác định con đường đi cho tài xế xe tải cần vận chuyển hàng gấp d. Tất cả đều đúng e. Tất cả đều sai 15. Thuật toán tìm đường đi ngắn nhất có thể được sử dụng để a. Tìm khoảng cách dài nhất để đi giữa hai điểm. b. Tìm thời gian ngắn nhất để đi giữa hai điểm. c. Tìm tuyến đường có cảnh quan đẹp nhất trong chuyến đi du lịch xuân. d. Nối tất cả các nút của một mạng lưới với nhau sao cho cực tiểu tổng số đường đi. e. Tất cả đều sai 16. Tìm chiều dài đường đi ngắn nhất từ nút 1 đến nút 5. Từ Đến Khoảng cách (m) 1 2 250 1 3 150 1 4 200 2 3 50 2 4 150 3 4 150 3 5 100 2 5 150 a. 200 GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 453
  52. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) b. 350 c. 250 d. 450 e. Tất cả đếu sai 17. Nếu chúng ta muốn đánh giá xem một mạng máy tính có bị quá tải hay không, chúng ta có thể sử dụng thuật toán a. Tìm đường đi ngắn nhất b. Cực đại lưu lượng c. Đường dây mắc loa d. Tất cả đều đúng e. Tất cả đều sai 18. Một mạng nhỏ và đơn giản có thể được giải dựa vào a. Phương pháp đơn hình. b. sự suy đoán c. Các kỹ thuật tính toán nâng cao d. Tất cả đều sai 19. Trong bài toán đường dây mắc loa, nếu có 2 hay nhiều hơn 2 nút liền kề có khoảng cách như nhau đến các nút đã được nối liền, khi đó 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ó ít nhất 3 lời giải tối ưu khác nhau tồn tại. e. Tất cả đều sai A2- Dạng trắc nghiệm đúng hoặc sai 1. Các công ty dịch vụ truyền hình cáp thường sử dụng bài toán tìm đường đi ngắn nhất để bố trí hệ thống đường dây cáp kết nối tất cả các hộ nhà ở cá nhân. 2. Bài toán đường dây mắc loa luôn luôn có một lời giải tối ưu duy nhất. GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 454
  53. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) 3. Tiêu chuẩn dừng của bài toán đường dây mắc loa là lặp lại các bước của thuật toán cho đến khi tất cả các nút đã được nối liền. 4. Trong bài toán cực đại lưu lượng, các đoạn đường đi được thể hiện bởi sự nối liến giữa các nút bằng các đoạn thẳng. 5. Bài toán cực đại lưu lượng có thể được sử dụng bởi các 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 các mối nguy hiểm từ lũ lụt. 6. Bài toán tìm đường đi ngắn nhất có thể được sử dụng để cực tiểu chiều dài di chuyển trong việc lập kế hoạch trong một chuyến đi nghỉ bằng xe. 7. Bài toán cực đại lưu lượng có thể được sử dụng bởi các kỹ sư giao thông để nghiên cứu tác động của chuỗi đèn tín hiệu điều khiển giao thông khác nhau lên hành vi giao thông trong một thành phố. 8. Trong bài toán cực đại lưu lượng, sự lưu thông có thể đi theo cả hai hướng cùng chiều hoặc ngược chiều trong mạng. 9. Các điểm trên một được gọi là các cung. 10. Trong bài toán cực đại lưu lượng, chúng ta cần phải biết khả năng lưu thông đến mỗi nút, chứ không cần biết khả năng lưu thông xuất phát từ nút đó. 11. Trong bài toán tìm đường đi ngắn nhất, mục tiêu là phải tìm được tuyến đường từ một điểm nguồn đến một điểm đích sao cho số lượng các nút đi qua là ít nhất. 12. Khi lời giải tối ưu đã tìm được trong bài toán cực đại lưu lượng, mỗi nút sẽ được kết nối với ít nhất là một nút khác. A3- Dạng trắc nghiệm điền vào chỗ trống 1. Trong khi giải bài toán ___, chúng ta bắt đầu bằng cách chọn một nút bất kỳ trong mạng. a. Cực đại lưu lượng b. Tìm đường đi ngắn nhất GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 455
  54. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. 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 đi dài nhất 2. Công ty dịch vụ truyền hình cáp thường sử dụng thuật toán ___. a. Đường dây mắc loa b. Tìm đường đi 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ả năng lưu thông 3. Thuật toán đường dây mắc toán liên quan đến việc xác định đường đi nối ___ điểm (nút) trên mạng lại với nhau sao cho tổng chiều dài (khoảng cách nối liền giữa các nút) là 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
  55. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) 4. Trong thuật toán___ , các kết quả trung gian cũng 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 đi ngắn nhất e. Tìm đường đi dài nhất 5. Trong ba bài toán (tìm đường đi ngắn nhất, đường dây mắc loa và cực đại lưu lượng), chỉ có bài toán ___ là có một lời giải duy nhất. a. Đường dây mắc loa b. Tìm đường đi ngắn nhất c. Cực đại lưu lượng d. Tất cả đều đúng e. Tất cả đều sai 6. Bước đầu tiên trong thuật toán tìm đường đi ngắn nhất là ___. a. Chọn một con đườ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 con đường có khả năng lưu thông nhỏ nhất. e. Nối liền tất cả các nút chưa được kết nối. 7. Trong bài toán cực đại lưu lượng, việc lưu thông có thể đi___. a. Chỉ theo hướng ngược dòng b. Chỉ theo hướng xuôi dòng c. Một cách bất kỳ bất kể hướng nào GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 457
  56. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) d. Hướng đường chéo e. Theo cả hai hướng ngược dòng và xuôi dòng 8. Trong bài toán tìm đường đi ngắn nhất, giá trị khoảng cách được ghi trong hộp cạnh mỗi node thể hiện con đường ___ đi đến nút này. a. Ngắn nhất b. Dài nhất c. Dài trung bình d. Tất cả đều đúng e. tất cả đều sai 9. Trong ba bài toán (tìm đường đi ngắn nhất, đường dây mắc loa và cực đại lưu lượng), chỉ có bài toán ___ là có thể lưu thông theo cả 2 hướng của một con đường. a. Tìm đường đi ngắn nhất b. Đường dây mắc loa c. Cực đại lưu lượng d. Tất cả đều đúng e. Tất cả đều sai 10. Tiêu chuẩn dừng của bài toán cực đại lưu lượng là lặp lại cá bước của thuật toán cho đến khi không còn ___ trong ___. a. Giảm, các nút b. Giảm, các khoảng cách c. Tăng, các cung d. Tăng, lưu lượng e. Tăng, các con đường 11. Mạng bao gồm ___ và ___ . a. các cung, các nút GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 458
  57. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) b. Các phần tử, các con đường c. Các cung, các đường thẳng d. Đường tròn, đường cong bậc ba e. Các nút, các module 12. ___ là bài 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 điểm này đến một địa điểm khác trên hệ thống nhiều đường giao thông có sẵn sao cho tổng chiều dài đường đi là ngắn nhất. a. Đường dây mắc loa b. Cực đại lưu lượng c. Tìm đường đi ngắn nhất d. Tất cả đều đúng e. Tất cả đều sai 13. Bài toá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 trên một mạng lưới đường trong một khoảng thời gian quy định được gọi là bài toán___. a. Đường dây mắc loa b. Cực đại lưu lượng c. Tìm đường đi ngắn nhất d. Tất cả đều đúng e. Tất cả đều sai 14. ___ là bài toán xác định đường đi nối tất cả các điểm (nút) trên mạng lại với nhau sao cho tổng chiều dài (khoảng cách nối liền giữa các nút) là nhỏ nhất. a. Đường dây mắc loa b. Cực đại lưu lượng c. Tìm đường đi ngắn nhất d. Tất cả đều đúng e. Tất cả đều sai GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 459
  58. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) 15. Nếu bạn muốn vẽ sơ đồ bố trí các văn phòng trong một tòa nhà lớn, thuật toá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 đi ngắn nhất d. Tất cả đều đúng e. Tất cả đều sai 16. Trong thuật toán___, chúng ta phải lặp lại bước điều chỉnh khả năng lưu thông trên các con đường. a. Tìm đường đi ngắn nhất b. Cực đại lưu lượng c. Đường dây mắc loa d. Tất cả đều đúng 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ả năng xảy ra lũ lụt nhờ dùng thuật toán___. a. Cực đại lưu lượng b. Tìm đường đi ngắn nhất c. Đường dây mắc loa d. Tất cả đều đúng e. Tất cả đều sai A4- Dạng trắc nghiệm liên kết 2 mệnh đề phù hợp 1.1 Đường dây mắc loa a. Các đường trong 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 đi ngắn nhất c. Các điểm trong 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ả năng lưu thông tối đa của GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 460
  59. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) xe cộ trong 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 điệ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 đi ngắn nhất GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 461
  60. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) B- Ngân hàng câu hỏi tự luận: 1. Nêu tên 3 mô hình quy hoạch mạng thường được sử dụng để tìm lời giải tối ưu cho các bài toán khác nhau. 2. Mô tả bài toán đường dây mắc loa. 3. Mô tả bài toán cực đại lưu lượng. 4. Trình bày các thành phần cấu tạo nên mạng. 5. Trình bày giải thuật tiến cho bài toán Tìm đường đi ngắn nhất 6. Trình bày các bước để giải bài toán cực đại lưu lượng. 7. Trình bày các bước giải bài toán đường dây mắc loa. 8. Trình bày cách thức xác định các lời giải tối ưu khác khi sử dụng thuật toán đường dây mắc loa. 9. Trình bày cách thức xác định các lời giải tối ưu khác khi sử dụng thuật toán tìm đường đi ngắn nhất. 10. Mô tả lý do tại sao trong bài toán cực đại lưu lượng chỉ có duy nhất một lời giải. C- Ngân hàng bài tập & tình huống thảo luận: 1. 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 các 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 hãy giúp ông Nam, giám đốc công ty tìm đường đi 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 như trong hình sau đây (với chiều dài tuyến đường tính theo đơn vị km). GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 462
  61. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) Hình. Sơ đồ các tuyến đường giao thông từ nhà máy đến nhà kho 2. Công ty Stagecoach Shipping cần phải vận chuyển cam bằng 6 xe tải từ thành phố Los Angeles đến nơi tiêu thụ tại 6 thành phố khác ở phía Tây và Trung Tây của nước Mỹ. Cho biết khoảng cách và thời gian (tính bằng giờ) đối với 1 xe tải di chuyển từ thành phố Los Angeles đến các thành phố khác được thể hiện ở hình vẽ sau. Hình. Hệ thống đường giao thông từ Los Angeles đến các thành phố GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 463
  62. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) Bạn hãy giúp giám đốc công ty muốn xác định đường đi ngắn nhất (nghĩa là phải tối thiểu thời gian vận chuyển cam) của các xe tải từ điểm nguồn (thành phố Los Angeles) đến các nơi thụ. 3. Công ty xây dựng An Bình Công ty xây dựng An Bình đang triển khai thi công xây dựng một dự án khu căn hộ cao cấp ở thành phố Nha Trang. Ông Bình, giám đốc kỹ thuật của công ty, đang muốn xác định hệ thống đường ống ngắn nhất nối liền các căn hộ nằm rải rác trong khu vực sao cho chi phí xây dựng hệ thống đường ống thoát nước của khu căn hộ cao cấp là ít nhất. Cho biết mạng lưới thể hiện khoảng cách (đơn vị 100m) của 8 căn hộ trong 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 4. Để thiết lập dự án xây dựng và 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 trên các tuyến đường chính từ phía Tây sang phía Đông của thành phố. Cho biết sơ đồ mạng lưới đường và 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
  63. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) Hình/. Hệ thống mạng lưới đường và khả năng lưu thông trên từng tuyến đường của thành phố Viễn Đông Bạn hãy 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 trên các tuyến đường chính từ phía Tây sang phía Đông. GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 465
  64. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) 7. 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 trong 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 bài toán tối ưu trong 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 trong quản lý và vận hành, Nhà xuất bản Khoa học và 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, 8th 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 GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 466
  65. Generated by Foxit PDF Creator © Foxit Software For evaluation only. Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING) hill.com/sites/0073129038/information_center_view0/ GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 467