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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:18

Thêm vào BST

Báo xấu

29
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀ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ại Viện Hàn lâm Khoa học và Công nghệ Việt Nam vào hồi 9 giờ 00 phú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ệ.
1 Mở đầu Ý tưởng thực hiện luận văn này được bắt đầu từ nghiên cứu của chúng tôi về bài toán sắp xếp thời khóa biểu trong các trường trung 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ủa mỗ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 hai tiế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 trong nhiều tiết liên tiếp là một khối lượng công việc nặng nề đối với họ. Tuy nhiên, quá nhiều tiết trống trong một ngày dạy của một giáo viên có thể gây lãng phí thời gian của giáo viên, do thời gian chờ đợi lâu giữa các tiết dạy. Vì những lý do đó, các ràng buộc chúng tôi quan tâm đặt ra một giới hạn dưới và giới hạn trên đối với số tiết trống trong mỗi ngày dạy của mỗi giáo viên. Chúng tôi gọ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ôi xây dựng mô hình quy hoạch nguyên cho ràng buộc tiết trống của giáo viên, và đánh giá hiệu quả của mô hình này thông qua các thực nghiệm trên các trường hợp thực tế của bài toán. Để xây dự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ó
2 thể được mã hóa bằng một vectơ nhị phân, trong đó một thành phầ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ên cũ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ên mà chúng tôi đề xuất là một hệ ràng buộc tuyến tính đối với các biến nhị phân, mà các nghiệm của hệ đó chính xác là các vectơ với số thành phần idle thỏa mãn giới hạn đã cho. Điều này gợi cho chúng ta về định lý Minkowski-Weyl nổi tiếng về sự tương đương củ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 quy hoạch nguyên chúng tôi đề xuất cho ràng buộc tiết trống của giáo viên chính là hệ các bất phương trình xác định các mặt của đa diệ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ận văn giới thiệu 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ể. Chương 3 của luận văn trình bày ứng dụng của 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.
3 Chương 1 Kiế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ới x1 , 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 k trong đó θ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ệu conv(C), là tập hợp gồm tất cả các tổ hợp lồi của các điểm trong C, 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.
4 Mệ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 . Định nghĩa 1.7. (Nón). Tập C ⊂ Rn là nón nếu với x ∈ C và θ ≥ 0 ta có θx ∈ C. Định nghĩa 1.8. (Nón lồi). Tập C là một nón lồi nếu với x1 , x2 ∈ C và θ1 , θ2 ≥ 0 ta có θ1 x1 + θ2 x2 ∈ C . Mệnh đề 1.9. Một nón lồi trong Rn vừa là tập lồi vừa là nón. Định nghĩa 1.10. (Tổ hợp nón). Tổ hợp nón 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 k với θ1 , . . . , θk ≥ 0. Định nghĩa 1.11. (Bao nón). Bao nón của tập C là tập hợp của tất cả các tổ hợp nón của các điểm thuộc C , nghĩa là cone(C) = {θ1 x1 + . . . + θk xk | xi ∈ C, θi ≥ 0, i = 1, . . . , k}. Mệnh đề 1.12. Bao nón cone(C) của tập C ⊂ Rd là nón lồi nhỏ nhất chứa C . 1.2 Đa diện lồi Định nghĩa 1.13. (V -đa diện). Một V -đa diện P ⊂ Rd là một tập hợp có dạng P = conv(x1 , . . . , xk ) (1.1) = {θ1 x1 + . . . + θk xk | θ1 , . . . , θk ≥ 0, θ1 + . . . + θk = 1}, trong đó k là số nguyên dương bất kì và x1 , . . . , xk các véc tơ trong Rd . Biểu thức (1.1) được gọi là V -biểu diễn của V -đa diện P .
5 Định nghĩa 1.14. (V -nón). Một V -nón C ⊂ Rd là tập hợp có dạng P = cone(v1 , . . . , vk ) = {θ1 v1 + . . . + θk vk | θ1 , . . . , θk ≥ 0}, (1.2) trong đó k là một số nguyên dương bất kì và v1 , . . . , vk các véc tơ trong Rd . Biểu thức (1.2) được gọi là V -biểu diễn của V -nón C . Định nghĩa 1.15. (H-nón). Một H-nón C ⊂ Rd là tập có dạng C = P (A, 0) = {x ∈ Rd | Ax ≤ 0}, trong đó A là ma trận trong Rn×d (với n bất kì) và 0 là véc tơ không trong Rd . Hệ tuyến tính thuần nhất Ax ≤ 0 được gọi là một H-biểu diễn của H-nón C . Định nghĩa 1.16. (H-đa diện). Một H-đa diện là tập bị chặn có dạng P = P (A, b) = {x ∈ Rd | Ax ≤ b}, trong đó A là một ma trận trong Rn×d (với n bất kì) và b ∈ Rd . Hệ tuyến tính Ax ≤ b được gọi là một H-biểu diễn của H-đa diện P. Định lý 1.17. Nếu P ⊂ Rd là một V -đa diện, nghĩa là, P là bao lồi của tập hữu hạn điểm P = conv(x1 , . . . , xn ) với x1 , . . . , xn ∈ Rd , khi đó P là H-đa diện, nghĩa là, P là giao bị chặn của các nửa không gian đóng P = P (A, z) := {x ∈ Rd | Ax ≤ z} với A ∈ Rm×d , z ∈ Rm . Bổ đề 1.18. Cho C là một H-nón trong Rd . Cho elimk (C) = {x − tek | x ∈ C, t ∈ R} projk (C) = elimk (C) ∩ Hk ,
6 trong đó Hk = {x ∈ Rd | xk = 0} Khi đó elimk (C) và projk (C) cũng là các H-nón. Bổ đề 1.19. Nếu C ⊂ Rd là một V -nón, nghĩa là, nó là bao nón của tập hữu hạn các điểm C = cone(y1 , . . . , yn ) với y1 , . . . , yn ∈ Rd , khi đó nó là H-nón, nghĩa là, giao bị chặn của các nửa không gian tuyến tính đóng P = P (A, 0) := {x ∈ Rd | Ax ≤ 0} với A ∈ Rm×d .
Chương 2 Đa diện idle 2.1 V-biểu diễn của đa diện idle Định nghĩa 2.1. Thành phần vi được gọi là một thành phần idle của véc tơ v ∈ {0, 1}n nếu tồn tại p ∈ {1, . . . , i − 1} và q ∈ {i + 1, . . . , n} sao cho vp = vq = 1, vi = 0. Với v ∈ {0, 1}n , cho f idle (v) là số lượng các thành phần idle trong v. Cho trước 0 ≤ ℓ ≤ u ≤ n − 2, kí hiệu Vnℓ,u := {v ∈ {0, 1}n | ℓ ≤ f idle (v) ≤ u}. Định nghĩa 2.2. Đa diện (ℓ, u, n)-idle được xác định bởi Pnℓ,u := conv(Vnℓ,u ). Ví dụ 2.3. Bảng 2.1 liệt kê tất cả các véc tơ nhị phân có n = 5 thành phần, cùng với số lượng thành phần idle (f idle ) của các véc tơ này. Tập hợp V50,0 chứa các véc tơ nhị phân 5-thành phần không có thành phần idle, nghĩa là, V50,0 = {v1 , v2 , v3 , v4 , v5 , v7 , v8 , v9 , v13 , v15 , v16 , v17 , v25 , v29 , v31 , v32 }, 7
8 Bảng 2.1: Véc tơ nhị phân 5-thành phần và số lượng thành phần idle tương ứng của chúng. Véc tơ Giá trị f idle Véc tơ Giá trị f idle v1 (0, 0, 0, 0, 0) 0 v17 (1, 0, 0, 0, 0) 0 v2 (0, 0, 0, 0, 1) 0 v18 (1, 0, 0, 0, 1) 3 v3 (0, 0, 0, 1, 0) 0 v19 (1, 0, 0, 1, 0) 2 v4 (0, 0, 0, 1, 1) 0 v20 (1, 0, 0, 1, 1) 2 v5 (0, 0, 1, 0, 0) 0 v21 (1, 0, 1, 0, 0) 1 v6 (0, 0, 1, 0, 1) 1 v22 (1, 0, 1, 0, 1) 2 v7 (0, 0, 1, 1, 0) 0 v23 (1, 0, 1, 1, 0) 1 v8 (0, 0, 1, 1, 1) 0 v24 (1, 0, 1, 1, 1) 1 v9 (0, 1, 0, 0, 0) 0 v25 (1, 1, 0, 0, 0) 0 v10 (0, 1, 0, 0, 1) 2 v26 (1, 1, 0, 0, 1) 2 v11 (0, 1, 0, 1, 0) 1 v27 (1, 1, 0, 1, 0) 1 v12 (0, 1, 0, 1, 1) 1 v28 (1, 1, 0, 1, 1) 1 v13 (0, 1, 1, 0, 0) 0 v29 (1, 1, 1, 0, 0) 0 v14 (0, 1, 1, 0, 1) 1 v30 (1, 1, 1, 0, 1) 1 v15 (0, 1, 1, 1, 0) 0 v31 (1, 1, 1, 1, 0) 0 v16 (0, 1, 1, 1, 1) 0 v32 (1, 1, 1, 1, 1) 0 và ta có dạng V -biểu diễn của đa diện idle-(0, 0, 5) như sau: P50,0 = conv(V50,0 ). Tương tự, các trường hợp khác người đọc có thể xem chi tiết trong cuốn luận văn. 2.2 H-biểu diễn của đa diện idle Chúng tôi sử dụng phần mềm Polymake để thu được H-biểu diễn của các đa diện lồi được giới thiệu trong Ví dụ 2.3. Chú ý
9 rằng trong những ví dụ này, các đa diện idle được miêu tả bởi V -biểu diễn của chúng. Ví dụ 2.4. Dạng H-biểu diễn được sinh ra bởi Polymake các đa diện idle đã đề cập trong Ví dụ 2.3 là như sau. • H-biểu diễn của P50,0 : x1 − x2 + x3 ≤1 x1 − x2 + x4 ≤1 x1 − x2 + x5 ≤ 1 x1 − x3 + x4 ≤1 x1 − x3 + x5 ≤ 1 x1 − x4 + x5 ≤ 1 x2 − x3 + x4 ≤1 x2 − x3 + x5 ≤ 1 x2 − x4 + x5 ≤ 1 x3 − x4 + x5 ≤ 1 x1 − x2 + x3 − x4 + x5 ≤ 1 0 ≤ x1 , x 2 , x 3 , x 4 , x 5 ≤ 1 Các trường hợp còn lại người đọc có thể xem trong cuốn luận văn.
10 Chương 3 Áp dụng vào bài toán lập thời khóa biểu 3.1 Mô tả bài toán Thời khóa biểu là sự phân công của các cặp giáo viên-môn học cho các lớp học tại các tiết học của các ngày học. Đối với bài toán lập thời khóa biểu cho các trường trung học ở Việt Nam, các ràng buộc sau đây là các ràng buộc cứng theo nghĩa là nếu ít nhất một trong số chúng bị vi phạm, thì không thể xây dựng một thời khóa biểu khả thi. (H1) Chương trình học của các lớp phải được tuân thủ. (H2) Phân công chuyên môn cho các giáo viên phải được tuân thủ. (H3) Mỗi lớp học được ấn định trước các tiết học trong tuần. (H4) Tại mỗi thời điểm, mỗi giáo viên được phân công dạy nhiều nhất một lớp. Ở đây, chương trình học quy định sự phân bổ lớp nào học môn nào trong thời gian bao nhiêu tiết mỗi tuần, phân công chuyên môn quy định giáo viên nào được sắp xếp dạy môn nào cho lớp nào. Ngoài các ràng buộc cứng nêu trên, có các ràng buộc bổ sung đến từ đặc điểm của thời khóa biểu và yêu cầu của giáo viên.
11 Chúng tôi xem xét các loại ràng buộc phổ biến nhất sau đây. (C1) Số tiết mà mỗi lớp học mỗi môn trong mỗi ngày học bị giới hạn. (C2) Một số môn học không được dạy cho một số lớp học vào một số thời gian (tiết học của ngày học) cố định. (C3) Một số môn học được dạy cho một số lớp học vào thời gian (tiết học của lớp học) cố định. (C4) Một số giáo viên được sắp xếp để không dạy vào một thời gian (tiết học của ngày học) cố định. Ngoài ra, loại ràng buộc sau đây thường được tính đến trong quá trình xây dựng thời khóa biểu cho các trường phổ thông Việt Nam. (C5) Số tiết trống trong một ngày học của một số giáo viên bị chặn trên và chặn dưới. 3.2 Mô hình hóa Kí hiệu tập các lớp học, ngày học, tiết học, môn học, và giáo viên lần lượt bởi C, D, P, S, và T . Chúng tôi sử dụng các biến nhị phân xcdpst , trong đó các chỉ số c, d, p, s, và t tương ứng lấy các giá trị từ các tập hợp C , D, P , S , và T . Biến xcdpst = 1 khi giáo viên t được sắp xếp để dạy môn s tại tiết p của ngày học d cho lớp c, ngược lại thì xcdpst = 0. Đặt A1 := {(s, c) ∈ S × C | môn học s được dạy cho lớp c}, A2 := {(t, s, c) ∈ T × A1 | giáo viên t dạy môn học s cho lớp c}, A3 := {(c, d, p) ∈ C × D × P | lớp c học tiết p của ngày d}, IX := {(c, d, p, s, t) | (t, s, c) ∈ A2 , (c, d, p) ∈ A3 }, X := {xcdpst | (c, d, p, s, t) ∈ IX }.
12 Sử dụng các biến trong tập hợp X , các ràng buộc cứng (H2) và (H3) tự động được thỏa mãn. Các ràng buộc còn lại được mô hình hóa như sau. (H1) Chương trình học của các lớp phải được tuân thủ ∑ xcdpst = αs¯,¯c ∀(¯ s, c¯) ∈ A1 , (c,d,p,s,t)∈IX (s,c)=(¯s,¯ c) trong đó αs,c là số tiết dạy môn s mỗi tuần cho lớp c. (H4) Mỗi giáo viên dạy nhiều nhất 1 lớp tại mỗi thời điểm. ∑ ¯ p¯, t¯) ∈ D × P × T. xcdpst ∀(d, (c,d,p,s,t)∈IX ¯ p,t¯) (d,p,t)=(d,¯ (C1) Giới hạn số tiết dạy mỗi môn học cho mỗi lớp học trong mỗi ngày học. ∑ xcdpst ≤ βc¯,¯s , (c,d,p,s,t)∈IX (c,s)=(¯c,¯ s) trong đó βc,s là giới hạn số tiết dạy môn s cho lớp c trong mỗi ngày. (C2) Môn s¯ không được xếp dạy cho lớp c¯ vào tiết p¯ của ngày d¯. ∑ xcdpst = 0. (c,d,p,s,t)∈IX (c,d,p,s)=(¯ ¯ p,¯ c,d,¯ s) (C3) Môn s¯ được xếp dạy cho lớp c¯ vào tiết p¯ của ngày d¯. ∑ xcdpst = 1. (c,d,p,s,t)∈IX (c,d,p,s)=(¯ ¯ p,¯ c,d,¯ s) (C4) Giáo viên t¯ được xếp nghỉ dạy tiết p¯ của ngày d¯. ∑ xcdpst = 0. (c,d,p,s,t)∈IX ¯ p,t¯) (d,p,t)=(d,¯
13 (C5) Giáo viên t¯ dự kiến sẽ có ít nhất ℓ và nhiều nhất u tiết trống trong ngày học d¯ (trong đó 0 ≤ ℓ ≤ u ≤ |P | − 2). Đặt ∑ vi := xcdpst (i ∈ {1, . . . , |P |}). (c,d,p,s,t)∈IX ¯ t¯) (d,p,t)=(d,i, Đặt v = (v1 , . . . , v|P | ). Khi đó v ∈ {0, 1}|P | , và số lượng thành phần idle trong v bằng với số lượng tiết trống của giáo viên t¯ trong ngày học d¯. Do đó, ràng buộc mà chúng ta đang xem xét tương đương với việc nói rằng số lượng các thành phần idle trong v nằm trong khoảng từ ℓ tới u. Bất kì H-biểu diễn của đa diện idle (ℓ, u, |P |) cung cấp cho chúng ta một công thức của ràng buộc này. Ví dụ, trong trường hợp |P | = 5, ℓ = 0, và u = 1, chúng ta suy ra từ H-biểu diễn của P50,1 trình bày trong mục 2.2 công thức sau đây cho (C5). v1 − v3 − v4 + v5 ≤ 1 v1 − v2 − v3 + v4 ≤1 v2 − v3 − v4 + v5 ≤ 1 2v1 − v2 − v3 − v4 + 2v5 ≤ 2 v1 − v2 − v3 + v5 ≤ 1 v1 − v2 − v4 + v5 ≤ 1 3.3 Thực nghiệm số Chúng tôi sử dụng ZIMPL 3.4.0 (cf. [?]) để cài đặt mô hình được đề xuất ở trên, và sử dụng GUROBI 9.1.1 (cf. [?]) để giải số mô hình này. Các thực nghiệm của chúng tôi được thực hiện trên máy tính PC Intel(R) Core (TM) i7-6700 CPU 2*2.60GHz, RAM 16 GB. Chúng tôi thực nghiệm mô hình trên dữ liệu từ một bài toán lập thời khóa biểu trong thực tế, với 54 giáo viên, 17 môn học, 21
14 lớp học, và 593 tiết học trong tuần. Để đánh giá ảnh hưởng của ràng buộc số tiết trống, chúng tôi đã thực hiện các thực nghiệm sau đây. • Thực nghiệm 1: tất cả giáo viên yêu cầu không có tiết trống trong thời gian biểu của họ. • Thực nghiệm 2: tất cả giáo viên yêu cầu có nhiều nhất 1 tiết trống trong mỗi ngày dạy trong thời khóa biểu của họ. • Thực nghiệm 3: tất cả giáo viên yêu cầu có nhiều nhất 2 tiết trống trong mỗi ngày dạy trong thời khóa biểu của họ. Bảng 3.1: Một số kết quả thực nghiệm mô hình được đề xuất trên một ví dụ về bài toán sắp xếp thời khóa biểu thực tế. Thí nghiệm Số biến Số ràng buộc Thời gian chạy (s) Thí nghiệm 1 10333 9716 18.93 Thí nghiệm 2 10333 8096 0.56 Thí nghiệm 3 10333 6476 0.22 Kết quả trong Bảng 3.1 cho thấy tính hiệu quả của mô hình chúng tôi đề xuất.
15 Kết luận Trong luận văn này, chúng tôi đề xuất khái niệm đa diện idle như một lớp đa diện lồi đặc biệt. Chúng tôi tập trung vào khía cạnh ứng dụng của khái niệm này thông qua việc sử dụng các đa diện idle trong việc mô hình hóa các ràng buộc tiết trống của giáo viên trong các bài toán xếp thời khóa biểu bậc trung học ở Việt Nam. Để có cơ sở lý thuyết cho việc nghiên cứu khái niệm được đề xuất, trong Chương 1, chúng tôi nhắc lại một số khái niệm và kết quả liên quan trong lý thuyết đa diện lồi. Một đa diện lồi có thể được biểu diễn bằng bao lồi của một tập hợp hữu hạn các điểm (V -biểu diễn), hoặc giao của một số hữu hạn các nửa không gian đóng (H-biểu diễn). Chúng tôi cũng đưa ra chứng minh chi tiết về một phần của định lý Minkowski-Weyl khẳng định rằng, với một V -biểu diễn của một đa diện lồi, chúng ta có thể thu được một H-biểu diễn cho đa diện đó. Trong Chương 2, chúng tôi định nghĩa khái niệm đa diện idle là bao lồi của một tập hợp các vectơ thành phần nhị phân, trong đó mỗi vectơ như vậy biểu thị trạng thái thực hiện một hành động trong một chuỗi các khung thời gian hữu hạn. Sau đó, chúng tôi trình bày chi tiết H-biểu diễn của một số ví dụ về đa diện idle. Chương 3 trình bày một ứng dụng cho khái niệm đa diện idle. Trong chương này, trước tiên, chúng tôi mô tả bài toán sắp xếp thời khóa biểu ở các trường trung học Việt Nam, trong đó chúng tôi nhấn mạnh đến ràng buộc về số tiết trống của giáo viên như một đặc thù của bài toán. Những ràng buộc này áp đặt giới hạn
16 dưới và giới hạn trên đối với số lượng tiết trống trong mỗi ngày dạy của mỗi giáo viên. Sau đó, chúng tôi mô hình hóa bài toán sắp xếp thời khóa biểu dưới dạng quy hoạch nguyên, trong đó chúng tôi sử dụng H-biểu diễn của các đa diện idle để mô hình hóa ràng buộc giới hạn số tiết trống của giáo viên. Các thực nghiệm số trên các trường hợp thực tế của bài toán sắp xếp thời khóa biểu ở trường cho thấy tính hữu ích và hiệu quả của mô hình của chúng tôi. Có một số vấn đề chúng tôi muốn theo đuổi sau khi thực hiện luận văn này. Về khía cạnh tổ hợp, chúng tôi dự định tính số đỉnh và số mặt của các đa diện idle. Về khía cạnh ứng dụng, chúng tôi dự định nghiên cứu khả năng ứng dụng của các đa diện idle trong việc mô hình hóa các vấn đề thực tế khác.