›
›

Bài giảng Tin học trong quản lý xây dựng - Chương 6: Bài toán phân công - Đỗ Thị Xuân Lan

pdf 58 trang ngocly 2390
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Tin học trong quản lý xây dựng - Chương 6: Bài toán phân công - Đỗ Thị Xuân Lan", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_tin_hoc_trong_quan_ly_xay_dung_chuong_6_bai_toan_p.pdf

Nội dung text: Bài giảng Tin học trong quản lý xây dựng - Chương 6: Bài toán phân công - Đỗ Thị Xuân Lan

  1. Chương 6Bàit6 Bài to án phân công
  2. Chương 6 Bài toán phân công •Thuật toán Hungarian • Bài toán phân công khi có số dòng và số cột khác nhau • Bài toán phân công cực đại hàm mục tiêu • Bài to án p hân c ông g iảibi bằng thuậttt toá n vận tải • Bài toán phân công giảiib bằng quy hoạch tuyến tính • Bài toán người bán hànggg rong ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  3. Chương 6 Bài toán phân công GIỚI THIỆU ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  4. Giới thiệu Phân bố nhân sự cho dự án Phâncông cán bộ giámsát đến từng công trường Giao hợp đồng cho các nhà thầu Cực Cực . tiểu đại hàm hàm mục Tổng chi mục Tổng tiền tiêu phí tiêu lời Thời gian Số lượng 1 1 thực hiện sản phẩm công việc làm ra ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  5. Chương 6 Bài toán phân công THUẬT TOÁN HUNGARIAN ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  6. Thuật toán Hungarian Ma trận chi phí (giờ công/ tiền lời hay số lượng sản phẩm) Bộ phận được Đối tượng cần được thực hiện phân công 12 n 1 c11 c12 c1n 2 c21 c22 c2n m cm1 cm2 cmn ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  7. Thuật toán Hungarian Ma trận chi Trường hợp phí hay giờ cực tiểu Thuật toán công có số hàm mục Hungarian dòng bằng tiêu số cột Thuật toán Hungarian: dựatrêntínhchấtrútgiảmmatrận. Khi trừđihaycộng thêm các giá trị thích hợp vào các phầntử ma trận chi phí ta sẽ có mộtmatrận chi phí cơ hội. Chi phí cơ hộilà giá trị thiệthại khi có sự phân công chưaphảilàtối ưunhất. Nếu ta có thể rút giảm ma trận đến khi có các phần tử có giá trị không “0” ở mỗi dòng và cộtthìcóthểđạt đượcsự phân công tối ưu vào các ô có giá trị không©2010 của Đ “0”ỗ Thị Xuânđó Lan , GVC. Ths.
  8. 1. Xác định ma trận chi phí cơ hội Trừ giá trị chi phí của mọi phần tử trong mỗi dòng ch o giá t rị chi phí nh ỏ nhấttt trong dò ng ấy Trừ giá trị chi phí của mọi phần tử trong mỗi Thựchiệnsự phân công cột cho giá trị chi phí nhỏ nhất trong cột ấy tối ưu Kiểm tra các dòng và các cộtcóduy 2. Kiểm tra điều kiện tối ưu nhấtmộtgiátrị Vẽ một số tối thiểu các đường thẳng trên dòng không “0”. Thực hay cột đi qua mọi số không (“0”) của bảng hiện sự phân công cho các ô đó Nếu như số NO Loạibỏ dòng và cột đường th ẳng ít có chứa số “0” đã hơn số dòng/cột phân phốivàtiếp tụctrở lạitìmkiếm YES các dòng và cộtcó duy nhất một giá trị 3. Xây dựng ma trận chi phí cơ hội mới không “0” để thực Chọn giá trị nhỏ nhất chưa nằm trên đường thẳng hiệnsự phân công Trừ giá trị chi phí của mọi phần tử không nằm trên các đường th ẳng cho giá tr ị nhỏ nhất ấyvàcy và cộng giá trị nhỏ nhất ấy với giá trị nằm trên giao điểm của hai đường thẳng. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  9. Ví dụ 6.1 Một xưởng gia công cốp pha có 4 ngườithi thợ được phân công làm 4 việc. Tiền công để làm xong từng việccc củama mỗingi ngườithi thợ như trong bảng (1.000 đồng). Đề nghị phân công sao cho tổng chi phí lao động ít nhất? Việc Công nhân B1 B2 B3 B4 A1 12 11 8 14 A2 10 9 10 8 A3 14 8 7 11 A4 6 8 10 9 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  10. 1. Xác định ma trận chi phí cơ hội Trừ giá trị củama mọiphi phầntn tử trong mỗi dòng cho giá trị nhỏ nhất trong dòng ấy Trừ giá trị của mọi phần tử trong mỗi cột cho giá trị nhỏ nhất trong cột ấy Chi phí cơ hội tính theo dòng (à(ngàn đồng) Công Việc Công Việc nhân B1 B2 B3 B4 nhân B1 B2 B3 B4 A1 12 11 8 14 A1 430 6 A2 10 9 10 8 A2 212 0 A3 14 8 7 11 A3 710 4 A4 68109 A4 024 3 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  11. 1. Xác định ma trận chi phí cơ hội Trừ giá trị của mọi phần tử trong mỗi dòng c ho g iá trị nhỏ nhấttt trong dò ng ấy Trừ giá trị của mọi phần tử trong mỗi cột cho giá trị nhỏ nhất trong cột ấy Chi phí cơ hội tính theo cột (à(ngàn đồng) Công Việc Công Việc nhân B1 B2 B3 B4 nhân B1 B2 B3 B4 A1 430 6 A1 4206 A2 212 0 A2 2020 A3 710 4 A3 7004 A4 024 3 A4 0143 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  12. 2. Kiểm tra điều kiện tối ưu Vẽ một số tối thiểu các đường thẳng trên dòng hay cột đi qua mọi số không (“0”) của bảng Công Việc nhân B1 B2 B3 B4 Thoả mãn A1 420 6 điều kiện tối ưu A2 202 0 A3 7 0 0 4 A4 014 3 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  13. 3. Thực hiện sự phân công tối ưu Kiểm tra các dòng và các cột có duy nhất một giá trị không “0”. Thựchic hiện sự phân công cho các ô đó. Loại bỏ dòng và cột có chứa số “0” đã phân phối và tiếp tục trở lại tìm kiếm các dòng và cột có duy nhất một giá trị không “0” để thực hiện sự phân công Công Việc Công Việc nhân B1 B2 B3 B4 nhân B1 B2 B3 B4 A1 420 6 A1 8 A2 2 0 2 0 A2 8 A3 700 4 A3 8 A4 014 3 A4 6 Tổ©2010ng cchiủa Đỗ Th phí:ị Xuân Lan 30.000, GVC. Ths. đ
  14. Ví dụ 6.2 Một công ty xây dựng có 3 kỹ sư được phân công phụ trách 3 dự án. Chi phí để thực hiện từng dự án của mỗi kỹ sư như trong bảng (đơn vị 1000 $) Đề nghị phân công sao cho tổng chi phí ít nhất? Dự án Kỹ sư An Cư An ĐiềnAn Hòa An 11 14 6 Dư 81011 Kỳ 9127 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  15. 1. Xác định ma trận chi phí cơ hội Trừ giá trị của mọi phần tử trong mỗi dòng cho giá trị nhỏ nhất trong dòng ấy Trừ giá trị của mọi phần tử trong mỗi cột cho giá trị nhỏ nhất trong cột ấy Chi phí cơ hội tính theo dòng (à(ngàn đồng) Dự án Dự án Kỹ sư An An An Kỹ sư An An An Cư Điền Hòa Cư Điền Hòa An 11 14 6 An 580 Dư 81011 Dư 023 Kỳ 9127 Kỳ 250 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  16. 1. Xác định ma trận chi phí cơ hội Trừ giá trị củaam mọiiph phầnnt tử trong mỗi dòng cho giá trị nhỏ nhất trong dòng ấy Trừ giá trị củaam mọiiph phầnnt tử trong mỗiic cột cho giá trị nhỏ nhất trong cột ấy Chi phí cơ hội tính theo cột (à(ngàn đồng) Dự án Dự án Kỹ sư An An An Kỹ sư An An An Cư Điền Hòa Cư Điền Hòa An 58 0 An 560 Dư 02 3 Dư 003 Kỳ 25 0 Kỳ 230 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  17. 2. Kiểm tra điều kiện tối ưu Vẽ một số tối thiểu các đường thẳng trên dòng hay cột đi qua mọi số không (“0”) của bảng Dự án Kỹ sư An An An Cư Điền Hòa An 560 Dư 003 Kỳ 230 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  18. 3. Xây dựng ma trận chi phí cơ hội mới Chọn giá trị nhỏ nhấtcht chưana nằmtrênm trên đường thẳng. Trừ giá trị chi phí của mọi phần tử không nằm trên các đường thẳng cho giá trị nhỏ nhất ấy và cộng giá trị nhỏ nhất ấy cho giá trị nằm trên giao điểm của hihai đờđường thẳng. Dự án Dự án Kỹ Kỹ sư sư An An An An An An Cư Điền Hòa Cư Điền Hòa An 560 An 340 Dư 003 Dư 005 Kỳ 230 Kỳ 010 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  19. 2. Kiểm tra điều kiện tối ưu Vẽ một số tối thiểu các đường thẳng trên dòng h ay cột đi qua mọi số không (“0”) của bảng Dự án Kỹ sư An An An Thoả mãn Cư Điền Hòa điều kiện tối ưu An 340 Dư 005 Kỳ 010 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  20. 3. Thực hiện sự phân công tối ưu Kiểm tra các dòng và các cột có duy nhất một giá trị không “0”. Thực hiện sự phân công cho các ô đó. Loại bỏ dòng và cột có chứa số “0” đã phân phốivàtii và tiếppt tụcctr trở lại tìm ki ếm các dòng và cột có duy nhất một giá trị không “0” để thực hiện sự phân công Dự án Dự án Kỹ sư An An An Kỹ sư An An An Cư Điền Hòa Cư Điền Hòa An 3 4 0 An 6 Dư 005 Dư 10 Kỳ 0 1 0 Kỳ 9 Tổng©2010 chi của Đỗ Thphí:ị Xuân Lan 25.000 , GVC. Ths. $
  21. Chương 6. Bài toán phân công BÀI TOÁN PHÂN CÔNG KHI CÓ SỐ DÒNG VÀ SỐ CỘT KHÁC NHAU ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  22. •Thuật tóan Hungari được áp dụng để giải bài toán phân công với điều kiện số dòng và cột của ma trận chi phí phải như nhau nhưng không phải lúc nào số bộ phận được phân công(số người) cũng bằng số việc, số máy cần được làm, vận hành. Trong trường hợp đótaphó ta phải thêm dòng ảo hay cột ảo. • Thêm dònggy hay thêm cột là thêm người ảo hay thêm công việc ảo nên giá trị thời gian hay chi phí thực hiện công việc ở dòng hay cột này bằng 0. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  23. Thêm dòng ảo: Máy Thợ M1 M2 M3 M4 M5 M6 A1 12 7 20 14 8 10 A2 10 14 13 20 9 11 A3 5 3 6 9 7 10 A4 911716910 A5 1061481012 A6 000000 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  24. Chương 6. Bài toán phân công BÀI TOÁN PHÂN CÔNG CỰC ĐẠI HÀM MỤC TIÊU ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  25. • Có 1 số bài toán tìm cực đại tiền lời, số lượng sản phẩm hay hiệu quả công việc thay vì tìm cực tiểu chí phí nên để có thể áp dụng thuật tóan Hungari phải chuyển bài toán về bài toán cực tiểu tương đương bằng cách xây dựng ma trận chi phí cơ hội. •Ma trận chi phí cơ hội có các phần tử được xác định bằng hiệu số của phần tử lớn nhất trong ma trận ban đầuvu vớiphi phầntn tử đang xét. • Sau khi lời giải tối ưu của bài toán tương đương được xác định, tính tổng tiền lời bằng cách cộng các giá trị tiền lời ban đầu ở các ô được phân phối tối ưu. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  26. Ví dụ 6.4: Tiền lời khi phân công mỗi người1i 1 c ông v iệc Công Việc nhân ABCD Anh 20 60 50 55 Bình 60 30 80 75 Can 80 100 90 80 Dân 65 80 75 70 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  27. Bảng ma trận chi phí cơ hội tương đương(à( ngàn đồng) Việc Công nhân ABCD 100- Anh 40 50 45 20=80 Bình 40 70 20 25 Can 20 0 10 20 Dân 35 20 25 30 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  28. Bảng ma trận chi phí theo cột (ngàn đồng) Việc Công nhân A B C D Anh 250100 Bình 55000 Can 5 0 10 15 Dân 0055 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  29. • Phân công công nhân Anh làm công việcDvớitiềnlời 55.000 đồng. • Phân công công nhân Bình làm công việc C với tiền lời 80.000 đồng. • Phân công công nhân Can làm công việc B với tiền lời 100.000 đồng • Phân công công nhân Dân làm công việc A với tiềnlời 65.000 đồng •Tổng tiềnlời là : 55+80+100+65= 300.000 đồng ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  30. Chương 6. Bài toán phân công GIẢI BÀI TOÁN PHÂN CÔNG BẰNG THUẬT TOÁN VẬN TẢI ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  31. • Bài toán phân công là dạng đặc biệt của bài toán vận tải với : •Cácđốitượng thựchiện (công việcphải làm,dự án phảithựchiện, ) tương ứng vớicácđiểmtiêuthụ có nhu cầubằng 1 •Cácbộ phận được phân công(công nhân,ngườilaođộng ) tương ứng với các điểmcung cấp có công suấtlà1. • Chi phí,giờ công thựchiện công việc tương ứng với cướcphí, cự li vận tải. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  32. Ví dụ 6.5 Sáu ngườiith thợ nhận làkhábllàm khoán ba loại sản phẩm,với số lượng sản phẩm làm khoán(chiếc/ngày) nh ư trong bảng. Phân công 2 thợ làm 1 loại sản phẩm sao cho đạt nhiều sản phẩm nhất. Thợ Sảnphẩm S1 S2 S3 T1 8811 T2 5610 T3 10710 T4 969 T5 678 T6 ©2010 của Đỗ Thị8910Xuân Lan , GVC. Ths.
  33. Người Loạisảnphẩm(điểmtiêuthụ) Khả thợ S1 S2 S3 năng (điểm đáp ứng cung cấp) T1 88111 1 T2 5610 1 1 T3 10 7 10 1 1 T4 9691 1 T5 6 781 1 T6 8 9 10 1 1 ủ ỗ ị Nhu cầu 222©2010 c a Đ Th Xuân Lan , GVC. Ths.  = 6
  34. Phân công thợ T1 và Khả năng T2 làm sản phẩm S3 đáp ứng bằng 1 Tổng số ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. sản phẩm
  35. Chương 6. Bài toán phân công GIẢI BÀI TOÁN PHÂN CÔNG BẰNG QHTT ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  36. Cũng có thể giải bài toán phân công ở ví d ụ 665b.5 bằng thu ật toán đơnnhìnhb hình bằng cách đặt ẩn số xij tương ứng với sự phân cônggg người thợ i làm loại sản phẩm j. Thợ Sảnphẩm S1 S2 S3 T1 x11 x12 x13 T2 x21 x22 x23 T3 x31 x32 x33 T4 x41 x42 x43 T5 x51 x52 x53 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. T6 x61 x62 x63
  37. GiẢI BÀI TOÁN PHÂN CÔNG BẰNG QUY HO ẠCH TUYẾNTÍNHN TÍNH • Mô hình toán: – Hàm mục tiêu: MaxZ=8x11+8x12+11x13+5x21+6x22+10x23+10x31+7x32+10x33+ 9x41+6x42+9x43+6x51+7x52+8x53+8x61+9x62+10x63 – Ràng buộc: • Theo đk mỗingười làm 1 sảnphẩm x11+x12+x13 =1; x21+x22+x23 =1; x31+x32+x33 =1; x41+x42+x43 =1; x51+x52+x53 =1; x61+x62+x63 =1 • Theo đk mỗisảnphẩmcần2 ngườithợ x11+x21+x31+x41+x51+x61=2;= 2 ; x12+x22+x32+x42+x52+x62=2= 2 x13+x23+x33+x43+x53+x63= 2 – Điềukiện biên : xij ϵ{0,1} Đáp số: x =1; x =1; x =1; x =1; x =1; x =1;Z = 56 13 23 ©201031 của Đỗ Thị Xuân41 Lan , GVC. Ths.52 62
  38. GIẢI BÀI TOÁN PHÂN CÔNG BẰNG QUY HOẠCH TUYẾN TÍNH ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  39. GIẢI BÀI TOÁN PHÂN CÔNG BẰNG QUY HOẠCH TUYẾN TÍNH ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  40. GiẢI BÀI TOÁN PHÂN CÔNG BẰNG QUY HOẠCH TUYẾN TÍNH Nghiệm của mô hình tóan Giá trị hàm mụcctiêu tiêu ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  41. Chương 6. Bài toán phân công BÀI TOÁN NGƯỜI BÁN HÀNG RONG ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  42. Bài toán người bán hàng rong Heuristic Khép Yes Hungarian/ kín QHTT Tối Finish ưu No Gángiá trị rấtlớncho từng cung đường ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  43. Sơ đồ cung đường 2 160 150 100 300 3 150 260 1 100 300 5 290 240 500 200 4 360 6 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  44. Từ địa điểm Đến địa điểm (công việc) (người được Dùngphân công) Win123456 QSB 1 100 150 300 500 2 100 160 150 300 3 150 160 100 260 290 4 150 100 240 360 5 300 300 260 240 200 6 500 290 360 200 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  45. Kết quả Win QSB Node Node 1 4 100 100 100 Node 100 Node 2 5 Vòng lặp 1 200 200 Node NdNode 3 6 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  46. Từ địa điểm Đe Đến địa điểm (công việc) (người được phân 123456 công) Vòng lặpp1 1 1 100 150 300 500 2 1000 160 150 300 3 150 160 100 260 290 4 150 100 240 360 5 300 300 260 240 200 6 500 290 360 200 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  47. Kết quả vòng lặp 1 Node Node 1 4 150 100 100 Node Node Vòng lặp 2 2 5 200 150 200 Node Node 3 6 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  48. Từ địa điểm Đến địa điểm (công việc) (người được phân công) Vòng lặ123456pp2 2 1 100 150 300 500 2 1000 160 150 300 3 150 160 100 260 290 4 150 100 240 360 5 300 300 260 240 200 6 500 290 360 1000 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  49. Kếtqut quả vòng l ặpp2 2 Node Node 1 4 150 100 240 Node Node 2 5 Vòng lặp 3 150 200 Node 290 Node 3 6 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  50. Từ địa điểm Đến địa điểm (công việc) (người được phân công) Vòng lặ123456p3p 3 1 100 150 300 500 2 1000 160 150 300 3 150 160 100 260 290 4 150 100 240 360 5 300 300 260 240 1000 6 500 290 360 200 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  51. Kếtqut quả Vòng l ặpp3 3 Node Node 1 4 150 100 300 Node 100 Node Vòng lặp 4 2 5 200 Node 290 Node 3 6 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  52. Từ địa điểm Đến địa điểm (công việc) (người được phân công) Vòng lặ123456pp4 4 1 1000 150 300 500 2 100 160 150 300 3 150 160 100 260 290 4 150 100 240 360 5 300 300 260 240 200 6 500 290 360 200 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  53. Kếtqut quả Vòng l ặpp4 4 Node Node 1 4 150 100 Node 150 Node Vòng lặp 5 2 5 100 200 200 Node Node 3 6 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  54. Từ địa điểm Đến địa điểm (công việc) (người được phân công) Vòng lặ123456pp5 5 1 1000 150 300 500 2 100 160 150 300 3 150 160 100 260 290 4 150 100 240 360 5 300 300 260 240 200 6 500 290 360 1000 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  55. Kếtqut quả vòng l ặpp5 5 Node Node 1 4 150 100 100 Node 300 Node Vòng lặp 6 2 5 200 Node 290 Node 3 6 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  56. Từ địa điểm Đến địa điểm (công việc) (người được phân 123456 công) Vòng lặpp6 6 1 1000 150 300 500 2 100 160 150 300 3 150 160 100 260 290 4 150 100 240 360 5 300 300 260 240 1000 6 500 290 360 200 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  57. Kếtqut quả vòng l ặpp6 6 Node Node 1 4 150 100 240 Node Node Finish 2 5 150 200 Node 290 Node 3 6 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  58. Kết luận Node Node Node Node 1 4 1 4 150 100 240 150 100 240 Node Node Node Node 2 5 2 5 ƩL= 1130 m 200 150 150 200 NdNode 290 Node Node 290 Node 3 6 3 6 Vòng lặp 2 Vòng lặp 6 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.