Bài giảng Khoa học quản lý ứng dụng: Chương 5 - ThS. Huỳnh Đỗ Bảo Châu

2/12/2017

TRƯỜNG ĐẠI HỌC NGÂN HÀNG TP
.HCM
KHOA HỆ THỐNG THÔNG TIN QUẢN LÝ

KHOA HỌC QUẢN LÝ ỨNG DỤNG

CHƯƠNG 5
KỸ THUẬT MẠNG TRONG QUẢN LÝ

Nội dung chính
PHẦN 1: KỸ THUẬT MẠNG
1. Giới thiệu về kỹ thuật mạng
2. Bài toán tìm đường ngắn nhất
3. Giải bài toán tìm đường ngắn nhất bằng Excel
4. Bài toán cây bao trùm tối thiểu
5. Bài toán luồng cực đại
6. Giải bài toán tìm luồng cực đại bằng Excel

GV. ThS. Huỳnh Đỗ Bảo Châu

1

2

GV. Huỳnh Đỗ Bảo Châu

Nội dung chính
PHẦN 2: KỸ THUẬT MẠNG TRONG QUẢN LÝ DỰ ÁN
7. Các thành phần của quản lý dự án
8. Biểu đồ Gantt
9. CPM / PERT
10.Xác suất thời gian hoạt động
11. Thiết lập sơ đồ mạng bằng MS Project
12. Điều chỉnh sơ đồ mạng theo thời gian
13. Chuyển đổi mô hình mạng CPM/PERT sang Mô hình quy
hoạch tuyến tính

3

GV. ThS. Huỳnh Đỗ Bảo Châu

GV. Huỳnh Đỗ Bảo Châu

PHẦN 1
KỸ THUẬT MẠNG
1. Giới thiệu về kỹ thuật mạng

4

GV. Huỳnh Đỗ Bảo Châu

1

2/12/2017

Khái niệm mạng (network)
Mạng là sự sắp xếp các đường dẫn kết nối tại các điểm
khác nhau, thông qua đó các hạng mục (items) được
di chuyển.
Ứng dụng mạng rất phổ biến vì chúng cung cấp một
bức tranh của hệ thống và hệ thống lớn có thể dễ dàng
mô hình hóa như các mạng.
Mô hình dòng chảy mạng (network flow models) mô tả
dòng chảy các hạng mục (items) thông qua hệ thống.







Các thành phần của mạng
Nút (nodes): biểu diễn bằng vòng tròn, đại diện cho các điểm giao nhau
nối các nhánh.
Nhánh (branches): đại diện là đường thẳng, kết nối các nút và hiển thị
dòng chảy từ điểm này đến điểm khác.
Giá trị đại diện cho khoảng cách, độ dài của thời gian, chi phí hoặc
được gán cho mỗi nhánh.
Mục đích của mạng là xác định khoảng cách ngắn nhất, độ dài thời
gian ngắn nhất, hoặc chi phí thấp nhất giữa các điểm trong mạng.






Mạng lưới đường sắt có 4 node, 4 nhánh
Nút 1 (atlanta) là nút gốc
5

GV. Huỳnh Đỗ Bảo Châu

6

GV. Huỳnh Đỗ Bảo Châu

Đường đi ngắn nhất (shortest route)
Đường ngắn nhất là khoảng cách ngắn nhất giữa một
node gốc (điểm xuất phát) và các điểm đến.
Bài toán tìm đường ngắn nhất được giải quyết bằng
cách sử dụng các kỹ thuật giải trình ngắn nhất




7

GV. ThS. Huỳnh Đỗ Bảo Châu

GV. Huỳnh Đỗ Bảo Châu

2. Bài toán tìm đường ngắn nhất

8

GV. Huỳnh Đỗ Bảo Châu

2

2/12/2017

Giải pháp tìm đường ngắn nhất
Chọn nút với đường đi trực tiếp ngắn nhất từ nút gốc.
Thiết lập một tập vĩnh viễn với các nút gốc và các
nút được chọn ở bước 1.
Xác định tất cả các nút được kết nối trực tiếp đến
các nút trong tập vĩnh viễn.
Chọn nút với các tuyến đường ngắn nhất (nhánh) từ
nhóm các nút được nối trực tiếp đến các nút trong
tập vĩnh viễn.
Lặp lại bước 3 và 4 cho đến khi tất cả các nút đã
tham gia vào tập vĩnh viễn.

1.
2.
3.
4.

5.

9

Tìm đường đi nhanh nhất để công ty vận chuyển Stagecoach
Shipping đi từ Los Angeles đến sáu thành phố có thời gian di
Xác định tuyến đường đi
chuyển (giờ) như hình.
có thời gian ngắn nhất từ
node 1 đến 6 node còn lại

GV. Huỳnh Đỗ Bảo Châu

Ví dụ minh họa (tt)


Ví dụ minh họa

 Node 3 đưa vào tập vĩnh viễn  {1,3}

GV. ThS. Huỳnh Đỗ Bảo Châu

GV. Huỳnh Đỗ Bảo Châu

Ví dụ minh họa (tt)

Xét từ node 1 – nằm trong tập vĩnh viễn

11

10

GV. Huỳnh Đỗ Bảo Châu



Xét từ node {1,3} – nằm trong tập vĩnh viễn

 Node 2 đưa vào tập vĩnh viễn  {1,2,3}
12

GV. Huỳnh Đỗ Bảo Châu

3

2/12/2017

Ví dụ minh họa (tt)


Ví dụ minh họa (tt)

Xét từ node {1,2,3} – nằm trong tập vĩnh viễn

 Node 4 đưa vào tập vĩnh viễn  {1,2,3,4}
13

 Node 5 đưa vào tập vĩnh viễn  {1,2,3,4,5,6}

GV. ThS. Huỳnh Đỗ Bảo Châu

14

GV. Huỳnh Đỗ Bảo Châu

Ví dụ minh họa (tt)

Xét từ node {1,2,3,4,6} – nằm trong tập vĩnh viễn

15

Xét từ node {1,2,3,4} – nằm trong tập vĩnh viễn

 Node 6 đưa vào tập vĩnh viễn  {1,2,3,4,6}

GV. Huỳnh Đỗ Bảo Châu

Ví dụ minh họa (tt)




GV. Huỳnh Đỗ Bảo Châu



Xét từ node {1,2,3,4,5,6} – nằm trong tập vĩnh viễn

 Node 7 đưa vào tập vĩnh viễn {1,2,3,4,5,6,7}
16

GV. Huỳnh Đỗ Bảo Châu

4

2/12/2017

Ví dụ minh họa (tt)


Kết luận của bài toán:

3. Giải bài toán tìm đường ngắn nhất
bằng Excel

17

GV. Huỳnh Đỗ Bảo Châu

Giải pháp trên Excel








Tìm đường đi nhanh nhất để công ty vận chuyển Stagecoach
Shipping đi từ Los Angeles đến sáu thành phố có thời gian di
chuyển (giờ) như hình.

Biến quyết định của từng nhánh trong mạng:
0 ế á
1 ế á



GV. Huỳnh Đỗ Bảo Châu

Ví dụ minh họa

Chuyển đổi bài toán tìm mạng lưới ngắn nhất thành mô
hình bài toán lập trình tuyến tính với các số nguyên 0, 1.
Xây dựng mô hình lập trình tuyến tính:


18




ư
ộ ế ả đườ ắ ấ

ộ ế ả đườ ắ ấ

Xác định tuyến đường đi
có thời gian ngắn nhất từ
node 1 đến 6 node còn lại

Giả định dòng chảy chỉ đi từ node nhỏ đến node lớn hơn.
Hàm mục tiêu:

∑
(K là giá trị thời gian, khoảng
cách, chi phí … của nhánh i – j )
Ràng buộc cho mỗi nút: bất cứ node nào cũng phãi có 1 đường ra 
bảo tồn dòng chảy.
Sử dụng Solve để giải bài toán QHTT trên
Đọc kết quả dựa trên các giá trị biến xij = 1

19

GV. ThS. Huỳnh Đỗ Bảo Châu

GV. Huỳnh Đỗ Bảo Châu

20

GV. Huỳnh Đỗ Bảo Châu

5