›
›

Giáo trình sản xuất và tác nghiệp - Chương 5: Mô hình vận tải

pdf 14 trang huongle 5240
Download
Bạn đang xem tài liệu "Giáo trình sản xuất và tác nghiệp - Chương 5: Mô hình vận tải", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfgiao_trinh_san_xuat_va_tac_nghiep_chuong_5_mo_hinh_van_tai.pdf

Nội dung text: Giáo trình sản xuất và tác nghiệp - Chương 5: Mô hình vận tải

  1. CH ƯƠ NG 5. MÔ HÌNH V N T I CH ƯƠ NG 5. MÔ HÌNH V N T I 1. Gi i thi u chung 4. Ti p nh n gi i pháp ci thi n 2. Ti p nh n gi i pháp ban đu 5. Các tr ưng hp đc bi t 2.1. Ph ươ ng pháp góc tây b c 5.1. Nhu c u và ngu n cung c p không b ng nhau 2.2. Ph ươ ng pháp x p x Vogel 5.2. Mô hình suy bi n (VAM: Vogel Approximation Method) 2.3. Ph ươ ng pháp tr c quan 6. S dng mô hình vn ti trong các quy t đnh đa đim 3. Ki m tra s ti ưu 7. Mô hình v n t i và bài toán c c đi 3.1. Ph ươ ng pháp th v 3.2. Ph ươ ng pháp phân ph i có điu ch nh Vũ Lệ Hằng 1 Vũ Lệ Hằng 2 1. Gi i thi u chung 1. Gi i thi u chung  Các thông tin cn thi t cho vi c s dng mô hình vn ti  Khái ni m   Danh sách các ngu n cung cp hàng hoá và kh  Bài toán vn ti nh m xác đnh cách vn chuy n hàng năng cung cp ti đa ca các ngu n trong mt giai hoá có li nh t t nhi u ngu n cung cp đn nhi u nơi đon. nh n khác nhau sao cho tng chi phí vn chuy n là   Danh sách các nơi ti p nh n hàng hoá và nhu cu nh nh t   Chi phí vn chuy n mt đơ n v sn ph m t nơi cung cp đn nơi ti p nh n. Vũ Lệ Hằng 3 Vũ Lệ Hằng 4 1
  2. 1. Gi i thi u chung 1. Gi i thi u chung  Ví d:  Gi đnh A BCD NCC  Các kho n mc hàng hoá đưc vn chuy n là nh ư nhau 4 7 7 1 (k c ngu n cung cp và nơi ti p nh n sn ph m) 1 100  Chi phí vn chuy n đơ n v gi a 2 đa đim c th là nh ư nhau bt k s lưng đơ n v đưc vn chuy n. 12 3 8 8  Ch có mt ph ươ ng th c vn chuy n duy nh t gi a 2 đa 2 200 đim (ngu n cung cp và nơi ti p nh n sn ph m) 3 8 10 16 5 150 450 NC 80 90 120 160 Vũ Lệ Hằng 450 5 Vũ Lệ Hằng 6 1. Gi i thi u chung 2. Ti p nh n gi i pháp ban đu  Trình t gi i bài toán mô hình vn ti 2.1. Ph ươ ng pháp góc Tây - Bc  Bưc 1: Ti p nh n gi i pháp ban đu 2.2. Ph ươ ng pháp xp x Vogel (an initial solution) 2.3. Ph ươ ng pháp tr c quan  Bưc 2: Ki m tra s ti ưu  Bưc 3: Ci ti n đ đt đưc mt gi i pháp ti ưu (suboptimal solution) Vũ Lệ Hằng 7 Vũ Lệ Hằng 8 2
  3. 2. Ti p nh n gi i pháp ban đu 2. Ti p nh n gi i pháp ban đu 2.1. Ph ươ ng pháp góc Tây - Bc 2.1. Ph ươ ng pháp góc Tây - Bc  Khái ni m  Các bưc ti n hành  Ph ươ ng pháp góc Tây - Bc luôn ưu tiên phân ph i cho ô  Bưc 1: Xác đnh ô nm phía trên bên trái (ô Tây - Bc) nm góc Tây - Bc ca bng ca bng  Ph ươ ng pháp này không quan tâm ti chi phí vn chuy n  Bưc 2: Phân ph i ti đa v ô đó và lo i b hàng ho c ct trong quá trình phân ph i đã tho mãn  Bưc 3: Xác đnh ô nm phía trên bên trái trong các ô còn li ca bng  Bưc 4: Lp li bưc 2 và 3 cho đn khi vi c phân ph i hoàn thành Vũ Lệ Hằng 9 Vũ Lệ Hằng 10 2. Ti p nh n gi i pháp ban đu 2. Ti p nh n gi i pháp ban đu 2.1. Ph ươ ng pháp góc Tây - Bc  Ví d: A BCD NCC 2.1. Ph ươ ng pháp góc Tây - Bc  Ví d: 4 7 7 1 20 1 80 20 100  Tng chi phí vn chuy n = 80*4 + 20*7 + 70*3 + 120*8 + 10*8 + 150*5 12 3 8 8 130 10 = 2.460$ 2 70 120 10 200 8 10 16 5 3 150 150 70 150 450 NC 80 90 120 160 450 Vũ Lệ Hằng 11 Vũ Lệ Hằng 12 3
  4. 2. Ti p nh n gi i pháp ban đu 2. Ti p nh n gi i pháp ban đu ươ 2.2. Ph ươ ng pháp xp x Vogel 2.2. Ph ng pháp x p x Vogel (VAM - Vogel Approximation Method) (VAM - Vogel Approximation Method)  Các bưc ti n hành:  Khái ni m Bưc 1: Tính toán s chênh lch gi a 2 ô có chi phí th p  Ph ươ ng pháp xp x Vogel tp trung vào s thi t hi v  nh t trên m i hàng và m i c t. chi phí xy ra khi ô có chi phí th p th hai đưc s dng thay vì ô th có chi phí th p nh t  Bưc 2: Xác đnh hàng ho c ct có s chênh lch ln nh t,  VAM ưu tiên phân ph i cho ô có chi phí nh nh t nm nu có s bng nhau la ch n hàng ho c ct có ch a ô có chi phí th p nh t. trên hàng ho c ct có s chênh lch gi a chi phí nh nhì và chi phí nh nh t là ln nh t. Nu vn bng nhau thì la ch n tu ỳ ý Vũ Lệ Hằng 13 Vũ Lệ Hằng 14 2. Ti p nh n gi i pháp ban đu 2. Ti p nh n gi i pháp ban đu 2.2. Ph ươ ng pháp xp x Vogel 2.2. Ph ươ ng pháp xp x Vogel (VAM) A BCD NCC (Vogel Approximation Method)  Các bưc ti n hành: 4 7 7 1 1 100 100 3 3 -  Bưc 3: Đi vi hàng ho c ct đã la ch n, phân ph i ti đa v ô có chi phí th p nh t. Nu vn bng nhau, tu ỳ ý 110 12 3 8 8 5 0 0 la ch n. 2 90 110 200 Lo i b hàng ho c ct đã tho mãn ư 8 10 16 5  B c 4: Lp li bưc 1 đn bưc 3 cho các hàng và ct 3 80 10 60 150 3 3 3 còn li cho đn khi vi c phân ph i hoàn thành. 10 60 450 NC 80 90 120 160 450 44 1 4 Vũ Lệ Hằng 15 4 -Vũ Lệ 1 Hằng 4 16 4 - 8 3 - 4
  5. 2. Ti p nh n gi i pháp ban đu 2. Ti p nh n gi i pháp ban đu 2.3. Ph ươ ng pháp tr c quan 2.3. Ph ươ ng pháp tr c quan  Khái ni m  Các bưc ti n hành  Là ph ươ ng pháp tu n t phân ph i ti đa sn ph m v ô  Bưc 1: Xác đnh ô có chi phí vn chuy n đơ n v nh nh t có chi phí nh nh t  Bưc 2: Phân ph i ti đa sn ph m v ô đó và lo i b hàng ho c ct (ho c c hai) đã tho mãn.  Bưc 3: Tìm ô có chi phí th p nh t ti p theo trong các ô còn li  Bưc 4: Lp li bưc 2 và 3 cho đn khi vi c phân ph i hoàn thành Vũ Lệ Hằng 17 Vũ Lệ Hằng 18 2. Ti p nh n gi i pháp ban đu 2. Ti p nh n gi i pháp ban đu 2.3. Ph ươ ng pháp tr c quan 2.3. Ph ươ ng pháp tr c quan  Ví d: A BCD NCC  Ví d: 4 7 7 1  Tng chi phí vn chuy n 1 100 100 = 100*1 + 90*3 + 110*8 + 80*8 + 10*16 + 60*5 = 2.350$ 12 3 8 8 110 2 90 110 200 90 10 3 8 10 16 5 80 10 60 150 10 60 450 NC 80 90 120 160 450 Vũ Lệ Hằng 19 Vũ Lệ Hằng 20 5
  6. 3. Ki m tra s ti ưu 3. Ki m tra s ti ưu 3.1. Ph ươ ng pháp th v 3.1. Ph ươ ng pháp th v  Nguyên tc th c hi n (Ph ươ ng pháp chuy n ô - Stepping Stone)  Chuy n 1 đơ n v sn ph m t ô đy vào ô tr ng và đánh 3.2. Ph ươ ng pháp phân ph i có điu ch nh giá xem chi phí tăng lên hay gi m đi (MODI - Modified distribution method)  Trình t th c hi n  To dng đưng đánh giá  Ki m tra điu ki n không suy bi n  Đánh giá các ô tr ng  S lưng ti thi u các ô đy = R + C - 1 Vũ Lệ Hằng 21 Vũ Lệ Hằng 22 3. Ki m tra s ti ưu 3. Ki m tra s ti ưu 3.1. Ph ươ ng pháp th v 3.1. Ph ươ ng pháp th v Bưc 1: To dng đưng đánh giá   Bưc 2: Đánh giá các ô tr ng  Ch n 1 ô tr ng (ô ch ưa s dng) đ đánh giá. Gán du (+)  Giá tr ô tr ng đưc xác đnh bng: vào ô tr ng cn đánh giá  Tng chi phí đơ n v ca các ô có ch a du (+)  Chuy n theo chi u ngang ho c chi u dc ti mt ô đy, Tr sao cho t ô đó có th chuy n ti mt ô đy khác. Gán du  Tng chi phí đơ n v ca các ô có ch a du (-) (-) cho ô va ch n  Bưc 3: Lp li các bưc 1 và 2 cho đn khi đánh giá đưc  Đi hưng và chuy n ti mt ô đy khác, gán du (+) cho tt c các ô tr ng. ô đã la ch n  Tu n t gán du (-) ho c (+) cho đn khi hoàn thi n mt con đưng khép kín đ tr v ô tr ng ban đu Vũ Lệ Hằng 23 Vũ Lệ Hằng 24 6
  7. 3. Ki m tra s ti ưu 3.1. Ph ươ ng pháp th v 3.1. Ph ươ ng pháp th v Ví d:  Ô tr ng 1-A  A BCD NCC (+) 4 7 7 (-) 1 1 - A 1 - B 1 - C 1 100 100 (+) (-) (+) (-) (+) (-) 4 1 7 1 7 1 12 3 8 8 2 90 110 200 5 8 5 16 5 16 8 3 (-) (+) 3 8 10 16 5 0 0 - 5 80 10 60 150 450 NC 80 90 120 160 450 Vũ Lệ Hằng 25 Vũ Lệ Hằng 26 3.2. Ph ươ ng pháp phân ph i có điu ch nh - MODI 3.1. Ph ươ ng pháp th v  Ví d:  Các bưc ti n hành  Bưc 1: Tính toán ch s hàng và ch s ct 2 - A 2 - D 3 - B (+) (-) (+) (-) (+) (-) a. Gán ch s hàng đu tiên = 0 b. Xác đnh ch s ct có ch a các ô đy nm trên hàng đu 12 8 8 5 10 16 tiên: 16 8 16 8 8 3 Ch s ct = Chi phí ô đy - Ch s hàng c. Xác đnh ch s hàng ti p theo 12 11 - 1 Ch s hàng = Chi phí ô đy - Ch s ct d. Lp li các bưc b, c cho đn khi xác đnh đưc tt c các ch s hàng và ch s ct Vũ Lệ Hằng 27 Vũ Lệ Hằng 28 7
  8. 3.2. Ph ươ ng pháp phân ph i có điu ch nh - MODI 3.2. Ph ươ ng pháp phân ph i có điu ch nh - MODI  VD: Ti p nh n gi i pháp ban đu bng ph ươ ng pháp tr c quan  Bưc 2: Xác đnh giá tr ô tr ng A 4BCD 7 12 1 NCC Giá tr ô tr ng = Chi phí ô tr ng – (Ch s hàng + Ch s ct) 4 7 7 1 1 100 100 0  Chú ý: 12 3 8 8 - 4  Ch s hàng ho c ct có th có giá tr (+), (-) ho c = 0 2 90 110 200  Phân b li s đòi hi ph i tính li các ch s hàng và 8 10 16 5 ct mi 3 80 10 60 150 4 450 NC 80 90 120 160 450 Vũ Lệ Hằng 29 Vũ Lệ Hằng 30 3.2. Ph ươ ng pháp phân ph i có điu ch nh 3. Ki m tra s ti ưu  Xác đnh giá tr ô tr ng  Ki m tra s ti ưu: 1 – A = 4 – (0 + 4) = 0 1 – B = 7 – (0 + 7) = 0  Giá tr các ô tr ng ≥ 0 → gi i pháp ti ưu 1 – C = 7 – (0 + 12) = - 5 2 – A = 12 – (- 4 + 4) = 12  Tn ti ít nh t mt ô tr ng có giá tr < 0 → gi i pháp ch ưa 2 – D = 8 – (- 4 + 1) = 11 ti ưu 3 – B = 10 – (4 + 7) = - 1 Vũ Lệ Hằng 31 Vũ Lệ Hằng 32 8
  9. 4. Ti p nh n gi i pháp đưc ci thi n 4. TiVíp d: nh n gi i pháp đưc ci thi n  Các bưc ti n hành  Bưc 1: Trong các ô cho giá tr âm, ch n ô có giá tr tuy t A BCD NCC đi ln nh t 4 7 7 1  Bưc 2: 1 10 90 100  Chuy n các đơ n v sn ph m t ô có du (-) sang ô có du (+) 12 3 8 8 2  S lưng sn ph m ti đa chuy n đưc là giá tr nh 90 110 200 nh t trong các ô mang du (-). 8 10 16 5  Bưc 3: Đánh giá các ô tr ng đ ki m tra s ti ưu 3 80 70 150  Chú ý ki m tra điu ki n R + C - 1 tr ưc khi đánh giá ô tr ng 450 NC 80 90 120 160 450 Vũ Lệ Hằng 33 Vũ Lệ Hằng 34 4. Ti p nh n gi i pháp đưc ci thi n 4. Ti p nh n gi i pháp đưc ci thi n  Ví d: Đánh giá ô tr ng bng MODI  Ví d: Ki m ra s ti ưu:  1 – A = 0 A 4 BC2 7 D 1 NCC  1 – B = 5 4 7 7 1 1 10 90 100 0  2 – A = 7  2 – D = 6 12 3 8 8 2 90 110 200 1  3 – B = 4  3 – C = 5 3 8 10 16 5 80 70 150 4 ⇒Gi i pháp ti ưu, vì giá tr tt c các ô tr ng ≥ 0  Tng chi phí: 10*7 + 90*1 + 90*3 + 110*8 + 80*8 + 70*5 450 NC 80 90 120 160 450 = 2.300 Vũ Lệ Hằng 35 Vũ Lệ Hằng 36 9
  10. 5. Các tr ưng hp đc bi t 5. Các tr ưng hp đc bi t 5.1. Nhu cu và Ngu n cung cp không bng nhau 5.1. Nhu cu và Ngu n cung cp không bng nhau  Chú ý:  TH 1: Tng cung > Tng cu => thêm mt ct gi (Dummy  Không có đơ n v hàng hoá nào đưc vn chuy n ti ô gi column): (ô Dummy)  Nhu cu ( ct gi ) = ∑ cung - ∑ cu.  Chi phí vn chuy n đơ n v mi ô Dummy bng 0  Khi s dng ph ươ ng pháp tr c quan đ ti p nh n gi i  TH 2: Tng cu > Tng cung => thêm mt hàng gi (Dummy pháp ban đu, nu tng nhu cu và ngu n cung cp row) không bng nhau thì ph i phân ph i v các ô Dummy cu i cùng. Vũ Lệ Hằng 37 Vũ Lệ Hằng 38 5. Các tr ưng hp đc bi t 5.1. Tng NCC và tng NC không bng nhau  Ví d: 5.1. Nhu cu và Ngu n cung cp không bng nhau  Ví d: S dng ph ươ ng pháp tr c quan đ ti p nh n gi i A B Dummy NCC pháp ban đu A B NCC 5 9 0 1 100 5 9 1 100 4 2 0 2 100 4 2 2 100 NC 200 80 90 30 200 NC 80 90 Vũ Lệ Hằng 39 Vũ Lệ Hằng 40 10
  11. 5. Các tr ưng hp đc bi t 5. Các tr ưng hp đc bi t 5.2. Mô hình suy bi n 5.2. Mô hình suy bi n (Degeneracy) VD: Ti p nh n gi i pháp ban đu bng ph ươ ng pháp tr c quan  Bài toán không th a mãn điu ki n s lưng ti thi u các A BC NCC ô đy (R + C – 1) → bài toán thu c dng suy bi n 3 2 5  Nguyên tc: 1 40  Gán mt giá tr ε rt nh vào mt ô tr ng nào đó và xem nh ư mt ô đy 8 1 4  Tránh đt ε vào ô mang du (-) trong đưng đánh giá; 2 60 giá tr ε có th đưc b gi i pháp cu i cùng. 3 7 7 6 20 120 NC 40 50 30 Vũ Lệ Hằng 41 Vũ Lệ Hằng 120 42 6. S dng mô hình vn ti trong các quy t 6. S dng mô hình vn ti trong các quy t đnh la ch n đa đim đnh đa đim  S dng bài toán vn ti đ so sánh các gi i pháp v đa  Ví d: Hi n ti công ty có mô hình vn ti nh ư dưi đây. Xác đim xét trên tng chi phí phân ph i trong toàn h th ng. đnh đa đim cho tng chi phí nh nh t  Ví d: Gi s công ty d đnh m thêm mt nhà kho mi vi nhu cu là 30 mt trong hai đa đim (Boston ho c A B NCC New York), bi t chi phí vn chuy n đơ n v đn hai đa 5 9 đim nh ư sau: 1 100 4 2 Đn Boston Đn New York 2 100 T 1 $3 $4 200 NC 80 90 T 2 $6 $1 170 Vũ Lệ Hằng 43 Vũ Lệ Hằng 44 11
  12. 6. S dng mô hình vn ti trong các quy t 6. S dng mô hình vn ti trong các quy t đnh đa đim đnh đa đim  Ví d:  Ví d: A B Boston NCC A B New York NCC 5 9 3 5 9 4 1 100 1 100 4 2 6 4 2 1 2 100 2 100 NC 200 200 80 90 30 200 NC 80 90 30 200 Vũ Lệ Hằng 45 Vũ Lệ Hằng 46 7. Mô hình vn ti và bài toán cc đi 7. Mô hình vn ti và bài toán cc đi  Bài toán mô hình vn ti có th áp dng trong tr ưng hp  Nguyên tc: các s li u th hi n li nhu n  Cách 2: Xác đnh chênh lch ca hai ô có li nhu n  Nguyên tc: ln nh t và li nhu n ln th nhì.  Cách 1: Xác đnh ô có li nhu n ln nhu n ln nh t,  Sau đó các bưc áp dng tươ ng t nh ư đi vi bài ly giá tr ca ô đó tr đi các ô còn li và xem nh ư mt toán cc ti u chi phí - S dng VAM. chi phí cơ hi.  Gi i pháp ti ưu: các ô tr ng ≤ 0  Bài toán cc đi li nhu n chuy n thành bài toán cc ti u chi phí. Gi i bài toán tươ ng t nh ư đi vi tr ưng hp cc ti u chi phí. Vũ Lệ Hằng 47 Vũ Lệ Hằng 48 12
  13. 7. Mô hình vn ti và bài toán cc đi 7. Mô hình vn ti và bài toán cc đi  Ví d: Cách 2: S dng VAM  Ví d: Xác đnh gi i pháp ti ưu trong tr ưng hp s li u A BCD NCC th hi n li nhu n BCD NCC 4 7 7 1 10 A 0 1 90 10 100 3 6 4 7 7 1 1 90 10 100 12 3 8 8 120 2 80 120 200 4 4 5 12 3 8 8 2 80 120 200 8 10 16 5 30 3 120 30 150 6 2 5 3 8 10 16 5 120 30 150 450 NC 80 90 120 160 450 450 4 3 8 3 NC 90 120 160 80 450 4 3- 3 Vũ Lệ Hằng 49 Vũ Lệ Hằng 50 - 3 - 3 7. Mô hình vn ti và bài toán cc đi 7. Mô hình vn ti và bài toán cc đi  Ví d: Cách 1: Bài toán cc ti u chi phí  Ví d: Ki m tra s ti ưu bng ph ươ ng pháp th v A BCD NCC  Ki m tra đk: R+C -1= 6 (ô đy) → th a mãn đk 12 9 9 15 10 0  1 – A = -1 1 90 10 100 3 6  1 – C = -5 120  2 – B = -11 4 13 8 8 2 80 4 4 5  2 – C = -11 120 200  3 – A = -1 8 6 0 11 30  3 – B = -1 3 120 30 150 6 2 5 → gp ti ưu 450 Tng li nhu n: NC 80 90 120 160 450 90*7 + 10*1 + 80*12 + 120*8 + 120*16 + 30*5 = $4.630 4 3 8 3 4 3- 3 Vũ Lệ Hằng 51 Vũ Lệ Hằng 52 - 3 - 3 13
  14. 7. Mô hình vn ti và bài toán cc đi 7. Mô hình vn ti và bài toán cc đi  Cách 1:  Ví d: Ki m tra s ti ưu bng ph ươ ng pháp th v  Ki m tra đk: R+C -1= 6 (ô đy) → th a mãn đk A BCD NCC  1 – A = +1  1 – C = + 5 4 7 7 1 1  2 – B = +11 90 10 100  2 – C = +11 12 3 8 8  3 – A = +1 2 80 120 200  3 – B = +1 3 8 10 16 5 → gp ti ưu 120 30 150 450 NC 80 90 120 160 450 Vũ Lệ Hằng 53 Vũ Lệ Hằng 54 7. Mô hình vn ti và bài toán cc đi Ví d: → gp ti ưu Tng li nhu n: 90*7 + 10*1 + 80*12 + 120*8 + 120*16 + 30*5 = $4.630 Vũ Lệ Hằng 55 14