Alapadatok
Év, oldalszám:2003, 17 oldal
Nyelv:magyar
Letöltések száma:828
Feltöltve:2005. április 11.
Méret:101 KB
Intézmény:
-
Megjegyzés:
Csatolmány:-
Letöltés PDF-ben:Kérlek jelentkezz be!
Értékelések
Nincs még értékelés. Legyél Te az első!Legnépszerűbb doksik ebben a kategóriában
Tartalmi kivonat
"! $# &%"!()* +$(,- "! .0/1235427698:<;>="?A@B:<;C&D*2AE6>FHGI2J;CHK 86ML"GNCO:<;QPG>R>8HGNCHSTRM=F ;U@9FHG78HVT@9CHECHEVWC8 F XRM= [Y Z]H^` Haab`HcaHd5[^JbJdeM HfNbJg*H^JhWe"af> HdHcji"g>HckHZ"lWccH^HZ]H^`Hmon lWh H^JpTHbrqHH^n lWhs ^`H^JcHlWZ"tdc u Hpve"^rwWe"c&gNZ"bJpvm^JeIx&pvy zgNZ"e"f{^Je"hWe"hHw gNZ"e"fN|aaTqH H^r}>lWZM}< HdHc5jpve"hW~"fs }>~"gN~"e"ZgNZ"cgN~"hWe"gNe"c Y 1CHKJ;j1H6<4@BRGI@B:G n lWh H^JpTo e"hHwWe"d e"hHwOH^JpTHZ&IqWe"c }>lWfNlWcUH^JpTHZM IuHpve"^rw ae"d~"f}>e"^Jpve"ZqWeUqHHd e"hHw ⊕sH^Ne"^JVW^r}]pk|oqWe"^Je}NWgNgNZ"eMHz
HgM0HZH^` Haab}>t^`NzlWdg> HhWlWccH^7 bApvbJdze"d x, y ∈ V sBfNeH x ⊕ y = y ⊕ x cHlWpvpkto}<}>brq br}< Hg<Iu bJbATpvbJdze"d x, y, z ∈ V sBfNeH x ⊕ (y ⊕ z) = (x ⊕ y) ⊕ z HgNgNZ"l i"b`}>brq br}< Hg<Iu bJbJbA&qHHdlW^rw Hd θ ∈ V uHpve"^rw fNe x ⊕ θ = x pvbJdze"d x ∈ V sBfNeHZWgNgNZ"eMHz HgNf> d~"ZqWejqHHd V sBae"dde"to}>f> H^JbJgQe"^Je"pIu brqOpvbJdze"d x ∈ V sBe"ZqHHdlW^rw Hd −x ∈ V ulWhHw x ⊕ (−x) = θ pvbJdze"d sBae"^Jbe"^Je"pvde"cvqHHdHzzbr}>rqTbJd qWe"fNZ"eI V f}>e"^Jpve"ZqWeqHHdpv~"he"hHwpk|oqWe"^Je} u[Hpve"^rwWe}gNcH^` HfNf>H^0qHH^JygNZ"lWfNZM HgNdHc rq tdc~"gHpve"^rwpvbJdze"d (α,
x) m HfNlWZHu&HlW^ α ∈ R e"hHwqHH^JyWggNZM Hp~"g u{e"hHw α ⊗ xsBe"^Ne"^JW^r} V sBae"^Jb{qWe"c }>lWf}TfNe"dze"^HZ x qWe"c }>lWfvgNcH^` HfNgNZ"lWfNls x ∈ V g> }I~"g[Hpve"^rw de"cHZH^` Haab}>t^`NzlWdg> Hh HbqHHddHc bJdze"d α, β ∈ R ~"g x, y ∈ V sBfNeHu α ⊗ (x ⊕ y) = (α ⊗ x) ⊕ (α ⊗ y) u a (α + β) ⊗ x = (α ⊗ x) ⊕ (β ⊗ x) u i (αβ) ⊗ x = α ⊗ (β ⊗ x) u z 1 ⊗ x = x ~"^Jz HcTqHH^JyWgqWe"c }>lWf}>e"fNe"cfNeH ¡ 0Y¢qHH^JyWg gNZM Hp nsBe"gNe"ck}>e"fNe nsBzbJpve"dZ"bJyWg*cHl lWfNzbJd }<}>~"f<Iu jHZ]WgNgNZ"eMHz Hg} ~"ggNcH^` HfNf>H^[qHH^JygNZ"lWfNZM Hg}cHlWpvmlWde"dgNe"dcH~"d }ze£db` H^
Ntc¤~"g$i"gNtm sBayW^ H^J^JykgNZM Hp nsBe"g¦HZUWgNgNZ"eMHz Hg[de"to}>f> H^JbJgQe"^Je"pveHu ¡ "e hHwWe"d F HZ [a, b] bJd }>e"fqHH^J^JtpvlWdk~"f}>e"^Jpve"Z"e}N}qHH^JyWg*n hWhHqW~"d wWe"c5H^JpTHZMo Y[Z[WgNgNZ"eMHz Hg}]~"gQgNcH^` HfNf>H^qHH^JygNZ"lWfNZM Hg}Q~"f}>e"^Jpve"Z"Z"cvcHqWe}>cHe"ZvcH~"m s me"d pvbJdze"d f, g ∈ F u α ∈ R ~"g x ∈ [a, b]sBfNej^Je"hHwWe"d (f ⊕ g)(x) = f (x) + g(x), (α ⊗ f )(x) = αf (x). Y[ZWgNgNZ"eMHz HgTde"to}>f> H^JbJg5e"^JpveOHZHZ"lWdlWg>Hd¤dt^J^`n hWhHqW~"d wW¦Wdd w |¤ae"^` }>db7u lWhHw F HZUJhHwze£db` H^r}]pk|oqWe"^Je}>e"ccHe"^qHH^JyWgQqWe"c }>lWf}>e"fNe} H^JcHlH}M Y }>lqH
Haab`HcaHd i"g>Hcde"p pvbJdzbJhqHH^JyWgTgNZM Hp nsBe"gNe"c¤}>e"fN~qWe"^[n lWhW^`H^JcHls Z"tdc~"g5de"p lWcHlWZOpTNz n ~"^JfNe"~"f}>~"g}Mu HZOe"hHw gNZ"e"fN|gN~"hcHe"zoqW~"~"f}qWe"c }>lWfNlWc WgNgNZ"eMHz Hg> Hf>5~"gQgNcH^` HfNf>H^ qHH^JykgNZ"lWfNZM Hg> Hf>5kHhHwWlWpT Hd wWlWg"uqHH^JyWggNZM HpvlWcvcHs fN~"ae"d pve"hWgNZ"lWcHlH}N } gNZ"bJpkayW^JtpvlH}jbJ^J^Je}NqWeTHZTe"hHw pT Hgpve"^J^J~&Jf> Hg}HgNZ"d H^ Ntc Y qWe"c }>lWfNlWc}UqHHg}<HhOae}>|oqWe"^7u-de"to}>f> H^JbJg e"^Je"pve}Mudt^J^ s9qWe"c }>lWf} os9qHH^n lWhMNtc Ne"^JW^Jdb7 e"hHwWe"d V e"hHwqWe"c }>lWf}>~"f"u v , . , v ∈ V ~"g α , ,
α ∈ R TY[Z α v + WgNgNZ"e"hWe}Q G = {v , 1. , v }n qWe"c }>lWfNfNe"dz1gNZ"e"f α ,n , α gNcH^` HfN1lWc1cH^ .cH~"m+ α n vn Z"e}N} K 2AE6>FHGI2J;Q4 RSvL"2AEF 27 "FH1EC 4 rqMNntc ¦eqWe"Z"Z"cv G qW1e"c }>lWfNfNe"ndzgNZ"e"f K 2AE6>F GI2J;L G>4WFHEC 4 ~"g Ne"^JW^ Nc5^JbJd (G)s9qWe"^ G qWe"c }>lWf>HbJdHcvWgNgNZ"e"g0^Je"e}>gN~"hWe"g]^JbJdeM HfNbJg cHlWpkabJd Hi"bJy > }M ¦Wdd wWe"d¤^` }>}>yulWhHw^JbJd pTHh bJgk^JbJdeM HfNbJg}>~"fH^r}>~"f< V sBae"d$ze£db` H^r}5pk|oqWe"^Je}>e"ccHe"^¦~"g&de"to}>f> H^JbJgk(G) e"^Je"pvpve"^7Y G = {v , . , v } 1 n qWe"c }>lWfNfNe"dzgNZ"e"f} K
2AE6>FHGI2J;MCH E W886@KJ6EE6<4 deqWe"Z"Z"c u α1 v1 + . + αn vn = 0 =⇒ α1 = = αn = 0 ¦Wdd wWe"dae"^` }>}>yu lWhHwU ^JbJdeM HfNbJgn hWhWe}>^Je"dgN~"h0n e"d }>b ze£dJi"bJy > MqHH^We"c q brqHH^Je"dg HZjH^` HaabcH~}[ze£dJi"bJy ¡ bJdze"d v ∈ ^JbJd (G) e"hHwW~"f}>e"^Jpk|e"d H^J^Jr}>}>yve"^ G qWe"c }>lWf>HbJdHc^JbJdeM HfNbJg cHlWpkabJd Hi"bJy >HcH~"d }M G e"hHwWe}>^Je"djqWe"c }>lWf> gNe"p n eBNe"Z"e} 0cb}>WaabJe"c[^JbJdeM HfNbJgcHlWpkabJd Hi"bJy >HcH~"d }M Yze£dJi"bJy&d~" Hd we"hHw gNZ"e"fN|cHqWe}>cHe"Z"pv~"d wWeH ¡ bJdeM HfNbJg>Hdn hWhWe}>^Je"d
fNe"dzgNZ"e"fde"p }<Hf}<H^JpTHZ"}jHZ"lWdlWgjqWe"c }>lWfNlWc}~"g 5dt^J^qWe"c }>lWf}[gNe"p 0Y[Z e"hHwWe}>^Je"dde"pvZ"~"fNy5qWe"c }>lWf}]}<Hf}<H^JpTHZ"yqWe"c }>lWfNfNe"dzgNZ"e"f¦^JbJdeM HfNbJg>Hdvn hs hWe}>^Je"d Jb deM HfNbJg>HdOn hWhWe}>^Je"dOqWe"c }>lWfNfNe"dzgNZ"e"f pvbJdze"dfN~"gNZ"fNe"dzgNZ"e"fNekbJg0^JbJdeM HfNbJg>Hd n hWhWe}>^Je"d hHw G qWe"c }>lWfNfNe"dzgNZ"e"f}O V qWe"c }>lWf}>~"f 86E6GNFH@BRGIG>6E3 ;>= 6G>:E6<4 rqMNtc u ^JbJd hHw qWe"c }>lWf}>e"fNe} 3H2AST6E ="27;EC 4 deqWe"Z"dc u{qHHd qWe"c }>lWf} V }<Hf=}<H^JpTHZ"(G)
yhWe"de"f> }>lWfNfNe"dzgNZ"e"fNeHuHzne a HfNpve"^rw nsBd~"^WcHeqWe"gNe"aaqWe"c }>lWf}}<Hnf}<H^JpTHZ"y qWe"c }>lWfNfNe"dzgNZ"e"fNeUpT Hf de"p hWe"de"f> }>lWfNfNe"dzgNZ"e"f" hHw V qWe"c }>lWf}>~"f G qWe"c }>lWfNfNe"dz s gNZ"e"fN~} L<F="2J;EC 4 cHl lWfNzbJd }<HfNe"dzgNZ"e"fNde"co]deqWe"Z"Z"c u G ^JbJdeM HfNbJg>HdTn hWhWe}>^Je"d hWe"de"f> }>lWfNfNe"dzgNZ"e"f" ¦qWe}>cHe"Z"pv~"d wWe"c ¡ bJdze"d qW~"hWe"gOzbJpve"dZ"bJyWg5qWe"c }>lWf}>~"fa HfNpve"^rw qWe"c }>lWf>e"hHwW~"f}>e"^Jpk|e"d cb s n eBNe"Z"e} $a
HfNpve"^rw¤a HZ"bJg> HdHc¤^JbJdeM HfNbJgvcHlWpkabJd Hi"bJy >HcH~"d }M Y pve"hHn e"^Je"^ gNZ"lWfNZ"yWc} C=kC 3R@@QL<F="2J;GNCv1HRECH@A4 RM= k4 RRGN3H2AEFH@9F 4EC 4 deqWe"Z"Z"c 0YqHH^JyWg]gNZM Hp nsBe"gNe"c}>e"fNe n zbJpve"dZ"bJyWg" hHw nsBzbJpve"dZ"bJyWgqWe"c }>lWf}>~"fa HfNpve"^rw^JbJdeM HfNbJg>Hdn hWhWe}>^Je"d qWe"c }>lWfNfNe"dz s gNZ"e"fNecbJe"hW~"gNZ"r}>e} &a HZ"bJgNg> o qWe"cWs ZM HpvlWgjmfNlWa^J~"pTpve"hWlW^Jz Hg>gNlWf> HdgNZ"cgN~"hWdc qHHdHfNf>oulWhHw V }>lWf}>~"f e"hHwkHzlH}N}a HZ"bJg> HfNyW^o }N}>~"fANdce"hHwkpT HgNbJcja HZ"bJgNf>o
e"fNpv~"gNZ"e}>e"gNe"dve"ZM H^r}<H^ a HfNpve"^rwqWe"c }>lWf e"gNe}>~"ae"d cHl lWfNzbJd }< HcbJgpve"h n lWhWdHcqH H^r}>lWZ"db7 BhWe"dve"hHw gNZ"e"fN| HZ cHl lWfNzbJd }< HcdHcj¦cbJgNZM Hpvr}< Hg>ou [HZ *a HZ"bJg fN~"hWbr} W^ i"g>Hce"hHwWe}>^Je"dqWe"cWs }>lWfNaHdc^JWdaWZ"bJc Y a HZ"bJg[pve"hHqH H^r}>lWZ}<}< Hg> }[e"ccHlWf 6KJ6S52QL<F="2J;@GNCHEo;>= MRGISvF 27EC 4 deqWe"Z"Z"c e"hHwWe"de"c B = {b , . , b } V nsBzbJpve"dZ"bJyWgqWe"c }>lWf}>~"f]e"hHw a HZ"bJg>O~"g c 6= 0 e"hHw}>e}>gNZ W^Je"hWe"gjqWe"c 1}>lWf"u*Hpvne"^rw de"c B
sBfNe5qWlWd}>cHlWZ"ycHl lWfNzb s d }< Hb ~"gQ}>e"hHw cvn e"^7uolWhHw e"hHwWe"dO}>lqH Haa e"hHwT}>e}>gNZ W^Je"hWe"g qWe"c }>lWf"cu1 ,H.pv e",^rw cdn e"c B sBfNejqWlWd}>cHlWZ"yTcHcl klW6=fNzbJ0d }< Hb x , , x xccHlWf b qWe"c }>lWf cbJi"gNe"fN~"^Je} cs9qWe"^~"g{HZ a HZ"bJg B 0 = {b , . , b 1 , c, b n , , b } kHe"^JW^ Nc s9qHH^-HZ x Hd w HzlWg}M ccHlWf[HZ x qWe"c }>1lWf B 0 a Hk−1 Z"bJgNf>kqWlWk+1 d}>cHlWZ"yTcHnl lWfNzbJd }< Hb7 δ k ck x1 − δc1 , . , xk−1 − δck−1 , δ , xk+1 − δck+1 , , xn − δcn Y gNZM HpvlH} 86E6GNFHKJ6KJ6S5E6<4 deqWe"Z"Z"c &Y[Z5e"^ WaabJe"cH^`Hm> Hdpve"h H^J^` s mr}>ck}>6=yu0lWhHwa
HZ"bJgNaae"^J~"m qWe"c }>lWfNdHca HZ"bJg}e"^JHhHwWyqWe"c }>lWfNf>qWlWd}s cHlWZ"ycHl lWfNzbJd }< >vjhWe"de"f> H^Jyje"^Je"p dt^J^` }>yW^c^JWdaWZcHe"^J^^Je"hHwWe"d ¦Wdd wWe"d ^` }>}>yu{lWhHw$e"ZgNZ"cgN~"hWe"gO~"gTe"^J~"hWgN~"hWe"gvn e"^r}>~}>e"^JeHddHc u]lWhHw HZe"^Je"pvb]a s Z"bJg}>f>HdgNZn lWfNpT Hi"bJykqW~"hWfNe"}>}>yv^Je"hHwWe"d lWcgNZ"lWf n lWd }>lWg }>tzdb m^7 pT }>fNb xolWc bJd qWe"f}< H^` Hg> Hd H^7uH¦gNZ"bJpvm^JeIxjpvy zgNZ"e"fNd~"^A ja HZ"bJgNayW^~"mme"dTcbJcHe"fN^r} b qWe"c }>lWfNdHcvHZ a
HZ"bJgNf>UqWlWd}>cHlWZ"ykcHl lWfNzbJd }< Hbr}M k u x = 1, x = 0, . , x = 0 g JhHw b sBdHcHZ ccHlWf x = 0, . . . , x = 0 1 k−1 k+1 n k ]a HZ"bJgNf>kqWlWd}>cHlWZ"yTcHl lWfNzbJd }<k Hb7 HlW^ −δc1 , . , −δck−1 , δ, −δck , , −δcn , a Hfs pve"^rw bJcpT HgNbJca HZ"bJgNao Z} &}>e"i<dbJc }[^Je"e}[HgNZ"d H^Jdb HZtd 4 RS[PCH@2L"2AK 2A@9F ; 12r=I;>8 FHKrCH@GNC e"hHw cn e"^7ulWhHwHzlH}N}Ue"hHw G = {a , . , a } qWe"c }>lWfNfNe"dzgNZ"e"fkHZ sBzbJpve"dZ"bJyWg0qWe"c }>lWf}>~"fNae"du}>lqH Haa OHZ nsBzbJpve"dZ"1bJyWg0qWe"c }>klWf}>~"fUe"hHw b qWe"c }>lWf>o n Y[Z}jgNZ"e"fNe}>d~"dc e"^JzWd }>e"db7u-lWhHwn e"dd H^J^ sBek
b ∈ ^JbJd G }<Hf}<H^JpTHZM Hg"uqHHhHw bJg b cbrn eBNe"Z"e}sBe qWe"c }>lWf>HbJdHcTqHH^`HpvbJ^rwWe"dO^JbJdeM HfNbJgQcHlWpkabJd Hi"bJy >HcH~"d }M e"hHw c n e"^7ulWhHw b cHl lWfNGzbJd }< Hb B = {e , . , e } e"hHw gN~"hHqWe"c }>lWfNlWckH^JcHlH}N}<¦a HZ"bJgNf>5HZ td @GI2A12FHK 2J;kL<F="2J;GNC qWlWd}>cHlWZ"dH1c u }>e" } n b = b e + . + b e Y[^`Hcr}>gNtc } pvlWg}Qn lWcHlWZM}>lWg>HdupvbJdzbJhke"hHwqWe"c }>lWf}¦cbJi"gNe"fN~"^rqW1eT1 e"^Je"pvba HZ"nbJg}>nf>HdgNZn lWfNpT Hi"bJyH} }NqHQqW~"hWfNe- B a HZ"bJg} hHwWulWhHwU G qWe"c }>lWfNfNe"dzgNZ"e"f qWe"c }>lWf>Hb cHWZ"^ ^Je"e} W^Je"h pvbJd~"^}>Waae}¦qWlWd
Ntdcaekva HZ"bJgNao e"fNpv~"gNZ"e}>e"gNe"dmlWd }>lWg>HdHdd w br}¦}>tztdc aeqWlWddb7uHpve"dd w b O^JbJd (G) H^r}>~"f zbJpve"dZ"bJy >ouHpvbr} G GNCHE 8 "FHEC 4 bJgUdeqWe"Z"eIs }>dc G f>HdhM> r ~"g}>Wf}>~"de}>e"gNe"d a , . , a ^JbJdeM HfNbJg>Hd&n hWhWe}>^Je"de"c ^JbJd G e"hHwa HZ"bJg> }[Hz > HcoIu Hpve"^rwWe"cHe} HZ e , . 1 , e qWe"rc }>lWfNlWccH^ i"gNe"fN~"^r}>dcn e"^7u HccHlWf HZe"^Je"pvb¦a HZ"bJg}>f>HdgNZn lWfNpT Hi"bJyWcgNlWfNlW1 ZM}<e"rhHw H = {a , . , a , e , , e } a HZ"bJg}e"fNe"zpv~"d wWe"Z"e}N}M Y b qWe"c }>lWfNdHcHZe"fNfNe ¤a H1Z"bJgNf>$qWlWrd}>r+1 cHlWZ"y
cHl lWnfs zbJd }< Hb0^Je"hHwWe"de"c d0, . , d0, d0 , , d0 d0 = = d0 = 0 u0HccHlWf 1 u qHHhHw rbJg r+1 ^JbJd n u r+1 qHH^`Hpve"^rw n 0 0 0 b = d a + . . . + d a b ∈ (G) d = 6 0 j 1 r e"gNe}>~"d1u]HccHlWf b ∈/r ^JbJd (G) e"hHw c~"gNZ"fNeHu]lWj hHw$ cHlWpvm}>bJabJ^J=br}< Hrg+q 1,bJZ"gN.h H ^`,n} }>t^`NzlWdcH~"mme"dHddHcO5pve"h H^J^`Hmr}< Hg>oulWhHwHZ 1 δ^Je"= pvbHcak HZ"bJg}>f>HdgNZn lWfNpT Hi"bJyWc0gNlWfNlWZM}< MqHH^Wa HfNpve"^rw[a HZ"bJgNayW^W }N}>~"fNe}>dc x 1 a1 + . + x k ak = b ^JbJdeM HfNbJg e"hHwWe"d^Je}>fNe"dzgNZ"e"fNde"cTqHHd sBe0pve"hWlW^Jz Hg>o U qHHduoHccHlWf{e"hHw o}N}<H^ pve"hbJg }< HfNlWZ"tdce"hHwWe}M x0 = (d01 , . , d0r , 0, , 0)
Y[Ze"hHwWe"d^Je}>fNe"dzgNZ"e"fUe"hHwbJ^rwWe"d 0 pve"hWlW^Jz Hg> }MuHpve"^rw ae"dHZ 0 de"p5sBdt^J^` cHlWpvmlWde"dgNe"bJe"Z}<Hf}>lWZ"yqWe"c }>lWf>Hb x G qWe"c }>lWfNfNe"dzgNZ"e"fNde"c^JbJd x(G) a HZ"bJg> } H^JcHlH} > Hc u L<F="2J;ST698RKr3 F ;EC 4 deqWe"Z"Z"c G pTHh a HZ"bJg"u]HccHlWfv^JbJd (G) HZ e"hW~"gNZ nsBzbJpve"dZ"bJyWgUqWe"c }>lWf}>~"f~"gk^JbJdeM HfNbJgUe"hHwWe"d^Je}>fNe"dzgNZ"e"fNde"c i"g>Hc e"hHwWe}>^Je"d pve"hWlW^Jz Hg>TqHHdjHZ&e"fNfNeva HZ"bJgNf>qWlWd}>cHlWZ"ycHl lWfNzbJd }< Hc 5Y cHlWpvm}>bJabJ^Jbr}< Hg q bJZ"gNh H^`}kpT
HgNbJcHgNZ"dlWg&pve"^J^J~"c }>e"fNpv~"cHeHulWhHw e"hHw o}N}<H^Qpve"hW}< HfNlWZ"Z"tc G qWe"c }>lWfNfNe"dzgNZ"e"f0f>HdhM> }QbJg"¦~"Z"Z"dcpvlWg}Qe"hHwTm~"^Jz }]cHlWpvm}>bJabJ^Jbr}< Hg q bJZ"gNh s ^`}>f>o e"hHwWe"d a1 a2 1 1 G= 2 1 1 , −1 3 0 a3 a4 a5 1 1 1 −1 1 1 , 1 , 0 , 1 0 1 2 b 9 4 1 5 Y gNZM Hpvr}< HgNlWc}Ui"~"^JgNZ"e"fN| }< Ha^` HZM}>lWg n lWfNpT HaHde"^rqW~"hWe"Z"db75Y }< Ha^` HZM}Ue"^Jg lWgNZ"^JlWm HaHd5HZ0Hc }>t H^JbJg*a HZ"bJgqWe"c }>lWfNlWc} }>d }>e} Ncn e"^7uWHZ]e"^Jg
UgNlWfNaHd& a HZ"bJgNlWd crq ^Jb qWe"c }>lWfNlWc}Mu }< Ha^` HZM}Uae"^JgNeBN~"ae"dme"zbJhOa HZ"bJgNlWd crq ^Jb*qWe"c }>lWfNlWcdHc HZvHzlH}N}ja HZ"bJgNf>OqWlWd}>cHlWZ"ycHl lWfNzbJd }< Hbr}MkY[Z jcHl lWfNzbJd }< Hc}jHZ&e"^Je"pvb a s Z"bJg}>f>HdgNZn lWfNpT Hi"bJy5gNZMHa H^rw MqHH^}< HfNlWZ"Z"tcOpve"h Bdzt^Jy5}< Ha^` HZM}M ¦e"pka HZ"bJgQqWe"c }>lWfNlWc ¡ ¡ a1 H Z"bJg qWe"c }>lWfNlWc e1 e2 e3 e4 ¡ ¡ a4 a5 ¡ ¡ ¡ a2 a3 ¡ −1 −1 ↓ ¡ ¡ ¡ b ¡ ¡ ¦l lWfNzbJd }< Hc Y[Z a , . , a qWe"c }>lWfNlWccHWZ"^¦a HfNpve"^rw bJcae"^J~"me} a HZ"bJgNa b qWe"c }>lWf} a HZ"bJgN1lWdcrq 5^ }<Hf} Ntc
Iu*HfNf>cHe"^J^ i"g>Hc hHwWe"^Jddc u lWhHw hWe"de"f> H^Jye"^Je"p HZT cHl lWfNzbJd }<ouHpve"^rw&a HZ"bJgNaae"^J~"m ~"gQa HZ"bJg}{e"^JHhHwWyqWe"c }>lWfUpve}>gNZ"~"gNmlWd }s > HaHdqHHd s9}>yW^*c^JWdaWZ"Z"~"c U H^`HgNgNZ"tcm^7kOae"cHe"fNe}>e"Z"e}N} ¡ sBe"g}jhWe"de"f> H^Jy e"^Je"pvde"c ZOHZ}¦Ne"^Je"d }>b7u lWhHw HZ e qWe"c }>lWf5e"^JHhHwM>a HZ"bJg}5~"g a cHe"fN^] 1 e"^rwW~"fNeHYgNZM Hpvr}< HgNlWc}i"~"^JgNZ"e"fN| hHwT e"^rqW~"hWe"Z"db7uolWhHwve"^ WgNZ"WfQhWe"de"f>1 H^Jyke"^Je"p gNlWf> }
qW~"hWbJhWlWgNZ} NtchWe"de"f> H^JyOe"^Je"pvpve"^7 ccHlWfjpvbJdze"dupv~"hOa HZ"bJgNlWdcrq ^ pTHf>Hzo}UqWe"c }>lWfNf>pve"hWcHmNtc δ 5 Hd w HzlWg}M Z"Z"e"^{HZ}< Hd hWe"de"f> H^Jye"^Je"p lWgNZ"^JlWm }kpve"hWgNZ"lWfNlWZ"Z"tc~"g&HZbJ^J^Je}qWe"c }>lWf&lWgNZ"^JlWm HayW^HZJhHwcHmlH}N}kqWe"c }>lWf} cbrqWlWd Ntc BhHw5cHqWe}>cHe"Z }< Ha^` HZM}>lWcvgNlWfNlWZM}< }0cHmNtc a1 e2 e3 e4 a1 a2 e3 e4 a1 a2 a4 e4 a2 ¡ a3 a4 a5 s¡ ¡ −3 −2 −3 −3 −1 −1 −2 −1 −14 −8 −1 −22 a3 −2 a5 ¡ 1 ¡ ¡ a3 −2 −3 a5 a4 ¡ ¡ b b −5 14 H H b −5 −6 H −1 YgNZM Hpvr}< HgNlWc}]de"p }>tz NtcT}>lqH
Haan lW^rw}<}>db7u bJgNZ"e"d e sBe}0de"p ^Je"e}¦gNe"p sH^7ugNe"p a sBe"^cbJi"gNe"fN~"^Jdb7 brqWe"^ bsBde"cvHZ e sBfNe¦qWlWd}>cHlWZ"y54 cHl lWfNzbJd }< > u b a 4 n e"3^JJfN}>y5HZ5H^` Haabpvy zlWd b = −5a1 − 6a2 + 20a4 . dde"ce"^rwWe"gNgN~"hW~"f W^ pve"hbJgUhHw WZ ze}>dc vY G qWe"c }>lWfNfNe"dzgNZ"e"ff>HdhM> ~"g ^JbJd (G) b∈ bsBde"cHZ e4 sBfNe qWlWd}>cHlWZ"y cHl lWfNzbJd }< >¦dt^J^` }>yW^Wc^JWdaWZ ^Je"ddeHuWHccHlWf ^JbJd ^Je"ddeH b∈ / Z"Z"e"(G) ^jgNZM Hpvr}< HgNg>H^e"hHw o}N}<H^ pve"hW}< HfNlWZ}>tc5jcHqWe}>cHe"Z5e"hHwWe"d^Je}>fNe"dzgNZ"e"f e"hHw a
HZ"bJg<pve"hWlW^Jz Hg> }M x1 + x 2 + x 3 + x 4 2x1 + x2 − x3 + x4 x1 − x 2 + x 3 3x1 + x4 + x5 + x5 + x5 + 2x5 = = = = 9 4 1 5 Y[Z u u u u i"g>HcthHw Hd e"hHwa HZ"bJgNpveIs hWlW^Jzx H1g"*=Y[−5 fNfNyW^7ux2lWhH=w&−6 pve"hWlW^Jxz3 H=ge"0hHw gNZ"xe"4fN|O=a20 e"e"^rwWxe5}N}>=e"gN0r}>~"gNgNe"^hHw WZ ze}>dc&pve"h Y[Z} me"zbJhu lWhHwa HZ"bJgNpve"hWlW^Jz Hg¦HaayW^ ^` }>} Ntc u lWhHwHZ x , x , x de"pvdt^J^` qH H^r}>lWZ"yWclWZ }<Hf}>lWZ"y a , a , a qWe"c }>lWfNlWcO^JbJd (G) a HZ"bJg> }¦H^JcHlH1} > Hc 2 4 5n e"d }>be"hHwWe"d^Je}>1fNe"d2zgNZ"4e"fNde"cde"pvi"g>Hcve"hHwpve"hWlW^Jz Hg> }gNZ"e"fNe}>d~"dcOpve"hs
}< HfNlWZ"db7u Hde"p qHH^`Hpve"dd w br}MuoHccHlWf]bJge"^Je"hWe"dz vn e"d }>bcHlWpvm}>bJabJ^Jbr}< Hgq bJZ"gs h H^`}>lH}[e"^rqW~"hWe"Z"db7Y cHlWpvm}>bJabJ^Jbr}< Hg]q bJZ"gNh H^`}Ue"fNe"zpv~"d wWe"cH~"d }thHw HdbJg GsBde"c a HZ"bJgNaaede"p cHe"fN^r}TqWe"c }>lWf>HbJdHc H a HZ"bJgNf> qWlWd}>cHlWZ"ycHl lWfNzbJd }< Hbr}&bJg pve"hW}< HfNlWZ}>tc e"hHwWe"de"ce"Z"e"c dj (i = 1, . , r; j = r + 1, , k) qHHhHw bJg i aj = dj1 a1 + . + djr ar ccHlWf[HZUe"hHwWe"d^Je}>fNe"dzgNZ"e"f[JhHwbJg]JfN}>y brqWe"^ j = r + 1, . , n r+1 a1 x1 + . + ar xr + dr+1 1 a1 + . + dr ar xr+1 + + dk1 a1 + . + dkr ar xk = d01 a1 + + d0r ar H a
HZ"bJgNf>kqWlWd}>yvcHl lWfNzbJd }< HcTe"hHwW~"f}>e"^Jpk|e"c u e"Z"~"f} xi + dr+1 xr+1 + . + dki xk = d0i i (i = 1, . , r) xi = d0i − dr+1 xr+1 − . − dki xk i (i = 1, . , r) qHHhHwO }>fNe"dze"ZqWe Y[Z x , . , x qH H^r}>lWZ"yWc} 4 /@B/@@L<F="2J;U1FHK @BRM= 4 dHc u HZ x , , x qH H^r}>lWZ"yWc} ^r}>lWZ"yWcdHck }>e}>gNZW^Je"hWe"g ;>=C L<C 13 E6SvrL<F="2J; 1FHK @BRM= 4EC 4 deqWe"Z"Z"c Y gNZMHaHz qH Hr+1 ~"f}>~"cHe}HzoqH~"gvHZ}< Hd cHH}>H}N}&qH H^r}>lWZ"yWc}5n e"d }>bQn lWfNpkt^` MqHH^cbJgNZM Hpvr}NqHHZ e"hHwWe"d^Je}>fNe"dzgNZ"e"f0e"hHwTpve"hWlW^Jz Hg> }U PCHGI@2J4 KrFHGI2J;UST698RKr3 F ; cHmNtcv~"g0HZ
e"hHwWe"d s ^Je}>fNe"dzgNZ"e"fQpvbJdze"dTpve"hWlW^Jz Hg>je"^ H^J^Jr}>}>y bJ^rw5pvy zlWd gNZMHaHz de"pka HZ"bJg< qH H^r}>lWZ"yWcdHcdt^J^`U~"f}>~"cHe}QHztdc uoHccHlWf{HZ0JhHwkcHmlH}N}[ mHf}>bJct^` HfNbJg< pve"hWlW^Jz Hg e"hHwOa HZ"bJgNpve"hWlW^Jz Hg" Y gNZM Hpvr}< HgNb*e"^ > Hf> HgUthHw HdHZHupvbJd }UOcHlWpvm}>bJabJ^Jbr}< Hg]q bJZ"gNh H^`}>d H^7 Z"lWc Hg HZ"lWdaHd bJ^rwWe"dcHlWfkqWe"c }>lWfNlWc}&lWZ"ZM }<Hf}>lWZ"yqH H^r}>lWZ"yWccH^ fNe"mfNe"Z"e"d }< H^Jdb7uHZ e"hHw gN~"hHqWe"c }>lWfNlWc} me"zbJh&de"p JfANtccb7 Y gNZM Hpvr}< HgNlWc}]JhHwO&cHqWe}>cHe"Z }>WpvWf n lWfNpT
HaHdqW~"hWe"Z"e} Nce"^7 x1 x1 x2 x4 2 1 3 x2 x3 x4 1 1 1 1 −1 1 −1 1 0 0 0 1 x5 1 1 1 2 b 9 4 1 5 x2 1 −2 −3 x3 x4 x5 b 1 1 1 9 −3 −1 −1 −14 0 −1 0 −8 −3 −2 −1 −22 x3 −2 3 6 6 x4 0 1 1 x5 0 1 2 2 b −5 14 20 20 x 3 x5 −2 0 −3 −1 6 2 0 0 b −5 −6 20 0 Y[Zje"hHwWe"d^Je}>fNe"dzgNZ"e"f H^r}<H^` HdlWgpve"hWlW^Jz Hg>o m^7HZ x1 = −5 + 2x3 x2 = −6 + 3x3 + x5 x4 = 20 − 6x3 − 2x5 u ~"f}>~"cHe"cHe}vHz NtcgNZMHaHz qH H^r}>lWZ"yWcdHc u HccHlWf5HZ mHf}>bJct^` HfNbJg¦pve"hWlW^Jz Hg} cHmNtc u x3 = 1 x 5 = 1 u u u u x 1 = −3 x2 = −2 x3 = 1 x4 = 12 x5 = 1 Hpv b}>e"fNpv~"gNZ"e}>e"gNe"dde"p a HZ"bJgNpve"hWlW^Jz Hg" Y cHlWpvm}>bJabJ^Jbr}< Hg q bJZ"gNh H^`}>lH}U ~"g]HZ
e"^Je"pvb a HZ"bJg}>f>HdgNZn lWfNpT Hi"bJyWg{}>e"i<dbJc }I pT }>fNb xOf>HdhM> HdHcOpve"hW}< HfNlWZM Hg> HlWZj~"g[pT }>fNb xbJd qWe"fNZ"~"de"ccbJgNZM Hpvr}< Hg> HlWZjbJg ^Je"e}[HgNZ"d H^Jdb7]Y[Ze"^ Waab HZ"~"f} ^Je"e}>gN~"hWe"g"upve"f}[vpT }>fNb xf>HdhM>vHZlWgNZ"^JlWm s qWe"c }>lWfNfNe"dzgNZ"e"fN~"de"cf>HdhM>qHHhHw bJgQHZ[lWgNZ"^JlWm qWe"c }>lWfNlWcTcHWZ"^a HfNpve"^rwva HZ"bJgNa aeqWlWd}>yqWe"c }>lWfNlWcpT xobJpT H^JbJg¦gNZM HpTo5Y n e"d }>be"hHwWe"d^Je}>fNe"dzgNZ"e"fe"hHw o}N}>}>y pT }>fNb x HdHc¦f>HdhM>
ubJgNZ"e"dmlWd }>lWg>Hde"dd w br}}>tzo}>tdcjHZ lWgNZ"^JlWm qWe"c }>lWfNlWcUcHWZ"^ 5a HZ"bJgNa5aeq bJddb7 nsBfNe"dz| A pT }>fNb xbJd qWe"fNZ"eme"zbJhvHZ Ax1 = e1 . Axn = en zHf>Hae"hHwWe"d^Je}>fNe"dzgNZ"e"f e"hHwW~"f}>e"^Jpk|kpve"hWlW^Jz Hg> HayW^ [HZbJd qWe"fNZQ^J~}>e"Z"bJco-cHm s n }>y A−1 = [x1 , . , xn ] Y[Z 1 1 1 A= 0 1 1 1 0 1 pT }>fNb x bJd qWe"fNZ"~}HZ{H^` HaabWgNZM Hpvr}< HgNlWccH^ }< HfNlWZ"} Ntc pve"h0e"^Je"pvb a HZ"bJg}>f>HdgNZIs n lWfNpT Hi"bJyWc&gNlWfNlWZM}< MqHH^7 a1 a1 a2 a3 0 1 a2 1 1 0 a3 1 1 1 e1 1 0 0 e2 0 1 0 e3 0 0 1 a2 1 a3 1 1 −1 0 e1 e2 1 0 0 1 −1 0 e3 0 0 1 a3 0 1 e1 e2 1 −1 0 1 −1 1 e3 0 0 1 e1 1 1 1
e2 −1 0 1 ↓ A−1 e3 0 −1 1 [Y Z AA−1 = I e"hHwWe"d^WgN~"he"^J^Je"d WfNZ"~"gN~qWe"^]hHw W Z ze}>dcpve"h HfNfNyW^7ulWhHw qHH^JyWaHdHZ A bJd qWe"fNZ"~}[gNZM Hpvr}>lH}N}>tcvcb7 "!()* + (,- "! F="KrCH@BR;2J;ST6GI@B6@B:<; e"cbJd }>gNdcTe"hHw K 2AE6>FHGI2J;{PG>R>8HGNCHSTRM=F ;2 M 6KrC 3 CH@BR@ HZ td 4WCHERE2J4 ;jCHKrC 4WL<CHE x≥0 ¡ Ax = b c0 x − max HlW^n e"^r}>e"gNgNZ"c ulWhHwHZ A m × nsBe"gpT }>fNb xgNlWf>Hb ^JbJdeM HfNbJg>Hd n hWhWe}>^Je"de"c ~"g u0qHH^`HpvbJd }TlWhHw¢HZ Ax = b e"hHwWe"d^Je}>fNe"dzgNZ"e"fNde"c qHHd ^Je"h H^` Haa¤e"hHw b ≥ 0 ^Je"e}>gN~"hWe"gTa HZ"bJgNpve"hWlW^Jz Hg>o Y[Z
H^r}<H^` HdlWgNg> HhcHlWfN^` }>lWZM Hg> d~"^Jc^]n e"^r}>e"e} Nc u lWhHwHZ x0 = [x0 , x0 ] de"pvde"h }>rqa HZ"bJgNpve"hWlW^Jz Hg hHwmHf}>Ji"bJlWd H^J}>yulWhHw }<Hf}<H^JpTHZ"ZMvBva HNZ"bJgqH H^r}>lWZ"yWc}k cHH}>H}N}[bJgNpve"fNe}>^Je"de"coIu x me"zbJhvde"pka s xB Z"bJgqH H^r}>lWZ"yWc} gNZMHaHzbJgNpve"fNe}>^Je"de"coI dde"cpve"hHn e"^Je"^ e"dmHNf}>Ji"bJlWd H^ NtcTHZ A pT }>fNb xolH}Mu qHH^`HpvbJd }Q c qWe"c }>lWf}[bJg" Y B pT }>fNb xlWgNZ"^JlWmHb}>e" }[HZ e"hHwWe"d^Je}>fNe"dzgNZ"e"fNa W ^7uHZ A = [B, N] , c0 = [c0B , c0N ] . A lWgNZ"^JlWm qWe"c }>lWf}>e"fN~"de"ce"hHwOa
HZ"bJg> }0Hz > Hcg]JhHw BxB + NxN = b xB + B−1 NxN = B−1 b e"c q brqHH^Je"dge"hHwWe"d^Je}>fNe"dzgNZ"e"f}cHmNtc u Hpve"^rw a W ^HZ dt^J^` HdHc&qH H^`HgNZ}NqH&HZ xB = B−1 b xN = 0 xN gNZMHaHz&qH H^r}>lWZ"yWc~"f}>~"cH~} a HZ"bJgNpve"hWlW^Jz HgNlWZ¦Nto}>tdc e"^r}>~}>e"^Je"Z"~"gNdcgNZ"e"fNbJd } −1 u gJhHwe"e"Z a HZ"bJgNpve"hWlW^Jz HgNlWZ}<Hf}>lWZ"yOi"~"^rn hWhHqW~"d wW~"f}>~"c c0 B−1Bb b ≥B0−1b > 0 uHccHlWf gNZ"yWaHd n lWfNhWyOa HZ"bJgNpve"hWlW^Jz Hg} E6Sv36986E6GNFHK @EBC 4 ue"^J^Je"dcHe"Ze"gNe}>ae"d 36986E6 GNFHK @EC 4 deqWe"Z"Z"c Y e"hHwWe"d^
WgN~"hWe}Qn e"^JHgNZ"d H^rqHHZ −1 −1 qWe"c }>lWf}[HZT ¡ i"~"^rn hWhHqW~"d wW~"aee"^rwWe}N}>e"gNr}NqWeHZH^` Haabxe"Bc q =brqHHB^Je"dg0b^J−bJdeMB HfNbJgNx mfNlNs hWf>HpvlWZM HgNbn e"^`Hz}>lH}0cHmNtc xB ≥ 0, xN ≥ 0 xB + B−1 NxN = B−1 b c0B B−1 b + (c0N − c0B B−1 N)xN − max bJd }>lWhHw[n e"^r}>e}N}>c u lWhHw B−1b ≥ 0 u ~"gpvbrqWe"^ x ≥ 0 u c0 −c0 B−1N ≤ 0 e"hHwWe"d^H}>^Je"dgN~"hn e"dd H^J^` Hg>e"gNe}>~"d$HZ x = B−1b u Nx = 0 aN HZ"bJgNpvB e"hWlW^Jz Hg> kn e"^`Hz}>dHc uQgJhHw qWe"^Jee"c q brqHH^Je"dBg ¡ 9sBde"c$bJgvNlWmo}>bJpT H^JbJg5pve"hWlW^Jz Hg>oY n e"^`Hz}[}>e" }HZHu-lWhHwcHe"fNe"gNgNdc HZ Ax = b
e"hHwWe"d^Je}>fNe"dzgNZ"e"fNde"c e"hHwlW^rw Hd a HZ"bJgNpve"hWlW^Jz Hg> }MuHpve"^rw fNe −1 ~"gT 0 e"hHwWe"d^ H}s 0 −1 ^Je"dgN~"hWe"c lWmo}>bJpTH^Jbr}< HgNb cfNbr}>~"fNbJBtpvlWbco¦≥e"hHw 0gNZ"e"fNfNeTc}>Ne"^ N−e"gNc^JBdBe"c TNY[Zv≤H^` H0aabg}>f>}>~Is hWb` }QcHqWe} Nc UbJbJdzt^Jtdcve"hHwlW^rw Hda HZ"bJgNpve"hWlW^Jz HgNayW^7u Hpve"^rw fNej B−1b ≥ 0 }>e"^ Ne"gN^]~"gT c0 − c0 B−1N ≤ 0 de"p H^J^n e"ddu]HccHlWfT }N}>~"fNdce"hHw$lW^rw Hd a HZ"bJgNpve"hWlW^Jz HgNf>oNuHpve"B^rwi"g>Hce"hHwa HZ"bJgqWe"c }>lWfNaHdc^JWdaWZ"bJcHZe"^ WZ H} W^7u}>ls qH
Haaf>Jgde"pvde"h }>rq$ze lWZ"ZM }<Hf}>lWZ"yi"~"^rn hWhHqW~"d wW~"f}>~"c¢dqWe"cgNZ"bJc AqHHhHw ^Je"h H^` HaabJg{de"p i"gNWccHe"d I Z}¦5a HZ"bJgNayW^cbJ^J~"m 5~"g¦ka HZ"bJgNa5ae"^J~"m kqWe"c }>lWfNlWc hWlWdzlWgpve"hHqH H^`HgNZ}< Hg> MqHH^H~"fANcUe"^7 e"hHw c n e"^7u lWhHwj j sBe"zbJc[de"pka HZ"bJgqWe"c }>lWfNf> ccHlWf0cH~}[e"gNe}[^Je"e}>gN~"hWe"g" (c0N − c0B B−1 N)ej > 0 ¡ B−1Ne ≤ 0 e"cbJd }>gNcpvlWg}HZ x = λe u x = B−1b − λB−1Ne ^Je"e}>gN~"hWje"gpve"hWlW^Jz Hg}Mu HlW^ λ > 0 Ne"ZU jλ(c0 B− c0 B−1N)e i"~"^rn hWhjs
qW~"d wW~"f}>~"c}<Hf}>lWZ"bJc uHpve"^rwTpvbJdze"d}< HfNlWd} ^-Nd uB λ − ∞j ZHZ} Ne"^Je"d }>b7uolWhHw bJ^J^7 HZT ¡ {n e"^`Hz}>dHcTdbJdi"g]lWmo}>bJpT H^JbJgpve"hWlW^Jz Hg>o e0 B−1Ne > 0 qHH^`Hpve"^rw ksBf>o k e"hHwWe"d Kj = {i | e0 B−1Ne > 0} 0w bJ^rqH Hd K 6= ∅ e"hHwWe"d i ∈ K e"hHw j lW^rw HdbJdzeIxulWhHw i e0i B−1 b e0k B−1 b = . min k∈K e0k B−1 Nej e0i B−1 Nej ¡ Z"to}< HdqW~"hWfNe"}>tdce"hHwa HZ"bJgNi"gNe"fN~}¤ e"^Je"pvba HZ"bJg}>f>HdgNZn lWfNpT Hi"bJyH}II HZ Bis bJc a HZ"bJgqH H^r}>lWZ"ye"^JHhHwM> a HZ"bJg}v~"gTe"^rwW~"fNe j sBe"zbJc de"pka HZ"bJgqH
H^r}>lWZ"y cHeIs fN^7Ue"de"f> H^Jy e"^Je"p HZ e0 B−1Ne > 0 e"^Je"p ^Je"gNZH Y qH H^`HgNZ}< HgNb]gNZMHa H^rw NgNZ"|ccHe"fNe"gNZ}>pve}>gNZ"e} kgNZ"ie"fNbJd }>b qH Hj ^`HgNZ}< Hg<0abJZ}>lWgNr} >ou lWhHwHZ [a HZ"bJgNpve"hWlW^ s z Hg bJg^Je"e}>gN~"hWe"g{^Je"gNZHu (c0 − c0 B−1N)e > 0 e"hHwWe"d^ H}>^Je"dgN~"hme"zbJhHZ}Mu lWhHw HZ a HZ"bJgNlWZ5}<Hf}>lWZ"yi"~"^rNn hWhHqWB~"d wW~"f}>~"cjde"p ^Je"gNZvfNlWgNgNZMHaa c0 B−1bsBd~"^7ug H} }< HfNlWZ"lH}N}<HdkNlWaa^Je"gNZHu e0 B−1b > 0 Zto}>yWaabe"gNe} pvbJdzBbJh5n e"dd H^J^7uT a HZ"bJgNlWZU}<Hf}>lWZ"y&a
HZ"bJgNpve"hWilW^Jz HgQde"pvze"hWe"de"f> H^r}M B Y n e"d }>bj^J~"m~"gNe"cHe}e"Z"to}< Hd pve"hWbJgNpv~}>e"^ Nc HZ a HZ"bJgNpve"hWlW^Jz Hge"gNe}>~"ae"d e"^J^Je"d WfNbJZ"Z"c$HZlWmo}>bJpTH^Jbr}< Hg}5bJ^J^7 n e"^`Hz}Tpve"hWlW^Jz}>yWg> Hh }MupTNz¤e"hHw a s Z"bJg}>f>HdgNZn lWfNpT Hi"bJyH}qW~"hWZ"dce"^Qn e"d }>bgNZMHa H^rwWlWcgNZ"e"fNbJd }M brqWe"^Q^Je"e}>gN~"hWe"g a HZ"bJgNlWc ~"g[JhHwva HZ"bJgNpve"hWlW^Jz HgNlWcogNZM HpT&qW~"hWe"g[~"g[ze"hWe"de"f> Hi"bJyTpve"d }>e"g[e"gNe}s ae"dvi"~"^rn hWhHqW~"d w~"f}>~"cHekd
uze"hWe"de"f> Hi"bJyTpve"d }>e"g e"gNe}>ae"dqW~"hWe"g gNZM Hp e"^Je"pvb a HZ"bJg}>f>HdgNZn lWfNpT Hi"bJy gNZ"bJpvm^JeIx¢br}>e"f> Hi"bJy&e"^rqW~"hWZ"~"gNeto}< Hde"^ cHe"^J^ Nto}>dtdc¢e"hHw lWmo}>bJpT H^JbJg a HZ"bJgNpve"hWlW^Jz HgNlWZQqHHhHw&HddHckpve"h H^J^`Hmr}< Hg> HlWZHuHlWhHw& n e"^`Hz}>dHc dbJdi"g0lWmo}>bJpT H^JbJg{pve"hWlW^Jz Hg>o e"hMNe"hHwWe"Z"Z"c u{lWhHw a HZ"bJgNaae"^J~"m bJ^J^7cbJ^J~"m qWe"c }>lWfNlWc pve"hHqH H^`HgNZ}< s g> HdHc£dlWpvr}< Hg> MqHH^U pve"hHn e"^Je"^ gNZMHa H^rwWlWcn e"^` H^J^Jr}< Hg> MqHH^{HfNf> HZe"gNe}>fNeHu qH H^`HgNZ}<
Hg{de"p e"hHwW~"f}>e"^Jpk| {jqW~"hWe"gNgN~"h&HZ[ H^r}<H^` HdlWge"gNe}>ae"dujde"pvze"hWe"de"f> H^r}s g> Hh5n e"^r}>~}>e"^Je"Z"~"gNed~"^Jc^bJg]abJZ"lWd w r}>}>y zzbJhvi"g>HcHZ}[HZe"gNe}>e} d~"Z}>c uHpvbJcHlWf]bJgNpve"f}>dce"hHwbJdzt^Jy&^Je"e}>gN~"hWe"g a HZ"bJgNpve"hWlW^Jz Hg}M [HhHwWlWdcHWdd w |e"hHwbJdzt^Jyvpve"hWlW^Jz Hg}¦Hzdb7u 5n e"^`Hz} HZ H^` HaabH^`Hc x ≥ 0, u ≥ 0 Ax + u = b c0 x − max ~"g b ≥ 0 Z}&n e"^`Hz}>lH} ERGISvFHK M6KrC 3 CH@EC 4 rqMNtc u*~"gkHZ x = 0 u u = b a HZ"bJgNpve"hWlW^Jz HgjHZ u &a HZ"bJgqH H^r}>lWZ"yWc uHZ x &de"pka
HZ"bJg]qH H^r}>lWZ"yWcvqWe"c }>lWf> ]e"hHw H^JcH^JpTHg{bJdzt^Jy5pve"hWlW^Jz Hg" vkn e"^`Hz}Q}>Wf}>~"de}>e"gNe"dde"p bJ^rwWe"dH^`Hc uHccHlWf q bJgNgNZMMqWe"Z"e}>e} NcHZ5 n lWfNpT Hf>m^7HZ td¦cH~}Nn HZ"bJg OgNZ"bJpvm^JeIxvpvy zgNZ"e"fNfNe"^B e"hHw cn e"^7ulWhHw5pve"hWlW^JzHdzykn e"^`Hz}05cHqWe}>cHe"Z x ≥ 0, u1 ≥ 0 A1 x + u 1 = b 1 A2 x = b 2 ¡W¡ c0 x − max Y[Z H^r}<H^` HdlWgNg> Hhjpve"hWgN~"f}>~"gNe[d~"^Jc^ n e"^r}>e"e} Nc uolWhHw ~"g ¦ bJd s ze"d^JbJdeM HfNbJg mfNlWhWf>HpvlWZM HgNb n e"^`Hz}jbJ^rwWe"dH^`Hcf>OlWZ"b}>1y≥TY[0 Z axb2≤≥ b0u b ≥ 0 H^`Hc
n e"^r}>~}>e"^Je"c HZ cbJe"hW~"gNZ"r}qH H^r}>lWZ"ygNe"hWr}>gN~"hW~qWe"^ + u = b H^`Hcf> lWZ"}>yWc~"g JhHwkHZ]e"u^Jg U≥n e"0^r}>~}>e"^i"gNlWmlWf}>aHd5qHHddHc Y[Z ax ax e"hHwWe"d^ WgN~"hWe"c& = b pT HgNl zbJcaHdu pvbrqWe"^br}N}0 b ≥ 0 gNZ"cgN~"hve"gNe}>~"d −1sBhHwWe"^qHH^Jykae"gNZ"lWfNZM HgNg>H^-pvbJd s zbJhabJZ}>lWgNr}>}>yjY[Z ≥ b u b ≥ 0 n e"^r}>~}>e"^Je"cme"zbJh v ≥ 0 n e"^Je"gN^Je"hqH H^r}>lWZ"y gNe"hWr}>gN~"hW~qWe"^ ax − v =ax H^`Hcf>lWZ"}>yWcv~"gQJhHwpT HgNl zbJc5n e"^r}>~}>e"^i"gNlWmlWf}>aHd b qHHddHc Y ]n e"^`Hz}>lH} STM3R;?A@BR@@QERGISvFHK
M6KrC 3 CH@EC 4 rqMNtc 0e"dze"^ NclWZ"ZM {n e"^`H z}>lWZj5cHqWe}>cHe"Z gNe"hW~"zon e"^`Hz}>lH} uHpve"^rwe"hHwOdlWfNpT H^n e"^`Hz}M x ≥ 0, u1 ≥ 0, u2 ≥ 0 A1 x + u 1 = b1 A2 x + u2 = b2 10 A2 x − max Y Qn e"^`Hz}¦i"~"^rn hWhHqW~"d wWekcHlWfN^` }>lWg"u bJgNZ"e"d 10b vi"~"^rn hWhHqW~"d we"hHwn e"^Jg TcHlWfs `^ } >oBhHw 9sBde"cvqHHdlWmo}>bJpT H^JbJg{pve"hWlW^Jz Hg>o e"2hHwWe"d x0, u0 , u0 Q {n e"^`Hz} e"hHwOlWmo}>bJpT H^JbJg{a HZ"bJgNpve"hWlW^Jz Hg> bJ^rwWe"dpvbJdzbJhk^J~}>e"Z"bJc I ccH1lWf¦cH2~}¦e"gNe}¦qHHd ¡ 10A x0 = 10b uHpvbJa W^ A x0 = b u u0 = 0 cHqWe}>cHe"Z"bJc u g]JhHw
x0, u0 HZ 1 e"fNe"z2e}>b{ {n e"^`2Hz}0e"hHwO^Je"2e}>gN~"hWe"g¦2a HZ"2bJgNpve"hWlW^Jz Hg>o 10A x0 < 10 b u[AqHHhHw Hpvb{thHw HdHZHu u0 sBdHc qHHd^Je"h H^` Haae"hHw mlWZ"br}>rq cHlWpv2mlWde"dgNeHu{H2pvb{gNZ"cgN~"hWcH~"mme"d¢a HZ"bJgqH2 H^r}>lWZ"yI aae"d¤HZe"gNe}>ae"d¤HZ e"fNe"ze}>b{ {n e"^`Hz}>dHcTdbJdi"g0^Je"e}>gN~"hWe"g¦pve"hWlW^Jz Hg>o ~"^JgNZ"e"fN| ]n e"^`Hz}>lH}[bJgUTgNZ"bJpvm^JeIxpvy zgNZ"e"fNfNe"^*pve"hWlW^JzHdb7 Z}UgNZ"lWc Hg e"^Jg On HZ"bJgNdHc5deqWe"Z"db~"ge"ZvcbJZM HfNyW^`Hh [n e"^`Hz}je"hHw ^Je"e}>gN~"hWeva HZ"bJgNpveIs hWlW^Jz Hg>
HdHcpve"hW}< HfNlWZM Hg> Hf>gNZ"lW^Jh H^7Y[Z e"^Jg n HZ"bJgNaHd¤de"p bJgv}>Wf zdc i"~"^rn hWhHqW~"dd wWe"^7udlW&e"dde"cqH H^r}>lWZM Hg> }0i"~"^JgNZ"e"fN|d wWlWpvlWdcHqWe}>db HZe"hHwWe"g cbr}>0e"xf> Hi"bJyWcgNlWf> Hd \HZe"^Jg n HZ"bJgvHZ"ZMH^]qW~"hWZ zbJc u]lWhHw$gNbJcHe"fN^r}&}<H^` H^JdbQe"hHw ^Je"e}>gN~"hWe"g¦a HZ"bJgNpve"hWlW^Jz Hg} ¡ e"gNe}IIu HccHlWf0bJdde"dcHe"Z"zoqWekHZ d[pT HgNl zbJc&n s Z"bJgNaHd{e"aa W^ a HZ"bJgNpve"hWlW^Jz HgNayW^cbJbJdzt^rqH n lW^rw}<} NtcHZQlWmo}>bJpTH^JbJZM H^` Hg}-pvlWg} pT Hf HZ 10 A x pT HgNl z^`HhWlWg
i"~"^rn hWhHqW~"d w}{£hHwWe"^Jpve"d&crq ^HhHwqHj~"g q bJgNgNZM}>~"fqWe 2 ¡ HZ0e"fNe"ze}>b 0 i"~"^rn hWhHqW~"d w&pT xobJpTH^JbJZM H^` Hg> Hf>o e"fNpv~"gNZ"e}>e"gNe"dHfNf> q bJhHw HZ"dtdc cHe"^J^7ulWhHwHcZ{xe"^J~"f}Q^Je"e}>gN~"hWe"gNgN~"hWe} {qW~"hWbJh¦pve"h WfNbJZ"Z"c dde"cje"hHw gNZ"e"fN|5pvy z > HZHuHZ u qH H^r}>lWZ"yWc}[dt^J^`&~"f}>~"cHe"d fNWhWZ"r} Nc uHpvb TgNZ"bJpvm^JeIxpvy zgNZ"e"fNae"d }>e"i<dbJcHbJ^`Hh 2 hHwOqHH^JyWgNr}>}>ykpve"hulWhHwHZ u qH H^r}>lWZ"yWbr}QqW~"hWbJhv&a HZ"bJgNlWdcrq ^ }<Hf} Ntc O e"hMNe"^JW^ Nc
WcHe}Mum~"^Jz Ht^*e"hH w MsBh H2^ ~"gjJhHwpv~"hHccHlWfUgNe"p q bJgNgNZ"c WcHe}5a HZ"bJgNaou*mlWZ"br}>rqi"~"^rn hWhHqW~"d we"hHw o}N}>}>y NtcqHHd ZHZvlWmo}>bJpTH^Jb s }< HgUcfNbr}>~"fNbJtpvlH}UbJgUpve"hHqH H^r}>lWZ}<} >o[pvbJdze"dde"p i"gNbJ^J^`HhWlWg[qH H^r}>lWZ"yWlWZ}<Hf}>lWZ"y i"~"^rn hWhHqW~"d we"hHw o}N}>}>yWdHcde"p mlWZ"br}>rq dHcTcHe"^J^^Je"ddbJeH Y gNZ"bJpvm^JeIxpvy zgNZ"e"f[pvbJdzcH~}[n HZ"bJg> Hd H^ TgNZM Hpvr}< HgNlWcO^Je"alWd wWlW^Jr}< Hg> }¦pve"hs cHWdd w r}>b7u e"hHwWe"d^Je}QfNe"dzgNZ"e"fNe"cTpve"hWlW^Jz Hg> Hd H^HgNZ"d H^r}}< Ha^` HZM}>lWgn lWfNpT HaHd
fNe"dze"Z"Z"cve"^HZ¦e"hHw o}N}>}>ykpT }>fNb xolH}Mu9NlWaaTlW^JzH^r} j b ~"g b qWe"c }>lWfNlWc}I ~"g Ti"~"^rn hWhHqW~"d we"hHw o}N}>}>yTqWe"c }>lWf>Hbr}5 c0 ~"gUHZ 10 A qWe"1c }>lWfNlWc2}M eqWe"Z"e}s Nc5pv~"h z ~"g t qH H^r}>lWZ"yWc}MuHpve"^rwWe"c&HZ0e"^Jg z^Je"hWe"g ~"gpT2 HgNl z^`HhWlWg i"~"^rn hWhHqW~"d w ~"f}>~"cH~}Un lWhM> HcNe"^JW^Jdb7 BhHw ]n e"^`Hz}¦n e"^r}>~}>e"^Jb e"hHwWe"d^Je}>e"bJe"Z5i"g>}>lW^ Ntcpv~"h ~"g¦ −z + c0 x = 0 −t + 10 Ax = 0 e"hHwWe"d^Je}>e"cHe}M Y −z ~"g −t qH H^r}>lWZ"yWc} bJ^J^Je}NqWe lWZ"ZM
Ntc¤}<Hf}>lWZ"y e ~"g lWgNZ"^JlWm qWe"c }>lWfNlWc}I pvbJdzbJhjUa HZ"bJgNaHd5n lWhMNtc}<Hf}<Hdb~"g JhHwkcHWdd w |Tm+1 ^` }>db7u em+2 lWhHwm~"^Jz Ht^ HZe"^Jg z^Je"hWe"g i"~"^rn hWhHqW~"d wgNlWf> HaHd5 0 0 B−1N qWe"c }>lWf Ne"^Je"dbJc pve"h e" }*a HZ"bJgNa ae"^J~"m ]qH H^r}>lWZ"yWdHc HZ e"^Jg 0n HZ"bJcgNaNH−c dHBZNWdjgNZ"yWaouWHpve"^rw e"Z mlWZ"br}>rqcHlWpvmlWde"dgU}<Hf}>lWZ"bJc −t gNlWf> HaHdvY pT HgNl zbJcn HZ"bJgNaHd¢HpvbJcHlWf −t gNlWf> } pT Hf¦e"^ bJg[^Je"e} HhHw dbA0HZ5&qH H^r}>lWZ"yT^J~"me} ae5Ta HZ"bJgNaouHpve"^rw bJcOde"p i"gNbJ^J^`HhWlWg~"g −z gNlWf>
HaHdmlWZ"br}>rqTcHl lWfNzbJd }< >qHHd Y}< Ha^` HZM}¦e"^Jg TlWgNZ"^JlWm HavTa HZ"bJgqH H^r}>lWZ"yWc}Mue"^Jg TgNlWf> HaTva HZ"bJgNlWdcrq ^Jb qH H^r}>lWZ"yWc}0JfANtc u5}< Ha^` HZM}¦e"^Je"pve"b-me"zbJhTHZHzlH}N}[a HZ"bJgNf>5qWlWd}>cHlWZ"ycHl lWfNzb s d }< Hc}[pkto}<} > Hc ]Y pvy zlWgNr}>lH}N}0dlWfNpT H^n e"^`Hz}[pve"hWlW^Jz Hg> }]}>e" }UHZkH^` Haab }< Ha^` HZM}>ayW^bJdzr} Ntc u1 ∗u2 −z −t x0 A1 b 1 A1 b 2 c0 0 0 1 A2 0 Y[Z u qH H^r}>lWZ"yWc}0pve"hWi"gNbJ^J^`HhWlWZ}>tcue"Z"Z"e"^ Ne"^Je"ZqWe0HZ}Mu lWhHw e"Z"e"cke"^JHhHwM> Hc a HZ"2bJg}Mu HccHlWfl zjpT Hf gNe"pvpvb
cHWfN^Jpv~"d wWe"c&cHWZ"H}N}Qde"p }>~"fNe}>de"c5q bJgNgNZMouoe"^ s ^Je"d }>~}>ae"dv }>WaaboqH H^r}>lWZ"yqHH^7uWHpve"^rwWe"ckHc Hf*}>WaagNZ"Wf bJg pve"e}>de"ckae0Ua HZ"bJgNa ¡ ~"gHhHw } > Hc5bJgHZ}e"^7 HZ¦e"^Jg n HZ"bJg qW~"hW~"djpT HgNl z^`HhWlWg i"~"^rn hWhHqW~"d wvlWm s }>bJpktpT Hd H^A qHH^`Hpve"dd w b i"gNbJ^J^`HhWlWgQqH H^r}>lWZ"yTe"^JHhHw}<Tva HZ"bJg}MuHccHlWfUHZe"fNe"ze}>b n e"^`Hz}¦e"hHw^Je"e}>gN~"hWe"g a HZ"bJgNpve"hWlW^Jz Hg> Hd H^qHHhHw tdc uHpve"^rw a W^-cbJbJdzt^rqH5pvlWg} pT
HfHZve"fNe"ze}>bi"~"^rn hWhHqW~"d wgNZ"e"fNbJd }n lW^rw}<} NtcHZTlWmo}>bJpTH^JbJZM H^` Hg}M HZve"^Jg n HZ"bJg0lWmo}>bJpT H^JbJgpve"hWlW^Jz Hg> HaHdqHH^`Hpve"^rwTi"gNbJ^J^`HhWlWgQqH H^r}>lWZ"y&mlWZ"br}>rqu HccHlWf[&n e"^ s Hz}>dHcTdbJdi"g0^Je"e}>gN~"hWe"g¦pve"hWlW^Jz Hg>o B^J^JtgNZ}>f> Hi"bJyWdHcvd~"Z"Z"c5cHqWe}>cHe"Z m~"^Jz }M x1 , x 2 , x 3 , x 4 , x 5 ≥ 0 3x1 + x2 + x4 + x5 = 13 x1 + x3 − x4 + x5 ≤ 7 2x1 + x2 + x3 + x4 − x5 = 17 6x1 + 3x2 + 2x3 + x4 − 4x5 − max Y[ZjbJdzt^Jyk}< Ha^` HZM}05cHqWe}>cHe"Z x1 x2 x3 x4 x5 ¡ 1 13 ∗u1 3 1 0 u2 1 0 1 −1 1 7 ∗u3 2 1 1 1 −1 17 −z 6 3 2 1 −4 0 −t 5 2 1 2 0 0 e"Zk}< Ha^` HZM}>lWZjHZjH^` Haaba
HZ"bJgNpve"hWlW^Jz Hg}<Hf}>lWZ"bJc x1 = x2 = x3 = x4 = x5 = 0 , u1 = 13, u2 = 7 , u3 = 17, z = 0, t = 0 U H^`HgNgNZ"tcOae"pve"d &qH H^r}>lWZ"yWdHcOHZ x Bs e}MY gNZ"|ccHe"fNe"gNZ}>pve}>gNZ"e} gNZM Hpvr}< Hg> s lWZ HZUH^` Haab Hd w HzlWgNlWc}]cH~"me"Z"Z"c ~"g uHpve"^rwWe"cvcHWZ"^ ¡ cbJgNe"aau }>e" } u ^Je"gNZvOcbJpve"d qH H^r}>lWZ"y { H^Jy > HaHd HZ (1, −1, 1, 1, 2) qWe"c }>lWfj^J~"m aeHu 4 ~"g¦HZ 13 1 1 (1, 0, 0, 0, 0) 17 1 ^J~"mcb7 kYhWe"de"f> H^Jy&e"^Je"pve}0ae"cHe"fNe}>e"Z}>c Y[Z ]}< Ha^` HZM}M x1 x2 x3 ∗u1 x5 x4 3 1 0 1 1 13 u2 4 1 1 1 2 20 ¡ −1 ∗u3 −1 0 −2 4 −z 3 2 2 −1 −5 −13 −t −1 0 1 −2 −2 −26
¡ YlWZ"ZM 5}<Hf}>lWZ"y&a HZ"bJgNpve"hWlW^Jz Hg" x1 = x2 = x3 = x5 = 0, x4 = 13, u1 = 0, u2 = 20, u3 = 4, z = 13, t = 26 lWg}{e"hHwW~"f}>e"^Jpk|ulWhHw&HZ x cHe"fN^ja HZ"bJgNaj~"g u e"^JHhHwM>jHZ} ¡ Hd w s 3 3 zlWgQcbJgNe"aaupvbJd }] H ¡ I Z"Z"e"^-pvbJdzcH~}]i"gNbJ^J^`HhWlWg qH H^r}>lWZ"ycbJcHe"fN^r}0ka HZ"bJgNayW^ ~"gQJhHwTcHqWe}>cHe"Z &}< Ha^` HZM}QHZ e"fNe"ze}>bn e"^`Hz}e"hHwT^Je"e}>gN~"hWe"gQa HZ"bJgNpve"hWlW^Jz Hg> } Hz >oYpT HgNl z^`HhWlWgQi"~"^rn hWhHqW~"d wgNlWf> }0pvlWg}0pT HfQcbgNe"p JfANtc x1 x2 ∗u3 ∗u1 x5 ¡ 0 1 1 13 x4 3 u2 5 1 −1 2 16 4 x3 −1 0 1 −1 −2 4 −z 5 2 −2 1 −1 −21 e"Zk}< Ha^`
HZM}>lWZ }<Hf}>lWZ"y5a HZ"bJgNpve"hWlW^Jz Hg x1 = x2 = x5 = 0, x3 = 4, x4 = 13, u1 = u3 = 0, u2 = 16 J^ e"e}>gN~"hWe"g"u zeOde"p lWmo}>bJpT H^JbJg"u bJgNZ"e"d HZ x ~"g x sBWZT}<Hf}>lWZ"yto}>lW^JgNygNlWfNae"^Jb e"^Je"pve"c mlWZ"br}>rqHHc u JhHwe"Z"e"c$a HfNpve"^rw bJcHeOae"1^J~"me}2 a HZ"bJgNao e"hHw c~"gNZ"fNeHu lWhHw¢HZ u H^`}N}^J~q to}>lW^JgNygNlWfNae"^Jb¦e"^Je"p bJgmlWZ"br}>rqu]zee"dde"c¢e"^J^Je"d~"fNe u 1 de"p ^J~"me}k aea HZ"bJgNaou*pvbrqWe"^ i"gNbJ^J^`HhWlWg qH H^r}>lWZ"yY[Z x s9}qH H^`HgNZ}NqHae"^J~"m 1 qH H^r}>lWZ"yWdHcHZ x n lWhM>TTa HZ"bJg[e"^JHhHw dbQ ¡ ¡ ¡
¡ ]~"2g TcHqWe}>cHe"Z upvlWg} 4 pT HfQlWmo}>bJpT H^JbJg }< Ha^` }0cHmNtc x1 x4 ∗u3 ∗u1 x5 x2 3 1 0 1 1 13 u2 2 −1 −1 1 3 3 x3 −1 0 1 −1 −2 4 −z −1 −2 −2 −1 −3 −47 aa W ^k}< Ha^` HZM}>ayW^^Je }>tz NtclW^rqHHgNdb-HZjlWmo}>bJpT H^JbJg{a HZ"bJgNpve"hWlW^Jz Hg}M x1 = 0, x2 = 13, x3 = 4, x4 = 0, x5 = 0, u1 = 0, u2 = 3, u3 = 0, z = 47 . Y Ng Z"bJpvm^JeIxpvy zgNZ"e"f& e"hHw bJco¦e"^Wd wWeHu-lWhHwHZkto}>lW^JgNyulWmo}>bJpT H^JbJg]}< Ha^` HZM}>ayW^* zt H^n e"^`Hz}0e"hHwlWmo}>bJpT H^JbJgpve"hWlW^Jz Hg> }]bJg0cb-}>tz NtclW^rqHHgNdb7 lWg} &a HZ"bJgNaHd ^J~q us9qH H^r}>lWZ"yWclWZ}<Hf}>lWZ"y[zt H^qH H^r}>lWZ"yWcU~"f}>~"cHeQ^Je"gNZ u}>e" } u = 0 uW¦a HZ"bJgNlWd crq ^Jb u qH
H^r}>lWZ"yWc[~"f}>~"cH~} HZto}>lW^JgNy0gNlWfNaHdde"h }>rq[e"^ Ne"^J^Je"^}<H^` H^ 2Ntc¦pve"h e" } u1 =¦W1,dd uwW3e"d = e"2^J^Je"d WfNbJZ"e} Nc u[lWhHw HZJhHw cHmlH}N}mfNbJpT H^ sBzt H^[pve"hWlW^Jz HgNm Hf cbJe"^J~"hWr}>b5ztH^Jbr}< HgNb}>~}>e"^Je"cHe}M ¡ VWC 4 RGIKJ M6KrC 3 CH@BR4 ¡ }< HfNlWZ"Z"tcpve"hOcHqWe}>cHe"Ze"hHwWe"d^Je}>fNe"dzgNZ"e"fNe"c H^r}<H^` HdlWg[pve"hWlW^Jz Hg> } e"^Je"pvba HZ"bJg}>f>HdgNZn lWfNpT Hi"bJyqHH^7 a x−y+z−u = 1 x−y−z+u = 0 −2x + 2y + 4z − 4u = 1 x +z+u = 2 x+y + u = −3 y + z + u = −1 }< HfNlWZ"Z"tc pve"h¤HZ ¡
n e"^`Hz}>aHdgNZ"e"fNe"m^¤e"hHwWe"d^Je}>fNe"dzgNZ"e"fNe"c qHH^` s pve"dd w b-a HZ"bJgNpve"hWlW^Jz Hg> } 0Y[ZH^` Haabe"hHwWe"d^Je}>fNe"dzgNZ"e"fTgNZMHaHzg> HhHn lWccHe}N} }< HfNlWZ"Z"tcpve"hHZ e"hHwWe"d^Je}>fNe"dzgNZ"e"fNae"d gNZ"e"fNe"m^ ~"g mHf>Hpv~}>e"fNe"c~"f}>~"cH~}MupTNzJfANtc n e"^-HZje"hHwWe"d^Je}>fNe"dzgNZ"e"f H^r}<H^` Hda,lWgb pve"hWclW^Jz Hg> }M x1 + x2 + 2x1 + x2 −x1 + ax2 x3 + x4 x3 + 2x4 + 3x5 + 2x3 − 2x5 − 2x3 + x4 + bx5 = = = = 2 1 2 c Jb Z"lWd w r}>gNtcUaeHuHlWhHwj¦e"hHwj^JbJdeM HfNbJg-e"hHwWe"d^Je}>fNe"dzgNZ"e"fNde"cqHHdcH~} c^JWd s
aWZmlWZ"br}>rq&pve"hWlW^Jz Hg>ou HccHlWfqHHdOHZ[e"hHwWe"d^Je}>fNe"dzgNZ"e"fNde"cde"p mlWZ"br}>rq pve"hWlW^Jz Hg>kbJg" }< HfNlWZ"tcTpve"hv5cHqWe}>cHe"Z OpT }>fNb xolWcvbJd qWe"fNZ"~}[e"^Je"pvba HZ"bJg}>f>HdgNZn lWfNpT s i"bJyqHH^7 1 1 2 0 1 1 1 1 3 a −2 5 1 3 −1 4 2 0 7 i 1 1 1 1 1 1 −1 −1 1 −1 1 −1 1 −1 −1 1 ^Jz Ntcpve"hT&gNZ"bJpvm^JeIxpvy zgNZ"e"fNfNe"^ HZH^` Haab-^JbJdeM HfNbJgQmfNlWhWf>HpvlWZM HgNbn e"^ s Hz}>lWc}M a) x 1 , x2 , x3 , x4 , x5 ≥ 0 x1 + 2x2 + 3x3 + x5 ≤ 100 x2 + x3 + x4 + x5 ≤ 80 x1 + x3 + x4 ≤ 50 2x1 + x2 + 3x3 + x4 + 2x5 − max ¡ b) x 1 , x2 , x3 , x4 ≥ 0 x1 + x 2 + x 3 ≤ 8 2x1 − x2 +
x4 = 12 7x1 + 3x2 + 4x3 + 6x4 − max c) x 1 , x2 , x3 ≥ 0 x1 + x2 + 2x3 ≤ 5 2x1 + x2 + x3 ≥ 2 BfANtcn e"^¦ x1 + x2 + 3x3 − max n e"^`Hz}>aHd¤gNZ"e"fNe"m^ sBc$zt H^JbJg>Hbr}&~"gT}< HfNlWZ"Z"tc$pve"h HZlWmo}>bJpT H^JbJggNZ"bJpvm^JeIx }< Ha^` HZM}>lWcayW^]zt H^JbJgkn e"^`Hz}>lWce"hHwlWmo}>bJpT H^JbJg a HZ"bJgNpve"hWlW^Jz Hg> }M bJZ"lWd w r}>gNtcaeHu{lWhHwe"hHw^JbJdeM HfNbJgmfNlWhWf>HpvlWZM HgNb{n e"^`Hz}5^Je"e}>gN~"hWe"g }<Hf}>lWpT Hd w jde"pkfNe"g~"g{cHlWfN^` }>lWg"u HccHlWfQjzt H^JbJg> HdHc5^Je"e}>gN~"hWe"g{}<Hf}>ls pT Hd w 5de"p cHlWfN^` }>lWg" ¡
HgM0HZH^` Haab}>t^`NzlWdg> HhWlWccH^7 bApvbJdze"d x, y ∈ V sBfNeH x ⊕ y = y ⊕ x cHlWpvpkto}<}>brq br}< Hg<Iu bJbATpvbJdze"d x, y, z ∈ V sBfNeH x ⊕ (y ⊕ z) = (x ⊕ y) ⊕ z HgNgNZ"l i"b`}>brq br}< Hg<Iu bJbJbA&qHHdlW^rw Hd θ ∈ V uHpve"^rw fNe x ⊕ θ = x pvbJdze"d x ∈ V sBfNeHZWgNgNZ"eMHz HgNf> d~"ZqWejqHHd V sBae"dde"to}>f> H^JbJgQe"^Je"pIu brqOpvbJdze"d x ∈ V sBe"ZqHHdlW^rw Hd −x ∈ V ulWhHw x ⊕ (−x) = θ pvbJdze"d sBae"^Jbe"^Je"pvde"cvqHHdHzzbr}>rqTbJd qWe"fNZ"eI V f}>e"^Jpve"ZqWeqHHdpv~"he"hHwpk|oqWe"^Je} u[Hpve"^rwWe}gNcH^` HfNf>H^0qHH^JygNZ"lWfNZM HgNdHc rq tdc~"gHpve"^rwpvbJdze"d (α,
x) m HfNlWZHu&HlW^ α ∈ R e"hHwqHH^JyWggNZM Hp~"g u{e"hHw α ⊗ xsBe"^Ne"^JW^r} V sBae"^Jb{qWe"c }>lWf}TfNe"dze"^HZ x qWe"c }>lWfvgNcH^` HfNgNZ"lWfNls x ∈ V g> }I~"g[Hpve"^rw de"cHZH^` Haab}>t^`NzlWdg> Hh HbqHHddHc bJdze"d α, β ∈ R ~"g x, y ∈ V sBfNeHu α ⊗ (x ⊕ y) = (α ⊗ x) ⊕ (α ⊗ y) u a (α + β) ⊗ x = (α ⊗ x) ⊕ (β ⊗ x) u i (αβ) ⊗ x = α ⊗ (β ⊗ x) u z 1 ⊗ x = x ~"^Jz HcTqHH^JyWgqWe"c }>lWf}>e"fNe"cfNeH ¡ 0Y¢qHH^JyWg gNZM Hp nsBe"gNe"ck}>e"fNe nsBzbJpve"dZ"bJyWg*cHl lWfNzbJd }<}>~"f<Iu jHZ]WgNgNZ"eMHz Hg} ~"ggNcH^` HfNf>H^[qHH^JygNZ"lWfNZM Hg}cHlWpvmlWde"dgNe"dcH~"d }ze£db` H^
Ntc¤~"g$i"gNtm sBayW^ H^J^JykgNZM Hp nsBe"g¦HZUWgNgNZ"eMHz Hg[de"to}>f> H^JbJgQe"^Je"pveHu ¡ "e hHwWe"d F HZ [a, b] bJd }>e"fqHH^J^JtpvlWdk~"f}>e"^Jpve"Z"e}N}qHH^JyWg*n hWhHqW~"d wWe"c5H^JpTHZMo Y[Z[WgNgNZ"eMHz Hg}]~"gQgNcH^` HfNf>H^qHH^JygNZ"lWfNZM Hg}Q~"f}>e"^Jpve"Z"Z"cvcHqWe}>cHe"ZvcH~"m s me"d pvbJdze"d f, g ∈ F u α ∈ R ~"g x ∈ [a, b]sBfNej^Je"hHwWe"d (f ⊕ g)(x) = f (x) + g(x), (α ⊗ f )(x) = αf (x). Y[ZWgNgNZ"eMHz HgTde"to}>f> H^JbJg5e"^JpveOHZHZ"lWdlWg>Hd¤dt^J^`n hWhHqW~"d wW¦Wdd w |¤ae"^` }>db7u lWhHw F HZUJhHwze£db` H^r}]pk|oqWe"^Je}>e"ccHe"^qHH^JyWgQqWe"c }>lWf}>e"fNe} H^JcHlH}M Y }>lqH
Haab`HcaHd i"g>Hcde"p pvbJdzbJhqHH^JyWgTgNZM Hp nsBe"gNe"c¤}>e"fN~qWe"^[n lWhW^`H^JcHls Z"tdc~"g5de"p lWcHlWZOpTNz n ~"^JfNe"~"f}>~"g}Mu HZOe"hHw gNZ"e"fN|gN~"hcHe"zoqW~"~"f}qWe"c }>lWfNlWc WgNgNZ"eMHz Hg> Hf>5~"gQgNcH^` HfNf>H^ qHH^JykgNZ"lWfNZM Hg> Hf>5kHhHwWlWpT Hd wWlWg"uqHH^JyWggNZM HpvlWcvcHs fN~"ae"d pve"hWgNZ"lWcHlH}N } gNZ"bJpkayW^JtpvlH}jbJ^J^Je}NqWeTHZTe"hHw pT Hgpve"^J^J~&Jf> Hg}HgNZ"d H^ Ntc Y qWe"c }>lWfNlWc}UqHHg}<HhOae}>|oqWe"^7u-de"to}>f> H^JbJg e"^Je"pve}Mudt^J^ s9qWe"c }>lWf} os9qHH^n lWhMNtc Ne"^JW^Jdb7 e"hHwWe"d V e"hHwqWe"c }>lWf}>~"f"u v , . , v ∈ V ~"g α , ,
α ∈ R TY[Z α v + WgNgNZ"e"hWe}Q G = {v , 1. , v }n qWe"c }>lWfNfNe"dz1gNZ"e"f α ,n , α gNcH^` HfN1lWc1cH^ .cH~"m+ α n vn Z"e}N} K 2AE6>FHGI2J;Q4 RSvL"2AEF 27 "FH1EC 4 rqMNntc ¦eqWe"Z"Z"cv G qW1e"c }>lWfNfNe"ndzgNZ"e"f K 2AE6>F GI2J;L G>4WFHEC 4 ~"g Ne"^JW^ Nc5^JbJd (G)s9qWe"^ G qWe"c }>lWf>HbJdHcvWgNgNZ"e"g0^Je"e}>gN~"hWe"g]^JbJdeM HfNbJg cHlWpkabJd Hi"bJy > }M ¦Wdd wWe"d¤^` }>}>yulWhHw^JbJd pTHh bJgk^JbJdeM HfNbJg}>~"fH^r}>~"f< V sBae"d$ze£db` H^r}5pk|oqWe"^Je}>e"ccHe"^¦~"g&de"to}>f> H^JbJgk(G) e"^Je"pvpve"^7Y G = {v , . , v } 1 n qWe"c }>lWfNfNe"dzgNZ"e"f} K
2AE6>FHGI2J;MCH E W886@KJ6EE6<4 deqWe"Z"Z"c u α1 v1 + . + αn vn = 0 =⇒ α1 = = αn = 0 ¦Wdd wWe"dae"^` }>}>yu lWhHwU ^JbJdeM HfNbJgn hWhWe}>^Je"dgN~"h0n e"d }>b ze£dJi"bJy > MqHH^We"c q brqHH^Je"dg HZjH^` HaabcH~}[ze£dJi"bJy ¡ bJdze"d v ∈ ^JbJd (G) e"hHwW~"f}>e"^Jpk|e"d H^J^Jr}>}>yve"^ G qWe"c }>lWf>HbJdHc^JbJdeM HfNbJg cHlWpkabJd Hi"bJy >HcH~"d }M G e"hHwWe}>^Je"djqWe"c }>lWf> gNe"p n eBNe"Z"e} 0cb}>WaabJe"c[^JbJdeM HfNbJgcHlWpkabJd Hi"bJy >HcH~"d }M Yze£dJi"bJy&d~" Hd we"hHw gNZ"e"fN|cHqWe}>cHe"Z"pv~"d wWeH ¡ bJdeM HfNbJg>Hdn hWhWe}>^Je"d
fNe"dzgNZ"e"fde"p }<Hf}<H^JpTHZ"}jHZ"lWdlWgjqWe"c }>lWfNlWc}~"g 5dt^J^qWe"c }>lWf}[gNe"p 0Y[Z e"hHwWe}>^Je"dde"pvZ"~"fNy5qWe"c }>lWf}]}<Hf}<H^JpTHZ"yqWe"c }>lWfNfNe"dzgNZ"e"f¦^JbJdeM HfNbJg>Hdvn hs hWe}>^Je"d Jb deM HfNbJg>HdOn hWhWe}>^Je"dOqWe"c }>lWfNfNe"dzgNZ"e"f pvbJdze"dfN~"gNZ"fNe"dzgNZ"e"fNekbJg0^JbJdeM HfNbJg>Hd n hWhWe}>^Je"d hHw G qWe"c }>lWfNfNe"dzgNZ"e"f}O V qWe"c }>lWf}>~"f 86E6GNFH@BRGIG>6E3 ;>= 6G>:E6<4 rqMNtc u ^JbJd hHw qWe"c }>lWf}>e"fNe} 3H2AST6E ="27;EC 4 deqWe"Z"dc u{qHHd qWe"c }>lWf} V }<Hf=}<H^JpTHZ"(G)
yhWe"de"f> }>lWfNfNe"dzgNZ"e"fNeHuHzne a HfNpve"^rw nsBd~"^WcHeqWe"gNe"aaqWe"c }>lWf}}<Hnf}<H^JpTHZ"y qWe"c }>lWfNfNe"dzgNZ"e"fNeUpT Hf de"p hWe"de"f> }>lWfNfNe"dzgNZ"e"f" hHw V qWe"c }>lWf}>~"f G qWe"c }>lWfNfNe"dz s gNZ"e"fN~} L<F="2J;EC 4 cHl lWfNzbJd }<HfNe"dzgNZ"e"fNde"co]deqWe"Z"Z"c u G ^JbJdeM HfNbJg>HdTn hWhWe}>^Je"d hWe"de"f> }>lWfNfNe"dzgNZ"e"f" ¦qWe}>cHe"Z"pv~"d wWe"c ¡ bJdze"d qW~"hWe"gOzbJpve"dZ"bJyWg5qWe"c }>lWf}>~"fa HfNpve"^rw qWe"c }>lWf>e"hHwW~"f}>e"^Jpk|e"d cb s n eBNe"Z"e} $a
HfNpve"^rw¤a HZ"bJg> HdHc¤^JbJdeM HfNbJgvcHlWpkabJd Hi"bJy >HcH~"d }M Y pve"hHn e"^Je"^ gNZ"lWfNZ"yWc} C=kC 3R@@QL<F="2J;GNCv1HRECH@A4 RM= k4 RRGN3H2AEFH@9F 4EC 4 deqWe"Z"Z"c 0YqHH^JyWg]gNZM Hp nsBe"gNe"c}>e"fNe n zbJpve"dZ"bJyWg" hHw nsBzbJpve"dZ"bJyWgqWe"c }>lWf}>~"fa HfNpve"^rw^JbJdeM HfNbJg>Hdn hWhWe}>^Je"d qWe"c }>lWfNfNe"dz s gNZ"e"fNecbJe"hW~"gNZ"r}>e} &a HZ"bJgNg> o qWe"cWs ZM HpvlWgjmfNlWa^J~"pTpve"hWlW^Jz Hg>gNlWf> HdgNZ"cgN~"hWdc qHHdHfNf>oulWhHw V }>lWf}>~"f e"hHwkHzlH}N}a HZ"bJg> HfNyW^o }N}>~"fANdce"hHwkpT HgNbJcja HZ"bJgNf>o
e"fNpv~"gNZ"e}>e"gNe"dve"ZM H^r}<H^ a HfNpve"^rwqWe"c }>lWf e"gNe}>~"ae"d cHl lWfNzbJd }< HcbJgpve"h n lWhWdHcqH H^r}>lWZ"db7 BhWe"dve"hHw gNZ"e"fN| HZ cHl lWfNzbJd }< HcdHcj¦cbJgNZM Hpvr}< Hg>ou [HZ *a HZ"bJg fN~"hWbr} W^ i"g>Hce"hHwWe}>^Je"dqWe"cWs }>lWfNaHdc^JWdaWZ"bJc Y a HZ"bJg[pve"hHqH H^r}>lWZ}<}< Hg> }[e"ccHlWf 6KJ6S52QL<F="2J;@GNCHEo;>= MRGISvF 27EC 4 deqWe"Z"Z"c e"hHwWe"de"c B = {b , . , b } V nsBzbJpve"dZ"bJyWgqWe"c }>lWf}>~"f]e"hHw a HZ"bJg>O~"g c 6= 0 e"hHw}>e}>gNZ W^Je"hWe"gjqWe"c 1}>lWf"u*Hpvne"^rw de"c B
sBfNe5qWlWd}>cHlWZ"ycHl lWfNzb s d }< Hb ~"gQ}>e"hHw cvn e"^7uolWhHw e"hHwWe"dO}>lqH Haa e"hHwT}>e}>gNZ W^Je"hWe"g qWe"c }>lWf"cu1 ,H.pv e",^rw cdn e"c B sBfNejqWlWd}>cHlWZ"yTcHcl klW6=fNzbJ0d }< Hb x , , x xccHlWf b qWe"c }>lWf cbJi"gNe"fN~"^Je} cs9qWe"^~"g{HZ a HZ"bJg B 0 = {b , . , b 1 , c, b n , , b } kHe"^JW^ Nc s9qHH^-HZ x Hd w HzlWg}M ccHlWf[HZ x qWe"c }>1lWf B 0 a Hk−1 Z"bJgNf>kqWlWk+1 d}>cHlWZ"yTcHnl lWfNzbJd }< Hb7 δ k ck x1 − δc1 , . , xk−1 − δck−1 , δ , xk+1 − δck+1 , , xn − δcn Y gNZM HpvlH} 86E6GNFHKJ6KJ6S5E6<4 deqWe"Z"Z"c &Y[Z5e"^ WaabJe"cH^`Hm> Hdpve"h H^J^` s mr}>ck}>6=yu0lWhHwa
HZ"bJgNaae"^J~"m qWe"c }>lWfNdHca HZ"bJg}e"^JHhHwWyqWe"c }>lWfNf>qWlWd}s cHlWZ"ycHl lWfNzbJd }< >vjhWe"de"f> H^Jyje"^Je"p dt^J^` }>yW^c^JWdaWZcHe"^J^^Je"hHwWe"d ¦Wdd wWe"d ^` }>}>yu{lWhHw$e"ZgNZ"cgN~"hWe"gO~"gTe"^J~"hWgN~"hWe"gvn e"^r}>~}>e"^JeHddHc u]lWhHw HZe"^Je"pvb]a s Z"bJg}>f>HdgNZn lWfNpT Hi"bJykqW~"hWfNe"}>}>yv^Je"hHwWe"d lWcgNZ"lWf n lWd }>lWg }>tzdb m^7 pT }>fNb xolWc bJd qWe"f}< H^` Hg> Hd H^7uH¦gNZ"bJpvm^JeIxjpvy zgNZ"e"fNd~"^A ja HZ"bJgNayW^~"mme"dTcbJcHe"fN^r} b qWe"c }>lWfNdHcvHZ a
HZ"bJgNf>UqWlWd}>cHlWZ"ykcHl lWfNzbJd }< Hbr}M k u x = 1, x = 0, . , x = 0 g JhHw b sBdHcHZ ccHlWf x = 0, . . . , x = 0 1 k−1 k+1 n k ]a HZ"bJgNf>kqWlWd}>cHlWZ"yTcHl lWfNzbJd }<k Hb7 HlW^ −δc1 , . , −δck−1 , δ, −δck , , −δcn , a Hfs pve"^rw bJcpT HgNbJca HZ"bJgNao Z} &}>e"i<dbJc }[^Je"e}[HgNZ"d H^Jdb HZtd 4 RS[PCH@2L"2AK 2A@9F ; 12r=I;>8 FHKrCH@GNC e"hHw cn e"^7ulWhHwHzlH}N}Ue"hHw G = {a , . , a } qWe"c }>lWfNfNe"dzgNZ"e"fkHZ sBzbJpve"dZ"bJyWg0qWe"c }>lWf}>~"fNae"du}>lqH Haa OHZ nsBzbJpve"dZ"1bJyWg0qWe"c }>klWf}>~"fUe"hHw b qWe"c }>lWf>o n Y[Z}jgNZ"e"fNe}>d~"dc e"^JzWd }>e"db7u-lWhHwn e"dd H^J^ sBek
b ∈ ^JbJd G }<Hf}<H^JpTHZM Hg"uqHHhHw bJg b cbrn eBNe"Z"e}sBe qWe"c }>lWf>HbJdHcTqHH^`HpvbJ^rwWe"dO^JbJdeM HfNbJgQcHlWpkabJd Hi"bJy >HcH~"d }M e"hHw c n e"^7ulWhHw b cHl lWfNGzbJd }< Hb B = {e , . , e } e"hHw gN~"hHqWe"c }>lWfNlWckH^JcHlH}N}<¦a HZ"bJgNf>5HZ td @GI2A12FHK 2J;kL<F="2J;GNC qWlWd}>cHlWZ"dH1c u }>e" } n b = b e + . + b e Y[^`Hcr}>gNtc } pvlWg}Qn lWcHlWZM}>lWg>HdupvbJdzbJhke"hHwqWe"c }>lWf}¦cbJi"gNe"fN~"^rqW1eT1 e"^Je"pvba HZ"nbJg}>nf>HdgNZn lWfNpT Hi"bJyH} }NqHQqW~"hWfNe- B a HZ"bJg} hHwWulWhHwU G qWe"c }>lWfNfNe"dzgNZ"e"f qWe"c }>lWf>Hb cHWZ"^ ^Je"e} W^Je"h pvbJd~"^}>Waae}¦qWlWd
Ntdcaekva HZ"bJgNao e"fNpv~"gNZ"e}>e"gNe"dmlWd }>lWg>HdHdd w br}¦}>tztdc aeqWlWddb7uHpve"dd w b O^JbJd (G) H^r}>~"f zbJpve"dZ"bJy >ouHpvbr} G GNCHE 8 "FHEC 4 bJgUdeqWe"Z"eIs }>dc G f>HdhM> r ~"g}>Wf}>~"de}>e"gNe"d a , . , a ^JbJdeM HfNbJg>Hd&n hWhWe}>^Je"de"c ^JbJd G e"hHwa HZ"bJg> }[Hz > HcoIu Hpve"^rwWe"cHe} HZ e , . 1 , e qWe"rc }>lWfNlWccH^ i"gNe"fN~"^r}>dcn e"^7u HccHlWf HZe"^Je"pvb¦a HZ"bJg}>f>HdgNZn lWfNpT Hi"bJyWcgNlWfNlW1 ZM}<e"rhHw H = {a , . , a , e , , e } a HZ"bJg}e"fNe"zpv~"d wWe"Z"e}N}M Y b qWe"c }>lWfNdHcHZe"fNfNe ¤a H1Z"bJgNf>$qWlWrd}>r+1 cHlWZ"y
cHl lWnfs zbJd }< Hb0^Je"hHwWe"de"c d0, . , d0, d0 , , d0 d0 = = d0 = 0 u0HccHlWf 1 u qHHhHw rbJg r+1 ^JbJd n u r+1 qHH^`Hpve"^rw n 0 0 0 b = d a + . . . + d a b ∈ (G) d = 6 0 j 1 r e"gNe}>~"d1u]HccHlWf b ∈/r ^JbJd (G) e"hHw c~"gNZ"fNeHu]lWj hHw$ cHlWpvm}>bJabJ^J=br}< Hrg+q 1,bJZ"gN.h H ^`,n} }>t^`NzlWdcH~"mme"dHddHcO5pve"h H^J^`Hmr}< Hg>oulWhHwHZ 1 δ^Je"= pvbHcak HZ"bJg}>f>HdgNZn lWfNpT Hi"bJyWc0gNlWfNlWZM}< MqHH^Wa HfNpve"^rw[a HZ"bJgNayW^W }N}>~"fNe}>dc x 1 a1 + . + x k ak = b ^JbJdeM HfNbJg e"hHwWe"d^Je}>fNe"dzgNZ"e"fNde"cTqHHd sBe0pve"hWlW^Jz Hg>o U qHHduoHccHlWf{e"hHw o}N}<H^ pve"hbJg }< HfNlWZ"tdce"hHwWe}M x0 = (d01 , . , d0r , 0, , 0)
Y[Ze"hHwWe"d^Je}>fNe"dzgNZ"e"fUe"hHwbJ^rwWe"d 0 pve"hWlW^Jz Hg> }MuHpve"^rw ae"dHZ 0 de"p5sBdt^J^` cHlWpvmlWde"dgNe"bJe"Z}<Hf}>lWZ"yqWe"c }>lWf>Hb x G qWe"c }>lWfNfNe"dzgNZ"e"fNde"c^JbJd x(G) a HZ"bJg> } H^JcHlH} > Hc u L<F="2J;ST698RKr3 F ;EC 4 deqWe"Z"Z"c G pTHh a HZ"bJg"u]HccHlWfv^JbJd (G) HZ e"hW~"gNZ nsBzbJpve"dZ"bJyWgUqWe"c }>lWf}>~"f~"gk^JbJdeM HfNbJgUe"hHwWe"d^Je}>fNe"dzgNZ"e"fNde"c i"g>Hc e"hHwWe}>^Je"d pve"hWlW^Jz Hg>TqHHdjHZ&e"fNfNeva HZ"bJgNf>qWlWd}>cHlWZ"ycHl lWfNzbJd }< Hc 5Y cHlWpvm}>bJabJ^Jbr}< Hg q bJZ"gNh H^`}kpT
HgNbJcHgNZ"dlWg&pve"^J^J~"c }>e"fNpv~"cHeHulWhHw e"hHw o}N}<H^Qpve"hW}< HfNlWZ"Z"tc G qWe"c }>lWfNfNe"dzgNZ"e"f0f>HdhM> }QbJg"¦~"Z"Z"dcpvlWg}Qe"hHwTm~"^Jz }]cHlWpvm}>bJabJ^Jbr}< Hg q bJZ"gNh s ^`}>f>o e"hHwWe"d a1 a2 1 1 G= 2 1 1 , −1 3 0 a3 a4 a5 1 1 1 −1 1 1 , 1 , 0 , 1 0 1 2 b 9 4 1 5 Y gNZM Hpvr}< HgNlWc}Ui"~"^JgNZ"e"fN| }< Ha^` HZM}>lWg n lWfNpT HaHde"^rqW~"hWe"Z"db75Y }< Ha^` HZM}Ue"^Jg lWgNZ"^JlWm HaHd5HZ0Hc }>t H^JbJg*a HZ"bJgqWe"c }>lWfNlWc} }>d }>e} Ncn e"^7uWHZ]e"^Jg
UgNlWfNaHd& a HZ"bJgNlWd crq ^Jb qWe"c }>lWfNlWc}Mu }< Ha^` HZM}Uae"^JgNeBN~"ae"dme"zbJhOa HZ"bJgNlWd crq ^Jb*qWe"c }>lWfNlWcdHc HZvHzlH}N}ja HZ"bJgNf>OqWlWd}>cHlWZ"ycHl lWfNzbJd }< Hbr}MkY[Z jcHl lWfNzbJd }< Hc}jHZ&e"^Je"pvb a s Z"bJg}>f>HdgNZn lWfNpT Hi"bJy5gNZMHa H^rw MqHH^}< HfNlWZ"Z"tcOpve"h Bdzt^Jy5}< Ha^` HZM}M ¦e"pka HZ"bJgQqWe"c }>lWfNlWc ¡ ¡ a1 H Z"bJg qWe"c }>lWfNlWc e1 e2 e3 e4 ¡ ¡ a4 a5 ¡ ¡ ¡ a2 a3 ¡ −1 −1 ↓ ¡ ¡ ¡ b ¡ ¡ ¦l lWfNzbJd }< Hc Y[Z a , . , a qWe"c }>lWfNlWccHWZ"^¦a HfNpve"^rw bJcae"^J~"me} a HZ"bJgNa b qWe"c }>lWf} a HZ"bJgN1lWdcrq 5^ }<Hf} Ntc
Iu*HfNf>cHe"^J^ i"g>Hc hHwWe"^Jddc u lWhHw hWe"de"f> H^Jye"^Je"p HZT cHl lWfNzbJd }<ouHpve"^rw&a HZ"bJgNaae"^J~"m ~"gQa HZ"bJg}{e"^JHhHwWyqWe"c }>lWfUpve}>gNZ"~"gNmlWd }s > HaHdqHHd s9}>yW^*c^JWdaWZ"Z"~"c U H^`HgNgNZ"tcm^7kOae"cHe"fNe}>e"Z"e}N} ¡ sBe"g}jhWe"de"f> H^Jy e"^Je"pvde"c ZOHZ}¦Ne"^Je"d }>b7u lWhHw HZ e qWe"c }>lWf5e"^JHhHwM>a HZ"bJg}5~"g a cHe"fN^] 1 e"^rwW~"fNeHYgNZM Hpvr}< HgNlWc}i"~"^JgNZ"e"fN| hHwT e"^rqW~"hWe"Z"db7uolWhHwve"^ WgNZ"WfQhWe"de"f>1 H^Jyke"^Je"p gNlWf> }
qW~"hWbJhWlWgNZ} NtchWe"de"f> H^JyOe"^Je"pvpve"^7 ccHlWfjpvbJdze"dupv~"hOa HZ"bJgNlWdcrq ^ pTHf>Hzo}UqWe"c }>lWfNf>pve"hWcHmNtc δ 5 Hd w HzlWg}M Z"Z"e"^{HZ}< Hd hWe"de"f> H^Jye"^Je"p lWgNZ"^JlWm }kpve"hWgNZ"lWfNlWZ"Z"tc~"g&HZbJ^J^Je}qWe"c }>lWf&lWgNZ"^JlWm HayW^HZJhHwcHmlH}N}kqWe"c }>lWf} cbrqWlWd Ntc BhHw5cHqWe}>cHe"Z }< Ha^` HZM}>lWcvgNlWfNlWZM}< }0cHmNtc a1 e2 e3 e4 a1 a2 e3 e4 a1 a2 a4 e4 a2 ¡ a3 a4 a5 s¡ ¡ −3 −2 −3 −3 −1 −1 −2 −1 −14 −8 −1 −22 a3 −2 a5 ¡ 1 ¡ ¡ a3 −2 −3 a5 a4 ¡ ¡ b b −5 14 H H b −5 −6 H −1 YgNZM Hpvr}< HgNlWc}]de"p }>tz NtcT}>lqH
Haan lW^rw}<}>db7u bJgNZ"e"d e sBe}0de"p ^Je"e}¦gNe"p sH^7ugNe"p a sBe"^cbJi"gNe"fN~"^Jdb7 brqWe"^ bsBde"cvHZ e sBfNe¦qWlWd}>cHlWZ"y54 cHl lWfNzbJd }< > u b a 4 n e"3^JJfN}>y5HZ5H^` Haabpvy zlWd b = −5a1 − 6a2 + 20a4 . dde"ce"^rwWe"gNgN~"hW~"f W^ pve"hbJgUhHw WZ ze}>dc vY G qWe"c }>lWfNfNe"dzgNZ"e"ff>HdhM> ~"g ^JbJd (G) b∈ bsBde"cHZ e4 sBfNe qWlWd}>cHlWZ"y cHl lWfNzbJd }< >¦dt^J^` }>yW^Wc^JWdaWZ ^Je"ddeHuWHccHlWf ^JbJd ^Je"ddeH b∈ / Z"Z"e"(G) ^jgNZM Hpvr}< HgNg>H^e"hHw o}N}<H^ pve"hW}< HfNlWZ}>tc5jcHqWe}>cHe"Z5e"hHwWe"d^Je}>fNe"dzgNZ"e"f e"hHw a
HZ"bJg<pve"hWlW^Jz Hg> }M x1 + x 2 + x 3 + x 4 2x1 + x2 − x3 + x4 x1 − x 2 + x 3 3x1 + x4 + x5 + x5 + x5 + 2x5 = = = = 9 4 1 5 Y[Z u u u u i"g>HcthHw Hd e"hHwa HZ"bJgNpveIs hWlW^Jzx H1g"*=Y[−5 fNfNyW^7ux2lWhH=w&−6 pve"hWlW^Jxz3 H=ge"0hHw gNZ"xe"4fN|O=a20 e"e"^rwWxe5}N}>=e"gN0r}>~"gNgNe"^hHw WZ ze}>dc&pve"h Y[Z} me"zbJhu lWhHwa HZ"bJgNpve"hWlW^Jz Hg¦HaayW^ ^` }>} Ntc u lWhHwHZ x , x , x de"pvdt^J^` qH H^r}>lWZ"yWclWZ }<Hf}>lWZ"y a , a , a qWe"c }>lWfNlWcO^JbJd (G) a HZ"bJg> }¦H^JcHlH1} > Hc 2 4 5n e"d }>be"hHwWe"d^Je}>1fNe"d2zgNZ"4e"fNde"cde"pvi"g>Hcve"hHwpve"hWlW^Jz Hg> }gNZ"e"fNe}>d~"dcOpve"hs
}< HfNlWZ"db7u Hde"p qHH^`Hpve"dd w br}MuoHccHlWf]bJge"^Je"hWe"dz vn e"d }>bcHlWpvm}>bJabJ^Jbr}< Hgq bJZ"gs h H^`}>lH}[e"^rqW~"hWe"Z"db7Y cHlWpvm}>bJabJ^Jbr}< Hg]q bJZ"gNh H^`}Ue"fNe"zpv~"d wWe"cH~"d }thHw HdbJg GsBde"c a HZ"bJgNaaede"p cHe"fN^r}TqWe"c }>lWf>HbJdHc H a HZ"bJgNf> qWlWd}>cHlWZ"ycHl lWfNzbJd }< Hbr}&bJg pve"hW}< HfNlWZ}>tc e"hHwWe"de"ce"Z"e"c dj (i = 1, . , r; j = r + 1, , k) qHHhHw bJg i aj = dj1 a1 + . + djr ar ccHlWf[HZUe"hHwWe"d^Je}>fNe"dzgNZ"e"f[JhHwbJg]JfN}>y brqWe"^ j = r + 1, . , n r+1 a1 x1 + . + ar xr + dr+1 1 a1 + . + dr ar xr+1 + + dk1 a1 + . + dkr ar xk = d01 a1 + + d0r ar H a
HZ"bJgNf>kqWlWd}>yvcHl lWfNzbJd }< HcTe"hHwW~"f}>e"^Jpk|e"c u e"Z"~"f} xi + dr+1 xr+1 + . + dki xk = d0i i (i = 1, . , r) xi = d0i − dr+1 xr+1 − . − dki xk i (i = 1, . , r) qHHhHwO }>fNe"dze"ZqWe Y[Z x , . , x qH H^r}>lWZ"yWc} 4 /@B/@@L<F="2J;U1FHK @BRM= 4 dHc u HZ x , , x qH H^r}>lWZ"yWc} ^r}>lWZ"yWcdHck }>e}>gNZW^Je"hWe"g ;>=C L<C 13 E6SvrL<F="2J; 1FHK @BRM= 4EC 4 deqWe"Z"Z"c Y gNZMHaHz qH Hr+1 ~"f}>~"cHe}HzoqH~"gvHZ}< Hd cHH}>H}N}&qH H^r}>lWZ"yWc}5n e"d }>bQn lWfNpkt^` MqHH^cbJgNZM Hpvr}NqHHZ e"hHwWe"d^Je}>fNe"dzgNZ"e"f0e"hHwTpve"hWlW^Jz Hg> }U PCHGI@2J4 KrFHGI2J;UST698RKr3 F ; cHmNtcv~"g0HZ
e"hHwWe"d s ^Je}>fNe"dzgNZ"e"fQpvbJdze"dTpve"hWlW^Jz Hg>je"^ H^J^Jr}>}>y bJ^rw5pvy zlWd gNZMHaHz de"pka HZ"bJg< qH H^r}>lWZ"yWcdHcdt^J^`U~"f}>~"cHe}QHztdc uoHccHlWf{HZ0JhHwkcHmlH}N}[ mHf}>bJct^` HfNbJg< pve"hWlW^Jz Hg e"hHwOa HZ"bJgNpve"hWlW^Jz Hg" Y gNZM Hpvr}< HgNb*e"^ > Hf> HgUthHw HdHZHupvbJd }UOcHlWpvm}>bJabJ^Jbr}< Hg]q bJZ"gNh H^`}>d H^7 Z"lWc Hg HZ"lWdaHd bJ^rwWe"dcHlWfkqWe"c }>lWfNlWc}&lWZ"ZM }<Hf}>lWZ"yqH H^r}>lWZ"yWccH^ fNe"mfNe"Z"e"d }< H^Jdb7uHZ e"hHw gN~"hHqWe"c }>lWfNlWc} me"zbJh&de"p JfANtccb7 Y gNZM Hpvr}< HgNlWc}]JhHwO&cHqWe}>cHe"Z }>WpvWf n lWfNpT
HaHdqW~"hWe"Z"e} Nce"^7 x1 x1 x2 x4 2 1 3 x2 x3 x4 1 1 1 1 −1 1 −1 1 0 0 0 1 x5 1 1 1 2 b 9 4 1 5 x2 1 −2 −3 x3 x4 x5 b 1 1 1 9 −3 −1 −1 −14 0 −1 0 −8 −3 −2 −1 −22 x3 −2 3 6 6 x4 0 1 1 x5 0 1 2 2 b −5 14 20 20 x 3 x5 −2 0 −3 −1 6 2 0 0 b −5 −6 20 0 Y[Zje"hHwWe"d^Je}>fNe"dzgNZ"e"f H^r}<H^` HdlWgpve"hWlW^Jz Hg>o m^7HZ x1 = −5 + 2x3 x2 = −6 + 3x3 + x5 x4 = 20 − 6x3 − 2x5 u ~"f}>~"cHe"cHe}vHz NtcgNZMHaHz qH H^r}>lWZ"yWcdHc u HccHlWf5HZ mHf}>bJct^` HfNbJg¦pve"hWlW^Jz Hg} cHmNtc u x3 = 1 x 5 = 1 u u u u x 1 = −3 x2 = −2 x3 = 1 x4 = 12 x5 = 1 Hpv b}>e"fNpv~"gNZ"e}>e"gNe"dde"p a HZ"bJgNpve"hWlW^Jz Hg" Y cHlWpvm}>bJabJ^Jbr}< Hg q bJZ"gNh H^`}>lH}U ~"g]HZ
e"^Je"pvb a HZ"bJg}>f>HdgNZn lWfNpT Hi"bJyWg{}>e"i<dbJc }I pT }>fNb xOf>HdhM> HdHcOpve"hW}< HfNlWZM Hg> HlWZj~"g[pT }>fNb xbJd qWe"fNZ"~"de"ccbJgNZM Hpvr}< Hg> HlWZjbJg ^Je"e}[HgNZ"d H^Jdb7]Y[Ze"^ Waab HZ"~"f} ^Je"e}>gN~"hWe"g"upve"f}[vpT }>fNb xf>HdhM>vHZlWgNZ"^JlWm s qWe"c }>lWfNfNe"dzgNZ"e"fN~"de"cf>HdhM>qHHhHw bJgQHZ[lWgNZ"^JlWm qWe"c }>lWfNlWcTcHWZ"^a HfNpve"^rwva HZ"bJgNa aeqWlWd}>yqWe"c }>lWfNlWcpT xobJpT H^JbJg¦gNZM HpTo5Y n e"d }>be"hHwWe"d^Je}>fNe"dzgNZ"e"fe"hHw o}N}>}>y pT }>fNb x HdHc¦f>HdhM>
ubJgNZ"e"dmlWd }>lWg>Hde"dd w br}}>tzo}>tdcjHZ lWgNZ"^JlWm qWe"c }>lWfNlWcUcHWZ"^ 5a HZ"bJgNa5aeq bJddb7 nsBfNe"dz| A pT }>fNb xbJd qWe"fNZ"eme"zbJhvHZ Ax1 = e1 . Axn = en zHf>Hae"hHwWe"d^Je}>fNe"dzgNZ"e"f e"hHwW~"f}>e"^Jpk|kpve"hWlW^Jz Hg> HayW^ [HZbJd qWe"fNZQ^J~}>e"Z"bJco-cHm s n }>y A−1 = [x1 , . , xn ] Y[Z 1 1 1 A= 0 1 1 1 0 1 pT }>fNb x bJd qWe"fNZ"~}HZ{H^` HaabWgNZM Hpvr}< HgNlWccH^ }< HfNlWZ"} Ntc pve"h0e"^Je"pvb a HZ"bJg}>f>HdgNZIs n lWfNpT Hi"bJyWc&gNlWfNlWZM}< MqHH^7 a1 a1 a2 a3 0 1 a2 1 1 0 a3 1 1 1 e1 1 0 0 e2 0 1 0 e3 0 0 1 a2 1 a3 1 1 −1 0 e1 e2 1 0 0 1 −1 0 e3 0 0 1 a3 0 1 e1 e2 1 −1 0 1 −1 1 e3 0 0 1 e1 1 1 1
e2 −1 0 1 ↓ A−1 e3 0 −1 1 [Y Z AA−1 = I e"hHwWe"d^WgN~"he"^J^Je"d WfNZ"~"gN~qWe"^]hHw W Z ze}>dcpve"h HfNfNyW^7ulWhHw qHH^JyWaHdHZ A bJd qWe"fNZ"~}[gNZM Hpvr}>lH}N}>tcvcb7 "!()* + (,- "! F="KrCH@BR;2J;ST6GI@B6@B:<; e"cbJd }>gNdcTe"hHw K 2AE6>FHGI2J;{PG>R>8HGNCHSTRM=F ;2 M 6KrC 3 CH@BR@ HZ td 4WCHERE2J4 ;jCHKrC 4WL<CHE x≥0 ¡ Ax = b c0 x − max HlW^n e"^r}>e"gNgNZ"c ulWhHwHZ A m × nsBe"gpT }>fNb xgNlWf>Hb ^JbJdeM HfNbJg>Hd n hWhWe}>^Je"de"c ~"g u0qHH^`HpvbJd }TlWhHw¢HZ Ax = b e"hHwWe"d^Je}>fNe"dzgNZ"e"fNde"c qHHd ^Je"h H^` Haa¤e"hHw b ≥ 0 ^Je"e}>gN~"hWe"gTa HZ"bJgNpve"hWlW^Jz Hg>o Y[Z
H^r}<H^` HdlWgNg> HhcHlWfN^` }>lWZM Hg> d~"^Jc^]n e"^r}>e"e} Nc u lWhHwHZ x0 = [x0 , x0 ] de"pvde"h }>rqa HZ"bJgNpve"hWlW^Jz Hg hHwmHf}>Ji"bJlWd H^J}>yulWhHw }<Hf}<H^JpTHZ"ZMvBva HNZ"bJgqH H^r}>lWZ"yWc}k cHH}>H}N}[bJgNpve"fNe}>^Je"de"coIu x me"zbJhvde"pka s xB Z"bJgqH H^r}>lWZ"yWc} gNZMHaHzbJgNpve"fNe}>^Je"de"coI dde"cpve"hHn e"^Je"^ e"dmHNf}>Ji"bJlWd H^ NtcTHZ A pT }>fNb xolH}Mu qHH^`HpvbJd }Q c qWe"c }>lWf}[bJg" Y B pT }>fNb xlWgNZ"^JlWmHb}>e" }[HZ e"hHwWe"d^Je}>fNe"dzgNZ"e"fNa W ^7uHZ A = [B, N] , c0 = [c0B , c0N ] . A lWgNZ"^JlWm qWe"c }>lWf}>e"fN~"de"ce"hHwOa
HZ"bJg> }0Hz > Hcg]JhHw BxB + NxN = b xB + B−1 NxN = B−1 b e"c q brqHH^Je"dge"hHwWe"d^Je}>fNe"dzgNZ"e"f}cHmNtc u Hpve"^rw a W ^HZ dt^J^` HdHc&qH H^`HgNZ}NqH&HZ xB = B−1 b xN = 0 xN gNZMHaHz&qH H^r}>lWZ"yWc~"f}>~"cH~} a HZ"bJgNpve"hWlW^Jz HgNlWZ¦Nto}>tdc e"^r}>~}>e"^Je"Z"~"gNdcgNZ"e"fNbJd } −1 u gJhHwe"e"Z a HZ"bJgNpve"hWlW^Jz HgNlWZ}<Hf}>lWZ"yOi"~"^rn hWhHqW~"d wW~"f}>~"c c0 B−1Bb b ≥B0−1b > 0 uHccHlWf gNZ"yWaHd n lWfNhWyOa HZ"bJgNpve"hWlW^Jz Hg} E6Sv36986E6GNFHK @EBC 4 ue"^J^Je"dcHe"Ze"gNe}>ae"d 36986E6 GNFHK @EC 4 deqWe"Z"Z"c Y e"hHwWe"d^
WgN~"hWe}Qn e"^JHgNZ"d H^rqHHZ −1 −1 qWe"c }>lWf}[HZT ¡ i"~"^rn hWhHqW~"d wW~"aee"^rwWe}N}>e"gNr}NqWeHZH^` Haabxe"Bc q =brqHHB^Je"dg0b^J−bJdeMB HfNbJgNx mfNlNs hWf>HpvlWZM HgNbn e"^`Hz}>lH}0cHmNtc xB ≥ 0, xN ≥ 0 xB + B−1 NxN = B−1 b c0B B−1 b + (c0N − c0B B−1 N)xN − max bJd }>lWhHw[n e"^r}>e}N}>c u lWhHw B−1b ≥ 0 u ~"gpvbrqWe"^ x ≥ 0 u c0 −c0 B−1N ≤ 0 e"hHwWe"d^H}>^Je"dgN~"hn e"dd H^J^` Hg>e"gNe}>~"d$HZ x = B−1b u Nx = 0 aN HZ"bJgNpvB e"hWlW^Jz Hg> kn e"^`Hz}>dHc uQgJhHw qWe"^Jee"c q brqHH^Je"dBg ¡ 9sBde"c$bJgvNlWmo}>bJpT H^JbJg5pve"hWlW^Jz Hg>oY n e"^`Hz}[}>e" }HZHu-lWhHwcHe"fNe"gNgNdc HZ Ax = b
e"hHwWe"d^Je}>fNe"dzgNZ"e"fNde"c e"hHwlW^rw Hd a HZ"bJgNpve"hWlW^Jz Hg> }MuHpve"^rw fNe −1 ~"gT 0 e"hHwWe"d^ H}s 0 −1 ^Je"dgN~"hWe"c lWmo}>bJpTH^Jbr}< HgNb cfNbr}>~"fNbJBtpvlWbco¦≥e"hHw 0gNZ"e"fNfNeTc}>Ne"^ N−e"gNc^JBdBe"c TNY[Zv≤H^` H0aabg}>f>}>~Is hWb` }QcHqWe} Nc UbJbJdzt^Jtdcve"hHwlW^rw Hda HZ"bJgNpve"hWlW^Jz HgNayW^7u Hpve"^rw fNej B−1b ≥ 0 }>e"^ Ne"gN^]~"gT c0 − c0 B−1N ≤ 0 de"p H^J^n e"ddu]HccHlWfT }N}>~"fNdce"hHw$lW^rw Hd a HZ"bJgNpve"hWlW^Jz HgNf>oNuHpve"B^rwi"g>Hce"hHwa HZ"bJgqWe"c }>lWfNaHdc^JWdaWZ"bJcHZe"^ WZ H} W^7u}>ls qH
Haaf>Jgde"pvde"h }>rq$ze lWZ"ZM }<Hf}>lWZ"yi"~"^rn hWhHqW~"d wW~"f}>~"c¢dqWe"cgNZ"bJc AqHHhHw ^Je"h H^` HaabJg{de"p i"gNWccHe"d I Z}¦5a HZ"bJgNayW^cbJ^J~"m 5~"g¦ka HZ"bJgNa5ae"^J~"m kqWe"c }>lWfNlWc hWlWdzlWgpve"hHqH H^`HgNZ}< Hg> MqHH^H~"fANcUe"^7 e"hHw c n e"^7u lWhHwj j sBe"zbJc[de"pka HZ"bJgqWe"c }>lWfNf> ccHlWf0cH~}[e"gNe}[^Je"e}>gN~"hWe"g" (c0N − c0B B−1 N)ej > 0 ¡ B−1Ne ≤ 0 e"cbJd }>gNcpvlWg}HZ x = λe u x = B−1b − λB−1Ne ^Je"e}>gN~"hWje"gpve"hWlW^Jz Hg}Mu HlW^ λ > 0 Ne"ZU jλ(c0 B− c0 B−1N)e i"~"^rn hWhjs
qW~"d wW~"f}>~"c}<Hf}>lWZ"bJc uHpve"^rwTpvbJdze"d}< HfNlWd} ^-Nd uB λ − ∞j ZHZ} Ne"^Je"d }>b7uolWhHw bJ^J^7 HZT ¡ {n e"^`Hz}>dHcTdbJdi"g]lWmo}>bJpT H^JbJgpve"hWlW^Jz Hg>o e0 B−1Ne > 0 qHH^`Hpve"^rw ksBf>o k e"hHwWe"d Kj = {i | e0 B−1Ne > 0} 0w bJ^rqH Hd K 6= ∅ e"hHwWe"d i ∈ K e"hHw j lW^rw HdbJdzeIxulWhHw i e0i B−1 b e0k B−1 b = . min k∈K e0k B−1 Nej e0i B−1 Nej ¡ Z"to}< HdqW~"hWfNe"}>tdce"hHwa HZ"bJgNi"gNe"fN~}¤ e"^Je"pvba HZ"bJg}>f>HdgNZn lWfNpT Hi"bJyH}II HZ Bis bJc a HZ"bJgqH H^r}>lWZ"ye"^JHhHwM> a HZ"bJg}v~"gTe"^rwW~"fNe j sBe"zbJc de"pka HZ"bJgqH
H^r}>lWZ"y cHeIs fN^7Ue"de"f> H^Jy e"^Je"p HZ e0 B−1Ne > 0 e"^Je"p ^Je"gNZH Y qH H^`HgNZ}< HgNb]gNZMHa H^rw NgNZ"|ccHe"fNe"gNZ}>pve}>gNZ"e} kgNZ"ie"fNbJd }>b qH Hj ^`HgNZ}< Hg<0abJZ}>lWgNr} >ou lWhHwHZ [a HZ"bJgNpve"hWlW^ s z Hg bJg^Je"e}>gN~"hWe"g{^Je"gNZHu (c0 − c0 B−1N)e > 0 e"hHwWe"d^ H}>^Je"dgN~"hme"zbJhHZ}Mu lWhHw HZ a HZ"bJgNlWZ5}<Hf}>lWZ"yi"~"^rNn hWhHqWB~"d wW~"f}>~"cjde"p ^Je"gNZvfNlWgNgNZMHaa c0 B−1bsBd~"^7ug H} }< HfNlWZ"lH}N}<HdkNlWaa^Je"gNZHu e0 B−1b > 0 Zto}>yWaabe"gNe} pvbJdzBbJh5n e"dd H^J^7uT a HZ"bJgNlWZU}<Hf}>lWZ"y&a
HZ"bJgNpve"hWilW^Jz HgQde"pvze"hWe"de"f> H^r}M B Y n e"d }>bj^J~"m~"gNe"cHe}e"Z"to}< Hd pve"hWbJgNpv~}>e"^ Nc HZ a HZ"bJgNpve"hWlW^Jz Hge"gNe}>~"ae"d e"^J^Je"d WfNbJZ"Z"c$HZlWmo}>bJpTH^Jbr}< Hg}5bJ^J^7 n e"^`Hz}Tpve"hWlW^Jz}>yWg> Hh }MupTNz¤e"hHw a s Z"bJg}>f>HdgNZn lWfNpT Hi"bJyH}qW~"hWZ"dce"^Qn e"d }>bgNZMHa H^rwWlWcgNZ"e"fNbJd }M brqWe"^Q^Je"e}>gN~"hWe"g a HZ"bJgNlWc ~"g[JhHwva HZ"bJgNpve"hWlW^Jz HgNlWcogNZM HpT&qW~"hWe"g[~"g[ze"hWe"de"f> Hi"bJyTpve"d }>e"g[e"gNe}s ae"dvi"~"^rn hWhHqW~"d w~"f}>~"cHekd
uze"hWe"de"f> Hi"bJyTpve"d }>e"g e"gNe}>ae"dqW~"hWe"g gNZM Hp e"^Je"pvb a HZ"bJg}>f>HdgNZn lWfNpT Hi"bJy gNZ"bJpvm^JeIx¢br}>e"f> Hi"bJy&e"^rqW~"hWZ"~"gNeto}< Hde"^ cHe"^J^ Nto}>dtdc¢e"hHw lWmo}>bJpT H^JbJg a HZ"bJgNpve"hWlW^Jz HgNlWZQqHHhHw&HddHckpve"h H^J^`Hmr}< Hg> HlWZHuHlWhHw& n e"^`Hz}>dHc dbJdi"g0lWmo}>bJpT H^JbJg{pve"hWlW^Jz Hg>o e"hMNe"hHwWe"Z"Z"c u{lWhHw a HZ"bJgNaae"^J~"m bJ^J^7cbJ^J~"m qWe"c }>lWfNlWc pve"hHqH H^`HgNZ}< s g> HdHc£dlWpvr}< Hg> MqHH^U pve"hHn e"^Je"^ gNZMHa H^rwWlWcn e"^` H^J^Jr}< Hg> MqHH^{HfNf> HZe"gNe}>fNeHu qH H^`HgNZ}<
Hg{de"p e"hHwW~"f}>e"^Jpk| {jqW~"hWe"gNgN~"h&HZ[ H^r}<H^` HdlWge"gNe}>ae"dujde"pvze"hWe"de"f> H^r}s g> Hh5n e"^r}>~}>e"^Je"Z"~"gNed~"^Jc^bJg]abJZ"lWd w r}>}>y zzbJhvi"g>HcHZ}[HZe"gNe}>e} d~"Z}>c uHpvbJcHlWf]bJgNpve"f}>dce"hHwbJdzt^Jy&^Je"e}>gN~"hWe"g a HZ"bJgNpve"hWlW^Jz Hg}M [HhHwWlWdcHWdd w |e"hHwbJdzt^Jyvpve"hWlW^Jz Hg}¦Hzdb7u 5n e"^`Hz} HZ H^` HaabH^`Hc x ≥ 0, u ≥ 0 Ax + u = b c0 x − max ~"g b ≥ 0 Z}&n e"^`Hz}>lH} ERGISvFHK M6KrC 3 CH@EC 4 rqMNtc u*~"gkHZ x = 0 u u = b a HZ"bJgNpve"hWlW^Jz HgjHZ u &a HZ"bJgqH H^r}>lWZ"yWc uHZ x &de"pka
HZ"bJg]qH H^r}>lWZ"yWcvqWe"c }>lWf> ]e"hHw H^JcH^JpTHg{bJdzt^Jy5pve"hWlW^Jz Hg" vkn e"^`Hz}Q}>Wf}>~"de}>e"gNe"dde"p bJ^rwWe"dH^`Hc uHccHlWf q bJgNgNZMMqWe"Z"e}>e} NcHZ5 n lWfNpT Hf>m^7HZ td¦cH~}Nn HZ"bJg OgNZ"bJpvm^JeIxvpvy zgNZ"e"fNfNe"^B e"hHw cn e"^7ulWhHw5pve"hWlW^JzHdzykn e"^`Hz}05cHqWe}>cHe"Z x ≥ 0, u1 ≥ 0 A1 x + u 1 = b 1 A2 x = b 2 ¡W¡ c0 x − max Y[Z H^r}<H^` HdlWgNg> Hhjpve"hWgN~"f}>~"gNe[d~"^Jc^ n e"^r}>e"e} Nc uolWhHw ~"g ¦ bJd s ze"d^JbJdeM HfNbJg mfNlWhWf>HpvlWZM HgNb n e"^`Hz}jbJ^rwWe"dH^`Hcf>OlWZ"b}>1y≥TY[0 Z axb2≤≥ b0u b ≥ 0 H^`Hc
n e"^r}>~}>e"^Je"c HZ cbJe"hW~"gNZ"r}qH H^r}>lWZ"ygNe"hWr}>gN~"hW~qWe"^ + u = b H^`Hcf> lWZ"}>yWc~"g JhHwkHZ]e"u^Jg U≥n e"0^r}>~}>e"^i"gNlWmlWf}>aHd5qHHddHc Y[Z ax ax e"hHwWe"d^ WgN~"hWe"c& = b pT HgNl zbJcaHdu pvbrqWe"^br}N}0 b ≥ 0 gNZ"cgN~"hve"gNe}>~"d −1sBhHwWe"^qHH^Jykae"gNZ"lWfNZM HgNg>H^-pvbJd s zbJhabJZ}>lWgNr}>}>yjY[Z ≥ b u b ≥ 0 n e"^r}>~}>e"^Je"cme"zbJh v ≥ 0 n e"^Je"gN^Je"hqH H^r}>lWZ"y gNe"hWr}>gN~"hW~qWe"^ ax − v =ax H^`Hcf>lWZ"}>yWcv~"gQJhHwpT HgNl zbJc5n e"^r}>~}>e"^i"gNlWmlWf}>aHd b qHHddHc Y ]n e"^`Hz}>lH} STM3R;?A@BR@@QERGISvFHK
M6KrC 3 CH@EC 4 rqMNtc 0e"dze"^ NclWZ"ZM {n e"^`H z}>lWZj5cHqWe}>cHe"Z gNe"hW~"zon e"^`Hz}>lH} uHpve"^rwe"hHwOdlWfNpT H^n e"^`Hz}M x ≥ 0, u1 ≥ 0, u2 ≥ 0 A1 x + u 1 = b1 A2 x + u2 = b2 10 A2 x − max Y Qn e"^`Hz}¦i"~"^rn hWhHqW~"d wWekcHlWfN^` }>lWg"u bJgNZ"e"d 10b vi"~"^rn hWhHqW~"d we"hHwn e"^Jg TcHlWfs `^ } >oBhHw 9sBde"cvqHHdlWmo}>bJpT H^JbJg{pve"hWlW^Jz Hg>o e"2hHwWe"d x0, u0 , u0 Q {n e"^`Hz} e"hHwOlWmo}>bJpT H^JbJg{a HZ"bJgNpve"hWlW^Jz Hg> bJ^rwWe"dpvbJdzbJhk^J~}>e"Z"bJc I ccH1lWf¦cH2~}¦e"gNe}¦qHHd ¡ 10A x0 = 10b uHpvbJa W^ A x0 = b u u0 = 0 cHqWe}>cHe"Z"bJc u g]JhHw
x0, u0 HZ 1 e"fNe"z2e}>b{ {n e"^`2Hz}0e"hHwO^Je"2e}>gN~"hWe"g¦2a HZ"2bJgNpve"hWlW^Jz Hg>o 10A x0 < 10 b u[AqHHhHw Hpvb{thHw HdHZHu u0 sBdHc qHHd^Je"h H^` Haae"hHw mlWZ"br}>rq cHlWpv2mlWde"dgNeHu{H2pvb{gNZ"cgN~"hWcH~"mme"d¢a HZ"bJgqH2 H^r}>lWZ"yI aae"d¤HZe"gNe}>ae"d¤HZ e"fNe"ze}>b{ {n e"^`Hz}>dHcTdbJdi"g0^Je"e}>gN~"hWe"g¦pve"hWlW^Jz Hg>o ~"^JgNZ"e"fN| ]n e"^`Hz}>lH}[bJgUTgNZ"bJpvm^JeIxpvy zgNZ"e"fNfNe"^*pve"hWlW^JzHdb7 Z}UgNZ"lWc Hg e"^Jg On HZ"bJgNdHc5deqWe"Z"db~"ge"ZvcbJZM HfNyW^`Hh [n e"^`Hz}je"hHw ^Je"e}>gN~"hWeva HZ"bJgNpveIs hWlW^Jz Hg>
HdHcpve"hW}< HfNlWZM Hg> Hf>gNZ"lW^Jh H^7Y[Z e"^Jg n HZ"bJgNaHd¤de"p bJgv}>Wf zdc i"~"^rn hWhHqW~"dd wWe"^7udlW&e"dde"cqH H^r}>lWZM Hg> }0i"~"^JgNZ"e"fN|d wWlWpvlWdcHqWe}>db HZe"hHwWe"g cbr}>0e"xf> Hi"bJyWcgNlWf> Hd \HZe"^Jg n HZ"bJgvHZ"ZMH^]qW~"hWZ zbJc u]lWhHw$gNbJcHe"fN^r}&}<H^` H^JdbQe"hHw ^Je"e}>gN~"hWe"g¦a HZ"bJgNpve"hWlW^Jz Hg} ¡ e"gNe}IIu HccHlWf0bJdde"dcHe"Z"zoqWekHZ d[pT HgNl zbJc&n s Z"bJgNaHd{e"aa W^ a HZ"bJgNpve"hWlW^Jz HgNayW^cbJbJdzt^rqH n lW^rw}<} NtcHZQlWmo}>bJpTH^JbJZM H^` Hg}-pvlWg} pT Hf HZ 10 A x pT HgNl z^`HhWlWg
i"~"^rn hWhHqW~"d w}{£hHwWe"^Jpve"d&crq ^HhHwqHj~"g q bJgNgNZM}>~"fqWe 2 ¡ HZ0e"fNe"ze}>b 0 i"~"^rn hWhHqW~"d w&pT xobJpTH^JbJZM H^` Hg> Hf>o e"fNpv~"gNZ"e}>e"gNe"dHfNf> q bJhHw HZ"dtdc cHe"^J^7ulWhHwHcZ{xe"^J~"f}Q^Je"e}>gN~"hWe"gNgN~"hWe} {qW~"hWbJh¦pve"h WfNbJZ"Z"c dde"cje"hHw gNZ"e"fN|5pvy z > HZHuHZ u qH H^r}>lWZ"yWc}[dt^J^`&~"f}>~"cHe"d fNWhWZ"r} Nc uHpvb TgNZ"bJpvm^JeIxpvy zgNZ"e"fNae"d }>e"i<dbJcHbJ^`Hh 2 hHwOqHH^JyWgNr}>}>ykpve"hulWhHwHZ u qH H^r}>lWZ"yWbr}QqW~"hWbJhv&a HZ"bJgNlWdcrq ^ }<Hf} Ntc O e"hMNe"^JW^ Nc
WcHe}Mum~"^Jz Ht^*e"hH w MsBh H2^ ~"gjJhHwpv~"hHccHlWfUgNe"p q bJgNgNZ"c WcHe}5a HZ"bJgNaou*mlWZ"br}>rqi"~"^rn hWhHqW~"d we"hHw o}N}>}>y NtcqHHd ZHZvlWmo}>bJpTH^Jb s }< HgUcfNbr}>~"fNbJtpvlH}UbJgUpve"hHqH H^r}>lWZ}<} >o[pvbJdze"dde"p i"gNbJ^J^`HhWlWg[qH H^r}>lWZ"yWlWZ}<Hf}>lWZ"y i"~"^rn hWhHqW~"d we"hHw o}N}>}>yWdHcde"p mlWZ"br}>rq dHcTcHe"^J^^Je"ddbJeH Y gNZ"bJpvm^JeIxpvy zgNZ"e"f[pvbJdzcH~}[n HZ"bJg> Hd H^ TgNZM Hpvr}< HgNlWcO^Je"alWd wWlW^Jr}< Hg> }¦pve"hs cHWdd w r}>b7u e"hHwWe"d^Je}QfNe"dzgNZ"e"fNe"cTpve"hWlW^Jz Hg> Hd H^HgNZ"d H^r}}< Ha^` HZM}>lWgn lWfNpT HaHd
fNe"dze"Z"Z"cve"^HZ¦e"hHw o}N}>}>ykpT }>fNb xolH}Mu9NlWaaTlW^JzH^r} j b ~"g b qWe"c }>lWfNlWc}I ~"g Ti"~"^rn hWhHqW~"d we"hHw o}N}>}>yTqWe"c }>lWf>Hbr}5 c0 ~"gUHZ 10 A qWe"1c }>lWfNlWc2}M eqWe"Z"e}s Nc5pv~"h z ~"g t qH H^r}>lWZ"yWc}MuHpve"^rwWe"c&HZ0e"^Jg z^Je"hWe"g ~"gpT2 HgNl z^`HhWlWg i"~"^rn hWhHqW~"d w ~"f}>~"cH~}Un lWhM> HcNe"^JW^Jdb7 BhHw ]n e"^`Hz}¦n e"^r}>~}>e"^Jb e"hHwWe"d^Je}>e"bJe"Z5i"g>}>lW^ Ntcpv~"h ~"g¦ −z + c0 x = 0 −t + 10 Ax = 0 e"hHwWe"d^Je}>e"cHe}M Y −z ~"g −t qH H^r}>lWZ"yWc} bJ^J^Je}NqWe lWZ"ZM
Ntc¤}<Hf}>lWZ"y e ~"g lWgNZ"^JlWm qWe"c }>lWfNlWc}I pvbJdzbJhjUa HZ"bJgNaHd5n lWhMNtc}<Hf}<Hdb~"g JhHwkcHWdd w |Tm+1 ^` }>db7u em+2 lWhHwm~"^Jz Ht^ HZe"^Jg z^Je"hWe"g i"~"^rn hWhHqW~"d wgNlWf> HaHd5 0 0 B−1N qWe"c }>lWf Ne"^Je"dbJc pve"h e" }*a HZ"bJgNa ae"^J~"m ]qH H^r}>lWZ"yWdHc HZ e"^Jg 0n HZ"bJcgNaNH−c dHBZNWdjgNZ"yWaouWHpve"^rw e"Z mlWZ"br}>rqcHlWpvmlWde"dgU}<Hf}>lWZ"bJc −t gNlWf> HaHdvY pT HgNl zbJcn HZ"bJgNaHd¢HpvbJcHlWf −t gNlWf> } pT Hf¦e"^ bJg[^Je"e} HhHw dbA0HZ5&qH H^r}>lWZ"yT^J~"me} ae5Ta HZ"bJgNaouHpve"^rw bJcOde"p i"gNbJ^J^`HhWlWg~"g −z gNlWf>
HaHdmlWZ"br}>rqTcHl lWfNzbJd }< >qHHd Y}< Ha^` HZM}¦e"^Jg TlWgNZ"^JlWm HavTa HZ"bJgqH H^r}>lWZ"yWc}Mue"^Jg TgNlWf> HaTva HZ"bJgNlWdcrq ^Jb qH H^r}>lWZ"yWc}0JfANtc u5}< Ha^` HZM}¦e"^Je"pve"b-me"zbJhTHZHzlH}N}[a HZ"bJgNf>5qWlWd}>cHlWZ"ycHl lWfNzb s d }< Hc}[pkto}<} > Hc ]Y pvy zlWgNr}>lH}N}0dlWfNpT H^n e"^`Hz}[pve"hWlW^Jz Hg> }]}>e" }UHZkH^` Haab }< Ha^` HZM}>ayW^bJdzr} Ntc u1 ∗u2 −z −t x0 A1 b 1 A1 b 2 c0 0 0 1 A2 0 Y[Z u qH H^r}>lWZ"yWc}0pve"hWi"gNbJ^J^`HhWlWZ}>tcue"Z"Z"e"^ Ne"^Je"ZqWe0HZ}Mu lWhHw e"Z"e"cke"^JHhHwM> Hc a HZ"2bJg}Mu HccHlWfl zjpT Hf gNe"pvpvb
cHWfN^Jpv~"d wWe"c&cHWZ"H}N}Qde"p }>~"fNe}>de"c5q bJgNgNZMouoe"^ s ^Je"d }>~}>ae"dv }>WaaboqH H^r}>lWZ"yqHH^7uWHpve"^rwWe"ckHc Hf*}>WaagNZ"Wf bJg pve"e}>de"ckae0Ua HZ"bJgNa ¡ ~"gHhHw } > Hc5bJgHZ}e"^7 HZ¦e"^Jg n HZ"bJg qW~"hW~"djpT HgNl z^`HhWlWg i"~"^rn hWhHqW~"d wvlWm s }>bJpktpT Hd H^A qHH^`Hpve"dd w b i"gNbJ^J^`HhWlWgQqH H^r}>lWZ"yTe"^JHhHw}<Tva HZ"bJg}MuHccHlWfUHZe"fNe"ze}>b n e"^`Hz}¦e"hHw^Je"e}>gN~"hWe"g a HZ"bJgNpve"hWlW^Jz Hg> Hd H^qHHhHw tdc uHpve"^rw a W^-cbJbJdzt^rqH5pvlWg} pT
HfHZve"fNe"ze}>bi"~"^rn hWhHqW~"d wgNZ"e"fNbJd }n lW^rw}<} NtcHZTlWmo}>bJpTH^JbJZM H^` Hg}M HZve"^Jg n HZ"bJg0lWmo}>bJpT H^JbJgpve"hWlW^Jz Hg> HaHdqHH^`Hpve"^rwTi"gNbJ^J^`HhWlWgQqH H^r}>lWZ"y&mlWZ"br}>rqu HccHlWf[&n e"^ s Hz}>dHcTdbJdi"g0^Je"e}>gN~"hWe"g¦pve"hWlW^Jz Hg>o B^J^JtgNZ}>f> Hi"bJyWdHcvd~"Z"Z"c5cHqWe}>cHe"Z m~"^Jz }M x1 , x 2 , x 3 , x 4 , x 5 ≥ 0 3x1 + x2 + x4 + x5 = 13 x1 + x3 − x4 + x5 ≤ 7 2x1 + x2 + x3 + x4 − x5 = 17 6x1 + 3x2 + 2x3 + x4 − 4x5 − max Y[ZjbJdzt^Jyk}< Ha^` HZM}05cHqWe}>cHe"Z x1 x2 x3 x4 x5 ¡ 1 13 ∗u1 3 1 0 u2 1 0 1 −1 1 7 ∗u3 2 1 1 1 −1 17 −z 6 3 2 1 −4 0 −t 5 2 1 2 0 0 e"Zk}< Ha^` HZM}>lWZjHZjH^` Haaba
HZ"bJgNpve"hWlW^Jz Hg}<Hf}>lWZ"bJc x1 = x2 = x3 = x4 = x5 = 0 , u1 = 13, u2 = 7 , u3 = 17, z = 0, t = 0 U H^`HgNgNZ"tcOae"pve"d &qH H^r}>lWZ"yWdHcOHZ x Bs e}MY gNZ"|ccHe"fNe"gNZ}>pve}>gNZ"e} gNZM Hpvr}< Hg> s lWZ HZUH^` Haab Hd w HzlWgNlWc}]cH~"me"Z"Z"c ~"g uHpve"^rwWe"cvcHWZ"^ ¡ cbJgNe"aau }>e" } u ^Je"gNZvOcbJpve"d qH H^r}>lWZ"y { H^Jy > HaHd HZ (1, −1, 1, 1, 2) qWe"c }>lWfj^J~"m aeHu 4 ~"g¦HZ 13 1 1 (1, 0, 0, 0, 0) 17 1 ^J~"mcb7 kYhWe"de"f> H^Jy&e"^Je"pve}0ae"cHe"fNe}>e"Z}>c Y[Z ]}< Ha^` HZM}M x1 x2 x3 ∗u1 x5 x4 3 1 0 1 1 13 u2 4 1 1 1 2 20 ¡ −1 ∗u3 −1 0 −2 4 −z 3 2 2 −1 −5 −13 −t −1 0 1 −2 −2 −26
¡ YlWZ"ZM 5}<Hf}>lWZ"y&a HZ"bJgNpve"hWlW^Jz Hg" x1 = x2 = x3 = x5 = 0, x4 = 13, u1 = 0, u2 = 20, u3 = 4, z = 13, t = 26 lWg}{e"hHwW~"f}>e"^Jpk|ulWhHw&HZ x cHe"fN^ja HZ"bJgNaj~"g u e"^JHhHwM>jHZ} ¡ Hd w s 3 3 zlWgQcbJgNe"aaupvbJd }] H ¡ I Z"Z"e"^-pvbJdzcH~}]i"gNbJ^J^`HhWlWg qH H^r}>lWZ"ycbJcHe"fN^r}0ka HZ"bJgNayW^ ~"gQJhHwTcHqWe}>cHe"Z &}< Ha^` HZM}QHZ e"fNe"ze}>bn e"^`Hz}e"hHwT^Je"e}>gN~"hWe"gQa HZ"bJgNpve"hWlW^Jz Hg> } Hz >oYpT HgNl z^`HhWlWgQi"~"^rn hWhHqW~"d wgNlWf> }0pvlWg}0pT HfQcbgNe"p JfANtc x1 x2 ∗u3 ∗u1 x5 ¡ 0 1 1 13 x4 3 u2 5 1 −1 2 16 4 x3 −1 0 1 −1 −2 4 −z 5 2 −2 1 −1 −21 e"Zk}< Ha^`
HZM}>lWZ }<Hf}>lWZ"y5a HZ"bJgNpve"hWlW^Jz Hg x1 = x2 = x5 = 0, x3 = 4, x4 = 13, u1 = u3 = 0, u2 = 16 J^ e"e}>gN~"hWe"g"u zeOde"p lWmo}>bJpT H^JbJg"u bJgNZ"e"d HZ x ~"g x sBWZT}<Hf}>lWZ"yto}>lW^JgNygNlWfNae"^Jb e"^Je"pve"c mlWZ"br}>rqHHc u JhHwe"Z"e"c$a HfNpve"^rw bJcHeOae"1^J~"me}2 a HZ"bJgNao e"hHw c~"gNZ"fNeHu lWhHw¢HZ u H^`}N}^J~q to}>lW^JgNygNlWfNae"^Jb¦e"^Je"p bJgmlWZ"br}>rqu]zee"dde"c¢e"^J^Je"d~"fNe u 1 de"p ^J~"me}k aea HZ"bJgNaou*pvbrqWe"^ i"gNbJ^J^`HhWlWg qH H^r}>lWZ"yY[Z x s9}qH H^`HgNZ}NqHae"^J~"m 1 qH H^r}>lWZ"yWdHcHZ x n lWhM>TTa HZ"bJg[e"^JHhHw dbQ ¡ ¡ ¡
¡ ]~"2g TcHqWe}>cHe"Z upvlWg} 4 pT HfQlWmo}>bJpT H^JbJg }< Ha^` }0cHmNtc x1 x4 ∗u3 ∗u1 x5 x2 3 1 0 1 1 13 u2 2 −1 −1 1 3 3 x3 −1 0 1 −1 −2 4 −z −1 −2 −2 −1 −3 −47 aa W ^k}< Ha^` HZM}>ayW^^Je }>tz NtclW^rqHHgNdb-HZjlWmo}>bJpT H^JbJg{a HZ"bJgNpve"hWlW^Jz Hg}M x1 = 0, x2 = 13, x3 = 4, x4 = 0, x5 = 0, u1 = 0, u2 = 3, u3 = 0, z = 47 . Y Ng Z"bJpvm^JeIxpvy zgNZ"e"f& e"hHw bJco¦e"^Wd wWeHu-lWhHwHZkto}>lW^JgNyulWmo}>bJpT H^JbJg]}< Ha^` HZM}>ayW^* zt H^n e"^`Hz}0e"hHwlWmo}>bJpT H^JbJgpve"hWlW^Jz Hg> }]bJg0cb-}>tz NtclW^rqHHgNdb7 lWg} &a HZ"bJgNaHd ^J~q us9qH H^r}>lWZ"yWclWZ}<Hf}>lWZ"y[zt H^qH H^r}>lWZ"yWcU~"f}>~"cHeQ^Je"gNZ u}>e" } u = 0 uW¦a HZ"bJgNlWd crq ^Jb u qH
H^r}>lWZ"yWc[~"f}>~"cH~} HZto}>lW^JgNy0gNlWfNaHdde"h }>rq[e"^ Ne"^J^Je"^}<H^` H^ 2Ntc¦pve"h e" } u1 =¦W1,dd uwW3e"d = e"2^J^Je"d WfNbJZ"e} Nc u[lWhHw HZJhHw cHmlH}N}mfNbJpT H^ sBzt H^[pve"hWlW^Jz HgNm Hf cbJe"^J~"hWr}>b5ztH^Jbr}< HgNb}>~}>e"^Je"cHe}M ¡ VWC 4 RGIKJ M6KrC 3 CH@BR4 ¡ }< HfNlWZ"Z"tcpve"hOcHqWe}>cHe"Ze"hHwWe"d^Je}>fNe"dzgNZ"e"fNe"c H^r}<H^` HdlWg[pve"hWlW^Jz Hg> } e"^Je"pvba HZ"bJg}>f>HdgNZn lWfNpT Hi"bJyqHH^7 a x−y+z−u = 1 x−y−z+u = 0 −2x + 2y + 4z − 4u = 1 x +z+u = 2 x+y + u = −3 y + z + u = −1 }< HfNlWZ"Z"tc pve"h¤HZ ¡
n e"^`Hz}>aHdgNZ"e"fNe"m^¤e"hHwWe"d^Je}>fNe"dzgNZ"e"fNe"c qHH^` s pve"dd w b-a HZ"bJgNpve"hWlW^Jz Hg> } 0Y[ZH^` Haabe"hHwWe"d^Je}>fNe"dzgNZ"e"fTgNZMHaHzg> HhHn lWccHe}N} }< HfNlWZ"Z"tcpve"hHZ e"hHwWe"d^Je}>fNe"dzgNZ"e"fNae"d gNZ"e"fNe"m^ ~"g mHf>Hpv~}>e"fNe"c~"f}>~"cH~}MupTNzJfANtc n e"^-HZje"hHwWe"d^Je}>fNe"dzgNZ"e"f H^r}<H^` Hda,lWgb pve"hWclW^Jz Hg> }M x1 + x2 + 2x1 + x2 −x1 + ax2 x3 + x4 x3 + 2x4 + 3x5 + 2x3 − 2x5 − 2x3 + x4 + bx5 = = = = 2 1 2 c Jb Z"lWd w r}>gNtcUaeHuHlWhHwj¦e"hHwj^JbJdeM HfNbJg-e"hHwWe"d^Je}>fNe"dzgNZ"e"fNde"cqHHdcH~} c^JWd s
aWZmlWZ"br}>rq&pve"hWlW^Jz Hg>ou HccHlWfqHHdOHZ[e"hHwWe"d^Je}>fNe"dzgNZ"e"fNde"cde"p mlWZ"br}>rq pve"hWlW^Jz Hg>kbJg" }< HfNlWZ"tcTpve"hv5cHqWe}>cHe"Z OpT }>fNb xolWcvbJd qWe"fNZ"~}[e"^Je"pvba HZ"bJg}>f>HdgNZn lWfNpT s i"bJyqHH^7 1 1 2 0 1 1 1 1 3 a −2 5 1 3 −1 4 2 0 7 i 1 1 1 1 1 1 −1 −1 1 −1 1 −1 1 −1 −1 1 ^Jz Ntcpve"hT&gNZ"bJpvm^JeIxpvy zgNZ"e"fNfNe"^ HZH^` Haab-^JbJdeM HfNbJgQmfNlWhWf>HpvlWZM HgNbn e"^ s Hz}>lWc}M a) x 1 , x2 , x3 , x4 , x5 ≥ 0 x1 + 2x2 + 3x3 + x5 ≤ 100 x2 + x3 + x4 + x5 ≤ 80 x1 + x3 + x4 ≤ 50 2x1 + x2 + 3x3 + x4 + 2x5 − max ¡ b) x 1 , x2 , x3 , x4 ≥ 0 x1 + x 2 + x 3 ≤ 8 2x1 − x2 +
x4 = 12 7x1 + 3x2 + 4x3 + 6x4 − max c) x 1 , x2 , x3 ≥ 0 x1 + x2 + 2x3 ≤ 5 2x1 + x2 + x3 ≥ 2 BfANtcn e"^¦ x1 + x2 + 3x3 − max n e"^`Hz}>aHd¤gNZ"e"fNe"m^ sBc$zt H^JbJg>Hbr}&~"gT}< HfNlWZ"Z"tc$pve"h HZlWmo}>bJpT H^JbJggNZ"bJpvm^JeIx }< Ha^` HZM}>lWcayW^]zt H^JbJgkn e"^`Hz}>lWce"hHwlWmo}>bJpT H^JbJg a HZ"bJgNpve"hWlW^Jz Hg> }M bJZ"lWd w r}>gNtcaeHu{lWhHwe"hHw^JbJdeM HfNbJgmfNlWhWf>HpvlWZM HgNb{n e"^`Hz}5^Je"e}>gN~"hWe"g }<Hf}>lWpT Hd w jde"pkfNe"g~"g{cHlWfN^` }>lWg"u HccHlWfQjzt H^JbJg> HdHc5^Je"e}>gN~"hWe"g{}<Hf}>ls pT Hd w 5de"p cHlWfN^` }>lWg" ¡
