Chương 1 : TỔNG QUAN VỀ ĐỀ TÀI Chương này giới thiệu chung về bối cảnh, mục tiêu, đối tượng và phạm vi nghiên cứu của đề tài. Cấu trúc nội dung của quyển thuyết minh được trình bày ở cuối chương. Chương 2 : CƠ SỞ LÝ THUYẾT Chương này trình bày nội dung cơ sở lý thuyết để giải bài toán xếp lịch thực hành phòng máy bao gồm các khái niệm liên quan đến hệ hỗ trợ ra quyết định, giải thuật tham lam và bài toán tối ưu, và phương pháp giải bài toán tối ưu bằng phần mềm Lingo. Phần cuối là một số công trình xếp thời khóa biểu đã tham khảo.
Chương 3 : MÔ HÌNH BÀI TOÁN Chương này trình bày mô hình bài toán xếp lịch thực hành phòng máy, bao gồm nội dung bài toán, các ràng buộc, tham số liên quan và giải thuật để giải quyết bài toán này. Phần cuối chương trình bày kết quả chi tiết khi áp dụng giải thuật trên dữ liệu bài toán cụ thể. Chương 4: HIỆN THỰC CHƯƠNG TRÌNH Chương này trình bày chi tiết phần hiện thực hệ thống xếp lịch thực hành phòng máy bao gồm cơ sở dữ liệu và các quá trình xử lý liên quan. Chương 5 : KẾT QUẢ THỰC NGHIỆM Chương này trình bày một số kết quả thực nghiệm trên các bộ dữ liệu khác nhau, vẽ biểu đồ dựa trên các tham số thực nghiệm và đưa ra một số nhận xét.
Trang 4 Chương 6 : TỔNG KẾT ĐÁNH GIÁ Chương này tổng kết lại những việc đã làm được, một số hạn chế và hướng phát triển của hệ thống. Trang 5 Chương 2: CƠ SỞ LÝ THUYẾT Chương này trình bày nội dung cơ sở lý thuyết để giải bài toán xếp lịch thực hành phòng máy bao gồm các khái niệm liên quan đến hệ hỗ trợ quyết định, giải thuật tham lam và bài toán tối ưu đơn mục tiêu, và phương pháp giải bài toán tối ưu đơn mục tiêu bằng phần mềm Lingo. Phần cuối là một số công trình xếp thời khóa biểu đã tham khảo. Hệ hỗ trợ quyết định (Decision Support System – DSS) 2.
Khái niệm về DSS DSS là một hệ thống thông tin trên nền máy tính giao tiếp, được phát triển để hỗ trợ việc giải quyết các vấn đề không có tính cấu trúc nhằm nâng cao hiệu quả của việc thực hiện quyết định ([1]). Những lợi ích chính của DSS - Khả năng hỗ trợ giải quyết các vấn đề phức tạp. - Đáp ứng nhanh với sự thay đổi của vấn đề. - Sự giao tiếp tiện lợi.
- Nâng cao hiệu quả công việc. - Tiết kiệm chi phí. Các thành phần của DSS - Hệ thống con quản lý dữ liệu: bao gồm cơ sở dữ liệu, hệ quản trị cơ sở dữ liệu, thư mục dữ liệu. - Hệ thống con quản lý mô hình: là một gói phần mềm bao gồm những mô hình tài chính, thống kê, khoa học quản lý, các mô hình định lượng khác nhằm cung cấp khả năng phân tích của hệ thống, và một sự quản lý phần mềm tích hợp.
- Hệ thống con quản lý kiến thức: là thành phần dùng để cung cấp những khả năng chuyên môn cần thiết để giải quyết một số khía cạnh của vấn đề và cung cấp tri thức để nâng cao sự điều hành của các thành phần DSS khác. - Hệ thống giao tiếp người dùng : cung cấp giao diện người dùng và giao tiếp với người sử dụng, bao gồm menu, lệnh, biểu mẫu, ngôn ngữ tự nhiên, thao tác trên đối tượng đồ họa. Trang 6 - Người sử dụng: là nhà quản lý hay người ra quyết định. Giải thuật tham lam (Greedy) 2.
Giới thiệu giải thuật Giải thuật tham lam là một thuật toán giải quyết một bài toán để tìm kiếm lựa chọn tối ưu địa phương ở mỗi bước đi với hy vọng tìm được tối ưu toàn cục. Chẳng hạn áp dụng giải thuật tham lam với bài toán hành trình của người bán hàng ta có giải thuật sau: "Ở mỗi bước hãy đi đến thành phố gần thành phố hiện tại nhất". Tính chất tham lam thể hiện ở chổ : Chúng ta có thể lựa chọn giải pháp nào được cho là tốt nhất (phụ thuộc vào hàm đánh giá) ở thời điểm hiện tại và sau đó giải bài toán con nảy sinh từ việc thực hiện lựa chọn vừa rồi. Thuật toán tiến triển theo kiểu thực hiện các chọn lựa theo một vòng lặp, cùng lúc đó thu nhỏ bài toán đã cho về một bài toán con nhỏ hơn.
Đối với nhiều bài toán, giải thuật tham lam hầu như không cho ra lời giải tối ưu toàn cục (nhưng không phải luôn như vậy), vì chúng thường không chạy trên tất cả các trường hợp. Chúng có thể bám chặt lấy một số lựa chọn nhất định một cách quá sớm, điều này dẫn đến hậu quả là trong giai đoạn sau, các thuật toán này không thể tìm ra các lời giải toàn cục tốt nhất. Ví dụ, đối với bài toán tô màu đồ thị và tất cả các bài toán NP-đầy đủ khác, không một thuật toán tham lam đã được biết nào đảm bảo tìm thấy các lời giải tối ưu. Tuy nhiên, các thuật toán này vẫn hữu ích vì chúng dễ thiết kế và cho ra các ước lượng tốt về lời giải tối ưu.
Nếu có thể chứng minh rằng một thuật toán tham lam cho ra kết quả tối ưu toàn cục cho một lớp bài toán nào đó, thì thuật toán thường sẽ trở thành phương pháp được chọn lựa, vì nó chạy nhanh hơn các phương pháp tối ưu hóa khác. Ví dụ: Xét không gian trạng thái được biểu diễn bởi đồ thị sau: 20 A 7 15 E C Trang 7 6 8 D K I 12 F Hình 1: Đồ thị minh họa giải thuật Greedy Tìm đường đi ngắn nhất với trạng thái ban đầu là A, trạng thái kết thúc là B. Giá trị của hàm đánh giá là các số ghi ở mỗi đỉnh. Quá trình tìm kiếm Greedy diễn ra như sau: Đầu tiên phát triển đỉnh A sinh ra các đỉnh kề là C, D và E.
Trong ba đỉnh này, đỉnh D có giá trị hàm đánh giá nhỏ nhất, nó được chọn để phát triển và sinh ra F, I. Trong số các đỉnh chưa được phát triển C, E, F, I thì đỉnh E có giá trị đánh giá nhỏ nhất, nó được chọn để phát triển và sinh ra các đỉnh G, K. Trong số các đỉnh chưa được phát triển thì G tốt nhất, phát triển G sinh ra B, H. Đến đây ta đã đạt tới trạng thái kết thúc.
20 A 7 15 C 6 E D Trang 8 I G K F 5 12 10 8 Hình 2: Đồ thị minh họa kết quả khi áp dụng giải thuật Greedy 2. Ứng dụng giải thuật Greedy Bài toán xếp lịch thực hành phòng máy có một số đặc điểm sau: Các môn học thực hành Tin học được xếp sau khi có lịch học lý thuyết nên sự đụng độ về mặt thời gian là khá nhiều. Do vậy, việc lựa chọn thứ/tiết nào và lớp-môn nào xếp trước là cần thiết, tạo cơ hội cho các lớp-môn bị trùng giờ học và giảng viên bận giờ dạy lý thuyết hoặc việc riêng. Trong luận văn này ứng dụng giải thuật Greedy nhằm lựa chọn thứ/tiết và lớp-môn nào được xếp lịch trước, giúp giải thuật tổng thể cho bài toán xếp lịch thực hành nhanh chóng đi đến đích mà vẫn thỏa mãn các ràng buộc, cụ thể như sau: - Chồng chập thời gian đăng ký của các lớp để tìm thời gian (thứ/tiết) có nhiều lớp đăng ký trùng nhau nhất.
- Xét các lớp có khả năng thực hành được tại thứ/tiết này, lớp được chọn xếp trước là lớp có ít cơ hội thay đổi nhất. Đây chính là giá trị hàm đánh giá để lựa chọn thứ tự xếp lịch cho các lớp. Giải thuật được minh họa rõ ở cuối chương 3. Bài toán tối ưu 2.
Giới thiệu bài toán tối ưu Tối ưu hóa là một trong những lĩnh vực kinh điển của toán học có ảnh hưởng đến hầu hết các lĩnh vực khoa học – công nghệ và kinh tế – xã hội. Trong thực tế, việc tìm giải pháp tối ưu cho một vấn đề nào đó chiếm một vai trò hết sức quan Trang 9 trọng. Phương án tối ưu là phương án hợp lý nhất, tốt nhất, tiết kiệm chi phí, tài nguyên, nguồn lực mà lại cho hiệu quả cao ([3]). Phân loại các bài toán tối ưu Các bài toán tối ưu, cũng còn được gọi là các bài toán quy hoạch toán học, được chia ra thành các lớp sau: - Bài toán quy hoạch tuyến tính.
- Bài toán tối ưu phi tuyến hay còn gọi là bài toán quy hoạch phi tuyến, bao gồm cả bài toán quy hoạch lồi và bài toán quy hoạch toàn phương. - Bài toán tối ưu rời rạc, bài toán tối ưu nguyên và hỗn hợp nguyên. - Bài toán quy hoạch động. Mô hình quy hoạch tuyến tính Mô hình quy hoạch tuyến tính bao gồm: - Tập biến quyết định: x1, x2, x3,…, xn-1, xn - Hàm mục tiêu: cực đại hoá hay cực tiểu hoá hàm mục tiêu dạng tuyến tính z = f(x) = c1x1 + c2x2 +.
+ cnxn → Max (Min), - Các điều kiện ràng buộc dưới dạng các bất đẳng thức tuyến tính: Ví dụ : Xét bài toán qui hoạch tuyến tính Max z = 8x1 + 6x2, với các ràng buộc: Cần tìm các giá trị của các biến quyết định x1, x2 để các ràng buộc được thoả mãn và hàm mục tiêu đạt giá trị lớn nhất. Phương pháp giải bài toán qui hoạch tuyến tính Có nhiều phương pháp khác nhau để giải bài toán qui hoạch tuyến tính như: phương pháp đồ thị, phương pháp đơn hình, phương pháp đơn hình đối ngẫu, phương pháp thế vị giải bài toán vận tải, các phương pháp cắt Gomory và nhánh cận Land – Doig cũng như phương pháp quy hoạch động giải bài toán quy hoạch tuyến tính nguyên. Trong luận văn này tận dụng phần mềm Lingo để giải bài toán qui hoạch tuyến tính – đơn mục tiêu. Phần mềm Lingo 2.
Giới thiệu phần mềm Lingo Lingo là công cụ được xây dựng để giải các bài toán tối ưu tuyến tính (LP – Linear Programing), không tuyến tính (NLP –None Linear Programing), tối ưu bậc 2 và tối ưu nguyên…một cách nhanh chóng và hiệu quả ([6]). Sự tiện lợi của Lingo - Biểu diễn mô hình dễ dàng: Ngôn ngữ mô hình của Lingo cho phép biểu diễn mô hình bài toán một cách trực quan đơn giản, dễ hiểu và dễ bảo trì. - Làm việc với dữ liệu thuận tiện : Lingo cho phép xây dựng các mô hình lấy thông tin trực tiếp từ cơ sở dữ liệu và bảng tính. Tương tự như vậy, Lingo có thể xuất thông tin kết quả vào một cơ sở dữ liệu hoặc bảng tính, dễ dàng hơn cho tạo các báo cáo trong ứng dụng.