Chương 4
BÀI TOÁN VẬN TẢI
20/6/2012
MaMH: C01019 Chương 4: Bài toán vận tải
1
NỘI DUNG
1. Bài toán vận tải dạng tổng quát
1.1 Phát biểu bài toán vận tải (BTVT)
1.2 Đặt bài toán vận tải dưới dạng bảng
1.3 Các tính chất của bài toán vận tải 1.3 Các tính chất của bài toán vận tải
2. Thuật toán thế vị
2.1 Tiêu chuẩn tối ưu
2.2 Thuật toán
20/6/2012
3. Các trường hợp đặc biệt của BTVT
MaMH: C01019 Chương 4: Bài toán vận tải
2
Bài toán vận tải dạng tổng quát
,iS
=
,jT
với lượng phát tương ứng với
1,...,
n .
jb j ,
x x
ij
phát hàng đến n điểm thu = 1. Phát biểu bài toán Có m điểm phát m ia i ; 1,..., , lượng thu tương ứng
S a : i i
T b : j
j
c
ij
=
=
1,...,
m
iS i ,
(cid:190) (cid:190) fi
jT j , iS
=
ijc với: là cước phí vận chuyển 1 đơn vị hàng từ n 1,..., điểm phát ijx ,jT = i
1,...,
1,...,
m j ;
n .
20/6/2012
đến điểm thu là lượng hàng được vận chuyển từ đến
MaMH: C01019 Chương 4: Bài toán vận tải
3
Bài toán vận tải dạng tổng quát
20/6/2012
Vấn đề: Lập kế hoạch vận chuyển như thế nào để tổng cước phí vận chuyển là bé nhất? Biết rằng hàng hóa có thể vận chuyển từ một điểm phát bất kỳ đến một điểm thu bất kỳ.
MaMH: C01019 Chương 4: Bài toán vận tải
4
Bài toán vận tải dạng tổng quát
n m
=
Mô hình bài toán có dạng:
f X (
)
min
∑ ∑
c x ij
ij
=
=
1
j
1
i
n
= =
= =
x x
1,..., 1,...,
m m
∑ ∑
ij
a i , , a i i
=
j
1
m
=
=
x
1,...,
n
∑
ij
b j , j
1
fi
0,
= i
1,...,
= m j ;
1,...,
n
= i x
ij
20/6/2012
‡
MaMH: C01019 Chương 4: Bài toán vận tải
5
Bài toán vận tải dạng tổng quát
m
n
b
=∑ a
Điều kiện cân bằng thu phát:
∑
i
j
=
=
1
i
1
j
20/6/2012
MaMH: C01019 Chương 4: Bài toán vận tải
6
Bài toán vận tải dạng tổng quát
Thu
...
...
Tj : bj
Tn : bn
T1 : b1
Phát
2. Đặt bài toán dưới dạng bảng
c11
c1j
c1n
S1 : a1
11x
1jx
1nx
...
...
⋮
ci1
cij
cin
Si : ai
1ix
inx
ijx
...
...
⋮
cm1
cmj
cmn
Sm : am
1mx
mjx
mnx
20/6/2012
MaMH: C01019 Chương 4: Bài toán vận tải
7
Bài toán vận tải dạng tổng quát
Định nghĩa 1 Một tập hợp các ô thỏa mãn tính chất: • 2 ô liên tiếp cùng nằm trên cùng 1 hàng hay 1 cột; • 3 ô liên tiếp không cùng nằm trên cùng 1 hàng hay 1
cột
được gọi là một dây chuyền. được gọi là một dây chuyền.
20/6/2012
Một dây chuyền khép kín được gọi là một chu trình.
MaMH: C01019 Chương 4: Bài toán vận tải
8
Bài toán vận tải dạng tổng quát
0
ijx >
được gọi là ô chọn, những ô
Định nghĩa 2 Những ô có còn lại được gọi là ô loại.
Định nghĩa 3 Một phương án (PA) mà các ô chọn không tạo thành chu trình đgl PA cơ bản (PACB).
20/6/2012
Một PACB đủ (m + n – 1) ô chọn đgl PACB không suy biến.
MaMH: C01019 Chương 4: Bài toán vận tải
9
Bài toán vận tải dạng tổng quát
3. Các tính chất của BTVT i. BTVT cân bằng thu phát luôn luôn có PATƯ. ii. Trong 1 PACB bất kỳ, tổng số ô chọn luôn nhỏ
+ - m n m n+ - (
( (Số ô chọn iii. Với PACB có đủ
£ hơn hoặc bằng tổng số điểm phát và thu trừ đi 1. 1)
20/6/2012
). 1) ô chọn, thì với 1 ô loại bất kỳ sẽ tạo thành một chu trình duy nhất với một số ô chọn.
MaMH: C01019 Chương 4: Bài toán vận tải
10
Thuật toán thế vị
=
min
f x (
)
c x ij
ij
=
=
1
i
1
j
n
=
=
x
1,...,
m
∑
ij
a i , i
=
1
j
m
=
=
x
1,...,
n
∑
ij
b j , j
1
fi 1. Tiêu chuẩn tối ưu Xét BTVT cân bằng thu phát m n ∑ ∑
0,
= i
1,...,
= m j ;
1,...,
n
= i x
ij
20/6/2012
‡
MaMH: C01019 Chương 4: Bài toán vận tải
11
Thuật toán thế vị
m
n
=
+
Bài toán đối ngẫu của bài toán trên:
g u v ( , )
max
fi
∑
∑
a u i
i
b v j
j
=
=
1
j
i + +
1 = =
= =
u u
v v
c c
, ,
i i
1, 1,
m ; ; m
j j
1, 1,
n . . n
i i
j j
ij ij
20/6/2012
£ £
MaMH: C01019 Chương 4: Bài toán vận tải
12
Thuật toán thế vị
=
=
u v i , ,
1,
1,
n
i
j
+ +
Định lý 1 x= PA của BTVT là PATƯ khi và chỉ khi tìm ( X )ij được các số m j ; thỏa mãn:
c c
, ,
v v
j ( , ) i ( , ) j i
ij
i
j
=
+
£ " £ "
c
,
v
i ( , )
j G X
(
),
ij
i
j =
>
u u u G X (
)
j {( , ) : i
x
0}
ij
20/6/2012
" ˛
MaMH: C01019 Chương 4: Bài toán vận tải
13
Thuật toán thế vị
0
X
x= 0( )ij
=
min{
x
a b , i
ij
j
theo nguyên tắc phân
2. Thuật toán thế vị - Bước 1 (Bước khởi tạo) Tìm PACB xuất phát phối tối đa: Giả sử cần phân phối cho ô (i,j). Lượng hàng tối đa } có thể phân phối là Sau đó, điều chỉnh lại các yêu cầu:
x
-
a i b
ij x
j
j
ij
¢ = a i ¢ = b
20/6/2012
-
MaMH: C01019 Chương 4: Bài toán vận tải
14
Thuật toán thế vị
0
ia¢ = 0 jb¢ = 0 ¢= b a i
j
20/6/2012
¢ , thì loại dòng i. , thì loại cột j. = • Nếu • Nếu • Nếu , thì loại cả dòng i và cột j.
MaMH: C01019 Chương 4: Bài toán vận tải
15
Thuật toán thế vị
Ví dụ 1
x 19
bj
60
30
46
25
ai
7 7
12 12
7 7
50 4 50 4
9
6
1
51
70 5
19
2
9
1
x
41 8
41
20/6/2012
MaMH: C01019 Chương 4: Bài toán vận tải
16
Thuật toán thế vị
0,
Ta được bảng mới thu gọn. Lặp lại hai phép toán trên với bảng mới thu gọn đến khi yêu cầu của điểm phát và điểm thu được thỏa mãn.
ijx >
0.
những ô còn lại
ijx =
20/6/2012
Các ô được phân phối có có
MaMH: C01019 Chương 4: Bài toán vận tải
17
Thuật toán thế vị
20/6/2012
Dựa vào nguyên tắc phân phối tối đa và cách thức chọn ô ưu tiên phân phối, xét 3 phương pháp: i. Phương pháp góc Tây Bắc: ô đầu tiên được chọn để phân phối là ô ở vị trí góc Tây Bắc (ô (1,1)). ii. Phương pháp cực tiểu cước phí: ô đầu tiên được ii. Phương pháp cực tiểu cước phí: ô đầu tiên được chọn để phân phối là ô có cước phí bé nhất. iii. Phương pháp Fogel: trên mỗi hàng, cột chọn ra hai ô có cước phí bé nhất (bé nhì), lấy hiệu số của chúng. Ô có cước phí bé nhất tương ứng ở hàng, cột có hiệu số lớn nhất sẽ là ô đầu tiên được chọn để phân phối.
MaMH: C01019 Chương 4: Bài toán vận tải
18
Thuật toán thế vị
m n+ -
(
1)
ij
1)
ô chọn, thì
sao cho: m n+ - ( j ( , ) i
20/6/2012
Nếu PACB tìm được có đủ sang Bước 2. Ngược lại, thêm vào ô nào đó một lượng hàng j i ( , ) ijx = 0 • đủ số • và ô này không tạo thành chu trình với các ô chọn. fi Bước 2.
MaMH: C01019 Chương 4: Bài toán vận tải
19
Thuật toán thế vị
u v i , ,
m n+ - ( = m j ; 1,
1) ô chọn. n 1,
= =
+ +
i j i ( , ) ( , ) i
v v
, ,
j G X j G X
( (
) )
i i
j j
ij ij
" ˛ " ˛ - Bước 2 (Bước lặp) Ở đầu bước lặp đã có PACB đủ = i. Xác định các thế vị c c u u
Chọn u1 = 0. ii. Tính các ước lượng theo công thức:
v
c
,
j ( , ) i
D = ij
+ u i
j
ij
20/6/2012
- "
MaMH: C01019 Chương 4: Bài toán vận tải
20
Thuật toán thế vị
ij
*
*
)
(
,
i
j
D £ " thì PA đang xét là PATƯ. Ngược
=
0}
D > : ij
ij
* * max{ j
i
*
*
j
i
,
)
*
)
(
,
i
( Khi đó, ô sẽ tạo nên một chu trình duy nhất với một số ô chọn. fi Ô sẽ là ô chọn ở bảng mới. * j
20/6/2012
iii. Kiểm tra tiêu chuẩn tối ưu j ( , ) i 0, Nếu lại, chuyển sang iv. iv. Chọn ô là ô có ước lượng dương lớn nhất: nhất: D D
MaMH: C01019 Chương 4: Bài toán vận tải
21
Thuật toán thế vị
*
*
(
)
,
i
j
K -
Đặt tên chu trình là K. Đánh dấu +, - xen kẽ vào các ô thuộc K, bắt đầu từ ô mang dấu +. Đặt : K + = { những ô mang dấu +}
20/6/2012
= { những ô mang dấu -}
MaMH: C01019 Chương 4: Bài toán vận tải
22
Thuật toán thế vị
X
),
x= (
ij
ij
x= (
),
Tiến hành điều chỉnh PA ta có PA mới X với
j ( , ) i
K
,
ijx
+ +
+ +
q q
ˇ
x x
x x
j ( , ) i ( , ) j i
K K
, ,
ij
ij
˛ ˛
q
x
j ( , ) i
K
,
= =
- - ˛
ij =
q
=
min{
x
K
}
ij
i
j 0 0
)
(
i
0
X
j i : ( , ) x trong đó, fi Ô là ô loại ở bảng mới. j , 0 Thay X bởi
- ˛
20/6/2012
và lặp lại Bước lặp.
MaMH: C01019 Chương 4: Bài toán vận tải
23
Thuật toán thế vị
bj
30 60 46 25 ai
4 7 u1= 0 50 50
20 20
30 30
+
9 12 -8 -8 6
-
70 u2= 2
24
7 -1 -1 1 746 1 2
41 u3= -5
+
9 -10 5 1 8 -9
16 v2= 7
v3= 4
- 25 v4= 6
q =
24
20/6/2012
v1= 4
MaMH: C01019 Chương 4: Bài toán vận tải
24
Thuật toán thế vị
Ví dụ 2 (tt) bj
30 60 46 25 ai
4 7 u1= 0 50 50
20 20
30 30
12 -1 -1 6 7 -1 -1 1
70 u2= -5
24
46
9 -7 2 1
41 u3= -5
40
5 -6 8 -9
9 -3 v3= 11
1 v4= 6
20/6/2012
v1= 4 v2= 7
MaMH: C01019 Chương 4: Bài toán vận tải
25
Thuật toán thế vị
0,
j ( , ) i
ij
D £ " Vì
0
0
*
=
X
0
46 24
0
nên 30 20
0
0
1
40
PATƯ
*
+ ·
+ ·
+ ·
+
+
f X = · (
) 4 30 7 20 6 46 24 2 40 1
=
641.
20/6/2012
Giá trị tối ưu:
MaMH: C01019 Chương 4: Bài toán vận tải
26
Các trường hợp đặc biệt của BTVT
i. BTVT không cân bằng thu phát
m
n
b
>∑ ∑ a i
j
=
=
1
i
1
j
a. Phát > Thu:
fi
m
n
=
b
;
m 1 . ,
+
+ = " = i 0,
b n
1
-∑ ∑ a i
j
i nc
(
1)
=
=
1
i
1
j
20/6/2012
fi Đưa về BTVT cân bằng thu phát Thêm một điểm thu giả, lượng hàng tương ứng
MaMH: C01019 Chương 4: Bài toán vận tải
27
Các trường hợp đặc biệt của BTVT
n
b
<∑ ∑ a i
j
=
=
1
i
1
j
b. Phát < Thu m
fi Đưa về BTVT cân bằng thu phát fi Đưa về BTVT cân bằng thu phát
n
m
=
= " = j 0,
n 1 . ,
;
+
c (
+ m j 1)
-∑ ∑ b
a m
1
j
a i
=
=
1
j
1
i
20/6/2012
fi Thêm một điểm phát giả, lượng hàng tương ứng
MaMH: C01019 Chương 4: Bài toán vận tải
28
Các trường hợp đặc biệt của BTVT
M M
ij
20/6/2012
fi fi Thay Thay , với , với là số dương rất lớn. là số dương rất lớn. ii. BTVT có ô cấm Ô cấm: ô không được nhận hàng. Giả sử ô là ô cấm. j i ( , ) ijc M=
MaMH: C01019 Chương 4: Bài toán vận tải
29
Các trường hợp đặc biệt của BTVT
iii. “BTVT” với hàm mục tiêu cực đại Có mô hình giống BTVT, nhưng hàm mục tiêu cực đại.
0, 0,
j ( , ) i ( , ) j i
ij ij
*
*
D ‡ " D ‡ "
(
,
i
j
• Dấu hiệu tối ưu: • Dấu hiệu tối ưu: • Chọn ô
0}
) = * min{
*
D < : ij
i
j
j ( , ) i
ij M= -
M
D D
ijc
, thay • Nếu có ô cấm , với là số dương
ijc
20/6/2012
rất lớn. • Chọn ô có lớn nhất phân phối trước.
MaMH: C01019 Chương 4: Bài toán vận tải
30
