7/25/2019 Examen Cp 2015

1/3

Examen Cercetari operat ionale

11.05.2015

Exercitiu 1 Se considera problema

(P)

min 2x1 2x2+x3+x4,cu restrictiile x1+ 3x2+x4= 4,

x1+x2+x3+x4= 2,x1, x2, x3, x4 0.

(i). Rezolvati problema folosind algoritmul simplex, pornind de la vari-abilele de bazax1, x2(verificati ntai ca variabilelex1, x2pot fi variabile

de baza).(ii). Detrminati dulalul (D) al programului (P).

(iii). Determinati solutia problemei duale.

Exercitiu 2 Se considera problema

(QP)

min x21

4x1x2+ 2x2

2 2x2x3 2x2+ 3x3,

cu restrictiile x21+x2

2+x2

3 2,

x1, x2, x3, x4 0.

(i). Aratati ca x= (0, 0, 0) nu este minim local.

(ii). Aratati ca x= (1, 1, 0) satisface conditiile KKT.

(iii). Consideram problema

(QP)

min x21

4x1x2+ 6x2

2 8x2.

Porniti cux = (0, 0) pentru a face o iteratie Newton. Aratati ca punctulastfel obtinut este optim.

Exercitiu 3 Consideram o problema de transport cu 3 fabrici si 3 depozite.

In depozite se afla 4,4, respectiv 12 unitati dintr-o anumita marfa iar cerereafabricilor este de 7,8, respectiv 5 unitati.Presupunem ca exista drumuri de la

1

7/25/2019 Examen Cp 2015

2/3

toate fabricile catre toate depozitele, iar costul de transport de la fabrici la

depozite este contnut n tabelul.

ci,j j = 1 j = 2 j = 3i= 1 2 3 2i= 2 1 2 2i= 3 2 1 2

Determinati o solutie de baza folosind metoda coltului N-V. Rezolvati prob-lema.

Exercitiu 4 (i). Se considera problema

(QP)

minimizeaza f(x),cu restrictia Ax= b,

unde f(x) = 12

xTHx+cTx, iar A, b, H, c, sunt date de

A= [1 1 1], b= [1], H=

1 2 12 6 6

1 6 10

, c=

10

1

.

Este f functie convexa pe R3?

(ii). Enuntati teorema fundamentala a programarii liniare.

2

7/25/2019 Examen Cp 2015

3/3

Exercitiu 1 Un proiectil este lansat din originea axelor de coordonate. Proiec-

tilul nu are sistem de propulsie si nici sistem de ghidare, prin urmare se poatepresupune ca traiectoria lui descrie parabola de ecuatie y = x2 + x. Ladistanta xk, k {1, , m} se masoara naltimea yk a traiectoriei. Acestemasuratori sunt folosite pentru a estima coeficientii , , prin minimizareadiferentei patratice dintre masuratori si valoarea functiei n punctul respec-tiv. Formulati si rezolvati problema ca o problema de tipul celor mai micipatrate, presupunand ca la distantele 1,2, 3, naltimile masurate sunt 1,4,2.

3