Xem mẫu
- 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
2. Thu t toán th v
2.1 Tiêu chu n t i ưu
2.2 Thu t toán
3. Các trư ng h p đ c bi t c a BTVT
20/6/2012 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
1. Phát bi u bài toán
Có m đi m phát S i , v i lư ng phát tương ng
ai , i = 1,..., m; phát hàng đ n n đi m thu T j , v i
lư ng thu tương ng b j , j = 1,..., n.
Si : ai →T j : b j
xij
cij
v i: cij là cư c phí v n chuy n 1 đơn v hàng t
đi m phát S i , i = 1,..., m đ n đi m thu T j , j = 1,..., n
xij là lư ng hàng đư c v n chuy n t S i đ n Tj ,
i = 1,..., m; j = 1,..., n.
20/6/2012 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
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ỳ.
20/6/2012 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
Mô hình bài toán có d ng:
n m
f(X) = ∑∑c
j =1 i =1
ij x ij → min
n
∑ x ij = ai , i = 1,..., m
j =1
m
∑ x ij = b j , j = 1,..., n
i =1
x ij ≥ 0, i = 1,..., m ; j = 1,..., n
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
Đi u ki n cân b ng thu phát:
m n
∑a
i =1
i = ∑b
j =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
2. Đ t bài toán dư i d ng b ng
Thu T1 : b1 ... Tj : bj ... Tn : bn
Phát
c11 c1j c1n
S1 : a1 x11 x1j x1n
⋮ ... ...
ci1 cij cin
Si : ai xi 1 xij xin
⋮ ... ...
cm1 cmj cmn
Sm : am x m1 xmj xmn
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.
M t dây chuy n khép kín đư c g i là m t chu trình.
20/6/2012 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
Đ nh nghĩa 2
Nh ng ô có x ij > 0 đư c g i là ô ch n, nh ng ô
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).
M t PACB đ (m + n – 1) ô ch n đgl PACB không
suy bi n.
20/6/2012 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
hơn ho c b ng t ng s đi m phát và thu tr đi 1.
(S ô ch n ≤ (m + n − 1) ).
iii. V i PACB có đ (m + n − 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.
20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 10
- Thu t toán th v
1. Tiêu chu n t i ưu
Xét BTVT cân b ng thu phát
m n
f (x) = ∑∑c
i =1 j =1
ij x ij → min
n
∑ x ij = ai , i = 1,..., m
j =1
m
∑ x ij = b j , j = 1,..., n
i =1
x ij ≥ 0, i = 1,..., m ; j = 1,..., n
20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 11
- Thu t toán th v
Bài toán đ i ng u c a bài toán trên:
m n
g (u,v ) = ∑ ai ui + ∑ b j v j → max
i =1 j =1
ui + v j ≤ cij , i = 1, m; j = 1, n.
20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 12
- Thu t toán th v
Đ nh lý 1
PA X = ( xij ) c a BTVT là PATƯ khi và ch khi tìm
đư c các s ui ,v j , i = 1, m; j = 1, n th a mãn:
ui + v j ≤ cij , ∀(i , j )
ui + v j = cij , ∀(i , j ) ∈ G( X ),
G( X ) = {(i , j ) : xij > 0}
20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 13
- Thu t toán th v
2. Thu t toán th v
- Bư c 1 (Bư c kh i t o)
Tìm PACB xu t phát X 0 = ( xij ) theo nguyên t c phân
0
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à xij = min{ai , b j }
Sau đó, đi u ch nh l i các yêu c u:
ai′ = ai − xij
b′ = b j − xij
j
20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 14
- Thu t toán th v
• N u ai′ = 0 , thì lo i dòng i.
• N u b′ = 0 , thì lo i c t j.
j
• N u ai′ = b′ = 0 , thì lo i c dòng i và c t j.
j
20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 15
- Thu t toán th v
x
Ví d 1
19
bj
ai 30 60 46 25
50 4 7 12 7
51 70 5 9 6 1
19
x 41 8 2 9 1
41
20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 16
- Thu t toán th v
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.
Các ô đư c phân ph i có xij > 0, nh ng ô còn l i
có xij = 0.
20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 17
- Thu t toán th v
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
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.
20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 18
- Thu t toán th v
N u PACB tìm đư c có đ ( m + n − 1) ô ch n, thì
sang Bư c 2.
Ngư c l i, thêm vào ô (i , j ) nào đó m t lư ng hàng
xij = 0 sao cho:
• đ s ( m + n − 1)
• và ô (i , j ) này không t o thành chu trình v i các ô
ch n.
→ Bư c 2.
20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 19
- Thu t toán th v
- Bư c 2 (Bư c l p)
đ u bư c l p đã có PACB đ ( m + n − 1) ô ch n.
i. Xác đ nh các th v ui ,v j , i = 1, m ; j = 1, n
ui + v j = cij , ∀(i , j ) ∈ G( X )
Ch n u1 = 0.
ii. Tính các ư c lư ng theo công th c:
∆ ij = ui + v j − cij , ∀(i , j )
20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 20
nguon tai.lieu . vn
