TAILIEUCHUNG - 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 | 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 CHƯƠNG III: MÔ HÌNH SƠ ĐỒ MẠNG LƯỚI . Khái niệm đồ thị và sơ đồ mạng lưới . Quy tắc thực hành lập sơ đồ mạng lưới . Phân tích sơ đồ mạng lưới theo chỉ tiêu thời gian . Sơ đồ mạng lưới với các yếu tố thời gian và chi phí . Bài toán cân đối tài nguyên . 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. 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. Đồ 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. 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.
đang nạp các trang xem trước
