Quản lý dự án - Mô hình hóa hệ thống sản xuất

ộn l Bài toán đơn giản nhưng khi giải cần đặc biệt lưu ý một số mẹo l Ràng buộc phi tuyến có thể chuyển thành tuyến tính bằng phép nhân đơn giản l Lựa chọn kỹ biến ra quyết định – Chia nhỏ các biến ra để dễ dàng tính toán và khống chế các yêu cầu về chất lượng 14© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội MÔ HÌNH HÓA HỆ THỐNG SẢN XUẤT TS. Đặng Vũ Tùng Hànội - 2014 Trường Đại học Bách Khoa Hà Nội Viện Kinh tế và Quản lý *** Mô hình hóa Chương 3. Các Bài toán Vận tải 1. Bài toán vận tải (transportation) 2. Bài toán giao việc (assignment) 3. Bài toán chuyển hàng (transshipment) 4. Bài tập ứng dụng Mô hình hóa Mục tiêu của Chương Giúp sinh viên: l Nắm được các đặc trưng của bài toán vận tải l Biết cách lập mô hình vận tải cân bằng, các phương pháp giải mô hình l Biết cách lập và giải mô hình cho bài toán phân việc; phương pháp Hungary l Biết cách lập mô hình cho bài toán chuyển hàng l Biết cách dùng phần mềm để giải mô hình (thời lượng: 4 tiết + 4 tiết thực hành) Mô hình hóa 3.1. Bài toán Vận tải l Bài toán vận tải liên quan đến việc xác định cách thức vận chuyển một loại hàng hóa từ một số điểm nguồn (điểm cung, chẳng hạn như các nhà máy) đến một số điểm đích (điểm cầu, chẳng hạn như các nhà kho). l Quá trình ra quyết định về tuyến đường tốt nhất để vận chuyển này thường liên quan đến yếu tố chi phí vận tải giữa các điểm cung - cầu, hoặc các ràng buộc tương tự. 15© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa Ví dụ 3.1: Truyền tải điệ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ố. l Mỗi nhà máy có sản lượng cung cấp điện & Nhu cầu phụ tải đỉnh của các thành phố ở bảng sau l Chi phí truyền tải từ nhà máy đến nơi tiêu thụ phụ 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 của Powerco Mô hình hóa Ví dụ 3.1 – tiếp Từ Đến Tp 1 Tp 2 Tp 3 Tp 4 Cung (GWh) Nhà máy 1 $8 $6 $10 $9 35 Nhà máy 2 $9 $12 $13 $7 50 Nhà máy 3 $14 $9 $16 $5 40 Cầu (GWh) 45 20 30 30 Mô hình hóa Ví dụ 3.1 l Biến ra quyết định: – Powerco cần xác định lượng điện truyền tải từ mỗi nhà máy đến mỗi thành phố, nên đặt xij = lượng điện cấp từ 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 l Ràng buộc: – Ràng buộc phía cung để đảm bảo tổng lượng điện mà 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 – Ràng buộc phía cầu để đảm bảo tổng lượng điện mà mỗi th.phố nhận được thỏa mãn nhu cầu phụ tải của th. phố – Lượng điện truyền tải không thể âm, nên xij≥ 0 (i,j). Mô hình hóa Ví dụ 3.1 l Mô hình LP cho bài toán Powerco Min Z = 8x11+6x12+10x13+9x14+9x21+12x22+13x23+7x24 +14x31+9x32+16x33+5x34 Th.mãn: x11+x12+x13+x14 ≤ 35 (Ràng buộc cung) x21+x22+x23+x24 ≤ 50 x31+x32+x33+x34 ≤ 40 x11+x21+x31 ≥ 45 (Ràng buộc cầu) x12+x22+x32 ≥ 20 x13+x23+x33 ≥ 30 x14+x24+x34 ≥ 30 xij ≥ 0 (i= 1,2,3; j= 1,2,3,4) (Không âm) 16© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa Ví dụ 3.1 Nhà máy 1 Nhà máy 2 Nhà máy 3 Th.phố 1 Th.phố 2 Th.phố 3 Th.phố 4 s1=35 s2=50 s3=40 d1=45 d2=20 d3=30 d4=30 x11=0 x12=10 x13=25x14=0 x21=45 x24=0 x22=0 x23=5 x31=0 x34=30 x32=10 x33=0 Điểm cung Điểm cầu Mô hình hóa Bài toán Vận tải tổng quát lMột bài toán vận tải tổng quát được đặc trưng bởi những thông tin sau: – Một tập m điểm cung cấp mà từ đó hàng hóa sẽ được vận chuyển đi. Mỗi điểm cung i có thể cung cấp tối đa si đơn vị hàng. – Một tập n điểm cầu mà hàng hóa sẽ được vận chuyển tới. Mỗi điểm cầu j phải nhận được tối thiểu dj đơn vị hàng. – Mỗi đơn vị hàng hóa vận chuyển từ điểm cung i tới điểm cầu j đòi hỏi chi phí cij. Mô hình hóa Mô hình tổng quát l Xij = số đơn vị hàng được chuyển từ điểm cung i tới điểm cầu j : Mô hình hóa 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 mục tiêu là max vẫn là một bài toán vận tải 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 17© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa 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: – Cân bằng bài toán vận tải bằng cách tạo ra một điểm cầu ‘giả’ (dummy) có lượng cầu đúng bằng lượng cung dư – Do việc chuyển hàng đến điểm cầu giả này không thực xảy ra, nên chi phí vận chuyển tới điểm này bằng 0 – Lượng hàng chuyển từ mỗi điểm cung tới điểm cầu giả đúng bằng lượng cung dư thừa của điểm cung đó – Nếu hàng hóa dư thừa tại điểm cung phải chịu phí lưu kho, thì đơn giá vận tải từ đó đến điểm cầu giả sẽ đúng bằng chi phí lưu kho Mô hình hóa Cân bằng Bài toán Vận tải l Trường hợp tổng cầu vượt quá tổng cung : – Không có nghiệm khả thi, vì sẽ có một phần nhu cầu không được thỏa mãn – Nếu được phép không đáp ứng một phần nhu cầu, với mỗi đơn vị hàng bị thiếu phải chịu khoản ‘tiền phạt’ (penalty), – Thì có thể lập bài toán cân bằng nhờ một điểm cung ‘giả’ (dummy) có chi phí vận chuyển tới mỗi điểm cầu đúng bằng mức tiền phạt tại điểm cầu đó – Lượng hàng chuyển tới một điểm cầu từ điểm cung giả thể hiện lượng hàng bị thiếu tại điểm cầu đó Mô hình hóa Giải Bài toán Vận tải l Khác với các bài toán LP khác, bài toán vận tải cân bằng với m điểm cung và n điểm cầu rất dễ giải, dù có tới m + n ràng buộc là đẳng thức l Nguyên nhân là nếu một tập các giá trị (xij) thỏa mãn (m + n – 1) ràng buộc thì ràng buộc còn lại sẽ nghiễm nhiên được thỏa mãn. l Khi giải bằng phương pháp đơn hình (simplex), nghiệm cơ sở có thể tìm dễ dàng bằng các phương pháp Góc Tây-Bắc, Chi phí Cực tiểu, hay Vogel thông qua Bảng vận tải (transportation tableau) Mô hình hóa Phương pháp Góc Tây-Bắc l Xuất phát từ góc trên bên trái (Tây-Bắc) của Bảng Vận tải, gán cho x11 giá trị lớn nhất có thể (= min{s1, d1}) l Gạch hàng/cột đã được thỏa mãn, các ô còn lại trong hàng/cột đó sẽ nhận giá trị 0. Nếu cả hàng và cột cùng thỏa mãn thì chỉ được gạch một l Cập nhật lượng cung/cầu còn lại và tiếp tục áp dụng quá trình gán cho ô tây-bắc của Bảng không nằm trên một hàng / cột đã bị gạch l Quá trình kết thúc khi trong bảng chỉ còn một hàng hoặc 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í 18© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa Phương pháp Chi phí Cực tiểu Phương pháp này thực hiện tương tự như phpháp Góc Tây-Bắc, nhằm tìm nghiệm cơ sở và có tính đến chi phí vận chuyển: l Tìm biến có chi phí nhỏ nhất (cij=min), gán xij cho giá trị lớn nhất có thể (=min{s1, d1}) l Gạch hàng/cột đã thỏa mãn, và cập nhật lượng cung/cầu còn lại l Lặp lại với ô tiếp theo có chi phí nhỏ nhất và không nằm trên hàng/cột đã bị gạch Phpháp này thường cho nghiệm cơ sở có chi phí lớn Mô hình hóa Phương pháp Vogel Phương pháp xấp xỉ Vogel (VAM) thường cho nghiệm cơ sở gần tối ưu l Bắt đầu với việc tính giá trị penalty cho mỗi hàng/cột (đúng bằng chênh lệch giữa 2 giá trị nhỏ nhất trong cùng hàng/cột đó) l Xác định hàng/cột có penalty lớn nhất, gán giá trị tối đa cho biến có chi phí nhỏ nhất trong hàng/cột đó l Gạch hàng/cột tương ứng (tương tự các pp trước), tính lại các giá trị penalty 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 Ứng dụng : Ví dụ 3.2 Bài toán Sản xuất – Dự trữ Một công ty lập kế hoạch SX cho 4 tháng tới: l Nhu cầu các tháng: 100, 200, 180 và 300 đvị. l Năng lực SX tương ứng: 50, 180, 280 và 270 đvị. l Hàng có thể giao ngay, dự trữ hoặc giao chậm l Chi phí: sản xuất = 4$/đvị, lưu kho = 0.5$/đvị/thg, giao hàng chậm = 2$/đvị/thg l Xác định kế hoạch SX để chi phí tối thiểu. Mô hình hóa Chuyển đổi sang bài toán vận tải Hệ thống Vận tải Hệ thống Sản xuất Điểm cung i Kỳ sản xuất i Điểm cầu j Kỳ tiêu thụ j Lượng cung tại nguồn i Năng lực Sxuất của kỳ i Nhu cầu tại đích j Nhu cầu của khách hàng trong kỳ j Chi phí vận chuyển từ nguồn i đến đích j Chi phí sản xuất và dự trữ từ kỳ i đến kỳ j 19© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa Ví dụ 3.2 - Bảng Tableau Kỳ SX Kỳ tiêu thụ 1 2 3 4 N.lực 1 4 4.5 5 5.5 50 2 6 4 4.5 5 180 3 8 6 4 4.5 280 4 10 8 6 4 270 Nhu cầu 100 200 180 300 780 Mô hình hóa Ví dụ 3.2 – Kế hoạch SX 1 2 3 4 50 180 280 270 1 2 3 4 50 130 180 270 100 200 180 300 50 70 30 Cung Cầu Kỳ tiêu thụ Kỳ sản xuất Mô hình hóa 3.2. Bài toán Giao việc l Các bài toán giao việc (assignment) là một lớp các bài toán vận tải đặc biệt có thể được giải một cách đơn giản và hiệu quả hơn rất nhiều mà không cần dùng đến phương pháp đơn hình (simplex). Mô hình hóa Ví dụ 3.3: Bố trí máy l Cty Machineco có 4 cỗ máy và cần gia công 4 chi tiết. Mỗi máy phải gia công một chi tiết. l Thời gian cần thiết để mỗi máy khởi động & gia công 1 chi tiết như sau: l Machineco cần bố trí máy thế nào để thời gian hoàn thành là tối thiểu Chi tiết 1 2 3 4 Máy 1 14 5 8 7 Máy 2 2 12 6 5 Máy 3 7 8 3 9 Máy 4 2 4 6 10 20© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa Ví dụ 3.3 – Mô hình l Machineco cần xác định máy nào được giao gia công chi tiết nào. Đặt biến: l xij=1 (nếu máy i được giao thực hiện chi tiết j) l xij=0 (nếu máy i không được giao thực hiện chi tiết j) l i,j=1,2,3,4 • Mô hình min z = 14x11+5x12+8x13+7x14 +2x21+12x22+6x23+5x24 +7x31+8x32+3x33+9x34 +2x41+4x42+6x43+10x44 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) xij = 0 hoặc 1 Mô hình hóa Đặc điểm Bài toán l Bài toán giao việc chính là bài toán vận tải cân bằng, trong đó mọi cung cầu đều bằng 1. l Được đặc trưng bởi các chi phí có liên quan đến việc gán mỗi điểm cung cho một điểm cầu (ma trận chi phí). l Do lượng cung và lượng cầu của bài toán giao việc là nguyên, nên nghiệm tối ưu cũng nhận giá trị nguyên. l Do vế phải (RHS) của mỗi ràng buộc đều bằng 1, mỗi biến xij phải là số nguyên không lớn hơn 1. Nên xij phải là 0 hoặc 1, và ta có thể bỏ qua ràng buộc xij = 0 hoặc 1, và giải bài toán như một bài toán vận tải cân bằng. Mô hình hóa Phương pháp Hungary l Phương pháp Hungary rất hiệu quả để giải các bài toán giao việc mà không cần sử dụng đến phép biến đổi đơn hình (simplex). Các bước thực hiện: l Bước 1: Tìm phần tử nhỏ nhất trong mỗi hàng của ma trận chi phí (m x m). Lập ma trận mới bằng cách trừ giá trị trong mỗi ô cho giá trị nhỏ nhất trong hàng tương ứng. Với ma trận này lại tìm phần tử nhỏ nhất trong mỗi cột, và xây dựng ma trận tối giản bằng cách trừ trừ giá trị trong mỗi ô cho giá trị nhỏ nhất trong cột tương ứng. Mô hình hóa Phương pháp Hungary (2) l Bước 2: Gạch số đường tối thiểu (ngang hoặc dọc) sao cho đi qua tất cả mọi số 0 trong ma trận tối giản. Nếu cần tổng cộng m đường thẳng, thì nghiệm tối ưu có được từ các giá trị 0 đã được gạch qua. Nếu chỉ cần ít hơn m đường => Bước 3. l Bước 3: Tìm phần tử khác 0 nhỏ nhất (có giá trị là k) chưa bị gạch qua trong ma trận tối giản ở Bước 2. Trừ k từ mỗi phần tử chưa được kẻ qua của ma trận tối giản, và cộng k vào những phần tử được gạch qua 2 lần. Quay lại bước 2. 21© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa Ví dụ 3.3 – Giải bằng ph.pháp Hungary 14 5 8 7 2 12 6 5 7 8 3 9 2 4 6 10 9 0 3 2 0 10 4 3 4 5 0 6 0 2 4 8 9 0 3 0 0 10 4 1 4 5 0 4 0 2 4 6 10 0 3 0 0 9 3 0 5 5 0 4 0 1 3 5 Mô hình hóa 3.3. Bài toán Chuyển hàng l Trong bài toán vận tải, hàng chuyển trực tiếp từ điểm cung đến điểm cầu l Khi hàng có thể chuyển giữa các điểm cung hoặc giữa các điểm cầu, hoặc có thể qua các điểm trung chuyển trên đường từ điểm cung đến điểm cầu => Bài toán chuyển hàng (transshipment) l Định nghĩa: Điểm cung là điểm chỉ có thể gửi đi mà không nhận vào; Điểm cầu là điểm chỉ có thể nhận vào mà không gửi đi; Điểm trung chuyển vừa có thể nhận & gửi hàng Mô hình hóa Thuật toán l Tìm nghiệm tối ưu cho bài toán chuyển hàng bằng mô hình vận tải (giả thiết cung ≥ cầu): – Bước 1. Cân bằng bài toán (bổ sung điểm cầu giả nếu cần, có cung bằng 0 và cầu bằng lượng cung vượt trội). Hàng chuyển đến điểm này có chi phí bằng 0. – Bước 2. Lập bảng vận tải: mỗi hàng thể hiện cho một điểm cung / trung chuyển, mỗi cột thể hiện cho một điểm cầu / trung chuyển. Gọi s = tổng lượng cung. Mỗi điểm trung chuyển lượng cung (cầu) bằng lượng cung (cầu) ban đầu của điểm đó + s (đảm bảo lượng hàng tịnh qua điểm trung chuyển và để bài toán cân bằng) – Bước 3. Giải mô hình vận tải tìm được Mô hình hóa Ví dụ 3.4: Định tuyến vận chuyển l Cty GM sản xuất xe tại 2 nhà máy ở Memphis và Denver, có công suất 150 và 200 xe/ngày. Xe được chuyển tới khách hàng ở L.A & Boston, mỗi nơi có nhu cầu 130 xe/ngày. Hàng có thể giao trực tiếp hoặc thông qua kho ở N.Y hoặc Chicago. Xác định tuyến vận chuyển tối ưu. Từ \ Đến Memphis Denver N.Y Chicago L.A Boston Memphis 0 - 8 13 25 28 Denver - 0 15 12 26 25 N.Y - - 0 6 16 17 Chicago - - 6 0 14 16 L.A - - - - 0 - Boston - - - - - 0 22© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa Ví dụ 3.4: Mô hình N.Y Chicago L.A Boston Dummy Cầu Memphis 8 13 25 28 0 150 Denver 15 12 26 25 0 200 N.Y 0 6 16 17 0 350 Chicago 6 0 14 16 0 350 Cung 350 350 130 130 90 l Lập mô hình vận tải cân bằng cho bài toán chuyển hàng bằng cách bổ sung điểm cầu giả có nhu cầu = 150+200-130-130 = 90 Mô hình hóa Bài toán Lập kế hoạch SX l Nhu cầu của loại động cơ tiết kiệm năng lượng trong 5 tháng tới là 200, 150, 300, 250 và 400 chiếc. Nhà sản xuất có khả năng sản xuất tương ứng trong các tháng đó là 180, 230, 430, 300 và 300 chiếc. Hàng không được phép giao chậm, nhưng cty có thể huy động làm thêm giờ nếu cần, với sản lượng bổ sung đạt tối đa 50% công suất bình thường. Chi phí SX các tháng là 100$, 96$, 115$, 102$ và 105$. Chi phí cho động cơ làm ngoài giờ cao gấp rưỡi chi phí SX bình thường. Ngoài ra những động cơ được SX và dự trữ để bán sau sẽ có chi phí lưu kho 4$/đcơ/tháng. Lập mô hình vận tải để giải bài toán này. Mô hình hóa Bài toán Cung ứng dịch vụ l Một cty cung ứng dvụ ký HĐ cung cấp khăn trải bàn sạch cho 1 nhà hàng có nhu cầu trong tuần như sau. Cty có thể: - cung cấp khăn mới, với giá 1.2$/chiếc - giặt hấp nhanh để ngay sáng hôm sau nhận được khăn sạch, với giá 0.6$/chiếc - giặt hấp thông thường để 3 ngày sau nhận được khăn sạch, với giá 0.3$/chiếc l Cty nên lập kế hoạch cung ứng khăn ntn? Ngày CN T2 T3 T4 T5 T6 T7 Nhu cầu 240 120 140 200 180 140 220 Mô hình hóa Bài toán Điều xe l Cảnh sát 113 Hànội nhận được 3 cuộc gọi yêu cầu hỗ trợ. Hiện có 5 xe tuần tra có thể huy động, thời gian cần thiết để các xe này tới được nơi yêu cầu như trong bảng. Hãy dùng phương pháp Hungary để xác định xe nào cần điều đến vị trí nào. Xe 1 Xe 2 Xe 3 Xe 4 Xe 5 Cuộc gọi 1 10 6 7 5 9 Cuộc gọi 2 11 7 8 6 4 Cuộc gọi 3 18 7 5 4 7 23© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa Bài toán Bố trí lịch bay l AirVN cần bố trí phi hành đoàn cho các chuyến bay hàng ngày giữa Hà Nội (HAN) và thành phố HCM (SGN). Mỗi ngày một phi hành đoàn phải bay một chuyến HAN-SGN và 1 chuyến SGN- HAN với thời gian nghỉ giữa 2 chuyến bay tối thiểu là 1h. Cty muốn lập lịch bay sao cho giảm thiểu thời gian chờ giữa 2 chuyến bay của phi hành đoàn. l Dùng mô hình giao việc để giải bài toán, giả thiết rằng cuối ngày các nhân viên phi hành đoàn đều trở về nhà. Mô hình hóa Lịch bay AirVN Chuyến Rời HAN Đến SGN Chuyến Rời SGN Đến HAN 1 7 am 9 am 1 6.30 am 8.30 am 2 7.30 am 9.30 am 2 8 am 10 am 3 11 am 1 pm 3 12 pm 2 pm 4 3 pm 5 pm 4 2 pm 4 pm 5 5 pm 7 pm 5 5 pm 7 pm 6 7 pm 9 pm 6 6 pm 8 pm 7 9 pm 11 pm 7 8 pm 10 pm Mô hình hóa Bài toán Tuyển dụng LĐ l Một cty môi giới cần cung ứng lao động bán phổ thông cho 5 tháng tới với số lượng tương ứng là 100, 120, 80, 170, 50 người. Chi phí để sử dụng lao động phụ thuộc vào độ dài thời gian thuê lao động. Dùng mô hình chuyển hàng xây dựng kế hoạch tuyển LĐ để chi phí là nhỏ nhất? Thời gian thuê LĐ (tháng) 1 2 3 4 5 Chi phí/LĐ (triệu đồng) 1 1,3 1,8 2,2 2,5 Mô hình hóa 24© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội MÔ HÌNH HÓA HỆ THỐNG SẢN XUẤT TS. Đặng Vũ Tùng Hànội - 2014 Trường Đại học Bách Khoa Hà Nội Viện Kinh tế và Quản lý *** Mô hình hóa Chương 4. Một số mô hình Mạng 1. Bài toán Tuyến đường ngắn nhất (shortest path) 2. Bài toán Lưu lượng tối đa (maximum flow) 3. Bài toán Mạng với chi phí tối thiểu (minimum cost capacitated network) 4. Bài toán cây tối thiểu (minimum spanning tree) 5. Bài tập ứng dụng: Kiểm soát dự án (CPM & PERT) Mô hình hóa Mục tiêu của Chương Giúp sinh viên: l Nắm được các đặc trưng của bài toán mạng l Biết cách lập mô hình để đưa một bài toán về dạng mô hình mạng l Lập mô hình cho một số bài toán mạng cơ bản l Dùng phần mềm để giải mô hình (thời lượng: 6 tiết + 4 tiết thực hành) Mô hình hóa 4.1. Khái niệm l Bài toán vận tải và các biến thể của nó là những bài toán có thể biểu diễn và giải bằng mô hình mạng. l Một số ví dụ khác: – Thiết kế mạng đường ống dẫn khí tự nhiên nối các giếng khoan ở Biển Đông vào nhà máy chế biến khí Dinh Cố – Xác định tuyến đường ngắn nhất nối 2 thành phố trong mạng giao thông đường bộ hiện có – Xác định kế hoạch vận chuyển với chi phí nhỏ nhất từ nơi khai thác dầu đến nhà máy lọc dầu và tới các trung tâm phân phối xăng dầu. Xăng dầu có thể vận chuyển bằng tàu thủy, xe bồn hoặc đường ống với công suất tối đa đã biết 25© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa Khái niệm (tiếp) l Nhiều bài toán tối ưu hóa có thể phân tích rất thuận tiện thông qua biểu đồ (graph) biểu thị quan hệ giữa các yếu tố. l Một biểu đồ mạng được xác định bởi tập các nút (node) và các cung (arc). l Trong mỗi mạng có dòng chảy (flow) của hàng hóa dưới dạng nào đó (dầu chảy qua mạng đường ống, dòng xe chạy trong mạng giao thông,..) l Các dòng chảy qua một cung bị hạn chế bởi công suất của cung (có thể là hữu hạn hoặc vô hạn) l Một cung sẽ là có hướng nếu nó cho dòng chảy dương qua nó theo một chiều và không cho chảy theo chiều ngược lại. Một mạng có hướng sẽ gồm nếu các cung của nó đều có hướng Mô hình hóa 4.2 Bài toán Tuyến đường ngắn nhất l Giả thiết mỗi cung trong mạng có độ dài xác định l Bài toán tìm đường đi ngắn nhất từ nút mạng số 1 đến một nút bất kỳ trong mạng gọi là Bài toán Tuyến đường ngắn nhất l Ví dụ: tìm đường ngắn nhất từ nhà T đến giảng đường D8 Mô hình hóa Ví dụ 4.1: Thay thế thiết bị l Một thiết bị mới được mua với giá $12,000 tại thời điểm 0. l Chi phí bảo dưỡng thiết bị trong một năm phụ thuộc vào số năm đã khai thác thiết bị (tuổi của thiết bị) l Có thể thanh lý máy cũ và mua máy mới để tránh chi phí bảo dưỡng quá lớn. giả thiết giá máy mới là không đổi l Mục tiêu là tối thiểu hóa chi phí cho 5 năm hoạt động Tuổi (năm) Chi phí bảo dưỡmg Giá thanh lý 0 $2,000 - 1 $4,000 $7,000 2 $5,000 $6,000 3 $9,000 $2,000 4 $12,000 $1,000 5 - $0 Mô hình hóa Ví dụ 4.1 – Lập mô hình mạng l Bài toán này có thể được lập mô hình dưới dạng bài toán tuyến đường ngắn nhất l Biểu đồ mạng gồm có 6 nút: – Nút i là thời điểm bắt đầu năm i và với i<j, cung (i,j) ứng với việc mua thiết bị mới ở đầu năm i và sử dụng đến đầu năm j. l Chiều dài của cung (i,j) là cij chính là tổng chi phí khi sử dụng máy từ năm i đến năm j cij = chi phí bảo dưỡng các năm i,i+1,,j-1 + chi phí mua máy mới đầu năm i - giá thanh lý máy cũ đầu năm j 26© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa Ví dụ 4.1 – Tính toán chi phí l Chiều dài các cung ứng với chi phí vận hành từ thời điểm i đến thời điểm j: c12=2+12-7=7 c13=2+4+12-6=12 c14=2+4+5+12-2=21 c15=2+4+5+9+12-1=31 c16=2+4+5+9+12+12-0=44 c23=2+12-7=7 c24=2+4+12-6=12 c25=2+4+5+12-2=21 c26=2+4+5+9+12-1=31 c34=2+12-7z=7 c35=2+4+12-6=12 c36=2+4+5+12-2=21 c45=2+12-7=7 c46=2+4+12-6=12 c56=2+12-7=7 Mô hình hóa Ví dụ 4.1 – Nghiệm l Từ biểu đồ có thể thấy cả hai tuyến 1-3-5-6 và 1-2-4-6 đều cho giá trị nhỏ nhất (=31). 1 65432 7 7 7 7 7 21 12 12 21 31 12 21 31 44 12 Mô hình hóa Phương pháp giải l Với giả thiết các cung có độ dài không âm, thuật toán Dijkstra được dùng để tìm tuyến ngắn nhất từ một nút mạng l Có thể lập bài toán này như bài toán trung chuyển (transshipment): 1 đơn vị hàng chuyển từ điểm nguồn đến điểm đích qua các tuyến khác nhau trong mạng. Mục tiêu là giảm thiểu quãng đường đi từ điểm nguồn đến điểm đích. l Giải bài toán trung chuyển bằng LINGO Mô hình hóa Bảng tableau Mua\Bán 2 3 4 5 6 1 7 12 21 31 44 1 2 0 7 12 21 31 B 3 - 0 7 12 21 B 4 - - 0 7 12 B 5 - - - 0 7 B B B B B 1 27© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa 4.3 Bài toán Lưu lượng Tối đa (Maximum Flow) l Nhiều tình huống có thể lập mô hình dưới dạng một mạng trong đó các cung có một năng lực hạn chế về lượng hàng có thể chuyển qua cung đó l Trong những tình huống đó, thường có nhu cầu vận chuyển dòng hàng tối đa từ một điểm ban đầu (nguồn) đến một điểm cuối (đích) l Những loại bài toán này gọi là Bài toán Lưu lượng Tối đa Mô hình hóa Ví dụ 4.2: Lưu lượng tối đa l Cty Sunco Oil muốn chuyển lượng dầu tối đa (mỗi giờ) qua hệ thống đường ống từ điểm so đến điểm si. l Các cung thể hiện các tuyến đường ống có Ø khác nhau => quyết định số thùng dầu tối đa có thể chuyển qua đường ống (công suất của cung) so si21 (2)2 (2)3 (2)2 (0)3 a0(2) 3(0)4 (0)1 Cung Công suất (1000 thùng/giờ) (so,1) 2 (so,2) 3 (1,2) 3 (1,3) 4 (3,si) 1 (2,si) 2 Mô hình hóa Phương pháp giải l Lập mô hình LP để xác định số thùng dầu tối đa có thể chuyển từ so đến si mỗi giờ l Lập cung giả a0 nối điểm đích đến điểm nguồn l Xác định biến ra quyết định: – xij = Lượng thùng dầu chuyển qua cung (i,j) mỗi giờ l Để có dòng chảy tồn tại phải thỏa mãn 2 đặc tính: – 0 <= lưu lượng chảy qua cung <= công suất của cung – Lưu lượng chảy vào nút i = Lưu lượng chảy ra khỏi nút i l Bài toán Lưu lượng tối đa có thể giải thuận tiện bằng LINGO Mô hình hóa Phương pháp giải l Gọi x0 = lưu lượng qua cung giả ao, nguyên lý bảo toàn dòng chảy => x0 = tổng lượng dầu đến điểm đích l Mục tiêu của Sunco là tối đa hóa x0. l Một nghiệm tối ưu cho bài toán LP này là Z=3, xso,1=2, x13=1, x12=1, xso,2=1, x3,si=1, x2,si=2, xo=3. Max Z= X0 S.t. Xso,1<=2 (Công suất của cung) Xso,2<=3 X12<=3 X2,si<=2 X13<=4 X3,si<=1 X0=Xso,1+Xso,2 (Cân bằng nút so) Xso,1=X12+X13 (Cân bằng nút 1) Xso,2+X12=X2,si (Cân bằng nút 2) X13+X3,si (Cân bằng nút 3) X3,si+X2,si=X0 (Cân bằng nút si) Xij>=0 28© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa Ví dụ 4.3 : Định tuyến vận chuyển l Hãng HK Fly-by-Night cần bố trí các chuyến bay nối chuyến giữa Juneau (Alaska) và Dallas (Texas). Các chuyến bay phải dừng tại Settle, rồi dừng ở Los Angeles hoặc Denver. Cty được cấp phép số chuyến bay tối đa giữa các thành phố mỗi ngày như sau. Hãy lập kế hoạch bay để tăng tối đa số chuyến bay hàng ngày từ Juneau đến Dallas. Chuyến Số lượng max Juneau- Settle 3 Settle – Los Angeles 2 Settle -Denver 3 Los Angeles - Dallas 1 Denver -Dallas 2 Mô hình hóa 4.4. Bài toán mạng với chi phí tối thiểu (MCCN) l Các bài toán vận tải, giao việc, trung chuyển, tuyến đường ngắn nhất, lưu lượng tối đa,.. đều là các trường hợp đặc biệt của bài toán mạng với chi phí tối thiểu (minimum cost capacitated network - MCCN). l Dạng thức chung của bài toán MCCN: (với mỗi nút i trong mạng) (với mỗi cung trong mạng) Mô hình hóa MCCN – Đặc điểm bài toán l Ràng buộc yêu cầu tổng dòng ra tịnh của nút i phải bằng bi được gọi là phương trình cân bằng dòng. l Các phương trình cân bằng dòng trong bài toán MCCN có thuộc tính quan trọng sau: Mỗi biến xij có hệ số +1 trong phương trình cân bằng của nút i, hệ số -1 trong phương trình cân bằng của nút j, và hệ số là 0 trong tất cả các phương trình cân bằng khác. l Dùng LINGO để giải dễ dàng các bài toán MCCN. Mô hình hóa Ví dụ 4.4 - Bài toán MCCN l Một cty sản xuất 1 hợp chất cơ bản để làm các loại sơn. Cty có 2 nhà máy và ký hợp đồng cung cấp từ 2 nhà cung ứng để bán SP cho 2 khách hàng. Hợp đồng cung ứng 500 và 700 tấn nguyên liệu từ nhà cung ứng 1 và 2 với gia tương ứng là 200$ và 210$/tấn. Để tạo 1 tấn hợp chất cần 1.2 tấn nguyên liệu. Chi phí vận chuyển, công suất của các nhà máy và nhu cầu của khách hàng như trong bảng. Nhà máy Chi phí SX/ tấn CS min (tấn) CS max (tấn) 1 25$ 400 800 2 28$ 450 900 Nhà máy Nhà cung ứng S1 Nhà cung ứng S2 Khách hàng C1 Khách hàng C2 1 10$ 9$ 3$ 4$ 2 12$ 13$ 5$ 2$ 29© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa Ví dụ 4.4 - Bài toán MCCN l Sơ đồ mạng biểu diễn bài toán: 1 4 53 2200$ (500,) 210$ (750,) 10$ (0,500) 13$ (0,750) 9$ 12$ (0,500) (450,900) 8 97 6 3$ 2$ 5$ 4$ 25$ 28$ (400,800) [-660] [-800] [F] Mô hình hóa Ví dụ 4.5 - Bài toán vận tải dưới dạng MCCN (1) l Mô hình MCCN dùng mô tả bài toán vận tải khi: – Điểm cung nối trực tiếp với điểm cầu – Công suất tối thiểu của các cung bằng 0 – Công suất tối đa của các cung bằng  1 2 4 3 Điểm cung 1 Điểm cung 2 Điểm cầu 2 Điểm cầu 1 1 2 4 (Nút 1) 3 4 5 (Nút 2) 6 (Nút 3) 3 (Nút 4) Mô hình hóa Ví dụ 4.5 - Bài toán vận tải dưới dạng MCCN (2) l Biểu diễn dưới dạng MCCN: min Z = X13+2X14+3X23+4X24 X13 X14 X23 X24 1 1 0 0 = 4 Nút 1 0 0 1 1 = 5 Nút 2 -1 0 -1 0 = -6 Nút 3 1 -1 0 -1 = -3 Nút 4 Các biến không âm Mô hình hóa Bài toán tuyến đường ngắn nhất dưới dạng MCCN l Mô hình MCCN dùng mô tả bài toán tuyến đường ngắn nhất khi: – Điểm nguồn chuyển +1 đơn vị hàng và điểm đích nhận -1 đơn vị – Tất cả các cung có công suất tối thiểu của các cung bằng 0, và công suất tối đa của các cung bằng  – Đơn giá chi phí của dòng vận chuyển trên mỗi cung thể hiện khoảng cách giữa các nút mạng l Mục tiêu của bài toán là chuyển 1 đơn vị hàng từ nguồn đến đích với chi phí (khoảng cách) là nhỏ nhất 30© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa Bài toán lưu lượng tối đa dưới dạng MCCN l Mô hình MCCN dùng mô tả bài toán lưu lượng tối đa khi: – Công suất tối đa của các cung thể hiện dòng tối đa cho phép, công suất tối thiểu của các cung bằng 0 – Tất cả các cung có đơn giá chi phí vận chuyển bằng 0 – Lượng chuyển từ nút nguồn và lượng nhận tại nút đích được đặt tương ứng bằng +F và –F. Giá trị F cần chọn đủ lớn để cho phép dòng tối đa chảy qua mạng – Một cung trực tiếp nối điểm nguồn với điểm đích. Mục đích là để chuyển lượng dư (surplus) của F không chảy qua mạng. Cung này không có hạn chế về công suất, và có chi phí vận chuyển đủ lớn để lượng hàng qua mạng ban đầu là lớn nhất. Mô hình hóa Ví dụ 4.6 - Bài toán lưu lượng tối đa dưới dạng MCCN l Xét ví dụ 4.2. Ta có: bso=b1=b2=b3=bsi=0 min Z = -X0 Xso,1 Xso,2 X13 X12 X3,si X2,si X0 1 1 0 0 0 0 -1 = 0 Nút so -1 0 1 1 0 0 0 = 0 Nút 1 0 -1 0 -1 0 1 0 = 0 Nút 2 0 0 -1 0 1 0 0 = 0 Nút 3 0 0 0 0 -1 -1 1 = 0 Nút si 1 0 0 0 0 0 0 ≤ 2 Cung (so,1) 0 1 0 0 0 0 0 ≤ 3 Cung (so,2) 0 0 1 0 0 0 0 ≤ 4 Cung (1,3) 0 0 0 1 0 0 0 ≤ 3 Cung (1,2) 0 0 0 0 1 0 0 ≤ 1 Cung (3,si) 0 0 0 0 0 1 0 ≤ 2 Cung (2,si) Các biến không âm Mô hình hóa Ví dụ 4.7 - Bài toán giao thông l Mỗi giờ có trung bình 900 xe vào mạng tại nút 1 để đi đến nút 6. Thời gian cần để đi qua mỗi phố và số xe tối đa có khả năng lưu thông qua mỗi phố trong 1 giờ (trong ngoặc) như trên hình. Lập mô hình MCCN để tối thiểu hóa tổng thời gian cần để tất cả các xe đi qua mạng từ nút 1 đến nút 6. 1 6 4 53 210 (800) 50 (600) 30 (600) 60 (400) 30 (600) 60 (400) 10 (300) 70 (100) 30 (600) Mô hình hóa 4.5 Bài toán Cây tối thiểu (Minimum Spanning Tree) l Xét trường hợp cần tạo mạng đường giao thông nối liền một số cụm dân cư ở vùng nông thôn. Do ngân sách hạn hẹp nên cần xây dựng số km đường tối thiểu mà vẫn cho phép giao thông từ nơi này đến nơi khác. l Trường hợp trên có thể biểu diễn bằng một mạng lưới trong đó mỗi cụm dân là một nút và mỗi con đường là một cung. 31© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa Bài toán Cây tối thiểu l Mô hình thu được là một điển hình của bài toán cây tối thiểu, trong đó phải xác định tập các cung trong một mạng sao cho chúng nối tất cả các nút mạng với nhau với tổng độ dài các cung là nhỏ nhất ( kết nối có hiệu quả nhất tất cả các nút mạng với nhau) l Mỗi cung (i,j) trong mạng có một độ dài nhất định, và cung (i,j) biểu diễn việc kết nối nút i với nút j l Với một mạng có n nút, một cây là nhóm n-1 cung nối tất cả các nút của mạng với nhau và không tạo thành vòng Mô hình hóa Thuật toán Cây tối thiểu l Bước 1. Bắt đầu từ nút i bất kỳ, nối nó với nút j gần nhất trong mạng. Hai nút i, j tạo thành tập các nút kết nối C={i,j} và cung (i,j) nằm trong cây tối thiểu. Các nút còn lại trong mạng tạo thành tập các nút chưa kết nối C’ l Bước 2. Chọn một phần tử thuộc C’ (nút n) gần nhất với một phần tử bất kỳ nằm trong C (nút m). Cung (m,n) sẽ thuộc cây tối thiểu. Cập nhật các tập C (gồm nút i,j, n) và C’ (loại bỏ nút n). l Bước 3. Lặp lại quá trình trên cho đến khi tập C’ rỗng, tức là toàn bộ các nút đã nằm trong cây tối thiểu. Các phương án có cùng giá trị có thể lựa chọn ngẫu nhiên, và thể hiện các phương án thay thế. Mô hình hóa Ví dụ 4.8 – Kéo mạng cáp l Cty truyền hình cáp ABC (1) đang lập kế hoạch cung cấp dịch vụ cho 4 khu đô thị mới (2-5). l Xác định cách kết nối cần ít cáp nhất – Nếu không có đường nối giữa 2 khu đô thị nghĩa là về mặt kỹ thuật không thể kéo cáp trực tiếp giữa 2 khu đó 4 2 5 3 1 6 4 5 1 3 2 2 2 4 Mô hình hóa Ví dụ 4.8 – Kéo mạng cáp – Bước 1: Chọn nút 1 để bắt đầu. Nút gần nhất là 2. Do đó C={1,2}, Ć={3,4,5}, cung (1,2) là thuộc cây nhỏ nhất 4 2 5 3 1 6 4 5 1 3 2 2 2 4 32© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa Ví dụ 4.8 – Kéo mạng cáp l Bước 2: Nút 5 gần nhất với tập C. Do nút 5 cách đều nút 1 và 2, nên có thể đưa cung (2,5) hoặc (1,5) vào cây nhỏ nhất. Giả sử chọn cung (2,5). Vậy C={1,2,5} và Ć={3,4}. 4 2 5 3 1 6 4 5 1 3 2 2 2 4 Mô hình hóa Ví dụ 4.8 – Kéo mạng cáp l Bước 3: Do nút 3 gần nút 5 nhất, đưa cung (5,3) vào cây nhỏ nhất. Ta có C={1,2,5,3} và Ć={4}. 4 2 5 3 1 6 4 5 1 3 2 2 2 4 Mô hình hóa Ví dụ 4.8 – Kéo mạng cáp l Bước 4: Nút 5 gần nút 4 nhất. Đưa cung (5,4) vào cây nhỏ nhất l Cây nhỏ nhất gồm các cung (1,2), (2,5), (5,3), và (5,4). Chiều dài tối thiểu của cây là 1+2+2+4=9 4 2 5 3 1 6 4 5 1 3 2 2 2 4 Mô hình hóa 4.6 CPM & PERT l Mô hình mạng có thể dùng để lập tiến độ cho các dự án lớn gồm rất nhiều hoạt động l Nếu thời gian thực hiện mỗi hoạt động đã biết và xác định, thì phương pháp đường găng (CPM) có thể dùng để tính toán thời gian cần thiết để hoàn thành một dự án l Nếu thời gian thực hiện các hoạt động là chưa biết chắc chắn, thì phương pháp (PERT) có thể dùng để dự tính xác suất là dự án sẽ hoàn thành tại một mốc thời gian nào đó 33© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa Ứng dụng l CPM & PERT được sử dụng trong nhiều ứng dụng khác nhau, chẳng hạn: – Lập tiến độ cho các dự án xây dựng như xây tòa nhà văn phòng, chung cư, cầu đường, sân vận động, – Cài đặt hệ thống máy tính mới – Thiết kế và marketing sản phẩm mới – Đóng tàu – Hòan tất việc sát nhập công ty – V.v. Mô hình hóa Hoạt động của dự án l Để áp dụng CPM & PERT, cần liệt kê các hoạt động (activities) của dự án. l Dự án hoàn thành khi tất cả các hoạt động đã hoàn thành l Để bắt đầu một hoạt động nhất định cần hoàn thành một tập các hoạt động khác (hoạt động tiền đề) l Dùng biểu đồ mạng để thể hiện quan hệ trình tự trước sau giữa các hoạt động của dự án l Hoạt động thể hiện bằng các cung có hướng và các nút thể hiện sự kiện (event) hoàn thành các hoạt động (biểu đồ AOA) Mô hình hóa Biểu đồ mạng AOA l Biểu đồ dự án AOA được xây dựng dựa trên các hoạt động và quan hệ tiền đề với những quy tắc sau: 1. Nút 1 biểu diễn sự kiện bắt đầu dự án. Cung đi ra từ nút 1 thể hiện một hoạt động không có tiền đề. 2. Có một nút thể hiện sự hoàn thành dự án (nút kết thúc) 3. Đánh số các nút trong mạng để nút thể hiện điểm hoàn thành của một hoạt động luôn có số lớn hơn nút thể hiện điểm bắt đầu của hoạt động đó. 4. Một hoạt động không thể hiện bởi nhiều hơn một cung trong mạng 5. Hai nút chỉ nối với nhau bởi tối đa 1 cung. l Để tránh vi phạm quy tắc 4 &5, đôi khi cần sử dụng các hoạt động giả có thời gian thực hiện bằng không. Mô hình hóa Ví dụ: lập tiến độ dự án l Cty Widgetco chuẩn bị giới thiệu SP mới. Các hoạt động và trình tự như sau. Thể hiện dự án bằng biểu đồ mạng Hoạt động Hđ trước Thời gian (ngày) A: đào tạo công nhân - 6 B: mua nguyên liệu - 9 C: SX sản phẩm 1 A, B 8 D: SX sản phẩm 2 A, B 7 E: thử nghiệm sản phẩm 2 D 10 F: lắp ráp sản phẩm 1&2 C, E 12 34© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa Biểu đồ mạng l Biểu đồ dự án Widgetco 1 65 42 3 A (6) B (9) Hđộng giả C (8) D (7) E (10) F (12) Nút 1 = bắt đầu Nút 6 = kết thúc Mô hình hóa Thời gian bắt đầu sớm ET(i) l Thời gian bắt đầu sớm của nút i, ET(i), là thời điểm sớm nhất mà sự kiện ứng với nút i có thể diễn ra. l Để tìm thời gian bắt đầu sớm của mỗi nút mạng: – Tìm các sự kiện tiền đề trực tiếp của nút i (là nút được nối bằng một cung tới nút i) – cộng thời gian của mỗi hoạt động tiền đề với giá trị ET của mỗi sự kiện tiền đề của nút i, – ET(i) bằng giá trị lớn nhất của các tổng vừa tính Mô hình hóa Thời gian bắt đầu muộn LT(i) l Thời gian bắt đầu muộn của nút i, LT(i), là thời điểm chậm nhất mà sự kiện ứng với nút i có thể diễn ra mà không làm ảnh hưởng đến thời gian hoàn thành dự án. l Để tính LT(i) ta bắt đầu từ nút kết thúc và tính ngược lại: – Tìm mỗi nút xảy ra sau nút i và được nối trực tiếp với nút i bởi một cung. Những sự kiện này là sự kiện kế tiếp của nút i. – Trừ thời gian thực hiện của hoạt động kế tiếp của nút i từ giá trị LT(i) của sự kiện kế tiếp của nút i. – LT(i) là giá trị nhỏ nhất trong các giá trị vừa tính Mô hình hóa Ví dụ - Tính LT(i) – Từ biểu đồ ta biết thời gian hoàn thành muộn của nút 6 là ngày 38. – Do nút 6 là nút kế tiếp duy nhất của nút 5, nên LT(5)=LT(6)-12=26. Tương tự LT(4)= LT(5)-10=16. – Nút 4 và 5 là các nút kế tiếp của nút 3, do vậy 35© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa l Tính ET(i) & LT(i) cho bài toán Widgetco Nút ET(i) LT(i) 1 0 0 2 9 9 3 9 9 4 16 16 5 26 26 6 38 38 Mô hình hóa Tính toán đường găng l Khái niệm độ tự do tổng của một hoạt động (i,j), TF(i,j), của là thời gian mà thời điểm bắt đầu của hoạt động (i,j) có thể lui lại kể từ điểm bắt đầu sớm nhất của nó mà không làm chậm thời điểm hoàn thành dự án. l Một hoạt động có TF=0 là một hoạt động găng l Đường nối từ nút 1 đến nút kết thúc mà chỉ gồm toàn các hoạt động găng gọi là đường găng l Đường găng của ví dụ Widgetco là 1-2-3-4-5-6. Mô hình hóa Công cụ LP l Dùng LP để tính toán chiều dài đường găng: – Biến ra quyết định : xj – thời gian diễn ra sự kiện ứng với nút j – Mục tiêu là giảm thiểu thời gian cần để hoàn thành dự án, Z = xF-x1 – Với mỗi hoạt động (i,j), trước khi j diễn ra thì i phải diễn ra và hoạt động (i,j) đã hoàn thành l LP còn có thể dùng để xác định phương án phân bổ các nguồn lực của dự án để hoàn thành dự án với chi phí nhỏ nhất trong trừơng hợp cần hoàn thành dự án trong thời gian ngắn hơn chiều dài của đường găng (crashing) Mô hình hóa 145 Bài tập ứng dụng 36© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội MÔ HÌNH HÓA HỆ THỐNG SẢN XUẤT TS. Đặng Vũ Tùng Hànội - 2014 Trường Đại học Bách Khoa Hà Nội Viện Kinh tế và Quản lý *** Mô hình hóa 147 Chương 5. Bài toán Biến nguyên (IP) 1. Đặc tính của mô hình IP 2. Giải mô hình IP: phương pháp B&B 3. Một số Bài toán điển hình: 1. Lập tiến độ chạy máy 2. Bài toán Set-covering 3. Bài toán Chi phí cố định 4. Bài toán kế hoạch sản xuất 5. Bài toán Knap-sack 6. Bài toán TSP Mô hình hóa 148 5.1. Ví dụ 5.1 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á bán 20 tr.đ/bồn) và sơn ngoài nhà (giá bán 30 tr.đ/bồn). Hai nguyên liệu chủ yếu A và B được cung cấp tối đa 6 tấn A và 8 tấn B mỗi ngày. Sản xuất 1 bồ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 1 bồn sơn ngoài trời cần 1 tấn A và 2 tấn B. Nghiên cứu thị trường => nhu cầu tối đa 2 bồn sơn trong nhà /ngày; nhu cầu sơn trong nhà không được nhiều hơn nhu cầu sơn ngoài trời quá 1 bồn / ngày. Công ty R. nên sản xuất bao nhiêu bồn sơn mỗi loại để đạt doanh thu lớn nhất? (Số bồn sơn phải nguyên.) Mô hình hóa 149 Lập mô hình 1. Biến ra quyết định: thể hiện phương án lựa chọn cho người ra quyết định, trong trường hợp này là lượng sơn SX – Xt = số bồn sơn trong nhà sản xuất mỗi ngày – Xn = số bồn sơn ngoài trời sản xuất mỗi ngày 2. Hàm mục tiêu: thể hiện đích mà mô hình muốn hướng tới, tức là tối đa hóa tổng doanh thu từ việc bán lượng sơn đã SX ra: Z = 20 xt + 30 xn. l Hàm mục tiêu: Max z = 20 xt + 30 xn. 3. Các điều kiện ràng buộc: l Hạn chế về mức độ sử dụng từng loại nguyên liệu (A, B) : – 2xt + xn  6 (nguyên liệu A) – xt + 2xn  8 (nguyên liệu B) l Hạn chế về nhu cầu thị trường của hai loại sơn, : – xt - xn  1 (chênh lệch giữa 2 loại sơn) – xt  2 (sơn trong nhà) l Các biến nguyên & không âm: xt  0; xn  0; xt , xn = nguyên 37© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa 150 Mô hình IP cho bài toán max: z = 20xt + 30xn thỏa mãn: 2xt + xn  6 xt + 2xn  8 xt - xn  1 xt  2 xt  0, xn  0 xt , xn : nguyên Mô hình hóa 151 5.2. Khái niệm l Bài toán biến nguyên (integer programming - IP) là một bài toán qui hoạch trong đó một số hoặc toàn bộ các biến phải nhận giá trị nguyên và không âm. l Bài toán biến nguyên tuyến tính (integer linear programming - ILP) là một bài toán qui hoạch tuyến tính (LP) trong đó một số hoặc toàn bộ các biến phải nhận giá trị nguyên và không âm. l Nếu trong bài toán có ít nhất một quan hệ phi tuyến và có biến cần nhận giá trị nguyên thì ta có một bài toán biến nguyên phi tuyến (integer nonlinear programming - INP). Mô hình hóa 152 Khái niệm (2) l Bài toán IP mà tất cả các biến đều phải là có giá trị nguyên gọi là bài toán IP thuần túy (pure IP). l Bài toán IP trong đó chỉ có một số biến đòi hỏi giá trị nguyên gọi là bài toán IP hỗn hợp (mixed IP). l Bài toán IP trong đó tất cả các biến đều bằng 0 hoặc 1 được gọi là bài toán IP 0-1 (binary IP hay IP nhị phân). l Một bài toán IP luôn có thể biến đổi đưa về bài toán IP nhị phân Mô hình hóa 153 Nới lỏng về tuyến tính l Bài toán IP giải khó hơn bài toán LP rất nhiều - miền nghiệm rời rạc l Bài toán LP thu được khi loại bỏ tất cả các ràng buộc về điều kiện nguyên hoặc 0-1 đối với các biến của một bài toán IP được gọi là sự nới lỏng về tuyến tính cho bài toán IP. l Nghiệm của bài toán IP không bao giờ “tốt hơn” nghiệm của bài toán LP nới lỏng tương ứng 38© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa 154 Phương pháp B&B l Phương pháp B&B: giải bài toán LP, sau đó bổ sung dần các điều kiện rẽ nhánh theo các biến có giá trị không nguyên trong nghiệm tối ưu của bài toán LP. l Bản chất là liệt kê (enumeration) toàn bộ các điểm nghiệm trong miền nghiệm nguyên, loại bỏ chúng cho đến khi chỉ còn lại nghiệm nguyên tối ưu. Mô hình hóa 155 Thực hiện phương pháp B&B l Chọn biến để rẽ nhánh: – Bất kỳ hoặc rẽ nhánh theo biến có ý nghĩa kinh tế quan trọng nhất (có đóng góp lớn nhất vào hàm mục tiêu) l Điều kiện dừng rẽ nhánh: Một bài toán con (LP) sẽ không cần phải tiếp tục rẽ nhánh khi bài toán con đó : – không có nghiệm – có nghiệm tối ưu với tất cả các biến đều nhận giá trị nguyên – có giá trị z của nghiệm tối ưu không tốt hơn giới hạn dưới (LB) hiện có (với bài toán maximization) Mô hình hóa 156 Thực hiện phương pháp B&B l Qui tắc chọn nhánh rẽ : – Back-tracking: rẽ nhánh theo bài toán con tạo ra gần nhất – Jump-tracking: rẽ nhánh theo bài toán con có giá trị z tốt nhất hiện có l Cập nhật giá trị nghiệm tối ưu: – Cập nhật giá trị z tốt nhất hiện thời làm giới hạn xét các bài toán con tiếp theo (giới hạn dưới LB với bài toán max.) l Quá trình kết thúc khi: – Toàn bộ các bài toán con đã được dừng rẽ nhánh – Nghiệm của bài toán IP chính là nghiệm tốt nhất hiện có Mô hình hóa 157 Giải Bài toán Hỗn hợp Sản phẩm (vd 5.1) bằng B&B Bài toán con No.1 (LP relaxation): max: z = 20xt + 30xn thỏa mãn: 2xt + xn  6 xt + 2xn  8 xt - xn  1 xt  2 xt  0, xn  0 Nghiệm tối ưu: l xt = 1 1/3 , xn = 3 1/3 l Doanh thu max tương ứng là z1 = 126 2/3 39© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa 158 Rẽ nhánh theo xt : Bài toán con No.2 = No1 + điều kiện xt  1 : max:z = 20xt + 30xn thỏa mãn: 2xt + xn  6 xt + 2xn  8 xt - xn  1 xt  2 xt  0, xn  0 xt  1 Nghiệm tối ưu: l xt = 1 , xn = 3.5 l Doanh thu max tương ứng là z2 = 125 Mô hình hóa 159 Rẽ nhánh theo xt : Bài toán con No.3 = No1 + điều kiện xt  2 : max: z = 20xt + 30xn thỏa mãn: 2xt + xn  6 xt + 2xn  8 xt - xn  1 xt  2 xt  0, xn  0 xt  2 Nghiệm tối ưu: l xt = 2 , xn = 2 l Doanh thu max tương ứng là z3 = 100 => ứng viên nghiệm tối ưu; LB=100 Mô hình hóa 160 Rẽ nhánh theo xn : Bài toán con No.4 = No2 + điều kiện xn  3: max: z = 20xt + 30xn thỏa mãn: 2xt + xn  6 xt + 2xn  8 xt - xn  1 xt  2 xt  0, xn  0 xt  1 xn  3 Nghiệm tối ưu: l xt = 1 , xn = 3 l Doanh thu max tương ứng là z4 = 110 => ứng viên nghiệm tối ưu; LB=110 Mô hình hóa 161 Rẽ nhánh theo xn : Bài toán con No.5 = No2 + điều kiện xn 4 : max: z = 20xt + 30xn thỏa mãn: 2xt + xn  6 xt + 2xn  8 xt - xn  1 xt  2 xt  0, xn  0 xt  1 xn  4 Nghiệm tối ưu: l xt = 0 , xn = 4 l Doanh thu max tương ứng là z5 = 120 => ứng viên nghiệm tối ưu; LB=120 40© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa 162 Ví dụ 5.2. Bài toán lập tiến độ chạy máy (machine scheduling) l Bốn công việc cần được gia công trên một thiết bị. Thời gian cần để thực hiện mỗi việc và thời hạn hoàn thành của chúng như trong bảng dưới đây. Thời gian trễ hạn tính bằng số ngày kể từ khi hết hạn đến khi việc được hoàn thành (hoàn thành trước hoặc đúng hạn thì thời gian trễ hạn bằng 0). Vậy phải thực hiện các việc trên theo trình tự nào để tổng thời gian trễ hạn là thấp nhất. Việc Thời gian thực hiện Thời hạn hoàn thành 1 6 ngày Cuối ngày 8 2 4 ngày Cuối ngày 4 3 5 ngày Cuối ngày 12 4 8 ngày Cuối ngày 16 Mô hình hóa 163 Bài toán xác định trình tự chạy máy (job sequencing) l Nếu 4 công việc được thực hiện theo trình tự 1-2-3-4, thì tổng thời gian trễ hạn sẽ là 16 ngày. Việc Thời gian hoàn thành Số ngày trễ hạn 1 6 0 2 6 + 4 = 10 10 – 4 = 6 3 10 + 5 = 15 15 – 12 = 3 4 15 + 8 = 23 23 – 16 = 7 Tổng thời gian trễ D = 0+6+3+7 = 16 ngày Mô hình hóa 164 Giải bằng phương pháp B&B l Để xác định trình tự thực hiện công việc, đặt: xij = 1 nếu việc i được thực hiện ở thứ tự j = 0 nếu khác l Thực hiện phương pháp B&B bằng cách phân vùng các nghiệm theo việc được thực hiện cuối cùng. l Ta có trong nghiệm thu được: hoặc x14 = 1, hoặc x24 = 1, hoặc x34 = 1, hoặc x44 = 1 => rẽ nhánh theo việc hoàn thành cuối cùng Mô hình hóa 165 Kế hoạch gia công x14=1 x24=1 x34=1 x44=1 D≥15 D≥19 D≥11 D≥7 x13=1 x23=1 x43=1 x13=1 x23=1 x33=1 D≥21 D≥25 D≥13 D≥14 D≥18 D≥10 x12=1 x22=1 D=12 D=16 41© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa 166 Bài toán tổng quát về xác định trình tự chạy máy l n công việc cần được gia công trên một thiết bị l Yêu cầu về trình tự gia công đối với một số việc l Yêu cầu về thời điểm bắt đầu gia công đối với một số việc l Thời gian cần để gia công việc i là ai l Thời hạn cần hoàn thành việc i là di l 1. Phải thực hiện các việc trên theo thứ tự nào để đảm bảo thời hạn hoàn thành của các việc, và trong thời gian ngắn nhất ? l 2. Một số việc được phép hoàn thành trễ hạn. Phải thực hiện các việc trên theo trình tự nào để tổng thời gian trễ hạn là thấp nhất ? Mô hình hóa 167 Ví dụ 5.3. Bài toán Set-covering l Bài toán trong đó các phần tử của một tập hợp A (Set A) phải được “phục vụ” (covered) bởi ít nhất một phần tử thuộc một tập hợp B khác (Set 2). Mục tiêu của bài toán là tối thiểu hóa số lượng phần tử B cần dùng để phục vụ được tất cả các phần tử A. l Bài toán loại này được ứng dụng trong nhiều lĩnh vực, chẳng hạn lập kế hoạch điều động phi hành đoàn / chuyến bay, điều động xe (routing), thiết lập mạng lưới đại lý, v.v. Mô hình hóa 168 Bài toán Set-covering l Thành phố A cần xác định số điểm tối thiểu để xây dựng các trạm cấp cứu tại trung tâm các quận để đảm bảo phục vụ tất cả các quận trong vòng 15’ kể từ khi có yêu cầu. Khoảng cách chạy xe giữa các quận như trong bảng. Hãy xác định số trạm cấp cứu cần xây và địa điểm đặt chúng. 1 2 3 4 5 6 1 0 10 20 30 30 20 2 0 25 35 20 10 3 0 15 30 20 4 0 15 25 5 0 14 6 0 Mô hình hóa 169 Bài toán Set-covering l Gợi ý đặt biến xi =1 nếu đặt trạm tại quận i = 0 nếu không đặt l Hàm mục tiêu: Min z = ? l Ràng buộc đảm bảo có ít nhất một trạm trong vòng 15’ chạy xe từ mỗi quận: ? 42© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa 170 Ví dụ 5.4. Bài toán Chi phí cố định l Một sản phẩm có thể được sản xuất trên 4 cỗ máy khác nhau. Mỗi máy có chi phí khởi động (cố định), chi phí gia công (biến đổi theo sản phẩm), và công suất tối đa như trong bảng. Cần phải SX tổng cộng 2000 đơn vị sản phẩm. Hỏi bố trí sản xuất thế nào để giảm thiểu chi phí. Máy Chi phí khởi động Fi Chi phí gia công Vi Công suất Pi 1 1000 20 900 2 920 24 1000 3 800 16 1200 4 700 28 1600 Mô hình hóa 171 Bài toán Chi phí cố định l Đặt xi = số SP làm bằng máy i l Hàm mục tiêu: min tổng chi phí cđịnh + bđổi: min z =  Fi * yi +  Vi*xi l Ràng buộc: – xi <= Pi max (CS tối đa) –  Xi = 2000 (đáp ứng nhu cầu) – Nếu xi >0 thì có chi phí cố định (yi=1) – xi nguyên, không âm – yi = 0 , 1 Nhiều bài toán logistic và sản xuất có thể mô hình hóa dưới dạng bài toán biến nguyên chi phí cố định Mô hình hóa 172 Điều kiện Nếu-Thì l Ta có thể biểu diễn quan hệ này bằng cách đưa vào biến nhị phân y và thể hiện bằng cặp 2 ràng buộc: f(xi) ≤ M.y, -g(xi) ≤ M(1-y), y = 0 hoặc 1 l Nếu ràng buộc f(xi) > 0 thỏa mãn thì ràng buộc g(xi) ≥ 0 cũng phải thỏa mãn l Ngược lại, nếu ràng buộc f(xi) > 0 không thỏa mãn thì ràng buộc g(xi) ≥ 0 có thể không thỏa mãn Mô hình hóa 173 Ví dụ 5.5. Bài toán kế hoạch SX l Cty Dorian sản xuất 3 loại ôtô: cỡ nhỏ-trung-lớn. Các nguồn lực cần thiết và lợi nhuận tương ứng khi SX xe mỗi loại như trong bảng. Hiện tại Cty có thể huy động 6000 tấn thép & 60.000 h lao động. Để SX 1 loại xe nhất định đạt hiệu quả kinh tế thì phải làm tối thiểu 1000 chiếc. Lập mô hình IP để giải bài toán. Cỡ nhỏ Cỡ trung Cỡ lớn Thép 1,5 tấn 3 tấn 5 tấn Lao động 30 h 25 h 40 h Lãi $2000 $3000 $4000 43© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa 174 Bài toán kế hoạch SX l Gọi lượng xe mỗi loại sẽ SX là xi l Hàm mục tiêu (1000 $): max z=2x1+3x2+4x3 l Ràng buộc về nguyên liệu thép: 1.5x1+3x2+5x3≤ 6000 l Ràng buộc về giờ lao động: 30x1+25x2+40x3≤ 60000 l Ràng buộc về lượng xe SX cỡ nhỏ: x1≤ 0 hoặc x1≥ 1000 l Ràng buộc về lượng xe SX cỡ trung: x2≤ 0 hoặc x2≥ 1000 l Ràng buộc về lượng xe SX cỡ lớn: x3≤ 0 hoặc x3≥ 1000 Mô hình hóa 175 Điều kiện Hoặc-Hoặc l Ta có thể biểu diễn quan hệ này bằng cách đưa vào biến nhị phân y và thể hiện bằng cặp 2 ràng buộc: f(xi) ≤ M.y, g(xi) ≤ M(1-y), y = 0 hoặc 1 l Hoặc ràng buộc f(xi) ≤ 0 phải thỏa mãn hoặc ràng buộc g(xi) ≤ 0 phải thỏa mãn Mô hình hóa 177 Ví dụ 5.6. Bài toán Knap-sack l NASA cần xác định trong 3 loại đồ vật cần mang lên tàu vũ trụ nên mang bao nhiêu chiếc mỗi loại. Trọng lượng và lợi ích của đồ vật nêu trong bảng. Được phép mang lên tàu tối đa 26 kg đồ vật. Nên mang những vật nào để có lợi nhất? Đồ vật Lợi ích Trọng lượng 1 10 3 2 15 4 3 17 5 Mô hình hóa 178 Biến thể của Bài toán Knap-sack l Knap-Sack (Xếp đồ vào túi) đơn (single dimension) là bài toán IP có dạng: – Max z =  ci xi – Thmãn: ai xi ≤ bi – xi nguyên l Knap-Sack đa chiều là bài toán có nhiều hơn một ràng buộc, chẳng hạn ràng buộc về thể tích của các vật. l Knap-Sack 0-1 (nhị phân) là bài toán trong đó mỗi biến chỉ được nhận giá trị 0 hoặc 1 (mỗi đồ vật chỉ được lấy 1 chiếc) l Giải bằng phương pháp Branch & Bound hoặc Dynamic Programming 44© TS Đặng Vũ Tùng – trường ĐH Bách Khoa Hà Nội Mô hình hóa 179 Ví dụ 5.7. Bài toán người giao hàng (TSP) l Một người xuất phát tại 1 điểm cần đi thăm n điểm khác nhau trước khi quay về điểm xuất phát. Anh ta phải đi theo trình tự nào để giảm thiểu tổng khoảng cách cần đi. l Số phương án có thể: n! l Giải bằng B&B l Giải bằng Heuristics: lân cận gần nhất (nearest neighbor); chèn rẻ nhất (cheapest insertion) Mô hình hóa 180 Các thuật toán Heuristic l Khi việc tìm nghiệm tối ưu là không thể / không hiệu quả (vd bài toán TSP) l Khi sai số nằm trong giới hạn chấp nhận được (vd mô hình EOQ) l Khi yêu cầu cần nhanh chóng xác định phương án đủ “tốt” l => Sử dụng giải thuật xây dựng riêng cho bài toán (mỗi giải thuật có chất lượng nghiệm khác nhau) Mô hình hóa 181 Bài tập ứng dụng Mô hình hóa – TS Đặng Vũ Tùng – ĐH Bách Khoa Hà Nội 182 KẾT THÚC