Zagadnienia

2.1 Przestrzenie afiniczne
2.2 Wielościany

2. Wielościany

2.1. Przestrzenie afiniczne

Zbiorowi ciągów n elementowych o współczynnikach rzeczywistych Rn można nadać strukturę przestrzeni liniowej wprowadzając dodawanie ciągów ( wektorów ) i mnożenie przez liczby. Można też nadać strukturę przestrzeni afinicznej wprowadzając następujące działanie zwane środkiem ciężkości lub kombinacją afiniczną.

Definicja 2.1

Układem wag nazywamy taki ciąg liczb rzeczywistych r1,r2,…,rt, że ∑i=1tri=1. Niech p1,p2,…,pt będzie ciągiem punktów z Rn. Środkiem ciężkości punktów pi o wagach ri nazywamy punkt p=∑i=1t⁢ri⁢pi.

Branie środka ciężkości ma następujące własności:

1) 1⁢p=p

2) ∑i=1t⁢ri⁢pi=∑i=1t⁢ri⁢pi+0⁢q

3) Jeżeli pj=∑i=1t⁢ri,j⁢qi i a=∑j=1k⁢sj⁢pj to a=∑j=1k⁢sj⁢∑i=1t⁢ri,j⁢qi⁢=⁢∑i=1t⁢∑j=1k⁢sj⁢ri,j⁢⁢qi.

Definicja 2.2

Podprzestrzenią afiniczną nazywamy podzbiór Rn zamknięty ze względu na branie środków ciężkości.

Twierdzenie 2.1

Niech W będzie niepustym podzbiorem Rn. Wówczas równoważne są warunki:

1) W jest przestrzenią afiniczną.

2) W jest postaci W=p+V={p+α|α∈V, gdzie p∈W i V jest podprzestrzenią liniową Rn.

3) W jest zbiorem rozwiązań pewnego układu równań liniowych.

Definicja 2.3

Układem bazowym przestrzeni afinicznej W=p+V nazywamy ciąg p⁢;α1,α2,…,αn, gdzie ciąg α1,α2,…,αn jest bazą przestrzeni liniowej V.

Każdy układ bazowy wyznacza izomorfizm afiniczny przestrzeni W na Rn zadany wzorem: φ⁢p+∑i=1n⁢ai⁢αi=a1,a2,…,an.

Definicja 2.4

Niech T będzie niepustym podzbiorem przestrzeni afinicznej Rn. Symbolem a⁢f⁢T oznaczać będziemy podprzestrzeń afiniczną rozpiętą przez T, czyli zbiór wszystkich środków ciężkości punktów z T.

To znaczy. Jeżeli p0∈T to a⁢f⁢T⁢=p0+l⁢i⁢n⁢p0,p→⁢|⁢p∈T=⁢p0+∑i=1kai⁢p0,pi→⁢|⁢p∈T=∑i=0kai⁢pi⁢|⁢p∈T,∑i=0kai=1. gdzie ciąg a0,a1,…,ak jest układem wag.

Uwaga 2.1

Z dowolnego ciągu liczb rzeczywistych a1,a2,…,ak można zrobić układ wag a0,a1,a2,…,ak przyjmując a0=1-∑i=1kai.

Definicja 2.5

Wymiarem zbioru T nazywamy wymiar przestrzeni a⁢f⁢T.

Definicja 2.6

Niech T będzie niepustym podzbiorem przestrzeni afinicznej Rn. Symbolem C⁢o⁢n⁢v⁢T zbiór wszystkich środków ciężkości punktów z T o wagach nieujemnych.

To znaczy. Jeżeli p0∈T to Conv(T)={∑i=0kaipi|pi∈T,∑i=0kai=1,ai≥0}=={p0+a0p0,p0→+∑i=1kaip0,pi→|pi∈T,∑i=0kai=1,ai≥0}=={p0+∑i=1kaip0,pi→,|pi∈T,∑i=1kai≤1,ai≥0}.

Przykład 2.1

Uwypukleniem trzech punktów A=0,0, B=0,2 i C=5,2 jest trójkąt △⁢A⁢B⁢C=C⁢o⁢n⁢v⁢A,B,C=a1⁢A+a2⁢B+a3⁢C⁢|⁢a1+a2+a3=1,ai≥0=5⁢a3,2⁢a2+2⁢a3⁢|⁢a1+a2+a3=1,ai≥0=0,0+a2⁢0,2+a3⁢5,2⁢|⁢a2+a3≤1,ai≥0

Twierdzenie 2.2

C⁢o⁢n⁢v⁢T jest najmniejszym zbiorem wypukłym zawierającym T.

1) Wypukłość.

Niech p=∑i=0k⁢ai⁢pi oraz q=∑i=0k⁢bi⁢pi będą dwoma punktami z C⁢o⁢n⁢v⁢⁢T. Zatem pi∈T, ∑i=0kai=1=∑i=0kbi oraz ai≥0,⁢bi≥0. Dowolny punkt odcinka p,q jest postaci 1-t⁢p+t⁢q, gdzie t∈0,1. Teraz 1-t⁢p+t⁢q=1-t⁢∑i=0k⁢ai⁢pi+t⁢∑i=0k⁢bi⁢pi=∑i=0k1-t⁢ai+t⁢bi⁢pi∈C⁢o⁢n⁢v⁢T, gdyż ∑i=0k1-t⁢ai+t⁢bi=1 i współczynniki są nieujemne.

2) Minimalność.

Niech X będzie zbiorem wypukłym zawierającym T. Pokażemy przez indukcję względem długości zapisu kombinacji wypukłej, że każdy punkt z C⁢o⁢n⁢v⁢T należy do X.

Niech p=∑i=0k⁢ai⁢pi∈C⁢o⁢n⁢v⁢⁢T, gdzie pi∈T, ∑i=0kai=1 oraz ai≥0.

10k=0. Wtedy p=p0∈T⊂X.

20 Krok indukcyjny. Zakładamy, że k>0 i każda kombinacja wypukła długości <k należy do X.

Punkt p przedstawiamy w postaci kombinacji wypukłej p=∑i=0k⁢ai⁢pi=a0⁢p0+1-a0⁢q, gdzie q=∑i=1k⁢ai1-a0⁢pi. Ponadto punkt q∈X z założenia indukcyjnego. Gdyby 1-a0=0 to p=p0.

∎

Definicja 2.7

Hiperpłaszczyzną V podpierającą zbiór wypukły W⊂Rn w punkcie p nazywamy taką podprzestrzeń afiniczną V, że: d⁢i⁢m⁢V=n-1, p∈V, W leży po jednej stronie V to znaczy istnieje taka półprzestrzeń H zawierająca W, że V=∂⁡H jest brzegiem i p∈∂⁡H. Inaczej mówiąc V jest opisana równaniem

V=x∈Rn⁢|⁢α∙x=b,

gdzie α∈Rni b∈R są takie, że ∀x∈W⁢⁢α∙x≤b oraz α∙p=b.

Twierdzenie 2.3

Jeżeli W jest zbiorem wypukłym i domkniętym i p∈∂⁡W (p należy do brzegu W) to istnieje hiperpłaszczyzna podpierająca zbiór W w punkcie p.

Niech p∈∂⁡W

Istnieje zatem ciąg punktów p1,p2,… ∉W taki że ϱ⁢pi,p<1i.

Z każdym z tych punktów związujemy pewną hiperpłaszczyznę rozdzielającą wyznaczoną przez wektory αi oraz liczby bi spełniające warunki:

1∘ pi∙αi⁢>bi

2∘⁢⁢∀q∈W⁢q∙αi⁢≤bi

(x∈Rn⁢|⁢x∙αi⁢≤bi jest półprzestrzenią zawierającą W, której brzeg jest hiperpłaszczyzną rozdzielającą pi oraz W)

3∘⁢αi∙αi⁢+bi2 =1

Przyjmijmy αi¯=αi,bi∈Rn+1.

Zbiór α1¯, α2¯, … jest zwarty w kuli jednostkowej K⁢0,1⊂Rn+1. Ponieważ K⁢0,1 jest zwarta, to w ciągu ai¯ możemy wybrać podciąg zbieżny (ze względów redakcyjnych przyjmujemy, bez zmniejszenia ogólności, że αi¯ jest zbieżny ).

Oznacza to, że zbieżne też są ciągi αi oraz bi.

Przyjmijmy:

l⁢i⁢mi→∞αi=α

l⁢i⁢mi→∞bi=b

Ponadto l⁢i⁢mi→∞ αi¯=α¯⁢ implikuje α¯=1.

Badamy H=x⁢|⁢α∙x⁢≤b.

Dla dowolnego punktu q∈W αi∙q⁢≤bi więc α∙q⁢≤b (bo nierówności tępe zachowują się przy przejściu do granicy). Więc W⊆H.

Aby wykazać, że ∂⁡H jest hiperpłaszczyzną podpierającą W w punkcie p wystarczy pokazać α∙p=b. Ponieważ p∈W więc α∙p⁢≤b. Ponadto p∙a⁢=l⁢i⁢mi→∞⁢p∙ai⁢≥⁢l⁢i⁢mi→∞⁢⁢bi=b

∎

2.2. Wielościany

Definicja 2.8

Wielościanem (uogólnionym) w Rn nazywamy część wspólną skończonej rodziny półprzestrzeni.

W szczególności zbiór pusty ∅ i Rn jako przecięcie pustej rodziny półprzestrzeni są wielościanami.

Ponieważ każdy zbiór wypukły i domknięty jest przecięciem półprzestrzeni, patrz twierdzenie 1.7, więc może być aproksymowany wielościanami z dowolną dokładnością. Szukanie ekstremów funkcji tylko na wielościanach nie jest więc poważnym ograniczeniem.

Tak jak trójkąt jest trójkątem niezależnie czy traktujemy go jako podzbiór płaszczyzny, przestrzeni 3 - wymiarowej czy większej tak też następne twierdzenie pokazuje, że pojęcie wielościanu nie zależy od wymiaru przestrzeni.

Twierdzenie 2.4

Definicja wielościanu nie zależy od przestrzeni w której go rozpatrujemy. W szczególności jeżeli W jest niepustym podzbiorem w przestrzeniach afinicznych V1⊂V2. Wówczas W jest wielościanem w V1 wtedy i tylko wtedy, gdy W jest wielościanem w V2.

Przyjmijmy V1≃Rn i V2≃Rt

⇒

Wprowadźmy układ bazowy p;α1,α2,…,αn przestrzeni V1 i rozszerzamy go do układu bazowego p;α1,α2,…,αn,αn+1,…,αt przestrzeni V2. Teraz jeżeli W=⋂i=1kHi, gdzie Hi⊂V1 są opisane nierównościami Hi=x⁢|⁢ai,1,ai,2,…,ai,n∙x⁢≤bi to w przestrzeni V2 zbiór W jest opisany układem nierówności: ai,1,ai,2,…,ai,n,0,…,0∙x⁢≤bi dla 1≤i≤k oraz xj≤0 i -xj≤0 dla n+1≤j≤t.

⇐ Niech W=⋂i=1kHi, gdzie Hi są półprzestrzeniami V2. Teraz W=⋂i=1kHi∩V1 a oczywistym jest, że Hi∩V1 może być półprzestrzenią w V1 lub całą przestrzenią V1.

∎

Definicja 2.9

Ścianą zbioru wypukłego W nazywamy zbiór W∩V gdzie V jest hiperpłaszczyzną podpierającą.

Wymiarem ściany nazywamy liczbę j=d⁢i⁢m⁢⁢a⁢f⁢W∩V.

Wierzchołkiem nazywamy taki punkt p∈W, że istnieje półprzestrzeń H taka, że W⊂H⁢ i p=∂⁡H∩W.

Uwaga 2.2

Zwykle wierzchołkiem nazywać będziemy nie tylko zbiór p ale także punkt p.

KrawędziąK nazywamy ścianę wymiaru 1. Dokładniej K=∂⁡H∩W jest krawędzią gdy jest podzbiorem prostej mającym więcej niż 1 element. ( H jest półprzestrzenią i W⊂H ).

Twierdzenie 2.5

Rozpatrujemy zadanie optymalizacji liniowej:

M⁢a⁢x⁢⁢x0=c∙x⁢, gdzie x∈W i W jest opisane układem nierówności: ⁡α1∙x⁢≤b1α2∙x⁢≤b2⋮αt∙x⁢≤bt⁢.

Niech p∈W będzie takim punktem, że αi∙p⁢=bi, dla i=1,2,…,j oraz αi∙p⁢<bi, dla i>j. Wówczas:

1) Jeżeli dla pewnych liczb rzeczywistych r1≥0,r2≥0,…,rj≥0

c=∑i=1j⁢ri⁢αi to p jest punktem optymalnym tego zadania.

2) Jeżeli p jest punktem optymalnym tego zadania to ∂⁡H=x∈Rn⁢|⁢c∙x⁢=c∙p⁢ jest hiperpłaszczyzną podpierającą W w punkcie p.

ad 1) Niech q∈W. Wtedy x0⁢q=c∙q=∑i=1j⁢ri⁢αi∙q≤∑i=1j⁢ri⁢bi=∑i=1j⁢ri⁢αi∙p=x0⁢p. Więc punkt p jest optymalny.

ad 2) Niech q∈W. Wtedy x0⁢q≤x0⁢p, co daje c∙q≤c∙p. Zatem q∈H=x∈Rn⁢|⁢c∙x⁢≤c∙p⁢ i p∈∂⁡H=x∈Rn⁢|⁢c∙x⁢=c∙p⁢.

∎

Uwaga 2.3

Jednym z podstawowych twierdzeń teorii dualności jest:

p jest punktem optymalnym tego zadania wtedy i tylko wtedy gdy dla pewnych liczb rzeczywistych r1≥0,r2≥0,…,rj≥0 zachodzi c=∑i=1j⁢ri⁢αi.

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∩∂⁡H będzie ścianą wielościanu W.

Jeżeli S≠W to d⁢i⁢m⁢⁢S<d⁢i⁢m⁢⁢W.

Niech q∈W∖S. Ponieważ ∂⁡H jest przestrzenią afiniczną więc a⁢f⁢S⊂∂⁡H i q∉∂⁡H. Zatem a⁢f⁢S≠a⁢f⁢W co implikuje d⁢i⁢m⁢⁢S<d⁢i⁢m⁢⁢W.

∎

Lemat 2.1

Niech S1,S2,…,St będą ścianami wielościanu W⊂Rn. Wówczas S=⋂⁢i=1⁢t⁢Si jest ścianą W lub zbiorem pustym.

Niech Si=W∩∂⁡Hi, gdzie Hi=x∈Rn⁢|⁢αi∙x⁢≤bi. Definiujemy półprzestrzeń H=x∈Rn⁢|⁢∑i=1tαi∙x⁢≤∑i=1tbi. Oczywiście jeżeli q∈W to ∀i⁢αi∙x⁢=bi implikuje q∈H. Ponadto S⊂∂⁡H.

Niech teraz q∈∂⁡H∩W wtedy warunki ∀i≤t⁢αi∙q⁢≤bi oraz ∑i=1tαi∙q⁢=∑i=1tbi implikują αi∙q⁢=bi dla i≤t. Zatem S=∂⁡H∩W.

∎

Lemat 2.2

Niech K⊂H będzie j-wymiarową kulą o środku p zawartą w półprzestrzeni H. Jeżeli p∈∂⁡H to K⊂∂⁡H.

Niech q∈K∩H⁢⁢q∉∂⁡H. Przyjmijmy:

H=x∈Rn⁢|⁢α∙x⁢≤b wtedy α∙q⁢<b i α∙p⁢=b.

Ale p=12⁢q+12⁢q′⁢ dla pewnego q′∈K

Dochodzimy do sprzeczności, gdyż z jednej strony

q′∈K⊂H implikuje α∙q′≤b

zaś z drugiej strony

α∙q′=α∙2⁢p-q=2⁢α∙p⁢-α∙q⁢=2⁢b-α∙q⁢>b.

∎

Definicja 2.10

Niech H=x∈Rn⁢|⁢α∙x⁢≤b będzie półprzestrzenią. Półprzestrzenią dopełniającą nazywamy półprzestrzeń H-=x∈Rn⁢|⁢α∙x⁢≥b

Stwierdzenie 2.2

Jeżeli H jest półprzestrzenią to H∪H-=Rn i H∩H-=∂⁡H=∂⁡H-.

Stwierdzenie to prowadzi bezpośrednio do wniosku.

Wniosek 2.1

Niech W=⋂i=1tHi⁢⊂Rn będzie wielościanem. Wówczas, dla każdego j, S=W∩∂⁡Hj=W∩Hj- jest ścianą wielościanu W lub zbiorem pustym.

Wniosek 2.2

Niech W=⋂i=1t⁢Hi zaś S=W⁢∩⁢⋂i=1s⁢Hi- będzie niepustym podzbiorem. Wówczas S jest ścianą W.

S=W⁢∩⁢⋂i=1s⁢Hi-=⋂i=1sW∩⁢Hi- jest przecięciem ścian a więc ścianą na mocy lematu 2.1.

∎

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Optymalizacja I