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

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.
Nội dung trích xuất từ tài liệu:
Bài giảng Tin học trong quản lý xây dựng: Chương 6 - ThS. Đỗ Thị Xuân LanChương 6 Bài ttoánCh áphân côngChương 6 Bài toán phâncô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 ©2010củaĐỗ Thị XuânLan,GVC.Ths.Chương 6BàitoánphâncôngGIỚI THIỆUGIỚITHIỆU ©2010củaĐỗ Thị XuânLan,GVC.Ths. 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ầuCực Cực ….tiểu đạihàm hàmmục Tổng chi mục Tổng tiềntiê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 ©2010củaĐỗ Thị XuânLan,GVC.Ths.Chương 6BàitoánphâncôngTHUẬT TOÁN HUNGARIANTHUẬTTOÁNHUNGARIAN ©2010củaĐỗ Thị XuânLan,GVC.Ths. 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 ©2010củaĐỗ Thị XuânLan,GVC.Ths. 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ử matrậ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” ©2010củaĐỗ đó Thị XuânLan,GVC.Ths.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ó duy2. 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ố ...