Bài giảng PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG KINH TẾ Mô hình mạng

Chia sẻ: Gray Swan | Ngày: | Loại File: PDF | Số trang:49

Thêm vào BST

Báo xấu

312
lượt xem 78
download

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

Kết thúc chương này, sinh viên có thể: 1. Nắm được những khái niệm cơ bản của mô hình mạng 2. Hiểu được bài toán đường đi ngắn nhất và vận dụng vào kinh tế 3. Hiểu được bài toán cây bao trùm tối thiểu và vận dụng vào kinh tế 4. Hiểu được bài toán đường dòng cực đại và vận dụng vào kinh tế

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 PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG KINH TẾ Mô hình mạng

Chương 3 MÔ HÌNH MẠNG Kết thúc chương này, sinh viên có thể: 1. Nắm được những khái niệm cơ bản của mô hình mạng 2. Hiểu được bài toán đường đi ngắn nhất và vận dụng vào kinh tế 3. Hiểu được bài toán cây bao trùm tối thiểu và vận dụng vào kinh tế 4. Hiểu được bài toán đường dòng cực đại và vận dụng vào kinh tế
Mục lục 117 3.1. Các khái niệm cơ bản 3.2. Bài toán đường ngắn nhất 3.3. Bài toán cây bao trùm tối thiểu 3.4. Bài toán dòng cực đại
3.1. Các khái niệm cơ bản 118 Đồ thị vô hướng G là một cặp gồm hai tập N và A, ký hiệu G(N,A), với N là tập các nút và A là tập các cung vô hướng. Cung vô hướng là một cặp không kể đến thứ tự hai nút khác nhau i và j (i,j∈N) ký hiệu là (i,j). Trong đồ thị vô hướng, cung (i,j) = cung (j,i). Một đường đi từ nút i1 đến nút it là bộ gồm t nút khác nhau i1,…, it sao cho (ik, ik+1)∈A. Chu trình là bộ gồm t nút i1,…,it sao cho i1,…, it-1 là một đường đi với it=i1 và có ít nhất ba nút khác nhau. Đồ thị vô hướng được gọi là liên thông nếu ứng với mỗi cặp i,j∈N đều có một đường đi từ i đến j.
3.1. Các khái niệm cơ bản 119 Đồ thị G (N,A) là đồ thị có hướng nếu mỗi cung là một cặp có thứ tự. Trong đồ thị có hướng, (i,j) ≠ (j,i). Trong đồ thị có hướng có thể chứa cả hai cung (i,j) và (j,i), nên để xác định một đường đi phải nói rõ cả dãy nút i1,…,it và dãy cung a1,…,at-1. Đồ thị có hướng là liên thông nếu đồ thị vô hướng tương ứng là liên thông. Cây là một đồ thị vô hướng, liên thông và không có chu trình. Cây bao trùm của đồ thị G (N,A) là một cây trong G có chứa tất cả các nút của G còn số cung có thể ít hơn. Do vậy, cây bao trùm là cây Gs (Ns, As) có Ns=N và As⊂ A.
3.2. Bài toán đường ngắn nhất Shortest path problem 120 3.2.1. Đặt vấn đề 3.2.2. Mô tả dạng toán học 3.2.3. Thuật toán đặt nhãn
3.2.1. Đặt vấn đề 121 Công ty ABC có một vài dự án xây dựng nằm khắp nơi trong địa bàn tỉnh. Hàng ngày công ty có nhiều chuyến xe đưa công nhân, chuyên chở thiết bị và vật tư đi lại giữa trụ sở công ty và các công trường xây dựng. Công ty muốn xác định các tuyến đường ngắn nhất nhằm tối thiểu khoảng cách di chuyển từ văn phòng công ty đến các công trường. Các tuyến đường mà phương tiện của công ty đi lại hằng ngày có thể được mô tả bằng sơ đồ mạng như sau:
Mạng tuyến đường di chuyển đến các công trường của công ty ABC 122 7 17 5 2 4 6 15 6 4 1 3 6 10 2 3 5 4
3.2.2. Mô tả dạng toán học của bài toán 123 Cho một đồ thị có hướng G (N,A). Mỗi cung có độ dài cij> 0 và cũng chính là khoảng cách giữa hai nút. Để tìm đường ngắn nhất từ một nút i đến nút k bất kỳ (k∈N) chính là tìm đường ngắn nhất từ nhiều hoặc thậm chí mọi nút khác nút i đến nút k. Vậy, bài toán đường ngắn nhất là bài toán tìm đường ngắn nhất từ mọi nút i∈N đến một nút k∈N cho trước trên đồ thị G(N,A).
3.2.3. Thuật toán đặt nhãn 124 Thuật toán đặt nhãn là thuật toán dựa vào việc đặt nhãn cho các nút để tìm đường ngắn nhất. Nhãn của nút i gồm 2 con số nằm trong dấu ngoặc vuông và được ký hiệu là [c1i, T], trong đó c1i là giá trị khoảng cách từ nút 1 đến nút i, và T là ký hiệu số thứ tự của nút đứng ngay trước nút i theo đường đi từ nút 1 đến nút i. Nút chưa đặt nhãn là nút chưa xác định được đường đi từ nút 1 đến nút đó. Nút đã được đặt nhãn tạm thời là nút đã xác định được một đường đi từ nút 1 đến nút đó. Nút có nhãn cố định khi thuật toán đã xác định được đường đi ngắn nhất từ nút 1 đến nút đó.
3.2.3. Các bước của thuật toán đặt nhãn 125 Bước 1: Đầu tiên, giả sử nút 1 có nhãn cố định [0,S]. Bước 2: Đặt nhãn tạm thời cho các nút liên thông trực tiếp từ nút 1. Gọi N1 là tập các nút có nhãn tạm thời với nút 1. Giả sử nút i ∈ N1 là nút liên thông trực tiếp với nút 1 sẽ có nhãn tạm thời là [c1i, 1]. Tiến hành đặt nhãn cố định cho nút k∈N1 thỏa mãn điều kiện c1k= min {c1i}, i∈N1. Loại nút k ra khỏi nút có nhãn tạm thời.
3.2.3. Các bước… 126 Bước 3: Xét các nút liên thông với nút k: Đặt nhãn tạm thời cho những nút liên thông với nút k và chưa đặt nhãn. Điều chỉnh nhãn tạm thời cho tất cả các nút theo nguyên tắc: giả sử nút j đang xét, liên thông với nút k bằng cung (k,j) thì thay thế giá trị khoảng cách của nhãn nút j bằng min {c1j, c1k + ckj}. Gọi Ntt là tập các nút có nhãn tạm thời. Xét các c1j với ∀j ∈ Ntt giả sử c1m= min {c1j}. Như vậy, đặt nhãn cố định cho nút m. Tiếp tục qui trình này cho đến khi tất cả các nút có nhãn cố định thì kết thúc thuật toán.
3.2.3. Các bước … 127 Bước 4: Xác định khoảng cách ngắn nhất từ nút 1 đến nút bất kỳ. Đường ngắn nhất đến một nút nhất định k có thể tìm bằng cách xuất phát từ nút k và di chuyển ngược về nút ngay trước. Tiếp tục di chuyển ngược chiều qua mạng sẽ tìm thấy đường ngắn nhất từ nút 1 đến nút đang đề cập.
Ứng dụng thuật toán cho mạng công ty ABC 128 Bước 1: Nút 1 có nhãn cố định [0,S] 7 17 5 2 4 6 15 6 [0,S] 4 1 3 6 10 2 5 3 4
Ứng dụng… 129 Bước 2: Tập các nút liên thông với nút 1 là nút 2 và 3. Đặt nhãn tạm thời cho các nút 2, 3 lần lượt là [15,1], [10,1]. Nút 3 [10,1] được đặt nhãn cố định. 7 17 5 [15,1] 2 4 6 15 6 [0,S] 4 1 3 6 10 2 5 [10,1] 3 4
Ứng dụng… 130 Bước 3: Các nút liên thông với nút 3 là 2 và 5. Đặt nhãn tạm thời cho nút 5 [14,3]; Điều chỉnh nhãn tạm thời cho nút 2 thành [13,3]. Đặt nhãn cố định cho nút 2. 7 17 5 2 [13,3] 4 6 15 6 [0,S] 4 1 3 6 10 2 5 [14,3] 3 [10,1] 4
Ứng dụng… 131 Đặt nhãn tạm thời cho nút 4 và 7: 4 [19,2] và 7 [30,2]. Xét tập các nút có nhãn tạm thời, lựa chọn nút có giá trị khoảng cách nhỏ nhất. Nút được lựa chọn là nút 5. 7 17 [30,2] 5 2 [13,3] 4 [19,2] 6 15 6 [0,S] 4 1 3 6 10 2 5 [14,3] 3 [10,1] 4
Ứng dụng… 132 Xét các nút liên thông với nút 5. Đặt nhãn tạm thời cho nút 6 [16,5], Điều chỉnh nhãn tạm thời cho nút 4 [18,5]. Xét 3 nút tạm thời 4,6,7. Nút 6 sẽ được đặt nhãn cố định 7 17 [30,2] 5 2 [13,3] 4 [18,5] 6 15 6 [0,S] 4 1 3 6 [16,5] 10 2 5 [14,3] 3 [10,1] 4
Ứng dụng… 133 Điều chỉnh nhãn tạm thời cho nút 7: [22,6]. Và nút 4 được chọn để đặt nhãn cố định: 4 [18,5]. 7 17 [22,6] 5 2 [13,3] 4 [18,5] 6 15 6 [0,S] 4 1 3 6 [16,5] 10 2 5 [14,3] 3 [10,1] 4
Ứng dụng… 134 Cuối cùng, chỉ có nút 7 liên thông với nút 4. Vì c14+5=18+5=23>22 nên không điều chỉnh nhãn của nút 7. Nút 7 là nút cuối cùng được đặt nhãn cố định. 7 17 [22,6] 5 2 [13,3] 4 [18,5] 6 15 6 [0,S] 4 1 3 6 [16,5] 10 2 5 [14,3] 3 [10,1] 4
3.2.3. Thuật toán đặt nhãn 135 Đường ngắn nhất từ nút 1 đến các nút khác Nút Đường ngắn nhất từ nút 1 Khoảng cách bằng km 2 1-3-2 13 3 1-3 10 4 1-3-5-4 18 5 1-3-5 14 6 1-3-5-6 16 7 1-3-5-6-7 22