TR NG Đ I H C KINH T K THU T CÔNG NGHI P ƯỜ Ạ Ọ Ế Ỹ Ậ Ệ
B MÔN KHOA H C C B NỘ Ọ Ơ Ả
BÀI GI NGẢ
QUY HO CH TUY N TÍNHẠ Ế
CH NG II:ƯƠ
BÀI TOÁN V N T IẬ Ả
2.1. D ng c a bài toán v n t iạ ủ ậ ả
2.2. Xây d ng ph ng án c c biênự ươ ự
2.3. Ph ng pháp th v gi i bài toán v n t iươ ế ị ả ậ ả
2.4. Bài toán không cân b ng thu phátằ
2.1. D ng c a bài toán v n t iạ ủ ậ ả
Ai (i =1,…m): các tr m phát ạ
Bj (j = 1,…n): các tr m thuạ
ai: l ng hàng hoá có tr m phát Aượ ở ạ i
bj: l ng hàng hoá yêu c u tr m thu Bượ ầ ở ạ j
cij: chi phí v n chuy n m t đ n v hàng hoá t tr m phát ậ ể ộ ơ ị ừ ạ
Ai (i = 1,.,m) đ n tr m thu Bế ạ j (j = 1, 2,..., n) (cij > 0)
xij: l ng hàng hoá v n chuy n t tr m phát Aượ ậ ể ừ ạ i đ n ế
tr m ạ
thu Bj , xij ≥ 0 (∀i, j)
Hãy thành l p m t ph ng án v n chuy n hàng hoá ậ ộ ươ ậ ể
sao cho đáp ng đ y đ yêu c u c a các tr m thu b ng ứ ầ ủ ầ ủ ạ ằ
t t c hàng hoá có các tr m phát v i t ng chi phí v n ấ ả ở ạ ớ ổ ậ
chuy n là nh nh t.ể ỏ ấ
( )
( )
( )
)4(,1;,10
)3(,1
)2(,1
)1(min)(
1
1
1 1
njmix
njbx
miax
xcxf
ij
m
i
jij
n
j
iij
m
i
n
j
ijij
==≥
==
==
⇒=
∑
∑
∑∑
=
=
= =
Tìm b giá tr sao cho:ộ ị
{ }
( )
njmix
ij
,1;,1
==
N u thì bài toán v n t i cân b ng thu phátế ậ ả ằ
∑∑
==
=
n
j
j
m
i
i
ba
11
Mô t bài toán d i d ng b ng:ả ướ ạ ả
Thu
Phát
b1b2…… bn
a1c11 c12 …… c1n
a2c21 c22 …… c2n
….. ….. …… …… ……
amcm1 cm2 …… cmn
Giao c a hàng i và c t j g i là ô (i, j) đ c tr ng cho ủ ộ ọ ặ ư
đo n đ ng n i tr m phát Aạ ườ ố ạ i và tr m thu Bạj , ô này ghi ở
c