tailieunhanh - Chương 3: Bài toán vận tải - bài 2

Tham khảo tài liệu 'chương 3: bài toán vận tải - bài 2', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | CHƯƠNG 3- BÀI toán Vận Tài BÀI 2. LẬP PACB xuất phát KHONG suy biến chương 3- BÀI toán Vận tài BÀI 2. LẬP PACB xuất phát KHONG suy biến Qui ước Nếuô i j có xij q 0 thì ta nói ô đó đượcphânphốimộtlượng hàng q. Khi phân phốitối đavào mộtô ta phân phốimộtlượng hàng lớnnhất mà ô đócóthể nhận được. 2 1 CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 2. LẬP PACB XUẤT PHÁT KHONG suy biến 1 Phương pháp cước phí bé nhất @ Nguyên tắc Phân phốitối đa hàng lầnlượtvào cácô có cướcphí từ bé đếnlớncho đếnkhi trạm phát phát hết hàng và trạmthu thu đủ hàng. @ Nội dung phương pháp Trên bảng vậntải chọnô cócước cij bé nhất và phân phốitối đa vào ô đó tứclà Xịj min ai bj . -Nếu xij a ta bỏ hàng i trạm Bj cần bj bj -ai. -Nếu xj ta bỏ cột j trạm Aị còn a ai -bj. -Nếu xj ai bj . ta bỏ hàng i và cộtj tương ứng. Sau đó ta sẽ có mộtbảng VT thu gọn. Và ta tiến hành tương tự như trên cho ô có cước phí thấpnhất trong bảng mới. Cuối cùng ta sẽ có PACB của bài toán. 3 CHƯƠNG 3- BÀI TOÁN VẬN TẢI I 2. LẬP PACB XUẤT PHÁT KHÔNG suy biến yng pháp cước phí bé nhất Ví dụ ì Tấtcả các trạm phát đều đã phát hết hàng và các trạm thu đều đãthu đủ hàng. 2 CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 2. LẬP PACB XUẤT PHÁT KHONG suy biến K LHUdr 1 Phương pháp cước phí bé nhất Trong bảng trên ta có tổng cộng 6 ô chọn đúng bằng m n-1 ô chọn và 6 ô này không tạo thành vòng cho nên ta có PACB xuất phát không suy biếnnhư sau í 0 40 0 25 30 0 ì 0 5 0 0 15 35 5 chương 3- BÀI TOÁN VẬN TẢI o BÀI 2. LẬP PACB XUẤT PHÁT KHONG suy biến 2 Phương pháp FOGELS @ Nguyên tắc PP tối đavào ô cócướcphínhỏ nhấtnằm trên dòng hay cột có chênh lệch lớnnhấtgiữacước phí bé nhì và cước phí bé nhất. @ Nội dung Trên mỗi hàng và mỗicộtcủabảng vậntải tìm hiệusố của CP bé nhì và bé nhất. Chọnmức chênh lệch lớnnhất. PP tối đa cho ô có CP bé nhấtnằm trên hàng hoặccột củahiệusốđượcchọn tương tự như theo phương pháp CP bé nhất . Và ta sẽ thu đượcbảng vậntảithu gọn. Trong bảng vậntảithu gọn ta lặplại quá trình trên cho đến khi phát hếthàngvà thu đủ hàng. Khi đó ta có PACB xuất