Zbiorowi ciągów elementowych o współczynnikach rzeczywistych
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ą.
Układem wag nazywamy taki ciąg liczb rzeczywistych , że
.
Niech
będzie ciągiem punktów z
. Środkiem ciężkości punktów
o wagach
nazywamy punkt
.
Branie środka ciężkości ma następujące własności:
1)
2)
3) Jeżeli i
to
.
Podprzestrzenią afiniczną nazywamy podzbiór zamknięty ze względu na branie środków ciężkości.
Niech W będzie niepustym podzbiorem . Wówczas równoważne są warunki:
1) W jest przestrzenią afiniczną.
2) W jest postaci , gdzie
i
jest podprzestrzenią liniową
.
3) W jest zbiorem rozwiązań pewnego układu równań liniowych.
Układem bazowym przestrzeni afinicznej nazywamy ciąg
, gdzie ciąg
jest bazą przestrzeni liniowej
.
Każdy układ bazowy wyznacza izomorfizm afiniczny przestrzeni na
zadany wzorem:
.
Niech będzie niepustym podzbiorem przestrzeni afinicznej
. Symbolem
oznaczać będziemy podprzestrzeń afiniczną
rozpiętą przez
, czyli zbiór wszystkich środków ciężkości
punktów z
.
To znaczy. Jeżeli to
. gdzie ciąg
jest układem wag.
Z dowolnego ciągu liczb rzeczywistych można zrobić układ wag
przyjmując
.
Wymiarem zbioru T nazywamy wymiar przestrzeni .
Niech będzie niepustym podzbiorem przestrzeni afinicznej
. Symbolem
zbiór wszystkich środków ciężkości
punktów z
o wagach nieujemnych.
To znaczy. Jeżeli to
.
Uwypukleniem trzech punktów ,
i
jest trójkąt
jest najmniejszym zbiorem wypukłym zawierającym
.
1) Wypukłość.
Niech oraz
będą dwoma punktami z
. Zatem
,
oraz
.
Dowolny punkt odcinka
jest postaci
, gdzie
.
Teraz
, gdyż
i
współczynniki są nieujemne.
2) Minimalność.
Niech będzie zbiorem wypukłym zawierającym
. Pokażemy przez indukcję względem długości zapisu kombinacji wypukłej, że każdy punkt z
należy do
.
Niech , gdzie
,
oraz
.
. Wtedy
.
Krok indukcyjny. Zakładamy, że
i każda kombinacja wypukła długości
należy do
.
Punkt przedstawiamy w postaci kombinacji wypukłej
, gdzie
. Ponadto punkt
z założenia indukcyjnego. Gdyby
to
.
Hiperpłaszczyzną podpierającą zbiór wypukły
w punkcie
nazywamy taką podprzestrzeń afiniczną
, że:
,
,
leży po jednej stronie
to znaczy istnieje taka
półprzestrzeń
zawierająca
, że
jest brzegiem
i
. Inaczej mówiąc
jest opisana równaniem
,
gdzie i
są takie, że
oraz
.
Jeżeli jest zbiorem wypukłym i domkniętym i
(
należy do brzegu
) to istnieje hiperpłaszczyzna
podpierająca zbiór
w punkcie
.
Niech
Istnieje zatem ciąg punktów
taki że
.
Z każdym z tych punktów związujemy pewną hiperpłaszczyznę
rozdzielającą wyznaczoną przez wektory oraz liczby
spełniające warunki:
1
( jest półprzestrzenią zawierającą W, której brzeg
jest hiperpłaszczyzną rozdzielającą
oraz
)
3
Przyjmijmy .
Zbiór ,
, … jest
zwarty w kuli jednostkowej
. Ponieważ
jest zwarta, to w ciągu
możemy wybrać
podciąg zbieżny (ze względów redakcyjnych przyjmujemy, bez
zmniejszenia ogólności, że
jest zbieżny ).
Oznacza to, że zbieżne też są ciągi oraz
.
Przyjmijmy:
Ponadto
implikuje
.
Badamy .
Dla dowolnego punktu
więc
(bo nierówności tępe zachowują
się przy przejściu do granicy). Więc
.
Aby wykazać, że jest hiperpłaszczyzną podpierającą
w punkcie
wystarczy pokazać
.
Ponieważ
więc
. Ponadto
Wielościanem (uogólnionym) w nazywamy część wspólną
skończonej rodziny półprzestrzeni.
W szczególności zbiór pusty i
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.
Definicja wielościanu nie zależy od przestrzeni w której go rozpatrujemy. W szczególności jeżeli
jest niepustym podzbiorem w przestrzeniach afinicznych
. Wówczas
jest wielościanem w
wtedy i tylko wtedy, gdy
jest wielościanem w
.
Przyjmijmy i
Wprowadźmy układ bazowy przestrzeni
i rozszerzamy go do układu bazowego
przestrzeni
. Teraz jeżeli
, gdzie
są opisane nierównościami
to w przestrzeni
zbiór
jest opisany układem nierówności:
dla
oraz
i
dla
.
Niech
, gdzie
są półprzestrzeniami
. Teraz
a oczywistym jest, że
może być półprzestrzenią w
lub całą przestrzenią
.
Ścianą zbioru wypukłego nazywamy zbiór
gdzie
jest
hiperpłaszczyzną podpierającą.
Wymiarem ściany nazywamy liczbę
Wierzchołkiem nazywamy taki punkt , że istnieje
półprzestrzeń H taka, że
i
.
Zwykle wierzchołkiem nazywać będziemy nie tylko zbiór ale także punkt
.
Krawędzią nazywamy ścianę wymiaru 1. Dokładniej
jest krawędzią gdy jest podzbiorem prostej mającym więcej niż 1 element.
(
jest półprzestrzenią i
).
Rozpatrujemy zadanie optymalizacji liniowej:
, gdzie
i
jest opisane układem nierówności:
.
Niech będzie takim punktem, że
, dla
oraz
,
dla
. Wówczas:
1) Jeżeli dla pewnych liczb rzeczywistych
to
jest punktem optymalnym
tego zadania.
2) Jeżeli jest punktem optymalnym tego zadania to
jest hiperpłaszczyzną podpierającą
w punkcie
.
ad 1) Niech . Wtedy
. Więc punkt
jest optymalny.
ad 2) Niech . Wtedy
, co daje
. Zatem
i
.
Jednym z podstawowych twierdzeń teorii dualności jest:
jest punktem optymalnym tego zadania wtedy i tylko wtedy gdy
dla pewnych liczb rzeczywistych
zachodzi
.
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.
Niech będzie ścianą wielościanu W.
Jeżeli to
.
Niech . Ponieważ
jest przestrzenią afiniczną więc
i
. Zatem
co implikuje
.
Niech będą ścianami wielościanu
.
Wówczas
jest ścianą
lub zbiorem pustym.
Niech , gdzie
. Definiujemy
półprzestrzeń
. Oczywiście
jeżeli
to
implikuje
. Ponadto
.
Niech teraz wtedy warunki
oraz
implikują
dla
. Zatem
.
Niech będzie j-wymiarową kulą o środku p zawartą w
półprzestrzeni
. Jeżeli
to
.
Niech . Przyjmijmy:
wtedy
i
.
Ale dla pewnego
Dochodzimy do sprzeczności, gdyż z jednej strony
implikuje
zaś z drugiej strony
.
Niech będzie półprzestrzenią.
Półprzestrzenią dopełniającą nazywamy półprzestrzeń
Jeżeli H jest półprzestrzenią to i
.
Stwierdzenie to prowadzi bezpośrednio do wniosku.
Niech będzie wielościanem.
Wówczas, dla każdego j,
jest ścianą wielościanu
lub zbiorem pustym.
Niech zaś
będzie niepustym podzbiorem. Wówczas S jest ścianą
.
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.
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.