VIN HN LM KHOA HÅC V CÆNG NGH VIT NAM
VIN TON HÅC
TRN VN THNG
ÈI NGU LIN HÑP CHO BI TON TÈI ×U
A MÖC TIU V ÙNG DÖNG
Chuy¶n ngnh: To¡n Ùng döng
M¢ sè: 62 46 01 12
TÂM TT LUN N TIN S TON HÅC
H NËI-NM 2014
Mð ¦u
Theo G. Dantzig, lþ thuy¸t èi ng¨u ÷ñc phäng o¡n bði J. V. Neu-
mann trong lþ thuy¸t trá chìi ngay sau khi G. Dantzig tr¼nh by c¡c v§n
· v· quy ho¤ch tuy¸n t½nh. N«m
1951
, mët chùng minh ¦y õ v· èi
ng¨u cho bi to¡n quy ho¤ch tuy¸n t½nh ¢ ÷ñc cæng bè l¦n ¦u bði A.
W. Tucker v nhâm cõa æng. Tø â lþ thuy¸t èi ng¨u ¢ trð trnh mët
ch÷ìng quan trång cõa lþ thuy¸t tèi ÷u, c£ v· ph÷ìng di»n lþ thuy¸t l¨n
t½nh to¡n v ùng döng thüc t¸ v thu hót nhi·u nh to¡n håc quan t¥m
nghi¶n cùu, trong â ¡ng chó þ l c¡c cæng tr¼nh cõa A. W. Tucker, R.
T. Rockafellar, Y. Sawaragi v ð Vi»t Nam l c¡c cæng tr¼nh cõa c¡c t¡c
gi£ Hong Töy, Ph¤m Húu S¡ch, inh Th¸ Löc, Phan Thin Th¤ch, Vô
Ngåc Ph¡t, Nguy¹n ành, ... Ban ¦u lþ thuy¸t èi ng¨u ÷ñc x¥y düng
cho c¡c bi to¡n tèi ÷u tuy¸n t½nh bði A. W. Tucker v nhâm cõa æng, sau
â c¡c nh to¡n håc ¢ mð rëng cho tr÷íng hñp phi tuy¸n, tèi ÷u a möc
ti¶u v c£ trong tèi ÷u a trà. Lþ thuy¸t èi ng¨u ÷ñc ÷a ra thüc sü câ
þ ngh¾a v câ nhi·u ùng döng khi nâ £m b£o ÷ñc èi ng¨u m¤nh. Tuy
nhi¶n, trong tr÷íng hñp têng qu¡t vi»c câ ÷ñc èi ng¨u m¤nh l r§t khâ
kh«n. Cho ¸n nay c¡c nh to¡n håc mîi ch¿ ÷a ra ÷ñc èi ng¨u m¤nh
cho mët sè lîp c¡c bi to¡n thäa m¢n mët sè i·u ki»n no â. ¢ câ
nhi·u k¸t qu£ quan trång v· èi ng¨u cho c¡c bi to¡n tèi ÷u, c¡c k¸t qu£
ny chõ y¸u câ ÷ñc düa tr¶n lþ thuy¸t èi ng¨u Lagrange v èi ng¨u
li¶n hñp düa vo c¡c ph²p bi¸n êi li¶n hñp nh÷ ph²p bi¸n êi li¶n hñp
1
Fenchel, ph²p bi¸n êi tüa li¶n hñp v mët sè ph²p bi¸n êi li¶n hñp kh¡c.
Vîi bi to¡n tèi ÷u væ h÷îng, c¡c nh to¡n håc ¢ thu ÷ñc èi ng¨u
m¤nh cho lîp c¡c bi to¡n tèi ÷u lçi bði èi ng¨u Lagrange hay èi ng¨u
Fenchel nh÷ c¡c k¸t cõa c¡c t¡c gi£: R. T. Rockafellar, H.W. Kuhn v A.
W. Tucker, H. Töy. Trong tr÷íng hñp bi to¡n tèi ÷u khæng lçi, mët sè
k¸t qu£ hay ÷ñc nâi ¸n l cõa Phan Thi¶n Th¤ch.
Vîi bi to¡n tèi ÷u a möc ti¶u, vi»c thu ÷ñc èi ng¨u m¤nh trð
n¶n khâ kh«n hìn. Cho ¸n nay c¡c ph÷ìng ph¡p chõ y¸u l düa tr¶n lþ
thuy¸t èi ng¨u Lagrange v èi ng¨u Fenchel b¬ng c¡ch væ h÷îng hâa
hm möc ti¶u hay nhóng bi to¡n ban ¦u vo trong lîp c¡c bi to¡n tèi
÷u ÷ñc nhi¹u bði c¡c tham sè. C¡c bi to¡n èi ng¨u ÷ñc x¥y düng bði
c¡c ph÷ìng ph¡p tr¶n th÷íng l bi to¡n tèi ÷u væ h÷îng hay tèi ÷u a
trà, do â sì ç èi ng¨u thu ÷ñc th÷íng l khæng èi xùng. Ngoi ra,
trong nhi·u k¸t qu£ º câ èi ng¨u m¤nh th¼ bi to¡n ban ¦u ph£i l bi
to¡n tèi ÷u lçi.
Trong lþ thuy¸t èi ng¨u li¶n hñp, bi to¡n èi ng¨u cõa mët bi to¡n
gèc trong khæng gian
X
:
max(min){f(x)|A⊂X}
÷ñc x¥y düng trong khæng gian èi ng¨u
X∗
:
max(min){g(p)|A∗⊂X∗},
trong â
g
l hm li¶n hñp cõa
f
v
A∗
l tªp li¶n hñp cõa
A
sao cho hai
bi to¡n li¶n quan ch°t ch³ vîi nhau, thº hi»n qua vi»c nghi¶n cùu bi
to¡n èi ng¨u s³ cung c§p thæng tin v· bi to¡n gèc hay º gióp cho vi»c
gi£i bi to¡n gèc d¹ dng hìn trong tr÷íng hñp tèt nh§t. Hi»n nay, èi
ng¨u li¶n hñp Fenchel ÷ñc sû döng mët c¡ch rëng r¢i v phê bi¸n trong
tèi ÷u lçi. èi vîi lîp c¡c bi to¡n têng qu¡t hìn, mët sè k¸t qu£ ÷ñc
kº ra ð ¥y l cõa Phan Thi¶n Th¤ch, t¡c gi£ ¢ ÷a ra èi ng¨u m¤nh
2
cho lîp c¡c bi to¡n tüa lçi düa tr¶n ph²p bi¸n êi tüa li¶n hñp cõa hm
f:Rn→R∪ {±∞}
÷ñc x¡c ành bði:
fH(p) =
−inf{f(x) : pTx≥1}
n¸u
p∈Rn\ {0}
−sup{f(x) : x∈Rn}
n¸u
p= 0.
C¡c k¸t qu£ ny ¢ ÷ñc cæng bè trong c¡c cæng tr¼nh ÷ñc nhi·u ng÷íi
bi¸t ¸n v ÷ñc nhi·u nh to¡n håc tr½ch d¨n. Ti¸p töc c¡c nghi¶n cùu
cõa m¼nh v· èi ng¨u li¶n hñp, n«m 2003, Phan Thi¶n Th¤ch ¡p döng
ph²p bi¸n êi tüa li¶n hñp d¤ng
f\(p) = 1
{sup{f(x) : pTx≤1, x ≥0}
(1)
cho lîp c¡c bi to¡n quy ho¤ch tuy¸n t½nh v ch¿ ra r¬ng bi to¡n èi ng¨u
cõa bi to¡n cüc ¤i mët hm tuy¸n t½nh khæng gi£m tr¶n tªp lçi trong
Rn
+
l bi to¡n s£n xu§t Leontief. Chó þ r¬ng, trong tr÷íng hñp tuy¸n t½nh,
bi to¡n èi ng¨u ÷ñc lªp bði lþ thuy¸t èi ng¨u Lagrange hay èi ng¨u
Fenchel l tròng nhau v công l bi to¡n quy ho¤ch tuy¸n t½nh. K¸t qu£
kh¡c bi»t ny gióp Phan Thi¶n Th¤ch ch¿ ra c¡c °c tr÷ng cho t½nh phi d÷
thøa trong bi to¡n s£n xu§t Leontief düa tr¶n mèi li¶n h» èi ng¨u giúa
nguy¶n li»u s£n xu§t v gi¡ nguy¶n li»u, ch¯ng h¤n nh÷ sü tçn t¤i gi¡ °c
tr÷ng º ÷a rng buëc ti nguy¶n v· rng buëc ìn gi£n hìn v· vèn s£n
xu§t. K¸t qu£ mð ¦u ny cán mð ra cho ta nhúng ùng döng rëng hìn.
Trong luªn ¡n ny, chóng tæi tr¼nh by mët sè k¸t qu£ mîi khi nghi¶n
cùu mð rëng sì ç èi ng¨u li¶n hñp düa tr¶n ph²p bi¸n êi tüa li¶n hñp
d¤ng (1) cho lîp c¡c bi to¡n rëng hìn bao gçm c¡c bi to¡n tèi ÷u væ
h÷îng v tèi ÷u a möc ti¶u phi tuy¸n, çng thíi ùng döng k¸t qu£ èi
ng¨u ¢ ¤t ÷ñc vo nghi¶n cùu mët sè bi to¡n trong kinh t¸. Luªn ¡n
bao gçm 3 ch÷ìng.
Ch÷ìng 1 "Ph²p bi¸n êi tüa li¶n hñp" nghi¶n cùu c¡c i·u ki»n °c
tr÷ng cho lîp hm thäa m¢n t½nh ph£n x¤ v âng k½n qua ph²p bi¸n
3
êi tüa li¶n hñp. K¸t qu£ ny gióp chóng ta thu ÷ñc t½nh èi xùng cõa
èi ng¨u cho c°p bi to¡n gèc-èi ng¨u s³ ÷ñc tr¼nh by trong ch÷ìng
2. Nhªn th§y c¡c hm tuy¸n t½nh khæng gi£m tr¶n
Rn
+
v hm s£n xu§t
Leontief ·u l nhúng tr÷íng hñp ri¶ng cõa lîp hm a di»n lãm thu¦n
nh§t d÷ìng v ìn i»u t«ng tr¶n
Rn
, chóng tæi ¢ chùng minh ÷ñc r¬ng
lîp hm ny thäa m¢n t½nh ph£n x¤, âng k½n qua ph²p bi¸n êi tüa li¶n
hñp v ¥y l sü mð rëng g¦n nh§t cho lîp hm tuy¸n t½nh ¢ ÷ñc x²t
tr÷îc â. Mët k¸t qu£ mð rëng hìn công ÷ñc ÷a ra khi chóng tæi chùng
minh ÷ñc r¬ng lîp c¡c hm nûa li¶n töc tr¶n, tüa lãm v ìn i»u t«ng
tr¶n
Rn
, l lîp hm têng qu¡t thäa m¢n t½nh ph£n x¤ èi vîi ph²p bi¸n
êi tüa li¶n hñp. Lîp c¡c hm ny bao hm ph¦n lîn c¡c hm s£n xu§t
trong c¡c mæ h¼nh kinh t¸, ch¯ng h¤n nh÷ c¡c hm s£n xu§t Leontief,
Cobb-Douglas, Leontief mð rëng, Cobb-Douglas mð rëng, ... Ch÷ìng ny
công ÷a ra kh¡i ni»m tüa d÷îi vi ph¥n v chùng minh mët sè t½nh ch§t
cõa tüa d÷îi vi ph¥n º phöc vö cho vi»c chùng minh c¡c k¸t qu£ v· èi
ng¨u ð c¡c ch÷ìng sau.
Ch÷ìng 2 "èi ng¨u li¶n hñp cho c¡c bi to¡n tèi ÷u" tr¼nh by i·u
ki»n c¦n v õ tèi ÷u d÷îi d¤ng mð rëng cõa nguy¶n lþ Fermat cho bi
to¡n tèi ÷u væ h÷îng. Tø nhúng k¸t qu£ mîi v· ph²p bi¸n êi tüa li¶n hñp
¢ tr¼nh by trong Ch÷ìng 1, chóng tæi ÷a ra sì ç èi ng¨u li¶n hñp cho
lîp c¡c bi to¡n tèi ÷u væ h÷îng v tèi ÷u a möc ti¶u vîi gi£ thi¸t möc
ti¶u l c¡c hm a di»n lãm, thu¦n nh§t d÷ìng, ìn i»u t«ng tr¶n
Rn
v
têng qu¡t hìn núa khi x²t vîi c¡c hm möc ti¶u ch¿ tüa lãm, li¶n töc v
ìn i»u t«ng ch°t tr¶n
Rn
+
. K¸t qu£, chóng ta thu ÷ñc èi ng¨u m¤nh,
èi xùng v bi to¡n èi ng¨u cõa bi to¡n tèi ÷u a möc ti¶u công l bi
to¡n tèi ÷u a möc ti¶u. Ngoi ra, chóng tæi cán ÷a ra ÷ñc ¯ng thùc
èi ng¨u gióp °c tr÷ng cho c°p nghi»m húu hi»u cõa c¡c bi to¡n tèi ÷u
a möc ti¶u gèc v èi ng¨u.
4