2/12/2017
GV.ThS.HuỳnhĐỗBảoChâu 1
CHƯƠNG 5
KỸ THUẬT MẠNG TRONG QUẢN LÝ
1
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
GV. ThS. Huỳnh Đỗ Bảo Châu
Nội dung chính
PHẦN1:KỸTHUẬTMẠNG
1.
Giới thiệuvềkỹthuậtmạng
2.
Bài toán tìm đường ngắnnhất
3.
Giải bài toán tìm đường ngắnnhấtbằ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đạibằng Excel
2GV. Huỳnh Đỗ Bảo Châu
Nội dung chính
PHẦN2:KỸTHUẬTMẠNG TRONG QUẢNLÝDỰÁN
7. Các thành phầncủaquảnlýdựán
8. Biểuđồ Gantt
9. CPM / PERT
10.Xác suấtthờigianhoạtđộng
11. Thiếtlậpsơđồmạng bằng MS Project
12. Điềuchỉnh sơđồmạng theo thờigian
13. Chuyểnđổimôhìnhmạng CPM/PERT sang Mô hình quy
hoạch tuyếntính
3GV. Huỳnh Đỗ Bảo Châu
1. Giới thiệu về kỹ thuật mạng
GV. Huỳnh Đỗ Bảo Châu4
PHẦN 1
KỸ THUẬT MẠNG
2/12/2017
GV.ThS.HuỳnhĐỗBảoChâu 2
Khái niệm mạng (network)
GV. Huỳnh Đỗ Bảo Châu5
Mạng là sựsắpxếpcácđường dẫnkếtnốitạicácđiểm
khác nhau, thông qua đócáchạng mục(items)được
di chuyển.
Ứng dụng mạng rấtphổbiến vì chúng cung cấpmột
bứctranhcủahệthống và hệthống lớncóthểdễdàng
mô hình hóa nhưcác mạng.
Mô hình dòng chảymạng (network flow models) mô tả
dòng chảycáchạng mục (items) thông qua hệthống.
Các thành phần của mạng
GV. Huỳnh Đỗ Bảo Châu6
Nút (nodes): biểudiễnbằng vòng tròn, đạidiệnchocácđiểmgiaonhau
nối các nhánh.
Nhánh (branches): đạidiệnlàđường thẳng, kếtnốicácnútvàhiểnthị
dòng chảytừđiểmnàyđếnđiểmkhác.
Giá trịđạidiệnchokhoảng cách, độ dài củathờigian,chiphíhoặc
đượcgánchomỗinhánh.
Mụcđích củamạng là xác định khoảng cách ngắnnhất, độ dài thời
gian ngắnnhất, hoặcchiphíthấpnhấtgiữacácđiểmtrongmạng.
Mạng lưới đường sắt có 4 node, 4 nhánh
Nút 1 (atlanta) là nút gốc
Đường đi ngắn nhất (shortest route)
GV. Huỳnh Đỗ Bảo Châu7
Đường ngắnnhấtlàkhoảng cách ngắnnhấtgiữamột
node gốc(điểmxuấtphát)vàcácđiểmđến.
Bài toán tìm đường ngắnnhấtđượcgiảiquyếtbằng
cách sửdụng các kỹthuậtgiải trình ngắnnhất
2. Bài toán tìm đường ngắn nhất
GV. Huỳnh Đỗ Bảo Châu8
2/12/2017
GV.ThS.HuỳnhĐỗBảoChâu 3
Giải pháp tìm đường ngắn nhất
GV. Huỳnh Đỗ Bảo Châu9
1.
Chọn nút vớiđường đitrựctiếpngắnnhấttừnút gốc.
2.
Thiếtlậpmộttậpvĩnh viễnvới các nút gốcvàcác
nút đượcchọnởbước1.
3.
Xác định tấtcảcác nút đượckếtnốitrựctiếpđến
các nút trong tậpvĩnh viễn.
4.
Chọn nút vớicáctuyếnđường ngắnnhất(nhánh)từ
nhóm các nút đượcnốitrựctiếpđến các nút trong
tậpvĩnh viễn.
5.
Lặplạibước3và4chođếnkhitấtcảcác nút đã
tham gia vào tậpvĩnh viễn.
Ví dụ minh họa
GV. Huỳnh Đỗ Bảo Châu10
Tìm đường đi nhanh nhấtđể công ty vận chuyểnStagecoach
Shipping đitừLos Angeles đến sáu thành phốcó thờigiandi
chuyển(giờ)nhưhình.
Xác định tuyếnđường đi
có thờigianngắnnhấttừ
node 1 đến6 node cònlại
Ví dụ minh họa (tt)
GV. Huỳnh Đỗ Bảo Châu11
Xét từ node 1 – nằm trong tập vĩnh viễn
Node 3 đưa vào tập vĩnh viễn
{1,3}
Ví dụ minh họa (tt)
GV. Huỳnh Đỗ Bảo Châu12
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}
2/12/2017
GV.ThS.HuỳnhĐỗBảoChâu 4
Ví dụ minh họa (tt)
GV. Huỳnh Đỗ Bảo Châu13
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}
Ví dụ minh họa (tt)
GV. Huỳnh Đỗ Bảo Châu14
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}
Ví dụ minh họa (tt)
GV. Huỳnh Đỗ Bảo Châu15
Xét từ node {1,2,3,4,6} – nằm trong tập vĩnh viễn
Node 5 đưa vào tập vĩnh viễn
{1,2,3,4,5,6}
Ví dụ minh họa (tt)
GV. Huỳnh Đỗ Bảo Châu16
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}
2/12/2017
GV.ThS.HuỳnhĐỗBảoChâu 5
Ví dụ minh họa (tt)
GV. Huỳnh Đỗ Bảo Châu17
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
GV. Huỳnh Đỗ Bảo Châu18
Giải pháp trên Excel
GV. Huỳnh Đỗ Bảo Châu19
Chuyểnđổi bài toán tìm mạng lướingắnnhất thành mô
hình bài toán lậptrìnhtuyếntínhvớicácsốnguyên 0, 1.
Xây dựng mô hình lậptrìnhtuyếntính:
Biếnquyếtđịnh củatừng nhánh trong mạng:

0ếáưộếảđườắấ

1ếáộếảđườắấ
Giảđịnh dòng chảychỉđitừnode nhỏđếnnodelớnhơn.
Hàm mụctiêu:∑


(Klà giá trịthờigian,khoảng
cách, chi phí … củanhánhi–j)
Ràng buộcchomỗi nút: bấtcứnode nào cũng phãi có 1 đường ra
bảotồndòngchảy.
Sửdụng Solve để giải bài toán QHTT trên
Đọckếtquảdựatrêncácgiátrịbiếnx
ij
=1
Ví dụ minh họa
GV. Huỳnh Đỗ Bảo Châu20
Tìm đường đi nhanh nhấtđể công ty vận chuyểnStagecoach
Shipping đitừLos Angeles đến sáu thành phốcó thờigiandi
chuyển(giờ)nhưhình.
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