zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

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

Chia sẻ: Tran Xuan Trung | Ngày: | Loại File: PDF | Số trang:9

Báo xấu

457
lượt xem 62
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Thông thường khi nói đến bài toán vận tải ta thường liên hệ ngay đến bài toán vận tải hai chỉ số, bởi đây là bài toán vận tải kinh điển có những phương pháp giải hay. Đây là tài liệu về một số trường hợp đặc biệt của bài toán vận tải, mời các bạn tham khảo

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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: m n Nế � >� a b i =1 i j =1 j tức là tổng phát lớn hơn u tổng thu, khi đó ta lập thêm trạm thu phụ Bn + 1 có m n yêu cầu: bn + 1 = � i − � j a b i =1 j =1 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 m n Nế � i < � j tức là tổng thu lớn hơn a b i =1 j =1 u tổng phát, khi đó ta lập thêm trạm phát phụ Am+ 1 có yêu cầu: n m am +1 = � j − � i b a j =1 i =1 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: 140 150 180 150 5 4 6 100 8 5 9 145 11 6 12 100 9 7 13
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 50 100 25 25 50 8 15 16 10 100 10 5 9 15 50 10 14 11 13 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 tìm ô đưa vào thì ta phải tìm ô có ước 3. Khi 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: B1 : 500 B2 : 400 B3 : 600 B4 : 500 A1 : 250 22 25 20 18 A2 : 1400 30 32 25 28 A3 : 350 29 28 25 23 Hãy lập kế hoạch trồng cây tối ưu của nông trường

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.