Chương 4 Bài toán vận tải

Chương 4 BÀI TOÁN VẬN TẢI 20/6/2012 1MaMH: C01019 Chương 4: Bài toán vận tải NỘI DUNG 1. Bài toán vận tải dạng tổng quát 1.1 Phát biểu bài toán vận tải (BTVT) 1.2 Đặt bài toán vận tải dưới dạng bảng 1.3 Các tính chất của bài toán vận tải 2. Thuật toán thế vị 2.1 Tiêu chuẩn tối ưu 2.2 Thuật toán 3. Các trường hợp đặc biệt của BTVT 20/6/2012 2MaMH: C01019 Chương 4: Bài toán vận tải Bài toán vận tải dạng tổng quát 1. Phát biểu bài toán Có m điểm phát với lượng phát tương ứng phát hàng đến n điểm thu với lượng thu tương ứng x ,iS , 1,..., ;ia i m= ,jT , 1,..., .jb j n= với: là cước phí vận chuyển 1 đơn vị hàng từ điểm phát đến điểm thu là lượng hàng được vận chuyển từ đến 20/6/2012 3MaMH: C01019 Chương 4: Bài toán vận tải : :ij iji i j jcS a T b→ ijc , 1,...,iS i m= , 1,...,jT j n= ijx iS 1,..., ; 1,..., .i m j n= = ,jT Bài toán vận tải dạng tổng quát Vấn đề: Lập kế hoạch vận chuyển như thế nào để tổng cước phí vận chuyển là bé nhất? Biết rằng hàng hóa có thể vận chuyển từ một điểm phát bất kỳ đến một điểm thu bất kỳ. 20/6/2012 4MaMH: C01019 Chương 4: Bài toán vận tải Bài toán vận tải dạng tổng quát Mô hình bài toán có dạng: 1 1 ( ) min , 1,..., n m ij ij j i n f X c x x a i m = = = →  = = ∑∑ ∑ 20/6/2012 5MaMH: C01019 Chương 4: Bài toán vận tải 1 1 , 1,..., 0, 1,..., ; 1,..., ij i j m ij j i ij x b j n x i m j n = =    = =   ≥ = =   ∑ Bài toán vận tải dạng tổng quát Điều kiện cân bằng thu phát: 1 1 m n i j i j a b = = =∑ ∑ 20/6/2012 6MaMH: C01019 Chương 4: Bài toán vận tải Bài toán vận tải dạng tổng quát 2. Đặt bài toán dưới dạng bảng T1 : b1 Tj : bj Tn : bn S1 : a1 c11 c1j c1n Thu Phát ... ... 11x 1 jx 1nx 20/6/2012 7MaMH: C01019 Chương 4: Bài toán vận tải Si : ai ci1 cij cin Sm : am cm1 cmj cmn ⋮ ⋮ ...... ...... 1ix ijx inx 1mx mjx mnx Bài toán vận tải dạng tổng quát Định nghĩa 1 Một tập hợp các ô thỏa mãn tính chất: • 2 ô liên tiếp cùng nằm trên cùng 1 hàng hay 1 cột; • 3 ô liên tiếp không cùng nằm trên cùng 1 hàng hay 1 cột được gọi là một dây chuyền. Một dây chuyền khép kín được gọi là một chu trình. 20/6/2012 8MaMH: C01019 Chương 4: Bài toán vận tải Bài toán vận tải dạng tổng quát Định nghĩa 2 Những ô có được gọi là ô chọn, những ô còn lại được gọi là ô loại. 0ijx > Định nghĩa 3 Một phương án (PA) mà các ô chọn không tạo thành chu trình đgl PA cơ bản (PACB). Một PACB đủ (m + n – 1) ô chọn đgl PACB không suy biến. 20/6/2012 9MaMH: C01019 Chương 4: Bài toán vận tải Bài toán vận tải dạng tổng quát 3. Các tính chất của BTVT i. BTVT cân bằng thu phát luôn luôn có PATƯ. ii. Trong 1 PACB bất kỳ, tổng số ô chọn luôn nhỏ hơn hoặc bằng tổng số điểm phát và thu trừ đi 1. (Số ô chọn ). iii. Với PACB có đủ ô chọn, thì với 1 ô loại bất kỳ sẽ tạo thành một chu trình duy nhất với một số ô chọn. 20/6/2012 10MaMH: C01019 Chương 4: Bài toán vận tải ( 1)m n≤ + − ( 1)m n+ − Thuật toán thế vị 1. Tiêu chuẩn tối ưu Xét BTVT cân bằng thu phát 1 1 ( ) min m n ij ij i j f x c x = = = →∑∑ 20/6/2012 11MaMH: C01019 Chương 4: Bài toán vận tải 1 1 , 1,..., , 1,..., 0, 1,..., ; 1,..., n ij i j m ij j i ij x a i m x b j n x i m j n = =  = =   = =   ≥ = =   ∑ ∑ Thuật toán thế vị Bài toán đối ngẫu của bài toán trên: 1 1 ( , ) max , 1, ; 1, . m n i i j j i j i j ij g u v a u b v i mu v c j n = = = + → = =+ ≤ ∑ ∑ 20/6/2012 12MaMH: C01019 Chương 4: Bài toán vận tải Thuật toán thế vị Định lý 1 PA của BTVT là PATƯ khi và chỉ khi tìm được các số thỏa mãn: ( )ijX x= , , 1, ; 1,i ju v i m j n= = , ( , )u v c i j+ ≤ ∀ 20/6/2012 13MaMH: C01019 Chương 4: Bài toán vận tải , ( , ) ( ), ( ) {( , ) : 0} i j ij i j ij ij u v c i j G X G X i j x  + = ∀ ∈ = > Thuật toán thế vị 2. Thuật toán thế vị - Bước 1 (Bước khởi tạo) Tìm PACB xuất phát theo nguyên tắc phân phối tối đa: 0 0( )ijX x= Giả sử cần phân phối cho ô (i,j). Lượng hàng tối đa có thể phân phối là Sau đó, điều chỉnh lại các yêu cầu: 20/6/2012 14MaMH: C01019 Chương 4: Bài toán vận tải min{ , }ij i jx a b= i i ij j j ij a a x b b x ′ = −  ′ = − Thuật toán thế vị • Nếu , thì loại dòng i. • Nếu , thì loại cột j. • Nếu , thì loại cả dòng i và cột j. 0ia′ = 0jb′ = 0i ja b′ ′= = 20/6/2012 15MaMH: C01019 Chương 4: Bài toán vận tải Thuật toán thế vị Ví dụ 1 30 60 46 25 50 4 7 12 7 bj ai 19 x 20/6/2012 16MaMH: C01019 Chương 4: Bài toán vận tải 70 5 9 6 1 41 8 2 9 1 41 x 19 51 Thuật toán thế vị Ta được bảng mới thu gọn. Lặp lại hai phép toán trên với bảng mới thu gọn đến khi yêu cầu của điểm phát và điểm thu được thỏa mãn. Các ô được phân phối có những ô còn lại có 20/6/2012 17MaMH: C01019 Chương 4: Bài toán vận tải 0,ijx > 0.ijx = Thuật toán thế vị Dựa vào nguyên tắc phân phối tối đa và cách thức chọn ô ưu tiên phân phối, xét 3 phương pháp: i. Phương pháp góc Tây Bắc: ô đầu tiên được chọn để phân phối là ô ở vị trí góc Tây Bắc (ô (1,1)). ii. Phương pháp cực tiểu cước phí: ô đầu tiên được chọn để phân phối là ô có cước phí bé nhất. iii. Phương pháp Fogel: trên mỗi hàng, cột chọn ra hai ô có cước phí bé nhất (bé nhì), lấy hiệu số của chúng. Ô có cước phí bé nhất tương ứng ở hàng, cột có hiệu số lớn nhất sẽ là ô đầu tiên được chọn để phân phối. 20/6/2012 18MaMH: C01019 Chương 4: Bài toán vận tải Thuật toán thế vị Nếu PACB tìm được có đủ ô chọn, thì sang Bước 2. Ngược lại, thêm vào ô nào đó một lượng hàng sao cho: ( 1)m n+ − ( , )i j 0ijx = • đủ số • và ô này không tạo thành chu trình với các ô chọn. → Bước 2. 20/6/2012 19MaMH: C01019 Chương 4: Bài toán vận tải ( 1)m n+ − ( , )i j Thuật toán thế vị - Bước 2 (Bước lặp) Ở đầu bước lặp đã có PACB đủ ô chọn. i. Xác định các thế vị ( 1)m n+ − , , 1, ; 1,i ju v i m j n= = , ( , ) ( )i j iju v c i j G X+ = ∀ ∈ Chọn u1 = 0. ii. Tính các ước lượng theo công thức: 20/6/2012 20MaMH: C01019 Chương 4: Bài toán vận tải , ( , )ij i j iju v c i j∆ = + − ∀ Thuật toán thế vị iii. Kiểm tra tiêu chuẩn tối ưu Nếu thì PA đang xét là PATƯ. Ngược lại, chuyển sang iv. iv. Chọn ô là ô có ước lượng dương lớn nhất: 0, ( , )ij i j∆ ≤ ∀ * *( , )i j Khi đó, ô sẽ tạo nên một chu trình duy nhất với một số ô chọn. → Ô sẽ là ô chọn ở bảng mới. 20/6/2012 21MaMH: C01019 Chương 4: Bài toán vận tải * * max{ : 0}ij iji j∆ = ∆ ∆ > * *( , )i j * *( , )i j Thuật toán thế vị Đặt tên chu trình là K. Đánh dấu +, - xen kẽ vào các ô thuộc K, bắt đầu từ ô mang dấu +. Đặt : = { những ô mang dấu +} * *( , )i j K + = { những ô mang dấu -} 20/6/2012 22MaMH: C01019 Chương 4: Bài toán vận tải K − Thuật toán thế vị Tiến hành điều chỉnh PA ta có PA mới với ( ),ijX x= ( ),ijX x= ( , ) , ( , ) , ijx i j K x x i j Kθ +  ∉  = + ∈ trong đó, → Ô là ô loại ở bảng mới. Thay X bởi và lặp lại Bước lặp. 20/6/2012 23MaMH: C01019 Chương 4: Bài toán vận tải ( , ) , ij ij ijx i j Kθ −  − ∈ 0 0 min{ : ( , ) }i j ijx x i j Kθ −= = ∈ 0 0( , )i j X Thuật toán thế vị 30 60 46 25 50 4 7 12 7 30 20 ai bj u1= 0 -8 -1 20/6/2012 24MaMH: C01019 Chương 4: Bài toán vận tải 70 5 9 6 1 41 8 2 9 1 16 24 25+ - - + v2= 7 u2= 2 v3= 4 u3= -5 v4= 6v1= 4 1 -9 -10 746 24θ = Thuật toán thế vị Ví dụ 2 (tt) 30 60 46 25 50 4 7 12 7 30 20 ai bj u1= 0 -1 -1 20/6/2012 25MaMH: C01019 Chương 4: Bài toán vận tải 70 5 9 6 1 41 8 2 9 1 2446 1 v2= 7 u2= -5 v3= 11 u3= -5 v4= 6v1= 4 -6 -9 -3 -7 40 Thuật toán thế vị Vì nên PATƯ 0, ( , )ij i j∆ ≤ ∀ * 30 20 0 0 0 0 46 24 0 40 0 1 X     =       Giá trị tối ưu: 20/6/2012 26MaMH: C01019 Chương 4: Bài toán vận tải *( ) 4 30 7 20 6 46 24 2 40 1 641. f X = × + × + × + + × + = Các trường hợp đặc biệt của BTVT i. BTVT không cân bằng thu phát a. Phát > Thu: 1 1 m n i j i j a b = = >∑ ∑ → Đưa về BTVT cân bằng thu phát → Thêm một điểm thu giả, lượng hàng tương ứng 20/6/2012 27MaMH: C01019 Chương 4: Bài toán vận tải 1 1 1 ; m n n i j i j b a b+ = = = −∑ ∑ ( 1) 0, 1 .,i nc i m+ = ∀ = Các trường hợp đặc biệt của BTVT b. Phát < Thu → Đưa về BTVT cân bằng thu phát 1 1 m n i j i j a b = = <∑ ∑ → Thêm một điểm phát giả, lượng hàng tương ứng 20/6/2012 28MaMH: C01019 Chương 4: Bài toán vận tải 1 1 1 ; n m m j i j i a b a+ = = = −∑ ∑ ( 1) 0, 1 .,m jc j n+ = ∀ = Các trường hợp đặc biệt của BTVT ii. BTVT có ô cấm Ô cấm: ô không được nhận hàng. Giả sử ô là ô cấm. → Thay , với là số dương rất lớn. ( , )i j ijc M= M 20/6/2012 29MaMH: C01019 Chương 4: Bài toán vận tải Các trường hợp đặc biệt của BTVT iii. “BTVT” với hàm mục tiêu cực đại Có mô hình giống BTVT, nhưng hàm mục tiêu cực đại. • Dấu hiệu tối ưu: 0, ( , )ij i j∆ ≥ ∀ • Chọn ô • Nếu có ô cấm , thay , với là số dương rất lớn. • Chọn ô có lớn nhất phân phối trước. 20/6/2012 30MaMH: C01019 Chương 4: Bài toán vận tải * *( , )i j * * min{ : 0}ij iji j∆ = ∆ ∆ < ( , )i j ijc M= − M ijc