- Phương pháp Hungary là gì?
- Bước 1: Trừ cực tiểu của mỗi hàng
- Bước 2: Trừ số tối thiểu cho mỗi cột
- Bước 3: bao gồm tất cả các số không với số dòng tối thiểu
- Bước 4: Tạo thêm các số 0
- Phân bổ tối ưu
- Thí dụ
- Bước 1: Trừ cực tiểu của mỗi hàng
- Bước 2: Trừ số tối thiểu cho mỗi cột
- Bước 3: bao gồm tất cả các số không với số dòng tối thiểu
- Bước 4: Tạo thêm các số 0
- Bước 3 (lặp lại)
- Phân bổ tối ưu
- Người giới thiệu
Các phương pháp Hungary là một thuật toán được sử dụng trong vấn đề phân bổ khi bạn muốn giảm thiểu chi phí. Đó là, nó được sử dụng để tìm chi phí tối thiểu bằng cách chỉ định nhiều người vào các hoạt động khác nhau dựa trên chi phí ít nhất. Mỗi hoạt động phải được giao cho một người khác nhau.
Bài toán phân bổ là một dạng bài toán lập trình tuyến tính đặc biệt, trong đó mục tiêu là giảm thiểu chi phí hoặc thời gian hoàn thành một số công việc của nhiều người.
Nguồn: pixabay.com
Một trong những đặc điểm quan trọng của bài toán phân bổ là chỉ một công việc (hoặc công nhân) được giao cho một máy (hoặc dự án).
Phương pháp này được phát triển bởi nhà toán học Hungary D. Konig. Vì lý do này, nó được gọi là phương pháp Hungary cho các bài toán phân công. Nó còn được gọi là thuật toán phân bổ Kuhn-Munkres.
Mọi vấn đề phân bổ đều có thể được giải quyết dễ dàng bằng cách áp dụng phương pháp này bao gồm hai giai đoạn:
- Với giai đoạn đầu tiên thực hiện giảm hàng và giảm cột.
- Trong giai đoạn thứ hai, giải pháp được tối ưu hóa trên cơ sở lặp lại.
Phương pháp Hungary là gì?
Phương pháp Hungary bao gồm bốn bước. Hai bước đầu tiên chỉ được thực hiện một lần, trong khi bước 3 và 4 được lặp lại cho đến khi tìm thấy phân bổ tối ưu.
Ma trận vuông bậc n x được coi là dữ liệu đầu vào, chỉ được chứa các phần tử không âm.
Đối với một bài toán đã cho, nếu số hàng trong ma trận không bằng số cột thì tùy trường hợp phải thêm hàng giả hoặc cột giả. Chi phí phân bổ cho các ô giả đó luôn được phân bổ bằng 0.
Bước 1: Trừ cực tiểu của mỗi hàng
Đối với mỗi hàng trong mảng, phần tử có giá trị thấp nhất được chọn và trừ từng phần tử trong hàng đó.
Bước 2: Trừ số tối thiểu cho mỗi cột
Tương tự như vậy, mục có giá trị thấp nhất được chọn cho từng cột và được trừ cho từng mục trong cột đó.
Bước 3: bao gồm tất cả các số không với số dòng tối thiểu
Tất cả các số không trong ma trận kết quả từ bước 2 phải được bao phủ bằng cách sử dụng số lượng đường ngang và dọc tối thiểu, theo hàng hoặc cột.
Nếu tổng số n dòng được yêu cầu để bao gồm tất cả các số không, trong đó n bằng kích thước n nhân với n của ma trận, một phân bổ tối ưu giữa các số không sẽ thu được và do đó thuật toán dừng lại.
Ngược lại, nếu cần ít hơn n dòng để bao gồm tất cả các số không trong mảng, hãy chuyển sang bước 4.
Bước 4: Tạo thêm các số 0
Phần tử nhỏ nhất của ma trận (gọi là k) không bị che bởi một trong các dòng ở bước 3 sẽ được chọn.
Giá trị của k được trừ cho tất cả các phần tử không được bao phủ bởi các dòng. Sau đó, giá trị của ka được thêm vào tất cả các phần tử được bao phủ bởi giao điểm của hai đường.
Các mục được bao phủ bởi một dòng sẽ được giữ nguyên. Sau khi thực hiện bước này, bạn quay lại bước 3.
Phân bổ tối ưu
Sau khi thuật toán dừng ở bước 3, một tập hợp các số không được chọn sao cho mỗi hàng và mỗi cột chỉ có một số không được chọn.
Nếu trong quá trình lựa chọn này không có số 0 nào trong một hàng hoặc cột, thì một trong các số không đó sẽ được chọn. Các số không còn lại trong cột hoặc hàng đó sẽ bị xóa, lặp lại tương tự cho các bài tập khác.
Nếu không có phép gán 0 duy nhất, thì có nhiều giải pháp. Tuy nhiên, chi phí sẽ không đổi cho các nhóm nhiệm vụ khác nhau.
Mọi hàng hoặc cột giả đã được thêm vào sẽ bị xóa. Do đó, các số không được chọn trong ma trận cuối cùng này tương ứng với phép gán lý tưởng được yêu cầu trong ma trận ban đầu.
Thí dụ
Hãy xem xét một công ty có bốn hoạt động (A1, A2, A3, A4) phải được thực hiện bởi bốn công nhân (T1, T2, T3, T4). Một hoạt động phải được chỉ định cho mỗi công nhân.
Ma trận sau đây cho thấy chi phí của việc chỉ định một công nhân nhất định cho một hoạt động nhất định. Mục tiêu là giảm thiểu tổng chi phí của nhiệm vụ được tạo thành từ bốn hoạt động này.
Bước 1: Trừ cực tiểu của mỗi hàng
Bạn bắt đầu bằng cách trừ phần tử có giá trị nhỏ nhất trong mỗi hàng với các phần tử khác trong hàng đó. Ví dụ, phần tử nhỏ nhất trong hàng đầu tiên là 69. Do đó, 69 được trừ cho mỗi phần tử trong hàng đầu tiên. Ma trận kết quả là:
Bước 2: Trừ số tối thiểu cho mỗi cột
Theo cách tương tự, phần tử có giá trị nhỏ nhất của mỗi cột được trừ cho các phần tử khác của cột đó, thu được ma trận sau:
Bước 3: bao gồm tất cả các số không với số dòng tối thiểu
Bây giờ chúng ta sẽ xác định số dòng tối thiểu (ngang hoặc dọc) được yêu cầu để bao gồm tất cả các số không trong ma trận. Tất cả các số không có thể được che bằng 3 dòng:
Vì số dòng yêu cầu là ba và nó nhỏ hơn kích thước của ma trận (n = 4), chúng ta tiếp tục với bước 4.
Bước 4: Tạo thêm các số 0
Phần tử nhỏ nhất không bị che bởi các dòng được chọn, có giá trị là 6. Giá trị này được trừ cho tất cả các phần tử không bị che và cùng một giá trị này được cộng vào tất cả các phần tử nằm trong giao điểm của hai dòng. Điều này dẫn đến ma trận sau:
Như đã chỉ ra trong phương pháp Hungary, bước ba phải được thực hiện lại.
Bước 3 (lặp lại)
Một lần nữa số dòng tối thiểu cần thiết để bao gồm tất cả các số không trong ma trận được xác định. Lần này cần có bốn dòng:
Vì số dòng yêu cầu là 4, bằng với kích thước của ma trận (n = 4), chúng ta có một phân bổ tối ưu giữa các số không trong ma trận. Do đó, thuật toán dừng lại.
Phân bổ tối ưu
Như phương pháp chỉ ra, lựa chọn được thực hiện bởi các số không sau tương ứng với một phép gán tối ưu:
Lựa chọn số không này tương ứng với phân bổ tối ưu sau đây trong ma trận chi phí gốc:
Do đó, công nhân 1 phải thực hiện hoạt động 3, công nhân 2, hoạt động 2, công nhân 3, hoạt động 1 và công nhân 4 phải thực hiện hoạt động 4. Tổng chi phí của nhiệm vụ tối ưu này là 69 + 37 + 11 + 23 = 140.
Người giới thiệu
- Thuật toán Hungary (2019). Thuật toán Hungary. Lấy từ: hungarianalgorithm.com.
- Nghiên cứu (2019). Sử dụng thuật toán Hungary để giải quyết các vấn đề về Bài tập. Lấy từ: study.com.
- Việc làm khôn ngoan (2018). Phương pháp Hungary để giải quyết vấn đề công việc - Kỹ thuật định lượng để quản lý. Lấy từ: Wisdomjobs.com.
- Geeks cho Geeks (2019). Thuật toán Hungary cho bài toán phân công. Lấy từ: geeksforgeeks.org.
- Karleigh Moore, Nathan Landman (2019). Thuật toán đối sánh tối đa của Hungary. Xuất sắc. Lấy từ: glow.org.