Niech d⁢i⁢m⁢⁢S=n. Dzięki twierdzeniu 2.4 bez zmniejszenia ogólności możemy przyjąć, że S⊂Rn.

Wybieramy wszystkie wektory γ∈Rn spełniające warunki:

1) ∀1≤i≤t⁢⁢αi∙γ≤0.

2) Istnieje n-1 liniowo niezależnych wektorów αi1,αi2,…,αin-1 w zbiorze α1,α2,…,αt , takich że ∀1≤j<n⁢⁢αij∙γ=0.

3) ⁢γ∙γ=1

Warunki 2) i 3) wymuszają skończoną liczbę wektorów γ.

Niech W=⋂⁢γ⁢Hγ, gdzie Hγ=x∈Rn⁢|⁢x∙γ≤0. Pokażemy teraz, że S=W.

Z warunku 1) wynika inkluzja S⊂W.

Niech b∉S. Badamy zadanie

M⁢a⁢x⁢⁢x0=b∙x

∀1≤i≤t⁢⁢αi∙x≤0.

Ponieważ wektory αi rozpinają przestrzeń Rn więc obszar dopuszczalny jest wielościanem o jedynym wierzchołku p=θ. Warunek b∉S oznacza, na mocy twierdzenia o dualności, twierdzenie 8.4, że p nie jest punktem optymalnym tego zadania. Zatem istnieje krawędź poprawiająca. Niech γ będzie unormowanym wektorem kierunkowym tej krawędzi. Wówczas:

1) γ∈W implikuje ∀1≤i≤t⁢αi∙γ≤0.

2) γ jest wektorem krawędzi więc istnieje n-1 liniowo niezależnych półprzestrzeni opisujących - wektorów αi1,αi2,…,αin-1 w zbiorze α1,α2,…,αt, takich że ∀1≤j<n⁢⁢αij∙γ=0.

3) γ∙γ=1.

Dodatkowo γ∙b≥0 więc b∉Hγ a zatem również b∉W.

Wykazaliśmy, że S=W jest wielościanem.

∎

Algorytm szukania hiperprzestrzeni.

Krok 1. Jeżeli β∉l⁢i⁢n⁢α1,α2,…,αt to jako V można wziąć dowolną hiperprzestrzeń zawierającą l⁢i⁢n⁢α1,α2,…,αt i nie zawierającą β.

Krok 2. Przyjmijmy, że Rn=l⁢i⁢n⁢α1,α2,…,αt. Wybieramy dowolny liniowo niezależny podzbiór D=αi1,αi2,…,αin z wektorów α1,α2,…,αt.

Następnie wykonujemy następującą iterację:

i) Zapisujemy β=∑j=1n⁢aij⁢αij. Jeżeli ai1,ai2,…,ain≥0 to stop jesteśmy w przypadku I).

ii) W przeciwnym przypadku wybieramy najmniejszy indeks h spośród i1,i2,…,in taki,

że ah<0. Następnie budujemy hiperprzestrzeń H=x⁢|⁢γ∙x=0=l⁢i⁢n⁢D∖αh,

gdzie γ tak normalizujemy by γ∙αh=1. (Wtedy γ∙β=ah<0).

iii) Jeżeli γ∙α1≥0,γ∙α2≥0,…,γ∙αt≥0 jesteśmy w przypadku II).

iv) W przeciwnym przypadku wybieramy najmniejszy indeks s taki, że γ∙αs<0.

Teraz zamieniamy zbiór D na D∖αh∪αs i powtarzamy iterację.

Dowód poprawności i skończoności algorytmu.

Przyjmijmy oznaczenia:

Di zbiór wektorów używanych w i-tej iteracji.

Jeżeli proces nie kończy się to, wobec skończoności zbioru wektorów α, dla pewnych k<l otrzymamy Dk=Dl.

Niech r będzie największym indeksem, takim, że wektor αr jest dodawany przy pewnej iteracji Dq a wyrzucany przy iteracji Dp. (k≤q≤l, k≤p≤l). Niech Dp=αi1,αi2,…,αin i β=∑j=1n⁢aij⁢αij.

Zaczynamy q-tą iterację:

ii) Ponieważ nie jesteśmy w przypadku I) wybieramy najmniejszy indeks h spośród i1,i2,…,in taki, że ah<0. Następnie budujemy hiperprzestrzeń H=x⁢|⁢γ∙x=0=l⁢i⁢n⁢D∖αh, gdzie γ tak normalizujemy by γ∙αh=1. Ponieważ αh jest kiedyś dodawany więc h<r. Otrzymujemy γ∙β=ah<0.

iv) Teraz r jest najmniejszym indeksem takim, że γ∙αr<0. Czyli i<r⇒γ∙αi≥0

Reasumując 0>γ∙β=γ∙∑j=1n⁢aij⁢αij=∑j=1n⁢aij⁢γ∙αij≥0 gdyż:

ij<r⇒γ∙αij≥0 oraz aij≥0,

ar<0 i γ∙ar<0,

ij>r⇒γ∙αij=0 bo αij∈Dp∩Dq z wyboru r.

Otrzymaliśmy sprzeczność.

∎

Bez zmniejszenia ogólności możemy przyjąć, że d⁢i⁢m⁢⁢S=n. Niech pi¯=1,pi∈Rn+1 oraz αj¯=0,αj∈Rn+1. Tworzymy stożek S¯={θ+∑i=1tripi¯+∑j=1ksjαj¯;ri≥0,sj≥0}. Niech H={(x0,x1,…,xn)∈Rn+1;x0=1}. Wtedy S≈S¯∩H. Ponadto d⁢i⁢m⁢⁢S¯=d⁢i⁢m⁢⁢S+1=n+1. Na mocy poprzedniego lematu stożek S¯ jest wielościanem więc S też jest wielościanem.

∎

1) S⊂W

Niech p=∑i=1tri⁢pi wtedy p∈W, bo W jest wypukły.

Ponieważ każda krawędź zawiera wierzchołek więc ∀j∃i⁢∀t⁢pi+t⁢αj∈W.

Zatem ∀t⁢∀pi⁢pi+tβ∈W

Na mocy poprzedniego lematu

β=∑j=1ksj⁢αj jest wektorem takim, że ∀t⁢p+t⁢β∈W Co daje tezę.

2) W⊂S:

Przypuśćmy, że W≠S i będziemy dochodzić sprzeczności.

Niech q∈W∖S.

S jako wielościan jest zbiorem wypukłym i domkniętym.

Istnieje taka półprzestrzeń  H, że q∈H i S∩H≠∅.

W∩H jest wielościanem zawartym w W, zatem istnieje wierzchołek p wielościanu H∩W. p nie jest wierzchołkiem W, bo S zawierał wszystkie wierzchołki (a nawet krawędzie). p leży na brzegach n liniowo niezależnych półprzestrzeni opisujących W∩H, więc leży na brzegach n-1 półprzestrzeni opisujących W. Stąd p leży na krawędzi W

- sprzeczność.

∎

Niech p będzie punktem wielościanu W. Definiujemy zbiór wektorów

V=α∈Rn⁢|⁢∀r∈R⁢p+r⁢α∈W

.

Zauważmy, że V jest przestrzenią liniową. Wprost z definicji wynika własność α∈V⇒r⁢α∈V. Dodatkowo z własności wielościanów mamy

α∈V⇒∀q∈W⁢q+α∈W

A więc dla α,β∈V zachodzi p+α+β=p+α+β∈W.

Podsumowując

∀α∈V∀q∈W⁢q+α∈W.

Niech S=W∩p+V⊥ będzie wielościanem powstałym z przecięcia W z podprzestrzenią prostopadłą do V. Zbiór S jest niepusty bo zawiera punkt p ale nie zawiera prostej. Zatem S ma wierzchołek i na mocy poprzedniego twierdzenia istnieją takie punkty p1,p2,…,pt oraz wektory α1,α2,…,αk,

że S=∑i=1tri⁢pi+∑j=1ksj⁢αj⁢|⁢∑i=1tri=1∧ri≥0∧sj≥0.

A stąd W=∑i=1tri⁢pi+∑j=1ksj⁢αj⁢+∑z=1maz⁢βz⁢+∑z=1mbz⁢-βz⁢,

gdzie ∑i=1tri=1∧ri≥0∧sj≥0,∧az≥0,∧bz≥0, oraz wektory β1,β2,…,βm tworzą bazę przestrzeni V.

∎

  3)⇒1) - wynika z poprzedniego twierdzenia

1)⇒2) - oczywiste

2)⇒3) - oczywiste.

∎