Luận văn Thuật toán xấp xỉ ứng dụng vào một số bài toán lớp Np

ang Thái Nguyên - 2020 i LỜI CẢM ƠN Để hoàn thành luận văn này trước tiên, em xin được gửi lời cảm ơn sâu sắc tới thầy giáo hướng dẫn TS. Vũ Vinh Quang đã tận tình hướng dẫn và đưa ra nhiều ý kiến đóng góp cho em trong suốt quá trình thực hiện và hoàn thành luận văn này. Em cũng xin được gửi lời cảm ơn đến các thầy giáo, cô giáo Trường Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên trực tiếp giảng dạy và truyền đạt những kiến thức quý báu cho em trong suốt quá trình học tập tại trường. Mặc dù đã cố gắng hoàn thành luận văn trong phạm vi và khả năng của mình, tuy nhiên sẽ không tránh khỏi những thiếu sót. Em rất mong nhận được sự cảm thông và chỉ bảo của quý thầy cô và các bạn. Em xin chân thành cảm ơn. ii LỜI CAM ĐOAN Tôi xin cam đoan Luận văn “Thuật toán xấp xỉ ứng dụng vào một số bài toán lớp NP” là do tôi thực hiện dưới sự hướng dẫn trực tiếp của thầy TS. Vũ Vinh Quang. Các kết quả, số liệu nêu trong luận văn là trung thực. Tất cả những tham khảo từ những nghiên cứu liên quan đều được nêu rõ nguồn gốc trong danh mục tài liệu tham khảo và được chỉ rõ tham khảo trong tài liệu nào. Mọi sao chép không hợp lệ và vi phạm quy chế đào tạo, tôi xin chịu hoàn toàn trách nhiệm. HỌC VIÊN Nguyễn Hữu Chuyên iii MỤC LỤC LỜI CẢM ƠN ............................................................................................................ I LỜI CAM ĐOAN .................................................................................................... II DANH MỤC CÁC BẢNG ....................................................................................... V DANH MỤC CÁC HÌNH ........................................................................................ V LỜI MỞ ĐẦU ............................................................................................................ 1 CHƯƠNG 1................................................................................................................ 2 MỘT SỐ KIẾN THỨC CƠ BẢN ............................................................................ 2 1.1 Thuật toán ............................................................................................................ 2 1.1.1 Khái niệm bài toán ........................................................................................ 2 1.1.2. Khái niệm thuật toán .................................................................................... 2 1.1.3. Các yêu cầu của thuật toán .......................................................................... 2 1.1.4 Các phương pháp mô tả thuật toán .............................................................. 3 1.2. Độ phức tạp của thuật toán ............................................................................... 4 1.2.1. Chi phí phải trả cho một quá trình tính toán .............................................. 4 1.2.2. Thời gian thực hiện giải thuật ..................................................................... 4 1.2.3. Độ phức tạp của thuật toán .......................................................................... 5 1.2.4. Các qui tắc xác định độ phức tạp thuật toán .............................................. 6 1.3. Vấn đề phân lớp các bài toán. ........................................................................... 6 1.4 Mô hình Bài toán Knapsack ............................................................................... 7 Hình 1.1 Bài toán xếp ba lô dạng 0-1 ................................................................... 8 CHƯƠNG 2.............................................................................................................. 13 MỘT SỐ THUẬT TOÁN XẤP XỈ ........................................................................ 13 2.1 Khái niệm về thuật toán xấp xỉ ........................................................................ 13 2.2 Phương pháp quy hoạch động ........................................................................ 15 2.2.1 Một số khái niệm ......................................................................................... 15 2.2.2 Các bước thực hiện ..................................................................................... 16 2.3 Phương pháp tham lam .................................................................................... 19 2.3.1 Giới thiệu chung .......................................................................................... 19 2.3.2 Đặc trưng của phương pháp tham lam ...................................................... 20 2.3.3 Các thành phần cơ bản ............................................................................... 20 iv 2.3.4 Các bước xây dựng thuật toán tham lam ................................................... 21 2.3.5 Mô hình thuật toán tham lam ..................................................................... 22 2.4 Thuật toán Di truyền GA ................................................................................. 27 2.4.1 Giới thiệu ..................................................................................................... 27 2.4.2 Các khái niệm cơ bản .................................................................................. 28 2.4.3 Thuật toán GA ............................................................................................. 29 2.4.4 Cơ chế thực hiện GA ................................................................................... 29 CHƯƠNG 3.............................................................................................................. 37 MÔ HÌNH BÀI TOÁN LẬP LỊCH TRONG BỆNH VIỆN ................................ 37 3.1 Đặt vấn đề .......................................................................................................... 37 3.2 Giới thiệu tổng quan bệnh viện A .................................................................... 37 3.3 Các mô hình phân công các ca trực ................................................................. 40 3.3.1 Bài toán phân công trực tại các khoa chuyên môn ................................... 41 3.3.2 Bài toán phân công trực tại các Phòng khám............................................ 45 KẾT LUẬN .............................................................................................................. 60 TÀI LIỆU THAM KHẢO ...................................................................................... 61 PHẦN PHỤ LỤC ..................................................................................................... 62 v DANH MỤC CÁC BẢNG STT Tên bảng 1 Bảng 2.1 Mô tả bảng phương án của phương pháp quy hoạch động 2 Bảng 3.1: Ma trận ràng buộc B 3 Bảng 3.2: Ma trận ràng buộc Y 4 Bảng 3.3: Lịch trực các buổi trong tuần 5 Bảng 3.4: Số buổi trực đối với các Bác sĩ – Y tá 6 Bảng 3.5: Bảng các Bác sĩ phù hợp với chuyên môn phòng khám (tham lam) 7 Bảng 3.6: Bảng các Y tá phù hợp với chuyên môn phòng khám (tham lam) 8 Bảng 3.7: Bảng các Bác sĩ sẵn sàng nhận buổi trực (tham lam) 9 Bảng 3.8: Bảng các Y tá sẵn sàng nhận buổi trực (tham lam) 10 Bảng 3.9: Lịch trực tại các phòng trong các buổi (tham lam) 11 Bảng 3.10: Số buổi trực đối với các Bác sĩ (tham lam) 12 Bảng 3.11: Số buổi trực đối với các Y tá (tham lam) 13 Bảng 3.12: Bảng các Bác sĩ phù hợp với chuyên môn phòng khám (GA) 14 Bảng 3.13: Bảng các Y tá phù hợp với chuyên môn phòng khám (GA) 15 Bảng 3.14: Bảng các Bác sĩ sẵn sàng nhận buổi trực (GA) 16 Bảng 3.15: Bảng các Y tá sẵn sàng nhận buổi trực (GA) 17 Bảng 3.16: Lịch trực tại các phòng trong các buổi (GA) 18 Bảng 3.17: Số buổi trực đối với các Bác sĩ (GA) 19 Bảng 3.18: Số buổi trực đối với các Y tá (GA) DANH MỤC CÁC HÌNH STT Tên hình Hình 1 Khối bắt đầu (Kết thúc) 2 Khối kiểm tra 3 Khối tính toán 4 Cung định hướng 1 LỜI MỞ ĐẦU Trong thực tế, lớp các bài toán giải được bằng các thuật toán có thời gian đa thức là không nhiều mà chủ yếu là chúng ta gặp các bài toán tối ưu mà việc tìm lời giải đúng của bài toán không trong thời gian đa thức (còn gọi là lớp NP, NPC). Để giải quyết các bài toán này, nói chung người ta phải xây dựng các thuật toán tìm nghiệm gần đúng tối ưu cho bài toán. Các thuật toán như vậy thường được gọi là các thuật toán xấp xỉ hay là các thuật toán gần đúng. Các thuật toán này hiện nay là mục tiêu nghiên cứu quan trọng trong công nghệ thông tin đặc biệt là đối với lớp các bài toán dữ liệu lớn. Nội dung chính của luận văn là nghiên cứu cơ sở toán học của các thuật toán gần đúng giải lớp các bài toán thuộc lớp NP và NPC, tìm hiểu chi tiết các bước mô tả thuật toán và các yêu cầu thiết kế các thuật toán. Trên cơ sở các thuật toán đã nghiên cứu, luận văn phân tích một số các bài toán thuộc lớp NP, NPC, xây dựng lời giải đúng và gần đúng, đánh giá kết quả. Dự kiến nội dung báo cáo của luận văn gồm: Phần mở đầu, 3 chương chính, phần kết luận, tài liệu tham khảo, phụ lục. Bố cục được trình bày như sau: Phần mở đầu của luận văn đưa ra lý do chọn đề tài và hướng nghiên cứu chính của luận văn. Chương 1: Trình bày các kiến thức cơ bản về thuật toán và độ phức tạp thuật toán bao gồm: khái niệm cơ bản về thuật toán, Vấn đề đánh giá độ phức tạp thuật toán. Phân lớp các bài toán dựa trên độ phức tạp của thuật toán. Chương 2: Trình bày cơ sở toán học của một số thuật toán xấp xỉ bao gồm: thuật toán tham lam, thuật toán quy hoạch động, Thuật toán GA và một số mô hình thực tế về các bài toán NP, NPC như: Bài toán Knapsack , bài toán đổi tiền, bài toán Domino cùng với các thuật giải tương ứng. Chương 3: Nghiên cứu mô hình 2 bài toán lập lịch trực các ca tại bệnh viện A Thái Nguyên bao gồm: Tìm hiểu xây dựng mô hình bài toán, xây dựng các ràng buộc thực tế và hàm mục tiêu, thiết lập các điều kiện tối ưu. Xây dựng thuật giải các bài toán bằng thuật toán tham lam và GA và cài đặt thuật toán trên máy tính điện tử. Tất cả các thuật toán tình bày trong luận văn được cài đặt trên máy tính điện tử bằng các ngôn ngữ lập trình C++ và Matlab. 2 CHƯƠNG 1 MỘT SỐ KIẾN THỨC CƠ BẢN VỀ THUẬT TOÁN VÀ ĐỘ PHỨC TẠP CỦA THUẬT TOÁN Nội dung chính của chương 1 trình bày các kiến thức cơ bản về thuật toán và độ phức tạp thuật toán bao gồm: khái niệm cơ bản về thuật toán, Vấn đề đánh giá độ phức tạp thuật toán. Phân lớp các bài toán dựa trên độ phức tạp của thuật toán. Các kiến thức cơ bản được tham khảo trong các tài liệu [1, 2, 3, 5, 6, 7] 1.1 Thuật toán 1.1.1 Khái niệm bài toán Một bài toán trong tin học là một bài toán thỏa mãn: xuất phát từ bộ INPUT đầu vào, chúng ta phải thu được bộ OUTPUT đầu ra. Một số vấn đề cần quan tâm + Bài toán được giải bằng máy tính điện tử + Cần làm rõ: dữ liệu cần được đưa vào máy tính (Input) là gì và cần lấy ra (Output) thông tin gì? + Làm thế nào để từ Input ta có được Output? (Thuật toán giải) Hiển nhiên đối với bài toán tin học là nghiên cứu thuật toán giải bài toán tương ứng. 1.1.2. Khái niệm thuật toán Định nghĩa 1.1: Thuật toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự nhất định để sau khi thực hiện dãy các thao tác đó, từ input ta có output cần tìm [1]. Trong lý thuyết thuật toán, cụm từ “thuật toán” đôi khi người ta dùng bằng một từ khác là “giải thuật”. 1.1.3. Các yêu cầu của thuật toán Thuật toán phải đảm bảo được các yêu cầu sau đây: - Tính tổng quan: thuật toán phải đúng đối với mọi bộ dữ liệu đầu vào. 3 - Tính xác định: Các bước của thuật toán phải được trình bày rõ ràng, mạch lạc, đảm bảo cho người đọc chỉ hiểu theo một nghĩa duy nhất. - Tính khả thi: Thuật toán phải thực hiện được, nghĩa là ta có thể sử dụng máy tính kết hợp giữa các ngôn ngữ lập trình để thể hiện thuật toán trong thời gian hữu hạn. - Tính dừng: Nếu dữ liệu vào thỏa mãn điều kiện đầu vào thì thuật toán phải kết thúc và cho ra kết quả sau một số hữu hạn bước. - Tính chính xác (tính đúng đắn): Thuật toán phải cho kết quả chính xác và thể hiện đúng đắn trên cơ sở toán học. - Tính tối ưu: Thuật toán phải có chi phí về không gian bộ nhớ ít nhất và chạy trong thời gian nhanh nhất. 1.1.4 Các phương pháp mô tả thuật toán Thuật toán được thể hiện bằng một trong các cách sau:  Phương pháp liệt kê: Liệt kê lần lượt các bước để thực hiện thuật toán, tại mỗi bước ta sử dụng các ký hiệu toán học kết hợp với ngôn ngữ tự nhiên (cách này ít khi dùng).  Phương pháp sử dụng sơ đồ khối Sử dụng ba loại hình khối để thể hiện là: hình elip chỉ điểm bắt đầu hay kết thúc, hình thoi chỉ khối kiểm tra và hình chữ nhật chỉ khối tính toán. Có một cung định hướng để chỉ hướng đi của thuật toán. Khối bắt đầu (kết thúc) Khối kiểm tra Khối tính toán Cung định hướng Ta kết hợp ba loại hình khối và cung định hướng này để biểu diễn thuật toán.  Mô tả thuật toán bằng các chương trình Sử dụng ngôn ngữ lập trình để thể hiện thuật toán, cấu trúc chặt chẽ của các ngôn ngữ lập trình cho phép chúng ta thể hiện thuật toán một cách rõ ràng và dễ hiểu. Phương pháp này được áp dụng rộng rãi nhất. Trong các tài liệu, các thủ tục thể hiện thuật toán thường được mô tả bằng ngôn ngữ tựa Algol. 4 1.2. Độ phức tạp của thuật toán 1.2.1. Chi phí phải trả cho một quá trình tính toán Xét một quá trình tính toán, chi phí phải trả cho một quá trình tính toán bao gồm: + Chi phí về không gian: bộ nhớ - số ô nhớ cần sử dụng trong quá trình tính toán. + Chi phí về thời gian: thời gian cần sử dụng cho một quá trình tính toán. Nếu cho một thuật toán A. Thuật toán này thực hiện trên bộ dữ liệu e. Khi đó thuật toán A phải trả 2 giá: giá về không gian là LA(e), giá về thời gian là TA(e), e là bộ dữ liệu vào. Nhận xét: cùng một thuật toán A mà xác định thực hiện trên các bộ dữ liêu khác nhau sẽ trả các giá khác nhau. Khi đó ta có các khái niệm về chi phí phải trả trong các trường hợp như sau: + Chi phí phải trả trong trường hợp xấu nhất ứng với bộ dữ liệu xấu nhất so với Output + Chi phí phải trả trung bình: là tổng số các chi phí khác nhau ứng với các bộ số liệu chia cho tổng số số bộ số liệu. + Chi phí phải trả tiệm cận: Đó là biểu thức biểu diễn tốc độ tăng của chi phí thực tế phải trả. Nó có giá trị tiệm cận với chi phí thực tế. Nhận xét: Ngày nay do sự phát triển không ngừng của khoa học công nghệ kỹ thuật điện tử nên chi phí về bộ nhớ không còn là vấn đề cần thiết phải bàn tới mà ta chỉ quan tâm tới chi phí phải trả về thời gian thực hiện giải thuật. Từ đây ta chỉ xét đến thời gian thực hiện giải thuật T(n), hay đó chính là độ phức tạp của thuật toán. 1.2.2. Thời gian thực hiện giải thuật Với một bài toán, không chỉ có một giải thuật. Chọn một giải thuật đưa tới kết quả nhanh là một đòi hỏi thực tế. Nhưng căn cứ vào đâu để có thể nói được giải thuật này nhanh hơn giải thuật kia? Có thể thấy ngay: thời gian thực hiện một giải thuật, (hay chương trình thể hiện một giải thuật đó) phụ thuộc vào rất nhiều yếu tố. Một yếu tố cần chú ý trước tiên đó là kích thước của dữ liệu đưa vào. Chẳng hạn thời gian sắp xếp một dãy số 5 phải chịu ảnh hưởng của số lượng các số thuộc dãy số đó. Nếu gọi n là số lượng này (kích thước của dữ liệu vào) thì thời gian thực hiện T của một giải thuật phải được biểu diễn như một hàm của n: T(n). Các kiểu lệnh và tốc độ xử lý của máy tính, ngôn ngữ viết chương trình và chương trình dịch ngôn ngữ ấy đều ảnh hưởng tới thời gian thực hiện; nhưng những yếu tố này không đồng đều với mọi loại máy trên đó cài đặt giải thuật, vì vậy không thể đưa chúng vào khi xác lập T(n). Điều đó có nghĩa là T(n) không thể được biểu diễn thành đơn vị thời gian bằng giây, bằng phút được. Tuy nhiên, không phải vì thế mà không thể so sánh được các giải thuật về mặt tốc độ. Nếu như thời gian thực 2 hiện của một giải thuật là T1(n) = c.n và thời gian thực hiện một giải thuật khác là T2(n) = k.n (với c và k là một hằng số nào đó), thì khi n khá lớn, thời gian thực hiện giải thuật T2 rõ ràng ít hơn so với thời gian thực hiện giải thuật T1. Như vậy, nếu nói thời gian thực hiện giải thuật bằng T(n) tỉ lệ với n2 hay tỉ lệ với n cũng cho ta ý niệm về tốc độ thực hiện giải thuật đó khi n khá lớn (với n nhỏ thì việc xét T(n) không có ý nghĩa). Cách đánh giá thời gian thực hiện giải thuật độc lập với máy tính và các yếu tố liên quan với máy như vậy sẽ dẫn tới khái niệm về cấp độ lớn của thời gian thực hiện giải thuật hay còn gọi là độ phức tạp tính toán của giải thuật. 1.2.3. Độ phức tạp của thuật toán Định nghĩa 1.2 : Một hàm f(n) được xác định là O(g(n)), kí hiệu f(n) = O(g(n)) nếu tồn tại các hằng số C và số nguyên n0 sao cho f(n) ≤ Cg(n) với mọi n ≥ n0 Thông thường các hàm thể hiện độ phức tạp tính toán của giải thuật có dạng: 2 3 n n n n O(log2n), O(n), O(nlog2n), O(n ), O(n ), O(2 ), O(n!), O(n ). Các hàm như 2 , n 3 2 được gọi là hàm loại mũ. Các dạng như n , n , nlog2n, log2n được gọi là các hàm loại đa thức. Giải thuật với thời gian thực hiện có cấp hàm đa thức thì thường hiệu quả và chấp nhận được. 6 1.2.4. Các qui tắc xác định độ phức tạp thuật toán  Quy tắc tổng: Giả sử T1(n) và T2(n) là thời gian thực hiện của 2 đoạn chương trình P1 và P2 kế tiếp nhau T1(n) = O(f(n)); T2(n) = O(g(n)) thì thời gian thực hiện P1 rồi P2 tiếp theo sẽ là:T1(n)+ T2(n)=O(max(f(n), g(n))).  Quy tắc nhân: Nếu tương ứng với P1 và P2 là T1(n)=O(f(n)); T2(n) = O(g(n)) thì thời gian thực hiện P1 và P2 lồng nhau sẽ là: T1(n).T2(n) = O(f(n).g(n)). Chú ý: Trong các ngôn ngữ lập trình, chúng ta có thể đánh giá + Thời gian thực hiện mỗi câu lệnh Gán, Read, Write là O(1). + Thời gian thực hiện mỗi chuỗi tuần tự các câu lệnh được tính theo quy tắc cộng. + Thời gian thực hiện cấu trúc If (điều kiện) then ... được tính bằng thời gian thực hiện câu lệnh sau then hoặc sau else. Còn câu lệnh điều kiện thường là O(1). + Thời gian thực hiện vòng lặp được tính là tổng trên tất cả số lần lặp thời gian thực hiện thân vòng lặp. Nếu thời gian thực hiện thân vòng lặp là hằng số thì thời gian thực hiện vòng lặp là tích của số lần lặp với thời gian thực hiện thân vòng lặp. 1.3. Vấn đề phân lớp các bài toán. Xét một bài toán tin học bất kì, chúng ta quan tâm đến các bài toán có lời giải. Vì độ phức tạp giải thuật đối với mỗi bài toán là khác nhau, trên cơ sở đó các bài toán cũng được phân chia thành các lớp thông qua độ phức tạp thuật toán giải chúng. Chúng ta xét các khái niệm sau:  Lớp bài toán P (Lớp P-Polynomial time): là lớp các bài toán có thể giải được bằng thuật toán đơn định đa thức có độ phức tạp đa thức  Lớp bài toán NP (Lớp NP - Nondeterministic Polynomial ): là lớp các bài toán có thể giải được bằng các thuật toán không đơn định đa thức. Hiện nay chúng ta đang chấp nhận P  NP.  Lớp NPC + Khái niệm dẫn về được: Bài toán B được gọi là dẫn về được bài toán A một cách đa thức nếu có một thuật toán đơn định đa thức để giải bài toán A thì cũng có một thuật toán đơn định đa thức để giải bài toán B. ký hiệu B  A. 7 + Bài toán NP – khó (NP hard): Bài toán A được gọi là NP – khó nếu có bài toán L  A với  L  NP. + Bài toán NP đầy đủ: Bài toán A được gọi là NP đầy đủ (NP-Complate) nếu: A là NP-khó và ANP. Từ đây chúng ta định nghĩa về lớp NPC như sau: Định nghĩa 1.3: Lớp NPC là lớp các bài toán NP đầy đủ, có độ phức tạp hàm mũ. Qua đó cho thấy: P  NPC = Ø 1.4 Mô hình Bài toán Knapsack Mô hình bài toán Knapsack là vấn đề đã được nghiên cứu trong hơn một thế kỷ từ năm 1897 cho đến nay. Việc nghiên cứu bài toán Knapsack đã được đưa ra đầu tiên trong các công trình của nhà toán học Tobias Dantzig (1884-1956). Các công trình tiếp theo được giới thiệu lần đầu tiên bởi Gallo, Hammer và Simeone vào năm 1960. Một công trình nghiên cứu các tác giả thuộc Đại học Stony Brook năm 1998 cho thấy rằng trong số 75 vấn đề về các bài toán NPC, bài toán Knapsack là 1 trong 18 bài toán quan trọng nhất trong lĩnh vực Toán và Công nghệ thông tin. Bài toán KNAPSACK - Bài toán xếp ba lô là một bài toán tối ưu tổ hợp. Bài toán được đặt tên từ vấn đề chọn những gì quan trọng có thể nhét vừa vào trong một cái túi (với giới hạn khối lượng) để mang theo trong một chuyến đi. Các bài toán tương tự thường xuất hiện trong ngành kinh doanh, lý thuyết tổ hợp, lý thuyết độ phức tạp tính toán, lý thuyết mật mã học và một số lĩnh vực trong toán ứng dụng. Bài toán được phát biểu tổng quát như sau: Có N đồ vật kí hiệu là xx1,..., n . Mỗi đồ vật xj có một giá trị p j và một thể tích w j , jN1, . Thể tích mà có thể chứa trong ba lô là M . Hãy xác định phương án chọn các đồ vật để sao cho: số đồ vật chứa vừa trong ba lô và tổng giá trị các đồ vật được chọn là lớn nhất có thể được. 8 Hình 1.1 Bài toán xếp ba lô dạng 0-1 Hình 1.1 trên là ví dụ về một bài toán xếp ba lô giới hạn 1 chiều: chọn các hộp nào để làm cực đại lượng tiền trong khi giữ được tổng khối lượng dưới 15 kg? Bài toán đa chiều có thể xét đến khối lượng riêng và kích thước của các hộp, đó là bài toán xếp vali điển hình Trong lớp các bài toán Knapsack, người ta thường đưa ra một số dạng bài toán điển hình như sau: + Bài xếp ba lô 0-1 là bài toán không hạn chế số đồ vật thuộc mỗi loại, bài toán được mô hình hóa như sau: n n Cực đại hóa hàm F(X )   p j x j sao cho  w j x j  M trong đó j1 j1 X  x1, x2 ,..., xn , x j  0,1,j 1,n . + Bài xếp ba lô bị chặn hạn chế số đồ vật thuộc mỗi loại không được vượt quá một lượng xác định. Bài xếp ba lô bị chặn có thể được phát biểu bằng mô hình toán học như sau: n n Cực đại hóa hàm F(X )   p j x j sao cho  w j x j  M trong đó j1 j1 X   x1, x2 ,..., xn , x j  0,1, .   x j  0,bj ,bj  N,j 1,n. 9 Một trường hợp đặc biệt của bài toán Knapsack là bài toán thỏa mãn các tính chất sau đây:  Là một bài toán quyết định  Là một bài toán xếp ba lô dạng 0-1  Phương án tối ưu là số đồ vật xếp vừa khít ba lô. Đối với dạng bài toán này, trong thực tế thường xuất hiện ở các dạng sau đây: Dạng 1: Cho trước một tập các số nguyên, tồn tại hay không một tập con có tổng đúng bằng 0? Dạng 2: Cho một tập các số nguyên dương, tồn tại hay không một tập con có tổng đúng bằng M ? Các bài toán này được gọi là bài toán tổng các tập con (subset sum problem) được sử dụng nhiều trong ngành mật mã học. Tổng quát hóa, từ mô hình bài toán KNAPSACK cũng có rất nhiều cách phát biểu khác nhau. Sau đây là một số cách phát biểu bài toán: Bài toán tập con cực đại: Cho một tập hữu hạn Uuin i,1,... , mỗi phần tử uUi  có kích cỡ Su()i và số tự nhiên B . Hãy xác định một tập con UU'  sao cho SuB() . Trong đó, uU ' .  i i Knapsack thuộc lớp bài toán NPC. Nói chung không có thuật toán hữu hiệu nào để giải nó cho trường hợp bất kỳ. Điều này không có nghĩa là tất cả các trường hợp đều có cùng độ phức tạp. Nhận xét: + Bài toán trên có thể xác định lời giải chính xác bẳng thuật toàn duyệt toàn bộ theo tư tưởng như sau: Hãy duyệt mọi tổ hợp của các đồ vật, ứng với mỗi tổ hợp (i1,i2,..,ik) thử điều kiện w(i1)+w(i2)++w(ik) = M để xác định nghiệm đúng. Khi đó 1 2n- 1 n n số phương án được duyệt chính bằng CCCCn+ n +... n + n ; 2 tức là chúng ta có độ phức tạp của thuật toán là hàm mũ. 10 + Chúng ta có thể giải bài toán bằng thuật toán không đơn định đa thức như sau: sử dụng hàm: CHOICE(0,1): là hàm chọn các đồ vật. Khi đó bài toán được đưa về bài toán sau đây Liệu có tồn tại tập chỉ số T {1,2,.. ,n} thỏa mãn wi  M . iT Khi đó bài toán được giải bằng thuật toán sau đây: For i:=1 to n do xi:= CHOICE({0,1}); n if  xi ai =B then TRUE else FALSE i1 Thuật toán trở thành thuật toán không đơn định đa thức với độ phức tạp O(n). + Bài toán trên có thể đưa về dạng tổng quát hơn bằng cách thay Output bằng: “Hãy xác định nhóm đồ vật đặt trong balo sao cho phần thừa còn lại là ít nhất”. Khi đó việc giải bài toán cũng được thực hiện tương tự, tuy nhiên chúng ta phải đưa thêm hàm mục tiêu f=b-(a(i1)+a(i2)++a(ik)). Khi đó phương án cần xác định là phương án thỏa mãn f đạt giá trị nhỏ nhất (f>=0).  Bài toán KNASPACK mở rộng Input: + Cho n đồ vật, đồ vật thứ i có thể tích là wi, có giá trị là pi + Cho 1 ba lô có thể tích M Output: Hãy xác định nhóm đồ vật thỏa mãn: tổng thể tích không vượt quá ba lô đồng thời tổng giá trị là lớn nhất Nhận xét: + Bài toán trên có thể xác định lời giải chính xác bằng thuật toán duyệt toàn bộ theo tư tưởng như sau: Kí hiệu (x12 , x ,... xn ) là một phương án lựa chọn các đồ vật với xi Î {0,1} . Khi đó hãy duyệt mọi phương án , ứng với mỗi phương án xác định điều kiện w1x 1+ w 2 x 2 + ... + wnn x £ M . Nếu thỏa mãn thì 11 xác định tiếp giá trị hàm mục tiêu fXp()... xpxpx=+++1122 nn từ đó xác định phương án tốt nhất. Hiển nhiên bài toán đưa về bài toán duyệt mọi dãy nhị phân có độ dài n với độ phức tạp hàm mũ. Thuật toán giải được mô tả như sau: using namespace std; int X[N],W[N],M,P[N],n,fmax,Xluu[N]; void input() { cout>n; cout>M; cout<<"Nhap the tich cac do vat: ";printf("\n"); for (int i=1;i>W[i];} cout<<"Nhap gia tri cac do vat : ";printf("\n"); for (int i=1;i>P[i];} fmax=0; } void output() { int f,T; f=0;T=0; for (int i=1;i<=n;i++) {T=T+X[i]*W[i];f=f+X[i]*P[i];} if ((Tfmax)) { fmax=f; for (int i=1;i<=n;i++) Xluu[i]=X[i];} } void Try(int k) { int j; for (j=0;j<=1;j++) { X[k]=j;if (k==n) output();else Try(k+1);} } int main() { input(); Try(1); cout<<"Phuong an toi uu: "; for (int i=1;i<=n;i++) cout<<Xluu[i]<<" "; cout<<"Gia tri toi uu fmax= "<<fmax; } + Tương tự, chúng ta có thể giải bài toán bằng thuật toán không đơn định đa thức như sau: sử dụng hàm: CHOICE(0,1): là hàm chọn các đồ vật. Khi đó bài toán 12 được đưa về bài toán sau đây: Liệu có tồn tại tập chỉ số T  {1,2,.. ,n} thỏa mãn n n wiixM và  pi xi đạt max. Khi đó bài toán được giải bằng thuật toán sau i1 i1 đây: For i:=1 to n do xi:= CHOICE({0,1}); n if  xiiw else FALSE i1 Thuật toán trở thành thuật toán không đơn định đa thức với độ phức tạp O(n). + Bài toán Knaspack có thể giải bằng thuật toán GA với cấu trúc gen là dãy nhị phân và toán tử lai ghép đa điểm hoặc lai ghép mặt nạ được trình bày trong chương 2. Kết luận: Trong chương 1, luận văn trình bày những khái niệm cơ bản về bài toán - thuật toán trong tin học, khái niệm về độ phức tạp của thuật toán và các nguyên tắc đánh giá độ phức tạp. Trên cơ sở đó đưa ra nguyên tắc phân lớp các bài toán để tiến hành lựa chọn giải thuật tốt nhất giải các lớp bài toán trong thực tế. Đưa ra mô hình bài toán Knaspack là một mô hình điển hình của lớp các bài toán NP. Các kiến thức này làm cơ sở để phân tích và thiết kế các thuật toán được trình bày trong các chương tiếp sau. 13 CHƯƠNG 2 MỘT SỐ THUẬT TOÁN XẤP XỈ Nội dung chính của chương 2 sẽ nghiên cứu một số thuật toán xấp xỉ đã được nghiên cứu trong các kĩ thuật thiết kế thuật toán như: Thuật toán tham lam, thuật toán quy hoạch động, thuật toán di truyền GA, cùng các bài toán mẫu mực trong thực tế. Các thuật toán đã được tham khảo trong các tài liệu [3, 4, 5, 6, 7, 8]. Việc mô phỏng các thuật toán được thực hiện trên nền ngôn ngữ lập trình C++ hoặc Matlab. 2.1 Khái niệm về thuật toán xấp xỉ Nhiều bài toán có ý nghĩa rất quan trọng trong thực tiễn lại là NP đầy đủ. Nếu là một bài toán NP đầy đủ, ta không thể tìm một thuật toán thời gian đa thức để giải nó chính xác. Có hai cách tiếp cận để khắc phục tính đầy đủ NP. Thứ nhất: nếu các đầu vào thực tế là nhỏ, một thuật toán có thời gian thực hiện hàm mũ có thể hoàn toàn chấp nhận được Thứ hai: vẫn có thể tìm các giải pháp gần tối ưu trong thời gian đa thức (hoặc trong trường hợp xấu nhất hoặc tính trung bình). Trong thực tế để tính gần tối ưu thường là đủ. Một thuật toán trả về các giải pháp gần tối ưu được gọi là một thuật toán xấp xỉ. Xét một bài toán tối ưu hóa, ở đó mỗi giải pháp có thể đưa ra có một mức hao phí dương, và ta muốn tìm giải pháp gần tối ưu. Tùy thuộc vào bài toán, một giải pháp gần tối ưu có thể được định nghĩa là một giải pháp có mức hao phí khả dĩ cực đại hoặc một giải pháp có mức hao phí khả dĩ cực tiểu, bài toán có thể là bài toán cực đại hóa hoặc cực tiểu hóa. Một số thuật toán xấp xỉ cho bài toán có một cận tỷ số P(n) nếu với bất kỳ đầu vào có kích cỡ n , mức hao phí C của giải pháp mà thuật toán xấp xỉ tạo sẽ nằm trong một thừa số p(n) của mức hao phí C* của một giải pháp tối ưu: Max  C C *   ,  ≤ p(n)  *   C C  14 Định nghĩa này áp dụng cả bài toán cực đại hóa lẫn cực tiểu hóa. Với một bài C * toán cực đại hóa, 0 < C ≤ C*, và tỷ số cho ra thừa số qua đó với mức hao phí C của một giải pháp tối ưu lớn hơn mức hao phí của một giải pháp xấp xỉ. Cũng vậy, C với một bài toán cực tiểu hóa, 0 < C* ≤C, và tỷ số cho ra thừa số qua đó mức C * hao phí của một giải pháp xấp xỉ lớn hơn mức hao phí của một giải pháp tối ưu. Bởi tất cả các giải pháp được mặc nhận có mức hao phí dương, các tỷ số này luôn được định nghĩa rõ ràng. Cận tỷ số của một thuật toán xấp xỉ không bao giờ nhỏ hơn 1, C bởi  1. Một thuật toán xấp xỉ có một cận lỗi tương đối ε(n) nếu C* C  C *   n C * Một lược đồ xấp xỉ cho một bài toán tối ưu hóa là một thuật toán xấp xỉ chấp nhận không những một bộ dữ liệu vào của bài toán, mà còn một giá trị ε>0 làm đầu vào sao cho với bất kỳ ε, cố định, lược đồ là một thuật toán xấp xỉ có cận lỗi tương đối ε. Ta nói rằng một lược đồ xấp xỉ có thời gian đa thức nếu với bất kỳ ε > 0 cố định, lược đồ chạy trong thời gian đa thức trong kích cỡ n củ...N s1=s1+A(l)*con1(l); 33 end; if s1<=b socon=socon+1; Quan_the(socon,:)=con1; end; s2=0; for l=1:N s2=s2+A(l)*con2(l); end; if s2<=b socon=socon+1; Quan_the(socon,:)=con2; end; end; end; %Ket thuc lai ghep % Chon loc for i=1:socon f(i)=0; for j=1:N f(i)=f(i)+Quan_the(i,j)*C(j); end; end; for i=1:socon-1 for j=i+1:socon if f(i)<f(j) tgf=f(i);f(i)=f(j);f(j)=tgf; tgz=Quan_the(i,:);Quan_the(i,:)=Quan_the(j,:);Quan_the(j,:)=tgz; end; end; end; end; %ket thuc GA % Phuong an toi uu phuong_an_toi_uu=Quan_the(1,:) gia_tri_toi_uu=f(1) Ví dụ 2.5: Bài toán quân cờ DOMINO Định nghĩa 1: Một quân bài Domino là một bộ (a,b) trong đó được gọi a là số hàng trên, b là số hàng dưới. Định nghĩa 2: Phép lật quân được hiểu là một phép biến đổi bộ (a,b) thành bộ (b,a) Bài toán: Input: Cho n quân bài Domino (a1,b1),(a2,b2),...(an,bn) xếp thành một hàng ngang. 34 Output: Hãy xác định các phép lật quân để sao cho độ chênh lệnh giữa tổng các số hàng trên so với tổng các số hàng dưới đạt giá trị nhỏ nhất. a1 a2 .... an-1 an b1 b2 bn-1 bn Có thể thấy rằng mô hình bài toán trên cũng là bài toán thuộc lớp NP. Phân tích + Kí hiệu một phương án lật quân là một bộ X=(x1,x2,,xn) trong đó xk=1 tức là lật quân thứ k, xk=0 tức là không lật quân thứ k. Khi đó để tìm phương án lật quân tối ưu, chúng ta có thể sử dụng thuật toàn duyệt toàn bộ tất cả các phương án từ đó xác định phương án có độ chênh lệch nhỏ nhất. Kí hiệu hàm mục tiêu n fXcxab()os()()=-p å ikk k= 1 Chú ý: co s(0 )=1 ứng với trạng thái không lật quân, co s(p ) = -1 ứng với trạng thái lật quân Khi đó sử dụng thuật toán duyệt tất cả các dãy nhị phân độ dài n bằng thuật toán quay lui, ta có thể tìm được lời giải chính xác của bài toán. Tuy nhiên khi n là lớn thì thuật toán không khả thi vì độ phức tạp của thuật toán là O(n!) Sau đây chúng ta thiết kế thuật toán GA tìm lời giải xấp xỉ. + Kí hiệu 1 cá thể là X=(x1,x2,,xn) ứng một phương án lật quân trong đó xk=1 tức là lật quân thứ k, xk=0 tức là không lật quân thứ k. + Sử dụng phương pháp toán tử lai ghép đa điểm hoặc lại ghép mặt nạ + Quá trình chọn lọc luôn sử dụng hàm mục tiêu f(X). Khi đó thuật toán GA được mô tả bằng ngôn ngữ Matlab như sau function domino=domino(tren,duoi,KK) clc; N=length(tren);M=10;%popsize z=round(rand(M,N)); for i=1:M for j=1:N if z(i,j)==0 A(i,j)=tren(j); B(i,j)=duoi(j); else A(i,j)=duoi(j); B(i,j)=tren(j); end; end; 35 end; % thuat toan GA count=0;k=3; while count<KK count=count+1; socon=M; for i=1:M-1 for j=i+1:M bo=[A(i,:);B(i,:)];me=[A(j,:);B(j,:)]; for j1=1:k con1(:,j1)=bo(:,j1); con2(:,j1)=me(:,j1); end; for j2=k+1:N con1(:,j2)=me(:,j2); con2(:,j2)=bo(:,j2); end; socon=socon+1; A(socon,:)=con1(1,:); B(socon,:)=con1(2,:); socon=socon+1; A(socon,:)=con2(1,:); B(socon,:)=con2(2,:); end; end; for i=1:socon sa=0; sb=0; for j=1:N sa=sa+A(i,j); sb=sb+B(i,j); end; f(i)=abs(sa-sb); end; % Phep chon loc for i=1:socon-1 for j=i+1:socon if f(i)>f(j) tgf=f(i);f(i)=f(j);f(j)=tgf; tgA=A(i,:);A(i,:)=A(j,:);A(j,:)=tgA; tgB=B(i,:);B(i,:)=B(j,:);B(j,:)=tgB; end; end; end; % Dot bien con thu 7 vi tri so 5 36 tg=A(7,5);A(7,5)=B(7,5);B(7,5)=tg; end; phuong_an_toi_uu=A(1,:) B(1,:) Gia_tri_toi_uu=f(1) Nhận xét: Qua 2 ví dụ trên chúng ta có thể thấy + Thuật toán GA được thiết kế rất đơn giản, dễ hiểu, các bài toán tương tự thì cấu trúc của các chương trình là như nhau + Thuật toán chỉ sử dụng 1 vòng lặp duy nhất nên độ phức tạp là rất thấp + Các thao tác lai ghép, đột biến, thích nghi đều thao tác trên vector nên khả năng thiết kế thuật toán song song trên máy tính có bộ nhớ vector là rất khả thi + Vì là thuật toán xác suất nên lời giải là gần đúng và với các lần thử nghiệm khác nhau thì kết quả có thể là khác nhau. Kết luận: Nội dung chương 2 đã nghiên cứu một số nguyên tắc thiết kế các thuật toán giải bài toán tối ưu theo tư tưởng Heuristic tìm nghiệm xấp xỉ của các bài toán thuộc lớp NP. Các ví dụ minh họa chứng tỏ tính khả thi của các thuật toán ứng dụng cho các bài toán trong thực tế. 37 CHƯƠNG 3 MÔ HÌNH BÀI TOÁN LẬP LỊCH TRONG BỆNH VIỆN 3.1 Đặt vấn đề Trong thực tế hiện nay thì lớp các bài toán lập lịch là một lớp các bài toán quan trọng vì tính thời sự của nó, có thể kể đến các mô hình: Lập lịch kế hoạch sản xuất trong các xí nghiệp, lập lịch giảng dạy trong các trường học, lập lịch bay cho các sân bay, lập lịch trực cho các nhà máy, bệnh viện Đặc điểm chung của các bài toán lập lịch là do rất nhiều các ràng buộc từ điều kiện thực tế nên khó có thể tìm được lịch biểu tối ưu, trong khi đó lịch biểu vẫn phải lập và thực hiện do nhu cầu thường ngày của các đơn vị nhà trường và doanh nghiệp. Do đó việc sử dụng các thuật toán xấp xỉ để tìm lịch biểu gần tối ưu luôn luôn là một lựa chọn hợp lý nhiều khi là bắt buộc. Trong các mô hình thực tế hiện nay, mô hình phân công các ca trực tại các phòng khám của các bệnh viện là một mô hình đã và đang diễn ra thường xuyên liên tục. Mô hình này là mô hình chung cho tất cả các bênh viện tuy rằng với mỗi bệnh viện lại có những ràng buộc đặc thù riêng biệt. Vì lý do đó, trong luận văn, chúng tôi sẽ nghiên cứu chi tiết hai mô hình bài toán lập lịch các ca trực tại các bệnh viện. Mô hình được tham khảo từ bệnh viện A tỉnh Thái Nguyên. 3.2 Giới thiệu tổng quan bệnh viện A - Lịch sử phát triển Ngày 4/9/1965 Ty Y tế Bắc Thái thành lập Ban kiến thiết Bệnh viện dã chiến (tiền thân của Bệnh viện A) tại xã Vô Tranh, huyện Phú Lương. Ngày 31/12/1965, Uỷ ban Hành chính tỉnh Bắc Thái chính thức có Quyết định số 657/TCDC về việc tiếp nhận và điều động 73 cán bộ nhân viên do UBHC Khu chuyển giao về và cho thành lập Bệnh viện tỉnh Bắc Thái với quy mô 100 giường bệnh và chỉ tiêu biên chế 62 cán bộ, bao gồm: 02 bác sỹ, 01 dược sỹ đại học, 14 y sỹ, 17 y tá, 02 nữ hộ sinh, 02 dược tá, 01 xét nghiệm viên, 11 hộ lý. 38 Được sự quan tâm của Tỉnh uỷ, UBND tỉnh và Bộ Y tế, Chính Phủ đã quyết định đầu tư cho tỉnh một bệnh viện phụ sản quy mô 200 giường bệnh, diện tích xây dựng 14.000m2 với tổng vốn xây lắp 43 tỷ đồng và trang thiết bị 16 tỷ đồng, trên một phần đất trước đây đã được cấp tại tổ 19, phường Thịnh Đán, T.P Thái Nguyên. Từ năm 2012, số bệnh nhân điều trị nội trú tăng lên nhiều, số giường bệnh phải tăng lên hàng năm: Năm 2012: 380 giường, năm 2013: 420 giường, năm 2014: 470 giường, năm 2015: 510 giường. - Cơ cấu tổ chức Cơ cấu tổ chức các khoa phòng hiện tại: 31 khoa/phòng, gồm: phòng Tổ chức - Hành chính, phòng Tài chính - Kế toán, phòng Kế hoạch - Tổng hợp, phòng Vật tư thiết bị y tế, phòng Điều dưỡng, phòng Công tác xã hội, phòng Quản lý chất lượng, phòng Đào tạo và chỉ đạo tuyến. Các khoa trong Bệnh viện gồm: khoa Khám bệnh, khoa Hồi sức cấp cứu, khoa Nội tổng hợp, khoa Nội Tim mạch - Bảo vệ sức khỏe cán bộ, khoa Ngoại Tổng hợp, Khoa Ngoại Chấn thương, Khoa Sản, Khoa Nhi, Khoa Phẫu thuật - Gây mê hồi sức, Khoa Hồi sức cấp cứu, khoa Mắt, khoa Răng - Hàm - Mặt, khoa Tai - Mũi - Họng, khoa Dược, khoa Truyền nhiễm, Khoa Y học cổ truyền - Vật lý trị liệu, khoa Da liễu, khoa Hỗ trợ sinh sản, khoa Giải phẫu bệnh, khoa Kiểm soát nhiễm khuẩn, khoa Chẩn đoán hình ảnh, khoa Huyết học truyền máu, khoa Sinh hóa - Vi sinh. - Đội ngũ Hiện nay, tổng số cán bộ viên chức trong biên chế của Bệnh viện là 610, bao gồm 138 bác sĩ, trong đó có 16 bác sĩ chuyên khoa cấp II, 37 bác sĩ chuyên khoa cấp I, 5 thạc sĩ; 80 bác sĩ đa khoa, 28 dược sĩ , 351 điều dưỡng, kỹ thuật viên, hộ sinh và 66 đại học. 39 - Quy trình Điều trị, khám bệnh BỆNH NHÂN PHÒNG KHÁM NHẬP KHOA DỰ TRÙ VÀ HOÀN TRẢ HAO PHÍ THEO KHOA CHỈ ĐỊNH TẠM VIỆN PHÍ PHÒNG NỘI ỨNG TRÚ CÔNG NỢ CHỈ ĐỊNH CẬN LÂM SÀNG PHẪU THUẬT, THỦ DỰ TRÙ VÀ HOÀN TRẢ HAO PHÍ THEO BỆNH THUẬT NHÂN THỰC HIỆN CẬN LÂM SÀNG DƯỢC XUẤT TỪ TRỰC XUẤT KHOA VIỆN PHÍ KẾT THÚC QUÁ TRÌNH NỘI TRÚ 40 - Quy trình xếp lịch thủ công Ca trực được phân thành 2 ca: Ca ngày từ 7h – 17h cùng ngày; Ca đêm từ 17h – 5h sáng hôm sau. Người trực ca đêm thì hôm sau được nghỉ; Nếu trong ca trực có người nghỉ đột xuất thì sẽ đôn người ở ca trực tiếp theo vào thay thế. Đối với điều dưỡng thì điều dưỡng trưởng của từng khoa phân công lịch trực nộp lên phòng kế hoạch tổng hợp để báo cáo và tổng hợp. Lịch trực Bác sĩ, trực hành chính, trực cận lâm sàng (siêu âm, X quang, xét nghiệm, nội soi), do phòng kế hoạch tổng hợp sắp xếp. + Tiếp nhận danh sách nhân sự: Họ tên, ngày sinh, giới tính, điện thoại, khoa, chức vụ. + Tiếp nhận danh sách ràng buộc: - Yêu cầu xếp lịch từ các khoa (số lượng Bác sĩ, y tá, điều dưỡng). - Yêu cầu cấp trực: trực lãnh đạo, ca trực, chức danh và khoa. + Thời gian ca trực: ca ngày, ca đêm. + Xếp lịch trực. + Cập nhật lịch trực. - Hiện trạng Việc xếp lịch trực của Bác sĩ hiện nay được thực hiện bằng tay (thủ công) và được lưu trữ thông tin trên giấy nên không thể tránh khỏi những sai sót như: trùng lặp người trực, mất thông tin, Cho nên để có được lịch trực chính xác, không xảy ra những sai sót thì chỉ có những người thực hiện công việc xếp lịch là người có kịnh nghiệm và thực hiện công việc này trong thời gian dài, nên việc xây dựng thuật toán lập lịch trên máy tính điện tử và ứng dụng vào công việc nêu trên là cần thiết, nâng cao chất lượng công việc. 3.3 Các mô hình phân công các ca trực Xuất phát từ tìm hiểu thực tế, tại bệnh viện tồn tại 2 mô hình phân công các bác sĩ và y tá trực tại các lịch trực, đó là: 1. Mô hình phân công trực tại các khoa chuyên môn 2. Mô hình phân công trực tại các phòng khám 41 Hai mô hình trên có tính chất chuyên môn cũng như độ phức tạp là hoàn toàn khác nhau. Sau đây chúng ta phân tích chi tiết 2 mô hình và tìm lời giải tối ưu trên từng mô hình 3.3.1 Bài toán phân công trực tại các khoa chuyên môn Giả sử tại một khoa chuyên môn (Nội, Ngoại, Nhi, Sản,) qua khảo sát thu được các thông tin như sau: + Tập BS={1,2,3,..,NB} các bác sĩ được mã số thứ tự từ 1 đến NB + Tập YT={1,2,3,..,NY} các y tá được mã số thứ tự từ 1 đến NY + Tập T={1,2,3,.,NT} danh sách các ca trực được mã số thứ tự từ 1 đến NT Các bác sĩ và y tá đều phải tham gia vào các ca trực cấp cứu tại khoa theo các yêu cầu sau đây: + Mọi bác sĩ và y tá đều có nghĩa vụ, trách nhiệm cũng như quyền lợi như nhau + Mỗi bác sĩ và y tá đều có thể đưa ra yêu cầu được nghỉ một số buổi trong lịch tùy theo hoàn cảnh mỗi người. + Tại mọi thời điểm tại phòng trực cấp cứu luôn luôn phải đảm bảo có 1 bác sĩ và 1 y tá trực. Yêu cầu: Hãy lên lịch phân công trực cấp cứu cho các khoa trong bệnh viện sao cho các yêu cầu của mọi người đều thỏa mãn đồng thời số buổi trực của các bác sĩ là tương đương, số buổi trực của các Y tá là tương đương. Phân tích: + Hiển nhiên mô hình các khoa là tương đương đồng thời giữa các khoa là hoạt động độc lập nên chúng ta chỉ cần xây dựng thuật toán phân lịch cho 1 khoa làm đại diện từ đó suy rộng cho toàn bệnh viện. + Do Bác sĩ và Y tá trong 1 khoa là độc lập nên chúng ta cũng chỉ cần phân lịch L1 cho bác sĩ và phân lịch L2 cho Y tá sau đó kết hợp lại chúng ta sẽ được lịch chung toàn khoa. Hiển nhiên 2 bài toán lập lịch L1 và L2 là tương đương. Như vậy chúng ta chỉ cần xét bài toán phân lịch cho các bác sĩ là đủ: 42 Kí hiệu L=(L(1),L(2),.,L(NB)) là lịch trực cần tìm trong đó L(i)=k (k=1..NB) được hiểu là bác sĩ k sẽ trực vào ca trực thứ i trong lịch (i=1..NT) Kí hiệu B=(B(i,j)) là ma trận ràng buộc yêu cầu trong đó B(i,j)=0 được hiểu là Bác sĩ thứ i không sẵn sàng trực tại ca thứ j trong lịch, B(i,j)=1 được hiểu là Bác sĩ thứ i sẵn sàng nhận nhiệm vụ. Hiển nhiên bài toán cần xây dựng phương án trực L thỏa mãn ràng buộc B sao cho số buổi trực của các bác sĩ là xấp xỉ bằng nhau. Để giải quyết bài toán trên, có nhiều phương pháp đưa ra lời giải gần đúng. Trong trường hợp này chúng ta sẽ xây dựng thuật toán gần đúng (theo tư tưởng tham lam) giải bài toán như sau: Tư tưởng: Lần lượt xếp các bác sĩ vào lịch trực (mỗi bác sĩ 1 lần) sao cho thỏa mãn điều kiện. Quá trình lặp đi lặp lại cho đến khi kín lịch thì dừng lại. Hiển nhiên do xếp lần lượt các bác sĩ (mỗi bác sĩ 1 lần) nên số các ca trực của các bác sĩ chỉ chênh lệnh nhiều nhất là 1 buổi, do đó ta đạt được nghiệm theo yêu cầu. Thuật toán Input: + NB, NY, NT + Ma trận B Output: L Bước 1: Xuất phát L=(0,0,..,0) Chưa xếp bác sĩ nào vào lịch Bước 1: (Bước lặp) k=1; %Xuất phát từ bác sĩ thứ nhất + Tìm ca chưa xếp đầu tiên mà bác sĩ k không bận xếp bác sĩ k vào lịch + Dich chuyển đến ca tiếp theo + k:=k=1; Lấy bác sĩ tiếp sau. Bước 2 Kiểm tra điều kiện dừng (Lịch đầy) Quay lại bước 1 Hiển nhiên độ phức tạp của thuât toán là O(NB.NT) 43 Thuật toán được mô tả chi tiết bằng ngôn ngữ Matlab function lap_lich=Tham_lam_1 clear all; clc;NT=14;NB=5; load d:\chuyen_dai_tu\B; % Phan lich truc cho bac si while KT(X)>0 k=1; while and(k0) i=1;ok=0; while and(i<=NT,ok==0) if and((X(i)==0),(B(k,i)==1)) X(i)=k;ok=1; else i=i+1; end; end; k=k+1; end; end; CB=zeros(1,NB);CY=zeros(1,NY); for k=1:NB for i=1:NT if (X(i)==k) CB(k)=CB(k)+1;end; end; end; Lich_truc_bac_si=X So_ca_truc=CB function KT=KT(X)%Hàm kiem tra s=0; for i=1:length(X) if X(i)==0 s=s+1; end; end; KT=s; 44 Sau đây là kết quả xếp lịch trực cho các bác sĩ và y tá tại 1 khoa chuyên môn với các số liệu như sau + Số bác sĩ là 5 + Số y tá là 7 + Số ca trực là 14 Ma trận ràng buộc của các bác sĩ và y tá được cho bởi bảng Bảng 3.1: Ma trận ràng buộc B (1-Sẵn sàng, 0-Không sẵn sàng) C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 C13 C14 BS 1 0 1 1 0 1 1 1 1 0 1 1 1 1 1 BS 2 1 0 1 1 0 1 1 1 1 0 1 1 1 1 BS 3 1 0 0 1 1 0 1 1 1 1 0 1 1 1 BS 4 1 1 1 0 1 1 0 1 1 1 1 0 1 1 BS 5 1 1 1 1 0 1 1 1 1 0 1 1 1 0 Bảng 3.2: Ma trận ràng buộc Y (1-Sẵn sàng, 0-Không sẵn sàng) C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 C13 C14 Yta 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 Yta 2 1 1 0 1 0 1 1 1 1 1 1 0 1 1 Yta 3 0 1 1 1 1 1 0 1 1 1 1 1 0 1 Yta 4 1 0 1 1 0 1 1 1 1 1 1 0 1 1 Yta 5 1 1 0 1 1 1 1 1 1 0 1 1 1 0 Yta 6 0 1 1 1 1 0 1 1 1 1 1 1 1 1 Yta 7 1 1 0 1 1 1 1 1 1 0 0 1 1 1 Kết quả chạy chương trình được đưa ra trong bảng 3.3 và 3.4 (Lap_lich_tham_lam_1.m) Bảng 3.3: Lịch trực các buổi trong tuần (Số hiệu bác sĩ – Số hiệu y tá) B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14 2-1 1-2 4-3 3-4 2-5 5-7 3-6 1-1 4-2 5-3 2-4 3-5 1-6 4-7 Bảng 3.4: Số buổi trực đối với các bác sĩ – y tá Bs1 Bs 2 Bs3 Bs4 Bs5 Yta1 Yta2 Yta3 Yta4 Yta5 Yta6 Yta7 3 3 3 3 2 2 2 2 2 2 2 2 45 Nhận xét: + Thuật toán cho kết quả là chấp nhận được tức là số buổi trực của các bác sĩ là đồng đều nhau, số buổi trực các Y tá là đồng đều nhau. + Mô hình bài toán là đơn giản, dễ giải quyết trong thực tế vì số ràng buộc là ít + Mô hình áp dụng tốt cho tất cả các khoa tại bệnh viện A Thái Nguyên 3.3.2 Bài toán phân công trực tại các Phòng khám Chúng ta xét bài toán: Giả sử tham khảo thông tin tại phòngTổ chức cán bộ tại bệnh viện A, ta thu được các thông tin sau:  Thông tin cơ bản + Bảng 1 gồm NBS các bác sĩ: (Số hiệu, tên, chuyên môn đào tạo) + Bảng 2 gồm NYT các y tá: (Số hiệu, tên, chuyên môn đào tạo) + Bảng 3 gồm NPK các phòng khám (Số hiệu, tên phòng khám) + Bảng 4 gồm NBT các buổi trực (Số hiệu, thời gian, ngày) Trong đó số hiệu được đánh số từ 1,2,,N  Để đảm bảo về chất lượng chuyên môn: Ban giám đốc yêu cầu mỗi Bác sĩ và Y tá chỉ được trực tại một số phòng khám phù hợp với chuyên môn đã được đào tạo (thông tin trong bảng gồm: Số hiệu bác sĩ (Y tá), Số hiệu phòng khám 1- Phù hợp, 0 – Không phù hợp)  Để tạo điều kiện thuận lợi, cho phép mỗi Bác sĩ và Y tá được đăng kí các buổi trực mà cá nhân sẵng sàng nhận trực theo lịch phân công trong một số buổi xác định (thông tin trong bảng gồm: Số hiệu bác sĩ (Y tá), Số hiệu ca trực 1- Phù hợp, 0 – Không phù hợp) Yêu cầu hãy xếp lịch trực cho tất cả các Bác sĩ và Y tá tại tất cả các phòng khám trong danh sách tất cả các ca trực để sao cho tại mọi buổi, tất cả các phòng khám phải có đầy đủ 1 Bác sĩ và 1 Y tá trực phù hợp với chuyên môn đào tạo đồng thời số ca trực của các Bác sĩ là tương đương nhau, các Y tá là tương đương nhau. Hiển nhiên bài toán này là phức tạp hơn rất nhiều bài toán trực tại các khoa chuyên môn bởi vì một bác sĩ hoặc y tá có thể trực tại nhiều phòng khám khác nhau tại nhiều ca khác nhau (Bài toán 2 chiều) 46 Xuất phát từ bài toán trên, chúng ta có mô hình toán học chi tiết cho bài toán như sau:  Sử dụng các kí hiệu - Tập BS={1,2,,NBS} số hiệu các Bác sĩ. - Tập YT={1,2,,NTY} số hiệu các Y tá. - Tập PK={1,2,,NPK} số hiệu các phòng khám. - Tập BT={1,2,,NBT} số hiệu các buổi trong lịch toàn lịch trực. - Mảng PBS(s,p) biểu diễn sự phù hợp chuyên môn giữa các Bác sĩ và phòng khám trong đó: PBS(s,p)=1 chuyên môn Bác sĩ số hiệu s phù hợp với phòng khám p, PBS(s,p)=0 – Không phù hợp. - Mảng PYT(s,p) biểu diễn sự phù hợp chuyên môn giữa các Y tá và phòng khám trong đó: PYT(s,p)=1 chuyên môn Y tá số hiệu s phù hợp với phòng khám p, PYT(s,p)=0 – Không phù hợp. - Mảng trạng thái MBS(s,t) trạng thái sẵn sàng nhận trực của Bác sĩ có số hiệu s trong ca trực thứ t trong đó MBS(s,t)=1 là sẵng sàng, MBS(s,t)=0 là không sẵn sàng - Mảng trạng thái MYT(s,t) trạng thái sẵn sàng nhận trực của Y tá có số hiệu s trong ca trực thứ t trong đó MYT(s,t)=1 là sẵng sàng, MYT(s,t)=0 là không sẵn sàng  Các biến số cần xác định - Các biến XBS(p,t)=k – bác sĩ số hiệu k được xếp vào phòng khám p trong buổi trực t. - Các biến XYT(p,t)=k – y tá số hiệu k được xếp vào phòng khám p trong buổi trực t. - Các biến CBS(s) - Ghi lại tổng số buổi trực của bác sĩ s trong toàn lịch phân công trực tại các phòng khám. - Các biến CYT(s) - Ghi lại tổng số buổi trực của y tá s trong toàn lịch phân công trực tại các phòng khám.  Các điều kiện ràng buộc: R1: Tại một thời điểm t, 1 Bác sĩ chỉ được trực nhiều nhất là 1 phòng khám. R2: Tại một thời điểm t, 1 Y tá chỉ được trực nhiều nhất là 1 phòng khám. 47 R3: Chỉ xếp lịch trực cho các Bác sĩ sẵn sàng trong buổi trực. R4: Chỉ xếp lịch trực cho các Y tá sẵn sàng trong buổi trực. R5: Các Bác sĩ và Y tá chỉ được phép trực tại các phòng khám phù hợp về chuyên môn. R6: Tại mọi thời điểm, các phòng khám đều phải có đầy đủ 1 Bác sĩ và 1 Y tá trực Yêu cầu: Hãy xây dựng bảng phân công trực tại các phòng khám cho tất cả các Bác sĩ và Y tá trong bệnh viện thỏa mãn tất cả các ràng buộc R1,,R6 sao cho tổng số các buổi trực của các Bác sĩ được phân công là tương đương nhau, số các buổi trực của các Y tá được phân công là tương đương nhau. Nhận xét: Bài toán trên là một dạng bài toán quy hoạch rời rạc. Để nhận được lời giải đúng là rất khó thực hiện và trong nhiều trường hợp chúng ta không thể xác định được lịch biểu tối ưu (Phụ thuộc vào 2 ma trận sẵn sàng là TBS và TYT). Sau đây chúng ta sẽ nghiên cứu hai phương án thiết kế giải bài toán Phương án 1: Thuật toán tham lam Phân tích: + Do Bác sĩ và Y tá trong 1 bênh viện là độc lập nên chúng ta cũng chỉ cần phân lịch L1 cho bác sĩ và phân lịch L2 cho Y tá sau đó kết hợp lại chúng ta sẽ được lịch chung toàn khoa. Hiển nhiên 2 bài toán lập lịch L1 và L2 là tương đương. Như vậy chúng ta chỉ cần xét bài toán phân lịch cho các bác sĩ là đủ: + Kí hiệu L1=(L1(i,j)) là lịch trực cần tìm trong đó L1(i,j)=k (k=1..NB) được hiểu là bác sĩ k sẽ trực tại phòng khám i (i=1..NP) trong ca trực thứ i trong lịch (i=1..NT) + Kí hiệu BT=(BT(i,j)) là ma trận ràng buộc yêu cầu trong đó B(i,j)=0 được hiểu là Bác sĩ thứ i không sẵn sàng trực tại ca thứ j trong lịch, B(i,j)=1 được hiểu là Bác sĩ thứ i sẵn sàng nhận nhiệm vụ. + Kí hiệu BP=(BP(i,j)) là ma trận ràng buộc yêu cầu trong đó B(i,j)=0 được hiểu là Bác sĩ thứ i không đáp ứng chuyên môn tại phòng khám thứ j, B(i,j)=1 được hiểu là Bác sĩ thứ i đáp ứng chuyên môn 48 Hiển nhiên bài toán cần xây dựng phương án trực L1 thỏa mãn 2 ràng buộc BT và BP sao cho số buổi trực của các bác sĩ là xấp xỉ bằng nhau. Chúng ta sẽ xây dựng thuật toán gần đúng (theo tư tưởng tham lam) giải bài toán như sau: Tư tưởng: Bước 1: Khởi động ma trận L1 là rỗng (Chưa xếp lịch) Bước lặp: Lần lượt xét các bác sĩ k= 1..NB + Xét 1 ô L1(i,j) còn trống (Chưa xếp bác sĩ) + Nếu Bác sĩ k thỏa mãn yêu cầu tại ô (i,j): BT(k,j)=1; BP(i,k)=1 thì xếp bác sĩ k vào ô (i,j) + Tăng k=k+1; Quay lại bước lặp. Quá trình dừng lại khi tất cả các ô L1(i,j) đã đầy Hiển nhiên do xếp lần lượt các bác sĩ theo dạng quay vòng nên số các ca trực là xấp xỉ bằng nhau. Quá trình xếp các y tá là hoàn toàn tương tự Thuật toán Input: + NB, NY, NT + Ma trận B Output: L Bước 1: Xuất phát L=(0,0,..,0) Chưa xếp bác sĩ nào vào lịch Bước 1: (Bước lặp) k=1; %Xuất phát từ bác sĩ thứ nhất + Tìm ca chưa xếp đầu tiên mà bác sĩ k không bận xếp bác sĩ k vào lịch + Dich chuyển đến ca tiếp theo + k:=k=1; Lấy bác sĩ tiếp sau. Bước 2 Kiểm tra điều kiện dừng (Lịch đầy) Quay lại bước 1 Hiển nhiên độ phức tạp của thuật toán là O(NB.NT.NP) Thuật toán được mô tả chi tiết bằng ngôn ngữ Matlab 49 function lap_lich=Tham_lam_2 clc;NT=14;NB=10;NY=14;NP=7;BT=ones(NB,NT);BP=ones(NB,NP);YT=ones(N Y,NT);YP=ones(NY,NP); load d:\chuyen_dai_tu\BT; load d:\chuyen_dai_tu\BP; load d:\chuyen_dai_tu\YT; load d:\chuyen_dai_tu\YT; X=zeros(NP,NT); Z=zeros(NP,NT); count=0; while KT(X)>0 k=1; while k<=NB i=0; while i<NP i=i+1;j=0;ok=0; while and(j<NT,ok==0) j=j+1; if and((X(i,j)==0),and((BP(k,i)==1),and((BT(k,j)==1),(KT1(X(:,j),k)==0)))) X(i,j)=k;ok=1; end; end; end; k=k+1; end; end; CB=zeros(1,NB); for k=1:NB for i=1:NP for j=1:NT if (X(i,j)==k) CB(k)=CB(k)+1;end; end; end; end; count=0; while KT(Z)>0 k=1; while k<=NY i=0; while i<NP i=i+1;j=0;ok=0; while and(j<NT,ok==0) 50 j=j+1; if and((Z(i,j)==0),and((YP(k,i)==1),and((YT(k,j)==1),(KT1(Z(:,j),k)==0)))) Z(i,j)=k;ok=1; end; end; end; k=k+1; end; end; CY=zeros(1,NY); for k=1:NY for i=1:NP for j=1:NT if (Z(i,j)==k) CY(k)=CY(k)+1;end; end; end; end; Lich_truc_bac_si=X So_ca_truc=CB Lich_truc_Y_ta=Z So_ca_truc=CY function KT=KT(X)%Hàm kiem tra NP=7;NT=14; s=0; for i=1:NP for j=1:NT if X(i,j)==0 s=s+1; end; end; end; KT=s; function KT1=KT1(Z,k)%Hàm kiem tra NP=7; s=0; for i=1:NP if (Z(i)==k) s=s+1; end; end; KT1=s; 51 Bộ số liệu Test + Số các bác sĩ tham gia trực NBS=10. + Số các y tá tham gia trực NYT=14. + Số các phòng khám NP=7. + Số các buổi trong lịch: NT=14. Bảng 3.5: Bảng các bác sĩ phù hợp chuyên môn với phòng khám (1-Phù hợp, 0-Không phù hợp) Phòng 1 Phòng 2 Phòng 3 Phòng 4 Phòng 5 Phòng 6 Phòng 7 Bs 1 0 1 1 0 1 1 1 Bs 2 1 0 1 1 1 1 0 Bs 3 1 1 0 0 1 1 1 Bs 4 0 1 1 1 1 0 1 Bs 5 1 0 1 1 1 0 1 Bs 6 0 1 1 0 1 1 1 Bs 7 1 0 1 1 1 1 0 Bs 8 0 1 0 1 1 1 1 Bs 9 0 1 1 1 1 1 1 Bs 10 1 1 1 0 1 1 1 Bảng 3.6: Bảng các y tá phù hợp chuyên môn với phòng khám (1-Phù hợp, 0-Không phù hợp) Phòng 1 Phòng 2 Phòng 3 Phòng 4 Phòng 5 Phòng 6 Phòng 7 Yta 1 0 1 1 0 1 1 1 Yta 2 1 0 1 1 1 1 0 Yta 3 1 1 0 0 1 1 1 Yta 4 0 1 1 1 1 0 1 Yta 5 1 1 1 0 1 0 1 Yta 6 0 1 1 0 1 1 1 Yta 7 1 0 1 1 1 1 0 Yta 8 0 1 1 1 1 1 1 Yta 9 0 1 1 1 1 1 1 Yta 10 1 1 1 0 1 1 1 Yta 11 1 0 1 1 1 1 1 Yta 12 1 1 1 1 0 1 1 Yta 13 1 1 1 1 1 0 1 Yta 14 1 1 1 1 1 1 1 52 Bảng 3.7: Bảng các Bác sĩ sẵn sàng nhận buổi trực (1-Sẵn sàng, 0-Không sẵn sàng) B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14 Bs 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 Bs 2 1 2 1 1 0 1 1 1 1 1 1 1 1 1 Bs 3 1 1 0 1 1 1 1 1 1 0 1 1 1 1 Bs 4 1 1 1 1 1 1 1 1 1 1 0 1 1 1 Bs 5 1 1 1 0 1 1 0 1 1 1 1 1 1 1 Bs 6 0 1 1 1 1 1 1 1 1 1 1 1 1 1 Bs 7 1 1 0 1 1 1 1 1 1 1 1 1 1 1 Bs 8 1 1 1 1 1 1 1 1 1 0 1 1 1 1 Bs 9 1 1 1 1 1 0 1 1 1 1 1 1 1 1 Bs 1 1 1 0 1 1 1 1 1 1 1 1 1 1 10 Bảng 3.8: Bảng các Y tá sẵn sàng nhận buổi trực (1-Sẵn sàng, 0-Không sẵn sàng) B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14 Yta 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 Yta 2 1 1 0 1 1 0 1 1 1 1 1 1 1 1 Yta 3 1 0 1 1 1 1 1 1 0 1 1 1 1 1 Yta 4 1 1 1 1 1 1 1 1 1 1 0 1 0 1 Yta 5 1 1 1 0 1 1 0 1 1 1 1 1 1 1 Yta 6 0 1 1 1 1 1 1 1 1 1 1 1 1 1 Yta 7 1 1 0 1 1 1 1 1 1 1 1 1 1 1 Yta 8 1 1 1 1 1 1 1 1 1 0 1 1 1 1 Yta 9 1 1 1 1 1 0 1 1 1 1 1 1 1 1 Yta10 1 1 1 0 1 1 1 1 1 1 1 1 1 1 Yta11 1 1 1 1 0 1 1 1 1 1 1 1 1 1 Yta12 1 0 1 1 1 1 1 1 1 1 1 1 1 1 Yta13 1 1 1 1 1 1 0 1 1 1 1 1 1 1 Yta14 1 1 1 1 1 1 1 1 1 1 1 1 1 1 53 Kết quả chạy chương trình trên bộ số liệu thực tế được đưa ra trong các bảng 3.9 và 3.10 và 3.11 (Lap_lich_tham_lam_2) Bảng 3.9: Lịch trực tại các phòng trong các buổi (Số hiệu bác sĩ – Số hiệu y tá) B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14 P1 2-2 3-5 5-3 7-7 10-10 2-11 3-12 5-13 7-14 10-2 2-3 3-5 5-7 7-10 P2 1-4 4-1 6-6 8-8 9-9 1-1 4-4 6-6 8-8 9-9 1-12 4-13 6-14 8-1 P3 9-11 10-2 2-4 1-6 4-5 5-7 6-8 7-9 9-10 1-11 10-13 2-12 4-1 5-14 P4 8-7 7-4 8-8 9-2 5-12 4-13 2-9 8-11 2-2 7-14 9-7 5-4 7-8 4-9 P5 3-3 6-6 10-5 3-3 1-1 3-10 10-3 1-5 6-6 6-10 3-11 8-14 9-13 10-2 P6 7-12 1-7 9-1 2-9 3-3 6-6 8-10 10-8 3-11 2-12 6-14 1-1 8-2 9-3 P7 4-5 5-13 4-9 4-4 6-4 10-5 1-6 3-10 5-12 6-13 8-8 9-11 10-3 1-14 Bảng 3.10: Số buổi trực đối với các bác sĩ Bs1 Bs 2 Bs3 Bs4 Bs5 Bs6 Bs7 Bs8 Bs9 Bs10 11 9 10 10 10 10 8 10 10 10 Bảng 3.11: Số buổi trực đối với các y tá YT1 YT2 YT3 YT4 YT5 YT6 YT7 YT8 YT9 YT10 YT11 YT12 YT13 YT14 7 7 8 8 7 7 6 7 7 7 7 7 7 6 Nhận xét: Kết quả nhận được là kết quả gần đúng. Điều kiện tối ưu chưa đảm bảo tốt vì thuật toán không xét đến hàm mục tiêu (Chỉ xét theo thứ tự lần lượt các bác sĩ và các y tá để xếp vào lịch mà không đánh giá hàm mục tiêu) Phương án 2: Thuật toán GA Xây dựng cấu trúc dữ liệu  Lựa chọn cấu trúc cá thể: Kí hiệu 1 phương án xếp lịch là cặp 2 ma trận [ZBS(NPK,NBT) ;ZYT(NPK,NBT] trong đó - ZBS(p,t)=k : Phân công bác sĩ có số hiệu k trực phòng khám p, tại buổi t, - ZYT(p,t)=k : Phân công Y tá có số hiệu k trực phòng khám p, pPK tại buổi t. Như vậy tập hợp các phương án chính là tập hợp các cặp ma trận các phần tử là các số nguyên dương có giá trị là các số hiệu của các Bác sĩ hoặc của các Y tá. Điều kiện phân công hợp lệ là trên một cột của các ma trận ZBS và ZYT không có 54 các phần tử có giá trị trùng nhau tức là tại 1 thời điểm mỗi bác sĩ hoặc y tá chỉ được trực tại 1 phòng khám.  Hàm CBS(k) có giá trị bằng tổng tất cả các phần tử trong ma trận phương án ZBS thỏa mãn điều kiện ZBS(p,t)=k, với mọi 1;1;pNPKtNBT Như vậy CBS(k) chính là tổng số buổi trực của bác sĩ k trong toàn lịch trực.  Hàm CYT(k) có giá trị bằng tổng tất cả các phần tử trong ma trận phương án ZYT thỏa mãn điều kiện XYT(p,t)=k, với mọi 1;1;pNPKtNBT Như vậy CYT(k) chính là tổng số buổi trực của y tá s trong toàn lịch trực. Các ràng buộc của bài toán + R1: Tại một thời điểm t, 1 bác sĩ chỉ được trực nhiều nhất là 1 phòng khám sẽ tương đương với điều kiện: Trên một cột của ma trận ZBS không tồn tại 2 phần tử bằng nhau. Xây dựng hàm R1(ZBS) để kiểm tra điều kiện R1 trong phương án ZBS. + R2: Tại một thời điểm t, 1 y tá chỉ được trực nhiều nhất là 1 phòng khám sẽ tương đương với điều kiện: Trên một cột của ma trận ZYT không tồn tại 2 phần tử bằng nhau. Xây dựng hàm R2(ZYT) để kiểm tra điều kiện R2 trong phương án XY. + R3: Chỉ xếp lịch trực cho các bác sĩ sẵn sàng trong buổi trực tương ứng sẽ tương đương với điều kiện: Nếu ZBS(p,t)=s thì MBS(s,t)=1 hay MBS(ZBS(p,t),t)=1. + R4: Chỉ xếp lịch trực cho các y tá sẵn sàng trong buổi trực tương ứng sẽ tương đương với điều kiện: Nếu ZYT(p,t)=s thì MYT(s,t)=1 hay MYT(ZYT(p,t),t)=1. + R5: Các bác sĩ và Y tá chỉ được phép trực tại các phòng khám phù hợp về chuyên môn đào tạo sẽ tương đương với điều kiện: Nếu ZBS(p,t)=s thì PK(s,p)=1 hay PK(ZBS(p,t),p)=1. Nếu ZYT(p,t)=s thì PK(s,p)=1 hay PK(XY(p,t),p)=1. Kết hợp 3 điều kiện R3,R4 và R5, điều kiện thỏa mãn đồng thời chính là 55 BT(XB(p,t),t)× PBS(XB(p,t),p) × BT(XY(p,t),t)× PYT(X(p,t),p)=1; với mọi 1;1;pNPtNT Xây dựng hàm R345(X) là hàm kiểm tra điều kiện H3, H4 và H3 trong phương án Z =[ZBS;ZYT]. + R6: Tại mọi thời điểm, các phòng khám đều phải có bác sĩ trực và y tá sẽ tương đương với tất cả các phần tử trong cặp ma trận Z=[ZBS;ZYT] đều dương. ZBS(p,t)>0; ZYT(p,t)>0; với mọi Chúng ta kí hiệu hàm R6(X) để kiểm tra điều kiện H6. Hàm mục tiêu của bài toán: Vì tổng số các buổi trực của các bác sĩ và y tá luôn bằng NP×NT (Giả thiết tất cả các phòng khám đều phải xếp kín tất cả các buổi), do đó sử dụng bất đẳng thức Bunhiakovski: “Tổng các phần tử là không đổi thì tích sẽ đạt giá trị lớn nhất khi tất cả các phần tử bằng nhau”, ta suy ra để đảm bảo yêu cầu của bài toán: số các buổi trực của các bác sĩ là xấp xỉ bằng nhau sẽ tương đương với: Hãy xác định phương án Z=[ZBS;ZYT] thỏa mãn tất cả các ràng buộc để sao cho 2 hàm mục tiêu: NBS FBXCBSsm()()ax s1 NYT FYXCYTtm()( )ax t1 Như vậy bài toán lập trực được đưa về bài toán: Hãy xác định phương án X thỏa mãn cás sĩc ràng buộc mô tả bởi các hàm ràng buộc R1(X), R2(X), R345(X), R6(X) để sao cho hàm mục tiêu F()()()ax ZFB ZBSFY ZYTm Thuật toán GA B1