BÀI TOÁN VẬN TẢI
Department of Applied Mathematics - School of Applied Mathematics and Informatics Hanoi University of Science and Technology
hoai.phamthi@hust.edu.vn
0 / 21
hoai.phamthi@hust.edu.vn
Lecturer: Phạm Thị Hoài
Content
1 Bài toán vận tải và các khái niệm, tính chất liên quan
2 Thuật toán thế vị giải bài toán vận tải
Mô hình bài toán vận tải Điều kiện tồn tại nghiệm Chu trình và phương án cực biên của bài toán vận tải
3 Bài toán vận tải mở rộng
hoai.phamthi@hust.edu.vn
1 / 21
Cơ sở lí thuyết Thuật toán thế vị
Bài toán vận tải và các khái niệm, tính chất liên quan Mô hình bài toán vận tải
Bài toán vận tải
Kế hoạch: Cần phát hàng từ m kho {K1, ..., Km} đến n cửa hàng {H1, ..., Hn}. Dữ kiện:
Lượng hàng cần phát từ kho Ki là ai; cửa hàng Hj cần nhập lượng hàng là bj. Chi phí vận chuyển 1 đơn vị hàng từ kho Ki đến cửa hàng Hj là cij.
Yêu cầu: ? cần chuyển bao nhiêu hàng từ kho Ki đến cửa hàng Hj để tổng chi phí vận chuyển ít nhất?
m X
n X
Mô hình toán học
i=1
j=1
n X
(PT) min f (x) = cijxij
j=1 m X
vđk. xij = ai, i = 1, ..., m
i=1 xij ≥ 0, i = 1, ..., m; j = 1, ..., n
hoai.phamthi@hust.edu.vn
2 / 21
xij = bj, j = 1, ..., n
Bài toán vận tải và các khái niệm, tính chất liên quan Mô hình bài toán vận tải
hoai.phamthi@hust.edu.vn
3 / 21
Bài toán vận tải và các khái niệm, tính chất liên quan Mô hình bài toán vận tải
hoai.phamthi@hust.edu.vn
4 / 21
Bài toán vận tải và các khái niệm, tính chất liên quan Mô hình bài toán vận tải
ij > 0}.
Mệnh đề 1: rank A = m + n − 1.
hoai.phamthi@hust.edu.vn
5 / 21
Kí hiệu: T = {(i, j) : i ∈ {1, ..., m}, j ∈ {1, ..., n}}; G(x0) = {(i, j) ∈ T : x0 x0 là pacb không suy biến ⇔ |G(x0)| = m + n − 1. Bảng vận tải của bài toán (PT)
Bài toán vận tải và các khái niệm, tính chất liên quan Điều kiện tồn tại nghiệm
m P i=1
n P j=1
Định lí 1: argmin (VT) 6= ∅ ⇔ ai = bj.
Chứng minh: in class
Ví dụ: Cho bài toán vận tải có
a = (80, 110, 90, 440); b = (85, 75, 280, 280); c = 8 7 1 0 2 5 3 2 5 6 7 3 4 8 5 1
hoai.phamthi@hust.edu.vn
6 / 21
Hỏi bài toán có nghiệm hay không? Điểm X 0 = có phải là một phương án 0 0 85 0 75 0 0 0 5 110 5 160 0 0 0 280 chấp nhận được của bài toán hay không?
Bài toán vận tải và các khái niệm, tính chất liên quan Chu trình và phương án cực biên của bài toán vận tải
Chu trình: Một tập sắp thứ tự của bảng vận tải được gọi là chu trình nếu nó thỏa mãn:
hoai.phamthi@hust.edu.vn
7 / 21
Hai ô cạnh nhau nằm trong cùng một hàng hay một cột; Không có ba ô nằm trong cùng một hàng hay một cột; Ô đầu tiên nằm trong cùng một hàng hay một cột với ô cuối cùng.
Chú ý: Nếu K ⊂ T thỏa mãn tính chất: trên mỗi hàng, mỗi cột của bảng vận tải không chứa ô nào của K hoặc chứa ít nhất hai ô của K thì K chứa chu trình.
Bài toán vận tải và các khái niệm, tính chất liên quan Chu trình và phương án cực biên của bài toán vận tải
Định lí 2: Cho tập các ô K ⊂ T. Khi đó {Aij : (i, j) ∈ K} độc lập tuyến tính khi và chỉ khi K không chứa chu trình.
Hệ quả 1: x0 là pacb ⇔ G(x0) không chứa chu trình. Hệ quả 2: Nếu K ⊂ T, |K| ≥ m + n, m ≥ 2, n ≥ 2 thì K chứa chu trình. Hệ quả 3: Nếu K ⊂ T, |K| = m + n − 1 và (i0, j0) /∈ K. K ko chứa chu trình. Khi đó K ∪ {(i0, j0)} sẽ chứa một chu trình duy nhất.
Ví dụ: Cho bài toán vận tải có
a = (50, 70, 41); b = (30, 60, 46, 25); c = 4 5 8 7 9 2 12 6 9 7 1 1
hoai.phamthi@hust.edu.vn
8 / 21
Hỏi bài toán có nghiệm hay không? Điểm X 0 = có phải là một pacb của bài 30 19 0 0 41 0 1 45 0 0 25 0 toán hay không?
Bài toán vận tải và các khái niệm, tính chất liên quan Chu trình và phương án cực biên của bài toán vận tải
Cách tìm 1 pacb của bài toán vận tải
Phương pháp góc tây bắc Phương pháp cực tiểu chi phí
Ví dụ:
Phương pháp góc tây bắc
Hình 1: Phương pháp góc tây bắc- Bảng 1, 2
hoai.phamthi@hust.edu.vn
9 / 21
Bài toán vận tải và các khái niệm, tính chất liên quan Chu trình và phương án cực biên của bài toán vận tải
Phương pháp góc tây bắc
Hình 2: Phương pháp góc tây bắc- Bảng 3, 4, 5, 6
hoai.phamthi@hust.edu.vn
10 / 21
Bài toán vận tải và các khái niệm, tính chất liên quan Chu trình và phương án cực biên của bài toán vận tải
Phương pháp góc tây bắc
Hình 3: Phương pháp góc tây bắc- Bảng 7, 8, 9, 10
hoai.phamthi@hust.edu.vn
11 / 21
Bài toán vận tải và các khái niệm, tính chất liên quan Chu trình và phương án cực biên của bài toán vận tải
Phương pháp góc tây bắc
Hình 4: Phương pháp góc tây bắc- Bảng 11, 12
Phương pháp cực tiểu chi phí
Hình 5: Phương pháp cực tiểu chi phí- Bảng 1, 2
hoai.phamthi@hust.edu.vn
12 / 21
Bài toán vận tải và các khái niệm, tính chất liên quan Chu trình và phương án cực biên của bài toán vận tải
Phương pháp cực tiểu chi phí
Hình 6: Minh họa phương pháp cực tiểu chi phí- Bảng 3, 4, 5, 6
hoai.phamthi@hust.edu.vn
13 / 21
Bài toán vận tải và các khái niệm, tính chất liên quan Chu trình và phương án cực biên của bài toán vận tải
Phương pháp cực tiểu chi phí
Hình 7: Minh họa phương pháp cực tiểu chi phí- Bảng 7
hoai.phamthi@hust.edu.vn
14 / 21
Thuật toán thế vị giải bài toán vận tải Cơ sở lí thuyết
Định lí 3: Cho x0 là một phương án chấp nhận được của bài toán (PT). Khi đó x0 là nghiệm tối ưu của (PT) khi và chỉ khi
∃ u1, ..., um; v1, ..., vn ∈ R thỏa ui + vj ≤ cij∀(i, j) ∈ T và ui + vj = cij∀(i, j) ∈ G(x0).
Chú ý: Giả sử x0 là pacb ksb. Khi đó
{Aij : (i, j) ∈ G(x0)} độc lập tuyến tính; G(x0) ko chứa chu trình; |G(x0)| = m + n − 1.
Khi đó hệ ui + vj = cij ∀(i, j) ∈ G(x0) có m + n − 1 phương trình và m + n ẩn và do đó có vô số nghiệm. Quy ước: Gán u1 = 0, từ đó tính được u2, ..., um; v1, ..., vn và bộ số này xác định duy nhất.
hoai.phamthi@hust.edu.vn
15 / 21
Bộ số u1, u2, ..., um; v1, ..., vn được gọi là các thế vị tương ứng với pacb x0. Kí hiệu ∆ij = ui + vj − cij ∀(i, j) ∈ T. Khi đó ( x0 ∈ argmin (P T ) ⇔ ∆ij ≤ 0 ∀(i, j) ∈ T ∆ij = 0 ∀(i, j) ∈ G(x0)
Thuật toán thế vị giải bài toán vận tải Cơ sở lí thuyết
Ví dụ: Xác định pacb của các bài toán dưới đây; kiểm tra tính tối ưu của các pacb tìm được? 25 30 60 46 bj
(i)
ai 50 70 41 4 5 8 7 9 2 12 6 9 7 1 2
60 30 40 70 bj
(ii)
ai 50 70 80 2 3 1 4 6 2 5 4 5 1 8 3
60 60 20 10 bj
(iii)
hoai.phamthi@hust.edu.vn
16 / 21
ai 10 20 30 40 50 10 13 4 14 3 20 9 15 7 12 17 12 6 1 5 16 8 9 0 19
Thuật toán thế vị giải bài toán vận tải Cơ sở lí thuyết
Định lí 4: Giả sử biết x0 là 1 pacb ksb của bài toán (PT) có bộ thế vị tương ứng u1, ...., um; v1, ..., vn. Nếu tồn tại (ik, jk) /∈ G(x0) sao cho ∆ikjk > 0 thì ta tìm được pacb x1 tốt hơn x0, tức là f (x1) < f (x0).
Chứng minh: in class
Tập ô G(x0) ∪ (ik, jk) chứa duy nhất một chu trình K. Xuất phát từ ô (ik, jk)+ ∈ K, đánh dấu ô tiếp theo dấu (−), ...
K + = {(i, j) ∈ K : đánh dấu +}, K − = {(i, j) ∈ K : đánh dấu −} ⊂ G(x0).
ij : (i, j) ∈ K −} = x0
irjr
Kí hiệu θ = min{x0 > 0. Xây dựng x1 như sau:
x1 ij = nếu (i, j) ∈ K + nếu (i, j) ∈ K − nếu (i, j) /∈ K x0 ij + θ, x0 ij − θ, x0 ij,
hoai.phamthi@hust.edu.vn
17 / 21
f (x1) = f (x0) − θ∆ikjk
Thuật toán thế vị giải bài toán vận tải Thuật toán thế vị
Sơ đồ khối thuật toán thế vị
Tìm pacb xuất phát x0 ∆ij = ui + vj − cij ∀ (i, j) ∈ G (cid:0)x0(cid:1) Tính bộ thế vị tương ứng u1, ..., um; v1, ..., vn
chuyển bảng mới
Sai (is, js) := argmax (cid:8)∆ij > 0 : (i, j) ∈ G (cid:0)x0(cid:1)(cid:9) ∆ij ≥ 0 ∀ (i, j) ∈ G (cid:0)x0(cid:1)
Đúng XĐ chu trình điều chỉnh K xuất phát từ (is, js)+
1 j =
j + θ; (i, j) ∈ K + 0 j − θ; (i, j) ∈ K − 0 0 j ; (i, j) /∈ K
hoai.phamthi@hust.edu.vn
18 / 21
STOP Kết luận x0 là nghiệm tối ưu xi x0 := x1 xi xi xi
Thuật toán thế vị giải bài toán vận tải Thuật toán thế vị
Nhận xét: Nếu bài toán vận tải ksb thì thuật toán thế vị dừng sau hữu hạn bước lặp.
Nếu lượng phát và lượng thu đều là số nguyên thì nghiệm tối ưu thu được cũng gồm toàn số nguyên. Nếu tại nghiệm tối ưu x0 : ∆ij < 0 ∀(i, j) /∈ G(x0) thì nghiệm tối ưu này là duy nhất. Ngược lại, bài toán có nghiệm tối ưu khác ngoài x0. Tương tự như thuật toán đơn hình, pacb suy biến xuất hiện nếu
θ = 0 : Vẫn thực hiện thuật toán như bình thường, kết quả điều chỉnh không thay đổi pacb nhưng thay đổi hệ vecto cơ sở ứng với pacb. θ đạt được tại nhiều ô khác nhau. Khi đó ta sẽ loại ngẫu nhiên một ô trong đó.
hoai.phamthi@hust.edu.vn
19 / 21
Thuật toán thế vị giải bài toán vận tải Thuật toán thế vị
Giải các ví dụ trước bằng thuật toán thế vị. v2 = 7 v3 = 12 v1 = 4 v4 = 7
bj 46 60 25 30 ai
12 7 7 4 u1 = 0 50 +
30 19 0 1 6 9 5 1 + u2 = −6 70
-8 -7 45 25
30 30 30 30
+ u3 = −5 41
hoai.phamthi@hust.edu.vn
20 / 21
41 1 -9 -2
Bài toán vận tải mở rộng
Bài toán vận tải mở rộng: Bài toán không cân bằng thu phát Bài toán vận tải với ràng buộc bất đẳng thức Bài toán lập kho nhận hàng Bài toán vận tải có ô cấm
hoai.phamthi@hust.edu.vn
21 / 21
Bài toán vận tải dạng max Bài toán phân việc Tự đọc!
