4.1. Twierdzenia strukturalne
Zajmiemy się teraz innym opisem wielościanów.
Twierdzenie 4.1 (Twierdzenie strukturalne)
1) Niech p1,p2,…,pt oraz α1,α2,…,αk należą do Rn. pi traktujemy jako
punkty, zaś αj jako wektory. Wówczas zbiór
S=∑i=1tripi+∑j=1ksjαj|∑i=1tri=1,ri≥0,sj≥0.
jest wielościanem.
2) Jeżeli W jest wielościanem to istnieją takie punkty p1,p2,…,pt oraz wektory α1,α2,…,αk, że W=∑i=1tripi+∑j=1ksjαj|∑i=1tri=1,ri≥0,sj≥0.
3) Jeżeli W jest wielościanem z wierzchołkiem, gdzie p1,p2,…,pt jest zbiorem wierzchołków W, zaś α1,α2,…,αk jest zbiorem wektorów kierunkowych krawędzi nieograniczonych, to W=∑i=1tripi+∑j=1ksjαj|∑i=1tri=1,ri≥0,sj≥0.
Twierdzenie to ma skomplikowany dowód więc przedstawimy go dopiero po wprowadzeniu teorii dualności.
Z twierdzenia strukturalnego wynika,
że każdy wielościan można przedstawić w postaci sumy algebraicznej dwóch zbiorów. Gdy
W=∑i=1tripi+∑j=1ksjαj|∑i=1tri=1,∀1≤i≤tri≥0,∀1≤j≤ksj≥0
to W=T+S, gdzie T=∑i=1tripi|∑i=1tri=1,∀1≤i≤tri≥0 jest wielościanem klasycznym zaś S=p1+∑j=1ksjαj|∀1≤j≤ksj≥0 jest stożkiem.
Aby przybliżyć twierdzenie przedstawimy przykład gdy W jest sympleksem:
Przykład 4.1
Niech p0,p1,⋯,pn będzie układem punktów z Rn w
położeniu ogólnym
takim, że detp01p11⋮⋮pn1>0. Wówczas W=Convp0,p1,⋯,pn jest
wielościanem opisanym układem n+1 nierówności:
0) detx1x2⋯xn1p11⋮⋮pn1≥0
1) detp01x1x2⋯xn1p2⋮⋮pn1≥0
⋮
n) detp01p11⋮⋮pn-11x1x2⋯xn1≥0.
Ponadto zbiorem wierzchołków W jest p0,p1,⋯,pn
zaś krawędziami są odcinki łączące dowolne dwa wierzchołki.
Niech q∈Rn będzie dowolnym punktem. Ponieważ ciąg p0,p1,⋯,pn jest bazą punktową Rn więc istnieje taki układ wag r0,r1,⋯,rn, (∑i=0nri=1), że q=∑i=0nripi. Badamy kiedy punkt q spełnia j - tą nierówność.
detp01⋮⋮pj-11q1pj+11⋮⋮pn1=detp01⋮⋮pj-11∑i=0nripi∑i=0nripj+11⋮⋮pn1=
teraz dla i≠j od j-tego wiersza macierzy odejmujemy wiersz i-ty pomnożony przez ri.
=det[p01⋮⋮pj-11rjpjrjpj+11⋮⋮pn1]=rj⋅det[p01p11⋮⋮pn1].
Ponieważ przyjęliśmy p01p11⋮⋮pn1>0, więc punkt q spełnia j - tą nierówność wtedy i tylko wtedy gdy rj≥0. Zatem punkt q∈W wtedy i tylko wtedy, gdy spełnia wszystkie n+1 nierówności.
Ponieważ dla każdego j punkt pj spełnia wszystkie za wyjątkiem j - tej nierówności jako równania więc jest wierzchołkiem. Więcej wierzchołków nie ma gdyż n nierówności ze zbioru n+1 elementowego można wybrać na n+1 sposobów.
Podobnie n-1 nierówności można wybrać na n+1n-1=nn+12 sposobów, czyli tyle ile jest par wierzchołków.
∎
Rozpoczynamy od badania wielościanów podobnych do stożków. Wprowadźmy zatem formalną definicję.
Definicja 4.1
S-wielościanem nazywamy wielościan który ma dokładnie jeden wierzchołek.
Stwierdzenie 4.1
Ściana s-wielościanu jest s-wielościanem.
Niech S będzie ścianą s-wielościanu W. Na mocy twierdzenia 3.5 ściana S ma wierzchołek i jest to jedyny wierzchołek.
∎
Stwierdzenie 4.2
Jeżeli s-wielościan W ma więcej niż jeden punkt to ma krawędź nieskończoną.
Niech p=W∩∂H będzie wierzchołkiem W zaś q dowolnym innym punktem
s-wielościanu. Teraz S=W∩∂H+p,q→ jest wielościanem zawierającym q, a nie zawierającym p. S ma wierzchołki na mocy wniosku 3.4. Niech q1 będzie wierzchołkiem S. Wówczas q1 leży na przecięciu brzegów n liniowo niezależnych półprzestrzeni opisujących S. Jednym z nich jest ∂H+p,q→ a pozostałe n-1 opisują W. Zatem q1 należy do krawędzi W i p,q1→ jest wektorem krawędzi nieskończonej.
∎
Lemat 4.1
Niech p będzie punktem wielościanu W. Jeżeli wektor β spełnia warunek:
∀r≥0p+rβ∈W to ∀q∈W∀r≥0q+rβ∈W.
1) Niech W=x∈Rn|α∙x≤b będzie
półprzestrzenią. Teraz:
∀r≥0α∙p+rβ≤b
∀r≥0α∙p+rα∙β≤b
∀r≥0rα∙β≤b-α∙p
to implikuje α∙β≤0
∀r≥0α∙q+rβ=α∙q+rα∙β≤α∙q≤b
2) Niech W=⋂i=1tHi będzie przecięciem półprzestrzeni. Jeżeli ∀r≥0p+rβ∈W, to
∀i∀r≥0p+rβ∈Hi, a z kroku 1) ∀i∀q∈Hi∀r≥0q+rβ∈W. Zatem ∀q∈W∀r≥0q+rβ∈W.
∎
Uwaga. Lemat pozostaje prawdziwy gdy założenie ”W jest wielościanem” zastąpimy ”W jest zbiorem wypukłym i domkniętym”.
Twierdzenie 4.2
Niech W∈Rn będzie s-wielościanem. Wówczas
W=p+∑j=1ksjαj|sj≥0 gdzie p jest wierzchołkiem W zaś α1,α2,…,αk jest zbiorem wektorów kierunkowych krawędzi nieograniczonych.
Z lematu 4.1 wynika inkluzja W⊇p+∑j=1ksjαj|sj≥0
Dowód przeciwnej inkluzji przeprowadzimy przez indukcję względem wymiaru W.
10 Jeżeli dimW=0 to Wjest punktem i dowód jest oczywisty.
20 Niech p będzie wierzchołkiem s-wielościanu W=⋂i=1tHi zaś q dowolnym innym punktem W. Niech α będzie wektorem krawędzi nieskończonej.
1) Jeżeli q należy do krawędzi o wektorze kierunkowym α to q=p+rα dla pewnego r≥0.
2) Przypuśćmy, że q nie należy do żadnej krawędzi. Prosta l=q+rα|r∈R przecięta z W daje półprostą. Nazwijmy jej początek q1. Istnieje teraz j≤t takie, że q1∈∂Hj. Ściana W∩∂Hj ma mniejszy wymiar niż W więc z założenia indukcyjnego q1=p+∑i=1ksiαi dla pewnych sj≥0 i wektorów kierunkowych krawędzi nieograniczonych α1,α2,…,αk. Zatem q=q1+sα=p+∑i=1ksiαi+sα ma żądane przedstawienie.
∎
Lemat 4.2
Niech punkt p będzie wierzchołkiem wielościanu W. Wówczas istnieje wielościan Wp spełniający warunki:
a) Punkt p jest wierzchołkiem wielościanu Wp.
b) W⊂Wp.
c) Jeżeli ki jest krawędzią wielościanu Wp, to si=ki∩W jest krawędzią wielościanu W.
Niech W=⋂i=1tHi będzie przecięciem półprzestrzeni, gdzie Hi=x|αi∙x≤bi. Przenumerowując półprzestrzenie w razie potrzeby możemy przyjąć, że p∈∂Hi⇔1≤i≤k.
Zdefiniujmy Wp=⋂i=1kHi.
Wtedy W⊆Wp i p jest jedynym wierzchołkiem
Wp, gdyż na mocy twierdzenia 3.2 p jest wierzchołkiem W⇔rzα1⋮αk=n ⇒p jest wierzchołkiem Wp.
Niech teraz ki=p+rα|r≥0 będzie krawędzią wielościanu Wp. Wówczas ki=Wp∩∂H, dla pewnej półprzestrzeni H zawierającej Wp. Ponieważ p∈W∩∂H⊂Wp∩∂H więc wystarczy wykazać, że ściana W∩∂H do której należy p nie jest jedno punktowa. Dla każdego j>k istnieje εj>0 taki, że εjα<ϱp;∂Hj . Przyjmując ε=minεjjk otrzymujemy p+εα∈Hi dla i>k. Zatem p+εα∈W oraz p+εα∈W∩∂H.
∎
4.2. Geometryczny algorytm metody sympleks
Definicja 4.2
Rozważmy zagadnienie PL
Maxx0=c∙x:x∈W
Niech p będzie wierzchołkiem W, zaś α wektorem
kierunkowym krawędzi wychodzącej z wierzchołka p
p+tαt0 lub p+tα|t∈0,r jest krawędzią.
Krawędź tą nazywamy:
poprawiającą gdy c∙α>0,
neutralną gdy c∙α=0,
pogarszającą gdy c∙α<0.
W przypadku zadania Minx0=d∙x|x∈W krawędź nazywamy:
poprawiającą gdy d∙α<0,
neutralną gdy d∙α=0,
pogarszającą gdy d∙α>0.
Twierdzenie 4.3
Jeśli z wierzchołka p wielościanu W nie wychodzi
żadna krawędź poprawiająca to p jest punktem optymalnym zadania
PL
Inaczej mówiąc, dla zadań typu Maxx0=c∙x|x∈W.
Jeżeli p jest wierzchołkiem wielościanu W i
jeśli dla każdego wektora α, kierunkowego dla krawędzi wychodzącej z p, iloczyn skalarny c∙α ≤0 to ∀q∈W c∙p≥ c∙q.
Niech Wp będzie wielościanem z lematu 4.2. Wówczas
na mocy twierdzenia 4.2 Wp jako s - wielościanem można opisać
Wp=p+∑i=1mriαi|ri≥0, gdzie
α1,α2,…,αm są wszystkimi wektorami kierunkowymi
krawędzi Wp a więc wektorami kierunkowymi krawędzi wielościanu W wychodzących z p.
Weźmy dowolny punkt q∈W. Wtedy q∈Wp=p+∑i=1mriαi.
Zatem
x0q=c∙q=c∙p+∑i=1mriαi=c∙p+∑i=1mri∙αi≤c∙p=x0p.
∎
Wniosek 4.1
Jeśli zadanie PL ma rozwiązanie i wielościan będący obszarem dopuszczalnym ma wierzchołek to istnieje wierzchołek obszaru
dopuszczalnego, który jest punktem optymalnym.
Wniosek 4.2
Badając krawędzie wychodzące z wierzchołka p możemy
rozstrzygnąć, czy jest to punkt optymalny.
Geometryczny algorytm metody sympleks.
|
|
Dany wielościan opisany układem t nierówności w Rn. Dany |
wierzchołek p (startowy). |
|
x= zmienna (punkty) |
|
α= zmienna (wektory) |
|
0) x:=p |
|
1) Budujemy tablicę T złożona z kandydatów na krawędzie |
|
wychodzące z wierzchołka x |
|
2) Dopóki T≠∅ wykonujemy |
|
3) Wybieramy krawędź k z T i usuwamy |
|
4) Jeżeli k jest krawędzią |
|
poprawiającą to: |
|
5) Jeżeli k jest krawędzią |
|
nieskończoną to STOP: zadanie nieograniczone. |
|
6) Jeżeli k jest krawędzią skończoną to: |
|
7) Znajdujemy jej drugi koniec q |
|
x:=q i wracamy do punktu 1) |
|
8) T=∅ STOP: x jest wierzchołkiem optymalnym. |
Uwaga 4.1
Algorytm sympleks jest skończony, gdyż wielościan
ma skończoną liczbę wierzchołków i krawędzi.
Przykład 4.2
Badamy zadanie Maxx0=3x1-2x2, gdzie
x1-x2≤2x2≤5
x1≥0,x2≥0
Jako wierzchołek startowy weźmiemy punkt 0,0.
x1=0x2=0 pochodzącym z dwóch ostatnich
nierówności.
Wychodzą z niego dwie krawędzie w kierunku wektora 1,0 -
poprawiająca i w kierunku wektora 0,1 - pogarszająca.
Wybieramy krawędź 0,0+t1,0 i szukamy ograniczenia na t
podstawiając do pozostałych nierówności. t≤20≤5t≥0
Więc t∈0,2 i drugim końcem krawędzi jest wierzchołek
2,0 opisany układem x1-x2=2x2=0
pochodzącym z pierwszej i ostatniej
nierówności. Opuszczając pierwszą równość otrzymamy krawędź,
którą przyszliśmy a więc z punktu widzenia wierzchołka 2,0
krawędź pogarszającą. Opuszczamy równanie x2=0.
Równanie x1-x2=2
opisuje prostą 2+t,t;t∈R.
Wstawiamy do pozostałych
nierówności i otrzymujemy:
Więc t∈0,5 i drugim końcem krawędzi jest wierzchołek
7,5 opisany układem x1-x2=2x2=5
pochodzącym z pierwszej i drugiej
nierówności. Zauważmy, że funkcja celu wzrosła z 2 do 3⋅7-2⋅5=11 więc krawędź była poprawiająca.
Z wierzchołka 7,5 wychodzą dwie krawędzie, pogarszająca,
którą przyszliśmy i leżąca na prostej opisanej równaniem x2=5. Wstawiając do pierwszej nierówności otrzymujemy
x1-5≤2. Więc wektorem kierunkowym jest -1,0. Jest to krawędź
pogarszająca i stąd 7,5 jest wierzchołkiem optymalnym.
Zadania
Ćwiczenie 4.1
Niech W∈R3 będzie wielościanem opisanym układem:
x1-2x2+x3≤32x1-3x2-3x3≤23x1-5x2-2x3≤5
x1≥0, x2≥0, x3∈R
a) Dla każdego z punktów: A=0,0,0 , B=0,0,3 , C=1,1,1 , D=4,1,1 wylicz najmniejszy wymiar ściany W do której ów punkt należy.
b) Opisz wszystkie krawędzie W zawierające punkt A=0,0,0.
Ćwiczenie 4.2
Opisz prosty algorytm metody sympleks na przykładzie zadania:
Max x0=3x1+2x2-7x3 , gdy:
x1+2x2-3x3≤3
2x1+8x2-4x3≤8
2x1-3x2-7x3≤9
x1≥0, x2≥0, x3≥0
Ćwiczenie 4.3
Niech W będzie niepustym wielościanem zawartym w Kθ,50
- kuli o środku w początku układu współrzędnych i promieniu 50
zawartej w R20. Badamy graf G niezorientowany, którego wierzchołki są
wierzchołkami W zaś krawędzie są krawędziami W.
a) Udowodnij, że G jest skończonym grafem spójnym.
b) Udowodnij, że G jest drzewem wtedy i tylko wtedy gdy W ma
co najwyżej jedną krawędź.
Ćwiczenie 4.4
Niech p będzie wierzchołkiem optymalnym zadania PL o obszarze dopuszczalnym W. Wiemy, że spośród krawędzi wychodzących z p tylko jedna krawędź k jest neutralna. Udowodnij, że k jest zbiorem punktów optymalnych.