1629289597

16 2. Wielościany

Uwaga 2.4. Twierdzenie 2.5 pozwala łatwo budować funkcję celu taką, by zbiorem punktów optymalnych była zadana ściana.

Przedstawimy teraz kilka prostych własności ścian.

Stwierdzenie 2.1. Niech S — W fi dH będzie ścianą wielościanu W.

Jeżeli S ^ W to dim S < dim W.

Dowód. Niech q £W\S. Ponieważ dH jest przestrzenią afiniczną więc af(S) C dH i q £ dH. Zatem af(S) 7^ af(W) co implikuje dim S < dim W.    □

Lemat 2.1. Niech Si, S2,..., St będą ścianami wielościanu W C Rⁿ. Wówczas S = f)i=i Ą jest ścianą W lub zbiorem pustym.

Dowód. Niech Si = W D dHi, gdzie Hi = {x G M" | a% • x < h}. Definiujemy półprzestrzeń H = {a: 6 Rⁿ | 5Zi=i ^ai • ^x < X)i=i &i}- Oczywiście jeżeli q € W to Vi ai • x = 6, implikuje q € H. Ponadto S C dH.

Niech teraz q € dH fi W wtedy warunki a, • q < bi oraz X)i=i ^ai* Q ⁼ Z)i=i implikują a* • q — bi dla i < t. Zatem S — dH fi W.

□

Lemat 2.2. Niech K C H będzie j-wymiarową kulą o środku p zawartą w pólprzestrzeni H. Jeżeli p € dH to K C dH.

Dowód. Niech q € K fi H q £ dH. Przyjmijmy:

H = {x € Rⁿ | a • x <6} wtedy a • q < bi a»p = b.

Ale p = ^q + dla pewnego q' € K Dochodzimy do sprzeczności, gdyż z jednej strony q' € K C H implikuje a • q' < b zaś z drugiej strony

a • q' = a • (2 p — q) = 2a»p—a»q = 2b — a • q > b.

□

Definicja 2.10. Niech H = {x € M” | a • x <6} będzie półprzestrzenią.

Półprzestrzenią dopełniającą nazywamy półprzestrzeń H~ = {x G Kⁿ | a • x >6}

Stwierdzenie 2.2. Jeżeli H jest półprzestrzenią to H U H~ = Rⁿ i H fi H~ = dH = dH~. Stwierdzenie to prowadzi bezpośrednio do wniosku.

Wniosek 2.1. Niech W = fjj=i Hi C Rⁿ będzie wielościanem. Wówczas, dla każdego j,

S = W fi dHj = IVfl HJ jest ścianą wielościanu W lub zbiorem pustym.

Wniosek 2.2. Niech W = fji=i Hi zaś S = W fi fjf=i H~ będzie niepustym podzbiorem. Wówczas S jest ścianą W.

Dowód. S = W fi fj|=i Hf — Df=i O jest przecięciem ścian a więc ścianą na mocy lematu 2.1.

□