Thạc Sĩ ứng dụng lý thuyết tối ưu giải bài toán lập lịch

ỨNG DỤNG LÝ THUYẾT TỐI ƯU GIẢI BÀI TOÁN LẬP LỊCH


PHẠM VĂN HUY​

Lời cảm ơn
Mục lục
Mở đầu

Chương 1: Tối ưu rời rạc và một số hướng tiếp cận

Chương 2: Thuật toán đa thức giải bài toán lập lịch.

Chương 3: ứng dụng bài toán lập lịch vào thực tế.

Chương 4: Kết luận và hướng phát triển.

Tài liệu tham khảo
Bảng tóm tắt

Tóm tắt nội dung:
- Lý thuyết
Tổng hợp những lý thuyết chung và cơ bản nhất về bài toán tối ưu, trong đó tập trung vào bài toán tối ưu rời rạc, đặc thù cho việc ứng dụng Toán vào Tin học và một số phương pháp thường dùng trong tối ưu rời rạc. Bài toán luồng cực đại trên mạng cũng đã được đề cập nhằm làm cơ sở cho việc nghiên cứu cấu trúc đặc biệt của bài toán xếp lịch học tập. Mô hình toán học của bài toán lập lịch ở đây là một bài toán quy hoạch phi tuyến. Nhưng với các biến là biến Boole (biến chỉ nhận giá trị hoặc 0 hoặc 1), nên nó có thể được quy về bài toán quy hoạch tuyến tính dạng đặc biệt để tìm lời giải thông qua một số bài toán luồng trên mạng với lời giải có độ phức tạp đa thức. Với việc tổ chức lại cấu trúc dữ liệu, thuật toán đa thức trên có thể được cài đặt hiệu quả hơn và trực quan hơn với việc sử dụng bảng, nhờ kỹ thuật điều chỉnh phương án đơn giản, giống như bài toán vận tải dạng bảng thường gặp trong quy hoạch tuyến tính. Nhờ đó thuật toán được trình bày rõ ràng hơn, việc cài đặt cũng được dễ dàng hơn.
Cơ sở toán học cho các thuật toán trên đây được tổng hợp từ các bài báo toán học đã được trình bày phần tài liệu tham khảo. Đề tài chỉ dừng lại ở mức tổng hợp và tin học hóa các thuật toán trên để đưa vào ứng dụng.
- Chương trình
Hiện thực ý tưởng trong việc ứng dụng lý thuyết đã trình bày vào thực tiễn với việc xây dựng một website đăng ký môn học trực truyến. Một số cài đặt cụ thể của thuật toán trên ngôn ngữ PHP, một ngôn ngữ trên nền web, cũng được trình bày. Cuối cùng là kết quả của một số thử nghiệm được thực hiện trên một môi trường cụ thể. Website đã hoàn thành ở mức cơ bản nhất
hướng đến việc giúp sinh viên đăng ký môn học tự chọn trực tuyến, từ đó mong muốn sẽ giúp giáo viên và các đơn vị trong trường Đại học có thể dự kiến được sự phân bổ việc lựa chọn học các môn học tự chọn của sinh viên.

1BMỤC LỤC
TULỜI CẢM ƠNUT .1
TUMỤC LỤCUT 2
TUMỞ ĐẦUUT 4
TUCHƯƠNG 1.UT TUTỐI ƯU RỜI RẠC VÀ MỘT SỐ HƯỚNG TIẾP CẬNUT 6
TU1.1.UT TUBÀI TOÁN TỐI ƯUUT 6
TU1.1.1.UT TUDạng tổng quát của bài toán tối ưuUT .6
TU1.1.2.UT TUPhân loại các bài toán tối ưuUT .7
TU1.2.UT TUCÁC PHƯƠNG PHÁP CHÍNH TRONG TỐI ƯU RỜI RẠCUT .8
TU1.2.1.UT TUPhương pháp cắt GomoryUT .9
TU1.2.2.UT TUPhương pháp nhánh cận Land – DoigUT .13
TU1.3.UT TUBÀI TOÁN LUỒNG TRÊN MẠNGUT 15
TU1.3.1.UT TULuồng trên mạngUT .15
TU1.3.2.UT TUPhân loại các thuật toán luồng trên mạngUT .16
TU1.3.3.UT TUThuật toán tìm luồng cực đại trong mạngUT .17
TU1.4.UT TUĐỘ PHỨC TẠP CỦA CÁC BÀI TOÁN TỐI ƯU RỜI RẠCUT .20
TUCHƯƠNG 2.UT TUTHUẬT TOÁN ĐA THỨC GIẢI BÀI TOÁN LẬP LỊCHUT 22
TU2.1.UT TUBÀI TOÁN LẬP LỊCHUT .22
TU2.1.1.UT TUMô hình toán học của bài toán lập lịchUT .22
TU2.1.2.UT TUMột số bài toán lập lịchUT .23
TU2.1.3.UT TUTính chất nghiệm của bài toán (P)UT 24
TU2.2.UT TUTHUẬT TOÁN ĐA THỨC GIẢI BÀI TOÁN (P)UT .27
TU2.3.UT TUTHUẬT TOÁN ĐA THỨC DẠNG BẢNG GIẢI BÀI TOÁN (P)UT 33
TU2.3.1.UT TUCơ sở phương pháp giảiUT 33
TU2.3.2.UT TUThuật toánUT 36
TU2.3.3.UT TUĐộ phức tạp của thuật toánUT 40
TU2.3.4.UT TUVí dụ minh họaUT 41
TU2.3.5.UT TUCài đặt và thử nghiệm trên máy tínhUT .46
TUCHƯƠNG 3.UT TUỨNG DỤNG BÀI TOÁN LẬP LỊCH VÀO THỰC TẾUT 49
TU3.1.UT TUWEBSITE ĐĂNG KÝ MÔN HỌC TỰ CHỌNUT 49
TU3.1.1.UT TUGiới thiệuUT .49
TU3.1.2.UT TUMô hình ứng dụngUT .50
TU3.2.UT TUXÂY DỰNG WEBSITEUT 52
TU3.2.1.UT TUCác thành phần chính xây dựng websiteUT .52
TU3.2.2.UT TUSơ đồ chức năngUT 53
TU3.2.3.UT TUTổ chức chương trìnhUT 54
TU3.2.4.UT TUCài đặt thuật toánUT 55
TU3.3.UT TUMỘT SỐ KẾT QUẢ THỬ NGHIỆMUT .59
TU3.3.1.UT TUMôi trường thử nghiệmUT .59
TU3.3.2.UT TUGiao diện websiteUT 59
TU3.3.3.UT TUMột số thử nghiệm khácUT 62
TUCHƯƠNG 4.UT TUKẾT LUẬN VÀ HƯỚNG PHÁT TRIỂNUT 65
TUTÀI LIỆU THAM KHẢOUT .67
TUPHỤ LỤCUT .68