Chương 2: Cơ sở qui hoạch lồi

Ly thuyêt Qui hoach tuyên tinh

́ ́ ̣ ́ ́

CH

ƯƠ

NG II: C S QUI HO CH L I Ồ

Ơ Ở

Ạ

§ 1 Bài toán qui ho ch l

i c b n

ạ

ồ ơ ả

1.1 Trình bày bài toán qui ho ch l

i c b n

ạ

ồ ơ ả

˝ G i, f là hàm l ồ ồ i xác đ nh trên ị G , gi, i =1,2,…,m, là m hàm lõm ế ậ , bi , i = 1,2,…,m, là m s th c. D th y r ng, n u t p ố ự ễ ấ ằ Cho G Rn, l cũng xác đ nh trên ị h pợ G } (1.1) X = {x˛ Rn/ gi(x) ‡ bi, i = 1,2,…,m; x˛

n (Bài t p 42). ậ

không r ng thì nó là t p h p l i, đóng trong R ợ ồ ậ ỗ

1(x), g2(x), …, gm(x)) là vect ơ i d ng c vi

Đ cho g n, ký hi u g(x) = (g m hàm ệ Rm. Khi đó t p t p X đ t d ọ 1, b2, …, bm) ˛ ể s , b = (b ố ậ ậ ế ướ ạ ượ

G X = { x˛ Rn / g(x) ‡ b, x˛ } (1.2)

‡ gi(x) ‡ ự ệ ị trong đó ký hi u g(x) đây đ b (cid:219) c g i là bài toán qui hoach lôi c b n. bi, i = 1,2, …, m. Bài toán c c tr sau ̀ ơ ả ượ ọ ̣

0 f (x )

= f (x) ể ˛ min x X Tìm x0˛ X, đ cho (1.3) Lý thuy t và các ph ng pháp gi ượ ươ ả ọ ế ạ ồ ỉ c g i là Lý ng này ch trình bày ph n lý thuy t làm ế i bài toán i bài toán (1.3) đ ầ ng pháp đ gi i. Trong ch ự ươ ậ ệ c trình bày trong chuyên đ Qui ho ch phi tuy n h c kỳ 7. thuy t qui ho ch l ế c s cho vi c xây d ng các thu t toán. Các ph ươ ơ ở (1.3) s đ ạ ẽ ượ ể ả ế ở ọ ề

1.2 Đi u ki n chính qui ệ

ề

c g i là th a ặ ượ ỏ mãn ọ Đn 1.1: T p h p X xác đ nh theo (1.1) ho c (1.2) đ ị đi u ki n cính qui , n uế ợ ệ ậ ề

" i, 1£ i £ m, $ (1.4) xi: gi(xi) > bi

c coi là tho mãn đi u ki n chính qui ượ ả ề ệ Ngoài ra, t p X cũng đ ậ Slater, n u ế $ i, 1£ i £ m (1.5) x0: gi(x0) > bi "

Lê Văn Phi, Khoa Toan Thông kê,

ng Đai hoc Kinh tê Tp. Hô Chi Minh

ườ

ươ ề D th y r ng hai đi u ki n chính qui (1.4) và (1.5) là t ễ ấ ằ ứ ng đ ỏ ế ỏ ươ ng ệ nhau; t c là n u X th a mãn đi u ki n chính qui (1.4) thì cũng th a đi u ề ề ệ i (Bài t p 43). ki n chính qui (1.5) và ng ậ c l ượ ạ ệ

́ ́ ̣ ̣ ́ ̀ ́

Ly thuyêt Qui hoach tuyên tinh

1.3 Hàm Lagrange

́ ́ ̣ ́ ́

G , xét vect m chi u h(x) = b – g(x), ớ ọ ˛ ng v i m i x ơ ề

· Ứ t c là ứ hi(x) = b – gi(x), i = 1,2,…,m Trên G {y˛ Rm/ y ‡ 0} ta đ nh nghĩa hàm s ố ị

= i 1

- (cid:229) g (x)] y [b i L(x,y) = f(x) + Æ y, h(x)æ = f(x) + (1.6)

c đ nh nghĩa theo (1.6) đ c g i là ượ ị ượ ọ ớ hàm Lagrange ng v i ứ Hàm L(x,y) đ bài toán qui hoach lôi (1.3). ̣ ̀

i u c a bài toán

qui ho

§ 2 Các đi u ki n t ề

ệ ố ư ủ

2.1 Đi m yên ng a ự

ể

· T. ị Rm và j (s,t) là hàm s xác đ nh trên S ˛ S· T đ Cho S ˝ Rn, T˝ Đn 2.1: Đi m (s*, t*) ể c g i là đi m yên ng a (Hình ) c a hàm ự ượ ọ ố ể ủ j (s, t) trên mi n Sề · T, n uế

S = T = [0;1], j

(s, t) = s + t

(s, t*)

(s*, t*)

j j j (s*, t)

2 (1;1) (0;1) (1;0)

s* t (s*, t*)

1 t 1 s

Hinh 2.1 Hinh 2.2

t˛ T : j (s*, t) £ j (s*, t*) £ j (s, t*) " s˛ S, " (2.1)

ể

0 lên 1) thì giá tr hàm s s

2.1, đi m (s*, t*) = (0; 1) là đi m yên ng a c a hàm ỉ

ự ủ ừ

ể

ị

ế

ổ

ỉ

ữ ừ

j (s,t) = s + t. Vì, ố ẽ ể ả nguyên s* = 0 và thay đ i t (t ch có th gi m 1 đ n 0. Trong khi đi m (1;0) không ph i là ả ể ự ví d này cũng cho th y r ng, đi m yên ng a không ph i là c c

ự

ể

hình Ở nguyên t* = 1 và thay đ i s (s ch có th tăng t n u gi ữ ổ ế 1 đ n 2. Trong khi đó, n u gi tăng t ế ừ 1 đ n 0) thì giá tr hàm s gi m t t ố ả ị ế ừ đi m yên ng a. ự Ở ụ ể Lê Văn Phi, Khoa Toan Thông kê,

ế ả ấ ằ ng Đai hoc Kinh tê Tp. Hô Chi Minh

ườ

̀ ̀

́ ́ ̣ ̣ ́ ̀ ́

Ly thuyêt Qui hoach tuyên tinh

(s,t) = s + t là 0, t

ạ

ị ự ạ i (0;0), giá tr c c đ i

ể

ị ự ể ủ j tr c a hàm Lagrange. (Giá tr c c ti u c a ị ủ i đi m (1;1). là 2 t ạ D dàng ch ng minh đ ứ ễ

́ ́ ̣ ́ ́

c quan h sau đây: ệ f £ f ượ (s, t) (2.2) ˛ ˛ inf s S inf s S ˛ ˛ sup t T sup t T

t T

s S

Đlí 2.1: Đ cho hàm ể ự ể f f j (s,t) có đi m yên ng a trên mi n S ề (s, t) maxinf i các minmax c n và đ là t n t ủ ầ ồ ạ ˛ ˛ ˛ min s S ˛ · T thì đi u ki n ệ ề (s, t) sup ; và t T . đ ng th i chúng b ng nhau ồ ằ ờ

ứ j (s,t) trên ả ử ầ ự ủ ể f £ f s (s*,t*) là đi m yên ng a c a hàm (s*, t*) (s*, t) và do đó mi n Sề ˛ Ch ng minh : a) Đi u ki n c n: Gi ệ ề sup · T. Khi đó theo (2.1) t T f £ f (s, t) (s*, t*) inf ˛ ˛

s S

t T

ng t , sup s S t T T ươ ự f £ f (s*, t*) (s, t) supinf ˛ ˛

ứ f £ f £ f £ f £ f (s*, t*) (s, t*) (s, t*) (s, t) (s, t) ˛ ˛ ˛ inf s S inf s S ˛ ˛ ˛

s S

t T

sup t T ả ở ừ ẵ f f Suy ra b t đ ng th c kép ấ ẵ sup sup inf s S t T t T ứ T (2.2) suy ra các d u b t đ ng th c bên trong ph i tr thành đ ng th c; ấ ứ = (s, t) = f (s*, t) (s*, t*) và t c là ứ ˛ ˛ ˛ f f = (s, t) = f (s, t*) (s*, t*) sup inf s S t T supinf ˛ ˛ ấ ẵ sup t T inf s S ˛ f f = f (s, t) (s*, t*) (s*, t*) = f (s, t*) maxinf Hay và ˛ ˛ ˛ min s S ˛

s S ủ

t T b) Đi u ki n đ : Gi ệ ề nhau, t c là ứ maxinf

t T

s S (s, t*)

sup t T s các giá tr minmax trong đ nh lý t n t ồ ạ ị ị ằ i và b ng $ f f f f = (s, t) (s, t*) = (s, t*) (s*, t) ˛ ˛ ˛ ˛ ˛ ˛ sup t T sup t T f £ f £ f ả ử s*˛ S, t*˛ T, sao cho inf và s S (s*, t*) min s S (s*, t) . Theo gi thi ế ả ằ t các minmax b ng ˛ ˛

ứ ứ ứ f f ẵ (s*, t) = f (s, t*) ˛ ˛ sup t T

ộ ậ

ế

1Trong ch ng minh trên các bi n s, t bi n thiên đ c l p, nên n u (s*,t*) và (s’,t’) là nh ng ữ ứ ự ủ j (s,t) thì các c p (s*,t’) và (s’,t*) cũng là đi m yên ng a. đi m yên ng a c a

ế ể

ự

ể

ặ

Lê Văn Phi, Khoa Toan Thông kê,

ng Đai hoc Kinh tê Tp. Hô Chi Minh

ườ

t˛ T: j (s*,t) £ j (s*,t*) £ j (s,t*). T c là c p (s*,t*) ứ ừ ặ sup inf Suy ra s S t T nhau, nên các b t đ ng th c ph i tr thành đ ng th c. T c là ả ở ấ ẵ = (s*, t*) inf s S T đây suy ra là đi m yên ng a c hàm · T. ª1 j (s,t) trên mi n Sề " s˛ S, " ự ủ ể

́ ́ ̣ ̣ ́ ̀ ́

Ly thuyêt Qui hoach tuyên tinh

́ ́ ̣ ́ ́

ể

ự ủ

ề

ệ ố i

2.2 Đi m yên ng a c a hàm Lagrange L(x,y) và đi u ki n t u ư

̀ ơ ả ầ ̣ · {y˛ Rm/ y ‡ Theo ph n 1.3, hàm Lagrange c a bài toán qui hoach lôi c b n (1.3) ủ ề G xác đ nh trên mi n 0} có d ngạ ị

= i 1

- (cid:229) g (x)] y [b i L(x,y) = f(x) + Æ y, h(x)æ = f(x) + (1.6)

x*, y*) là đi m yên ng a c a L( Theo Đn 2.1, thì c p (ặ ự ủ ể x,y) trên mi nề G · {y˛ Rm/ y ‡ 0} khi

G " x˛ , " y‡ 0: L(x*,y) £ L(x*,y*) £ L(x,y*) (2.3)

y 0 i và b ng nhau.

Do L(x,y) l x và tuy n tính theo ế ‡ ể · ở {y˛ Rm/ y ‡ ự và {y˛ Rm/ y ậ G y, đ ng th i các t p ồ ờ thành: Đ cho hàm Lagrange 0} thì đi u ki n c n và ề ệ ầ i theo ồ Đlí 2.2 tr 0} là nh ng t p đóng, nên ữ ậ ề G L(x,y) có đi m yên ng a trên mi n ể đ là các minmax ủ L(x, y) L(x, y) maxmin (2.4) ˛ G ‡ ˛ G ‡ min x max y 0

ằ t n t ồ ạ

Quan h gi a đi m yên ng a c a hàm L( i gi i c a bài ả ủ ể i c b n (1.3) đ x,y) và l ự ủ ờ c cho b i đ nh lý sau đây. toán qui hoach l ệ ữ ồ ơ ả ượ ở ị ̣

ủ ể x,y) trên mi nề Đlí 2.2: N u (ế G· x*, y*) là đi m yên ng a c a hàm L( i gi {y˛ Rm, y ‡ 0} thì x* là l ự i c a bài toán (1.3). ả ủ ờ

: Gi ả ử x*, y*) là đi m yên ng a c a hàm L( ự ủ x,y) trên mi nề G · G , " Ch ng minh ứ {y˛ Rm, y ‡ £ f(x) + Æ y*, h(x)æ (2.5) ể y ‡ " x˛ 0 : f(x*) + Æ y*, h(x*)æ

Lê Văn Phi, Khoa Toan Thông kê,

ng Đai hoc Kinh tê Tp. Hô Chi Minh

ườ

" Æ y*, h(x*)æ £ (2.6) b – g(x*) £ 0; hay G x*) £ 0. T c là ứ , suy ra x*˛ X. ớ ớ x*) £ ặ ế x*˛ t 0 nên cũng đúng khi y = 0. T (2.6) suy ra ứ 0, nên ta cũng có b t đ ng th c ừ ấ ẵ s ( 0}. T c là ứ f(x*) + Æ y, h(x*)æ £ T đây suy ra: ừ 0 : Æ y, h(x*)æ y ‡ a) D th y r ng đi u ày ch xãy ra khi h( ỉ ề ễ ấ ằ g(x*) ‡ thi b. K t h p v i gi ả ế ợ ọ y ‡ b) Do (2.6) đúng v i m i 0. M t khác, do h( = 0. c l G (2.5) suy ra f(x) + Æ y*, h(x)æ ‡ Æ y*, h(x*)æ ượ ạ Suy ra Æ y*, h(x*)æ ng i. " x˛ c) T đây và t ừ ệ 0. Do đó f(x*) £ . Đ c bi t khi ặ f(x), " x˛ X. T cứ ừ x˛ X, thì h(x) £ i gi là x* là l : f(x*) £ 0, nên Æ y*, h(x)æ £ i c a bài toán (1.3).ª ờ ả ủ

́ ́ ̣ ̣ ́ ̀ ́

Ly thuyêt Qui hoach tuyên tinh

́ ́ ̣ ́ ́

t đi u ki n đ đ m t vect x* là l i gi ủ ể ộ ế ờ i c a bài toán ả ủ ỉ ầ i bài toán (1.3) ch c n Đ nh lý 2.2 cho bi ơ ị ệ i c b n (1.3). T đ nh lý này suy ra, đ gi QH l ể ả ồ ơ ả ng ng L(x,y). tìm m t đi m yên ng a c a hàm Lagrange t ươ ứ ộ ề ừ ị ự ủ ể

2.3 Đ nh lý Kuhn- Tucker ị

Đlý 2.3: Gi ệ ể i gi ờ ồ ơ ả i đi m ỏ ề i c a bài toán QH l ả ủ ồ ạ ầ s r ng t p X th a mãn đi u ki n chính qui. Khi đó đ cho i c b n (1.3) thì đi u ề ể y* ‡ 0 đ cho c p ( x*, y*) là ặ ể {y˛ Rm, y ‡ x,y) trên mi n ề G· ậ là l ủ ự ủ ả ử ằ đi m ể x* ˛G ki n c n và đ là t n t ệ đi m yên ng a c a hàm Lagrange L( ể 0}.

(m+1).

ệ ề ứ s ầ i gi ứ ả ủ ả ử x* là l ừ ị ệ ầ . Gi ủ suy t đi u ki n c n ề ệ đ nh lý 2.2 mà không c n có đi u ki n ề i c a bài toán ờ ồ ơ ả G f(x*), z £ , đ t ặ 0}. V i ớ x˛ b – g(x)}

i trong R . Rõ ràng P, S đ u là t p l ặ ậ ồ f(x), z ‡ ề ˛ G U x

i. Gi P0 ˙ ả ử 0 ˙ s P ấ ˘ ứ f(x’), z’ ‡ G X và f(x’) < f(x*). Đi u này trái v i gi

0 = intP và do đó P0 0, z’) ˛ . T c là có th tìm th y (z’ ể b – g(x’) ng v i ít nh t m t ộ ấ ớ x* t r ng thi ế ằ ả

a tách P v i S. T c là t n t

ứ ớ ề S „ ậ ồ 0 < f(x*), z’ < 0 và z’0 ‡ ư ậ x’˛ i c a (1.3). ờ ˙ ng I, s t i và intP ẽ ồ ạ i t i 0, i (u ươ 0,u)˛ R (m+1), (u0,u) „ , nên theo đ nh lý tách 3 ch ị ồ ạ S = ˘ ớ ứ

, ‡ (w0, w) ˛ P: u0z0 + Æ u, zæ (z0, z)˛ S và " u0w0 + Æ u, wæ 0. (2.7) ‡ u0 (z0 - w0) + Æ u, z - wæ f(x) ‡ f(x*) > w0, nên z0–w0 > 0. Từ "

0 = 0, ta có x˛

= i 1

(z0, z)˛ S và " 0, i = 1,2,…,m (bài t p…). (w0, w) ˛ P0 thì u0 ‡ ậ ự G ừ : Đi u ki n đ Ch ng minh chính qui. Ta ch ng minh QH l i c b n (1.3). 1) Xét tâp P = {(z0, z) ˛ R (m+1)/ z0 £ S(x) = {(z0, z) ˛ R (m+1)/ z0 ‡ S(x) Và đ t S = 2) Đ t Pặ 0 = {(z0, z) ˛ R (m+1)/ z0 < f(x*), z < 0}. Khi y Pấ cũng là t p l S v i z’ớ x’˛ . Nh v y, i gi là l ả ủ 3) Do P, S l ồ m t siêu ph ng H ẳ ộ đ choể " Hay (w0, w) ˛ P0 thì z0 ‡ Do " (z0, z)˛ S và " đây d dàng suy ra r ng, đ (2.7) đúng ể ằ ễ i ‡ , cũng suy ra r ng u ng t 0. T ằ ươ 4) Ch n ọ x˛ tùy ý, z0 = f(x), z = b – g(x) và w0 = f(x*), w = 0. T (2.7) suy ra: " G ‡ : u0 f(x) + Æ u, b – g(x)æ u0 f(x*). x˛ (2.8) N u uế " G : Æ u, b – g(x)æ ‡ 0. (2.9) Do u ‡ = 0. Hay - (cid:229) 0, " x˛ X, nên trên X: Æ u, b – g(x)æ = g (x)) 0 , " 0, b – g(x) £ u (b i

Lê Văn Phi, Khoa Toan Thông kê,

ng Đai hoc Kinh tê Tp. Hô Chi Minh

ườ

Hay " x˛ X. (2.10) x˛ X i = 1,2,….,m: ui(bi – gi (x)) = 0, "

́ ́ ̣ ̣ ́ ̀ ́

Ly thuyêt Qui hoach tuyên tinh

́ ́ ̣ ́ ́

0, nên đ (2.10) th a mãn ph i t n t ỏ thi ộ i’> 0 và do ế t ả ỏ ệ 0. Chia hai v i ít nh t m t u ấ ớ ề 0 > 0. (2.8) cho u ấ ẵ 0 > 0, ta có b t đ ng G

x*˛ X, : f(x) + Æ y*, b – g(x)æ x = x* thì t ừ Vì (u0,u) „ ể ả ồ ạ x˛ X: (bi’ – gi’(x)) = 0. Đi u này trái v i gi ư ậ " đó ng v i i’ nh v y ớ ứ r ng X ph i th a mãn đi u ki n chính qui. V y u ậ ề ả ằ 5) Đ t ặ y* = (1/ u0)u ‡ " x˛ th cứ Đ c bi t khi ệ ặ nên (b – g(x*)) £ ế ở f(x*). (2.11) ‡ Æ y*, b – g(x*)æ 0. Nh ng, do ư c l i. Suy ra ượ ạ ứ

ng v i ấ ẵ ớ ‡ đây suy ra 0 và ta có b t đ ng th c ng ấ ẵ Æ y*, b–g(x*)æ = 0. Do đó b t đ ng th c (2.11) t ươ L(x*,y*) (2.12) ứ L(x,y*) ‡ 0, thì M t khác, do " y‡ ặ

ế

ề

ệ

i(x) là phi tuy n thì đi u ki n chính qui là c n thi

t. Có th

ể ỏ ệ

ế

ầ

ầ ấ

ế ụ

ề

ả

= {x / x ‡

0} ˝

Chú ý: Khi gi(x) là nh ng hàm tuy n tính thì có th b qua đi u ki n chính qui (xem ữ ph n 2.5). Nh ng khi g ể ề th y rõ đi u này thông qua ph n ví d sau đây: Cho n =1, f(x) = -x, g1(x) = g(x) = -x2; b1 = b = 0; G Bài toán qui ho ch l

i có d ng

ạ

ồ

v i X = {x ớ T p X nh v y ỏ ậ ràng là x* = 0 và fmin = f(x*) = 0. Hàm Lagrange t

min{-x / x˛ X} 0, x ‡ ˛ R / -x2 ‡ 0} = {0} ư ậ không th a mãn đi u ki n chính qui ệ ề ươ

i c a bài toán này rõ . L i gi ờ ng ng có d ng: L(x,y) = -x + ứ

ả ủ ạ

f(x*) + Æ y, b – g(x*)æ x*,y*) ‡ L(x*,y) (2.13) x,y) trên ừ ế ợ ặ x*,y*) là đi m yên ng a c a L( ự ủ ể · ớ 0}.ª {y/ y ‡ f(x*) ‡ T đây cũng suy ra L( K t h p (2.12) v i (2.13), c p ( mi n ề G

2 yx )

yx2 xác đ nh trên mi n x

0, y ‡

0. Do đó

ề

ị

không t n t

ồ ạ . Vì v y hàm L(x,y) ậ

không có đi m yên ng a. ể

ự

+ = - ‡ ) ‡ ‡ ‡ max min (-x x 0 y 0 max ( y 0 1 4y

ng h p f(x), g ị ườ ợ

i(x) là nh ng hàm ữ

nR +

G 2.4. Đ nh lý Kuhn – Tucker cho tr kh vi và = ả

nR + và f(x), gi(x) là nh ng hàm kh vi trên ữ

G = , i = 1,2,…,m; t cứ i các gradient f’(x) và g ả i’(x), i = 1,2,…,m. Cho G là t n t ồ ạ

Lê Văn Phi, Khoa Toan Thông kê,

ng Đai hoc Kinh tê Tp. Hô Chi Minh

ườ

ặ ể ự ể ủ ệ ề ầ ệ ấ ẵ ệ ấ ẵ ứ ỏ Đlí 2.4: Đ cho c p (x*, y*) là đi m yên ng a c a hàm Lagrange L(x,y) ủ ‡ 0}· {y/ y ‡ 0} thì đi u ki n c n và đ là chúng trên mi n {x/ x ề th a mãn h b t đ ng th c sau đây (g i là h b t đ ng th c ứ ọ Kuhn-Tucker):

́ ́ ̣ ̣ ́ ̀ ́

Ly thuyêt Qui hoach tuyên tinh

́ ́ ̣ ́ ́

* L x

* L y

* x . j

* y . i

* L x

i * L y

* i

* j

(cid:236) ¶ (cid:236) ¶ ‡ ‡ 0 (cid:239) 0 (cid:239) ¶ ¶ (cid:239) (cid:239) (cid:239) (cid:239) ¶ ¶ (cid:239) (cid:239) = = (cid:237) (cid:237) 0 0 j = 1,2,…,n: ; (2.14) i = 1,2,…,m: , (2.15) ¶ ¶ (cid:239) (cid:239) (cid:239) (cid:239) ‡ ‡ y 0 x 0 (cid:239) (cid:239) (cid:239) (cid:239) (cid:238) (cid:238)

* L x

* L y

¶ ¶ ¶ ¶ = = = = ; j 1, 2,..., n ;i 1, 2,..., m Trong đó và ¶ ¶ ¶ ¶ L(x*, y*) x L(x*, y*) y

: ứ ể ả ử ầ : Gi ‡ £ 0, y ‡ 0; t c là L(x*,y) x‡ ự ủ L(x*,y*) £ j £ ¥ i xác đ nh trong kho ng [0, s (x*,y*) là đi m yên ng a c a hàm Lagrange L(x,y*), " n. Khi đó hàm ), có ả ị

j. Khi đó có hai tr

* dL(x ) j

ng h p xãy ra: i x* Ch ng minh a) Đi u ki n c n ệ ề L(x,y) v i x ớ 0," y‡ % jL(x ) c c ti u t ự ể ạ ứ 0. Đ t xặ (j) = (x*1,…, x*j-1, xj, x*j+1,…,x*n), 1£ = L(x(j),y*) là hàm m t bi n l ế ồ ộ ườ ợ % ‡ 0 tăng trên [0, ¥ ), hay x*j = 0; t c là ứ và hi nễ % jL(x ) dx

* dL(x ) / dx j

j.(¶ L(x*,y*)/¶ xj) = x*j.( %

ii)

% ) = 0 nhiên đi u ki n x* ề ệ

* dL(x ) / dx j

= 0. Do đó ể

¶ = = - g (x*); i 1, 2,..., m b M t khác, vì ng t ặ , nên ch ng minh t ứ ươ ự ¶ Khi x*j > 0. Do x*j là đi m trong nên (¶ L(x*,y*)/¶ xj) = 0. * L y

i* = 0 ho c là, khi y ặ

i* > 0 thì L (yi

ể ế L (yi) = L(x*, y(i)) t là ự ấ ằ i y = y* thì đi u ki n c n thi ạ ề ế ầ ạ ¶ = - £ " g (x*) 0; b i và ho c là y ặ ¶ nh trên ta cũng th y r ng đ cho hàm tuy n tính ư đ t c c đ i t ạ ệ * L y

b) Đi u ki n đ ề

i(x) lõm trên G theo x. Đ t ặ j (x) = L(x, y*). Khi y ấ j (x) l

) = const. Do đó (d L (yi*)/dyi) = ¶ L(x*,y*)/¶ yi = 0. Trong đó y(i) = (y1*, …, y i-1*, yi, yj+1*,…, y n*). ệ ủ: Do f(x) l i, gồ iồ

Lê Văn Phi, Khoa Toan Thông kê,

ng Đai hoc Kinh tê Tp. Hô Chi Minh

ườ

¶ f ¶ = Æ j Ch ng I, ’(x*), x – x*æ £ j (x) - j (x*). Do ươ ¶ ¶ = {x/ x ‡ 0}, nên L(x, y) l i và kh vi. Theo Đlí 6.2, ả ồ L(x*, y*) (x*) x x

́ ́ ̣ ̣ ́ ̀ ́

Ly thuyêt Qui hoach tuyên tinh

́ ́ ̣ ́ ́

* j

= j 1

nên theo (2.14) thì ¶ £ - £ - " ‡ (cid:229) 0 .(x x ) L(x, y*) L(x*, y*), x 0 . Suy ra: ¶ L(x*, y*) x

" 0: L(x, y*) ‡ L(x*, y*)

x ‡ (2.16) (2.15) suy ra: ừ M t khác, t ặ " y ‡ 0: L(x*, y) = f(x*) +Æ y, b – g(x*)æ = L(x*, y*) f(x*) = f(x*) +Æ y*, b –g(x*)æ ể ự ủ ‡ {y/ y ‡ 0)}.ª 0)}· £ K t h p v i (2.16), (x*,y*) là đi m yên ng a c a hàm Lagrange trên ế ợ ớ mi n {x/ x ề

Các b t đ ng th c (2.14) – (2.15) g i là các ứ ấ ẵ ứ ọ ầ ả i bài toán QH l ‡ ấ ẵ c các tác gi Tucker, đ ượ r ng, vi c gi ả ệ ằ trên mi n {x/ x ề ố ầ ồ ơ ả 0)} tr thành vi c gi ệ B t đ ng th c Kuhn- công b l n đ u tiên năm 1951. T đây th y ấ ừ ng h p f(x), g i(x) kh viả ợ i các b t đ ng th c Kuhn-Tucker. ứ i c b n trong tr ả ườ ấ ẵ ở

Cũng t ch ng minh ừ ứ = Rn, các b t đ ng ấ ẵ th c Kuhn-Tucker s có d ng: ứ ẽ ế G Đlí 2.4 d th y r ng, n u ễ ấ ằ ở ạ

* L y

* y . i

i * L y

* i

(cid:236) ¶ ‡ 0 (cid:239) ¶ (cid:239) (cid:239) ¶ ¶ (cid:239) = = = 0, j 1, 2,..., n; (cid:237) 0 và , i = 1, 2,…,m. ¶ ¶ L * x (cid:239) (cid:239) ‡ y 0 (cid:239) (cid:239) (cid:238)

2.5 D ng hình h c c a Đ nh lý Kuhn-Tucker ọ ủ ạ ị

Đ trình bày d ng hình h c c a đ nh lý Kuhn-Tucker, ng v i x ạ ọ ủ ứ ướ ế

ấ i(x), i = 1, 2, …, m,(t ớ ˛ X ị i = gi(x)} ˝ {1, 2, …, m} và J(x) = c h t ta ký hi u: I(x) = {i / b ệ {1, 2, …, n}; gradgi(x) = g’i(x); gradf(x) = f’(x). Khi y I(x), ngươ ợ ậ ng ng f(x)). ể b t kỳ tr ấ {j / xj = 0}˝ J(x) là t p h p các m t biên c a X ch a x; -g ứ ặ ươ ứ ứ ủ ng -f(x) g i là đ i gradien c a g ố ủ i (x) (t ọ

-g’i(x*)

x* gi(x*) = bi

Lê Văn Phi, Khoa Toan Thông kê,

ng Đai hoc Kinh tê Tp. Hô Chi Minh

ườ

Hinh 2.3 ̀

́ ́ ̣ ̣ ́ ̀ ́

Ly thuyêt Qui hoach tuyên tinh

́ ́ ̣ ́ ́

Đlí 2.5: Trong tr ỏ ườ ợ ậ ề ầ i gi ả ử s ệ ề G ={x/ x ‡ 0)} thì đi u ki n c n và đ ủ ệ ố i x = x* đ i ồ ạ i sinh b i các đ i gradien i c a bài toán QH l ồ ề i (1.3) là t ở ố ng h p t p X th a mãn đi u ki n chính qui và gi f(x), g(x) kh vi trên mi n ả ˛ X* là l đ x*ể ờ gradien c a f(x) ph i ủ . c a các m t biên c a X ch a x* ặ ủ ả ủ ả n m trong nón l ằ ủ ứ

ệ ế ứ : N u X th a mãn đi u ki n chính qui thì t ề ỏ ấ ẵ các đ nh lý ị ừ ệ ầ

ứ ể ấ ẵ ả ủ ế ứ i c a bài toán QH l ồ ỏ

* j

* i

= i 1

i. Gi ỏ ấ J(x*) „ I(x*)¨ ˘ ằ ¶ ¶ ¶ ¶ " = ‡ (cid:229) 0; x 0 y = * j 1, 2,..., n : v j = * x .v j ¶ ¶ ¶ ¶ Ch ng minh 2.2, 2.3 và 2.4 suy ra các b t đ ng th c Kuhn-Tucker là đi u ki n c n và đ đ ủ ể ề ỉ ầ x* là l i (1.3). Đ ch ng minh Đlí 2.5 ch c n i gi ờ r ng n u (x*, y*) th a mãn các b t đ ng th c Kuhn-Tucker thì ch ng t ứ ứ ỏ ằ t ố i sinh b i các đ i i x = x* đ i gradien c a f(x) s n m trong nón l ở ồ ủ ố ạ ẽ ằ = xj, - ej, j˛ J(x*), v i eớ j gradien c a gủ i(x), - g’i(x), i˛ I(x*) và pj(x) = Æ ej, xæ s (x*, y*) c l = (0,…, 0, 1, 0,…,0) là vect đ n v th j và ng ả ử ượ ạ ị ứ ơ ơ ng h p: th a mãn các b t Kuhn-Tucker. Ta xét 2 tr ợ ườ . Khi y x* n m trên m t biên c a X. Theo (2.15) thì ặ a) L * = x ấ f * + x ủ L * = x g * i x

* j

* y ( i

= i 1

* g + - ) i x

¶ ¶ - - (cid:229) ( 1)v Suy ra , j = 1,2,…,n (2.17) ¶ ¶ f * = x

* i

* y ( i

= i 1

Tuy nhiên, v i jớ ˇ J(x*) thì xj* > 0, nên vj* = 0. Do đó (2.17) tr thành ở ¶ ¶ - - ˇ (cid:229) ); j J(x*) (2.18) ¶ ¶ f * = x g x

* y ( i

* ( 1)v ; k

k J ( x*)

= i 1

j K t h p (2.18) và (2.17) có th vi f * = x

j ể ế ạ * g + i x

t l i thành: ế ợ ¶ ¶ = - - - (cid:229) (cid:229) ) j 1, 2,..., n (2.19) ˛ ¶ ¶

i(x*) > bi thì theo (2.15), yi* = 0. Khi đó

* y ( i

I( x*)

k J ( x*)

* g + i x

ˇ I(x*), t c là g ứ ặ M t khác, khi i (2.19) tr thành ở ¶ ¶ - - - (cid:229) (cid:229) = ) ) ( 1)v ; j 1, 2,..., n ( = * k ˛ ˛ ¶ ¶ f * x

* i

* j

j J ( x*)

i* ‡

- - - (cid:229) (cid:229) = [ f '(x*)] + y [ g '(x*)] i ( e )v j T c là (2.20) ứ ˛ ˛

ớ ề 0, i = 1,2,…, m; j = 1,2,….,n, (2.20) i’(x*)], i˛ I(x*) và (-ej), ỏ i sinh b i các [-g ở 0, vj* ‡ ồ

intX, và n u các b t d ng th c ứ , thì x* ˛ ấ ẵ ứ ở ế

I ( x*) i K t h p v i đi u ki n y ế ợ ệ ch ng t [-f’(x*)] n m trong nón l ằ ứ j ˛ I(x*), t c là các m t biên ch a x*. ặ ứ b) Khi I(x*)¨ J(x*) = ˘ (2.15), j* = 0 và yi* = 0, j =1,2,…,n; i =1,2,…, m. Do f(x) khả (2.16) th a mãn thì v ỏ ¶ f(x*)/¶ xj) = 0; t cứ vi và nh n c c ti u t i x* nên di u ki n c n thi ậ ự là (-¶ f(x*)/¶ xj) = 0, j =1,2….,n. Hay [-f’(x*)] = 0. Nh v y (2.20) cũng th a ỏ mãn.

Lê Văn Phi, Khoa Toan Thông kê,

ng Đai hoc Kinh tê Tp. Hô Chi Minh

ườ

ể ạ ề ệ ế ầ t là ( ư ậ

́ ́ ̣ ̣ ́ ̀ ́

Ly thuyêt Qui hoach tuyên tinh

́ ́ ̣ ́ ́

ứ ủ ệ ằ Ch ng minh đi u ki n đ : Gi ề ồ s có (2.20), t c là [-f’(x*)] n m trong ứ ỉ ầ i sinh b i các đ i gradien c a các m t biên c a X ch a x*. Ch c n ứ ủ ở ố ả ử ủ ặ I(x*) ta có nón l thêm vj* = 0, jˇ J(x*) và yi* = 0, iˇ

* i

* j

= i 1

= j 1

- - - (cid:229) (cid:229) = [ f '(x*)] + y [ g '(x*)] i ( e )v j

* y ( i

* ( 1)v ; j

= i 1

* g + - ) i x

¶ ¶ = - - (cid:229) j 1, 2,..., n T c là ứ ¶ ¶ f * = x

* i

* j

* y ( i

= i 1

Hay ¶ ¶ ¶ = = + ‡ (cid:229) v ) 0 ; = j 1, 2,..., n ¶ ¶ ¶ g x

f * L * x x j* = (¶ L*/¶ xj) ‡ 0 và do j ˛ J(x*) thì xj* = 0, nên ậ

˛ X, nên (¶ L*/¶ yi) = bi – gi (x*) £

ứ ặ ỏ i gi 0, i = 1,2,…, m và khi ặ I(x*) thì bi – gi (x*) = 0, nên yi*.(¶ L*/¶ yi) = 0, i = 1,2,…,m. T c làứ Do đó c p (x*,y*) là ả i ờ ị i (1.3).ª V y v xj*.v j* = 0 ; j = 1,2,…,n M t khác, do x* i˛ (x*,y*) th a mãn các b t đ ng th c Kuhn-Tucker. ấ ẵ đi m yên ng a c a hàm Lagrange L(x,y). Theo đ nh ly 2.3 thì x* là l ự ủ ể c a bài toán QH l ồ ủ

2.6 Bài toán qui ho ch l i v i các ràng bu c tuy n tính ồ ớ ộ ế Bài toán Qui ho ch toàn ph ng ươ ạ ạ

i (x) =

= j 1

(cid:229) a x ij Xét bài toán QH l i (1.3) trong đó g , i = 1,2,…, m. ồ

j 1,2,...,n = i 1,2,..,m

là ma tr n th c m hàng, n c t cho tr c. Khi đó ự ộ ướ ậ

((a )) = i (1.3) tr thành bài toán: ở

x X

= f (x*) min f (x) Trong đó A = bài toán QH l ồ Tìm x* sao cho ˛

˛ ‡ ‡ (cid:229) x R / = 0, j 1, 2,..., n

}

= j 1

(2.21) v iớ X = { a x ij = b ,i 1, 2,..., m; x i

d ng ma tr n X đ c vi t thành: Ở ạ ậ ượ ế

X = {x˛ Rn/ Ax ‡ b} (2.22)

i(x) D th y r ng các ràng bu c xác đ nh X có d ng tuy n tính (các hàm g ị là các hàm tuy n tính, i = 1,2,…,m) nên bài toán (2.21) g i là bài toán QH l ồ ớ

Lê Văn Phi, Khoa Toan Thông kê,

ng Đai hoc Kinh tê Tp. Hô Chi Minh

ườ

ễ ấ ằ ế ạ ộ ế ọ i v i các ràng bu c ty n tính. ế ộ

́ ́ ̣ ̣ ́ ̀ ́

Ly thuyêt Qui hoach tuyên tinh

́ ́ ̣ ́ ́

t khi hàm f(x) có ng Đ c bi ặ ệ d ng toàn ph ạ ươ , t c là có d ng ứ ạ

2. Bài toán

f(x) = Æ p, xæ + Æ x, Qxæ ; (2.23)

trong đó Q là ma tr n vuông đ i x ng c p (2.21) đ ậ c g i là bài toán Qui ho ch toàn ph ố ứ ạ ấ n, xác đ nh không âm ị ươ . ng ượ ọ

= (cid:229) i / b

{

}

* j

= j 1

a x ij ˛ X b t kỳ, đ t I(x*) = V i x*ớ ấ ặ ; J(x) = {j / x*j = 0}; t cứ

¨ ợ ậ là I(x*), J(x*) là t p h p các m t biên c a X ch a x*. N u I(x*) ặ ứ ˘ ng s đ u ch p nh n đ ế ấ ậ ¨

ủ thì x* là đi m trong c a X, nên m i h ọ ướ J(x*) „ ạ ng s là ch p nh n đ ấ J(x*) = ượ ạ i c t ề ậ . Khi y b n đ c s ch ng minh trong bài t p ọ ẽ ứ i x* khi và ch khi ỉ ủ ˘ ấ c t ậ ượ ạ ể s I(x*) ả ử ướ x*. Gi r ng h ằ

= j 1

(cid:236) ‡ ˛ (cid:229) 0, i I(x*) (cid:239) a s ij (cid:237) (2.24) (cid:239) ‡ ˛ s 0; j J(x*) (cid:238)

= i 1

ứ ạ ớ Hàm Lagrange ng v i bài toán (2.21) có d ng L(x,y) = f(x) + Æ y, b - Axæ n = + - (cid:229) (cid:229) L(x, y) f (x) y (b i a x ) ij j (2.25) Hay

= j 1 ng v i bài toán (2.21) đ nh lý Kuhn-Tucker v n đúng mà không c n có ề

ầ ẫ ị Ứ đi u ki n chính qui. ớ ệ

ặ ả ủ ề ồ i gi i y* s f(x) kh vi trên X, xác đ nh theo (2.21) ho c (2.22). Khi đó, ị ệ ắ i c a bài toán QH l t ‡ 0, đ cho c p (x*, y*) là đi m yên ng a ự i (2.21) thì đi u ki n ể ể ặ Đlí 2.6: Gi ả ả ử ˛ X là l đ cho x* ờ ể có và đ là t n t ồ ạ ủ c a hàm Lagrange (2.25). ủ

: Do bài toán (2.21) ch là tr ứ ợ ặ ủ ỉ ứ ứ ườ c ch ng minh i gi ệ ư ờ ề ể ệ ự ủ ị i x*. ả ậ ng h p đ c bi t c a bài toán ệ ủ đ nh lý 2.2. Ta ch ng minh ở ị ượ i c a bài toán (2.21), t c là s x* là l ứ ả ủ ả ử ng I: i f(x) trên X. Khi y theo đ nh lý 4.3 ch ươ ấ i x* c t ng ch p nh n đ Do f kh vi t ấ ạ ượ ạ ượ ng s ch p nh n đ c . Do đó v i m i h ấ ọ ướ ớ ậ Ch ng minh (1.3), nên đi u ki n đ đã đ ề đi u ki n c n nh sau: Gi ầ đi m c c ti u c a hàm l ồ ể (¶ f(x*)/¶ s) ‡ 0, " s là h ướ nên //s//.(¶ f(x*)/¶ s) = Æ f’(x*), sæ i x*ạ t

" x˛ Rn: Æ x, Qxæ

ọ

Æ f’(x*), sæ ‡ 0 (2.26)

ng t

Rn, x„ 0:Æ x, Qxæ

> 0; Q là

ấ n g i là xác đ nh không âm khi ị ế " x˛ ng, n u

ươ xác đ nh âm, n u

ươ < 0.

0. T ị

2 Q là ma tr nậ vuông, đ i x ng c p , Q đ ự ế " x˛ Lê Văn Phi, Khoa Toan Thông kê,

ố ứ c g i là xác đ nh d ị ượ ọ Rn, x„ 0:Æ x, Qxæ Tr

ng Đai hoc Kinh tê Tp. Hô Chi Minh

ườ

‡

́ ́ ̣ ̣ ́ ̀ ́

Ly thuyêt Qui hoach tuyên tinh

́ ́ ̣ ́ ́

ấ ậ £

i x* ta có (2.24). Không gi m tính ả m; J(x*) ={1, 2, …, l}, l £ m. = 0, j = 1, 2, …, l . Trong đó Ai. là các c t Tuy nhiên, n u s là ch p nh n đ ế ượ ạ s I(x*) = {1, 2, …, k}, k t ng quát, gi ả ử ổ = bi, i =1,2,…, k; Æ ej, xæ Æ Ai., xæ T c là ứ hàng c a A. Đ t vect ủ ặ ơ

+ 1(l 1) ...

1n ...

11 ... a

1l ... ... ... a

k1 1

kl 0

+ k ( l 1) 0

kn 0

+ k 1 ... s

(cid:230) (cid:246) (cid:230) (cid:246) (cid:230) (cid:246) a a ... a ... a A 1. (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) ... A s 1 ... s a ... ... a (cid:231) (cid:247) = (cid:231) (cid:247) (cid:231) (cid:247) s B = = ; . s ... ... (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) e 1 (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) ... e ... 0 ... 1 ... ... ... 0 ... 0 ... ... Ł ł Ł ł Ł ł

Khi đó (2.24) tr thành ở

Tu; t c là f’(x*) n m trong nón l

Bs ‡ 0 (2.27) ị ‡ ứ ể ư ậ " s th a mãn (2.27) luôn luôn xãy ra (2.26). Theo đ nh lí Farkas ồ i 0, đ cho f’(x*) = B I(x*) và ej, j˛ J(x*). Đây là các gradien c a các m t biên ỏ i các u i., i˛ ặ Nh v y, s t n t ằ ẽ ồ ạ sinh b i các A ủ ở c a X ch a x*. T đ nh lý 2.5 suy ra đi u ph i ch ng minh. ª ủ ừ ị ứ ứ ề ả

ệ ạ ồ ớ ộ i v i ràng bu c Đi u ki n Kuhn-Tucker cho bài toán Qui ho ch l ): tuy n tính (bài toán (2.21) ề ế

Lê Văn Phi, Khoa Toan Thông kê,

ng Đai hoc Kinh tê Tp. Hô Chi Minh

ườ

ề i t i gi ầ i các y* ủ ấ ẵ ứ ứ ệ ả ỏ K t h p các đ nh lý 2.4 và 2.6, ta có đi u ki n c n và đ đ cho ủ ể ế ợ ị ệ ˛ Rm, v*˛ Rn, x*˛ Rn là l i u c a bài toán (2.21) là t n t ồ ạ ả ố ư ờ u*˛ Rm th a mãn các b t đ ng th c và đ ng th c sau đây, g i là các b t ấ ẵ ọ ứ ỏ đ ng th c Kuhn-Tucker (X không c n thi t ph i th a mãn đi u ki n chính ề ế ầ ẵ qui):

́ ́ ̣ ̣ ́ ̀ ́

Ly thuyêt Qui hoach tuyên tinh

́ ́ ̣ ́ ́

* i

= i 1

* x .v j

* j 0, v

* j

¶ (cid:236) - - (cid:229) 0 a y ij = * v j (cid:239) ¶ f (x*) x (cid:239) (cid:239) = (cid:237) 0 = j 1, 2,..., n ; (cid:239) ‡ ‡ x 0 (cid:239) (cid:239) (cid:238)

= j 1

* y .u i

* i 0, u

* i

(cid:236) - (cid:229) b u 0 a x ij + * j = * i (cid:239) (cid:239) = = (cid:237) 0 i 1, 2,..., m (cid:239) ‡ ‡ y 0 (cid:239) (cid:238)

t khi f(x) có d ng toàn ph ng (2.23) thì Đ c bi ặ ệ ạ ươ

= k 1

¶ = + (cid:229) p = q x ; j 1, 2,..., n ¶ f (x) x

Qui ho ch toàn ph ứ ề ớ ạ ươ ng Do v y đi u ki n Kuhn-Tucker ng v i bài toán ệ ậ i d ng ma tr n nh sau: d ậ ướ ạ ư

(2.28) P + Qx - ATy – v = 0 Ax – b – u = 0 + Æ y, uæ Æ x, væ = 0 0; u ‡ 0; y ‡ 0 x ‡ 0; v ‡

./.

Lê Văn Phi, Khoa Toan Thông kê,

ng Đai hoc Kinh tê Tp. Hô Chi Minh

ườ

ng tr ươ ạ ở ng trình và b t ph ươ ả ươ t đ ươ ệ ờ i thành vi c tìm l i bài toán Qui ho ch toàn ph ệ ng trình phi tuy n Kuhn – Tucker ế ấ ng trình và ng pháp h u hi u gi i h ph ươ ả ệ ữ ế ề t v ệ ả ị ạ ể ế ượ ng trình (2.28) đ ngh b n đ c tham kh o các tài li u vi ọ c các ph ề Khi y vi c gi ấ ệ i c a h ph gi ệ ả ủ (2.28). Đ bi b t ph ươ ấ qui ho ch phi tuy n. ế ạ

́ ́ ̣ ̣ ́ ̀ ́