BÀI 3
1. Đinh nghia:
A1, …,Am la m tram phat, co l ng hang phat ra t ng ươ ươ
ng la aư 1,…,am
B1,…, Bn la n tram thu cân nhâp l ng hang t ng ươ ươ
ng la bư 1,…,bn
cij c c phi vân chuyên môt đ n vi hang hoa t tram ươ ơ ư
phat Ai đên tram thu B j.
Điêu kiên:
1 1
m n
i j
i j
a b
= =
=
� �
Thu
Phat
B1
b1
B2
b2
…
…
Bn
bn
A1 a1c11 c12 c1n
A2 a2c21 c22 c2n
Am amcm1 cm2 cmn
2. Mô hinh toan hoc cua bai toan vân tai:
Goi xij la khôi l ng hang hoa ta se vân chuyên t tram ươ ư
phat Ai đên tram thu B j (i = 1,..,m; j = 1,…,n), ta co mô
hinh:
min
1 1
, 1,...,
1
, 1,...,
1
0, 1,..., ; 1,...,
m n c x
ij ij
i j
nx a i m
ij i
j
mx b j n
ij j
i
x i m j n
ij
� �
= =
= =
=
= =
=
= =
3. Ph ng an cua bai toan vân tai:ươ
Môt ph ng an cua bai toan vân tai la môt ma trân ươ
trong đo la cac sô không âm sao
cho:
va
( )
0
0ij m n
X x
=
0
ij
x
0
1
, 1,...,
n
ij i
j
x a i m
=
= =
0
1
, 1,...,
m
ij j
i
x b j n
=
= =
4. Ph ng an c ban cua bai toan vân tai:ươ ơ
- Ô chon: trong môt ph ng an c ban cua bai toan ươ ơ
vân tai cac ô co l ng hang d ng đ c goi la ô ươ ươ ươ
chon, cac ô co l ng hang băng 0 đ c goi la ô loai. ươ ươ
- Vong: Môt day cac ô chon cua môt ph ng an nao ươ
đo đ c goi la tao nên môt vong nêu môi ô trong day ươ
ô đo đêu phai năm trên cung môt dong (côt) chi v i ơ
môt ô đ ng tr c no đông th i phai năm trên cung ư ươ ơ
môt côt (dong) chi v i môt ô đ ng sau no. ơ ư