Chương 4
BÀI TOÁN VN TI
20/6/2012 1MaMH: C01019 Chương 4: Bài toán vn ti
NI DUNG
1. Bài toán vn ti dng tng quát
1.1 Phát biu bài toán vn ti (BTVT)
1.2 Đt bài toán vn ti dưi dng bng
1.3
Các
tính
cht
ca
bài
toán
vn
ti
1.3
Các
tính
cht
ca
bài
toán
vn
ti
2. Thut toán thv
2.1 Tiêu chun tiưu
2.2 Thut toán
3. Các trưng hpđc bit ca BTVT
20/6/2012 2MaMH: C01019 Chương 4: Bài toán vn ti
Bài toán vn ti dng tng quát
1. Phát biu bài toán
Có mđim phát vi lưng phát tương ng
phát hàng đnnđim thu vi
lưng thu tương ng
,
i
S
, 1,..., ;
i
a i m
=
,
j
T
, 1,..., .
j
b j n
=
vi: là cưc phí vn chuyn 1 đơn vhàng t
đim phát đnđim thu
là lưng hàng đưc vn chuyn t đn
20/6/2012 3MaMH: C01019 Chương 4: Bài toán vn ti
: :
ij
ij
i i j j
c
S a T b
→
ij
c
, 1,...,
i
S i m
=
, 1,...,
j
T j n
=
ij
x
i
S
1,..., ; 1,..., .
i m j n
= =
,
j
T
Bài toán vn ti dng tng quát
Vnđ: Lp khoch vn chuyn nhưthnào đ
tng cưc phí vn chuyn là bé nht? Bit rng
hàng hóa có thvn chuyn tmtđim phát bt
kỳ đn mtđim thu bt kỳ.
20/6/2012 4MaMH: C01019 Chương 4: Bài toán vn ti
Bài toán vn ti dng tng quát
Mô hình bài toán có dng:
1 1
( ) min
, 1,...,
n m
ij ij
j i
n
f X c x
x a i m
= =
= →
= =
∑∑
∑
20/6/2012 5MaMH: C01019 Chương 4: Bài toán vn ti
1
1
, 1,...,
, 1,...,
0, 1,..., ; 1,...,
ij i
j
m
ij j
i
ij
x a i m
x b j n
x i m j n
=
=
= =
= =
≥ = =
∑
∑