Phương pháp hungari giải bài toán giao việc tuyến tính và mở rộng

  • Số trang: 34 |
  • Loại file: PDF |
  • Lượt xem: 40 |
  • Lượt tải: 0
tailieuonline

Đã đăng 27670 tài liệu

Mô tả:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC VŨ THỊ CÚC PHƢƠNG PHÁP HUNGARI GIẢI BÀI TOÁN GIAO VIỆC TUYẾN TÍNH VÀ MỞ RỘNG LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2015 1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ MỤC LỤC Trang LỜI NÓI ĐẦU 2 Chƣơng 1. PHƢƠNG PHÁP HUNGARI VÀ BÀI TOÁN GIAO VIỆC 4 1.1. Bài toán giao việc 4 1.2. Phƣơng pháp Hungari 8 1.3. Ví dụ áp dụng 12 1.4. Bài toán tìm cực đại 15 Chƣơng 2. PHƢƠNG PHÁP THU HẸP CHÍNH TẮC 18 2.1. Bài toán vận tải tuyến tính 18 2.2. Phƣơng pháp thu hẹp chính tắc 21 2.4. Ví dụ minh họa 27 KẾT LUẬN 31 TÀI LIỆU THAM KHẢO 32 2 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ LỜI NÓI ĐẦU Bài toán giao việc (Assignment Problem) là một trƣờng hợp riêng quan trọng của bài toán qui hoạch tuyến tính và có quan hệ gần gũi với bài toán vận tải (Transportation Problem) và bài toán ngƣời du lịch (Traveling Salesman Problem) trong tối ƣu tổ hợp và lý thuyết đồ thị. Bài toán giao việc có nhiều ứng dụng thiết thực, đa dạng trong thực tiễn và luôn là chủ đề hấp dẫn của tối ƣu hóa. Hiện vẫn có nhiều nghiên cứu đề cập tới bài toán giao việc nhằm tổng quát và mở rộng phạm vi ứng dụng của bài toán. Phương pháp Hungari (Hungarian Method) rất độc đáo và hiệu qủa để giải bài toán giao việc. Tên gọi của phƣơng pháp là để tƣởng nhớ hai nhà toán học Hungari: König và Egeváry, đã có công đầu tạo ra cơ sở lý luận cho phƣơng pháp. Harold W. Kuhn là ngƣời đã phát triển và công bố phƣơng pháp này năm 1955 (xem [6]). Phƣơng pháp Hungari đã trở nên quen thuộc, đƣợc dùng rộng rãi và có thể mở rộng cho nhiều bài toán khác của qui hoạch tuyến tính, trong đó có bài toán vận tải mà thuật toán "thu hẹp chính tắc" là một dạng mở rộng nhƣ thế. Luận văn "Phương pháp Hungari giải bài toán giao việc tuyến tính và mở rộng" nhằm mục đích tìm hiểu bài toán giao việc với hàm mục tiêu tuyến tính và các ứng dụng của bài toán; Phƣơng pháp Hungari giải bài toán giao việc tuyến tính và phƣơng pháp "thu hẹp chính tắc" giải bài toán vận tải (ở dạng ma trận) của qui hoạch tuyến tính. Luận văn đƣợc trình bày trong hai chƣơng. Chƣơng 1 "Phƣơng pháp Hungari và bài toán giao việc" trình bày nội dung bài toán giao việc với hàm mục tiêu tuyến tính và một số ứng dụng của bài toán, đồng thời đề cập tới một số bài toán có liên quan: Bài toán vận tải và bài toán ngƣời du lich. Tiếp đó, luận văn trình bày phƣơng pháp Hungari quen thuộc giải bài toán và các ví dụ minh họa. 3 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ Chƣơng 2 "Phƣơng pháp thu hẹp chính tắc" đề cập tới bài toán vận tải với hàm mục tiêu tuyến tính, một dạng mở rộng của bài toán giao việc tuyến tính (khi vế phải nguyên, khác 1) và trình bày phƣơng pháp "thu hẹp chính tắc" do Giả sử Hoàng Tụy đƣa ra trong [3] (có chung ý tƣởng với phƣơng pháp Hungari) để giải bài toán.Luận văn đã nêu các ví dụ minh họa cho thuật toán giải đã trình bày. Phân tích quan hệ giữa phƣơng pháp thu hẹp chính tắc với phƣơng pháp Hungari và một số phƣơng pháp giải khác có cùng ý tƣởng. Do thời gian và kiến thức còn hạn chế nên chắc chắn luận văn này còn có những thiếu sót nhất định, kính mong quí thầy, cô và các bạn đóng góp ý kiến để tác giả tiếp tục hoàn thiện luận văn sau này. Nhân dịp này, tác giả luận văn xin bày tỏ lòng biết ơn sâu sắc tới GS - TS Trần Vũ Thiệu, ngƣời đã tận tình giúp đỡ trong suốt quá trình làm luận văn. Tác giả chân thành cảm ơn các thầy giáo, cô giáo Trƣờng Đại học Khoa học Đại học Thái Nguyên, Viện Toán hoc - Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã giảng dạy và tạo mọi điều kiện thuận lợi trong quá trình tác giả học tập và nghiên cứu. Thái Nguyên, tháng 04 năm 2015 Tác giả Vũ Thị Cúc 4 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ Chƣơng 1 PHƢƠNG PHÁP HUNGARI VÀ BÀI TOÁN GIAO VIỆC Chƣơng này đề cập tới bài toán giao việc, một dạng đặc biệt của bài toán vận tải và có nhiều ứng dụng rộng rãi. Sau khi nêu nội dung và ý nghĩa của bài toán, luận văn sẽ trình bày phƣơng pháp Hungari quen thuộc giải bài toán và các ví dụ minh họa. Nội dung của chƣơng đƣợc tham khảo từ tài liệu [1], [4] và [7]. 1.1. BÀI TOÁN GIAO VIỆC TUYẾN TÍNH Bài toán này có nội dung nhƣ sau: Có n ngƣời (i = 1, 2, ... , n) và n công việc (j = 1, 2, ... , n). Để giao cho ngƣời i thực hiện công việc j cần một chi phí cij ≥ 0. Vấn đề là cần giao cho ngƣời nào làm việc gì (mỗi ngƣời chỉ làm một việc, mỗi việc chỉ do một ngƣời làm) sao cho chi phí tổng cộng nhỏ nhất? Mô hình toán học cho bài toán này nhƣ sau: n n z= c ij x ij → min (1.1) i 1j 1 với các điều kiện n x ij = 1, i = 1, ... , n (mỗi ngƣời chỉ làm một việc), (1.2) x ij = 1, j = 1, ... , n (mỗi việc chỉ do một ngƣời làm), (1.3) xij = 0 hay 1, i = 1, ... , n, j = 1, ... , n (biến nhị nguyên). (1.4) j 1 n i 1 Vì có các điều kiện (1.2), (1.3) nên điều kiện (1.4) có thể thay bằng xij nguyên ≥ 0, i = 1, 2, ... , n, j = 1, 2, ... , n. Bài toán (1.1) - (1.4) gọi là bài toán giao việc với ma trận chi phí C = [cij]. 5 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ Định nghĩa 1.1. Các số {xij} thỏa mãn (1.2) - (1.4) gọi là một phương án giao việc, hay ngắn gọn là một phương án, một phƣơng án đạt cực tiểu của (1.1) gọi là một phương án tối ưu hay lời giải của bài toán. Giả sử danh sách người và việc đƣợc viết theo một thứ tự nhất định. Khi đó có một cách giao việc đơn giản là giao cho ngƣời i thực hiện công việc ở vị trí thứ i trong danh sách. Nếu danh sách các công việc đƣợc sắp xếp lại và ta vẫn giao cho ngƣời i làm việc j trong danh sách thì rất có thể ta sẽ có chi phí tổng cộng nhỏ hơn. Vấn đề là cần xáo trộn danh sách các công việc sao cho chi phí tổng cộng là nhỏ nhất. Nói một cách khác, cần tìm một hoán vị = (i1, i2, ... , in) của n số 1, 2, ... , n sao cho tổng số c1i1 + c1i2 + ... + c1in đạt giá trị nhỏ nhất. Số hoán vị của n số 1, 2, ... , n bằng n!, vì thế bài toán có n! phƣơng án. Hàm n! tăng theo hàm giai thừa: 4! = 24, 10! = 3.628.800 và 100! = 9,3×10157. Tính và so sánh n! phƣơng án để chọn ra phƣơng án tối ƣu là một thuật toán không có hiệu quả thực tế, vì đó là một thuật toán thời gian mũ. Mỗi hoán vị của n số 1, 2, ... , n có thể đặt tƣơng ứng với một ma trận vuông cấp n : X = [xij], với các phần tử 0 hoặc 1, xij = 1 có nghĩa là ngƣời i đƣợc giao làm việc j. Chẳng hạn, hoán vị 3, 1, 2 tƣơng ứng với ma trận 0 0 1 X= 1 0 0 0 1 0 Để ý rằng trên mỗi hàng, mỗi cột của ma trận X có vừa đúng một số 1 (mọi số còn lại bằng 0). Cùng với bài toán min z, ta có thể xét bài toán max z với cùng các điều kiện (1.2) - (1.4). Khi đó cij biểu thị hiệu quả thu đƣợc khi giao cho ngƣời i thực hiện công việc j. Bài toán giao việc rất gần với hai bài toán quen thuộc sau đây. 6 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ • Bài toán vận tải: Cần vận chuyển một loại hàng (xi măng chẳng hạn) từ m nơi cung cấp hàng (gọi là trạm phát) tới n nơi tiêu thụ hàng (gọi là trạm thu). Cho biết lƣợng hàng có ở trạm phát i (i = 1, 2, ... , m) là số pi nguyên > 0, và lƣợng hàng cần ở tram thu j (j = 1, 2, ... , n) là số qj nguyên > 0 và giá cƣớc vận chuyển một đơn vị hàng từ trạm phát i tới trạm thu j là cij ≥ 0. Giả thiết các pi, qj thỏa mãn điều kiện cân bằng cung cầu: p1 + p2 + ... + pm = q1 + q2 + ... + qn. Vấn đề đặt ra là: cần tìm một phƣơng án vận chuyển hàng từ mỗi trạm phát tới mỗi trạm thu sao cho mọi trạm phát đều giao hết lƣợng hàng có, mọi trạm thu đều nhận đủ lƣợng hàng cần, và tổng chi phí vận chuyển là nhỏ nhất? Mô hình toán học của bài toán này sẽ đƣợc nêu ở Mục 2.1, Chƣơng 2. • Bài toán ngƣời du lịch: Có n thành phố, đánh số từ 1 tới n. Xuất phát từ một trong n thành phố này (chẳng hạn thành phố 1), một khách du lịch muốn tới thăm (n - 1) thành phố còn lại, mỗi thành phố vừa đúng một lần, rồi trở về thành phố xuất phát. Cho biết cij là chi phí đi từ thành phố i tới thành phố j. Giả thiết cij > 0 với mọi i ≠ j và cii = + ∞ với mọi i (có thể cij ≠ cji). Hãy tìm cho khách du lịch một hành trình có tổng chi phí nhỏ nhất? Có một số cách diễn đạt toán học cho bài toán này, trong đó có mô hình tƣơng tự (1.1) (1.4) (xem chẳng hạn, [1] tr. 250). Trong mô hình (1.1) - (1.4) ở trên, ta giả thiết số ngƣời bằng số việc. Tuy nhiên, có thể xét trƣờng hợp khi số ngƣời khác số việc. Ví dụ, nếu số ngƣời nhiều hơn số việc, ta thêm vào các việc giả với chi phí hay hiệu quả bằng 0. Một số vấn đề không liên quan gì tới ngƣời và việc cũng có thể giải quyết nhờ mô hình bài toán giao việc. Chẳng hạn, cần lắp đặt các máy vào những vị trí khác nhau sao cho tốn ít chi phí, hay cần phân công các nhà máy sản xuất các sản phẩm sao cho đạt hiệu quả cao nhất. Ta hãy xét vài ví dụ. Ví dụ 1.1. Một cơ sở dịch vụ vừa mua 3 loại máy mới. Có 4 vị trí thích hợp cho việc lắp đặt các loại máy này, mỗi vị trí đặt đƣợc một máy. Do đặc điểm vị trí và do tính năng của mỗi máy, nên chi phí lắp đặt và khai thác mỗi máy ở các vị trí khác nhau có thể khác nhau. Chi phí này đƣợc cho ở Bảng 7 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ 1.1. Vị trí 2 không phù hợp để đặt máy 2 nên ở ô tƣơng ứng không ghi chi phí. Cần đặt máy vào những vị trí nào sao cho chi phí tổng cộng là nhỏ nhất? Để diễn đạt bài toán này dƣới dạng bài toán giao việc, ta thêm vào một máy giả (máy 4) cho vị trí thừa ra. Đồng thời, gán cho ô ứng với máy 2 và vị trí 2 một chi phí bằng số M khá lớn, để ngăn không cho đặt máy 2 ở vị trí 2. Kết quả ta nhận đƣợc Bảng 1.2. Bảng 1.1. Dữ liệu Ví dụ 1.1 Máy Bảng 1.2. Phƣơng án tối ƣu Vị trí 1 2 3 4 1 17 20 16 15 2 16 - 14 21 3 10 12 15 11 Máy 1 2 3 4 Vị trí 1 2 3 4 17 16 10 0 20 M 12 0 16 14 15 0 15 21 11 0 Áp dụng thuật toán giải nêu ở mục sau, ta nhận đƣợc lời giải: máy 1 đặt ở vị trí 4, máy 2 đặt ở vị trí 3, máy 3 đặt ở vị trí 1, với tổng chi phí bằng 39. Máy giả đƣợc đặt ở vị trí 2, vì thế vị trí này có thể dùng để đặt máy thực trong tƣơng lai. Ví dụ 1.2. Một hãng sản xuất định chế tạo 4 loại sản phẩm mới bằng cách tận dụng năng lực dƣ thừa của 4 nhà máy thuộc hãng. Hiệu quả sản xuất của các nhà máy đƣợc cho trong Bảng 1.3. Hãy tìm cách phân công cho nhà máy nào sản xuất sản phẩm gì (mỗi nhà máy chỉ sản xuất một loại sản phẩm, mỗi loại sản phẩm chỉ do một nhà máy sản xuất) để thu đƣợc hiệu quả tổng cộng lớn nhất? Lời giải: Nhà máy 1 sản xuất sản phẩm I, nhà máy 2 sản xuất sản phẩm III, nhà máy 3 sản xuất sản phẩm IV, nhà máy 4 sản xuất sản phẩm II. Hiệu quả tổng cộng bằng 30 (xem Bảng 1.3). 8 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Bảng 1.3. Dữ liệu Ví dụ 1.2 Nhà máy 1 2 3 4 I 9 7 6 5 Sản phẩm II III 6 3 9 10 3 2 6 5 http://www.lrc-tnu.edu.vn/ Bảng 1.4. Dữ liệu Ví dụ 1.3 Tầu IV 7 6 5 3 A B C D 1 3 4 3 5 Cảng 2 3 5 7 7 8 4 6 7 9 4 5 3 2 6 Ví dụ 1.3. Ở một cảng nọ có 4 tầu A, B, C, D có thể dùng để chở hàng tới 4 cảng 1, 2, 3, 4. Do sự khác nhau về loại tầu và loại hàng nên tổng chi phí xếp, dỡ và vận chuyển hàng trên các tầu khác nhau tới các cảng khác nhau có sự khác biệt đáng kể. Các chi phí này đƣợc cho ở Bảng 1.4. Vấn đề là điều tầu nào tới cảng nào (mỗi tầu tới một cảng, mỗi cảng có một tầu tới) sao cho chi phí tổng cộng của cả 4 chuyến hàng là nhỏ nhất? Một trong số các lời giải là: A → 1, B → 4, C → 2, D → 3, với tổng chi phí bằng 19 (xem Bảng 1.4). 1.2. PHƢƠNG PHÁP HUNGARI Bài toán (1.1) - (1.4) là trƣờng hợp riêng của mô hình bài toán vận tải, trong đó số địa điểm sản xuất bằng số địa điểm tiêu thụ, đồng thời các khả năng cung cấp pi bằng các yêu cầu tiêu thụ qj và đều bằng 1. Vì thế về nguyên tắc có thể dùng phƣơng pháp giải bài toán vận tải (chẳng hạn, thuật toán thế vị) để giải bài toán giao việc. Tuy nhiên, do cấu trúc đặc biệt của bài toán giao việc nên có những thuật toán giải riêng, hiệu quả hơn. Dƣới đây sẽ trình bày một trong các phƣơng pháp đó, với tên gọi phương pháp Hungari. Giả sử ta xét bài toán min z. Trƣớc hết ta nêu một số định lý làm cơ sở lý luận cho phƣơng pháp Hungari. Định lý 1.1. Giả sử ma trận chi phí của bài toán (1.1) - (1.4) không âm và có ít nhất n phần tử bằng 0. Hơn nữa nếu n phần tử 0 này nằm ở n hàng khác nhau và n cột khác nhau thì phương án giao cho người i thực hiện công 9 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ việc tương ứng với số 0 này ở hàng i sẽ là phương án tối ưu (lời giải) của bài toán (1.1) - (1.4). Chứng minh. Theo giả thiết của định lý, mọi phƣơng án giao việc có chi phí không âm. Trong khi đó, phƣơng án giao việc nêu trong định lý có chi phí ∎ bằng 0, nên chắc chắn phƣơng án đó là tối ƣu. Định lý sau đây cho thấy rằng ta có thể biến đổi ma trận chi phí của bài toán mà không làm ảnh hƣởng tới lời giải của nó. Vì thế phƣơng pháp giải nêu dƣới đây sẽ thực hiện ý tƣởng biến đổi ma trận chi phí cho đến khi đạt tới ma trận có ít nhất một phần tử 0 trên mỗi hàng và mỗi cột. Định lý 1.2. Cho C = [cij] là ma trận chi phí của bài toán giao việc (n người, n việc) và X* = [ x ij ] là một lời giải (phương án tối ưu) của bài toán này. Giả sử C' là ma trận nhận được từ C bằng cách thêm số ≠ 0 (dương hay âm) vào mỗi phần tử ở hàng r của C. Khi đó X* cũng là lời giải của bài toán giao việc với ma trận chi phí C'. Chứng minh. Hàm mục tiêu của bài toán giao việc mới bằng n n n n n c ij x ij = z' = i 1j 1 n n c ij x ij + × i 1j 1 n n x rj = j 1 x rj j 1 i 1 j 1 i r n = c rj c ij x ij + c ij x ij + . i 1j 1 Đẳng thức cuối cùng có đƣợc là do tổng các xij trên mỗi hàng, mỗi cột đều bằng 1. Vì thế, giá trị nhỏ nhất của z' đạt đƣợc khi và chỉ khi n n c ij x ij z= i 1j 1 là nhỏ nhất. Cụ thể là, z' đạt cực tiểu tại X = X*. ∎ Định lý 1.2 vẫn còn đúng nếu ta thêm một hằng số vào mỗi phần tử trên cùng một cột của ma trận chi phí. Vậy, chiến thuật của ta là biến đổi C bằng cách thêm hằng số vào các hàng và các cột của ma trận chi phí. 10 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ Giả sử ta xét bài toán min z và ma trận chi phí không âm. Thuật toán giải gồm các bƣớc sau đây. Bƣớc 0 (Bƣớc chuẩn bị). Trừ các phần tử trên mỗi hàng của C cho phần tử nhỏ nhất trên hàng đó, tiếp theo trừ các phần tử trên mỗi cột cho phần tử nhỏ nhất trên cột đó. Kết quả ta nhận đƣợc ma trận C' có tính chất: trên mỗi hàng, cột có ít nhất một phần tử 0 và bài toán giao việc với ma trận C' có cùng lời giải nhƣ bài toán với ma trận C (Định ý 1.2). Bƣớc 1 (Đánh dấu * cho phần tử 0). Với mỗi hàng, lần lƣợt từ hàng 1 tới hàng n, đánh dấu * cho phần tử 0 đầu tiên (trên hàng đó) không nằm trên cột đã có phần tử 0* (phần tử 0 đƣợc đánh dấu *). Xét hai khả năng: a) Nếu sau khi đánh dấu thấy có đủ n phần tử 0* thì dừng: các phần tử 0* sẽ cho lời giải cần tìm. Cụ thể là: ngƣời i đƣợc giao thực hiện công việc tƣơng ứng với phần tử 0* trên hàng i (Định lý 1.1). b) Nếu số phần tử 0* nhỏ hơn n thì chuyển sang thực hiện Bƣớc 2. Bƣớc 2. Lần lƣợt từ hàng 1 tới hàng n, tìm hàng đầu tiên không chứa phần tử 0*. Hàng nhƣ thế phải có vì lúc này chƣa đủ n phần tử 0*. Giả sử đó là hàng i0. Vì trên mỗi hàng đều có ít nhất một phần tử 0, nên trên hàng i0 phải có phần tử 0, chẳng hạn ở cột j0. Xuất phát từ ô (i0, j0), ta sẽ xây dựng một dây chuyền các ô kế tiếp nhau theo chiều dọc (theo cột), ngang (theo hàng) nối các phần tử 0 với 0* và 0* với 0 (gọi tắt là dây chuyền đan) nhờ hai thao tác: (A) (Tìm 0* theo cột) Giả sử ta đang ở phần tử 0 trong ô (ik, jk) với k ≥ 0, ta tìm phần tử 0* trong cột jk. a) Nếu tìm thấy thì thêm vào dây chuyền đang xét ô chứa phần tử 0* này, rồi thực hiện thao tác (B) dƣới đây; b) Nếu trái lại, ta đổi mỗi phần tử 0 trên dây chuyền đan này thành 0* và đổi mỗi 0* (cũ) thành 0. Sau đó, nếu có đủ n phần tử 0* thì dừng. Nếu chƣa đủ, thì xét hàng tiếp theo không chứa 0* (nếu còn), hoặc chuyển sang Bƣớc 3 (nếu đã xét hết). (B) (Tìm 0 theo hàng) Giả sử ta đang ở phần tử 0* trong ô (ik+1, jk), với k ≥ 0. Trên hàng ik+1 ta tìm phần tử 0 không nằm trên cột đã có mặt trong dây chuyền đang xét. Có hai khả năng: 11 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ a) Nếu tìm đƣợc thì ta thêm vào dây chuyền đang xét ô chứa phần tử 0 này, rồi thực hiện thao tác (A) nêu trên đây để tìm tiếp 0* theo cột. b) Nếu trái lại, thì ta gọi jk là cột thiết yếu và loại khỏi dây chuyền đang xét hai ô (ik+1, jk) và (ik, jk), tức quay lui trên dây chuyền đang xét. b1) Nếu sau đó vẫn còn ô trên dây chuyền đang xét (k ≥ 1), ta lại xuất phát từ phần tử 0* trong ô (ik, jk-1) và lặp lại thao tác (B) với hàng ik thay cho hàng ik+1, nghĩa là trên hàng ik ta tìm phần tử 0, không nằm trên cột jk (cột thiết yếu) và trên các cột trƣớc đó đã có mặt trong dây chuyền đang xét. b2) Nếu không còn ô nào trên dây chuyền này (k = 0), thì ta lại tìm phần tử 0 ở tƣơng giao của hàng không chứa 0* và cột không phải là thiết yếu. Nếu thấy phần tử 0 nhƣ thế, chẳng hạn trong ô ( i 0 , j0 ), ta lặp lại thao tác (A), xuất phát từ ô ( i 0 , j0 ). Nếu hết phần tử 0 nhƣ thế thì ta chuyển sang Bƣớc 3. Bƣớc 3. (Xác định hàng thiết yếu) Lúc này chƣa có đủ n phần tử 0* và ở Bƣớc 2 ta đã xác định đƣợc các cột thiết yếu. Bây giờ ta cần xác định các hàng thiết yếu. Một hàng gọi là thiết yếu nếu hàng đó chứa phần tử 0* ở cột không phải là thiết yếu. König, chuyên gia về lý thuyết đồ thị ngƣời Hungari, đã chứng minh định lý sau đây làm cơ sở lý luận cho việc biến đổi tiếp ma trận C' ở Bƣớc 4. Định lý 1.3. Số tối đa các phần tử 0* (phần tử 0 được đánh dấu *) bằng số tối thiểu các hàng và cột thiết yếu. Hơn nữa, số hàng và cột này chứa trọn mọi phần tử 0 và 0* của C'. Bƣớc 4. (Biến đổi ma trận C') Giả sử là số nhỏ nhất trong số các phần tử của ma trận C' thuộc hàng và cột không thiết yếu. Từ Định lý 1.3 suy ra > 0, vì mọi phần tử 0 đều nằm trên các hàng và cột thiết yếu. Biến đổi các phần tử trong C' bằng cách: trừ vào mọi phần tử thuộc các hàng không thiết yếu và thêm vào mọi phần tử thuộc các cột thiết yếu. Việc làm này tƣơng đƣơng với trừ vào mọi phần tử thuộc hàng và cột không thiết yếu, và thêm vào mọi phần tử thuộc hàng và cột đều là thiết yếu. Quay trở lại thực hiện Bƣớc 2 để đánh thêm dấu * cho các phần tử 0 trong ma trận thu đƣợc. 12 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ Để ý rằng sau khi biến đổi ma trận C' nhƣ trên, thì trong ma trận C vừa nhận đƣợc, các phần tử 0* trong C' vẫn đƣợc giữ nguyên nhƣ cũ, và ở một số hàng không thiết yếu sẽ có thêm các phần tử 0 mới. Do đó tạo khả năng đánh ∎ thêm dấu * cho các phần tử 0 mới này. Phƣơng pháp vừa nêu có tên gọi phương pháp Hungari là để tƣởng nhớ hai nhà toán học ngƣời Hungari tên là König và Egeváry, đã có công đầu tạo ra cơ sở lý luận cho phƣơng pháp. Phƣơng pháp Hungari thuộc loại phƣơng pháp tối ƣu tổ hợp dựa trên các kết quả nghiên cứu của König và Egeváry, và đƣợc Harold W. Kuhn phát triển và công bố năm 1955 (xem [6]). Thuật toán Kuhn có độ phức tạp tính toán bằng O(n3), nó rất dễ đƣợc thực thi và lập trình trên máy tính. Có thể xem phƣơng pháp Hungari nhƣ một dạng đặc biệt của phƣơng pháp đơn hình đối ngẫu trong qui hoạch tuyến tính. Thật vậy, bài toán qui hoạch đối ngẫu của bài toán giao việc (1.1) - (1.4) có dạng (các biến ui và vj): n n ui + i 1 v j → max j 1 với các điều kiện ui + vj ≤ cij, i, j = 1, 2, ... , n. Có thể thấy một phƣơng án của bài toán đối ngẫu là ui = min cij , i = 1, 2, ... , n, 1 j n vj = min c ij 1 i n u i , j = 1, 2, ... , n. Đây chính là cách chọn ui, vj để nhận đƣợc ma trận C' với mọi phần tử cij = cij - vj - ui ≥ 0 ở Bƣớc chuẩn bị. Do đặt xij = 0 với mọi ô (i, j) có cij > 0 và chỉ đặt xij = 1 với ô (i, j) chứa phần tử 0*, nên ta luôn có (cij - vj - ui)xij = 0, tức là hệ thức về độ lệch bù trong điều kiện tối ƣu luôn đƣợc thỏa mãn. Vì thế, nếu trong C' có đủ n phần tử 0* thì ma trận X = [xij]m×n tƣơng ứng sẽ thỏa mãn (1.2), (1.3) và do đó X là một phƣơng án tối ƣu của bài toán giao việc. Nếu C' chƣa có đủ n phần tử 0* thì ta phải thay đổi hệ thế vị ui, vj (các 13 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ biến đối ngẫu), tức là biến đổi ma trận C' thành C" = cij - ui - vj, sao cho ui, vj vẫn là phƣơng án của bài toán đối ngẫu (tức C" ≥ 0). Biến đổi ma trận chi phí đƣợc thực hiện cho đến khi ma trận đó có đủ n phần tử 0* thì dừng thuật toán. 1.3. VÍ DỤ ÁP DỤNG Ví dụ 1.4. Để minh họa cho các bƣớc của thuật toán giải nêu trên, ta giải bài toán phân việc với n = 4 và ma trận chi phí nhƣ sau: 5 6 7 7 0 1 0 3 2 6 2 1 0 2 C= ⇒ C' = 1 6 9 4 0 5 6 2 5 8 7 0 3 4 2 0 . 3 5 Thực hiện Bƣớc 0, ta nhận đƣợc ma trận C': Trên mỗi hàng, mỗi cột đều có chứa phần tử 0. Ở Bƣớc 1, ta đánh dấu * cho phần tử 0 ở hàng 1, cột 1 và phần tử 0 ở hàng 2, cột 2 (vì trên cột 2 chƣa có phần tử 0*). Hàng 3 và 4 chỉ có phần tử 0 ở cột 1 mà cột này đã có 0* ở hàng 1, vì thế không thể đánh dấu * đƣợc nữa. Kết quả là mới có hai phần tử 0*, ta chuyển sang thực hiện Bƣớc 2. C' = 0 1 0 2 1 0 2 0 0 5 6 3 0 3 4 5 . Bƣớc 2: Bắt đầu xét từ hàng 3, hàng chƣa có phần tử 0*. Ô đầu tiên của hàng này chứa phần tử 0 là ô (3, 1). Ta tìm phần tử 0* trong cột 1 (thao tác A) và thấy 0* ở ô (1, 1), tiếp đó ta tìm phần tử 0 trong hàng 1 (thao tác B) và thấy 0 ở ô (1, 3). Lập lại thao tác A, ta thấy cột 3 không chứa phần tử 0*, nhƣ vậy ta có dây chuyền đan (mũi tên nét đứt trong ma trận C' trên đây): 0 trong ô (3, 1) - 0* trong ô (1, 1) - 0 trong ô (1, 3). Trên dây chuyền này, đổi 0 thành 0* và ngƣợc lại, ta nhận đƣợc ma trận C' mới. Trong C' bây giờ đã có 3 phần tử 0*. 14 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên C' = http://www.lrc-tnu.edu.vn/ 0 1 0 2 1 0 2 0 0 5 6 3 0 3 4 5 . Ta lặp lại Bƣớc 2: Bắt đầu từ hàng 4 (hàng đầu tiên từ trên xuống chƣa có 0*). Hàng này chứa 0 ở ô (4, 1). Thực hiện thao tác (A), ta thấy cột 1 chứa 0* ở ô (3, 1). Ta đƣợc dây chuyền, gồm hai ô: 0 trong ô (4, 1) - 0* trong ô (3, 1). Thực hiện thao tác (B), ta thấy hàng 3 không có phần tử 0 nào khác, nên cột 1 là cột thiết yếu và loại khỏi dây chuyền hai ô (3, 1) và (4, 1). Lúc này, không còn dây chuyền nào nữa và cũng không còn hàng nào không chứa phần tử 0*, nhƣng có phần tử 0 trên cột không thiết yếu, nên ta chuyển sang thực hiện Bƣớc 3 để xác định các hàng thiết yếu. C' = 0 1 0 2 1 0 2 0 0 5 6 3 0 3 4 5 . Bƣớc 3: Bắt đầu từ hàng 1, hàng này có 0* ở cột 3 (cột không thiết yếu), nên hàng 1 là thiết yếu. Hàng 2 có 0* ở cột 2 (cột không thiết yếu) nên hàng 2 là thiết yếu. Hàng 3 có 0* ở cột 1 (cột thiết yếu), nên hàng 3 không phải là thiết yếu. Hàng 4 không có 0* nên cũng không phải là thiết yếu. Nhƣ vậy, hàng 1, 2 và cột 1 là thiết yếu (kẻ nét đứt): các hàng, cột này chứa đƣợc mọi phần tử 0 và 0*. Ta chuyển sang thực hiện Bƣớc 4 để điều chỉnh ma trận C'. Bƣớc 4: Số nhỏ nhất trong các ô thuộc các hàng và cột không thiết yếu là 3. Trừ 3 vào các ô thuộc các hàng và cột không thiết yếu và thêm 3 vào các ô thuộc các hàng và cột đều là thiết yếu, ma trận C' bây giờ trở thành 15 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên C" = http://www.lrc-tnu.edu.vn/ 3 1 0 2 4 0 2 0 0 2 3 0 0 0 1 2 . Trở lại thực hiện Bƣớc 2, ta thấy hàng 4 chƣa có phần tử 0*. a) Nếu xét phần tử 0 ở ô (4, 1) thì ta tìm đƣợc dây chuyền đan 0 trong ô (4, 1) - 0* trong ô (3, 1) - 0 trong ô (3, 4). Sau khi đổi 0 thành 0* và ngƣợc lại, ta nhận đƣợc ma trận C1 , trong đó đã có n = 4 phần tử 0*: Dừng thuật toán. b) Nếu xét phần tử 0 ở ô (4, 2) thì ta tìm đƣợc dây chuyền đan 0 trong ô (4, 2) - 0* trong ô (2, 2) - 0 trong ô (2, 4). Sau khi đổi 0 thành 0* và ngƣợc lại, ta nhận đƣợc ma trận C2 , trong đó đã có n = 4 phần tử 0*: Dừng thuật toán. C1 = 3 1 0 2 4 0 2 0 0 2 3 0 0 0 1 2 , C2 = 3 1 0 2 4 0 2 0 0 2 3 0 0 0 1 2 . Ma trận C1 cho lời giải: ngƣời 1 việc 3, ngƣời 2 việc 2, ngƣời 3 việc 4, ngƣời 4 việc 1. Tổng chi phí là 7 + 2 + 4 + 2 = 15. Ma trận C2 cho lời giải: ngƣời 1 việc 3, ngƣời 2 việc 4, ngƣời 3 việc 1, ngƣời 4 việc 2, cũng với tổng chi phí bằng 7 + 2 + 1 + 5 = 15. ∎ 1.4. BÀI TOÁN TÌM CỰC ĐẠI Mặc dầu phƣơng pháp Hungari đƣợc mô tả để giải bài toán giao việc với hàm mục tiêu cực tiểu hóa. Song bài toán với mục tiêu cần làm cực đại cũng có thể giải nhờ phƣơng pháp này. Giả sử ta cần giải bài toán n n z= c ij x ij → max i 1j 1 16 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ với các điều kiện (1.2) - (1.4). Bài toán này có thể đƣa về bài toán tìm cực tiểu của hàm n n -z= ( c ij ) x ij → min i 1 j 1 với cùng các ràng buộc (1.2) - (1.4). Ma trận C = [cij] có phần tử dƣơng, thì ma trận [- cij] sẽ có phần tử âm và tiêu chuẩn tối ƣu nêu trong Định lý 1.1 không áp dụng đƣợc. Tuy nhiên, ta có thể sử dụng Định ý 1.2, và thêm vào mỗi phần tử của ma trận [- cij] một số bằng số đối của số âm nhỏ nhất trong các phần tử - cij. Ma trận thu đƣợc sẽ có mọi phần tử không âm, và bài toán giao việc với ma trân mới này có thể giải theo phƣơng pháp Hungari đã nêu. Ví dụ 1.5. Xét bài toán giao việc với mục tiêu cần làm cực đại tƣơng ứng với ma trận hiệu quả 8 2 C = [cij] = 4 4 5 6 6 7 5 6 3 1 2 5 . 7 3 Bài toán cực tiểu hóa tƣơng đƣơng là n n -z= ( c ij ) x ij → min i 1 j 1 với các ràng buộc (1.2) - (1.4). Phần tử nhỏ nhất trong ma trận [- cij] là - 8. Vì thế ta thêm 8 vào mỗi phần tử trong ma trận [- cij] và nhận đƣợc ma trận 0 3 3 6 6 2 2 3 C' = . 4 2 5 1 4 1 7 5 Ma trận này đƣợc xem nhƣ ma trận chi phí và bài toán giao việc tƣơng ứng có thể giải theo phƣơng pháp Hungari đã nêu. 17 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Thực hiện Bƣớc 0, ta nhận đƣợc ma trận 0 3 3 4 0 0 C = 3 1 4 3 0 6 http://www.lrc-tnu.edu.vn/ 6 1 . 0 4 Thực hiện Bƣớc 1 ta nhận đƣợc ma trận C = 0 3 3 6 4 0 0 1 3 1 4 0 3 0 6 4 . Ma trận này cho lời giải: ngƣời 1 việc 1, ngƣời 2 việc 3, ngƣời 3 việc 4, ngƣời 4 việc 2. Hiệu quả tổng cộng là: 8 + 6 + 7 + 7 = 28. ∎ Tóm lại, chƣơng này đã giới thiệu nội dung bài toán giao việc tuyến tính và một số ứng dụng của bài toán. Trình bày cơ sở lý luận và các bƣớc thuật toán của phƣơng pháp Hungari giải bài toán. Đây là một loại thuật toán tối ƣu tổ hợp chạy trong thời gian đa thức, rất hiệu quả và gần về ý tƣởng với "thuật toán thu hẹp chính tắc" giải bài toán vận tải, đƣợc trình bày ở chƣơng sau. 18 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ Chƣơng 2 PHƢƠNG PHÁP THU HẸP CHÍNH TẮC Chƣơng này đề cập tới bài toán vận tải ở dạng đồ thị, sau đó dƣới dạng bảng và trình bày phƣơng pháp thu hẹp chính tắc giải bài toán. Nội dung của chƣơng đƣợc tham khảo từ các tài liệu [2], [3] và [5]. 2.1. BÀI TOÁN VẬN TẢI TUYẾN TÍNH Giả sử trong một đồ thị G = (A, E) với tập đỉnh A = {a1, a2, ... , am; b1, b2, ... , bn} và tập cạnh E = {(ai, bj) : i = 1, 2, ... , m, j = 1, 2, ... , n}. Các đỉnh a1, a2, ... , am là các trạm phát (nơi cung cấp hàng), b1, b2, ... , bn là các trạm thu (nơi tiếp nhận hàng). Trạm phát ai cần chuyển đi pi (lƣợng cung) đơn vị hàng, trạm thu bj cần nhận qj (lƣợng cầu) đơn vị hàng, pi và qj là những số nguyên dƣơng thỏa mãn điều kiện cân bằng cung cầu: p1 + p2 + ... + pm = q1 + q2 + ... qn. (2.1) Ta biết giá cƣớc cij để vận chuyển một đơn vị hàng từ trạm phát ai tới trạm thu bj. Khi đó, bài toán vận tải đƣợc đặt ra nhƣ sau: xác định số đơn vị hàng xiị cần vận chuyển từ mỗi trạm phát ai tới mỗi trạm thu bj sao cho tiết kiệm cƣớc phí vận chuyển nhất. Nói chính xác hơn, vấn đề là: Cho biết các số nguyên pi > 0 (i = 1, 2. … , m), qj > 0 (j = 1, 2, ... , n) và các số cij ≥ 0. Giả thiết có điều kiện (2.1), hãy tìm các số nguyên xij ≥ 0 sao cho n x ij = pi, i = 1, 2, ... , m (mọi trạm phát giao hết hàng), (2.2) x ij = qj, j = 1, 2, ... , n (mọi trạm thu nhận đủ hàng), (2.3) j 1 m i 1 m n c ij x ij (tổng cƣớc phí vận chuyển) nhỏ nhất có thể đƣợc. (2.4) i 1j 1 Trong các tài liệu về vận trù học (Operations Research) khi nói đến bài toán vận tải thƣờng là ám chỉ dạng phát biểu trên đây (cũng gọi là dạng bảng hay dạng ma trận). Đƣơng nhiên, nhƣ ta vừa thấy, bài toán vận tải dƣới dạng 19 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ đồ thị (hay dạng mạng) có thể đƣa về dạng bảng (dạng ma trận) một cách dễ dàng. Ngƣợc lại, sau đây ta sẽ thấy rằng bài toán vận tải dƣới dạng bảng cũng có thể xem nhƣ một trƣờng hợp riêng của dạng đồ thị và do đó, có thể giải bài toán bằng những phƣơng pháp đã có về bài toán vận tải trên đồ thị. Thật vậy, xét đồ thị G = (A, E) với A = {a1, a2, ... ,am, b1, b2, ... , bn}, E = {(ai, bj) : i = 1, 2, ... , m, j = 1, 2, ... , n} (xem Hình 2.1). Nếu ta lấy hệ yêu cầu o b1 a1o o b2 a2 o o b3 a3 o o b4 Hình 2.1. Đồ thị G = (A, E) {- pi (i = 1, 2, ... , m), qj (j = 1, 2, ... , n)} và giá cƣớc cij trên mỗi cung (ai, bj) thì rõ ràng việc tìm các xij theo các điều kiện (2.2), (2.3), (2.4) chẳng qua là giải bài toán trên đồ thị G, với các dữ kiện đã cho. Định nghĩa 2.1. Một ma trận không âm X = ||xij|| thỏa mãn (2.2), (2.3) gọi là một phương án của bài toán, một phƣơng án thỏa mãn (2.4) gọi là một phương án tối ưu (lời giải) của bài toán. Để tiện việc tính toán, ngƣời ta thƣờng biểu diễn đồ thị G trên đây bằng một bảng T (gọi là bảng vận tải), gồm m hàng và n cột: hàng thứ i đại diện cho đỉnh ai (trạm phát), cột thứ j đại diện cho đỉnh bj (trạm thu) và ô (i, j) ở tƣơng giao của hàng i và cột j đại diện cho cạnh (ai, bj) (xem Bảng 2.1). Trong bảng ngƣời ta ghi các dữ kiện của bài toán: Yêu cầu pi (lƣợng cung) ở trƣớc hàng i, yêu cầu qj (lƣợng cầu) ở trên đầu cột j, giá cƣớc cij ở góc trên bên trái ô (i, j). Trong quá trình tính toán, số xij sẽ ghi ở góc dƣới bên phải ô (i, j). Nhƣ vậy, muốn áp dụng vào đây các phƣơng pháp về đồ thị chỉ cần diễn giải theo ngôn ngữ bảng T các khái niệm thông thƣờng về đồ thị nhƣ: dây 20
- Xem thêm -