BÀI GIẢNG QUY HOẠCH TUYẾN TÍNH CHƯƠNG 3

1. Đồ thị: - Một tập hợp các điểm A1, A2,.....,An được nối liền với nhau bởi các cạnh có độ dài u1, u2,.......,un gọi là một đồ thị. - Các điểm A1, A2,......., An gọi là các đỉnh. - Các đoạn thẳng nối từ đỉnh Ai đến Aj ( i ≠ j) gọi là cạnh của đồ thị. - Cạnh AiAj là cạnh liền thuộc 2 đỉnh Ai , Aj. - Nếu các cạnh là các véc tơ (được quy định chiều) thì đồ thị gọi là có hướng....
Nội dung trích xuất từ tài liệu:
BÀI GIẢNG QUY HOẠCH TUYẾN TÍNH CHƯƠNG 3 TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP BỘ MÔN KHOA HỌC CƠ BẢN BÀI GIẢNG QUY HOẠCH TUYẾN TÍNH MÔ HÌNH SƠ ĐỒ MẠNG LƯỚI 3.1. Khái niệm đồ thị và sơ đồ mạng lưới 3.2. Quy tắc thực hành lập sơ đồ mạng lưới 3.3. Phân tích sơ đồ mạng lưới theo chỉ tiêu thời gian 3.4. Sơ đồ mạng lưới với các yếu tố thời gian và chi phí 3.5. Bài toán cân đối tài nguyên 3.1. Các khái niệm: 1. Đồ thị: - Một tập hợp các điểm A1, A2,.....,An được nối liền với nhau bởi các cạnh có độ dài u1, u2,.......,un gọi là một đồ thị. - Các điểm A1, A2,......., An gọi là các đỉnh. - Các đoạn thẳng nối từ đỉnh Ai đến Aj ( i ≠ j) gọi là cạnh của đồ thị. - Cạnh AiAj là cạnh liền thuộc 2 đỉnh Ai , Aj. - Nếu các cạnh là các véc tơ (được quy định chiều) thì đồ thị gọi là có hướng. Đồ thị phản xứng: Trong một đồ thị các cạnh chỉ đi từ Ai đến Aj ( i ≠ j ) mà không có chiều ngược lại. Đồ thị đơn: Giữa hai đỉnh bất kỳ Ai, Aj (i ≠ j) chỉ có nhiều nhất là một cạnh có hướng. Dây chuyền: là một dãy các đỉnh, cạnh nối nhau liên tiếp. Nếu các cạnh trên dây chuyền là có hướng nối đuôi nhau thì dây chuyền đó trở thành một đường đi. Chu trình: là một đường đi đóng kín. Khuyên: là một đường xuất phát từ 1 đỉnh rồi lại quay về đỉnh đó mà không đi qua bất kỳ đỉnh nào khác. 2. Mạng: Trước hết ta quy ước cho một điểm Ai các cạnh đi tới ký hiệu ui+, các cạnh từ Ai ra ký hiệu ui−, trên mỗi cạnh u (i,j) gán một số dương tij gọi là độ dài của cạnh. ● Định nghĩa 1: Mạng là một đồ thị phản xứng liên thông, không khuyên, không chu trình và trên mỗi cạnh đều có ghi độ dài tij của nó. ● Định nghĩa 2: Mạng Ford - Fulkerson là một mạng mà đỉnh A1 (đỉnh đầu tiên) chỉ có các cạnh ra, đỉnh An ( đỉnh cuối cùng) chỉ có các cạnh vào. A1 được gọi là đỉnh vào, An được gọi là đỉnh ra. ● Định nghĩa 3: Độ dài M của một đường đi là tổng số độ dài các cạnh của đường đi đó. Đường đi có độ dài lớn nhất trong mạng Ford - Fulkerson gọi là đường Găng. Ví dụ: A2 9 A5 4 1 2 A1 7 A3 6 A6 8 A7 3 4 6 A4 (Hình 1) A1 là đỉnh vào, A7 là đỉnh ra. Đường găng là đường nối các đỉnh A1, A3, A6, A7. Ký hiệu đường Găng: (A1(A1, A3), A3 , (A3, A6), A6 , (A6, A7), A7). Trong mạng đường găng được vẽ bằng mũi tên đậm. 3. Sơ đồ mạng lưới: Sơ đồ mạng lưới (PERT) là một hình thức mô tả trình tự thực hiện các công việc của một dự án nhằm đạt 1 mục tiêu nào đó (tiết kiệm thời gian, giá thành...) Hai yếu tố cơ bản của một sơ đồ mạng lưới là: - Các công việc biểu thị bằng các cạnh có hướng - Các sự kiện được biểu thị bằng các đỉnh Trong đó một đỉnh vào là sự kiện khởi công và đỉnh ra là sự kiện hoàn thành toàn bộ. 3.2. Quy tắc thực hành lập sơ đồ mạng lưới: 1. Nguyên tắc chung: - Giữa hai đỉnh bất kỳ chỉ duy nhất có một cạnh nối liền chúng. - Trong một sơ đồ không có chu trình nói chung các cạnh không nên bắt chéo nhau khi không cần thiết. 2. Quy tắc thực hành: a. Nếu có nhiều công việc cùng làm song song (cùng khởi công và cùng kết thúc) (hình 1a) thì: -Hoặc gộp chúng lại thành một công việc lớn và thời gian bằng tổng các thời gian gộp lại nếu chúng cùng tính chất công việc (hình 1b). -Hoặc lập thành các đỉnh mới và các cạnh giả và thời gian tij = 0 (hình 1c). t1 0 t1 t2 t2 i j i j i j t1+t2+t3 t3 t3 0 Hình 1a Hình 1b Hình 1c b. Nếu có một nhóm công việc tạo thành một mạch con khi đưa vào mạch lớn ta coi là một việc, thời gian bằng đường găng của mạch con (hình 2a thành 2b). 2 x4 x1 x3 4 1 Z1 Z2 x2 x5 3 Hình 2a j i Z2 Z1 T Hình 2b c. Nếu Z4 khởi công sau khi xong Z1, Z2 còn Z5 khởi công sau khi xong Z1, Z2, Z3 thì phải lập mũi tên giả để vẽ (hình 3a). Nếu Z4 sau Z1, Z2 và Z5 sau Z2, Z3 thì phải vẽ như hình 3c. Z1 Z1 Z4 Z4 Z1 Z4 Z2 Z2 Z2 ...