Tóm tắt Luận văn Thạc sĩ Toán học: Biểu diễn đa diện lồi và ứng dụng trong lập thời khóa biểu

Tóm tắt Luận văn Thạc sĩ Toán học "Biểu diễn đa diện lồi và ứng dụng trong lập thời khóa biểu" trình bày các nội dung chính sau: Một số khái niệm cơ bản và kết quả quan trọng trong lý thuyết đa diện lồi; Khái niệm đa diện idle và đưa ra các biểu diễn chi tiết cho một số trường hợp cụ thể; Khái niệm đa diện idle trong việc mô hình hóa ràng buộc tiết trống của giáo viên trong bài toán lập thời khóa biểu cho các trường trung học.
Nội dung trích xuất từ tài liệu:
Tóm tắt Luận văn Thạc sĩ Toán học: Biểu diễn đa diện lồi và ứng dụng trong lập thời khóa biểuBỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌCVÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------- Đỗ Thị Thùy BIỂU DIỄN ĐA DIỆN LỒI VÀ ỨNG DỤNG TRONG LẬP THỜI KHÓA BIỂU Chuyên ngành: Toán ứng dụng Mã số: 8 46 01 12 TÓM TẮT LUẬN VĂN THẠC SĨ TOÁN HỌC Hà Nội - 2021 Công trình được hoàn thành tại: Học viện Khoa học vàCông nghệ - Viện Hàn lâm Khoa học và Công nghệ Việt Nam. Người hướng dẫn khoa học: TS. Lê Xuân Thanh. Phản biện 1: TS. Lê Hải Yến. Phản biện 2: TS. Nguyễn Đức Mạnh. Luận văn được bảo vệ trước Hội đồng chấm luận văn họp tạiViện Hàn lâm Khoa học và Công nghệ Việt Nam vào hồi 9 giờ 00phút, ngày 15 tháng 11 năm 2021. Có thể tìm hiểu luận văn tại: - Thư viện Học viện Khoa học và Công nghệ. 1Mở đầu Ý tưởng thực hiện luận văn này được bắt đầu từ nghiên cứucủa chúng tôi về bài toán sắp xếp thời khóa biểu trong các trườngtrung học ở Việt Nam. Sau khi khảo sát các trường hợp thực tếcủa bài toán, chúng tôi quan tâm đến một loại ràng buộc đặc biệtđối với số tiết trống của giáo viên. Cụ thể hơn, trong mỗi tiết củamỗi ngày dạy, mỗi giáo viên có thể được sắp xếp dạy hoặc không.Nếu giáo viên không được phân công dạy trong một tiết giữa haitiết dạy của cùng một ngày dạy, thì tiết nghỉ dạy đó được gọi làtiết trống của giáo viên này. Một số giáo viên yêu cầu phải cónhững tiết trống trong ngày dạy của họ, vì việc giảng dạy trongnhiều tiết liên tiếp là một khối lượng công việc nặng nề đối vớihọ. Tuy nhiên, quá nhiều tiết trống trong một ngày dạy của mộtgiáo viên có thể gây lãng phí thời gian của giáo viên, do thời gianchờ đợi lâu giữa các tiết dạy. Vì những lý do đó, các ràng buộcchúng tôi quan tâm đặt ra một giới hạn dưới và giới hạn trên đốivới số tiết trống trong mỗi ngày dạy của mỗi giáo viên. Chúng tôigọi những ràng buộc này là “ràng buộc tiết trống của giáo viên”. Những đóng góp chính của luận văn này như sau. Chúng tôixây dựng mô hình quy hoạch nguyên cho ràng buộc tiết trống củagiáo viên, và đánh giá hiệu quả của mô hình này thông qua cácthực nghiệm trên các trường hợp thực tế của bài toán. Để xâydựng mô hình này, chúng tôi đề xuất khái niệm “đa diện idle”.Chính xác hơn, chúng tôi sử dụng các biến nhị phân để quyếtđịnh giáo viên nào được sắp xếp dạy vào tiết nào. Bằng cách này,việc sắp xếp giảng dạy của mỗi giáo viên trong mỗi ngày học có 2thể được mã hóa bằng một vectơ nhị phân, trong đó một thànhphần của vectơ được gọi là idle nếu giáo viên trống tiết tương ứng.Với cách biểu diễn này, giới hạn số lượng tiết trống của giáo viêncũng là giới hạn số lượng thành phần idle của vectơ tương ứng.Mô hình quy hoạch nguyên cho ràng buộc tiết trống của giáo viênmà chúng tôi đề xuất là một hệ ràng buộc tuyến tính đối với cácbiến nhị phân, mà các nghiệm của hệ đó chính xác là các vectơ vớisố thành phần idle thỏa mãn giới hạn đã cho. Điều này gợi chochúng ta về định lý Minkowski-Weyl nổi tiếng về sự tương đươngcủa các biểu diễn của đa diện lồi. Lấy cảm hứng từ định lý này,chúng tôi định nghĩa một đa diện idle là bao lồi của các vectơ cósố thành phần idle thỏa mãn giới hạn cho trước. Mô hình quyhoạch nguyên chúng tôi đề xuất cho ràng buộc tiết trống của giáoviên chính là hệ các bất phương trình xác định các mặt của đadiện idle này. Chương 1 của luận văn nhắc lại một số khái niệm cơ bản vàkết quả quan trọng trong lý thuyết đa diện lồi. Chương 2 của luậnvăn giới thiệu khái niệm đa diện idle và đưa ra các biểu diễn chitiết cho một số trường hợp cụ thể. Chương 3 của luận văn trìnhbày ứng dụng của khái niệm đa diện idle trong việc mô hình hóaràng buộc tiết trống của giáo viên trong bài toán lập thời khóabiểu cho các trường trung học. 3Chương 1Kiến thức chuẩn bị1.1 Tập lồi và nón lồiĐịnh nghĩa 1.1. (Tập lồi). Một tập C ⊂ Rn là tập lồi nếu vớix1 , x2 ∈ C và θ ∈ [0, 1] ta có θx1 + (1 − θ)x2 ∈ C .Định nghĩa 1.2. (Tổ hợp lồi). Tổ hợp lồi của các điểm x1 , . . . , xk ∈Rn là một điểm có dạng θ1 x 1 + θ2 x 2 + . . . + θk x ktrong đó θ1 , . . . , θk ∈ [0, 1] thỏa mãn θ1 + . . . + θk = 1.Định nghĩa 1.3. (Bao lồi). Bao lồi của tập C ⊂ Rn , kí hiệuconv(C), là tập hợp gồm tất cả các tổ hợp lồi của các điểm trongC, nghĩa là conv(C) = {θ1 x1 + . . . + θk xk | xi ∈ C, θi ≥ 0, i = 1, . . . , k, θ1 + . . . + θk = 1}.Bổ đề 1.4. Cho C là tập lồi trong Rn và x1 , . . . , xk ∈ C . Khi đómọi tổ hợp lồi của các điểm x1 , . . . , xk cũng thuộc C .Bổ đề 1.5. Với tập C ⊂ Rn bất kỳ, bao lồi của nó conv(C) làmột tập lồi. 4Mệnh đề 1.6. Bao lồi conv(C) của tập C ⊂ Rn là tập lồi nhỏnhất chứa C . ...