Bài giảng Quản trị sản xuất và tác nghiệp: Chương 5 - ThS. Vũ Lệ Hằng

Chia sẻ: Fgnfffh Fgnfffh | Ngày: | Loại File: PDF | Số trang:14

Thêm vào BST

Báo xấu

161
lượt xem 18
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương 5 Mô hình vận tải thuộc bài giảng Quản trị sản xuất và tác nghiệp trình bày về tiếp cận giải pháp ban đầu như phương pháp góc tây bắc, phương pháp xấp xỉ Vogel, phương pháp trực quan; kiểm tra sự tối ưu như phương pháp thế vị, phương pháp phân phối có điều chỉnh.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Quản trị sản xuất và tác nghiệp: Chương 5 - ThS. Vũ Lệ Hằng

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 c i thi n 2. Ti p nh n gi i pháp ban đ u 5. Các trư ng h p đ 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 d ng mô hình v n t i trong các quy t đ nh đ a đi m 3. Ki m tra s t i ư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ó đi u 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 c n thi t cho vi c s d ng mô hình v n t i Khái ni m Danh sách các ngu n cung c p hàng hoá và kh Bài toán v n t i nh m xác đ nh cách v n chuy n hàng năng cung c p t i đa c a các ngu n trong m t giai hoá có l i nh t t nhi u ngu n cung c p đ n nhi u nơi đo n. nh n khác nhau sao cho t ng chi phí v n chuy n là Danh sách các nơi ti p nh n hàng hoá và nhu c u nh nh t Chi phí v n chuy n m t đơn v s n ph m t nơi cung c p đ n nơi ti p nh n. Vũ Lệ Hằng 3 Vũ Lệ Hằng 4 1
1. Gi i thi u chung 1. Gi i thi u chung Ví d : Gi đ nh A B C D NCC Các kho n m c hàng hoá đư c v n chuy n là như nhau 4 1 (k c ngu n cung c p và nơi ti p nh n s n ph m) 7 7 1 100 Chi phí v n chuy n đơn v gi a 2 đ a đi m c th là như nhau b t k s lư ng đơn v đư c v n chuy n. 12 3 8 8 Ch có m t phương th c v n chuy n duy nh t gi a 2 đ a 2 200 đi m (ngu n cung c p và nơi ti p nh n s n ph m) 3 8 10 16 5 150 80 90 120 160 450 NC 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 v n t i 2.1. Phương pháp góc Tây - B c Bư c 1: Ti p nh n gi i pháp ban đ u 2.2. Phương pháp x p x Vogel (an initial solution) 2.3. Phương pháp tr c quan Bư c 2: Ki m tra s t i ưu Bư c 3: C i ti n đ đ t đư c m t gi i pháp t i ưu (suboptimal solution) Vũ Lệ Hằng 7 Vũ Lệ Hằng 8 2
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 - B c 2.1. Phương pháp góc Tây - B c Khái ni m Các bư c ti n hành Phương pháp góc Tây - B c luôn ưu tiên phân ph i cho ô Bư c 1: Xác đ nh ô n m phía trên bên trái (ô Tây - B c) n m góc Tây - B c c a b ng c a b ng Phương pháp này không quan tâm t i chi phí v n chuy n Bư c 2: Phân ph i t i đa v ô đó và lo i b hàng ho c c t trong quá trình phân ph i đã tho mãn Bư c 3: Xác đ nh ô n m phía trên bên trái trong các ô còn l i c a b ng Bư c 4: L p l i 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 - B c Ví d : NCC A B C D 2.1. Phương pháp góc Tây - B c Ví d : 4 7 7 1 20 1 80 20 100 T ng chi phí v n 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 3 8 10 16 5 150 150 70 150 450 NC 80 90 120 160 450 Vũ Lệ Hằng 11 Vũ Lệ Hằng 12 3
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 x p 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 Phương pháp x p x Vogel t p trung vào s thi t h i v Bư c 1: Tính toán s chênh l ch gi a 2 ô có chi phí th p nh t trên m i hàng và m i c t. chi phí x y ra khi ô có chi phí th p th hai đư c s d ng thay vì ô th có chi phí th p nh t Bư c 2: Xác đ nh hàng ho c c t có s chênh l ch l n nh t, VAM ưu tiên phân ph i cho ô có chi phí nh nh t n m n u có s b ng nhau l a ch n hàng ho c c t có ch a ô có trên hàng ho c c t có s chênh l ch gi a chi phí nh nhì chi phí th p nh t. và chi phí nh nh t là l n nh t. N u v n b ng nhau thì l a 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 x p x Vogel 2.2. Phương pháp x p x Vogel (VAM) A B C D 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 v i hàng ho c c t đã l a ch n, phân ph i t i đa v ô có chi phí th p nh t. N u v n b ng nhau, tuỳ ý 12 3 8 8 110 5 0 0 l a ch n. 2 90 110 200 Lo i b hàng ho c c t đã tho mãn Bư c 4: L p l i bư c 1 đ n bư c 3 cho các hàng và c t 3 8 10 16 5 80 10 60 150 3 3 3 còn l i cho đ n khi vi c phân ph i hoàn thành. 10 60 450 NC 80 90 120 160 450 4 4 1 4 Vũ Lệ Hằng 15 4 - 1 Vũ Lệ Hằng 4 16 4 - 8 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.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 t i đa s n ph m v ô Bư c 1: Xác đ nh ô có chi phí v n chuy n đơn v nh nh t có chi phí nh nh t Bư c 2: Phân ph i t i đa s n ph m v ô đó và lo i b hàng ho c c t (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 l i Bư c 4: L p l i 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 : B C D NCC A Ví d : 4 1 T ng chi phí v n chuy n 7 7 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 8 10 16 5 90 10 3 80 10 60 150 10 60 450 NC 80 90 120 160 450 Vũ Lệ Hằng 19 Vũ Lệ Hằng 20 5
3. Ki m tra s t i ưu 3. Ki m tra s t i ưu 3.1. Phương pháp th v 3.1. Phương pháp th v Nguyên t c th c hi n (Phương pháp chuy n ô - Stepping Stone) Chuy n 1 đơn v s n ph m t ô đ y vào ô tr ng và đánh 3.2. Phương pháp phân ph i có đi u 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 T o d ng đư ng đánh giá Ki m tra đi u ki n không suy bi n Đánh giá các ô tr ng S lư ng t i thi u các ô đ y = R + C - 1 Vũ Lệ Hằng 21 Vũ Lệ Hằng 22 3. Ki m tra s t i ưu 3. Ki m tra s t i ưu 3.1. Phương pháp th v 3.1. Phương pháp th v Bư c 1: T o d ng đư ng đánh giá Bư c 2: Đánh giá các ô tr ng Ch n 1 ô tr ng (ô chưa s d ng) đ đánh giá. Gán d u (+) Giá tr ô tr ng đư c xác đ nh b ng: vào ô tr ng c n đánh giá T ng chi phí đơn v c a các ô có ch a d u (+) Chuy n theo chi u ngang ho c chi u d c t i m t ô đ y, Tr sao cho t ô đó có th chuy n t i m t ô đ y khác. Gán d u T ng chi phí đơn v c a các ô có ch a d u (-) (-) cho ô v a ch n Bư c 3: L p l i các bư c 1 và 2 cho đ n khi đánh giá đư c Đ i hư ng và chuy n t i m t ô đ y khác, gán d u (+) cho t t c các ô tr ng. ô đã l a ch n Tu n t gán d u (-) ho c (+) cho đ n khi hoàn thi n m t con đư ng khép kín đ Vũ Lệ Hằng ô tr ng ban đ u tr v 23 Vũ Lệ Hằng 24 6
3. Ki m tra s t i ưu 3.1. Phương pháp th v 3.1. Phương pháp th v Ô tr ng 1-A Ví d : A B C D 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 (-) 8 10 16 (+) 5 0 3 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ó đi u ch nh - MODI 3.1. Phương pháp th v Ví d : Các bư c ti n hành 2-D 3-B Bư c 1: Tính toán ch s hàng và ch s c t 2-A (+) (-) (+) (-) (+) (-) a. Gán ch s hàng đ u tiên = 0 b. Xác đ nh ch s c t có ch a các ô đ y n m trên hàng đ u 12 8 8 5 10 16 tiên: 16 8 16 8 8 3 Ch s c t = Chi phí ô đ y - Ch s hàng -1 c. Xác đ nh ch s hàng ti p theo 12 11 Ch s hàng = Chi phí ô đ y - Ch s c t d. L p l i các bư c b, c cho đ n khi xác đ nh đư c t t c các ch s hàng và ch s c t Vũ Lệ Hằng 27 Vũ Lệ Hằng 28 7
3.2. Phương pháp phân ph i có đi u ch nh - MODI 3.2. Phương pháp phân ph i có đi u ch nh - MODI VD: Ti p nh n gi i pháp ban đ u b ng phương pháp tr c quan Bư c 2: Xác đ nh giá tr ô tr ng A 4 B 7 C 12 D 1 NCC Giá tr ô tr ng = Chi phí ô tr ng – (Ch s hàng + Ch s c t) 4 7 7 1 1 100 100 0 Chú ý: 12 3 8 8 -4 Ch s hàng ho c c t có th có giá tr (+), (-) ho c = 0 2 90 110 200 Phân b l i s đòi h i ph i tính l i các ch s hàng và 3 8 10 16 5 c tm i 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ó đi u ch nh 3. Ki m tra s t i ưu Xác đ nh giá tr ô tr ng Ki m tra s t i ưu: 1 – A = 4 – (0 + 4) = 0 1 – B = 7 – (0 + 7) = 0 Giá tr các ô tr ng ≥ 0 → gi i pháp t i ưu 1 – C = 7 – (0 + 12) = - 5 2 – A = 12 – (- 4 + 4) = 12 T n t i ít nh t m t ô tr ng có giá tr < 0 → gi i pháp chưa 2 – D = 8 – (- 4 + 1) = 11 t i ưu 3 – B = 10 – (4 + 7) = - 1 Vũ Lệ Hằng 31 Vũ Lệ Hằng 32 8
4. Ti p nh n gi i pháp đư c c i thi n 4. Ti p :nh n gi i pháp đư c c i thi n Ví d 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 B C D NCC đ i l n nh t 4 7 7 1 Bư c 2: 1 100 10 90 Chuy n các đơn v s n ph m t ô có d u (-) sang ô có d u (+) 12 3 8 8 S lư ng s n ph m t i đa chuy n đư c là giá tr nh 2 90 110 200 nh t trong các ô mang d u (-). 3 8 10 16 5 Bư c 3: Đánh giá các ô tr ng đ ki m tra s t i ưu 80 70 150 Chú ý ki m tra đi u 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 c i thi n 4. Ti p nh n gi i pháp đư c c i thi n Ví d : Đánh giá ô tr ng b ng MODI Ví d : Ki m ra s t i ưu: A 4 B 2 C 7 D 1 NCC 1–A=0 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 t i ưu, vì giá tr t t c các ô tr ng ≥ 0 T ng 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
5. Các trư ng h p đ c bi t 5. Các trư ng h p đ c bi t 5.1. Nhu c u và Ngu n cung c p không b ng nhau 5.1. Nhu c u và Ngu n cung c p không b ng nhau Chú ý: TH 1: T ng cung > T ng c u => thêm m t c t gi (Dummy Không có đơn v hàng hoá nào đư c v n chuy n t i ô gi column): (ô Dummy) Nhu c u ( c t gi ) = ∑ cung - ∑ c u. Chi phí v n chuy n đơn v m i ô Dummy b ng 0 Khi s d ng phương pháp tr c quan đ ti p nh n gi i TH 2: T ng c u > T ng cung => thêm m t hàng gi (Dummy pháp ban đ u, n u t ng nhu c u và ngu n cung c p row) không b ng 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 h p đ c bi t 5.1. T ng NCC và t ng NC không b ng nhau Ví d : 5.1. Nhu c u và Ngu n cung c p không b ng nhau Ví d : S d ng 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 200 NC 80 90 30 200 NC 80 90 Vũ Lệ Hằng 39 Vũ Lệ Hằng 40 10
5. Các trư ng h p đ c bi t 5. Các trư ng h p đ 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 b ng phương pháp tr c quan Bài toán không th a mãn đi u ki n s lư ng t i thi u các A B C NCC ô đ y (R + C – 1) → bài toán thu c d ng suy bi n 3 2 5 Nguyên t c: 1 40 Gán m t giá tr ε r t nh vào m t ô tr ng nào đó và xem như m t ô đ y 8 1 4 Tránh đ t ε vào ô mang d u (-) 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 NC 120 Vũ Lệ Hằng 41 40 50 Vũ Lệ Hằng 30 120 42 6. S d ng mô hình v n t i trong các quy t 6. S d ng mô hình v n t i trong các quy t đ nh l a ch n đ a đi m đ nh đ a đi m S d ng bài toán v n t i đ so sánh các gi i pháp v đ a Ví d : Hi n t i công ty có mô hình v n t i như dư i đây. Xác đi m xét trên t ng chi phí phân ph i trong toàn h th ng. đ nh đ a đi m cho t ng chi phí nh nh t Ví d : Gi s công ty d đ nh m thêm m t nhà kho m i v i nhu c u là 30 m t trong hai đ a đi m (Boston ho c A B NCC New York), bi t chi phí v n chuy n đơn v đ n hai đ a 5 9 đi m như sau: 1 100 4 2 Đ n Boston Đ n New York 2 100 T 1 $3 $4 NC 200 80 90 170 T 2 $6 $1 Vũ Lệ Hằng 43 Vũ Lệ Hằng 44 11
6. S d ng mô hình v n t i trong các quy t 6. S d ng mô hình v n t i trong các quy t đ nh đ a đi m đ nh đ a đi m 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 v n t i và bài toán c c đ i 7. Mô hình v n t i và bài toán c c đ i Bài toán mô hình v n t i có th áp d ng trong trư ng h p Nguyên t c: các s li u th hi n l i nhu n Cách 2: Xác đ nh chênh l ch c a hai ô có l i nhu n Nguyên t c: l n nh t và l i nhu n l n th nhì. Cách 1: Xác đ nh ô có l i nhu n l n nhu n l n nh t, Sau đó các bư c áp d ng tương t như đ i v i bài l y giá tr c a ô đó tr đi các ô còn l i và xem như m t toán c c ti u chi phí - S d ng VAM. chi phí cơ h i. Gi i pháp t i ưu: các ô tr ng ≤ 0 Bài toán c c đ i l i nhu n chuy n thành bài toán c c ti u chi phí. Gi i bài toán tương t như đ i v i trư ng h p c c ti u chi phí. Vũ Lệ Hằng 47 Vũ Lệ Hằng 48 12
7. Mô hình v n t i và bài toán c c đ i 7. Mô hình v n t i và bài toán c c đ i Ví d : Xác đ nh gi i pháp t i ưu trong trư ng h p s li u Ví d : Cách 2: S d ng VAM A B C D NCC th hi n l i nhu n A B C D NCC 4 7 7 1 10 1 90 10 100 0 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 80 90 120 160 450 4 3 - 3 Vũ Lệ Hằng 49 Vũ Lệ Hằng 50 - 3 - 3 7. Mô hình v n t i và bài toán c c đ i 7. Mô hình v n t i và bài toán c c đ i Ví d : Cách 1: Bài toán c c ti u chi phí Ví d : Ki m tra s t i ưu b ng phương pháp th v A B C D NCC Ki m tra đk: R+C -1= 6 (ô đ y) → th a mãn đk 12 9 9 15 10 1 – A = -1 1 90 10 100 0 3 6 1 – C = -5 2 – B = -11 4 13 8 8 120 2 – C = -11 2 80 120 200 4 4 5 3 – A = -1 8 6 0 11 30 3 – B = -1 3 120 30 150 6 2 5 → gp t i ưu 450 T ng l i 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
7. Mô hình v n t i và bài toán c c đ i 7. Mô hình v n t i và bài toán c c đ i Cách 1: Ví d : Ki m tra s t i ưu b ng phương pháp th v Ki m tra đk: R+C -1= 6 (ô đ y) → th a mãn đk A B C D NCC 1 – A = +1 1–C=+5 4 7 7 1 1 90 10 100 2 – B = +11 2 – C = +11 12 3 8 8 3 – A = +1 2 80 120 200 3 – B = +1 3 8 10 16 5 → gp t i ư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 v n t i và bài toán c c đ i Ví d : → gp t i ưu T ng l i nhu n: 90*7 + 10*1 + 80*12 + 120*8 + 120*16 + 30*5 = $4.630 Vũ Lệ Hằng 55 14