Bài toán quy hoạch tuyến tính chương 4

Nội dung Text: Bài giảng Quy hoạch tuyến tính - Chương 4: Bài toán vận tải (ĐH Tôn Đức Thắng)

1. Chương 4 BÀI TOÁN VẬN TẢI 20/6/2012 MaMH: C01019 Chương 4: Bài toán vận tải 1
2. 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 MaMH: C01019 Chương 4: Bài toán vận tải 2
3. 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 S i , với lượng phát tương ứng ai , i = 1,..., m; phát hàng đến n điểm thu T j , với lượng thu tương ứng b j , j = 1,..., n. Si : ai → xij cij Tj : bj với: cij là cước phí vận chuyển 1 đơn vị hàng từ điểm phát S i , i = 1,..., m đến điểm thu T j , j = 1,..., n xij là lượng hàng được vận chuyển từ S i đến Tj , i = 1,..., m; j = 1,..., n. 20/6/2012 MaMH: C01019 Chương 4: Bài toán vận tải 3
4. 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 MaMH: C01019 Chương 4: Bài toán vận tải 4
5. Bài toán vận tải dạng tổng quát Mô hình bài toán có dạng: n m f(X) = ∑∑c j =1 i =1 ij x ij → min  n  ∑ x ij = ai , i = 1,..., m  j =1  m  ∑ x ij = b j , j = 1,..., n  i =1  x ij ≥ 0, i = 1,..., m ; j = 1,..., n   20/6/2012 MaMH: C01019 Chương 4: Bài toán vận tải 5
6. 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: m n ∑a i =1 i = ∑b j =1 j 20/6/2012 MaMH: C01019 Chương 4: Bài toán vận tải 6
7. 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 Thu T1 : b1 ... Tj : bj ... Tn : bn Phát c11 c1j c1n S1 : a1 x11 x1j x1n ⋮ ... ... ci1 cij cin Si : ai xi 1 xij xin ⋮ ... ... cm1 cmj cmn Sm : am x m1 xmj xmn 20/6/2012 MaMH: C01019 Chương 4: Bài toán vận tải 7
8. 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 MaMH: C01019 Chương 4: Bài toán vận tải 8
9. Bài toán vận tải dạng tổng quát Định nghĩa 2 Những ô có x ij > 0 được gọi là ô chọn, những ô còn lại được gọi là ô loại. Đị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 MaMH: C01019 Chương 4: Bài toán vận tải 9
10. 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 ≤ (m + n − 1) ). iii. Với PACB có đủ (m + n − 1) ô 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 MaMH: C01019 Chương 4: Bài toán vận tải 10
11. Thuật toán thế vị 1. Tiêu chuẩn tối ưu Xét BTVT cân bằng thu phát m n f (x) = ∑∑c i =1 j =1 ij x ij → min  n  ∑ x ij = ai , i = 1,..., m  j =1 m  ∑ x ij = b j , j = 1,..., n  i =1  x ij ≥ 0, i = 1,..., m ; j = 1,..., n   20/6/2012 MaMH: C01019 Chương 4: Bài toán vận tải 11
12. Thuật toán thế vị Bài toán đối ngẫu của bài toán trên: m n g (u,v ) = ∑ ai ui + ∑ b j v j → max i =1 j =1 ui + v j ≤ cij , i = 1, m; j = 1, n. 20/6/2012 MaMH: C01019 Chương 4: Bài toán vận tải 12
13. Thuật toán thế vị Định lý 1 PA X = ( xij ) của BTVT là PATƯ khi và chỉ khi tìm được các số ui ,v j , i = 1, m; j = 1, n thỏa mãn: ui + v j ≤ cij , ∀(i , j )  ui + v j = cij , ∀(i , j ) ∈ G( X ), G( X ) = {(i , j ) : xij > 0} 20/6/2012 MaMH: C01019 Chương 4: Bài toán vận tải 13
14. 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 X 0 = ( xij0 ) theo nguyên tắc phân phối tối đa: 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à xij = min{ai , b j } Sau đó, điều chỉnh lại các yêu cầu: ai′ = ai − xij  b′j = b j − xij 20/6/2012 MaMH: C01019 Chương 4: Bài toán vận tải 14
15. Thuật toán thế vị • Nếu ai′ = 0 , thì loại dòng i. • Nếu b′j = 0 , thì loại cột j. • Nếu ai′ = b′j = 0 , thì loại cả dòng i và cột j. 20/6/2012 MaMH: C01019 Chương 4: Bài toán vận tải 15
16. Thuật toán thế vị x Ví dụ 1 19 bj ai 30 60 46 25 50 4 7 12 7 51 70 5 9 6 1 19 x 41 8 2 9 1 41 20/6/2012 MaMH: C01019 Chương 4: Bài toán vận tải 16
17. 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ó xij > 0, những ô còn lại có xij = 0. 20/6/2012 MaMH: C01019 Chương 4: Bài toán vận tải 17
18. 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 MaMH: C01019 Chương 4: Bài toán vận tải 18
19. Thuật toán thế vị Nếu PACB tìm được có đủ ( m + n − 1) ô chọn, thì sang Bước 2. Ngược lại, thêm vào ô (i , j ) nào đó một lượng hàng xij = 0 sao cho: • đủ số ( m + n − 1) • và ô (i , j ) này không tạo thành chu trình với các ô chọn. → Bước 2. 20/6/2012 MaMH: C01019 Chương 4: Bài toán vận tải 19
20. Thuật toán thế vị - Bước 2 (Bước lặp) Ở đầu bước lặp đã có PACB đủ ( m + n − 1) ô chọn. i. Xác định các thế vị ui ,v j , i = 1, m ; j = 1, n ui + v j = cij , ∀(i , j ) ∈ G( X ) Chọn u1 = 0. ii. Tính các ước lượng theo công thức: ∆ ij = ui + v j − cij , ∀(i , j ) 20/6/2012 MaMH: C01019 Chương 4: Bài toán vận tải 20