1. Trang Chủ
  2. Kiến trúc - Xây dựng
  3. Bài giảng Phương pháp định lượng trong quản lý: Chương 4 - PGS. Nguyễn Thống

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

Nội dung chương 4: Bài toán vận tải thuộc bài giảng Phương pháp định lượng trong quản lý trình bày nội dung về hàm mục tiêu bài toán, phương pháp giải bài toán vận tải, phương pháp góc tây bắc, phương pháp chi phí bé nhất, phương pháp xấp xỉ vogel, phương pháp thế vị, bài toán phân công. TRƯỜNG ĐẠI HỌC BÁCH KHOA TP. HCM PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Khoa KTXD - Bộ môn KTTNN 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í

Thể loại Tài liệu miễn phí Kiến trúc - Xây dựng

Số trang 12

Ngày tạo 8/30/2018 4:40:29 AM +00:00

Loại tệp PDF

Kích thước 0.44 M

Tên tệp

Tải Bài giảng Phương pháp định lượng trong quản lý: Ch... (.pdf)

Xem mẫu

  1. TRƯỜNG ĐẠI HỌC BÁCH KHOA TP. HCM PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Khoa KTXD - Bộ môn KTTNN 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. Giảng viên: PGS. TS. NGUYỄN THỐNG CHƯƠNG 5: Quaûn lyù kho. E-mail: nguyenthong@hcmut.edu.vn or nthong56@yahoo.fr CHƯƠNG 6: Ra quyeát ñònh ña muïc tieâu. Web: http://www4.hcmut.edu.vn/~nguyenthong 11/26/2013 1 CHƯƠNG 7: Lyù thuyeát saép haøng. 11/26/2013 2 Tél. (08) 38 640 979 - 098 99 66 719 PHÖÔNG PHAÙP ÑÒNH PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ LÖÔÏNG TRONG QUAÛN LYÙ NỘI DUNG MÔN HỌC (tt) TÀI LIỆU THAM KHẢO Chương 8: Phân tích thành phần chính (PCA). 1. Phương pháp định lượng trong quản lý. Chương 9: Kiểm định Cronbach’s Alpha & NXB Trẻ 1999. Tác giả PGS. Dr. Nguyễn KMO Thống & Dr. Cao Hào Thi. Chương 10: Phương pháp AHP Chương 11: Qui hoạch động 2. Phân tích số liệu và áp dụng vào dự báo. Chương 12: Hoạch định dự án NXB Thanh Niên 2000. Tác giả PGS. Dr. Chương 13: Xích Markov Nguyễn Thống Chương 14: Lý thuyết trò chơi. 3. Phần mềm QSB, Crystal Ball Chương 15: Mô phỏng Monte Carlo. 11/26/2013 3 11/26/2013 4 PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi 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 • Baøi toaùn vaän taûi (1939) laø daïng ñaëc bieät cuûa trong coâng taùc vaän chuyeån haøng hoùa. Baøi toaùn Qui Hoaïch Tuyeán Tính  do ñoù coù Vì vaäy coù teân laø baøi toaùn vaän taûi. 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.  Nhöng moâ hình cuûa baøi toaùn vaän taûi, Tuy nhieân caáu truùc baøi toaùn coù nhöõng tính chaát sau khi ñöôïc coâng boá, ñaõ ñöôïc raát ñaëc bieät neân coù phöông phaùp giaûi rieâng höõu nhieàu ngaønh kinh teá khaùc nhau öùng hieäu hôn. duïng nhö laõnh vöïc quaân söï, quaûn lyù, y teá,... 11/26/2013 5 11/26/2013 6 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 1
  2. PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi 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ù • Chi phí vaän chuyeån moät ñôn vò haøng hoùa hieäu laø Ai ( i= 1,n ). Khaû naêng cung caáp töø Ai ñeán Bj laø Cij. haøng hoùa cuûa traïm phaùt thöù i laø ai. HÀM MỤC TIÊU CỦA BÀI TOÁN • Coù m traïm thu haøng. Moãi traïm kyù hieäu  Xaùc ñònh phöông aùn vaän chuyeån sao laø Bj ( j = 1,m ). Nhu caàu haøng hoùa cuûa cho toång chi phí vaän chuyeån laø nhoû nhaát. traïm thu thöù j laø bj. 11/26/2013 7 11/26/2013 8 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi Chöông 4: Baøi toaùn vaän taûi SOÁ LIEÄU DAÏNG BAÛNG • Bieán quyeát ñònh: Goïi xij laø soá löôïng ñôn vò Nhận hàng Bj haøng hoùa vaän chuyeån töø traïm phaùt thöù i ñeán Ai b1 b2 . bm traïm thu thöù j. MinZ   Cij x ij a1 x11(c11) x12(c12) . x1m • Haøm muïc tieâu: a2 x21 x22 . x2m (Coâng suaát traïm phaùt) m Chi phí ñôn vò x ij  ai i=1,n . . . . . • Raøng buoäc: j 1 an xn1 xn2 . xnm (Coâng suaát traïm thu) xij >=0 n Phát hàng Bieán quyeát ñònh 11/26/2013 PGS. Dr. Nguyễn Thống (lượng hàng hóa) 9 11/26/2013 PGS. Dr. Nguyễn Thống x i 1 ij  b j j=1,m10 PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi Chöông 4: Baøi toaùn vaän taûi n m Tröôøng hôïp: Cung = Caàu • 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 a i 1 i  b j 1 j vaän chuyeån  nghóa laø giöõa 2 traïm ñoù Ví du 1: Baøi toaùn vaän chuyeån chaát ñoát khoâng theå toå chöùc vaän chuyeån ñöôïc ÔÛ 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  khi ñoù ta laáy ñôn gía vaän chuyeån Cij = töông öùng 60, 70 vaø 110 taán chaát ñoát ñoù. Chi M vôùi M laø moät soá döông lôùn tuøy yù. phí chôû 1 taán chaát ñoát töø A ñeán caùc vò trí 1, 2,  Trong tröôøng hôïp ñoù lôøi giaûi cho xij seõ 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 laø 0. toái öu sao cho toång chi phí vaän chuyeån laø beù 11/26/2013 11 nhaát. 11/26/2013 12 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 2
  3. PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi Chöông 4: Baøi toaùn vaän taûi n 2 Trong tröôøng hôïp khoâng coù söï caân baèng giöõa a i  150  90  240 Cung vaø Caàu, ta coù theå luoân luoân trôû veà baøi i 1  Cung = Caàu toaùn caân baèng Cung vaø Caàu baèng caùch theâm m 3 vaøo nguoàn Cung giaû hoaëc Caàu giaû vaø gaùn caùc b j 1 j  60  70  110  240 chi phí vaän chuyeån LÔÙN töông öùng tuyeán vaän chuyeån. Traïm thu Traïm phaùt 1 2 3  Lôøi giaûi vaãn tìm ñöôïc sau khi loaïi caùc nguoàn 60T 70T 110T giaû töø keát quaû tìm ra cuoái cuøng. A 150T x11=?(6$) x12=?(10$) x13=?(4$) B 11/26/2013 90T x21=?(12$) x22=?(2$) x23=?(8$) 13 11/26/2013 14 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi 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 PHƯƠNG PHÁP GIẢI BÀI TOÁN VẬN Vì baøi toaùn vaän taûi cuõng laø moät baøi toaùn QHTT TẢI 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 • Phöông phaùp chi phí beù nhaát Cmin (The toaùn vaän taûi neân ta coù nhöõng phöông phaùp Least Cost Method). GIAÛI ñôn giaûn hôn. • Phöông phaùp xaáp xæ cuûa Vogel (Vogel’s Coù 3 phöông phaùp  LÔØI GIAÛI GAÀN ÑUÙNG: Approximation Method - VAM). • Phöông phaùp goùc Taây Baéc  P/aùn ñaàu (The  PHÖÔNG PHAÙP TOÅNG QUAÙT (tìm lôøi North West Corner Method). giaûi chính xaùc)  PHÖÔNG PHAÙP THEÁ 11/26/2013 15 VÒ 11/26/2013 16 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi 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, PHƯƠNG PHÁP GÓC TÂY BẮC töùc oâ (n,m).  Treân ñöôøng ñi gaëp oâ naøo ta phaân phoái cho (Dantzig) 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 17 11/26/2013 18 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 3
  4. PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi 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 Laáy laïi soá lieäu ôû treân: (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 60T 70T 110T aùn nhaän ñöôïc goïi laø phöông aùn ñaàu. A 150T x11=?(6$) x12=?(10$) x13=?(4$) Nhaän xeùt: Lôøi giaûi cuûa phöông aùn ñaàu B 90T x21=?(12$) x22=?(2$) x23=?(8$) trong phöông phaùp goùc Taây Baéc ít khi Tìm lôøi giaûi sô boä baèng phöông phaùp toái öu bôûi vì khi giaûi KHOÂNG quan taâm goùc Taây Baéc. ñeán chi phí vaän chuyeån. 11/26/2013 19 11/26/2013 20 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi 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 Traïm thu phöông phaùp goùc Taây Baéc ñeå tìm lôøi Traïm phaùt 1 2 3 giaûi sô boä vôùi caùc tröôøng hôïp sau: 60T 70T 110T 1. Khaû naêng cung caáp cuûa traïm A baây giôø A 150T 60 70 20 laø 100T. B 90T 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Û) Ví duï phöông phaùp giaûi Taây Baéc: Z = 60*6 + 70*10 + 20*4 + 90*8 = 1860 $ 11/26/2013 21 11/26/2013 22 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi 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) Chi phí saûn xuaát 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û Saûn phaåm naêng xuaát vaø tieâu thuï toång 5 loaïi nhö sau. Nhaø maùy 1 2 3 4 5 1 20 19 14 21 16 Nhaø maùy 1 2 3 Khaû naêng saûn 40 ñôn vò 60 90 2 15 20 13 19 16 xuaát 5 loaïi 3 18 15 18 20 ? Saûn phaåm 1 2 3 4 5 Bieát raèng nhaø maùy 3 khoâng theå saûn xuaát saûn phaåm 5. Khaû naêng 30 40 70 40 60 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 baùn 11/26/2013 23 nhieâu ñôn vò cho moãi loaïi saûn phaåm ? 11/26/2013 24 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 4
  5. PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi 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 PHƯƠNG PHÁP CHI PHÍ Nhaø maùy 1 2 3 4 5 BÉ NHẤT CMIN 30 40 70 40 60 1 40 30 10 2 60 30 30 3 90 40 40 10 4 PGS. Dr. Nguyễn Thống50 11/26/2013 50 25 11/26/2013 PGS. Dr. Nguyễn Thống 26 PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi Chöông 4: Baøi toaùn vaän taûi Khi duøng phöông phaùp goùc Taây Baéc • Trong phöông phaùp Cmin, tröôùc tieân ta ta khoâng ñeå yù ñeán chi phí vaän tìm oâ coù trò soá Cij nhoû nhaát. Phaân phoái chuyeån Cij. Do ñoù keát quaû coù ñöôïc ôû löôïng haøng lôùn nhaát coù theå coù ñöôïc vaøo oâ ñoù. 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 27 11/26/2013 28 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi Chöông 4: Baøi toaùn vaän taûi • Trong quaù trình phaân phoái caàn ñaûm Phöông phaùp Cmin. Laáy ví duï 1 noùi treân: baûo ñieàu kieän caân baèng giöõa soá cung Traïm thu Traïm phaùt 1 2 3 vaø soá caàu. 60T 70T 110T • Kieåm tra ñieàu kieän : Toång soá oâ choïn A 150T 40(6)3 110(4)2 =m+n-1 B 90T 20(12)4 70 (2)1 Trình Ví duï phöông phaùp giaûi Cmin töï choïn 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 11/26/2013 29 11/26/2013 30 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 5
  6. PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi 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 : Baøi taäp: Tìm lôøi giaûi baèng phöông phaùp Cmin : Traïm thu Traïm thu Traïm phaùt 1 2 3 Traïm phaùt 1 2 3 60T 70T 110T 60T 70T 110T A 90T x11=?(6$) x12=?(10$) x13=?(4$) A 90T x11=?(6$) x12=?(10$) x13=?(4$) B 150T x21=?(12$) x22=?(2$) x23=?(8$) B 150T x21=?(12$) x22=?(2$) x23=?(4$) Traïm thu Traïm phaùt 1 2 3 (Xét trường hợp có một số phương án có chi phí như nhau) 60T 70T 110T A 80T x11=?(6$) x12=?(10$) x13=?(4$) PGS. Dr.B 120T x21=?(12$) x22=?(2$) x23=?(8$) 11/26/2013 31 11/26/2013 32 Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi 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 PHƯƠNG PHÁP 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í XẤP XỈ VOGEL vaän chuyeån).  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 33 11/26/2013 34 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi Chöông 4: Baøi toaùn vaän taûi CAÙC BÖÔÙC CUÛA PHÖÔNG PHAÙP VOGEL: PHÖÔNG PHAÙP XAÁP XÆ CUÛA • Böôùc 1: Treân moãi haøng vaø moãi coät choïn chi phí Cij VOGEL 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 • Phöông phaùp Vogel khaéc phuïc ñöôïc nhaát trong caùc hieäu soá ñoù. nhöôïc ñieåm naày Traïm thu  Cho keát quaû toát hôn, gaàn baèng Traïm phaùt 1 2 3 hoaëc baèng keát quaû lôøi giaûi toái öu. 60T 70T 110T A 150T 6$ 10$ 4$ 2(6-4) B 90T 12$ 2$ 8$ 6(8-2) 11/26/2013 35 11/26/2013 6 (12-6) 8 4 36 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 6
  7. PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi 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 Böôùc 2: Phöông phaùp Vogel : Traïm thu haøng (hoaëc coät) coù trò soá hieäu soá lôùn nhaát Traïm phaùt 1 2 3 (coät traïm thu soá 2). 60T 70T 110T • Luùc phaân phoái, thì phaân phoái löôïng haøng A 150T 6$ 10$ 4$ 2 lôùn nhaát coù theå ñöôïc vaøo oâ coù Cij nhoû B 90T 12$ (70)2$ 8$ 6 6 8 4 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). Choïn coät soá [2] phaân phoái vì giaù trò (8) laø lôùn • Trong quaù trình phaân phoái caàn ñaûm baûo nhaát vaø löïa choïn oâ treân coät naøy coù chi phí beù söï caân baèng giöõa soá cung vaø soá caàu. nhaát  oâ B-2 11/26/2013 37 11/26/2013 38 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi 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 Böôùc 3: Phöông phaùp Vogel : Traïm thu naøo thì ñaùnh daáu (-) vaø caùc oâ bò loaïi cuûa haøng Traïm phaùt 1 2 3 hay coät ñoù. OÂ loaïi laø oâ coù xij = 0. 60T 70T 110T  Tieáp tuïc laäp laïi quaù trình treân cho caùc oâ coøn A 150T 6$ 10$ 4$ 2 laïi cho ñeán khi thoûa maõn heát caùc haøng vaø coät B 90T 12$ (-) 8$ 4 thì thoâi. 6 8 4  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  Kieåm tra veà ñieàu kieän: Toång soá oâ choïn = m + n -1. 11/26/2013 39 11/26/2013 40 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi Chöông 4: Baøi toaùn vaän taûi Böôùc 3: Phöông phaùp Vogel : Böôùc 3: Phöông phaùp Vogel : Traïm thu Traïm thu Traïm phaùt 1 3 Traïm phaùt 1 3 60T 110T 60T 110T A 150T 6$ 4$ 2 A 150T 60 4$ 2 B 90T 12$ 8$ 4 B 90T 12$ (70) 8$ 4 4 4 6 6 Giaù trò (6) coät 1 laø lôùn nhaát, keát hôïp giaù nhoû 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. 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 41 11/26/2013 42 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 7
  8. PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi Chöông 4: Baøi toaùn vaän taûi Böôùc 3: Phöông phaùp Vogel : Böôùc 3: Phöông phaùp Vogel : Traïm thu Traïm thu Traïm phaùt 1 3 Traïm phaùt 1 3 60T 110T 60T 110T A 150T (60) 4$ A 150T (60) 90 (4$) B 90T (70) 8$ B 90T (70) 8$ 4 4 Loại Vaø sau ñoù loaïi coät soá 1 vì traïm thi 1 ñaõ thoûa Coät 3 coøn laïi coù coù oâ A-3 chi phí beù  ta seõ maõn. 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 43 11/26/2013 44 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi Chöông 4: Baøi toaùn vaän taûi Böôùc 3: Phöông phaùp Vogel : Baøi taäp 1: Duøng caùc phöông phaùp goùc Taây Baéc, Cmin Traïm thu vaø Vogel ñeå tìm lôøi giaûi ban ñaàu cho baøi toaùn sau: Traïm phaùt 1 3 60T 110T Ñeán Khaû A 150T (60) (90) Töø X Y Z naêng B 90T (70) 20 A 5 4 3 100 Keát quaû cuoái cuøng laø phaân boå vaøo B-3. 4 B 8 4 3 300 Lôøi giaûi chi phí cho phöông phaùp Vogel nhö sau: C 9 7 5 300 F=60*6+90*4+70*2+20*8=1020$ (toát HƠN so vôùi p/p goùc Taây Baéc vaø Cmin1060$) Yeâu caàu 300 200 200 =700 11/26/2013 45 11/26/2013 46 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi Chöông 4: Baøi toaùn vaän taûi Ñaùp soá: Phöông phaùp Vogel 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 Ñeán Khaû toaùn sau: Töø X Y Z naêng Ñeán A 100 100 Töø X Y Z Khaû naêng B 200 100 300 A 5 2 7 200 C 200 100 300 B 9 6 1 300 Yeâu caàu 300 200 200 C 10 13 3 500 11/26/2013 PGS. Dr. Nguyễn Thống 47 PGS.u caàu Yeâ Dr. Nguyễn Thống 11/26/2013 300 200 200 1&2 ! 48 8
  9. PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi 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$. LÔØI GIAÛI TOÁI ÖU BAØI TOAÙN VAÄN TAÛI Traïm thu Traïm phaùt 1 2 3 PHÖÔNG PHAÙP THEÁ VÒ 60T 70T 110T A 150T 40 (6) (10) 110 (4) B 90T 20 (12) 70 (2) (8) Duøng phöông phaùp theá vò ñeå tìm lôøi giaûi toái öu. 11/26/2013 49 11/26/2013 50 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi 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ù: Baøi taäp: Cho baøi toaùn vaän taûi ñöôïc trình baøy ôû baûng B(1)  A(1): tieát kieäm 12-6=6 ÑV sau: A(3)  B(3): maát 4-8 =-4ÑV Thu Phaùt 75 60 65 Tieát kieäm: 6Ñ-4ÑV =2ÑV  Neân thöïc hieän Traïm thu 100 5 4 1 Traïm phaùt 1 2 3 50 2 6 3 60T 70T 110T 50 10 7 2 A 150T 60 (6) (10) 90 (4) a/ Laäp phöông aùn ñaàu baèng phöông phaùp goùc Taây B 90T 00 (12) 70 (2) 20 (8) Baéc, phöông phaùp Cmin. F=60*6+90*4+ 20*8+70*2= 1020$
  10. PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi Chöông 4: Baøi toaùn vaän taûi PHÖÔNG PHAÙP HUNGARY PHÖÔNG PHAÙP HUNGARY Böôùc 1: Tìm baûng chi phí cô hoäi Böôùc 2: Thöû ñieàu kieän toái öu  Tröø chi phí nhoû nhaát trong moãi haøng Veõ moät soá toái thieåu caùc ñöôøng thaúng treân vaøo moïi phaàn töû trong haøng aáy. haøng hay treân coät maø ñi qua moïi soá 0  Tröø chi phí nhoû nhaát trong moãi coät trong baûng. vaøo moïi chi phí trong coät aáy (coù ñöôïc töø Neáu soá ñöôøng thaúng baèng soá haøng hay soá a). coät (baèng n) thì coù lôøi giaûi toái öu nhö sau: 11/26/2013 55 11/26/2013 56 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi 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 Böôùc 3: Taïo ra baûng chi phí cô hoäi môùi oâ coù soá 0 duy nhaát naèm treân giao ñieåm cuûa  Tröø soá nhoû nhaát chöa naèm treân moät haøng vaø moät coät. ñöôøng thaúng naøo vaøo moïi soá chöa naèm b.  Loaïi boû haøng vaø coät chöùa soá 0 ñaõ phaân treân ñöôøng thaúng naøo. phoái. Quay veà böôùc a vaø tieáp tuïc cho ñeán khi phaân phoái xong.  Coäng soá nhoû nhaát aáy vaøo moïi soá naèm Neáu soá ñöôøng thaúng toái thieåu nhoû hôn n, chuùng treân giao ñieåm cuûa hai ñöôøng thaúng. ta chuyeån qua böôùc 3.  Trôû laïi böôùc 2. 11/26/2013 57 11/26/2013 58 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi Chöông 4: Baøi toaùn vaän taûi Böôùc 1a Min haøng 1 Maùy \Vò trí 1 2 3 4 Vò trí Maùy 1 2 3 4 A 3 0 2 1 A 13 12 11 B 2 M 0 7 10 C 0 2 5 1 B 15 M 13 20 D 0 0 0 0 C 5 7 10 6 Böôùc 1b (khoâng caàn trong t/h naøy) D 0 0 0 0 11/26/2013 Moãi haøng xaùc ñònh chi phí Min 59 11/26/2013 60 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 10
  11. PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi Chöông 4: Baøi toaùn vaän taûi Böôùc 2 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 Maùy \Vò trí phaân coâng sao cho toång chi phí laø nhoû nhaát. 1 2 3 4 A 3 0 2 1 1 2 3 B 2 M 0 7 X 11 14 6 C 0 2 5 1 D 0 0 0 0 Y 8 10 11 Soá ñöôøng ngang = Soá ñöôøng thaúng  tìm lôøi giaûi. Z 9 12 7 Maùy A vò trí 2, maùy B vò trí 3 vaø maùy C vò trí 1. 11/26/2013 61 11/26/2013 Chi phí 62 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi 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 X 11 14 6 ===> lôøi giaûi chöa toái öu Y 8 10 11 Böôùc 3a: Tröø soá nhoû nhaát chöa naèm treân ñöôøng Z 9 12 7 thaúng naøo vaøo moïi soá chöa naèm treân ñöôøng thaúng naøo. 1 2 3 Baûng 0 1 2 3 X 5 8 0 X 5(3) 8(6) 0 Y 0 2 3 Y 0 2 (0) 3 Z 2 5 0 Z 2(0) 5(3) 0 11/26/2013 63 11/26/2013 64 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi Chöông 4: Baøi toaùn vaän taûi Böôùc 3b: Coäng soá nhoû nhaát aáy vaøo moïi soá naèm treân Baøi taäp: Duøng Solver trong Excel ñeå giao ñieåm cuûa hai ñöôøng thaúng. giaûi caùc baøi taäp neâu treân. Baûng 0 1 2 3 X 3 6 0 Y 0 0 5 Z 0 3 0 Soá ñöôøng ngang = Soà ñöôøng ñöùng  Coù lôøi giaûi toái öu (X=3, Y=2, Z=1). 11/26/2013 65 11/26/2013 66 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 11
  12. PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ Chöông 4: Baøi toaùn vaän taûi HẾT CHƯƠNG 11/26/2013 67 PGS. Dr. Nguyễn Thống 12
nguon tai.lieu . vn
Kiến trúc - Xây dựng Tự động hoá Điện - Điện tử Kĩ thuật Viễn thông Cơ khí - Chế tạo máy Năng lượng Hoá dầu Hoá học Sinh học