Zagadnienia

4. Geometryczna metoda sympleks

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,ri0,sj0.

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,ri0,sj0.

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,ri0,sj0.

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,1itri0,1jksj0 to W=T+S, gdzie T=i=1tripi|i=1tri=1,1itri0 jest wielościanem klasycznym zaś S=p1+j=1ksjαj|1jksj0 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 detp01p11pn1>0. Wówczas W=Convp0,p1,,pn jest wielościanem opisanym układem n+1 nierówności:

0) detx1x2xn1p11pn10

1) detp01x1x2xn1p2pn10

n) detp01p11pn-11x1x2xn10.

Ponadto zbiorem wierzchołków W jest p0,p1,,pn zaś krawędziami są odcinki łączące dowolne dwa wierzchołki.

Niech qRn 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ść.

detp01pj-11q1pj+11pn1=detp01pj-11i=0nripii=0nripj+11pn1=

teraz dla ij od j-tego wiersza macierzy odejmujemy wiersz i-ty pomnożony przez ri.

=det[p01pj-11rjpjrjpj+11pn1]=rjdet[p01p11pn1].

Ponieważ przyjęliśmy p01p11pn1>0, więc punkt q spełnia j - tą nierówność wtedy i tylko wtedy gdy rj0. Zatem punkt qW 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=WH będzie wierzchołkiem W zaś q dowolnym innym punktem s-wielościanu. Teraz S=WH+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:

r0p+rβW to qWr0q+rβW.

1) Niech W=xRn|αxb będzie półprzestrzenią. Teraz:

r0αp+rβb

r0αp+rαβb

r0rαβb-αp

to implikuje αβ0

r0αq+rβ=αq+rαβαqb

2) Niech W=i=1tHi będzie przecięciem półprzestrzeni. Jeżeli r0p+rβW, to ir0p+rβHi, a z kroku 1) iqHir0q+rβW. Zatem qWr0q+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 WRn będzie s-wielościanem. Wówczas W=p+j=1ksjαj|sj0 gdzie p jest wierzchołkiem W zaś α1,α2,,αk jest zbiorem wektorów kierunkowych krawędzi nieograniczonych.

Z lematu 4.1 wynika inkluzja Wp+j=1ksjαj|sj0

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 r0.

2) Przypuśćmy, że q nie należy do żadnej krawędzi. Prosta l=q+rα|rR przecięta z W daje półprostą. Nazwijmy jej początek q1. Istnieje teraz jt takie, że q1Hj. Ściana WHj ma mniejszy wymiar niż W więc z założenia indukcyjnego q1=p+i=1ksiαi dla pewnych sj0 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) WWp.

c) Jeżeli ki jest krawędzią wielościanu Wp, to si=kiW jest krawędzią wielościanu W.

Niech W=i=1tHi będzie przecięciem półprzestrzeni, gdzie Hi=x|αixbi. Przenumerowując półprzestrzenie w razie potrzeby możemy przyjąć, że pHi1ik.

Zdefiniujmy Wp=i=1kHi.

Wtedy WWp i p jest jedynym wierzchołkiem Wp, gdyż na mocy twierdzenia 3.2 p jest wierzchołkiem Wrzα1αk=n p jest wierzchołkiem Wp.

Niech teraz ki=p+rα|r0 będzie krawędzią wielościanu Wp. Wówczas ki=WpH, dla pewnej półprzestrzeni H zawierającej Wp. Ponieważ pWHWpH więc wystarczy wykazać, że ściana WH 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+εαWH.

4.2. Geometryczny algorytm metody sympleks

Definicja 4.2

Rozważmy zagadnienie PL

Maxx0=cx:xW

Niech p będzie wierzchołkiem W, zaś α wektorem kierunkowym krawędzi wychodzącej z wierzchołka p

p+tαt0 lub p+tα|t0,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=dx|xW 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=cx|xW.

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 qW cp cq.

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|ri0, 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 qW. Wtedy qWp=p+i=1mriαi.

Zatem

x0q=cq=cp+i=1mriαi=cp+i=1mriαicp=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-x22x25

x10,x20

Jako wierzchołek startowy weźmiemy punkt 0,0.

Jest on opisany układem

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. t205t0

Więc t0,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;tR.

Wstawiamy do pozostałych nierówności i otrzymujemy:

t5t+20t0.

Więc t0,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 37-25=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-52. 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 WR3 będzie wielościanem opisanym układem:

x1-2x2+x332x1-3x2-3x323x1-5x2-2x35

x10, x20, x3R

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-3x33

2x1+8x2-4x38

2x1-3x2-7x39

x10, x20, x30

Ć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.

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

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.