Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING)
GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 403
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
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.
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING)
GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 405
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.
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING)
GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 406
Ví dụ: Tuyến OT, đường đi từ O sang T có thể đi qua các cung OB -
BD - DT (O
→
B
→
D
→
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING)
GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 407

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

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.
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING)
GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 409
-
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 đã

+ c
ij
: 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:
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING)
GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 410
Gọi
0
x
1
ij
nếu không có đường nối từ nút i
đến nút j

nếu có đường nối từ nút i đến nút j

=



x
ij
= 1 (nếu ij được chọn là đường đi ngắn nhất)
Hàm mục tiêu: Min
ij ij

ij
ngun
Chú ý rằng bài tốn đường đi ngắn nhất là trường hợp đặc biệt
của bài tốn cực tiểu chi phí trên mạng lưu thơng. Từ đó ta sẽ xét tố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 x
ij
= 0 hay 1 bằng
ij
x 0
≥
. Khi đó bài
tốn trở thành:
Hàm mục tiêu: Min
ij ij
i j
c *x
∑∑

Ràng buộc:
•
ij ki
j k
1
x x 0 2,m 1
1
nếu i = 1
nếu i =
nếu i = m


u min u d
= +

Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING)
GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 411
Trong đó:
+ u
j
= Khoảng cách ngắn nhất từ nút 1 đến nút j với u
1
= 0;
+ u
i
= Khoảng cách ngắn nhất từ nút 1 đến nút i
+ d
ij
= Khoảng cách giữa nút j và nút i trước nó
Lưu ý: u
j
chỉ được tính sau khi ui đã được tính.
Nhãn của nút j là [u
j
, n] với n là nút j tạo ra khoảng cách ngắn
nhất:
{
}
ij
j i

+ 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à: [u
j
, i] = [ u
i
+ d
ij
, i] với d
ij

≥
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.
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING)
GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 412
Ký hiệu nhãn tạm thời: [u
j
, i] hay (u
j
, 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: [u

, 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 u
j
+ d
ij
nhỏ nhất sẽ là nút được gắn nhãn cố
định [u
j
+ d
ij
, i].
+ Nếu nút j đã được gắn 1 nhãn tạm thời (u
j
, k) đến từ 1 nút k nào
đó, và nếu khoảng cách đến từ nút i là u
i
+ d
ij
< u
j
(khoảng cách
đến từ nút k), chúng ta thay thế nhãn tạm thời (u
j
, k) bằng (u
i
+
d
ij

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).
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING)
GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 414

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. Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING)
GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 415


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.

Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING)
GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 418
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

n
Tập nút
đã khảo sát
nối trực tiếp với
nút chưa khảo sát

Nút
chưa
khảo
sát
Tuyến

3
1-2
1-3
100
200
100

Nút 2

1-2

2

{
}
1,21
2
2
2
3
3
4
5
1-3
2-3
2-4
2-5

150+40=190 190 Nút 5 3-5

{
}
1,2,3,54
2
5
5
4
4
6
2-4
5-4
5-6
300

190+150=3401
90+100=290

(200, 1)
[0, -]
(200, 1)
[100, 1]
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING)
GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 420
Hình 5.9a. Vòng lặp thứ hai
[0, -]
(150, 2)
[100, 1]
(300, 2)
(200, 2)
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING)
GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 421

Hình 5.9b. Vòng lặp thứ hai


(300, 2)
[150, 2] [190, 3]
[290, 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)
GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 423
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ụ.
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING)
GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 424
3.8.1.
Phần mềm QM
Bước 1.
-
Menu Module

-
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:
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
Chương 5. QUY HOẠCH MẠNG (NETWORKS PROGRAMMING)
GV. ThS. Nguyễn Thanh Phong- Trường Đại học Mở Tp. HCM 427 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
→