Chương 1 Kiến thức chuẩn bị 1. Định nghĩa |8| Cho F = 8". Tập F được gọi là tập lồi nê u: Vx,yweF, Y4e[0.2 là các tập lỗi, tập chỉ có một điểm là tập lồi. Định nghĩa {3} Cho vecto be R*.
b được gọi là một tổ hợp lỗi của m vectơ 4.m >1) nêu tồn tại m số thực p,.p_ sao cho: b= pa, +. Mệnh đê |8| Giá sử 4, X(œe/) là các tập lỗi trong *. với / là tập chi số bắt kỳ. Khi đó, tập giao 4= ( Ì4, cũng là một tập lỗi.
Định lý [8] Tập [' =R" lả tập lỗi nếu va chi nếu với mỗi số n guyên m >1, mọi tô hợp lôi của bat cử m điểm nao trong F' đẻ u thuộc F. nghĩa là: ÂN. ớ OF } I là tân lôi <= neo PX + PN ++ px el A+ Pst r pl =l ; mc ^.TCén ễ ri Š gn Diệ ku >3 Trang6 SVTH: Trả» Minh Phượng Tiêu ehuae tại uv che lớp bài teấn Quy Hoach thảa điều kite chink quy 2. Định nghĩa |4| Cho DR.
Trên do thị cua ham /, ky hiệu epi /. là tập hợp được xác định bơi: epiƒ =|(x. Định nghĩa [8] Cho F©R'*. Một hàm số 2 xác định trén tập F được gọi là lỗi tại Kel neu: ver O<2sl =(1~4)#(x)+ AØ(+)>#[(I-4)x+Ax] (!-A)x+Aver Ham Ø được gọi là lỗi trên F nếu nó lôi tại mọi điểm vel.
Chủ ý: Định nghĩa này không đòi hỏi E là tập lôi. Định lý |8Ị Ham số Ø xác định trên một tập lỗi Fc R” là một ham lỗi trên F nêu và chỉ nêu: x,„x; 6F => (1-A)O(x,)+ AØ(+x;)> O[(1-A)x, + Ax, } O<sAsl 2. Định nghĩa |8 Cho F<R*. Một hàm số Ø xác định trên tập F được gọi là lõm tại x eT neu: xe 0<24I1 =(1~24)#(x)+AØ(x)< Ø[(I~4)x+Ax] (l=4}x+ xe Nhận xét: Hàm Ø lõm tại xe <> -Ø lồi tại vel, Hàm Ø được gọi là lõm trên F nếu nó dm tại mọi điểm xe.
Định lý |8 Ham số @ xác định trên một tập lỗi F c RB” là một ham Wm trên F nếu vả chi nếu: GVHD: TS.Trinh Cảng Diệu Trang 7 SVTH: Tria Mink Phương Tiêu chuan toi uu the lập bai leás Quy Hoach thảa dieu kige chính uy => (1- AJA) AGE) ((Ix4}x, +20] Chú ÿ: Trong các Dinh nghĩa 2.2 và 2 4 nêu ti thay các dâu >.< thi ta có định nghĩa hàm @ lỗi ngặt hoặc lõm ngật tại ve1 (hoặc trên E). Tính chất |4| Hảm / được gọi lá lồi trên D nêu và chỉ nẻu epi / là tập loi trong Eˆ*” 2. Định lý |8| Cho Ø là một hàm số xác định trên tập [ = R". Điều kiện cần nhưng không phai là điều kiện da để Ø là một ham lôi trên E là tập hợp: A, =|x/xeT.Ø(x)<øœ|c<Fc' là mot tập hợp lỗ: với mỗi số thực ø.
Tính khả vi của hàm nhiều biến và gradient 3. Định nghĩa |8| ( Cho 2 là một hàm số xác định trên tập mở PCR" và «eFF. Ham số Ø được gọi là khả vi tại x nếu với mọi xe Rˆ thỏa x+xeT thi ta có: @(x+x)=0(x)+¢(x)x+a(x,x) p> trong đó r(x) là một vectơ m chiều, va a là một hàm theo x thỏa: lima(x,x)=0. vd (ii) Gia sử F CR" là tập mở, hàm số @ được gọi là khả vi trên F nêu nó khả vị tại mọi điểm xeTF.
Các định nghĩa |8 Cho @ là một hàm số xác định trên tập mơ FcR", và vel, (1) Ham số Ø được gọi là có đạo hàm riêng tại © theo biến x, (f= I,. ,z) nếu * Ệ hàm số: GYHO: TS.Trinh Cảng Diệu Trang 8 SVTH: Trí. Minh Phượng Tiêu chuẩn lãi sợ che lấp bai toa Quy Hoạch this diều kiện chích quy có giới hạn hữu hạn khi 3 0. Giới hạn nảy được gọt là đạo ham riêng cua 2 theo biến + tại x.
KY hiệu: =ứ) (ii) Ta xác định các hàm số: 26 ‘ror ox, oe Ud —— (1) được gọi la các hàm đạo ham riêng của @ theo biển x,.(3) và VØ(x) được gọi là gradient của Ø tai x. Định lý [8 Giả sử Ø là một hàm số xác định trên tập mở F CR", và ver.x)k| trong đó limz(x,x)=0, VxeRˆ thỏa x+xeT. (ii) Giá sử Ø có đạo hàm riêng theo tắt cá các biến tại x eT, và các hàm đạo ham riêng của Ø theo các biến x,,.x„ liên tục tại x thì Ø khả vi tại x.Trinh Công Diệu Trang 9 SVTH: Trần Minh Phang Tiêu chasm lôi ưu che lớp bai oán Quy Heach thỏa điều kiện chís qey 3. Định lý |8| Cho / là ham vectơ m chiêu xác định trẻn tập mơ ['c R", và gia sư ¢ là ham sỏ xác định trên RE”.
Ham Ø xác dịnh trên F định bởi: Ø(x)=ø{ /(v}| kha vi tại ref nếu f khả vi tại x , ¢ khả vi tại y = f(x) và khi đó: vø(x)= vớ( r)Y/ (x] 4. Một số kết quả Tôpô trong R” 4. Định nghĩa [9] Cho F và A là hai tập hợp thỏa Fc Ac R". Tập F được gọi là mo (đóng) tương đối trong 4 nếu F = AQ, trong đó Q là một tập mở (đóng) trong R”.
Định lý [8] Một tập FR* được gọi là compact nêu nó thỏa một trong các điều kiện sau đây: (i) F là tập đóng và bị chặn. (ii) Mọi dãy trong F đều cógiới hạn trong F. (iii) Với một họ các tập đóng tương đối (T,)„„ bat kỳ trong T, ta có: fr,zØ=r,a.e! ““ hoặc dưới dạng tương đương: F,. Các khái niệm và dạng của hài toán Quy Hoạch Cho X° cR".
Giả sử: 9:R"+R g:R* +R” và các hàm này đều xác định trên X°. AR" +R’ GVHD: TS.Trinh Cong Diệu Trang (0 SVTH: Trin Minh Phasing Tiew chean tat uv cho lip bai bode Quy Moạch thỏa diew kiệm chính quy — [ưu bài toan Quy Hoạch tuyến tinh đã biết Tim cực tiêu hàm mục uéu Moos vy) là ham tuyến tính, đồng thời trong do các biển xv.v, thoa các ràng bude tuyến tính: g, ( imate seiko h,u(xy. Ta nghiên cửu bài toán Quy Hoạch phi tuyển như sau: Hãy tìm gia trị xác định \=Íw.3› je Ä'” thỏa các rang buộc phi tuyến: 8, (x,.É đồng thởi làm cực tiểu hàm mục tiêu Ø( x,,x,.v,) trong đó @ là ham phi tuyến. * Trong các bai toán trên, đặt: # x“(\,.É và tập X được gọi là tập các phương án của bài toán hay tập các rang buộc.
Nếu có một giá trị xeX thì ta gọi x là một phương án chấp nhận được hay một phương án.x«) thỏa tính chit; - 502; -Ø(x]}<Ø(x),VxeX. thi x được gọi là phương án tối ưu hoặc là nghiệm của bai toán Quy Hoạch phi tuyển. Lúc đó @(x) được gọi là giá trị tối ưu. Giải một bài toán Quy Hoạch chính là xác định một phương án tối ưu nào đó.
Định nghĩa {10} Cho ham số thực g(x,y) với xe SCR" và re[cR*, Điểm (r ,y `} được gọt là điểm yên ngựa cua ham ø( x. y) nêu: GYHO: TS.Trinh Cong Vids Trang tt SVTH: Trảa Minh Phương Tike thuân lôi wa che lép bai loán Quy Hoạch thos điều kien chính quy @(+v`.ref Vi vậy, khi r cổ định tại + vả ¿{c.} dược coi như một ham sé theo biến vthi + là điểm cực tiêu toản cục cua nó, con khi có định tai và ø@{ v.v} được coi như một hàm số theo biến y thì yˆ là điểm cực đại toản cục của nó GVHD: TS. Trinh Cong Diệu Trang 12 SVTH: Trần Minh Phương Tiêu chaân lãi uu che lép bài toán Quy Heach théa điều kiện chinh quy Chương 2 Các giả thiết vê điêu kiện chính quy trong bài toán Quy Hoạch Chương nảy ta sẽ khảo sát một số điều kiện chỉnh quy và mỗi liên hệ giờa các điều kiện chính quy đó. Các điều kiện chính quy này đóng một vai trò khả quan trọng khi khảo sát điều kiện cằn và đủ tối ưu cho các bài toán Quy Hoạch sẽ được khảo sat trong chương 3 và chương 4.
Điều kiện chính quy Slater Giả sử X" là một tập lồi trong R". Hàm g là ham vecto Idi m chiều trên 1“ xác định tập lồi: X=|x/xeX°. Điều kiện chính quy Karlin Gia sử X° là một tập lỗi trong R". Hàm g là hàm vectơ Idi m chiều trên X° xác định tập Idi: X=|x!xeX°®,g(x)<0) được gọi la thea man diéu kiện chính quy Karlin (trên A") nếu không ton tại pe#",p>0 thỏa pg(x)>0, Yxe X?, GVHD: TS.Trinh Céeg Diệu Trang 13 SVTH: Trin Mish Phương liêu chase tôi wa che lớp bai leás Quy Heach théa dite kiện chính quý -—--_—-——-—— — ——_- —= >——=— — —— 3.
Điêu kiện chính quy ngặt Của sự VY” 1a một tap lôi trong Fo Tham g là hain xectd lật chiếu trên V” xác định tap lót 1) 20! e{ " v=hei veN được gọt là thoa man diéu kiến chính quy ngặt (trên V") néu_Y chửa ít nhất hai điểm phan biệt xạ, v. thoa g là một ham lỗi ngat tại x,. Bố đê Điều kiện chính quy Slater (1) và điều kiện chính quy Karlin (2) la tương đương nhau. Điều kiện chỉnh quy Slater (1) và điều kiện chính quy Karlin (2) la hệ quá suy ra tử điều kiện chính quy ngặt (3).
¢ Chứng miah (1) ©(2): Tức là ta cần chứng minh điều sau: axe X°:g(x}<0<» Không tổn tại pe R”, p> 0: pg(x)20, Wxe x". [—>]: (Phan chứng) Gia sử 3p« RTM, p> 0: pg(x)>0, vxe X* Cho x = x trong biểu thức trên ta có pg(x)>0 (l') p>U0 Mặt khác ta có KỊP” Son Su (2') Từ (I') và (2") ta có điều mâu thuần. Vậy không tôn tại p eR”, p >0: pg(x}>U, xe Xx”.l)< R” vả ta có p20 => pe(x)20, Vice X° (trai giả thiét) Vậy dre X":g(x)<0 và do đó (1) ¢>(2). ® Chứng minh (3) > (1): GVHD: TS.Trinh Côsg Diés Trang 14 SVTH: Tria Minh Phượng liệu chuẩn lỗi đã the TẾ bai toáe Qey Hoach this điểu kiện chí quy Từ điều kiện chính quy (3) thì .Ý chứa hai điểm phân biệt x.
sao cho g là ham lôi ngặt tại +,.V” la tập lỗi nên với x,. eX" va với 0< 2< Ì ta có: (l-A)x, + ax, eX" Mat khác. do g lỗi ngặt tai x, nên: g[(t-A}y, +Ax, ]<(1-A)g(x,)+Ag(x. Do (1) (2) nên tử đó (2) cũng được suy ra tử (3), « Nhdn xét: (1zZ ) (3) Thật vậy.
xét hàm g(x) = 2x là hàm tuyến tỉnh xác định trên đoạn [-1,1] thi 3x, > sao cho g(x,}<0. Tuy nhiên vx,,x, €[~1,1] thì không thể xảy ra trưởng hợp #[(!~Ä)x, +Äx; Ì<(I~3)#(x,)+^Äø(x;) vig là ham tuyến tính. Điêu kiện chính quy Kuhn ~- Tucker Cho X° là tập mở trong R*, g là một ham vecto m chiều xác định trên X°, và cho: X ={x/xe X°,ø(x)<0}. Hàm g được gọi là thỏa điều kiện chính quy Kuhn - Tucker tại xe X nếu g khả vi tại x và: Tổn tại một ham vectơ n chiều e xác định trên đoạn [0,1] thỏa: Ve (z}y<0 => b.e(r)e#X, 0<z<l mee vi tại r=0 va e.