Bài giảng Toán kinh tế: Bài toán vận tải

Bài giảng "Toán kinh tế: Bài toán vận tải" được biên soạn với các nội dung chính sau: Bài toán vận tải và các khái niệm, tính chất liên quan; Thuật toán thế vị giải bài toán vận tải; Bài toán vận tải mở rộng. Mời các bạn cùng tham khảo bài giảng!
Nội dung trích xuất từ tài liệu:
Bài giảng Toán kinh tế: Bài toán vận tải BÀI TOÁN VẬN TẢI Lecturer: Phạm Thị Hoài Department of Applied Mathematics - School of Applied Mathematics and Informatics Hanoi University of Science and Technology hoai.phamthi@hust.edu.vn 0 / 21 Content 1 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 Đ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 2 Thuật toán thế vị giải bài toán vận tải Cơ sở lí thuyết Thuật toán thế vị 3 Bài toán vận tải mở rộng hoai.phamthi@hust.edu.vn 1 / 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 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ô hình toán học m X X n min f (x) = cij xij (PT) i=1 j=1 n X vđk. xij = ai , i = 1, ..., m j=1 Xm xij = bj , j = 1, ..., n i=1 xij ≥ 0, i = 1, ..., m; j = 1, ..., n hoai.phamthi@hust.edu.vn 2 / 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 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 Mệnh đề 1: rank A = m + n − 1. Kí hiệu: T = {(i, j) : i ∈ {1, ..., m}, j ∈ {1, ..., n}}; G(x0 ) = {(i, j) ∈ T : x0ij > 0}. 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) hoai.phamthi@hust.edu.vn 5 / 21 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 n P Định lí 1: argmin (VT) 6= ∅ ⇔ ai = bj . i=1 j=1 Chứng minh: in class Ví dụ: Cho bài toán vận tải có   8 2 5 4 7 5 6 8 a = (80, 110, 90, 440); b = (85, 75, 280, 280); c =  1  3 7 5 0 2 3 1   0 75 5 0 0 0 110 0  Hỏi bài toán có nghiệm hay không? Điểm X 0 =  85 0  có phải là một phương án 5 0  0 0 160 280 chấp nhận được của bài toán hay không? hoai.phamthi@hust.edu.vn 6 / 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 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: 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 hoai.phamthi@hust.edu.vn 7 / 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 Đị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 ...