Bài giảng môn Tối ưu hóa - Chương 4 Sơ đồ mạng

CHƯƠNG 4: SƠ ĐỒ MẠNG I) MỘT VÍ DỤ THỰC TẾ Ví dụ 4.1: Giả sử một quy trình cưới vợ “chuẩn” gồm các công việc có trình tự thực hiện, định mức thời gian (tháng) như sau : Công việc Trình tự thực hiện Định mức thời gian 1. Kiếm vợ Bắt đầu ngay 6 2. Kiếm tiền mua nhà Bắt đầu ngay 12 3. Kiếm tiền cưới vợ Bắt đầu ngay 7 4. Đám nói Sau 1 2 5. Đám hỏi Sau 2, 3, 4 4 6. Chụp hình cưới Sau 5 3 7. Chọn đồ cưới, nữ trang Sau 5 4 8. Chọn nơi đặt tiệc cưới Sau 5 5 9. Đám cưới Sau 6, 7, 8 1  Câu hỏi đặt ra là:  Với thời gian định mức như trên thì:   Thời gian ngắn nhất hoàn thành quy trình này (cưới được vợ) là bao nhiêu tháng?   Muốn rút ngắn thời gian ngắn nhất hoàn thành quy trình này ta chỉ cần tìm cách rút ngắn thời gian thực hiện của một số công việïc nào?   Những công việc nào có thể hoàn thành chậm trễ một khoảng thời gian nào đó so với thời gian định mức mà không ảnh hưởng đến thời gian ngắn nhất hoàn thành toàn bộ quy trình?  Các câu hỏi trên được trả lời 1 cách dễ dàng khi ta lập sơ đồ mạng cho quy trình và tính 1 số chỉ tiêu của sơ đồ.  II) CÁC KHÁI NIỆM VÀ ĐỊNH NGHĨA  1) Đồ thị Là 1 tập hợp các đỉnh A và tập hợp các cạnh, cung U nối liền các đỉnh của A. Ký hiệu: G = (A, U) : đồ thị G  Ví dụ 1: Trích 1 phần bản đồ TP.HCM có các địa điểm a1, a2, a3, a4 được nối với nhau bằng đường 1 chiều và đường 2 chiều.  Các đỉnh: a1, a2, a3, a4. Tập hợp các đỉnh A={a1, a2, a3 , a4}  Các cung: (a1, a2) , (a2, a4) , (a4, a3) ; các cạnh: (a1,a3) , (a2,a3)  Tập hợp các cạnh, cung: U= {(a1,a2) , (a2,a4) , (a4,a3) , (a1,a3) , (a2,a3)}  Cung (a1,a2) : đỉnh gốc (đỉnh đứùng trước) là a1 , đỉnh ngọn (đỉnh đứng sau) là a2  Cạnh (a1,a3) : không phân biệt đỉnh gốc, đỉnh ngọn  2) Đồ thị hữu hạn A là tập hữu hạn.  3) Đồ thị có hướng Mọi phần tử trong U đều là cung.  4) Dây chuyền từ đỉnh a đến đỉnh b là 1 dãy đỉnh và cung kế tiếp nhau.  Dây chuyền (1, u1, 2, u2, 3, u3, 4) nối đỉnh 1 với đỉnh 4.  5) Đường đi làø 1 dây chuyền có các cung nối đuôi nhau (ngọn cung trước là gốc của cung sau).  Đường đi (1, u1, 2, u2, 3, u3, 4) có đỉnh bắt đầu 1, đỉnh kết thúc 4.  6) Khuyên là 1 cung có đỉnh gốc và đỉnh ngọn trùng nhau.  Khuyên (2, u2, 2).  7) Chu trình là đường đi có đỉnh bắt đầu trùng với đỉnh kết thúc.  Chu trình (1, u1, 2, u2, 3, u3, 1)  8) Đồ thị liên thông là đồ thị có mọi cặp đỉnh a, b của A đều nối với nhau bởi 1 dây chuyền.  Ví dụ 5: đồ thị liên thông  9) Đồ thị phản xứng  nếu 2 đỉnh a, b bất kỳ của A có cung nối từ ab thì sẽ không có cung nối ngược lại từ ba.  Ví dụ 5: đồ thị phản xứng  10) Đồ thị đơn Giữa 2 đỉnh a, b bất kỳ của A có nhiều nhất 1 cung nối.  Ví dụ 5: đồ thị đơn  11) Sơ đồ mạng là 1 đồ thị hữu hạn, có hướng, không khuyên, không chu trình, liên thông, phản xứng, đơn; đồng thời trên mỗi cung gán cho 1 số thực không âm gọi là độ dài cung.  12) Độ dài đường đi là tổng các độ dài của các cung thuộc đường đi. Ví dụ 9: Xét các đường đi từ đỉnh 1 tới đỉnh 5 là: Đường đi A : (1, u1, 2, u2, 3, u4, 5) có độ dài 3 + 5 + 9 = 17 Đường đi B : (1, u3, 3, u4, 5) có độ dài 7 + 9 = 16 Đường đi C : (1, u5, 4, u6, 5) có độ dài 5 + 8 = 13  13) Đường đi dài nhất trong các đường đi từ đỉnh i đến đỉnh j là đường đi có độ dài lớn nhất từ đỉnh i đến đỉnh j. Ví dụ 9: Trong 3 đường đi từ đỉnh 1 tới đỉnh 5 thì đường đi A là đường đi dài nhất (đường đi có độ dài lớn nhất). III) LẬP SƠ ĐỒ MẠNG Ta lập sơ đồ mạng lưới (PERT - Program Evaluation and Review Technique) với các tương ứng như sau: Đỉnh tương ứng với sự kiện hoàn thành một số công việc và bắt đầu một số công việc khác. Cung tương ứng với công việc. Độ dài cung tương ứng với thời gian định mức cho công việc.  Công việc (i,j) có : sự kiện đầu (đỉnh gốc) i , sự kiện sau (đỉnh ngọn) j , thời gian định mức tij  Dự án là 1 quá trình gồm các công việc, nhiệm vụ có liên quan với nhau, được thực hiện nhằm đạt được mục tiêu đã đề ra trong điều kiện ràng buộc về thời gian, nguồn lực và ngân sách. 1) Các chú ý cần thiết Khi lập sơ đồ mạng ta chú ý những trường hợp sau: 2) Cách vẽ sơ đồ Ví dụ 4.1: Xác định 3 loại công việc: - Công việc khởi công (bắt đầu ngay): y1, y2, y3 - Công việc kết thúc (là các công việc chỉ nằm ở cột công việc, không nằm ở cột trình tự thực hiện): y9 - Công việc trung gian: là các công việc còn lại Ví dụ 4.2: Lập sơ đồ mạng cho quy trình sản xuất sau: Công việc Trình tự thực hiện Định mức thời gian (ngày) y1 y2 y3 y4 y5 y6 y7 y8 y9 y10 y11 y12 y13 bắt đầu ngay bắt đầu ngay sau y1 sau y1 sau y2 sau y2 sau y2 sau y3 và y5 sau y4 sau y4 sau y7 sau y6 , y8 , y9 , y11 sau y7 15 21 9 16 17 20 19 14 11 14 10 18 11  Xác định 3 loại công việc: - Công việc khởi công (bắt đầu ngay): y1, y2 - Công việc kết thúc (là các công việc chỉ nằm ở cột công việc, không nằm ở cột trình tự thực hiện): y10 , y12 , y13 - Công việc trung gian: là các công việc còn lại Các phần xem thêm trong sách.  3) Đánh số các đỉnh  IV) PHÂN TÍCH SƠ ĐỒ MẠNG THEO CÁC CHỈ TIÊU THỜI GIAN  1) Chỉ tiêu thời gian đối với đỉnh  1.5) Đường găng:  2) Chỉ tiêu thời gian đối với công việc  V) MỘT SỐ LƯU Ý VỀ SƠ ĐỒ MẠNG  1) Thời gian dự trữ chung của công việc  2) Rút ngắn thời gian hoàn thành dự án  4) Bài toán giá thành rẻ nhất  5) Đánh giá khả năng hoàn thành dự án Mời ghé thăm trang web: 42  https://sites.google.com/a/ueh.edu.vn/phamtricao/  https://sites.google.com/site/phamtricao/