H3 6RT6[È0X H-ÊKU 46-;Xk\ù:]90=G_ LZ=96^XN90= _ KU90 T=G Z: Pp

!"$#%& ')(*+-, ./0 ' 132421&5&678490:<;.9 =?>4>@5 ABDC =EGFHJI90KML@NOL@KQP3;;RSKTRU69VP3=WRTXZY[=W74\4=WL@:]74NVP@XGRSI90KQL3^L3_]^FP@KURTXWP3_V`:aLEG^cbL3_dP@=G74N0N FHe:a9 \fL@N 90=G90^9g_hR`RTKTKU9 _G849iLZ^FP3KTRTX$I90KQL3^L3_D74Y[_WRT:jF[:ak =G_hk H@kg_Vl manpoq3rpsut"vcwpsxyvesz|{erps}~ bL suty{fs} sut"vesxM sxyvesz|{fs} szM sutgWsx0WszWs} -, / B* R8490KLI90KTL@^L3_W;L@6H-R83L@6H3@_W8@9L+83P@KU_W74N04He69 :a6[90\L3_WU8k0=_hk H[XWk0\@9@`S90N k0=_ k0=G^90:]90XL@Ng_ mnoqpsesGs)&~ L@KQL3H[6L@H _h90H-RU6-_W906Rk XL^FP@KURTXG_iL ma¡U¢.q£&j.£¤ h£¥&~ L@KQL3H;L@6I90KUT=W6[R§¦/KTP@XW^ L]¨M9 6^XGN090=G74Y[_WRT:aL@KTRUNVP@KTP@X"EG9 \@©N09g_<>ª574KT^L@KQP3_d«g5&¬HH374=D_h90bP3_ ®¯¯ >±2 2 { ´0µµ ®¯¯ > ´0µµ >²> 2 2 ¥ ° 2³ S ° >> ¶ > > { ¶ 2²2 {? 2 { k0X D¸·r&w&04V{r4¹ 5 C \@©_h9 bP3_ML*^FP@KURTXºI9 KQL@^L3_V» m]¡T¢q£tuv£3x¼ve£@z§{f£p}V~ bL £-t"ve£@xM¥r £3xyve£@zM¥w £3z|{J£p}M £-t"ve£@zM¥r £-th£@x0h£@z h£3} ½ HpL@Y7@_G_?9 KTXG¾Ok0XbL@=G:L3^RTH¿9 \@©49 6KT¾3_hKT9 6XWk \49 _?4XGXWN090L@^[83L[» £t¼v£@x|v¥£3zS{£3}a±À `T\@©ÁL ^FP3KTRTX:]RT6RU:jF:aLDKU90\L3KQP@;;?Â[5 P@XG=Wk0XGN _§H3466©]7@KU©L36j:a9 \474KU^P@XG__dL3KQP@KU6R-L^FP3KTRTXI90KTL@^L3_Wb74N ¦/Yk0KU^P@FK» £tÃ4h£3xÄÆÅ[h£@zÄÃ4h£p}ÄÇ «g`|L@:]RTH@7@=*LÉÈ k0KUIÊ[\4\@84k 6©ek0=G_Wk0H39Ok0Y[Y.9 6Â[`90N k0=_ Lf^FP3KTRTX*I90KTL@^L3_:aRU6RT:

¦ 90\VEG90\@©@90N0N ÊH`b74\@©Õ90;;906ÉL@N<90XW9g_h;906É;P@N RTXk Xi90=W¾@X;P@N RTXH34N0@_G_ 6RT6[È0XH-ÊKU46-;XWk \ù:]90=G_ LZ=W9 6^XWN 90=_KU90T=GZ:Pp_h=WR Ì7@XWN0KU74YL@RÏKTRT6[9VP@=GRTXhL36IÊ\4\49g_hKT9 690H5 « ½ N s Ws =G906^[XWN09 =G_ s ` ·{Mi¹ s { ` · { ¹ s² L@KQL@H-;L36¥U=WbLp_GÒ EGFHÔXGN074HpP@XG74X9 \@©49 6KT¾@_WKT9 6XWk \4=W9 6^XWN 90=iL3KQL@H-;L[`L3b74K L3N 9 X9 \@©XWk \4:Pp_h=WR Ì&7@_§EG9 KT4KUR§¦ Y90^RU\ 7@XWN0KU74YL@RU6L@HÔXGNVP@:aL«g5 Î 90H-RT6_hXGÊ6HÕ90\@© s ;P@N RTXW:]90\@74KT^P3XG_VÜ9 ;;906¿_h9 bP3_L@N<9 \@©49 6KT¾3Ò ® ´ XWk \4\49 K_W90KÖEG90XW_h9g_W_MXW74=G74H=WL@6\VEWL]:]90\*H@9 KTK90\3©490N N09 6L]=G906^XGN09 =G_KU90U=W Ë ° {M ¶ :Pp_h=WR Ì { =hL36\EWPV83L@K`83L@\@©RUX 6[90KÐ 5 M©RTK8@P36Á90\@©@906KU¾4XWk \4\490K_h90KÖEG90XGÊKT69 H¿L@N Ms ` ·{Mi¹ s¤{ 690H :]90\@I9 KT90KU¾XW74=G74H¥¦/bRUXWN 9069 N0N09 Kk YY906 Ms -_]I74\L3KT:aL@N _WFHfP3_d«g`_h783P@;;P ·{ ¹ s¸³ ;4KL@N s 2 H@7@:aY7469 6XW9 RT69 H¿:a9 \@I90KU90KU¾ÔXW74=G74HÜL@KTH374XWXWP@H¿90N 90HLÔXW7@=W74HÁL3N :aP3_h=GRÌ&7@_05 ½ N ×[·/ ¹|¥×· ¹ ÁI9 KU_hkg_h9 K"L@N _¼EG9 KT906_WRÐ`[b[74\@© 74XGN0KU74YL@RuKURT690P@=WRUXhL@6IÊ[\4\49 _WKT9 690H5 C \@©e_h9 bP3_ÔL3N s 69 :a6-FKUKQLÁH@7@:aY7469 6XW9 RT69 H):]90\@I9 KT9 KT¾ ;90KURS74XWN KT74Y74HJRUXaKURT690P@=WRUXhL@6 IÊ\4\@9 _hKU9069 H5u¬N09 H6[90HL@Nj7@XWN0KU74Y74H-6L@H¿L3Nj90=G90^9g_hRTKU90\ { -b90NZ_dL3=G_h7@N0=Gk0XWN 9*È0XWF[YL 2 -__hL@=Ò _dL3KT:aL@N@5¬N0k =G_¼L@Nº¾KTRT6[9VP@=GRTX"IÊ\4\49g_hKU906XGk0\4ÊHL@Ng_EG9 KT906_WRÐ`b74\3©e90KU90:j=Gk0XGN0bL@KU:L3N074H¥IÊ\4\49g_hKT9 690H5 Î 90H-RU6-_WXWÊH L@ N · ¹! x 4XWXGN090\@:L3_W=W74RU^7@_0»y90;[;.9 6 · ¹ 90\@©J=Gk0XGN0bL@KU:L3NVL¿Y746_h74XWL@6cL3HH374=ZIÊ\4\49g_GÒ KT9 6uùbLÔ9 KT¾P@KUK9 \@©ÁH34=W:]906_h9 X k0KTbL@KT:aL@N0;4KKT9 \@I4KÝEG9 ;;¿9 \@©¿_h783P@;;[Rk0K¼b7@N0NVPV8@k _h9 KTkg8490K5¬§N k0=_ · ¹ x ;P@N RTXWL@RL@N 74HZL@Nºk0KTbL@KT:aL@N07@H`3L@:]90K©490H?90\@©?I90XGN0U_W¾@I/P@;4K[9 \@©49g_hKU906*pE¼k0Kb7@N0NVPV8@k _h9Ò KTkg849 KH390KU9 _hH390N 690H54¬N 90HL@N07@6;L@6±1 >Ù1 1 >87 1%9 -, / B§ R8490KLZ:aP3_h=GRÌ74XWN KT74YL@R;: x ;90KTRU90H`9 N0k0=_1<6k KÏ_h4;[;Õ9 KT90:< IÊ[\4\49 _WKT9 6ÔbL@KT:aL@N 6RU6È0XLa:aL3_h=G74RT^;L@6u5 ½ N?90KUXW¾bP3=W74: 74XGN0KU74YOH34N0ÊKXW9 :a9 KU©RTHÔH39 _W_W¾ÔXW9 : YP@=Wb-FN0L@:a7@X0>5 =LL@N F[_W74KTXGÄ7@XWN0KU74YÉXW90:³YP@=Wb-FN0L@:a7@X
½ 1 ÙÅV4dÀ 90XG9 _W90H-;.9 6JY.9 ^RT\OLÄIÊ\@\49 _WKT906ÉbL@KU:L3N074HÁLÄKT9 \@I4KÝEG9 ;;e>9 KT90:<+bL@KU:L3N074H` 83L@KQL3:aRU6-_D9 \@© H-RU8@k _h9 KTkg8490KyL1Z90KU90:j9 H5Ï¬NjL]:Lp_h=W7@RT^ H@46[6-©@906Á9 KTH@k YN09 KTb9g_h¾Yk0KU^P@FKL@6[6L@H L\4=hP3I6L@HfLH@4=G:Lp_h=W7@RT^pEWL@H3k06_V`¼L@:a9 KU©@9 _*90\3©ebP@=W7@:aXGN04\4;¾4KºL@N 90\@©RTH+k0KD:a9 \4^FY[KQP@N0P@XhPV83L@K 6©49 =WÊ6H5y¬§NaL :L3_W=W74RU^¿_h9 bP3_\4=hL H-FX0`T\3©Á=W9 \4FKQP3=WRTX 5 R8490K|LÔ\4=WP3IËXGTH-;L@=WLEGN074KUbL3_Wù90N k0=_ LÔ:Lp_h=W7@RT^Á^FP3KTRTXWP3_iH3466©49 6f:a9 \4HpL@YbLp_/EGFHOLÄ\4=WP3I$^FP@KURTXhP36L@HÄH@4=G:L3_W=W74RU^pEWL@H3k06_V»"H-RT^[90=WÊ[KÐ` b74\3©Ô90NLZ:Lp_h=W7@RT^ÔRTXSRUN074:]74=IL*^[FP@KTRUXhPV83L@KÐ5 uB ½ ^7@_W_90\3© ¤· § ¹ RT=hP36-©_h7@_G_\@=hP3Iyk0X9 6690H 9 \@©Ä:LpÌ&RU:P@KURTXËk KTXGNVP@:jÏ`.L3È0RTH-KURTH-FX<¦/RT=WPpÒ 6©U_h73_W_H@4=:a9 6-_W90Xh«=Wk XWN0\@=hP3I EWP3_XWN 90=G9 _h6[k06HÕ:a9 \@_dL@KTP@KT6[RÐ5 ½ ÊGF6HÄ90=W=G9jLaI9 KQL@^L3_h=WLO¦Y.74KURT67@: RT^[9 EG« xt H34N09 KT_h¾]L@KT\@74=WR_h:jFX_Vl -, / B N0P@:]74N0N FH:]90\OLO\4=WP3IDÈ0XGÈ0XWL@RU_> -_h¾@!K RT\Ä_h9 _WXWN ¾4KT9 \490XG906u5 ½ Nk KTbL@KU:L3N _H@kg_ ^RUXWN EGF[6H_i=Wk XWN0=G9Z;.7@6-_EGFH»uL@N?90\@©RUHÄ=Gk0XGN0;9j_dL@=_h74N 6L@HÄL@N07@HOL@N

'&

%

!

" $#

( )# &

+*-,

.*

/'&+0-132

%

( )# &

!4

5'&

'&

'6

: !( )# &

5 !( )# &

;'6

798

:98

*<

=>&

?8

?8 ?6

( )# &

( )# &

+>&

( )# &

@BA

?8

( )# &

-?6

@

5

C*

+*-,

D*-,

C*-,

E

GFH'IJ

7

K4

/%

?8

!"$#%& ' (*))+(,.-0/213/2465/2798 :;, <=?> @BA -CED.FG4H/JI >LK>LMON 5.50PQ/JILR+/2S MUTLVWM / S0XZYJI+7E/2S0-.X K /27ZS0/2F[/JI\R]/27 T X^5 N*K P_X`4H/JI\a Mcb - N X NV2d 5 @A -*CED0Fe4H/JI >LKf>LM_N 505.P/2ILR/ S MUTLVWM /2S.XZYJI+7g/ S0-.X K /27ZS0/2Fh/JI\Ria M R > Sj5 N*K P_X`4H/JI\a Mcb - N X NV2k> 4iPlnmpo /27 T Xq5 NLK PUX`4i/JI\a M - N X d r"sturwvyx 8 rvturz{x 8 rz|tur}~x , 8 , rg|tur"syx 8 rstursux 8 = /JILR;.FG/ Mk aILR >LK[ rx M P_S;/ N 7ZPUX/JI\R/2S MT\VWM /2S.XZYJI7E/2S.-.X K /27^S;/ 4 4H/2I b a M - &>V` ,?P K a+S+R; V X`D0F5/ k a\I\R/2FF\a7 V / V X KJT+M /JI/2Xa M R > S b 7E/ k> 4iPU7E/ rx 4H/JIa M - &>V`.k b S;/ F/JI\R/ VWM /2S k >\M F >LM 4 > X > S64i/JIL NLMO> X K3V a VEV F\aa7Z-.PUS NVN C > 4H/JIL N\Mcb V a K3V>*V`&>Vì ILR k. a\I\R > F >L a VZV b 7E/ rGx 4 N 7$S0/24 4H/JI\a M - .>*V`.d ¡= P K a+S+R; V X`D0F¢5/ k£ aILR >*KH¤¥ aS VW§¦ X`X K /30I\I T¢¨ I7 N aS V aX > S ¤ tª© Y M_« F ¦ 7Z4H/2S V /2X"7EY2X K I+7 N ¬C > P!/ K /2F®Y M_.>\M 4 >LK > P @ /JI\R¯4 >*V 7Ea+PU-°5 NLK PUX > P V>LM FLa V C N F d²± Y M - N S 46D V> X`X`D.Fe4i/JI k0 aILR³/ K S;/24 4iP_S0-0/2S ¨ I7 N /2XZ/ V Y2S M /2X K I7 >´ FD0Xq4 >*V 7Ea+PU- d µ =°¶ /JI M / / VEb / >¸·ª&> 7 > 4HY V /27Y27 V Y FLY V[ I\Ru N\M_> X K3V> S.P k a\ILR > ¹ · (~º»: 8ª¼¾½À¿¯Á 4 N*V 7ZPÃÂ > >LMU X V /2X V / M / VEV®>*KN 5.7 N S MONVW.>*V` I7 N ?F ¦ 7E4 >VEb 7EaP_-C N*V FLaa+7Z-0P_S N*VWNLKJK > Ä Å=wA -*CED.S0F a M PUS0a4 PU-0/EC «Æ>LM I\a+7EP V 4ÇD.X Vq>*KeÈ;ÉËÊpÌ+ÉÎÍÐÏ"Ñ%Ò V /24H/ K Y X`P/ MO> - >V 7 >;d Ó= P K a+S+R; V X`D.FÔ5/ k$ a\I\R >uÕ V /2PUS0/27 b >Ö 7Ea5 M Y 4 > 4H/ V 7ZPUFD.Xj/2XZ/ V Y2S0/2F×4iP_S0-.PI > SØa M R > SØa ÙV PU4 NLM P_X4H/2I\a M - N X >;k> 4H/ M R M /JIL ¦+M Cg/25.5 >¢V /27Z4iPUS NLM_ aS V aFX K N 4 N²b S NLM F\/ VZV`T +/ M FL/J/2XZ/25.5 Õ V /2PUS0/27 bÚ aS V a Ve&> X K S N\Md A 7ga+5 M Y24 > 4H/ V 7ZP_FD0X6/2XZ/ V / >LMO>VZVq>LK3V Y27 V CE.F k0 a\I\R > I+7 N Y M /2P_S > -;a VZV X .M R0I\IL+Y2S+RjFPU/ M Y2I V P >Û.N 7ga+4iX KJ¦ I b /JI\R/2S MT\V`M /2S.XZYJI\/ V Y2X > I7 N V / M Cg/ XJ, @

!"$#%& ')(*+-, ./0 ' 132424576&89:4;0<>=.; ?A@CB76 DE.FHG 94I?KJL;0?NMPOQ9SRKT0U-JV8W;0XLJVi3TmiSXnZ3==J XVJL8;CZ3?KJV]$;0_ShS;08XLoSRlXL;08]pa0_4?p;08b7]KT0; ?K8; U6cqkir:3iS8s<W; _494XLbZS]0f7iSbutpI87UJV]v¦1S24245uMjiS]§U-Jni3bZS]lZ38iSU&¨v©ª@2uM%;0bJLUW9SXVbiSXVZS8`L?pR«i3U]KT ;0?pJV8R¬:4a0_S;0T0T eU 0¡¡ ²±4®4w³4®4w ¡ ®4± w4®4± ¡ }}®4w¯®4w }w ¡¡ w } }A ¡¡ }®4w }®4w ¡¡ } } }kw } ¡¡ ¡ ®S ¡ } }A }A ¢ } } ¢° } ¢ ° }A ° 4®4± w4®S± ¡¡ w4®S ¡¡ }A®4w }A®4w ¢ } }A ¢ }®S ° ° } F UuiS´9SRKRiSXni3UQ; XV]Ko]K94?KiµiST R¶;jtp;0T J·U-J¸f¹g794_Sh~Q²º»-fcigiS?p<i3bJVUµ]p94?]KT ;0?pJV8Rm:JV]KT 948R~Q¼46 ½ T0a ?pRiY?p;08b7]KT0; ?K8; Us8JV8[ ]¬<W; _494XVbZS]li76 ¾cE i¨§¿j?tpIUW¶;0X"iSTiSXVZS==J¹XVJV87;CZS?pJV]À´7?K94_4?KiS
-, / EcF ¶;0XViSbi3R

ÇWÈuÉÊ

x4x CÏriSXViSUcfiSg794X ¼ ¡¡ ¡¡ ¼ w v ¼ ¢ ¢ £ £ Ç Ê F bIZSXLJV]§¶;0XViSbi3R¬b7; 8`L[0JL\W]pT0;0?pJV8R {& {H ¥ {s&Ïri3XniSUc6 ½ T R?Ka ]KT XV; RK;0T :4;ri*bIZSXLJV] Ç Ê irUSd:4; RlU3;0T0o7 £ {Ëcy w3{ y)S{ » y4{3Í0Ï º gi {-Ë Ã {-Ëy{ º Ã { º y{ » Ã { » y{3ÍÀÃ {uÍvÃ {-Ë { º { » {3Í F T 9488i3X XnZuRlgi3RK\fg94_ShibIZSXLJV]8£;0< £ <W; £ _494XLbgi3RK\ ¦/;0XV]poµ8a0_3h;0_3h4;087XV; RK=.oSX {Ë¬ 4f { º Ä7f{ » 4f{3ÍkÆ7f.iS<WJ; XVXV; 8RldSRKd&bJLUµ;0_ShS;08XL; RK8;0U&¨ 6 ½ ==.oSX ´;0bJL_USd:S; RlU3;0T JVUf g94_3hµiz´?pJV<WZSX¶;0Xni3bi3Rv[ a0XL¶e7_4_S:4a 8h4;iz<W; _494XLbZS]KgiSXV<WiST09S88; < ¶;0XLeXV?po4XUS94?pXnZ3RK94]^¦<W; ?pRv; Tî tp;0_3h&T ; R1S24245MNiS]§U-JViSbZS]KZS8iSU@S6 uM%94]§Rla Rl; XV;^]KT ;0?KJL8Rki3T0TCi3X:S94XV8i*; U:&J :3iSXV; 8]0fg9S_Shsi*bIZSXLJV]K8iSU :3iS8Å<W; _494XVbZS]li¨ 6 i U-I]<i3RK?K94JLb?li&f7iS T Í I8J ¶94?K<<Wi3Rl?p94JVbc6 ½ ?K?po4XÀJL]K; _Sh; XV; <W; RÀ; XVgiS_3h&I78 U Í º M » =o4X¸fiSU-US9S? º M%R0f-:3iS_3h&JL]§igZS?K9S<W]pT0d4_zU3d4?K<Wi3RK?K94JLbutKZ3R UuiS´tpIU¦i3<WJ´;0?K]pT0;`L_Sh*_4?Ki U-I]«¨ 6qi Í Mj=;08^d4]p]KT0; g T0I87U>;0_3hm;0XL;0<WJL8b;08 ]K`VU-=i3?litpT 94XVgiuRl\f·`L_Sh+i ¦/]p`VU-=iS?KitpT09SXnZS]KZS=.\SXc8h4;0?pg; RKo-¨vbIZSXLJV]v_4?KZ3¶ tKZSg94TRliS?pRK94T0\Y_4?Ki U-I]¬<iuRl?K9SJVbµ=JLT0948h`LRtKiYi3TAZ3XVXV`M R«Z3]pRC>6 =_Sh4iS8;0T^; XV¶;0Xni3bi3Rl?Ki76

E ½ _Sh;0_ShJL´7Rl94

@ 2 2 22 2@ 2@

1 2 @ @ 2 5 ¢

S\ RK94X tpI7UiST^94X :Si3]Kgi3Rli3RlXViS8?pa0]KT ;0U3; R*¦/iS

Ê

Ê

F gg794TSfug94_ShiUuiS´.93RKR_4?lZu¶<WZ3Rl?pJ &?K; ´?K; T0;08RlZS[0JL\utKig7;0XLhS;0]XV;0_3h4;08¹fSi Ï§a ] i Ï 94]pT0XV9S´giSXL<iST 94U-8iSUXVJV87;CZS?pJV]li38md4]K]pT0; ¶e7_4_4o4U-8; UU3;0XLXXV;0878J¦/:8' ;"?@,A5CB<8' ,?4365CBD8 *:4 %E5CBD8 F%G(465CBD8'H.?%"?65I28'J04;,4KL51I28'M"?KF%.N5O28'P04;,: .3A5O28/Q

kq itPRK]KIUW:4a0_S?K;^;0T ;08QiSbi3RK94U-U3i3X"iSTîSXViS´giSXL<i3T?pa0]KT giSXL<iST 94U-UuiSX.RKd4?pRKa08o*XV; ¶;0ba ]Ka ?K;^]KT 94X M _ZSXL\rUSd4T ;0XL`LRlo*i3XV_494?pJLRK
½ XV]KoSUSa0Ë 8Ri 23(4 gi3XV<WiST R$US; XVX:SZ3XniS]pT R«i38I78Uf<W; ?pRÀ;0==;08si>XL;0_4U-JL]K;0=7=siSTk; _Sh; XV; <W?p;k;0]po USdSXLRl]pa0_Â¦ º ¨ 6 F U3d:S; RKUS;0T oQgiSXV<WiSTi 04;,D.3 U3;0XLXXL;0_ShS;08cf;0TriWgZ3Rl?KiSXVa :4o=.; R1=o4X Mjd3R¶; b XV;3fAU3d4XLRK]Ka0_S_4;0Xf;0TÎ USd4X Rl]Ka _4; R"tp;0XL;08R$=.; R18U3a08RCf7iS]pTCiC:3iSU*USd4T eX¸6 ½ U-US94?vi "- %' * =.; 1R Ur:3iS88i3UYI8UuZSU ® a ?pRKa0US; U]KT ;0?pJV8R¬8;0; XVofg94_Sh :3iSXni3<W; XLhJL8b; &?p;®!#".ËP® #".Ë^º Rl; X tp; ]KeX tpd48cfiS<WJL=.oSX <WZS? USd:S; RlU3;0T JVUfvg94_Sh)i+<>I8UuZSU$ ® µ]KT0; ?KJL8-R8;0< [0]pd4U-US; 8o]K94?p?K£ ;087b£C=.¥0¥C; ¥08 £ :3iS88iSUf$;0XVXL;08U3;0T o ;0]p; RK=.; 8I_3hiS8JL]:3iSXniSI8UuiÌI7R«ZS8; _Sh 8Z3Xni+U-JV]p;0== ¦#& ® Ü3d4XLRK]Ka ;_ USa 8;g794_Sh USd:S; RlU3;0T T0;08¹6 ; _SheUr¶;0XJL8bJV?p;0URl; 8cf4g9S¥ _ShrXVa Rl; T0JVU>94XLh4iS8'JL8b; ¹f 1 5Ë ? 5Ë¬a0]2@A1 " º ?#" º @#1 " » !#" » >1 !&f.RK9:SZ3==ZB>1 !#".Ëa ] ¥ £ #1 ".Ë 4¸6 £¿j_S¥Ch ¥C¥ £ £ £A¥C¥0¥C£ 5Ë C 1 1 C 1 1 y% 1 1 y% #1 ".Ë #1 ".Ë y C 1 1 ED.Ë ED.Ë ED #" º 5Ë C C F yG#". Ë #,6&yA".Ë·}H &"yGI6#".Ëcy D.Ë ED A" º ¥ OQJ :4;0X(6A".Ë 86&y$#".Ë fi3TmI7Rl94XL]K\*]K9S? 5Ë C F yG#".;Ë #J6#".Ë}9 &"yG( #,6&yA".Ë &"y C ED.Ë ED A" º iSXViSU-=ir`V?Kgi3Rl\f7iS
!"$#%& ' (*)),+.-0/2143514687149;: <.=>"?A@BDCFEHG0I 14JLK0M.NOQPSR*T > R U`L9 t2I 14JR*TRQJ l 7270oJmo B 1 l 9yo E8 9N u RDUWVYX Z[]\^X _`Z[bacX _ed OD9yR,6`N,T l E o 14JmR,/0R C / t l Jmo E l C 7U$VfXhg0[]\^X Z[ia8X Z 7UR C l 9sNTpT t0I 6`1pOR 9yoq6 l JU 1 JmR u 3jUWVYX Z[F\^Xhg&[bacX _cZ /&R C 6^Rj2om6 t 6 l C k,l JmR E T C l EHE RQJn7 l T4o E 6`1pONJq/ l E l C KoqJqJq1 C k 1 * d,V_nDV}d,V_~DV} d,V¡£¢ 1 9sr E 7 l T4o E 6`1pONJq/ l E l C RQ/ CHt0Iu 1v6w1pOxRQT M0R R,J l 7270o.Jmo B 1 l 9yo E 14OQP1 B Jqr C Jz1 B0Ey{ OD9s1 B / E Tp149 u V"¤_~VA Z B 1 I| V _~V ¥d V`}~\f Z V _~V ¦ \c_~a Z V _~V ¡ ¨§ V`}dQ\c_~a Z ©ª>&« /* t2B0Iw{ Jq/ l C NJzP R B¬ OD9 l 9HR.K6w14J®P.91°¯ ± ¬²´³ ¯ ± ¬² C 14M l C R ¬ O9 l ªI,@ 9y6^R Csu 9NDoq/* l B R I RQT @B 6^RQO l4k RQJ k 1 CyC;@EHE Tp1pO1U B 1 6 O9HRµ It0E -¤¶;JmJq· C l EHt2B0I R C 70ozTpN B P.· CFEHt2I o E 71-¸U ¹ > l B P N BDC yRJq14M.1 C R B0B R I R*T @EHE Tp1 G OO,rvO9 l B R I K6w14J®P B 1 I R I,@ 9y6^R C 9NDoq/* l C RQT R,J l 7270o&6 l C 9yoº`9s1 91pTp1 BDC l J»yR¼R k RQJz½ E¤C 1 EC 14Jz1 CyCi¾ «À¿ju O RQJQs14J @ J CE T l 6 NDJ k R E M&R C R C JÁR B K /21 B 1 6 o EI 1 JqJ CHt / B oªR k,l JÁR E T4M2N,TD-¸U ÂÃ ZÄZÄZ¦d ÆÇ ZÄZÅd d ZÅd ¿ È">É« / t0B2I ( u R 0 9N 2oq6 l 3poq½ E RQJqO,ND9o C 6 t0EC 1pOQP C 1 CFE TprDJz1pO1 E O9 l 6^R2oq6 l Jqo EÊ{ J E T l 68Ë k,l O l E l B R I 6w1pOM&R C l 9NT l E l 9yR2-LÌ1pOD· CFEy{ O |&I 1491 EHEHG0B2I NJzP R B k,l O l EC KRQ6woRQT @DEHE Tp1 EÍ{ J u B 1 I Jz1pO RQJ l 707vR 1 J {5C$C R,9 C R,Jq6^RQTpT R.-ºU Îª>,« / t0I 6`1pOÏR*TRQJ l 7270o 9143p14/.1 B 3poÁR*OD9 l*Ð RQJ6`1pO RQ/2N CyC¤Ñ dÒ ÓÔDÕ ÖQ[%Ó.×X Z.ÒÙØÚÜÛsÝ 14JÁRQ/&R C 14OQPN C om6 l Jmo E 6`14O,NJm/ l E l C ßÞàW"á5âv j ã j!jåäw4ãæ! 4çãç è A

E F

C

B

D

K

L

H

G

J

!"$#%& ')(*+-, ./0 ' 13242657&89:4;0<>=.; ?@135A7 B CEDFHG ?IKJLNM; O D6PQD OSR6=A=TUOVTW8;XR3?YTVZ\[A?Y94]4? D <^9 P R6ZKT_M;0O D6`D3a*` JR6OVTWZbR a0ced/f M; OVgV?YR6Z\94Oih D 8 D O D Lj OV; ]6h4; 8lk<^TV8 aeD [?YTW<mR6OM;0O D6`D3a M; OVgW?bR6Z D 7 F = FonpD3a R6?Y9 P0P JAL
max{8x1 + 7x2 + 8x3 } 3x1 + 2x2 + x3 ≤ 1 x1 + x2 + 2x3 ≤ 1 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0

vw-,x x/ Clf M;0O D6`D3a

D O D L-jlk D u 96O

max{cx : Ax ≤ b, x ≥ 0} 3 2 1 1 A= , b= , 1 1 2 1 8 7 8 . c=

fy` JR6OWTVZ a ; P z ? a$z ? ` ;0<^;0Z D|{ ; 8 ` Z P ;0?K94[ a TW< D OVT P R6OSR3Z}L6~68-h-: d 16242653%;0ZL-T D3` R6ZbR38 D L F 16t1t57494O `D OSR38qOW;0gV? a ;0L:TW: D OV; 8Z D O D L0IYR6= D 8^M; OVgW?Y8T7 d 96OV]49 P u D3a J8LH[x;0?KZ P ; D` JR3OVTVZ; ?Y; ` ; a Tk ` ; 8AgV0TWZ P ; ?YTW8 a T D O D LXIYRX: D OTWZ0k;0L-L394? D6P 948-= D 8 D M;0O D6`D3a DQ` JR6OVTWZ min{yb : yA ≥ c, y ≥x ≥0}0k D <^Tl? z Z P OV; a ; P :4; D L3~:6; a L6; P uD

min{y1 + y2 } 3y1 + y2 ≥ 8 2y1 + y2 ≥ 7 y1 + 2y2 ≥ 8 y1 , y2 ≥ 0

f [?KTVJ< D u ; OWh4; aYa|Dm` J D OVT a R6Z abza ;0O z ? a ; OV< z =x;08<^;0] a ; u ; a IKLk u 94]6h D <^94Z a <^;0] u D3a R3?Y9 P 9 aYap` JR6OWTVZpM; O D6`Dta <^TV8TW94OWh D 8 A [x94OVTW894<^TSR6OWTVZT ` ; IK D OV]694?YT a <^;0]496O ` R6ZYR6? D : D 8H[x94OVTW894<wT ` ; IK D OW]494?KT a <>JZ0k; P0P ; O D M; O D6`Dta 9 a <^;0]494O ` IKJL7 OVZY*L3~ P ; OVg aYz ZK=.; 8r; ] z Z P0z ? abz L[?Y94]6? D <^9 P R3ZYT[A?Y94=O z < D L z 8 a M94] D OW< D6P P JL^<^;0] D M;0O D6`D 9a a 7 npDQD6P A <mR a ?YT s n 94Z P OV94[Ajlk D L-L694?|;0]3h¢94OWh D 8 n ` TW
0

2

D <^;0Oih&8A;0L <^TV8 ` ;08¢L694<^[x948;08AZY;2: D ]6h 6 D6P ; Z|L39&96? ` TW8R a R3L8 D L <^;0]6M; OV;0OW94Z P OV94[x94L D Oi L69 a IYR6LH< D I `^D L-TW:3R6O D Z P a 9 aYa ? z Z P u D OV< D6P a 7 f M;0O D6`D3a M; O aYz a ; OV;oj]3h>M94] D OV< D6P u Dta @<^;0]k u 94]6h D L-TW:3R6O D Z Pa 9 aKa 94Z P OV94[x94LH~6ZYZ P ;0]4; D 8-JOVOi:4;0L a 94?0k4: D ]6hTWZ D6P x :4; L a 94?K? D A · x = 0 a ; O IK; ZYO7 ~48A8-h ] D ? D 8 a R6OW8Tk u 94]6h x 2*: D ]3h¢OW;0]6h6;08l D 0 ≤ x ≤ (1, 1, . . . , 1) M;0O abz a ;0O z [A[.; 8; P a LTi:3R6O D Z P a R6Z0k u D ; 88; L D [A?Y94]4? D <^8 D L D < Dts TV
T

 A  −A     E , −E 

D <^T D\aD 8-JO aoa ?YTi:TSR6OWTVZ_OW;0<^< D Z P ; ?YTV8 aHd{ ;08 ` Z P ; ?Y94[ a TV< D OWT P R3OSR6Z$L6~48h-:xk47iA7AOV;0<^< DF Z P TV8 abz 8 a 9 a R6OWTVZ D 8rJ8ATV<^9 ` JAOSR6?KTVZ0k u D A D6P :694O a 7 ¡ TW:4; O D3P ;0]3h4;08AOV a OV;08AZ z ]6;0L>IK94== 96O `D O D TW8QTWZ; ] z Z P ; L R6OWOV8 D L d <^TV8 ` ; 8 u 94O2E: D ]6h F k; P0z ? a\D M;08 a T M;0O D6`D3a u ; OWh4; aYa L3~48h-:.k 47i1&7 aYz a ; O FHD L za 94[ a TV;0L7 ¡ ; ]4 |Y | <^;0OWh?K; Y +|X| 7 TW:4; O |X| > |Y | [x; ` TV] D u R6?Y94< [R6? u J P0D <^94Z z OV=x4OR6OWOV]4?YR3MlL3~4?Y< D3a ?Y94T ` I D 7 d ; ?YZ P ;p<^TV8 ` L z a ;0ZK; a =.; 8Z P R6< abD O D 8
0

0

1

2

2

0

3

3

0

4,3

4,2

3,2

3,1

C" ;0]6h6;08

Mx

D6P

1 0 1 2 0 x 1 x

Z P0D = D6` < D3a ?K94T `qz Z D3P ;0OW;0

[?K94=O z < D L6~:4; a L3; P ;0ZK; abza 7 ; ]6h4; 8;0L D3P S u D OW< D6P ;0OW;0<^;0T &k Ak Ak"141k"135k z ZOV; ]6h4; 8 D ? z Z P OV; a ~4ZKZ P ;0]4L z 8 a <^;0]4 z O P 9 aKa z ? aYz L 5657 nD I a ZKJL: z ]4?Y; z Z ` 94L-J<^;08 a R6O IKJL D6P ;0OW D6` R6ZK948 aD 8-JO a (1 − ε) L3~ P ; OVg a D OV]694?YT a OWTVZ a R6L D6P ~4ZKZ P ; M z ZKO z ZY; Lxk?KT a L-g a R6ZK94L d δ = ε/n = 0.1F$z Z D t%8 z Ol8 D ]6h496==E;0OV;
x

1

2

3

4

2

1

x

x

1

3

4

x

3,3

3

x

4

x

1,0

1

x

x

4

1

2

2

3

x

L0 L1 L2 L3 L4 L5

x

3

4

x

4,4

= {0}, L00 = {15} = {0, 15}, L01 = {16, 31} = {0, 15, 31}, L02 = {18, 33, (49)} = {0, 15, 18, 31}, L03 = {22, 37, 40, (53)} = {0, 15, 18, 22, 31, 37}, L04 = {24, 39, 42, (46), (55), (61)} = {0, 15, 18, 22, 31, 37, 42}.

f L D [.9 aKa L6~ P ;0OWg a z ? aYz L D6P L u D OV< D6P OW;0]48 D ]6h494=A=Q; OV; J8LtR6L 8; < MA]4]48; L; ]6h4; a OW;08+: D 8lk; PmD M/R P TVZ D6P ;0<^;0OW; a [x948 a I D TW8 D L>; OWM94]3hR6ZYR: D O z ? : z ]4; a 7 %94OWh abD ZYZKJL D6P a ;0<^; P0z Z a D3` 9 aYa T ` 4[.968 a ? D : D O D <^;088hTV; 8;0OWL z Z P O a ; L d p = 1 <^TV8 ` ;08 j ?K; c F $7 & ]6h D 8gV]6hqOSR a u D3a H=x;6k u 94]6h D3P ;0O IYR6?bR3ZM94Oih abD3a u D3a Dra 9:3R6==T$;0<^;0OW; a ; L-?Y;TWZ07 fpP a ;0<^; P z Z\ZY96?bR68N<^TV8 ` L za ] z [+
j

max

j

!"#%$&' ( )+*,*+- .0/ 132 1346571389)+*'. :;=<>@? /BADC EF4G13H <+IJT? /BADC'E_4G13H <+I`
cd;Ze9< 13H+U G f 13H+UR I 138Dg > H,8 MLh Y K 1 OSi 1 I P 1 4jP'13H H,8 MLh 23RDq 23R < OSi'\ I 8[1 P / 1 KSp P EP 1 4jP 1 H H+8 MLh 8 << 4
 1 0 0 1 a M =0 1 0 1 b  0 0 1 1 c

ª;#« 8
4 1

2

3

1

2

3

5

5

d;? /BADC Eo4j1 H <+I9<+KNM 5'5 O [8 1 2313/'13P 2 O < H,8 MLh i \ I®W< 8 W \ I n 4G13H,\ K / M R MLW¨²´³ µ B ³ 3¤ µ7¶3·uµ·¸¹ .

P 3|prec, pj = 1|C

¯°± 8[\,5 K Y34 < 13H+Uj\ 'W OS4 M+K OQR

A B

F

C

H

G L

D

M

J

N Q

E

K

P

ºd;@? /BADC'P E
!"$#%& ')(*+-, ./0 ' 132425&6&7894:0;=<.: >?1A@&6 BCD >FEHGIKJ:0L.MANOMALQPAHSTVW>H84X4>YM3;Z84N0PAV[SJ: LQMA\M3]^\RGPALTS_VYP3]0`ba/cdJ:0L_eT>YP3Vf8AL_gM37MALTMAI-hZL_:0XAgA:07ji;ZS_7] M*WR>[ST;ZPALbJ:0LQM3\M3]kJ: LTeT>[PAVYM&6ml nM

min{x1 + x2 + x3 + x4 } x1 + 2x2 ≥ 2 x2 + 3x3 ≥ 3 x3 + 4x4 ≥ 4 x4 + x 1 ≥ 1

op-, b Cq V[;r:0>s]Ui n 84XAgtMvu w0L_JxRX4XA94w 7gy;rST7S_;zG;ZM*: XAg4: 7LT{Mvu0w L_JxX4X394w07gt:0LTL_:07]Y:|][]EH:=;ZM~}&ST;zG& ;vPA7MAIv: LTLT: 7]Y: ]H]/EHw|94:0L6N0w >H]MKJ: LQMA\M3] (−1) · max{cx : Ax ≤ b} MALQM3IhiM n 84L   −1 −2 0 0   0 −1 −3 0    A=   0 0 −1 −4  , b =  −1 0 0 −1 −1 −1 −1 −1 . c= 

 −2 −3  , −4  −1

c\RGPALTS_VkJ:0LTMA\M3]: N0w0>s] (−1) · min{yb : yA = c, y ≥ 0} MALQM3Iha/: 7\V[N :0>H84WR]YS_;vM3LTSTN0PALQP3VÎAA7-g-9bi141&6 84LT\M3LFl|63MS_]H]fM;ZS_7ST;zGR;: LTL_:07]Y:|][]/EH: n :0L_gA: ]H]^S_V[;rw ]MAN: LTLT: 7]Y: ]H]u0w L_JxX4X394w07g*;ZM~}&ST;zGR;vPA>[MO]Yw >[x7RI P3]a/w VOM*LTS_7:UP3>[STV$:0XAgA:07L_: ][:0IA:|]?S_V (−1)XAgA:0L"V[N 84>[8AN0N0GRIRlibM*\RGPALTS_VkJ:0LTMA\M3]k9Aw0X4xRLS_VMKIA94:|]YIA: N0{ nM

max{2y1 + 3y2 + 4y3 + y4 } y1 + y 4 = 1 2y1 + y2 = 1 3y2 + y3 = 1 4y3 + y4 = 1 y1 , y2 , y3 , y4 ≥ 0

" Cb :0X3g4:07M3\8A][]$:0X3gZ][: ]YVHN0{4L_:0X4: VaF9AM3LT4V i7R:0;J:0L_][w ][LT:07Z7w0X3g&N : ][:0Vl^;ZP3][>[S}.6cJ:0LQM3\M3]YGR7IrMANAi n 84XAg IS93PALQMAVHV[N GIM;ZP3][>[S}7w n P37-g: LT:0;rw ]hX3g4i n 84XAg;rST7R\:07V[84>H<MA7w0V;ZS_7\:0784VHN0LT8AW<MA7LT:0X4MALQPAHS_][;zGV^: 77: IMKJ: LQMA\M3]Y7M3IMK;Z: X484L_\PAVYP3>YMR` op-, b C¤ w0VHN0e]YV[xR7I¥:0XAg G WPA>H84VrX4>YP3J83]Ui;r:0L_g7: I¥:0XAgSTI¡Wb847]Y8AV[N ]YPAL_g4PA<MA7)LTw|94{+u V[hu VYMASMAN MA\8A]H];vP3][>[S¦}§VH84>YMAS_7MAIi¨;ZPAV[S_I©Wb847]Y84VHN ]P3L_gP3<MA7LTw 9A{¥u0V[hRu0VYM3S=M¡;ZP3]Y>HS}ª8AV[N0L_84WMAS_7MAI¥J:0L_:0L«EH: 7:0I ;Z: X6"¬S_7\: 7VH84>[7MAIy;r:0XAJ: LT:0L_{vu V[hu V[8A]IA4VHV[x7RI4V[VHN0:*;ZS_7\: 784V[N LT84W7MAIt;r:0XAJ: LT: LT{vu V[hu u0V[MALw0V MAN?eTX3gZI3:0L_: ]YI3:0N { e w0L n :0N>H:07\R:0L«EHxR7IZ: XAg w(e) V[hRL_g-]UM;Z: XAJ:0L_:0LT{V[84>¨w Vk84VHN0LT8AW IA:0>H:0VHN ]Y: N0{\w0VHw0HS}&:0L_:0;r: ]U6c§J: LQMA\M~];r84VH][;vPA>®MANAi n 84XAg GH:0WL_{Zw LT: I4V[VHN0VHhL_g4MZ;rST7S_;vPAL_STV 6 ¬:0X4;zG&]M3]EHGIi n 84X3gv: NMJ:0LTMA\M3]$;r:0XAJ84X4MALT;ZMAN n M3]YLTS_7:UP3>[STVfW>H84X4>YM3;Z84N0PAV[SJ: LQMA\M~]YIAw 7]U6¬S_94: L STV[;r:0>s]Ui n 84XAg: N0: I ;Z: X484LT\PAVYPA>[M=93MA7W.84L_ST78A;¯S_\:°EH£MAL_X484>[S]Y;zGRV0i:0N0N :0LMzJ:0LTMA\M3][8A]¨;r:0X484L_\~EHGI6 L_V[{¥IA4N :0L_e_]Yw V[s]Yw0I-£±W>[84XA>YMA;r84NUP3V[SWR>[84<L_w0;ZMAIAw 7] J84XMAL_;vMAN N0GI²;r:0X¥M+J:0LTMA\M3][8A]U6 ¬ST7\R:07 e w0L n :0N>[: 7\:0L³EHx7I²:0XAg x(e) 93PAL_][84N03]UifMA;r:0L_g>H:e_>EHGI¡J:0LOMAN 0 ≤ x(e) ≤ 1 :0X3g4:07RLT{A]s LT:07RV[w0XA:0IA:|]*w0VK\: I-LQMA>[PAL«EHGI x(e)´]K:0X4w V[N w0>H][w0I-£7: I6^N0N :0Lk7gSTL93PA7¥MAN ]zXMA>YM37-]YPAL«EHGRIbi n 84X3g+;rST7\R:07

R2 ij93MAXAg¥rw0>s]Yw0I-£j6^w LTG7Ii n 84XAgMANrw0>s]Yw I£93PAL_][84N04I-7M3Iy;Z: XAJ:0L_:0L_{w LT: IyLT:|J84X4w0L n MALT;ZMAN|] MALTI384V[V[MA7MAI6 nn :0N:0L_w0Xz;rST7R\:07 v u0VHhu0VH>YMzJ:0L_eT>H7S:0XAgZ:0XAgA:07L_{A]YL_:07RV[w0XA: ]U n M v>H:MAN e , . . . , e w LT:0I STLTL_:0VHN0IA: \7: Ibi~MAI-I384> X x(e ) ≥ 1 w WWb:07zM3N ]J:°EH:0N S-ISi n 84XAg v %>[:STL_LT: V[N0I3:0\S_I?LT: XMALTPA<<*$I-S9AP3LQMAVHN ]Y83][] w0L´6N w0>H]=MI3M3W.8A]H]:0XAgA:07L_{A]YL_:07VHw0X4>H:07\VHN0: >=:0XAw0V[NZ;Z: X484L_\PAVYM3ST7M P w(e)x(e) LTS_7:UP3>[STV?JxRX4XA94w 7g] ;ZS_7ST;ZMALTS_NUPAL93Ma93MAXAgM377MAIy: LTL_:07]Y:|][]/EHw|];vM}RS_;vM3LTSTN0PAL_93Ml$93MAL_4<MA7;r:0XAI3M3WR]YGIyMI-S]Y£N A][]J: LQMA\M~] :0X4w V[N0w >H][w0I-£yW>H84X4>YM3;Z84N0PAV[S.;Z: XAJ84XM3LT;ZMANUPAV[P3]U6 : XAgxI w0VHN0>H:Ai n 84XAg MKJ: 7]YSjJ:0LTMA\M3] n 84N?]YMA>H][84N0*:0X3g&x&][] n M3]Y4;ZP3][>[S}

x(e)

1

d

d

i

i=1



 −B  E , −E

M n 84L B M G WPA>[8AV²XA>YP3JSTL_LT:0VHN0I3:0\w V[S;vP~]Y>[S¦}RMR6K¬S94: L B ]Y83]PAL_STVYM37 G7S_;Z8\GLTPA>[S_Vªa:07R\V[N :0>s 84WR]YS_;vM3LTSTN0PALQP3VIAA7-g-9bi466][w ]Y: LFli3M]MA7-GL]][>[S_9STPALTS_VjLT: ;Z;ZMVHN0: >[ST7]ä:07\VHN0: >[84WR][ST;ZMALTS_NUPALTPAV"IAA7-g-9bi 46_U@R6jLT: ;Z;ZMlMJ: 7-][S:0XAgxR]H] n M~]Y4;ZP3]Y>HS}yV[N0S_7]Yw07MAN36¬S_9A:0LMAN*:0X3g4:07RLT{A][LT:07RV[w0XA:0IZEH84<<84L_\MALQM3ST7tS_V :0X4w V[N0: IzPAL_LT7M3Ira/;rST7\: 7 n 84L ±1 93MAXAg=2l|i~:0N w0>s]MJ:07]YS q J: LQMA\M3] n :0L_gA: ]H];Z: X484L_\ n M3]EHGIM;r:0XAJ: LT:0L_{ J: LQMA\M3]Y8A]S_V0i-M]MA7-GL]]Yw ][:0LV[N :0>HST7]a/: 7\VHN0:0>H84WR][ST;ZMALTS_NUPALTPAV®I347g9bi.46_1&6A]Yw|]Y: LFlMI3w ]$84WR]YS_;zG; MAN0847R84V06 D XAg MKJ: LQMA\M3]Y8A]^9AM3LT4<M37 V[STI3:0>HxL_] J: LQMA\M~]YIAw 7]O;r:0X3J84XMAL_;vMAN 7S´6 "C PA7g-Jw0L_:7:0;rSTN 84;r84>HJ;ZM3]Y>H84ST\R8A]^>H:0W>H:0N :07]PAL n M3]Mz93MALTAV^]Y: VH]¨J:0L_: ]H]MANMALTPA<<S.;vP3][>[S¦} I-xLT47 x <.4N {K9AP3LQMAVHN ]P3VYMASj;r:0L_LT:|][] c n 84L"M*;vM3][>[84S_\X4>[ M I-GV0i83][]X4>YP jMAL.STVMA\EHGI;r:0X` 

 1 0 1 0 1 3 0 2 x

o -, b C c±@: LT:0;=£ZM3LQMAW n MALT;ZMAN¨1?: LT:0;=£Z>Hw0V[N n MAL_;vMAN0MASR;rST7R\*JxRX4X4: ][LT: 7:0Ii n S_V[N0: 7ZVH:0;r:0Lg&S_I=I3w ] p 84V[N LT84W94: I]Y84>k7R:0; L_: n :|]kWP3> n GNUM3;Z84Va x w0>s]Yw0I3w ][{4LJxX4XA: ]YL_:07-xLQl|6-c ;ZP3]Y>HS}r\:|]Y:0>H;ZS_7PA7V[M a/Wbw0L_\PAGL MANv: LTV[{t84V[N LT84W VHN0: >[ST7][S$I-S_J:Es]Yw V[H]*M3N :0VH: ]YkM=;vP~]Y>[S¦}rMAN U aV[N0MA<MAx\−l;v6 M~]Y>[8AST\8A]f>H:0Wx>H:06=N0: 76]PAL³E[MR6RNM=;vM~]Y>[8AST\rX4>YM IGRV0iW.w LT\PAGRL :0XAg§@¥w LT£ªhR]I34>[;ZM3][>[84S_\~E[MR6cN : V[: ][<.: 79S_V[N08A7-]u VYMAI§M¥L_:0XAJAL«EH:0s]^: I-IA84>$M;vP3][>[S¦}KxMAN =U 6 ;ZM3][>[84S_\8A]>H:0W>H:0N :07]PAL³E[MR6-NSTVX4>YM I-GV0i: XAg n PA>H84; w LT£ IA4>IAA>[;ZM3]Y>H84ST\~E[M&6 6ªM~]PA>H84N0N GI ;r:0X M3N w0V C cN P3<>YPA7 LTP3] n M3]Y X4>YP3JI34>[;ZM3]Y>H84ST\E[M LT: XAg4: 7 MAN M ∨ U ;vM3][>[84S_\&AV[V[N :0X4: IA:|]U`²c n 84L±MAN 4V[VHN0: X MX4>Y M IGRV0i©83][]¯X4>Y P MALdSTV¯MMA\~EH∨GRI M;r:0X` 3,3

3,2

5,2

4 1

2

3 5

o -, b C cN M ∨M ;vM3][>[84S_\<MA7=W.847][84VYMA7*M3N084IM n MAL_;vMAN 84IJxX4X4:|]YL_:07: IbiAMA;r:0L_gA:0IMAN {1, 2, 3} p :0LT: ;Z: II34N0xRLLT:0X3J4L«EH: <s]MAL_;vM3N07MAI6 OXAg4MA7S_V;ZS_7\: 7 M s]MAL_;vMAN n M3]fMAN {1, 2, 3} :0L_:0;r:0IKIAAN0xLi&: N0w0>s]kI3w ]¨S_L_g4: 7 n M3LT;ZMAN¨G7S_~E[MaF9AM3XAgSTVf:0XAg (M ∨ M )[w V[N|]Ui n MKWbw0LT\PAGL: XAg>Hw0VHN n MAL_;vM3N?7:0; ]MA>s]MAL_;vM3N0NUM=MAN : V¨:0LT: ;Z:|]UiM3II384>¨JxX4X4:|]YL_:07ji;r:0>s]¨>[w V[N n MALT;ZMAN0MrM {2, 3, 4, 5}%7:0I RG&]Y4<H] M {2, 4} w VM {3, 5} IA4>H;Z: 7-][:0V>[w V[N n MALT;ZMAN 84IGR7ST~E[M&6jM3V[847L_ 84IA8AIH]YMALT;ZMAN NUMR6 ;r84Vs]Y;ZPA>I3477g4: 7LTP3] n M~]YMA7tX4>Y M IGRV0"M X4>YP3J<MA7 2, 3} MALTI384V[V[MA7MAI n PA>H84;ZVHN03 X4: ]0iM M ∨~:0MVw Vz5%4Vw0L_:0I-7: IW.: \STXLT: XAJ4L³EH:0<<: XAgIAAN04GVu0VHhu0V[MLT: XA{1,g4: 7+ M n PA>H84;rV[N0AX4X4:0L : II384> G IA4>H;vM3][>[84S_\~E[M=w WW.: 7 M ∨ M 6

Oc N M ∨ U ;ZM3]Y>H84ST\<MA7ML_:0XAJAL«EH:0Hw0V[N n MAL_;vMAN 84ItJxXAX4: ][LT:07R:0Iij93MAXAgSTV M ∨ U STN08A;Z84>sJ U %XAg4: L´6 OXAg4MA7S_V M %<.: 7;ZS_7\: 7ZJxX4XA: ]YL_:07ZLT:0X3J4L«EH: <<1:0LT: ;z£a/MAN?M3\8A][]$X4>[P3J<MA7Z7ST7u V @ w0LT£©IA4>H;Z: 7-][:0V >Hw0V[N n MAL_;vMANUl|i$:0N0w >H]: XAg Hw0VHN ] n M:0XAg :0LT: ;z£*>[w V[N n MALT;ZMAN0:0L_{PALTL&W.w LT\P3GL {2, 4} ∪ {3, 5} MALTMAI-<MA7ji 9AM3XAgSTV:0X3g M M?>Hw0VHN n MAL_;vM3N :0LT{4PALTL {3, 5}∪{1, 2} MALQM3I<MA7ji9AM3XAgSTV (M ∨U )[S_7]OS_V[;rw ]¨XA>Y M I-GV i n STVHN0:07 U M3N=5zw LT£IA4>I34>[;ZM3]Y>H84ST\E[MR6 M ∨U <.:|]Y£ n MALT;ZMAN ]0iw0VMAN=:0LT: ;Z: STHw0VHN n MAL_;vM3N084I~M3]aMKV[N0M93MAIvGR]PA7RSNUP3>[~EH: LT
5,2

5,4

5,2

5,2

5,2

5,2

5,2

5,4

"! # $&%'! ( )*&%'!+,-./&01! ( 23401!5 )(#67)! ( '-$7)!8-( '-$7)!9:3(;<7)!+5#=">&?'!@( #(>A1!B

OMEs]YVHGI¥94w0XA>[:yw Vv\84I-G;r:07]YPAL«EHGI¡: N0: 7dMA\M3][84I-I3M3LMANMALTMAW n MAL_;vM3N >[w0VHN n M3LT;ZMAN084I-I~MAL¨]YA>H]Yw 7{ LT: J: \w0VHw0>H:VHN084L_XPALTRi&: LT{MA\PAV[847 ]YMA7-GL_]I34N0: LTe_][{rMALTX48A>[S_][;zGVs]U6 op-, b C XAgA:0VHw 94: L®93PALQM3V[N ]EHGI M n MALT;ZMAN 84I~M3]Ui&;ZS_7\STXK8AL_gM37 H n MALT;ZMAN|]¨9AP3LQMAVHN ][93MRiR;Z: L_g>[: H IA4L]YV[w X4w07R:0I w0VMANPAL]MALTM=LT:|J:0\:|][]0iMA\\S_X*;Zw X*J: \: ][LT: 7: LT: ;Z: IV[N0PA;vP37MAI n PA7gMA\8AVYMZ;rST7RST;ZPALTS_V06 L_V[{4I3w07]MAN = n MAL_;vMAN|]IA:0L_L93PALTMAV[N|]MA7-G7RIbi~;r:0>H]®:0<[:f:0VH{IA4L]YVHw0X a l|6~c§I39A: ][IA:0N { n MALT;ZMAN$MAN IA:0L_L&L_:0XAgA:07ji3:0N¨M n P3]Y>[MALTw|94E{ DO<.:|]Y£YM3LTw 9A{VHNUMU93MAI¥IA4N xL´6c IA94:|]YI3:0N0{¥I3w ] LTw0Wbw0VH<.: 7 M #() w0V #= n M3LT;ZMAN084I~M3]I3:0L_L93PALTMAV[N|]MA7-G7RIy]Y: ][V[N {4LT: X4:0VV[84>H>[:07R\<.: 7jiGXAgM37STV:0N :0I->[: LT:0VHN*;ZS_7ST;ZPALTS_Va/7:|94:0N : ][:0V[: 7²14l?MANK: XAg:0L_:0;r>[:OEHGR][I34L_][V[w X6 w X4xLM n P3][>YMA;ZMA>YM3\ H]M3LT;ZMAN0;rw0XI-S&7:0;p93PALQMAVHN ][8A][]V[N A]I3:0LTL94: XAgxIi4:0N$W.: \STXM3N¨5I34L_][V[w X4£ #=" 6 cI~MAWb8A]H]kJ:0\w V][: n P~]U { F( 23+G )(#HI J#. } iI34L_][V[w0XA:r5&6 x&]Y:0;r:0N w0VHSJ: LQMA\M3]Y>[MR6 K"C c¨\~EHG7IWb84L_ST784;rSQP3LTSTVM3LTX484>HS_][;zGVH]kMAN* |r |C op-, b LC :0I-S_7-][V[xI²MAN: LTV[{AIAw07]Z>[: 7\:0L_IA: N0w0VH>[:P3LTLT;=G7I~P3]U6N|]aSTVlz: LÏA:0L_L¨94w0XA:0N07RSO: LT{4<< GR]Y4YMEs]MMAN08A77MAL\R84LTX48AN07SiAMAN NUMAL7R:0; 7g4: >[x7RIKV[:0;r;rS_]aV[{A]l|i4I3:0N0\EHxI ]Y: n P3]f:0L´6cd;ZPAV[8\S_II3w07]$>[:07R\:0L_IA:0N w0VH>[:PAL_LT;zGR7I~P93MALS_V n MAV[8A7LTM n :0Lg&N : ]0i&M3N0NUM3L.MI-xLTA7ü0V[MAI MA77MAIvJ84XUEHGI: LTI3:0N0\R:07Si3M3;ZS_IA84>j;ZPA>">H:07\: LTI3:0N0w V[>H:kPAL_L4w0V;rST7\: 7IA84>[PA<<MA7 <.: w0>[I3:0N : ][];zk.G7I~PU93MAL9Aw0X4: N ]YxR7I6 q Lg;r&\8A7 1 3

3 4

i

max{rk +

max

n X

pi | 1 ≤ k ≤ n}

i=k

ST\{M3LQM3]H]®94w X4N0xR7Ii-M n 84L r ≤ r ≤ . . . ≤ r M?>H:07\: LTI3:0N0w V[>H:OP3LTLQP3V[SST\{4I6 ¤ 47R7-gA:07rLQP3] n M3][i n 84XAg:0N 84WR]YS_;vP3LTSTV i n STV[N :07vMAN0847Zw0>s]Yw0I3:0IiR;r:0Lg4: I>H:M;ZM~}&ST;zG;r8A]][:0I-ST7]EHxIi;rST7R\ZM3LTV[YMR6 cNMALTXA84>[S]Y;zGV$W.8ALTST7R84;ZSTMALTS]PAV[M?W.: \STXK][>[S_9STPALTS_V06 1

2

n

max

Rendszeroptimalizálás Pótzárthelyi feladatok 2005. de ember 20.

1. Döntsük el, hogy az x = 1, y z = 3 választással

2. Egy

= −2,

G irányított gráfban irányított körök egy {C1, C2, . . . , Ck } halmazát nevezzük irányított körpakolásnak, ha a Ci körök páronként éldiszjunktak. Adott G irányított gráf és w : E(G) 7→ R+

a) bázismegoldását b) er®s bázismegoldását adtuk-e meg az alábbi egyenl®tlenségrendszernek:

nemnegatív élsúlyozás esetén feladatunk egy maximális összsúlyú irányított körpakolás megtalálása. (Egy körpakolás súlya a benne szerepl® körök élei súlyának összege.) Bizonyítsuk be, hogy létezik polinomiális idej¶ algoritmus ennek a feladatnak a megoldására! 4. Az ábrán látható gráf körmatroidja legyen M . Határozzuk meg az M ∨ M és az M ∨ U4,2 matroid-összegeket! Ahol az összeg grakus, ott gráal is adjuk meg!

x−y+z ≤6 2x + y − 2z ≤ −6 3x − z ≤ 1

3. Hányféle nemizomorf matroidot rep-

rezentálhat a valós test felett az alábbi mátrix x különböz® választásai mellett? Ahol a matroid grakus, ott gráal is adjuk meg! 

3 1



1 0 2 3 0 1 x 9 0 2 4 6

2 4

5. Mutassuk meg, hogy a Graham-féle listás ütemezési algoritmus approximá iós fak-

tora két gép esetén nem lehet jobb, mint 3/2. (Azaz mutassunk példát olyan ütemezési feladatra, amelyre az algoritmus által adott eredmény az optimumnak legalább 3/2szerese.)

6. Adjuk meg az alábbi pre eden iagráal megadott P 2|prec, pj = 1|Cmax feladat egy optimális megoldását a Coman-Graham algoritmus segítségével. A

E C

F

B

D

K

L

H

G

J

A feladatok megoldásához segédeszköz nem használható. A rendelkezésre álló munkaid® 100 per . Nem szükséges minden feladatot külön lapra írni, de kérjük, hogy a beadott dolgozat szétválaszt-

ható legyen 3 részre: az 1-es/2-es, a 3-as/4-es, illetve az 5-ös/6-os feladatpárokra.

Rendszeroptimalizálás Zárthelyi feladatok és megoldások 2006. de ember 9.

1.

Döntsük el, hogy az

x1 = 1, x2 = 2, x3 = 1, x4 = 0

választással

a) bázismegoldását b) er®s bázismegoldását adtuk-e meg az alábbi egyenl®tlenségrendszernek:

x1 + x2 ≤ 4 x1 + x3 ≤ 2 x2 + x4 ≤ 2 x1 + x2 + x3 + x4 ≤ 4 Megoldás.

Ax ≤ b, ahol   4 2  b=  2 . 4

Az egyenl®tlenségrendszer mátrixos alakja



1 1 A= 0 1

1 0 1 1

0 1 0 1

 0 0 , 1 1

A utolsó sora az el®z® kett® összege, az els® három sor viszont lineárisan független, így r(A) = 3. A megadott x1 = 1, x2 = 2, x3 = 1, x4 = 0 megoldás az A második, harmadik Látható, hogy

és negyedik sorának megfelel® egyenl®tlenségeket teljesíti egyenl®séggel, az els®t nem. Ezért az egyenl®séggel teljesített sorok alkotta mátrix rangja sak 2 (mert az utolsó sor az el®z® kett® összege), így a megadott megoldás nem bázismegoldás (és így persze nem is er®s bázismegoldás).

2. Egy G irányított gráfban irányított körök egy {C1 , C2 , . . . , Ck } halmazát nevezzük irányított

körfedésnek, ha

a

Ci

körök páronként sú sdiszjunktak és a gráf minden sú sa rajta van vala-

melyik körön. Legyen adott egy

G

irányított gráf, amelyr®l tudjuk, hogy van benne irányított

körfedés. Legyen adott továbbá egy

w : E(G) → R

élsúlyozás. A feladatunk egy maximális

összsúlyú irányított körfedés megtalálása. (Egy körfedés súlya a benne szerepl® körök élei súlyának összege.) Bizonyítsuk be, hogy létezik polinomiális idej¶ algoritmus ennek a feladatnak a megoldására!

Els® megoldás.

Megmutatjuk, hogy ez a feladat megfogalmazható lineáris programozási fel-

adatként. Mivel ismert, hogy ezek megoldására van polinom idej¶ algoritmus, ezzel a feladatot megoldjuk. Els® közelítésben egészérték¶ programozási problémaként fogalmazzuk meg a feladatot. Minden

e

élhez rendeljünk egy

ségeket és deklaráljuk

x(e)-t

x(e)

változót, amelyre írjuk fel az

0 ≤ x(e) ≤ 1

egyenl®tlen-

egészérték¶nek. Ezzel nyilván azt garantáljuk, hogy minden

x(e)

0, vagy 1 érték¶. Célunk, hogy az 1 érték¶ változóknak megfelel® élek irányított körfedést alkossanak. Az irányított körfedés más megfogalmazásban az élek egy olyan teljesül, hogy minden sú sba pontosan egy lép ki. Ezért elég minden és

v -b®l

az

f1 , . . . , fd

azt fejezik ki, hogy

v

E0 -beli él lép be

részhalmaza, amelyre

E0 -beli él

v -be az e1 , . . . , er élek lépnek be d X x(ei ) = 1 és x(fi ) = 1 egyenletek éppen

sú sra felírni két egyenletet: ha r X

élek lépnek ki, akkor az

v -be

E0

és minden sú sból egy

i=1 egy kiválasztott él lép be és

v -b®l

i=1 egy kiválasztott él lép ki. (Avagy,

a hálózati folyamok kap sán a Rendszeroptimalizálás könyv 36. oldalán bevezetett jelöléseket

̺x (v) = 1 és δx (v) = 1.) Így a kapott egyenl®tlenségrendszer egész megoldásain a w(e)x(e) lineáris függvényt maximalizálva valóban megkaptuk a kit¶zött feladat egészérték¶

alkalmazva:

P

programozási megfogalmazását. Célunk azt megmutatni, hogy a fenti rendszert leíró mátrix totálisan unimoduláris, mert

ebb®l (tekintve, hogy az egyenl®tlenségek jobb oldalán álló számok egészek mindenhol

±1

vagy 0) valóban következik (Rendszeroptimalizálás könyv, 1.12. tétel), hogy a fenti IP feladat helyett megoldhatjuk a megfelel® LP feladatot is, a két optimum azonos. r d X X

x(ei ) ≤ 1 és

Ehhez a rendszert leíró mátrixból elég sak a

és

δx (v) ≤ 1)

i=1 soroknak megfelel® részt jelöljük ezt

rendszert leíró mátrixot úgy kapjuk, hogy el®ször

M -mel

M

x(fi ) ≤ 1 (azaz: ̺x (v) ≤ 1

i=1 vizsgálni, mert ebb®l a teljes

sorainak ellentettjét vesszük hozzá

M-

hez (hogy a fenti egyenl®tlenségekb®l egyenletet sináljunk), majd az egységmátrixot és annak ellentettjét vesszük még hozzá (a

0 ≤ x(e) ≤ 1

feltételek miatt). Ezek a kiegészítések azonban

a tanult triviális lemma szerint (Rendszeroptimalizálás könyv, 1.13. lemma) meg®rzik a mátrix totális unimodularitását.

M

sorai kétfelé választhatók: az

r X

x(ei ) ≤ 1 (azaz ̺x (v) ≤ 1), illetve az

i=1

d X

x(fi ) ≤ 1 (azaz

i=1

δx (v) ≤ 1) egyenl®tlenségeknek megfelel® sorokra; jelöljük az els® részt M1 -gyel, a másodikat M2 -vel. Mivel minden irányított él egyetlen sú sból lép ki és egy sú sba lép be, ezért M minden oszlopában pontosan két darab 1-es van, az egyik M1 -ben, a másik M2 -ben; minden más elem 0. Ezért M egy páros gráf illeszkedési mátrixa: a páros gráf mindkét osztálya az irányított gráf sú shalmazának felel meg, és minden irányított élb®l a páros gráf egy éle keletkezik. Ezért

M

valóban totálisan unimoduláris (Rendszeroptimalizálás könyv, 1.14. tétel),

amivel a feladatot megoldottuk.

Második megoldás (vázlat).

V (G) sú sezeket V1 -gyel és V2 -vel és G minden u → v irányított u-nak a V1 -beli megfelel®jét kössük össze v -nek a V2 -beli

Készítsünk

halmazt két példányban jelöljük éle esetén a készül® páros gráfban

G-b®l

egy páros gráfot: vegyük fel a

megfelel®jével. (Ugyanez a páros gráf került el® az els® megoldás végén is.) Az így kapott élhez rendeljük hozzá az

u→v

él

G-beli

súlyát. Nem nehéz végiggondolni, hogy a

G-beli

irányított

körfedések a kapott páros gráf teljes párosításainak felelnek meg. Ezért a feladatunk maximális összsúlyú teljes párosítás keresése páros gráfban, ami megtehet® az Egerváry-algoritmussal.

3.

Lehet-e olyan értéket adni az

test felett koordinátázott

M1

a

paraméternek, hogy az alábbi mátrix oszlopai által a valós

matroid grakus legyen?

 x 1  0 −2 Megoldás.

Látható, hogy a mátrix

u

y u v w  0 −2 1 a 1 0 1 −2  2 4 0 −4 oszlopa

(−2)-szerese

az

x

oszlopnak, így a készül®

x, y és v oszlopok között hogy x + y = v ; ezért ennek

grakus reprezentá ióban ezeknek párhuzamos élek felelnek meg. Az nin s olyan pár, amelyek párhuzamosak volnának, de jól látható,

a három oszlopnak egy három él¶ kör felel meg. Az els® négy oszlopnak megfelel® rész tehát egy olyan háromszöggel reprezentálható, amelynek az egyik élét megdupláztuk. Így a kérdés az, hogy

a

értéke megválasztható-e úgy, hogy a

w -nek

megfelel® él hozzávehet® legyen ehhez a

gráfhoz. A válasz igen. Legegyszer¶bb talán az szerese az

y

a=0

választás. Ilyenkor ugyanis a

w

oszlop

(−2)-

oszlopnak, így a gráfban a megfelel® élek párhuzamosak; ezt mutatja az alábbi,

bal oldali ábra. Némi számolással az is végiggondolható, hogy

x, y, v

a 6= 0

esetén

x, y, v, w

közül az

hármast leszámítva bármely három oszlop lineárisan független. Ezért a matroid ilyenkor

is grakus, a megfelel® gráfot az alábbi, jobb oldali ábra mutatja. Vagyis a matroid valójában az

a paraméter minden értékére grakus (amit persze a feladat teljes érték¶ megoldásához nem

szükséges végiggondolni).

x

u

v x

w

v

u

y 4. az

w

y

M2 matroidot az alábbi mátrix koordinátázza (a valós test fölött). Mutassuk meg, hogy M1 ∨ M2 matroid (ahol M1 az el®z® feladatbeli M1 -gyel azonos) az a paraméter bármely

Az

értéke esetén grakus!

x 1 0 Megoldás.

Az

M2

y 1 1

u 1 2

matroid jól láthatóan az

v 1 3

U5,2

w 1 4 uniform matroid (azzal izomorf ), hiszen a

mátrix bármely két oszlopa lineárisan független, de bármely három tekintve, hogy síkbeli vektorokról van szó lineárisan összefügg®. Ezért az hogy az

M1

M1 ∨ M2

matroid függetlenjei úgy kaphatók,

matroid függetlenjeit kiegészítjük két tetsz®leges elemmel.

Az el®z® feladat megoldásából kiderül, hogy az

M1

a

rangja (bázisának mérete)

függ®en 2 vagy 3. (Ehhez nin s szükség a fenti megoldásban az

a 6= 0

értékét®l

eset részletes végiggon-

dolására.)

M1

Ha az

rangja 3, akkor egy bázisát a hiányzó két elemmel kiegészítve az

halmazt kapjuk; ez tehát független

M1 ∨ M2

az

U5,5

{x, y, u, v, w}

M1 ∨M2 -ben (és persze minden részhalmaza is), így ilyenkor

szabad matroid. Ez valóban grakus, bármely 5 él¶, körmentes gráf reprezen-

tálja. Ha az

M1

rangja sak 2, akkor

M1 ∨ M2 -ben

a független halmazok legföljebb 4 elem¶ek.

Könny¶ azonban végiggondolni, hogy minden 4 elem¶ halmaz független: kételem¶ek közül sak az

{x, u}

és esetleg az

{y, w}

M1 -ben

ugyanis a

összefügg®. Nyilván tetsz®leges 4 elem¶

részhalmazt felbonthatunk 2 darab 2 elem¶re úgy, hogy ezt a két párt szétválasszuk, amivel a részhalmazt egy

U5,4

M1

és egy

M2 -beli független

uniójára bontottuk. Ezért ilyenkor

M1 ∨ M2

az

uniform matroid, ami szintén grakus: egy 5 él¶ kör reprezentálja.

(Mindezt az el®z® feladat megoldásában írtakkal összevetve az is kiderül, hogy az összeg

a 6= 0-ra az U5,5 -tel, a = 0-ra az U5,4 -gyel izomorf; ennek

M1 ∨ M2

végiggondolására sin s szükség

a feladat teljes érték¶ megoldásához.)

5. Igaz-e, hogy mindig létezik a munkáknak olyan sorbarendezése,

amely sorrendben a Graham-

féle listás ütemez® algoritmust végrehajtva optimális megoldást kapunk a

Megoldás.

Az állítás igaz. Tekintsünk egy olyan

S

P ||Cmax

feladatra?

optimális ütemezést, melyben egyetlen

gép sem áll, amíg van el nem kezdett munka. Megmutatjuk, hogy ilyen létezik. Induljunk ki egy tetsz®leges optimális ütemezésb®l. Egy gépen a két munka közti esetleges állásid®ket megszüntetve a teljes átfutási id® nem n®het. Ha egy gép utolsó munkája után még lenne elkezdhet® feladat, vegyük a legkorábbi ilyen utolsó munkát, az ennek befejezésekor elkezdhet® feladatot valamely más gép kés®bb kezdené el; ekkor a másik gép összes hátralev® munkáját erre a gépre át soportosítva a teljes átfutási id® nem n®ne. E m¶veletet szükség esetén többször

is elvégezve felesleges állásid® nélküli ütemezést kapunk, melynek átfutási ideje nem nagyobb az eredetinél, így maga is optimális. Az eljárás biztosan végetér, hiszen a felesleges állásid®k kezdetének minimuma szigorúan monoton n® egy lépés során. Vegyük most a munkáknak egy olyan sorrendjét, melyet az

S

szerinti kezdési id®k határoz-

nak meg. Nyilvánvaló, hogy a listás ütemezés ebben a sorrendben optimális lesz, hiszen sem

S -ben,

sem a kapott listás ütemezésben nem áll egyetlen gép sem, amíg van el nem kezdett

munka, így a két ütemezés munkáinak kezdési és befejezési idejei is azonosak lesznek.

6.

Mutassuk meg, hogy a ládapakolás feladatra adott First Fit algoritmus approximá iós fak5 tora nem jobb, mint . 3

Megoldás.

Legyenek a ládák 100 egység térfogatúak és tekintsük a

15, 15, 15, 15, 15, 15, 34, 34, 34, 34, 34, 34, 51, 51, 51, 51, 51, 51 bemenetet. A First Fit ezt láthatóan 1+3+6=10 ládában helyezi el, míg az optimum 6 láda lenne.

Rendszeroptimalizálás Pótárthelyi feladatok

2006. de ember 19. A Fourier-Motzkin eliminá ió segítségével döntsük el, hogy van-e megoldása az alábbi lineáris egyenl®tlenségrendszernek. Ha van megoldás, adjunk is meg egyet.

1.

x+y+z ≥8 2x − y + 2z ≤ 8 x + 2y + 3z ≤ 10 x ≥ 0, y ≥ 0, z ≥ 0

Tegyük fel hogy az Ax ≤ b lineáris egyenl®tlenségrendszer megoldható. Döntsük el, hogy igazak-e az alábbi állítások! a) Ha az Ax ≤ b rendszernek van olyan bázismegoldása, ami nem er®s bázismegoldás, akkor az A mátrix oszlopai lineárisan összefügg®k. b) Ha az A mátrix oszlopai lineárisan összefügg®k, akkor az Ax ≤ b rendszernek van olyan bázismegoldása, ami nem er®s bázismegoldás. 2.

Az a paraméter mely értékei mellett lesz az alábbi mátrix oszlopai által a valós test felett koordinátázott matroid grakus?

3.

4.

1 2 3 4 2 3 4 a

Grakus lesz-e az alábbi két gráf körmatroidjának az összege? a

b

e c d

a b d e c

Létezik-e a ládapakolás feladatnak olyan bemenete, melyre az optimális megoldás 2 láda, a First Fit De reasing algoritmus (melyben a tárgyakat sökken® súly szerinti sorrendben helyezzük el a First Fit algoritmus segítségével) viszont 3 ládába pakol?

5.

Tekintsük a P 3||Cmax feladatot. Mutassuk meg, hogy Graham listás ütemez® algoritmusának approximá iós faktora nem jobb, mint 78 . 6.



Rendszeroptimalizálás Zárthelyi feladatok

2007. november 28. A Fourier-Motzkin eliminá ió segítségével döntsük el, hogy a p paraméter milyen értékeire van megoldása az alábbi lineáris egyenl®tlenségrendszernek.

Az A mátrixra teljesül, hogy minden, az A soraiból készített lineáris kombiná ióként el®álló sorvektor tartalmaz 0nál nem nagyobb elemet. Bizonyítsuk be, hogy az A oszlopaiból a nullvektor kifex − 2y − z ≤ p jezhet® nemtriviális módon (vagyis nem 2x − 3y − 2z + 28 ≥ 0

supa nulla együtthatót használva) nemx + 2y + z ≤ 21 negatív együtthatós lineáris kombiná ióx ≥ 0, y ≥ 0, z ≥ 0 val. 3. Grakus-e az alábbi két gráf által meghatározott matroid összege? 1.

2.

b

d c e

c

a

b f

d

a

e f

Válasszuk meg a p és q paramétereket úgy, hogy az alábbi mátrix által meghatározott matroid a) grakus legyen; b) ne legyen grakus.   4.

1 2 3 1 2 p 2 0 5 q 5 0

Tekintsük az {a,b, ,d,e,h,i,k,l,m,n,o,p,r,s,t} bet¶halmazt, és az elemeib®l képzett alábbi szavakat, mint részhalmazokat (a szavak utáni zárójelben lév® szám jelenti az adott halmaz költségét): 5.

od (3), per h (3), arp (4), pike (4), dab (5), ten h (5), salmon (5), hake (5), bream (6), sprat (6).

Hajtsuk végre ezen adatokkal az alaphalmaz részhalmazokkal történ® lefedésére szolgáló, el®adáson tanult közelít® algoritmust. Igaz-e, hogy ha a pre eden iagráf minden pontjának kifoka legfeljebb 1, akkor a P |prec, pi = 1|Cmax ütemezési feladat polinom id®ben megoldható?

6.

A feladatok megoldásához segédeszköz nem használható. A rendelkezésre álló munkaid® 100 per . Nem szükséges minden feladatot külön lapra írni, de kérjük, hogy a beadott dolgozat szétválasztható legyen 3 részre: az 1-es/2-es, a 3-as/4-es, illetve az 5-ös/6-os feladatpárokra.

A zárthelyi feladatok megoldása Az 1. feladat megoldása. Az egyenl®tlenségrendszer mátrixos alakja







1 −2 −1  −2 3 2     1 2 1 ,  A=  −1 0 0    0 −1 0  0 0 −1

p 28 21 0 0 0

   b=   

Ax ≤ b,

ahol



   .   

Az eliminá iót (a Rendszeroptimalizálás könyv 17. oldalán írtak szerint végezve) végezve a következ®ket kapjuk:







1 2 1 21     1 −2 −1 p         3  −1 2   1 14  ∼     −1 0 0 0       0 −1 0 0      0 0 −1 0

0

7 2

2

35

0

2

1

21

0 − 12

0 p + 14

0 −2 −1

p

0 −1

0

0

0 −1

0

0







4 7 1 2

1 10    21    1   2       −1  2p + 28 0 ∼ ∼   p    −1 − 21 2       −1  0 0    0 0 −1     0 74 2p + 38 1 72 (p + 19)    p+20  0 1   1 7(p + 20)  14 2        35  4 10   1 0 7 2      4p+77  1    ∼0 2  ∼  1 4p + 77  2    p+21  0 0   1 21  2     0 1   −1 21  0     2 2 0 −1 0 0 p + 21

A kapott alak utolsó sora miatt a rendszernek sak

p + 21 ≥ 0

esetén lehet megoldása, ebben az

esetben viszont ez a sor elhagyható. Az utolsó el®tti sor ekkor azt jelenti, hogy viszont

z -re

z ≥ 0.

Az els® 5 sor

vonatkozó fels® korlátokat jelent, így a rendszer megoldhatósága azon múlik, hogy ezek

a fels® korlátok mind nemnegatívak legyenek. Ez a harmadik és ötödik sorra fennáll, a többi sorból pedig a

p ≥ −19, p ≥ −20,

illetve a

akkor és sak akkor megoldható, ha

p ≥ −19.25 p ≥ −19.

korlátokat kapjuk. Ezek összevetéséb®l a rendszer

A 2. feladat megoldása. Azt kell bizonyítani, hogy létezik olyan

x ≥ 0, x 6= 0.

x

oszlopvektor, amelyre

Erre az alakra a Farkas-lemma közvetlenül nem alkalmazható az

x 6= 0

Ax = 0,

feltétel miatt.

x megoldása λ · x is megoldás lesz minden λ > 0-ra. Ezért az x komponenseinek összegét alkalmas λ válasz-

Ezen azonban könnyen segíthetünk, ha észrevesszük, hogy a vizsgált rendszer bármely esetén

tásával tetsz®leges pozitív értékre beállíthatjuk. Így a bizonyítandó állítás ekvivalens módon úgy is megfogalmazható, hogy az

Ax = 0, 1·x = 1, x ≥ 0 rendszer megoldható (ahol 1 a supa 1 sorvektort

jelöli). Erre az alakra pedig már alkalmazható a Farkas lemma (Rendszeroptimalizálás könyvbeli, 1.4

0 1

(y|µ) sorvektor, amelyre (y|µ)

Tételnek megfelel® alakja). Azt kapjuk, hogy ha az

volna megoldható, akkor létezik olyan

A 1

·x =

x ≥ 0 rendszer indirekt nem A 0 ≥ 0 és (y|µ) · < 0. 1 1

,

1·x = 1 sornak megfelel® komponensét különváyA + (µ, µ, . . . , µ) ≥ 0, µ < 0. Vagyis az yA sorvektor nagyobb-egyenl® a supa pozitív elemeket tartalmazó (−µ, −µ, . . . , −µ) sorvektornál. Ez ellentmond a feladat feltételének (hiszen yA az A soraiból készített lineáris kombiná ió).

(Itt a Farkas-lemma által garantált sorvektor utolsó, lasztottuk és

µ-vel jelöltük). Átrendezve

ez azt jelenti, hogy

A 3. feladat megoldása. Jelöljük a bal oldali gráf által meghatározott matroidot

oldali által meghatározottat

M2 -vel. M2 -ben

az üres halmazon kívül sak

{a}

M1 -gyel,

a jobb

független (hiszen a

többi elem hurok). Ezért a két matroid összegének függetlenjeit úgy kapjuk, hogy

M1

független-

a-val. M1 bázisai (maximális körmentes élhalmazai) jól láthatóan a {d, e} és M1 ∨ M2 bázisai az {a, d, e}, {a, d, f } halmazok lesznek (és így ezek részhalM1 ∨ M2 függetlenjei). Könnyen látható, hogy ez a matroid is grakus, az alábbi gráf

jeit kiegészít(het)jük

{d, f }

halmazok. Így

mazai lesznek reprezentálja.

e d f a b

c

A 4. feladat megoldása. Jelölje a mátrix 4 oszlopát sorban

M

matroidban

a, c

és

d

a, b, c és d. A mátrix által reprezentált

háromszöget (három elem¶ kört) határoznak meg, hiszen közülük semelyik

kett® nem párhuzamos, de a három oszlop együtt lineárisan összefügg® (c = a + 2d). A b oszlop 10 4 akkor lesz párhuzamos a-val, c-vel, illetve d-vel, ha p = q = 0, p = , q = , illetve p = 4, q = 10. 3 3 Ezekben az esetekben M grakus, hiszen reprezentálja az a gráf, amelyet egy háromszög egyik élének megduplázásával kapunk. Egyéb esetekben azt kell ellen®riznünk, hogy az halmazok függetlenek-e; ezt legegyszer¶bb a 3 darab

3 × 3-as

{a, b, c}, {a, b, d}, {b, c, d}

determináns kiszámításával megtenni.

Mindhárom esetben azt kapjuk, hogy a halmaz akkor és sak akkor független (azaz a determináns

5p 6= 2q . Ez azt jelenti, hogy 5p 6= 2q esetén M ismét grakus: ha b élet, a kapott gráf reprezentálja M -et. A fennmaradó esetekben viszont (amikor tehát 5p = 2q , de p 6= 0, 34 , 4) azt kapjuk, hogy M ben minden 3 elem¶ halmaz összefügg®, de minden 2 elem¶ még független. Vagyis ilyenkor M ∼ = U4,2 , vagyis M nem grakus. (Mindezt persze egy teljes érték¶ megoldáshoz nem kell végiggondolni, elég egy-egy olyan esetet mutatni, amikor M grakus, illetve amikor nem.) akkor és sak akkor nem nulla), ha

az

a, c

és

d

élek által meghatározott háromszögr®l lelógatjuk a

Az 5. feladat megoldása. Az algoritmus mindig azt a részhalmazt választja ki amelyre a lehet®

legkisebb a halmaz költségének és az újonnan lefedett elemek számának hányadosa. Az els® lépésben a per h részhalmazt kell választanunk, mert ennek a legkisebb az egy elemre 3 5 es® aktuális költsége ( ). Ezt követ®en a salmon részhalmaz jön, aktuális költséggel. A következ® 5 6 halmaz a pike kell legyen, ez újabb 2 elemet fed le, 4 költséggel, majd a dab halmaz jön, ennek 5 költsége . Végül a hátramaradt t bet¶t kell lefednünk, ezt a legol sóbban a ten h szóval tehetjük 2 meg. A kapott fedés tehát: {perch, salmon, pike, dab, tench}, költsége 22. A 6. feladat megoldása. Megmutatjuk, hogy a feladatbeli gráfok komponensei be-feny®k. El®ször

azt látjuk be, hogy a gráf irányítatlan értelemben erd®. Irányított kört természetesen nem tartalmazhat, ha pedig irányítatlan kört tartalmazna, akkor annak lenne olyan sú sa, amelynek kifoka a körben kett®, ami ellentmond a feltételnek (ha a kör kifokainak összege a körben

k,

k

sú sból áll, akkor a benne szerepl® élek

ha ezek közt nin s egynél nagyobb, akkor mindegyiknek épp egynek

kell lennie, ekkor viszont irányított körr®l lenne szó). Tekintsük a gráf egy tetsz®leges komponensét. Mivel ez a iklikus, kell hogy legyen benne nyel®, legyen ez

s.

x pontból az s-be vezet® irányítatlan értelemben vett s felé van irányítva, igazolva ezzel, hogy a komponens valóban be-feny®. Az s-sel s felé vannak irányítva, hiszen s nyel®. Ezen éleket elhagyva s szomszédai válnak

Megmutatjuk, hogy bármely

utak minden éle szomszédos élek

nyel®vé, ellenkez® esetben a kifokuk legalább kett® lenne. Az így kapott gráfban tehát minden él, ami

s

szomszédai közül valamelyikhez satlakozik, a szomszédok felé mutat. Az eljárást

folytatva (ez be fog következni, hiszen kapunk.

s

és

x

között létezik út)

x-b®l s-be

x

eléréséig

vezet® irányított utat

Beláttuk tehát, hogy a komponensek be-feny®k. Most minden komponens nyel®jéb®l egy közös új pontba élet húzva be-feny®t kapunk, amire Hu algoritmusát alkalmazva polinom id®ben optimális ütemezést kapunk. Ebb®l az újonnan hozzávett pontot törölve nyilván optimális ütemezést kapunk az eredeti feladatra.

Rendszeroptimalizálás Pótzárthelyi feladatok

2007. de ember 13. a) Írjuk fel az alábbi lineáris programozási feladat duálisát! (A felírás hasonló alakú legyen, mint a primál feladat felírása.) b) Határozzuk meg a (primál) feladat maximumát. 1.

max{10x1 + 14x2 + 18x3}

ha x1 + 2x2 + 3x3 ≤ 1 2x1 + 3x2 + 4x3 ≤ 2 3x1 + 4x2 + 5x3 ≤ 3 4x1 + 5x2 + 6x3 ≤ 4

Az A mátrixra teljesül, hogy a nullvektor az egyetlen olyan, az A soraiból készített lineáris kombiná ióként el®álló sorvektor, amely nem tartalmaz 0-nál kisebb elemet. Bizonyítsuk be, hogy az A oszlopaiból a nullvektor kifejezhet® pozitív együtthatós lineáris kombiná ióval. 2.

Jelölje M az alábbi gráf által meghatározott matroidot. Grakus lesz-e az M ∨ M összegmatroid?

3.

c a

b

f

e d

Lerögzíthetjük-e a p paraméter értékét úgy, hogy utána a q paraméter tetsz®leges értéke mellett az alábbi mátrix által meghatározott matroid sose legyen grakus?

4.



 1 2 3 1 2 p 2 0 5 q 5 0

Tekintsük a Részletösszeg probléma következ® esetét. Legyenek az S halmaz elemei 3, 5, 7, 12, 13, és legyen a részletösszegként meg élzott t érték 26. Hajtsuk végre és dokumentáljuk az el®adáson tanult (1 + ε)-közelít® algoritmust az ε = 2 értékre. 5.

Mutassuk meg, hogy a ládapakolás feladatra adott First Fit eljárás 2-approximá iós algoritmus. 6.




2008. de ember 5. A p paraméter milyen értékeire teljesül, hogy az x1 = x2 = x3 = x4 = 1 választással a) bázismegoldását b) er®s bázismegoldását adtuk meg az alábbi egyenl®tlenségrendszernek?

1.

x1 − x2 + x3 x2 − x3 + x4 x1 + x4 x3 + 2x4

≤ ≤ ≤ ≤

1 1 2 p

Legyen A egy m × n-es mátrix, aminek az els® oszlopa legyen b. Legyen továbbá c az az n hosszú sorvektor, amelynek minden komponense 1. Tegyük fel, hogy a cx

élfüggvény felülr®l korlátos az Ax ≤ b egyenl®tlenségrendszer megoldáshalmazán. Adjuk meg a max{cx : Ax ≤ b} maximum értékét! 2.

Lehet-e a p paramétert úgy megválasztani, hogy az alábbi mátrixszal (a valós test fölött) koordinátázott matroid grakus legyen?

3.

1 1 1 1 1 0 1 2 3 p

Bizonyítsuk be, hogy az alábbi három gráf körmatroidja közül bármelyik kett® összege grakus! 4.

a b c

d

a b c

d

b c d

a

Hajtsuk végre a Steiner-fa probléma alábbi bemenetére a tanult approximá iós algoritmust és döntsük el, hogy optimális megoldást ad-e. A G gráf pontjai a síkon egy szabályos nyol szög sú saiban és a nyol szög középpontjában helyezkednek el, bármely két sú s össze van kötve és a köztük futó él költsége megegyezik a sú sok síkon vett távolságával. A terminálok és a Steiner-pontok felváltva követik egymást a nyol szögön, a középpont Steiner-pont (vagyis négy terminál lesz, a nyol szög minden második sú sa). 5.

Mutassuk meg, hogy a Graham-féle listás ütemezés akkor sem ad feltétlenül optimális megoldást a P ||Cmax feladatra, ha a lista megmunkálási id®k szerint monoton (de nem feltétlenül szigorúan monoton) sökken® sorrend¶. 6.


A zárthelyi feladatok megoldása Az 1. feladat megoldása. Az egyenl®tlenségrendszer mátrixos alakja



1 −1 1  0 1 −1 A=  1 0 0 0 0 1 Látható, hogy

 0 1  , 1  2

Ax ≤ b,

ahol

 1  1   b=  2 . p 

A harmadik sora az els® két sorának összege, viszont az els®, második és negyedik sor r(A) = 3. A megadott x1 = x2 = x3 = x4 = 1 megoldás az A els®, második

lineárisan független. Így

és harmadik sorát biztosan egyenl®séggel teljesíti. Ha a negyediket nem, akkor az egyenl®séggel teljesül® sorok rangja sak 2, hiszen az már kiderült, hogy az els® három sor lineárisan összefügg®. Ezért pontosan akkor kapunk bázismegoldást, ha a negyedik sor is egyenl®séggel teljesül, vagyis ha

p = 3. Er®s bázismegoldást viszont még ebben az esetben sem kapunk, hiszen a megadott megoldás nemnulla komponenseinek (vagyis mindnek) megfelel® oszlopok az lineárisan összefügg®k (hiszen

A négyzetes

A

összes oszlopa. Ezek pedig nyilván

mátrix, így az oszlopok és a sorok lineáris összefügg®sége

egymással ekvivalens). A 2. feladat megoldása. Alkalmazhatjuk a dualitástételt, hiszen az

Ax ≤ b egyenl®tlenségrendszer

x, amelynek az els® komponense 1, az összes többi 0) cx felülr®l korlátos a megoldáshalmazon. Így a keresett maximum értéke min{yb : yA = c, y ≥ 0} (és a duális feladat megoldható és a élfüggvénye alulról korlátos a megoldáshalmazán). Mivel A els® oszlopa ébben b, ezért az yA = c lineáris egyenletrendszer els® egyenlete éppen yb = 1. Vagyis a duális feladat minden y megoldására az yb élfüggvény értéke 1, így a duális program minimuma is 1. Ezért max{cx : Ax ≤ b} = 1 is igaz.

nyilván megoldható (hiszen megoldása az az és a feladat szövege szerint

A 3. feladat megoldása. A mátrix els® 4 oszlopa az

U4,2

uniform matroidot koordinátázza, hiszen

nin s köztük párhuzamos, de síkbeli vektorokról lévén szó - közülük bármelyik három összefügg®. Mivel

U4,2

nem grakus, ezért a megadott mátrix semmilyen

p

értékre nem koordinátázhat grakus

matroidot (hiszen egy elem elhagyásával a matroid grakussága nem romolhatna el). A 4. feladat megoldása. Jelölje a három matroidot sorban

matroid függetlenjeit úgy kapjuk, hogy az

M2

M1 , M2

és

M3 .

Ekkor az

M1 ∨ M2

függetlenjeihez (vagyis körmentes részhalmazaihoz)

a, b és c elemek közül egyet. Így a legföljebb két elem¶ halmazok mind függetlenek {a, b, c} lesz összefügg®. Ezért M1 ∨ M2 annak a gráfnak amelyben az a, b és c élek háromszöget alkotnak és d lelóg err®l a háromszögr®l

hozzávehetünk az

lesznek és a három elem¶ek közül is sak a körmatroidja,

(vagy akár külön komponenst alkot).

M1 ∨ M3

a, b és c elemek közül egyet hozzávenni. Így itt is független lesz minden legföljebb két elem¶ halmaz és a három elem¶ek is a {b, c, d} kivételével. Ezért M1 ∨ M2 annak a gráfnak a körmatroidja, amelyben a b, c és d élek alkotnak háromszöget és a lóg le a háromszögr®l. Végül az M2 ∨ M3 matroid esetében {c, d} független M2 -ben és {a, b} független M3 -ban, így az összegmatroidban az egész alaphalmaz is független lesz, vagyis M2 ∨ M3 az U4,4 szabad matroid. Ez Az

matroidnál az

M3

függetlenjeihez szabad az

nyilván grakus: bármely 4 él¶ fa körmatroidja ez. Az 5. feladat megoldása. Anélkül, hogy az az általánosság rovására menne, feltehetjük, hogy a

középpont és a nyol szög sú sainak távolsága 1. Mivel a bemenet metrikus (hiszen a gráf teljes és a síkon vett távolságra teljesül a háromszög-egyenl®tlenség), az algoritmus a terminálok által feszített részgráf egy minimális feszít®fáját adja. Ezt Kruskal-algoritmussal (vagy bármilyen más, tudottan polinomiális idej¶ minimális költség¶ feszít®fát keres® algoritmussal) kell meghatározni. A kérdéses gráfnak hat éle van, ebb®l négynek a költsége

√

2,

a másik kett®é

2.

A Kruskal-algoritmus az els®

négy élb®l talál meg tetsz®leges hármat, az összköltség tehát

√ 3 2.

Ez nem lesz optimális, mert a

középpontot a négy terminállal összeköt® élek alkotta Steiner-fa költsége

√ 4 < 3 2.

A 6. feladat megoldása. Legyen két gépünk, a megmunkálási id®k pedig legyenek (mondjuk)

3,3,2,2,2. A nem növekv® sorrend¶ listás ütemezés el®ször mindkét gépre 3 költség¶, ennek végeztével mindkét gépre 2 költség¶ munkát tesz, végül az egyik gép elvégzi a hátralév® 2 költség¶ munkát, az összid® így 7 egység, holott ha a két 3-as munkát az egyik, a három 2-es munkát a másik gép végezné, akkor 6 id®egység alatt végezhetnénk.

Rendszeroptimalizálás Pótzárthelyi feladatok

2008. de ember 16. A p paraméter milyen értékeire teljesül, hogy az x = 1, y = 1, z = p választással a) bázismegoldását b) er®s bázismegoldását adtuk meg az alábbi egyenl®tlenségrendszernek?

1.

x+z x+y 2x + y + z y−z x+y+z

≤1 ≤2 ≤3 ≤1 ≤3

Legyen A egy m × n-es mátrix, c pedig egy n hosszú sorvektor. Tegyük fel, hogy az Ax ≤ b lineáris egyenl®tlenségrendszer megoldható és a cx élfüggvény felülr®l korlátos a megoldáshalmazán. Tegyük fel továbbá, hogy ráadásul az Ax = b lineáris egyenletrendszer is megoldható és egy megoldása x0. Bizonyítsuk be, hogy ekkor x0 maximumhelye a max{cx : Ax ≤ b} lineáris programnak! 2.

Az alábbi mátrix koordinátázza (a valós test fölött) az Ma,b matroidot. Bizonyítsuk be, hogy a értéke megválasztható úgy, hogy azt lerögzítve b minden értékére Ma,b grakus lesz!   3.

1 1 1 1  0 1 2 a  0 0 0 b

Jelölje A és B az alábbi két gráf körmatroidját! Az A∨A, A∨B és B ∨B matroidok közül melyik (melyek) grakus(-ak)? 4.

a b c

d

a b c d

Hajtsuk végre a Steiner-fa probléma alábbi bemenetére a tanult approximá iós algoritmust és döntsük el, hogy optimális megoldást ad-e. G a K3,3 teljes páros gráf, az egyik osztályban az 1, 2, 3, a másikban a 4, 5, 6 pontok vannak. Az (x, y) él költsége (ha be van húzva) x+y−4. A terminálok az 1, 2, 6 pontok. 5.

Létezik-e polinomiális algoritmus a P 2||Cmax feladat azon spe iális eseteire, amikor a megmunkálási id®k legfeljebb kétfélék lehetnek?

6.




2009. április 29. 1. a) Írjuk fel az alábbi lineáris programozási feladat duálisát! (A felírás hasonló

alakú legyen, mint a primál feladat felírása, vagyis

ne

mátrixos alakot használjunk.)

b) Tegyük fel, hogy tudjuk, hogy a duális feladat rendszere megoldható (ezt tehát igazolni nem kell). Döntsük el, hogy korlátos-e (a megfelel® irányból) a duális feladat élfüggvénye a megoldáshalmazán.

max{2x + 3y + 5z} ha

3x + 5y + 7z ≤ 11 7x + 11y + 13z ≥ −17 13x + 17y + 19z ≤ 23 19x + 23y + 29z ≥ −31 G(A, B; E) teljes páros gráf két színosztálya legyen A = {a1 , a2, . . . , an } és B = {b1, b2, . . . , bn}. Az ai -t a bj -vel összeköt® él súlya legyen i2 + j 3 minden 1 ≤ i, j ≤ n esetén. Adjunk meg G-ben egy maximális összsúlyú teljes párosítást 2. A

(és mutassuk meg róla, hogy maximális). 3. Az

M(a, b)

matroidot az alábbi mátrix reprezentálja a valós test felett:



 1 0 1 1  0 1 1 a  0 0 0 b Meg lehet-e

b értékét úgy választani, hogy M(a, b) az a értékét®l függetlenül mindig

grakus legyen? Hát úgy, hogy sose legyen grakus? 4. A második gráf éleir®l véletlenül lemaradtak a bet¶k, nem tudjuk, hogy az

a, b,

c, d élek közül melyik a hurokél. Eldönthet®-e azért, hogy a két gráf körmatroidjának az összege grakus-e?

a c

d b

5. Tekintsük a Metrikus Utazóügynök probléma azon eseteit, ahol bármely két sú s

között létezik olyan út, amely sak 1 súlyú éleket használ. Igaz-e, hogy ezekben az esetekben polinom id®ben találhatunk olyan Hamilton-kört, melynek költsége legfeljebb

2n

(ahol

n

a sú sok száma)?

6. Mutassuk meg, hogy a Ládapakolás problémára adott First Fit De reasing al-

goritmus approximá iós faktora nem jobb, mint

3 2.


A zárthelyi feladatok megoldása Az 1. feladat megoldása.

a) A feladat max{cx : Ax ≤ b} alakú, ahol 

3 5  −7 −11 A=  13 17 −19 −23

  7  −13  , b =   19  −29

 11 17  , c = 23  31

2

3 5

.

Ezért a feladat duálisa min{yb : yA = c, y ≥ 0}. Ezt részletesebben kiírva és az y = (y1 , y2 , y3 , y4) jelölést alkalmazva: min{11y1 + 17y2 + 23y3 + 31y4 }

ha

3y1 − 7y2 + 13y3 − 19y4 = 2 5y1 − 11y2 + 17y3 − 23y4 = 3 7y1 − 13y2 + 19y3 − 29y4 = 5 y1 , y2 , y3 , y4 ≥ 0

b) Mivel y1 , y2 , y3, y4 ≥ 0, ezért 11y1 + 17y2 + 23y3 + 31y4 ≥ 0 nyilván fennáll, így a duális

élfüggvénye alulról korlátos a megoldáshalmazán. Megjegyzés. Általában ha a duális megoldható, akkor a duális élfüggvény alulról korlátosságának szükséges és elégséges feltétele a primál feladat megoldhatósága. Ez következik a Rendszeroptimalizálás könyv 1.6. Tételéb®l, valamint abból a tényb®l, hogy a duális feladat duálisa ekvivalens a primállal. A 2. feladat megoldása.

Legyen c(v) =

i2 , ha v ∈ A, v = ai ; j 3 , ha v ∈ B, v = bj .

Ekkor minden e = {a, b} élre w(e) = c(a) + c(b) teljesül (ahol w -vel a feladatban deniált súlyfüggvényt jelöltük). Ebb®l következik, hogy tetsz®leges M teljes párosításra X

w(e) =

e={a,b}∈M

X

e={a,b}∈M

(c(a) + c(b)) =

X

v∈A∪B

c(v) =

n X

(i2 + i3 ).

i=1

Vagyis minden teljes párosítás összsúlya a fenti érték, így tetsz®leges teljes párosítás (például az {a1 , b1 }, . . . , {an , bn } élek) maximális összsúlyú. Jelölje a mátrix oszlopait sorban x, y , z és u. Látható, hogy x, y és z közül semelyik kett® nem párhuzamos, de a három együtt lineárisan összefügg® (hiszen x+y = z ). Tegyük fel el®ször, hogy b 6= 0. Ekkor az {x, y, z} bármely lineárisan független részhalmazához u-t hozzávéve a lineáris függetlenség nyilván megmarad, így ekkor a értékét®l függetlenül az M(a, b) matroidot reprezentálja az a gráf, amit egy négy pontú teljes gráfból két szomszédos él elhagyásával kapunk. Ezért a feladat els® kérdésére a válasz igen: tetsz®leges b 6= 0 választás esetén M(a, b) minden a-ra grakus. Tegyük fel most, hogy b = 0. Ekkor a reprezentáló mátrix rangja nyilván 2, így a négy oszlop között már nem lesz három lineárisan független. Ha a = 0 vagy a = 1, akkor u egyenl® x-szel vagy z -vel, így ebben a két esetben M(a, b) grakus: reprezentálja az a gráf, amit egy háromszög egyik élének megduplázásával kapunk. Ezért a feladat második kérdésére a válasz nemleges, hiszen az a = 0, 1 esetekben M(a, b) minden b-re grakus. Megjegyzés. A fennmaradó b = 0, a 6= 0, a 6= 1 esetekben M(a, b) az U4,2 uniform matroiddal izomorf, így nem grakus. A 3. feladat megoldása.

Világos, hogy a bal oldali gráf körmatroidjának függetlenjei sak {a}, {b} (és ∅). A jobb oldali gráf körmatroidjának nemüres függetlenjei pedig a három párhuzamos élnek megfelel® egyelem¶ halmaz. Így az összegmatroid rangja mindenképp 2. Tegyük fel el®ször, hogy a jobb oldali gráfban a hurokél a. Ekkor az összegmatroidban a {c, d}t kivéve minden kételem¶ halmaz független (mert az összes többi kételem¶ halmaz el®állítható úgy, hogy egyrészt a és b, másrészt pedig b, c és d közül választunk egy-egy elemet). Így ebben az esetben az összegmatroid grakus: reprezentálja az a gráf, amelyet egy háromszög egyik élének megduplázásával kapunk és a két párhuzamos él c és d. Teljesen hasonló a helyzet akkor, ha a hurokél b. Tegyük fel most, hogy a jobb oldali ábrán a hurokél c. Ekkor az összegmatroidban c hurok (mert mindkét matroidban az), viszont az {a, b, d} halmaz minden kételem¶ részhalmaza könnyen láthatóan független. Ezért az összegmatroid megint grakus: reprezentálja az a gráf, amit egy háromszög és egy hurokél alkot (ahol a hurokél c). Mivel a legutolsó eset, amikor d hurokél, az el®bbivel analóg, azt kapjuk, hogy az összegmatroid mindenképp grakus; ez tehát a bet¶k ismerete nélkül is eldönthet®. A 4. feladat megoldása.

A feltétel szerint az összes sú sból és az 1 súlyú élekb®l álló gráf összefügg®, így létezik az eredeti gráfnak supa 1 súlyú élb®l álló feszít®fája. Ennek az éleit megduplázva, majd a kapott gráf (mely összefügg® és minden foka páros) Euler-körét az el®adáson tanultak szerint levágva legfeljebb 2n − 2 súlyú Hamilton-kört kapunk (a levágások a metrikusság miatt nem növelik a költséget). Az 5. feladat megoldása.

Legyen a ládák súlya (mondjuk) 13, az elhelyezend® tárgyak súlyai (mondjuk) 5,5,4,4,4,4. Az optimális megoldáshoz nyilván elég két láda, míg a FFD algoritmus el®ször a két 5 súlyú tárgyat helyezi el, éspedig egy ládába. Ezután ebbe a ládába más már nem fér, így összesen három láda fog kelleni. Mivel meg tudtunk adni olyan esetet, ahol az algoritmus az optimum 32 -szeresét adja, az approximá iós faktor nem lehet jobb, mint 32 . 11 OP T + 4 ládát használ, ez azonban nem Megjegyzés. Ismert, hogy a FFD algoritmus legfeljebb 9 ekvivalens azzal, hogy az approximá iós faktora nem rosszabb, mint 119 . A 6. feladat megoldása.

!"$#%& ' (*)+),.-0/21354768(9).:;&<>= 3547?A@B C7D9EFD*CG1*H0H7I7CJIJK7B 1 = IL6NM =5OP= D*/ O E 1*6QI@BRCLD+S0D9TNS04&1*CJIL6U1TRV0WXY@B CJZ = 1+6N[0D+6 O K0C]\^D*CLD+?_ C]B P*` B Kba7/cIJKdTFDeM = IJ/21+Cf@BRCLD+S0D9T$@BRCJZ = 1*6UD.ahg+D P+` IJ6jibkA/219T = Iml O 6nD+CLD+? O To[0D+6pERK01+Cq3540K7?-sr [&D

min{2x + 3y + 5z} 3x + 5y + 7z = 11 7x + 11y + 13z = 17 x ≥ 0, y ≥ 0, z ≥ 0

ut ; X G(A, B; E) TpB Cq3vBR6cM&1 =5O 6 Pd= 19@A?+wxT6pERZLK O 6pExTy1*C ` DzC]B P+` BRK A = {a1, a2, . . . , a10} wR6 B = {b1, b2, . . . , b10} -"X8E ai { T|D bj { gBRC~}d6Q6pEBR?*}+TQwRCN6Q_0C ` DC]B P+` BRK |i − j| /cIJK0S7BRK BR6pBxTQwRKu-.XoS3540K0?/B P G{ HBRKB P*` /2Dl7IL/21*CLIJ6}6Q6pE 6Q_7C ` _TQBRCq3vBR6nM01 =5O 6QZmTy1+65T 1 ≤ i, j ≤ 10 WwR6/4.TUD+6Q6Q47?/B P= \CGD.a0[ OP*` /2Dl7IL/21*CLIJ6r; X8E M (a, b) /2D9T =5O IJS O ToD*EAD+CL1*H0H0I"/21T = Isl = B M = BEB KdTU1+Cq3pDDeg+D*C]\d6TQBR65T$@B C]BxTpTR 

1  2 −1

2 4 −2

3 6 1

4 8 0

 a 0  b

+P ` B P*` Mw CJS&1*KY/4hTyD*6Q6Q40?/B P a[ O+P+` a wR6 b w = TQwR?*B_ P+` JI 62/B P g+1+CLD*6pETQ[&DTQ\&aN[ O P*` { Pd= D9&?406oC]B P+` BRKua7wR6_ P*` IJ6a0[ O+P*` K7BR/V M (a, b) ; X/21*6 O S0IJ? P= 1@uwRCJBRI = ChmgwRCJBxTUC]BRK0Cs$C]B /2D = D*S.TyD*?DAHBxTU7?- JC S7}KdTU[7BxTQ { BD9Ew = TRad[ O P*` D?*wxT P= 1@N?*} = /2DT =5O ILS3p1+K0D+?D9E}6Q6pERB P B P= D?476 { B a c

b

d

u ; X dTQBRILK.B = { @DM =5O H7CJwR/2DeB P*` BR6pBxTQwxToK.BxgdBEER0?2?+BRCJCJBR/BR6QK7BR?a[&DcDeTQB = /cILK01+C O ? T [&D*C { /2D*E DM O KdT O 6UD+K [&1 =5O / ¡R6Q_7¡6Q_wR6oC]B P D*CL1+H7HB P*` wRCJBxT@BR6pE ZmTRa7BR/BRCLC]BxTpTn/cILK7S7BRKw CJ6Q_0C `£¢ ¤ wxTQBE IJ? B¥M O CJIJK O /2IL1*CLIJ6"D*C P+Od= I]TU/e406¦D¨§BRCJCJBR/BR6 TpB IJK7B = @DoM =vO H7CJwR/21 = D|WD*[ O CDFHB /BRK7BxT TQB = /wR6pE{ BTpB 6pBRK©Dc TQBRIJK7B = { @DªM =5O H0C]wR/D|B P+` ?+BRCJCJBR/BR6BR6p{ BTpB9r5 «;¬P D9E { Baf[ OP*` D9E$TyD9E\d P+` K.}d? M =5O H0C]wR/2D©D*?? O= IJ6A®8¯ { K7BR[7wEau[&DDHBR/B K.BxTUI P= 1@ wRCL6Q_7C Ò E1*6U1*[ O E P D = D+KdTU1+CmTyD*KC]B P @BRCq3vBRH0H[01 =5O / ?7CJ}KH}E6Q_7C ` ToC]B [.BxTo[0D+6pERK01+CJK0I° ± ²]³v´sµ·¶µ¸º¹¼»½³5¾·¹¼´¿¶9ÀÁºÀ·Â¹·ÃÁ³5¾¼Äv¶³5ÁÃ5»·Å·ÃÆ³5½ÇÂ9µ·Á>ÃvÆ9À·´ÈÂ9µ¸ºÉÊ ± Ë>³5Æ¶³5´È»·³5ÃvÄ5ÁË>³À·´¿´ÈÉ¥½ÍÌÆ»yµ·Î¿¶ÏÐ¼ÑÍÒ+³5ËÓ·Ê Ô ³v½ÕÁ>Ã5Ö»RÁÄ5¾¼³vÁ½nÎÈÆ¶³vÆe²]³5´¿µ·¶9µ¸>¹·¸»Ö´¿Å·Æ´sµÒËºµ¨×¿Ë>ÆÎGØ ¶³n»·ÄvË]ÙÖ»*Ø0Â¹¼¾·ÚeµjÛ+³pµ·¶¹·¸>¸¥¶¹¼´È¾¼¹¼Ãpµy¸ÍÜvÝxÞß5àá â ã]ä Ü5Ý¼ßUå ä ßQæ ãJçè9é+çRêAëì ÞRÜ5Ý ìUç*íRä Ýoî·â ç Üyïðâ ç Ü·ñ änë â ä Üyï ò9â ç Ü·ñ9ó ãLã]ç ßpà çNä Ý¥ô âºõ+Üyïö âº÷+Üø çRãJäù.ä ßpú7á ì ÷*û ìUä ü

!"$#%& ' (*)),+.-0/21435769857:<; =.>?A@ BDC :EGF2HJI5 K @MLN@ KPOM8082QKRQS/.5 O,:TQRUDV0:W1X: @ 6Y1*Z t?2 5qX,r57/ A m×nZ%57U6uO ^ :TQ|{zs b ∈ Rm 1fU L Z L OMU[Q\I5 K @M]&@^_] F0O,KRQRUÒ ^bac@ t 3 @ KedfUV @ : @ 6Yg ^ 57: Ke1Vf3f57H ^ 1:-F ^@ U[U[F0HJ65qX&s2n21,X,r @ML@ KSO,8280Q 6YQR/ ] 57/hg : ^ g7H,g7:G5 Bjikal I5 KRmR:[O,Uon @ UT1/0Ked @ K @ Hp :W5 / ] U L 57:G57HH ,L 0KV1/ ^ 1fU @ / @*L 5qX,r.QRH657X*Z Ke5qX,r57/tsq6uQR/ ^v@ V0:TQR6uO,K*I57K @M]&@^ I57KRmS:[OMU @ sw3 @ XMr.QSU 1K ] n @^ d0 xzy 6uO ^ :TQ|{.1fU @ K @ H,1 ^ n @ U L /&OMK}EGF2/0H- B Wj Ax = b s x > 0 8 Bt~\ / ^ U[0HD57Ksn.1XMr @ t V @ : @ 6g ^ 57:z6YQRKer57/ % yA ≥ 0 s yb ≤ 0 s y(A|b) 6= 0 g7: ^ g7HM57QS:G5Ke5 U L@a V2:TQR6OMK B I5 K @M]&@^ g7KI2X,X,3gwZ a!lDLq^ HM5 KRK ^ 5 n0O ^ 65qXf6NF ^@^ /0Qcsn21,X,r @ML Wj Z /fr5I57KS2KS:WfKH,1:TKSO ^ 1U @ 6Y5qX,1fK ] OMU[n @ KR6 @*L O,/z57U[857KSQ x g7U @ q Z%57U[857KSQ y 357H ^ 1f:W1fHhH ,L 0K max{x1 − x2 − x3 − x4 + t · x5} V1/ ^ 1U @ / @*L 5qX,r.QRHKeg ^ 5 L QSH- x > 0 @*L^ EW5Z n@ Ke57/ ^ Qcsn21,XMr @*L x 6YQR/ ] 57/HM16uV1/257/0UT5NV1MZ x1 − 2x2 ≤ 1 L Q ^ m3- (A|b) @ML^@ 6uO ^ :TQ|{.1 ^ EW57K KRQs @ 6YQ ^@*L x2 − 2x3 ≤ 2 Z8dK2/fr57:T0/2Hp.X,rfsMn21,X,r bZ ^ n21 LqL Oq3f57U[U L 0H A x3 − 2x4 ≤ 3 pE$1U L KR1V0HMg7/ ^ - B x − 2x ≤ 4 v? 11f4: ] QS/0O ^ 5O LqL @@ML@ KSO,8280Qv6uO ^ :GQ{ a@ 3 @ KedfU ^ 57U ^ I K M^T^¡B¢@*L Mx,y 6 @*^ :W1fQ ] 1 ^ - lDL x s y g7: ^ gZ HM57H ^ fKI2X,X57/6YQSHM1f:£Ke57U Lo@*L M 6 @^ :G1Q ] X: @¤ HF0Uj¥ x,y



1  0   3 0

0 2 0 6

 2 0 0 −1   x 0  0 y

¦ §? l 8 @ K1K ]&@ KSQ
A

s @ EW1808ª1K ]0@ KRQS/«KSO ^ n @^ dg

4 1

2

3

1 3

5

B

4

5 2

t ?® 57HQS/ ^ U[2H @ML F ^`@ML d2XMr./ HV2:G1f82KRg76 @¯@ML 1/°U[V5 QSO,KRQRUz57UT5 ^ 5 Q ^ s @ 6uQRHM1f: @ Xf:TO*I2V1f/ ^ E @ Qf5qXMrU L @ Z 80O,Krf1U nZU Lq X U[p U @ QR/n.57Ker5 L HM5 ] /.5 H±57Kcs @*L g7Ke57HuU[p2Ker @ QzV5 ] QeX @ 3g7XV1f/ ^ 1fHY57F0HKRQ ] 5 U L Q ^ O731KZ UÒ*X Oq3 @ K @*L 1f/.1fU @ H- ²cX @ML Z5fs*n.1XMr5 L 57/U[V5 QSO,KRQSU5 UT5 ^ 57H:G5 @*L 57KR @,] O,UT1/ ^`@ /F2K ^ 3 Z @ V0V2:G1 {2QR6uO QedfU 2 @ KRX,1:TQ ^ 69F0U£1V ^ QR6uO,KRQRU¯65qX,1fK ] OMU ^¢@,] ¥ ³v? F ^@ U[U[F2H65qX&sn.1XMrKeg ^ 5 L QRH (2 − 1 )Z @ V2V0:G1 {2QR6uO QedfU @ KRX,1:TQ ^ 69F0U @ P m|prec|Cmax I5 K|Z @M]&@^ : @ sń @ QRU[6Y57: ^ sn21,X,r @ V0:G5 5 ] 57/ Q @ mX:[OI\V1/ ^ 1U @ /5qX,rµg KR8fK$OMKRK- a _57KSKe LqL 0H @ /0/ @ H @*L 57Ke @M] OMUT1f/¶82Q L 1/fr.m ^ O,U·/2g7KRH0K°H Lq K ^^ g7/fr./.5 H @ n @ U L /&OMK @^ O ^ s\6YQSU L 57:TQR/ ^·@ KRQSU ^ OMU· ^ 5765 L g7U Z @ V0V0:W1 {2QS6uO QRdU @ KeX,1f:TQ ^ 6NF0U @ P m|prec|Cmax I5 K @M]&@^ : @ - B (2 − 1 ) m

¸º¹e»G¼¾½¡¿*½jÀÁwÂ\Ã¯»GÄ¡Áw¼¾¿*ÅjÆÅ¡ÇÁ¡ÈÆ»WÄwÉG¿»WÆÈWÂ¡ÊwÈÌË»GÃÍÇ*½jÆÈGËÅ¡¼¾Ç*½ÀÎÏ¸ºÐc»GË¿4»G¼¾Âj»GÈWÉGÆÐc»ÑÅ¡¼Ò¼¾Î£ÃÑÓ4ËÂ½¡Ô¾¿Õ$Ö¡×$Ø,»GÐcÙ¡Ï Ú »GÃ«ÆÈWÛÂqÆÉGÄ¡»GÆ´Ã¯Ô¾Ë¿»WË¹e»W¼|½¡¿½jÀÁ¡ÀvÂqÛ¼ÒÊwË¼¾½¡ØÐ½$ÜÒÐËÔSÝ¿»ÌÂ¡ÉGÐÞcÛÂMÝÇ4ÁwÄ¡ß½¢à,»T½j¿Á¡ÀÀ¿Áw¼ÒÄwÁwÈG½jÀâáGãäåTæçèRé*áWãwå`ê.é å[ë èeìqíMî,ì7ï_ðNñ`ä7áGãñ`ìMò0éã9ó¡ôì7áõö ôì7á¡÷0é±ð ôé*áõ øôì7á¡÷ùRèSèeìåTæ,ìDéãoú ôûá`õ*ü ôý,á¯þÿì7èeé é4å .çñ`ý fñé

-

!"¯#%&4' 7

ãNó&þÿì7èRé .é4å9ìqíMý,è ç*áGé ½ z¸¹e»G¼¾½¡¿*½jÀ ½¡¼¾½¡Â Ý*½¡ÇÁ¡¼ max{cx : Ax ≤ b}

  1 −2 0 0 0   0 1 −2 0 0  , b =  A=   0 0 1 −2 0  0 0 0 1 −2 

ÈGÉWÐcÀt½A¹e»W¼|½¡¿*½À¿4Ó*Å¡¼¾ÔÒÆ½ ½¡¼ÒÂ½¡¼¾Ã¢½¡È j½

min{yb : yA = c, y ≥ 0}

 1 2  , c = 3  4

1 −1

−1

Ï È ÀzÐcÉGÆcÈG¼¾» À»WÆ»Gà4à»WËDÂ7ÔÒÜ¾Ð ¡½´ÉWÆz½¡È

−1

t

.

y = (y1 , y2 , y3 , y4 )

Þc»G¼ÒÊw¼¾ÉWÆcÀ

Ç*½

min{y1 + 2y2 + 3y3 + 4y4 } y1 = 1 y2 − 2y1 = −1 y3 − 2y2 = −1 y4 − 2y3 = −1 −2y4 = t y1 , y2 , y3 , y4 ≥ 0

à Ú ß7Ô¾¼jÅ¡Ëj½¡¼ÒÎÝDÇÁwÄ¡ß¨½ ØÐcÔ¾Ã¢Å¡¼o¹e»G¼¾½¡¿*½jÀ »GÄ¡ß¡»GË¼ÒÕ¡À¼Ò»GËÆcÉGÄwÐc»GË¿4ÆÈG»WÐ»Ã¯»GÄwÁw¼Ò¿Ç*½jÀÎeØÉW¼¾¿*Å¡Ó4¼ Ý 0 ¯ Ã G » w Ä ¡ Á ¾ ¼ * ¿ ¡ Å Ï!Ä¡ß½¡ÈÌÔ¾ÆÃ¯»GÐÀvÀÉWÀ»G¼v»GË¿ÆcÈG»WÐÁwØ4ÀÔ¾Ã¢½¡¼¾ÔÒÈTÅ¡¼¾Å¡Æ"Â¡Ê¡Ëqß ,Ý¡Ï4Ï"ÉWÀ»G¼vÆcÈG»GÐcÔ¾ËÀAx½¯Ø= Æ Ð Ò Ô \ Ã ¡ Å ¼ i¹e»W= ¼|½¡¿*1,½À2,ÙW3,ÉG¼ ¹e4,ÛÄw5Ä ¡ÉGËßw»$½¡ÂqÂjÁwÐÉWÆÙGÆ½¡Â½¡ÂqÂ¡ÁwÐâ¹e»G¼ÒÛ¼¾ÐcÕw¼Â¡ÁwÐc¼|ÅjÀÁwÆâ½\Ã¯»GÄwÁw¼Ò¿*Å¡ÆcÇ*½¡¼¾Ã¢½¡ÈGÅ¡Ë Ý4Ç½\½¢¿4Ó*Å¡¼¾ÔÒÆv»GÄ¡ß¡»GË¼ÒÕ¡À¼Ò»GË"! ÆcÉGÄwÐc»GË¿ÆcÈG»WÐ»kÃ¯»GÄ¡Áw¼¾¿Ç½jÀÎÏ ¸ ¿Ó*Åj¼¾Ô¾Æ¢¹e»G¼¾ÜÒÐÅ¡Æ½¡Â¡Á¡Ð\Â½¡Ø,Á¡ÀÀD»W¼¾ÆcÕuË4ÉGÄ¡ß»GÄ¡ß¡»GË¼Ò»WÀà,Õw¼´½j¿Î ¿4Ô¾ÂMÝzÇÁ¡Ä¡ß y = y = y = y = 1 #Ï !Ä¡ß½¡È ¹e»W¼ÒÀÉWÀ»W¼¾»WÂJ½¡È»GÄjßw»WÀ¼¾»WË ÆcÈGÎwà*½[Þc$Ê ¡Õ¿ÓÅ¡¼¾ÔÒÆDÃ¢»WÄwÁw¼¾¿Å¡ÆÐ½½¡Ó4ÀÁ¡Ã\½jÀÔ¾ÂqÓÆ½¡ËJÀ»W¼ Þc»GÆcÛ¼¾Ë4»GÂMÏ ÈG»GÂ y ,y ,y ,y ≥ 0 ÆcÈG»GÐcÔ¾ËÀ½¿4Ó*Å¡¼¾ÔÒÆ2Ðc»GË¿4ÆÈG»WÐÉWË»GÂ£Ã¯»GÄwÁ¡¼¾¿Ç*½ÀÎwÆÅ¡Ä½â½¡ÈzÓ4ÀÁw¼¾ÆcÎÝ −2y = t »GÄ¡ß¡»GË¼Ò»WÀcÀÕw¼q¹eÛÄw%Ä ¼|ÅÀÆÈWÔ¾ÂMÝÇÁwÄ¡ßØ,ÁwËÀÁwÆ½¡Ë ½ t = −2 ÉWÐcÀÉWÂqÐ»Ã¢»WÄwÁw¼¾¿4Ç*½jÀÎ4Ï 2»WÇ*ÅjÀ½£ØÐÔÒÃ\Åj¼fÙGÉW¼Ò¹eÛÄ¡Ä wÉWËqß¡»k½jÂ7ÂjÁwÐvÉGÆâÙGÆ½¡ÂD½¡ÂqÂ¡Á¡Ðâ¹e»W¼¾Û¼ÒÐÕw¼,Â¡ÁwÐc¼|ÅjÀÁwÆGÝ4Ç*½ Ï t = −2 å 9ìqíMý,è ç*áGé ¼¾ÕwÆcÈGÊwÐDÃ¯»GÄ¡ÃÑÓ4À%½ÀRÞcÓÂMÝzÇ4ÁwÄ¡( ß '*),+ÉW-Æ '/.0+»WÄ¡ß7ÆÈW»GÐÐc»NË4»GÃ ¼Ò»GÇ» ÀDÃ¢»WÄwÁw¼Ò¿Ç*½jÀÎÏ ö £þÿì7èeé é4& .»GÄ¡ß7ÛÂ_¹e»W¼PÝ"ÇÁwÄjßÃ¢ÉWÄwÔ¾Æ<ÉGÆ¼¾»WÄ¡ßw»WË ÝvÔ¾¼Ò¼¾» 1À w» »WÄ¡ß !!»WÄ¡ßÃ¢»WÄwÁw¼Ò¿*Å¡ÆG3Ï 2 Å¡ÐÎÞc»W¼¾»WÈGÈGÛ4Â_Â¡ÉWÀc¹eÉG¼Ò»GÂ¡ÉWØØ,»GËb½¡È ÆcÈGÁwÐcÈT½jÀÁ¡4À 0 ≤ (yA)x = y(Ax) = ybx ≤ 0 5Ï 76ÿyÀÀ 0 ≤ (yA)x!ÿÇ»GÈ§¹e»W¼¾Ç*½jÆÈGËÅ¡¼ÒÀÓÂMÝ&ÇÁwÄ¡ß yA ≥ 0 ÉGÆ x yAx 8¡½j¼|½¡Ã¯Ô¾ËÀ½ÌÃ¢ÅjÀÐ:Ô 9 ÆcÈGÁwÐcÈTÅ¡Æ¿ » ;ËÜ¾ÙWÔ¾ÎÞÅj<À Ý !!ÇÁwÈvØ,»G¿ÔÒÄÑ½¡È ÀTÝqÇÁwÄjß ÉWÆ yb ≤ 0 =Ï ?>ÅjÀÇ>½jÀÎ0Ý y(Ax) = yb ≤ 0 Ax = b ÇÁ¡Ä¡ß°»WÈ¯ÙWÆ½¡Â°½¡ÂqÂ¡Áw@Ð j½¡¼¾Î¡ÆÓ¼ÒÇ*½jÀË½\Ã¢»WÄÝ Ç*½ ÉGÆ Ô¾Æ¹e»WËË*Å¡¼Ò¼¾Ë*½4Ï È$½¡ÈGÁwËqà*½jË9½¡È ¹e»W¼ÒÀÉ À»W¼Ã¯Ô|½ÀÀA¼¾»WÇ»WÀ»WÀ¼¾»GAË .Ç½ yb = 0 Ý2½jÂ7ÂjÁwÐybÆÈG=Û4Â7Æc0ÉGÄwÂjÉG(yA)x ØØ½¡È =yA0 ÆcÁwBÐ ¡»GÂÀÁ¡ÐkÂ¡Á7ÁwÐc¿Ô¾Ë*ÅÀ%Å¡ÔÂjÊwÈGÊ¡ÀcÀky(A|b) Âj»G¼Ò¼¼Ò»GÄ¡6=ß¡»GË0 Ë»WÃ¢ËqÓ¼Ò¼|C½ R½¡ÈT½¡ÈAØ,ÁwÈGÔ À:Ü %ÆÈTÅjÃÝ*½jÃ¢ÔÒàÕw¼ x > 0 Ã¯Ô|½ÀÀ (yA)x > 0 ÂjDÊ w»WÀÂ¡»WÈGÔ¾ÂMÏ 2»WÄ¡ß7ÛÂo¹e»G¼Ã¯ÁwÆcÀGÝÇÁwÄ¡E ß '/.0+\Ë»WÃ Ã¯»GÄ¡Áw¼¾¿Ç½jÀ%Î FÙGÉW¼¾ÓËÂoà,»G¼¾ÅjÀË4ÔPÝ ÇÁ¡Ä¡ß½¡ÂqÂ¡ÁwGÐ '*),+\Ô¾Äw»WË IÏ H-½ '/.0+4!ÿÀ´¹e»W¼ÀÓ"¿ ! Ë*ÅjËÂoÜ¾ÐcËÔ J!Ç*½jÄ¡ßwÁwÃ¢Å¡ËßwÁ¡ Æ K$»WÄ¡ßw»WË¼¾Õ¡À¼¾»WËÆÉWÄwÐ»WË¿ÆÈW»GÐk½¡¼|½¡Âqà*½jË Ý½¡ÂqÂ¡ÁwÐÌ½¡¼ÒÂj½j¼¾Ã¢½¡ÈGÇ*½ÀË*Å¡Ë4ÂM½ LM½¡ÐÂ½¡*Æ !!¼¾»WÃ¢Ã¢Åj0À F¿» ½¡È ¹e»W¼ÒÀÉWÀ»W¼v»GÈWÀ¢¼|ÅÀÆÈWÎw¼|½jÄ¼Ò»GÇ» À» À¼¾»WËËÉ<À»WÆÈGÔSÏ¸ÈGÁ¡Ë7à½¡Ë¼¾ÅjÀÆcÈGÔ¾ÂMÝÇÁ¡Ä¡ßYÇ*½9N ½ '/.0+Ð»GË4¿ÆÈW»GÐË4»GÂ Ã¯»GÄwy(A|b) Á¡¼¾¿*Å¡Æ½4Ý6=½¡Âq0ÂjÁwÐ α · y ÔÒÆ´Ã¢»WÄwÁw¼Ò¿*Å¡ÆÀ» ÀÆcÈGÕw¼Ò»GÄw»WÆ α > 0!ÿÐ½4OÏ !Äjß½¡È y(A|b) 6= 0 ¹e»W¼ÒÀÉ À»W¼ÒÀÅjÀc¹eÁwÄ½¡¼ÒÃ\½¡ÈWÇ*½jÀeÞcÓÂ y Ý yb ≤ 0 Ç»G¼ ßw» ÀÀÜ¾ÐcÇ*½jÀeÞcÓÂMÝ¡ÇÁwÄjß y(−A|b) ≤ 0 F y(A|b) 6= 0 Ø»W¿Ô¾Ä´Ëß7Ô¾:¼ jÅ¡Ë£»GÂ 7Ô j½¡¼Ò»GËÆ y(−A|b) 6= 0!/j½¡¼PÏ yA ≥ 0 ÆÁ¡BÐ w»WÂÀÁwÐÃ¢ÔÒË¿»GËÂ¡Á¡Ã¢Ø,ÁwË»WËÆ»Ë»GÃ¯Ø,ÁwÈGÔ ÀÜ \ÉG5Æ ¡½jËÂjÊwÈWÀÛÂ<Ë»GÄ½ÀÜ §Ô¾ÆGÏ !Ä¡ß½£¹e»GËÀÔ

ÈG»WÂ<ÆÈG»WÐÔÒËqÀ½¡È !!ÐM ½ wÁwË*½ÀÂ¡y(−A|b) ¡ Á G È Î £Ã¢»WÄ ;*Ä¡ß¡»G¼ÒÉGÆ$Ã¢Ô¾½jÀÀÌ¹e»G¼ À»GÇ4»WÀRÞcÛ4Â,ÝÇÁ¡Ä¡ß½¡È ÆÁw Ð w»WÂqÀÁwÐ¯Â¡Á7ÁwÐ¿ÔÒË*ÅjÀÅ¡Ô¾Ë*½jÂNÊwÆcÆÈW»GÄw» α · y y(−A|b) ¼Ò»GÄ¡¹eÊw¼ Þc»Gàà −1 Ï P ÆÆÈW»W¹eÁwÄ¡¼|½¡:¼ ¡½½¹e»WËÀÔ¾»WÂ¡» 4À Þc»G¼¾Ê¡¼ Þc» ½ JÿÙGÆÓ4Ø*½¡»GÄj ß KÁwÆcÈG¼ÒÁwØ w»GÂÀÁwÐcÀDÉWÆ\¼Ò»GÄ¡ß¡»GË u = (−A|b) · 1 Rj½¡Ä¡ß7Ô¾Æ¢½ Q 1 ÁwÆcÈG¼¾Á¡Ø*½¡Ô¾Ë½¡Â¢Ê¡ÆÆÈW»GÄw4» Ï HQ½ '/.0+Ë»WÃ Ã¯»GÄwÁw¼Ò¿Ç*½jÀÎÝ½jÂ7ÂjÁwÐvË»GÃ Ã¢»WÄwÁw¼¾¿4Ç*½jÀÎÑ½¡È y(−A|b) ≤ 0 Ý yu ≤ −1 (−A|b) Ðc»GË¿ÆcÈG»WÐDÆ»GÃ RÇ4Ô¾ÆÈW»GË yu = y((−A|b)1) = (y(−A|b))1 ÉWØØ½¡È y(−A|b) Â¡Á7ÁwÐ¿ÔÒË*ÅjÀÅ¡Ô¾Ë*½jÂ±ÊwÆÆcÈG»WÄwD» Ï ÐÐ» Ø,»G¿ÔÒSÄ ÀÐ½¡ËÆÈWØÁ¡Ë*Å¡¼|ÅjÆÓ4À%Å¡TË Ã¢Å¡Ð½¡¼ÒÂ½¡¼¾Ã¢½¡ÈGÇ½jÀRÞcÓÂU½ LM½¡ÐÂ½¡*Æ !!¼¾»WÃ¢Ã¢½ÆcÈGÁwÂÅ¡ÆcÁwÆz½j¼|½¡ÂGÞÅjVÀ 7â»WË¿ÆÈW»GÐcÁwØ4ÀÔÒÃ\½j¼¾Ô¾ÈGÅ¡¼|ÅjÆ ÂjÊwËWß ,?Ý wYÏ X4OÏ "É À»G¼ Ï ¸ÈWÀAÂ½¡Ø7ÞcÓ4Â,ÝÇ4ÁwÄ¡ß°¼ÒÉWÀ»GÈGÔÒÂ°½¡È x ∈ R Ý x ≥ 0 w»WÂqÀÁwÐAÉGÆA½ λ, µ ≥ 0 ÆÂ½¡¼|ÅjÐÁwMÂ Ä¡ß¡Ý ÇÁwÄ¡ß ÉGÆ (−µ) < 0 ZÏ R6ÿÀÀ[½ L,½jÐÂ½¡ Æ !ÿ¼¾»WÃ¢Ã¢½$Å¡¼ÒÀ½¡¼2Äw½¡Ð½¡ËÀÅ¡¼ÒÀ (n + 2)!!¿ÔÒÃ¢»WËÈGÔÒÎwÆÁ¡ÆÈG¼ÒÁwØ w»WÂqÀÁwÐ (−A)x + λb + µu = 0 Ó4ÀÁw¼¾ÆcÎkÂjÉWUÀ b!ÿË»GÂMÝ Ô¾¼¾¼Ò»WBÀ w» u!!Ë*½¡Â£Ã¯»GÄj¹e»G¼¾»W¼¾ Õ &ÂjÁ ÁwÐc¿Ô¾ËÅjÀ%Å`ÞÅÀÞc»W¼¾Êw¼ ÀÛÂ λ!\¡½j¼PÝÔ¾¼Ò¼¾» 1À w» µ!\w»W¼PÝ7½¡È»WÈG»WÂ\»G¼ÒÇ*½¡Ä¡ßwÅ¡Æ4Å j½¡¼ Â½¡Ø,Á¡ÀÀvÁ¡ÆÈG¼ÒÁwØ w»WÂqÀÁwÐcÀØ,»G¿ÔÒÄ x!!ÆÈW»G¼S=Ï i

1

1

2

3

4

4

n

2

3

4

6ÿÀÀ Ï ÈWÀ2½v¹e»WËÀÔ¾à,»Ç»G¼ ßw» ÀÀ»WÆÜ À1w»ÉGÆ2ÅjÀÐ»GË4¿»GÈ,w» A(x + µ1) = (λ + µ)b Ï = (−A)·(µ1)+µb :Ô w»W¼ µu = µ(−A|b)1 Ý G É Æ eÓ4ÀÎ¡ààÔ Ã¯Ô|½ÀÀ Ý»WÈGÉWÐcÀ λ + µ > 0 ÉWÆ x + µ1 > 0 Ï àà,Õw¼ 7Ô¾ÆcÈGÁwËÀ x≥0 λ≥0 µ>0 (−µ) < 0 j½¡¼ÒÎwà*½¡Ë<Â¡ÊD¡»WÀÂj»GÈWÔ¾ÂMÝÇ4ÁwÄ¡ß '*),+Ã¢»WÄwÁw¼Ò¿Ç*½jÀÎ%4½jÈ 1 w»WÂqÀÁwÐâÃ¢»WÄwÁw¼¾¿Å¡Æ½4Ï (x + µ1) ¸ ¹e»G¼¾½¡¿*½jÀ»GÄjß\Ã¢Å¡ÆÔÒÂ£¼¾»WÇ»WÀÆÉGÄ¡»GÆtÃ¯»GλÄwÁ¡+¼¾¿*µÅ¡ÆÅ¡Ë*½¡ÂÑ½¡¼|½¡Ø4ÄwÁwË¿Á¡¼|½jÀ½½ÌÂ¡ÊDw» ÀÂ¡»WÈGÕÏT.»GÂqÔÒËqÀÆÛÂ\½ÌÂjÊ$¡»WÀ ! Âj»GÈGÕ$¼ÒÔ¾Ë»GÅ¡ÐÔÒÆØ4ÐÁwÄwÐ½¡Ã¯Á¡4À Ax = b Ý x ≥ µ1 Ý max : µ OÏ È»GÄ¡ß n + 1 ¡Åj¼ÒÀÁ¡ÈGÎwÆ¹e»G¼¾½¡¿*½jÀGÝ x ÂjÁ Á¡Ð¿ÔÒË*ÅjÀ%ÅjÔ¾Ë\Âq:Ü Û4¼ µ ÔÒÆ jÅ¡¼ÒÀÁwÈGÎÏ ÂqÂ¡Á¡Ðv½Ì¹e»G¼¾½¡¿*½jÀà»W¼¾#Ô '*),+AÐ»WË¿ÆÈW»GÐâ½¡ÂqÂ¡Á¡ÐtÉGÆ"ÙWÆ½¡Â\½¡ÂqÂ¡ÁwÐ"Ã¯»GÄwÁ¡¼¾¿Ç*½ÀÎÝqÇ*½£½Ì¹e»WËÀÔ ¼ÒÔ¾Ë»GÅ¡ÐÔÒÆØÐcÁwÄwÐ½¡Ã Ðc»GË¿ÆcÈG»WÐ»vÃ¢»WÄwÁw¼Ò¿Ç*½jÀÎ S½jÃ¢Ô7»GÂ 7Ô j½¡¼Ò»GËÆ = b Ã¯»GÄwÁ¡¼¾¿Ç*½ÀÎwÆÅ¡Ä4Å j½¡8¼ fÉWÆ½Ã\½ 9 ÔÒÃÑÓÃ¯ÉGÐcÀÉGÂj#» j½¡Ä¡ßË»WÃµ¼¾É À»WÈGÔ¾ÂMÝ j½¡Ä¡ßÑØÁwÈWÔÒÀÜ ,Ï¡¸¼¾Â½¡¼¾Ã¢½¡,È ¡½½¿4Ó*½¡¼¾Ô À%Å¡ÆÀÉ ÀAx »G¼ À j½¡¼ÒÎwà*½¡Ë$C½ '/.0+4!ÿ»GÆÐ»WË¿ÆcÈG»GÐÃ¯»GÄwÁw¼Ò¿Ç*½jÀÎwÆÅjÄ4Å ¡½j¼4»GÂ 7Ô j½¡¼Ò»GËÆÅj¼¾¼¾Ü À%Å¡ÆÀ Â½¡ØÓ4ËÂMÏ å 9ìqíMý,è ç*áGé ¡»G¼ÒÊw¼ Þc»k½DÃ\ÅjÀÐÔ 9Á¡ÆÈG¼ÒÁwØ*½¡Ô À e»Gàà,»GËN½§ÆÁwÐcÐ»WË¿à,»GË Ý Ý ÉWÆ OÏ >ÅjÀÇ½jÀÎÝÇÁwÄ¡ß ð tþÿì7èRé .é4G Ç*½ x = 6 ÝM½¡ÂqÂ¡Á¡Ð c = 2a F*Ç*½¡ÆcÁwË¼ÒÎ½¡Ë Ý*Ç*½ y = −3 Ý,½¡ÂqÂ¡ÁwÐ b = −2d ÏM¸ÈÌÔÒÆâÂjÊwËËßw»WËoa ¼|ÅjbÀÆcÈWÔ¾ÂMÝ*ÇdÁwÄ¡ß<Ç½ x 6= 6 ÉGÆ Ý*½¡ÂqÂ¡Á¡Ðv½ÑÃ\ÅjÀÐÔ 9$ÁwÆcÈG¼ÒÁwØ*½Ñ¼¾ÔÒË»TÅjÐÔ¾Æ½¡Ë¢¹eÛ4ÄwÄw»WÀ¼¾»WË Ï Ä¡ßw½¡ËÔ¾Æ"»WÄ¡ß§»W¼¾ÂjÉGØÈW»G¼ÒÀ αa + βb + γc + δd ¼¾ÔÒË»TÅ¡ÐcÔ¾Æ yÂjÁw6= −3 ÃÑàÔÒË*Å¡ÙGÔÒÎÑ»G¼ÒÆÕ£ÉWÆ"Ç*½¡ÐÃ¢½¡¿ÔÒÂ$Â¡Á7ÁwÐ¿ÔÒË*ÅjÀÅ`ÞÅjÀtÙWÆ½¡Â ÉWÆ Ç*½À%Å¡ÐcÁwÈGÈG½ÑÃ¢»WÄÝ½ÑÃ¢Å¡ÆÁ7¿ÔÒÂj½ÀzÉWÆ½ÑË4»GÄ¡ß¡»G¿ÔÒÂ¡»WÀâÙWÆ½¡Â Éb GÆ d Ï,¸ÈÌ»G¼ÒÕwààÔ.»GÆc»WÀà,»GËØ,ÉG¼Ò¿*Å¡Ó¼2½¡È α + 2γ ÝÔÒ¼¾¼¾» 1À a¡» 3αc + x · β ½\ÂjÉWÀ´ÂjÁ ÁwÐc¿Ô¾ËÅjÀ%½4Ý,½¡Ã¯Ô¾Â<½jÈ x 6= 6 »WÆ»WÀà»WË ÙWÆ½¡Â α = β = 0!!Ð½½¡¿4Ë*½¡Â°»WÄ¡ß½¡ÐÅ¡ËÀÑ$× !ÿ4À F½<Ã¢Å¡ÆÁ7¿Ô¾Â»GÆc»WÀÐc»\½jÈ¢»W¼¾¼¾»WËÕwÐcÈGÉGÆAÇ*½jÆÁwË¼ÒÎÏ Ø,ÙGÔ¾Á¡Ë*Å¡¼¾ÔÒÆ½¡Ë½<Ã¢ÅjÀÐc:Ô 9 ¿» À»WÐÃ¯Ô¾Ë*Å¡Ë4Æ½\ÔÒÆÂ¡Ê¡ËËßw»GËÂqÔ¾ÆcÈTÅ¡Ã¯ÜÒÀÇ*½jÀÎ (x − 6)(2y + 6) F,¼|ÅjÀÆÈWÔ¾ÂMÝÇ4ÁwÄ¡ß»GÈÑÙWÆ½¡Â½¡È x = 6 j½¡Ä¡ß½¡È y = −3 »WÆ»WÀà»WË¼Ò»GÆÈ×4Ï !Ä¡ß¢½¡È Ý »GÆc»WÀà,»GË ½¡È ÓË4ÔÒ¹eÁwÐcÃ Ã\½jÀÐÁwÔÒ¿¿*½¡¼4Ô¾ÈGÁ¡Ã¢ÁwÐ¹Ï ÈËß ÔÒ¼ jÅ¡Ë¢ÄwÐ½ ;Â7Ó40Æ 4àÅ¡ÐÃ¯»G¼ ß $ÉG¼ D¹R½$Ðc»GØxÐc6=»GÈW»G6ËÀ%yÅ¡¼ 6=Þ½4Ï−3H½ x 6= 6 Ý¿4M» y = −3UÝM½¡ÂqÂjÁwÐ a Ý b ÉGÆ c ¹eÛ4ÄwÄw»WÀ¼¾»WË»GQÂ e»GÈ½Ñ¹e»GËÀÔÒÇ»GÈAË*½jÄ¡ßwÁwË<Ç*½jÆÁwË¼ÒÎ½¡Ë ÔÒË¿ÁwÂjÁw¼¾Ç*½À Î OÏ !Ä¡ß½DÃ¢½jÀÐcÁwÔ¾¿oÔÒ¼Òßw»WËÂ¡Á¡ÐÔÒÆ´ÄwÐ½ ;*ÂqÓ0Æ Ð»WØÐ»WÈG»WËqÀÅ¡¼ Þ½<»GÄjQß XÉW¼ o¹R½4Ý½¡Ã¯»G¼ ß7Ë»GÂ½¡È$»GÄ¡ß7Ô¾ÂÉG¼¾É ÀÂ¡ÉWÀ Ø*ÅjÐÇqÓÈT½jÃ¢ÁwÆ"ÉW¼¾¼Ò»G¼fÇ4»G¼Òß¡»WÀcÀ»GÆcÜÒÀeÞcÛQÂ R»WÈG»WÂ b!!Ë»WÂ§ÉGÆ d!ÿË»GÂ¯¹e»G¼¾»W¼¾Ë»WÂ\Ã¯»G Ä Ï4¸È x = 6 Ý y 6= −3 »WÆ»WÀâÆcÈGÔ¾Ã¯Ã¯»WÀÐcÔ¾ÂqÓ Æ !ÿÀÔÒ¼Òß¡»GËÂjÁwÐÔ¾Æ»GÄ¡ßÑÓÄ¡ß½jËÔ¾¼ ßw»GË¯ÄwÐÅj¹ Ðc»GØÐc»GÈG»WËÀ%Å¡¼ Þ½4ÝÙGÆ½¡Â$½ØÅ¡ÐÇqÓÈG½¡Ã¢Á¡ÆÉW¼¾»WÂ !!Ë*½jÂÑÉGÆ !ÿË»GÂÌ¹e»G¼¾»W¼¾Ë»WÂÑÃ¯»GÄÏ MÉGÄwÛ¼M½jÈ Ý W » Æ W » À à W » Ë G É Æ e ¹ 4 Û w Ä w Ä W » À ¾ ¼ W » Ë G » M Â w Ý ¿ » W É Æ c Ð G » Ë 4 ¿ Ð â » ¡ ½ " È G » Ò ¼ Æ DÕ w»W¼PÝaÔÒ¼¾¼¾» 1À ¡»t½ćÃ\ÅjÆÁ7¿Ô¾ÂqÂ½¡¼4ØÅ¡ÐÇq"Ó ! ÈG½¡Ã¢Á¡ÆGÏ !ÄjxßÑ=½Ã¢6 ½jyÀÐcÁw=Ô¾¿Ì−3Ô¾¼ ßw»GË4Â¡ÁwÐ&ÔÒÆ0aÄwÐ½ ;*bÂqÓ Æ wÐ»WØÐ»WÈG»GËÀÅ¡¼ Þ½c »WÄ¡ß dÉW¼ 4ÀGÝw½¡Ã¯»G¼ ß7Ë»GÂÃ¢ÔÒË¿ÂjÉWÀÉW¼¾ÉWÀ&Ç»G¼ ßw»WÀcÀ»WÆÜÒÀeÞcÛÂ $! ÑØ*Å¡ÐÇqÓÈG½¡Ã¯ÁwÆ"ÉG¼Ò¼¾»G¼SÏ ½ GeÇÔ¾ÆcÈG»WË X£Ø,ÁwËÀ Ý*ÊwÆcÆÈW»W¹eÛÄwÄ¡Õ\ÄwÐÅj¹eÁwÂ\Ðc»GØÐc»GÈW»GËÀ%Å¡¼ ÞÅ¡Â ø &þÿì7èRé .é4å 9ìqíMý,è ç*áGé Ô¾Ë¿4Â¡ÉWÀâÃ¢½jÀÐcÁwÔ¾¿DÐ½¡ËÄTÞ ÕwÂj»W<À Ýf»WÈGÉWÐcÀ´Ã¯Ô¾Ë¿4Â¡ÉWÀÊwÆÆcÈG»WÄwÃ\½ÀÐÁ¡Ô¾¿Ð½¡ËÄTÞ½¢¼Ò»W¹eÊw¼ Þc»Gà!à §¼¾»WÇ»WÀG#Ï " ÕjÀTÝ,ØÉW¼¾¿*Å¡Ó4¼2½jÈ {1, 4} ÉWÆ´½ {2, 5} Ç*½j¼¾Ã¢½¡ÈGÁwÂ Ã¯Ô¾Ë¿4Â¡ÉWÀÃ¢½jÀÐcÁwÔ¾¿4à*½¡Ëo¹eÛÄwÄw» À¼Ò»GË»WÂ,ÝÜÒÄ¡ß½¡È {1, 2, 4, 5} Ã¯Ô¾Ë¿ÂjÉWÀÊwÆcÆÈG»WÄwÃ¢½jÀÐcÁwÔ¾¿à½¡Ë¹eÛ4ÄwÄw»WÀ¼¾»WOË F Ü¾Äjß A ∨ A ÉGÆ Ð½jËÄ[Þ½ÑÔÒ$Æ Ï A∨B !!à*½jË½jÈGÁwËqà*½¡ËË»WÃ Ã¢ÔÒË¿»W% Ë $»W¼¾»G&Ã Ç*½j¼¾Ã¢½¡È¹eÛÄwÄ¡»WÀ¼Ò»GË Ý4ÇÔ¾ÆcÈG»GË½¡È w'Ý ÑÉWÆ X£»G¼Ò»GÃ¯»GÂ§ÂjÊwÈGÛ4¼Ã¢ÔÒË¿»GË !ÿàA»W¼¾ÔM∨¹eÛAÄwÄw» À¼¾»WË§ÙGÆ½¡Â ,!!»WÀzÀ%½¡ÐÀ%½¡¼ÒÃ\½¡ÈWÇ*½jÀGÝ7»WÈGÉWÐcÀvÃ¯Ô¾Ë¿»WË !ÿà»W¼¾ÔM¹eÛÄwÄw» À¼¾»WË§¼¾»WÄ¡¹eÊw¼ Þc»Gàà¢ÙGÆ½j( Â $!PÀTÏ4¸ÈGÁwËqà*½jË A A ∨ A ½¡È 2, 3}!½jÀvË»WÃÍÀ%½¡ÐÀ%½¡¼ÒÃ\½¡ÈWÎ ¢»W¼¾»G&Ã »GÂ<Ã¯Ô¾Ë¿D¹eÛÄwÄ¡»WÀ¼Ò»GË»WÂ w)Ý $ÉGVÆ X¢Â¡Ê¡ÈGÛ¼.Â¡» ÀÀÕjÀ jÅ¡¼|½jÆÈWBÀ j½¢½¡ÈÌ»GÄ¡ß7ÔÒÂ7Ç4»GÈ ÇÁ¡ÈG{1, ÈT4Å ¡»GÇ» ÀRÞcÛÂ½ X !½ÀTÝ½£Ã¢Å¡ÆÔÒÂqÇÁwÈA*½ !!» 4À FÜÒÄ¡ß¢Â¡ÉWÀâÂjÉWÀ»W¼¾»W+Ã ¹eÛ4ÄwÄw»WÀ¼¾»WËqÀvÂ½¡Ø4ÓËÂMÝM½¡Ã¯Ô¾ÂqË»GÂ\½¡È´ÓËÔÒÎÞ½ A ∨ A! à,»G¼ÒÔPÏ ÈGÉWÐcÀ A ∨ A ÄwÐ½ ;*ÂqÓ0Æ qÐc»GØÐc»GÈG»WËÀ%Å¡¼ Þ½Ì½¡È½´ÄwÐÅ¹Ýq½¡Ã¢Ô À»GÄjß£Ç*Å¡ÐcÁwÃ¢ÆcÈGÊwÄ¡àÕw¼4Âj½jØÓËÂ ÄjßwÝqÇÁwÄ¡ß J!¼¾»W¼¾ÎwÄw½jÀÓË4Â K ÐcÎw¼|½ÑÂjÉWÀÉG¼¾» ÀTIÏ e¸bÇ*Å¡ÐÁ¡Ã¢ÆcÈGÊwÄ$ÉG¼Ò»GÔf¹e»W¼¾»W¼¾Ë»WÂ\Ã¯»GCÄ !!Ë4»GÂM,Ý $!!Ë4»GÂ§ÉWVÆ X$!!Ë*½¡ÂMÝ*½£¼Ò»G¼¾Î¡Ä½jÀÁjÀÀtÉW¼¾»W-Â !!Ë4»GÂ§ÉW/Æ .D!!Ë»WÂ,Ï !!à,»GË 7Ô¾ÆÈWÁwËÀ.Ã\Å¡ÐfÃ¢ÔÒË¿»G0 Ë v»G¼Ò»G+Ã AÇ*½j¼¾Ã¢½¡È2¹eÛÄ¡Äw»WÀ¼¾»GËfÏ ÈWÀ.¼¾»WÄw»GÄ¡ß7ÆcÈG»GÐ ààk½¡1È .t»GÆ» À ¡ÉGÄwÔÒÄwØÐcÎwà*Å¡¼¾Å¡Æ4Å j½¡¼ A∨B »W¼¾¼¾»WËÕwÐcÔ¾ÈGË4\Ô Ã\Å¡Ð\¼|ÅjÀcÀÓÂMÝtÇÁ¡Ä¡ß {1, 2, 4, 5} = {1, 4} ∪ {2, 5} ÉWÆ<Ç*½¡ÆÁ¡Ë¼¾Î½jË {1, 2, 3, 4} = {1, 4} ∪ {2, 3} Ý Ý ÉWÆ S½¡Ç4Áw¼Ã¢ÔÒË¿ÔÒÄ¯à½¡¼ {1, 2, 3, 5} = {1, 5} ∪ {2, 3} {1, 3, 4, 5} = {4, 5} ∪ {1, 3} {2, 3, 4, 5} = {4, 5} ∪ {2, 3} Áw¼Ò¿*½¡¼ÒÐ½AÜ¾ÐcÀÓÂ¯½¡È A ÝTÞcÁwààÐ½Ñ½ B!!à,»G¼¾Ô*¹eÛÄ¡Äw»WÀ¼¾»GË<À WÏ !Ä¡ß A ∨ B ½¡È U ÓËÔÒ¹eÁ¡ÐÃ Ã¢½jÀÐcÁwÔ¾¿¿½¡¼MÔ¾ÈGÁ¡Ã¢ÁwÐ¹Ýq½¡Ã¯ÔÔÒÆÃ¯ÉWÀ ÄwÐ½ ;*ÂqÓ Æ ,Ðc»GØÐc»GÈW»GËÀ%Å¡¼ Þ½£»GÄ¡%ß .£ÉG¼ <Â¡ÊwÐWÏ å 9ìqíMý,è ç*áGé ¸Èo½¡¼¾Ä¡ÁwÐÔ ÀÃÑÓÆ$»W¼¾ÕwÆcÈGÊwÐ§»WÄ¡ßÃ¢ÔÒËÔ¾Ã¢Å¡¼¾ÔÒÆÑ1Æ 4¼ÒWß J¹e»GÆcÈGÜÒÀÕ¡¹RÅjÀ¢Â¡»WÐ»GÆWÝ"»GÈ eÃ¢ÔÒËÀD½¡È ã ú Ñþÿì7èRé .é4Ã¯ÁwË¿ÞcÓ4Â§½ 2´ÐÓÆcÂj½j:¼ !½j¼¾ÄwÁwÐcÔÒÀÃÑÓZÆ wÉWÄwÐ»WÇ*½`ÞÀ%ÅjÆ4Å j½¡¼¼|ÅjÀÇ*½jÀ Î ½£ÆÁ¡Â7ÆcÈGÊwÄ¯Áw¼Ò¿*½¡¼|½jÔ,ÂjÊwÈGÛ4¼ À%½¡ÐÀ%½¡¼ÒÃ\½¡È n − 1 ¿*½¡Ð½jàÁ¡À eÉGÆ§Ø,»GÐcÆÈG»oÃ¢Å¡Æ¢ÉG¼¾» À§Ë»WS Ã Ï àà,»GË_ÂjÉWÀ<Ø*Å¡Ð½jÀ¼¾½¡Ë¹eÁ¡WÂ ÙG1Æ 4ÙGÆ<¼¾»WÆÈ¡ÝÀ»WÇ*ÅjÀ<½NØ*Å¡Ð½À¼|½jË¹eÁw Â _ÙGBÆ ÙGÆcÁwÂ¡Á¡N Ë ¡»WÀÀ Ã¯Ô¾ËÔÒÃ\Åj¼¾Ô¾Æ0ÊwÆÆcÈG1Æ 4¼ÒWß <Ø*Å¡ÐÁ¡ÆÜÒÀÅ¡Æt½ÌÂ¡ÉWÀ S½kÆcÁwÂqÆÈGÊ¡ÄwÊwË<ÆÈWÁwÃ¢ÆcÈGÉW¿Áw<Æ ÙG1Æ 4ÙGÆvÂ¡ÊwÈ ÀÔÉG¼¾à,Õw¼,Å¡¼Ò¼PÏ ÈWÀv½Ì¹RÅjÇÁwVÈ ¡ É ¡»Ë4»GÃ ÙWÆ½¡Â Ó¼¾»W Ð !!ÂjÊwÐcÀGÝ Ç½¡Ë»GÃ H½¡Ã¢ÔÒ¼ÒÀÁw"Ë !!ÂjÊwÐcÀÔÒÆÂ½¡Ø4ÓËÂMÝ À»GÇ*ÅjÀt½Ì¼Ò » jÅ¡ÄÅ¡ÆcÁwÂ£Ó4ÀÅ¡ËD½¡ÈÉG¼¾Ç½¡¼¾Ã¢½¡È jÅ¡¼ÒÀÁwÈT½À¼|½jË¢Ã¢½¡Ð½jO¿ ÉWØØ°½$ÆÁwÂqÆcÈGÊwÄ§Á¡¼¾¿*½¡¼¾½¡Ô¾à,Îw¼*¹eÁwÄ¢Å¡¼¾¼ÒËÔPÏ ÈÌËß7Ô¾:¼ ¡ÅjË½jÈÁ¡Ø4ÀÔÒÃ\Å¡¼ÒÔ¾ÆÃ¢»WÄwÁw¼¾¿Å¡ÆGÝÇ4Ô¾ÆÈW»GËØÁwËÀ½¡È n ¼Ò»GÄwÐcDÊ ÔÒ¿»Gà4àÉW¼¾à,Õw¼ Å¡¼Ò¼PÏ å 9ìqí,ý,è .çáGé A.»GÂqÔÒËqÀÆÛÂ<½jÈWÀv½¡È L ¼¾ÔÒÆcÀ%ÅjÆtÛ4À»WÃ¢»WÈGÉWÆcÀTÝM½jÇÁw¼½ÑÄwÐÅj¹.»GÄ¡ß¡»WÀ¼¾»GËÉG¼ÒÉGË»WÂ§Â¡»WÈG¿Õ¡ØÁwËÀeÞ½ ü 0þÿì7èeé é4 e¼¾»GÄjßw»GËu»GÈ Ñ½¡ÈD»G¼ÒÆÕÝ&½ wÉGÄ¡ØÁwËÀ Ø,»G¿ÔÒÄ½¡ÈDÓ4ÀÁw¼¾ÆcÎo»G¼¾»WÃ ½°¼ÒÔ¾ÆcÀÅ¡à*½¡ËfÏ ÈDËß ÔÒ¼ jÅ¡ËØ,Áw¼¾ÔÒËÁwÃ¯Ô|Å¡¼ÒÔ¾ÆWÝ Ã¢»WÄ ! J (J ) ÃÑÓ À%½jÀeÞcÓÂMÝ2ÇÁ¡Ä¡ß9»WÃ¢»W¼¾¼Ò»WÀÀk½¡ØØ4Ð4Á 9 Ô¾Ã¢Å¡ÙGÔÒÎwÆ´¹R½¡ÂÀÁwÐ½¼¾»WÄ¡¹e»G¼ Þc»Gàà 2 − Ï2¸È§»GÐc»G¿» ÀÔ¹e»G¼|½j¿*½jÀÑ»WÄ¡ßÀ» ÀÆÈWÕw¼¾»WÄw»GÆ B x,y

4,4

x,y

5,4

1

n

1 m

à,»GÃ¯»GË» ÀÉWË»GÂ§ÔÒ¿ÕwÔÒÄwÉGËßw»¼¾»WÄ¡ßw»WË T Ý4½Ì¹e»W¼|½¡¿½jÀtØÐc»GÙW»G¿»WËÙGÔ¾Å¡Â\ËÉW¼¾ÂqÛ¼ÒÔjÅ¡¼ ÀÁwÈG½jÀ%Å¡Ç4ÁwÈÀ½¡ÐcÀÁwÈGÎÝ7»GÄjßwÉGà<Ø*½jÐ½¡Ã¯É,! À»GÐ»WÔ¾à,»GË B!/w»W¼fÃ¯»GÄw»WÄ¡ßw»WÈGÕ B à,OP »GÃ¯»GË» ÀtÔ¾¿4ÕwÔ¾ÄwÉWËßw»Ø,»G¿4Ô¾Ä OP T Ï ÂqÂ¡Á¡ÐtËß ÔÒ¼jÅ¡Ë OP T ≤ OP T Ï >»WÄ¡ßw»WËD»GÈW»GË ÂqÜ 7Û¼ L ½ B à»WÃ¢»WË»WÀÇ»GÈAÀ%½jÐcÀÁ¡ÈGÎ$¼¾ÔÒÆcÀ%ÅjÆtÛ4À»WÃ¢»WÈGÉWÆ½¡È L Û À»GÃ¯»GÈWÉGÆcÇ»GÈAÀ%½¡ÐÀÁwÈWÎ$ÆÁwÐcÐ»GË4¿à»WË Ï H½§½jÈ Û4À»WÃ¢»WÈGÉGÆcà»WË »G¼ÒÂ¡»WÈG¿ÉWÆ»GÂjÁwÐ !!Äjßw»G¼2Ã\ÅjÐVwÉWÄw»GÈ ÀÛË4Â,Ý.½¡ÂqÂjÁwÐ´½¡È ÉGÆ Û4À»GÃ¯»GÈWÉGÆ»WÂ°Ëß7Ô¾¼jÅ¡Ë ÓÄjß½¡Ë*½jËËß LÔMÔÒ¿Õ¡ÀÔ¾Ä¡ÉGËßw»W¼¾Ë»WÂ,JÏ Ô w»W¼ L ½jØØÐ4Á 9 JÔ¾Ã¢Å¡ÙWÔ¾ÎwÆ0¹R½jÂqÀÁwÐ½ 2 − ÉGÆ OP T ≤LOP TLÝ¡»GÂqÂjÁwÐÂ¡ÉGÆcÈVj½¡Ä¡ß7ÓË4Â,Ï H½A½¡È Û À»GÃ¯»GÈWÉGÆcà»WË »W¼¾Â¡»WÈG¿ÉWÆ»WÂ¡ÁwÐ !!Ä¡ß¡»G¼*Ã¯ÉGÄAË»WÃ wÉGÄ¡»GÈWÀÛËÂMÝ ½¡ÂqÂ¡ÁwÐ½¡È Û4À»GÃ¯»GÈGÉWÆz½ à»WÃ¢»WË»,! À»GË max(pL+ p , OP T ) ÔÒ¿J»GÔÒÄ¹eÁwÄ´À%½¡ÐÀ%½¡Ë4ÔPÝ½¡JÃ¯Ô4Á¡Ø4ÀÔÒÃ\Å¡¼ÒÔ¾ÆWÝjÇÔÒÆÈW»GË OP T ≤ OP T ÉWÆLËß7Ô¾:¼ jÅ¡Ë p + pB ≤ OP T Ý ÜÒÄ¡ß§»Wàà»WË°½¡È´»WÆ» Àà,»GËÔÒÆ"Â¡ÉWÆÈG»WË j½¡Ä¡ß7ÓËÂMÏ 0

0

0

0

0

0

n

0

1

n

n

0

0

1

0

0

1 m

1

0

1

n

! "$#%'&( ) *,++.-0/2143657368:936;<=/ >?A@CB!D!EGFIH4J 36KML2N4O.P.QSRUT x1 = 2 L x2 = 0 L kl?m 3]PUQ!3 D A m × nc 3 F 8 W E ;i[onpL b ∈ Rm L KXR F T E W FIF RUK O F T6KgO!q V 3 J!E O;7/sr b0E R FIFIb4J 8\3]P2LZN4O.P.QtR,T x3 = 0 x4 = 1 VUW R YZ9 W T6[ F 8\3]P.O!K^1 W F W E R.K W 9292[u;a3 D 1 F T]3 ;v3 J JUB T H KwqO D!E O F R D R,T 9Y_36;a` F 9 W T6[ F 8\3]POK^1 W F W E 3]P.Q0[ J 8\3]P.O!K^12N2R EIx2j RU1 EGb4Jc 3d8\3]PeR,TSRUK W 9492[f3]PUQ!3 D K^` E Kg3 D4Fih P c y{z}| Ax ≤ b L x ≥ 0 ;a3 D 1 F T]3 ; D 3 Jj y~]| yA ≥ 0 L y ≥ 0 L yb < 0 T EJ 3 K^K E 36N W E 8\3]P!8 b0E R EGD [L'N4O.P.QR,T x1 − x 2 ≤ 2 yvz| c 3 F 936K^[ x h6F R y~]| c 3 F 936KX[ y V 3 J!E O!;aO J x2 − x 3 ≤ 0 x1 − x 3 ≤ 2 J.B T H KlqO D!E O F R D RUT3]P.Q0[ J K h7E 3]T6[ J /Y A? p q RU;IRU8 h]xE 33 ;%+8x[ D4 10≤3 D2h ; EIh6J ;a3f1 BD!EGFIH2J 36KL]N4O.P.QR,TZRUK W 9492[!8 W E ;i[n W K E RUK J OO!;a12[ D W E W c T]O EaE 8R E ;aO![^1P!;iR, Jb2Fvc 3 8\3 D2D Q0[^93 D [gP3 D L,RU1, b4J 8\36P3]PUQP;IR Jb2F ;v3 q4;a3]T]3 D!E W 5][ x W E   0 1 0 2 2 0 2 1 4 3  p 0 1 0 −1

? m 3]P.Q3 D M1 R,TSRUK W 9492[_P; W JUB ;a8R E ;aO[^1,iR0L[^KXKg3 E V 3 M2 RUTdR.K W 9292[_8 V RUK xFR.KXE R.3 q4FaNE RU KXB 8K BUR,EiT E Y D JR OJ O!36;aKg123 [ 8\D W 36E[W 4T]PUO Q EiL4E N48O.P.R QSE ;aR O![^J.1lh7/E rS83]R P E ;a3 OKg36[^1 K E 3 B!E FIN4F T]3 E3]`PJ3 c 3e3]P.Q08 M2 R YR,T U6,6 F T RUW 9 RU1 E 36Kv3 F Y_8R E ;aO![^1SKg36PUQ3 Dp 9Y D 3R,T U6,6 F T R.92R.1 E 36Kv3 F YZ8R E ;aO[X1SKg3]P.Q3 D  0 1  0 0

1 0 0 0

1 1 0 1

1 1 1 0

0 0 0 0

 1 1  0 1

W FIE D ;iR[n J W K E RUK 6h R F W M1

l ?m 3]P.Q3 D 3 J R G E 3 Kv3 F P; W 5 F 25 F RU[ R E 36;i8 h6F T]3 E 3 F F T W 8\O J < cE `K¡ c [gP L Rq W ;vO FfF T W 8\O J JUB T E V 3]T]3 E ` h Kg3 J:F 2KoQ RKg3]P.Q3 D¢ L£R¤q W ;iR E KXR DF T W 8\O J:JUB T E V 3]T]3 E ` h Kg3 J¥F 2KoQ R F T6[ D!EIh6D¢ L Rq W ;vO Fh6F q W ;iR E KXR D¦F T W 8\O JSJ.B T E [ h Kg3 JSF 4KgQ Rq3612[gPe<./ m 3]PUQ!3 D 3 J RdRd§ E 36[ D 36; c qO D!E O J Rq W ;IR E K¨R DF T W 8\O J L R E 36;i8[ D W KÔ J Rq W ;aO FZF T W 8\O J / 1 b2D4J 83]P3]PUQ LR,TOq E [^8 W K^[ F N0OT JUh q3 FaE K^3]P 3 Kv36929 JUh7EGF T]3 ;v3 F¤F 2KoQ0©§ E 36[ D 36; c MW E RUTS36Kg` RU1 W F O DE R Db K E * c RUq2q4;aO n4[^8 W 5][ x!F RUK^P.O!;a[ E 8 b2FªF 3]P!« EGFih P h V 36K/ ¬A? 1, b2D4J Oq E [^8 W K^[ F'H£E 368\36T h6FaE R,T 1|| P wiCi 3 KXRU1 R E ;IR0/ w®g¯v°±}²±³´¶µ·'¯a¸}´¶°²,¹º¹}»´}¼ºM¯a¸¶½v²¯aºM¼aµ}¾}¼À¿Á¯a·Â»,±}º¼v¿,¹}°Ã»,±³ÄÁÅ wÆ¯a¿Á²¯a°Ãµ}¯a¼v½aºMÆ¯À¹}°°ÃÄf·_Ç¿µÈ±}É²ÁÊZË¶Ì_Í.¯aÆMÎ}Å Ï%ÐgÑUÒ.Ó6ÔgÓ ÕÖ.× ¯a·ØºM¼aÙµ]º½v¸¶¯aºp·sÉÃ¿²¯a¿ª®g¯a°±}²,±³´}³µ]Ù°¾}¿s°±}ÍÆ± ÚÃÆ¿ÉXÛ¶²¯Üµ}½aÆoÝMÙµUÛ »Á´¶¸}Þ'±àß¯a±}²´}³M³p²´}°¸¶´¶¼a±³ áaâ7ã7äiåÁæ Ô^ç áaâ¶äGè ç äIé ÔgÓ]Ñ,ÒÓ6êëì ã6áaâ ìGÓUí ç âî}ï Ó áÈð ë ï Ó áÈðñ ï ç á}ò ÐXÔ^Ô^Ó äiå Óªçó ï Ó áÈðô ïõ.áÈðö ï÷.á_ø Ó Ôgç,ù£ç äGú7áa÷ï û ÷ ì äI÷Uü ìGç ý

Rendszeroptimalizálás Zárthelyi feladatok 2010. április 28. 1. a) Írjuk fel az alábbi lineáris programozási feladat duálisát! (A felírás hasonló alakú legyen, mint a primál feladat felírása, vagyis ne mátrixos alakot használjunk.) b) Igaz-e, hogy az x1 = 3, x2 = −1, x3 = 0 választással a primál feladat optimális megoldását adtuk meg? Igaz-e, hogy az y1 = 1, y2 = 1, y3 = 1, y4 = 0 választással a duális feladat optimális megoldását adtuk meg? max{6x1 + 6x2 + 6x3} ha x1 + 2x2 + 3x3 ≤ 1 2x1 + 3x2 + x3 ≤ 3 3x1 + x2 + 2x3 ≤ 8 2x1 + 5x2 ≤ 2 2. Nevezzünk egy mátrixot unalmasnak, ha minden eleme 0, 1 vagy −1 és minden sorában legföljebb két nemnulla elem van. Mutassuk meg, hogy a Fourier-Motzkin elimináció apró módosításával olyan, polinomiális lépésszámú algoritmus adható, amely az Ax ≤ b lineáris egyenlőtlenségrendszer megoldhatóságát eldönti abban az esetben, ha A unalmas mátrix. 3. Koordinátázza az alábbi mátrix a T test fölött az M(T ) matroidot. Mutassuk meg, hogy vannak olyan T1, T2 testek, melyek esetén M(T1) nem izomorf M(T2)-vel!   1 1 1 0  1 1 0 1     1 0 1 1  0 1 1 1

4. A bal oldali ábrán látható gráf körmatroidja legyen A, a jobb oldalin láthatóé B. Uniformak-e az A ∨ A, illetve az A ∨ B matroidok? b c d e

a

a c d e

b

5. Tekintsük az {a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,r,s,t,w,y} betűhalmazt, és az elemeiből képzett alábbi szavakat, mint részhalmazokat (a szavak utáni zárójelben lévő szám jelenti az adott halmaz költségét): ike (3), chef (3), jimbo (3), stan (4), mackey (4), kyle (5), wendy (5), liane (6), randy (6), gerald (6). Hajtsuk végre ezen adatokkal az alaphalmaz részhalmazokkal történő lefedésére szolgáló, előadáson tanult közelítő algoritmust. 6. Hajtsuk végre és dokumentáljuk a RÉSZÖSSZEG problémára tanult (1 + ε)approximációs algoritmust az alábbi bemenetre. 4, 6, 9, 14, 22; t = 34; ε = 2 A feladatok megoldásához segédeszköz nem használható. A rendelkezésre álló munkaidő 90 perc. Nem szükséges minden feladatot külön lapra írni, de kérjük, hogy a beadott dolgozat szétválasztható legyen 3 részre: az 1-es/2-es, a 3-as/4-es, illetve az 5-ös/6-os feladatpárokra.

A zárthelyi feladatok megoldása Az 1. feladat megoldása. a) A feladat max{cx : Ax ≤ b} alakú, ahol    1 2 3   2 3 1  , b =  A=   3 1 2  2 5 0

 1 3  , c = 8  2

6

6 6

.

Ezért a feladat duálisa min{yb : yA = c, y ≥ 0}. Ezt részletesebben kiírva és az y = (y1 , y2, y3 , y4 ) jelölést alkalmazva: min{y1 + 3y2 + 8y3 + 2y4 } ha y1 + 2y2 + 3y3 + 2y4 = 6 2y1 + 3y2 + y3 + 5y4 = 6 3y1 + y2 + 2y3 = 6 y1 , y2 , y3 , y4 ≥ 0 b) A megadott x1 , x2 , x3 értékeket a primál egyenlőtlenségeibe, az y1 , y2 , y3 , y4 értékeket a duális egyenleteibe (és nemnegativitást előíró egyenlőtlenségeibe) helyettesítve látszik, hogy valóban a primál, illetve a duális egy-egy megoldását adtuk meg. Mindkét esetben kiszámítva a megfelelő célfüggvényértékeket (cx = 6 · 3 − 6 · 1 = 12, illetve yb = 1 · 1 + 1 · 3 + 1 · 8 = 12) azt kapjuk, hogy ezek megegyeznek. Ebből pedig következik, hogy mindkét esetben optimális megoldásról van szó. (Ugyanis ismert, hogy a primál feladat tetszőleges x′ és a duális tetszőleges y ′ megoldására cx′ ≤ y ′ b áll fenn. Így tetszőleges x′ megoldásra cx′ ≤ yb = 12, vagyis 12-nél nagyobb célfüggvényértéket adó primál megoldás nem lehet, x tehát optimális. A duális esetében az indoklás analóg.) A 2. feladat megoldása. Először megmutatjuk, hogy a Fourier-Motzkin elimináció (apró kiegészítéssel) fenntartja azt a tulajdonságot, hogy a rendszert leíró mátrix unalmas. Tegyük fel ugyanis, hogy a (kibővített együtthatómátrixával megadott) (A|b) rendszerre az elimináció egy lépését alkalmazva a (A∗ |b∗ ) rendszert kapjuk. Ha az (A∗ |b∗ ) egyik sora az (A|b) egyik 0-val kezdődő sorának másolata (levágva belőle az első, 0 elemet), akkor ez a sor persze továbbra is megfelel az unalmasság kritériumának. Ha viszont az (A∗ |b∗ ) rendszer (a∗k |b∗k ) sora az (A|b) 1-essel kezdődő (ai |bi ) és (−1)-essel kezdődő (aj |bj ) sorának összegéből keletkezett, akkor ai -ben és aj -ben is legföljebb 1 további nemnulla elem lehet. Feltehető, hogy mindkettőben pontosan 1 van, különben a∗k -nak is legföljebb csak 1 nemnulla eleme lesz (és az is ±1). Ha az ai -beli és aj -beli (nem az első oszlopba eső) nemnulla elemek különböző oszlopban vannak, akkor a∗k nyilván megfelel az unalmasság fogalmának. Ha viszont azonos oszlopban vannak, akkor a∗k vagy a nullvektor, vagy pedig egyetlen nemnulla eleme van és az ±2. Ebben az esetben viszont nyilván leoszthatjuk (a∗k |b∗k )-ot 2-vel, hogy az továbbra is megfeleljen az unalmasság definíciójának. (Ez tehát az említett apró kiegészítés.) Most megmutatjuk, hogy az algoritmus (apró módosításának) futása közben a sorok száma mindig legföljebb O(n2 ) marad (ahol n az A oszlopainak száma). Ebből nyilván következni fog a polinomiális futásidő (hiszen m sorú A estén (A∗ |b∗ ) nyilván O(m2 ) lépésben megkapható). Könnyen látszik, hogy ha A unalmas n oszlopú mátrix, akkor legföljebb 4 n2 + 2n + 1 = O(n2 ) féle sora lehet (ahol az összeadandók a 2, 1, illetve 0 darab nemnulla elemet tartalmazó sorok számának felelnek meg). Az persze előfordulhat, hogy valamelyik sortípus többször is előfordul az (A∗ |b∗ )-ban; ekkor azonban ezek közül egy kivételével nyilván mind fölösleges és elhagyható. (Ha például az (a∗k |b∗k ) és (a∗l |b∗l ) sorokra a∗k = a∗l és b∗k ≤ b∗l , akkor az utóbbi fölösleges.) Így az elimináció minden lépése után az így adódó fölösleges sorokat elhagyva (ezzel tehát az algoritmust másodszor is némileg módosítva) elérhető a sorok számára említett korlát és ezzel a polinomiális lépésszám.

A 3. feladat megoldása. Legyen T1 a 3 elemű test. Azonnal látszik, hogy ekkor a mátrix oszlopait összeadva a nullvektort kapjuk (hiszen ebben a testben 1 + 1 + 1 = 0). Így a 3 elemű test felett az oszlopok lineárisan összefüggőek, vagyis a mátrix nem az U4,4 szabad matroidot koordinátázza (hanem az U4,3 matroidot – bár ennek a megállapítása nem szükséges a feladat megoldásához). Azonban például T2 = R fölött a mátrix determinánsát meghatározva −3 6= 0-t kapunk (a számolást mellőzzük), így az oszlopok lineárisan függetlenek, vagyis ekkor a matroid az U4,4 szabad matroid. A 4. feladat megoldása. A kapott összegmatroid (mindkét esetben) akkor uniform, ha pontosan a legföljebb k elemű részhalmazok függetlenek benne alkalmas k-ra (0 ≤ k ≤ 5). Az A ∨ A matroidban a nyilván továbbra is hurok lesz, a {b, c, d, e} halmaznak viszont a legföljebb 2 elemű részhalmazai lesznek függetlenek. Ezért A ∨ A nem uniform matroid (hanem izomorf az U4,2 ⊕ U1,0 matroiddal, ahol a ⊕ direkt összeget jelöl). Az A∨B matroid ezzel szemben izomorf az U5,2 matroiddal. Az ugyanis világos, hogy a rangja 2 (hiszen sem A-ban, sem B-ben nincs 1-nél több elemű független) és azt is könnyű ellenőrizni, hogy bármely 2 elemű részhalmaz előáll egy A-beli és egy B-beli 1 elemű független uniójaként. (Valóban, minden 2 elemű részhalmaz egyik eleme a-tól, a másik b-től különbözik.) Az 5. feladat megoldása. Az algoritmus mindig azt a részhalmazt választja ki, amelyre a lehető legkisebb a halmaz költségének és az újonnan lefedett elemek számának hányadosa. Az első lépésben a jimbo részhalmazt kell választanunk, mert ennek a legkisebb az egy elemre eső aktuális költsége ( 53 ). Ezt követően a chef részhalmaz jön, 43 aktuális költséggel. A következő halmaz a stan kell legyen, ez újabb 4 elemet fed le, 4 költséggel, majd a gerald halmaz következik, ennek költsége 3 . Az ezt követő lépésben a mackey halmazra lesz a kérdéses érték minimális (2), az utolsó beválasztott 2 szó pedig a wendy, 5-ös értékkel. A kapott fedés tehát: {jimbo, chef, stan, gerald, mackey, wendy}, költsége 25. A 6. feladat megoldása. Az exponenciális lépésszámú pontos megoldás során az Li listában az első i elem által alkotott részösszegek szerepelnek, ezeket az L0 = {0}, L′i = {x + ai+1 | x ∈ Li }, Li+1 = Li ∪ L′i képletekkel kapjuk. A közelítő algoritmusban szereplő listák ettől annyiban különböznek, hogy a t-nél ε nagyobb elemeket azonnal töröljük és az Li listákat a δ = 2n értékkel ritkítjuk (azaz alulról kezdve töröljük azokat az x elemeket, melyekhez létezik olyan náluk kisebb nem törölt y elem, melyre x ≤ (1 + δ)y). Az algoritmus kimenete az Ln lista legnagyobb eleme. Esetünkben n = 5, így δ = 0, 2. A listák: L0 = {0}, L′0 = {4} L1 = {0, 4}, L′1 = {6, 10} L2 = {0, 4, 6, 10}, L′2 = {9, 13, 15, 19} L3 = {0,4,6,9,10,13,15,19 }, L′3 = {14, 18, 20, 23, 27, 33} L4 = {0,4,6,9,13,14,18,19,20,23,27,33}, L′4 = {22,26,28,31,35,40,45,55} L5 = {0, 4, 6, 9, 13, 22, 23, 26, 28, 31, 33}, tehát az algoritmus 33-at ad eredményként.

Rendszeroptimalizálás Pótzárthelyi feladatok 2010. május 13. 1. Írjuk fel az alábbi lineáris programozási feladat duálisát! (A felírás hasonló alakú legyen, mint a primál feladat felírása, vagyis ne mátrixos alakot használjunk.) a) Igaz-e, hogy a (primál) feladat célfüggvénye felülről korlátos a megoldáshalmazán? max{2x1 + 3x2 + 4x3 + 5x4} ha x1 + 2x2 + x3 ≤ 5 x2 + 2x4 ≤ 6 x1 + x3 + x4 ≤ 7 2x2 + 3x4 ≤ 8

2. A G(A, B; E) teljes páros gráf két színosztálya legyen A = {a1 , a2, a3 , a4, a5 } és B = {b1, b2, b3, b4, b5}. Az ai -t a bj -vel összekötő él súlya legyen az alábbi mátrix i-edik sorának és j-edik oszlopának kereszteződésében álló elem. Adjunk meg G-ben egy maximális összsúlyú teljes párosítást (és mutassuk meg róla, hogy maximális).   9 6 6 6 6 6 5 5 3 3   6 4 5 1 2   6 5 5 4 4 6 4 4 2 4

3. Koordinátázza az alábbi mátrix a valós számok teste fölött az M(x) matroidot. Mutassuk meg, hogy x értékének ismerete nélkül is  1 1  1 0 0 1

eldönthető, hogy M(x) grafikus-e!  0 1 1 2  1 x

4. A bal oldali ábrán látható gráf körmatroidja legyen A, a jobb oldalin láthatóé B. Uniformak-e az A ∨ A, illetve az A ∨ B matroidok? a b c

d e

a c d

b e

5. Igaz-e, hogy a Steiner-fa probléma polinom időben megoldható, ha a terminálok halmaza pontosan három elemű, az élsúlyok pedig csak az 1 és a 2 lehetnek? 6. Mutassuk meg, hogy a P 2||Cmax feladatra az LPT sorrendben történő listás ütemezés approximációs faktora nem jobb, mint 76 . A feladatok megoldásához segédeszköz nem használható. A rendelkezésre álló munkaidő 90 perc. Nem szükséges minden feladatot külön lapra írni, de kérjük, hogy a beadott dolgozat szétválasztható legyen 3 részre: az 1-es/2-es, a 3-as/4-es, illetve az 5-ös/6-os feladatpárokra.

Rendszeroptimalizálás Zárthelyi feladatok 2011. április 21. 1. A G(A, B; E) teljes páros gráf két színosztálya legyen A = {a1 , a2 , a3, a4 , a5} és B = {b1, b2, b3, b4, b5}. Az ai -t a bj -vel összekötő él súlya legyen a balra látható mátrix i-edik sorának és j-edik oszlopának kereszteződésében álló elem. Az α valós paraméter mely értékeire teljesül, hogy a csúcsokhoz a jobb oldali táblázatban látható értékeket rendelve a) címkézést kapunk; b) minimális összegű címkézést kapunk?   1 1 2 3 1  4 3 3 4 2    a1 a2 a3 a4 a5 b1 b2 b3 b4 b5  5 5 6 5 5    2 4 6 6 6 0 0 1 1 α  6 6 6 6 5  6 5 7 6 4

2. Tegyük fel, hogy az Ax ≤ b lineáris egyenlőtlenségrendszer megoldható. Jelölje az A mátrix i-edik sorát ai , az ai sor elhagyásával kapott mátrixot pedig A− i .Hasonlóan, a b vektor i-edik komponensét jelölje bi , az ennek elhagyásával kapott oszlopvektort b− i . Az Ax ≤ b rendszer i-edik egyenlőtlenségét (ai x ≤ bi -t) akkor nevezzük redundánsnak, ha az elhagyása nem változtatja meg az egyenlőtlenségrendszer megoldáshalmazát. Bizonyítsuk be, hogy ai x ≤ bi akkor és csak akkor redundáns, ha létezik olyan y ≥ 0 sorvektor amelyre − y · A− i = ai és ybi ≤ bi teljesül! 3. Koordinátázza az alábbi mátrix a valós számok teste fölött az Mx matroidot. Az x valós paraméter minden értékére döntsük el, hogy Mx grafikus-e (és ahol igen, ott adjuk meg a megfelelő gráfot)! 1 0 x 1 0 2 x x 4. Az {a, b, c, d} halmazon két grafikus matroidot definiáltunk, azonban a második gráf éleiről „véletlenül” lemaradtak a betűk. Eldönthető-e azért, hogy a két matroid összege grafikus-e? a b c

d

5. Igaz-e, hogy a Steiner-fa probléma polinom időben megoldható, ha a Steiner-pontok halmaza pontosan két elemű? 6. Mutassuk meg, hogy a P 3||Cmax feladatra az LPT sorrendben történő listás ütemezés . approximációs faktora nem jobb, mint 11 9 A feladatok megoldásához segédeszköz nem használható. A rendelkezésre álló munkaidő 90 perc. Nem szükséges minden feladatot külön lapra írni, de kérjük, hogy a beadott dolgozat szétválasztható legyen 3 részre: az 1-es/2-es, a 3-as/4-es, illetve az 5-ös/6-os feladatpárokra.

A zárthelyi feladatok megoldása Az 1. feladat megoldása. A táblázat adatai (definíció szerint) akkor határoznak meg egy c címkézést, ha minden 1 ≤ i, j ≤ 5 számpárra c(ai )+c(bj ) ≥ mi,j , ahol mi,j mátrix i-edik sorának és j-edik oszlopának kereszteződésében álló elem. Ez az 1 ≤ j ≤ 4 oszlopokra automatikusan teljesül (ez gyorsan ellenőrizhető), a j = 5 esetben pedig α-ra rendre a 2 + α ≥ 1, 4 + α ≥ 2, 6 + α ≥ 5, 6 + α ≥ 5 és 6 + α ≥ 4 feltételeket kapjuk. Ezek együttesen pedig az α ≥ −1 esetben teljesülnek, így tehát ezekre az értékekre kapunk címkézést. Minimális összúlyú címkézést nyilván csak az α = −1 esetben kaphatunk (hiszen α összes többi szóba jövő értékére olyan címkézést kapunk, amelynek összege nagyobb az α = −1 választással adódónál). Az előadáson tanultak szerint úgy tudjuk kimutatni, hogy az α = −1 esetben kapott címkézés minimális összegű, ha mutatunk a gráfban egy olyan teljes párosítást, amelynek összsúlya megegyezik a címkék összegével (vagyis 25-tel). (Ugyanis bármely teljes párosítás összsúlya legföljebb annyi, mint bármely címkézés összege; tehát egy 25 összsúlyú teljes párosítás bizonyítja, hogy minden címkézés összege legalább 25.) Egy ilyen teljes párosítás megtalálását az könnyíti meg, hogy (ugyancsak a tanultak szerint) csak olyan éleket van esélyünk beválogatni, amelyekre c(ai )+c(bj ) = mi,j . (Valóban, bármely M teljes párosítás éleire összeadva a c(ai ) + c(bj ) ≥ mi,j egyenlőtlenséget bal oldalon az összes címke összegét, jobb oldalon M összsúlyát kapjuk; így egyenlőség a két oldal közt csak akkor lehet, ha mind az öt összeadott egyenlőtlenség is egyenlőséggel teljesült.) Ebből tehát az következik, hogy a következő élek közül kell a teljes párosítást kiválasztani: {a1 , b4 }, {a1 , b5 }, {a2 , b1 }, {a3 , b5 }, {a4 , b1 }, {a4 , b2 }, {a4 , b5 }, {a5 , b1 } és {a5 , b3 }. Jól látható, hogy a2 párja csak b1 lehet, a3 -é csak b5 , b2 -é csak a4 és b4 -é csak a1 ; a5 -nek pedig marad b3 . Vagyis megkaptuk a keresett, 25 összsúlyú teljes párosítást: {a1 , b4 }, {a2 , b1 }, {a3 , b5 }, {a4 , b2 }, {a5 , b3 }. Ebből pedig következik, hogy az α = −1 esetben valóban minimális összegű címkézést kapunk. − Az 2. feladat megoldása. Az ai x ≤ bi (definíció szerint) pontosan akkor redundáns, ha az A− i x ≤ bi lineáris egyenlőtlenségrendszer minden x megoldására ai x ≤ bi is teljesül. Más szóval: akkor, ha a − max{ai x : A− i x ≤ bi } lineáris program olyan, hogy a megoldáshalmazán a célfüggvénye felülről korlátos − és a maximum értéke legföljebb bi . (Azt nem kell vizsgálni, hogy az A− i x ≤ bi egyenlőtlenségrendszer megoldható-e: ez az Ax ≤ b megoldhatóságából nyilván következik.) − Alkalmazva a dualitástételt azt kapjuk, hogy ez pontosan akkor igaz, ha a min{yb− i : yAi = ai , y ≥ 0} duális program rendszere megoldható és a minimum értéke legföljebb bi . Más szóval ez éppen azt jelenti, hogy létezik olyan megoldása a duálisnak (vagyis az yA− i = ai , y ≥ 0 feltételeket kielégítő vektor), amelyre − ybi ≤ bi . Éppen ezt kellett bizonyítani.

Az 3. feladat megoldása. Jelölje a mátrix oszlopait sorban a, b, c és d. Az Mx matroid megismeréséhez azt kell megvizsgálnunk, hogy (x különböző értékeire) mely oszlophalmazok lineárisan függetlenek. Mivel az oszlopok síkvektorok, nyilván nem találunk köztük 3 (vagy 4) lineárisan függetlent. A kérdés tehát az, hogy mely oszloppárok párhuzamosak (mint síkvektorok). Jól látható, hogy az x = 0 esetben c mindenkivel párhuzamos, továbbá a k d. Az x 6= 0 esetben viszont csak c és d tud párhuzamos lenni, ezek is csak az x = 1 esetben. Mindez azt jelenti, hogy az x = 0 esetben Mx grafikus: reprezentálja egy olyan gráf, amelyben a és d párhuzamos élek, b egy ezekről „lelógó” (vagy akár külön komponenst alkotó) él, c pedig hurokél. Mx az x = 1 esetben is grafikus: ekkor egy olyan háromszög reprezentálja, amelynek egyik élét megdupláztuk (ezek lesznek c és d). Az x 6= 0, x 6= 1 esetekben viszont bármely oszloppár lineárisan független, így az U4,2 matroidot kapjuk, amelyről ismert, hogy nem grafikus. Az 4. feladat megoldása. Jelölje sorrendben M1 és M2 a két gráf körmatroidját. Mindkét matroid rangja 1, az elsőben {d}-n kívül minden 1 elemű halmaz független, a másodikban pedig a két párhuzamos élnek megfelelő egyelemű halmaz. Így az összegmatroid rangja 2 lesz: ekkora független halmazt nyilván kaphatunk egy M1 és M2 -beli uniójaként, nagyobbat biztosan nem. Mivel a, b és c szerepe szimmetrikus, a feladat kérdésének megválaszolásához csak két esetet kell megvizsgálnunk: az elsőben a d hurokélre, a másodikban a két párhuzamos él valamelyikére kerül a jobb oldali gráfban. Az első esetben d az összegmatroidban is hurok (vagyis {d} összefüggő), az {a, b, c} bármely kételemű részhalmaza viszont nyilván független. Így ekkor M1 ∨M2 grafikus: reprezentálja egy olyan gráf, amelyben a, b és c háromszöget alkot, d pedig hurokél.

A második esetben tegyük fel, hogy a jobb oldali gráfban a két hurokélre a és b kerül (mint említettük, ez mindegy). Ekkor M1 ∨M2 -ben {a, b} összefüggő, hiszen M1 -ből csak az egyiküket, M2 -ből egyiküket sem választhatjuk, ha független halmazt akarunk kapni. A másik három 2 elemű részhalmaz viszont független M1 ∨ M2 -ben: ha a két elem egyike a vagy b, akkor ezt M1 -ből, a másikat M2 -ből választhatjuk, ha viszont a {c, d}-ről van szó, akkor c-t M1 -ből, d-t M2 -ből választhatjuk, hogy független M1 ∨ M2 -belit kapjunk. Az összegmatroidot tehát egy olyan háromszög reprezentálja, amelynek egyik élét megdupláztuk (ezek lesznek a és b). Így tehát M1 ∨ M2 a betűk elhelyezésétől függetlenül mindig grafikus. Az 5. feladat megoldása. Legyenek a és b a Steiner-pontok. Ekkor az optimális Steiner-fa négyféle lehet aszerint, hogy melyiket tartalmazza az a és b pontok közül: tartalmazhatja csak a-t, csak b-t, mindkettőt vagy egyiket sem. A gráf többi pontját a fának természetesen tartalmaznia kell, hiszen ezek terminálok lesznek. Az optimális Steiner-fa tehát a T , T ∪ a, T ∪ b, T ∪ a, b ponthalmazok valamelyike által feszített részgráf egy feszítőfája lesz. Így az említett feszített részgráfokon minimális feszítőfát keresve (ha van) a mohó algoritmussal, majd a kapott fák közül a minimális összsúlyút véve polinomiális algoritmust kapunk a legkisebb költségű Steiner-fa megtalálására. Az 6. feladat megoldása. Legyenek a munkák elvégzési idői 5,5,4,4,3,3,3. Ekkor az LPT algoritmusra a teljes átfutási idő 3 gépen 11 lesz, míg az optimum 3 gépen 9, amiből az állítás következik.

Rendszeroptimalizálás Pótzárthelyi feladatok 2011. május 3. 1. a) Írjuk fel az alábbi (n változós) lineáris programozási feladat duálisát! (A felírás hasonló alakú legyen, mint a primál feladat felírása, vagyis ne mátrixos alakot használjunk.) b) Igaz-e, hogy az x1 = x2 = . . . = xn = 1 választással a primál feladat optimális megoldását adtuk meg? max{nx1 + (n − 1)x2 + . . . + 2xn−1 + xn } ha x1 ≤ 1 x1 + x2 ≤ 2 x1 + x2 + x3 ≤ 3 .. .. .. . . . x1 + x2 + . . . + xn ≤ n x1 , x2 , . . . , xn ≥ 0 2. Legyen A egy totálisan unimoduláris, m sorú mátrix és jelölje minden 1 ≤ i ≤ m esetén si az A i-edik sorában álló elemeinek összegét. Legyen továbbá k ≥ 1 tetszőleges egész. Mutassuk meg, hogy A-ból kiválasztható néhány oszlop (esetleg egy sem, vagy akár mind) úgy, hogy minden 1 ≤ i ≤ m esetén si a kiválasztott oszlopok által alkotott mátrix i-edik si sorában az elemek összege k és k közé esik (ahol ⌊ ⌋, illetve ⌈ ⌉ az alsó, illetve a felső egészrészt jelöli). 3. Koordinátázza az alábbi mátrix a valós számok teste fölött az Ma,b matroidot. Az a és b valós paraméterek minden értékére döntsük el, hogy Ma,b grafikus-e (és ahol igen, ott adjuk meg a megfelelő gráfot)!   1 0 1 a  0 1 1 0  0 0 1 b 4. Az {a, b, c, d} halmazon két grafikus matroidot definiáltunk, azonban a második gráf éleiről „véletlenül” lemaradtak a betűk. Milyen matroidok állhatnak elő a két matroid összegeként? (Ahol az összeg grafikus, ott a megfelelő gráffal adjuk meg az összegmatroidot!) a

c

b

d

5. Igaz-e, hogy a Steiner-fa probléma polinom időben megoldható, ha a Steiner-pontok halmaza legfeljebb 2 log n elemű (ahol n a gráf csúcsainak száma)? 6. Adjunk 2-approximációs algoritmust egy G gráf olyan H részgráfjának megkeresésére, e(H) maximális. (e(H) a H gráf élszámát, χ(H) a H gráf kromatikus számát jelöli.) melyre χ(H) A feladatok megoldásához segédeszköz nem használható. A rendelkezésre álló munkaidő 90 perc. Nem szükséges minden feladatot külön lapra írni, de kérjük, hogy a beadott dolgozat szétválasztható legyen 3 részre: az 1-es/2-es, a 3-as/4-es, illetve az 5-ös/6-os feladatpárokra.

Rendszeroptimalizálás Zárthelyi feladatok 2012. április 16. 1. A G(F, L; E) teljes páros gráf két színosztálya legyen F = {a1 , a2, a3 , a4, a5 } és L = {b1, b2, b3, b4, b5}. Az ai -t a bj -vel összekötő él súlya legyen a balra látható mátrix i-edik sorának és j-edik oszlopának kereszteződésében álló elem (minden 1 ≤ i, j ≤ 5 esetén). Valaki már elkezdte futtatni G-re a maximális összsúlyú teljes párosítás keresésére szolgáló Egerváry-algoritmust: éppen ott tart, hogy az aktuális M párosítás az {a1 , b1}, {a2 , b2} és {a3 , b3} élekből áll, az aktuális c címkézés pedig a jobb oldali táblázatban látható. Hajtsuk végre az algoritmus (egyetlen) következő ciklusát, vagyis határozzuk meg az algoritmus futása során előálló következő M ′ párosítást és c′ címkézést!   7 4 3 3 4  5 4 4 1 2    v : a1 a2 a3 a4 a5 b1 b2 b3 b4 b5  6 3 6 2 6    c(v) : 5 3 5 6 2 2 1 1 0 1  7 7 6 4 4  4 1 1 0 0 (Az algoritmust tehát nem szükséges leállásig futtatni, elég a következő ciklus utáni állapotot megadni. Ha a ciklus végrehajtása nem egyértelmű – vagyis több, az algoritmus helyes futásának megfelelő változat is lehetséges, – akkor elég ezek közül egyet megadni.) 2. a) Írjuk fel a jobbra látható lineáris programozási feladat duálisát! (A felírás hasonló alakú legyen, mint a primál feladat felírása, vagyis ne mátrixos alakot használjunk.) b) Adjuk meg a (primál) feladat maximumértékét! 3. Hányféle nemizomorf matroidot reprezentálhat a valós test felett az alábbi mátrix az x különböző választásai mellett? Ahol a matroid grafikus, ott gráffal is adjuk meg!   1 0 1 0  1 2 3 4  0 1 2 x 5. Adjunk 2-approximációs algoritmust a maximális független ponthalmaz keresésének problémájára olyan bemenetek esetére, melyekre a független pontok maximális száma legalább 2n 3 , ahol n a bemeneti gráf csúcsszáma. Az algoritmus működését szemléltessük is a K2,5 teljes páros gráfon.

max{x1 + 6x2 − x4 } ha 2x2 − 7x3 − x4 ≤ −1 2x1 + 5x3 + 3x4 ≥ 6 7x1 + 5x2 − 4x4 ≤ 0 x1 + 3x2 + 4x3 ≤ 1 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0

4. Az ábrán látható gráf körmatroidja legyen M. Határozzuk meg az M ∨ M és az M∨U5,2 matroidösszegeket! Ahol az összeg grafikus, ott gráffal is adjuk meg! a b c

d e

6. Hajtsuk végre és dokumentáljuk a RÉSZÖSSZEG problémára tanult (1 + ε)-approximációs algoritmust az alábbi bemenetre. 2, 6, 7, 14, 28, 44;

t = 49;

ε=

1 2

A feladatok megoldásához segédeszköz nem használható. A rendelkezésre álló munkaidő 90 perc. Nem szükséges minden feladatot külön lapra írni, de kérjük, hogy a beadott dolgozat szétválasztható legyen 3 részre: az 1-es/2-es, a 3-as/4-es, illetve az 5-ös/6-os feladatpárokra.

A zárthelyi feladatok megoldása Az 1. feladat megoldása. Az algoritmus futása során előálló következő M ′ párosítás meghatározásához először a „piros éleket” kell megkeresni, vagyis azokat az e = {a, b} éleket, amelyekre w(e) = c(a) + c(b) teljesül (ahol w(e) az e él súlyát jelöli). A megadott adatokból könnyen kiolvasható, hogy a piros élek a következők: {a1 , b1 }, {a2 , b1 }, {a2 , b2 }, {a2 , b3 }, {a3 , b3 }, {a3 , b5 }, {a4 , b2 } és {a5 , b1 }; lásd az alábbi, bal oldali ábrát. (Látszik az is, hogy a megadott M párosítás élei – az ábrán vastag vonallal – is pirosak; ha ez nem volna így, az azt jelentené, hogy az algoritmus korábbi futása hibás volt.) Ezek után M ′ meghatározásához M-ből kiindulva futtatni kell a maximális párosítás keresésére szolgáló javító utas algoritmust a piros élek alkotta részgráfban. A párosítatlan F -beli pontok: a4 és a5 . Látható, hogy a5 -ből nem vezet javító út párosítatlan L-beli pontba (vagyis b4 -be vagy b5 -be), mert a5 -ből piros élen egyedül b1 -be lehet lépni, ennek az M szerinti párjából, a1 -ből viszont nem lehet továbblépni. Ezzel szemben a4 -ből indítva a javítóút keresést hamar sikerrel járunk: az a4 , b2 , a2 , b3 , a3 , b5 sorrendben bejárva a csúcsokat javítóutat kapunk; ementén javítva a következő párosítást kapjuk: {a4 , b2 }, {a2 , b3 }, {a3 , b5 }, {a1 , b1 } (lásd a jobb oldali ábrát). b1

b2

b3

b4

b5

b1

b2

b3

b4

b5

a1

a2

a3

a4

a5

a1

a2

a3

a4

a5

Egyelőre nem biztos, hogy ezzel már megkaptuk a keresett M ′ párosítást, mert előfordulhatna, hogy a most kapott párosítás még nem maximális a piros részgráfban. Azonban nem ez a helyzet: b4 -re nem illeszkedik piros él, így nyilván nincs öt élű párosítás a piros részgráfban. Ezért M ′ a javítás után kapott fenti négy élből áll. A következő c′ címkézés meghatározásához először meg kell határoznunk az F -beli párosítatlan csúcsokból (jelenleg ez csak a5 -öt jelenti) alternáló úton elérhető L-belieket, illetve ezek F -beli párjait. a5 -ből azonban továbbra is csak b1 -be vezet piros él, ahonnan a1 -be lépve elakadunk, így b1 az egyetlen ilyen L-beli csúcs (amelynek F -beli párja tehát a1 ). Így az algoritmus működési szabálya szerint az {a1 , a5 } és {b2 , b3 , b4 , b5 } halmazok közti éleket kell vizsgálnunk: ezek mindegyikére ki kell számítani a c(a) + c(b) − w(e) „fölösleget”, majd ezek minimumát kell venni. A feladat adatait felhasználva az a1 -ből induló (és {b2 , b3 , b4 , b5 }-be menő) élek fölöslegei rendre 2, 3, 2 és 2, az a5 -ből induló élek fölöslegei pedig 2, 2, 2 és 3. Ezeknek a minimuma pedig δ = 2. Ezek után c′ meghatározásához azokon az F -beli csúcsokon kell δ-val csökkenteni a jelenlegi címkézést, amelyek párosítatlanok, vagy amelyeknek a párja altenáló úton elérhető; ezek tehát a1 és a5 . Hasonlóan, az alternáló úton elérhető L-belieken – vagyis most csak b1 -en – kell δ-val növelni az aktuális címkézést. Így tehát a keresett címkézés: v

:

a1

a2

a3

a4

a5

b1

b2

b3

b4

b5

c′ (v)

:

3

3

5

6

0

4

1

1

0

1

Az 2. feladat megoldása. a) A megadott lineáris programban a változók nemnegativitása is szerepel a feltételek között, ezért érdemes azt (a második egyenlőtlenség (−1)-gyel szorzása után) max{cx : Ax ≤ b, x ≥ 0} alakúnak tekinteni, ahol     −1 0 2 −7 −1    −2 0 −5 −3   , b =  −6  , A=   0   7 5 0 −4  1 1 3 4 0 1 6 0 −1 . c=

Ekkor a duálist a tanult min{yb : yA ≥ c, y ≥ 0} alakban írhatjuk. Ezt részletezve: min{−y1 − 6y2 + y4 } ha −2y2 + 7y3 + y4 ≥ 1 2y1 + 5y3 + 3y4 ≥ 6 −7y1 − 5y2 + 4y4 ≥ 0 −y1 − 3y2 − 4y3 ≥ −1 y1 ≥ 0, y2 ≥ 0, y3 ≥ 0, y4 ≥ 0 (Megjegyezzük, hogy a primál feladatot felfoghatjuk max{cx : Ax ≤ b} alakúnak is és erre használhatjuk a duális eredeti definíció szerinti alakját, vagyis a min{yb : yA = c, y ≥ 0} alakot. Ekkor a változók nemnegativitását előíró négy egyenlőtlenség is az Ax ≤ b rendszer része, vagyis A-nak és b-nek 8 sora van. Ennek megfelelően a duális egy 8 változós lineáris program – amely azonban az előadáson tanultak szerint ekvivalens a fent kapottal.) b) A kapott duális feladatot megvizsgálva azonnal látszik, hogy annak az egyenlőtlenségrendszere azonos a primál feladatéval; valóban, a duális 1., 3. és 4. egyenlőtlenségét (−1)-gyel szorozva a primál megfelelő egyenlőtlenségét kapjuk, a 2. egyenlőtlenségek pedig eleve azonosak. Következésképp a primál és a duális megoldáshalmaza is azonos (eltekintve attól, hogy a primál esetében a változókat oszlopvektorban, a duális esetében sorvektorban tároltuk). A két feladat célfüggvényét összevetve az is látszik, hogy ezek egymás ellentettjei. Azonban könnyen látható (és az előadáson is szerepelt), hogy a −y1 − 6y2 + y4 célfüggvény minimalizálása és az y1 + 6y2 − y4 célfüggvény maximalizálása (ugyanazon a megoldáshalmazon) egymással ekvivalens feladatok: a két feladat optimumhelyei azonosak, az optimumértékek pedig egymás ellentettjei. A dualitástétel értelmében a primál feladat maximuma megegyezik a duális minimumával; ebből és a fentiekből következik, hogy primál maximuma sajátmagának az ellentettjével egyenlő. Következésképp a primál feladat maximumértéke 0. Persze a dualitástétel alkalmazásához még ellenőrizni kell, hogy a primál feladat rendszere valóban megoldható és a célfüggvénye felülről korlátos a megoldáshalmazán. A megoldhatóság könnyen látszik: például az x1 = x2 = x3 = 0 és x4 = 2 választással megoldást kapunk. Ebből persze a duális megoldhatósága is következik (hiszen a két megoldáshalmaz most azonos), így a tanult tétel értelmében a primál célfüggvénye felülről korlátos. Az 3. feladat megoldása. Jelölje a mátrix oszlopait sorban a, b, c és d. Az matroid megismeréséhez azt kell megvizsgálnunk, hogy x különböző értékeire mely oszlophalmazok lineárisan függetlenek. Mivel az oszlopok térvektorok (vagyis R3 -beliek), ezért a négy oszlop együtt nyilván lineárisan összefüggő. A négy darab háromelemű oszlophalmaz függetlenségének vizsgálata legegyszerűbben talán a megfelelő 3 × 3-as determinánsok vizsgálatával történhet. Például az {a, c, d} halmazra a számítás: 1 1 0 1 1 0 1 1 0 = 2(x − 4), 1 3 4 = 0 2 4 = 0 2 4 0 2 x 0 2 x 0 0 x−4

amiből látszik, hogy {a, c, d} csak az x = 4 esetben összefüggő, minden más x értékre független. A másik három esetben hasonló számítással azt kapjuk, hogy az {a, b, c} halmaz mindenképp független, az {a, b, d} és a {b, c, d} halmaz pedig az x = 2 esetben összefüggő, egyébként független. Az is látszik, hogy az x = 2 esetben az utóbbi két halmaz azért összefüggő, mert b párhuzamos d-vel. A fentiek alapján három esetet kell megkülönböztetnünk. Az x = 2 esetben b k d, de bármely, a b és d elemek közül legföljebb egyet tartalmazó három elemszámú halmaz független. Ezért a matroid grafikus, reprezentálható például egy olyan három élű úttal, amelynek az egyik élét megdupláztuk (és a két párhuzamos él felel meg b-nek és d-nek). Az x = 4 esetben az {a, c, d} halmaz összefüggő, de minden más, három elemszámú halmaz független (és így párhuzamos elemek sincsenek). Ezért a matroid megint grafikus, reprezentálható például azzal a négy csúcsú gráffal, amelyet egy háromszögből kapunk úgy, hogy egy negyedik élet „lelógatunk” róla (és ez az él felel meg b-nek).

Végül ha x 6= 2 és x 6= 4, akkor minden három elemű részhalmaz független, így a matroid U4,3 -mal izomorf. Ez is grafikus matroid, reprezentálja egy négy élű kör. Ezek szerint tehát x különböző értékeire háromféle nemizomorf matroidot kaphatunk. Az 4. feladat megoldása. Az M matroidban definíció szerint azok a részhalmazok függetlenek, amelyek az {a, b, c} és a {d, e} halmazból is legföljebb egy-egy elemet tartalmaznak. Az M ∨ M matroid függetlenjei tehát azok a részhalmazok, amelyek két ilyen halmaz uniójaként előállhatnak. Ez nyilván nem teljesül az {a, b, c} halmazra (hiszen a két egyesítendő részhalmaz mindegyike csak egyet tartalmazhat eközül a három elem közül). Ebből következően (mivel matroidban a függetlenek részhalmazai is függetlenek) a négyelemű részhalmazok közül sem függetlenek azok, amelyek {a, b, c}-t tartalmazzák (és pláne nem független az {a, b, c, d, e} alaphalmaz). Azonban könnyű végiggondolni, hogy az {a, b, c}-t nem tartalmazó négyeleműek már függetlenek: {a, b, d, e} = {a, d} ∪ {b, e}, {a, c, d, e} = {a, d} ∪ {c, e} és {b, c, d, e} = {b, d} ∪ {c, e} (mindhárom esetben az egyenlet jobb oldalán álló kételemű részhalmazok függetlenek M-ben). A fentiekből következik, hogy M ∨ M grafikus matroid: reprezentálja például az az öt csúcsú gráf, amelyet egy háromszögből kapunk úgy, hogy két élet „lelógatunk” róla (és ezek felelnek meg d-nek és e-nek). Az M ∨ U5,2 matroid függetlenjei definícó szerint azok a részhalmazok, amelyek M egy függetlenjéből legföljebb két további, tetszőleges elem hozzávételével megkaphatók. Az {a, b, c, d, e} alaphalmaz így továbbra sem független (hiszen két, legföljebb kételemű részhalmazt egyesítünk), azonban könnyen ellenőrizhető, hogy most már minden négyelemű részhalmaz független. Mivel M ∨U5,2 függetlenjeinek halmaza (definíció szerint) nyilván bővebb a fent vizsgált M ∨ M függetlenjeinek halmazánál, ezért ezt elég a két „hiányzó” négyelemű részhalmazra megvizsgálni: {a, b, c, d} = {a, d} ∪ {b, c} és {a, b, c, e} = {a, e} ∪ {b, c} (ahol a kéttagú uniókban a baloldali tag M-beli, a jobboldali U5,2 -beli független). Ezek szerint M ∨ U5,2 az U5,4 matroiddal izomorf és így grafikus is: reprezentálja egy 5 élű kör. Az 5. feladat megoldása. Tudjuk, hogy egy csúcshalmaz akkor és csak akkor független, ha a komplementere lefogó. Keressünk a gráfban (például mohón) egy nem bővíthető párosítást. A párosítás végpontjai által alkotott halmaz legyen L. Tudjuk, hogy L lefogó, a komplementere, L tehát független. Megmutatjuk, hogy L legalább feleakkora, mint a maximális független ponthalmaz (ezzel igazolva, hogy algoritmusunk approximáxiós faktora csakugyan 2, az eljárás polinomialitása nyilvánvaló). Mivel n − |L| = |L| ≤ 2ν(G) ≤ 2τ (G), tehát α(G) α(G) α(G) |L| ≥ n − 2τ (G) = α(G) − τ (G) ≥ + − τ (G) ≥ , 2 2 2 ≥ n3 egyenlőtlenséget és felhasználva az α(G) + τ (G) = n egyenlőséget, a (feladat szövegében adott) α(G) 2 n az ezekből adódó τ (G) ≤ 3 egyenlőtlenséget. A K2,5 teljes páros gráfon való alkalmazáshoz legyenek a csúcsok K2,5 egyik osztályában 1 és 2, a másik osztályában A, B, C, D, E. Egy nem bővíthető párosítás 2 élből fog állni, az egyik tartalmazza az 1-et (pl. 1A), a másik a 2-t (pl. 2B). Az algoritmus által kimenetként adott ponthalmaz tehát ez esetben a {C, D, E} halmaz lesz. Az 6. feladat megoldása. A tanult módon (eltolásokkal, törlésekkel és összefésülésekkel) elkészítjük a 1 ε = 24 -del ritkítva. Ez azt jelenti, hogy 24-nél kisebb számok részösszegek listáit, minden fázisban δ = 2n senkit nem tudnak képviselni, a 24 és 47 közti számok a náluk eggyel nagyobbat tudják képviselni, az ennél nagyobb számok tudnának két számot is képviselni, erre azonban nem fog sor kerülni, hiszen 49-nél nagyobb számokat nem veszünk fel a listákba. L0 = {0}, L′0 = {2}, L1 = {0, 2}, itt ritkítani nem lehet. L′1 = {6, 8}, L2 = {0, 2, 6, 8}, ritkítani nem lehet. L′2 = {7, 9, 13, 15}, L3 = {0, 2, 6, 7, 8, 9, 13, 15}, ritkítani nem lehet. L′3 = {14, 16, 20, 21, 22, 23, 27, 29}, L4 = {0, 2, 6, 7, 8, 9, 13, 14, 15, 16, 20, 21, 22, 23, 27, 29}, ritkítani továbbra sem lehet. L′4 = {28, 30, 34, 35, 36, 37, 41, 42, 43, 44, 48, 49}, hiszen a 49-nél nagyobb elemeket nem vesszük be a listába. L5 = {0, 2, 6, 7, 8, 9, 13, 14, 15, 16, 20, 21, 22, 23, 27, 28, 29, 30, 34, 35, 36, 37, 41, 42, 43, 44, 48, 49}, itt a ritkítás során töröljük a 28,30,35,37,42,44,49 elemeket, ezt követően tehát L5 = {0, 2, 6, 7, 8, 9, 13, 14, 15, 16, 20, 21, 22, 23, 27, 29, 34, 36, 41, 43, 48}.

L′5 = {44, 46}, hiszen a 49-nél nagyobb elemeket nem vesszük be a listába. L6 = {0, 2, 6, 7, 8, 9, 13, 14, 15, 16, 20, 21, 22, 23, 27, 29, 34, 36, 41, 43, 44, 46, 48}. Itt már nem muszáj ritkítani (ha mégis ritkítunk, akkor a 44-et kell törölni), az algoritmus kimenete az utolsó lista legnagyobb eleme, azaz 48.

Rendszeroptimalizálás Pótzárthelyi feladatok 2012. április 26. max{x1 + 6x2 + 4x3 + 2x4} ha x1 + 2x2 + 3x3 + 4x4 ≤ 3 2x2 − x4 = 6 x1 + 3x2 + 2x3 + 5x4 ≤ 8 3x2 − 2x4 ≥ −9

1. a) Írjuk fel a jobbra látható lineáris programozási feladat duálisát! (A felírás hasonló alakú legyen, mint a primál feladat felírása, vagyis ne mátrixos alakot használjunk.) b) Döntsük el, hogy a (primál) feladat célfüggvénye felülről korlátos-e a megoldáshalmazán!

2. Tekintsük a következő minimális költségű folyam feladatot: az alábbi ábrán látható gráfban keresünk az s-ből t-be menő, legalább 3 értékű folyamok között minimális költségűt, ha minden él kapacitása 2, az élekhez tartozó költségek pedig az alábbi táblázatban láthatók. Írjuk fel ezt a feladatot lineáris programként (vagyis adjunk meg egy olyan lineáris programozási feladatot, amelynek a megoldása ekvivalens a megadott minimális költségű folyam feladattal)!

A s

e1 e3 e5

e2 e4 e6

t

e

:

e1

e2

e3

e4

e5

e6

k(e)

:

3

3

1

1

5

1

B (A folyam feladatot tehát nem szükséges megoldani, a feladat csupán a lineáris programként való megfogalmazás.) 3. Hányféle nemizomorf matroidot reprezentálhat a valós test felett az alábbi mátrix az x különböző választásai mellett? Ahol a matroid grafikus, ott gráffal is adjuk meg!   1 0 1 0  1 2 3 4  0 1 3 x

4. Az ábrán látható gráf körmatroidja legyen M. Határozzuk meg az M ∨ M és az M ∨ U5,2 matroidösszegeket! Ahol az összeg grafikus, ott gráffal is adjuk meg! d

a b c

e

5. Hajtsuk végre és dokumentáljuk a Steiner-fa problémára tanult 2-approximációs algoritmust az alábbi bemenetre. A G gráf legyen teljes gráf az 1,3,5,7,9,11 csúcsokon, az (i, j) él súlya legyen i + j − 3, T pedig legyen az {5, 7, 9, 11} halmaz. 6. Bizonyítsuk be, hogy a P m||Cmax feladatra az LPT ütemezés approximációs faktora 1 . nem rosszabb, mint 23 − 2m A feladatok megoldásához segédeszköz nem használható. A rendelkezésre álló munkaidő 90 perc. Nem szükséges minden feladatot külön lapra írni, de kérjük, hogy a beadott dolgozat szétválasztható legyen 3 részre: az 1-es/2-es, a 3-as/4-es, illetve az 5-ös/6-os feladatpárokra.

Rendszeroptimalizálás Zárthelyi feladatok 2013. április 22. 1. Írjuk fel a jobbra látható lineáris egyenlőtlenségrendszert Ax ≤ b alakban, majd bizonyítsuk be a Farkas-lemma felhasználásával, hogy a rendszer nem megoldható! (Vagyis adjunk meg egy vektort és mutassuk meg róla, hogy ez a Farkas-lemma értelmében bizonyítja a rendszer megoldhatatlanságát!)

7x1 − 3x2 + 9x3 − 5x4 ≥ 1 x1 − 8x4 = 5 x1 − x2 + x3 − x4 ≤ 1 x1 + x3 − 3x4 ≤ 1

2. Tekintsük a következő kéttermékes folyamfeladatot: mae1 v ximalizálandó az összfolyamérték a jobbra látható ábra hás1 e2 lózatában, ha az első, illetve a második termékhez tartozó e3 e4 e5 t2 termelő és fogyasztó pontok s1 és t1 , illetve s2 és t2 , továbbá e7 az e1 , e5 és e6 élek kapacitása 2, a többi él kapacitása 1. Írjuk s2 e6 t fel ezt a feladatot lineáris programként (vagyis adjunk meg 1 egy olyan lineáris programozási feladatot, amelynek a megoldása ekvivalens a megadott kéttermékes folyam feladattal)! A keresett lineáris programot ne mátrixos alakban adjuk meg, hanem vezessünk be a feladat szempontjából releváns változókat és ezek segítségével írjuk fel. (A folyam feladatot tehát nem szükséges megoldani, a feladat csupán a lineáris programként való megfogalmazás.) 3. Koordinátázza az alábbi mátrix a valós számok teste fölött az Mx matroidot. Bizonyítsuk be, hogy Mx az x minden nemnegatív értéke esetén grafikus. Igaz-e ugyanez az állítás x negatív értékeire is?   1 0 1 2  0 −1 3 1  1 x 4 3 4. Az alábbi két gráf az {a, b, c, d, e} halmazon két grafikus matroidot definiál, azonban a második gráf két éléről „véletlenül” lemaradt a c, illetve az e betű. Eldönthető-e azért, hogy a két matroid összege grafikus-e? e

a b c

d d

b

a

5. Adjunk olyan 2-approximációs algoritmust egy összefüggő gráf maximális élszámú páros részgráfjának keresésére, amely páros gráf bemenetekre optimális megoldást ad. Az algoritmus működését szemléltessük is egy tetszőleges összefüggő, 8 csúcsú, 8 élű, nem páros, egyszerű gráfon. 6. Igaz-e, hogy a Steiner-fa probléma polinom időben megoldható, ha a Steiner-pontok halmaza legfeljebb 2 log n elemű, ahol n a gráf csúcsainak száma? A feladatok megoldásához segédeszköz nem használható. A rendelkezésre álló munkaidő 90 perc. Nem szükséges minden feladatot külön lapra írni, de kérjük, hogy a beadott dolgozat szétválasztható legyen 3 részre: az 1-es/2-es, a 3-as/4-es, illetve az 5-ös/6-os feladatpárokra.

A zárthelyi feladatok megoldása Az 1. feladat megoldása. A rendszer mátrixos alakja Ax ≤ b, ahol    −1 −7 3 −9 5    1 0 0 −8   5    0 0 8  és b =  A =  −1  −5  1  1 −1 1 −1  1 1 0 1 −3



  .  

A Farkas-lemma értelmében az Ax ≤ b megoldhatatlanságát egy olyan y = (y1 , y2 , y3 , y4, y5 ) sorvektor bizonyítja, amelyre yA = 0, y ≥ 0 és yb < 0. Ezt részletesen kiírva a következő feltételeket kapjuk: (1) −7y1 + y2 − y3 + y4 + y5 = 0 (2) 3y1 − y4 = 0 (3) −9y1 + y4 + y5 = 0 (4) 5y1 − 8(y2 − y3 ) − y4 − 3y5 = 0 (5) y1 ≥ 0, y2 ≥ 0, y3 ≥ 0, y4 ≥ 0, y5 ≥ 0 (6) −y1 + 5(y2 − y3 ) + y4 + y5 < 0 Legyen y1 = α valamilyen α ≥ 0 értékre. Ekkor (2)-ből y4 = 3α. Ezt felhasználva (3)-ból y5 = 6α. Ezekből és (1)-ből y2 −y3 = −2α. Ha viszont y1 , . . . , y5 értékeit úgy választjuk, hogy az eddig kapott feltételeknek (és y2 , y3 ≥ 0-nak) megfeleljenek, akkor ezekből már (4) és (6) automatikusan teljesül: erről egyszerű behelyettesítéssel meggyőződhetünk (utóbbi esetben (−2α) a kifejezés értéke). Így a rendszer megoldhatatlanságát bizonyítja a Farkas-lemma értelmében minden, a fenti feltételeknek megfelelő vektor, például y = (1, 0, 2, 3, 6). Az 2. feladat megoldása. A többtermékes folyamfeladat tanult definíciója szerint minden élhez 2 változót kell bevezetnünk: jelölje x1i az ei élen az 1-es termékből (s1 -ből t1 -be) menő folyam mennyiségét és hasonlóan x2i jelölje a 2-es termékből ei -n folyó mennyiséget. Ezek a változók természetesen mind nemnegatívak: xij ≥ 0 minden 1 ≤ i ≤ 2 és 1 ≤ j ≤ 7 esetén. Valójában a 14 változó közül a „folyam megmaradási” feltételek miatt 4 értéke garantáltan 0: x21 = x23 = x12 = x17 = 0 (hiszen például s1 -be nem lép be él, így az s1 -ből kimenő éleken a 2-es termékből nem mehet pozitív folyam). Ezzel az s1 és t2 csúcsokra vonatkozó megmaradási feltételek már teljesülnek is (hiszen s1 -nél az első termékre, t2 -nél a másodikra nincs ilyen feltétel). A többi csúcsra viszont fel kell írnunk a megmaradási feltételeket: v-nél x12 +x15 −x11 −x14 = 0 és x22 +x25 −x21 −x24 = 0, s2 -nél x16 + x14 − x13 = 0, továbbá t1 -nél x27 − x25 − x26 = 0. Végül minden élre fel kell írnunk a rá vonatkozó kapacitás feltételt: x11 + x21 ≤ 2, x12 + x22 ≤ 1, x13 + x23 ≤ 1, x14 + x24 ≤ 1, x15 + x25 ≤ 2, x16 + x26 ≤ 2, x17 + x27 ≤ 1. Ezzel a folyamértékekre vonatkozó összes feltételt felírtuk, már csak a célfüggvény van hátra: a két folyam nagyságát s1 -nél, illetve s2 -nél mérve, maximalizálandó az x11 + x13 + x24 + x26 − x23 kifejezés értéke. Az 3. feladat megoldása. Jelölje a mátrix oszlopait sorban a, b, c és d. Az Mx matroid megismeréséhez azt kell megvizsgálnunk, hogy (x különböző értékeire) mely oszlophalmazok lineárisan függetlenek. Mivel az oszlopok térvektorok, együttesen nyilván lineárisan összefüggők. Sőt, már az {a, c, d} halmaz is összefüggő – amiről legegyszerűbben az általuk alkotott 3×3-as mátrix determinánsának kiszámításával győződhetünk meg (ugyanis ez 0). Hasonlóan, az {a, b, c}, {a, b, d}, illetve {b, c, d} halmazoknak megfelelő determinánsokat kiszámítva sorban a −3x − 3, a −x − 1, illetve a −5x − 5 értékeket kapjuk. Így tehát az x = −1 értékre ezek mind összefüggőek, x 6= −1 esetén viszont egyikük sem. Következésképp x 6= −1 esetén (és így minden nemnegatív x-re) Mx grafikus: reprezentálja az a gráf, amelyben {a, c, d} háromszöget alkotnak és b erről „lelóg”. Az x = −1 esetben viszont Mx az U4,2 -vel izomorf, így nem grafikus (vagyis az állítás negatív x-ekre nem mindig igaz).

Az 4. feladat megoldása. Jelölje sorrendben M1 és M2 a két gráf körmatroidját. Az M1 ∨ M2 összegmatroid rangja biztosan 3 lesz: ekkora független halmazt nyilván kaphatunk egy M1 és M2 -beli uniójaként (például: {a, b, d} = {b} ∪ {a, d} vagy {a, c, d} = {c} ∪ {a, d}), de nagyobbat biztosan nem (mert M1 rangja 1, M2 -é 2). A feladat kérdésének megválaszolásához csak két esetet kell megvizsgálnunk: az elsőben e hurokél és c párhuzamos d-vel, a másodikban fordítva. Mindkét esetben elég megtalálnunk a bázisokat, vagyis a 3 elemű függetleneket. Az első esetben {e} összefüggő (vagyis e hurok), mert mindkét matroidban az. Maradnak tehát az {a, b, c, d} három elemű részhalmazai. Ezek közül {b, c, d} összefüggő: d M1 -ben hurok, ezért őt M2 -ből kellene kiválasztani és hasonló okokból b-t M1 -ből – de akkor c-t már egyikből sem választhatjuk ki. Viszont {a, b, c, d} többi három elemű részhalmaza már független M1 ∨M2 -ben: {a, b, d}-ről és {a, c, d}ről ezt már fentebb láttuk, továbbá {a, b, c} = {b}∪{a, c}. Mindez azt mutatja, hogy M1 ∨M2 grafikus: reprezentálja egy olyan gráf, amelyben {b, c, d} háromszöget alkot, a erről ”lelóg”, e pedig hurokél. A második esetben már a 2 elemű halmazok sem mind függetlenek: {b, c} és {d, e} is összefüggő, mert b és c M2 -ben hurkok és M1 -ben kört alkotnak, d és e esetében pedig fordítva. Így a bázisok csak olyan három elemű halmazok lehetnek, amelyek {b, c}-ből és {d, e}-ből egy-egy elemet, valamint még a-t tartalmazzák. Az ilyen halmazok viszont mind függetlenek is: {a, b, d}-ről és {a, c, d}-ről ezt már fentebb láttuk, továbbá {a, b, e} = {b} ∪ {a, e} és {a, c, e} = {c} ∪ {a, e}. Így M1 ∨ M2 ebben az esetben is grafikus: reprezentálja például egy olyan hatpontú gráf, mely a {b, c}, illetve {d, e} párhuzamos élpárok és az a él pontdiszjunkt uniója. Vagyis M1 ∨ M2 mindenképp grafikus. Az 5. feladat első megoldása. A gráf csúcsait sorban, egyesével két osztályba soroljuk az órán tanult algoritmus szerint, azaz egy újonnan érkező csúcsot abba az osztályba helyezünk, ahol kevesebb (nem több) szomszédja van. Láttuk, hogy ez az algoritmus 2-approximációs. Ha a csúcsokat olyan sorrendben vesszük, hogy az aktuálisan már elhelyezett csúcsok mindig összefüggő részgráfot alkossanak, akkor az egy osztályba kerülő csúcsok közt lesz (páros hosszú) út a gráfban, így semelyik kettő nem lehet szomszédos, ekkor ugyanis lenne a gráfban páratlan kör, ami páros gráfban lehetetlen. Ebben a sorrendben véve tehát a csúcsokat, minden él bekerül a páros részgráfba, így a kapott megoldás optimális lesz. Azt kell még belátnunk, hogy a kérdéses típusú sorrend létezik és előállítható polinom időben: például szélességi vagy mélységi kereséssel is ilyen sorrendhez jutunk. Az 5. feladat második megoldása. Egyszerűbb megoldás, ha először ellenőrizzük, hogy a kapott gráf páros-e (szélességi kereséssel, polinom időben). Ha igen, akkor a kimenet maga a gráf lesz, ellenkező esetben az órán tanult algoritmusok valamelyikét (pl. az első megoldásban leírtat) hajtjuk végre. Páros gráfokra optimális, más gráfokra 2-közelítő algoritmust kapunk, ami nyilván polinom időben fut. Az 6. feladat megoldása. Legyen a Steiner-pontok halmaza S, a terminálok halmaza T , az optimális Steiner-fa F . F tartalmazza T minden csúcsát és S csúcsainak egy R részhalmazát (ami lehet üres is). A T ∪ R halmazok által feszített részgráfokon minimális feszítőfát keresve tehát megtaláljuk az F fát vagy egy másik, vele azonos súlyú Steiner-fát. A szóbajövő R halmazok száma 2|S| = n2 , ami a bemenet méretében polinomiális, az egyes esetek lépésszáma pedig (pl. a Kruskal-algoritmust használva) szintén polinomális. A kapott fák közül a minimális összsúlyút véve tehát polinomiális algoritmust kapunk a legkisebb költségű Steiner-fa meghatározására.

Rendszeroptimalizálás Pótzárthelyi feladatok 2013. május 2. 1. a) Írjuk fel az alábbi lineáris programozási feladat duálisát a t valós paraméter minden értékére. (A felírás hasonló alakú legyen, mint a primál feladat felírása, vagyis ne mátrixos alakot használjunk.) b) A t paraméter milyen értékeire lesz a (primál) feladat célfüggvénye felülről korlátos a megoldáshalmazán? max{x4} ha 3x1 + 2x2 + 4x3 + 5x4 ≤ 4 2x1 + x2 + 3x3 + 4x4 ≥ 1 x3 + 2x4 ≤ 1 x2 − 2x3 + t · x4 ≥ −2 2. Az alábbi állításokról döntsük el, hogy igazak-e minden A totálisan unimoduláris mátrixra! a) Ha A-hoz hozzáveszünk egy csupa 1-eseket tartalmazó oszlopot, a kapott mátrix is totálisan unimoduláris lesz. b) Ha A minden (+1)-es elemét kicseréljük (−1)-esre és minden (−1)-es elemét kicseréljük (+1)-esre, a kapott mátrix is totálisan unimoduláris lesz. c) Ha A valamelyik nemnulla elemét kicseréljük 0-ra, a kapott mátrix is totálisan unimoduláris lesz. 3. Mely x, y valós értékekre lesz az alábbi mátrix oszlopvektorai által a valós test fölött koordinátázott matroid grafikus? Ahol grafikus lesz, ott adjuk is meg egy-egy gráfreprezentációját!   1 0 1 2  0 1 2 1  0 0 x y 4. Határozzuk meg az alábbi gráf által reprezentált matroid önmagával való összegét. Ha az összeg grafikus, adjuk meg gráffal; ha nem, bizonyítsuk ezt be. a

c d e

b

5. Mutassuk meg, hogy a metrikus utazóügynök probléma NP-nehéz. 6. Hajtsuk végre és dokumentáljuk a részösszeg problémára tanult (1 + ε)-approximációs algoritmust a 2, 5, 6, 7, 10, t = 20 bemenetre ε = 1 mellett. A feladatok megoldásához segédeszköz nem használható. A rendelkezésre álló munkaidő 90 perc. Nem szükséges minden feladatot külön lapra írni, de kérjük, hogy a beadott dolgozat szétválasztható legyen 3 részre: az 1-es/2-es, a 3-as/4-es, illetve az 5-ös/6-os feladatpárokra.

Rendszeroptimalizálás Zárthelyi feladatok 2014. április 14. 1. A G(F, L; E) teljes páros gráf két színosztálya legyen F = {a1 , a2, a3 , a4, a5 } és L = {b1, b2, b3, b4, b5}. Az ai -t a bj -vel összekötő él súlya legyen a balra látható mátrix i-edik sorának és j-edik oszlopának kereszteződésében álló elem (minden 1 ≤ i, j ≤ 5 esetén). A maximális összsúlyú teljes párosítást kereső Egerváry-algoritmust valaki már elkezdte futtatni G-re és ott tart, hogy az aktuális M párosítás az {a1 , b1}, {a2, b2} és {a3 , b3} élekből áll, az aktuális c címkézés pedig a jobb oldali táblázatban látható. Fejezzük be az algoritmus futtatását és adjuk meg az eredményként kapott maximális összsúlyú teljes párosítást!   2 1 2 1 1  6 5 7 3 5    v : a1 a2 a3 a4 a5 b1 b2 b3 b4 b5  2 2 6 1 3    c(v) : 1 5 4 7 3 1 0 2 0 1  4 4 9 3 5  3 3 4 2 2 (A megoldásban ne csak az algoritmus futásának az eredményét adjuk meg, hanem dokumentáljuk is a lépéseket – vagyis adjunk meg minden, a futás közben keletkező adatot.) max{x1 + x2 + 3x3 − 2x4} 2. a) Írjuk fel a jobbra látható lineáris programozási ha feladat duálisát! (A felírás hasonló alakú legyen, mint x1 + 3x2 + 2x3 − 2x4 = 5 a primál feladat felírása, vagyis ne mátrixos alakot 2x1 − 4x2 − x3 + x4 ≥ 3 használjunk.) x1 + 5x2 − x4 ≤ 6 b) Döntsük el, hogy a (primál) feladat célfüggvénye 2x1 + x2 + x3 − x4 ≤ 10 felülről korlátos-e a megoldáshalmazán! x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0 3. Az alábbi mátrix jobb alsó sarkában álló 4. A bal oldali ábrán látható gráf körmatelem olyan kétjegyű szám, melynek másoroidja legyen A, a jobb oldalin láthatóé B. dik jegye „sajnos” elmosódott. Meg lehet-e Grafikusak-e az A∨A, illetve az A∨B matazért határozni, hogy milyen matroidot koroidok? a a ordinátáz ez a mátrix a valós test felett? d b   c e 1 0 0 2  0 1 0 d b 5  e c 1 1 1 1 5. Adjunk meg olyan 10 csúcsú, 10 élű egyszerű, összefüggő gráfot, melyre a minimális lefogó ponthalmaz problémára tanult 2-approximációs algoritmusok soha nem adnak optimális eredményt (és igazoljuk, hogy a gráf csakugyan rendelkezik a kívánt tulajdonsággal). 6. Egy négyzet egyik átlóját osszuk három pont segítségével négy egyenlő részre. Legyenek a G teljes gráf csúcsai a négyzet csúcsai és az átlón lévő három pont (G-nek tehát összesen hét csúcsa van), minden él súlya legyen azonos végpontjainak távolságával. Hajtsuk végre és dokumentáljuk a G gráfra az utazóügynök probléma közelítésére szolgáló Christofidesalgoritmust. A feladatok megoldásához segédeszköz nem használható. A rendelkezésre álló munkaidő 90 perc. Nem szükséges minden feladatot külön lapra írni, de kérjük, hogy a beadott dolgozat szétválasztható legyen 3 részre: az 1-es/2-es, a 3-as/4-es, illetve az 5-ös/6-os feladatpárokra.

A zárthelyi feladatok megoldása Az 1. feladat megoldása. A megadott címkézéshez tartozó „piros élek” meghatározásával kezdjük – vagyis azokat az e = {a, b} éleket keressük, amelyekre w(e) = c(a) + c(b) (ahol w(e) az e él súlyát jelöli). Ezek a következők: {a1 , b1 }, {a1 , b2 }, {a1 , b4 }, {a2 , b1 }, {a2 , b2 }, {a2 , b3 }, {a3 , b3 }, {a4 , b3 } és {a5 , b2 }; lásd az alábbi, bal oldali ábrát. (Látszik, hogy a megadott M párosítás élei – az ábrán vastag vonallal – is pirosak; ha ez nem így volna, az azt jelentené, hogy az algoritmus korábbi futása hibás volt.) Most M-ből kiindulva a maximális párosítás keresésére szolgáló javító utas algoritmust futtatjuk a piros élek alkotta részgráfban. A párosítatlan F -beli pontok: a4 és a5 . Látható, hogy a4 -ből nem vezet javító út párosítatlan L-beli pontba (vagyis b4 -be vagy b5 -be), mert a4 -ből piros élen egyedül b3 -ba lehet lépni, ennek az M szerinti párjában, a3 -ban pedig elakadunk. Viszont a5 -ből indítva a javítóút keresést sikerrel járunk: az a5 , b2 , a2 , b1 , a1 , b4 sorrendben bejárva a csúcsokat javítóutat kapunk; ementén javítva a következő párosítást kapjuk: {a5 , b2 }, {a2 , b1 }, {a1 , b4 }, {a3 , b3 } (lásd a jobb oldali ábrát). b1

b2

b3

b4

b5

b1

b2

b3

b4

b5

a1

a2

a3

a4

a5

a1

a2

a3

a4

a5

A most kapott M ′ párosítás maximális a (jelenlegi) piros részgráfban, mert b5 -re nem illeszkedik piros él, így nyilván nincs öt élű párosítás. Ezért áttérünk a következő c′ címkézés meghatározására. A párosítatlan F -beli, illetve L-beli csúcsok halmaza F1 = {a4 } és L1 = {b5 }. Az F1 -ből alternáló úton elérhető L-beliek halmaza L2 = {b3 }, mert a4 -ből továbbra is csak b3 -ba vezet piros él, ahonnan a3 -ba lépve elakadunk. Az L2 -beliek M ′ szerinti párjainak halmaza tehát F2 = {a3 }. Így a maradék F -beliek, illetve L-beliek halmaza F3 = {a1 , a2 , a5 }, illetve L3 = {b1 , b2 , b4 }. Az algoritmus működési szabálya szerint az F1 ∪ F2 = {a3 , a4 } és az L1 ∪ L3 = {b1 , b2 , b4 , b5 } halmazok halmazok közti élek mindegyikére ki kell számítani a c(a) + c(b) − w(e) „fölösleget”, majd ezek minimumát kell venni. A feladat adatait felhasználva az a3 -ból induló (és L1 ∪ L3 -ba menő) élek fölöslegei rendre 3, 2, 3 és 2, az a4 -ből induló élek fölöslegei pedig 4, 3, 4 és 3. Ezeknek a minimuma pedig δ = 2. Ezek után a következő c′ címkézés meghatározásához F1 ∪F2 elemein δ-val csökkenteni, L2 elemein pedig δ-val növelni kell a jelenlegi címkézést. Így c′ a következő: v

: a1 a2 a3 a4 a5 b1 b2 b3 b4 b5

c′ (v) : 1

5

2

5

3

1 0 4 0 1

Ezzel az algoritmus teljes ciklusát végrehajtottuk, ismét a (most már c′ -höz tartozó) piros élek meghatározásával folytatjuk. A fenti ábrákon látható piros részgráfhoz képest három változás történik: {a2 , b3 } megszűnik pirosnak lenni, viszont {a3 , b2 } és {a3 , b5 } új piros élek (lásd az alábbi, bal oldali ábrát). (Ezek a változások egyrészt c′ -ből és a megadott élsúlyokból közvetlenül is kiolvashatók, de a fentiekből is következik: {a2 , b3 } volt az egyetlen F3 és L2 közötti él, a δ meghatározásakor pedig a minimum az {a3 , b2 } és {a3 , b5 } éleken vétetett föl.) Az új piros részgráfban könnyen találunk az M ′ -re nézve javító utat: a4 , b3 , a3 , b5 . Ementén javítva M ′ -t pedig már teljes párosítást kapunk: {a4 , b3 }, {a3 , b5 }, {a1 , b4 }, {a2 , b1 } és {a5 , b2 } (lásd a jobb oldali ábrát). Így ezzel (illetve a fenti c′ címkézéssel) áll meg az algoritmus futása. b1

b2

b3

b4

b5

b1

b2

b3

b4

b5

a1

a2

a3

a4

a5

a1

a2

a3

a4

a5

A 2. feladat megoldása. a) A megadott lineáris programban a változók nemnegativitása is szerepel a feltételek között, ezért érdemes azt max{cx : Ax ≤ b, x ≥ 0} alakúnak tekinteni, ahol     5 1 3 2 −2  −5   −1 −3 −2 2       −3  ,   −2 4 1 −1 , b = A=       6  1 5 0 −1  10 2 1 1 −1 1 1 3 −2 . c= Amint látható, a feltételek között szereplő egyenletet helyettesítettük az x1 +3x2 +2x3 −2x4 ≤ 5 és a −x1 −3x2 −2x3 + 2x4 ≤ −5 egyenlőtlenségekkel, illetve a következő egyenlőtlenséget is megszoroztuk (−1)-gyel. Most a duálist a tanult min{yb : yA ≥ c, y ≥ 0} alakban írhatjuk. Ezt részletezve: min{5y1 − 5y2 − 3y3 + 6y4 + 10y5 } ha y1 − y2 − 2y3 + y4 + 2y5 ≥ 1 3y1 − 3y2 + 4y3 + 5y4 + y5 ≥ 1 2y1 − 2y2 + y3 + y5 ≥ 3 −2y1 + 2y2 − y3 − y4 − y5 ≥ −2 y1 ≥ 0, y2 ≥ 0, y3 ≥ 0, y4 ≥ 0, y5 ≥ 0 (Megjegyezzük, hogy a primál feladatot felfoghatjuk max{cx : Ax ≤ b} alakúnak is és erre használhatjuk a duális eredeti definíció szerinti alakját, vagyis a min{yb : yA = c, y ≥ 0} alakot. Ekkor a változók nemnegativitását előíró négy egyenlőtlenség is az Ax ≤ b rendszer része, vagyis A-nak és b-nek 9 sora van. Ennek megfelelően a duális egy 9 változós lineáris program – amely azonban az előadáson tanultak szerint ekvivalens a fent kapottal.) b) A primál feladat rendszere megoldható, például az x1 = 5, x2 = x3 = x4 = 0 választással. Ha a célfüggvénye felülről korlátos volna a megoldáshalmazán, akkor a dualitástétel szerint a duális feladat egyenlőtlenségrendszere is megoldható volna . Ez azonban jól láthatóan nem igaz: az utolsó egyenlőtlenség (−1)-gyel szorzás után 2y1 − 2y2 + y3 + y4 + y5 ≤ 2, ami nyilván ellentmond a 2y1 − 2y2 + y3 + y5 ≥ 3 és az y4 ≥ 0 feltételeknek. Így a primál célfüggvénye nem felülről korlátos a megoldáshalmazán. A 3. feladat megoldása. Jelölje a mátrix oszlopait sorban a, b, c és d. Az ezek által koordinátázott M matroid rangja nyilván legföljebb 3 (hiszen négy R3 -beli vektor nem lehet lineárisan független). A négy lehetséges oszlophármas lineáris függetlenségét legegyszerűebben a megfelelő 3 × 3-as determinánsok kiszámításával lehet eldönteni. Ha a mátrix jobb alsó sarkában álló elemet x-szel jelöljük, akkor azt kapjuk, hogy az {a, b, c}, {a, b, d}, {a, c, d}, illetve {b, c, d} oszlopok által alkotott determinánsok értéke rendre 1, x − 7, (−5), illetve 2. Mivel x − 7 = 0 lehetetlen (hiszen x ≥ 10), ezért egyik determináns értéke sem 0, így bármely három oszlop lineárisan független. Következésképp M az elmosódott jegy értékétől függetlenül az U4,3 uniform matroiddal izomorf. A 4. feladat megoldása. Az A matroidban definíció szerint azok a részhalmazok függetlenek, amelyek az {a, b, c} halmazból legföljebb egy elemet tartalmaznak és emellett tartalmazhatják még d-t. Az A ∨ A függetlenjei tehát azok a részhalmazok, amelyek két ilyen halmaz uniójaként előállhatnak. Így az e elem A ∨ A-ban is hurok (vagyis az egyelemű {e} részhalmaz összefüggő) és összefüggő {a, b, c} is. Függetlenek viszont az {a, b, d}, {a, c, d} és a {b, c, d} részhalmazok. Következésképp A ∨ A grafikus, reprezentálja például az alábbi gráf.

b d

a c

e

Hasonlóan az A-hoz, B függetlenjei azok a részhalmazok, amelyek az {a, d, e} halmazból legföljebb egy elemet tartalmaznak és emellett tartalmazhatják még b-t. Az A∨B meghatározásához tehát ezeknek és az A függetlenjeinek az unióját kell képezni. Rögtön látszik, hogy {a, c, e} összefüggő lesz A ∨ B-ben, mert a, c és e közül bárhogyan kettőt választva A-ban és B-ben is összefüggő halmazt kapunk. Független viszont mind a három olyan 4 elemű részhalmaz, amely {a, c, e}-t nem tartalmazza: {a, b, c, d} = {c, d}∪{a, b}, {a, b, d, e} = {a, d}∪{b, e} és {b, c, d, e} = {c, d}∪{b, e} (ahol mindhárom esetben az unióban balra egy A-beli, jobbra egy B-beli függetlent írtunk). Következésképp A ∨ B is grafikus, reprezentálja például az alábbi gráf.

e b

a

d

c Az 5. feladat megoldása. Mivel mindkét tanult algoritmus egy (nem bővíthető) párosítás végpontjait adja kimenetként, a kimenet mindig páros számú csúcsból áll. Ha az optimum értéke páratlan, akkor tehát egyik algoritmus sem adhatja ezt. Olyan 10 csúcsú, 10 élű egyszerű, összefüggő G gráfot, melyre τ (G) = 3 nem nehéz adni: legyen például G egy háromszög, melynek A, B, C csúcsaihoz rendre 3,2,2 további csúcs csatlakozik egy-egy éllel. Könnyen látható, hogy ekkor A, B, C lefogó ponthalmaz és hogy 2 elemű lefogó ponthalmaz nincs G-ben. A 6. feladat megoldása. Legyenek a négyzet csúcsai A, B, C, D, az AC átlón lévő pontok (A-tól vett távolság szerint növő sorrendben) E, F, G. Az algoritmus először minimális összköltségű feszítőfát keres (például) Kruskal algoritmusával, azaz kiválasztja először az AE, EF, F G, GC éleket (valamilyen sorrendben), majd a BF, DF éleket (szintén tetszőleges sorrendben), mivel ezek a legrövidebbek azok közül, amik a már meglévőkkel együtt nem alkotnak kört. Következő lépésben az így kapott feszítőfa páratlan fokú csúcsai által feszített részgráfban kell minimális összsúlyú párosítást találnunk. A páratlan fokú csúcsok A, B, C, D, a minimális összsúlyú teljes párosítás tehát az AB, CD vagy pedig az AD, BC élekből áll. (Álljon mondjuk az AD, BC élekből). A feszítőfa és a párosítás éleinek uniójaként kapott részgráf egy Euler-körsétájának megkeresése, majd a tanult módszer szerint Hamilton-körré való levágása van hátra. Az Euler-körséta lehet pl. A, D, F, B, C, G, F, E, A, ekkor az első és egyetlen levágás a G − F − E út GE éllel való helyettesítése lesz. A kapott Hamilton-kör ekkor tehát A, D, F, B, C, G, E, A.

Rendszeroptimalizálás Zárthelyi feladatok 2014. április 30. 1. Mutassuk meg a Farkas-lemma segítségével, hogy az alábbi lineáris egyenletrendszernek nincs olyan megoldása, amelyben mind az öt változó értéke nemnegatív. (Vagyis adjunk meg egy olyan vektort, amely a Farkas-lemma értelmében bizonyítja a rendszer nemnegatív számokkal való megoldhatatlanságát.) 7x1 + 2x3 − 21x4 = 6 7x2 + x3 − 14x5 = 1 3x1 − 5x2 − 9x4 + 10x5 = 2 2. Legyenek adottak a számegyenesen az I1 = [1; 2], I2 = [1; 3], I3 = [1; 4], I4 = [1; 5], I5 = [2; 4], I6 = [2; 5] és I7 = [3; 5] zárt intervallumok. Adjuk meg ennek az intervallumrendszernek egy olyan színezését 2 színnel, amely megfelel az intervallumrendszerek egyenletes színezéséről tanult tétel feltételeinek (és mutassuk meg, hogy a megadott színezés valóban megfelel a feltételeknek). 3. Koordinátázza az alábbi mátrix a valós számok teste fölött az Mp,q matroidot. Mely p, q értékekre lesz ez a matroid grafikus? A grafikus esetekben adjuk is meg a gráfreprezentációt!   1 1 2 3  0 −1 p −1  0 2 q 2 4. A bal oldali ábrán látható gráf körmatroidja legyen A, a jobb oldalin láthatóé B. Grafikusak-e az A ∨ A, illetve az A ∨ B matroidok? a b c d

e

a b c d e

5. Tekintsük az {a,b,c,d,e,g,h,i,j,l,m,n,o,r,s,t,v,z} betűhalmazt, és az elemeiből képzett alábbi szavakat, mint részhalmazokat (a szavak utáni zárójelben lévő szám jelenti az adott halmaz költségét): zach (3), evan (4), josh (4), gavin (5), monica (5), thomas (5), jared (6), dinesh (6), erlich (7), bighead (8). Hajtsuk végre ezen adatokkal az alaphalmaz részhalmazokkal történő lefedésére szolgáló, előadáson tanult közelítő algoritmust. 6. Egy 2n csúcsú élsúlyozott teljes gráfban minden élsúly 1 vagy 2 és minden csúcsra legfeljebb n − 1 darab 2 súlyú él illeszkedik. Adjunk polinomiális algoritmust, mely talál egy legfeljebb 3n súlyú kört a gráfban. A feladatok megoldásához segédeszköz nem használható. A rendelkezésre álló munkaidő 90 perc. Nem szükséges minden feladatot külön lapra írni, de kérjük, hogy a beadott dolgozat szétválasztható legyen 3 részre: az 1-es/2-es, a 3-as/4-es, illetve az 5-ös/6-os feladatpárokra.

H3 6RT6[È0X H-ÊKU 46-;Xk\ù:]90=G_ LZ=96^XN90= _ KU90 T=G Z: Pp

Recommend Documents