Trong hệ thống du lịch thông minh, lập lộ trình tự động là một trong những chức năng phức tạp nhưng rất quan trọng và cần thiết cho du khách trước và trong hành trình thăm quan của mình. Chức năng này không chỉ yêu cầu tạo ra phương án lộ trình phù hợp với điều kiện của du khách một cách nhanh chóng, mà còn phải tối ưu về thời gian thăm quan và hiệu quả kinh tế. Trong bài báo này, chúng tôi trình bày một thuật toán lập lộ trình tự động mới dựa trên ý tưởng của bài toán lập lịch TSP (Traveling Salesman Problem) và bổ sung tham số về thời gian du lịch hợp lý, được gọi là TPA (Travel Planning Algorithm). Thuật toán TPA được cài đặt trong hệ thống du lịch thông minh đa nền tảng của tỉnh Thái Nguyên. Dựa vào điểm du lịch được gợi ý trong quá trình lựa chọn điểm thăm quan của du khách, thuật toán TPA hoạt động ổn định và lập được lộ trình du lịch tốt hơn so với chức năng lập lộ trình trong hệ thống du lịch thông minh của TripHunter và Tập đoàn bưu chính viễn thông Việt Nam (VNPT). Se analiza como a traves de la aritmetica en diferentes sistemas de numeracion posicional, se fomenta, desarrolla y promueve el pensamiento numerico. Observando que cuando uno se ve enfrentando a situaciones de trato numerico, suele convertir la resolucion de un problema en la solucion de algoritmos; no se analiza, en cambio si se opera. Se busca que mediante bases numericas diferentes al decimal, se analicen y comprendan los principios posicionales implicitos al operar. La investigacion se centra en tres pilares que contribuyen a desarrollar el pensamiento numerico, tomados del Ministerio de Educacion Nacional y del investigador Luis Rico Romero y su grupo de investigacion, los cuales son: - Comprension de los numeros y de la numeracion. - Comprension del concepto de las operaciones. - Calculos con numeros y aplicaciones de numeros y operaciones. Bài báo sử dụng các phương pháp điều tra xã hội học để tìm hiểu nhận thức của sinh viên (SV) khoa Địa lí khi đăng kí các học phần chuyên ngành tự chọn. Kết quả khảo sát cho thấy SV Địa lí lựa chọn các học phần chuyên ngành bị chi phối nhiều bởi các yếu tố khách quan, môi trường học tập và các mục tiêu ngắn hạn; đồng thời, một số yếu tố hỗ trợ học chế tín chỉ của Trường Đại học Sư phạm Thành phố Hồ Chí Minh (ĐHSP TPHCM) chưa phát huy vai trò đúng mức. Định lý Fritz John: Nếu điểm x∗ là cực tiểu địa phương của (P ) thì tồn tại (λ, μ) : = (λ 0 , λ 1 , ..., λr, μ 1 , ..., μm) không đồng thời bằng không, (λ 0 , λ 1 , ..., λr) ≥ 0 , thỏa λ 0 5 f (x∗) + ∑ r i= λi 5 gi(x∗) + ∑ m j= μj 5 hj (x∗) = 0, (1) λi ≥ 0 , gi(x∗) ≤ 0 , λigi(x∗) = 0, i = 1, ..., r. (2) Chứng minh Cách 1: Vì điều kiện (2), ta có thể viết (1) thành λ 0 5 f (x∗) + ∑j∈I(x∗) λj 5 gj (x∗) + ∑ m j= μj 5 hj (x∗) = 0. Nếu các vectơ {5hi(x∗)}m 1 là phụ thuộc tuyến tính, khi đó tồn tại μ : = (μ 1 , ..., μm) 6 = 0 sao cho ∑ m j= μj 5 hj (x∗) = 0. Cho λ : = (λ 0 , ..., λr) = 0, ta thấy định lý thỏa với (λ, μ) 6 = 0. Giả sử các vectơ {5hi(x∗)}m 1 là độc lập tuyến tính. Ta có {d : 〈5f (x∗), d〉 < 0 , 〈5gi(x∗), d〉 < 0 , i ∈ I(x∗), 〈5hj (x∗), d〉 = 0, j = 1, ..., m} = ∅. (3) Vì nếu (3) sai và ta chọn một hướng d, ‖d‖ = 1 thuộc tập trên. Khi {5hi(x∗)}m 1 độc lập tuyến tính, theo định lý Lyusternik thì tồn tại một dãy xn → x∗ có hướng tiếp tuyến d và thỏa hj (xn) = 0, j = 1, ..., m. Ta có f (xn) = f (x∗) + [〈5f (x∗), xn − x∗ ‖xn − x∗‖〉 +o(xn − x∗) ‖xn − x∗‖ ]· ‖xn − x∗‖ , khi xn − x∗ ‖xn − x∗‖ → d và o(xn − x∗) ‖xn − x∗‖ → 0 , n → ∞. Và theo đó biểu thức trong ngoặc là âm và do đó f (xn) < f (x∗) với n đủ lớn. Nếu x∗ là nghiệm của gi thì gi(xn) < gi(x∗) = 0 với n đủ lớn. Tóm lại, {xn}∞ 1 là dãy thỏa (P ) sao cho f (xn) < f (x∗) với n đủ lớn. Điều này mâu thuẫn với giả thuyết x∗ là cực tiểu địa phương của (P ), và do đó (3) được chứng minh. Định lý được chứng minh từ (3) theo định lý hoán vị Motzkin. Cách 2: Sử dụng hàm phạt để chứng minh FJ Trước hết, cùng xem xét hàm phạt Fk(x) = f (x) + k 2 ∑ r i= g+ i (x) 2 + k 2 ∑ m j= h 2 j (x) + 1 2 ‖x − x∗‖ 2. với g i+ (x) = max { 0 , gi(x)} và k > 0 là tham số. Lấy > 0 đủ nhỏ sao cho f (x∗) ≤ f (x) với mọi x ∈ B(x∗). Do định lí Weierstrass: tồn tại min trên tập đóng và bị chặn, lấy xk là cực tiểu toàn cục của Fk trên B(x∗). Vì Fk(x∗) = f (x∗), ta có fk(x) ≤ f (x) + k 2 ∑ r i= g+ i (x) 2 + k 2 ∑ m j= h 2 j (x) + 1 2 ‖x − x∗‖ 2 \= Fk(xk) ≤ Fk(x∗) = f (x∗). (4)Các hàm g i+ , hj và f bị chặn trên B(x∗), và (4) cho thấy k 2 g+ i (xk) 2 , k 2 h 2 j (xk) cũng bị chặn. Do đó, ta có g i+ (xk) → 0 và hj (xk) → 0 khi k → +∞. Đặt x ∈ B(x∗) là điểm giới hạn của dãy {xk}. Ta có g+ i (x) = 0(tức là gi(x) ≤ 0 ) và hj (x) = 0. Điều này chứng tỏ x là điểm chấp nhận được của (P ). Cho k → ∞ ở (4), ta được f (x) ≤ f (x) + 1 2 ‖x − x∗‖ 2 ≤ f (x∗). Bởi vì f (x∗) ≤ f (x) với mỗi x ∈ B(x∗), ta có f (x∗) ≤ f (x). Điều này và bất đẳng thức trên suy ra ‖x − x∗‖ 2 = 0, tức là x = x∗. Kết quả là, bài toán Min min {Fk(x) : x ∈ B(x∗) }trở thành một bài toán tối ưu không ràng buộc với k đủ lớn. Vì vậy, ∇Fk(xk) = 0, nghĩa là ∇f (xk) + ∑ r i= (kg+ i (xk))∇gi(xk) + ∑ m j= (khj (x∗ k))∇hj (xk) + (xk − x∗) = 0. (5) Đặt αi,k = kg i+ (xk) và βj,k = khj (x∗ k), điều chỉnh véc tơ (1, α 1 ,k,... , αr,k, β 1 ,k,... , βm,k, 1) sao cho tổng của các trị tuyệt đối của các phần tử trong véc tơ là 1 (tức là, chia các phần tử cho γk := 2 + ∑r i= λi,k + ∑m j= |βj,k|), và như vậy ta có thể ký hiệu véc tơ αk bởi αk := (λ 0 ,k, λ 1 ,k,... , λr,k, μ 1 ,k,... , μm,k, λ 0 ,k). Chia cả hai vế của (5) cho γk được λ 0 ,k∇f (xk) + ∑ r i= λi,k∇gi(xk) + ∑ m j= μj,k∇hj (xk) + λ 0 ,k(xk − x∗) = 0. Bởi vì các λi,k, μj,k đều bị chặn, ta có thể giả sử rằng chúng hội tụ khi k → ∞ (nói cách khác, ta có thể lấy được một dãy con hội tụ). Lấy giới hạn khi k → ∞, ta định nghĩa λi,k → λi(i = 0,... , r), μj,k → μj (j = 1,... , m). Ta cũng có λ 0 ,k(xk − x∗) → 0 , vì λ 0 ,k bị chặn và xk → x∗. Do đó λ 0 ∇f (x∗) + ∑ r i= λi∇gi(x∗) + ∑ m j= μj ∇hj (x∗) = 0. Cách 3: Sử dụng nguyên lí biến phân Ekeland Lấy x∗ là cực tiểu địa phương của bài toán (P ), với f (x∗) ≤ f (x) với mọi x ∈ C = Br(x∗) = {x : ‖x − x∗‖ ≤ r}. Định nghĩa tập T := {(λ 0 , λ, μ) ∈ R × Rr × Rn : (λ 0 , λ) ≥ 0 , ‖(λ 0 , λ, μ)‖ = 1} Lời giải.
lim t→ 0 + f (x + td) − f (x) t \= lim t→ 0 + f (td 1 , td 2 ) − f (0, 0) t \=lim t→ 0 + t 6 d 41 d 22 t 5 (t 4 d 81 + d 42 ) , (d 1 , d 2 ) 6 = (0, 0) 0 , (d 1 , d 2 ) = (0, 0) \=lim t→ 0 + td 41 d 22 (t 4 d 81 + d 42 ) , (d 1 , d 2 ) 6 = (0, 0) 0 , (d 1 , d 2 ) = (0, 0) \=[0 , (d 1 , d 2 ) 6 = (0, 0) 0 , (d 1 , d 2 ) = (0, 0) Vậy hàm số trên khả vi theo hướng d tại x. Do đó hàm số khả vi theo hướng tại x = (0; 0).
(1m, 1m 2 )→ (0, 0), nhưng f (xm, ym) → 126\= f (0; 0) = 0. Do đó f không liên tục tại (0, 0). Bài 2. Cho ánh xạ f : R 2 → R xác định bởi f (x, y) = {x 2 , y = x 2 0 , y 6 = x 2.
Lời giải.
(d 1 t ;d 2 t )∈ R 2 , t ∈ R+. Xét lim t→ 0 + f (x + td) − f (x) t \= lim t→ 0 + f (d 1 , d 2 ) − f (0, 0) t \= tlim→ 0 + d 21 t , d 2 \= d 21 0 , d 2 6 = d 21 .Rõ ràng với những d 1 6 = 0 thì lim t→ 0 + d 21 t không tồn tại hữu hạn. Vậy hàm số trên không khả vi theo hướng tại x = (0; 0).
Bài 3. Cho ánh xạ f : R 2 → R được xác định bởi f (x, y) = |xy|m, trong đó m là số tự nhiên. Biện luận theo m tính khả vi Fréchet của hàm số trên tại x = (0, 0). Lời giải. Ta chứng minh với m > 12thì hàm số trên khả vi Fréchet. Chọn A = [00]∈ L(R 2 , R), khi đó f (x, y) − f (x) = A(x − x) + o(‖(x, y) − x‖) ⇔ |xy|m = o‖(x, y)‖ đúng do ta có lim (x,y)→(0,0) |xy|m √ x 2 + y 2 \= 0.Thật vậy, Với x = 0 ∨ y = 0 thì hiển nhiên giới hạn trên bằng 0. Với x 6 = 0 , y 6 = 0 , |xy|m √ x 2 + y 2 ≤|xy|m √ 2 xy \=1√2|xy|m− 1 / 2 → 0 do m > 12, theo định lí kẹp thì lim (x,y)→(0,0) |xy|m √ x 2 + y 2 \= 0.Bài 4. Trong các tập hợp sau, tập nào là lồi, tập nào là nón?
D = {x ∈ Rn|r 1 ≤ ‖x − x 0 ‖ ≤ r 2 }.
F = {x ∈ Rn| 〈ai, x〉 ≤ ri, ∀i = 1, 2 ,... , k}.
G = {x ∈ Rn| ‖x − x 0 ‖ ≤ ‖x − y‖, ∀y ∈ S}. Lời giải.
λ(x 1 , y 1 ) + (1 − λ)(x 2 , y 2 ) = (λx 1 + (1 − λx 2 ), λy 1 + (1 − λy 2 )). Do λy 1 + (1 − λ)y 2 ≥ λ|x 1 | + (1 − λ)|x 2 | = |λx 1 | + |(1 − λ)x 2 )| ≥ |λx 1 + (1 − λ)x 2 | nên λ(x 1 , y 1 ) + (1 − λ)(x 2 , y 2 ) ∈ A ⇒ A lồi. Lấy (x, y) ∈ A, lấy λ ≥ 0 , ta có λ(x, y) = (λx, λy). Do y ≥ |x| nên λy ≥ λ|x| = |λx|. Vậy A là nón. Lời giải. Ta chứng minh bằng quy nạp. Với k = 2, theo định nghĩa của tập lồi, ta có điều cần chứng minh. Giả sử với k = n, ta có ∑n i= λixi ∈ Ω với λ 1 , λ 2 ,... , λn ≥ 0 và ∑n i= λi = 1. Ta sẽ chứng minh với k = n + 1 : n∑+ i= λixi ∈ Ω. Thật vậy, nếu λn+1 = 1 thì λ 1 = λ 2 = λ 3 =... = λn = 0 ⇒ n∑+ i= λixi = xn+1 ∈ Ω. Với λn+1 < 1 , ta có ∑n i= λi = 1 − λn+1 và ∑n i= λi 1 − λn+ \= 1.Đặt z = ∑n i= λi 1 − λn+ xi. Theo giả thiết quy nạp, z ∈ Ω. Khi đó (1 − λn+1)z + λn+1xn+1 ∈ Ω ⇔ n∑+ i= λixi ∈ Ω. Vậy bài toán được chứng minh. Bài 6. Dùng các đặc trưng của hàm lồi để kiểm tra xem trong các hàm sau đây, hàm số nào là hàm lồi?
x 21 x 2 trên miền R × R+. Lời giải.
− 1x , f ′′(x) = 1x 2 0 , do đó f lồi.
Ta có f ′(x) = ln x + 1, f ′′(x) = 1 x > 0 , do đó f lồi.
δf δx 1 (x 1 , x 2 ) = 2x 1 − x 2 + 1, δf δx 2 (x 1 , x 2 ) = 2x 2 − x 1 − 2 , δ 2 δx 21 (x 1 , x 2 ) = 2, δ 2 δx 22 (x 1 , x 2 ) = 2, δ 2 δx 2 x 1 (x 1 , x 2 ) = − 1 , δ 2 δx 1 x 2 (x 1 , x 2 ) = − 1. Khi đó ∇ 2 f (x, y) = [2 − 1− 1 2].Ta có ∆ 1 = 2, ∆ 2 = 2 · 2 − (−1) · (−1) = 3 > 0 , suy ra ∇ 2 f (x, y) là xác định dương, do đó f lồi.
Ta có δf δx 1 (x 1 , x 2 ) = x 2 , δf δx 2 (x 1 , x 2 ) = x 1 , δ 2 f δx 21 (x 1 , x 2 ) = 0, δ 2 f δx 22 (x 1 , x 2 ) = 0, δ 2 f δx 1 x 2 (x 1 , x 2 ) = 1, δ 2 f δx 2 x 1 (x 1 , x 2 ) = 1. Khi đó ∇ 2 f (x 1 , x 2 ) = [0 11 0].Lấy (u, v) ∈ R+ × R+, ta có [ u v ] [ 0 11 0] [u v ]\= 2uv ≥ 0. Do đó ∇f 2 (x 1 , x 2 ) là dạng toàn phương nửa xác định dương, nên f lồi.
x 21 x 2 trên miền R × R+. Ta có δf δx 1 (x 1 , x 2 ) = 2 x 1 x 2 , δf δx 2 (x 1 , x 2 ) = −x 21 x 22 , δ 2 f δx 21 (x 1 , x 2 ) = 2x 2 , δ 2 δx 22 (x 1 , x 2 ) = 2 x 21 x 32 ,δ 2 δx 1 x 2 (x 1 , x 2 ) = − 2 x 1 x 22 ,δ 2 δx 2 x 1 (x 1 , x 2 ) = − 2 x 1 x 22 .Khi đó ∇ 2 f (x 1 , x 2 ) = 2x 2 − 2 x 1 x 22 − 2 x 1 x 22 2 x 21 x 32 .Suy ra ∆ 1 = 2x 2 0 , ∆ 2 = 0 ≥ 0 , vậy∇ 2 f (x 1 , x 2 ) là nửa xác định dương nên f là hàm lồi. Bài 7. Cho hai ánh xạ f 1 , f 2 : Rn → R là hàm lồi. Đặt g(x) = Min {f 1 (x), f 2 (x)} và h(x) = Max {f 1 (x), f 2 (x)}}. Hỏi hàm g và h hàm nào là hàm lồi, vì sao? (Nếu là hàm lồi hãy chứng minh, ngược lại hãy cho phản ví dụ). Lời giải. Ta sẽ chứng minh hàm h là hàm lồi. Lấy x, y ∈ Rn và λ ∈ [0; 1], do fi là các hàm lồi nên fi(λx + (1 − λ)y) ≤ λfi(x) + (1 − λ)fi(y) ≤ λh(x) + (1 − λ)h(y), i = 1, 2. Do đó h(λx + (1 − λ)y) = max {f 1 (λx + (1 − λ)y), f 2 (λx + (1 − λ)y)} ≤ λh(x) + (1 − λ)h(y). Vậy h là hàm lồi. Ta chứng minh g không là hàm lồi. Xét f 1 (x) = x, f 2 (x) = x 2 , dễ thấy f 1 , f 2 : R → R là các hàm lồi. Lấy x = 1 2 , y = 2, λ = 1 2 . Ta có λx + (1 − λ)y = 1 4 + 1 = 5 4 , f 1 (54)\= 54, f 2 (54)\= 2516.g(λx + (1 − λ)y) = g (54)\= Min {f 1 (54), f 2 (54)}\= 54.Khi đó f (n+ ∑ i= λixi )\= f (1 − λn+1) ∑ n i= λixi 1 − λn+
≤ (1 − λn+1) f ∑ n i= λixi 1 − λn+
\= (1 − λn+1) f ( n ∑ i= λi 1 − λn+ xi )
≤ (1 − λn+1) ∑ n i= λi 1 − λn+ f (xi) + λn+1f (xn+1) \=n∑+ i= λif (xi) Vậy bài toán được chứng minh.
, ta được ln ( k ∑ i= 1k xi )≥∑ k i= 1k ln(xi). Mũ hóa bởi cơ số e hai vế, ta được ∑ k i= 1 k xi ≥ e ∑ k i= 1 k ln(xi) = e 1 k ln x 1... e k 1 ln xk = x 1 k 1... x k 1 k ⇔ x 1 + x 2 +... + xk k ≥ k √x 1 x 2... xk.
Cho x, y ∈ Rn, p > 1 , q > 1 sao cho |xi| > 0 và 1p + 1q \= 1, khi đó ∑ n i= |xi||yi| ≤ ( n ∑ i= |xi|p ) 1 p ( n ∑ i= |yi|q ) 1 q .(∗) Thực vậy, xét hàm lồi f (a) = aq, a ∈ (0; +∞), q > 1 , theo bất đẳng thức Jensen về hàm lồi, ta có ( n ∑ i= wiai )q ≤ ∑ n i= wiaqi , ∀ai, wi > 0 , ∑ n i= wi = 1. Đặt wi = |xi|p ∑n i= |xi|p và ai = |xi||yi| wi . Khi đó ta được ( n ∑ i=
)q ≤ ∑ n i= |xi|q|yi|q w iq− 1 \=∑ n i= |xi|q|yi|q |xi|pq−p ·( n ∑ i= |xi|p )q− 1 \=∑ n i= |yi|q · (∑|xi|p )q− 1 Lấy căn bậc q hai vế và chú ý 1p + 1q \= 1, ta được ∑ n i= |xi||yi| ≤ ( n ∑ i= |xi|p ) 1p ( n ∑ i= |yi|q ) 1q . Do đó, bài toán (∗) được chứng minh. Quay trở lại bài toán ban đầu, nếu có i : xi = 0 thì có ngay điều phải chứng minh. Giả sử với mọi i : xi 6 = 0 ⇒ |xi| > 0 , khi đó bài toán ban đầu là hệ quả của bài toán (∗) vừa chứng minh, do ∑ n i= xiyi ≤ ∑ n i= |xi||yi|. Bài 9. Cho X là một không gian định chuẩn, M ⊂ X và x 0 ∈ X. Nón tiếp xúc (Contingent cone, Tangent cone, Bouligand cone) của M tại x 0 được cho bởi công thức sau T (M, x 0 ) = {u ∈ X|∃tn → 0 +, un → u, x 0 + tnun ∈ M, ∀n ∈ N}. Bằng định nghĩa trên, hãy tính các nón tiếp xúc sau
Lời giải.
Chọn tn = 1 n → 0 +, v 1 n = v 1 , v 2 n = √v 31 n → 0.Khi đó ta có tnv 31 n − v 22 n = 0, ∀n ⇒ (v 1 , v 2 ) ∈ T (M, x 0 ). Vậy T (M, x 0 ) = {v = (v 1 , v 2 ) ∈ R 2 | v 1 ≥ 0 , v 2 = 0}.
(xn − x 0 ) ⇒ vn ∈ cone(M − x 0 ), ∀n. Do đó v ∈ cone(M, x 0 ) ⇒ T (S, x) ⊂ cone(M, x 0 ).
→ 0 +, vn = x − x 0 , khi đó x 0 + tnvn = x 0 + 1 n (x − x 0 ) = 1 n x +(1 −1n )x 0 ∈ M, ∀n. do tính lồi của M. Như vậy x − x 0 ∈ T (M, x 0 ). Tóm lại T (M, x 0 ) = cone(M − x 0 ). Bài 11. Công thức tính nón tiếp xúc của hệ ràng buộc bất đẳng thức. Giả sử gi : Rn → R là các hàm khả vi Fréchet với mọi i = 1,... , m. Tập M được xác định bởi M = {x ∈ Rn|gi(x) ≤ 0 , ∀i = 1,... , m}. Lấy x 0 ∈ M , đặt tập chỉ số I (x 0 ) = {i ∈ { 1 ,... , m}|gi (x 0 ) = 0}. Khi đó ta có
T (M, x 0 ) = {v ∈ Rn|∇gi (x 0 ) (v) ≤ 0 , ∀i ∈ I (x 0 )}. Trong đó ∇gi (x 0 ) (v) là đạo hàm Fréchet của gi tại x 0 áp lên vecto v. Lời giải.
x 0 ∈ M ′ = {x ∈ Rn|gi(x) < 0 , ∀i = 1,... , m}. Do M ′ = ⋂ n i= g− i 1 (−∞, 0) và gi, i = 1, 2 ,... , n là các hàm liên tục nên M ′ là tập mở. Do đó x 0 ∈ M ′ = int M ′ ⇒ T (M ′, x 0 ) = Rn, lại có M ′ ⊂ M nên T (M ′, x 0 ) ⊂ T (M, x 0 ) ⇒ Rn ⊂ T (M, x 0 ). Vậy T (M, x 0 ) = Rn. Cách 2: Lấy v ∈ Rn, chọn dãy vn = v. Do gi(x 0 ) < 0 nên x 0 ∈ g− 1 (−∞, x 0 ) là tập mở do g liên tục. Khi đó, tồn tại r > 0 : B(x 0 , r) ⊂ g− 1 (−∞, x 0 ). Chọn tn = r n (‖v + 1‖) , ta được ngay x 0 + tnvn ∈ B(x 0 , r), ∀n, suy ra g(x 0 + tnvn) < 0 , ∀n. Vậy v ∈ T (M, x 0 ) ⇒ T (M, x 0 ) = Rn.
gi(x 0 + tnvn) = gi(x 0 + tnvn) − gi(x 0 ) = ∇gi(x 0 )(tnvn) + o(‖tnvn‖) \= tn (∇gi(x 0 )(vn) + o(‖tnvn‖) tn ).Do gi(x 0 + tnvn) ≤ 0 , ∀n nên ∇gi(x 0 )(vn) + o(‖tnvn‖) tn ≤ 0. Cho n → +∞, ta được ∇gi(x 0 )(v) ≤ 0 do o(‖tnvn‖) tn \=o(‖tnvn‖)‖vn‖ ‖tnvn‖ → 0 · v = 0. Vậy T (M, x 0 ) ⊂ {v ∈ Rn|∇gi (x 0 ) (v) ≤ 0 , ∀i ∈ I (x 0 )}.
[(r ‖v‖ + 1 + 1 )]→ 0 +.Khi đó tn ≤ r ‖v‖ + 1 + 1 , ∀n nên |tn − 1 |‖v + 1‖ ≤ r ⇒ |tn − 1 |‖v‖ < r ⇔ tnvn ∈ B(v, r), ∀n. Suy ra ∇gi(x 0 )(tnvn) < 0 , ∀n ⇒ ∇gi(x 0 )(tnvn) + o(‖tnvn‖) ≤ 0 ⇒ gi(x 0 + tnvn) − gi(x 0 ) ≤ 0 ⇒ gi(x 0 + tnvn) ≤ 0 , ∀n ⇒ x 0 + tnvn ∈ M, ∀n. Vậy v ∈ T (M, x 0 ). Tiếp theo, ta lấy v ∈ {v ∈ Rn|∇gi (x 0 ) (v) ≤ 0 , ∀i ∈ I (x 0 )}, ta chứng minh v ∈ T (M, x 0 ). Thật vậy, đặt vn = 1 nv +(1 −1n )v → v. Ta sẽ chứng minh vn ∈ T (M, x 0 ), ∀n và do M là tập đóng nên v ∈ T (M, x 0 ). Do ∇gi(x 0 )(v) < 0 và ∇gi(x 0 )(v) ≤ 0 nên ∇gi(x 0 )(vn) = ∇gi(x 0 ) (1n v +(1 −1n )v )\=1n ∇gi(x 0 )(v) + (1 −1n )∇gi(x 0 )(v) < 0. Theo (∗), ta cũng có vn ∈ T (M, x 0 ), ∀n, từ đó kết thúc chứng minh.
f (λx + (1 − λ)x 0 ) − f (x 0 ) ≤ λf (x) + (1 − λ)f (x 0 ) − f (x 0 ) = λ(f (x) − f (x 0 )) ⇒ f (x 0 + λ(x − x 0 )) − f (x 0 ) λ ≤ f (x) − f (x 0 ) ⇔〈∇f (x 0 ), λ(x − x 0 )〉 + o(‖λ(x − x 0 )‖) λ ≤ f (x) − f (x 0 ) ⇒ 〈∇f (x 0 ), x − x 0 〉 ≤ f (x) − f (x 0 ). Theo giả thiết 〈∇f (x 0 ), x − x 0 〉 ≥ 0 ⇒ f (x) ≥ f (x 0 ). Vậy x 0 là cực tiểu toàn cục của (P ). Bài 13. Xét bài toán sau (P ) : Min x 2 + y 2 s x 2 − (y − 1) 3 = 0.
Lời giải. a) Cách 1: Giả thiết suy ra (y − 1) 3 = x 2 ≥ 0 ⇒ y ≥ 1. Do đó x 2 + y 2 ≥ 0 + 1 = 1. Dấu “ = “ xảy ra khi và chỉ khi x = 0, y = 1. Cách 2: Thay x 2 = (y − 1) 3 vào biểu thức tính Min, ta được x 2 + y 2 = (y − 1) 3 + y 2 = f (y). f ′(y) = 3(y − 1) 2 + 2y > 0 ∀y, suy ra hàm f tăng trên [1; +∞). Vậy f (y) ≥ f (1) = 1.
}.Lấy v ∈ T (Ω, x 0 ), khi đó ∃tn → 0 +, ∃vn = (v 1 n, v 2 n) → v : (0, 1) + (tnvn) ∈ Ω, ∀n ⇔ (tnv 1 n, 1 + tnv 2 n) ∈ Ω, ∀n ⇔ v 21 n − tnv 32 n = 0, ∀n. Cho n → +∞ ⇒ v 1 = 0, ngoài ra v 2 n ≥ 0 , ∀n ⇒ v 2 ≥ 0. Vậy T (Ω, x 0 ) ⊂ {v = (v 1 , v 2 ) ∈ R 2 | v 1 = 0, v 2 ≥ 0 }. Ta chứng minh { v = (v 1 , v 2 ) ∈ R 2 | v 1 = 0, v 2 ≥ 0 }⊂ T (Ω, x 0 ). Lấy v = (v 1 , v 2 ) ∈ {v = (v 1 , v 2 ) ∈ R 2 | v 1 = 0, v 2 ≥ 0 }. Nếu v = (0, 0) thì chọn tn = 1 n, v 1 n = 0, v 2 n = 0. Nếu v 6 = (0, 0). Chọn v 1 n = 1 n → v 1 , v 2 n = v 2 , tn = v 21 n v 32 n → 0 +.Khi đó v 21 n − tnv 32 n = 0, ∀n. Do đó v ∈ T (Ω, x 0 ) ⇒ T (Ω, x 0 ) = {v = (v 1 , v 2 ) ∈ R 2 | v 1 = 0, v 2 ≥ 0 }. Ta có ∇f (x, y) = [2 x 2 y ]⇒ 〈∇f (0, 1), v〉 = 2v 2 ≥ 0. Vậy theo điều kiện cần tối ưu cấp 1 dạng hình học: (0, 1) là cực tiểu địa phương của (P ). Bài 14. Xét bài toán sau (P ) : Min x 3 − y s. (x, y) ∈ Ω = {(x, y) ∈ R 2 |x 2 − y 3 = 0 }.
Lời giải.
∃tn → 0 +, ∃vn = (v 1 n, v 2 n) → v : (0, 0) + (tnvn) ∈ Ω, ∀n ⇔ (tnv 1 n, tnv 2 n) ∈ Ω, ∀n ⇔ v 12 n − tnv 23 n = 0, ∀n. Cho n → +∞, ta được v 1 = 0, ngoài ra v 2 n ≥ 0 , ∀n ⇒ v 2 ≥ 0. Vậy T (Ω, x 0 ) ⊂ {v = (v 1 , v 2 ) ∈ R 2 | v 1 = 0, v 2 ≥ 0 }. Ta chứng minh { v = (v 1 , v 2 ) ∈ R 2 | v 1 = 0, v 2 ≥ 0 }⊂ T (Ω, x 0 ). Lấy v = (v 1 , v 2 ) ∈ {v = (v 1 , v 2 ) ∈ R 2 | v 1 = 0, v 2 ≥ 0 }. Nếu v = (0, 0) thì chọn tn = 1 n, v 1 n \= 0, v 2 n = 0. Nếu v 6 = (0, 0). Chọn v 1 n = 1 n → v 1 , v 2 n = v 2 , tn = v 21 n v 32 n → 0 +.Khi đó v 12 n − tnv 23 n = 0, ∀n. Do đó v ∈ T (Ω, x 0 ) ⇒ T (Ω, x 0 ) = {v = (v 1 , v 2 ) ∈ R 2 | v 1 = 0, v 2 ≥ 0 }.
[3 x 2 − 1 ]⇒ 〈∇f (0, 0), v〉 = −v 2 ≤ 0. Vậy theo điều kiện cần tối ưu cấp 1 dạng hình học: (0, 0) không là cực tiểu địa phương của (P ). Bài 15. Xét bài toán sau (P ) : Min x + 2y s. x 2 + y 2 = 1, x + y ≤ 1. Áp dụng điều kiện cần tối ưu cấp 1 dạng hình học, kiểm tra x 0 = (0; 1) có phải là cực tiểu địa phương của (P ) hay không? Lời giải. Ω ={(x, y) ∈ R 2 | x 2 + y 2 = 1, x + y ≤ 1 }.Bước 1: Tính nón tiếp xúc T (Ω, x 0 ). Lấy v ∈ T (Ω, x 0 ), khi đó ∃tn → 0 +, ∃vn = (v 1 n, v 2 n) → v : (0, 1) + (tnvn) ∈ Ω, ∀n ⇔ (tnv 1 n, 1 + tnv 2 n) ∈ Ω, ∀n
(12,12).Bài 17. Xét bài toán sau (P ) : Min x + 2y s. x 2 + y 2 = 1, x + y ≤ 1.
Lời giải. 1. Xét f (x, y) = x + 2y. Hàm f liên tục và bức, hơn nữa Ω = {(x, y) ∈ R 2 | x 2 + y 2 = 1, x + y ≤ 1 } là tập đóng nên (P ) có nghiệm.
λ 0 + λ 1 + 2μx = 0 2 λ 0 + λ 1 + 2μy = 0 λ 1 (x + y − 1) = 0 x 2 + y 2 − 1 = 0 λ 0 ≥ 0 , λ 1 ≥ 0. (13)Giả sử λ 0 = 0, khi đó λ 1 + 2μx = 0 λ 1 + 2μy = 0 λ 1 (x + y − 1) = 0 x 2 + y 2 − 1 = 0 λ 1 ≥ 0. (14)Nếu μ = 0 thì λ 1 = 0, khi đó λ 0 = λ 1 = μ = 0 (loại). Vậy μ 6 = 0. Nếu λ 1 = 0 thì từ μ 6 = 0 ⇒ x = y = 0 (vô lý). Do đó λ 1 6 = 0. Với λ 1 6 = 0, từ phương trình thứ 3 suy ra x + y − 1 = 0, giải hệ {x + y − 1 = 0 x 2 + y 2 − 1 = 0 được nghiệm (1, 0) và (0, 1). Với (x, y) = (1, 0), thay vào hai phương trình đầu: {λ 1 + 2μ = 0 λ 1 = 0 ⇒ λ 1 = μ = 0 (loại). Với (x, y) = (0, 1), thay vào hai phương trình đầu cũng suy ra λ 1 = μ = 0 (loại). Vậy λ 0 6 = 0.
1 + λ 1 + 2μx = 0 2 + λ 1 + 2μy = 0 λ 1 (x + y − 1) = 0 x 2 + y 2 − 1 = 0 λ 1 ≥ 0. (15)Nếu λ 1 = 0 thì 1 + 2μx = 0 2 + 2μy = 0 x 2 + y 2 − 1 = 0. ⇒ (x, y, μ) = (− 1√5,− 2√5,2√5)∨ (x, y, μ) = (1√5,2√5,− 2√5).Loại nghiệm (x, y, μ) = (1√5,2√5,− 2√5)do x + y > 1 mâu thuẫn giả thiết. Nếu λ 1 6 = 0 ⇒ x + y − 1 = 0, khi đó (x, y) = (1, 0) ∨ (x, y) = (0, 1). Với (x, y) = (1, 0) thì {1 + λ 1 + 2μ = 0 2 + λ 1 = 0 ⇒ λ 1 = − 2 < 0 (loại). Với (x, y = (0, 1) thì {1 + λ 1 = 0 2 + λ 1 + 2μ = 0 ⇒ λ 1 = − 1 < 0 (loại). Vậy (x, y) = (− 1√5,− 2√5).
(− 1√5,− 2√5)là nghiệm của bài toán (P ). Bài 18. Xét bài toán sau (P ) : Min ln x − y s. x 2 + y 2 ≤ 4 , x ≥ 1. a) Tìm các ứng viên nghiệm thỏa điều kiện FJ.
Lời giải. Trước hết ta nhận xét là f (x, y) = ln x − y liên tục trên Ω = {(x, y) ∈ R 2 : x 2 + y 2 ≤ 4 , x ≥ 1 }, hơn nữa Ω đóng và bị chặn, do vậy bài toán (P ) có nghiệm. Bài toán P chuyển lại thành (P ) : Min ln x − y s. x 2 + y 2 ≤ 4 , −x ≤ − 1. g 1 (x, y) = x 2 + y 2 − 4 , g 2 (x, y) = −x + 1. Xét hàm Lagrange L(x, y, λ 0 , λ 1 , λ 2 ) = λ 0 (ln x − y) + λ 1 (x 2 + y 2 − 4) + λ 2 (−x + 1). Xét hệ FJ |
