Tiến Sĩ Đối ngẫu liên hợp cho bài toán tối ưu đa mục tiêu và ứng dụng

L˝I CƒM ÌN
Lu“n ¡n ưæc ho n th nh dưîi sü hưîng d¤n t“n t nh, chu ¡o, ƒy
tr¡ch nhi»m cıa TS. Phan Thi¶n Th⁄ch v  GS. Ho ng Töy.
T¡c gi£ xin b y tä lÆng bi‚t ìn s¥u s›c ‚n thƒy Phan Thi¶n Th⁄ch
vã cæng lao Thƒy ¢ t“n t nh hưîng d¤n trong suŁt thíi gian t¡c gi£ l m
vi»c vîi Thƒy.
T¡c gi£ xin b y tä lÆng bi‚t ìn s¥u s›c ‚n thƒy Ho ng Töy, ngưíi
¢ ti‚p töc t“n t nh cæng vi»c hưîng d¤n v  gióp ï t¡c gi£ sau khi thƒy
Phan Thi¶n Th⁄ch bà Łm n°ng.
T¡c gi£ xin tr¥n trång c£m ìn PGS. TS. Trưìng Xu¥n øc H , GS.
TSKH. Vô Ngåc Ph¡t, GS. TSKH. L¶ Dông Mưu, PGS. TS. Bòi Th‚
T¥m, GS. TSKH. Nguy„n æng Y¶n, nhœng ngưíi ¢ luæn t“n t nh gióp
ï t¡c gi£ trong suŁt qu¡ tr nh håc Cao håc v  l m nghi¶n cøu sinh.
T¡c gi£ xin ch¥n th nh c£m ìn Ban l¢nh ⁄o Vi»n To¡n håc, Trung
t¥m  o t⁄o Sau ⁄i håc v  t“p th” c¡n bº cæng nh¥n vi¶n cıa Vi»n
To¡n håc ¢ t⁄o måi iãu ki»n thu“n læi cho t¡c gi£ trong thíi gian håc
Cao håc v  l m nghi¶n cøu sinh.
T¡c gi£ xin ch¥n th nh c£m ìn Ban hi»u trưðng trưíng ⁄i håc i»n
lüc, Ban l¢nh ⁄o Sð Gi¡o döc v   o t⁄o B›c Giang, trưíng THPT
BŁ H⁄, Y¶n Th‚, B›c Giang, c¡c thƒy cæ v  çng nghi»p ð trong trưíng
THPT BŁ H⁄ v  Khoa Khoa håc cì b£n trưíng ⁄i håc i»n lüc.
Xin c¡m ìn gia  nh, c¡c b⁄n nghi¶n cøu sinh v  b⁄n b– vã sü khuy‚n
kh‰ch, gióp ï t¡c gi£ trong qu¡ tr nh håc t“p v  nghi¶n cøu.
iiT´M TT
Lu“n ¡n n y tr nh b y mºt sŁ k‚t qu£ vã Łi ng¤u li¶n hæp cho c¡c
b i to¡n tŁi ưu væ hưîng v  tŁi ưu a möc ti¶u v  ¡p döng c¡c k‚t qu£
Łi ng¤u n y ” nghi¶n cøu mºt sŁ b i to¡n trong kinh t‚. Lu“n ¡n bao
gçm 3 chưìng.
Trong Chưìng 1, chóng tæi 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 Œi tüa li¶n
hæp, ư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.
Trong Chưìng 2, chóng tæi tr nh b y lþ thuy‚t Łi ng¤u li¶n hæp cho
c¡c b i to¡n tŁi ưu væ hưîng v  tŁi ưu a möc ti¶u.
Trong Chưìng 3, chóng tæi øng döng sì ç Łi ng¤u li¶n hæp ” nghi¶n
cøu mºt sŁ b i to¡n trong kinh t‚ như sau: b i to¡n vîi mºt r ng buºc
ph¥n bŁ nguçn lüc, b i to¡n vîi nhiãu r ng buºc ph¥n bŁ nguçn lüc v 
b i to¡n tŁi ưu khæng lçi vîi c¡c r ng buºc ph¥n bŁ nguçn lüc.
iiiABSTRACT
This thesis is devoted to the study of conjugate duality in scalar and
multiobjective optimization problems. The obtained results are applied
to study some optimization problems in economy.
The thesis consists of three chapters.
In Chapter 1 necessary and sufficient conditions are established for
the reflexivity and closedness of the quasi-conjugate transformation. Also
the concept of quasi-subgradient is introduced and some basic properties
of quasi-subgradient are proved.
In Chapter 2 the conjugate duality for scalar and multiobjective op-
timization problems is studied.
In Chapter 3 we apply the conjugate duality scheme to production
planning and optimization problems with one or multiple resource allo-
cation constraints
ivMöc löc
Möc löc 1
Mºt sŁ kþ hi»u 3
Mð ƒu 4
1 Ph†p bi‚n Œi tüa li¶n hæp 10
1.1 Mºt sŁ ki‚n thøc chu'n bà . 10
1.2 Ph†p bi‚n Œi tüa li¶n hæp . 16
1.3 Tüa dưîi vi ph¥n 29
2 Łi ng¤u li¶n hæp cho c¡c b i to¡n tŁi ưu 35
2.1 Łi ng¤u li¶n hæp cho b i to¡n tŁi ưu væ hưîng . 36
2.2 Łi ng¤u li¶n hæp cho b i to¡n tŁi ưu a möc ti¶u 43
3 Ùng döng 57
3.1 B i to¡n vîi mºt r ng buºc ph¥n bŁ nguçn lüc . 58
13.2 B i to¡n vîi r ng buºc ph¥n bŁ nhiãu nguçn lüc . 63
3.3 TŁi ưu vîi c¡c r ng buºc ph¥n bŁ nguçn lüc . 67
3.4 Quy ho⁄ch hai c§p v  tŁi ưu ìn i»u . 73
K‚t lu“n 77
Danh möc cæng tr nh cıa t¡c gi£ li¶n quan ‚n lu“n ¡n 78
T i li»u tham kh£o 79
2Mºt sŁ kþ hi»u
R t“p c¡c sŁ thüc
R
+ t“p sŁ thüc khæng
N t“p c¡c sŁ tü nhi¶n
R
n khæng gian Euclide nưchiãu
R
n
+ t“p c¡c v†ctì khæng ¥m nưchiãu
R
n
++ t“p c¡c v†ctì dưìng nưchiãu
a
T
x t‰ch væ hưîng cıa hai v†ctì trong R
n
kxk chu'n cıa x ∈ R
n
{x
n } d¢y sŁ thüc hay d¢y v†ctì
N(x, X) nân v†ctì ph¡p tuy‚n cıa t“p X t⁄i i”m x
∇f(x) gradient cıa f t⁄i x
∂f(x) dưîi vi ph¥n
∂
\
f(x) tüa dưîi vi ph¥n
intX phƒn trong cıa t“p X
cl(X) bao âng cıa t“p X
conv(X) bao lçi cıa t“p X
co(X) bao nân lçi cıa t“p X
M tŒng trüc ti‚p
X E t“p nghi»m hœu hi»u cıa b i to¡n tŁi ưu v†ctì
argmax{f(x) : x ∈ X} t“p c¡c i”m cüc ⁄i cıa h m f(x) tr¶n t“p X
f
\ h m tüa li¶n hæp cıa f
F : X ⇒ Y ¡nh x⁄ a trà tł X v o Y
3Mð ƒu
Theo G. Dantzig, lþ thuy‚t Łi ng¤u ưæc phäng o¡n bði J. V.
Neumann 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 ([18]). 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 ([6]). 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 ([6], [9]), R. T. Rockafellar ([15]), Y. Sawaragi ([17], [20])
v  ð Vi»t Nam l  c¡c cæng tr nh cıa c¡c t¡c gi£ Ho ng Töy ([3]), Ph⁄m
Hœu S¡ch ([16]), inh Th‚ Löc ([10]), Phan Thi¶n Th⁄ch ([21]-[27]), Vô
Ngåc Ph¡t ([14]), Nguy„n ành ([5]), . 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
4ng¤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 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 ([15]), H.W. Kuhn
v  A. W. Tucker ([9]), Ho ng Töy ([3]). 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 P. T. Thach ([21],
[22], [23]), [24]).
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 ([8],
[17]). 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 ([17], [19], [20]).
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,
5Ł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 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 : R
n → R ∪ {±∞} ưæc x¡c ành bði:
f
H
(p) =



ư inf{f(x) : p T x ≥ 1} n‚u p ∈ R
n \ {0}
ư sup{f(x) : x ∈ R
n } 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 ([21], [22], [23], [24]) 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) : p T x ≤ 1, x ≥ 0}
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 R
n
+ 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, chflng 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£ v  øng döng cıa sì ç Łi ng¤u n y
øng vîi trưíng hæp tuy‚n t‰nh ¢ ưæc cæng bŁ trong [2] v  [25]. 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 ¢ ưæc tr nh b y trong c¡c b i b¡o [2] v  [25] cho lîp c¡c b i to¡n
6rº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
Œ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 R
n
+ 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 R
n , 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 R
n
+ 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‚, chflng h⁄n như c¡c h m s£n xu§t
Leontief, Cobb-Douglas, Leontief mð rºng, Cobb-Douglas mð rºng ([4],
[7]), 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 nguy¶n lþ Fermat mð rºng 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
R
n
+ 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
7