Một số trường hợp đặc biệt của bài toán vận tải

§3 Một số trường hợp đặc biệt của bài toán vận tải 1. Bài toán vận tải không cân bằng thu phát. 2. Bài toán vận tải có ô cấm 3. Bài toán vận tải có hàm mục tiêu cực đại Bài toán vận tải không cân bằng thu phát Phương pháp giải: Bước 1: Nếu tức là tổng phát lớn hơn tổng thu, khi đó ta lập thêm trạm thu phụ Bn + 1 có yêu cầu: và cước phí vận chuyển tới trạm Bn + 1 bằng 0 Bài toán vận tải không cân bằng thu phát Nếu tức là tổng thu lớn hơn tổng phát, khi đó ta lập thêm trạm phát phụ Am+ 1 có yêu cầu: và cước phí vận chuyển từ trạm phát An + 1 bằng 0 Bước 2: Tiến hành giải bình thường, với lưu ý khi tìm PACB xuất phát bằng phương pháp cước phí bé nhất ta ưu tiên phân phối vào các trạm chính. PATƯ của bài toán gốc là PATƯ của bài toán phụ bỏ đi cột ứng với trạm thu phụ Bài toán vận tải không cân bằng thu phát Ví dụ: Giải bài toán vận tải sau: Bài toán vận tải có ô cấm Trong thực tế vì nhiều lý do dẫn tới hàng không thể vận chuyển từ trạm phát tới trạm thu nào đó và ô tương ứng của các trạm đó không thể phân phối hàng và ta gọi đó là ô cấm Phương pháp: Giả sử ô (i, j) là ô cấm Bước 1: Thay cước phí ô cấm bằng M (là số dương lớn tùy ý) ta có bài toán vận tải mở rộng của bài toán đã cho (gọi là bài toán gốc) Bước 2: Giải bài toán mở rộng với lưu ý khi tìm PACB xuất phát ta phải ưu tiên phân phối hàng vào ô bình thường trước, cuối cùng mới phân phối hàng vào ô cấm Bài toán vận tải có ô cấm Bước 3: Kết luận Nếu PATƯ của bài toán mở rộng có lượng hàng trong ô cấm đều bằng không thì bài toán gốc có PATƯ và PATƯ của bài toán gốc là PATƯ của bài toán mở rộng Nếu PATƯ của bài toán mở rộng có ít nhất 1 ô cấm có lượng hàng dương thì bài toán xuất phát không có PATƯ Bài toán vận tải có ô cấm Ví dụ: Giải bài toán vận tải Biết ô (2, 2) và ô (2, 4) là các ô cấm Bài toán vận tải có hàm mục tiêu cực đại Phương pháp giải bài toán vận tải có hàm mục tiêu cực đại về cơ bản giống với các giải một bài toán vận tải thông thường chỉ cần chú ý các vấn đề sau: 1. Khi lập PACB thì phải ưu tiên ô có cước phí lớn nhất 2. Khi kết luận tính tối ưu của PACB thì điều kiện tối ưu là các hệ số ước lượng phải không âm 3. Khi tìm ô đưa vào thì ta phải tìm ô có ước lượng âm nhỏ nhất Bài toán vận tải có hàm mục tiêu cực đại Ví dụ: Nông trường có 3 khu đất A1, A2, A3 có diện tích tương ứng là 250, 1400, 350 ha. Nông trường định trồng 4 loại cây B1, B2, B3, B4 với diện tích dự định là 500, 400, 600, 500 ha. Lợi nhuận khi trồng loại cây Bj trên một hecta đất Aj là cij được cho bởi bảng sau: Hãy lập kế hoạch trồng cây tối ưu của nông trường