Tài liệu

Bài toán vận tải (TS. Nguyễn Công Trí)

Chia sẻ bởi
Lượt xem: 12681     Tải về: 75     Lượt mua: 3     Định dạng:  
Báo lỗi
Bình luận
Nhúng
/ 17
Tài liệu Bài toán vận tải (TS. Nguyễn Công Trí) - tài liệu, sách iDoc.VnBài toán vận tải (TS. Nguyễn Công Trí),Các tính chất và tiêu chuẩn tối ưu của bài toán vận tảiCác phương pháp tìm phương án cực biên đầu tiên của bài toán vận tảiThuật…
Ths. Nguyn Coâng Tr
Ths. Nguyn Coâng Tr
Ths. Nguyn Coâng Tr
í
í
í
Copyright 2001
Copyright 2001
Copyright 2001
Ths. Nguyeãn Coâng Tr
Ths. Nguyeãn Coâng Tr
Ths. Nguyeãn Coâng Tr
í
í
í
Copyright 2001
Copyright 2001
Copyright 2001
BA
BA
Ø
Ø
I TOA
I TOA
Ù
Ù
N VA
N VA
Ä
Ä
N TA
N TA
Û
Û
I
I
1.
1.
BA
BA
Ø
Ø
I TOA
I TOA
Ù
Ù
N VA
N VA
Ä
Ä
N TA
N TA
Û
Û
I DA
I DA
Ï
Ï
NG TO
NG TO
Å
Å
NG QUA
NG QUA
Ù
Ù
T
T
(Xem)
(Xem)
2.
2.
CA
CA
Ù
Ù
C T
C T
Í
Í
NH CHA
NH CHA
Á
Á
T VA
T VA
Ø
Ø
TIU CHUA
TIU CHUA
Å
Å
N TO
N TO
Á
Á
I
I
Ö
Ö
U
U
CU
CU
Û
Û
A
A
BA
BA
Ø
Ø
I TOA
I TOA
Ù
Ù
N VA
N VA
Ä
Ä
N TA
N TA
Û
Û
I
I
(Xem)
(Xem)
3.
3.
CA
CA
Ù
Ù
C PH
C PH
Ö
Ö
ÔNG PHA
ÔNG PHA
Ù
Ù
P M PH
P M PH
Ö
Ö
ÔNG A
ÔNG A
Ù
Ù
N C
N C
ÖÏ
ÖÏ
C
C
BIEÂN
BIEÂN
Ñ
Ñ
A
A
À
À
U TIEÂN CU
U TIEÂN CU
Û
Û
A BA
A BA
Ø
Ø
I TOA
I TOA
Ù
Ù
N VA
N VA
Ä
Ä
N TA
N TA
Û
Û
I
I
(Xem)
(Xem)
4.
4.
THUA
THUA
Ä
Ä
T GIA
T GIA
Û
Û
I THE
I THE
Á
Á
VÒ CHO BA
VÒ CHO BA
Ø
Ø
I TOA
I TOA
Ù
Ù
N VA
N VA
Ä
Ä
N TA
N TA
Û
Û
I
I
(Xem)
(Xem)
5.
5.
CA
CA
Ù
Ù
C DA
C DA
Ï
Ï
NG KHA
NG KHA
Ù
Ù
C CU
C CU
Û
Û
A BA
A BA
Ø
Ø
I TOA
I TOA
Ù
Ù
N VA
N VA
Ä
Ä
N TA
N TA
Û
Û
I
I
(Xem)
(Xem)
6.
6.
BA
BA
Ø
Ø
I TA
I TA
Ä
Ä
P
P
(Xem)
(Xem)
CHÖÔNG 3
NO
NO
Ä
Ä
I DUNG BA
I DUNG BA
Ø
Ø
I TOA
I TOA
Ù
Ù
N VA
N VA
Ä
Ä
N TA
N TA
Û
Û
I
I
Gia
Gia
û
û
s
s
öû
öû
ca
ca
à
à
n va
n va
ä
ä
n chuye
n chuye
å
å
n mo
n mo
ä
ä
t loa
t loa
ï
ï
i ha
i ha
ø
ø
ng ho
ng ho
ù
ù
a (xi
a (xi
maêng, sa
maêng, sa
é
é
t the
t the
ù
ù
p, ...) t
p, ...) t
öø
öø
m
m
ñ
ñ
ie
ie
å
å
m cung ca
m cung ca
á
á
p (tra
p (tra
ï
ï
m
m
pha
pha
ù
ù
t), ky
t), ky
ù
ù
hie
hie
ä
ä
u la
u la
ø
ø
A
A
1
1
, A
, A
2
2
, ..., A
, ..., A
m
m
ñ
ñ
e
e
á
á
n n
n n
ñ
ñ
ie
ie
å
å
m tieâu
m tieâu
thu
thu
ï
ï
(tra
(tra
ï
ï
m thu), ky
m thu), ky
ù
ù
hie
hie
ä
ä
u la
u la
ø
ø
B
B
1
1
, B
, B
2
2
, ..., B
, ..., B
n
n
, bie
, bie
á
á
t ra
t ra
è
è
ng
ng
(1)
(1)
So
So
á
á
l
l
ö
ö
ô
ô
ï
ï
ng ha
ng ha
ø
ø
ng co
ng co
ù
ù
ô
ô
û
û
ca
ca
ù
ù
c tra
c tra
ï
ï
m pha
m pha
ù
ù
t A
t A
1
1
, A
, A
2
2
, ...,
, ...,
A
A
m
m
la
la
à
à
n l
n l
ö
ö
ô
ô
ï
ï
t la
t la
ø
ø
a
a
1
1
, a
, a
2
2
,..., a
,..., a
m
m
(2)
(2)
So
So
á
á
l
l
ö
ö
ô
ô
ï
ï
ng ha
ng ha
ø
ø
ng ca
ng ca
à
à
n ô
n ô
û
û
ca
ca
ù
ù
c tra
c tra
ï
ï
m thu B
m thu B
11
, B
, B
22
, ...,
, ...,
B
B
n
n
la
la
à
à
n l
n l
ö
ö
ô
ô
ï
ï
t la
t la
ø
ø
b
b
1
1
, b
, b
2
2
,..., b
,..., b
n
n
.
.
(3)
(3)
Chi ph
Chi ph
í
í
va
va
ä
ä
n chuye
n chuye
å
å
n mo
n mo
ä
ä
t
t
ñ
ñ
ôn vò ha
ôn vò ha
ø
ø
ng ho
ng ho
ù
ù
a t
a t
öø
öø
tra
tra
ï
ï
m pha
m pha
ù
ù
t A
t A
i
i
ñ
ñ
e
e
á
á
n tra
n tra
ï
ï
m thu B
m thu B
j
j
la
la
ø
ø
c
c
ij
ij
.
.
Haõy la
Haõy la
ä
ä
p ke
p ke
á
á
hoa
hoa
ï
ï
ch va
ch va
ä
ä
n ta
n ta
û
û
i ha
i ha
ø
ø
ng ho
ng ho
ù
ù
a sao cho
a sao cho
to
to
å
å
ng chi ph
ng chi ph
í
í
va
va
ä
ä
n ta
n ta
û
û
i tha
i tha
á
á
p nha
p nha
á
á
t va
t va
ø
ø
tho
tho
û
û
a maõn yeâu
a maõn yeâu
ca
ca
à
à
u thu
u thu
pha
pha
ù
ù
t.
t.
BA
BA
Ø
Ø
I TOA
I TOA
Ù
Ù
N VA
N VA
Ä
Ä
N TA
N TA
Û
Û
I DA
I DA
Ï
Ï
NG TO
NG TO
Å
Å
NG QUA
NG QUA
Ù
Ù
T
T
MOÂNH BA
MOÂNH BA
Ø
Ø
I TOA
I TOA
Ù
Ù
N VA
N VA
Ä
Ä
N TA
N TA
Û
Û
I
I
Ñ
Ñ
a
a
ë
ë
t x
t x
ij
ij
la
la
ø
ø
so
so
á
á
l
l
ö
ö
ô
ô
ï
ï
ng ha
ng ha
ø
ø
ng ca
ng ca
à
à
n va
n va
ä
ä
n chuye
n chuye
å
å
n t
n t
öø
öø
tra
tra
ï
ï
m
m
pha
pha
ù
ù
t A
t A
i
i
ñ
ñ
e
e
á
á
n tra
n tra
ï
ï
m thu B
m thu B
j
j
.
.
Ta co
Ta co
ù
ù
to
to
å
å
ng chi ph
ng chi ph
í
í
va
va
ä
ä
n ta
n ta
û
û
i:
i:
(1)
(1)
Tra
Tra
ï
ï
m pha
m pha
ù
ù
t, pha
t, pha
ù
ù
t he
t he
á
á
t ha
t ha
ø
ø
ng:
ng:
(2)
(2)
Tra
Tra
ï
ï
m thu, thu
m thu, thu
ñ
ñ
u
u
û
û
ha
ha
ø
ø
ng:
ng:
(3)
(3)
Yeâu ca
Yeâu ca
à
à
u tra
u tra
ï
ï
m pha
m pha
ù
ù
t, tra
t, tra
ï
ï
m thu
m thu
ñö
ñö
ô
ô
ï
ï
c tho
c tho
û
û
a
a
(
(
ñ
ñ
k caân ba
k caân ba
è
è
ng thu
ng thu
pha
pha
ù
ù
t).
t).
BA
BA
Ø
Ø
I TOA
I TOA
Ù
Ù
N VA
N VA
Ä
Ä
N TA
N TA
Û
Û
I DA
I DA
Ï
Ï
NG TO
NG TO
Å
Å
NG QUA
NG QUA
Ù
Ù
T
T
11
min
mn
ijij
ij
Zcx
1
,1,
n
iji
j
x
aim
1
,1,
m
ijj
i
x
bjn
11
mn
ij
ij
ab
Va
Va
ä
ä
y, moâ h
y, moâ h
ì
ì
nh toa
nh toa
ù
ù
n cu
n cu
û
û
a ba
a ba
ø
ø
i toa
i toa
ù
ù
n va
n va
ä
ä
n ta
n ta
û
û
i (BTVT)
i (BTVT)
da
da
ï
ï
ng to
ng to
å
å
ng qua
ng qua
ù
ù
t nh
t nh
ö
ö
sau:
sau:
T
T
ì
ì
m {x
m {x
ij
ij
} sao cho:
} sao cho:
BA
BA
Ø
Ø
I TOA
I TOA
Ù
Ù
N VA
N VA
Ä
Ä
N TA
N TA
Û
Û
I DA
I DA
Ï
Ï
NG TO
NG TO
Å
Å
NG QUA
NG QUA
Ù
Ù
T
T
11
1
1
11
min
,1,
,1,
0;0;0;0;
mn
ijij
ij
n
iji
j
m
ijj
i
mn
ijijijij
ij
Zcx
xaim
xbjn
x cabab
BA
BA
Ø
Ø
I TOA
I TOA
Ù
Ù
N VA
N VA
Ä
Ä
N TA
N TA
Û
Û
I D
I D
Ö
Ö
Ô
Ô
Ù
Ù
I DA
I DA
Ï
Ï
NG BA
NG BA
Ø
Ø
I TOA
I TOA
Ù
Ù
N QHTT
N QHTT
khai trie
khai trie
å
å
n BTVT va
n BTVT va
ø
ø
xe
xe
á
á
p he
p he
ä
ä
ra
ra
ø
ø
ng buo
ng buo
ä
ä
c d
c d
ö
ö
ô
ô
ù
ù
i da
i da
ï
ï
ng
ng
he
he
ä
ä
m + n ph
m + n ph
ö
ö
ông tr
ông tr
ì
ì
nh cu
nh cu
û
û
a m
a m
n bie
n bie
á
á
n nh
n nh
ö
ö
sau
sau
Ky
Ky
ù
ù
hie
hie
ä
ä
u A
u A
m+n,m
m+n,m
n
n
ma tra
ma tra
ä
ä
n he
n he
ä
ä
so
so
á
á
cu
cu
û
û
a hpt treân.
a hpt treân.
X
X
T
T
= (x
= (x
11
11
x
x
12
12
...
...
x
x
1n
1n
x
x
21
21
x
x
22
22
... x
... x
2n
2n
... x
... x
m1
m1
x
x
m2
m2
... x
... x
mn
mn
) la
) la
ø
ø
vectô co
vectô co
ä
ä
t go
t go
à
à
m m
m m
n tha
n tha
ø
ø
nh pha
nh pha
à
à
n; C = (c
n; C = (c
11
11
c
c
12
12
...
...
c
c
1n
1n
c
c
21
21
c
c
22
22
... c
... c
2n
2n
c
c
m1
m1
c
c
m2
m2
...
...
c
c
mn
mn
) la
) la
ø
ø
vectô do
vectô do
ø
ø
ng
ng
go
go
à
à
m m
m m
n tha
n tha
ø
ø
nh pha
nh pha
à
à
n; b
n; b
T
T
= (a
= (a
1
1
a
a
2
2
...
...
a
a
m
m
b
b
1
1
b
b
2
2
...
...
b
b
n
n
)
)
la
la
ø
ø
vectô co
vectô co
ä
ä
t go
t go
à
à
m m+ n tha
m m+ n tha
ø
ø
nh pha
nh pha
à
à
n.
n.
BA
BA
Ø
Ø
I TOA
I TOA
Ù
Ù
N VA
N VA
Ä
Ä
N TA
N TA
Û
Û
I DA
I DA
Ï
Ï
NG TO
NG TO
Å
Å
NG QUA
NG QUA
Ù
Ù
T
T
11121 1
212222
12
112111
122222
12
n
n
mmmnm
m
m
nnmnn
xxxa
xxxa
xxxa
x xxb
xxxb
x xxb
BTVT vie
BTVT vie
á
á
t d
t d
ö
ö
ô
ô
ù
ù
i da
i da
ï
ï
ng vectô va
ng vectô va
ø
ø
ma tra
ma tra
ä
ä
n nh
n nh
ö
ö
sau
sau
Mo
Mo
ä
ä
t vectô X tho
t vectô X tho
û
û
a (*) va
a (*) va
ø
ø
(**) go
(**) go
ï
ï
i la
i la
ø
ø
ph
ph
ö
ö
ông a
ông a
ù
ù
n
n
.
.
Mo
Mo
ä
ä
t P.A
t P.A
ñ
ñ
a
a
ï
ï
t c
t c
öï
öï
c tie
c tie
å
å
u th
u th
ì
ì
go
go
ï
ï
i la
i la
ø
ø
P.A.T.
P.A.T.
Ö
Ö
cu
cu
û
û
a BTVT.
a BTVT.
Mo
Mo
ä
ä
t ph
t ph
ö
ö
ông a
ông a
ù
ù
n X
n X
ñö
ñö
ô
ô
ï
ï
c go
c go
ï
ï
i la
i la
ø
ø
P.A.C.B
P.A.C.B
khi ca
khi ca
ù
ù
c
c
vectô co
vectô co
ä
ä
t A
t A
j
j
cu
cu
û
û
a ma tra
a ma tra
ä
ä
n he
n he
ä
ä
so
so
á
á
A
A
öù
öù
ng
ng
ù
ù
i ca
i ca
ù
ù
c
c
tha
tha
ø
ø
nh pha
nh pha
à
à
n x
n x
ijij
> 0 la
> 0 la
ø
ø
ñ
ñ
o
o
ä
ä
c la
c la
ä
ä
p tuye
p tuye
á
á
n t
n t
í
í
nh.
nh.
Mo
Mo
ä
ä
t P.A.C.B cu
t P.A.C.B cu
û
û
a BTVT co
a BTVT co
ù
ù
nhie
nhie
à
à
u nha
u nha
á
á
t la
t la
ø
ø
m + n
m + n
1 tha
1 tha
ø
ø
nh pha
nh pha
à
à
n d
n d
ö
ö
ông. Ne
ông. Ne
á
á
u mo
u mo
ä
ä
t P.A.C.B cu
t P.A.C.B cu
û
û
a BTVT
a BTVT
co
co
ù
ù
ñ
ñ
u
u
ù
ù
ng m + n
ng m + n
1 tha
1 tha
ø
ø
nh pha
nh pha
à
à
n d
n d
ö
ö
ông th
ông th
ì
ì
ñö
ñö
ô
ô
ï
ï
c
c
go
go
ï
ï
i la
i la
ø
ø
khoâng suy bie
khoâng suy bie
á
á
n.
n.
Ng
Ng
ö
ö
ô
ô
ï
ï
c la
c la
ï
ï
i,
i,
ñö
ñö
ô
ô
ï
ï
c go
c go
ï
ï
i la
i la
ø
ø
ph
ph
ö
ö
ông a
ông a
ù
ù
n c
n c
öï
öï
c bieân suy bie
c bieân suy bie
á
á
n
n
.
.
BA
BA
Ø
Ø
I TOA
I TOA
Ù
Ù
N VA
N VA
Ä
Ä
N TA
N TA
Û
Û
I DA
I DA
Ï
Ï
NG TO
NG TO
Å
Å
NG QUA
NG QUA
Ù
Ù
T
T
min
*
0**
T
zCX
AXb
X
ÝØJLÒÙ íæ ÞßH× ÌÑßGÒ Êß\Ò ÌßE×
ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ
ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ
̸-ò Ò¹«§» ݱ¹ Ì®3
ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ
¸¬¬°æññ²½¬®·ò½±ò½½
Nguyeãn Coâng T
PDF created with pdfFactory Pro trial version www.pdffactory.com
B
B
1
1
B
B
2
2
B
B
n
n
T
T
r
r
a
a
ï
ï
m
m
t
t
h
h
u
u
B
B
j
j
T
T
r
r
a
a
ï
ï
m
m
p
p
h
h
a
a
ù
ù
t
t
A
A
i
i
b
b
1
1
b
b
2
2
b
b
n
n
A
A
1
1
c
c
1
1
1
1
c
c
1
1
2
2
c
c
1
1
n
n
a
a
1
1
x
x
1
1
1
1
x
x
1
1
2
2
x
x
1
1
n
n
A
A
2
2
c
c
2
2
1
1
c
c
2
2
2
2
c
c
2
2
n
n
a
a
2
2
x
x
2
2
1
1
x
x
2
2
2
2
x
x
2
2
n
n
A
A
mm
c
c
mm11
c
c
mm22
c
c
mmnn
a
a
m
m
x
x
m
m
1
1
x
x
m
m
2
2
x
x
m
m
n
n
MTA
MTA
Û
Û
BA
BA
Ø
Ø
I TOA
I TOA
Ù
Ù
N D
N D
Ö
Ö
Ô
Ô
Ù
Ù
I DA
I DA
Ï
Ï
NG BA
NG BA
Û
Û
NG VA
NG VA
Ä
Ä
N TA
N TA
Û
Û
I
I
(1)
(1)
Ky
Ky
ù
ù
hie
hie
ä
ä
u (i, j) la
u (i, j) la
ø
ø
oâ treân
oâ treân
do
do
ø
ø
ng i va
ng i va
ø
ø
co
co
ä
ä
t j
t j
.
.
(2)
(2)
Chi ph
Chi ph
í
í
va
va
ä
ä
n chuye
n chuye
å
å
n c
n c
ij
ij
ñö
ñö
ô
ô
ï
ï
c ghi ô
c ghi ô
û
û
go
go
ù
ù
c treân
c treân
beân tra
beân tra
ù
ù
i cu
i cu
û
û
a oâ (i, j), l
a oâ (i, j), l
ö
ö
ô
ô
ï
ï
ng ha
ng ha
ø
ø
ng ca
ng ca
à
à
n va
n va
ä
ä
n chuye
n chuye
å
å
n
n
x
x
ij
ij
ñö
ñö
ô
ô
ï
ï
c ghi ô
c ghi ô
û
û
go
go
ù
ù
c d
c d
ö
ö
ô
ô
ù
ù
i beân pha
i beân pha
û
û
i cu
i cu
û
û
a oâ (i, j) bie
a oâ (i, j) bie
å
å
u
u
dieãn tuye
dieãn tuye
á
á
n
n
ñö
ñö
ô
ô
ø
ø
ng va
ng va
ä
ä
n chuye
n chuye
å
å
n t
n t
öø
öø
tra
tra
ï
ï
m pha
m pha
ù
ù
t A
t A
i
i
ñ
ñ
e
e
á
á
n tra
n tra
ï
ï
m thu B
m thu B
j
j
.
.
(3)
(3)
Trong BA
Trong BA
Û
Û
NG VA
NG VA
Ä
Ä
N TA
N TA
Û
Û
I, mo
I, mo
ä
ä
t oâ
t oâ
ñö
ñö
ô
ô
ï
ï
c go
c go
ï
ï
i la
i la
ø
ø
oâ
oâ
treo
treo
ne
ne
á
á
u no
u no
ù
ù
la
la
ø
ø
oâ duy nha
oâ duy nha
á
á
t treân do
t treân do
ø
ø
ng hay treân co
ng hay treân co
ä
ä
t.
t.
(4)
(4)
Nh
Nh
ö
ö
õng oâ
õng oâ
öù
öù
ng
ng
ù
ù
i x
i x
ij
ij
> 0 trong BA
> 0 trong BA
Û
Û
NG VA
NG VA
Ä
Ä
N TA
N TA
Û
Û
I
I
ñö
ñö
ô
ô
ï
ï
c go
c go
ï
ï
i la
i la
ø
ø
oâ cho
oâ cho
ï
ï
n
n
, nh
, nh
ö
ö
õng oâ kha
õng oâ kha
ù
ù
c go
c go
ï
ï
i la
i la
ø
ø
oâ loa
oâ loa
ï
ï
i
i
.
.
(5)
(5)
Mo
Mo
ä
ä
t daõy ca
t daõy ca
ù
ù
c oâ cho
c oâ cho
ï
ï
n, trong
n, trong
ñ
ñ
o
o
ù
ù
3 oâ lieân tie
3 oâ lieân tie
á
á
p
p
khoâng na
khoâng na
è
è
m treân cu
m treân cu
ø
ø
ng mo
ng mo
ä
ä
t do
t do
ø
ø
ng hay mo
ng hay mo
ä
ä
t co
t co
ä
ä
t th
t th
ì
ì
ñö
ñö
ô
ô
ï
ï
c go
c go
ï
ï
i la
i la
ø
ø
mo
mo
ä
ä
t daây chuye
t daây chuye
à
à
n
n
.
.
MTA
MTA
Û
Û
BA
BA
Ø
Ø
I TOA
I TOA
Ù
Ù
N D
N D
Ö
Ö
Ô
Ô
Ù
Ù
I DA
I DA
Ï
Ï
NG BA
NG BA
Û
Û
NG VA
NG VA
Ä
Ä
N TA
N TA
Û
Û
I
I
(6)
(6)
Mo
Mo
ä
ä
t daây chuye
t daây chuye
à
à
n khe
n khe
ù
ù
p k
p k
í
í
n
n
ñö
ñö
ô
ô
ï
ï
c go
c go
ï
ï
i la
i la
ø
ø
mo
mo
ä
ä
t
t
chu tr
chu tr
ì
ì
nh
nh
hay
hay
mo
mo
ä
ä
t vo
t vo
ø
ø
ng
ng
.
.
(7)
(7)
Mo
Mo
ä
ä
t ma tra
t ma tra
ä
ä
n (x
n (x
ij
ij
) la
) la
ø
ø
mo
mo
ä
ä
t
t
P.A
P.A
cu
cu
û
û
a BTVT ne
a BTVT ne
á
á
u no
u no
ù
ù
thoa
thoa
û
û
he
he
ä
ä
ra
ra
ø
ø
ng buo
ng buo
ä
ä
c. Mo
c. Mo
ä
ä
t P.A (x
t P.A (x
ij
ij
) la
) la
ø
ø
m c
m c
öï
öï
c tie
c tie
å
å
u
u
ha
ha
ø
ø
m mu
m mu
ï
ï
c tieâu th
c tieâu th
ì
ì
(x
(x
ij
ij
) la
) la
ø
ø
P.A.T.
P.A.T.
Ö
Ö
. cu
. cu
û
û
a ba
a ba
ø
ø
i toa
i toa
ù
ù
n.
n.
(8)
(8)
Mo
Mo
ä
ä
t P.A cu
t P.A cu
û
û
a BTVT khoâng ta
a BTVT khoâng ta
ï
ï
o tha
o tha
ø
ø
nh chu tr
nh chu tr
ì
ì
nh
nh
(vo
(vo
ø
ø
ng) th
ng) th
ì
ì
ñö
ñö
ô
ô
ï
ï
c go
c go
ï
ï
i la
i la
ø
ø
Ph
Ph
ö
ö
ông a
ông a
ù
ù
n c
n c
öï
öï
c bieân.
c bieân.
(9)
(9)
Mo
Mo
ä
ä
t P.A.C.B cu
t P.A.C.B cu
û
û
a BTVT co
a BTVT co
ù
ù
ñ
ñ
u
u
û
û
m+n
m+n
-
-
1 oâ cho
1 oâ cho
ï
ï
n th
n th
ì
ì
ñö
ñö
ô
ô
ï
ï
c go
c go
ï
ï
i la
i la
ø
ø
P.A.C.B khoâng suy bie
P.A.C.B khoâng suy bie
á
á
n
n
, ne
, ne
á
á
u co
u co
ù
ù
í
í
t
t
hôn m+n
hôn m+n
-
-
1 oâ cho
1 oâ cho
ï
ï
n
n
ñö
ñö
ô
ô
ï
ï
c go
c go
ï
ï
i la
i la
ø
ø
P.A.C.B suy bie
P.A.C.B suy bie
á
á
n
n
.
.
MTA
MTA
Û
Û
BA
BA
Ø
Ø
I TOA
I TOA
Ù
Ù
N D
N D
Ö
Ö
Ô
Ô
Ù
Ù
I DA
I DA
Ï
Ï
NG BA
NG BA
Û
Û
NG VA
NG VA
Ä
Ä
N TA
N TA
Û
Û
I
I
V
V
Í
Í
DU
DU
Ï
Ï
3.1.
3.1.
H
H
ì
ì
nh 2.1.
nh 2.1.
H
H
ì
ì
nh 2.2.
nh 2.2.
H
H
ì
ì
nh 2.3.
nh 2.3.
H
H
ì
ì
nh 2.4.
nh 2.4.
H
H
ì
ì
nh 2.5.
nh 2.5.
H
H
ì
ì
nh 2.1. ca
nh 2.1. ca
ù
ù
c oâ cho
c oâ cho
ï
ï
n, co
n, co
ù
ù
da
da
á
á
u
u
!
!
"
"
, ta
, ta
ï
ï
o tha
o tha
ø
ø
nh
nh
daây chuye
daây chuye
à
à
n, ca
n, ca
ù
ù
c oâ (1,1) va
c oâ (1,1) va
ø
ø
(4,3) la
(4,3) la
ø
ø
ca
ca
ù
ù
c oâ treo.
c oâ treo.
H
H
ì
ì
nh 2.2. ca
nh 2.2. ca
ù
ù
c oâ cho
c oâ cho
ï
ï
n ta
n ta
ï
ï
o tha
o tha
ø
ø
nh dy chuye
nh dy chuye
à
à
n,
n,
ca
ca
ù
ù
c oâ (4,1) va
c oâ (4,1) va
ø
ø
(3,3) la
(3,3) la
ø
ø
ca
ca
ù
ù
c oâ treo.
c oâ treo.
H
H
ì
ì
nh 2.3., H
nh 2.3., H
ì
ì
nh 2.4 va
nh 2.4 va
ø
ø
H
H
ì
ì
nh 2.5. ca
nh 2.5. ca
ù
ù
c oâ cho
c oâ cho
ï
ï
n ta
n ta
ï
ï
o
o
tha
tha
ø
ø
nh chu tr
nh chu tr
ì
ì
nh, khoâng co
nh, khoâng co
ù
ù
oâ treo.
oâ treo.
MTA
MTA
Û
Û
BA
BA
Ø
Ø
I TOA
I TOA
Ù
Ù
N D
N D
Ö
Ö
Ô
Ô
Ù
Ù
I DA
I DA
Ï
Ï
NG BA
NG BA
Û
Û
NG VA
NG VA
Ä
Ä
N TA
N TA
Û
Û
I
I
T
T
Í
Í
NH CHA
NH CHA
Á
Á
T 1:
T 1:
Ba
Ba
ø
ø
i toa
i toa
ù
ù
n va
n va
ä
ä
n ta
n ta
û
û
i luoân luoân co
i luoân luoân co
ù
ù
ph
ph
ö
ö
ông a
ông a
ù
ù
n to
n to
á
á
i
i
ö
ö
u.
u.
T
T
Í
Í
NH CHA
NH CHA
Á
Á
T 2:
T 2:
ù
ù
i mo
i mo
ä
ä
t ph
t ph
ö
ö
ông a
ông a
ù
ù
n ba
n ba
á
á
t ky
t ky
ø
ø
, so
, so
á
á
oâ
oâ
cho
cho
ï
ï
n cu
n cu
û
û
a ph
a ph
ö
ö
ông a
ông a
ù
ù
n khoâng v
n khoâng v
ö
ö
ô
ô
ï
ï
t qua
t qua
ù
ù
to
to
å
å
ng so
ng so
á
á
tra
tra
ï
ï
m pha
m pha
ù
ù
t va
t va
ø
ø
tra
tra
ï
ï
m thu
m thu
.
.
m + n
m + n
1 (
1 (
ù
ù
i
i
la
la
ø
ø
so
so
á
á
oâ cho
oâ cho
ï
ï
n cu
n cu
û
û
a P.A)
a P.A)
T
T
Í
Í
NH CHA
NH CHA
Á
Á
T 3:
T 3:
ù
ù
i mo
i mo
ä
ä
t ph
t ph
ö
ö
ông a
ông a
ù
ù
n co
n co
ù
ù
ñ
ñ
u
u
û
û
m+n
m+n
1 oâ
1 oâ
cho
cho
ï
ï
n th
n th
ì
ì
ù
ù
i mo
i mo
ä
ä
t oâ loa
t oâ loa
ï
ï
i ba
i ba
á
á
t ky
t ky
ø
ø
ñö
ñö
ô
ô
ï
ï
c
c
ñö
ñö
a va
a va
ø
ø
o
o
ph
ph
ö
ö
ông a
ông a
ù
ù
n seõ ta
n seõ ta
ï
ï
o tha
o tha
ø
ø
nh chu tr
nh chu tr
ì
ì
nh va
nh va
ø
ø
chu tr
chu tr
ì
ì
nh
nh
na
na
ø
ø
y la
y la
ø
ø
duy nha
duy nha
á
á
t.
t.
T
T
Í
Í
NH CHA
NH CHA
Á
Á
T 4:
T 4:
Ne
Ne
á
á
u l
u l
ö
ö
ô
ô
ï
ï
ng cung a
ng cung a
i
i
va
va
ø
ø
l
l
ö
ö
ô
ô
ï
ï
ng ca
ng ca
à
à
u b
u b
j
j
la
la
ø
ø
so
so
á
á
nguyeân th
nguyeân th
ì
ì
ba
ba
ø
ø
i toa
i toa
ù
ù
n co
n co
ù
ù
ø
ø
i gia
i gia
û
û
i nguyeân.
i nguyeân.
CA
CA
Ù
Ù
C T
C T
Í
Í
NH CHA
NH CHA
Á
Á
T CU
T CU
Û
Û
A BA
A BA
Ø
Ø
I TOA
I TOA
Ù
Ù
N VA
N VA
Ä
Ä
N TA
N TA
Û
Û
I
I
Xe
Xe
ù
ù
t ba
t ba
ø
ø
i toa
i toa
ù
ù
n va
n va
ä
ä
n ta
n ta
û
û
i sau
i sau
11
min
mn
ijij
ij
Zcx
1
1
,1,
,1,
n
iji
j
m
ijj
i
xaim
xbjn
TIEÂU CHUA
TIEÂU CHUA
Å
Å
N TO
N TO
Á
Á
I
I
Ö
Ö
U CU
U CU
Û
Û
A BA
A BA
Ø
Ø
I TOA
I TOA
Ù
Ù
N VA
N VA
Ä
Ä
N TA
N TA
Û
Û
I
I
11
0;0;0;0;
ijijij
mn
ij
ij
x
cab
ab
Vie
Vie
á
á
t la
t la
ï
ï
i ba
i ba
ø
ø
i toa
i toa
ù
ù
n
n
11
min
mn
ijij
ij
Zcx
1
1
,1,
,1,
m
ijj
i
n
iji
j
x
bjn
x aim
11
0;0;0;0;
ijijij
mn
ij
ij
x
cab
ab
ÝØJLÒÙ íæ ÞßH× ÌÑßGÒ Êß\Ò ÌßE×
ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ
ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ
̸-ò Ò¹«§» ݱ¹ Ì®3
ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ
¸¬¬°æññ²½¬®·ò½±ò½½
Nguyeãn Coâng T
PDF created with pdfFactory Pro trial version www.pdffactory.com
Liên hệ quảng cáo

Ba
Ba
ø
ø
i toa
i toa
ù
ù
n
n
ñ
ñ
o
o
á
á
i ngaãu cu
i ngaãu cu
û
û
a BTVT
a BTVT
T
T
ì
ì
m {u
m {u
i
i
,v
,v
j
j
} sao cho:
} sao cho:
ù
ù
i ca
i ca
ù
ù
c ca
c ca
ë
ë
p
p
ñ
ñ
o
o
á
á
i ngaãu:
i ngaãu:
x
x
ij
ij
0 va
0 va
ø
ø
v
v
j
j
u
u
i
i
c
c
ij
ij
,
,
i,j
i,j
Theo
Theo
ñ
ñ
ònh ly
ònh ly
ù
ù
ñ
ñ
o
o
ä
ä
le
le
ä
ä
ch bu
ch bu
ø
ø
th
th
ì
ì
ph
ph
ö
ö
ông a
ông a
ù
ù
n {x
n {x
ij
ij
} cu
} cu
û
û
a
a
BTVT co
BTVT co
ù
ù
P.A.T.
P.A.T.
Ö
Ö
la
la
ø
ø
to
to
à
à
n ta
n ta
ï
ï
i he
i he
ä
ä
tho
tho
á
á
ng {u
ng {u
i
i
, v
, v
j
j
} sao cho:
} sao cho:
Ne
Ne
á
á
u x
u x
ij
ij
> 0 th
> 0 th
ì
ì
v
v
j
j
u
u
i
i
= c
= c
ij
ij
,
,
Ne
Ne
á
á
u v
u v
j
j
u
u
i
i
< c
< c
ij
ij
th
th
ì
ì
x
x
ij
ij
= 0.
= 0.
Va
Va
ä
ä
y tieâu chua
y tieâu chua
å
å
n to
n to
á
á
i
i
ö
ö
u cu
u cu
û
û
a BTVT: v
a BTVT: v
j
j
u
u
i
i
c
c
ij
ij
,
,
i,j
i,j
u
u
i
i
:
:
ñö
ñö
ô
ô
ï
ï
c go
c go
ï
ï
i la
i la
ø
ø
the
the
á
á
vò do
vò do
ø
ø
ng
ng
.
.
v
v
jj
:
:
ñö
ñö
ô
ô
ï
ï
c go
c go
ï
ï
i la
i la
ø
ø
the
the
á
á
vò co
vò co
ä
ä
t
t
.
.
*
11
max
nm
jjii
ji
Zbvau
TIEÂU CHUA
TIEÂU CHUA
Å
Å
N TO
N TO
Á
Á
I
I
Ö
Ö
U CU
U CU
Û
Û
A BA
A BA
Ø
Ø
I TOA
I TOA
Ù
Ù
N VA
N VA
Ä
Ä
N TA
N TA
Û
Û
I
I
Treân ba
Treân ba
û
û
ng va
ng va
ä
ä
n ta
n ta
û
û
i, cho
i, cho
ï
ï
n oâ
n oâ
ñ
ñ
a
a
à
à
u tieân co
u tieân co
ù
ù
c
c
ö
ö
ô
ô
ù
ù
c ph
c ph
í
í
va
va
ä
ä
n chuye
n chuye
å
å
n be
n be
ù
ù
nha
nha
á
á
t va
t va
ø
ø
cho
cho
ï
ï
n x
n x
ij
ij
nh
nh
ö
ö
sau:
sau:
La
La
ë
ë
p la
p la
ï
ï
i qua
i qua
ù
ù
tr
tr
ì
ì
nh treân cho oâ tie
nh treân cho oâ tie
á
á
p theo cho
p theo cho
ñ
ñ
e
e
á
á
n
n
ñ
ñ
e
e
á
á
n khi yeâu ca
n khi yeâu ca
à
à
u tra
u tra
ï
ï
m pha
m pha
ù
ù
t va
t va
ø
ø
tra
tra
ï
ï
m thu
m thu
ñö
ñö
ô
ô
ï
ï
c
c
thoa
thoa
û
û
maõn.
maõn.
Ba
Ba
û
û
ng thu
ng thu
ñö
ñö
ô
ô
ï
ï
c
c
ù
ù
i ca
i ca
ù
ù
c x
c x
ij
ij
> 0 la
> 0 la
ø
ø
ph
ph
ö
ö
ông a
ông a
ù
ù
n c
n c
öï
öï
c
c
bieân cu
bieân cu
û
û
a ba
a ba
ø
ø
i toa
i toa
ù
ù
n.
n.
PH
PH
Ö
Ö
ÔNG PHA
ÔNG PHA
Ù
Ù
P CHI PH
P CHI PH
Í
Í
BE
BE
Ù
Ù
NHA
NHA
Á
Á
T
T
in,m
j
i
ijij
ba
abab
ij
ji
ij
ij
a:loaïi doøng i, b
b:loaïi coät j, a
ab:loaïi doøng i vaø coät j
x
V
V
í
í
du
du
ï
ï
3.2.
3.2.
Du
Du
ø
ø
ng ph
ng ph
ö
ö
ông pha
ông pha
ù
ù
p chi ph
p chi ph
í
í
be
be
ù
ù
nha
nha
á
á
t, t
t, t
ì
ì
m ph
m ph
ö
ö
ông a
ông a
ù
ù
n c
n c
öï
öï
c bin cu
c bin cu
û
û
a ba
a ba
ø
ø
i
i
toa
toa
ù
ù
n va
n va
ä
ä
n ta
n ta
û
û
i co
i co
ù
ù
da
da
ï
ï
ng ba
ng ba
û
û
ng sau
ng sau
ñ
ñ
aây
aây
Kie
Kie
å
å
m tra
m tra
a
a
i
i
=
=
b
b
j
j
= 175
= 175
PH
PH
Ö
Ö
ÔNG PHA
ÔNG PHA
Ù
Ù
P CHI PH
P CHI PH
Í
Í
BE
BE
Ù
Ù
NHA
NHA
Á
Á
T
T
10
10
14
14
4
4
3
3
6
6
60
60
16
16
7
7
3
3
5
5
16
16
45
45
11
11
5
5
10
10
1
1
5
5
28
28
13
13
2
2
7
7
8
8
13
13
42
42
45
45
35
35
25
25
40
40
30
30
T
T
P
P
28
28
35
35
25
25
12
12
30
30
18
18
7
7
20
20
PH
PH
Ö
Ö
ÔNG PHA
ÔNG PHA
Ù
Ù
P CHI PH
P CHI PH
Í
Í
BE
BE
Ù
Ù
NHA
NHA
Á
Á
T
T
P.A.C.B treân khoâng suy bie
P.A.C.B treân khoâng suy bie
á
á
n,
n,
ù
ù
i gia
i gia
ù
ù
trò Z = 980.
trò Z = 980.
10
10
14
14
4
4
3
3
6
6
60
60
16
16
7
7
3
3
5
5
16
16
45
45
11
11
5
5
10
10
1
1
5
5
28
28
13
13
2
2
7
7
8
8
13
13
42
42
45
45
35
35
25
25
40
40
30
30
T
T
P
P
Ph
Ph
ö
ö
ông pha
ông pha
ù
ù
p Vogels (1958) cho P.A.C.B kha
p Vogels (1958) cho P.A.C.B kha
ù
ù
to
to
á
á
t
t
theo ngh
theo ngh
ó
ó
a gia
a gia
ù
ù
trò ha
trò ha
ø
ø
m mu
m mu
ï
ï
c tieâu cu
c tieâu cu
û
û
a no
a no
ù
ù
kha
kha
ù
ù
ga
ga
à
à
n
n
ù
ù
i P.A.T.
i P.A.T.
Ö
Ö
. Ph
. Ph
ö
ö
ông pha
ông pha
ù
ù
p
p
ñö
ñö
ô
ô
ï
ï
c moâ ta
c moâ ta
û
û
nh
nh
ö
ö
sau
sau
(1) Treân ba
(1) Treân ba
û
û
ng va
ng va
ä
ä
n ta
n ta
û
û
i, t
i, t
í
í
nh hie
nh hie
ä
ä
u so
u so
á
á
gi
gi
ö
ö
õa chi ph
õa chi ph
í
í
be
be
ù
ù
th
th
öù
öù
hai
hai
ù
ù
i chi ph
i chi ph
í
í
be
be
ù
ù
th
th
öù
öù
nha
nha
á
á
t.
t.
(2) Cho
(2) Cho
ï
ï
n so
n so
á
á
ù
ù
n nha
n nha
á
á
t trong ca
t trong ca
ù
ù
c hie
c hie
ä
ä
u treân va
u treân va
ø
ø
phaân
phaân
pho
pho
á
á
i to
i to
á
á
i
i
ñ
ñ
a cho oâ co
a cho oâ co
ù
ù
chi ph
chi ph
í
í
be
be
ù
ù
nha
nha
á
á
t mo
t mo
ä
ä
t l
t l
ö
ö
ô
ô
ï
ï
ng
ng
x
x
ij
ij
= min(a
= min(a
i
i
, b
, b
j
j
), sau
), sau
ñ
ñ
o
o
ù
ù
t
t
í
í
nh la
nh la
ï
ï
i hie
i hie
ä
ä
u so
u so
á
á
do
do
ø
ø
ng (co
ng (co
ä
ä
t).
t).
(3) Qua
(3) Qua
ù
ù
tr
tr
ì
ì
nh treân
nh treân
ñö
ñö
ô
ô
ï
ï
c la
c la
ë
ë
p la
p la
ï
ï
i cho
i cho
ñ
ñ
e
e
á
á
n khi ch
n khi ch
æ
æ
co
co
ø
ø
n la
n la
ï
ï
i mo
i mo
ä
ä
t do
t do
ø
ø
ng hay mo
ng hay mo
ä
ä
t co
t co
ä
ä
t duy nha
t duy nha
á
á
t.
t.
(4) Ba
(4) Ba
û
û
ng thu
ng thu
ñö
ñö
ô
ô
ï
ï
c
c
ù
ù
i ca
i ca
ù
ù
c {x
c {x
ij
ij
} la
} la
ø
ø
ph
ph
ö
ö
ông a
ông a
ù
ù
n c
n c
öï
öï
c
c
bieân cu
bieân cu
û
û
a ba
a ba
ø
ø
i toa
i toa
ù
ù
n.
n.
PH
PH
Ö
Ö
ÔNG PHA
ÔNG PHA
Ù
Ù
P VOGELS
P VOGELS
V
V
í
í
du
du
ï
ï
3.3:
3.3:
Du
Du
ø
ø
ng ph
ng ph
ö
ö
ông pha
ông pha
ù
ù
p Vogels, t
p Vogels, t
ì
ì
m
m
ph
ph
ö
ö
ông a
ông a
ù
ù
n c
n c
öï
öï
c bieân cu
c bieân cu
û
û
a ba
a ba
ø
ø
i toa
i toa
ù
ù
n va
n va
ä
ä
n ta
n ta
û
û
i
i
co
co
ù
ù
da
da
ï
ï
ng ba
ng ba
û
û
ng sau
ng sau
Kie
Kie
å
å
m tra
m tra
a
a
i
i
=
=
b
b
j
j
= 175
= 175
PH
PH
Ö
Ö
ÔNG PHA
ÔNG PHA
Ù
Ù
P VOGELS
P VOGELS
10
10
14
14
4
4
3
3
6
6
60
60
16
16
7
7
3
3
5
5
16
16
45
45
11
11
5
5
10
10
1
1
5
5
28
28
13
13
2
2
7
7
8
8
13
13
42
42
45
45
35
35
25
25
40
40
30
30
T
T
P
P
ÝØJLÒÙ íæ ÞßH× ÌÑßGÒ Êß\Ò ÌßE×
ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ
ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ
̸-ò Ò¹«§» ݱ¹ Ì®3
ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ
¸¬¬°æññ²½¬®·ò½±ò½½
Nguyeãn Coâng T
PDF created with pdfFactory Pro trial version www.pdffactory.com
Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Bài toán vận tải (TS. Nguyễn Công Trí)

Các tính chất và tiêu chuẩn tối ưu của bài toán vận tảiCác phương pháp tìm phương án cực biên đầu tiên của bài toán vận tảiThuật giải thế vị cho bài toán vận tải...

Chia sẻ bởi
Lượt xem: 12681     Tải về: 75     Lượt mua: 3     Định dạng:  
Gửi nhận xét của bạn về tài liệu này
comments powered by Disqus
Tài liệu liên quan
Có thể bạn quan tâm