Bài toán phân công hỏi: có n người và n việc, biết chi phí hoặc thời gian khi mỗi người làm mỗi việc, cần ghép mỗi người với đúng một việc sao cho tổng chi phí nhỏ nhất. Nó xuất hiện khi chia ca trực, giao đơn hàng cho tài xế, xếp giảng viên vào lớp, ghép máy với lô sản xuất. Số cách ghép là n giai thừa: với 10 người đã là hơn 3,6 triệu cách, nên thử hết không phải lựa chọn khi n lớn.
Bài này cho thấy vì sao cách chọn "ai làm nhanh nhất thì giao trước" có thể cho kết quả kém, rồi đi qua thuật toán Hungary bằng một ví dụ 3 người 3 việc tính tay đầy đủ, có cả bước điều chỉnh mà nhiều tài liệu bỏ qua. Phần cuối nói về các biến thể và cách dùng AI để giải mà không mất khả năng tự kiểm.
Cái bẫy của cách chọn tham lam
Ví dụ giả định: một xưởng in nhỏ có ba người là An, Bình, Chi và ba việc cần làm trong buổi sáng là việc 1, việc 2, việc 3. Thời gian (giờ) mỗi người làm mỗi việc như sau. An: 7, 4, 6. Bình: 5, 3, 8. Chi: 6, 5, 5. Mỗi người nhận đúng một việc, cần tổng thời gian nhỏ nhất.
Cách làm theo trực giác: tìm ô nhỏ nhất trong cả bảng, đó là Bình làm việc 2 hết 3 giờ, giao luôn. Còn An và Chi với việc 1 và việc 3; ô nhỏ nhất còn lại là Chi làm việc 3 hết 5 giờ; An nhận việc 1 hết 7 giờ. Tổng 3 cộng 5 cộng 7 bằng 15 giờ. Nghe hợp lý, vì ai cũng được giao việc họ làm khá nhanh.
Nhưng có phương án tốt hơn: An làm việc 2 (4 giờ), Bình làm việc 1 (5 giờ), Chi làm việc 3 (5 giờ), tổng 14 giờ. Bình không còn được làm việc mình nhanh nhất, nhưng việc 2 vẫn được người khá nhanh là An làm, còn việc 1, việc khiến An chậm nhất, được chuyển cho Bình. Cách tham lam chỉ nhìn từng ô một, không thấy được cái giá mà một lựa chọn sớm áp lên những người còn lại.
Với ba người, bạn kiểm được hết sáu cách ghép trong vài phút và thấy 14 là nhỏ nhất. Với hai mươi người thì không. Thuật toán Hungary giải được bài toán này với khối lượng tính tăng theo khoảng n mũ 3, thay vì n giai thừa.
Ý tưởng chính: trừ đi một hằng số không làm đổi đáp án
Nếu bạn trừ cùng một số khỏi mọi ô trong một hàng của bảng chi phí, mọi cách ghép đều giảm đúng số đó, vì mỗi cách ghép dùng đúng một ô của hàng đó. Thứ tự tốt xấu giữa các cách ghép không đổi, nên đáp án tối ưu cũng không đổi. Điều tương tự đúng với cột.
Thuật toán Hungary khai thác điều này: liên tục trừ các hằng số khỏi hàng và cột để tạo ra càng nhiều số 0 càng tốt, trong khi mọi ô vẫn không âm. Khi tìm được n số 0 nằm ở n hàng khác nhau và n cột khác nhau, cách ghép theo các số 0 đó có tổng chi phí rút gọn bằng 0, và vì không ô nào âm, không cách ghép nào làm tốt hơn. Đó là đáp án.
Thuật toán được Harold Kuhn công bố năm 1955, đặt tên Hungary để ghi nhận công trình trước đó của hai nhà toán học Hungary là Dénes Kőnig và Jenő Egerváry. Định lý Kőnig cũng là cơ sở cho bước kiểm trong thuật toán: số đường thẳng (hàng hoặc cột) ít nhất cần để phủ hết các số 0 bằng số số 0 độc lập nhiều nhất có thể chọn, tức là chọn được bao nhiêu số 0 không chung hàng, không chung cột.
Tính tay ví dụ 3x3 từng bước
Áp dụng cho bảng của xưởng in. Ghi bảng theo hàng An, Bình, Chi và cột việc 1, việc 2, việc 3.
- Trừ theo hàng. Trừ số nhỏ nhất của mỗi hàng: An trừ 4 được 3, 0, 2; Bình trừ 3 được 2, 0, 5; Chi trừ 5 được 1, 0, 0.
- Trừ theo cột. Cột 1 nhỏ nhất là 1, trừ đi được 2, 1, 0. Cột 2 và cột 3 đã có số 0 nên giữ nguyên. Bảng mới: An 2, 0, 2; Bình 1, 0, 5; Chi 0, 0, 0.
- Phủ số 0 bằng ít đường nhất. Các số 0 nằm ở An–việc 2, Bình–việc 2 và cả hàng Chi. Phủ bằng cột 2 và hàng Chi là đủ: chỉ 2 đường, ít hơn 3, nên chưa ghép được.
- Điều chỉnh. Tìm số nhỏ nhất trong các ô chưa bị phủ: đó là các ô An–1 (2), An–3 (2), Bình–1 (1), Bình–3 (5), nhỏ nhất là 1. Trừ 1 khỏi mọi ô chưa phủ, cộng 1 vào ô nằm ở giao của hai đường (Chi–việc 2). Bảng mới: An 1, 0, 1; Bình 0, 0, 4; Chi 0, 1, 0.
- Phủ lại. Giờ cần 3 đường mới phủ hết số 0, bằng n, nên ghép được.
- Chọn số 0 độc lập. Hàng An chỉ có một số 0 ở việc 2, chọn nó. Cột 2 đã dùng, hàng Bình còn số 0 ở việc 1, chọn. Hàng Chi còn số 0 ở việc 3, chọn. Đáp án: An–việc 2, Bình–việc 1, Chi–việc 3, tổng thời gian theo bảng gốc 4 cộng 5 cộng 5 bằng 14 giờ.
Kiểm chéo: tổng các số đã trừ ở bước 1 và 2 là 4 cộng 3 cộng 5 cộng 1 bằng 13, bước điều chỉnh làm tổng tăng thêm số được trừ nhân với (n trừ số đường phủ), ở đây 1 nhân (3 trừ 2) bằng 1, ra 14, khớp với đáp án. Phép kiểm này rất đáng làm khi giải tay bảng lớn, vì nó bắt được lỗi cộng trừ ngay lập tức.
Các biến thể thường gặp
Tìm lớn nhất thay vì nhỏ nhất. Nếu bảng là mức hiệu quả hay điểm phù hợp, cần tổng lớn nhất, thì lấy số lớn nhất trong bảng trừ đi từng ô để đổi thành bài tìm nhỏ nhất, hoặc đổi dấu toàn bộ bảng rồi giải như thường.
Số người khác số việc. Thêm hàng giả hoặc cột giả với chi phí 0 để bảng thành vuông. Người được ghép với việc giả là người không nhận việc; việc được ghép với người giả là việc bỏ lại. Nếu bỏ việc có thiệt hại, đặt chi phí của cột giả bằng mức thiệt hại đó.
Ghép bị cấm. Người chưa có chứng chỉ không được vận hành máy nào đó: đặt chi phí ô đó bằng một số rất lớn, thuật toán sẽ tránh.
Một người nhận nhiều việc. Nếu một người được nhận tối đa hai việc, nhân đôi hàng của người đó. Khi ràng buộc phức tạp hơn, như giới hạn tổng giờ làm, bài toán vượt khỏi khuôn phân công và cần quy hoạch nguyên.
Liên hệ với bài toán vận tải. Phân công chính là bài toán vận tải trong đó mỗi kho có 1 đơn vị và mỗi điểm nhận cần 1 đơn vị. Cũng có thể giải bằng quy hoạch tuyến tính, và nhờ cấu trúc đặc biệt, nghiệm vẫn ra số nguyên 0 hoặc 1.
Ở đâu gặp bài toán phân công và mô hình dừng ở đâu
Ngoài xưởng sản xuất, khuôn phân công xuất hiện ở nhiều chỗ ít ai gọi tên. Một trung tâm điều phối giao hàng ghép đơn với tài xế đang rảnh sao cho tổng quãng đường chạy không tải nhỏ nhất. Một khoa trong trường đại học xếp giảng viên vào các lớp học phần sao cho mức phù hợp chuyên môn cao nhất. Một bệnh viện ghép ca trực với nhân viên theo mức độ bận của từng người. Trong lĩnh vực thị giác máy tính, khi theo dõi nhiều vật thể qua các khung hình video, việc ghép vật thể ở khung trước với vật thể ở khung sau cũng thường được giải bằng thuật toán Hungary trên bảng khoảng cách.
Điểm chung của các ứng dụng đó là mỗi bên chỉ được ghép với đúng một bên kia, và cái giá của mỗi cặp ghép độc lập với các cặp khác. Khi điều kiện thứ hai không còn đúng, chẳng hạn hai người làm cùng ca thì năng suất cả hai tăng lên vì hỗ trợ nhau, bài toán trở thành dạng bậc hai hoặc dạng có ràng buộc phụ, khó hơn rất nhiều và thường phải giải gần đúng.
Một giới hạn nữa là bảng chi phí chỉ tốt bằng dữ liệu đưa vào. Nếu thời gian làm việc của từng người được ước lượng qua loa, đáp án tối ưu theo bảng có thể không tốt hơn cách xếp theo kinh nghiệm. Trước khi chạy thuật toán, đáng bỏ công đo lại những ô có ảnh hưởng lớn, tức những ô nằm trong đáp án và những ô có giá trị rút gọn gần 0 ở bảng cuối.
Dùng AI để giải mà vẫn tự kiểm được
Chatbot thường biết thuật toán Hungary, nhưng khi tự tính trên bảng 5x5 trở lên rất hay nhầm ở bước phủ số 0 bằng ít đường nhất, hoặc trừ nhầm một ô khi điều chỉnh. Lỗi kiểu này khó thấy vì phần trình bày nghe rất đúng quy trình. Câu lệnh mẫu: "Giải bài toán phân công nhỏ nhất với bảng sau bằng thuật toán Hungary. In bảng sau mỗi bước, ghi rõ đường phủ và số dùng để điều chỉnh. Cuối cùng tính tổng chi phí theo bảng gốc và so với tổng các số đã trừ."
Ba phép kiểm bạn nên tự làm. Một: mỗi hàng và mỗi cột có đúng một ô được chọn. Hai: tổng chi phí tính lại từ bảng gốc khớp với con số chatbot đưa. Ba: so với một trình giải độc lập, chẳng hạn trình giải tối ưu trong bảng tính đặt biến 0–1 cho mỗi ô, hoặc thư viện tối ưu trong một ngôn ngữ lập trình nếu bạn biết dùng.
Khi bảng chi phí là dữ liệu nhân sự thật, như năng suất từng nhân viên hay đánh giá năng lực, hãy thay tên bằng ký hiệu trước khi đưa vào bất kỳ chatbot nào. Và nhớ rằng mô hình chỉ thấy con số; nguyện vọng, sức khoẻ, sự công bằng trong phân việc là những thứ người quản lý phải tự cân nhắc thêm, không phải phần thừa của bài toán.
Câu hỏi thường gặp
Thuật toán Hungary có luôn cho đáp án tối ưu không?
Có, với bài toán phân công chuẩn có bảng chi phí vuông và hữu hạn. Thuật toán dừng khi tìm được n số 0 độc lập, và lúc đó tổng chi phí là nhỏ nhất. Nếu bảng không vuông, cần thêm hàng hoặc cột giả trước.
Vì sao chọn ô nhỏ nhất trước lại có thể sai?
Vì giao một việc cho người làm nhanh nhất có thể buộc những người còn lại nhận việc họ làm rất chậm. Cách chọn tham lam không tính đến cái giá đó. Ví dụ trong bài cho thấy tham lam ra 15 giờ trong khi tối ưu là 14 giờ.
Bước phủ số 0 bằng ít đường nhất làm thế nào cho đúng?
Với bảng nhỏ có thể thử bằng mắt. Với bảng lớn, sách thường hướng dẫn chọn trước các số 0 độc lập, đánh dấu hàng chưa được ghép, rồi lan dần theo cột và hàng để tìm đường phủ. Số đường phủ ít nhất luôn bằng số số 0 độc lập nhiều nhất.
Có thể giải bài phân công bằng bảng tính không?
Được. Đặt một biến 0 hoặc 1 cho mỗi ô, ràng buộc tổng mỗi hàng và mỗi cột bằng 1, mục tiêu là tổng chi phí nhân biến. Trình giải tối ưu tuyến tính trong bảng tính sẽ trả về nghiệm nguyên nhờ cấu trúc của bài toán.
Bài phân công khác bài toán vận tải ở đâu?
Phân công là trường hợp riêng của bài vận tải, trong đó mỗi nguồn có đúng một đơn vị và mỗi đích cần đúng một đơn vị. Vì quá đặc biệt nên có thuật toán riêng gọn hơn là thuật toán Hungary.
Dùng chatbot để giải bài phân công trong bài tập có được không?
Dùng để học cách làm và kiểm lại bài của mình thì hữu ích. Với bài nộp lấy điểm hoặc bài thi, làm theo quy định của giảng viên và tự trình bày lời giải. Hiểu bước điều chỉnh mới là phần bài tập muốn bạn học.