ĐẠ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
i
Mục lục
Bảng ký hiệu 1
Lời nói đầu 2
1 Kiến thức bổ trợ 2
1.1 Tậplồi.............................. 2
1.2 Tậpa-phin............................ 3
1.3 Định lí tách các tập lồi . . . . . . . . . . . . . . . . . . . . . 4
1.4 Baolồ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 . . . . . . . . . . . . . . . 15
2 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 . . . . . . . . . . . 32
Kết luận 35
ii
Tài liệu tham khảo 36
1
Bảng ký hiệu
Rtập số thực
Rnkhông gian Euclid n-chiều trên trường số thực
xitọa độ thứ icủa x
hx,yitích vô hướng của hai vectơ xvà y
kxkchuẩn của vectơ x
[x,y]đoạn thẳng đóng nối xvà y
(x,y)đoạn thẳng mở nối xvà y
Abao đóng của A
coAbao lồi của A
intAtập hợp các điểm trong của A
riAtập hợp các điểm trong tương đối của A
V(A)tập hợp các điểm cực biên(đỉnh) của A
fhàm bao đóng của hàm f
convPbao lồi của P
dom ftập hữu dụng của f
epi ftrên đồ thị của f
∂f(x)dưới vi phân của ftại x
∇f(x)đạo hàm của ftại x
∇f(x,d)đạo hàm theo phương dcủa ftại x
2
Lờ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ảng
cá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ần
xâ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ãn
nhu 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ều
nhấ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 sao
cho khoảng cách tới các khu dân cư đông đúc là ngắn nhất, thuận tiện đường
nhấ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ính
viễ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ư trong
việc xác định vị trí của một điểm thuộc một miền cho trước sao cho đạt được
mục tiêu tốt nhất theo một tiêu chuẩn nào đó. Đây là đề tài đã được nhiều tác
giả 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