tailieunhanh - Bài giảng Quy hoạch tuyến tính: Chương 3 - Nguyễn Hoàng Tuấn

Bài giảng Quy hoạch tuyến tính: Chương 3 Bài toán vận tải, cung cấp cho người học những kiến thức như: Bài toán cân bằng; phương án cực biên; thuật toán thế vị; một số trường hợp đặc biệt. Mời các bạn cùng tham khảo! | QUY HOẠCH TUYẾN TÍNH CHƯƠNG 3. BÀI TOÁN VẬN TẢI CHƯƠNG 3. BÀI TOÁN VẬN TẢI 1 Bài toán cân bằng 2 Phương án cực biên 3 Thuật toán thế vị 4 Một số trường hợp đặc biệt 1. BÀI TOÁN VẬN TẢI CÂN BẰNG THU PHÁT . Lập mô hình bài toán Có một loại hàng cần được chuyên chở từ hai kho trạm phát P1 và P2 tới ba nơi tiêu thụ trạm thu T1 T2 T3 . Lượng hàng có ở hai kho và lượng hàng cần ở ba nơi tiêu thụ cũng như số tiền vận chuyển một đơn vị hàng từ mỗi kho đến các nơi tiêu thụ được cho ở bảng sau 1. BÀI TOÁN VẬN TẢI CÂN BẰNG THU PHÁT THU T1 T2 T3 35 tấn 25 tấn 45 tấn PHÁT P1 5 2 3 30 tấn P2 2 1 1 75 tấn Tìm phương án vận chuyển thỏa yêu cầu về thu phát sao cho chi phí vận chuyển bé nhất. Nguyễn Hoàng Tuấn soạn thảo 1 QUY HOẠCH TUYẾN TÍNH CHƯƠNG 3. BÀI TOÁN VẬN TẢI 1. BÀI TOÁN VẬN TẢI CÂN BẰNG THU PHÁT . Bài toán cân bằng Giả sử có m kho là nơi phát hay cung cấp hàng hoá kho thứ i chứa ai đơn vị hàng hoá i 1 2 . m có n nơi tiêu thụ hay nhận hàng hoá nơi nhận thứ j cần bj đơn vị hàng hoá j 1 2 . n . Giá tiền hay cước phí vận chuyển một đơn vị hàng hóa từ kho thứ i đến nơi nhận thứ j là cij đơn vị tiền tệ. Bài toán được gọi là cân bằng nếu tổng lượng m n phát tổng lượng thu ai b j i 1 j 1 1. BÀI TOÁN VẬN TẢI CÂN BẰNG THU PHÁT Bài toán vận tải thường cho dưới dạng bảng sau Thu b1 b2 bj . bn Phát a1 c11 c12 c1 j c1n a2 c21 c22 c2 j c2n ai ci 1 ci 2 cij cin am cm 1 cm 2 cmj cmn Yêu cầu bài toán tìm cách phân bổ lượng hàng vận chuyển xij từ trạm phát i đến trạm thu j thỏa 1. BÀI TOÁN VẬN TẢI CÂN BẰNG THU PHÁT Tổng chi phí vận chuyển thấp nhất m n f cij xij min i 1 j 1 Tổng lượng hàng phát đi xij ai i 1 m n j 1 Tổng lượng hàng nhận về xij b j j 1 n m i 1 Một phương án bài toán bộ xij thỏa và có dạng ma trận nên cũng gọi là ma trận phương án. Nguyễn Hoàng Tuấn soạn thảo 2 QUY HOẠCH TUYẾN TÍNH CHƯƠNG 3. BÀI TOÁN VẬN TẢI 1. BÀI TOÁN VẬN TẢI CÂN BẰNG THU PHÁT Ví dụ Xét lại bài toán vận tải đã biết ở trên THU T1 T2 T3 35 tấn 25 tấn 45 tấn PHÁT P1 5 2 3 30 tấn P2 2