Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1010WPROWADZENIEDOPROGRAMOWANIALINIOWEGO
27
RYSo1050Punktmjakoliniowakombinacja
wypukławierzchołkówtrójkąta
ZzałożeniaAl7AbE(071>wynika?żerównieżA17A27A3E(071>.Osta-
tecznie
m1A1m
1+A2m2+A3m37
przyczym
A1+A2+A31Al1Ab+11Al+Ab11:
(1:31)
(1:32)
wyniktegorozważaniamożnauogólnićnadowolnąliczbęwierzchoł-
kówr(tw.Oarath/
eodory?ego?[44])iwyrazićdowolnypunktmEUjako
wypukłąkombinacjęliniowązbioruwierzchołków{m
m1A1m
1+...+Akm
k+...+Armr1
;
r
Akmk7
kg?k117:::7r:
(1:33)
kż1
przyczym
A1+...+Ak+...+Ar1
;
r
Ak11:
kż1
wtedy
Q(m)1C
Tm1CT(A1m1+...+Akmk+...+Armr)1
1A1CTm1+...+AkCTmk+...+ArCTmr1
1A1Q(m
1)+...+AkQ(m
k)+...+ArQ(mr):
(1:34)
Spośródwierzchołkówmkwybierzemyten?wktórymfunkcjaQ(mk)mawar-
tośćnajmniejszą:min(Q(mk))1Q(^
m).wówczas
A1Q(m
1)+...+AkQ(m
k)+...+ArQ(mr)>A1Q(^
m)+...+AkQ(^
m)+
+...+ArQ(^
m)>(A1+...+Ak+...+Ar)
\
\r
1
J
Q(^
m)7
czyli
Q(m)>Q(^
m):
