1629289596

2.2. Wielościany 15

Dowód. Przyjmijmy V\ ~ Mⁿ i F₂ ~ R^ł

=>

Wprowadźmy układ bazowy (p;ai,a2, ...,a_n) przestrzeni V\ i rozszerzamy go do układu bazowego (p; a\,oi2, ..., a„, a_n+i,...,oct) przestrzeni V<i. Teraz jeżeli W — H?=i Hi, gdzie Hi c V\ są opisane nierównościami

Hi = {x | (oi,i,Oi_t2, • ••, 0-i,_n) • x < 6,} to w przestrzeni Vi zbiór W jest opisany układem nierówności:    ai,2> •••! Oj,m 0) •••) 0) • x < bi dla 1 < i < A; oraz Xj < 0 i — Xj < 0 dla n + 1 < j < i.

4= Niech W = fli=i Hi, gdzie Hi są półprzestrzeniami V2- Teraz W = fli=i (Hi fi Fi) a oczywistym jest, że Hi fi Fi może być półprzestrzenią w Fi lub całą przestrzenią Fi-

□

Definicja 2.9. Ścianą zbioru wypukłego W nazywamy zbiór W fi F gdzie F jest hiperpłasz-czyzną podpierającą.

Wymiarem ściany nazywamy liczbę j = dim af(W fi F).

Wierzchołkiem nazywamy taki punkt p G W, że istnieje półprzestrzeń H taka, żeWcH i {p} = dH fi W.

Uwaga 2.2. Zwykle wierzchołkiem nazywać będziemy nie tylko zbiór {p} ale także punkt p.

Krawędzią K nazywamy ścianę wymiaru 1. Dokładniej K = dH D W jest krawędzią gdy jest podzbiorem prostej mającym więcej niż 1 element. ( H jest półprzestrzenią i W C H ).

Twierdzenie 2.5. Rozpatrujemy zadanie optymalizacji liniowej:

Max xq = c • x, gdzie x € W i W jest opisane układem nierówności:

!ai • x < b\

a₂ • x < ł>2

cit*x ś:bt

Niechp G W będzie takim punktem, że cą*p = bi, dla i = 1,2, ...,j oraz Oj»p < bi, dla i > j. Wówczas:

1) Jeżeli dla pewnych liczb rzeczywistych r\ > 0,r2 > 0, ...,rj > 0 c = ]£j_i ^ri^ai t° P 3^est punktem optymalnym tego zadania.

2) Jeżeli p jest punktem optymalnym tego zadania to dH = {x € Rⁿ | c • x = c • p } jest hiperplaszczyzną podpierającą W w punkcie p.

Dowód.

ad 1) Niech q € W. Wtedy Xq(q) = c*q = £)i=i riOti»q < Yl\= i ^ri^i = I3i=i ^ri^ai*P = ^xo(p)-Więc punkt p jest optymalny.

ad 2) Niech q € W. Wtedy xo(q) < ^xo(p), co daje c • q < c • p. Zatem q € H = {x (ż Rⁿ | c • x < c • p } i p € dH = {xGi?“|c«x=c*p}.    □

Uwaga 2.3. Jednym z podstawowych twierdzeń teorii dualności jest:

p jest punktem optymalnym tego zadania wtedy i tylko wtedy gdy dla pewnych liczb rzeczywistych ri > 0, r2 > 0,..., rj > 0 zachodzi c — ^ri^ai-