BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
PHẠM THỊ HOÀI
MỘT SỐ LỚP BÀI TOÁN TỐI ƯU KHÔNG LỒI:
THUẬT TOÁN VÀ ỨNG DỤNG
LUẬN ÁN TIẾN SĨ TOÁN HỌC
Hà Nội - 2020
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
PHẠM THỊ HOÀI
MỘT SỐ LỚP BÀI TOÁN TỐI ƯU KHÔNG LỒI:
THUẬT TOÁN VÀ ỨNG DỤNG
Ngành: Toán học
Mã số: 9460101
LUẬN ÁN TIẾN SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC
1. TS. NGUYỄN CẢNH NAM
2. GS. TSKH. LÊ THỊ HOÀI AN
Hà Nội - 2020
LỜI CAM ĐOAN
Bản luận án này được hoàn thành tại Viện Toán ứng dụng và Tin học, Trường Đại
học Bách khoa Hà Nội, dưới sự hướng dẫn khoa học của TS. Nguyễn Cảnh Nam và
GS. TSKH. Lê Thị Hoài An.
Tôi xin cam đoan các kết quả được trình bày trong luận án là trung thực và chưa
từng được tác giả khác công bố. Các đồng tác giả đã đồng ý với việc đưa các kết quả
công bố chung vào luận án.
Hà Nội, ngày tháng năm 2020
Thay mặt tập thể hướng dẫn
TS. Nguyễn Cảnh Nam
Nghiên cứu sinh
Phạm Thị Hoài
i
LỜI CẢM ƠN
Luận án được hoàn thành dưới sự hướng dẫn tận tình và nghiêm khắc của TS. Nguyễn
Cảnh Nam và GS. TSKH. Lê Thị Hoài An. Tác giả xin được bày tỏ lòng kính trọng
và biết ơn sâu sắc tới Thầy, Cô. Thầy Cô đã luôn ân cần hướng dẫn, chỉ bảo cho tác
giả kiến thức về chuyên môn, từng bước định hướng nghiên cứu và truyền cho tác giả
niềm đam mê nghiên cứu khoa học, ý thức tự học, tự tìm tòi bằng tấm gương của mình
trong công việc cũng như trong cuộc sống. Những lời động viên, khích lệ của Thầy
Cô là nguồn động lực to lớn để tác giả có thể vượt qua những khó khăn và trở ngại
trên con đường học tập và nghiên cứu, tự tin bước tiếp trên con đường mình đã chọn.
Trong quá tr ình học tập nói chung và thực hiện luận án này nói riêng, tác giả cũng
nhận được sự quan tâm, giúp đỡ, chỉ dẫn tận tình cùng những lời khuyên quý báu của
GS. Hoàng Tụy, GS. TSKH. Lê Dũng Mưu, PGS. TS. Nguyễn Thị Bạch Kim, GS.
TSKH. Nguyễn Đông Yên, TS. Tạ Anh Sơn, TS. Trần Ngọc Thăng, TS. Trần Đức
Quỳnh, TS. Lê Quang Thủy, TS. Nguyễn Thị Bích Thủy, TS. Nguyễn Quang Thuận.
Tác giả xin được bày tỏ lòng biết ơn sâu sắc tới các Thầy Cô.
Tác giả xin trân trọng cảm ơn Ban Giám hiệu, Phòng Tổ chức Cán bộ, Phòng Đào
tạo - Trường Đại học Bách khoa Hà Nội, đã tạo điều kiện thuận lợi cho tác giả trong
suốt quá trình làm việc, học tập, nghiên cứu và hoàn thành luận án.
Tác giả xin được gửi lời cảm ơn chân thành tới Ban lãnh đạo cùng toàn thể cán bộ
Viện Toán ứng dụng và Tin học, Trường Đại học Bách khoa Hà Nội, đã giúp đỡ, tạo
điều kiện để tác giả vừa có thể hoàn thành công tác và vừa có thời gian học tập, hoàn
thành chương trình nghiên cứu sinh.
Trong quá trình thực hiện luận án tác giả cũng nhận được sự hỗ trợ của Quỹ Phát
tr iển Khoa học và Công nghệ Quốc gia (NAFOSTED) về kinh phí tham gia báo cáo
tại hội thảo khoa học quốc tế và sự giúp đỡ tài trợ từ dự án của GS. TSKH. Lê Thị
Hoài An trong thời gian học tập tại phòng nghiên cứu về khoa học máy tính và ứng
dụng, Đại học Lorraine, Cộng Hòa Pháp. Ngoài ra tác giả cũng nhận được kinh phí
tài trợ mua vật tư, dụng cụ, tài liệu từ chương trình học bổng 911 trong nước. Tác giả
trân trọng cảm ơn.
Tác giả xin chân thành cảm ơn PGS. TS. Đỗ Đức Thuận, TS. Nguyễn Phương
Thùy, TS. Nguyễn Hải Sơn, TS. Trịnh Ngọc Hải cùng các Thầy Cô và anh chị em
đồng nghiệp trong Xêmina Lý thuyết tối ưu và ứng dụng và Xêmina Bài toán cân
bằng, bài toán điểm bất động và các vấn đề liên quan, Viện Toán ứng dụng và Tin
học - Đại học Bách khoa Hà Nội, đã dành cho tác giả những cơ hội học tập trao đổi
chuyên môn cùng những ý kiến đóng góp quý báu giúp cho tác giả hiểu sâu sắc hơn
ii
vấn đề nghiên cứu của mình.
Cuối cùng tác giả xin dành lời cảm ơn đặc biệt gửi tới những người thân yêu trong
gia đình cùng bạn bè của tác giả - những người đã, đang và sẽ là hậu phương vững
chắc, cho tác giả nguồn cổ vũ và động viên tinh thần lớn lao để tác giả có thể hoàn
thành công việc, học tập, nghiên cứu nói chung và việc viết luận án này nói riêng.
iii