tailieunhanh - Bài giảng Quy hoạch tuyến tính - Chương 3: Bài toán vận tải

Mời các bạn tham khảo Bài giảng Quy hoạch tuyến tính - Chương 3: Bài toán vận tải sau đây để cung cấp cho các bạn những kiến thức về bài toán vận tải cân bằng thu phát, phương án cực biên, thuật toán thế vị, một số trường hợp đặc biệt. | 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 PHÁT P1 30 tấn P2 75 tấn T1 35 tấn T2 25 tấn T3 45 tấn 5 2 3 2 1 1 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 n xij ai i 1, m () Tổng lượng hàng nhận về m xij b j j 1, n () j 1 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. .