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 - Đỗ Thi Xuân Lan

17 trang hapham 1500

Download

Bạn đang xem tài liệu "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 - Đỗ Thi Xuân Lan", để 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:

bai_giang_tin_hoc_trong_quan_ly_xay_dung_chuong_7_mo_hinh_ma.pdf

Nội dung text: 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 - Đỗ Thi Xuân Lan

Chương 7Mô hì nh mạng l ưới đường
Chương 7 Mô hình mạng lưới đờđường • Bài toán tìm đường điing ngắnnnh nhất - Phương pháp thế vị • Bài toán đườnggy dây loa • Bài toán tìm luồng cực đại ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Chương 7Mô 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Ị ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Bài toán tìm đường đi ngắn nhất • Ví dụ 7.1. Mỗi nggyày côn gyg 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ươiCi 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 nhấ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ếptp 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ínhlàkhochính là khoảng cách ngắnnnh nhấttt 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 E2 = 10 E4 = 30 20 2 4 E1 = 0 10 10 10 15 1 5 6 10 20 3 4 5 E6 = 29 Ej = min{Ei + lij } E3 = 15 E5 = 19 Vậy đường đi ngắn nhất là 29 (100m) theo lộ trình 1-2-3-5-6 ©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ựng hệ thống đờđường ống thoát nước của khu nhà là rẻ nhất. Khoảng cách giữa các ngôi nhà (100m) đượctrìnhc 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áútXem xét các nút đã được nốiili 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 •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 3 2 5 3 4 5 1 3 7 2 7 2 3 5 3 8 2 1 4 6 6 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) ©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ộtdt 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 của thàn h p hố. Sơ đồ mạng lưới đờđườ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ọnmn mộttuyt tuyến đường bấtkt kỳ điti từ nút xuất phát đến nút cuối • Tậndn dụng tối đala lưulu 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ếtlt lưulu lượng trên tấtct 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 Giá trị nhỏ nhất 2 1 2 3 2 1 6 Khả năng lưu thông còn lại = 3-2 0 1 2 1 2 1 6 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.