Vài suy nghĩ về một bài toán tối ưu trong R2 - Nguyễn Kiều Linh

Nguyễn Kiều Linh Tạp chí KHOA HỌC & CÔNG NGHỆ 99(11): 85 - 89 85 VÀI SUY NGHĨ VỀ MỘT BÀI TOÁN TỐI ƯU TRONG ℝ2 Nguyễn Kiều Linh Trường Đại học Khoa học - ĐH Thái Nguyên TÓM TẮT Bài báo này đề cập tới bài toán tối ưu, thường gặp trong ứng dụng thực tiễn: Tìm trên đường tròn đã cho một điểm sao cho tổng khoảng cách từ đó tới hai điểm cho trước ở ngoài đường tròn là nhỏ nhất? Bài toán đặt ra tuy đơn giản nhưng việc tìm lời giải cho nó bằng giải tích hay hình học thực không dễ. Nó là một mở rộng trực tiếp của bài toán quen biết sau đây, nhưng đơn giản hơn và đã có lời giải đẹp: Tìm trên đường thẳng cho trước một điểm sao cho tổng khoảng cách từ nó tới hai điểm đã cho ở ngoài đường thẳng là nhỏ nhất? Trong bài viết này chúng tôi trình bày hai cách tiếp cận bài toán dựa trên kiến thức tối ưu và các tính chất hình học của ellipse. Từ khóa: Bài toán tối ưu, cách tiếp cận giải tích, cách tiếp cận hình học. NỘI DUNG BÀI TOÁN VÀ Ý NGHĨA THỰC TẾ* Xét bài toán tối ưu sau đây trong mặt phẳng: Bài toán. Tìm trên đường tròn đã cho một điểm sao cho tổng khoảng cách từ đó tới hai điểm cho trước ở ngoài đường tròn là nhỏ nhất? Bài toán này là một mở rộng của bài toán quen biết sau đây: Tìm trên đường thẳng cho trước một điểm sao cho tổng khoảng cách từ nó tới hai điểm đã cho ở ngoài đường thẳng là nhỏ nhất? Có thể giải thích ý nghĩa của bài toán đặt ra theo một số cách như sau: a. Giả sử điện lưới được truyền dọc theo tuyến đường H đến một ngã ba trung tâm, sau khi cấp điện chiếu sáng và sinh hoạt cho vòng tròn trung tâm, nguồn điện cần được chuyển tiếp tới hai tuyến đường tiếp theo sau ngã ba, bắt đầu ở A và B (xem Hình 1). Vấn đề đặt ra là cần tìm một vị trí D trên vòng tròn trung tâm để từ đó đặt hai đường cáp ngầm chạy thẳng tới A và B sao cho tổng khoảng cách từ vị trí được chọn (trên vòng tròn trung tâm) tới A và B là nhỏ nhất (tức là tốn ít công sức, vật liệu và điện năng nhất)? b. Giả sử có một hồ nước hình tròn (tâm I, bán kính r). Có hai cánh đồng mà A và B là nguồn cấp nước cho mỗi cánh đồng. Cần đặt một trạm bơm ở ven hồ và các đường mương (hoặc ống) dẫn nước thẳng từ đó tới A và B sao cho đỡ tốn đường dẫn nhất? * Tel: 0985 059646, Email: nguyenkieulinhk4@gmail.com Bài toán đặt ra tuy đơn giản nhưng hàm chứa nội dung toán học sâu sắc, bởi vì việc tìm lời giải cho nó bằng giải tích hay hình học thực không dễ. Trong bài viết này chúng tôi xin nêu một vài suy nghĩ về bài toán đặt ra, mong được trao đổi với bạn đọc và đồng nghiệp có quan tâm tới bài toán. Hình 1. Minh họa bài toán: Tìm D cấp điện cho A và B TRƯỜNG HỢP DỄ GIẢI Cách giải bài toán tùy thuộc vào vị trí tương đối của đường tròn và hai điểm đã cho (ký hiệu A và B). Sau đây là một số trường hợp dễ giải khác nhau. a. Đoạn thẳng AB tiếp xúc với đường tròn (tiếp điểm nằm trong AB). Khi đó tiếp điểm chính là điểm cần tìm và khoảng cách ngắn nhất bằng độ dài đoạn AB (xem Hình 2a). Lưu ý: nếu đường thẳng qua A, B tiếp xúc với đường tròn ở ngoài đoạn AB thì tiếp điểm không là lời giải (xem cách giải cho trường hợp tổng quát). Nguyễn Kiều Linh Tạp chí KHOA HỌC & CÔNG NGHỆ 99(11): 85 - 89 86 a) tiếp điểm T b) giao điểm P hoặc Q c) điểm R d) điểm K Hình 2. Điểm cần tìm b. Đoạn thẳng AB cắt đường tròn tại hai điểm (nằm trong AB). Khi đó mỗi giao điểm đều là điểm cần tìm và khoảng cách ngắn nhất bằng độ dài đoạn AB (xem Hình 2b). Lưu ý: nếu đường thẳng đi qua A và B cắt đường tròn tại hai điểm (nằm ngoài đoạn AB) thì các giao điểm cũng không chắc chắn là lời giải (xem cách giải cho trường hợp tổng quát). c. Tâm đường tròn nằm ngoài đoạn AB, nhưng ở trên đường thẳng đi qua A và B. Khi đó một trong hai giao điểm của đường thẳng với đường tròn (điểm nằm gần A hoặc B hơn điểm kia) sẽ là điểm cần tìm và khoảng cách ngắn nhất bằng độ dài đoạn AB cộng với khoảng cách từ giao điểm tới A hoặc B (xem Hình 2c). d. Một trường hợp riêng dễ giải nữa như sau: Tâm I của đường tròn nằm trên đường trung trực của đoạn thẳng AB với O là điểm giữa đoạn AB. Giả sử IO cắt đường tròn tại điểm K. Khi đó K chính là điểm cần tìm. Có thể tính tổng khoảng cách từ K tới A và B như sau: Nếu đặt h = IO, b = h - r, c = |AB|/2 và a = 22 cb + thì tổng khoảng cách nhỏ nhất từ K tới A và B bằng 2a (xem Hình 2d). TRƯỜNG HỢP TỔNG QUÁT Nếu không gặp một trong bốn trường hợp kể trên thì ta cần cách tiếp cận khác. Bài toán đặt ra được phát biểu bằng lời mà không dùng đến bất cứ một công thức toán học nào. Đây thực chất là một bài toán tối ưu (tìm cực tiểu hàm khoảng cách theo điểm chạy trên đường tròn). Để có thể vận dụng được công cụ tối ưu, trước hết cần đặt lại (hay mô hình hóa) bài toán bằng ngôn ngữ toán học. Cùng một bài toán có thể có nhiều cách đặt mô hình toán học khác nhau và cách giải đơn giản hay không phụ thuộc rất nhiều vào mức độ thành công của việc mô hình hóa đó. Trong bài viết này chúng tôi mô hình hóa bài toán như sau. Ký hiệu độ dài đoạn AB đã cho là 2c (c > 0). Lấy đường thẳng đi qua A và B làm trục hoành, đường thẳng vuông góc với trục hoành và đi qua trung điểm đoạn thẳng AB làm trục tung. Như vậy gốc tọa độ là điểm giữa đoạn thẳng AB, ký hiệu đó là điểm O với tọa độ O = (0, 0). Giả sử A nằm phía trái O có tọa độ A = (- c, 0) và B nằm phía phải O có tọa độ B = (c, 0). A I B R A I B K r O h - r c a B T A A B P Q Nguyễn Kiều Linh Tạp chí KHOA HỌC & CÔNG NGHỆ 99(11): 85 - 89 87 Giả sử tâm I của đường tròn đã cho có tọa độ (p, q) với p, q ∈ ℝ, và bán kính của đường tròn là r (r > 0). Ký hiệu tọa độ của điểm D nằm trên đường tròn đã cho là D = (x, y) (xem Hình 3). Khi đó tổng khoảng cách từ D tới A và B là f(x, y) = 22 y)cx( ++ + 22 y)cx( +− và ta đi đến bài toán: Tìm cực tiểu hàm f(x, y) với điều kiện (x - p)2 + (y - q)2 = r2. Hình 3. Hệ trục tọa độ Đây là bài toán tối ưu hai biến với một ràng buộc đẳng thức phi tuyến. Có thể thấy f(x, y) là một hàm lồi (trong giải tích lồi ta đã biết hàm khoảng cách từ một điểm trong ℝn tới một tập lồi là một hàm lồi). Hơn nữa, ràng buộc đẳng thức đã cho có thể thay thế bằng ràng buộc bất đẳng thức (x - p)2 + (y - q)2 ≤ r2 mà không làm thay đổi nghiệm của bài toán. Từ đó mô hình bài toán có dạng một bài toán qui hoạch lồi (xem [1]): min {f(x, y) = 22 y)cx( ++ + 22 y)cx( +− : (x - p)2 + (y - q)2 ≤ r2}. Do hàm mục tiêu f liên tục và tập ràng buộc compac, khác rỗng (do r > 0) nên bài toán phải có nghiệm cực tiểu (Định lý Weierstrass). Vấn đề là xét xem điểm cực tiểu có tính chất gì và làm thế nào tìm được điểm cực tiểu đó (bằng giải tích hoặc hình học)? Từ luật phản xạ ánh sáng suy ra điểm cực tiểu D có tính chất: đoạn AD và BD tạo với tiếp tuyến đường tròn tại D hai góc bằng nhau (góc tới = góc phản xạ). Cách tiếp cận giải tích Bằng giải tích ta có thể dùng phương pháp nhân tử Lagrange (xem [1], §8.2, tr. 229 - 240). Cách làm như sau: Đưa vào nhân tử λ và xét hàm Lagrange: L(x, y, λ) = 22 y)cx( ++ + 22 y)cx( +− + λ ((x - p)2 + (y - q)2 - r2). Lấy đạo hàm riêng của L theo x, y, λ và cho bằng 0 ta được hệ ba phương trình của ba ẩn số (x, y và λ): Rất tiếc là ta không thể giải trực tiếp hệ phương trình này để tìm ra các điểm dừng, từ đó xác định điểm cực tiểu. Ta chỉ có thể giải gần đúng bằng số hệ này. Cách tiếp cận hình học Ta nhắc lại định nghĩa và các tính chất của ellipse trong mặt phẳng. Theo định nghĩa, ellipse là quĩ tích tất cả những điểm có tổng khoảng cách từ nó tới hai điểm cố định đã cho (chẳng hạn, A và B) bằng hằng số ℓ ≥ 0 cho trước. Điểm A và B gọi là các tiêu điểm, độ dài đoạn thẳng AB = 2c gọi là tiêu cự của ellipse. Mỗi ellipse có một trục lớn, độ dài ký hiệu là 2a và một trục nhỏ, độ dài ký hiệu là 2b (với a ≥ b ≥ 0), vuông góc với nhau tại trung điểm đoạn thẳng AB. Ta có mối liên hệ: a2 = b2 + c2 và ℓ = 2a (xem Hình 4). Nếu vẽ hệ trục tọa độ vuông góc với gốc tọa độ O tại điểm giữa hai tiêu điểm của ellipse và trục hoành song song với trục lớn thì ellipse sẽ được biểu diễn bởi phương trình: 2 2 a x + 2 2 b y = 1 Như vậy, những điểm nằm phía trong đường ellipse có tổng khoảng cách tới A và B nhỏ hơn ℓ; những điểm nằm phía ngoài đường p A B O D I - c x y q r Nguyễn Kiều Linh Tạp chí KHOA HỌC & CÔNG NGHỆ 99(11): 85 - 89 88 ellipse có tổng khoảng cách tới A và B lớn hơn ℓ. Một tính chất đáng chú ý nữa là ellipse tuân theo luật phản xạ ánh sáng: Tiếp tuyến với ellipse tại điểm bất kỳ D trên ellipse tạo với AD và BD hai góc bằng nhau (góc tới bằng góc phản xạ, nghĩa là tia sáng đi từ A tới D sẽ phản chiếu tới B và ngược lại). Khi A trùng với B (c = 0) thì ellipse trở thành đường tròn (tâm O, bán kính a = b). Hệ số e = c/a gọi là hệ số độ lệch tâm hay tâm sai của ellipse (0 ≤ e ≤ 1). Hình 4. Ellipse với a = 5, b = 4 và c = 3 (ℓ = 10) Để mô tả họ ellipse nhận A và B cố định làm tiêu điểm (|AB| = 2c) và có bán trục lớn a = αc (α ≥ 1) ta phải có: b2 = a2 - c2 = α2c2 - c2 = (α2 -1)c2 (b là bán trục bé). Khi đó phương trình biểu diễn họ ellipse này có dạng (phụ thuộc tham số α): 22 2 c x α + 22 2 c)1( y −α = 1 (α ≥ 1). Khi α = 1 thì a = c và ellipse suy thoái thành đoạn thẳng AB (b = 0). Khi α càng lớn thì diện tích hình ellipse càng lớn (diện tích hình ellipse bằng S = piab, nhưng chiều dài đường ellipse rất khó tính!). Cách tiếp cận bằng hình học dựa trên ý tưởng: Điểm cực tiểu cần tìm D có tính chất: đoạn AD và BD tạo với tiếp tuyến đường tròn tại D hai góc bằng nhau (góc tới bằng góc phản xạ). Như trên đã thấy, bất cứ điểm nào trên ellipse nhận A và B làm tiêu điểm đều có tính chất đòi hỏi. Như vậy, tiếp điểm của đường tròn tâm I bán kính r với một đường ellipse trong họ trên sẽ là điểm cần tìm (xem Hình 5). Hình 5. Cách tiếp cận hình học Vì thế, bài toán đặt ra có thể diễn đạt thành: Tìm ellipse nhận A và B làm tiêu điểm sao cho nó tiếp xúc với đường tròn tâm I bán kính r tại một điểm. Tiếp điểm này và tiếp tuyến chung của ellipse với đường tròn sẽ thỏa mãn yêu cầu đề ra. Ta có thể dựng ellipse này bằng hình học như sau. Lấy một đoạn dây không đàn hồi có độ dài lớn hơn 2c một chút. Gắn cố định một đầu dây ở A, đầu kia ở B. Dựng ellipse gồm các điểm có tổng khoảng cách từ nó tới A và B bằng độ dài đoạn dây đã chọn (đặt đầu bút chì tựa vào một điểm bất kỳ trên dây và di chuyển đầu bút chì theo dây sao cho đoạn dây luôn căng và quay đủ một góc 3600). Sau đó kéo dài độ dài đoạn dây (nếu ellipse không cắt đường tròn) hoặc rút ngắn độ dài dây (nếu ellipse cắt đường tròn tại hai điểm) sao cho ellipse nhận được theo cách này tiếp xúc với đường tròn đã cho (tâm I, bán kính r). Tiếp điểm nhận được sẽ là điểm cần tìm (điểm trên đường tròn có tổng khoảng cách tới A và B nhỏ nhất). Có thể thấy ellipse cuối cùng thu được sẽ có diện tích lớn nhất trong số các ellipse nhận A, B làm tiêu điểm, không chứa đường tròn và không có quá hai điểm chung với đường tròn. Nhận xét. Có thể mở rộng bài toán cho trường hợp A và / hoặc B nằm trong (hoặc trên) đường tròn. Đường tròn cũng có thể thay bằng các đường cong bậc hai khác (ellipse, parabol, hyperbon ... ). Bài toán còn có thể mở rộng trong không gian ba chiều, tức là có thể thay đường tròn bởi mặt cầu, ellipse bởi ellipsoid. Nguyễn Kiều Linh Tạp chí KHOA HỌC & CÔNG NGHỆ 99(11): 85 - 89 89 TÀI LIỆU THAM KHẢO [1]. T. V. Thiệu và N. T. T. Thủy. Giáo trình tối ưu phi tuyến. Nxb Đại học Quốc gia Hà Nội, 2011. [2]. M.S. Bazara et all. Nonlinear Programming. Theory and Algorithms. 3rd Edition. A John Willey & Sons, Inc., Publication, 2006. [3]. Properties of Ellipses (Internet). SUMMARY SOME IDEAS ABOUT AN OPTIMIZATION PROBLEM IN PLANE Nguyen Kieu Linh* College of Sciences - TNU This paper deals with the following optimization problem usually encountered in many applications and containing interesting mathematical contents: Find on a given circle one point such that the sum of distance from it to two specified points out of the circle is smallest? The problem seems to be rather simple, but finding by analysis or geometry a solution for it is not easy. The problem under consideration is a direct extension of the well-known following problem, but simpler and having a nice solution: Find on a given line in plane one point such that the sum of distance from it to two given points out of the line is smallest? In this paper we present some approach to the problem based on optimization knowledge and geometry properties of ellipses. Key word: Optimization problem, analysis approach, geometry approach. Ngày nhận bài: 08/11/2012, ngày phản biện: 23/11/2012, ngày duyệt đăng:10/12/2012 * Tel: 0985 059646, Email: nguyenkieulinhk4@gmail.com