W3.1

Wykład 3, sem II, 2012/2013

Geometria układów nierówności

liniowych.

Metoda sympleks. Przypadki szczególne.

Dualność w optymalizacji liniowej.

Zbiory wypukłe

X - przestrzeń liniowa nad ciałem R.

Definicja 1.1 Zbiór A ⊂ X jest wypukły jeśli

∀x1, x2∈A ∀0≤λ≤1 λx1 + (1 − λ)x2 ∈ A.

Niech [x1, x2] odcinek o końcach x1, x2 ∈ X,

[x1, x2] = {y ∈ X : y = λx1 + (1 − λ)x2, 0 ≤ λ ≤ 1}

równoważnie: A wypukły jeśli ∀x1,x2∈A [x1, x2] ⊂ A Twierdzenie 1.1 Przeciecie dowolnej rodziny A

t, t ∈

T zbiorów wypukłych jest zbiorem wypukłym.

Definicja 1.2 A ⊂ X dowolny zbiór w X. Zbiór

co(A) :=

B-wypukły,A⊂B

nazywamy powłoka wypukła zbioru A . Równoważnie,

coA jest zbiorem wszystkich kombinacji wypukłych elementów zbioru A,

coA := {z =

λiai,

λi = 1, λi ≥ 0, ai ∈ A i = 1, ..., kz}.

i=1

punkty wewnetrzne odcinka [a, b]: punkt z ∈ [a, b]

jest jego punktem wewnetrznym jeśli z = λa + (1 −

λ)b, 0 < λ < 1

Definicja 1.3 K ⊂ X - dowolny podzbiór przestrzeni liniowej X. Niepusty podzbiór S ⊂ K nazywamy

podzbiorem ekstremalnym dla K jeśli żaden punkt S nie jest punktem wewnetrznym żadnego odcinka,

którego końce leża do K, chyba, że obydwa końce

sa w S.

Analitycznie: jeśli x, y ∈ K i 0 < t < 1 to (1 − t)x + ty ∈ S

⇒

x, y ∈ S.

Punktem ekstremalnym nazywamy jednoelemen-

towy zbiór ekstremalny S = {a}, a ∈ K. Anali-

tycznie, jeśli dla pewnych x, y ∈ K mamy

a = (1 − t)x + ty, 0 < t < 1 to x = y = a.

oznaczenie: E(A) - zbiór punktów ekstremalnych

Twierdzenie 1.2 ( Krein’a-Milman’a) X - przestrzeń lokalnie wypukła . Niech A ⊂ X niepusty zwarty

i wypukły podzbiór X.

Wtedy A jest domknieta

powłoka wypukła zbioru swoich punktów ekstremal-

nych, tzn

A = ¯

co(E(A)).

Dowód. oparty na twierdzeniu o rozdzielaniu

Twierdzenie 1.3 ( Krein’a-Milman’a 1) X - przestrzeń lokalnie wypukła .

Niech ∅ 6= A ⊂ X - zwarty

podzbiór X. Wtedy

A ⊂ ¯

co(A).

Twierdzenie 1.4 (Twierdzenie Milman’a) X - przestrzeń lokalnie wypukła . Niech A ⊂ X bedzie niepustym

zwartym podzbiorem X takim, że ¯

co(A) jest zwarty.

Wtedy każdy punkt ekstremalny E( ¯

co(A)) powłoki

wypukłej ¯

co(A) zbioru A należy do A, czyli

E( ¯

co(A)) ⊂ A.

Dowód. Przez zaprzeczenie, niech p ∈ X bedzie

punktem ekstremalnym domknietej powłoki wy-

pukłej ¯

co(A) ale nie należy do A,

p ∈ ¯

co(A) \ A.

Istnieje wówczas wypukłe i zbalansowane otocze-

nie zera V takie, że

(p + ¯

V ) ∩ A = ∅.

(1)

Ze zwartości A ⇒ istnieja x

1, ...xm ∈ A takie, że

[

A ⊂

(xi + ¯

V ).

i=1

Każdy ze zbiorów Ai := ¯

co(A ∩ (xi + ¯

V )) i = 1, ..., m

jest wypukły i zwarty (dlaczego?) oraz A ⊂ (A1 ∪

A2∪, ..., Am). Oraz

(A1 ∪ A2∪, ..., Am)

zwarty (i wypukły)

a wiec

co(A) ⊂ ¯

co(A1 ∪ A2∪, ..., Am) = co(A1 ∪ A2∪, ..., Am).

Ale Ai ⊂ ¯

co(A), i = 1, .., m a wiec

co(A) = co(A1 ∪ ... ∪ Am).

W szczególności,

p = t1y1 + ... + tN yN , yi ∈ Ai, ti ≥ 0,

ti = 1.

i=1

Stad mamy przedstawienie

t2y2 + ... + t

p = t

N yN

1y1 + (1 − t1)

t2 + ... + tN

Zauwaźmy, że

t2y2 + ... + t

N yN

∈ ¯

co(A)

t2 + ... + tN

czyli musi być p = y1 a wiec dla pewnego i mamy

p ∈ Ai ⊂ xi + ¯

V ⊂ K + ¯

co przeczy (1).

Przykłady

1. zbiór Z := {x ∈ Rn a1x1 + a2x2 + ... + anxn ≤ b}

jest domkniety i wypukły. Z dzieli przestrzeń

Rn na dwie półprzestrzenie.

2. zbiór N := {x ∈ Rn b1x1 + b2x2 + ... + bnxn = d } jest domkniety i wypukły - hiperpłaszczyzna w

3. zbiór K ⊂ Rn jest stożkiem jeśli λx ∈ K dla

każdego x ∈ K and λ ≥ 0. Nie kaźdy stożek

jest zbiorem wypukłym.

4. zbiór K = {x ∈ Rn aT x = a1x1 + ...anxn ≤ 0} jest stożkiem wypukłym.

2.1

Zbiór rozwiazań dopuszczalnych Ω w optymalizacji lin-

iowej

Ω zbiór rozwiazań układu równań i nierówności lin-

iowych:

a11x1 + a12x2 + ..... + a1nxn ≤ b1

......

am1x1 + am2x2 + ... + amnxn ≤ bm

b11x1 + b12x2 + ... + b1nxn = d1

......

bk1x1 + bk2x2 + ...bknxn = dk

x1 ≥ 0, x2 ≥ 0, .... xn ≥ 0.

macierzowo: A macierz m × n, B macierz k × n,

b ∈ Rm, d ∈ Rk x = (x1, x2, ..., xn) ∈ Rn,

x ≥ 0 ⇔ xi ≥ 0 i = 1, ..., n

Ω := {x ∈ Rn : Ax ≤ b Bx = d x ≥ 0} = Ω1 ∩ Ω2

Ω1 := {x ∈ Rn : Ax ≤ b x ≥ 0}

Ω2 := {x ∈ Rn : Bx = d x ≥ 0}

zbiór Ω1 jest postaci

Ω1 = Z1 ∩ Z2 ∩ ... ∩ Zm ∩ Rn+

gdzie

Rn := {x ∈

Rn : x1 ≥ 0, ..., xn ≥ 0}

oraz dla i = 1, ..., m mamy

Zi := {x ∈ Rn ai1x1 + ai2x2 + ... + ainxn ≤ bi}

zbiór Ω2 jest postaci

Ω2 = N1 ∩ N2 ∩ ... ∩ Nk ∩ Rn+

gdzie dla i = 1, ..., k mamy

Ni := {x ∈ Rn bi1x1 + bi2x2 + ... + binxn = di}

Z Tw. o wypukłości przeciecia, Twierdzenie 1.1

zbiory

Twierdzenie 2.1 Zbiory

Ω, Ω1, Ω2

sa wypukłe i domkniete.

Zbiory postaci Ω, Ω1, Ω2 nazywamy zbiorami wieloś-

ciennymi (przeciecia skończonej liczby półprzestrzeni).

Rozpatrzmy zadanie optymalizacji liniowej: niech c ∈ Rn,

cT x = c1x1 + c2x2 + ... + cnxn → max

(P ) przy ograniczeniach

x ∈ Ω

Wartość maksymalna

Vmax := max cT x

x∈Ω

Twierdzenie 2.2 W zadaniu optymalizacji liniowej (P ) zbiór rozwiazań optymalnych

S := {x∗ ∈ Ω : cT x∗ = Vmax}

jest wypukły i domkniety.

Dowód. Wynika z Tw. o przecieciu

S = Ω ∩ {x ∈ Rn cT x = Vmax} .

}

hiperplaszczyzna

Zbiór rozwiazań układu równości i nierówności

liniowych jednorodnych (prawe strony równe

zero bi = 0, i = 1, ..., m, di = 0, i = 1, ..., k) jest stożkiem wypukłym

2.2

zdegenerowane i niezdegenerowane punkty ekstremalne (wierzchołkowe) zbiorów wielościennych

Rozwiazania bazowe w metodzie symplex

Zagadnienie w postaci standardowej

cT = c1x1 + ... + cnxn → max

przy ograniczeniach

Ax = b

x ≥ 0

gdzie A macierz ograniczeń m × n, m < n, rz(A) =

m, b ∈ Rm -wektor prawych stron, c ∈ Rn - wektor funkcji celu.

W każdym kroku metody symplex mamy nastepujacatablice

(po ewentualnym przenumerowaniu zmiennych)

x = (xB, xN) xB - zmienne bazowe o numerach 1 do m, xN - zmienne niebazowe o numerach m+1

do n

IxB + ¯

AxN = ¯b

(2)

gdzie ¯

A i ¯b sa to A i b przetransformowane za

pomoca eliminacji Gaussa

Definicja 3.1 Rozwiazanie bazowe otrzymujemy kładac

xN = 0 w (2).

Twierdzenie 3.1 (bazowe rozwiazanie dopuszczalne jest punktem ekstremaln

Bazowe rozwiazanie dopuszczalne problemu (P )

cT = c1x1 + ... + cnxn → max

przy ograniczeniach

Ax = b

x ≥ 0

jest punktem ekstremalnym (wierzchołkowym) wy-

pukłego zbioru rozwiazań dopuszczalnych

Ω = {x ∈ Rn : Ax = b, x ≥ 0}.

Dowód.

Zakładamy, że rzad macierz A jest m.

Poprzez ewentualne przenumerowanie indeksów niech x0 = (¯b1, ¯b2, ..., ¯bm, 0, ..., 0)

bedzie dopuszczalnym rozwiazaniem bazowym wz-

gledem zmiennych bazowych x

1, x2, ..., xm.

Załóżmy, przez zaprzeczenie, że x0 nie jest punktem ekstremalnym Ω. Z definicji, istnieja dwa inne

punkty dopuszczalne

p = (p1, ..., pn) ≥ 0,

q = (q1, ..., qn) ≥ 0

takie, że x0 = 1(p + q). W szczególności dla zmien-2

nych niebazowych j = m + 1, ..., n musi być xj = 0

czyli

pj = qj = 0

Ale wartości zmiennych bazowych wyznaczone sa֒

w sposób jednoznaczny przez wartości zmiennych

bazowych czyli musi być

p = q = x0.

Twierdzenie 3.2 (punkt ekstremalny jest rozwiazaniem bazowym dopuszczaln

Każdemu punktowi wierzchołkowemu odpowiada cona-jmniej jedno rozwiazanie bazowe dopuszczalne. Jeśli

dla danego punktu wierzchołkowego takie rozwiazanie

bazowe dopuszczalne jest niezdegenerowane to jest ono dokładnie jedno.