Bài giảng Phương pháp định lượng trong quản lý: Chương 4

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

TRƯỜNG ĐẠI HỌC BÁCH KHOA TP. HCM

Khoa KTXD - Bộ môn KTTNN

NỘI DUNG MÔN HỌC

löôïng trong Quaûn lyù.

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

11/26/2013

CHƯƠNG 1: Giôùi thieäu Phöông phaùp ñònh 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.

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

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

NỘI DUNG MÔN HỌC (tt)

KMO

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

Chương 8: Phân tích thành phần chính (PCA). Chương 9: Kiểm định Cronbach’s Alpha & Chương 10: Phương pháp AHP Chương 11: Qui hoạch động Chương 12: Hoạch định dự án Chương 13: Xích Markov Chương 14: Lý thuyết trò chơi. Chương 15: Mô phỏng Monte Carlo.

3 11/26/2013

11/26/2013

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi • 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.

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 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.

 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á,...

11/26/2013

PGS. Dr. Nguyễn Thống

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 • Chi phí vaän chuyeån moät ñôn vò haøng hoùa

töø Ai ñeán Bj laø Cij.

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.

HÀM MỤC TIÊU CỦA BÀI TOÁ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.

• 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.

11/26/2013

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

SOÁ LIEÄU DAÏNG BAÛNG

Nhận hàng

.

Bj Ai

b1

b2

bm

• 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. • Haøm muïc tieâu:

. a1 x11(c11) x12(c12) x1m

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

. a2 x21 x22 i=1,n

.

x2m Chi phí ñôn vò .

.

• Raøng buoäc:

an xn1 xn2 xnm

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

11/26/2013

xij >=0 Phát hàng j=1,m 10 Bieán quyeát ñònh (lượng hàng hóa)

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

• 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.

Tröôøng hôïp: Cung = Caàu 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.

11/26/2013

PGS. Dr. Nguyễn Thống

2

 Cung = Caàu

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

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

Traïm thu Traïm phaùt

1

2

3 giaû töø keát quaû tìm ra cuoái cuøng.

70T

110T

A

150T

90T

60T x11=?(6$) x21=?(12$)

x12=?(10$) x13=?(4$) x23=?(8$) x22=?(2$)

B 11/26/2013

11/26/2013

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 GIẢI BÀI TOÁ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

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 GIẢI BÀI TOÁ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.

Approximation Method - VAM).

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 PHAÙP TOÅNG QUAÙT (tìm lôøi giaûi chính xaùc)  PHÖÔNG PHAÙP THEÁ VÒ

11/26/2013

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

• 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).

PHƯƠNG PHÁP GÓC TÂY BẮC (Dantzig)

 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. 

11/26/2013

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 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:

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.

Traïm thu Traïm phaùt

1

2

3 Neáu ñieàu kieän naày thoûa maõn thì phöông

70T

110T

aùn nhaän ñöôïc goïi laø phöông aùn ñaàu.

A

150T

B

90T

60T x11=?(6$) x21=?(12$)

x12=?(10$) x13=?(4$) x23=?(8$) x22=?(2$)

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

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.

11/26/2013

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

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

2

3 60T

70T

110T

1. Khaû naêng cung caáp cuûa traïm A baây giôø

laø 100T.

A

150T

60

70

20 90T

B

90 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Û)

Laáy ví duï 1 noùi treân: Traïm thu Traïm phaùt Ví duï phöông phaùp giaûi Taây Baéc: Z = 606 + 7010 + 204 + 908 = 1860 $

11/26/2013

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 3 90 Nhaø maùy Khaû naêng saûn xuaát 5 loaïi

Saûn phaåm Nhaø maùy 1 2 3

4 21 19 20

1 20 15 18

5 16 16 ?

3 14 13 18

Saûn phaåm 1 2 3 4 5

30 40 70 40 60 Khaû naêng baùn

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 2 19 20 15 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âu ñôn vò cho moãi loaïi saûn phaåm ?

11/26/2013

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 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.

1 2 3 4 5 Saûn phaåm Nhaø maùy

PHƯƠNG PHÁP CHI PHÍ BÉ NHẤT CMIN

11/26/2013

60 30 30 40 10 30 70 30 40 40 40 60 10 90 50 50 1 2 3 4 PGS. Dr. Nguyễn Thống

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

• 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ù.

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.

• 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.

 Phöông phaùp Cmin khaéc phuïc ñöôïc

• Cöù tieáp tuïc nhö theá cho ñeán heát.

moät phaàn nhöôïc ñieåm naøy.

11/26/2013

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

2

3

1

• 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.

60T

70T

110T

A

150T

40(6)3

110(4)2

• Kieåm tra ñieàu kieän : Toång soá oâ choïn

20(12)4

70 (2)1

90T

B

= m + n - 1

11/26/2013

Trình töï choïn

PGS. Dr. Nguyễn Thống

Phöông phaùp Cmin. Laáy ví duï 1 noùi treân: Traïm thu Traïm phaùt Ví duï phöông phaùp giaûi Cmin Z = 406 + 1104 + 702 + 2012 = 1060 $ (1860$) chæ trình töï phaân boá khoái löôïng vaän chuyeån PGS. Dr. Nguyễn Thống

5

2

1

3

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi Baøi taäp: Tìm lôøi giaûi baèng phöông phaùp Cmin : Traïm thu Traïm phaùt

1

2

3

PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi Baøi taäp: Tìm lôøi giaûi baèng phöông phaùp Cmin : Traïm thu Traïm phaùt

70T

110T

70T

110T

A

90T

A

90T

B

150T

B

150T

60T x11=?(6$) x21=?(12$)

x12=?(10$) x13=?(4$) x23=?(8$) x22=?(2$)

60T x11=?(6$) x21=?(12$)

x12=?(10$) x13=?(4$) x23=?(4$) x22=?(2$)

Traïm thu Traïm phaùt

1

2

3 (Xét trường hợp có một số phương án có chi phí như nhau)

70T

110T

80T

11/26/2013

A 11/26/2013 B

120T

PGS. Dr. Nguyễn Thống

60T x11=?(6$) x21=?(12$)

x12=?(10$) x13=?(4$) x23=?(8$) x22=?(2$)

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 PHAÙP XAÁP XÆ CUÛA VOGEL • Trong phöông phaùp Cmin ta ñaõ xem xeùt ñeán chi phí vaän chuyeån Cij nhöng chöa chuù yù ñeán hieäu soá cuûa chuùng (söï cheânh leäch veà chi phí vaän chuyeån).

PHƯƠNG PHÁP XẤP XỈ VOGEL

 Vì vaäy coù theå xaûy ra tröôøng hôïp böôùc tröôùc thì toát nhöng böôùc sau laïi xaáu (böôùc tröôùc rôi vaøo oâ coù chi phí thaáp nhöng böôùc sau rôi vaøo oâ coù chi phí raát cao).

11/26/2013

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 XAÁP XÆ CUÛA VOGEL • Phöông phaùp Vogel khaéc phuïc ñöôïc

nhöôïc ñieåm naày

CAÙC BÖÔÙC CUÛA PHÖÔNG PHAÙP VOGEL: • Böôùc 1: Treân moãi haøng vaø moãi coät choïn chi phí Cij beù nhaát vaø Cij beù thöù hai. Laáy hieäu soá cuûa chuùng roài ghi vaøo oâ beân phaûi vaø beân döôùi baûng. Tìm soá lôùn nhaát trong caùc hieäu soá ñoù.

Traïm thu Traïm phaùt

 Cho keát quaû toát hôn, gaàn baèng hoaëc baèng keát quaû lôøi giaûi toái öu.

2(6-4)

A B

1 60T 6$ 12$

150T 90T

2 70T 10$ 2$

3 110T 4$ 8$

6(8-2)

11/26/2013

6 (12-6) 8 4

PGS. Dr. Nguyễn Thống

6

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

Böôùc 2: Phaân phoái tröôùc löôïng haøng cho haøng (hoaëc coät) coù trò soá hieäu soá lôùn nhaát (coät traïm thu soá 2).

Böôùc 2: Phöông phaùp Vogel : Traïm thu Traïm phaùt

150T 90T

A B

2 6

2 70T 10$ (70)2$ 8

1 60T 6$ 12$ 6

3 110T 4$ 8$ 4

• Luùc phaân phoái, thì phaân phoái löôïng haøng lôùn nhaát coù theå ñöôïc vaøo oâ coù Cij nhoû nhaát cuûa haøng vaø coät öùng vôùi hieäu soá lôùn nhaát noùi treân (haøng traïm phaùt B).

• Trong quaù trình phaân phoái caàn ñaûm baûo

Choïn coät soá [2] phaân phoái vì giaù trò (8) laø lôùn nhaát vaø löïa choïn oâ treân coät naøy coù chi phí beù nhaát  oâ B-2

söï caân baèng giöõa soá cung vaø soá caàu.

11/26/2013

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

• Böôùc 3: Sau khi thoûa maõn moät haøng hay moät naøo thì ñaùnh daáu (-) vaø caùc oâ bò loaïi cuûa haøng hay coät ñoù. OÂ loaïi laø oâ coù xij = 0.

Böôùc 3: Phöông phaùp Vogel : Traïm thu Traïm phaùt

A

150T

1 60T 6$

2 70T 10$

3 110T 4$

B

90T

2 4

(-) 8

12$ 6

8$ 4

 Tieáp tuïc laäp laïi quaù trình treân cho caùc oâ coøn laïi cho ñeán khi thoûa maõn heát caùc haøng vaø coät thì thoâi.

 Doøng hoaëc coät naøo thoûa maõn roài thì ñaùnh

chöõ k (keát thuùc) ñeå veà sau khoûi xeùt nöõa.

Loại ở bước 3

Toång soá oâ choïn = m + n -1.

11/26/2013

PGS. Dr. Nguyễn Thống

 Kieåm tra veà ñieàu kieän: 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

Böôùc 3: Phöông phaùp Vogel : Traïm thu Traïm phaùt

150T 90T

1 60T 6$ 12$

A B

150T 90T

1 60T 60 12$

(70)

2 4 2 4

3 110T 4$ 8$ 4

6 6

Giaù trò (6) coät 1 laø lôùn nhaát, keát hôïp giaù nhoû nhaát  phaân phoái oâ A-1.

Giaù trò (6) coät 1 laø lôùn nhaát, keát hôïp giaù nhoû nhaát  phaân phoái oâ A-1. Vaø sau ñoù loaïi coät soá 1 vì traïm thi 1 ñaõ thoûa maõn.

11/26/2013

PGS. Dr. Nguyễn Thống

7

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

Böôùc 3: Phöông phaùp Vogel : Traïm thu Traïm phaùt

1 60T (60)

A B

150T 90T

(70)

A B

150T 90T

(70)

3 110T 4$ 8$ 4

3 110T 90 (4$) 8$ 4

Loại

Vaø sau ñoù loaïi coät soá 1 vì traïm thi 1 ñaõ thoûa maõn.

Coät 3 coøn laïi coù coù oâ A-3 chi phí beù  ta seõ phaân phoái giaù trò vaøo ñoù (chuù yù ñeán ñieàu kieän caân baèng theo haøng tröôøng hôïp naøy).

11/26/2013

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

Baøi taäp 1: Duøng caùc phöông phaùp goùc Taây Baéc, Cmin vaø Vogel ñeå tìm lôøi giaûi ban ñaàu cho baøi toaùn sau:

Böôùc 3: Phöông phaùp Vogel : Traïm thu Traïm phaùt

X Y Z Ñeán Töø Khaû naêng

1 60T (60)

A B

150T 90T

(70)

5 4 3 A 100

3 110T (90) 20 4

=700

Keát quaû cuoái cuøng laø phaân boå vaøo B-3. 8 4 3 B 300 Lôøi giaûi chi phí cho phöông phaùp Vogel nhö sau: 9 7 5 C 300

Yeâu caàu 300 200 200

F=606+904+702+208=1020$ (toát HƠN so vôùi p/p goùc Taây Baéc vaø Cmin1060$)

11/26/2013

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 Baøi taäp 2: Duøng caùc phöông phaùp goùc Taây Baéc, Cmin vaø Vogel ñeå tìm lôøi giaûi ban ñaàu cho baøi toaùn sau:

Ñaùp soá: Phöông phaùp Vogel

Y Z X Ñeán Töø Khaû naêng

X Z Khaû naêng Y Ñeán Töø A 100 100

A 5 7 200 2 B 200 100 300

B 9 1 300 6

C

200

100

300

11/26/2013

1&2 !

C 10 3 500 13 200 Yeâu caàu 300 200

200 300 200

PGS. Dr. Nguyễn Thống

Yeâu caàu 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

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 vaø lôøi giaûi ban ñaàu

Cmin coù Z=1060$.

3

2

1 110T

70T

60T

LÔØI GIAÛI TOÁI ÖU BAØI TOAÙN VAÄN TAÛI PHÖÔNG PHAÙP THEÁ VÒ

40 (6)

150T

(10)

A

110 (4)

70 (2)

90T

B

Traïm thu Traïm phaùt (8) 20 (12) Duøng phöông phaùp theá vò ñeå tìm lôøi giaûi

toái öu.

11/26/2013

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

Baøi taäp: Cho baøi toaùn vaän taûi ñöôïc trình baøy ôû baûng sau:

F=60*6+90*4+ 20*8+70*2= 1020$ <1060$

60 75 65 Thu Phaùt 100 4 5 1 PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi Xeùt söï hoaùn vò kieán nghò neâu treân ta coù: B(1)  A(1): tieát kieäm 12-6=6 ÑV A(3)  B(3): maát 4-8 =-4ÑV Tieát kieäm: 6Ñ-4ÑV =2ÑV  Neân thöïc hieän Traïm thu Traïm phaùt 50 3 2 6 10 50 7 2 a/ Laäp phöông aùn ñaàu baèng phöông phaùp goùc Taây 1 60T 60 (6) 00 (12) 150T 90T 2 70T (10) 70 (2) 3 110T 90 (4) 20 (8) A B Baéc, phöông phaùp Cmin. b/ Döïa treân keát quaû cuûa phöông phaùp goùc Taây Baéc

haõy tìm phöông aùn toái öu.

11/26/2013

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ï: Moät Coâng ty mua 3 maùy môùi A, B, C vaø coù 4 vò trí coù theå ñaët maùy. Öôùc tính chi phí ñaët moãi maùy vaøo moãi vò trí ñöôïc cho nhö sau, trong ñoù maùy B khoâng theå ñaët ôû vò trí 2.

Tìm caùc vò trí hôïp lyù cho A, B, C sao cho chi phí nhoû

nhaát. BAØI TOAÙN PHAÂN COÂNG (The assigment problem)

11/26/2013

Vò trí Maùy A B C 1 13 15 5 2 10 - 7 3 12 13 10 4 11 20 6

PGS. Dr. Nguyễn Thống

9

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 HUNGARY 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 HUNGARY

Böôùc 1: Tìm baûng chi phí cô hoäi  Tröø chi phí nhoû nhaát trong moãi haøng

vaøo moïi phaàn töû trong haøng aáy.

Böôùc 2: Thöû ñieàu kieän toái öu Veõ moät soá toái thieåu caùc ñöôøng thaúng treân haøng hay treân coät maø ñi qua moïi soá 0 trong baûng.

 Tröø chi phí nhoû nhaát trong moãi coät vaøo moïi chi phí trong coät aáy (coù ñöôïc töø a).

Neáu soá ñöôøng thaúng baèng soá haøng hay soá coät (baèng n) thì coù lôøi giaûi toái öu nhö sau:

11/26/2013

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

a.  Phaân phoái vaøo oâ coù soá 0. Öu tieân phaân vaøo oâ coù soá 0 duy nhaát naèm treân giao ñieåm cuûa moät haøng vaø moät coät.

Böôùc 3: Taïo ra baûng chi phí cô hoäi môùi  Tröø soá nhoû nhaát chöa naèm treân ñöôøng thaúng naøo vaøo moïi soá chöa naèm treân ñöôøng thaúng naøo.

 Coäng soá nhoû nhaát aáy vaøo moïi soá naèm

b.  Loaïi boû haøng vaø coät chöùa soá 0 ñaõ phaân phoái. Quay veà böôùc a vaø tieáp tuïc cho ñeán khi phaân phoái xong.

treân giao ñieåm cuûa hai ñöôøng thaúng.

Neáu soá ñöôøng thaúng toái thieåu nhoû hôn n, chuùng

ta chuyeån qua böôùc 3.

11/26/2013

 Trôû laïi böôùc 2. PGS. Dr. Nguyễn Thống

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

Min haøng 1

2 0 M 2 0 1 3 2 0 0 3 2 0 5 0 4 1 7 1 0

Vò trí Vò trí Vò trí Maùy Maùy Maùy A A A B B B C C C D D D 1 1 1 13 13 13 15 15 15 5 5 5 0 0 0 2 2 2 10 10 10 M M M 7 7 7 0 0 0 3 3 3 12 12 12 13 13 13 10 10 10 0 0 0 4 4 4 11 11 11 20 20 20 6 6 6 0 0 0

Böôùc 1a Maùy \Vò trí A B C D Böôùc 1b (khoâng caàn trong t/h naøy) 11/26/2013

11/26/2013

Moãi haøng xaùc ñònh chi phí Min

PGS. Dr. Nguyễn Thống

10

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

Ví duï: Coù 3 ngöôøi X, Y, Z. Moãi ngöôøi coù theå laøm 1 trong 3 vieäc 1, 2, 3 vôùi chi phí cho ôû baûng sau. Haõy phaân coâng sao cho toång chi phí laø nhoû nhaát.

1 2 3

11

14

6 X

8 10 11 Y 1 3 2 0 0 2 0 M 2 0 4 1 7 1 0 3 2 0 5 0 9 12 7 Z

11/26/2013

Chi phí

PGS. Dr. Nguyễn Thống

Böôùc 2 Maùy \Vò trí A B C D Soá ñöôøng ngang = Soá ñöôøng thaúng  tìm lôøi giaûi. Maùy A vò trí 2, maùy B vò trí 3 vaø maùy C vò trí 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 Böôùc 2: Soá ñöôøng thaúng baèng 2 nhoû hôn soá haøng 1 2 3

baèng soá coät vaø baèng 3 ===> lôøi giaûi chöa toái öu

X Y Z 11 8 9 14 10 12 6 11 7

1 2 3 Böôùc 3a: Tröø soá nhoû nhaát chöa naèm treân ñöôøng thaúng naøo vaøo moïi soá chöa naèm treân ñöôøng thaúng naøo. Baûng 0 3 1 2