tailieunhanh - 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! | 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 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 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 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 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 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 gt 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 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 6 21 Bài toán vận tải và các khái niệm tính chất liên quan