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<br /> <br /> TRƯỜNG ĐẠI HỌC NGÂN HÀNG TP<br /> .HCM<br /> KHOA HỆ THỐNG THÔNG TIN QUẢN LÝ<br /> <br /> KHOA HỌC QUẢN LÝ ỨNG DỤNG<br /> <br /> CHƯƠNG 5<br /> KỸ THUẬT MẠNG TRONG QUẢN LÝ<br /> <br /> Nội dung chính<br /> PHẦN 1: KỸ THUẬT MẠNG<br /> 1. Giới thiệu về kỹ thuật mạng<br /> 2. Bài toán tìm đường ngắn nhất<br /> 3. Giải bài toán tìm đường ngắn nhất bằng Excel<br /> 4. Bài toán cây bao trùm tối thiểu<br /> 5. Bài toán luồng cực đại<br /> 6. Giải bài toán tìm luồng cực đại bằng Excel<br /> <br /> GV. ThS. Huỳnh Đỗ Bảo Châu<br /> <br /> 1<br /> <br /> 2<br /> <br /> GV. Huỳnh Đỗ Bảo Châu<br /> <br /> Nội dung chính<br /> PHẦN 2: KỸ THUẬT MẠNG TRONG QUẢN LÝ DỰ ÁN<br /> 7. Các thành phần của quản lý dự án<br /> 8. Biểu đồ Gantt<br /> 9. CPM / PERT<br /> 10.Xác suất thời gian hoạt động<br /> 11. Thiết lập sơ đồ mạng bằng MS Project<br /> 12. Điều chỉnh sơ đồ mạng theo thời gian<br /> 13. Chuyển đổi mô hình mạng CPM/PERT sang Mô hình quy<br /> hoạch tuyến tính<br /> <br /> 3<br /> <br /> GV. ThS. Huỳnh Đỗ Bảo Châu<br /> <br /> GV. Huỳnh Đỗ Bảo Châu<br /> <br /> PHẦN 1<br /> KỸ THUẬT MẠNG<br /> 1. Giới thiệu về kỹ thuật mạng<br /> <br /> 4<br /> <br /> GV. Huỳnh Đỗ Bảo Châu<br /> <br /> 1<br /> <br /> 2/12/2017<br /> <br /> Khái niệm mạng (network)<br /> Mạng là sự sắp xếp các đường dẫn kết nối tại các điểm<br /> khác nhau, thông qua đó các hạng mục (items) được<br /> di chuyển.<br /> Ứng dụng mạng rất phổ biến vì chúng cung cấp một<br /> bức tranh của hệ thống và hệ thống lớn có thể dễ dàng<br /> mô hình hóa như các mạng.<br /> Mô hình dòng chảy mạng (network flow models) mô tả<br /> dòng chảy các hạng mục (items) thông qua hệ thống.<br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> Các thành phần của mạng<br /> Nút (nodes): biểu diễn bằng vòng tròn, đại diện cho các điểm giao nhau<br /> nối các nhánh.<br /> Nhánh (branches): đại diện là đường thẳng, kết nối các nút và hiển thị<br /> dòng chảy từ điểm này đến điểm khác.<br /> Giá trị đại diện cho khoảng cách, độ dài của thời gian, chi phí hoặc<br /> được gán cho mỗi nhánh.<br /> Mục đích của mạng là xác định khoảng cách ngắn nhất, độ dài thời<br /> gian ngắn nhất, hoặc chi phí thấp nhất giữa các điểm trong mạng.<br /> <br /> <br /> <br /> <br /> <br /> <br /> Mạng lưới đường sắt có 4 node, 4 nhánh<br /> Nút 1 (atlanta) là nút gốc<br /> 5<br /> <br /> GV. Huỳnh Đỗ Bảo Châu<br /> <br /> 6<br /> <br /> GV. Huỳnh Đỗ Bảo Châu<br /> <br /> Đường đi ngắn nhất (shortest route)<br /> Đường ngắn nhất là khoảng cách ngắn nhất giữa một<br /> node gốc (điểm xuất phát) và các điểm đến.<br /> Bài toán tìm đường ngắn nhất được giải quyết bằng<br /> cách sử dụng các kỹ thuật giải trình ngắn nhất<br /> <br /> <br /> <br /> <br /> 7<br /> <br /> GV. ThS. Huỳnh Đỗ Bảo Châu<br /> <br /> GV. Huỳnh Đỗ Bảo Châu<br /> <br /> 2. Bài toán tìm đường ngắn nhất<br /> <br /> 8<br /> <br /> GV. Huỳnh Đỗ Bảo Châu<br /> <br /> 2<br /> <br /> 2/12/2017<br /> <br /> Giải pháp tìm đường ngắn nhất<br /> Chọn nút với đường đi trực tiếp ngắn nhất từ nút gốc.<br /> Thiết lập một tập vĩnh viễn với các nút gốc và các<br /> nút được chọn ở bước 1.<br /> Xác định tất cả các nút được kết nối trực tiếp đến<br /> các nút trong tập vĩnh viễn.<br /> Chọn nút với các tuyến đường ngắn nhất (nhánh) từ<br /> nhóm các nút được nối trực tiếp đến các nút trong<br /> tập vĩnh viễn.<br /> Lặp lại bước 3 và 4 cho đến khi tất cả các nút đã<br /> tham gia vào tập vĩnh viễn.<br /> <br /> 1.<br /> 2.<br /> 3.<br /> 4.<br /> <br /> 5.<br /> <br /> 9<br /> <br /> Tìm đường đi nhanh nhất để công ty vận chuyển Stagecoach<br /> Shipping đi từ Los Angeles đến sáu thành phố có thời gian di<br /> Xác định tuyến đường đi<br /> chuyển (giờ) như hình.<br /> có thời gian ngắn nhất từ<br /> node 1 đến 6 node còn lại<br /> <br /> GV. Huỳnh Đỗ Bảo Châu<br /> <br /> Ví dụ minh họa (tt)<br /> <br /> <br /> Ví dụ minh họa<br /> <br />  Node 3 đưa vào tập vĩnh viễn  {1,3}<br /> <br /> GV. ThS. Huỳnh Đỗ Bảo Châu<br /> <br /> GV. Huỳnh Đỗ Bảo Châu<br /> <br /> Ví dụ minh họa (tt)<br /> <br /> Xét từ node 1 – nằm trong tập vĩnh viễn<br /> <br /> 11<br /> <br /> 10<br /> <br /> GV. Huỳnh Đỗ Bảo Châu<br /> <br /> <br /> <br /> Xét từ node {1,3} – nằm trong tập vĩnh viễn<br /> <br />  Node 2 đưa vào tập vĩnh viễn  {1,2,3}<br /> 12<br /> <br /> GV. Huỳnh Đỗ Bảo Châu<br /> <br /> 3<br /> <br /> 2/12/2017<br /> <br /> Ví dụ minh họa (tt)<br /> <br /> <br /> Ví dụ minh họa (tt)<br /> <br /> Xét từ node {1,2,3} – nằm trong tập vĩnh viễn<br /> <br />  Node 4 đưa vào tập vĩnh viễn  {1,2,3,4}<br /> 13<br /> <br />  Node 5 đưa vào tập vĩnh viễn  {1,2,3,4,5,6}<br /> <br /> GV. ThS. Huỳnh Đỗ Bảo Châu<br /> <br /> 14<br /> <br /> GV. Huỳnh Đỗ Bảo Châu<br /> <br /> Ví dụ minh họa (tt)<br /> <br /> Xét từ node {1,2,3,4,6} – nằm trong tập vĩnh viễn<br /> <br /> 15<br /> <br /> Xét từ node {1,2,3,4} – nằm trong tập vĩnh viễn<br /> <br />  Node 6 đưa vào tập vĩnh viễn  {1,2,3,4,6}<br /> <br /> GV. Huỳnh Đỗ Bảo Châu<br /> <br /> Ví dụ minh họa (tt)<br /> <br /> <br /> <br /> <br /> GV. Huỳnh Đỗ Bảo Châu<br /> <br /> <br /> <br /> Xét từ node {1,2,3,4,5,6} – nằm trong tập vĩnh viễn<br /> <br />  Node 7 đưa vào tập vĩnh viễn {1,2,3,4,5,6,7}<br /> 16<br /> <br /> GV. Huỳnh Đỗ Bảo Châu<br /> <br /> 4<br /> <br /> 2/12/2017<br /> <br /> Ví dụ minh họa (tt)<br /> <br /> <br /> Kết luận của bài toán:<br /> <br /> 3. Giải bài toán tìm đường ngắn nhất<br /> bằng Excel<br /> <br /> 17<br /> <br /> GV. Huỳnh Đỗ Bảo Châu<br /> <br /> Giải pháp trên Excel<br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> Tìm đường đi nhanh nhất để công ty vận chuyển Stagecoach<br /> Shipping đi từ Los Angeles đến sáu thành phố có thời gian di<br /> chuyển (giờ) như hình.<br /> <br /> Biến quyết định của từng nhánh trong mạng:<br /> 0 ế á <br /> 1 ế á<br /> <br /> <br /> <br /> GV. Huỳnh Đỗ Bảo Châu<br /> <br /> Ví dụ minh họa<br /> <br /> Chuyển đổi bài toán tìm mạng lưới ngắn nhất thành mô<br /> hình bài toán lập trình tuyến tính với các số nguyên 0, 1.<br /> Xây dựng mô hình lập trình tuyến tính:<br /> <br /> <br /> 18<br /> <br /> <br /> <br /> <br /> ư <br /> ộ ế ả đườ ắ ấ<br /> <br /> ộ ế ả đườ ắ ấ<br /> <br /> Xác định tuyến đường đi<br /> có thời gian ngắn nhất từ<br /> node 1 đến 6 node còn lại<br /> <br /> Giả định dòng chảy chỉ đi từ node nhỏ đến node lớn hơn.<br /> Hàm mục tiêu:<br /> <br /> ∑<br /> (K là giá trị thời gian, khoảng<br /> cách, chi phí … của nhánh i – j )<br /> Ràng buộc cho mỗi nút: bất cứ node nào cũng phãi có 1 đường ra <br /> bảo tồn dòng chảy.<br /> Sử dụng Solve để giải bài toán QHTT trên<br /> Đọc kết quả dựa trên các giá trị biến xij = 1<br /> <br /> 19<br /> <br /> GV. ThS. Huỳnh Đỗ Bảo Châu<br /> <br /> GV. Huỳnh Đỗ Bảo Châu<br /> <br /> 20<br /> <br /> GV. Huỳnh Đỗ Bảo Châu<br /> <br /> 5<br /> <br />