Bài giảng Tin học trong quản lý xây dựng - Chương 7: Mô hình mạng lưới đường

Ch 7Mô hì hương n mạng lưới đường Chương 7 Mô hình mạng l ới đ ờư ư ng • Bài toán tìm đường đi ngắn nhất - Phương pháp thế vị • Bài toán đường dây loa • Bài toán tìm luồng cực đại ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN Chương 7 Mô hình mạng lưới đường NHẤT ‐ PHƯƠNG PHÁP THẾ VỊ ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. Bài toán tìm đường đi ngắn hấn t • Ví dụ 7.1. Mỗi ngày công ty xây dựng Vĩnh Thạnh cần phải vận chuyển vữa bê tông từ nhà máy sản xuất bê tông tươi Cửu Long đến các công trường xây dựng nằm rải rác trong thành phố. Hãy tìm đường đi ngắn nhất từ nhà máy sản xuất (nút 1) đến công trường xây dựng cao ốc văn phòng Vĩnh Cửu (nút 6). Sơ đồ mạng lưới đường giao thông như trong hình 7.1 với chiều dài các tuyến đường có đơn vị 100m. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. Bài toán tìm đường đi ngắn hấn t Các bước để giải bài toán: • Tìm nút gần nút xuất phát nhất, ghi giá trị khoảng cách đến nút này từ nút xuất phát • Tiếp tục tìm nút tiếp theo gần nút xuất phát nhất, ghi khoảng cách ngắn nhất đến nút này từ nút xuất phát, giá trị này gọi là thế vị của nút. • Tiếp tục lập lại quá trình xác định thế vị của các nút/ 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. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. Bài toán tìm đường đi ắ ấng n nh t 20 E2 = 10 E4 = 30 1010 2 4 E1 = 0 15 5 10 1  10 6 20 4 3 5 E = min{E + l } E6 = 29 E3 = 15 j    i   ij E5 = 19 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. Vậy đường đi ngắn nhất là 29 (100m) theo lộ trình 1-2-3-5-6 BÀI TOÁN ĐƯỜNG DÂY LOA Chương 7 Mô hình mạng lưới đường ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. Bài toán đường dây loa • Ví dụ 7.2. Công ty xây dựng Coxadu đang xây dựng một khu nhà ở cao cấp ở thành phố. Tìm hệ thống đường ống ngắn nhất nối liền các ngôi nhà nằm rải rác trong khu vực để cho chi phí xây d hệ thố đ ờ ố th át ớựng ng ư ng ng o nư c của khu nhà là rẻ nhất. Khoảng cách giữa các ngôi nhà (100m) được trình bày như trong hình. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. Bài toán đường dây loa Các bước để giải bài toán: • Chọn một nút bất kỳ • Nối liền nút đã chọn với một nút liền kề sao cho tổng khoảng cách nối liền giữa các nút là nhỏ nhất. X ét á út đã đ ối liề tì à• em x c c n ược n n, m v nối những nút này với một nút liền kề gần nhất • Lập lại bước 3 cho đến khi tất cả các nút đã được nối liền ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. Bài toán đường dây loa 2 5 3 4 3  3 5  1 7 2 7 2  3 1 5  3  2 8 64 6 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. Vậy các nút đã được nối liền với tổng chiều dài ngắn nhất là 16 (100m) BÀI TOÁN TÌM LUỒNG CỰC ĐẠI Chương 7 Mô hình mạng lưới đường ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. Bài toán tìm luồng cực đại Ví dụ 7.3. Để xây dựng một dự án phát triển thành phố Hoa Hồng, công ty tư vấn thiết kế ABC cần xác định khối lượng xe máy tối đa có thể lưu thông trên đường từ phía tây sang phía đông ủ thà h hố S đồ l ới đ ờc a n p . ơ mạng ư ư ng và số lượng xe (100 chiếc/giờ) có thể lưu thông trên các tuyến đường được trình bày như trong hình. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. Bài toán tìm luồng cực đại Các bước để giải bài toán: • Chọn một tuyến đường bất kỳ đi từ nút xuất phát đến nút cuối • Tận dụng tối đa lưu lượng (khả năng lưu thông) trên tuyến đường đó • Xác định lưu lượng còn lại trên từng đoạn đường • Lập lại quá trình tính toán cho đến khi sử dụng hết lưu lượng trên tất cả tuyến đường đi từ nút xuất phát đến nút cuối cùng của mạng lưới đường ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. Bài toán tìm luồng cực đại 1 2 2 23 1 1 1  1 2 6 0 1 10 0  4 1   6   3 1 0  523 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. Bài toán tìm luồng cực đại Giá trị nhỏ nhất   2 3 1 2 2 1   6  21 0 Khả năng lưu thông còn lại = 3-2 1   6 1 2 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. Bài toán tìm luồng cực đại   2 1 4 1  6 1 1 1 1 1   2  0 1 0 4   1  6  1 0 1 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. Bài toán tìm luồng cực đại   1  10 6  5 0 1 6 0 3 2   1  6 8 3 50 1 0 0 4 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.