Trường Đại học Tự nhiên TPHCM
Khoa Môi Trường
1
GIẢI BÀI TOÁN VẬN TẢI
BẰNG PHƯƠNG PHÁP THẾ VỊ
HVTH:Phan Nguyên Hồng
Nguyễn Thành Trí
Trần Ngọc Thanh
GVHD:PGS.TS. Nguyễn Thị Vân Hà
7/2013
NỘI DUNG3
3
2
2
1
1
Đặt vấn đề
Xác lập bài toán
Các bước giải bài toán vận tải
4
4
Kết luận
3
1.Đặt vấn đề
Vận chuyển hết số rác từ các bệnh viện đến các bãi rác sao cho tổng cước phí vận chuyển là nhỏ nhất.
Bài toán cụ thể:
Ta có 4 bệnh viện (phát) mỗi bệnh viện có số rác thải là a
1

Tổng chi phí để vận chuyển hết rác từ các bệnh viện đến bãi rác là Z.
4
1.Đặt vấn đề
Bãi rác 1 Bãi rác 2 Bãi rác 3 Bãi rác 4 Lượng phát thải
(kg/ngày)
Bệnh viện A 31 19 25 25 160
Bệnh viện B 25 13 18 22 150
Bệnh viện C 37 29 27 20 190
Bệnh viện D 13 24 30 18 100
Lượng tiếp nhận
(kg/ngày)
120 175 155 150 600
5
2.Xác lập bài toán
Theo yêu cầu của đặt vấn đề ta có:
Hàm mục tiêu:
Z = đạt giá trị nhỏ nhất
hay tìm x
ij
sao cho Z đạt giá trị cực tiểu
Điều kiện ràng buộc:
∑∑
= =
4
1
4
1i j
ijij
cx
∑ ∑

i
i
ij
ba
x
•
Góc Tây-Bắc
•
Cước phí bé nhất
Bước 1: Tìm điểm xuất phát X
0
•
Xác định ô cơ sở
•
Từ ô cơ sở  lập hệ phương trình
thế vị có dạng u
i
+v
j
=c
ij
•
Ước tính các ô tự do
Bước 2:
Xác định hệ thế vị
•
Nếu các ô tự do có:
u
i
+v

= (120.31 + 40.19 + 135.13 + 15.18 + 140.27 + 50.20 + 100.18) x 1000 =13.085.000 triệu đồng
Min(120;160)
Min(175;40)
Min(135;150)
Min(155;15)
Min(140;190) Min(150;50)
Min(50;100)
Ô CƠ SỞ
Ô TỰ DO
v
1
=?
v
2
=?
v
3
=?
v
4
=?
u
1
=?
u
2
=?
u
3
=?

=+
=+
=+
=+
=+
1u
3u
6u
0u
4
3
2
1
=
=
−=
=
17v
24v
19v
31v
4
3
2
1
=
=
=
=
9

u
2
=-6
u
3
=3
u
4
=1
10
3. Các bước giải bài toán vận tải
Bước 3: Kiểm tra tiêu chuẩn tối ưu

Ở các ô tự do ta kiểm tra điều kiện:

Nếu không thỏa điều kiện  phương án chưa tối ưu  chọn phương án khác (thay đổi giá trị x
ij
ở các ô cơ sở và tiếp
tục vòng lặp thứ n)

Cách chọn phương án khác là
chọn một chu trình tính ứng với
ô tự do có giá trị

Chu trình là một đường gãy
khép kín, các chỗ gãy vuông góc
với nhau, có 1 đỉnh là ô tự do, các đỉnh còn lại là ô cơ sở.
0cvu
ijjiij
≤−+=∆

20vu
27vu
18vu
13vu
19vu
31vu
14
43
33
32
22
21
11
=+
=+
=+
=+
=+
=+
=+
18u
3u
6u
0u
4
3
2
1
−=
=

v
1
=31
v
2
=19
v
3
=24
v
4
=17
u
1
=0
u
2
=-6
u
3
=3
u
4
=-18
14
3. Các bước giải bài toán vận tải
Bước 3: Kiểm tra tiêu chuẩn tối ưu
Tất cả các ô tự do đều thỏa điều kiện tối ưu,

Với phương án được lựa chọn trên thì tổng chi phí vận chuyển rác từ 4 bệnh viện đến 4 bãi rác là:

0

k
g

v
ớ
i

c
ư
ớ
c

p
h
í

1
9
.
0
0
0
/
k
g
3
5


g

v
ớ
i

c
ư
ớ
c

p
h
í

1
8
.
0
0
0
/
k
g
4
0

k
g


ớ
i

c
ư
ớ
c

p
h
í

2
0
.
0
0
0
/
k
g
1
0
0

k
g

v
ớ