Phương pháp định lượng trong quản lý - Chương 4: Bài toán vận tải

1 11/26/2013 1 TRƯỜNG ĐẠI HỌC BÁCH KHOA TP. HCM Khoa KTXD - Bộ mơn KTTNN Giảng viên: PGS. TS. NGUYỄN THỐNG E-mail: nguyenthong@hcmut.edu.vn or nthong56@yahoo.fr Web: Tél. (08) 38 640 979 - 098 99 66 719 11/26/2013 2 NỘI DUNG MƠN HỌC CHƯƠNG 1: Giới thiệu Phương pháp định lượng trong Quản lý. CHƯƠNG 2: Quy hoạch tuyến tính. CHƯƠNG 3: Cơ sở lý thuyết ra quyết định. CHƯƠNG 4: Bài toán vận tải. CHƯƠNG 5: Quản lý kho. CHƯƠNG 6: Ra quyết định đa mục tiêu. CHƯƠNG 7: Lý thuyết sắp hàng. PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ 11/26/2013 3 NỘI DUNG MƠN HỌC (tt) Chương 8: Phân tích thành phần chính (PCA). Chương 9: Kiểm định Cronbach’s Alpha & KMO 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. PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ 11/26/2013 4 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 PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ 11/26/2013 5 GIỚI THIỆU • Bài toán vận tải (1939) là dạng đặc biệt của Bài toán Qui Hoạch Tuyến Tính  do đó có thể giải bài toán theo các phương pháp đã trình bày trong Qui Hoạch Tuyến Tính. Tuy nhiên cấu trúc bài toán có những tính chất đặc biệt nên có phương pháp giải riêng hữu hiệu hơn. PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải PGS. Dr. Nguyễn Thống 11/26/2013 6 • Bài toán này đầu tiên được trình bày trong công tác vận chuyển hàng hóa. Vì vậy có tên là bài toán vận tải.  Nhưng mô hình của bài toán vận tải, sau khi được công bố, đã được rất nhiều ngành kinh tế khác nhau ứng dụng như lãnh vực quân sự, quản lý, y tế,... PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải PGS. Dr. Nguyễn Thống 2 11/26/2013 7 MÔ HÌNH TỔNG QUÁT • Có n trạm phát hàng. Mỗi trạm ký hiệu là A i ( i= 1,n ). Khả năng cung cấp hàng hóa của trạm phát thứ i là a i . • Có m trạm thu hàng. Mỗi trạm ký hiệu là B j ( j = 1,m ). Nhu cầu hàng hóa của trạm thu thứ j là b j . PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 8 MÔ HÌNH TỔNG QUÁT • Chi phí vận chuyển một đơn vị hàng hóa từ A i đến B j là C ij . HÀM MỤC TIÊU CỦA BÀI TOÁN  Xác định phương án vận chuyển sao cho tổng chi phí vận chuyển là nhỏ nhất. PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 9 SỐ LIỆU DẠNG BẢNG PGS. Dr. Nguyễn Thống Bj Ai b1 b2 . bm a 1 x 11 (c 11 ) x 12 (c 12 ) . x 1m a 2 x 21 x 22 . x 2m . . . . . a n x n1 x n2 . x nm Chi phí đơn vị Biến quyết định (lượng hàng hóa) PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Phát hàng Nhận hàng 11/26/2013 10 • Biến quyết định: Gọi x ij là số lượng đơn vị hàng hóa vận chuyển từ trạm phát thứ i đến trạm thu thứ j. • Hàm mục tiêu: • Ràng buộc: PGS. Dr. Nguyễn Thống MinZ C x x a x b ij ij ij i j m ij j i n         1 1 i=1,n j=1,m (Công suất trạm phát) (Công suất trạm thu) x ij >=0 PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 11 • Ghi chú: Nếu giữa một trạm A i nào đó đến một trạm B j nào đó không có đường vận chuyển  nghĩa là giữa 2 trạm đó không thể tổ chức vận chuyển được  khi đó ta lấy đơn gía vận chuyển C ij = M với M là một số dương lớn tùy ý.  Trong trường hợp đó lời giải cho x ij sẽ là 0. PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 12 Trường hợp: Cung = Cầu Ví du 1: Bài toán vận chuyển chất đốt Ở các trạm phát A và B có 150 tấn và 90 tấn chất đốt. Phải cung cấp cho các vị trí 1, 2, 3 tương ứng 60, 70 và 110 tấn chất đốt đó. Chi phí chở 1 tấn chất đốt từ A đến các vị trí 1, 2, 3 tương ứng là 6, 10 và 4$ còn từ B đến 1, 2, 3 là 12, 2 và 8$. Hãy lập kế hoạch vận chuyển tối ưu sao cho tổng chi phí vận chuyển là bé nhất. PGS. Dr. Nguyễn Thống a bi i n j j m     1 1 PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 3 11/26/2013 13 PGS. Dr. Nguyễn Thống a b i i n j j m              1 2 1 3 150 90 240 60 70 110 240  Cung = Cầu Trạm thu Trạm phát 1 2 3 60T 70T 110T A 150T x 11 =?(6$) x 12 =?(10$) x 13 =?(4$) B 90T x 21 =?(12$) x 22 =?(2$) x 23 =?(8$) PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 14 Trong trường hợp không có sự cân bằng giữa Cung và Cầu, ta có thể luôn luôn trở về bài toán cân bằng Cung và Cầu bằng cách thêm vào nguồn Cung giả hoặc Cầu giả và gán các chi phí vận chuyển LỚN tương ứng tuyến vận chuyển.  Lời giải vẫn tìm được sau khi loại các nguồn giả từ kết quả tìm ra cuối cùng. PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 15 PHƯƠNG PHÁP GIẢI BÀI TOÁN VẬN TẢI Vì bài toán vận tải cũng là một bài toán QHTT nên hoàn toàn có thể giải bằng phương pháp đơn hình. Nhưng do tính chất đặc thù của bài toán vận tải nên ta có những phương pháp GIẢI đơn giản hơn. Có 3 phương pháp  LỜI GIẢI GẦN ĐÚNG: • Phương pháp góc Tây Bắc  P/án đầu (The North West Corner Method). PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 16 PHƯƠNG PHÁP GIẢI BÀI TOÁN VẬN TẢI • Phương pháp chi phí bé nhất C min (The Least Cost Method). • Phương pháp xấp xỉ của Vogel (Vogel’s Approximation Method - VAM).  PHƯƠNG PHÁP TỔNG QUÁT (tìm lời giải chính xác)  PHƯƠNG PHÁP THẾ VỊ PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 17 PHƯƠNG PHÁP GÓC TÂY BẮC (Dantzig) PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 18 • Xuất phát từ ô nằm ở góc Tây Bắc, tức ô (1,1) ta tiến dần xuống ô ở góc Đông Nam, tức ô (n,m).  Trên đường đi gặp ô nào ta phân phối cho ô đó một lượng hàng lớn nhất có thể được dựa trên nguyên tắc đảm bảo điều kiện cân bằng giữa số cung và số cầu.  Khi phân phối hết thì dừng lại.  PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 4 11/26/2013 19 Sau đó kiểm tra xem tổng ô chọn có bằng (m + n - 1) hay không. Ô chọn là ô có x ij > 0. Nếu điều kiện nầy thỏa mãn thì phương án nhận được gọi là phương án đầu. Nhận xét: Lời giải của phương án đầu trong phương pháp góc Tây Bắc ít khi tối ưu bởi vì khi giải KHÔNG quan tâm đến chi phí vận chuyển. PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 20 PGS. Dr. Nguyễn Thống Lấy lại số liệu ở trên: Trạm thu Trạm phát 1 2 3 60T 70T 110T A 150T x 11 =?(6$) x 12 =?(10$) x 13 =?(4$) B 90T x 21 =?(12$) x 22 =?(2$) x 23 =?(8$) PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Tìm lời giải sơ bộ bằng phương pháp góc Tây Bắc. 11/26/2013 21 Lấy ví dụ 1 nói trên: Ví dụ phương pháp giải Tây Bắc: Z = 60*6 + 70*10 + 20*4 + 90*8 = 1860 $ PGS. Dr. Nguyễn Thống Trạm thu Trạm phát 1 2 3 60T 70T 110T A 150T 60 70 20 B 90T 90 PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 22 Bài tập: Lấy lại ví dụ 1 nói trên, dùng phương pháp góc Tây Bắc để tìm lời giải sơ bộ với các trường hợp sau: 1. Khả năng cung cấp của trạm A bây giờ là 100T. 2. Khả năng trạm thu 3 là 80T. (Chú ý: Trong trường hợp Cung < Cầu  Bổ sung trạm Cung GIẢ) PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 23 Ví dụ: Bài toán quản lý sản xuất (p/p góc Tây Bắc) Một Công ty có 3 nhà máy 1, 2, 3. Mỗi nhà máy có thể sản xuất 5 loại sản phẩm 1, 2, 3, 4, 5 với khả năng xuất và tiêu thụ tổng 5 loại như sau. Nhà máy 1 2 3 Khả năng sản xuất 5 loại 40 đơn vị 60 90 PGS. Dr. Nguyễn Thống Sản phẩm 1 2 3 4 5 Khả năng bán 30 40 70 40 60 PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 24 Chi phí sản xuất Biết rằng nhà máy 3 không thể sản xuất sản phẩm 5. Giả thiết mỗi đơn vị sản phẩm đều có lợi nhuận bằng nhau. Vậy mỗi nhà máy nên sản xuất bao nhiêu đơn vị cho mỗi loại sản phẩm ? PGS. Dr. Nguyễn Thống Sản phẩm Nhà máy 1 2 3 4 5 1 20 19 14 21 16 2 15 20 13 19 16 3 18 15 18 20 ? PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 5 11/26/2013 25 Vì không có sự cân bằng giữa sản xuất và nhu cầu  thêm một nhà máy giả số 4 có khả năng sản xuất 240 - 190 = 50 đơn vị sản phẩm với chi phí sản xuất bằng 0. PGS. Dr. Nguyễn Thống Sản phẩm Nhà máy 1 2 3 4 5 30 40 70 40 60 1 40 30 10 2 60 30 30 3 90 40 40 10 4 50 50 PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 26 PHƯƠNG PHÁP CHI PHÍ BÉ NHẤT CMIN PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 27 Khi dùng phương pháp góc Tây Bắc ta không để ý đến chi phí vận chuyển C ij . Do đó kết quả có được ở phương án đầu còn cách xa phương án tối ưu.  Phương pháp C min khắc phục được một phần nhược điểm này. PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 28 • Trong phương pháp C min , trước tiên ta tìm ô có trị số C ij nhỏ nhất. Phân phối lượng hàng lớn nhất có thể có được vào ô đó. • Sau đó ta phân phối hàng hóa cho ô có trị số C ij nhỏ nhất trong các ô còn lại. • Cứ tiếp tục như thế cho đến hết. PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 29 • Trong quá trình phân phối cần đảm bảo điều kiện cân bằng giữa số cung và số cầu. • Kiểm tra điều kiện : Tổng số ô chọn = m + n - 1 PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 30 Phương pháp C min . Lấy ví dụ 1 nói trên: Ví dụ phương pháp giải Cmin Z = 40*6 + 110*4 + 70*2 + 20*12 = 1060 $ (1860$) chỉ trình tự phân bố khối lượng vận chuyển PGS. Dr. Nguyễn Thống Trạm thu Trạm phát 1 2 3 60T 70T 110T A 150T 40(6)3 110(4)2 B 90T 20(12)4 70 (2)1 Trình tự chọn PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 6 11/26/2013 31 PGS. Dr. Nguyễn Thống Bài tập: Tìm lời giải bằng phương pháp C min : Trạm thu Trạm phát 1 2 3 60T 70T 110T A 90T x 11 =?(6$) x 12 =?(10$) x 13 =?(4$) B 150T x 21 =?(12$) x 22 =?(2$) x 23 =?(8$) PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Trạm thu Trạm phát 1 2 3 60T 70T 110T A 80T x 11 =?(6$) x 12 =?(10$) x 13 =?(4$) B 120T x 21 =?(12$) x 22 =?(2$) x 23 =?(8$) 11/26/2013 32 PGS. Dr. Nguyễn Thống Bài tập: Tìm lời giải bằng phương pháp C min : Trạm thu Trạm phát 1 2 3 60T 70T 110T A 90T x 11 =?(6$) x 12 =?(10$) x 13 =?(4$) B 150T x 21 =?(12$) x 22 =?(2$) x 23 =?(4$) PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải (Xét trường hợp có một số phương án có chi phí như nhau) 11/26/2013 33 PHƯƠNG PHÁP XẤP XỈ VOGEL PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 34 PHƯƠNG PHÁP XẤP XỈ CỦA VOGEL • Trong phương pháp C min ta đã xem xét đến chi phí vận chuyển C ij nhưng chưa chú ý đến hiệu số của chúng (sự chênh lệch về chi phí vận chuyển).  Vì vậy có thể xảy ra trường hợp bước trước thì tốt nhưng bước sau lại xấu (bước trước rơi vào ô có chi phí thấp nhưng bước sau rơi vào ô có chi phí rất cao). PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 35 PHƯƠNG PHÁP XẤP XỈ CỦA VOGEL • Phương pháp Vogel khắc phục được nhược điểm nầy  Cho kết quả tốt hơn, gần bằng hoặc bằng kết quả lời giải tối ưu. PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 36 CÁC BƯỚC CỦA PHƯƠNG PHÁP VOGEL: • Bước 1: Trên mỗi hàng và mỗi cột chọn chi phí C ij bé nhất và C ij bé thứ hai. Lấy hiệu số của chúng rồi ghi vào ô bên phải và bên dưới bảng. Tìm số lớn nhất trong các hiệu số đó. PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Trạm thu Trạm phát 1 2 3 60T 70T 110T A 150T 6$ 10$ 4$ B 90T 12$ 2$ 8$ 2(6-4) 6(8-2) 4 8 6 (12-6) 7 11/26/2013 37 Bước 2: Phân phối trước lượng hàng cho hàng (hoặc cột) có trị số hiệu số lớn nhất (cột trạm thu số 2). • Lúc phân phối, thì phân phối lượng hàng lớn nhất có thể được vào ô có C ij nhỏ nhất của hàng và cột ứng với hiệu số lớn nhất nói trên (hàng trạm phát B). • Trong quá trình phân phối cần đảm bảo sự cân bằng giữa số cung và số cầu. PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 38 PGS. Dr. Nguyễn Thống Bước 2: Phương pháp Vogel : Chọn cột số [2] phân phối vì giá trị (8) là lớn nhất và lựa chọn ô trên cột này có chi phí bé nhất  ô B-2 Trạm thu Trạm phát 1 2 3 60T 70T 110T A 150T 6$ 10$ 4$ B 90T 12$ (70)2$ 8$ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 2 6 6 8 4 11/26/2013 39 • Bước 3: Sau khi thỏa mãn một hàng hay một nào thì đánh dấu (-) và các ô bị loại của hàng hay cột đó. Ô loại là ô có x ij = 0.  Tiếp tục lập lại quá trình trên cho các ô còn lại cho đến khi thỏa mãn hết các hàng và cột thì thôi.  Dòng hoặc cột nào thỏa mãn rồi thì đánh chữ k (kết thúc) để về sau khỏi xét nữa.  Kiểm tra về điều kiện: Tổng số ô chọn = m + n -1. PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 40 PGS. Dr. Nguyễn Thống Bước 3: Phương pháp Vogel : Trạm thu Trạm phát 1 2 3 60T 70T 110T A 150T 6$ 10$ 4$ B 90T 12$ (-) 8$ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 2 4 6 8 4 Loại ở bước 3 11/26/2013 41 PGS. Dr. Nguyễn Thống Bước 3: Phương pháp Vogel : Giá trị (6) cột 1 là lớn nhất, kết hợp giá nhỏ nhất  phân phối ô A-1. Trạm thu Trạm phát 1 3 60T 110T A 150T 6$ 4$ B 90T 12$ 8$ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 2 4 6 4 11/26/2013 42 PGS. Dr. Nguyễn Thống Bước 3: Phương pháp Vogel : Giá trị (6) cột 1 là lớn nhất, kết hợp giá nhỏ nhất  phân phối ô A-1. Và sau đó loại cột số 1 vì trạm thi 1 đã thỏa mãn. Trạm thu Trạm phát 1 3 60T 110T A 150T 60 4$ B 90T 12$ (70) 8$ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 2 4 6 4 8 11/26/2013 43 PGS. Dr. Nguyễn Thống Bước 3: Phương pháp Vogel : Và sau đó loại cột số 1 vì trạm thi 1 đã thỏa mãn. Trạm thu Trạm phát 1 3 60T 110T A 150T (60) 4$ B 90T (70) 8$ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 4 Loại 11/26/2013 44 PGS. Dr. Nguyễn Thống Bước 3: Phương pháp Vogel : Cột 3 còn lại có có ô A-3 chi phí bé  ta sẽ phân phối giá trị vào đó (chú ý đến điều kiện cân bằng theo hàng trường hợp này). Trạm thu Trạm phát 1 3 60T 110T A 150T (60) 90 (4$) B 90T (70) 8$ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 4 11/26/2013 45 PGS. Dr. Nguyễn Thống Bước 3: Phương pháp Vogel : Kết quả cuối cùng là phân bổ vào B-3. Lời giải chi phí cho phương pháp Vogel như sau: F=60*6+90*4+70*2+20*8=1020$ (tốt HƠN so với p/p góc Tây Bắc và C min 1060$) Trạm thu Trạm phát 1 3 60T 110T A 150T (60) (90) B 90T (70) 20 PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 4 11/26/2013 46 Bài tập 1: Dùng các phương pháp góc Tây Bắc, C min và Vogel để tìm lời giải ban đầu cho bài toán sau: PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Đến Từ X Y Z Khả năng A 5 4 3 100 B 8 4 3 300 C 9 7 5 300 Yêu cầu 300 200 200 =700 11/26/2013 47 Đáp số: Phương pháp Vogel PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Đến Từ X Y Z Khả năng A 100 100 B 200 100 300 C 200 100 300 Yêu cầu 300 200 200 11/26/2013 48 Bài tập 2: Dùng các phương pháp góc Tây Bắc, C min và Vogel để tìm lời giải ban đầu cho bài toán sau: PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Đến Từ X Y Z Khả năng A 5 2 7 200 B 9 6 1 300 C 10 13 3 500 Yêu cầu 300 200 200 1&2 ! 9 11/26/2013 49 LỜI GIẢI TỐI ƯU BÀI TOÁN VẬN TẢI PHƯƠNG PHÁP THẾ VỊ PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 50 Lấy ví dụ 1 nói trên và lời giải ban đầu C min có Z=1060$. Dùng phương pháp thế vị để tìm lời giải tối ưu. PGS. Dr. Nguyễn Thống Trạm thu Trạm phát 1 2 3 60T 70T 110T A 150T 40 (6) (10) 110 (4) B 90T 20 (12) 70 (2) (8) PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 51 Xét sự hoán vị kiến nghị nêu trên ta có: B(1)  A(1): tiết kiệm 12-6=6 ĐV A(3)  B(3): mất 4-8 =-4ĐV Tiết kiệm: 6Đ-4ĐV =2ĐV  Nên thực hiện F=60*6+90*4+ 20*8+70*2= 1020$ <1060$ PGS. Dr. Nguyễn Thống Trạm thu Trạm phát 1 2 3 60T 70T 110T A 150T 60 (6) (10) 90 (4) B 90T 00 (12) 70 (2) 20 (8) PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 52 Bài tập: Cho bài toán vận tải được trình bày ở bảng sau: a/ Lập phương án đầu bằng phương pháp góc Tây Bắc, phương pháp C min . b/ Dựa trên kết quả của phương pháp góc Tây Bắc hãy tìm phương án tối ưu. PGS. Dr. Nguyễn Thống Thu Phát 75 60 65 100 5 4 1 50 2 6 3 50 10 7 2 PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 53 BÀI TOÁN PHÂN CÔNG (The assigment problem) PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 54 Ví dụ: Một Công ty mua 3 máy mới A, B, C và có 4 vị trí có thể đặt máy. Ước tính chi phí đặt mỗi máy vào mỗi vị trí được cho như sau, trong đó máy B không thể đặt ở vị trí 2. Tìm các vị trí hợp lý cho A, B, C sao cho chi phí nhỏ nhất. PGS. Dr. Nguyễn Thống Vị trí Máy 1 2 3 4 A 13 10 12 11 B 15 - 13 20 C 5 7 10 6 PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 10 11/26/2013 55 PHƯƠNG PHÁP HUNGARY Bước 1: Tìm bảng chi phí cơ hội  Trừ chi phí nhỏ nhất trong mỗi hàng vào mọi phần tử trong hàng ấy.  Trừ chi phí nhỏ nhất trong mỗi cột vào mọi chi phí trong cột ấy (có được từ a). PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 56 PHƯƠNG PHÁP HUNGARY Bước 2: Thử điều kiện tối ưu Vẽ một số tối thiểu các đường thẳng trên hàng hay trên cột mà đi qua mọi số 0 trong bảng. Nếu số đường thẳng bằng số hàng hay số cột (bằng n) thì có lời giải tối ưu như sau: PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 57 a.  Phân phối vào ô có số 0. Ưu tiên phân vào ô có số 0 duy nhất nằm trên giao điểm của một hàng và một cột. b.  Loại bỏ hàng và cột chứa số 0 đã phân phối. Quay về bước a và tiếp tục cho đến khi phân phối xong. Nếu số đường thẳng tối thiểu nhỏ hơn n, chúng ta chuyển qua bước 3. PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 58 Bước 3: Tạo ra bảng chi phí cơ hội mới  Trừ số nhỏ nhất chưa nằm trên đường thẳng nào vào mọi số chưa nằm trên đường thẳng nào.  Cộng số nhỏ nhất ấy vào mọi số nằm trên giao điểm của hai đường thẳng.  Trở lại bước 2. PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 59 PGS. Dr. Nguyễn Thống Vị trí Máy 1 2 3 4 A 13 10 12 11 B 15 M 13 20 C 5 7 10 6 D 0 0 0 0 Min hàng 1 Mỗi hàng xác định chi phí Min PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 60 Bước 1a Bước 1b (không cần trong t/h này) PGS. Dr. Nguyễn Thống Máy \Vị trí 1 2 3 4 A 3 0 2 1 B 2 M 0 7 C 0 2 5 1 D 0 0 0 0 PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11 11/26/2013 61 Bước 2 Số đường ngang = Số đường thẳng  tìm lời giải. Máy A vị trí 2, máy B vị trí 3 và máy C vị trí 1. PGS. Dr. Nguyễn Thống Máy \Vị trí 1 2 3 4 A 3 0 2 1 B 2 M 0 7 C 0 2 5 1 D 0 0 0 0 PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 62 Ví dụ: Có 3 người X, Y, Z. Mỗi người có thể làm 1 trong 3 việc 1, 2, 3 với chi phí cho ở bảng sau. Hãy phân công sao cho tổng chi phí là nhỏ nhất. PGS. Dr. Nguyễn Thống 1 2 3 X 11 14 6 Y 8 10 11 Z 9 12 7 Chi phí PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 63 PGS. Dr. Nguyễn Thống 1 2 3 X 11 14 6 Y 8 10 11 Z 9 12 7 1 2 3 X 5 8 0 Y 0 2 3 Z 2 5 0 PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 64 Bước 2: Số đường thẳng bằng 2 nhỏ hơn số hàng bằng số cột và bằng 3 ===> lời giải chưa tối ưu Bước 3a: Trừ số nhỏ nhất chưa nằm trên đường thẳng nào vào mọi số chưa nằm trên đường thẳng nào. PGS. Dr. Nguyễn Thống Bảng 0 1 2 3 X 5(3) 8(6) 0 Y 0 2 (0) 3 Z 2(0) 5(3) 0 PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 65 Bước 3b: Cộng số nhỏ nhất ấy vào mọi số nằm trên giao điểm của hai đường thẳng. Số đường ngang = Sồ đường đứng  Có lời giải tối ưu (X=3, Y=2, Z=1). PGS. Dr. Nguyễn Thống Bảng 0 1 2 3 X 3 6 0 Y 0 0 5 Z 0 3 0 PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 11/26/2013 66 Bài tập: Dùng Solver trong Excel để giải các bài tập nêu trên. PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải 12 11/26/2013 67 HẾT CHƯƠNG PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải PGS. Dr. Nguyễn Thống