QUY HOẠCH MẠNG

QUY HOẠCH MẠNG

Nguyễn Như Phong

Kỹ thuật Hệ thống Công nghiệp

Đại học Bách Khoa TPHCM

a. Mô hình mạng

Một mạng là một tập hợp các nút liên kết nhau bởi các cung. Một mạng (N,A) bao gồm tập các nút N và tập các cung A. Chẳng hạn như mạng sau bao gồm 5 nút và 8 cung

N = {1,2,3,4,5}

A = {(1,2), (1, 3), (2, 3), (2,5), (3,4), (3, 5), (4,2), (4, 5)}

Hình 6.1 Mô hình mạng

Các mạng thường dùng để mô hình hóa các hệ thống như mạng giao thông, mạng phân phối dầu. Một khái niệm liên kết với một mạng là dòng, mô hình dòng chảy trong mạng, chẳng hạn như dòng chảy của dầu trong mạng phân phối dầu hay dòng xe trong một mạng giao thông. Các dòng trong một mạng bị giới hạn bởi năng lực của cung tương ứng, chẳng hạn như giới hạn lưu lượng dầu do thiết diện đường ống dẫn hay giới hạn lưu lượng xe ở các cung đường của hệ thống giao thông.

Một cung có thể có định hướng hay không, cung định hướng là cung chỉ cho dòng chảy theo một chiều xác định và không cho dòng chảy theo chiều ngược lại. Cung không định hướng là cung cho dòng chảy theo cả hai chiều. Mạng các cung định hướng là mạng định hướng, mạng các cung không định hướng là mạng không định hướng.

Một đường của 1 mạng là một chuỗi các cung nối 2 nút của mạng qua các nút khác. Một đường của 1 mạng tạo thành 1 vòng của mạng khi nó nối một nút với chính nó qua nhiều nút trung gian khác của mạng.

Một mạng được xem là mạng liên kết khi 2 nút khác nhau bất kỳ của mạng liên kết nhau bởi ít nhất 1 đường.

Một nhánh của một mạng là một mạng liên kết một số nút của mạng mà không có vòng trên nhánh. Nếu một nhánh của một mạng liên kết tất cá các nút của mạng mà không có vòng trên nhánh thì được gọi là cây của mạng.

a. Ứng dụng mô hình mạng

Mô hình mạng thường được sử dụng để giải quyết các bài toán thực tế như:

Bài toán xác định đường đi ngắn nhất liên kết các vị trí khác nhau, như các thành phố, các điểm giao hàng, ...
Bài toán xác định mạng cáp liên kết các điểm truyền hình với lượng cáp nhỏ nhất.
Bài toán xác định đường đi ngắn nhất giữa hai thành phố.
Bài toán xác định chính sách thay thế thiết bị.
Bài toán xác định lưu lượng cực đại trên một hệ thống ống dẫn lưu chất với các ràng buộc về năng lực hệ thống.
Bài toán xác định số lượng phương tiện vận chuyển tối ưu thỏa lịch vận chuyển xác định.
Bài toán cực tiểu chi phí với các yêu cầu về lưu lượng cung và cầu trên một hệ thống ống dẫn lưu chất.
Bài toán điều độ dự án, …

Các mô hình mạng sử dụng giải quyết các bài toán trên bao gồm: