tailieunhanh - Bài giảng quy hoạch toán phần 6

Tham khảo tài liệu 'bài giảng quy hoạch toán phần 6', kinh tế - quản lý, kinh tế học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Trang 52 Bài giảng Quy hoạch toán học 10 45 65 120 25 10 7 9 8 120 4 5 2 3 60 -f 2 6 2 GV Phan Thanh Tao Bài giảng Quy hoạch toán học Trang 53 Chương 5. PHƯƠNG PHÁP HUNGARY Phương Pháp này được nhà toán học Hungary Egervary công bố trong một bài báo năm 1931 16 năm trước khi phương pháp đơn hình của Dantzig ra đời nhưng không ai biết đến cho đến năm 1953 nhà toán học Mỹ Kuhn dịch bài báo và đặt tên là Phương pháp Hungary . . Bài toán bổ nhiệm Cần phân n việc cho n người. Người i làm việc j thì chi phí là cij i j . Hãy phân công việc cho n người để tổng chi phí thấp nhất. Đặt Xịj 1 nếu người i làm việc j ngược lại đặt Xịj 0. Mô hình toán học n n g x 2 2 jj min i 1 j 1 n 2 xij 1 i 1-n j1 2 x 1 j i 1 ĩ 2 . X. 0 hay1 i j Ma trận C cij n n gọi là ma trận chi phí. Thực sự có thể bỏ hạn chế Xij 0 hoặc 1 để thay Xij là số tự nhiên thì mỗi ràng buộc đảm bảo Xij 0 hoặc 1. Do đó ràng buộc Xij 0 hoặc 1 được viết lại là Xij 0 nguyên. Đây là mô hình thực sự của bài toán vân tải. Có thể dùng thuật toán thế vị để giải. Với thuật toán này có 2n-1 ô chọn. Tuy nhiên chỉ có n ô chọn khác 0 vì bài toán suy biến. Vì vậy có thể có nhiều bước lặp mà phương án mới không tốt hơn. Rõ ràng mỗi phương án là một hoán vị của các số . Ví dụ hoán vị 4 2 1 3 nghĩa là người 1 làm việc 4 người 2 làm việc 2 người 3 làm việc 1 và người 4 làm việc 3. Một cách viết hoán vị dạng ma trận M mij nxn với mij 1 khi và chỉ khi người i làm việc j. Định lý . Nếu ma trận chi phí của bài toán bổ nhiệm có các phần tử không âm và có ít nhất n số 0 thì một phương án tối ưu tồn tại nếu n số 0 nằm trong các vị trí các số 1 của ma trận hoán vị Pnxn. Ma trận P biểu diễn phương án tối ưu. Rõ ràng mọi phương án đều có tổng chi phí không nhỏ hơn 0 nên 0 là nhỏ nhất. GV Phan Thanh Tao Bài giảng Quy hoạch toán học Trang 54 Định lý này cung cấp một mục tiêu của thuật toán. Chúng ta sẽ chứng tỏ rằng có thể thay đổi chi phí mà không thay đổi lời giải. Thuật toán sẽ trình bày cách sửa đổi để ma trận chi phí có