Thực hành tin đại cương Thực hành tin đại cươThực hành tin đại cương Thực hành tin đại cương Thực hành tin đại cương ng
- 488560 WP0 Vietn 110Vietnamese 0version
Related documents
- TIẾN SĨ BÁO CHÍ HỌC 2021 2022 kdkddkkdkdk
- CHU DE THAO LUAN Chuong 2 PLDC HANU
- so sánh Các kiểu nhà nước
- Bai giang KT TBBC-đã chuyển đổi
- PHẦN MẪU VĂN BẢN-đã chuyển đổi
- 1905QTNB030-Phan Thi Huong-QTDN
Preview text
4. Bài toán vận tải cân bằng thu phát
Giả sử:
+] Có m nơi cung cấp hàng hóa [trạm phát], trạm phát thứ i chứa ai 0 đơn vị hàng hóa,
i 1,. m
+] Có n nơi tiêu thụ hàng hóa [trạm thu], trạm thu thứ j yêu cầu bj 0 đơn vị hàng hóa,
j 1,. n
+] Tổng lượng phát bằng lượng thu, tức là
1 1
. [1]
m n i j i j
a b
+ Cước phí vận chuyển một đơn vị hàng hóa từ trạm phát i đến trạm thu j là c ij.
Yêu cầu của bài toán là tìm lượng hàng phân phối x ijtừ trạm phát i đến trạm thu j
sao cho:
ij ij
1 1
min
m n
i j
f x c x
[Tổng cước phí vận chuyển là nhỏ nhất] [2]
Với các điều kiện ràng buộc:
1
, 1,
n ij i j
x a i m
[mọi điểm phát giao hết hàng] [3]
1
, 1,
m ij j i
x b j n
[mọi điểm thu nhận đủ hàng] [4]
xij 0, 1, , 1, i m j n [lượng hàng vận chuyển là không âm] [5]
Bài toán [2]-[5] thỏa mãn điều kiện [1] gọi là bài toán vận tải cân bằng thu phát.
Nhận xét: Bài toán vận tải cũng là bài toán QHTT dạng chính tắc, có m ẩn; hệ
ràng buộc chính có m+n phương trình.
+ Bài toán vận tải được viết dưới dạng bảng vận tải [BVT]
- Nếu có m trạm phát, n trạm thu thì BVT có m hàng, n cột. Nơi giao nhau của hàng i và
cột j gọi là ô [i,j]
Véc tơ x thỏa mãn tất cả các ràng buộc gọi là phương án [PA] của bài toán vận tải. Một
PA làm cho hàm mục tiêu đạt min gọi là PATU. Ta ký hiệu
11 12 1 21 22 2
1 2
... ... . ... ... ... ... ...
n n
m m mn
x x x x x x x
x x x
Ví dụ
Thu
Phát
- Trường hợp 2: Nếu ai bj x ij bj , khi đó ta xóa bỏ cột j [bằng cách đánh dấu x
vào các ô còn lại trên cột j] và đổi lượng phát ai ai ' a bi j.
- Trường hợp 3: Nếu ai bj thì ta có thể xóa dòng i hoặc cột j, nhưng không được xóa đồng thời cả dòng i và cột j
Lặp lại quá trình trên cho các ô tiếp theo đến khi yêu cầu của các trạm phát và trạm thu
được thỏa mãn. Phương án thu được là phương án cực biên [thường là có m+n-1 ô chọn,
tức là ô có lượng hàng dương]
Giải bài toán vận tải sau đây:
Thu
Phát
####### 25 25 10
####### 10
####### 30
####### 20
####### 5 3 5
####### 7 6 8
####### 3 2 2
Thu
Phát
####### 25
####### 25
####### 10
####### 10
####### 30
####### 20
Giải bài toán vận tải sau đây:
Thu
Thu - Phát - - - - - - - Phát - - - - - - - -