Luận văn Bài toán định vị và một số ứng dụng

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC THĂNG LONG --------------------------------------- Phạm Thị Hồi BÀI TOÁN ĐỊNH VỊ VÀ MỘT SỐ ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC Hà Nội - Năm 2015 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC THĂNG LONG --------------------------------------- Phạm Thị Hồi BÀI TOÁN ĐỊNH VỊ VÀ MỘT SỐ ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC CHUYÊN NGÀNH : TOÁN ỨNG DỤNG MÃ SỐ: 60. 46. 01. 12 NGƢỜI HƢỚNG DẪN KHOA HỌC : GS.TSKH Lê Dũng Mƣu Hà Nội - Năm 2015 Thang Long University Libraty i LỜI CAM ĐOAN Tác giả luận văn xin cam đoan về tính hợp pháp và tính đúng đắn của luận văn. Dưới sự hướng dẫn của GS.TSKH Lê Dũng Mưu, Luận văn đã tổng hợp các kiến thức lý thuyết và kết quả nghiên cứu mới đây về bài toán định vị và không trùng lặp với các luận văn khác. Học viên Phạm Thị Hồi ii LỜI CẢM ƠN Trước tiên tôi xin được gửi lời cảm ơn đến tất cả quý Thầy Cô đã giảng dạy trong chương trình Cao học Toán ứng dụng khóa 1 – Trường Đại học Thăng Long, những người đã truyền đạt kiến thức hữu ích về ngành Toán ứng dụng làm cơ sở cho tôi hoàn thành luận văn này. Đặc biệt tôi xin chân thành cảm ơn Thầy giáo GS.TSKH. Lê Dũng Mưu. Thầy đã dành nhiều thời gian quý báu tận tình hướng dẫn tôi trong suốt quá trình thực hiện luận văn, đồng thời còn là người giúp tôi lĩnh hội được những kiến thức chuyên môn và rèn luyện cho tôi tác phong nghiên cứu khoa học. Qua đây, tôi cũng xin được bày tỏ lòng biết ơn sâu sắc tới gia đình, bạn bè thân thiết là những người luôn sát cánh bên tôi, tạo mọi điều kiện tốt nhất cho tôi, đã nhiệt tình giúp đỡ, chia sẻ, động viên tôi trong suốt quá trình học tập, cũng như khi tôi thực hiện và hoàn thành luận văn này. Mặc dù đã rất cố gắng song luận văn không tránh khỏi có những thiếu sót, rất mong nhận được ý kiến góp ý của các Thầy giáo, Cô giáo và các anh chị học viên để luận văn được hoàn thiện hơn. Hải Phòng, tháng 07 năm 2015 Học viên thực hiện Phạm Thị Hồi Thang Long University Libraty MỤC LỤC Bản cam đoan ................................................................................................. i Lời cảm ơn ............................................................................................................ ..ii LỜI NÓI ĐẦU ................................................................................................. 1 CHƢƠNG 1 KIẾN THỨC BỔ TRỢ ............................................................. 3 1.1.Tập lồi ......................................................................................................... 3 1.2. Tập a-phin .................................................................................................. 4 1.3. Tập lồi đa diện và định lý tách các tập lồi đa diện .................................... 5 1.4. Bao lồi ........................................................................................................ 7 1.5. Hàm lồi và cực trị của hàm lồi ................................................................... 9 1.6. Bài toán quy hoạch lồi .............................................................................. 14 1.7. Toán tử chiếu ............................................................................................ 16 CHƢƠNG 2 BÀI TOÁN ĐỊNH VỊ VÀ ỨNG DỤNG ................................ 21 2.1. Giới thiệu bài toán .................................................................................... 21 2.2. Phương pháp tối ưu giải một bài toán định vị .......................................... 26 KẾT LUẬN .................................................................................................... 41 TÀI LIỆU THAM KHẢO ............................................................................ 42 LỜI NÓI ĐẦU 1 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, một ứng dụng quan trọng từ bài toán xác định vị trí của điểm là xác định vị trí một cơ sở cần được xây dựng. 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. Bài toán xác định vị trí của một điểm, một cơ quanlà một ví dụ của bài toán định vị. Bài toán này không chỉ thu hẹp trong phạm vi những điểm lân cận mà còn được mở rộng sao cho đạt được sự tối ưu với các điểm ở biên, ví dụ như khi ta xây dựng một trạm phát sóng hay một trạm điện trong một thị trấn thì vấn đề đặt ra là vị trí xây dựng ở đâu để những hộ dân hay cơ quan xa nhất cũng nhận được tốt nhất. Bài toán định vị được gặp và áp dụng nhiều từ những bài toán tìm cực trị của một điểm đến những bài toán xác định nghiệm tối ưu kèm theo những điều kiện ràng buộc để giải quyết vấn đề tìm vị trí của một điểm sao cho đạt được sự tối ưu. Đâ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ôi chọn đề tài: Bài toán định vị và một số ứng dụng. Luận văn trình bày một cách có hệ thống 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 minimax và ứng dụng của bài toán này. Thang Long University Libraty LỜI NÓI ĐẦU 2 Luận văn gồm hai chương Chương 1: Kiến thức bổ trợ. 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, cực trị của hàm lồi, bài toán quy hoạch lồi, toán tử chiếu là những kiến thức nền tảng, cần thiết phục vụ cho việc nghiên cứu và giải quyết bài toán định vị. Chương 2: Bài toán định vị và ứng dụng. Chương này trình bày một cách tổng quan hơn về một bài toán định vị là bài toán tìm một điểm (hay một vị trí) trong một miền xác định sao cho khoảng cách lớn nhất từ điểm (vị trí) đó tới các điểm (vị trí) cho trước là nhỏ nhất. Xét một số ví dụ từ quá trình được nghiên cứu và giải bằng phương pháp hình học đến ví dụ áp dụng một thuật toán giải cho bài toán phức tạp hơn. 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. Chương 1. KIẾN THỨC BỔ TRỢ 3 CHƢƠNG 1 KIẾN THỨC BỔ TRỢ Chương này trình bày lại một số khái niệm và kết quả của giải tích lồi. Các khái niệm và kết quả này là những kiến thức nền tảng quan trọng, được sử dụng cho chương sau. Các kết quả trình bày trong chương này được tổng hợp từ các tài liệu [1], [2], [3], [4]. 1.1.Tập lồi Định nghĩa 1.1. Một tập C  là một tập lồi nếu C chứa đoạn thẳng đi qua hai điểm bất kỳ ,x y C , tức là ( ) , , 0,1 1x y C x y C            (1.1) Ta nói x là tổ hợp lồi của các điểm (véc-tơ) 1,..., kx x nếu 1 , 0 1...... k j j j j x x j k       và 1 1 k j j    . Tương tự, x là tổ hợp a-phin của các điểm (véc-tơ) 1,..., kx x nếu 1 k j j j x x    với 1 1 k j j    . Mệnh đề 1.1. Tập hợp C lồi khi và chỉ khi nó chứa mọi tổ hợp lồi của các điểm của nó. Tức là: C lồi khi và chỉ khi     1 k k N, ,..., > 0: 1 1 k j j    , 1,..., xkx C   1 k j j j x   C . Chứng minh. Điều kiện đủ là hiển nhiên từ định nghĩa. Ta chứng minh điều kiện cần bằng quy nạp theo số điểm. Với k = 2, điều cần chứng minh suy ra ngay từ định nghĩa của tập lồi và tổ hợp lồi. Giả sử mệnh đề đúng với k−1 điểm. Ta cần chứng minh mệnh đề đúng với k điểm. Thang Long University Libraty Chương 1. KIẾN THỨC BỔ TRỢ 4 Giả sử 1,..., xkx C là tổ hợp lồi của k điểm. Tức là 1 , 0 1,... , k j j j jx x j k       và 1 1 k j j    . Đặt      k 1 j j 1 . Khi đó 0 1  và 1 1 1 1 k k jj jk k j k k j j x x x x x                . Do 1 1 1 k j j      và 0 j   , 1,..., 1j k   nên theo giả thuyết quy nạp điểm 1 1 C k j j y       . Ta có k k x y x   . Do 0, 0k   và 1 1 k jk j        nên x là một tập hợp lồi của hai điểm y và kx đều thuộc C. Vậy .x C 1.2. Tập a-phin Định nghĩa 1.2. Nếu mọi đường thẳng đi qua hai điểm bất kỳ ,x y C đều thuộc tập C, tức là , , 1( )x y C x y C          (1.2) thì C được gọi là tập a-phin. Chương 1. KIẾN THỨC BỔ TRỢ 5 Từ định nghĩa cho thấy tập a-phin là một trường hợp riêng của tập lồi. Các không gian con, các siêu phẳng vv... là các trường hợp riêng của tập a- phin. Một ví dụ về tập a-phin là siêu phẳng được định nghĩa dưới đây. Định nghĩa 1.3. Siêu phẳng trong không gian n là một tập hợp các điểm có dạng  | an Tx x   trong đó na là một véc-tơ khác 0 và  . Véc-tơ a thường được gọi là véc-tơ pháp tuyến của siêu phẳng. 1.3. Tập lồi đa diện và định lý tách các tập lồi đa diện Định nghĩa 1.4. Một tập được gọi là tập lồi đa diện, nếu nó là giao của một số hữu hạn các nửa không gian đóng. Quy ƣớc: Giao của một họ rỗng các nửa không gian đóng là n . Định nghĩa 1.5. Nửa không gian là một tập hợp có dạng  | aTx x  trong đó 0a  và  . Tập trên là nửa không gian đóng. Tập  | aTx x  là nửa không gian mở. Nhận xét 1.1. (i) ,n  là các tập lồi đa diện. (ii) Tập lồi đa diện là tập hợp nghiệm của một hệ hữu hạn các bất phương trình tuyến tính. Dạng tường minh của một tập lồi đa diện được cho như sau:  |: , , 1,...,jn jD x a x b j m      , Thang Long University Libraty Chương 1. KIẾN THỨC BỔ TRỢ 6 ở đó , j 1, , , j 1,j n ja m b m    . Hoặc nếu ký hiệu A là ma trận có m-hàng là các véc tơ ja với j = 1, ..., m và véc-tơ 1(b ,..., b ) T mb  , thì hệ trên được viết là: |: .{ }nD x Ax b   Chú ý rằng, do một phương trình ,a x b có thể viết một cách tương đương dưới dạng hai bất phương trình ,a x b và ,a x b  nên tập nghiệm của một hệ hữu hạn các phương trình và bất phương trình cũng là một tập lồi đa diện. Định nghĩa 1.6. Cho 1 2,D D là hai tập khác rỗng. (i) Ta nói siêu phẳng H tách 1D và 2 D nếu 1D nằm trong nửa không gian đóng xác định bởi H, còn 2D nằm trong nửa không gian đóng kia. (ii) Ta nói siêu phẳng H tách thực sự 1D và 2 D nếu 1D và 2 D không đồng thời thuộc H. (iii) Ta nói siêu phẳng H tách mạnh 1D và 2 D nếu tồn tại ε >0 sao cho tập 1 nD B nằm trong nửa không gian mở xác định bởi H, còn 2 n D B nằm trong nửa không gian mở kia, ở đây { | || || 1}nB x x  là hình cầu đơn vị trong n . Nhận xét 1.2. Giả sử  | ,H x a x     , khi đó H tách mạnh 1D và 2D nếu tồn tại ε >0 sao cho Chương 1. KIẾN THỨC BỔ TRỢ 7  1 | ,nD B x a x      và  2 | ,nD B x a x      . Định lí 1.1. Nếu 1D và 2 D là các tập lồi đa diện, khác rỗng, rời nhau trong không gian Euclid hữu hạn chiều, thì tồn tại siêu phẳng tách mạnh 1 D và 2D . Định lí 1.2. Nếu 1D và 2 D là các tập lồi, khác rỗng trong n , thì điều kiện cần và đủ để tồn tại một siêu phẳng tách thực sự 1 D và 2 D là 1 2 riD riD  , ở đó riD ký hiệu cho phần trong tương đối của D. Định lí 1.3. (Định lý minimax) Cho hàm :f C D  với mC  , nD  là các tập lồi đóng khác rỗng f (u, v) là hàm lồi theo biến u, lõm theo biến v, xác định và liên tục trên C × D. Nếu một trong hai tập C và D là compact thì inf sup ( ) sup inf ( ), , v D vu Du C C f u v f u v     1.4. Bao lồi Định nghĩa 1.7. Cho P là tập hữu hạn k-điểm trong n , giao của tất cả các tập lồi chứa P được gọi là bao lồi của P. Ta kí hiệu bao lồi của P là conv(P).             1 1 ( ) : / , 0, 1,..., , 1 . k k i i i i i i i conv P x x P i k Nhận xét 1.3. Bao lồi của tập S là tập lồi nhỏ nhất chứa S. Bao lồi của một tập hữu hạn điểm nP  là một đa diện lồi trong n . Định nghĩa 1.8. Mỗi p P thỏa mãn  ( \ )p conv P p được gọi là một đỉnh của conv(P). Thang Long University Libraty Chương 1. KIẾN THỨC BỔ TRỢ 8 Định lí 1.4. (Định lí Caratheodory). Nếu dim X=m thì mọi điểm x ConvX có thể biểu diễn bằng tổ hợp lồi của không quá m+1 điểm thuộc X. Chứng minh: Xét x ConvX và giả sử tổ hợp lồi 1 1 , 1, 0, k k i i i i i i i x x x X          . là tổ hợp lồi có số véctơ k nhỏ nhất có thể được của x . Ta sẽ chứng minh 1k m  . Thật vậy, giả sử ngược lại 1k m  , các vectơ 1{ ,..., }kx x không thể độc lập affine vì dim X m , như vậy các véctơ 2 1 1{ ,..., }kx x x x  không thể độc lập tuyến tính. Tức là, tồn tại bộ số  2,..., 0k   sao cho 1 2 ( ) 0. k i i i x x    Nếu đặt 1 2 k i i      , ta có 1 1 1 0, 0, ( ,..., ) 0. k k i i i k i i x          Như vậy, x có thể viết lại như sau 1 1 1 ( ) ( ) . k k k i i i i i i i i i i x x t x t x             Rõ ràng, với t đủ nhỏ, biểu thức trên vẫn là tổ hợp lồi của x . Tuy nhiên nếu ta chọn 0 min | | i i i t     thì số hệ số dương trong tổ hợp lồi sẽ ít hơn số hệ số dương trong tổ hợp ban đầu, mâu thuẫn với giả thiết k là nhỏ nhất có thể được. Chương 1. KIẾN THỨC BỔ TRỢ 9 Lưu ý: chắc chắn tồn tại , 0ii   vì 1 1 0, ( ,..., ) 0 k i k i       . Định lý 1.5. (Định lý Radon) Một tập có ít nhất 2n  điểm trong n có thể chia thành hai tập con có bao lồi giao nhau. 1.5. Hàm lồi và cực trị của hàm lồi Định nghĩa 1.9. Cho hàm f xác định trên tập lồi D. Hàm f được gọi là hàm lồi trên D nếu           1 1 , , , 0,1 .f x y f x f y x y D             (1.3) Hàm f được gọi là hàm lồi chặt trên D nếu            1 1 , , , 0,1 .f x y f x f y x y D             (1.4) Hàm f được gọi là hàm lồi mạnh trên D với hệ số 0  nếu   2 (1 ) ( ) (1 )f( ) (1 ) , , , (0,1). 2 f x y f x y x y x y D                    (1.5) Bổ đề 1.1. (i). Cho vector a cố định, na nào đó, hàm   2 ( ) :f x x a là lồi mạnh với modun 1  trên toàn không gian n . (ii). Cho J là tập chỉ số hữu hạn khác rỗng, X là tập lồi và jg là hàm lồi mạnh trên X với modun  j với mọi j J . Khi đó, hàm max jj Jg g là lồi mạnh trên X với modun   min j J j . Định nghĩa 1.10. Cho    : nf là hàm lồi. Vector v được gọi là dưới gradient của f tại x nếu với mọi  n y ta có   , ( ) ( ).v y x f y f x Tập dưới gradient của f tại x được gọi là dưới vi phân của f tại x và được kí hiệu bởi ( )f x . Hàm f được gọi là khả dưới vi phân tại x nếu Thang Long University Libraty Chương 1. KIẾN THỨC BỔ TRỢ 10 ( )f x  . f được gọi là khả dưới vi phân nếu nó khả dưới vi phân tại mọi x domf , với     : ( ) .ndomf x f x Định nghĩa 1.11. Cho X là một tập lồi trong n . Điểm x X được gọi là điểm cực biên của X nếu không tồn tại , ,y z X y z  sao cho (1 )x y z    với 0 1  . Khi X là một tập lồi đa diện, điểm cực trị của nó còn được gọi là đỉnh. Đối với tập hữu hạn điểm P, chúng ta sẽ đề cập đến các bài toán lồi như là bài toán tìm bao lồi của P. 1.5.1. Cực tiểu địa phƣơng và cực tiểu toàn cục. Định nghĩa 1.12. Giả sử : ,[ ] n f    là hàm số tùy ý và n C  là tập tùy ý. Điểm 0 x C dom f  , nếu với mọi x ∈ C ta có  0( ) f x f x   thì 0x được gọi là điểm cực tiểu toàn cục của  f x trên C. Nếu tồn tại lân cận 0 ( )U x của 0x sao cho   0 ( ) f x f x   với mọi 0 ( )x C U x  thì 0x C được gọi là điểm cực tiểu địa phương của  f x trên C. Các khái niệm cực đại địa phương và cực đại toàn cục được định nghĩa tương tự. Đối với hàm tùy ý f trên tập C, ta ký hiệu tập tất cả các điểm cực tiểu (cực đại) toàn cục của f trên C là    ( )x C x CArgmin f x Argmax f x  . Do    { }: :{ }min f x x C max f x x C     nên lý thuyết cực tiểu (hay cực đại) hàm lồi cũng chính là lý thuyết cực đại (hay cực tiểu) hàm lõm. Chương 1. KIẾN THỨC BỔ TRỢ 11 1.5.2. Cực tiểu hàm lồi (cực đại hàm lõm) Định lý 1.6. Cho : n f  là hàm lồi và C là tập lồi, khác rỗng trong n . Mọi điểm cực tiểu địa phương của f trên C đều là điểm cực tiểu toàn cục. Tập  x CArgmin f x là tập lồi của C. Từ đây suy ra bất cứ điểm cực đại địa phương nào của một hàm lõm trên một tập lồi cũng là điểm cực đại toàn cục. Tập tất cả các điểm cực đại của một hàm lõm trên tập lồi là lồi. Định lý 1.7. Với mọi hàm lồi chính thường f: a) Cực đại của f trên một đoạn thẳng bất kỳ đạt tại một đầu mút của đoạn đó. b) Nếu  f x hữu hạn và bị chặn trên trên một nửa đường thẳng thì cực đại của f trên nửa đường thẳng này đạt tại điểm gốc của nó. c) Nếu  f x hữu hạn và bị chặn trên trên một tập a-phin thì f bằng hằng số trên tập này. Mệnh đề 1.2. Giả sử  f x là hàm lồi khả vi liên tục, xác định trên tập lồi C và giả sử 0 x C . Khi đó,  0( )f x f x x C   (nghĩa là 0 x là điểm cực tiểu của hàm  f x trên C) khi và chỉ khi 0 0, 0( )f x x x    với mọi x C . Mệnh đề 1.3. Giả sử : n f  là hàm lồi và C là tập lồi trong n . Điều kiện cần và đủ để 0 x C là điểm cực tiểu của f trên C là 0 0 ( )0 ( ),Cf x N x với 0 0 : , 0,( ) { }CN x p p x x x C      là nón pháp tuyến trong của C tại 0 x . Thang Long University Libraty Chương 1. KIẾN THỨC BỔ TRỢ 12 Hệ quả 1.1. Với các giả thiết như trong Mệnh đề 1.3, điểm trong 0 x C là điểm cực tiểu khi và chỉ khi 0 ( ).0 f x Mệnh đề 1.4. Giả sử n C  là tập , :Compact f C  là một hàm liên tục bất kì và C f là hàm bao lồi của f trên C. Khi đó, mỗi điểm cực tiểu toàn cục của f trên C cũng là một điểm cực tiểu của ( ) C f x trên convC. Mệnh đề 1.5. Muốn cho điểm * x của tập lồi đóng C là điểm cực tiểu của hàm lồi khả vi  f x trên C, điều kiện cần và đủ là * *( ,)x p y trong đó * * * ( )y x f x   và 0  là một số bất kỳ. 1.5.3. Cực tiểu của hàm lồi mạnh Sau đây ta xét một lớp hàm luôn có cực tiểu trên mọi tập đóng khác rỗng. Hơn nữa, giống như hàm lồi chặt, cực tiểu này là duy nhất nếu tập đó là lồi. Định nghĩa 1.13. Hàm  f x xác định trên tập lồi nC  được gọi là lồi mạnh, nếu tồn tại hằng số 0  đủ nhỏ (hằng số lồi mạnh) sao cho với mọi , y Cx  và mọi  0,1  ta có bất đẳng thức: 2 [ ( ) ] ( ) ( ) ( ) ( ) || | 1 1 |1 .f x y f x f y x y              (1.6) Có thể chứng minh rằng hàm  f x lồi mạnh khi và chỉ khi hàm 2 ( ) .f x x là lồi. Rõ ràng một hàm lồi mạnh thì lồi chặt, nhưng điều ngược lại không chắc đúng (chẳng hạn, hàm , x e x lồi chặt nhưng không lồi mạnh). Mệnh đề 1.6. Nếu  f x là hàm lồi mạnh và khả vi trên tập lồi đóng C thì: Chương 1. KIẾN THỨC BỔ TRỢ 13 a) Tồn tại duy nhất điểm *x C sao cho  .( ) min ( ) :f x f x x C   b) 2 , ( ) ( ) || ||f x f y x y x y      với mọi x, y ∈ C. c) Với bất kỳ 0 x C tập mức dưới   0 0 : ( ) ( )C x C f x f x   bị chặn. Mệnh đề 1.7. Giả sử  f x lồi mạnh trên tập lồi đóng C và 0x là điểm cực tiểu của f trên C. Khi đó, với mọi x C ta có 020 || || [ ( ) 2 ( )].x x f x f x     (1.7) Hơn nữa, nếu f khả vi thì 0 || || || ( ) | 1 |x x f x     (1.8) và 0 21 ( ) ( ) |0 | ( ) || .f x f x f x      1.5.4. Cực đại hàm lồi (cực tiểu hàm lõm) Mệnh đề 1.8. Giả sử n C  là tập lồi và :f C  là hàm lồi. Nếu  f x đạt cực đại trên C tại điểm trong tương đối 0x của 0 )(C x riC thì  f x bằng hằng số trên C . Tập  x CArgmax f x là hợp của một số diện của .C Mệnh đề 1.9. Giả sử C là tập lồi, đóng và :f C  là hàm lồi. Nếu C không chứa đường thẳng nào và  f x bị chặn trên trên mọi nửa đường thẳng trong C thì    ( ) : ( ) : ( ) ,sup f x x C sup f x x V C   Thang Long University Libraty Chương 1. KIẾN THỨC BỔ TRỢ 14 trong đó  V C là tập các điểm cực biên của C , nghĩa là nếu cực đại của  f x đạt được trên C thì cực đại cũng đạt được trên  V C . Hệ quả 1.2. Hàm lồi thực  f x trên tập lồi đa diện D, không chứa đường thẳng nào, hoặc không bị chặn trên trên một cạnh vô hạn nào đó của D, hoặc đạt cực đại tại một đỉnh của D. Hệ quả 1.3. Hàm lồi thực  f x trên tập lồi compact C đạt cực đại tại một điểm cực biên của C. 1.6. Bài toán quy hoạch lồi 1.6.1. Bài toán và định nghĩa Cho nD  và : n f  . Xét bài toán quy hoạch toán học   : }.{min f x x D (P) Bài toán này có nghĩa là hãy tìm một điểm x D  sao cho ( ) ( )f x f x   với mọi x D . Mỗi điểm x D  được gọi là một phương án chấp nhận được của bài toán (P). Tập D được gọi là miền (tập) chấp nhận được, f được gọi là hàm mục tiêu của bài toán (P). Thông thường, tập D được cho như là tập nghiệm của một hệ bất đẳng thức hoặc đẳng thức có dạng    : :g 0,h 0, 1,..., , 1,. }, ,{ ..j iD x X x x j m i p      (1.9) trong đó nX   và  g ,h : 1,... , 1,... . n j i j m i p   Bài toán (P) với D cho bởi (1.9) gọi là trơn nếu cả hàm mục tiêu và các ràng buộc đều trơn (khả vi). Bài toán (P) có rất nhiều ứng dụng trong các lĩnh vực khác nhau. Định nghĩa1.14. Điểm x D được gọi là lời giải tối ưu địa phương của bài toán (P) nếu tồn tại một lân cận U của x  sao cho Chương 1. KIẾN THỨC BỔ TRỢ 15  * (x ) ,f f x x U D    và x D gọi là lời giải tối ưu toàn cục của (P) nếu  *(x ) , .f f x x D   1.6.2. Sự tồn tại nghiệm tối ƣu Xét bài toán tối ưu toàn cục (P). Có 4 trường hợp tồn tại nghiệm tối ưu của bài toán này • D = ∅ (không có nghiệm). • f không bị chặn dưới trên  (inf ). x D D f x    •  inf x D f x   nhưng giá trị cực tiểu không đạt được trên D. • Tồn tại x D sao cho ( ) min ( ). x D f x f x   Định lí 1.8. Để bài toán (P) tồn tại nghiệm tối ưu toàn cục thì điều kiện cần và đủ là  ( ) : : },{D t f x t xF D      đóng và bị chặn dưới. Định lí 1.9. (Weierstrass). Nếu D là tập compact và f nửa liên tục dưới trên D thì bài toán (P) có nghiệm tối ưu. Định lí 1.10. Nếu f nửa liên tục dưới trên D và thỏa mãn điều kiện bức sau   ,f x khi x D x   thì f có điểm cực tiểu trên D. 1.6.3. Điều kiện tối ƣu Xét bài toán (P) định nghĩa bởi Min f(x) với điều kiện  : : ( ) 0, ( ) 0, 1,..., , 1,..., ,j ix D x X g x h x j m i k       Thang Long University Libraty Chương 1. KIẾN THỨC BỔ TRỢ 16 trong đó nX   và , : ), ,( n j i f g h j i  . Ta gọi bài toán (P) là bài toán lồi nếu X là tập lồi đóng và các hàm , jf g là lồi, ih là hàm affine. Định lí 1.11. (Karush-Kuhn-Tucker). Giả sử (P) là bài toán lồi. Nếu * x là một nghiệm tối ưu của bài toán (P) thì tồn tại  * 0 0,1,...,i i m   và  * 1,...,jµ j k không đồng thời bằng 0 sao cho * * * * *, , min , ,( ) ( ) x X L x µ L x µ    (điều kiện đạo hàm triệt tiêu),  * * 0 1,..( ) ,i ig x i m   (điều kiện bù). Hơn nữa, nếu intX = và điều kiện Slater .    0 0: 0 1,..., .ix D g x i m    được thỏa mãn và các hàm affine  1,..,ih i k độc lập tuyến tính trên X thì * 0 0  và các điều kiện đạo hàm triệt tiêu và điều kiện bù là điều kiện đủ để điểm chấp nhận được * x là nghiệm tối ưu của bài toán (P). Chú ý rằng, nếu X là tập mở (hơn nữa X là toàn bộ không gian) thì theo Moreau-Rockafellar, điều kiện đạo hàm triệt tiêu kéo theo 1.7. Toán tử chiếu Định nghĩa 1.15. Giả sử C  là một tập con của không gian n và ny là một vectơ bất kì, gọi ( ) inf . C x C d y x y    Ta nói ( )Cd y là khoảng cách từ y tới C. Nếu tồn tại ( )CP y C sao cho ( ) (y) C C d y y P  , thì ta nói (y)CP là hình chiếu của y lên C. * * * * * 1 1 0 f(x ) + (x ) + (x ). m k j j i i j i g h        Chương 1. KIẾN THỨC BỔ TRỢ 17 Từ định nghĩa này hình chiếu (y)CP của y trên C là nghiệm của bài toán tối ưu 21 min 2x C x y         . Nói cách khác, việc tìm hình chiếu của y trên C có thể đưa về việc tìm cực tiểu của hàm 2x y trên C. Mệnh đề 1.10. Cho C là một tập lồi đóng khác rỗng trong không gian n , khi đó với mọi n x , hình chiếu ( )CP x của x trên C luôn tồn tại và duy nhất. Chứng minh: Giả sử ,nx y C  ta có ( )Cd x y x  , suy ra tồn tại dãy ( )n nx  trong C sao cho ( )n Cx x d x   . Vậy dãy ( )n nx  là bị chặn do đó có một dãy con ( )nk x hội tụ yếu đến y . Do C đóng nên y C vậy lim lim ( ) n n Cn nk y x x x x x d x      . Chứng tỏ y là hình chiếu của x trên C. Bây giờ ta chứng minh tính duy nhất của hình chiếu. Thật vậy, nếu tồn tại hai điểm y và z đều là hình chiếu của x trên C thì ( ), (z) C C x y N y x z N    . Tức là, , 0y x z y   và , 0z x y z   . Thang Long University Libraty Chương 1. KIẾN THỨC BỔ TRỢ 18 Cộng hai vế của bất đẳng thức này ta suy ra 0y z  và do đó y z . Mệnh đề 1.11. Cho C là một tập lồi đóng khác rỗng trong không gian n , ánh xạ ( )Cy P y khi đó: ( ). ( ) (y) , n C C i P x P x y x y     (tính không giãn); 2 ( ). ( ) (y) ( ) (y), , n C C C C ii P x P P x P x y x y      (tính đồng bức). Chứng minh: Theo Mệnh đề 1.10 ánh xạ ( ) C x P x xác định khắp nơi. Do ( ) ( ( )) C z p z N p z  với mọi z. Nên áp dụng với z x và z y , ta có ( ), ( ) ( ) 0;x p x p y p x   và ( ), ( ) ( ) 0.y p y p x p y   Cộng hai bất đẳng thức lại ta được ( ) ( ), ( ) ( ) 0.p y p x p y p x x y     Áp dụng bất đẳng thức Cauchy-Shwarz suy ra ( ) ( ) .p x p y x y   ii) Để chứng minh tính đồng áp bức áp dụng Mệnh đề 1.11 lần lượt với ( )p x và ( )p y ta có: ( ) , ( ) ( ) 0.p x x p x p y   ( ), ( ) ( ) 0.y p y p x p y   Cộng hai bất đẳng thức ta được 2 ( ) ( ) , ( ) ( ) ( ) ( ), ( ) ( ) 0.p x p y y x p x p y p x p y y x p x p y          Chương 1. KIẾN THỨC BỔ TRỢ 19 Chuyển vế ta được 2 ( ) ( ), ( ) ( ) .p x p y x y p x p y    Tóm lại việc xác định hình chiếu là rất khó, nhưng trong một số trường hợp chúng ta vẫn có thể xác định được. Ta xét một số trường hợp cụ thể thường gặp trong các ví dụ dưới đây. Ví dụ 1.1. Chiếu xuống hình cầu đóng. Cho C là hình cầu bán kính R tâm 1 2(a , ,..., ) T n nA a a  được định nghĩa bởi 2 2 1 2 1 ( ) .: (z ,z ,...,z ) | n T n n i i i z aC z             Khi đó, hình chiếu ( )Cy P x của x lên C được xác định như sau Nếu x C thì y x . Nếu x C thì hình chiếu của x lên C là giao điểm của đường thẳng nối x với tâm A của C, kí hiệu là  với mặt cầu 2 2 1 : | ( ) . n n i i i C z z a            Ta có  1 2(z ,z ,...,z ) | ( ), i 1,...,n, t . n n i i i iz z a t x a         Thay ( )i i i iz a t x a   ta được 2 2 2 1 .( ) n i i i t x a    Do đó 1 22 1 . ( ) n i i i R t x a          Vì vậy, y có tọa độ như sau Thang Long University Libraty Chương 1. KIẾN THỨC BỔ TRỢ 20 1 22 1 ( ) ( ). ( ) i i i i i i i n i i i R y a t x a a x a x a               Ví dụ 1.2. Chiếu xuống hình hộp chữ nhật Cho C là một hình hộp được định nghĩa bởi  1 2: ( , ,..., ) | , 1,2,...,n ,T nn i i iC x x x x a x b i      1 2 1 2 ( , ,..., ) , (b ,b ,...,b )T Tn na a a a b T   . Khi đó, hình chiếu của x lên C được xác định như sau: , ( ( )) , , , i i i i i i i iC i i i a khi x a P x x khi x a b b khi x b             . Chương 2. BÀI TOÁN ĐỊNH VỊ VÀ ỨNG DỤNG 21 CHƢƠNG 2 BÀI TOÁN ĐỊNH VỊ VÀ ỨNG DỤNG Trong chương này giới thiệu về bài toán định vị, 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 và ví dụ áp dụng. Các kết quả trình bày trong chương này được tổng hợp từ các tài liệu [4],[5], [6]. 2.1. Giới thiệu bài toán Bài toán định vị xét trong chương này có thể mô tả như sau. Giả sử trong không gian 2 cho tập C gồm p điểm 1 2,v ,...,v pv và một tập 2D cho trước, D  . Bài toán yêu cầu tìm một điểm trong tập D sao cho khoảng cách (theo một nghĩa nào đó) đối với các điểm trong tập C là nhỏ nhất. Khoảng cách ở đây có thể lấy theo chuẩn Euclid hoặc có thể được định nghĩa một cách tổng quát phù hợp với yêu cầu cụ thể của từng bài toán. Trong nhiều trường hợp người ta có thể thay khoảng cách bằng một hàm chi phí nào đó phụ thuộc vào điểm cần tìm. Một trường hợp riêng được xét là tổng khoảng cách từ điểm cần tìm tới các điểm khác là nhỏ nhất. Một trường hợp riêng khác là khoảng cách xa nhất từ điểm cần tìm đến các điểm khác là nhỏ nhất. Gọi ( , )c x v là chi phí (hay khoảng cách) liên quan đến điểm x,v. Khi đó mô hình toán học cho bài toán tìm vị trí x D sao cho tổng chi phí ( , )c x v , v là nhỏ nhất. Vậy bài toán có thể viết dưới dạng bài toán tối ưu như sau: 1 ( ) : ( , ) : p j j Min f x c x v x D          . (1) Người ta có thể thay hàm mục tiêu bằng tổng chi phí bởi những hàm mục tiêu khác tùy thuộc vào yêu cầu cụ thể của từng bài toán. Một trường hợp hay được sử dụng là lấy hàm mục tiêu min, max. Tức là Thang Long University Libraty Chương 2. BÀI TOÁN ĐỊNH VỊ VÀ ỨNG DỤNG 22  1( ) max ( , ) : 1,..., jf x c x v j p  . Ví dụ khi ( , )j jc x v x v  thì hàm  1 .( ) max : 1,...,jf x x v j p   Khi đó bài toán có dạng  1 .( ) :Min f x x D (2) Có nghĩa là tìm một điểm (vị trí) x D sao cho khoảng cách xa nhất từ x đến các điểm đã cho là gần nhất. Hay nói một cách khác Bài toán (2) là bài toán: Tìm x D sao cho: * 1 1 ( ) ( )f x f x x D   . Bài toán định vị đã có một lịch sử phát triển từ thế kỉ 17. Ta xét một trường hợp đơn giản của bài toán định vị đã được nghiên cứu trong ví dụ sau: Ví dụ 2.1.(Bài toán Fermat – Torricelli – Napoleon) Vào thế kỉ 17, nhà toán học Pháp Pierre de Fermat (1601-1665) đã đặt ra bài toán sau đây: “Cho trước ba điểm trong mặt phẳng. Hãy tìm điểm thứ tư sao cho tổng khoảng cách từ điểm này tới ba điểm cho trước là nhỏ nhất”. Bài toán đã được nhiều nhà toán học nghiên cứu và đưa ra lời giải. Chương 2. BÀI TOÁN ĐỊNH VỊ VÀ ỨNG DỤNG 23 Hình 2.1. Phƣơng pháp Torricelli. Vào khoảng năm 1640 Evangelista Torricelli (1608-1647) đã giải bài toán của Fermet bằng phương pháp hình học như sau: 1. Từ ba điểm cho trước A, B, C, dựng các tam giác đều: CAB’, ABC’,CBA’ bên ngoài ABC. 2. Dựng các đường tròn ngoại tiếp các tam giác đều CAB’, ABC’,CBA’. Ba đường tròn này cắt nhau tại một điểm, kí hiệu là M. Điểm M chính là điểm có tổng khoảng cách đến ba điểm A, B, C ngắn nhất. Điểm này được gọi là điểm Torricelli của ABC đã cho. Bonaventura Francesco Cavalieri (1598 – 1667) trong cuốn sách “Exezci-tationes geometricae” xuất bản năm 1647 đã chỉ ra rằng điểm Torricelli M nhìn ba cạnh của ABC dưới các góc bằng 0120 . Vào năm 1750 Thomas Simpson (1710 – 1761) đưa ra một phương pháp tìm điểm Torricelli thực hiện bằng cách vẽ ba đường Simpson nối mỗi đỉnh của tam giác đều nằm ngoài ABC với đỉnh đối diện của ABC. Ba đường Simpson cắt nhau tại một điểm, điểm này cũng là điểm Torricelli. Thang Long University Libraty Chương 2. BÀI TOÁN ĐỊNH VỊ VÀ ỨNG DỤNG 24 Hình 2.2. Phƣơng pháp Simpson. Phải đến năm 1834 nhà toán học Franz Heinen mới đưa ra lời giải trọn vẹn cho bài toán Fermat như sau: 1. Nếu một trong các góc của ABC được tạo thành từ ba điểm A, B, C lớn hơn hoặc bằng 0120 thì lời giải bài toán Fermat là điểm trùng với đỉnh của góc lớn hơn hoặc bằng 0120 . 2. Nếu các góc của ABC nhỏ hơn 0120 thì lời giải bài toán Fermat là giao điểm của các đường Simpson hoặc điểm Torricelli và là điểm nhìn các cạnh của ABC với ba góc bằng 0120 . Ông cũng chỉ ra rằng tổng khoảng cách từ điểm Torricelli đến ba đỉnh của tam giác bằng độ dài của các đường Simpson. Hình 2.3. Phƣơng pháp Napoleon - Heinen. Chương 2. BÀI TOÁN ĐỊNH VỊ VÀ ỨNG DỤNG 25 Ứng dụng bài toán Fermat trong thực tế Vào thế kỷ thứ 19, Steiner đã tổng quát bài toán của Fermat bằng cách không hạn chế số điểm cần tìm. Quãng 100 năm sau, Courant và Robin đã ghi chú về bài toán tổng quát này như sau: “Một vấn đề rất giản đơn nhưng lại rất có tính kiến thiết là vấn đề được nêu ra bởi Jacob Steiner, một đại diện nổi tiếng của trường phái hình học Berlin vào đầu thế kỷ 19. Ba làng A, B và C phải được nối với nhau bởi một hệ thống đường giao thông với tổng độ dài nhỏ nhất có thể.” Bài toán này Gauss đã đặt ra cho hệ thống các đường tàu nối các thành phố Harburg, Bremen, Hannover và Braunschweig và đã được Karl Bopp (1856-1905) giải quyết một cách triệt để. Trong hình (2.4), chúng ta đã thấy mô tả lời giải của bài toán này. Hệ thống đường sắt tối ưu được bổ sung thêm một điểm, điểm Torricelli của tam giác với ba đỉnh là ba thành phố Harburg, Bremen, Hannover, và Braunschweig được nối với Hannover bởi một tuyến đường sắt chạy thẳng. Hình 2.4. Mạng giao thông tối ƣu nối bốn thành phố Harburg Bremen Hannover Braunschweig Thang Long University Libraty Chương 2. BÀI TOÁN ĐỊNH VỊ VÀ ỨNG DỤNG 26 2.2. Phƣơng pháp tối ƣu giải một bài toán định vị Trong chương này, chúng ta sẽ đề cập đến phương pháp giải bài toán tìm một điểm sao cho khoảng cách lớn nhất từ điểm ấy đến tập C là nhỏ nhất. Trước hết ta xét một số khái niệm: Định nghĩa 2.1. Khoảng cách cực đại từ một điểm x đến một tập C được định nghĩa bởi   2 ( ,C) : maxy Cd x x y , khi đó bài toán tối ưu phải giải là: min ( , ) x D d x C  (P) . Hình 2.5. Một bài toán định vị Bổ đề 2.1. Gọi CV là kí hiệu tập các đỉnh của conv(C). Khi đó, ta có (i)  ;CV C (ii)    2( ,C) : max / .Cd x x y y V Chứng minh. Ta thấy (i) được suy ra trực tiếp từ định nghĩa của tập .CV Từ (ii) ta thấy rằng          2 2 2 ( ) ( , ) max max max , y C y conv C y VC d x C x y x y x y trong đó, đẳng thức sau là giá trị lớn nhất của hàm lồi trên tập lồi đạt được tại cực trị của nó. d(x,C)x D C Chương 2. BÀI TOÁN ĐỊNH VỊ VÀ ỨNG DỤNG 27 Bổ đề 2.2. Cho 1 ,.., m v v là các phần tử của CV và   2 (x,C) : j jd x v với mỗi   : 1,...,j J m . Khi đó, ta có (i) ( , )d x C là lồi mạnh với hệ số 1. (ii) ( )(., )( ) ( (., )( ))jj J xd C x conv d C x    với (., )( )jd C x là dưới vi phân của hàm lồi (., )jd C tại x và    J( ) / ( , ) ( , ) .jx j J d x C d x C Chứng minh. Từ Bổ đề 1.1(i) ta có      2 ( , ) max max ( , ). j jj J j J d x C x v d x C (2.1) Từ Bổ đề 1.1(i), hàm   2 ( , ) j jd x C x v với mỗi j J nào đó là lồi mạnh với hệ số 1. Do đó (i) nhận được từ (ii) của Bổ đề 1.1, và (ii) nhận được từ (2.1). Bổ đề 2.3. Giả sử rằng dãy  k là dãy các số dương thỏa mãn điều kiện 1 , , k kk k        với 0 k   và 0 . k k     Khi đó, dãy  k là hội tụ. Chứng minh: Trước hết ta sẽ chứng minh điều dưới đây: Cho ( )nS là dãy số không âm thỏa mãn điều kiện 1 (1 ). , 0n n n nnS S n       , ( ) trong đó ( ),( )n n  là các dãy số thực sao cho: (i) ( ) 0,1na    và 0 n n a    , hoặc tương đương 0 0 (1 ) lim (1 ) 0 n n knn k           . Thang Long University Libraty Chương 2. BÀI TOÁN ĐỊNH VỊ VÀ ỨNG DỤNG 28 (ii) sup 0n n Lim    (iii) n n n   hội tụ Khi đó , lim 0nn S   . Thật vậy, đầu tiên giả sử rằng (i) và (ii) là đúng. Với 0  bất kì, cho 1N  đủ lớn sao cho n  với n N . Từ ( ) , cho n N , ta có 1 1 1 1 (1 ) (1 )(1 ) (1 (1 )(1 )). n n nn n nn n n S S S                      Do đó, bằng phép quy nạp, ta thu được 1 (1 ) 1 (1 ) ,n N. n n j jNn j N j N S S                  Từ điều kiện (i) ta có 1 lim sup nn S   Tiếp theo, giả sử rằng (i) và (iii) đúng. Khi đó, tiếp tục áp dụng (*) ta nhận được với mọi n > N 1 (1 ) . n n j j jn j mj m S Sm          từ (**) ta thu được limsup 0.nn S  Từ đó suy ra Bổ đề (2.3) được chứng minh . 2.2. 1. Thuật toán Từ Bổ đề 2.1(ii) xét bài toán sau đây , ,Cho n m  Chương 2. BÀI TOÁN ĐỊNH VỊ VÀ ỨNG DỤNG 29      2 min ( ,C) min max . x D x D v VC d x x v (P) Giả sử D là tập lồi đóng. Vì d(x,C) lồi mạnh trên D nên bài toán (P) có nghiệm tối ưu duy nhất . Thuật toán sau có thể được coi như cải biên của thuật toán dưới vi phân. Thuật toán 2.1. Khởi đầu. Chọn 0x D , tham số 0  cố định và một dãy  k của các số dương thỏa mãn điều kiện            2 0 0 , .k k k k (2.2) Cho k:=0 Bước 1. Tìm  k Cv V sao cho    2arg : .k k Cv max x v v V Bước 2. Lấy  : 2( ), k k k g x v nghĩa là, đạo hàm của  2k k x v tại . k v Trường hợp 2a): Nếu  0 k g , khi đó dừng thuật toán: k x là nghiệm tối ưu của (P). Trường hợp 2b): Nếu  0, k g tính       max , k k k g , và   1 : ( )k k kD kx P x g , với DP là toán tử hình chiếu Ơclid lên D. Bước 3. Nếu 1k kx x  , khi đó, thuật toán dừng: kx là nghiệm tối ưu của (P). Ngược lại, cho k:=k+1 và quay lại bước 1. Thang Long University Libraty Chương 2. BÀI TOÁN ĐỊNH VỊ VÀ ỨNG DỤNG 30 Hình 2.6. Sơ đồ thuật toán 2.1 Chọn Cho k:=0 Tìm ? Tính Tính Cho k :=k+1 là nghiệm tối ưu là nghiệm tối ưu Đ S Đ S Chương 2. BÀI TOÁN ĐỊNH VỊ VÀ ỨNG DỤNG 31 Để minh họa cho thuật toán ta xét ví dụ sau: Ví dụ 2.2. Cho  1 2 3 4 2 1 2 3 4) :( , , , (0,0); a (0,1); (1,1); (1,0)CV a a a a a a a      là tập các đỉnh của convC.  2 1 2: 0D x x x    . Hãy tìm một điểm trên D sao cho khoảng cách từ điểm đó tới điểm xa nhất trên C là ngắn nhất. Bước khởi đầu. Chọn 0 (0,0)x  , tham số 1  và dãy 1 1k k    . Cho k:=0 Bước 1. Tìm 0v . Ta có: 2 2 2 0 1 0 0 0 0. 0 0 0 x a                             2 2 2 0 2 0 0 0 1. 0 1 1 x a                              2 2 2 0 3 0 1 1 2. 0 1 1 x a                               2 2 2 0 4 0 1 1 1. 0 0 0 x a                              C a2=(0;1) a1=(0;0) a4=(1;0) a3=(1;1) 1 1 1 4 1 4 (14; 1 4) (1;1) 0 Thang Long University Libraty Chương 2. BÀI TOÁN ĐỊNH VỊ VÀ ỨNG DỤNG 32 Vậy 0 3v a . Bước 2. Tính 0 0 0 . 0 1 1 2 2( ) 2 2 0 1 1 2 g x v                                              0 0g  và 0 8.g  Có 0 1     0 0 . 1 1 1 8max 1, 8max , g         1 0 00 . 1 1 0 2 0 2 21 0,0 0 2 0 1 18 2 2 D D D Dx P x g P P P                                                                     Ta thấy 1 0x x . Vậy thuật toán dừng: 1x là điểm tối ưu cần tìm. Định lý 2.1. (i). Nếu Thuật toán 2.1 dừng tại bước lặp k, khi đó kx là nghiệm tối ưu của bài toán (P). (ii). Nếu Thuật toán 2.1 chưa dừng, khi đó dãy  kx hội tụ đến nghiệm x của bài toán (P). Chứng minh. (i). Nếu Thuật toán 2.1 dừng tại bước lặp k, khi đó hoặc  0 k g hoặc  : ( )k k kD kx P x g . Trong trường hợp đầu tiên,  0 ( , ) k k g d x C , theo định nghĩa của dưới vi phân ta suy ra     0,x x ( , ) (x,C) x D k k d x C d . Do đó Chương 2. BÀI TOÁN ĐỊNH VỊ VÀ ỨNG DỤNG 33   ( , ) ( , ) . k d x C d x C x D (2.3) Điều này có nghĩa là kx là cực tiểu hóa hàm (x,C)d trên D. Trong trường hợp thứ 2,   1 ( )k k k kD kx x P x g . Khi đó, áp dụng tính chất của phép chiếu tham số ta có              ( ) , 0 , 0 , 0. k k k k k k k k k k x g x x x g x x g x x (2.4) Vì  ( , ) k k g d x C , ta có   , (x , ) ( , ) k k k g x x d C d x C . Kết hợp với bất đẳng thức (2.4) ta có (x , ) ( , ) k d C d x C với mỗi x D . Do đó kx là nghiệm tối ưu của (P). (ii). Bây giờ, giả sử rằng các thuật toán không dừng. Giả sử x là nghiệm của Bài toán (P). Ta sẽ chứng minh (ii) dựa vào các bổ đề sau. Bổ đề 2.4. Ta có     1 .k k kx x k N Chứng minh. Theo định nghĩa của k ta có         max , . k kk k kk g g g Từ 1 : ( ),k k kD kx P x g    áp dụng tính chất của phép chiếu tham số, ta có Thang Long University Libraty Chương 2. BÀI TOÁN ĐỊNH VỊ VÀ ỨNG DỤNG 34        1 1, 0 .k k k kkx g x x x x D (2.5) Thay thế x bởi kx ta được               21 1 1 1 , k k k k k k k k k k k k k x x g x x g x x x x (2.6) trong đó   1k k kx x . Bổ đề 2.5. Với mỗi k, dãy  2*kx x hội tụ . Chứng minh. Áp dụng định nghĩa không gian định chuẩn Ơclid, ta có             2 2 2* 1 1 * 1 1 * 2 , k k k k k k k x x x x x x x x x x . Vì vậy             2 2 21 * * 1 1 * 1 2 , . k k k k k k k x x x x x x x x x x (2.7) Chú ý rằng từ (2.6), ta có       1 1 2 .,k k k k kk k kg x x x x (2.8) Khi đó, từ (2.7) và (2.8) cho ta                                  2 2 21 * * 1 * 1 2* * 1 2 * * 1 2 * 2 2 g , 2 g , 2 g , 2 g , * 2 g , 2 . k k k k k k k k k k k k k k k k k k k k k k k k x x x x x x x x x x x x x x x x x x x x x x (2.9) Vì  ( , ), k k g d x C ta có Chương 2. BÀI TOÁN ĐỊNH VỊ VÀ ỨNG DỤNG 35    * * ( )., ( , ) , k k kg x x d x C d x C (2.10) Thay (2.10) vào (2.9) ta được         2 21 * * * 2 .2 ( ( , ) ( ,C)) 2 k k k k kx x x x d x C d x (2.11) Vì x là nghiệm tối ưu,  * ( , ) ( , ) k d x C d x C và từ (2.11) ta có      2 21 * * 2 2 , k k kx x x x trong đó, từ giả thiết      2 0 k k và theo Bổ đề 2.3 thì dãy  2*kx x là hội tụ. Bổ đề 2.6. Ta có    * lim sup( ( , ) ( , )) 0. k k d x C d x C (2.12) Chứng minh. Từ (2.11), ta có         2 2* * 1 * 2 0 2 ( ( , ) ( , )) 2 . k k k k kd x C d x C x x x x (2.13) Kết hợp hai vế của bất đẳng thức trên, ta được                   2 2* 0 * 1 * 2 00 20 * 2 0 0 2 ( ( , ) ( , )) 2 2 . m m k m k k kk m k k d x C d x C x x x x x x Cho m ta được             2* 0 * 2 0 0 0 2 ( ( , ) ( , )) 2 . k k k k k d x C d x C x x (2.14) Vì      2 0 ,k k ta có       * 0 ( ( , ) ( , )) . k k k d x C d x C (2.15) Thang Long University Libraty Chương 2. BÀI TOÁN ĐỊNH VỊ VÀ ỨNG DỤNG 36 Mặt khác, vì dãy  kx bị chặn và dãy  kg cũng bị chặn . Vì vậy, tồn tại  0L sao cho    k g L , với mọi k . Cho  0 : max ,L L , khi đó, từ định nghĩa của k ta có         0 , max , k k k k Lg (2.16) kết hợp với (2.15) ta thu được             * * 0 1 ( ( , ) ( , )) ( ( , ) ( , )) . k k k k k o k o d x C d x C d x C d x C L (2.17) Vì      0 ,k k ta suy ra    * lim sup( ( , ) ( , )) 0. k k d x C d x C (2.18) Bây giờ, ta sử dụng các kết quả chứng minh ở trên để chứng minh khẳng định (ii) của định lý. Thật ra, theo định nghĩa của lim sup sẽ tồn tại dãy con  jkx của dãy  kx sao cho      * * lim ( ( , ) ( , )) lim sup( ( , ) ( , )) 0 jk k kj d x C d x C d x C d x C . Vì  jkx bị chặn, ta giả sử rằng  lim .j k j x x Khi đó Chương 2. BÀI TOÁN ĐỊNH VỊ VÀ ỨNG DỤNG 37              * * * * ( , ) ( , ) lim ( ( , ) ( , )) lim ( ( , ) ( , )) lim sup( ( , ) ( , )) 0 j j k j k j k k d x C d x C d x C d x C d x C d x C d x C d x C trong đó x cũng là nghiệm tối ưu. Nhắc lại rằng x là nghiệm duy nhất của bài toán (P), nên x x   . Vì dãy   *kx x hội tụ và dãy con  jkx của  kx hội tụ đến x , ta có lim lim .j j jk k k x x x    Vì vậy, dãy kx hội tụ đến x . Nhận xét 2.1. Như ta đã biết, nếu hoặc  0 k g hoặc   1k k x x , khi đó kx là nghiệm đúng. Trong tính toán, cho ta nghiệm xấp xỉ, thuật toán dừng nếu hoặc  k g hoặc    1 max ,1 ,k k kx x x với   0 là sai số cho trước. Nhận xét 2.2. Trong các bài toán thực tế tập C thường rất lớn, ví dụ nếu cho tập C là tập những người sử dụng mạng internet. Tuy nhiên, số đỉnh của tập C lại nhỏ hơn rất nhiều so với số điểm của tập C (được minh họa như hình vẽ dưới đây). Thang Long University Libraty Chương 2. BÀI TOÁN ĐỊNH VỊ VÀ ỨNG DỤNG 38 Trong thuật toán trên ta nhận thấy rằng ta không nhất thiết cần biết các điểm trong tập C mà chỉ cần xác định các đỉnh của bao lồi của tập C. Việc tính các đỉnh của bao lồi của một tập bất kì trong không gian nhiều chiều là một bài toán cơ bản và khó của bộ môn hình học tính toán. Tuy nhiên, trong không gian hai chiều đã có nhiều thuật toán rất hiệu quả để tính các điểm cực biên (các đỉnh) của tập bao lồi cho một tập bất kì. Trong số các thuật toán đó, thuật toán Quickhull là thuật toán rất hữu hiệu nên thường được sử dụng nhiều. Bảng dưới đây là kết quả tính toán áp dụng thuật toán Quickhull trong trường hợp tập C lớn (bảng trích từ 5  ). Chương 2. BÀI TOÁN ĐỊNH VỊ VÀ ỨNG DỤNG 39 Bảng 2.1. Kết quả tính toán theo thuật toán Quickhull |C| (1) |Vc| (2) Tỉ lệ trung bình của (3) Thời gian tìm conv (C) (4) Thời gian tính toán sử dụng (5) 1000 1000 1000 1000 1000 25 39 35 22 17 2.76% < 10 -4 < 10 -4 < 10 -4 < 10 -4 < 10 -4 0.0014 0.0019 0.0016 0.0012 0.0009 10000 10000 10000 10000 10000 48 81 100 27 19 2.75% 0.0010 0.0010 0.0010 < 10 -4 < 10 -4 0.0018 0.0079 0.0117 0.0017 0.0015 100000 100000 100000 100000 100000 94 124 155 23 18 0.414% 0.0151 0.0155 0.0165 0.0010 0.0010 0.0023 0.0027 0.0037 0.0017 0.0017 Thang Long University Libraty KẾT LUẬN 41 KẾT LUẬN Bài toán định vị tuy đã có một lịch sử phát triển lâu dài, nhưng vẫn là đề tài đang được nhiều tác giả quan tâm nghiên cứu. Luận văn đã trình bày những lý thuyết cơ bản nhất cũng như mô hình về bài toán định vị, bao gồm: Một số khái niệm và kết quả của giải tích lồi như: tập lồi, hàm lồi, bài toán quy hoạch lồi. Trong đó, nêu lên những kiến thức cơ bản, nền tảng nhất cho việc xây dựng bài toàn định vị và phương pháp để giải bài toán, đó là các định nghĩa, tính chất về tập lồi, bao lồi, hàm lồi, hàm lồi mạnh, dưới vi phân, toán tử chiếu và bài toán tối ưu. Giới thiệu về bài toán định vị được xét trong luận văn đó là bài toán tìm một điểm (hay một vị trí) trong một miền xác định sao cho khoảng cách lớn nhất từ điểm (vị trí) đó tới các điểm (vị trí) cho trước là nhỏ nhất. Xét một số ví dụ đơn giản về bài toán định vị đã được nghiên cứu và được giải bằng phương pháp hình học. Tuy nhiên, khi xét những bài toán phức tạp hơn mà số điểm cho trước là một số rất lớn thì thấy rằng việc giải bài toán bằng phương pháp hình học sẽ không thực hiện được. Luận văn 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. TÀI LIỆU THAM KHẢO 42 TÀI LIỆU THAM KHẢO Tài liệu tiếng Việt [1] Đỗ Văn Lưu và Phan Huy Khải (1998), Giải tích lồi, Nhà xuất bản Khoa học và Kỹ thuật, Hà Nội. [2] Lê Dũng Mưu (1998), Giáo trình các phương pháp tối ưu, Nhà xuất bản Khoa học và Kỹ thuật, Hà Nội. [3] Trần Vũ Thiệu và Nguyễn Thị Thu Thủy (2011), Tối ưu phi tuyến, Nhà xuất bản Đại học Quốc gia Hà Nội. Tài liệu tiếng Anh [4] Zvi Drezner (1995), Facility Location: A Survey of Applications and Methods, Springer 1995. [5] Nguyễn Kiều Linh and Lê Dũng Mưu. A convex hull algorithm for solving a location problem. RAIRO-Oper. Res. 49 (2015) 589–600. [6] Masamichi Kon and Shigeru Kushimoto, A Single Facility Minisum Location Problem Under The A-Distance, Journal of the Operations Research Society of Japan, Vol. 40, No. l, March 1997. Thang Long University Libraty