Tài liệu Tóm tắt luận án tiến sĩ toán học đối ngẫu liên hợp cho bài toán tối ưu đa mục tiêu và ứng dụng

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 TT 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. 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. 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 Thi¶n 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:  − inf{f (x) : pT x ≥ 1} n¸u p ∈ Rn \ {0} H f (p) = − 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 1 (1) f \ (p) = {sup{f (x) : pT 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 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 Ch÷ìng 3 "Ùng döng" tr¼nh b y ùng döng sì ç èi ng¨u li¶n hñp v o nghi¶n cùu mët sè b i to¡n s£n xu§t trong kinh t¸. Nhí èi ng¨u li¶n hñp chóng tæi chùng minh ÷ñc b i to¡n t¼m ph÷ìng ¡n s£n xu§t vîi mët r ng buëc ph¥n bè nguçn lüc (b i to¡n gi£i h» phi tuy¸n) t÷ìng ÷ìng vîi b i to¡n cüc ¤i mët h m lãm ch°t tr¶n mët a di»n lçi. i·u n y gióp ch¿ ra r¬ng b i to¡n vîi mët r ng buëc ph¥n bè nguçn lüc câ mët nghi»m duy nh§t v  ÷ñc gi£i bði b i to¡n tèi ÷u lçi ìn gi£n hìn. B i to¡n mð rëng t¼m ph÷ìng ¡n s£n xu§t vîi k (k > 1) r ng buëc ph¥n bè nguçn lüc t÷ìng ÷ìng vîi b i to¡n tèi ÷u a möc ti¶u vîi c¡c möc ti¶u l  c¡c h m s£n xu§t Cobb-Douglas, k¸t qu£ n y gióp chóng ta quy mët lîp c¡c 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 v· b i to¡n tèi ÷u tr¶n tªp nghi»m húu hi»u Pareto cõa mët b i to¡n tèi ÷u a möc ti¶u. B i to¡n ÷ñc quy v· ¢ ÷ñc nhi·u t¡c gi£ quan t¥m nghi¶n cùu v  câ thº ÷ñc gi£i bði mët sè thuªt to¡n ¢ bi¸t. B¬ng ph÷ìng ph¡p ti¸p cªn cõa P. T. Th¤ch, H. Konno v  D. Yokota, chóng tæi quy b i to¡n tèi ÷u tr¶n tªp nghi»m húu hi»u Pareto v· b i to¡n cüc ¤i h m tüa lçi tr¶n mët tªp lçi comp­c trong Rk+ v  do â ta câ thº gi£i b i to¡n n y b¬ng ph÷ìng ph¡p x§p x¿ ngo i. Vîi ph÷ìng ph¡p ti¸p cªn kh¡c, düa tr¶n quy ho¤ch hai c§p v  lþ thuy¸t tèi ÷u ìn i»u cõa Ho ng Töy, chóng tæi ch¿ ra b i to¡n tèi ÷u vîi c¡c r ng buëc ph¥n bè nguçn lüc t÷ìng ÷ìng vîi mët b i to¡n cì b£n cõa tèi ÷u ìn i»u. C¡c k¸t qu£ trong luªn ¡n ¢ ÷ñc b¡o c¡o v  th£o luªn t¤i: - Hëi nghà Tèi ÷u v  T½nh to¡n khoa håc, Ba V¼, H  Nëi (2010). - Hëi nghà Tèi ÷u v  T½nh to¡n khoa håc, Ba V¼, H  Nëi (2011). - ¤i hëi To¡n håc to n quèc, Nha Trang, Kh¡nh Háa (2013). - Seminar cõa Pháng Tèi ÷u v  i·u khiºn, Vi»n To¡n håc, Vi»n H n l¥m Khoa håc v  Cæng ngh» Vi»t Nam. 5 - Hëi nghà nghi¶n cùu sinh h ng n«m t¤i Vi»n To¡n håc, Vi»n H n l¥m Khoa håc v  Cæng ngh» Vi»t Nam. C¡c k¸t qu£ ch½nh cõa luªn ¡n ¢ ÷ñc cæng bè ð t¤p ch½ Journal of Mathematical Analysis and Applications, t¤p ch½ Journal of Global Optimization v  mët b i b¡o ¢ ÷ñc gûi «ng. 6 Ch÷ìng 1 Ph²p bi¸n êi tüa li¶n hñp Ð ch÷ìng n y, sau mët sè ki¸n thùc chu©n bà, chóng tæi tr¼nh b y c¡c k¸t qu£ ¢ ¤t ÷ñc v· i·u ki»n º mët h m thäa m¢n t½nh ph£n x¤ v  chùng minh mët sè t½nh ch§t cõa tüa d÷îi vi ph¥n. Nëi dung cõa Ch÷ìng n y düa tr¶n c¡c b i b¡o [1] v  [3] trong danh möc c¡c cæng tr¼nh cõa t¡c gi£. 1.1 Mët sè ki¸n thùc chu©n bà 1.2 Ph²p bi¸n êi tüa li¶n hñp Ph¦n n y, chóng tæi ÷a ra mët sè k¸t qu£ v· ph²p bi¸n êi tüa li¶n hñp cõa h m f . Tø ¥y cho ¸n h¸t ch÷ìng ta luæn gi£ thi¸t r¬ng f (x) l  h m sè khæng ¥m, nhªn gi¡ trà húu h¤n tr¶n Rn+ v  f (x) > 0 ∀x > 0. ành ngh¾a 1.2.1. H m f \ ÷ñc gåi l  tüa li¶n hñp cõa f n¸u f \ (p) = 1 sup{f (x) : pT x 7 ≤ 1, x ≥ 0} ∀p ∈ Rn+ 1 (quy ÷îc +∞ = 0). M»nh · 1.2.2. Cho x ∈ Rn+ v  p ∈ Rn+. N¸u pT x ≤ 1, th¼ (1.1) f (x)f \ (p) ≤ 1. ành ngh¾a 1.2.4. H m sè f ÷ñc gåi l  câ t½nh ph£n x¤ èi vîi ph²p bi¸n êi tüa li¶n hñp n¸u (f \)\ = f , ngh¾a l : f (x) = 1 ∀x ∈ Rn+ . \ T sup{f (p) : p x ≤ 1, p ≥ 0} ành lþ 1.2.6. N¸u f l  h m lãm a di»n, thu¦n nh§t d÷ìng v  ìn i»u t«ng tr¶n Rn, th¼ h m tüa li¶n hñp cõa f công l  h m lãm a di»n, thu¦n nh§t d÷ìng v  ìn i»u t«ng tr¶n Rn. Hìn núa, (f \)\ = f . K¸t qu£ ÷ñc ph¡t biºu trong ành lþ 1.2.6 l  sü mð rëng cõa ph²p bi¸n êi tüa li¶n hñp cho lîp h m tuy¸n t½nh v  ÷ñc tr¼nh b y ð b i b¡o [1] trong danh möc c¡c cæng tr¼nh cõa t¡c gi£. M»nh · 1.2.8. H m f \ l  tüa lãm v  ìn i»u t«ng tr¶n Rn+. ành lþ sau cho ta i·u ki»n têng qu¡t º mët h m sè thäa m¢n t½nh ph£n x¤ qua ph²p tüa li¶n hñp. ành lþ 1.2.10. N¸u f l  h m tüa lãm, nûa li¶n töc tr¶n v  ìn i»u t«ng tr¶n Rn+, th¼ f câ t½nh ph£n x¤ qua ph²p bi¸n êi tüa li¶n hñp. M»nh · 1.2.11. N¸u f li¶n töc tr¶n Rn+, th¼ f \ nûa l¶n töc tr¶n t¤i måi p ≥ 0 v  nûa li¶n töc d÷îi t¤i måi p > 0. Kþ hi»u Fγ v  F ∗γ t÷ìng ùng l  c¡c tªp mùc tr¶n cõa f v  f \ t¤i γ > 0. M»nh · 1.2.12. Cho f l  h m li¶n töc, tüa lãm v  ìn i»u t«ng ch°t tr¶n Rn+. Khi â, vîi måi γ > 0 sao cho Fγ 6= ∅, F ∗ v  Fγ l  li¶n hñp tr¶n cõa nhau. 1 γ 8 1.3 Tüa d÷îi vi ph¥n Trong ph¦n n y, º x¥y düng i·u ki»n tèi ÷u cho b i to¡n tèi ÷u khæng lçi, chóng tæi ÷a ra kh¡i ni»m tüa d÷îi gradient v  chùng minh mët sè t½nh ch§t phöc vö cho vi»c thi¸t lªp c¡c k¸t qu£ trong c¡c ch÷ìng sau. ành ngh¾a 1.3.1. V²ctì p ∈ Rn+ ÷ñc gåi l  tüa d÷îi gradient cõa f t¤i x n¸u pT x = 1 v  f (x)f \ (p) ≥ 1. Tªp gçm c¡c tüa d÷îi gradient cõa f t¤i x ÷ñc gåi l  tüa d÷îi vi ph¥n cõa f t¤i x, kþ hi»u bði ∂ \f (x). ành lþ 1.3.3. Cho f li¶n töc, tüa lãm v  ìn i»u t«ng ch°t tr¶n Rn+. Khi â, ∂ \f (x) l  tªp lçi kh¡c réng t¤i måi x > 0. Ngo i ra, p ∈ ∂ \ f (x) ⇔ x ∈ ∂ \ f \ (p). M»nh · 1.3.4. N¸u f l  h m li¶n töc, tüa lãm, ìn i»u t«ng ch°t tr¶n Rn+ , th¼ i·u ki»n õ º p ∈ ∂ \f (x) l  pT x = 1 v  pT z ≥ 1 ∀z ∈ Ff (x). M»nh · 1.3.5. Cho f l  h m li¶n töc, tüa lãm v  ìn i»u t«ng ch°t tr¶n Rn+. Khi â, vîi måi x > 0 chóng ta câ −p ∈ ∂(−f (x)) \ {0} ⇒ 1 p ∈ ∂ \ f (x), T p x trong â ∂(−f (x)) l  tªp d÷îi vi ph¥n cõa −f t¤i x. M»nh · 1.3.7. Cho f l  h m li¶n töc, tüa lãm v  ìn i»u t«ng ch°t tr¶n Rn+. N¸u f kh£ vi t¤i x > 0 thäa m¢n ∇f (x) 6= 0, th¼ 1 T ∇f (x) x ∇f (x) ∈ ∂ \ f (x), trong â ∇f (x) l  gradient cõa f t¤i x. 9 Ch÷ìng 2 èi ng¨u li¶n hñp cho c¡c b i to¡n tèi ÷u Ch÷ìng n y tr¼nh b y sì ç èi ng¨u li¶n hñp cho c¡c b i to¡n tèi ÷u khæng lçi bao gçm c¡c b i to¡n tèi ÷u væ h÷îng v  tèi ÷u a möc ti¶u. C¡c ành lþ èi ng¨u y¸u v  m¤nh công ÷ñc ÷a ra còng vîi c¡c ¯ng thùc °c tr÷ng cho c°p nghi»m cõa c¡c b i to¡n tèi ÷u. Nëi dung cõa Ch÷ìng n y düa tr¶n c¡c b i b¡o [1] v  [3] trong danh möc c¡c cæng tr¼nh cõa t¡c gi£. 2.1 èi ng¨u li¶n hñp cho b i to¡n tèi ÷u væ h÷îng Trong ph¦n n y, chóng tæi ÷a ra i·u ki»n c¦n v  õ tèi ÷u d÷îi d¤ng nguy¶n lþ Fermat mð rëng v  èi ng¨u cho b i to¡n tèi ÷u væ h÷îng sau ¥y. max{f (x) : x ∈ X}, (2.1) trong â f l  h m li¶n töc, tüa lãm, ìn i»u t«ng ch°t, húu h¤n, khæng ¥m tr¶n Rn+; X l  tªp chu©n t­c, lçi, comp­c vîi ph¦n trong kh¡c réng 10 trong Rn+. ành lþ 2.1.2. i·u ki»n c¦n v  õ º x ∈ X l  nghi»m tèi ÷u cõa b i to¡n (2.1) l  0 ∈ ∂ \ f (x) − N (x, X). (2.2) K½ hi»u P l  li¶n hñp d÷îi cõa X . B i to¡n èi ng¨u cõa b i to¡n (2.1) ÷ñc ành ngh¾a nh÷ sau: max{f \ (p) : p ∈ P }. (2.3) V¼ X v  P l  li¶n hñp d÷îi cõa nhau çng thíi f thäa m¢n t½nh ph£n x¤, n¶n b i to¡n (2.1) công l  b i to¡n èi ng¨u cõa (2.3). i·u n y câ ngh¾a l  sì ç èi ng¨u m  chóng ta ÷a ra thäa m¢n t½nh èi xùng. ành lþ 2.1.8. Vîi måi x ∈ X v  p ∈ P ta câ f (x)f \(p) ≤ 1. èi ng¨u m¤nh ÷ñc ph¡t biºu trong ành lþ sau. ành lþ 2.1.9. Cho x ∈ X v  p ∈ P . Khi â, x l  nghi»m tèi ÷u cõa (2.1) v  p l  nghi»m tèi ÷u cõa (2.3) n¸u v  ch¿ n¸u f (x)f \ (p) = 1. (2.4) Nhªn x²t 2.1.10. ành lþ èi ng¨u m¤nh cho c°p b i to¡n (2.1) v  (2.3) trong tr÷íng hñp f l  h m a di»n, lãm, thu¦n nh§t d÷ìng v  ìn i»u t«ng tr¶n Rn+ ¢ ÷ñc chóng tæi chùng minh mët c¡ch ìn gi£n hìn trong b i b¡o [1] trong danh möc c¡c cæng tr¼nh cõa t¡c gi£. Tø k¸t qu£ cõa ành lþ 2.1.9, chóng ta câ thº nâi (2.4) l  ¯ng thùc èi ng¨u cho c¡c b i to¡n (2.1) v  (2.3). Do â, chóng ta câ èi ng¨u m¤nh cho lîp b i to¡n tèi ÷u khæng lçi (2.1) ¢ x²t. H» qu£ 2.1.11. Cho x ∈ X v  p ∈ P . Khi â, x l  nghi»m tèi ÷u cõa (2.1) v  p l  nghi»m tèi ÷u cõa (2.3) n¸u v  ch¿ n¸u p ∈ ∂ \ f (x). 11 2.2 èi ng¨u li¶n hñp cho b i to¡n tèi ÷u a möc ti¶u max(f1 (x), f2 (x), ..., fk (x)) (2.5) x ∈ X. trong â fi : Rn → R; X l  mët tªp con trong Rn. Gi£ sû Rn l  t½ch · c¡c cõa c¡c khæng gian Rn , i = 1, 2, ..., k (k ≥ 1) i n R = k Y R ni , i=1 trong â n = i=1 ni v  ni ≥ 1 i = 1, 2, ..., k. °t x = (x1, x2, ..., xk ), trong â xi ∈ Rn+ vîi måi i = 1, 2, ..., k. Tø ¥y cho ¸n h¸t ch÷ìng, chóng ta luæn x²t b i to¡n (2.5) vîi gi£ thi¸t fi(x) = fi(xi), fi l  h m húu h¤n tr¶n Rn+ thäa m¢n t½nh li¶n töc, tüa lãm, ìn i»u t«ng, thu¦n nh§t v  fi(xi) > 0 ∀xi ∈ Rn++, i = 1, 2, ..., k; X l  tªp chu©n t­c, lçi, comp­c câ ph¦n trong kh¡c réng trong Rn+. V¼ fi li¶n töc ð tr¶n Rn+ vîi måi i = 1, 2, ..., k v  X l  tªp comp­c n¶n b i to¡n (2.5) câ nghi»m húu hi»u. Pk i i i i B i to¡n èi ng¨u cõa (2.5) ÷ñc ành ngh¾a bði (2.6) max(f1\ (p1 ), f2\ (p2 ), ..., fk\ (pk )) p = (p1 , p2 , ..., pk ) ∈ P, pi ∈ Rn+i , i = 1, 2, ..., k, trong â fi\ l  h m tüa li¶n hñp cõa fi tr¶n Rn+ vîi måi i = 1, 2, ..., k v  P l  li¶n hñp d÷îi cõa X. B i to¡n èi ng¨u l  gi£i ÷ñc v¼ fi\ nûa li¶n töc i 12 tr¶n ð tr¶n Rn+ vîi måi i = 1, 2, ..., k v  P comp­c. Do X công l  li¶n hñp d÷îi cõa P v  fi ph£n x¤ vîi måi i = 1, 2, ..., k, n¶n sì ç èi ng¨u cho b i to¡n tèi ÷u a möc ti¶u l  èi xùng. i ành lþ 2.2.10. Vîi måi x ∈ X v  p ∈ P , chóng ta câ k X fi (xi )fi\ (pi ) ≤ 1. (2.7) i=1 M»nh · 2.2.11. Cho x ∈ X v  p ∈ P . N¸u c°p (x, p) thäa m¢n ¯ng thùc k X fi (xi )fi\ (pi ) = 1, (2.8) i=1 th¼ x l  nghi»m húu hi»u y¸u Pareto cõa (2.5) v  p l  nghi»m húu hi»u y¸u Pareto cõa (2.6). Chóng ta câ ành lþ èi ng¨u m¤nh sau. ành lþ 2.2.14. N¸u x l  nghi»m húu hi»u y¸u Pareto cõa (2.5), th¼ tçn t¤i v²ctì p ∈ P sao cho (x, p) thäa m¢n ¯ng thùc (2.8). T÷ìng tü, n¸u p l  nghi»m húu hi»u y¸u Pareto cõa (2.6), th¼ tçn t¤i v²ctì x ∈ X sao cho (x, p) thäa m¢n ¯ng thùc (2.8). Nhªn x²t 2.2.15. Trong tr÷íng hñp fi l  h m a di»n, lãm, thu¦n nh§t v  ìn i»u t«ng tr¶n Rn vîi måi i = 1, 2, ..., k, th¼ ành lþ 2.2.14 câ thº ÷ñc chùng minh ch¿ düa tr¶n c¡c cæng cö cõa Gi£i t½ch lçi. i K¸t qu£ cõa ành lþ 2.2.14 v  M»nh · 2.2.11 ch¿ ra r¬ng (2.8) l  ¯ng thùc èi ng¨u gióp °c tr÷ng cho c°p nghi»m húu hi»u y¸u Pareto cho c¡c b i to¡n tèi ÷u a möc ti¶u (2.5) v  (2.6). Do â, ành lþ 2.2.14 ÷ñc xem l  ành lþ èi ng¨u m¤nh cõa c¡c b i to¡n tèi ÷u a möc ti¶u n y. 13 Ch÷ìng 3 Ùng döng Trong ch÷ìng n y, chóng tæi ùng döng sì ç èi ng¨u li¶n hñp ÷ñc tr¼nh b y trong Ch÷ìng 2 º nghi¶n cùu mët sè b i to¡n s£n xu§t trong kinh t¸. Nëi dung cõa ch÷ìng n y düa tr¶n b i b¡o [2] trong danh möc c¡c cæng tr¼nh cõa t¡c gi£. 3.1 B i to¡n vîi mët r ng buëc ph¥n bè nguçn lüc Cho m v²ctì ai ∈ Rn++, αji i = 1, . . . , m v  α ∈ Rn+ sao cho > 0 ∀j = 1, . . . , n; n X j=1 14 αj = 1. (3.1) X²t b i to¡n t¼m c¡c v²ctì x ∈ Rn+ v  p ∈ Rn+, thäa m¢n h» c¡c ¯ng thùc v  b§t ¯ng thùc sau: x= m X i θi a , θi ≥ 0 i = 1, 2, . . . , m, i=1 m X θi = 1, i=1 T i pj ≥ 0 j = 1, 2, . . . , n, p a ≤ 1 i = 1, 2, . . . , m, pj xj = αj j = 1, 2, . . . , n. (3.2) (3.3) (3.4) B i to¡n n y câ thº g°p trong vi»c lªp k¸ ho¤ch ho¤t ëng cõa mët cæng ty câ m nh  m¡y º s£n xu§t n h ng ho¡ kh¡c nhau. º s£n xu§t c¡c h ng ho¡ n y, mët nguçn lüc nh§t ành câ têng b¬ng 1 ÷ñc ph¥n bè cho c¡c nh  m¡y. Gi£ sû ai, minj=1,...,n aij > 0 l  v²ctì °c tr÷ng cho n«ng lüc cõa nh  m¡y thù i, ngh¾a l  nh  m¡y thù i ch¤y h¸t cæng su§t câ thº s£n xu§t ÷ñc aij ìn và h ng hâa thù j , j = 1, . . . , n. Sè pj biºu thà ph¦n nguçn lüc ÷ñc ph¥n bè cho vi»c s£n xu§t mët ìn và h ng hâa thù j v  xj l  têng l÷ñng h ng hâa thù j c¦n s£n xu§t bði c£ cæng ty. Khi â, pj xj l  têng nguçn lüc ÷ñc ph¥n bè cho vi»c s£n xu§t h ng hâa thù j , tùc l  gi¡ vèn s£n xu§t l÷ñng h ng hâa thù j . º £m b£o kh£ n«ng c¤nh tranh tr¶n thà tr÷íng, c¦n thi¸t r¬ng pj xj = αj , j = 1, . . . , n, trong â α1, . . . , αn l  c¡c sè cho tr÷îc. B i to¡n °t ra l  t¼m mët ph÷ìng ¡n ho¤t ëng kh£ thi, tùc l  t¼m mët v²ctì (x, p) ∈ Rn+ × Rn+, thäa m¢n h» (3.2)-(3.4). V²ctì α ÷ñc gåi l  v²ctì ph¥n bè nguçn lüc. Kþ hi»u X l  tªp c¡c v²ctì x ∈ Rn+, thäa m¢n (3.2) v  P l  tªp c¡c v²ctì p ∈ Rn+, thäa m¢n (3.3). D¹ th§y c£ X v  P l  c¡c mi·n lçi a di»n. Nghi»m cõa h» (3.2)-(3.4) l  c¡c v²ctì (x, p) ∈ X × P , thäa m¢n c¡c ¯ng thùc (3.4). V¼ (3.4) l  c¡c ¯ng thùc phi tuy¸n, n¶n (3.2)-(3.4) l  h» phi tuy¸n. i·u n y d¨n ¸n vi»c gi£i h» n y l  khæng ìn gi£n. Sau ¥y, ta s³ ch¿ ra r¬ng h» (3.2)-(3.4) t÷ìng ÷ìng vîi mët b i to¡n tèi ÷u lçi. Ngo i ra, ta cán ch¿ ra r¬ng h» n y câ mët líi gi£i duy nh§t (x, p) ∈ X × P . 15 °t f (x) = n Y α xj j , j=1 g(p) = n Y α pj j . (3.5) j=1 X²t c¡c b i to¡n max{f (x) : x ∈ X}, max{g(p) : p ∈ P }. (3.6) (3.7) Vîi x > 0 v  p > 0, °t 1 ∇f (x), ∇f (x)T x 1 ˜ ∇g(p) = ∇g(p), ∇g(p)T p ˜ (x) = ∇f trong â ∇f (x) l  gradient cõa f t¤i x, ∇g(p) l  gradient cõa g t¤i p. ành lþ sau cho th§y r¬ng c¡c b i to¡n (3.6) v  (3.7 ) l  èi ng¨u cõa nhau. ˜ (x) l  nghi»m ành lþ 3.1.3. N¸u x l  nghi»m cõa b i to¡n (3.6), th¼ ∇f ˜ cõa (3.7). £o l¤i, n¸u p l  nghi»m cõa (3.7), th¼ ∇g(p) l  nghi»m cõa b i to¡n (3.6). ành lþ 3.1.4. N¸u (x, p) l  nghi»m cõa h» (3.2)-(3.4), th¼ x l  nghi»m cõa (3.6) v  p l  nghi»m cõa (3.7). £o l¤i, n¸u x l  nghi»m cõa (3.6), ˜ (x) l  nghi»m cõa h» (3.2)-(3.4); n¸u p l  nghi»m cõa th¼ (x, p) vîi p = ∇f ˜ l  nghi»m cõa h» (3.2)-(3.4). (3.7), th¼ (x, p) vîi x = ∇g(p) D¹ th§y c¡c b i to¡n (3.6) v  (3.7 ) t÷ìng ùng t÷ìng ÷ìng vîi c¡c b i to¡n cüc ¤i h m lãm sau: max{ln(f (x)) : x ∈ X}, (3.8) max{ln(g(p)) : p ∈ P }. (3.9) C¡c h m ln(f (x)) v  ln(g(p)) l  lãm ch°t tr¶n Rn++, n¶n nghi»m cõa c¡c b i to¡n (3.6) v  (3.7 ) l  tçn t¤i duy nh§t. Do â, tø ành lþ 3.1.4 chóng 16 ta kh¯ng ành nghi»m cõa h» (3.2)-(3.4) l  tçn t¤i v  duy nh§t, çng thíi nghi»m n y câ ÷ñc b¬ng c¡ch gi£i b i to¡n (3.8) ho°c (3.9). Chó þ r¬ng c¡c b i to¡n (3.8) v  (3.9) t÷ìng ÷ìng vîi c¡c b i to¡n tèi ÷u lçi, n¶n vi»c gi£i c¡c b i to¡n n y ìn gi£n hìn vi»c gi£i h» phi tuy¸n (3.2)-(3.4). 3.2 B i to¡n vîi r ng buëc ph¥n bè nhi·u nguçn lüc Trong ph¦n n y, chóng ta x²t b i to¡n mð rëng cõa (3.2)-(3.4) khi cæng ty câ k ≥ 1 nguçn lüc ÷ñc sû döng º s£n xu§t n s£n ph©m trong m nh  m¡y, vîi µr l  gi¡ trà cõa nguçn lüc thù r (r = 1, . . . , k). Khæng m§t t½nh têng qu¡t ta câ thº gi£ thi¸t r¬ng Pkr=1 µr = 1. Gi£ sû αjr l  ph¦n nguçn lüc thù r ÷ñc ph¥n bè cho vi»c s£n xu§t s£n ph©m thù j v  to n bë c¡c nguçn lüc ÷ñc sû döng h¸t, khi â ta câ 0≤ αjr ≤ 1, n X αjr = 1 r = 1, . . . , k. (3.10) j=1 V²ctì α = (α1, . . . , αn) ∈ Rn+ vîi αj = Pkr=1 µr αjr (têng gi¡ trà c¡c nguçn lüc ÷ñc sû döng º s£n xu§t s£n ph©m thù j ), j = 1, . . . , n, ÷ñc gåi l  v²ctì ph¥n bè c¡c nguçn lüc. °t ∆ l  tªp gçm t§t c£ c¡c v²ctì ph¥n bè c¡c nguçn lüc, ngh¾a l  ( ∆= α ∈ Rn+ | α = k X r=1 µr α r , k X ) µr = 1, µr ≥ 0 r = 1, 2, . . . , k . r=1 (3.11) Ùng vîi méi v²ctì ph¥n bè c¡c nguçn lüc α ∈ ∆, v²ctì x ∈ Rn+ thäa m¢n (3.2)-(3.4) s³ ÷ñc gåi l  mët ph÷ìng ¡n s£n xu§t. V²ctì p = (p1, . . . , pn) vîi pj l  têng gi¡ trà c¡c nguçn lüc ÷ñc sû döng º s£n xu§t mët ìn và h ng hâa thù j (tùc l  gi¡ vèn s£n xu§t cõa ìn và h ng hâa thù j ) s³ ÷ñc gåi l  v²ctì chi ph½ s£n xu§t ìn và. 17 B i to¡n °t ra l  t¼m ph÷ìng ¡n s£n xu§t x ∈ Rn+ v  v²ctì chi ph½ s£n xu§t ìn và p ∈ Rn+, thäa m¢n (p1x1, . . . , pnxn) ∈ ∆, trong â ∆ ÷ñc cho bði (3.11). i·u â câ ngh¾a l  chóng ta c¦n gi£i h» sau: x= m X i θi a , θi ≥ 0 i = 1, 2, . . . , m, i=1 m X θi = 1, (3.12) i=1 (3.13) pj xj = αj j = 1, 2, . . . , n, (3.14) α = (α1 , . . . , αn ) ∈ ∆. (3.15) Sau ¥y, chóng ta s³ ch¿ ra r¬ng vi»c gi£i h» (3.12)-(3.15) ÷ñc quy v· vi»c gi£i mët trong hai b i to¡n tèi ÷u a möc ti¶u. T i pj ≥ 0 j = 1, 2, . . . , n, p a ≤ 1 i = 1, 2, . . . , m, Ta ành ngh¾a fr (x) = gr (p) = n Y j=1 n Y αr xj j r = 1, 2, . . . , k, αr pj j r = 1, 2, . . . , k. j=1 X²t b i to¡n tèi ÷u a möc ti¶u fr (x) → max r = 1, 2, . . . , k, x ∈ X, (3.16) v  b i to¡n èi ng¨u gr (p) → max r = 1, 2, . . . , k, p ∈ P, (3.17) trong â X l  tªp c¡c v²ctì x thäa m¢n (3.12) v  P l  tªp c¡c v²ctì p thäa m¢n (3.13). Bê · 3.2.1. x ∈ X l  nghi»m húu hi»u Pareto cõa (3.16) n¸u v  ch¿ n¸u tçn t¤i µ ∈ Rk+ sao cho x l  nghi»m tèi ÷u cõa b i to¡n k Y max{ fr (x)µr | x ∈ X}. r=1 18 (3.18) Bê · 3.2.2. p ∈ P l  nghi»m húu hi»u Pareto cõa (3.17) n¸u v  ch¿ n¸u tçn t¤i µ ∈ Rk+ sao cho p ∈ P l  nghi»m tèi ÷u cõa b i to¡n k Y max{ gr (p)µr | p ∈ P }. (3.19) r=1 Cho x l  nghi»m húu hi»u Pareto cõa (3.16) v  p l  nghi»m húu hi»u Pareto cõa (3.17). Khi â, (x, p) ÷ñc gåi l  c°p nghi»m húu hi»u Pareto gèc-èi ng¨u n¸u tçn t¤i µ ∈ Rk+ sao cho x l  nghi»m húu hi»u Pareto cõa (3.18) v  p l  nghi»m húu hi»u Pareto cõa (3.19). ành lþ sau ch¿ ra (3.18) v  (3.19) l  èi ng¨u li¶n hñp cõa nhau. ành lþ 3.2.3. Cho (x, p) l  nghi»m cõa h» (3.12)-(3.15). Khi â, (x, p) l  c°p nghi»m húu hi»u Pareto gèc-èi ng¨u. ành lþ 3.2.4. Gi£ sû (x, p) l  c°p nghi»m húu hi»u Pareto gèc-èi ng¨u. Khi â, (x, p) l  nghi»m cõa h» (3.12)-(3.15). 3.3 Tèi ÷u vîi c¡c r ng buëc ph¥n bè nguçn lüc X²t b i to¡n max q(x) x= m X θi ai , θi ≥ 0 i = 1, 2, . . . , m, i=1 m X θi = 1, i=1 T i pj ≥ 0 j = 1, 2, . . . , n, p a ≤ 1 i = 1, 2, . . . , m, pj xj = αj j = 1, 2, . . . , n, α = (α1 , . . . , αn ) ∈ ∆. trong â q(x) l  h m lãm li¶n töc tr¶n Rn+ sao cho q(x) > 0 19 (3.20) (3.21) (3.22) (3.23) (3.24) ∀x > 0.