Luận văn Thạc sĩ Toán học: Bài toán định vị với hàm mục tiêu lồi

Bài luận văn nhằm giới thiệu chi tiết về bài toán định vị, trong đó đi sâu vào các bài toán có hàm mục tiêu lồi. Cụ thể là sẽ trình bày một thuật toán được coi như cải biên của thuật toán dưới vi phân để giải bài toán định vị trong trường hợp số điểm cho trước có thể rất lớn.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Toán học: Bài toán định vị với hàm mục tiêu lồi ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– PHẠM XUÂN HÀ BÀI TOÁN ĐỊNH VỊVỚI HÀM MỤC TIÊU LỒI Chuyên ngành: Toán ứng dụng Mã số: 62 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC Giáo viên hướng dẫn GS. TSKH. LÊ DŨNG MƯU Thái Nguyên - 2017 iMục lụcBảng ký hiệu 1Lời nói đầu 21 Kiến thức bổ trợ 2 1.1 Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Tập a-phin . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Định lí tách các tập lồi . . . . . . . . . . . . . . . . . . . . . 4 1.4 Bao lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.5 Hàm lồi và cực trị của hàm lồi . . . . . . . . . . . . . . . . . 11 1.5.1 Cực tiểu hàm lồi (cực đại hàm lõm) . . . . . . . . . . 14 1.5.2 Cực tiểu của hàm lồi mạnh . . . . . . . . . . . . . . . 152 Bài toán định vị với hàm mục tiêu lồi 18 2.1 Về bài toán quy hoạch lồi . . . . . . . . . . . . . . . . . . . . 18 2.1.1 Bài toán và định nghĩa . . . . . . . . . . . . . . . . . 18 2.1.2 Sự tồn tại nghiệm tối ưu . . . . . . . . . . . . . . . . 19 2.1.3 Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . 20 2.2 Bài toán định vị với hàm mục tiêu lồi . . . . . . . . . . . . . . 24 2.3 Thuật toán dưới đạo hàm giải bài toán định vị với hàm mục tiêu mimax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.3.1 Thuật toán và sự hội tụ của nó . . . . . . . . . . . . . 27 2.3.2 Các khía cạnh và kết quả tính toán . . . . . . . . . . . 32Kết luận 35 iiTài liệu tham khảo 36 1Bảng ký hiệuR tập số thựcRn không gian Euclid n-chiều trên trường số thựcxi tọa độ thứ i của xhx, yi tích vô hướng của hai vectơ x và ykxk chuẩn của vectơ x[x, y] đoạn thẳng đóng nối x và y(x, y) đoạn thẳng mở nối x và yA bao đóng của AcoA bao lồi của AintA tập hợp các điểm trong của AriA tập hợp các điểm trong tương đối của AV (A) tập hợp các điểm cực biên(đỉnh) của Af hàm bao đóng của hàm fconvP bao lồi của Pdom f tập hữu dụng của fepi f trên đồ thị của f∂ f (x) dưới vi phân của f tại x∇ f (x) đạo hàm của f tại x∇ f (x, d) đạo hàm theo phương d của f tại x 2Lời nói đầu Một vấn đề quan trọng trong hình học là xác định vị trí của điểm, với nhữngđiều kiện nhất định, sao cho đạt được mục tiêu tốt nhất theo một tiêu chuẩn nàođó. Bài toán định vị đơn giản nhất mà ta đã gặp trong chương trình toán phổthông là bài toán tìm một điểm trong một tam giác đã cho, sao cho tổng khoảngcách từ điểm đó đến ba đỉnh của tam giác là nhỏ nhất. Bài toán định vị có rất nhiều ứng dụng trong thực tế. Ví dụ, khi chúng ta cầnxây dựng một bệnh viện, một nhà máy, một trạm xăng, một bến xe, hay một hệthống giao thông nối các điểm quan trọng với nhau thì câu hỏi đặt ra là vị tríxây dựng như thế nào là tối ưu, thuận tiện nhất sao cho đảm bảo việc thỏa mãnnhu cầu của người sử dụng là tốt nhất để đem lại sự thu hút và lợi ích nhiềunhất. Ví dụ như khi xây dựng một trạm đổ xăng hay bến xe cần tính toán saocho khoảng cách tới các khu dân cư đông đúc là ngắn nhất, thuận tiện đườngnhất, . . . , cũng như vậy khi xây dựng một hệ thống giao thông thì xây dựng thếnào để hệ thống giao thông đó có độ dài ngắn nhất, tiết kiệm chi phí xây dựng,thuận tiện cho việc sử dụng sau này. Một ví dụ quan trọng khác của bài toánđịnh vị, gần đây được nghiên cứu là là xây dựng các trạm phát trong bưu chínhviễn thông để bảo đảm tín hiệu tốt nhất. Bài toán định vị thường xuất hiện trong những lĩnh vực thực tế, như trongviệc xác định vị trí của một điểm thuộc một miền cho trước sao cho đạt đượcmục tiêu tốt nhất theo một tiêu chuẩn nào đó. Đây là đề tài đã được nhiều tácgiả trong và ngoài nước quan tâm nghiên cứu. Chính vì vậy tác giả chọn đề tài:Bài toán định vị với hàm mục tiêu lồi. Bài luận văn nhằm giới thiệu chi tiết về bài toán định vị, trong đó đi sâu vào 3các bài toán có hàm mục tiêu lồi. Cụ thể là sẽ trình bày một thuật toán được coinhư cải biên của thuật toán dưới vi phân để giải bài ...