intTypePromotion=1

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

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

0
70
lượt xem
10
download

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

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

Bài giảng Quản lý sản xuất và tác nghiệp 1 - Chương 5 giới thiệu về các mô hình vận tải. Những nội dung chính trong chương này gồm có: Tiếp nhận giải pháp ban đầu, kiểm tra sự tối ưu, tiếp nhận giải pháp cải thiện, các trường hợp đặc biệt, sử dụng mô hình vận tải trong các quyết định địa điểm, mô hình vận tải và bài toán cực đại.

Chủ đề:
Lưu

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

  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 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
  2. 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
  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 - 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
  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 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
  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 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
  6. 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ũtrở về ô trống ban đầu Lệ Hằng 23 Vũ Lệ Hằng 24 6
  7. 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
  8. 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ột mớ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
  9. 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
  10. 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
  11. 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
  12. 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
  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  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
  14. 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
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2