Luận văn Ứng dụng lý thuyết tối ưu giải bài toán lập lịch

22 CHƯƠNG 2. 4BTHUẬT TOÁN ĐA THỨC GIẢI BÀI TOÁN LẬP LỊCH 2.1. 12B ÀI TOÁN LẬP LỊCH 2.1.1. 25BMô hình toán học của bài toán lập lịch Xét bài toán tối ưu sau đây: (P): 1 1 ( ) max min m ijj n i f x x ≤ ≤ = = →∑ (2.1) 1 , =1, 2,..., n ij i j x p i m = =∑ (2.2) ≤ ≤0 nguyeân ij ijx a , = 1, 2, ..., ; =1, 2, ..., i m j n (2.3) trong đó ∈{0,1}ija và ∈{1,2,..., } ip n là những hằng số cho trước. - Hàm mục tiêu (2.1) làm một hàm lồi, các ràng buộc (2.2), (2.3) là ràng buộc nguyên, tuyến tính. Vì thế (P) thuộc lớp bài toán quy hoạch nguyên phi tuyến. Tuy nhiên có thể đưa bài toán (P) về bài toán quy hoạch nguyên tuyến tính có cấu trúc đặc biệt. - Ràng buộc (2.2) có thể thay bằng ràng buộc nới lỏng (2.2’) mà không làm ảnh hưởng tới lời giải của (P): 1 , =1, 2,..., n ij i j x p i m = ≥∑ (2.2’) Có thể thấy (P) tương đương với bài toán quy hoạch nguyên 0-1: ij i ij 1 1 : , , , ; , , , n m ij ij ij j i min t x p i x t j x {0,1} x a i j = = ⎧ ⎫⎪ ⎪≥ ∀ ≤ ∀ ∈ ≤ ∀⎨ ⎬⎪ ⎪⎩ ⎭∑ ∑ Bài toán (P) là mô hình toán học cho một số bài toán lập lịch ứng dụng trong thực tiễn. 23 2.1.2. 26BMột số bài toán lập lịch 2.1.2.1. 47B ài toán xếp lịch học tập Có m sinh viên và n chuyên đề cho các sinh viên này. Cho biết: 1, neáu sinh vieân öa thích chuyeân ñeà , 0, neáu ngöôïc laïi, 1,2,..., ; 1,2,...,ij i j a i m j n ⎧= ⎨ = =⎩ và pRiR nguyên dương là số chuyên đề mà sinh viên i cần học, i = 1, 2,..., m. Hãy tìm cách bố trí sinh viên học các chuyên đề phù hợp với họ sao cho mỗi sinh viên học đủ số chuyên đề cần học và làm đồng đều đến mức tối đa số sinh viên học trong các chuyên đề này (tức là phân chia sao cho số người trong nhóm chuyên đề có nhiều sinh viên tham dự nhất là nhỏ nhất có thể được). Nếu đặt các biến số: 1,neáu sinh vieân hoïc chuyeân ñeà , 0,neáu ngöôïc laïi, 1,2,..., ; 1,2,...,ij i j x i m j n ⎧= ⎨ = =⎩ Rõ ràng các xRijR phải thỏa mãn điều kiện 0 ij ijx a≤ ≤ (mỗi sinh viên chỉ tham dự những chuyên đề mà họ ưa thích) và xRi1R + xRi2R + … + xRinR = pRiR (tổng số chuyên đề mà sinh viên i tham dự vừa đủ yêu cầu). Khi đó số lượng sinh viên tham dự nhóm chuyên đề j là xR1jR + xR2jR + … + xRmjR và dễ thấy mô hình toán học cho bài toán đặt ra chính là bài toán (P). 2.1.2.2. 48B ài toán lập lịch cho hội nghị Một hội nghị có m tiểu ban, mỗi tiểu ban cần sinh hoạt trong một ngày tại phòng họp phù hợp phù hợp với nó. Có n phòng họp dành cho việc sinh hoạt của các tiểu bang. Cho biết: 1, neáu phoøng hoïp thích hôïp cho tieåu ban , 0, neáu ngöôïc laïi, ( 1,2,..., ; 1,2,..., )ij j i a i m j n ⎧= ⎨ = =⎩ 24 Hãy bố trí các phòng họp cho các tiểu ban sao cho hội nghị kết thúc sau ít ngày làm việc nhất? Nếu đặt các biến số: 1,neáu boá trí tieåu ban laøm vieäc ôû phoøng , 0,neáu ngöôïc laïi, 1,2,..., ; 1,2,...,ij i j x i m j n ⎧= ⎨ = =⎩ Khi đó, dễ thấy mô hình toán học cho bài toán đặt ra chính là bài toán (P), trong đó pRiR = 1 với mọi i = 1, 2, …, m (trong trường hợp này hàm mục tiêu biểu thị cho số ngày làm việc của hội nghị). 2.1.3. 27BTính chất nghiệm của bài toán (P) Trong mục này sẽ xét điều kiện của bài toán (P) có nghiệm và nêu ra ước lượng khoảng cho giá trị tối ưu (2.1) của bài toán. Bổ đề 2.1. Bài toán (P) có phương án khi và chỉ khi 1 , 1,2,..., n ij i j a p i m = ≥ =∑ (2.4) Chứng minh. Điều kiện cần của Bổ đề trên là hiển nhiên, vì từ các điều kiện (2.2) và (2.3) ta suy ra các bất đẳng thức trong (2.4). Để chứng minh điều kiện đủ, ta chỉ cần chỉ ra rằng nếu điều kiện (2.4) được thực hiện thì bài toán (P) luôn có phương án. Thật vậy, giả sử điều kiện (2.4) được thực hiện. Khi đó, nếu đặt: { }: 1,1i ijI j a j n= = ≤ ≤ thì mipI ii ,...,2,1, =≥ Nếu chọn tùy ý các tập ii II ⊂+ thỏa mãn , 1,2,...,i iI p i m+ = = , thì ( )ij mxnX x= với các thành phần được xác định theo công thức 1, , 0, , 1,2,...,ij i ij ix j I x j I i m + += ∈ = ∉ = (2.5) là phương án của bài toán (P). Bổ đề được chứng minh. 25 Điều kiện (2.3) cho thấy tập phương án của bài toán (P) là bị chặn, vì thế (2.4) cũng là điều kiện cần và đủ của bài toán (P) có nghiệm (phương án tối ưu). Để tìm khoảng ước lượng tối ưu (2.1) ta đưa vào các ký hiệu: 1 1 1 , 1, 2,..., , , 1, 2,..., = = = = = = = = ∑ ∑ ∑ n i ij j m j ij i m i i a a i m b a j n p p (aRiR biểu thị số chuyên đề mà sinh viên i ưa thích, bRjR biểu thị số sinh viên ưa thích học chuyên đề j, còn p là tổng số mọi chuyên đề mà sinh viên cần tham dự). Ta giả thiết i ia p≥ , 1,2,...,i m= , nghĩa là giả thiết có (2.4), 0jb > với mọi j = 1, 2, .., m; nghĩa là một chuyên đề phải có ít nhất một sinh viên muốn tham dự. Rõ ràng, ta có mbj ≤ với mọi j. Không mất tính tổng quát, ta giả thiết: 1 20 ... mb b b m< ≤ ≤ ≤ ≤ (2.6) Ký hiệu kP* P là trị tối ưu của hàm mục tiêu (2.1). Khi đó, ta có: Bổ đề 2.2. Ký hiệu ⎢⎣ ⎡⎥⎦ ⎤= n pk , trong đó ] [x biểu thị số nguyên nhỏ nhất lớn hơn hay bằng x, và 1 jj nk max b≤ ≤= . Khi đó ta ước lượng sau: kkk ≤≤ * . Chứng minh. Tổng số chuyên đề mà mọi sinh viên cần tham dự là p, mà mỗi chuyên đề có tối đa kP*P sinh viên tham dự nên phải có *.k n p≥ hay * pk n ≥ . Vì kP* P nguyên nên * ≥k k . Mặt khác, do ≤ij ijx a nên ij ij 1 1 m m j i i x a b = = ≤ =∑ ∑ với mọi 1,2,...,j n= . 26 Từ đó suy ra: 11≤ ≤ ≤ ≤= ≤ =∑m ij ji j n j nimax x maxb k và do đó * ≤k k . Bổ đề được chứng minh. Nếu k được xác định như trong Bổ đề 2.2 thỏa mãn 1>k b thì có thể cải tiến cận dưới của kP* P như sau: Bổ đề 2.3. Với các giả thiết đã nêu trên, nếu 1>k b thì * '≥ ≥k k k , trong đó k’ là số nguyên nhỏ nhất thỏa mãn: 1's sb k b +< ≤ và ( ) 1 '. s i i p b k n s = ≤ + −∑ , 1 1s n≤ ≤ − (2.7) Chứng minh. Từ Bổ đề và giả thiết 1k b> ta có * 1k b> . Theo cách sắp xếp (2.6) nên tìm được chỉ số t, 1 1t n≤ ≤ − , thỏa mãn * 1t tb k b +< ≤ . Vì các chuyên đề j với j t≤ ta có tối đa * 1t tb k b +< ≤ . Vì các chuyên đề j với j t≤ có tối đa *jb k< sinh viên tham dự, nên kP*P phải thỏa mãn điều kiện: * 1 ( ) t j j b k n t p = + − ≥∑ (2.8) Vì thế, nếu k’ là một cận dưới của kP*P, nghĩa là *'k k≤ , thì k’ cũng phải thỏa mãn bất đẳng thức có dạng (2.8) với t thay bởi s, trong đó s là chỉ số thỏa mãn 1's sb k b +< ≤ . Bổ đề được chứng minh. Chú ý: Ví dụ sau đây cho thấy cận dưới k’ tính theo (2.7) tốt hơn cận dưới k trong Bổ đề 2.2. Xét bài toán (P) với các số liệu: m = 4, n = 6, 1p = 5, 2p = 4, 3p = 3, 4p = 3 và 27 aRiR pRi 1 0 1 1 1 1 5 5 1 0 1 0 1 1 4 4 0 1 0 0 1 1 3 3 0 1 0 1 1 1 4 3 A ⎡ ⎤⎢ ⎥⎢ ⎥= ⎢ ⎥⎢ ⎥⎣ ⎦ : 2 2 2 2 4 4jb Rõ ràng , ( 1 4)i ia p i≥ = ÷ và 4 1 15i i p p = = =∑ . Theo Bổ đề 2.2, 15 3, 4 6 k k⎤ ⎡= = =⎥ ⎢⎦ ⎣ . Theo Bổ đề 2.3, cận dưới ' 4k = vì đó là số nhỏ nhất thỏa mãn (với s = 4): 4 52 ' 4b k b= = Vậy kP* P = 4. 2.2. 13BTHUẬT TOÁN ĐA THỨC GIẢI BÀI TOÁN (P) Bây giờ ta sẽ chỉ ra rằng việc giải bài toán (P) có thể dẫn về việc giải một số hữu hạn bài toán luồng cực đại trong mạng. Trước hết, với mỗi số nguyên dương k ( )k k k≤ ≤ , xây dựng mạng G(k) = (V, E) với tập đỉnh: { } { } { } { }: 1, 2,..., : 1, 2,...,= ∪ = ∪ = ∪i jV s u i m w j n t Trong đó s là điểm phát, t là điểm thu, và tập cung: ( ){ } ( ){ } ( ){ }j, : 1,2,..., , w : 1,2,..., ; 1,2,..., , : 1,2,...,= = ∪ = = ∪ =i i jE s u i m u i m j n w t j n Mỗi cung e E∈ được gán với khả năng thông qua ( )q e theo quy tắc sau: 28 ( ) ( ) ( ) , , 1, 2,..., , , , 1, 2,..., ; 1, 2,..., , , , 1, 2,..., . = = = = = = = i i i j ij j q s u p i m q u w a i m j n q w t k j n Hình 2.1 chỉ ra cách xây dựng mạng G(k). Hình 2.1. Mạng G(k) Bổ đề sau đây cho thấy mối liên hệ giữa luồng cực đại trong mạng G(k) và phương án của bài toán (P). Bổ đề 2.4. Giả sử đối với số nguyên dương k nào đó thỏa mãn k k k≤ ≤ và luồng cực đại nguyên ξ trong mạng G(k) có giá trị là p. Khi đó ( )= ij mxnX x với các thành phần được xác định theo công thức: ( ), , 1, 2,..., ; 1, 2,..., ,ξ= = =ij i jx u w i m j n là phương án của bài toán (P). Chứng minh. Do giá trị của luồng cực đại trong mạng G(k) không vượt quá p, nên: ( ) ( ) , , 1, 2,..., , {0, 1}, 1,2,..., ; 1,2,..., ξ ξ = = ∈ = = i i i j s u p i m u w i m j n Từ đó suy ra: 29 ( )j 1 1 , w ( , ) , 1, 2,...,ξ ξ = = = = = =∑ ∑n nij i i i j j x u s u p i m Vậy X là phương án của bài toán (P). Bổ đề được chứng minh. Bổ đề 2.5. Giả sử ( )ij= mxnX x là phương án tối ưu và k là giá trị tối ưu của bài toán (P). Khi đó luồng cực đại trong mạng G(k) có giá trị là p. Chứng minh. Do giá trị của luồng cực đại trong mạng G(k) không vượt quá p, nên để chứng minh bổ đề ta chỉ cần chỉ ra luồng với giá trị p trong mạng G(k). Xây dựng luồng ξ theo công thức sau: ( ) ( ) ( ) ij ij 1 , , , , 1, 2,..., ; 1, 2,..., . ξ ξ ξ = = = = = =∑ i i i j m j i s u p u w x w ,t x i m j n Dễ dàng kiểm tra được rằng ξ là luồng trong mạng G(k) có giá trị p. Bổ đề được chứng minh. Bổ đề 2.6. Nếu k k= thì luồng cực đại trong mạng ( )G k có giá trị là p. Chứng minh. Lập luận tương tự như trong Bổ đề 2.5, ta chỉ cần chỉ ra luồng với giá trị p trong mạng ( )G k . Thực vậy, giả sử là phương án của bài toán (P) xây dựng theo công thức (2.5). Xây dựng luồng ξ theo công thức giống như trong chứng minh Bổ đề 2.5, ta có luồng với giá trị p. Bổ đề được chứng minh. Từ Bổ đề 2.4 và Bổ đề 2.5 suy ra việc giải bài toán (P) dẫn về việc tìm giá trị k nguyên dương nhỏ nhất sao cho luồng cực đại trong mạng G(k) có giá trị p. Bổ đề 2.2 cho thấy giá trị ,⎡ ⎤∈ ⎣ ⎦k k k . Vì vậy để giải bài toán trong (P) ta có thể áp dụng phương pháp tìm kiếm nhị phân trên đoạn ,k k⎡ ⎤⎣ ⎦ để tìm giá trị k, trong đó ở mỗi bước cần giải một bài toán luồng cực đại trong mạng. 30 Từ đó suy ra kết quả sau: Định lý 2.1. Bài toán (P) giải được nhờ các thuật toán đa thức với độ phức tạp tính toán là logR2Rq.ORNFR, trong đó 1+−= kkq và ORNFR là độ phức tạp tính toán của bài toán tìm luồng cực đại trong mạng G(k). Dựa trên các kết quả trên ta có thuật toán sau để giải bài toán (P): THUẬT TOÁN 2.1 Bước 1. Tính các số: 1 m i i p p = = ∑ , ⎢⎣⎡⎥⎦⎤= n pk , và 1 max jj nk b m≤ ≤= ≤ Ký hiệu q(k) là giá trị của luồng cực đại trong mạng G(k). Bước 2. Nếu 1k k− ≤ , chuyển sang bước 5. Trái lại, đặt: ( ) / 2⎡ ⎤= + −⎣ ⎦k k k k Bước 3. Tìm luồng cực đại trên mạng G(k). Bước 4. Nếu ( )q k p< ta đặt 1k k= + , còn nếu q(k) = p thì đặt k k= . Trở lại Bước 2. Bước 5. Tìm luồng cực đại trên G(k) với =k k . Nếu ( )q k p= thì *k k= , còn nếu ( )q k p< thì *k k= . Dừng thuật toán. 31 Ví dụ 2.1. Để minh họa cho thuật toán nêu trên ta giải bài toán (P) với các số liệu sau: m = n = 5, và aRiR pRi 1 0 0 1 1 3 3 0 0 1 1 1 3 2 0 1 0 1 1 3 3 1 0 1 1 1 4 3 0 1 0 1 1 3 2 A ⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥= ⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦ : 2 2 2 5 5 16 13jb Quá trình giải diễn ra như sau: 1. Ta có: p = 13, 13 3, 5 5 k k⎤ ⎡= = =⎥ ⎢⎦ ⎣ 2. Do 2 1k k− = > nên ta đặt 3 1 4k = + = . 3. Mạng G(k = 4) có dạng như ở Hình 2.2. Hình 2.2. Mạng G(4) 4. Giá trị luồng cực đại ( )4 13q k p= = = . Đặt 4.k = Trở lại bước 2. 32 5. Do 1k k− = nên ta đặt 3k k= = và chuyển sang Bước 5. 6. Mạng G(k = 3) có dạng như ở Hình 2.3. Hình 2.3. Mạng G(3) Giá trị luồng cực đại q(k = 3)=12 < 13 = p. Vậy 4= =k k . Ta được phương án tối ưu tương ứng với mạng G(k = 4) vẽ ở Hình 2.2. Như vậy, chuyên đề đông nhất có 4 sinh viên và được phân bổ như ở Bảng 2.1. Bảng 2.1. Bảng kết quả phân bổ sinh viên và chuyên đề Chuyên đề 1 2 4 4 5 pRiR SV1 x x x 3 SV2 x x 2 SV3 x x x 3 SV4 x x x 3 SV5 x x 2 ∑ 2 2 2 3 4 13 33 2.3. 14BTHUẬT TOÁN ĐA THỨC DẠNG BẢNG GIẢI BÀI TOÁN (P) 2.3.1. 28BCơ sở phương pháp giải Xét lại mô hình bài toán (P): 1 1 ( ) max min m ijj n i f x x ≤ ≤ = = →∑ (2.9) 1 , =1, 2,..., n ij i j x p i m = =∑ (2.10) ≤ ≤0 nguyeân ij ijx a , = 1, 2, ..., ; =1, 2, ..., i m j n (2.11) trong đó ∈{0,1}ija và ∈{1,2,..., } ip n là những hằng số cho trước. Ta ký hiệu: = = = = = = >∑ ∑ ∑ij ij 1 1 , =1, 2,..., ; , =1, 2,..., ; 0 n m m i j i j 1 i i a a i m b a j n p p Khi đó, theo Bổ đề 2.1, điều kiện cần và đủ để bài toán (P) có lời giải là: =1, 2, ..., i ia p i m≥ ∀ (2.12) Ta giả thiết bài toán (P) thỏa mãn điều kiện (2.12). Giả sử x={ }ijx là một phương án của (P). Ứng với mỗi x ta kẻ một bảng gồm m hàng và n cột; mỗi hàng ứng với một sinh viên, mỗi cột ứng với một chuyên đề. Ô nằm ở hàng i, cột j được gọi là ô (i, j). Ta quy ước ô (i, j) là ô đen nếu aRijR=0 (ô đen sẽ không được xét, do sinh viên i không thích chuyên đề j nên xRijR = 0), các ô còn lại được phân thành 2 loại: ô trắng nếu xRijR=0 (sinh viên i ưa thích chuyên đề j, nhưng không được bố trí học chuyên đề 34 này trong phương án x) và ô xanh nếu xRijR=1 (sinh viên i ưa thích chuyên đề j, và được bố trí học chuyên đề này trong phương án x). Ký hiệu: = ∀ =∑ ij , 1,2,..., ; mxj i=1 t x j n xjnj x tt ≤≤ = 1 max (2.13) ( xjt biểu thị số sinh viên được bố trí học chuyên đề j trong phương án x và xt là giá trị hàm mục tiêu (2.9) tương ứng với phương án x). Với mỗi phương án x = { }ijx của (P), theo (2.13) ta luôn có: = = = = = = = = = =∑ ∑∑ ∑∑ ∑ 1 1 1 1 1 1 n n m m n m x j ij ij i j j i i j i t x x p p (2.14) Cột j được là cột đầy nếu =x xjt t , gọi là cột gần đầy nếu = −1x xjt t và gọi là cột vơi nếu ≤ − 2x xjt t . Ví dụ 2.2 Có 3 sinh viên và 4 chuyên đề, trong đó: ƒ Sinh viên 1 có thể học các chuyên đề 1, 3, 4 tổng số chuyên đề sinh viên 1 cần học là 2; ƒ Sinh viên 2 có thể học chuyên đề 3, tổng số chuyên đề sinh viên 2 cần học là 1; ƒ Sinh viên 3 có thể học các chuyên đề 1, 2, 3, 4 tổng số chuyên đề sinh viên 3 cần học là 3; Điều kiện của bài toán trên ta có thể viết lại thành dạng bảng như sau: 1 0 1 1 pR1 R= 2 0 0 1 0 pR2 R= 1 1 1 1 1 pR3 R= 3 35 Ở đây ta có một phương án như sau: 1 1 0 1 1 1 1 0 Đối với phương án này ta có: ƒ Cột 3 là cột đầy; ƒ Cột 1 là cột gần đầy; ƒ Cột 2, 4 là cột vơi. Từ các khái niệm trên, ta có ngay quy tắc đơn giản sau đây cho biết lời giải của (P): Mệnh đề 2.1. Nếu phương án x không có cột vơi thì x là phương án tối ưu của bài toán (P). Chứng minh. Từ (2.13) và (2.14) suy ra: p = ∑ = n j x jt 1 > n.( xt - 1) (2.15) Giả sử tồn tại phương án y tốt hơn phương án x hiện có, nghĩa là: 1−≤ xyj tt , ∀ j = 1, 2, …, n. (2.16) Từ (2.13) và (2.16) suy ra: p = ∑ = n j x jt 1 ≤ n.( xt - 1), điều này mâu thuẫn với (2.15). Chứng tỏ x là phương án tối ưu. 36 Mệnh đề 2.2. Nếu tồn tại dây chuyền C các ô xanh và trắng xen kẽ nhau nối một cột đầy với một cột vơi thì ta có thể điều chỉnh phương án hiện có thành phương án mới tốt hơn hoặc có số cột đầy ít hơn. Mệnh đề 2.3. Nếu không tồn tại dây chuyền C các ô xanh và trắng xen kẽ nhau nối một cột đầy với một cột vơi thì phương án hiện có là phương án tối ưu. Phép gán số cho các hàng và cột và tìm dây chuyền C Ta lần lượt gán số cho các hàng và cột của bảng như sau: - Gán số 0 cho các cột đầy, nếu cột j đã được gán số thì gán số j cho các hàng i chưa được gán số với xRij R=1 ((i, j) là ô xanh). Nếu hàng i đã được gán số thì gán số i cho các cột j chưa được gán số với xRij R= 0 ((i, j) là ô trắng). - Nếu một cột vơi nào đó được gán số thì tồn tại một dây chuyền C nối một cột đầy nào đó với một cột vơi jR0R. Cách tìm như sau: giả sử cột jR0R được gán số là iR0R ((iR0R,jR0R) là ô trắng) và hàng iR0R được gán số là jR1 R≠ jR0 R((iR0R, jR1R) là ô xanh). Giả sử cột jR1R được gán số khác 0, chẳng hạn iR1 R≠ iR0R ((iR1R, jR1R) là ô trắng, và hàng iR1R được gán số là jR2 R≠ jR1R, jR0R ((iR1R, jR2R) là ô xanh). Nếu cột jR2R được gán số khác 0, ta lại tiếp tục làm như trên. Do số cột trong bảng là hữu hạn (bằng n) nên cuối cùng, ta phải tìm được cột jRk R≠ jRtR, t = 0, 1,…, k-1, được gán số 0, nghĩa là cột jRkR đầy và dây chuyền cần tìm là: C={(iR0R, jR0R) , (iR0R, jR1R) , … , (iRk-1R, jRk-1R) , (iRk-1R, jRkR)} (k > 0) 2.3.2. 29BThuật toán Bước 0. Khởi tạo Lập bảng gồm m hàng và n cột, mỗi hàng tương ứng với một sinh viên, mỗi cột tương ứng với một chuyên đề. Tô đen các ô (i, j) có aRijR = 0 (ô đen không thay đổi trong suốt quá trình giải bài toán), gọi các ô còn lại là ô trắng. Đối với ví dụ 2.2 ta lập được bảng như sau: 37 Bước 1. Xây dựng phương án ban đầu Xây dựng phương án ban đầu. Với mỗi hàng i, từ hàng 1 tới m, ta lần lượt ghi số 1 vào các ô trắng từ trái qua phải cho đến khi đủ pRi Rsố (các ô còn lại xem như là số 0), rồi chuyển sang hàng tiếp theo. Kết quả là ta nhận được phương án ban đầu 1 1 ijx = {x } . Đặt k = 1. Chuyển sang Bước 2. Phương án ban đầu cho ví dụ 2.2: 1 1 0 1 1 1 1 0 Bước 2. Kiểm tra tối ưu Với phương án xPkP nhận được, ta quy ước gọi các ô được ghi số 1 là ô xanh, các ô (khác ô đen) được ghi số 0 là ô trắng. Tính các số: 1 , vaø kx k m k k k x k j j ij jj n i=1 t t x j = 1,2,...,n t t max t ≤ ≤ ≡ = ≡ =∑ Với phương án xPkP, ta quy ước gọi cột j là cột đầy nếu =k kjt t , gọi là cột gần đầy nếu = −1k kjt t và là cột vơi nếu ≤ − 2k kjt t . Nếu không có cột nào vơi thì theo Mệnh đề 1, xPkP là phương án tối ưu. Ngược lại ta thực hiện gán số cho các hàng và cột của bảng, sau khi gán số nếu không có cột vơi nào được gán số thì xPkP là phương án tối ưu. Nếu có cột vơi thì ta tìm được một dây chuyền C gồm các ô xanh và ô trắng xen kẽ nhau nối một cột đầy jRkR với một cột vơi jR0R. Sau đó chuyển sang Bước 3. (*) 38 Xét ví dụ 2.2: Kiểm tra tính tối ưu lần 1 (k = 1), ta có: 1 1t = 2, 1 2t R R= 1, 1 3t R R= 3, 1 4t R R= 0 ⇒ tP1P= max(2, 1, 3, 0) = 3 Do đó ta có cột 3 là cột đầy, cột 1 là cột gần đầy, các cột 2, 4 là cột vơi. Do tồn tại cột vơi nên phương án trên không phải là phương án tối ưu. Ta thực hiện gán số cho bảng. 0 1 3 1 1 0 3 1 3 1 1 1 0 Đầu tiên gán số 0 cho cột 3 là cột đầy; Xét cột 3 các ô (1, 3); (2, 3); (3, 3) có giá trị là 1 (ô xanh) nên tại các hàng tương ứng 1, 2, 3 ta gán số là 3. Trên hàng 1 ô (1, 4)R Rcó giá trị là 0 (ô trắng) nên ta gán 1 cho cột 4. Vì cột 4 là cột vơi đã được gán số nên đến đây việc gán số dừng lại. Do đó, tồn tại một dây chuyền C các ô xanh và trắng xen kẽ nhau nối một cột đầy với cột vơi 4, và ta tìm như sau: Cột 4 được gán số 1 nên ta có ô (1, 4) là ô trắng. Tiếp theo ta thấy hàng 1 được gán số 3 nên ta có ô (1,3) là ô xanh, mà cột 3 đã được đánh số 0 (tức cột 3 là cột đầy) nên đến đây ta đã tìm được dây chuyền C = {(1, 3); (1,4)}. Bước 3. Điều chỉnh phương án Thực hiện phép biến đổi ô xanh thành ô trắng và ô trắng thành ô xanh trên dây chuyền C ta nhận được phương án mới x’ tốt hơn phương án xPkP (tPx’ P< tPkP) hoặc x’ sẽ có số cột đầy ít hơn số cột đầy của xPkP. Đặt xPk+1 P= x’. Thay k bởi k +1 rồi quay lại Bước 2. 39 Như ở ví dụ 2.2, đối với chu trình C vừa tìm được, ta đổi các ô trắng thành ô xanh và ngược lại, ta được phương án mới như sau: 1 0 1 1 1 1 1 0 Kiểm tra tính tối ưu lần 2 (k = 2), ta có: 2 1t R R= 2, 2 2t R R= 1, 2 3t R R= 2, 2 4t R R= 1 ⇒ tP2 P= max(2, 1, 2, 1) = 2 Cột 1, 3 là các cột đầy; cột 2, 4 là các cột gần đầy. Như vậy, do không có cột vơi, nên theo Mệnh đề 1 thì đây là phương án tối ưu và thuật toán kết thúc. Ta có lưu đồ thuật toán như hình dưới đây: Hình 2.4. Lưu đồ thuật toán đa thức dạng bảng 40 Mệnh đề 2.4: Thuật toán sẽ kết thúc sau một số hữu hạn bước. 2.3.3. 30BĐộ phức tạp của thuật toán Để đánh giá độ phức tạp của thuật toán đã nêu trên, ta tiến hành phân tích độ phức tạp của từng bước trong thuật toán: Ở bước 1: Số phép toán cần thực hiện để xây dựng phương án ban đầu (kể cả việc tính tổng theo cột) tương đương với O(m.n). Ở bước 2: Để tính các số vaø k kjt t ta cần thực hiện số phép toán tương đương với O(m+n). Phép gán số cho các hàng và cột trong bảng cần tối đa O(m.n) phép toán. Việc tìm dây chuyền “xanh-trắng” nối một cột đầy với một cột vơi cần thực hiện O(m+n) phép toán (dựa theo số được gán cho các hàng và cột trong bảng). Như vậy, số phép toán cần ở Bước 2 tương đương với O(m.n). Ở bước 3: Việc điều chỉnh luồng trên dây chuyền nối một cột đầy với một cột vơi cần tối đa O(m+n) phép toán (m+n bằng số tối đa các ô trên dây chuyền). Các bước 2 và 3 lặp đi lặp lại một số lần. Sau mỗi lần lặp, hoặc giá trị hàm mục tiêu giảm đi 1 hoặc là số cột đầy giảm đi 1. Do hàm mục tiêu (2.9) chỉ nhận nhiều nhất là )(max 1 mbjnj ≤≤≤ giá trị và do số cột trong bảng bằng n nên số lần lặp tối đa là m x n. Như vậy số phép toán cần thực hiện theo thuật toán tương đương với O((m.n).(m.n)) hay O(mP2P.n P2 P). Tóm lại, thuật toán trên là một thuật toán đa thức. Hơn nữa, nó còn là thuật toán đa thức mạnh, theo nghĩa: độ phức tạp tính toán chỉ phụ thuộc vào kích thước của bài toán (m và n), chứ không phụ thuộc vào độ dài dữ liệu (các số aRi Rvà pRiR). 41 2.3.4. 31BVí dụ minh họa Giải bài toán (P) được cho bởi bảng sau: 1 0 0 1 1 1 1 pR1R = 3 0 0 1 1 1 0 0 pR2R = 3 1 0 1 1 0 1 0 pR3R = 2 1 1 0 1 1 0 0 pR4R = 3 1 1 0 1 0 1 1 pR5R = 3 1 1 1 1 0 1 1 pR6R = 3 Bước 1: Xây dựng phương án x={xRijR} ban đầu, ta được bảng sau: 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 0 Bước 2 (k =1): Kiểm tra tính tối ưu lần 1, ta có: 1 1t R R= 5, 1 2t = 3, 1 3t = 3, 1 4t = 4, 1 5t = 2, 1 6t R R= 0, 1 7t R R= 0 ⇒ t P1 P= 5 Tồn tại các cột 2, 3, 5, 6, 7 là các cột vơi nên đây chưa phải là phương án tối ưu. Thực hiện gán số cho bảng, ta được: 0 3 4 1 1 1 1 1 1 0 0 4 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 0 0 0 Bắt đầu từ cột vơi đầu tiên được đánh số là cột 5 ta tìm được dây chuyền sau: CR1R = {(4,1); (4,5)} 42 Bước 3 (k =1): Đổi các ô trắng thành ô xanh và ngược lại trên dây chuyền CR1R, ta được phương án mới như sau: 1 1 1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 Bước 2 (k =2): Kiểm tra tính tối ưu lần 2, ta có: 2 1t R R= 4, 2 2t R R= 3, 2 3t R R= 3, 2 4t R R= 4, 2 5t R R= 3, 2 6t = 0, 2 7t = 0 ⇒ t P2 P= 4 Tồn tại các cột 6, 7 là các cột vơi nên đây chưa phải là phương án tối ưu. Thực hiện gán số cho bảng, ta được: 0 3 1 1 1 1 1 1 0 0 4 1 1 1 1 1 1 0 0 4 0 1 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 Bắt đầu từ cột vơi đầu tiên được đánh số là cột 6 ta tìm được dây chuyền sau: CR2R = {(1,1); (1,6)} Bước 3 (k = 2): Đổi các ô trắng thành ô xanh và ngược lại trên dây chuyền CR2R, ta được phương án mới như sau: 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 43 Bước 2 (k = 3): Kiểm tra tính tối ưu lần 3, ta có: 3 1t R R= 3, 3 2t = 3, 3 3t R R= 3, 3 4t = 4, 3 5t R R= 3, 3 6t R R= 1, 3 7t = 0 ⇒ t P3 P= 4 Tồn tại các cột 6, 7 là các cột vơi nên đây chưa phải là phương án tối ưu. Thực hiện gán số cho bảng, ta được: 1 0 5 1 4 0 1 1 1 0 4 1 1 1 1 1 0 0 4 0 1 1 1 4 1 1 1 0 0 1 1 1 0 0 0 Bắt đầu từ cột vơi đầu tiên được đánh số là cột 6 ta tìm được dây chuyền sau: CR3R = {(5,4); (5,6)} Bước 3 (k = 3): Đổi các ô trắng thành ô xanh và ngược lại trên dây chuyền CR3R, ta được phương án mới như sau: 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1 0 0 0 Bước 2 (k = 4): Kiểm tra tính tối ưu lần 4, ta có: 4 1t R R= 3, 4 2t R R= 3, 4 3t R R= 3, 4 4t R R= 3, 4 5t = 3, 4 6t R R= 2, 4 7t = 0 ⇒ t P4 P= 3 Tồn tại cột 7 là cột vơi nên đây chưa phải là phương án tối ưu. Thực hiện gán số cho bảng, ta được: 44 0 3 3 5 0 1 1 1 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 1 0 1 1 1 1 0 0 0 Bắt đầu từ cột vơi đầu tiên được đánh số là cột 7 ta tìm được dây chuyền sau: CR4R = {(5,1); (5,7)} Bước 3 (k = 4): Đổi các ô trắng thành ô xanh và ngược lại trên dây chuyền CR4R, ta được phương án mới như sau: 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 0 1 0 1 1 1 1 1 0 0 0 Bước 2 (k = 5): Kiểm tra tính tối ưu lần 5, ta có: 5 1t R R= 2, 5 2t R R= 3, 5 3t = 3, 5 4t R R= 3, 5 5t = 3, 5 6t R R= 2, 5 7t = 1 ⇒ t P5 P= 3 Tồn tại cột 7 là cột vơi nên đây chưa phải là phương án tối ưu. Thực hiện gán số cho bảng, ta được: 4 0 5 6 6 0 1 1 1 0 1 1 1 1 1 0 0 2 0 1 1 1 2 0 1 0 1 1 2 1 1 1 0 0 0 45 Bắt đầu từ cột vơi đầu tiên được đánh số là cột 7 ta tìm được dây chuyền: CR6R = {(6,2); (6,7)} Bước 2 (k = 6): Đổi các ô trắng thành ô xanh và ngược lại trên dây chuyền CR6R, ta được phương án mới như sau: 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 0 1 0 1 1 1 0 1 0 0 1 Bước 2 (k = 6): Kiểm tra tính tối ưu lần 6, ta có: 6 1t R R= 2, 6 2t = 2, 6 3t = 3, 6 4t = 3, 6 5t = 3, 6 6t = 2, 6 7t = 2 ⇒ t P6 P= 3 Đến đây không còn tồn tại cột vơi nên ta thu được phương án tối ưu với giá trị hàm mục tiêu là t P6 P= 3. Từ kết quả thu được ở trên, ta có phương án xếp lịch học tối ưu cho bài toán đặt ra như sau: Chuyên đề 1 2 4 5 6 7 pRiR SV1 x x x 3 SV2 X x x 3 SV3 x X 2 SV4 x x x 3 SV5 x x x 3 SV6 x X x 3 ∑ 2 2 3 3 4 3 17 46 2.3.5. 32BCài đặt và thử nghiệm trên máy tính Sau đây là bảng kết quả thử nghiệm trên máy tính của thuật toán dạng bảng. Thuật toán được cài đặt trên ngôn ngữ lập trình Pascal, một ngôn ngữ có cấu trúc rõ ràng, sáng sủa. Mục đích của chương trình là để minh họa quá trình cài đặt và test thuật toán (đoạn mã cài đặt có ở phần phụ lục). Phương pháp thử nghiệm được thực hiện ở đây là sinh ngẫu nhiên dữ liệu đầu vào với kích thước cho trước và lưu trữ trong một tập tin văn bản (input). Sau đó chương trình sẽ đọc tập tin này, xử lý theo thuật toán đã cài đặt, cuối cùng là xuất kết quả ra tập tin văn bản khác (output). Bảng 2.2. Thời gian thực hiện của thuật toán đa thức dạng bảng * Kích thước dữ liệu vào (m x n) Thời gian thực hiện (giây) 40 x 20 80 x 20 100 x 20 0.1099 0.2198 0.3846 40 x 40 80 x 40 100 x 40 0.2747 0.8791 1.3187 40 x 80 80 x 80 100 x 80 0.8791 2.9670 5.2198 100 x 100 8.0769 * Ghi chú: Quá trình tối ưu cài đặt đệ quy trên máy tính Laptop IBM, Pentium 3 - 1.13GHz, 256 MB RAM. Ngoài ra, để minh họa trực quan cho quá trình thực hiện của thuật toán, một chương trình nhỏ được thực hiện cho những bài toán kích thước nhỏ. Dưới đây là một số hình ảnh của chương trình minh họa trực quan. 47 Quá trình thực hiện của mỗi thuật toán 48 Minh họa biểu diễn và so sánh các thuật toán