Bài giảng Phương pháp định lượng trong quản lý: Chương 4 - PGS.TS. Nguyễn Thống

TRƯỜNG ĐẠI HỌC BÁCH KHOA TP. HCM
Khoa KTXD - Bộ môn KTTNN

Giảng viên: PGS. TS. NGUYỄN THỐNG

E-mail: nguyenthong@hcmut.edu.vn or nthong56@yahoo.fr
Web: http://www4.hcmut.edu.vn/~nguyenthong
10/20/2017

1

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ

NỘI DUNG MÔN HỌC
CHƯƠNG 1: Giôùi thieäu Phöông phaùp ñònh
löôïng trong Quaûn lyù.
CHƯƠNG 2: Quy hoaïch tuyeán tính.
CHƯƠNG 3: Cô sôû lyù thuyeát ra quyeát ñònh.
CHƯƠNG 4: Baøi toaùn vaän taûi.
CHƯƠNG 5: Quaûn lyù kho.
CHƯƠNG 6: Ra quyeát ñònh ña muïc tieâu.
CHƯƠNG 7: Lyù thuyeát saép haøng.
10/20/2017
2

Tél. (08) 38 640 979 - 098 99 66 719

PHÖÔNG PHAÙP ÑÒNH
LÖÔÏNG TRONG QUAÛN LYÙ

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ

NỘI DUNG MÔN HỌC (tt)
CHƯƠNG 8: Phaân tích nhaân toá chính (PCA).
CHÖÔNG 8Bis: Phöông phaùp AHP
CHƯƠNG 9: Qui hoïach ñoäng
CHƯƠNG 10: Hoaïch ñònh döï aùn.
CHƯƠNG 11: Xích Markov
CHƯƠNG 12: Lyù thuyeát troø chôi.
CHƯƠNG 13: Moâ phoûng Monte Carlo.
10/20/2017

3

TÀI LIỆU THAM KHẢO
1. Phương pháp định lượng trong quản lý.
NXB Trẻ 1999. Tác giả PGS. Dr. Nguyễn
Thống & Dr. Cao Hào Thi.
2. Phân tích số liệu và áp dụng vào dự báo.
NXB Thanh Niên 2000. Tác giả PGS. Dr.
Nguyễn Thống
3. Phần mềm QSB, Crystal Ball
10/20/2017

4

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chöông 4: Baøi toaùn vaän taûi

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chöông 4: Baøi toaùn vaän taûi

GIỚI THIỆU

Baøi toaùn naøy ñaàu tieân ñöôïc trình baøy
trong coâng taùc vaän chuyeån haøng hoùa.
Vì vaäy coù teân laø baøi toaùn vaän taûi.
 Nhöng moâ hình cuûa baøi toaùn vaän taûi,
sau khi ñöôïc coâng boá, ñaõ ñöôïc raát
nhieàu ngaønh kinh teá khaùc nhau öùng
duïng nhö laõnh vöïc quaân söï, quaûn lyù, y
teá,...

Baøi toaùn vaän taûi (1939) laø daïng ñaëc bieät cuûa
Baøi toaùn Qui Hoaïch Tuyeán Tính  do ñoù coù
theå giaûi baøi toaùn theo caùc phöông phaùp ñaõ
trình baøy trong Qui Hoaïch Tuyeán Tính.
Tuy nhieân caáu truùc baøi toaùn coù nhöõng tính chaát
ñaëc bieät neân coù phöông phaùp giaûi rieâng höõu
hieäu hôn.

10/20/2017

PGS. Dr. Nguyễn Thống

5

10/20/2017

PGS. Dr. Nguyễn Thống

6

1

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chöông 4: Baøi toaùn vaän taûi

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chöông 4: Baøi toaùn vaän taûi

MOÂ HÌNH TOÅNG QUAÙT

MOÂ HÌNH TOÅNG QUAÙT

Coù n traïm phaùt haøng. Moãi traïm kyù
hieäu laø Ai ( i= 1,n ). Khaû naêng cung caáp
haøng hoùa cuûa traïm phaùt thöù i laø ai.
Coù m traïm thu haøng. Moãi traïm kyù hieäu
laø Bj ( j = 1,m ). Nhu caàu haøng hoùa cuûa
traïm thu thöù j laø bj.
10/20/2017

7

PGS. Dr. Nguyễn Thống

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chöông 4: Baøi toaùn vaän taûi

SOÁ LIEÄU DAÏNG BAÛNG
Ai

b1

b2

.

bm

a1

x11(c11)

x12(c12)

.

x1m

a2

x21

x22

.

.

.

xn1

xn2

an

Phát hàng
10/20/2017

PGS. Dr. Nguyễn Thống

(Coâng suaát traïm phaùt)
m

Chi phí ñôn vò
.
.
.

Raøng buoäc:

xnm

Bieán quyeát ñònh
(lượng hàng hóa)

xij >=0
9

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chöông 4: Baøi toaùn vaän taûi

Ghi chuù: Neáu giöõa moät traïm Ai naøo ñoù
ñeán moät traïm Bj naøo ñoù khoâng coù ñöôøng
vaän chuyeån  nghóa laø giöõa 2 traïm ñoù
khoâng theå toå chöùc vaän chuyeån ñöôïc
 khi ñoù ta laáy ñôn gía vaän chuyeån Cij =
M vôùi M laø moät soá döông lôùn tuøy yù.
 Trong tröôøng hôïp ñoù lôøi giaûi cho xij seõ
laø 0.
10/20/2017

PGS. Dr. Nguyễn Thống

8

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chöông 4: Baøi toaùn vaän taûi

x2m

.

10/20/2017

PGS. Dr. Nguyễn Thống

Bieán quyeát ñònh: Goïi xij laø soá löôïng ñôn vò
haøng hoùa vaän chuyeån töø traïm phaùt thöù i ñeán
traïm thu thöù j.
MinZ   Cij x ij
Haøm muïc tieâu:

Nhận hàng

Bj

Chi phí vaän chuyeån moät ñôn vò haøng hoùa
töø Ai ñeán Bj laø Cij.
HÀM MỤC TIÊU CỦA BÀI TOÁN
 Xaùc ñònh phöông aùn vaän chuyeån sao
cho toång chi phí vaän chuyeån laø nhoû nhaát.

11

10/20/2017

PGS. Dr. Nguyễn Thống

x

ij

 ai

j 1

i=1,n

(Coâng suaát traïm thu)
n

x

ij

 b j j=1,m10

i 1

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chöông 4: Baøi toaùn vaän taûi

Tröôøng hôïp: Cung = Caàu

n

a
i 1

i



m

b

j

j 1

Ví du 1: Baøi toaùn vaän chuyeån chaát ñoát
ÔÛ caùc traïm phaùt A vaø B coù 150 taán vaø 90 taán
chaát ñoát. Phaûi cung caáp cho caùc vò trí 1, 2, 3
töông öùng 60, 70 vaø 110 taán chaát ñoát ñoù. Chi
phí chôû 1 taán chaát ñoát töø A ñeán caùc vò trí 1, 2,
3 töông öùng laø 6, 10 vaø 4$ coøn töø B ñeán 1, 2, 3
laø 12, 2 vaø 8$. Haõy laäp keá hoaïch vaän chuyeån
toái öu sao cho toång chi phí vaän chuyeån laø beù
nhaát.
10/20/2017
12

PGS. Dr. Nguyễn Thống

2

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chöông 4: Baøi toaùn vaän taûi
n 2

a

i

 150  90  240

j

 60  70  110  240

i 1

m 3

b

 Cung = Caàu

j 1

Traïm thu
Traïm phaùt
A
B
10/20/2017

1

2

3

60T

70T

110T

150T

x11=?(6$)

x12=?(10$)

x21=?(12$)

x22=?(2$)

x23=?(8$)
13

Trong tröôøng hôïp khoâng coù söï caân baèng giöõa
Cung vaø Caàu, ta coù theå luoân luoân trôû veà baøi
toaùn caân baèng Cung vaø Caàu baèng caùch theâm
vaøo nguoàn Cung giaû hoaëc Caàu giaû vaø gaùn caùc
chi phí vaän chuyeån LÔÙN töông öùng tuyeán vaän
chuyeån.
 Lôøi giaûi vaãn tìm ñöôïc sau khi loaïi caùc nguoàn
giaû töø keát quaû tìm ra cuoái cuøng.

x13=?(4$)

90T

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chöông 4: Baøi toaùn vaän taûi

PGS. Dr. Nguyễn Thống

10/20/2017

PGS. Dr. Nguyễn Thống

14

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chöông 4: Baøi toaùn vaän taûi

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chöông 4: Baøi toaùn vaän taûi

PHƯƠNG PHÁP GIẢI BÀI TOÁN VẬN TẢI
Vì baøi toaùn vaän taûi cuõng laø moät baøi toaùn QHTT
neân hoaøn toaøn coù theå giaûi baèng phöông phaùp
ñôn hình. Nhöng do tính chaát ñaëc thuø cuûa baøi
toaùn vaän taûi neân ta coù nhöõng phöông phaùp
GIAÛI ñôn giaûn hôn.
Coù 3 phöông phaùp  LÔØI GIAÛI GAÀN ÑUÙNG:
Phöông phaùp goùc Taây Baéc  P/aùn ñaàu (The
North West Corner Method).

PHƯƠNG PHÁP GIẢI BÀI TOÁN VẬN
TẢI
Phöông phaùp chi phí beù nhaát Cmin (The
Least Cost Method).
Phöông phaùp xaáp xæ cuûa Vogel (Vogel’s
Approximation Method - VAM).
 PHÖÔNG PHAÙP TOÅNG QUAÙT (tìm lôøi
giaûi chính xaùc)  PHÖÔNG PHAÙP THEÁ
VÒ

10/20/2017

PGS. Dr. Nguyễn Thống

15

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chöông 4: Baøi toaùn vaän taûi

PHƯƠNG PHÁP GÓC TÂY BẮC
(Dantzig)

10/20/2017

PGS. Dr. Nguyễn Thống

16

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chöông 4: Baøi toaùn vaän taûi

Xuaát phaùt töø oâ naèm ôû goùc Taây Baéc, töùc oâ
(1,1) ta tieán daàn xuoáng oâ ôû goùc Ñoâng Nam,
töùc oâ (n,m).
 Treân ñöôøng ñi gaëp oâ naøo ta phaân phoái cho
oâ ñoù moät löôïng haøng lôùn nhaát coù theå ñöôïc
döïa treân nguyeân taéc ñaûm baûo ñieàu kieän
caân baèng giöõa soá cung vaø soá caàu.
 Khi phaân phoái heát thì döøng laïi.


10/20/2017

PGS. Dr. Nguyễn Thống

17

10/20/2017

18

PGS. Dr. Nguyễn Thống

3

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chöông 4: Baøi toaùn vaän taûi

Sau ñoù kieåm tra xem toång oâ choïn coù baèng
(m + n - 1) hay khoâng. OÂ choïn laø oâ coù xij
> 0.
Neáu ñieàu kieän naày thoûa maõn thì phöông
aùn nhaän ñöôïc goïi laø phöông aùn ñaàu.
Nhaän xeùt: Lôøi giaûi cuûa phöông aùn ñaàu
trong phöông phaùp goùc Taây Baéc ít khi
toái öu bôûi vì khi giaûi KHOÂNG quan taâm
ñeán chi phí vaän chuyeån.
10/20/2017

19

PGS. Dr. Nguyễn Thống

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chöông 4: Baøi toaùn vaän taûi

Laáy laïi soá lieäu ôû treân:
Traïm thu
Traïm phaùt

1

2

3

60T

70T

110T

A

150T

x11=?(6$)

x12=?(10$)

x13=?(4$)

B

90T

x21=?(12$)

x22=?(2$)

x23=?(8$)

Tìm lôøi giaûi sô boä baèng phöông phaùp
goùc Taây Baéc.
10/20/2017

20

PGS. Dr. Nguyễn Thống

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chöông 4: Baøi toaùn vaän taûi

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chöông 4: Baøi toaùn vaän taûi

Laáy ví duï 1 noùi treân:

Baøi taäp: Laáy laïi ví duï 1 noùi treân, duøng
phöông phaùp goùc Taây Baéc ñeå tìm lôøi
giaûi sô boä vôùi caùc tröôøng hôïp sau:
1. Khaû naêng cung caáp cuûa traïm A baây giôø
laø 100T.
2. Khaû naêng traïm thu 3 laø 80T.
(Chuù yù: Trong tröôøng hôïp Cung < Caàu
 Boå sung traïm Cung GIAÛ)

Traïm thu
Traïm phaùt

1

A

3

70T

110T

60

70

20

150T

B

2

60T
90T

90

Ví duï phöông phaùp giaûi Taây Baéc:
Z = 60*6 + 70*10 + 20*4 + 90*8 = 1860 $
10/20/2017

21

PGS. Dr. Nguyễn Thống

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chöông 4: Baøi toaùn vaän taûi
Ví duï: Baøi toaùn quaûn lyù saûn xuaát (p/p goùc Taây Baéc)
Moät Coâng ty coù 3 nhaø maùy 1, 2, 3. Moãi nhaø maùy coù
theå saûn xuaát 5 loaïi saûn phaåm 1, 2, 3, 4, 5 vôùi khaû
naêng xuaát vaø tieâu thuï toång 5 loaïi nhö sau.
1
40 ñôn vò

2
60

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chöông 4: Baøi toaùn vaän taûi

Chi phí saûn xuaát

1

2

3

4

5

Khaû naêng
baùn

30

40

70

40

60
23

Saûn phaåm
Nhaø maùy

1

2

3

4

5

1

20

19

14

21

16

2

3
90

Saûn phaåm

10/20/2017

22

15

20

13

19

16

3

Nhaø maùy
Khaû naêng saûn
xuaát 5 loaïi

PGS. Dr. Nguyễn Thống

10/20/2017

PGS. Dr. Nguyễn Thống

18

15

18

20

?

Bieát raèng nhaø maùy 3 khoâng theå saûn xuaát saûn phaåm 5.
Giaû thieát moãi ñôn vò saûn phaåm ñeàu coù lôïi nhuaän
baèng nhau. Vaäy moãi nhaø maùy neân saûn xuaát bao
nhieâ
10/20/2017 u ñôn vò cho moãi loaïi saûn phaåm ?
24

PGS. Dr. Nguyễn Thống

4

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chöông 4: Baøi toaùn vaän taûi
Vì khoâng coù söï caân baèng giöõa saûn xuaát vaø nhu caàu 
theâm moät nhaø maùy giaû soá 4 coù khaû naêng saûn xuaát
240 - 190 = 50 ñôn vò saûn phaåm vôùi chi phí saûn xuaát
baèng 0.
Saûn phaåm
Nhaø maùy
1
2
3
4
5
30
1

40

2

60

3

90

4

PGS. Dr. Nguyễn Thống50
10/20/2017

40

30

40

60

40

10

30
40

50 25

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chöông 4: Baøi toaùn vaän taûi

Khi duøng phöông phaùp goùc Taây Baéc
ta khoâng ñeå yù ñeán chi phí vaän
chuyeån Cij. Do ñoù keát quaû coù ñöôïc ôû
phöông aùn ñaàu coøn caùch xa phöông
aùn toái öu.
 Phöông phaùp Cmin khaéc phuïc ñöôïc
moät phaàn nhöôïc ñieåm naøy.
10/20/2017

PGS. Dr. Nguyễn Thống

27

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chöông 4: Baøi toaùn vaän taûi

Trong quaù trình phaân phoái caàn ñaûm
baûo ñieàu kieän caân baèng giöõa soá cung
vaø soá caàu.
Kieåm tra ñieàu kieän : Toång soá oâ choïn
=m+n-1

10/20/2017

PGS. Dr. Nguyễn Thống

PHƯƠNG PHÁP CHI PHÍ
BÉ NHẤT CMIN

10

30

70

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chöông 4: Baøi toaùn vaän taûi

29

10/20/2017

26

PGS. Dr. Nguyễn Thống

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chöông 4: Baøi toaùn vaän taûi

Trong phöông phaùp Cmin, tröôùc tieân ta
tìm oâ coù trò soá Cij nhoû nhaát. Phaân phoái
löôïng haøng lôùn nhaát coù theå coù ñöôïc vaøo
oâ ñoù.
Sau ñoù ta phaân phoái haøng hoùa cho oâ coù
trò soá Cij nhoû nhaát trong caùc oâ coøn laïi.
Cöù tieáp tuïc nhö theá cho ñeán heát.
10/20/2017

28

PGS. Dr. Nguyễn Thống

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chöông 4: Baøi toaùn vaän taûi

Phöông phaùp Cmin. Laáy ví duï 1 noùi treân:
Traïm thu
Traïm phaùt

1

2

60T

70T

A

150T

40(6)3

B

90T

20(12)4

3
110T
110(4)2

70 (2)1

Trình
töï choïn

Ví duï phöông phaùp giaûi Cmin
Z = 40*6 + 110*4 + 70*2 + 20*12 = 1060 $ (1860$)
chæ trình töï phaân boá khoái löôïng vaän chuyeån
10/20/2017

PGS. Dr. Nguyễn Thống

30

5