ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THÀNH CƠNG NGUN LÝ LAGRANGE TRONG CÁC BÀI TỐN CỰC TRỊ LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2014 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THÀNH CÔNG NGUYÊN LÝ LAGRANGE TRONG CÁC BÀI TỐN CỰC TRỊ Chun ngành: Tốn ứng dụng Mã số: 60.46.01.12 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC GS-TS Trần Vũ Thiệu Thái nguyên - 2014 LỜI NÓI ĐẦU Trong lý thuyết ứng dụng ta thường gặp tốn cực trị (tìm cực đại cực tiểu) Khi giải toán cực trị người ta thường tìm cách đưa toán đơn giản hơn: với số biến số ràng buộc hơn, chí khơng có ràng buộc tốt Ý tưởng thể rõ nét phương pháp nhân tử Lagrange số phương pháp tối ưu khác Nguyên lý Lagrange tạo sở lý thuyết cho phương pháp nhân tử Lagrange giải tốn cực trị có ràng buộc, đặc biệt toán với ràng buộc đẳng thức Mục tiêu luận văn tìm hiểu nguyên lý Lagrange lý thuyết toán cực trị, chủ yếu xét không gian hữu hạn chiều ℝn ứng dụng nguyên lý vào việc tìm nghiệm (cực tiểu cực đại) tốn cực trị có hay khơng có ràng buộc, đặc biệt tốn quen thuộc số học hình học, nhằm nâng cao kiến thức khả giảng dạy nghiên cứu tốn tối ưu nói riêng tốn ứng dụng nói chung Nội dung luận văn viết ba chương Chương “Bài tốn cực trị” trình bày khái qt tốn cực trị có khơng có ràng buộc, nhắc lại khái niệm nghiệm cực tiểu (cực đại) địa phương (toàn cục), tồn nghiệm tốn, điều kiện địi hỏi nghiệm toán cần thỏa mãn (điều kiện cần điều kiện đủ), dựa vào tìm nghiệm tối ưu tốn Chương “Ngun lý Lagrange” trình bày kết lý thuyết điều kiện cần tối ưu (cấp 1, cấp 2) điều kiện đủ tối ưu (cấp 2) cho nghiệm cực tiểu địa phương toán qui hoạch phi tuyến với ràng buộc đẳng thức trình bày phương pháp nhân tử Lagrange đưa tốn có ràng buộc đẳng thức tốn (không ràng buộc) hàm Lagrange (bằng hàm mục tiêu ban đầu cộng với hàm ràng buộc, sau nhân với hệ số gọi nhân tử Lagrange) Chương “Áp dụng giải toán cực trị” trình bày ứng dụng nguyên lý Lagrange vào việc tìm nghiệm cực tiểu hay cực đại số toán cực trị, chủ yếu toán với ràng buộc đẳng thức Đặc biệt xét tốn quen thuộc số học hình học, toán chứng minh bất đẳng thức, toán khoảng cách, toán Steiner Đây tốn có ý nghĩa thực tế, nhà toán học tiếng đề nêu cách giải Qua giới thiệu số ứng dụng lý thuyết tối ưu thực tiễn Do thời gian kiến thức hạn chế nên chắn luận văn cịn có thiếu sót định, kính mong q thầy bạn đóng góp ý kiến để tác giả tiếp tục hoàn thiện luận văn sau Nhân dịp tác giả luận văn xin bày tỏ lòng biết ơn sâu sắc tới GS-TS Trần Vũ Thiệu, Viện Toán học - Viện Hàn Lâm Khoa học Cơng nghệ Việt Nam tận tình bảo, giúp đỡ tơi q trình làm luận văn Bên cạnh tơi xin bày tỏ lịng biết ơn đến ban giám hiệu trường Đại học Khoa học Thái Nguyên, Khoa Toán - Tin, Trung tâm học liệu Đại học Thái Nguyên tận tình động viên, tạo điều kiện giúp đỡ thời gian học tập làm luận văn Tơi xin bày tỏ lịng biết ơn sâu sắc đến Viện Toán học - Viện Hàn Lâm Khoa học Công nghệ Việt Nam tạo điều kiện thuận lợi cho thời gian học tập nghiên cứu Tôi xin gửi lời cảm ơn chân thành đến người thân gia đình, bạn bè đồng nghiệp quan tâm, động viên giúp đỡ thời gian qua Thái Nguyên, ngày 09 tháng năm 2014 Học viên Nguyễn Thành Cơng Chương BÀI TỐN CỰC TRỊ Chương nhắc lại số khái niệm tốn cực trị có khơng có ràng buộc, khái niệm nghiệm cực tiểu (cực đại) địa phương (toàn cục), tồn nghiệm toán, điều kiện địi hỏi nghiệm tốn cần thỏa mãn (điều kiện tối ưu cần đủ) Nội dung chương tham khảo chủ yếu từ tài liệu [1], [2], [4] [6] 1.1 CÁC KHÁI NIỆM CƠ BẢN 1.1.1 Ví dụ tốn cực trị Các tốn cực trị biết từ bậc phổ thơng Để làm ví dụ, ta xét hai tốn quen thuộc hình học phẳng Bài tốn (Bài tốn Heron) Tìm đường thẳng cho điểm cho tổng khoảng cách từ điểm tới hai điểm cho trước nhỏ nhất? (Hình 1.1) Bài tốn Vẽ nội tiếp hình trịn hình chữ nhật có diện tích lớn nhất? (Hình 1.2) y y B (d, b) (x, y) r A (0, a) 0 1 2 Cˆ ( xˆ , 0) C (x, 0) x x A'(0,- a) Hình 1.1 Hình 1.2 Bài tốn tìm cực tiểu (minimum), tốn tìm cực đại (maximum) Cực tiểu cực đại gọi chung cực trị (extremum) Đôi người ta dùng từ tối ưu (optimization), nghĩa tốt hay hoàn hảo Như vậy, toán toán cực trị hay toán tối ưu Lý thuyết tốn tìm giá trị nhỏ (lớn nhất) hàm gọi lý thuyết toán cực trị hay lý thuyết tối ưu Các toán mô tả lời, không dùng công thức Các toán cực trị nảy sinh từ lĩnh vực khoa học hay từ thực tiễn thường vậy: chúng mô tả lời theo thuật ngữ có nội dung lĩnh vực nảy sinh tốn Để áp dụng lý thuyết tối ưu cần chuyển tốn sang ngơn ngữ tốn học Cách làm gọi hình thức hóa tốn Cùng tốn hình thức hóa theo nhiều cách khác cách giải có đơn giản hiệu qủa hay khơng thường phụ thuộc nhiều vào mức độ thành công hình thức hóa Ta hình thức hóa toán sau Bài toán 1: Vẽ trục Ox dọc theo đường thẳng cho trục Oy vng góc qua điểm A (xem Hình 1.1) Giả sử tọa độ hai điểm cho là: A = (0, a) B = (d, b); tọa độ điểm cần tìm C = (x, 0) Khoảng cách từ A tới C từ B tới C |AC| = a  x |BC| = b  (d  x ) Từ đó, ta đến tốn: Tìm cực tiểu hàm biến f(x) = a2  x2 + b  (d  x ) với x ∈ ℝ Bài toán 2: Giả sử đường trịn mơ tả phương trình x2 + y2 = r2, Vẽ trục Ox Oy song song với cạnh hình chữ nhật ký hiệu (x, y) tọa độ đỉnh hình chữ nhật nằm góc phần tư thứ (xem Hình 1.2) Khi diện tích hình chữ nhật 4xy Ta nhận tốn: Tìm cực đại hàm hai biến f(x, y) = 4xy với điều kiện g1(x, y) = x2 + y2 - r2 = 0, g2(x, y) = x ≥ 0, g3(x, y) = y ≥ Có thể thấy điều kiện x ≥ 0, y ≥ thừa tốn tìm cực đại 4xy với x + y2 = r2 tương đương toán với điều kiện bất đẳng thức x2 + y2 ≤ r2 Bất kỳ tốn hình thức hóa xây dựng theo cách tương tự, bao gồm yếu tố sau đây: phiếm hàm f : X → ℝ ∪ {+ ∞, - ∞} (X miền xác định phiếm hàm f) ràng buộc, tức tập D ⊂ X Ta giải thích số ký hiệu thuật ngữ thường gặp lý thuyết tối ưu: R đường thẳng thực mở rộng, tức tập số thực cộng thêm hai giá trị + ∞ - ∞; cách viết F : X → Y có nghĩa ánh xạ F có miền xác định khơng gian X với phần tử x ∈ X, phần tử F(x) nằm không gian Y; ta dùng từ phiếm hàm để ánh xạ vào đường thẳng thực mở rộng R Như vậy, hình thức hóa tốn cực trị có nghĩa mơ tả xác yếu tố f, X D Với toán hình thức hóa ta dùng cách viết f(x) → inf (sup), x ∈ D (P) để tốn tìm cực tiểu (cực đại) Khi cần xét hai toán cực tiểu cực đại, ta viết f(x) → extr, x ∈ D Như vậy, cách viết hình thức cho toán sau Bài toán (X = D = ℝ - đường thẳng thực): f(x) = a2  x2 + b  (d  x ) → inf (P1) Bài toán (X = ℝ2 - mặt phẳng hai chiều): f(x, y) = 4xy → sup, x2 + y2 = r2, x ≥ 0, y ≥ (P2) Bài toán (P2), nói trên, có cách hình thức hóa khác: f(x, y) = 4xy → sup, x2 + y2 = r2 ( P2 ) Bài tốn (P1) khơng có ràng buộc, tốn (P2) có ràng buộc D = {(x, y) ∈ ℝ2 : x2 + y2 = r2, x ≥ 0, y ≥ 0} cho dạng đẳng thức bất đẳng thức, cịn tốn ( P2 ) có ràng buộc D = {(x, y) ∈ ℝ2 : x2 + y2 = r2} cho đạng đẳng thức 1.1.2 Một số thuật ngữ Như vậy, toán tối ưu f(x) → inf (sup) với x  D (P) tốn tìm véctơ x*  D cho f(x*)  f(x) (f(x*) ≥ f(x)) với x  D, D ⊂ ℝn tập khác rỗng f : D → ℝ hàm số thực tùy ý Định nghĩa 1.1 Hàm f gọi hàm mục tiêu, tập D gọi tập ràng buộc hay miền chấp nhận Một véctơ (điểm) x  D gọi phương án (lời giải, nghiệm) chấp nhận Véctơ x*  D cho f(x*)  f(x) (hay f(x*) ≥ f(x)) với x  D gọi phương án (lời giải, nghiệm) tối ưu toán Trường hợp D = ℝn ta có tốn tối ưu khơng ràng buộc, thường viết {f(x) : x  ℝn} hay minn f(x) xR Khi D ⊂ ℝn ta có tốn tối ưu có ràng buộc tập D thường có dạng D = {x  ℝn : gi(x)  0, i = 1, , m, hj(x) = 0, j = 1, , p} với gi, hj : ℝ n  ℝ hàm số cho trước, gọi hàm ràng buộc Khi đó, tốn (P) viết dạng tường minh: {f(x) : gi(x)  0, i = 1, , m, hj(x) = 0, j = 1, , p} Các hệ thức gi(x)  gọi ràng buộc bất đẳng thức, hệ thức hj(x) = gọi ràng buộc đẳng thức Ràng buộc bất đẳng thức dạng xj  (- xj  0) gọi ràng buộc không âm hay ràng buộc dấu Nhận xét min{f(x) : x  D} = - max{- f(x) : x  D}, tốn tìm cực tiểu đưa tốn tìm cực đại ngược lại Định nghĩa 1.2 Ta nói điểm xˆ ∈ D nghiệm cực tiểu địa phương (P) viết xˆ ∈ loc P có số  > cho f( xˆ ) ≤ f(x) với x ∈ D ||x - xˆ || <  Nếu f ( xˆ ) < f(x) với x  D, x  xˆ ||x - xˆ || <  xˆ gọi nghiệm cực tiểu địa phương chặt (P) Định nghĩa 1.3 Điểm xˆ  D gọi nghiệm cực tiểu toàn cục hay cực tiểu tuyệt đối (P) f ( xˆ )  f(x) với x  D ta viết xˆ ∈ abs P Nếu f( xˆ ) < f(x) với x  D, x  xˆ xˆ gọi nghiệm cực tiểu toàn cục chặt (P) Các khái niệm nghiệm cực đại địa phương nghiệm cực đại toàn cục định nghĩa tương tự ta viết xˆ ∈ loc max P hay xˆ ∈ abs max P Đối với hàm tùy ý f tập D, ký hiệu tập tất điểm cực tiểu (cực đại) toàn cục f D Argmin xD f(x) (Argmax x  D f(x)) Khi xét toán tối ưu ta mong muốn tìm nghiệm cực trị (cực tiểu, cực đại) tồn cục Tuy nhiên, nghiệm không tồn Chẳng hạn, hàm biến f(x) = x hay f(x) = ex khơng có nghiệm cực tiểu toàn cục tập số thực ℝ hàm f(x) = x giảm vô hạn tới -  x dần tới - , hàm f(x) = ex nhận giá trị dương giảm tới x dần tới -  Tập {f(x) : x  D} gọi miền giá trị hàm f Có hai khả năng: a) Tập {f(x) : x  D} bị chặn dưới, nghĩa có số m cho m  f(x) với x  D Trong trường hợp cận lớn {f(x) : x  D} số thực ký hiệu inf f(x) Chẳng hạn, inf ex = xD xR b) Tập {f(x) : x  D} không bị chặn (tức tập chứa số thực nhỏ tùy ý) Trong trường hợp ta viết inf f(x) = -  xD ˆ = ( xˆ , 0) Trong Bài toán cực tiểu tuyệt đối xˆ xác định điểm cần tìm C đặc trưng kiện hình học biết góc nhọn tạo nên cạnh ˆ C ˆ B với trục Ox phải (góc tới góc phản xạ) giá trị tối AC ưu toán fmin = (a  b)  d ( Cˆ giao điểm A'B với trục Ox, xem Hình 1.1) Trong Bài tốn hình chữ nhật cần tìm hình vng cạnh 2r/ , tương ứng với nghiệm xˆ = yˆ = r/ fmax = 2r2 (xem Hình 1.2) Lý thuyết toán cực trị đưa qui tắc tìm nghiệm tốn, thường tách tập điểm gọi điểm tới hạn (thường bao gồm điểm đạo hàm theo biến 0, điểm khơng có đạo hàm điểm biên miền ràng buộc ) Tập rộng tập điểm cực trị địa phương hay tồn cục Sau tìm điểm tới hạn, sử dụng điều kiện tối ưu cần đủ, tìm điểm cực tiểu (hay cực đại) Để minh họa, ta xét ví dụ tìm điểm tới hạn, điểm cực trị địa phương cực trị tồn cục tốn sau Bài tốn (Hình 1.3) Tìm cực trị hàm biến f(x) = x3(x2 - 1) → extr, - ≤ x ≤ (P3) Cực trị tồn cục tốn đạt hai đầu mút đoạn [- 1, 2] điểm Nếu cực trị đạt điểm đạo hàm f phải 0, tức f '(x) = ⇔ 5x4 - 3x2 = ⇔ x ∈ {- / , 0, y x1 x2 / } f(x) x3 x4 x5 - - 3/5 x 3/5 Hình 1.3 Các điểm tới hạn Như có điểm tới hạn: x = - 1, x2 = - / , x3 = 0, x4 = / , x5 = 2, x2, x 3, x4 điểm dừng Từ đồ thị hàm f (Hình 1.3) ta thấy x1, x4 ∈ loc P3; x2, x ∈ loc max P3; x ∈ abs P3; x ∈ abs max P3 Từ fmin = - 0,6 /25 ≈ - 0,1859 fmax = 24 1.2 SỰ TỒN TẠI NGHIỆM TỐI ƯU Câu hỏi tự nhiên đặt tốn xét có hay khơng có nghiệm tối ưu (cực tiểu hay cực đại toàn cục)? Trả lời cho câu hỏi Định lý 1.1 (Định lý Weierstrass) Một hàm liên tục f tập D compac, khác rỗng đạt cực tiểu cực đại D Do hàm V liên tục miền biến thiên h đoạn thẳng đóng hữu hạn nên theo định lý Weierstrass tồn nghiệm hˆ toán Rõ ràng hˆ ≠ hˆ ≠ a /  , V(0) = V( a /  ) = a a /(6  ) < V( a / 2 ) = a a /(3  ), nghĩa a = 2 hˆ Từ hˆ = r Kết luận: chỏm cầu cần tìm nửa hình cầu 3.2 BÀI TỐN VỀ BẤT ĐẲNG THỨC Bài toán 3.2.1 Chứng minh bất đẳng thức trung bình lũy thừa  n   xi  i1  n   1/ p p        n   xi ≤  i1  n   1/ q q       , - ∞ < p ≤ q ≤ + ∞, p ≠ q, q ≠ Lời giải Hình thức hóa: Xét tốn tối ưu n  xi p → sup i 1 n với điều kiện  xi q = aq (1 < p < q, a > 0) i 1 Miền chấp nhận toán compac, hàm mục tiêu liên tục nên tồn nghiệm xˆ tốn Hàm Lagrange có dạng n L(x, ) =  xi i 1 p n q  +   x i  a q   i1  Điều kiện cần tối ưu: Đạo hàm riêng L theo biến xi  0: L( x,  ) = ⇔ p| xˆ i |p - sign xˆ i + q| xˆ i |q - sign xˆ i = 0, ≤ i ≤ n x i L( x, ) =0⇔  n  xˆ i q = aq i 1 Từ điều kiện tối ưu suy ra: xˆ i = | xˆ i | = (q/p)1/(p - q) với i 36 Cực đại hàm mục tiêu đạt điểm tới hạn Giả sử điểm tới hạn khác 0, có k tọa độ Khi tọa độ | xˆ i | = ak-1/q Smax(a) = aP max k1 - p/q = apn1 - p/q 1 k n Từ nghiệm toán tối ưu ta suy bất đẳng thức cần chứng minh: n A) p > Giả sử  xi q = aq Khi i 1 1/ p  n p    xi / n   i1  -1/p ≤n (Smax(a)) =n p  xi  i1 = n 1/p 1/ p n -1/p  -1/p    1/p - 1/q an ≤  n q  =   xi / n   i1  1/ q B) p = Cho qua giới hạn bất đẳng thức p → ta nhận 1/ q  n   n q   xi / n ≤  xi / n   i1   i1  C) < p < Đặt yi = |xi|p Khi 1/ p  n p   xi / n   i1   n  =   yi / n   i1  1/ p ≤ 1/ q p/q  n  q/p  ≤    yi /n    i1    1/ q  n q  =  xi / n   i1  D) p < q < ⇒ < - q < - p ⇒ (A), B), C)) 1/ p  n p   xi / n   i1  p  n  =   x i1 / n   i1  q  n  ≤   x i1 / n   i1   ( 1 / p ) ≤  ( 1 / q )  n q  =   xi / n   i1  E) Cho p → ta nhận 1/ p  n p  lim   x i / n  p0  i 1  37  n  i 1 1/ n  =   x1   1/ q Từ đó, p < < q 1/ p  n p   xi / n   i1  1/ n  n  ≤   x1   i 1   n q  ≤   xi / n   i1  1/ q Bài toán 3.2.2 Chứng minh bất đẳng thức trung bình cộng trung bình nhân 1/ n  n    x1   i 1   n    xi  ≤  i1  với xi ≥ 0, i = 1, , n n Đáp án Bài toán trường hợp riêng toán 3.2.1 (xem E) Bài tốn 3.2.3 Chứng minh bất đẳng thức Hưlder: 1/ p n  n p x a ≤  i i  xi  i 1  i1   n q    i1  1/ q , 1 + = 1, ≤ p p q Lời giải Hình thức hóa: Xét toán tối ưu n f(x) = a ixi → sup i 1 n với điều kiện  xi p = bp (p > 1, ∈ ℝ, b > 0) i 1 Bài tốn có nghiệm tối ưu hàm mục tiêu f(x) liên tục miền chấp nhận compac khác rỗng Hàm Lagrange có dạng n L(x, ) = n a ixi + (  x i i 1 p - bp) i 1 Điều kiện cần tối ưu: Đạo hàm riêng L theo biến xi  L( x,  ) = ⇔ + |xi|p - 1sign xi = 0, i = 1, , n x i L( x, ) =0⇔  38 n  xi i 1 p = bp Tìm điểm dừng: Từ điều kiện tối ưu suy xi = |ai|q - 1sign ai, i = 1, , n (1/p + 1/q = 1) n Do p  xi n p = b nên  = b  a i 1 / p q Từ điểm dừng i 1 i 1 1 / p n xi = b  a i q |ai|q - 1sign ai, i = 1, , n i 1 Tìm nghiệm tốn: Điểm dừng nên điểm cực đại 1 / q n Smax(b) = b  a i q i 1 Vì 1/ p 1/ p 1/ q  n    n p  n q   x i a i ≤ Smax    a i p   =   x i    a i  i 1   i1     i1   i1 n Trường hợp p = p = + ∞ nhận cách cho qua giới hạn Bài toán 3.2.4 Chứng minh bất đẳng thức Minkowski  n p   x i  yi   i1  1/ p 1/ p  n p ≤  xi   i1  1/ p  n p +   yi   i1  , p ≥ Đáp án Lời giải suy từ nghiệm toán tối ưu n p   x i  y i  → sup  i1  với điều kiện n  n p p p  p   x i  = a ,   y i  = b , (p > 1, a > 0, b > 0)  i1   i1  3.3 BÀI TỐN VỀ KHOẢNG CÁCH Bài tốn 3.3.1 Tìm khoảng cách từ điểm tới siêu phẳng cho trước không gian ℝn 39 Lời giải Cho điểm x0 = ( x10 , , x 0n ) ∈ ℝn giả sử siêu phẳng có dạng a1x1 + a2x2 + + anx n = , với a1, a2, , an (không 0)  số cho Xét toán tối ưu {f(x) = (x1 - x10 )2 + + (xn - x 0n )2 : a1x1 + a2x + + anxn -  = 0} Đây qui hoạch lồi f(x) = ||x - x0||2 hàm lồi chặt (|||| ký hiệu chuẩn Euclid) với ràng buộc đẳng thức tuyến tính Ký hiệu H = {x  ℝn : a1x1 + a2x2 + + anx n = } tập lồi đóng (siêu phẳng ℝn) Nghiệm cực tiểu tốn (nếu có) (do f lồi chặt) điểm dừng Hàm Lagrange có dạng L = (x - x10 )2 + + (xn - x 0n )2 + (a1x1 + a2x2 + + anx n - ) Điều kiện tối ưu: (i) 2(xj - x 0j ) + aj = 0, j = 1, 2, , n (ii) aTx = a1x1 + a2x2 + + anxn =  Tìm điểm dừng: Nhân hai vế (i) với aj cộng lại theo j để ý tới (ii) ta 2aT(x - x 0) + (a 12 + a 22 + + a 2n ) =  2( - aTx 0) + ||a||2 =   = - 2( - aTx0)/||a||2  x j = x 0j - (/2)aj = x 0j + ( - aTx0)aj/||a||2 Nghiệm hệ xˆ j = x 0j + ( - aTx 0)aj/||a||2, j = 1, 2, , n với  = - 2( - aTx0)/||a||2 Vì giá trị cực tiểu fmin = ( - aTx0)2/||a||2 Chú ý ta tính bình phương khoảng cách ngắn từ điểm x0 tới siêu phẳng aTx =  Kết quả: khoảng cách ngắn từ x0 tới siêu phẳng cho d(x0, H) = | - aTx0|/||a|| 40 Chẳng hạn, với n = 2, x0 = (- 1, 2)T, a = (3, 4)T,  = 30 aTx0 = 5, ||a|| = Từ ( - aTx0) = 25,  = - 2, dmin = Điểm siêu phẳng gần x xˆ = (2, 6)T Bài tốn 3.3.2 Tìm khoảng cách từ điểm y = (y1, y2, y3) ∈ ℝ3 đến nón kem x3 ≥ x12  x 22 x3 •y x3 • xˆ • xˆ •y x2 x2 x1 x1 Hình 3.3 Bài tốn 3.3.2 Hình 3.4 Bài tốn 3.3.3 y12  y 22 ≤ ⇒ xˆ = (0, 0, 0)T nghiệm cực tiểu; Đáp án  ≡ y3+ T   y1 y    > ⇒ xˆ =  nghiệm cực tiểu , , 2  y2  y2  2 y1  y 2       Bài tốn 3.3.3 Tìm khoảng cách từ điểm y = (y1, y2, y3) ∈ ℝ3 ngồi ellipsoid có phương trình x12 x 22 x 32 + + ≤1 a12 a 22 a 32 đến ellipsoid Đáp án xˆ i = yiai/( a i2 + ), i = 1, 2, 3,  nghiệm dương phương trình y12 a 12 a    a y 22 a 22 2    a y 32 a 32   = Bài tốn 3.3.4 Tìm cực tiểu hàm tuyến tính f(x) = c1x1 + + cnxn mặt cầu x 12 + + x 2n = r2 với r c1, , cn số cho trước tuỳ ý 41 Lời giải Do f(x), g(x) = x 12 + + x 2n - r2 hàm lồi nên toán tối ưu lồi, điểm cực tiểu tìm số nghiệm thoả mãn điều kiện cần tối ưu Trong toán f(x) = (c1, , cn)T, g(x) = (2x1, , 2xn)T với x Hàm Lagrange có dạng L(x,  ) = c1x1 + + cnx n +  ( x12 + + x 2n - r2) Điều kiện cần tối ưu: L ( x ,  ) = ⇔ cj + 2xj = 0, j = 1, 2, , n, x j L( x,  ) = ⇔ x 12 + x 22 + + x 2n = r2  Tìm điểm dừng: Nếu c = (c1, , cn)T = điểm chấp nhận điểm cực tiểu Vì ta giả thiết c  Từ điều kiện tối ưu suy   Từ x j = - cj/(2), j = 1, 2, , n n n  c 2j j1 42  x 2j = r  j1 n = r2   c 2j = 42r2 j1 n n  c 2j  c 2j j1 ⇔ 2 = 4r ⇔=± j1 2r > Tìm nghiệm tối ưu: Có thể thấy nghiệm cực tiểu ứng với  > Vậy xj =  2rc j  2    c 2j  j1  n =  rc j n với j = 1, 2, , n  c 2j j1 Nghiệm cực tiểu toàn cục 42 T       rc1  rc2  rc n  xˆ =  , , ,  n n n   c 2j  c 2j  c 2j   j1 j1 j1   Bài tốn 3.3.5 Tìm cực tiểu phiếm hàm tuyến tính khơng gian ℓ2 biên ellipsoid với độ dài bán trục đơn điệu giảm dần tới Lời giải Hình thức hóa tốn: Xét tốn tối ưu ℓ2:  a, x = a kxk → inf k 1 với điều kiện x 2k  = (a ∈ ℓ2, a ≠ 0, bk ↓ k → + ∞) k 1 b k  Hàm Lagrange có dạng   x 2k     1 +   akxk  k 1 b  k 1  k   L(x, ) = Điều kiện cần tối ưu: ∇xL(x, ) = ⇔ ak + 2xk/ b 2k = 0, k = 1, 2, x 2k  = k 1 b k  ∇L(x, ) = ⇔ Tìm điểm dừng: Từ điều kiện tối ưu suy  ≠ (do a ≠ 0) xk = - akb 2k /(2), k = 1, 2, Do x thuộc biên ellipsoid nên   a 2k b 2k = 42 ⇒ || = k 1 Điểm xˆ với tọa độ 43   a 2k b 2k k 1 xˆ k =  a k b 2k  , k = 1, 2,  a 2k b 2k k 1 đạt cực tiểu toàn cục phiếm hàm tuyến tính khơng gian ℓ2 biên ellipsoid với bán trục đơn điệu giảm dần tới 3.4 BÀI TỐN STEINER Các tốn nêu mục thường gặp nhiều ứng dụng Chẳng hạn, chọn địa điểm xây dựng nhà máy, đặt sở dịch vụ (cửa hàng, trạm cung cấp vật tư, trạm sửa chữa, trạm thu gom sản phẩm) cho vùng dân cư Bài tốn 3.4.1 (Bài tốn Steiner) Tìm mặt phẳng điểm cho tổng khoảng cách từ điểm tới ba điểm khác cho nhỏ nhất? Lời giải Hình thức hoa tốn: Ký hiệu ba điểm cho xi = ( x 1i , x i2 ), i = 1, 2, giả sử điểm cần tìm x = (x1, x2) ∈ ℝ2 Bài toán đặt f(x) = ||x - x 1|| + ||x - x2|| + ||x - x3|| → inf, x ∈ ℝ2 (|| • || chuẩn Euclid) Đây toán tối ưu lồi khơng có ràng buộc Do hàm mục tiêu f liên tục toàn ℝ2 (do f(x) → + ∞ ||x|| → + ∞) nên tồn nghiệm cực tiểu xˆ toán xˆ = ( xˆ1 , xˆ ) Điều kiện cần tối ưu: ∈ ∂f( xˆ ) Tìm điểm dừng: Có hai khả xảy a) xˆ ≠ xi, i = 1, 2, b) xˆ ∈ {x1, x2, x 3} Trong trường hợp a) ∂f( xˆ ) = xˆ  x1 xˆ  x xˆ  x + + = 0, xˆ  x1 xˆ  x xˆ  x nghĩa ba véctơ đơn vị từ xˆ tới x1, x2, x3 có tổng véctơ Từ suy từ điểm xˆ nhìn đoạn thẳng [x 1, x2],[x1, x3],[x2, x3] góc 120o Nếu 44 ba góc tam giác nhỏ 120o dễ dàng dựng điểm xˆ Điểm gọi điểm Toriceli Xét trường hợp b) Đánh số lại điểm xi cho xˆ = x1 Từ điều kiện cần tối ưu ta nhận xˆ  x xˆ  x p+ + = 0, xˆ  x xˆ  x p ∈ ∂|x| điểm x = 0, tức |p| < Như vậy, tổng hai véctơ đơn vị từ x1 tới x2 x3 với véctơ thứ ba có chuẩn nhỏ véctơ Từ suy góc x2x1x3 lớn hay 120o Tìm nghiệm tốn: Do f(x) hàm lồi nên ∈ ∂f( xˆ ) đồng thời điều kiện đủ tối ưu Từ điều phân tích ta kết luận: góc tam giác nhỏ 120o nghiệm tốn điểm Toriceli; cịn tam giác có góc lớn hay 120o nghiệm tốn đỉnh góc Nhận xét Bài tốn có cách giải khác hình hoc Cách giải nhằm nêu cách áp dụng nguyên lý Lagrange vào toán cực trị cụ thể Bài toán 3.4.2 (Bài tốn Steiner mở rộng) Tìm mặt phẳng điểm cho tổng khoảng cách theo trọng số dương từ điểm tới ba điểm khác cho nhỏ nhất? Lời giải Ký hiệu ba điểm cho xi = ( x 1i , x i2 ), i = 1, 2, 3, điểm cần tìm x = (x1, x2) ∈ ℝ2 trọng số xi mi > 0, i = 1, 2, Bài tốn tối ưu có dạng: f(x) = m 1||x - x1|| + m2||x - x2|| + m3||x - x3|| → inf (|| • || - chuẩn Euclid) Đây tốn tối ưu lồi khơng có ràng buộc Do hàm mục tiêu f liên tục toàn ℝ2 (do f(x) → + ∞ ||x|| → + ∞) nên tồn nghiệm cực tiểu xˆ toán xˆ = ( xˆ , xˆ ) Nghiệm xˆ tìm số điểm dừng: ∈ ∂f(x) 45 Áp dụng điều kiện tối ưu ta đến kết luận sau (giống toán Steiner): Giả sử tồn tam giác với độ dài cạnh m 1, m2, m3 giả sử ij góc tam giác tạo nên hai cạnh mi mj (1 ≤ i < j ≤ 3) Vẽ cung tròn gồm điểm nhìn đoạn thẳng [x i, xj] góc  - ij (tương ứng) Nếu cung tròn cắt điểm bên tam giác giao điểm điểm cần tìm; cịn cung trịn cắt phía ngồi tam giác khơng tồn tam giác với độ dài cạnh m1, m2, m nghiệm tốn trùng với đỉnh tam giác (ba đỉnh x1, x2, x 3) Chẳng hạn, xét toán Steiner mở rộng với ba điểm x 1, x 2, x cho trọng số m1 = 1, m2 = m3 = Có thể thấy tam giác với độ dài ba cạnh nửa tam giác cạnh Vì thế, tốn có 1, lời giải điểm nằm tam giác ba đỉnh x 1, x2, x3 (xem Hình 3.5) x1 30o m3 60 m2 o m1 90 o x2 120o 90 o 150o x3 Hình 3.5 Bài tốn Steiner mở rộng Bài tốn 3.4.3 Tìm mặt phẳng điểm cho tổng khoảng cách từ điểm tới bốn điểm khác cho nhỏ nhất? Đáp án Nếu điểm tạo thành tứ giác lồi điểm cần tìm giao điểm hai đường chéo tứ giác; tứ giác nhận khơng lồi điểm cần tìm đỉnh ứng với góc lớn Bài tốn 3.4.4 Tìm mặt phẳng điểm cho tổng khoảng cách từ điểm tới đỉnh đa giác cho trước nhỏ nhất? 46 Đáp án Tâm đa giác Tóm lại, chương trình bày số dạng tốn tối ưu áp dụng ngun lý Lagrange để giải Qua giới thiệu số ứng dụng lý thuyết tối ưu thực tiễn 47 KẾT LUẬN Trong khoa học thực tiễn thường gặp toán cực trị (cực tiểu hay cực đại) Nguyên lý Lagrange tạo sở lý thuyết cho nhiều phương pháp giải toán này, đặc biệt toán với ràng buộc đẳng thức Luận văn tìm hiểu trình bày nguyên lý Lagrange lý thuyết toán cực trị áp dụng nguyên lý để tìm nghiệm cực tiểu (cực đại) số tốn cực trị có ràng buộc đẳng thức Luận văn trình bày nội dung sau đây: Một số kiến thức tốn cực trị có khơng có ràng buộc: tồn nghiệm toán điều kiện tối ưu không ràng buộc Kết lý thuyết điều kiện cần điều kiện đủ tối ưu phi tuyến với ràng buộc đẳng thức Phương pháp nhân tử Lagrange đưa toán với ràng buộc đẳng thức tốn khơng ràng buộc ví dụ minh họa cho phương pháp nhân tử Lagrange Ứng dụng nguyên lý Lagrange vào tìm nghiệm cực tiểu (cực đại) số toán cực trị, chủ yếu toán với ràng buộc đẳng thức Đặc biệt toán quen thuộc số học hình học, tốn bất đẳng thức, tốn khoảng cách, tốn Steiner Có thể xem luận văn bước tìm hiểu ban đầu nguyên lý Lagrange ứng dụng nguyên lý vào giải toán cực trị Tác giả luận văn hy vọng có dịp tìm hiểu nghiên cứu sâu nhiều phương pháp khác lý thuyết tối ưu hóa 48 TÀI LIỆU THAM KHẢO [1] N T B Kim Giáo trình phương pháp tối ưu: Lý thuyết thuật toán NXB Bách Khoa Hà Nội, 2008 [2] T V Thiệu, 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 [3] B M Alekceev, E M Galeev V M Tikhomirov Tuyển tập tốn tối ưu hóa Nxb Khoa học, Mát-xcơ-va, 1984 (tiếng Nga) [4] M S Bazara et al., Nonlinear Programming: Theory and Algorithms 3rd Edition A John Willey & Sons, Inc., Publication, 2006 [5] B Chachuat Nonlinear and Dynamic Optimization: From Theory to Practice (Chapter 1) Automatic Control Laboratory, EPFL, Switzerland, 2007 [6] H A Eiselt, C L Sandblom Linear Programming and its Applications Springer, 2007 49 Luận văn chỉnh sửa theo ý kiến Hội đồng chấm luận văn cao học ngày 22 tháng năm 2014 Giáo viên hướng dẫn GS-TS Trần Vũ Thiệu 50 ... toán toán cực trị hay toán tối ưu Lý thuyết tốn tìm giá trị nhỏ (lớn nhất) hàm gọi lý thuyết toán cực trị hay lý thuyết tối ưu Các toán mô tả lời, không dùng công thức Các toán cực trị nảy sinh... xét Bài tốn có cách giải khác hình hoc Cách giải nhằm nêu cách áp dụng nguyên lý Lagrange vào toán cực trị cụ thể Bài toán 3.4.2 (Bài toán Steiner mở rộng) Tìm mặt phẳng điểm cho tổng khoảng cách... để minh họa cho lý thuyết trình bày 28 Chương ỨNG DỤNG GIẢI BÀI TOÁN CỰC TRỊ Chương trình bày ứng dụng nguyên lý Lagrange tìm nghiệm cực tiểu hay cực đại toán cực trị, chủ yếu toán với ràng buộc