Bài giảng Mô hình hóa hệ thống sản xuất - TS. Đặng Vũ Tùng (ĐH Bách khoa Hà Nội)

Chia sẻ: Gió Biển | Ngày: | Loại File: PDF | Số trang:44

Thêm vào BST

Báo xấu

171
lượt xem 11
download

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

Bài giảng "Mô hình hóa hệ thống sản xuất" do TS. Đặng Vũ Tùng biên soạn cung cấp cho người đọc các kiến thức: Giới thiệu, mô hình tuyến tính, mô hình vận tải, mô hình mạng, mô hình biến nguyên. Mời các bạn cùng tham khảo nội dung chi tiết.

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 Mô hình hóa hệ thống sản xuất - TS. Đặng Vũ Tùng (ĐH Bách khoa Hà Nội)

Trường Đại học Bách khoa Hà Nội Viện Kinh tế và Quản lý MỤC ĐÍCH MÔN HỌC Giúp cho sinh viên: MÔ HÌNH HÓA l Hiểu biết về các phương pháp và kỹ năng lập mô hình cho các hệ thống sản xuất HỆ THỐNG SẢN XUẤT l Làm chủ một số công cụ giải mô hình l Khả năng nhận dạng, xây dựng, giải quyết & diễn giải kết quả cho các bài toán thực tế TS. Đặng Vũ Tùng liên quan đến tối ưu hóa hoạt động của hệ thống sản xuất Hànội - 2014 Mô hình hóa – TS Đặng Vũ Tùng – ĐH Bách Khoa Hà Nội NỘI DUNG MÔN HỌC PHƯƠNG PHÁP l Chương 1. Giới thiệu l Giờ lý thuyết + thực hành phòng máy l Chương 2. Mô hình tuyến tính l Phát bài giảng; yêu cầu đọc trước ở nhà l Chương 3. Mô hình vận tải l Trên lớp cần lắng nghe + phát biểu l Chương 4. Mô hình mạng l Đánh giá kết quả: Kiểm tra giữa kỳ (60’) + l Chương 5. Mô hình biến nguyên Bài tập nghiên cứu/thực hành + Thi cuối kỳ (60’) l Làm bài được phép sử dụng tài liệu Mô hình hóa Mô hình hóa © TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội 1
Chương 1. Nhu cầu Giới thiệu về Mô hình hóa Nghiên cứu qua Mô hình Luôn có nhu cầu nghiên cứu hoàn thiện các hệ thống. 1. vai trò của mô hình hóa Khó khăn gặp phải: 2. tiềm năng ứng dụng l khi tiếp cận/tái tạo các hệ thống đang tồn tại 3. các bước thực hiện mô hình hóa l khi không hiệu quả (về thời gian, nguồn lực, chi phí) nếu nghiên cứu trên hệ thống thực 4. thành phần của một mô hình ra quyết định l khi nghiên cứu các hệ thống chưa tồn tại 5. một số yếu tố ảnh hưởng tới mô hình hóa => cần 1 công cụ nghiên cứu: mô hình! Mô hình hóa Mô hình hóa Các loại Mô hình Mô hình ra quyết định l mô hình nguyên mẫu thu nhỏ (prototype): là sự thể l Nhằm tìm kiếm đáp ứng tốt nhất (tối ưu) cho một hiện cấu trúc hệ thống qua các quan hệ vật chất hữu vấn đề cần ra quyết định trong điều kiện có các hình, ví dụ như các mẫu thiết kế/kiến trúc, mô hình hạn chế, ràng buộc (về nguồn lực, v.v.) nhà xưởng, mẫu máy bay/ôtô thử nghiệm l mô hình ra quyết định (decision model): là sự thể l Mô hình hóa = sử dụng công cụ mô hình toán để hiện hệ thống qua các quan hệ toán học hay logíc, giải quyết vấn đề tối ưu cho hệ thống ví dụ như mô hình dự báo nhu cầu sản phẩm, mô hình tương tác điện từ l mô hình khác => Bài toán Tối ưu hóa Mô hình hóa Mô hình hóa © TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội 2
Ví dụ Tiềm năng ứng dụng l Tính toán vị trí đặt nhà máy để giảm thiểu chi phí vận chuyển nguyên vật liệu và sản phẩm l Mô hình “Lập thời biểu tuần tra” cho cảnh sát San Francisco: l Thiết kế bộ phận dịch vụ khách hàng tại các ngân => tiết kiệm chi phí 11 triệu đôla/năm, giảm thời hàng, siêu thị, hãng taxi gian phản ứng 20% & tăng thu từ tiền phạt vi phạm l Thiết kế qui trình vận hành của robot/tay máy tại giao thông 3 triệu đôla. (Interfaces 19, 1989, no.1). các dây chuyền sản xuất, lắp ráp l Lập mô hình bố trí sản xuất giảm thiểu tác động l Mô hình “Dự trữ nhiên liệu tối ưu” cho Viện môi trường Nghiên cứu Điện lực Hoa Kỳ (EPRI) cắt giảm trên l Điều độ sản xuất sao cho đáp ứng nhu cầu với chi 125 triệu đôla từ chi phí dự trữ nhiên liệu tại 79 cty phí tối thiểu điện lực trên toàn nước Mỹ. (Interfaces 19, 1989, l V.v. no.1). Mô hình hóa Mô hình hóa Mô hình hóa Minh họa Quá trình chế tạo một sản phẩm thường qua nhiều công đoạn và đòi hỏi sự tham gia từ nhiều bộ phận khác nhau trong doanh nghiệp, từ bộ phận thiết kế đến bộ phận kế hoạch, bộ phận vật tư, Hệ thống thực xưởng sản xuất, bộ phận lưu kho, đến bộ phận marketing và bán hàng. Nhu cầu xác định sản lượng tối ưu mà DN cần duy trì ? Hệ thống thực có vô số quan hệ ràng buộc và yếu tố ảnh hưởng Hệ thống giả Mô đến sản lượng của DN cần được xem xét. lập hình Hệ thống giả lập chỉ “trích ra” những ràng buộc và ảnh hưởng có tính then chốt đối với sự vận động của hệ thống thực. Mô hình lại “giản hóa” những quan hệ then chốt này thành các công thức toán học dưới dạng hàm mục tiêu và tập hợp các ràng buộc. Mô hình hóa Mô hình hóa © TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội 3
Các bước thực hiện mô Các bước mô hình hóa hình hóa 1. Xác định vấn đề: tìm hiểu vấn đề gặp phải, tìm hiểu hệ thống, xác định các phương án có thể ra 1. Xác định vấn đề quyết định, thu thập số liệu 2. Xây dựng mô hình 2. Xây dựng mô hình: lượng hóa các quan hệ, xác 3. Giải mô hình định loại mô hình phù hợp, và phương pháp sử 4. Kiểm chứng mô hình dụng để giải mô hình 5. Ứng dụng kết quả vào thực tế & 3. Giải mô hình: tìm phương án tối ưu và các phương đánh giá án lựa chọn nếu có, phân tích độ nhạy để dự đoán hành vi của nghiệm khi các thông số thay đổi Mô hình hóa Mô hình hóa Các bước mô hình hóa Chu trình thực hiện 4. Kiểm chứng mô hình: kiểm tra xem mô hình có thể hiện được hành vi của hệ thống không, phương Xác định Xây dựng pháp phổ biến là so sánh với các số liệu quá khứ. Vấn đề Mô hình Điều chỉnh lại mô hình nếu cần. 5. Ứng dụng kết quả và đánh giá: trình bày kết quả thu được với người ra quyết định trong đơn vị, diễn Áp dụng & Giải giải kết quả thành các hành động cụ thể, phối hợp Đánh giá Mô hình cùng thực hiện và đánh giá kết quả của việc áp dụng. Rút ra bài học. Kiểm chứng Mô hình hóa Mô hình hóa © TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội 4
Thành phần của một Mô hình Ví dụ Công ty R. sản xuất sơn tường nhà gồm 2 loại: sơn Ba thành phần cơ bản: trong nhà (giá bán 20 triệu đồng/tấn) và sơn ngoài nhà (giá bán 30 triệu đồng/tấn). l các phương án lựa chọn (biến ra quyết định), Hai nguyên liệu chủ yếu A và B được cung cấp tối đa l các điều kiện ràng buộc của vấn đề (=> mỗi ngày là 6 tấn A và 8 tấn B. Để sản xuất 1 tấn sơn nghiệm khả thi), và trong nhà cần 2 tấn nguyên liệu A và 1 tấn nguyên liệu B, trong khi 1 tấn sơn ngoài trời cần 1 tấn A và 2 tấn B. l tiêu chí lựa chọn phương án (hàm mục tiêu, Nghiên cứu thị trường cho thấy nhu cầu tối đa đối với => nghiệm tối ưu). sơn trong nhà là 2 tấn /ngày. Vậy công ty R. nên sản xuất bao nhiêu tấn sơn mỗi loại để doanh thu đạt lớn nhất? Mô hình hóa Mô hình hóa Ví dụ (tiếp) Ví dụ (tiếp) Tóm tắt vấn đề: Công ty cần xác định số lượng (tấn) sơn 2. Hàm mục tiêu: thể hiện đích mà mô hình muốn mỗi loại sẽ sản xuất để tối đa hóa tổng doanh thu trong khi hướng tới, trong trường hợp này là tối đa hóa thỏa mãn các điều kiện ràng buộc về mức độ sử dụng các tổng doanh thu từ việc bán 2 loại sơn. nguyên liệu. 1.Biến ra quyết định: thể hiện phương án lựa chọn cho 3. Các điều kiện ràng buộc: thể hiện những yêu người ra quyết định, trong trường hợp này là lượng sơn SX cầu đặt ra đối với các giá trị của biến để nhằm – số tấn sơn trong nhà sản xuất mỗi ngày ồm hạn chế về mức độ sử dụng từng loại nguyên – số tấn sơn ngoài trời sản xuất mỗi ngày liệu (A, B) không vượt quá lượng nguyên liệu sẵn có, và thỏa mãn đòi hỏi của thị trường (nhu Đây là bước quan trọng nhất có ảnh hưởng đến cầu tối đa 2 tấn sơn trong nhà) và các biến là thành công của việc lập và giải mô hình. không âm Mô hình hóa Mô hình hóa © TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội 5
Vai trò của số liệu Thuật toán sử dụng l Kết quả của mô hình chỉ có ý nghĩa khi có l Mong muốn giải ra nghiệm tối ưu số liệu đầu vào tin cậy l Không phải tất cả các mô hình đều có thuật toán l Mô hình tất định: các thông số đã biết chắc tương ứng giải ra nghiệm tối ưu – vấn đề thời gian! chắn l Phương pháp tìm kiếm nghiệm gần tối ưu được l Mô hình bất định: 1 vài số liệu chưa biết nghiên cứu áp dụng cho 1 số loại mô hình: chắc chắn – Thời gian tính toán – Chất lượng nghiệm gần tối ưu l Nhu cầu thay đổi mô hình để phù hợp với các số liệu sẵn có Mô hình hóa Mô hình hóa Kết luận l mô hình hóa có vai trò và tiềm năng quan trọng trong đời sống và SXKD l có 5 bước thực hiện mô hình hóa l ba thành phần của một mô hình ra quyết định l yếu tố số liệu đầu vào và thuật toán phù hợp có ảnh hưởng lớn tới mô hình hóa Mô hình hóa Mô hình hóa © TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội 6
Trường Đại học Bách khoa Hà Nội Viện Kinh tế và Quản lý Chương 2. Mô hình Tuyến tính (LP) 1. Đặc tính của mô hình tuyến tính MÔ HÌNH HÓA 2. Phương pháp giải bằng đồ thị HỆ THỐNG SẢN XUẤT 3. Bài toán cơ cấu sản phẩm 4. Phân tích độ nhạy 5. Bài toán phối trộn sản phẩm TS. Đặng Vũ Tùng Hànội - 2014 Mô hình hóa Mục tiêu của Chương Lịch sử ra đời & phát triển Giúp sinh viên: l Ra đời từ đầu TK20 trong lĩnh vực quân sự l Nắm được các đặc trưng của bài toán LP l Là công cụ giải bài toán tối ưu hóa l Biết cách xây dựng mô hình LP cho bài toán l Được ứng dụng rộng rãi trong quân sự, các sản xuất ngành công nghiệp, nông nghiệp, ngân hàng, l Biết cách giải bài toán LP giáo dục, hóa dầu, vận tải, y tế, lâm nghiệp, và l Biết cách phân tích độ nhạy của nghiệm thậm chí cả các ngành khoa học xã hội. l Các công ty Fortune 500: 85% có sử dụng LP (thời lượng: 8 tiết + 4 tiết thực hành) Mô hình hóa Mô hình hóa © TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội 7
Ví dụ 2.1 Thế nào là bài toán LP Bài toán cơ cấu sản phẩm Công ty R. sản xuất 2 loại sơn tường : sơn trong nhà (giá Là một bài toán tối ưu hóa trong đó: bán 20 tr.đ/tấn) và sơn ngoài nhà (giá bán 30 tr.đ/tấn). l Phân bổ các nguồn lực cho các hoạt động Hai nguyên liệu chủ yếu A và B được cung cấp tối đa 6 l Nhằm đến tối ưu hóa một mục tiêu tấn A và 8 tấn B mỗi ngày. Sản xuất 1 tấn sơn trong nhà cần 2 tấn nguyên liệu A và 1 tấn nguyên liệu B, trong khi l Việc phân bổ nguồn lực phải thỏa mãn các 1 tấn sơn ngoài trời cần 1 tấn A và 2 tấn B. điều kiện ràng buộc về các tài nguyên Nghiên cứu thị trường => nhu cầu tối đa 2 tấn sơn và/hoặc các hoạt động trong nhà /ngày; nhu cầu sơn trong nhà không nhiều hơn l Các ràng buộc và mục tiêu đều là các đẳng nhu cầu sơn ngoài trời quá 1 tấn / ngày. thức hay bất đẳng thức tuyến tính Công ty R. nên sản xuất bao nhiêu tấn sơn mỗi loại để đạt doanh thu lớn nhất? Mô hình hóa Mô hình hóa Ví dụ 2.1 (2/5) Ví dụ 2.1 (3/5) Tóm tắt vấn đề: Công ty cần xác định số lượng (tấn) sơn mỗi 2. Hàm mục tiêu: thể hiện đích mà mô hình muốn loại sẽ sản xuất để tối đa hóa tổng doanh thu trong khi thỏa mãn hướng tới, trong trường hợp này là tối đa hóa các điều kiện ràng buộc về mức độ sử dụng các nguyên liệu và tổng doanh thu từ việc bán lượng sơn đã SX ra. nhu cầu thị trường. l Vì mỗi tấn sơn trong nhà bán được 20 triệu 1.Biến ra quyết định: thể hiện phương án lựa chọn cho người đồng, nên doanh thu từ sơn trong nhà là 20 xt. ra quyết định, trong trường hợp này là lượng sơn SX l Tương tự doanh thu từ sơn ngoài trời là 30 xn. – Xt = số tấn sơn trong nhà sản xuất mỗi ngày l Với giả thiết là việc tiêu thụ 2 loại sơn độc lập – Xn = số tấn sơn ngoài trời sản xuất mỗi ngày với nhau thì tổng doanh thu z = 20 xt + 30 xn. l Hàm mục tiêu: Max z = 20 xt + 30 xn. Đây là bước quan trọng nhất có ảnh hưởng đến thành công của việc lập và giải mô hình. Mô hình hóa Mô hình hóa © TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội 8
Ví dụ 2.1 (4/5) Ví dụ 2.1 (5/5) 3. Các điều kiện ràng buộc: thể hiện những yêu cầu đặt ra Mô hình xây dựng được: đối với các giá trị của biến, gồm: l Hạn chế về mức độ sử dụng từng loại nguyên liệu (A, B) không vượt quá lượng nguyên liệu sẵn có: max: z = 20xt + 30xn – 2xt + xn  6 (nguyên liệu A) thỏa mãn: 2xt + xn  6 (1) – xt + 2xn  8 (nguyên liệu B) xt + 2xn  8 (2) l Hạn chế về nhu cầu thị trường của hai loại sơn, tức là xt - xn  1 (3) “lượng sơn trong nhà trừ lượng sơn bên ngoài”  1 xt 2 (4) tấn/ngày, và “nhu cầu sơn trong nhà”  2 tấn/ngày: – xt - xn  1 (chênh lệch giữa 2 loại sơn) xt  0, xn  0 (5), (6) – xt 2 (sơn trong nhà) l Các biến là không âm: xt  0; xn  0 Mô hình hóa Mô hình hóa Giả thiết cho bài toán LP Giả thiết cho bài toán LP (1/2) (2/2) 1. Giả định về tính tỷ lệ (proportionality): 3. Giả định về tính chia được (divisibility): Đóng góp của mỗi biến ra quyết định vào giá trị Tính chia được yêu cầu mỗi biến được phép của hàm mục tiêu hay vào mức độ sử dụng tài nhận các giá trị không nguyên (giá trị thực). nguyên tỷ lệ thuận với giá trị của biến ra quyết 4. Giả định về tính chắc chắn (certainty): định đó. Giả định này cho rằng tất cả các thông số của bài 2. Giả định về tính cộng được (addivity): toán (các hệ số trong hàm mục tiêu, các hệ số Đóng góp của mỗi biến ra quyết định vào giá trị công nghệ và các giá trị ở vế phải của các hàm của hàm mục tiêu / hàm ràng buộc độc lập với ràng buộc) đều là các hằng số đã biết một cách giá trị của các biến khác. chắc chắn. Mô hình hóa Mô hình hóa © TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội 9
PP Giải bằng đồ thị (1) PP Giải bằng đồ thị (2) l Bước 1. Vẽ miền nghiệm của bài toán. l Bước 2. Thể hiện hàm mục tiêu trên đồ thị. xt xt (5) z=0 z = 60 z = 126,67 8 6 (3) Z 6 (2) 4 (1) 4 (4) 2 E D 2 F C E D F C l Bước 3. Tìm A B A B nghiệm tối ưu: C 0 2 4 6 xn 0 2 4 6 (6) xn Mô hình hóa Mô hình hóa PP Giải bằng đồ thị (3) Trường hợp đặc biệt (1) a) Trường hợp vô số nghiệm. Ví dụ 2.1.a Tính toán giá trị của nghiệm: l Lưu ý rằng C là điểm giao giữa các đường thẳng VD 2.1: Do cạnh tranh, giá bán của sơn trong nhà (1) và (2), tức là C đồng thời thỏa mãn : giảm xuống còn 15 tr.đ/tấn.x t – 2xt + xn = 6 (1) Phương án SX tối ưu? Z – xt + 2xn = 8 (2) 4 l => xt = 11/3 , xn = 31/3 . Tức là cty nên SX 11/3 tấn Đường Z // ràng buộc (2) sơn trong nhà và 31/3 tấn sơn bên ngoài mỗi ngày. => mọi điểm trên đoạn CB 2 E D l Doanh thu cực đại tương ứng là: đều đạt z tối đa F C z = 20xt + 30xn = 126 2/3 (triệu đồng). A B 0 2 4 6 xn Mô hình hóa Mô hình hóa © TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội 10
Trường hợp đặc biệt (2) Trường hợp đặc biệt (3) b) Trường hợp vô c) Trường hợp nghiệm không xác định. Ví dụ 2.1.c nghiệm. Ví dụ 2.1.b VD 2.1: nhà cung cấp đảm bảo cung cấp không hạn chế xt (5) (8) VD 2.1: GĐ cty đặt chỉ lượng nguyên liệu A, B mỗi ngày. tiêu sản xuất ít nhất 1,5 8 Phương án SX tối ưu? tấn sơn trong nhà và 3,5 xt (3) (5) (2) (3) tấn sơn bên ngoài / ngày. 6 6 Phương án SX tối ưu? Miền nghiệm không bị chặn. (1) 4 Z có thể dịch chuyển tăng 4 (4) (7) vô tận mà không rời khỏi (4) Miền nghiệm không tồn 2 miền nghiệm 2 tại !!! Mô hình hóa 0 2 4 6 (6) xn Mô hình hóa 0 2 4 6 (6) xn PP giải bằng Bảng tính PP giải bằng Bảng tính l Bước 1: Nhập tất cả các thông số đầu vào l Bước 3: Tính toán lượng tài nguyên mỗi của mô hình loại sử dụng bởi các biến (dùng hàm – Đóng khung các ô này bằng viền màu xanh SUMPRODUCT) – Nhập dấu của các ràng buộc l Bước 2: Nhập giá trị bất kỳ vào các ô có thể l Bước 4: Tính toán doanh thu (dùng hàm thay đổi (biến ra quyết định) SUMPRODUCT) – Đóng khung các ô này bằng viền màu đỏ – Đóng khung ô mục tiêu bằng viền màu đen Mô hình hóa Mô hình hóa © TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội 11
PP giải bằng Bảng tính Hộp thoại Solver l Nhấn vào Tools/Solver l Nhập thông số vào hộp thoại Solver – Xem slide sau l Đánh dấu vào ô Assume Linear Model trong phần Options – Giữ nguyên các giá trị mặc định khác l Nhấn vào nút Solve Mô hình hóa Mô hình hóa Đặc tính của nghiệm tối ưu Phân tích độ nhạy l Sơn trong nhà sản xuất 1,33 tấn/ngày l Nửa trên trình bày mỗi hàng ứng với một ô l Sơn ngoài trời sản xuất 3,33 tấn/ngày có giá trị thay đổi (biến) l Tổng doanh thu đạt 126,67 triệu đ/ngày – Chú ý tới giá trị “reduced costs” l Toàn bộ lượng nguyên liệu A, B đều sử l Nửa dưới trình bày mỗi hàng ứng với một dụng hết ràng buộc (không phải là các giới hạn trên và dưới của các biến) – Chú ý tới giá trị “shadow prices” Mô hình hóa Mô hình hóa © TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội 12
Phân tích độ nhạy Một số bài toán SX khác l Một cách khác để phân tích độ nhạy là thay l Bài toán phối trộn nguyên vật liệu đổi các thông số đầu vào và chạy lại mô l Bài toán dự trữ - sản xuất tối ưu hình (Solver) l Bài toán danh mục đầu tư l Biện pháp này rõ ràng và đơn giản nhưng l V.v. không thuận tiện khi có nhiều thông số đầu vào Mô hình hóa Mô hình hóa Bài toán phối trộn Nhận xét bài toán phối trộn l Cho số lượng các nguyên liệu đầu vào (nhận giá trị liên tục) l Bài toán đơn giản nhưng khi giải cần đặc l Phối trộn sao cho thỏa mãn: biệt lưu ý một số mẹo – Ràng buộc về sản lượng đầu ra l Ràng buộc phi tuyến có thể chuyển thành – Ràng buộc về chất lượng (thành phần, v.v.) tuyến tính bằng phép nhân đơn giản – Chi phí có liên quan đến quá trình phối trộn l Lựa chọn kỹ biến ra quyết định l Trong các cách có thể, chọn biện pháp mang lại lợi – Chia nhỏ các biến ra để dễ dàng tính toán và ích tối đa (chi phí tối thiểu, v.v.) khống chế các yêu cầu về chất lượng Mô hình hóa Mô hình hóa © TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội 13
Trường Đại học Bách Khoa Hà Nội Viện Kinh tế và Quản lý Chương 3. *** Các Bài toán Vận tải 1. Bài toán vận tải (transportation) MÔ HÌNH HÓA 2. Bài toán giao việc (assignment) HỆ THỐNG SẢN XUẤT 3. Bài toán chuyển hàng (transshipment) 4. Bài tập ứng dụng TS. Đặng Vũ Tùng Hànội - 2014 Mô hình hóa Mục tiêu của Chương 3.1. Bài toán Vận tải Giúp sinh viên: l Bài toán vận tải liên quan đến việc xác định cách l Nắm được các đặc trưng của bài toán vận tải thức vận chuyển một loại hàng hóa từ một số điểm l Biết cách lập mô hình vận tải cân bằng, các nguồn (điểm cung, chẳng hạn như các nhà máy) phương pháp giải mô hình đến một số điểm đích (điểm cầu, chẳng hạn như l Biết cách lập và giải mô hình cho bài toán phân các nhà kho). việc; phương pháp Hungary l Quá trình ra quyết định về tuyến đường tốt nhất để l Biết cách lập mô hình cho bài toán chuyển hàng vận chuyển này thường liên quan đến yếu tố chi l Biết cách dùng phần mềm để giải mô hình phí vận tải giữa các điểm cung - cầu, hoặc các (thời lượng: 4 tiết + 4 tiết thực hành) ràng buộc tương tự. Mô hình hóa Mô hình hóa © TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội 14
Ví dụ 3.1: Truyền tải điện Ví dụ 3.1 – tiếp Đến l Công ty Powerco mua điện từ 3 nhà máy điện để cấp điện cho 4 thành phố. Từ Tp 1 Tp 2 Tp 3 Tp 4 Cung l Mỗi nhà máy có sản lượng cung cấp điện & Nhu (GWh) cầu phụ tải đỉnh của các thành phố ở bảng sau Nhà máy 1 $8 $6 $10 $9 35 l Chi phí truyền tải từ nhà máy đến nơi tiêu thụ phụ Nhà máy 2 $9 $12 $13 $7 50 thuộc vào khoảng cách giữa 2 điểm này l Lập mô hình để giảm thiểu chi phí truyền tải điện Nhà máy 3 $14 $9 $16 $5 40 của Powerco Cầu (GWh) 45 20 30 30 Mô hình hóa Mô hình hóa Ví dụ 3.1 Ví dụ 3.1 l Biến ra quyết định: l Mô hình LP cho bài toán Powerco – Powerco cần xác định lượng điện truyền tải từ mỗi nhà Min Z = 8x11+6x12+10x13+9x14+9x21+12x22+13x23+7x24 máy đến mỗi thành phố, nên đặt xij = lượng điện cấp từ +14x31+9x32+16x33+5x34 nhà máy i cho thành phố j l x14 = lượng điện cấp từ nhà máy 1 cho thành phố 4 Th.mãn: x11+x12+x13+x14 ≤ 35 (Ràng buộc cung) l Ràng buộc: x21+x22+x23+x24 ≤ 50 – Ràng buộc phía cung để đảm bảo tổng lượng điện mà x31+x32+x33+x34 ≤ 40 mỗi nhà máy cung cấp không thể vượt quá sản lượng tối đa của nhà máy x11+x21+x31 ≥ 45 (Ràng buộc cầu) – Ràng buộc phía cầu để đảm bảo tổng lượng điện mà mỗi x12+x22+x32 ≥ 20 th.phố nhận được thỏa mãn nhu cầu phụ tải của th. phố x13+x23+x33 ≥ 30 – Lượng điện truyền tải không thể âm, nên xij≥ 0 (i,j). x14+x24+x34 ≥ 30 xij ≥ 0 (i= 1,2,3; j= 1,2,3,4) (Không âm) Mô hình hóa Mô hình hóa © TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội 15
Ví dụ 3.1 Bài toán Vận tải tổng quát Điểm cung Điểm cầu Th.phố d1=45 l Một bài toán vận tải tổng quát được đặc 1 s1=35 Nhà x11=0 trưng bởi những thông tin sau: x12=10 máy 1 x14=0 x13=25 – Một tập m điểm cung cấp mà từ đó hàng hóa sẽ d2=20 Th.phố x21=45 2 được vận chuyển đi. Mỗi điểm cung i có thể s2=50 Nhà x22=0 x23=5 cung cấp tối đa si đơn vị hàng. máy 2 x24=0 d3=30 – Một tập n điểm cầu mà hàng hóa sẽ được vận Th.phố x31=0 x32=10 3 chuyển tới. Mỗi điểm cầu j phải nhận được tối s3=40 Nhà máy 3 x33=0 thiểu dj đơn vị hàng. x34=30 Th.phố d4=30 – Mỗi đơn vị hàng hóa vận chuyển từ điểm cung i 4 tới điểm cầu j đòi hỏi chi phí cij. Mô hình hóa Mô hình hóa Mô hình tổng quát Trường hợp đặc biệt l Bài toán có các ràng buộc như trên với hàm l Xij = số đơn vị hàng được chuyển từ điểm cung i tới mục tiêu là max vẫn là một bài toán vận tải điểm cầu j : l Nếu i si = j dj thì tổng cung bằng với tổng cầu, và bài toán đó được gọi là bài toán vận tải cân bằng (balanced transportation problem), khi đó tất cả các ràng buộc đều trở thành ràng buộc chặt (binding constraint) : j Xij = si và i Xij = dj l Bài toán vận tải cân bằng có thể giải dễ dàng hơn các bài toán LP khác Mô hình hóa Mô hình hóa © TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội 16
Cân bằng Bài toán Vận tải Cân bằng Bài toán Vận tải l Trường hợp tổng cung vượt quá tổng cầu: l Trường hợp tổng cầu vượt quá tổng cung : – Cân bằng bài toán vận tải bằng cách tạo ra một điểm – Không có nghiệm khả thi, vì sẽ có một phần nhu cầu cầu ‘giả’ (dummy) có lượng cầu đúng bằng lượng cung không được thỏa mãn dư – Nếu được phép không đáp ứng một phần nhu cầu, với – Do việc chuyển hàng đến điểm cầu giả này không thực mỗi đơn vị hàng bị thiếu phải chịu khoản ‘tiền phạt’ xảy ra, nên chi phí vận chuyển tới điểm này bằng 0 (penalty), – Lượng hàng chuyển từ mỗi điểm cung tới điểm cầu giả – Thì có thể lập bài toán cân bằng nhờ một điểm cung đúng bằng lượng cung dư thừa của điểm cung đó ‘giả’ (dummy) có chi phí vận chuyển tới mỗi điểm cầu – Nếu hàng hóa dư thừa tại điểm cung phải chịu phí lưu đúng bằng mức tiền phạt tại điểm cầu đó kho, thì đơn giá vận tải từ đó đến điểm cầu giả sẽ đúng – Lượng hàng chuyển tới một điểm cầu từ điểm cung giả bằng chi phí lưu kho thể hiện lượng hàng bị thiếu tại điểm cầu đó Mô hình hóa Mô hình hóa Giải Bài toán Vận tải Phương pháp Góc Tây-Bắc l Khác với các bài toán LP khác, bài toán vận tải l Xuất phát từ góc trên bên trái (Tây-Bắc) của Bảng Vận cân bằng với m điểm cung và n điểm cầu rất dễ tải, gán cho x11 giá trị lớn nhất có thể (= min{s1, d1}) giải, dù có tới m + n ràng buộc là đẳng thức l Gạch hàng/cột đã được thỏa mãn, các ô còn lại trong l Nguyên nhân là nếu một tập các giá trị (xij) thỏa hàng/cột đó sẽ nhận giá trị 0. Nếu cả hàng và cột cùng mãn (m + n – 1) ràng buộc thì ràng buộc còn lại sẽ thỏa mãn thì chỉ được gạch một nghiễm nhiên được thỏa mãn. l Cập nhật lượng cung/cầu còn lại và tiếp tục áp dụng quá l Khi giải bằng phương pháp đơn hình (simplex), trình gán cho ô tây-bắc của Bảng không nằm trên một nghiệm cơ sở có thể tìm dễ dàng bằng các phương hàng / cột đã bị gạch pháp Góc Tây-Bắc, Chi phí Cực tiểu, hay Vogel l Quá trình kết thúc khi trong bảng chỉ còn một hàng hoặc thông qua Bảng vận tải (transportation tableau) một cột chưa bị gạch Đặc điểm: đơn giản, nhưng chưa tính đến yếu tố chi phí Mô hình hóa Mô hình hóa © TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội 17
Phương pháp Chi phí Cực tiểu Phương pháp Vogel Phương pháp này thực hiện tương tự như phpháp Phương pháp xấp xỉ Vogel (VAM) thường cho nghiệm Góc Tây-Bắc, nhằm tìm nghiệm cơ sở và có tính cơ sở gần tối ưu đến chi phí vận chuyển: l Bắt đầu với việc tính giá trị penalty cho mỗi l Tìm biến có chi phí nhỏ nhất (cij=min), gán xij cho hàng/cột (đúng bằng chênh lệch giữa 2 giá trị nhỏ giá trị lớn nhất có thể (=min{s1, d1}) nhất trong cùng hàng/cột đó) l Gạch hàng/cột đã thỏa mãn, và cập nhật lượng l Xác định hàng/cột có penalty lớn nhất, gán giá trị tối cung/cầu còn lại đa cho biến có chi phí nhỏ nhất trong hàng/cột đó l Lặp lại với ô tiếp theo có chi phí nhỏ nhất và l Gạch hàng/cột tương ứng (tương tự các pp trước), không nằm trên hàng/cột đã bị gạch tính lại các giá trị penalty Phpháp này thường cho nghiệm cơ sở có chi phí lớn l Lặp lại cho đến khi chỉ còn 1 hàng/cột chưa bị gạch Mô hình hóa Mô hình hóa Ứng dụng : Ví dụ 3.2 Bài toán Sản xuất – Dự trữ Chuyển đổi sang bài toán vận tải Một công ty lập kế hoạch SX cho 4 tháng tới: Hệ thống Vận tải Hệ thống Sản xuất l Nhu cầu các tháng: 100, 200, 180 và 300 đvị. Điểm cung i Kỳ sản xuất i l Năng lực SX tương ứng: 50, 180, 280 và 270 đvị. Điểm cầu j Kỳ tiêu thụ j l Hàng có thể giao ngay, dự trữ hoặc giao chậm Lượng cung tại nguồn i Năng lực Sxuất của kỳ i l Chi phí: sản xuất = 4$/đvị, Nhu cầu tại đích j Nhu cầu của khách hàng lưu kho = 0.5$/đvị/thg, trong kỳ j giao hàng chậm = 2$/đvị/thg Chi phí vận chuyển từ Chi phí sản xuất và dự l Xác định kế hoạch SX để chi phí tối thiểu. nguồn i đến đích j trữ từ kỳ i đến kỳ j Mô hình hóa Mô hình hóa © TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội 18
Ví dụ 3.2 - Bảng Tableau Ví dụ 3.2 – Kế hoạch SX Cung 50 180 280 270 Kỳ tiêu thụ Kỳ SX 1 2 3 4 N.lực Kỳ sản xuất 1 2 3 4 1 4 4.5 5 5.5 50 50 50 130 70 180 30 270 2 6 4 4.5 5 180 3 8 6 4 4.5 280 Kỳ tiêu thụ 1 2 3 4 4 10 8 6 4 270 Nhu cầu 100 200 180 300 780 Cầu 100 200 180 300 Mô hình hóa Mô hình hóa 3.2. Bài toán Giao việc Ví dụ 3.3: Bố trí máy l Cty Machineco có 4 cỗ Chi 1 2 3 4 l Các bài toán giao việc (assignment) là một máy và cần gia công 4 chi tiết lớp các bài toán vận tải đặc biệt có thể được tiết. Mỗi máy phải gia công một chi tiết. Máy 14 5 8 7 giải một cách đơn giản và hiệu quả hơn rất l Thời gian cần thiết để mỗi 1 nhiều mà không cần dùng đến phương pháp máy khởi động & gia công Máy 2 12 6 5 đơn hình (simplex). 1 chi tiết như sau: 2 l Machineco cần bố trí máy Máy 7 8 3 9 thế nào để thời gian hoàn 3 thành là tối thiểu Máy 2 4 6 10 4 Mô hình hóa Mô hình hóa © TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội 19
Ví dụ 3.3 – Mô hình Đặc điểm Bài toán l Machineco cần xác định máy nào được giao gia công chi tiết l Bài toán giao việc chính là bài toán vận tải cân bằng, trong nào. Đặt biến: đó mọi cung cầu đều bằng 1. l xij=1 (nếu máy i được giao thực hiện chi tiết j) l Được đặc trưng bởi các chi phí có liên quan đến việc gán l xij=0 (nếu máy i không được giao thực hiện chi tiết j) mỗi điểm cung cho một điểm cầu (ma trận chi phí). l i,j=1,2,3,4 l Do lượng cung và lượng cầu của bài toán giao việc là • Mô hình nguyên, nên nghiệm tối ưu cũng nhận giá trị nguyên. min z = 14x11+5x12+8x13+7x14 +2x21+12x22+6x23+5x24 l Do vế phải (RHS) của mỗi ràng buộc đều bằng 1, mỗi biến +7x31+8x32+3x33+9x34 +2x41+4x42+6x43+10x44 xij phải là số nguyên không lớn hơn 1. Nên xij phải là 0 th.mãn j xij = 1 (i=1,2,3,4) (ràng buộc về máy) i xij = 1 (j=1,2,3,4) (ràng buộc về chi tiết) hoặc 1, và ta có thể bỏ qua ràng buộc xij = 0 hoặc 1, và giải xij = 0 hoặc 1 bài toán như một bài toán vận tải cân bằng. Mô hình hóa Mô hình hóa Phương pháp Hungary Phương pháp Hungary (2) l Phương pháp Hungary rất hiệu quả để giải các bài l Bước 2: Gạch số đường tối thiểu (ngang hoặc toán giao việc mà không cần sử dụng đến phép dọc) sao cho đi qua tất cả mọi số 0 trong ma trận biến đổi đơn hình (simplex). Các bước thực hiện: tối giản. Nếu cần tổng cộng m đường thẳng, thì l Bước 1: Tìm phần tử nhỏ nhất trong mỗi hàng của nghiệm tối ưu có được từ các giá trị 0 đã được ma trận chi phí (m x m). Lập ma trận mới bằng gạch qua. Nếu chỉ cần ít hơn m đường => Bước 3. cách trừ giá trị trong mỗi ô cho giá trị nhỏ nhất l Bước 3: Tìm phần tử khác 0 nhỏ nhất (có giá trị là trong hàng tương ứng. Với ma trận này lại tìm k) chưa bị gạch qua trong ma trận tối giản ở Bước phần tử nhỏ nhất trong mỗi cột, và xây dựng ma 2. Trừ k từ mỗi phần tử chưa được kẻ qua của ma trận tối giản bằng cách trừ trừ giá trị trong mỗi ô trận tối giản, và cộng k vào những phần tử được cho giá trị nhỏ nhất trong cột tương ứng. gạch qua 2 lần. Quay lại bước 2. Mô hình hóa Mô hình hóa © TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội 20