FMI, Info, Master ISemestrul I 2014/2015Tehnici de optimizarecombinatorialaLaurentiu Leustean

05.12.2014

Tema 2

(H2.1) Scrieti toate fetele poliedrului P = {x 2 R2 | 2 x 3}.Proof. P este solutia urmatorului sistem de 4 inegalitati: x1 2, x1 3,x2 2, x2 3,i.e. 0BB@

1 01 00 10 1

1CCAx1x2

0BB@2323

1CCAConform Teoremei 1.7.5, avem ca orice fata nevida a lui P este de forma

F = {x 2 P | AIx = bI}, unde I {1, . . . , 4}.Obtinem

I = ; ) FI = PI = {1} ) FI = {x 2 P | x1 = 2} = {(2, x2)T | 2 x2 3}I = {2} ) FI = {x 2 P | x1 = 3} = {(3, x2)T | 2 x2 3}I = {3} ) FI = {x 2 P | x2 = 2} = {(x1,2)T | 2 x1 3}I = {4} ) FI = {x 2 P | x2 = 3} = {(x1, 3)T | 2 x1 3}

I = {1, 3} ) FI = {x 2 P | x1 = 2,x2 = 2} = {(2,2)T}I = {1, 4} ) FI = {x 2 P | x1 = 2, x2 = 3} = {(2, 3)T}I = {2, 3} ) FI = {x 2 P | x1 = 3,x2 = 2} = {(3,2)T}I = {2, 4} ) FI = {x 2 P | x1 = 3, x2 = 3} = {(3, 3)T}I = {1, 2} ) FI = {x 2 P | x1 = 2, x1 = 3} = ;I = {3, 4} ) FI = {x 2 P | x2 = 2, x2 = 3} = ;

Pentru I cu cel putin 3 elemente, avem {1, 2} I sau {3, 4} I, deci FI = ;.

(H2.2) Demonstrati ca orice poliedru marginit este punctat.

Proof. Fie P un poliedru marginit. Presupunem prin reducere la absurd ca P nu estepunctat. Rezulta ca exista y 2 P, y 6= 0. Aplicam acum Remarca 1.6.2 pentru a conclude caP contine o dreapta Lx,y P .Claim: Lx,y este nemarginita.Proof of Claim: Avem ca Lx,y = {x+ y | 2 R},

kx+ yk kyk kxk = ||kyk kxk si lim!1

||kyk kxk =1.

Deci lim!1 kx+ yk =1, adica Lx,y este nemarginita. Rezulta ca P nu este marginit, fapt care contrazice ipoteza.

(H2.3) Fie c 2 Rn, 2 R, S Rn si conv(S) nchiderea convexa a lui S. Demonstrati ca oinegalitate cTx este valida pentru conv(S) daca si numai daca este valida pentru S.Proof. ) este evidenta, deoarece S conv(S). ( Fie s 2 conv(S). Atunci s =Pmi=1 isi, unde s1, . . . , sm 2 S, 1, . . . ,m 2 R, i 0pentru orice i = 1, . . . ,m si

mXi=1

i = 1. Deoarece si 2 S, rezulta din ipoteza ca cT si pentru orice i = 1, . . . ,m.Rezulta

cT s =mXi=1

i(cT si)

mXi=1

i = mXi=1

i = .

(H2.4) Demonstrati ca intersectia a doua fete ale unui poliedru este de asemenea o fata apoliedrului.

Proof. Fie F1, F2 fete ale poliedrului P = {x 2 Rn | Ax b}. Daca intersectia lor este vida,atunci este desigur fata a poliedrului. Presupunem ca F1 \ F2 = ;. Rezulta ca F1, F2 suntnevide si, deci, putem aplica Teorema 1.7.5 pentru a obtine I, J {1, . . . ,m} astfel ncatF1 = {x 2 P | AIx = bI} si F2 = {x 2 P | AJx = bJ}. Atunci K := I [ J {1, . . . ,m} siF1 \ F2 = {x 2 P | AKx = bK}. Asadar, F1 \ F2 este fata a poliedrului.

(H2.5) Demonstrati ca P = lin.space(P ) daca si numai daca P este subspatiu liniar.

Proof. ) este evidenta, deoarece lin.space(P ) este subspatiu liniar.( Presupunem ca P este subspatiu liniar. Evident, 0 2 lin.space(P ). Fie y 2 P, y 6= 0. Atunci pentru orice x 2 P si orice 2 R, obtinem ca y 2 P , deci x+ y 2 P , adica Lx,y P . Aplicam Remarca 1.6.2 pentrua conclude ca y 2 lin.space(P ). Evident, 0 2 P . Fie y 2 lin.space(P ), y 6= 0. Atunci, aplicand din nou Remarca 1.6.2,rezulta existenta unui x 2 P astfel ncat Lx,y P , deci, n particular, x + y 2 P . Rezultaca y = (x+ y) x 2 P .