Đại Học Quốc Gia TP. Hồ Chí Minh
TRƯỜNG ĐẠI HỌC BÁCH KHOA
----------------------

TRẦN SƠN HÀ

DÙNG PHƯƠNG PHÁP COLUMN GENERATION Đ Ể SẮP
XẾP THỜI KHĨA BIỂU MƠN HỌC
Chun ngành: Khoa Học Máy Tính

LUẬN VĂN THẠC SĨ

TP. Hồ Chí Minh, tháng 12 năm 2008


CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI
TRƯỜNG ĐẠI HỌC BÁCH KHOA
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH

Cán bộ hướng dẫn khoa học : Tiến sĩ Trần Văn Hoài

Cán bộ chấm nhận xét 1 :

Tiến sĩ Nguyễn Văn Minh Mẫn

Cán bộ chấm nhận xét 2 :

Tiến sĩ Nguyễn Đức Cường

Luận văn thạc sĩ được bảo vệ tại

HỘI ĐỒNG CHẤM BẢO VỆ LUẬN VĂN THẠC SĨ
TRƯỜNG ĐẠI HỌC BÁCH KHOA , ngày 10 tháng 02 năm 2009


ĐẠI HỌC QUỐC GIA TP. HCM
TRƯỜNG ĐẠI HỌC BÁCH KHOA
----------------

CỘNG HOÀ XÃ HỘI CHỦ NGHIÃ VIỆT
NAM
Độc Lập - Tự Do - Hạnh Phúc
---oOo--Tp. HCM, ngày 10 tháng 02 năm 2009

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ và tên học viên: TRẦN SƠN HÀ

Giới tính : Nam

Ngày, tháng, năm sinh : 01/07/1982

Nơi sinh : Bình Thuận.

Chun ngành : Khoa Học Máy Tính
Khố (Năm trúng tuyển) : 2006
1- TÊN ĐỀ TÀI:
“Dùng phương pháp Column Generation đ ể sắp xếp thời khóa biểu mơn học”
2- NHIỆM VỤ LUẬN VĂN

Generation


Nghiên cứu lý thuyết về quy hoạch nguy ên và phương pháp Column


Đề xuất mơ hình Column Generation thích h ợp với bài tốn sắp xếp thời khóa
biểu mơn học

Xây dựng chương trình tự động sắp xếp thời khóa biểu mơn học cho tr ường
Đại Học Bách Khoa thành phố Hồ Chí Minh
3- NGÀY GIAO NHIỆM VỤ : 21/01/2008
4- NGÀY HOÀN THÀNH NHI ỆM VỤ : 10/02/2009
5- HỌ VÀ TÊN CÁN BỘ HƯỚNG DẪN: Tiến sĩ Trần Văn Hoài
Nội dung và đề cương Luận văn thạc sĩ đã được Hội Đồng Chuyên Ngành thông qua.
CÁN BỘ HƯỚNG DẪN
(Họ tên và chữ ký)

Tiến sĩ Trần Văn Hoài

CHỦ NHIỆM BỘ MÔN
QUẢN LÝ CHUYÊN NGÀNH
(Họ tên và chữ ký)


LỜI CẢM ƠN
Tơi xin gởi lời cảm đến gia đình, những người luôn sát cánh động vi ên, và tạo mọi điều kiện
tốt để tơi hồn thành luận văn này.
Xin chân thành cám ơn anh Nguy ễn Dương Tường Lam, giám đốc công ty TNHH Niềm Tin
Việt, người đã tạo điều kiện cho tôi học Cao học trong thời gian cơng tác tại cơng ty. Nếu
khơng có sự giúp đỡ q báu của anh th ì tơi khó có thể hồn thành khóa học của mình.
Xin chân thành cám ơn th ầy TS. Trần Văn Hồi, đã nhiệt tình hướng dẫn tơi hồn thành tốt
luận văn này.

Cuối cùng, xin gởi lời cám ơn đến các thầy cơ đã tận tình dạy dỗ và giúp đỡ trong suốt thời
gian tôi tham gia khóa học.

Dùng Phương Pháp Column Generation để Sắp Xếp Thời Khóa Biểu Mơn Học

Trang i


TĨM TẮT
Bài tốn sắp xếp thời khóa biểu mơn học l à một bài toán tối ưu tổ hợp. Các hướng tiếp cận
cho bài toán này chủ yếu là lập trình ràng buộc và tìm kiếm cục bộ. Luận văn này trình bày
một phương pháp mới, dựa vào nền tảng quy hoạch nguyên, đó là phương pháp Column
Generation. Ý tưởng của phương pháp này là tạo ra các “column”, mỗi column sẽ đại diện
cho một nghiệm của bài toán. Các column này được tạo một phần hay tạo to àn bộ là tùy
thuộc vào kích thước của dữ liệu bài tốn. Sau đó, sử dụng các giải thuật của quy hoạch
nguyên để tìm ra nghiệm tối ưu.
Luận văn đã sử dụng BCP framework để xây dựng ch ương trình sắp xếp thời khóa biểu mơ n
học cho trường Đại học Bách Khoa Tp. HCM và tiến hành thử nghiệm, đánh giá trên dữ liệu
thực.

Dùng Phương Pháp Column Generation để Sắp Xếp Thời Khóa Biểu Mơn Học

Trang ii


ABSTRACT
The uinversity course timetabling is a well -studied combinatorial optimization problem. The
common approachs for this problem are constraint programming and local search. In this
thesis, we’d like to present a new approach, based on integer programming. That is Column
Generation. The basic idea of this approach is to produce some columns, each column

represents to a solution. These columns are produced totally or partially depend on the
problem. Subsequently, some integer programming algorithms are used to give an optimal
solution.
We use BCP framework to implement university timetabling program for HCMC University
of Technology and test, evaluate problem’s results on real data.

Dùng Phương Pháp Column Generation để Sắp Xếp Thời Khóa Biểu Mơn Học

Trang iii


MỤC LỤC
LỜI CẢM ƠN................................ ................................ ................................ ....................... i
TÓM TẮT ................................ ................................ ................................ ........................... ii
ABSTRACT ................................ ................................ ................................ ....................... iii
MỤC LỤC ................................ ................................ ................................ .......................... iv
DANH MỤC HÌNH ẢNH................................ ................................ ................................ ... vi
DANH MỤC BẢNG................................ ................................ ................................ .......... vii
Chương 1
GIỚI THIỆU ................................ ................................ ................................ .. 1
1.1
Mục tiêu nghiên cứu ................................ ................................ ............................. 1
1.2
Nhiệm vụ của luận văn ................................ ................................ ......................... 1
1.2.1
Mục đích của chương trình sắp xếp thời khóa biểu mơn học ........................... 1
1.2.2
Các quy tắc học vụ ................................ ................................ ......................... 1
1.2.3
Các yêu cầu đặt ra................................ ................................ ........................... 2

1.3
Kết quả của luận văn ................................ ................................ ............................ 3
1.4
Cấu trúc nội dung luận văn ................................ ................................ ................... 4
Chương 2
CÁC CƠNG TRÌNH LIÊN QUAN ................................ ................................ 5
2.1
Phương pháp xây dựng tuần tự ................................ ................................ ............. 5
2.2
Lập trình ràng buộc ................................ ................................ .............................. 5
2.3
Tìm kiếm cục bộ................................ ................................ ................................ ... 6
2.4
Quy hoạch nguyên................................ ................................ ................................ 7
2.5
Kết luận ................................ ................................ ................................ ................ 7
Chương 3
CƠ SỞ LÝ THUYẾT ................................ ................................ ..................... 9
3.1
Quy hoạch tuyến tính................................ ................................ ............................ 9
3.1.1
Định nghĩa quy hoạch tuyến tính ................................ ................................ .... 9
3.1.2
Sự tồn tại nghiệm và tính chất tập nghiệm của quy hoạch tuyến tính ............ 11
3.1.3
Phương pháp đơn hình để giải bài tốn quy hoạch tuyến tính chính tắc ........ 11
3.1.4
Tìm phương án cực biên xuất phát và cơ sở xuất phát – Phương pháp biến giả
cải biên ................................ ................................ ................................ ..................... 18
3.1.5

Đối ngẫu................................ ................................ ................................ ....... 20
3.2
Quy hoạch nguyên................................ ................................ .............................. 22
3.2.1
Phương pháp nhánh cận................................ ................................ ................ 23
3.2.2
Phương pháp mặt phẳng cắt ................................ ................................ .......... 26
3.2.3
Phương pháp branch-and-cut ................................ ................................ ........ 28
3.3
Column Generation ................................ ................................ ............................ 28
3.3.1
Giới thiệu ................................ ................................ ................................ ..... 28
3.3.2
Phân rã Dantzig-Wolfe ................................ ................................ ................. 29
3.3.3
Column Generation cho bài tốn quy ho ạch tuyến tính ................................ . 30
3.3.4
Column Generation cho bài toán Quy ho ạch nguyên ................................ .... 32
3.4
Kết luận ................................ ................................ ................................ .............. 38
Chương 4
PHƯƠNG PHÁP GIẢI BÀI TỐN SẮP XẾP THỜI KHĨA BIỂU MƠN
HỌC
................................ ................................ ................................ ..................... 40
4.1
Giới thiệu ................................ ................................ ................................ ........... 40
4.2
Mô tả bài toán................................ ................................ ................................ ..... 40
4.2.1

Các quy tắc học vụ ................................ ................................ ....................... 40
4.2.2
Các yêu cầu đặt ra................................ ................................ ......................... 41
4.2.3
Mơ hình hóa bài tốn ................................ ................................ .................... 42
Dùng Phương Pháp Column Generation để Sắp Xếp Thời Khóa Biểu Mơn Học

Trang iv


4.3
Các thành phần chính của giải thuật ................................ ................................ .... 46
4.3.1
Khởi tạo nghiệm ban đầu ................................ ................................ .............. 46
4.3.2
Branching ................................ ................................ ................................ ..... 47
4.3.3
Pricing ................................ ................................ ................................ .......... 48
4.3.4
Upper bounding ................................ ................................ ............................ 51
Chương 5
HIỆN THỰC VÀ THỬ NGHIỆM ................................ ................................ 53
5.1
Hiện thực bài tốn sắp xếp thời khóa biểu môn học ................................ ............ 53
5.1.1
BCP Framework ................................ ................................ ........................... 53
5.1.2
Tổ chức dữ liệu của bài toán ................................ ................................ ......... 54
5.2
Thử nghiệm ................................ ................................ ................................ ........ 56

5.2.1
Thống kế số liệu thử nghiệm ch ương trình sắp xếp thời khóa biểu mơn học . 56
5.2.2
Kết quả thử nghiệm ................................ ................................ ...................... 56
Chương 6
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ................................ ..................... 60
6.1
Kết luận ................................ ................................ ................................ .............. 60
6.2
Hướng phát triển................................ ................................ ................................ . 60
TÀI LIỆU THAM KHẢO ................................ ................................ ................................ .. 62
Phụ lục A CƠ SỞ DỮ LIỆU THẬT CỦA CH ƯƠNG TRÌNH ................................ ......... 64
Phụ lục B BCP FRAMEWORK ................................ ................................ ....................... 70
Phụ lục C CÁC THUẬT NGỮ ................................ ................................ .......................... 72

Dùng Phương Pháp Column Generation để Sắp Xếp Thời Khóa Biểu Môn Học

Trang v


DANH MỤC HÌNH ẢNH
Hình 3.1: Giải thuật đơn hình................................ ................................ ......................... 18
Hình 3.2: Giải thuật hai pha ................................ ................................ ........................... 19
Hình 3.3: Giải thuật branch-and-bound ................................ ................................ .......... 23
Hình 3.4: Giải thuật cutting-plane ................................ ................................ .................. 28
Hình 3.5: Sơ đồ khối phương pháp Column Generation ................................ ................. 32
Hình 3.6: Giải thuật branch-and-price ................................ ................................ ............ 37
Hình 4.1: Ma trận các vector cột ................................ ................................ .................... 47
Hình 4.2: Giải thuật local search cho b ài tốn pricing ................................ .................... 49
Hình 4.3: Giải thuật branch-and-bound cho bài tốn pricing ................................ .......... 51

Hình 4.4: Giải thuật tìm upper bound ................................ ................................ ............. 52
Hình 5.1: Sơ đồ khối của BCP framework ................................ ................................ ...... 54
Hình 5.2: Dữ liệu bài tốn theo mơ hình UML ................................ ............................... 55
Hình 5.3: Thử nghiệm cho 15 lớp................................ ................................ ................... 58

Dùng Phương Pháp Column Generation để Sắp Xếp Thời Khóa Biểu Mơn Học

Trang vi


DANH MỤC BẢNG
Bảng 3.1: Cặp bài toán quy hoạch tuyến tính đối ngẫu ................................ ................... 20
Bảng 5.1: Bảng các số liệu thử nghiệm ................................ ................................ .......... 56
Bảng 5.2: Bảng các kết quả cần t hống kê ................................ ................................ ....... 57
Bảng 5.3: Thử nghiệm cho 5 lớp ................................ ................................ .................... 57
Bảng 5.4: Thử nghiệm cho 10 lớp ................................ ................................ .................. 58

Dùng Phương Pháp Column Generation để Sắp Xếp Thời Khóa Biểu Môn Học

Trang vii


Chương 1

GIỚI THIỆU

1.1 Mục tiêu nghiên cứu
Trong những năm gần đây, trường Đại học Bách Khoa Tp HCM, cũng nh ư nhiều trường đại
học khá trong thành phố, đã liên tục phát triển về số lượng các khoa cũng như số lượng sinh
viên vào học. Bài toán này nếu được thực hiện bằng tay th ì rất phức tạp. Do đó cần một

chương trình hỗ trợ sắp xếp thời khóa biểu ho àn toàn tự động. Đứng trước nhu cầu trên, đã
có nhiều nghiên cứu của các học viên và sinh viên khóa trư ớc đề xuất các cách tiếp cận khác
nhau. Tuy nhiên, hầu hết các nghiên cứu này đều sử dụng kỹ thuật lập tr ình ràng buộc và
tìm kiếm cục bộ để giải và kết quả là cho nghiệm khá tốt nhưng không tối ưu [18], [19].
Mục tiêu của luận văn này là nghiên cứu áp dụng một cách tiếp cận mới để giải b ài toán sắp
xếp thới khóa biểu. Đó là phương pháp quy hoạch nguyên mà cụ thể là Column Generation.
Thế mạnh của phương pháp này là giải ra nghiệm tối ưu và thích hợp cho các bài tốn tối ưu
tổ hợp có kích thước lớn. Đề tài này cịn có nhiệm vụ nghiên cứu mơ hình quy hoạch
ngun phù hợp với các ràng buộc mềm đặc thù của trường Đại học Bách Khoa Tp. HCM.
Tuy nhiên, kết quả thực hiện của luận văn cũng có thể mở rộng sang các c ơ sở đào tạo khác
nếu tìm ra được cách mơ hình hóa thích hợp.

1.2 Nhiệm vụ của luận văn
Những đặc điểm của bài tốn sắp xếp thời khóa biểu mơn học th ường thay đổi theo từng
trường đại học/cao đẳng. Ri êng đề tài nghiên cứu này chủ yếu dựa vào những đặc trưng
riêng của việc sắp xếp thời khóa biểu mơ n học ở trường Đại học Bách Khoa Tp. HCM.
1.2.1 Mục đích của chương trình sắp xếp thời khóa biểu mơn học
Chương trình sắp xếp thời khóa biểu mơn học có nhiệm vụ sắp xếp thời khóa biểu cho tất cả
các lớp trong một học kỳ thỏa mãn tất cả các ràng buộc cứng và tối ưu hóa các ràng buộc
mềm.
1.2.2 Các quy tắc học vụ
Các thuật ngữ
 Lớp cứng (stable class): l à một nhóm sinh viên được ghép cố định khi vào trường. Ở
đây, ta giả thiết rằng trong một học k ì, tất cả sinh viên thuộc cùng lớp cứng sẽ học
cùng lớp môn học ở tất cả các mơn học mà các sinh viên này có đăng kí mơn h ọc.
 Lớp mơn học (group): trong học k ì, một mơn học có thể mở th ành nhiều lớp môn
học. Mỗi lớp môn học do một hay nhiều lớp cứng ghép lại nhằm đủ một số l ượng
sinh viên nào đó để mở lớp.
 Phân tiết (meeting): Mỗi lớp mơn học có thể học một hay nhiều cụm tiết trong một
tuần. Mỗi cụm tiết học của một lớp mơn học cụ thể n ào đó được gọi là một phân tiết.

Dùng Phương Pháp Column Generation đ ể Sắp Xếp Thời Khóa Biểu Mơn Học

Trang 1


 Phịng học (room): Mỗi lớp mơn học có thể đ ược tổ chức trong một ph òng học tại
một thời điểm nhất định. Mỗi ph òng học được đặc trưng bởi sức chứa, loại phịng
học.
Quy trình nghiệp vụ
Trước khi bắt đầu học kì mới, Phịng Đào tạo sẽ dựa vào thơng tin về chương trình đào tạo,
lớp sinh viên (lớp cứng) để tạo ra danh sách các lớp môn học dự kiến sẽ đ ược tổ chức giảng
dạy trong học kì. Mỗi lớp mơn học có thể có một hay nhiều phân tiết trong tuần. Thơng tin
về các phịng học trong trường cũng được tập hợp
lại để làm dữ liệu đầu vào khi xếp thời khóa biểu.
Các phân tiết là đơn vị được xếp thời khoá biểu : phân tiết được diễn ra vào tiết nào của một
ngày trong tuần, và tại phịng nào.
Thời khố biểu cho một lớp cứng , hay cho một sinh viên sẽ được trích ra dựa vào
thời khoá biểu đã xếp cho các phân tiết.
1.2.3 Các yêu cầu đặt ra
Chương trình sắp xếp thời khóa biểu mơn học phải đáp ứ ng các u cầu sau: thỏa mãn các
ràng buộc cứng, và tối ưu hóa các ràng buộc mềm.
Ràng buộc cứng về xếp thời gian cho phân tiết
 Các phân tiết xung đột nhau khơng đ ược diễn ra trong các cụm tiết có phần “phủ lấp”
nhau.
 Các phân tiết phải được dạy trọn vẹn trong một buổi của một ngày trong tuần. Một
phân tiết không được cắt ra thành các tiết cuối buổi sáng và đầu buổi chiều hay cuồi
ngày này và đầu ngày kia.
 Một số phân tiết được quy định tránh không đ ược xếp vào một số tiết học cụ thể nào
đó.


Ràng buộc mềm về xếp thời gian cho phân tiết
 Thời khoá biểu của một sinh vi ên (hay một lớp cứng) nên hạn chế các ngày học cả
hai buổi sáng và chiều.
 Trong thời khoá biểu của một sinh viên (hay một lớp cứng), các tiết học của một buổi
học nào đó phải liên tục, khơng có những tiết trống xen giữa.
 Các phân tiết của cùng một lớp mơn học nên diễn ra cách nhau ít nhất một ng ày.
 Các phân tiết không nên được xếp vào ngày thứ bảy.
 Các phân tiết trong một thời khố biểu của một lớp cứng khơng n ên được xếp đơn lẻ
rải rác ở các buổi học trong tuần, khiến sinh vi ên phải vào trường quá nhiều buổi học
mà mỗi buổi chỉ học một phân tiết, l àm ảnh hưởng đến thời gian tự học của sinh vi ên.
Dùng Phương Pháp Column Generation đ ể Sắp Xếp Thời Khóa Biểu Mơn Học

Trang 2


 Các phân tiết cùng một môn học của các lớp cứng n ên được xểp rải rác vào các tiết
học trong tuần để tiện cho việc xếp giảng vi ên.
Ràng buộc cứng về xếp phòng cho phân tiết
 Các phân tiết phải được xếp vào phịng có tính chất phòng phù hợp.
 Tại mỗi thời điểm, một ph òng chỉ được gán cho một phân tiết duy nhất n ào đó.
 Số sinh viên trong lớp mơn học của phân tiết phải phù hợp với sức chứa của phòng.
Ràng buộc mềm về xếp phòng cho phân tiết
 Các lớp mơn học nên được xếp vào các tịa nhà phân bổ theo khoa quản lý mơn học
đó.
 Những phân tiết trong cùng một buổi học của một lớp cứng n ên được xếp học ở
những phòng học gần nhau.
 Các phòng học được sử dụng tối ưu về sức chứa, tránh trường hợp phịng có sức chứa
lớn được xếp cho phân tiết có số sinh vi ên nhỏ hơn nhiều.
Tóm lại bài tốn sắp xếp thời khóa biểu bao gồm nhiều loại r àng buộc khác nhau mà chương
trình phải cố gắng thỏa mãn. Đối với các ràng buộc cứng, đây là bài toán thỏa mãn ràng

buộc. Đối với ràng buộc mềm, đây là bài toán tối ưu tổ hợp.
Dữ liệu mẫu cho bài tốn sắp xếp thời khóa biểu mơn học gồm 378 lớp, 1864 phân tiết và
212 phịng học.

1.3 Kết quả của luận văn
Kết quả của luận văn gồm những nội dung chính sau:
 Nghiên cứu các cơng trình liên quan đến bài tốn sắp xếp thời khóa biểu môn học đ ã
được công bố gần đây trong đó chú ý đến các nghi ên cứu sử dụng quy hoạch nguy ên.
Đề tài cũng tổng hợp lý thuyết về quy hoạch nguyên và Column Generation đ ể áp
dụng vào bài tốn sắp xếp thời khóa biểu mơn học.
 Đề tài cũng nghiên cứu mơ hình sắp xếp thời khóa biểu hiện tại của tr ường Đại học
Bách Khoa Tp.HCM, phân tích ưu như ợc điểm của mơ hình này khi áp dụng phương
pháp Column Generation đ ồng thời cũng đề xuất ra mơ h ình mới thỏa mãn các ràng
buộc cứng cũng như các ràng buộc mềm.
 Áp dụng mơ hình đã đề xuất để xây dựng một ch ương trình tự động sắp xếp thời
khóa biểu mơn học cho trường Đại học Bách Khoa Tp. HCM.
 Phân tích, đánh giá kết quả thực nghiệm trên các dữ liệu có kích thước nhỏ, đồng thời
cũng phát hiện các hiệu ứng bất th ường và đã khắc phục các hiệu ứng này.

Dùng Phương Pháp Column Generation đ ể Sắp Xếp Thời Khóa Biểu Mơn Học

Trang 3


1.4 Cấu trúc nội dung luận văn
Nội dung của luận văn được trình bày thành 6 chương. Trong chương 1, luận văn giới thiệu
mục tiêu nghiên cứu của đề tài qua đó nêu rõ bài tốn sắp xếp thời khóa biểu môn học của
trường Đai học Bách Khoa Tp. HCM, xác định cụ thể các mục ti êu và kết quả đạt được của
luận văn.
Trong chương 2, luận văn trình bày các cơng trình đã nghiên cứu gần đây có liên quan đến

nhiệm vụ của luận văn, phần n ày tập trung nêu rõ các tác giả và các công trình họ đã làm
được, đồng thời nêu lên các vấn đề còn tồn tại trong các nghiên cứu trước, qua đó nêu lên
phương hướng mà đề tài sẽ giải quyết.
Trong chương 3, luận văn trình bày cơ sở lý thuyết cho đề tài. Phần đầu là lý thuyết về quy
hoạch tuyến tính. Đây chính là cơ sở cho các phương pháp giải bài tốn quy hoạch tuyến
tính và quy hoạch nguyên. Phần tiếp theo trình bày lý thuyết về quy hoạch nguyên, trong
phần này giới thiệu hai phương pháp thông dụng để giải bài tốn quy hoạch ngun, đó là
phương pháp branch-and-bound và branch-and-cut. Phần cuối cùng là cơ sở lý thuyết của
phương pháp Column Generation đ ể giải bài tốn quy hoạch ngun cỡ lớn. Đây chính là
phương pháp mà luận văn sử dụng để giải b ài toán sắp xếp thời khóa biểu mơn học.
Trong chương 4, luận văn trình bày chi tiết mơ hình bài tốn sắp xếp thời khóa biểu mơn
học, phương pháp Column Generation đ ể giải bài tốn trong đó gồm các giai đoạn: tạo ra lời
giải khả thi ban đầu, giai đoạn branching v à giai đoạn tạo ra các column.
Trong chương 5, luận văn trình bày cách thức hiện thực bài tốn sắp xếp thời khóa biểu mơn
học bao gồm trình bày tổng quan BCP framework l à framework mà đề tài sử dụng để hiện
thực. Luận văn cũng trình bày các mơ hình dữ liệu sử dụng trong bài tốn. Phần cuối cùng là
các thử nghiệm của bài tốn.
Chương 6 trình bày kết luận và hướng phát triển cho đề tài.

Dùng Phương Pháp Column Generation đ ể Sắp Xếp Thời Khóa Biểu Môn Học

Trang 4


Chương 2

CÁC CƠNG TRÌNH LIÊN QUAN

2.1 Phương pháp xây dựng tuần tự
Đây là nhóm phương pháp ra đ ời sớm nhất để giải bài tốn sắp xếp thời khóa biểu môn học

trong trường học. Theo những ph ương pháp này, các môn h ọc được chia tiết học tuần tự
từng môn một cho đến khi tất cả các môn học đ ã được chia. Tiêu biểu của nhóm phương
pháp này là giải thuật tô màu đồ thị (graph coloring). Mỗi đỉnh của đồ thị là một môn học.
Một cạnh nối hai đỉnh đó nếu hai mơn học t ương ứng với mỗi đỉnh có cùng sinh viên đăng
ký. Selim [20] đã sử dụng phương pháp tô màu đồ thị để sắp xếp thời khóa biểu mơn học
trong đó các đỉnh được chia thành các tập khác nhau để giảm số m àu tô. Neufeld và Tartar
[21] hiện thực giải thuật này cho bài tốn lên lịch phân cơng giảng dạy (class-teacher
scheduling). Trong thời gian gần đây có Asratian v à de Werra [22] cũng giải bài tốn này
với nhiều nhóm giờ dạy khác nhau.
Nhược điểm chính của phương pháp tơ màu đồ thị cho bài tốn sắp xếp thời khóa biểu mơn
học là giải thuật này khó thích ứng với lớp bài tốn có nhiều ràng buộc, nhất là các bài tốn
có thêm các ràng buộc mềm do việc diễn tả q nhiều r àng buộc sẽ làm mơ hình đồ thị trở
nên rất phức tạp, việc tối ưu cho các ràng buộc mềm khơng cịn hiệu quả.

2.2 Lập trình ràng buộc
Dùng lập trình ràng buộc, thơng qua các ngơn ngữ lập tr ình ràng buộc (Constraint Logic
Proggramming - CLP) hoặc các giải thuật giải hệ r àng buộc để giải bài tốn sắp xếp thời
khóa biểu mơn học. Các ngơn ngữ lập tr ình ràng buộc khá phổ biến là CHIP, OZ,
CLP(FD),v.v…
Để tìm kiếm lời giải, CLP sẽ sinh ra các trị cho biến, lan truyền các r àng buộc để loại bỏ các
nhánh không cần thiết trong quá trình tìm kiếm. CLP sử dụng phương pháp tìm kiếm có
quay lui để hướng q trình tìm kiếm sang các nhánh khác kh i các ràng buộc bị vi phạm.
Azevedo và Barahoma [8] đã sử dụng ngơn ngữ lập trình ràng buộc DOMLOG kết hợp với
heuristic kiểm tra hướng tới để sắp xếp thời khóa biểu cho tr ường đại học Lisbon.
Zervoudakis và Stamatopoulus [14] đã sử dụng thư viện lập trình ràng buộc có hỗ trợ hướng
đối tượng ILOG SERVER C++ để sắp xếp thời khóa biểu cho khoa Công nghệ thông tin v à
Truyền thông của trường đại học Athens. Tác giả đ ã sử dụng phương pháp tìm kiếm theo
chiều sâu (depth-first search) và heuristics th ứ tự biến (variables ordering heuristic) đ ể sắp
xếp 68 môn học.
Ưu điểm chính của nhóm ph ương pháp lập trình ràng buộc là thời gian phát triển nhanh,

thích hợp vời bài tốn có nhiều ràng buộc. Nhược điểm chính là nó khơng giải quyết hữu
hiệu đồng thời cả ràng buộc cứng và ràng buộc mềm, tức là trong trường hợp các ràng buộc
được phân cấp có nhiều mức r àng buộc có độ ưu tiên khác nhau.

Dùng Phương Pháp Column Generation đ ể Sắp Xếp Thời Khóa Biểu Mơn Học

Trang 5


2.3 Tìm kiếm cục bộ
Trong nhóm này có 3 phương pháp thư ờng hay được sử dụng là: giải thuật di truyền
(Genetic Algorithm), mô ph ỏng luyện kim (Simulated Annealing) và tìm ki ếm Tabu (Tabu
Search). Đặc điểm của tìm kiếm heuristics là có thể tránh rơi vào tối ưu cục bộ, việc tìm
kiếm cũng được thực hiện có hệ thống, nh ưng không quét hết được không gian nghiệm hoặc
có cách để loại bỏ bớt khơng gian nghiệm n ên dẫn đến nghiệm tìm được thơng thường là
khơng tối ưu và cũng không thể chứng minh l à tối ưu ngay khi đó là nghiệm tối ưu.
Giải thuật di truyền là chiến lược tìm kiếm dựa vào sức mạnh của quần thể, mơ phỏng theo
q trình chọn lọc tự nhiên trong giới sinh vật. Giải thuật luôn luôn l ưu giữ một tập
hợp(quần thể) các lời giải khả thi, thực hiện các phép toán lai ghép các cá thể bố mẹ hoặc
đột biến để tạo ra các cá thể con. Sau đó thực h iện việc tái tạo lại quần thể bằng cách lựa
chọn các cá thể từ quần thể hiện có theo nguy ên tắc các cá thể đời sau phải tốt (thích nghi)
hơn các cá thể đời trước. Cứ tiếp tục như vậy cho đến khi đạt được lời giải tốt. Erben và
Keppler [9] đã dùng giải thuật di truyền cho b ài toán sắp xếp thời khóa biểu cho tr ường đại
học Konstanz. Trong giải thuật n ày, thời khóa biểu là một bộ 5 phần tử (c, t , l , r , p ) , trong đó
c là lớp học (class), t là thầy giáo (teacher), l là bài giảng (lesson), r là phòng học (room)
và p là tiết học (period). Tác giả đã thử nghiệm trên dữ liệu thực, chạy qua 2500 thế hệ,
mất hết 8.5 giờ.
Mô phỏng luyện kim là chiến lược tìm kiếm phỏng theo quá trình luyện kim trong thực tế.
Đầu tiên sẽ đốt nóng khối kim loại lên một nhiệt độ rất cao, sau đó l à q trình làm nguội
khối kim loại đến một nhiệt độ gọi là điểm đóng băng. Chuỗi các nhiệt độ v à thời gian luyện

khối kim loại dưới nhiệu độ đó được gọi là lịch biểu làm nguội. Việc mô phỏng quá tr ình
luyện kim vào các bài toán tối ưu tổ hợp đã được Kirkpatrick và các đồng tác giả [10] giới
thiệu vào năm 1983. Giải thuật bắt đầu bằng cách tạo ngẫu nhi ên một số lời giải. Sau đó
việc tìm kiếm các lời giải láng giềng đ ược điều khiển bởi lịch làm nguội. Elmohammed [11]
sử dụng giải thuật luyện kim với nhiều lịch biểu làm nguội khác nhau cho bài tốn sắp xếp
thời khóa biểu mơn học của tr ường đại học Syracuse. Tác giả đ ã tiến hành thử nghiệm cho
nhiều lịch biểu làm nguội và đạt được kết quả tốt hơn so với các phương pháp khác.
Tìm kiếm tabu là một giải thuật tìm kiếm cục bộ nhưng có khả năng thốt khỏi các điểm tối
ưu cục bộ. Cơ chế tìm kiếm dựa trên giải thuật leo đồi (hill-climbing algorithm) nhưng nó
có sử dụng một danh sách (gọi là danh sách tabu) chứa các bước chuyển mà nó đã thực hiện
nhằm tránh rơi vào điểm cục bộ. Chiều dài của danh sách tabu sẽ điều khiển chiến lược tìm
kiếm. Nếu cần đa dạng hóa q tr ình tìm kiếm (diversification), tức là muốn nhảy đến một
khơng gian khác có kỳ vọng hơn thì duy trì danh sách tabu ng ắn (short-term tabu list). Nếu
xét thấy không gian tìm kiếm hiện tại có khả năng đ em lại lời giải tốt thì nên tăng cường tìm
kiếm (intensification), và duy trì danh sách tabu đủ dài (long-term tabu list).
Costa [12] đã sử dụng chiến lược tìm kiếm tabu với hai danh sách tabu cho b ài toán sắp xếp
thời khóa biểu mơn học. Danh sách đầu ti ên là các bài giảng đã được sắp xếp vào các tiết
học cụ thể trong tuần. Các b ài giảng này không được sắp xếp lại nếu nó đã nằm trong danh
sách. Danh sách thứ hai là những cặp (l , t ) chứa thông tin về bài giảng và tiết dạy trước đó
đã sắp xếp cho nó. Tiết dạy l sẽ khơng được sắp xếp vào giờ học t nếu nó đã nằm trong
danh sách. Tác giả sử dụng chiến lược đa dạng hóa khơng gian t ìm kiếm để điều khiển quá
Dùng Phương Pháp Column Generation đ ể Sắp Xếp Thời Khóa Biểu Mơn Học

Trang 6


trình tìm kiếm. Kết quả thử nghiệm cho thấy giải thuật có khả năng t ìm ra được lời giải khả
thi. Tuy nhiên, phải điều chỉnh nhiều thông số nh ư chiều dài và trọng số của danh sách tabu.
Alvarez-Valdes [13] áp dụng tìm kiếm tabu với hai pha để s ắp xếp lịch học cho các sinh
viên thuộc khoa Toán của trường đại học Valencia. Pha đầu ti ên là tạo ra các thời khóa biểu

tốt cho mỗi sinh viên. Pha tiếp theo là dùng giải thuật tìm kiếm tabu với chiến lược tăng
cường để cải thiện lịch học cho mỗi sinh vi ên.
Nói chung, các heuristics này là m ột chiến lược tiếp cận rất khả thi cho b ài tốn sắp xếp thời
khóa biểu, đó là chỉ cần tìm ra các nghiệm xấp xỉ, chấp nhận đ ược trong một thời gian cho
phép. Tuy nhiên nhóm phương pháp này ph ụ thuộc rất nhiều vào đặc trưng của bài tốn, để
tạo ra một heuristic tốt th ì phải khảo sát kỹ lưỡng bài toán, phải tiến hành đo đạc thực
nghiệm nhiều mới điều chỉnh tốt các thông số. Giải thuật di truyền cần phải điều chỉnh h àm
đánh giá độ thích nghi, các phép tốn lai ghép lại “xa l ạ” với các ràng buộc. Giải thuật mơ
phỏng luyện kim thì phải có một lịch biểu làm nguội hợp lý và khó xác định nhiệt độ khởi
đầu. Do đó việc áp dụng các ph ương pháp này vào thực tế thì lại khó khăn do người sử dụng
phải có hiểu biết về các ph ương pháp này.

2.4 Quy hoạch ngun
Đối với các bài tốn có kích thước nhỏ, có thể áp dụng quy hoạch nguy ên để giải. Phương
pháp này yêu cầu các ràng buộc phải được mơ tả dưới các phương trình hoặc bất phương
trình tốn học. Sử dụng chiến lược nhánh và cận để tìm lời giải tối ưu, mỗi node trên cây
tìm kiếm là một bài tốn quy hoạch tuyến tính dựa trên bài tốn quy hoạch ngun ban đầu.
Đã có nhiều tác giả áp dụng phương pháp này như Breslaw [15], Shin và Sullivan [16],
Triphathy [17].
Với các bài tốn có kích thước lớn, dữ liệu cho bài tốn mơ tả theo phương pháp này rất lớn,
do đó khơng thể giải trực tiếp ngay từ đầu đ ược, mà phải được tạo ra từ từ trong quá tr ình
giải. Barnhard [1] và Maculan [2] đã đưa ra phương pháp Column Generation đ ể giải cho
bài tốn quy hoạch ngun có kích thước lớn. Ý tưởng của phương pháp này khá đơn gi ản.
Tại mỗi node trên cây tìm kiếm nhánh và cận (branch-and-bound tree), trước khi thực hiện
nới lỏng bài toán quy hoạch nguyên (LP relaxation) thành bài tốn quy ho ạch tuyến tính,
thực hiện gọi thủ tục sinh cột để tạo th êm các cột cho ma trận ràng buộc của bài toán quy
hoạch tuyến tính, các cột đ ược tạo ra phải thỏa mãn thơng số chi phí (reduced cost) khơng
âm để nhằm mục đích sinh ra các cột có lợi nhất cho b ài tốn quy hoạch tuyến tính. Chi tiết
của giải thuật sẽ được bàn kỹ trong chương sau. Andrea [3] đã đưa ra phương hướng sử
dụng phương pháp này cho bài tốn s ắp xếp thời khóa biểu mơn học trong đó các r àng buộc

mềm sẽ được thỏa mãn trong thủ tục sinh cột. Về thực nghiệm, Papousis [4] đã áp dụng
phương pháp này để sắp xếp thời khóa biểu cho một t rường trung học ở Hy Lạp.

2.5 Kết luận
Qua nghiên cứu các cơng trình đã cơng bố, tôi rút ra một số kết luận sau:
 Các cơng trình tập trung nghiên cứu phương pháp tìm kiếm cục bộ và lập trình ràng
buộc cho bài tốn sắp xếp thời khóa biểu. Có một số cơng tr ình sử dụng phương pháp
Dùng Phương Pháp Column Generation đ ể Sắp Xếp Thời Khóa Biểu Mơn Học

Trang 7


quy hoạch ngun. Số lượng cơng trình sử dụng phương pháp Column Generation r ất
ít.
 Các cơng trình sử dụng phương pháp Column Generation thư ờng áp dụng vào bài
toán có mơ hình rất đơn giản. Trong khi đó, mơ hình sắp xếp thời khóa biểu của
trường Đại học Bách Khoa rất phức tạp với rất nhiều r àng buộc cứng và ràng buộc
mềm đặc thù. Các đề tài này cũng tìm ra nghiệm tối ưu nhưng chỉ được thử nghiệm
trên dữ liệu có kích thước nhỏ so với số lượng dữ liệu rất lớn của tr ường Đại học
Bách Khoa.
Từ những kết luận trên và qua thảo luận với thầy hướng dẫn, tôi đã xác định một số vấn đề
cần tập trung nghiên cứu như sau:
 Nghiên cứu cơ sở lý thuyết về quy hoạch tuyến tính, quy hoạch nguy ên và phương
pháp Column Generation đ ể có cơ sở áp dụng cho đề tài.
 Xây dựng mơ hình sắp xếp thời khóa biểu cho tr ường Đại học Bách Khoa thích hợp
với phương pháp Column Generation.
 Nghiên cứu giải thuật branch-and-price để hiện thực phương pháp Column
Generation.

Dùng Phương Pháp Column Generation đ ể Sắp Xếp Thời Khóa Biểu Môn Học


Trang 8


Chương 3

CƠ SỞ LÝ THUYẾT

Chương này trình bày cơ sở lý thuyết và một số giải thuật quan trọng để giải b ài toán quy
hoạch nguyên.
Phần đầu tiên giới thiệu về quy hoạch tuyến tính. Phần n ày giới thiệu một số khái niệm về
quy hoạch tuyến tính. Trong phần n ày cũng giới thiệu về giải thuật đơn hình, một giải thuật
quan trọng được sử dụng để giải hầu hết các b ài tốn quy hoạch tuyến tính.
Phần tiếp theo giới thiệu về quy hoạch hoạch nguy ên, là cách tiếp cận dưới góc độ tốn học
cho các bài toán tối ưu tổ hợp. Phần này dựa vào các khái niệm đã có trong phần quy hoạch
tuyến tính.
Phần cuối cùng trình bày phương pháp Column Generation. Đây là phương pháp đư ợc sử
dụng để giải các bài toán quy hoạch nguyên cỡ lớn. Đây cũng là phương pháp mà đề tài áp
dụng để giải bài toán sắp xếp thời khóa biểu.

3.1 Quy hoạch tuyến tính
Những ý niệm đầu tiên về quy hoạch tuyến tính lần đầu ti ên được nhà tốn học Liên Xơ
Leonid Vitaliyevich Kanto rovich giới thiệu trong cuốn sách “Phương pháp toán học về tổ
chức và kế hoạch hóa sản xuất” được xuất bản vào năm 1939, trong đó tập trung vào xây
dựng các cơng thức về các vấn đề kinh tế c ơ bản, những biểu thức toán học của chúng v à
những phác thảo cơ bản về phương pháp giải. Sau đó, vào năm 1947, George Dantzig và các
cộng sự phát hiện lại mô h ình quy hoạch tuyến tính khi nghiên cứu bài tốn lập kế hoạch sản
xuất cho khơng qn Mỹ. C ùng năm đó, Dantzig đã cơng bố thuật tốn đơn hình nổi tiếng
để giải bài tốn quy hoạch tuyến tính.
Quy hoạch tuyến tính là một bộ phận quan trọng của quy hoạch tốn học, nó l à mơ hình tốn

cho nhiều bài toán của nhiều bài toán thực tế khác nhau như kinh tế, viễn thông, xây
dựng…Hiệu quả của quy hoạch tuyến tính đ ã được chứng minh trong thực tiễn, l à một trong
những động lực làm thay đổi bộ mặt kinh tế của thế giới v ào nửa cuối thế kỷ 20.
Trong phần này sẽ trình bày một số khái niệm cơ bản về quy hoạch tuyến tính v à giải thuật
đơn hình để giải bài tốn quy hoạch tuyến tính.
3.1.1 Định nghĩa quy hoạch tuyến tính
Bài tốn quy hoạch tuyến tính tổng quát được phát biểu như sau
min{ f ( x )  c, x | x  D},

trong đó c  (c1 , c 2 ,..., c n ) T  R n và D  R n là tập lồi đa diện được xác định bởi hệ bất
phương trình tuyến tính
Dùng Phương Pháp Column Generation đ ể Sắp Xếp Thời Khóa Biểu Mơn Học

Trang 9


a11 x1  a12 x 2  ...  a1n x n  b1
a 21 x1  a 22 x 2  ...  a 2 n x n  b2
...
a m1 x1  a m 2 x 2  ...  a mn x n  bm

Trong bài toán trên, ta gọi
f ( x )  c, x  c1 x1  c 2 x 2  ...  c n x n là hàm mục tiêu;

c j , j  1,..., n là các hệ số của hàm mục tiêu;
x j , j  1,..., n là các biến;

 a i , x  (, )bi , i  1,..., m là các ràng buộc;

Tập lồi đa diện D được gọi là tập nghiệm chấp nhận được. Mỗi điểm x  D được gọi là một

nghiệm chấp nhận được hày là một phương án khả thi (gọi tắt là phương án). Điểm x   D
mà
f ( x  )  c, x   f ( x )  c, x , x  D

được gọi là nghiệm tối ưu hay lời giải tối ưu của bài tốn.
Khi nghiên cứu quy hoạch tuyến tính, ng ười ta thường dùng hai dạng đặc thù sau:
 Dạng chuẩn tắc
min f ( x)  c1 x1  c 2 x 2  ...  c n x n

a

subject

j 1,..., n

ij

x j  bi , i  1,..., m
x j  0, j  1,..., n

hay có thể được viết dưới dạng ma trận là
min f ( x)  c, x 
subject Ax  b
x0

 Dạng chính tắc
min f ( x)  c1 x1  c 2 x 2  ...  c n x n
subject

a


j 1,..., n

ij

x j  bi , i  1,..., m
x j  0, j  1,..., n

tương tự, chuyển sang dạng ma trận l à
Dùng Phương Pháp Column Generation đ ể Sắp Xếp Thời Khóa Biểu Môn Học

Trang 10


min f ( x )  c, x 
subject Ax  b
x0

3.1.2 Sự tồn tại nghiệm và tính chất tập nghiệm của quy hoạch tuyến tính
Dưới đây trình bày một số định lý (không chứng minh) về tập nghiệm của quy hoạch tuyến
tính.
Xét bài tốn quy hoạch tuyến tính tổng quát
min{ f ( x )  c, x | x  D},

( LP )

trong đó c  R n và D  R n là tập lồi đa diện khác rỗng
 Sự tồn tại nghiệm
Hai định lý dưới đây cho biết điều kiện có nghiệm của một quy hoạch tuyến tính
Định lý 3.1: Nếu tập nghiệm chấp nhận đ ược D khác rỗng và bị chặn thì bài tốn

quy hoạch tuyến tính (LP ) ln có nghiệm tối ưu
Định lý 3.2: Nếu tập D khác rỗng và hàm mục tiêu f ( x)  c, x  bị chặn dưới trên
D thì quy hoạch tuyến tính (LP ) ln có nghiệm tối ưu.
 Tính chất tập nghiệm
Định lý 3.3: Nếu bài tốn quy hoạch tuyến tính có nghiệm tối ưu thì tập nghiệm tối
ưu của nó phải là một mặt (face) của tập lồi đa diện D .
Hệ quả 3.1: Nếu một quy hoạch tuyến tính có nghiệm tối ưu và tập lồi đa diện có
đỉnh thì nghiệm tối ưu phải đạt tại ít nhất một đỉnh, tức đạt tại một ph ương án cực
biên.
Định lý 3.4: Nếu một quy hoạch tuyến tính có nghiệm tối ưu thì nghiệm tối ưu đó
cũng là nghiệm tối ưu tồn cục của quy hoạch tuyến tính.
3.1.3 Phương pháp đơn h ình để giải bài tốn quy hoạch tuyến tính chính tắc
Như đã biết, phương pháp đơn hình giải bài tốn quy hoạch tuyến tính do George Dantzig
đề xuất vào năm 1947. Mặc dù, về mặt lý thuyết, thuật tốn đ ơn hình có độ phức tạp hàm
mũ và cho đến nay đã có nhiều thuật tốn có độ phức tạp đa thức để giải quy hoạch tuyến
tính như thuật tốn elipsoid của Khachiyan, thuật toán điểm trong của Karmarkar, nhưng
cho đến nay, thuật tốn đơn hình vẫn là phương pháp phổ biến nhất để giải các b ài tốn quy
hoạch tuyến tính trong thực tế.

Dùng Phương Pháp Column Generation đ ể Sắp Xếp Thời Khóa Biểu Mơn Học

Trang 11


Vì mọi quy hoạch tuyến tính đều có thể chuyển về dạng chính tắc, n ên khơng giảm tính tổng
qt, trong phần này sẽ trình bày thuật tốn đơn hình để giải bài tốn quy hoạch tuyến tính
dạng chính tắc.
Xét bài tốn quy hoạch tuyến tính chính tắc
min{ c, x | x  D},


( LP ct )

trong đó c  R n \ {0} và D  R n là tập lồi đa diện được xác định bởi
Ax  b, x  0,

(3.1)

với A là ma trận cấp m  n, m  n và b  (b1 , b2 ,..., bm ) T  0
Định lý sau đây giúp ta xét b ài tốn quy hoạch tuyến tính ( LP ct ) với giả thiết rằng: Ma trận
A có rank ( A)  m , tức m vector hàng của A độc lập tuyến tính.
Định lý 3.5: Cho tập lồi đa diện khác rỗng D  {x | Ax  b, x  0} , trong đó A là ma trận cấp
m  n . Giả sử rank ( A)  k  m và các hàng a i1 , a i 2 ,..., a ik độc lập tuyến tính. Khi đó D  D  ,
trong đó D  là tập lồi đa diện được xác định bởi
D   {x | a i1 , x  b i1 ,...,  a ik , x  b ik , x  0}.

Phương pháp đơn hình giải bài tốn quy hoạch tuyến tính dựa trên hai tính chất sau:
i. Nếu bài tốn quy hoạch tuyến tính chính tắc ( LP ct ) có nghiệm tối ưu thì nghiệm tối
ưu đó phải nằm trên một đỉnh (phương án cực biên) của tập lồi đa diện chấp nhận
được D (Hệ quả 3.1).
ii. Nghiệm tối ưu địa phương của bài toán ( LP ct ) cũng là nghiệm tối ưu toàn cục (Định
lý 3.4).
Dựa vào hai tính chất trên ta đi vào xem xét một số khái niệm và định lý để xây dựng
phương pháp đơn hình.
a. Phương án cực biên
Do quy hoạch tuyến tính có nghiệm tối ưu tại ít nhất một phương án cực biên nên ta quan
tâm đến các tính chất của nó.
Xét tập chấp nhận được D (được xác định bởi định lý 3.5) của quy hoạch tuyến tính chính
tắc ( LP ct ) . Ký hiệu A j là cột thứ j của ma trận A, j  1,..., n . Hệ ràng buộc (3.1) của tập
chấp nhận D được viết lại dưới dạng vector như sau:
A1 x1  A1 x1  ...  A1 x1  b, x j  0, j  1,..., n


(3.2)

Xét một phương án chấp nhận được x 0  ( x10 , x 20 ,..., x n0 ) T  D . Ký hiệu:

Dùng Phương Pháp Column Generation đ ể Sắp Xếp Thời Khóa Biểu Mơn Học

Trang 12


J ( x 0 )  { j  {1,..., n} | x 0j  0}.

là tập các chỉ số của các thành phần dương của phương án chấp nhận được x 0 . Tập J ( x 0 )
còn gọi là tập các chỉ số cơ sở.
Sau đây là điều kiện cần và đủ để x 0 là phương án cực biên.
Định lý 3.6: Phương án chấp nhận được x 0  D là phương án cực biên khi và chỉ khi các
vector { A j | j  J ( x 0 )} độc lập tuyến tính.
Dưới đây là các hệ quả trực tiếp từ định lý 3.6
Hệ quả 3.2: Số thành phần dương trong mỗi phương án cực biên của bài tốn quy hoạch
tuyến tính khơng vượt quá m
Hệ quả 3.3 : Số phương án cực biên của bài tốn quy hoạch tuyến tính dạng chính tắc là
hữu hạn.
b. Điều kiện tối ưu
Ta xét bài toán quy hoạch tuyến tính chính tắc
min{ c, x | x  D},

( LP ct )

trong đó c  R n \ {0} , và tập chấp nhận được
D  {x  R n | Ax  b, x  0},


trong đó b  (b1 , b2 ,..., bm ) T  0 , A là ma trận cấp m  n với các cột A1 , A2 ,..., An , rank ( A)  m
và m  n .
Định nghĩa: Một bộ m vector cột độc lập tuyến tính B  { A j1 , A j 2 ,..., A jm ) được gọi là một cơ
sở của ma trận A .
Cho x 0  ( x10 ,..., x n0 ) T là một phương án cực biên của bài toán ( LP ct ) . Theo định lý 3.6, các
vector { A j | j  J ( x 0 )} độc lập tuyến tính. Vì rank ( A)  m nên
 Nếu x 0 là phương án cực biên không suy biến, tức | J ( x 0 ) | m thì { A j | j  J ( x 0 )} là
cơ sở duy nhất của A tương ứng với x 0 .
 Nếu x 0 là phương án cực biên suy biến, tức | J ( x 0 ) | m , thì ta bổ sung thêm các
vector cột của A thuộc tập { A j | j  J ( x 0 )} vào bộ vector { A j | j  J ( x 0 )} để nhận
được bộ m vector độc lập tuyến tính { A j | j  J } với J  J ( x 0 ) và | J | m . Khi đó,
_

B  { A j | j  J } . Dễ thấy, ứng với một ph ương án cực biên suy biến x 0 có thể có

nhiều cơ sở của A .
Dùng Phương Pháp Column Generation đ ể Sắp Xếp Thời Khóa Biểu Mơn Học

Trang 13


Xét bài tốn quy hoạch tuyến tính chính tắc ( LP ct ) với giả thiết thêm rằng: bài toán ( LP ct )
là không suy biến và biết trước một phương án cực biên x 0 .
Giả sử ta đã biết phương án cực biên không suy biến x 0  ( x10 , x 20 ,..., x n0 ) T có | J ( x 0 ) | m . Hệ
vector độc lập tuyến tính { A j | j  J ( x 0 )} là cơ sở duy nhất của ma trận A tương ứng với x 0 .
Ta gọi
J ( x 0 )  { j  {1,..., n} | x 0j  0} là tập chỉ số cơ sở
{1,..., n} \ J ( x 0 ) là tập chỉ số phi cơ sở


{x j | j  J ( x 0 )} là các biến cơ sở
{x j | j  J ( x 0 )} là các biến phi cơ sở

{ A j | j  J ( x 0 )} là các vector cơ sở
{ A j | j  J ( x 0 )} là các vector phi cơ sở

Do { A j | j  J ( x 0 )} là cơ sở của ma trận A nên mỗi vector cột Ak , k  {1,2,..., n} được biểu
diễn dưới dạng
Ak 

z

jk

(3.3)

Aj

jJ ( x 0 )

tức

a

ij

z jk  a ik , i  1,2,..., m

và bộ số thực z jk , j  J ( x 0 ) được xác định là duy nhất. Vì x 0j  0 j  J ( x 0 ) nên


x

0
j

Aj  b

(3.4)

jJ ( x 0 )

Giá trị của hàm mục tiêu tại x 0 là
n

f ( x 0 )  c, x 0   x 0j c j 
j 1

Đại lượng
k 

z

jk

x c
0
j

j


(3.5)

jJ ( x )
0

c k  c k , k  {1,2,..., n}

(3.6)

jJ ( x 0 )

được gọi là ước lượng của biến x k
Dễ thấy rằng  k  0, k  J ( x 0 )
Ký hiệu:
B là ma trận có cột là các vector { A j | j  J ( x 0 )}

Dùng Phương Pháp Column Generation đ ể Sắp Xếp Thời Khóa Biểu Mơn Học

Trang 14


Z Bk là vector cột có các thành phần là z jk , j  J ( x 0 )
C B là các vector thành phần c j , j  J ( x 0 )

X B là vector cột có thành phần là x j , j  J ( x 0 )

Khi đó các cơng thức (3.3)-(3.6) được viết lại dưới dạng như sau
Ak  BZ Bk




Z Bk  B 1 Ak

BX B  b



X B  B 1b

f (x0 )  CB X B
 k  C B Z Bk  c k  C B B 1 Ak  c k

Sau đây là điều kiện đủ dể phương án cực biên x 0 là phương án tối ưu của bài toán ( LP ct ) .
Định lý 3.7: Nếu phương án cực biên x 0 thỏa mãn  k  0 k  J ( x 0 ) thì x 0 là một phương
án tối ưu của bài tốn quy hoạch tuyến tính chính tắc ( LP ct ) .
Hệ quả 3.4: Giả sử x 0 là phương án tối ưu của bài toán quy hoạch tuyến tính ( LP ct ) . Nếu
 k  0 với mọi k  J ( x 0 ) thì x 0 là phương án tối ưu duy nhất. Ngược lại, nếu tồn tại k
sao cho  k  0 thì x 0 khơng phải là phương án tối ưu duy nhất.
Định lý sau đây cho biết dấu hiệu b ài tốn khơng có lời giải hoặc từ phương án cực biên x 0
có thể chuyển đến phương án cực biên mới tốt hơn.
Định lý 3.8: Cho x 0 là một phương án cực biên của bài toán quy hoạch tuyến tính chính tắc
( LP ct ) . Khi đó,
i. Nếu tồn tại k  J ( x 0 ) sao cho  k  0 và z jk  0 j  J ( x 0 ) thì hàm mục tiêu giảm vô
hạn trên tập chấp nhận được và bài tốn khơng có lời giải
ii. Nếu tồn tại k  J ( x 0 ) sao cho  k  0 và tồn tại j  J ( x 0 ) sao cho z jk  0 thì ta có
thể chuyển đến phương .án cực biên x1 tốt hơn, nghĩa là c, x1  c, x 0 .
Chứng minh: Xét chỉ số k  J ( x 0 ) sao cho  k  0 . Ta có
n

x

j 1

và

z

jk

0
j

A j  Ak

jJ ( x 0 )

Aj 

x

0
j

Aj  b

(3.7)

jJ ( x )
0




 z

jk

A  Ak ,   0

(3.8)

jJ ( x 0 )

Trừ (3.7) cho (3.8) và chuyển vế Ak ta được

 (x

0
j

 z jk ) A j  Ak  b

(3.9)

jJ ( x )
0

Dùng Phương Pháp Column Generation đ ể Sắp Xếp Thời Khóa Biểu Mơn Học

Trang 15