Luận văn Thạc sĩ Toán học: Một phương pháp qui hoạch lồi giải bài toán chấp nhận lồi

Luận văn nghiên cứu về bài toán chấp nhận lồi và giới thiệu một vài phương pháp giải bài toán này, đặc biệt đi sâu vào phương pháp chuyển bài toán chấp nhận lồi về qui hoạch lồi. Mời các bạn tham khảo!
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Toán học: Một phương pháp qui hoạch lồi giải bài toán chấp nhận lồi ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC VŨ THỊ NGỌC BÍCHMỘT PHƯƠNG PHÁP QUI HOẠCH LỒI GIẢI BÀI TOÁN CHẤP NHẬN LỒI LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2018 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC VŨ THỊ NGỌC BÍCHMỘT PHƯƠNG PHÁP QUI HOẠCH LỒI GIẢI BÀI TOÁN CHẤP NHẬN LỒI Chuyên ngành: Toán ứng dụng Mã số: 84 60 112 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TSKH. Lê Dũng Mưu Thái Nguyên - 2018 iMục lụcMở đầu 1Chương 1 Bài toán qui hoạch lồi 3 1.1 Tập lồi, hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.1 Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.2 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2 Bài toán qui hoạch lồi . . . . . . . . . . . . . . . . . . . . . . . . . 16Chương 2 Một phương pháp qui hoạch lồi giải bài toán chấp nhận lồi 24 2.1 Bài toán chấp nhận lồi và ví dụ . . . . . . . . . . . . . . . . . . . . 24 2.1.1 Bài toán chấp nhận lồi . . . . . . . . . . . . . . . . . . . . 24 2.1.2 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2 Một phương pháp qui hoạch lồi giải bài toán chấp nhận lồi . . . . . 25 2.2.1 Tóm tắt hai phương pháp cơ bản: chiếu lần lượt và chiếu song song . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2.2 Thuật toán đạo hàm giải bài toán qui hoạch lồi . . . . . . . . 29 2.2.3 Phương pháp chuyển về bài toán qui hoạch lồi . . . . . . . . 32Kết luận 41Tài liệu tham khảo 42 1Mở đầu Tối ưu hóa được khởi nguồn như một ngành của Toán học, có rất nhiều ứng dụngtrong quy hoạch tài nguyên, thiết kế chế tạo máy, điều khiển tự động, quản trị kinhdoanh... trong việc tạo nên các hệ hỗ trợ ra quyết định trong quản lý và phát triển cáchệ thống lớn. Chính vì vậy, các lĩnh vực của tối ưu hóa ngày càng trở nên đa dạng mang nhiềutên gọi khác nhau như Quy hoạch toán học, Điều khiển tối ưu, Vận trù học, Lý thuyếttrò chơi... Hiện nay môn học Tối ưu hóa được đưa vào giảng dạy trong nhiều chươngtrình đào tạo đại học cho các ngành khoa học cơ bản. Một trong những bài toán quantrọng của Tối ưu hóa là bài toán qui hoạch lồi. Nhiều bài toán quan trọng trong lĩnh vực toán học hoặc trong thực tế có thểchuyển về bài toán qui hoạch lồi (tìm cực tiểu của một hàm lồi trên một tập lồi). Đốivới lớp bài toán này có nhiều phương pháp giải hiệu quả, ví dụ như phương pháp đạohàm, phương pháp dưới đạo hàm, phương pháp điểm trong,. . . Bài toán chấp nhậnlồi là bài toán tìm một điểm chung của một số hữu hạn hoặc vô hạn các tập lồi. Bàitoán này rất quan trọng vì nhiều bài toán trong toán học cũng như trong các lĩnh vựcthực tế khác đều có thể chuyển về bài toán chấp nhận lồi. Ví dụ như bài toán giải hệphương trình, bài toán tìm nghiệm chung của các bài toán tối ưu, bất đẳng thức biếnphân,. . . Chính vì vậy chúng tôi chọn đề tài: Một phương pháp qui hoạch lồi giải bài toánchấp nhận lồi. Luận văn nghiên cứu về bài toán chấp nhận lồi và giới thiệu một vàiphương pháp giải bài toán này, đặc biệt đi sâu vào phương pháp chuyển bài toán chấpnhận lồi về qui hoạch lồi. Nội dung luận văn gồm hai chương: Chương 1. Bài toán qui hoạch lồi” giới thiệu các kiến thức cơ bản nhất về giải 2tích lồi và bài toán qui hoạch lồi. Chương 2. Một phương pháp qui hoạch lồi giải bài toán chấp nhận lồi giớithiệu phương pháp chiếu lần lượt và chiếu song song, thuật toán đạo hàm để giải bàitoán qui hoạch lồi. Cuối chương, đề cập đến một phương pháp giải bài toán chấpnhận lồi. Trong quá trình học tập và làm luận văn, từ bài giảng của các giáo sư, phó giáo sưcông tác tại Viện Toán học, Viện Công nghệ Thông tin - Viện Hàn lâm Khoa học vàCông nghệ Việt Nam, Đại học Thăng Long, các thầy cô trong trường Đại học Khoahọc - Đại học Thái Nguyên, tôi đã trau dồi thêm rất nhiều kiến thức phục vụ cho việcnghiên cứu và công tác của bản thân. Tôi xin gửi lời cảm ơn chân thành đến các thầycô. Tôi xin chân thành cảm ơn Ban giám hiệu, Phòng đào tạo, khoa Toán - Tin trườngĐại học Khoa học - Đại học Thái Nguyên đã quan tâm và giúp đỡ tôi trong suốt thờigian học tập tại trường. Cuối cùng tôi xin gửi lời cảm ơn tới gia đình, bạn bè đã luônđộng viên, giúp đỡ và tạo điều kiện tốt nhất cho tôi trong quá trình học tập, nghiêncứu và làm luận văn. Thái Nguyên, tháng 05 năm 2018 Học viên Vũ Thị Ngọc Bích 3Chương 1Bài toán qui hoạch lồi Chương này trình bày một số kiến thức của giải tích lồi như tập lồi, hàm lồi,bài toán qui hoạch lồi, đây là những kiến thức nền tảng, cần thiết phục vụ cho việcnghiên cứu và giải quyết đề tài. Nội dung của chương được tham khảo từ các tài liệu[1], [2] và [3].1.1 Tập lồi, hàm lồi1.1.1 Tập lồiĐịnh nghĩa 1.1. Cho hai điểm a, b trong không gian Rn . Đường thẳng đi qua haiđiểm a và b là tập tất cả các điểm x trong Rn có dạng x = λa + (1 − λ)b, λ ∈ R.Đoạn thẳng nối hai ...