Ch÷ìng 3 Ùng döng
3.4 Quy ho¤ch hai c§p v tèi ÷u ìn i»u
Trong ph¦n n y, chóng tæi s³ ch¿ ra r¬ng b i to¡n (3.33) t÷ìng ÷ìng vîi b i to¡n cì b£n cõa tèi ÷u ìn i»u. Ph÷ìng ph¡p m chóng tæi ti¸p cªn cì b£n düa tr¶n quy ho¤ch hai c§p v lþ thuy¸t tèi ÷u ìn i»u cõa H. Töy ÷a ra ð [32], [33] v [34].
Cho x ∈ X l mët ph÷ìng ¡n s£n xu§t ùng vîi v²ctì ph¥n bè nguçn lücα = Pk
r=1µrαr ∈ ∆. Theo ành lþ 3.2.3,x = x(µ)l iºm cüc ¤i duy nh§t cõa h m lãm ch°tln(Qk
r=1fµr
r (x)) tr¶n tªp a di»n X. Mët h m lñi ½ch v câ thº phö thuëc v o c£ x v µ, ch¯ng h¤n v(µ, x) = q(x)−c(µ, x), trong â q(x) l têng doanh thu düa tr¶n gi¡ b¡n v c(µ, x) l têng chi ph½ ho¤t ëng (bao gçm chi ph½ s£n xu§t v chi ph½ chung).
B¥y gií, chóng ta x²t b i to¡n cüc ¤i h m v(µ, x) tr¶n tªp c¡c v²ctì
(µ, x) ∈ Rk
+×X sao cho x ∈ argmaxx0∈X
Qk r=1fµr r (x0), ngh¾a l v(µ, x) → max, (3.35) µ ∈ Rk +, x ∈ X (3.36) x ∈ argmaxx∈X Qk r=1fµr r (x). (3.37)
¥y l b i to¡n quy ho¤ch hai c§p ¢ ÷ñc nghi¶n cùu trong [33]. Sû döng c¡ch ti¸p cªn nh÷ trong [33], ta °t G= {(µ, t)| t≥ maxx∈XQk r=1fµr r (x)} (3.38) F(µ, t) = max{v(µ, x)| x ∈ X, t ≤Qk r fµr r (x)}. (3.39) Bê · 3.4.1. Quy ho¤ch hai c§p (3.35)-(3.37) t÷ìng ÷ìng vîi b i to¡n tèi ÷u sau:
Chùng minh. D¹ th§y (3.40) l t÷ìng ÷ìng vîi max{v(µ, x)| max x0∈X k Y r=1 fµr r (x0) ≤ t ≤ k Y r=1 fµr r (x), x ∈ X}. (3.41) Thüc vªy, gi£ sû (¯µ,¯t) l nghi»m tèi ÷u cõa (3.40) vîi gi¡ trà tèi ÷u
¯
v = F(¯µ,t¯). Khi â, ta câ (¯µ,¯t) ∈ G v do â, ¯t ≥ maxx∈X Qkr=1fµ¯r
r (x). Tø (3.39) ta gi£ thi¸tF(¯µ,¯t) = v(¯µ,x¯), trong âx¯∈ X, ¯t ≤Qk
r=1fµ¯r r (¯x). Do â max x∈X k Y r=1 fµ¯r r (x) ≤ ¯t≤ k Y r=1 fµ¯r r (¯x), x¯ ∈ X.
i·u n y d¨n ¸n v¯= v(¯µ,x¯) ≤ v∗, vîi v∗ l gi¡ trà tèi ÷u cõa (3.41). £o l¤i, cho (µ∗, x∗) l líi gi£i cõa b i to¡n (3.41) vîi v(µ∗, x∗) = v∗. Khi â, tçn t¤i t sao cho
max x∈X k Y r=1 fµ∗r r (x) ≤t ≤ k Y r=1 fµ∗r r (x∗), x∗ ∈ X,
i·u n y suy ra (µ∗, t) ∈ G v v¼ vªy, v∗ ≤F(µ∗, t∗) ≤ v.¯ Do â, ¯v = v∗. V¼ r ng buëc cõa (3.41) t÷ìng ÷ìng vîi x ∈ argmaxx∈X Qk
r=1fµr
r (x), do â (3.41) t÷ìng ÷ìng vîi (3.35)-(3.37). Bê · ÷ñc chùng minh.
Ta vi¸t l¤i b i to¡n (3.41) d÷îi d¤ng
max{v(µ, x)| k Y r=1 fµr r (x) = max x0∈X k Y r=1 fµr r (x0), x ∈ X}. (3.42) i·u n y còng vîi k¸t qu£ cõa Bê · 3.4.1 cho ta th§y r¬ng b i to¡n (3.40) khæng thüc sü phö thuëc v o gi¡ trà cõa t, tùc l tch¿ âng vai trá trung gian. Do â, chóng ta câ thº l§y t l h¬ng sè t¯sao cho b§t ¯ng thùc t¯≤ Qk
r=1fµr
r (x) óng vîi ½t nh§t mët v²ctì x ∈ X. B¥y gií, ta °t G := {µ ∈ Rk +| Qk r=1fµr r (x)} ≤ ¯t ∀x ∈ X}, (3.43) F(µ) := max{v(µ, x)| Qk r=1fµr r (x) ≥ ¯t, x ∈ X }. (3.44)
Chóng ta câ ành lþ sau.
ành lþ 3.4.2. Quy ho¤ch hai c§p (3.35)-(3.37) t÷ìng ÷ìng vîi b i to¡n tèi ÷u ìn i»u sau:
max{F(µ)| µ∈ G}. (3.45)
Chùng minh. Sü t÷ìng ÷ìng giúa (3.35)-(3.37) v (3.45) ÷ñc suy ra tø c¡c lªp luªn ð tr¶n. Do â, º ho n th nh chùng minh ta c¦n ch¿ ra (3.45) l b i to¡n tèi ÷u ìn i»u.
Gi£ sû µ0 ≥ µ. Tø gi£ thi¸t (3.32) xj > 2 ∀j, ta câ Qk
r=1fµ0r
r (x) ≥
Qk r=1fµr
r (x) vîi måi x ∈ X cè ành, do â, h m Qk r=1fµr
r (x) l ìn i»u t«ng theo µ. i·u n y d¨n ¸n F(µ) l ìn i»u t«ng tr¶n Rk+. M°t kh¡c, tø 0 ≤µ0 ≤ µ∈ G suy ra µ0 ∈ G v do â, G l tªp chu©n tc trong Rk+. ành lþ ÷ñc chùng minh.
Nhªn x²t 3.4.3. Ð ¥y, chóng ta th§y r¬ng (3.45) l b i to¡n tèi ÷u ìn i»u cì b£n. N¸u v(µ, x) l h m ìn i»u t«ng ho°c ch¿ c¦n l h m d.m. (hi»u cõa hai h m ìn i»u t«ng), th¼ b i to¡n con (3.44) x¡c ành F(µ) t¤i µ câ thº ÷ñc gi£i b¬ng c¡c ph÷ìng ph¡p m H. Töy ¢ ÷a ra trong c¡c b i b¡o [32] v [34]. Bði vªy, b i to¡n (3.45) câ thº ÷ñc gi£i b¬ng c¡c ph÷ìng ph¡p ¢ bi¸t cõa tèi ÷u ìn i»u. °c bi»t, khi v(µ, x) = q(x) ta câ F(µ) = max{q(x)| Qk
r=1fµr
r (x) ≥ ¯t, x ∈ X}. V¼
3≤ maxx∈X Qk
r=1fµr
r (x), n¶n ta câ thº l§y ¯t= 3. Trong tr÷íng hñp n y, b i to¡n (3.45) tròng vîi b i to¡n (3.33), do â nâ câ thº ÷ñc gi£i bði ph÷ìng ph¡p x§p x¿ ngo i nh÷ ¢ ch¿ ra trong Möc 3.3.
K¸t luªn cõa Ch÷ìng 3
C¡c k¸t qu£ ch½nh cõa ch÷ìng n y bao gçm:
- B i to¡n vîi mët r ng buëc ph¥n bè nguçn lüc t÷ìng ÷ìng vîi b i to¡n tèi ÷u lçi trong ành lþ 3.1.3 v ành lþ 3.1.4.
- B i to¡n vîi nhi·u r ng buëc ph¥n bè nguçn lüc t÷ìng ÷ìng vîi b i to¡n tèi ÷u lçi a möc ti¶u trong ành lþ 3.2.3, ành lþ 3.2.4 v H» qu£ 3.2.5.
- B i to¡n tèi ÷u khæng lçi vîi r ng buëc v· ph¥n bè nguçn lüc t÷ìng ÷ìng vîi b i to¡n cüc ¤i h m tüa lçi tr¶n tªp lçi compc trong ành lþ 3.3.3 hay b i to¡n cì b£n cõa tèi ÷u ìn i»u trong trong ành lþ 3.4.2.