Zajmiemy się teraz innym opisem wielościanów.
1) Niech oraz należą do . traktujemy jako punkty, zaś jako wektory. Wówczas zbiór
.
jest wielościanem.
2) Jeżeli jest wielościanem to istnieją takie punkty oraz wektory , że .
3) Jeżeli jest wielościanem z wierzchołkiem, gdzie jest zbiorem wierzchołków , zaś jest zbiorem wektorów kierunkowych krawędzi nieograniczonych, to .
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 to , gdzie jest wielościanem klasycznym zaś jest stożkiem.
Aby przybliżyć twierdzenie przedstawimy przykład gdy jest sympleksem:
Niech będzie układem punktów z w położeniu ogólnym takim, że . Wówczas jest wielościanem opisanym układem nierówności:
0)
1)
n) .
Ponadto zbiorem wierzchołków jest zaś krawędziami są odcinki łączące dowolne dwa wierzchołki.
Niech będzie dowolnym punktem. Ponieważ ciąg jest bazą punktową więc istnieje taki układ wag , (), że . Badamy kiedy punkt spełnia - tą nierówność.
teraz dla od j-tego wiersza macierzy odejmujemy wiersz i-ty pomnożony przez .
.
Ponieważ przyjęliśmy , więc punkt spełnia - tą nierówność wtedy i tylko wtedy gdy . Zatem punkt wtedy i tylko wtedy, gdy spełnia wszystkie nierówności.
Ponieważ dla każdego punkt spełnia wszystkie za wyjątkiem - tej nierówności jako równania więc jest wierzchołkiem. Więcej wierzchołków nie ma gdyż nierówności ze zbioru elementowego można wybrać na sposobów. Podobnie nierówności można wybrać na 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ę.
S-wielościanem nazywamy wielościan który ma dokładnie jeden wierzchołek.
Ściana s-wielościanu jest s-wielościanem.
Niech będzie ścianą s-wielościanu . Na mocy twierdzenia 3.5 ściana ma wierzchołek i jest to jedyny wierzchołek.
∎Jeżeli s-wielościan ma więcej niż jeden punkt to ma krawędź nieskończoną.
Niech będzie wierzchołkiem zaś dowolnym innym punktem s-wielościanu. Teraz jest wielościanem zawierającym , a nie zawierającym . ma wierzchołki na mocy wniosku 3.4. Niech będzie wierzchołkiem . Wówczas leży na przecięciu brzegów liniowo niezależnych półprzestrzeni opisujących . Jednym z nich jest a pozostałe opisują . Zatem należy do krawędzi i jest wektorem krawędzi nieskończonej.
∎Niech będzie punktem wielościanu . Jeżeli wektor spełnia warunek:
to .
1) Niech będzie półprzestrzenią. Teraz:
to implikuje
2) Niech będzie przecięciem półprzestrzeni. Jeżeli , to , a z kroku 1) . Zatem .
∎Uwaga. Lemat pozostaje prawdziwy gdy założenie ” jest wielościanem” zastąpimy ” jest zbiorem wypukłym i domkniętym”.
Niech będzie s-wielościanem. Wówczas gdzie jest wierzchołkiem zaś jest zbiorem wektorów kierunkowych krawędzi nieograniczonych.
Z lematu 4.1 wynika inkluzja
Dowód przeciwnej inkluzji przeprowadzimy przez indukcję względem wymiaru .
Jeżeli to jest punktem i dowód jest oczywisty.
Niech będzie wierzchołkiem s-wielościanu zaś dowolnym innym punktem . Niech będzie wektorem krawędzi nieskończonej.
1) Jeżeli należy do krawędzi o wektorze kierunkowym to dla pewnego .
2) Przypuśćmy, że nie należy do żadnej krawędzi. Prosta przecięta z daje półprostą. Nazwijmy jej początek . Istnieje teraz takie, że . Ściana ma mniejszy wymiar niż więc z założenia indukcyjnego dla pewnych i wektorów kierunkowych krawędzi nieograniczonych . Zatem ma żądane przedstawienie.
∎Niech punkt będzie wierzchołkiem wielościanu . Wówczas istnieje wielościan spełniający warunki:
a) Punkt jest wierzchołkiem wielościanu .
b) .
c) Jeżeli jest krawędzią wielościanu , to jest krawędzią wielościanu .
Niech będzie przecięciem półprzestrzeni, gdzie . Przenumerowując półprzestrzenie w razie potrzeby możemy przyjąć, że .
Zdefiniujmy .
Wtedy i jest jedynym wierzchołkiem , gdyż na mocy twierdzenia 3.2 jest wierzchołkiem jest wierzchołkiem .
Niech teraz będzie krawędzią wielościanu . Wówczas , dla pewnej półprzestrzeni zawierającej . Ponieważ więc wystarczy wykazać, że ściana do której należy nie jest jedno punktowa. Dla każdego istnieje taki, że . Przyjmując otrzymujemy dla . Zatem oraz .
∎Rozważmy zagadnienie
Niech będzie wierzchołkiem , zaś wektorem kierunkowym krawędzi wychodzącej z wierzchołka
lub jest krawędzią.
Krawędź tą nazywamy:
poprawiającą gdy ,
neutralną gdy ,
pogarszającą gdy .
W przypadku zadania krawędź nazywamy:
poprawiającą gdy ,
neutralną gdy ,
pogarszającą gdy .
Jeśli z wierzchołka wielościanu nie wychodzi żadna krawędź poprawiająca to jest punktem optymalnym zadania
Inaczej mówiąc, dla zadań typu .
Jeżeli jest wierzchołkiem wielościanu i jeśli dla każdego wektora , kierunkowego dla krawędzi wychodzącej z , iloczyn skalarny to .
Niech będzie wielościanem z lematu 4.2. Wówczas na mocy twierdzenia 4.2 jako s - wielościanem można opisać
, gdzie są wszystkimi wektorami kierunkowymi krawędzi a więc wektorami kierunkowymi krawędzi wielościanu wychodzących z .
Weźmy dowolny punkt . Wtedy .
Zatem
.
∎Jeśli zadanie 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.
Badając krawędzie wychodzące z wierzchołka możemy rozstrzygnąć, czy jest to punkt optymalny.
Dany wielościan opisany układem t nierówności w . Dany |
wierzchołek (startowy). |
zmienna (punkty) |
zmienna (wektory) |
0) |
1) Budujemy tablicę złożona z kandydatów na krawędzie |
wychodzące z wierzchołka |
2) Dopóki wykonujemy |
3) Wybieramy krawędź z i usuwamy |
4) Jeżeli jest krawędzią |
poprawiającą to: |
5) Jeżeli jest krawędzią |
nieskończoną to STOP: zadanie nieograniczone. |
6) Jeżeli jest krawędzią skończoną to: |
7) Znajdujemy jej drugi koniec |
i wracamy do punktu 1) |
8) STOP: jest wierzchołkiem optymalnym. |
Algorytm sympleks jest skończony, gdyż wielościan ma skończoną liczbę wierzchołków i krawędzi.
Badamy zadanie , gdzie
Jako wierzchołek startowy weźmiemy punkt .
Jest on opisany układem
pochodzącym z dwóch ostatnich nierówności.
Wychodzą z niego dwie krawędzie w kierunku wektora - poprawiająca i w kierunku wektora - pogarszająca.
Wybieramy krawędź i szukamy ograniczenia na podstawiając do pozostałych nierówności.
Więc i drugim końcem krawędzi jest wierzchołek opisany układem
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 krawędź pogarszającą. Opuszczamy równanie .
Równanie opisuje prostą .
Wstawiamy do pozostałych nierówności i otrzymujemy:
.
Więc i drugim końcem krawędzi jest wierzchołek opisany układem
pochodzącym z pierwszej i drugiej nierówności. Zauważmy, że funkcja celu wzrosła z 2 do więc krawędź była poprawiająca.
Z wierzchołka wychodzą dwie krawędzie, pogarszająca, którą przyszliśmy i leżąca na prostej opisanej równaniem . Wstawiając do pierwszej nierówności otrzymujemy . Więc wektorem kierunkowym jest . Jest to krawędź pogarszająca i stąd jest wierzchołkiem optymalnym.
Niech będzie wielościanem opisanym układem:
, ,
a) Dla każdego z punktów: , , , wylicz najmniejszy wymiar ściany do której ów punkt należy.
b) Opisz wszystkie krawędzie zawierające punkt .
Opisz prosty algorytm metody sympleks na przykładzie zadania:
Max , gdy:
, ,
Niech będzie niepustym wielościanem zawartym w - kuli o środku w początku układu współrzędnych i promieniu 50 zawartej w . Badamy graf niezorientowany, którego wierzchołki są wierzchołkami zaś krawędzie są krawędziami .
a) Udowodnij, że jest skończonym grafem spójnym.
b) Udowodnij, że jest drzewem wtedy i tylko wtedy gdy ma co najwyżej jedną krawędź.
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ź jest neutralna. Udowodnij, że jest zbiorem punktów optymalnych.
Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.
strona główna | webmaster | o portalu | pomoc
© Wydział Matematyki, Informatyki i Mechaniki UW, 2009-2010. Niniejsze materiały są udostępnione bezpłatnie na licencji Creative Commons Uznanie autorstwa-Użycie niekomercyjne-Bez utworów zależnych 3.0 Polska.
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.