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

Chia sẻ: Hồ Văn Toàn | Ngày: | Loại File: PPT | Số trang:39

Thêm vào BST

Báo xấu

603
lượt xem 76
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 Z5 Z3 Z3 Z5 Z5 Z3 Hình 3a Hình 3b Hình 3c (Sai)
d. Khi chia nhỏ công việc chẳng hạn công việc a, b, c bắt đầu sau khi hoàn thành 1/3 ; 2/3 và cả công việc X thì vẽ như hình 4 a a b c b X X/3 X/3 X/3 c Hình 4 Hình 5 (Sai)
e. Khi có 2 đỉnh vào hoặc 2 đỉnh ra trở lên thì nối chúng bằng mũi tên giả (hình 6). Đỉnh vào Đỉnh ra Hình 6
3. Cách đánh số thứ tự các đỉnh: - Đỉnh khởi công được đánh số 0. - Đỉnh kết thúc đánh số lớn nhất. - Các đỉnh liên thông với đỉnh số 0 được đánh số thứ tự từ 1 trở đi, sau đó đến lượt các đỉnh liên thông với đỉnh số 1, đỉnh số 2... - Khi một đỉnh đã đánh số thì xoá đường đến đỉnh đó. - Thứ tự các đỉnh không được đánh trùng nhau. Chú ý : - Dựa vào thứ tự tiến hành từng công việc để có thể thiết lập các sơ đồ càng đơn giản bao nhiêu càng tốt bấy nhiêu. - Khi thiết lập các sơ đồ cần tránh tới mức tối đa việc vẽ các cạnh cắt nhau. - Cần lợi dụng triệt để kỹ thuật dùng đỉnh giả và cạnh
Ví dụ : Một công trình xây dựng gồm 10 công việc lớn y1, y2, .., y10: Thứ tự Tên công Thời hạn Thứ tự tiến hành việc (tháng) Bắt đầu ngay 1 y1 2 Bắt đầu ngay 2 y2 4 Bắt đầu ngay 3 y3 3 Khởi công sau khi xong y1 4 y4 5 Khởi công sau khi xong y1 5 y5 4 Khởi công sau khi xong y1 6 y6 6 Khởi công sau khi xong y2 và y4 7 y7 3 Khởi công sau khi xong y3 8 y8 11 Khởi công sau khi xong y6 và y7 9 y9 4
● Biểu đồ Gantt: (Sơ đồ ngang hay sơ đồ đường thẳng) + Các công việc được thể hiện bằng các đoạn thẳng nằm ngang với tên công việc. + Độ dài đoạn thẳng là thời gian hoàn thành công việc. + Số đoạn thẳng trong 1 cột là số công việc cùng phải làm trong cùng 1 tháng. Người ta dựa vào biểu đồ Gantt để bố trí công việc và chỉ đạo kế hoạch.
Thời gian Quý 1/08 Quý 2/08 Quý 3/08 Quý 4/08 2009 Công việc 1 2 3 4 5 67 8 9 10 11 12 1 2 y1 y2 y3 y4 y5 y6 y7 y8 y9 y10
● Lập sơ đồ mạng: y5 1 4 4 y1 y6 y10 y4 2 5 5 6 y9 y2 y7 0 3 5 6 4 3 4 y3 y8 3 11 2 Hình 7
♦ So sánh hai loại sơ đồ: Sơ đồ mạng có những ưu nhược điểm: điểm: + Ưu - Nhờ hai yếu tố công việc sự kiện mà quá trình thi công được nêu 1 cách toàn cục, người chỉ đạo theo dõi được cả tổng thể và cá biệt. - Có kế hoạch nhịp nhàng và kiểm tra được từng khâu công việc. - Thấy vị trí từng việc và ảnh hưởng của nó. - Đặc biệt thấy được khâu chủ yếu (đường Găng) để tập trung chỉ đạo dứt điểm. + Nhược điểm: - Số lượng công việc trong từng thời điểm chưa được thể hiện rõ. - Trong các trường hợp phải cân đối tài nguyên thì sơ đồ mạng chưa phát huy được tác dụng. Trong quá trình lập kế hoạch và chỉ đạo thực hiện kế hoạch người ta thường kết hợp cả hai dạng sơ đồ.
3.3. Phân tích sơ đồ mạng lưới theo chỉ tiêu thời gian: A - Xác định thời điểm sớm nhất và muộn nhất hoàn thành các sự kiện: 1. Thời điểm sớm nhất hoàn thành sự kiện: Ký hiệu: (i, j) là một cạnh của mạng tj(s) là thời điểm sớm nhất hoàn thành sự kiện j, j = 0, 1,…, n, n + 1 t0(s) = 0 tj(s) = max {ti(s) + tij}