intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Star Star | Ngày: | Loại File: PDF | Số trang:58

Thêm vào BST
Báo xấu
99
lượt xem 10
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương 6: Bài toán phân công. Nội dung chương gồm có: 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 phân công giải bằng thuật toán vận tải, bài toán phân công giải bằng quy hoạch tuyến tính, bài toán người bán hàng rong.

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 Tin học trong quản lý xây dựng: Chương 6 - ThS. Đỗ Thị Xuân Lan

  1. Chương 6 Bài ttoán Ch á phân công
  2. Chương 6 Bài toán phân công ô • Thuậtậ toán Hungarian g • 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 ttoán á phân hâ công ô giảiiải bằ bằng thuật th ật toán t á vận tải • Bài toán phân công giải bằng quy hoạch tuyến tính g • Bài toán người bán hàng g rong g ©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 GIỚI THIỆU ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  4. Giới thiệu ố nhân sự cho dự án Phân bố Phân công Phâ ô cán á bộ giám iá sá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 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í ề lời hay số (giờ công/ tiền ố lượng sản phẩm) ẩ Bộ ộpphận ậ đượcợ Đối tượng ợ g cần được ợ thực ự hiện ệ phân công 1 2 … 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ựa trên tính chất rút giảm ma trận. Khi trừ đi hay cộng thêm các giá trị thích hợp vào các phần tử ma trận chi phí ta sẽ có một ma trận chi phí cơ hội. Chi phí cơ hội là giá trị thiệt hại khi có sự phân công chưa phải là tối ưu nhấ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ột thì có thể đạt được sự phân công tối ưu vào các ô có giá trị không “0” ©2010 của Đỗ đó 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ò cho dòng h giá iá trị t ị chi hi phí hí nhỏ hỏ nhất hất trong t dòng dò ấyấ Trừ giá trị chi phí của mọi phần tử trong mỗi Thực hiện sự 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ột có duy 2. Kiểm tra điều kiện tối ưu nhất một giá 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ại bỏ dòng và cột đường thẳng ít có chứa số “0” 0 đã hơn số dòng/cột phân phối và tiếp tục trở lại tìm kiếm YES các dòng và cột có 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ện sự 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 ấy 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ười thợ được phân công làm 4 việc. Tiền công để làm xong từng việc của mỗi người 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ủa mọi phần tử trong mỗi dòng cho giá trị nhỏ nhất trong dòng ấy Trừ g giá trị của mọi p phần tử trongg 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) (ngàn đồ ) 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 4 3 0 6 A2 10 9 10 8 A2 2 1 2 0 A3 14 8 7 11 A3 7 1 0 4 A4 6 8 10 9 A4 0 2 4 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ò cho dòng h giá iá ttrịị nhỏ hỏ nhất hất trong t dòng dò ấ ấ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) (ngàn đồ ) Công Việc Công Việc nhân hâ B1 B2 B3 B4 nhân hâ B1 B2 B3 B4 A1 4 3 0 6 A1 4 2 0 6 A2 2 1 2 0 A2 2 0 2 0 A3 7 1 0 4 A3 7 0 0 4 A4 0 2 4 3 A4 0 1 4 3 ©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ò h dòng hay cột ột đi qua mọii số ố khô không (“0”) của bảng Công Việc nhân B1 B2 B3 B4 Thoả mãn A1 4 2 0 6 điều kiện tối ưu A2 2 0 2 0 A3 7 0 0 4 A4 0 1 4 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” 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ối và tiếp p p tục trở lại tìm kiếm các dòng g 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 4 2 0 6 A1 8 A2 2 0 2 0 A2 8 A3 7 0 0 4 A3 8 A4 0 1 4 3 A4 6 Tổng chi phí: 30.000 đ ©2010 của Đỗ Thị Xuân Lan , 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ền An Hòa A An 11 14 6 Dư 8 10 11 Kỳ 9 12 7 ©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àn dòng ( à đồ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 5 8 0 Dư 8 10 11 Dư 0 2 3 Kỳ 9 12 7 Kỳ 2 5 0 ©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ủ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 cột ( à đồng) (ngàn đồ ) 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 5 8 0 An 5 6 0 Dư 0 2 3 Dư 0 0 3 Kỳ 2 5 0 Kỳ 2 3 0 ©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 đườngg thẳng g 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 5 6 0 Dư 0 0 3 Kỳ 2 3 0 ©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ất chưa nằm 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 h iđ hai đường ờ thẳ thẳng. Dự án Dự án Kỹ An An An Kỹ sư An An An sư Cư Điền Hòa Cư Điền Hòa An 5 6 0 An 3 4 0 Dư 0 0 3 Dư 0 0 5 Kỳ 2 3 0 Kỳ 0 1 0 ©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 dò hayh cộtột đi qua mọii số ố không khô (“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 3 4 0 Dư 0 0 5 Kỳ 0 1 0 ©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” 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 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ư 0 0 5 Dư 10 Kỳ 0 1 0 Kỳ 9 Tổng chi phí: 25.000 $ ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.15: Bộ Đồ Án Tốt Nghiệp Chuyên Ngành Cơ Khí
65 tài liệu
2431 lượt tải
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

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