1. Fie problema de programare liniara: 1 2 3

1 2 3

1 2 3

1 2 3

[max] 5 10 202 3 5

2 42 2 6

0, 1,3i

f x x xx x x

x x xx x x

x i

= + +

+ + ≤⎧⎪ + + ≤⎨⎪ + + ≤⎩≥ =

Sa se aduca la forma standard pentru simplex. 2. Fie problema de programare liniara

1 2 3

1 2 3

1 2 3

1 2 3

[max] 5 10 202 3 5

2 42 2 6

0, 1,3i

f x x xx x x

x x xx x x

x i

= + +

+ + ≤⎧⎪ + + ≤⎨⎪ + + ≤⎩≥ =

Prima iteratie a algoritmului simplex este 5 10 20 0 0 0

B 0 5 1 2 3 1 0 0 0 4 2 1 1 0 1 0 0 6 1 2 2 0 0 1 0 0 0 0 0 0 5 10 20 0 0 0

Sa se indice linia pivotului. 3. Fie problema de programare liniara

1 2 3

1 2 3

1 2 3

1 2 3

[max] 5 10 202 3 5

2 42 2 6

0, 1,3i

f x x xx x x

x x xx x x

x i

= + +

+ + ≤⎧⎪ + + ≤⎨⎪ + + ≤⎩≥ =

Prima iteratie a algoritmului simplex este 5 10 20 0 0 0

B 0 5 1 2 3 1 0 0 0 4 2 1 1 0 1 0 0 6 1 2 2 0 0 1 0 0 0 0 0 0 5 10 20 0 0 0

Stabiliti care este vectorul care iese, respectiv vectorul care intra in baza 4. Fie problema de programare liniara

1 2 3

1 2 3

1 2 3

1 2 3

[max] 5 10 202 3 5

2 42 2 6

0, 1,3i

f x x xx x x

x x xx x x

x i

= + +

+ + ≤⎧⎪ + + ≤⎨⎪ + + ≤⎩≥ =

[max]f = 5x 1 + 10x 2 + 20x 3 + 0x 4 + 0x 5 + 0x 6

x 1 + 2x 2 + 3x 3 + x4 = 5

2x1 + x 2 + x 3 + x 5 = 4

x 1 + 2x 2 + 2x 3 + x6 = 6

Ï

Ì

Ó

ÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔ

x i ≥ 0,i = 1,6

1 2 3[max] 5 10 20f x x x= + +

a 4

intra a 3 , iese a 4

max f =100

3, x o = 0,0,

5

3Ë

ÁÁÁÁÁÁÁ¯

˜̃˜̃˜̃˜, y o = 0,

7

3,8

3Ë

ÁÁÁÁÁÁÁ¯

˜̃˜̃˜̃˜

Care este solutia optima pentru problema de programare liniara? 5. Fie problema de programare liniara

Se se determine forma standard pentru simplex a problemei de programare liniara. 6. Fie problema de programare liniara

Prima iteratie a algoritmului simplex este: 7 8 0 0

0 5 2 1 1 0 0 4 1 2 0 1 0 0 0 0 0 7 8 0 0

Specificati coloana pivotului. 7. Fie problema de programare liniara

Prima iteratie a algoritmului simplex este: 7 8 0 0

0 5 2 1 1 0 0 4 1 2 0 1 0 0 0 0 0 7 8 0 0

Stabiliti care este vectorul care intra, respectiv vectorul care iese din baza 8. Fie problema de programare liniara

[max]f = 7x1 + 8x 2 + 0y 1 + 0y 2

2x 1 + x 2 + y 1 = 5

x 1 + 2x 2 + y 2 = 4

Ï

Ì

Ó

ÔÔÔÔÔÔÔÔÔÔÔÔÔÔ

x 1 ,x 2 ≥ 0,y 1 ,y2 ≥ 0

a 2

intra a 2 , iese a 4

3, 0, 0, -4

Aplicandu-se algoritmul simplex se ajunge la un moment dat la: 7 8 0 0

0 3

0 1

8 2

1 0

16 4 8 0 4

Completati linia lui . 9. Fie problema de programare liniara

Aplicandu-se algoritmul simplex se ajunge la un moment dat la: 7 8 0 0

0 3

0 1

8 2

1 0

16 4 8 0 4 3 0 0 -4

Specificati coloana pivotului 10. Fie problema de programare liniara

Indicati optimul problemei. 11. Fie problema de programare liniara

Dati matricea asociata formei standard. 12. Fie problema de programare liniara

a 1

solutia optima este f max = 22, x o = 2,1ÊËÁÁ ˆ

¯˜̃ ,y o = 0,0Ê

ËÁÁ ˆ

¯˜̃

A = −1

1

1

−2

−1

0

0

1

Ê

Ë

ÁÁÁÁÁÁÁÁÁÁÁ

ˆ

¯

˜̃˜̃˜̃˜̃˜̃̃

Specificati duala acestei probleme de programare liniara. 13. Fie problema de programare liniara

Care este duala acestei probleme de programare liniara. 14. Fie problema de programare liniara

Precizati prima linie a matricii asociata formei standard. 15. Fie problema de programare liniara

Dupa ce se aduce la forma standard se obtine primul tabel simplex: 7 -8 3 2 2 0

4 3 0 1 1 0 1 1 2 0 -1 1 1 0 2 1 1 2 2 0 0

Care este baza initiala pentru algoritmul simplex ? 16. Fie problema de programare liniara

[max]g = y 1 + y 2

−y 1 + y 2 ≤ 6

5y 1 − 2y 2 ≤ 7

Ï

Ì

Ó

ÔÔÔÔÔÔÔÔÔÔÔÔÔÔ

y 1 ,y2 ≥ 0

[max]g = 2y 1 + y2

y1 + 2y2 ≤ 4

2y 1 + y 2 ≤ 5

y 1 + y 2 ≤ 6

Ï

Ì

Ó

ÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔ

y 1 ,y2 ≥ 0

3 0 2 5 0 -1

B = {a 6 ,a 5 ,a 2}

Dupa ce se aduce la forma standard se obtine primul tabel simplex: 2 2 3 2 5 0

0 4 3 0 1 1 0 1 2 1 2 1 -1 1 0 0 5 2 1 0 2 2 1 0

Construiti linia lui . 17. Fie problema de programare liniara

Dupa ce se aduce la forma standard se obtine tabelul simplex: 2 -1 3 2 3 0

0 4 3 0 1 1 0 1 -1 1 2 1 -1 1 0 0 3 2 1 0 2 2 1 0 5 1 -1 7 5 3 0 1 0 -4 -3 0 0

Care este coloana pivotului. 18. Fie problema de programare liniara

Dupa ce se aduce la forma standard se obtine tabelul simplex: 2 -1 3 2 3 0

0 4 3 0 1 1 0 1 -1 1 2 1 -1 1 0 0 3 2 1 0 2 2 1 0

12, 9, 2, 8, 12, 5, 0

a 1

solutia obtinuta nu este optima, a 1 intra in baza, a 2 iese din baza

5 1 -1 7 5 3 0 1 0 -4 -3 0 0

Ce decizie se ia? 19. Fie problema de programare liniara

Ce optim se obtine? 20. Se considera problema de transport:

Disponibil 2 1 3 20 1 4 2 45 3 5 4 65

Necesar 30 40 60 Dati o solutie initiala de baza obtinuta prin metoda coltului N-V .

21. Se considera problema de transport: Disponibil

2 1 3 20 1 4 2 45 3 5 4 65

Necesar 30 40 60 Dati o solutie initiala de baza obtinuta prin metoda costului minim pe linie.

22. Fie problema de programare liniara

Specificati duala acestei probleme de programare liniara. 23. Fie problema de programare liniara

Specificati matricea sistemului restictiilor. 24. Fie problema de programare liniara

f max =11

2, x 0 =

1

2,0,0,0,

3

2

Ê

Ë

ÁÁÁÁÁÁÁ

ˆ

¯

˜̃˜̃˜̃˜

x 11 = 20, x 21 = 10, x 22 = 35, x 32 = 5, x 33 = 60, in rest x ij = 0

x 12 = 20, x 21 = 30, x 23 = 15, x 32 = 20, x 33 = 45, in rest x = 0

[max]f = 7x 1 + 4x 2

5x 1 + 3x 2 ≤ 6

2x1 + x 2 ≤ 8

Ï

Ì

Ó

ÔÔÔÔÔÔÔÔÔÔÔÔÔÔ

x ≥ 0

A =

1

2

1

0

1

1

1

3

2

2

0

0

Ê

Ë

ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ

ˆ

¯

˜̃˜̃˜̃˜̃˜̃˜̃˜̃˜

Dati forma standard a problemei de programare liniara. 25. Fie problema de programare liniara

Prima iteratie a algoritmului simplex este B

0 40 1 0 1 2 1 0 0 0 16 2 1 3 0 0 1 0 0 48 1 1 2 0 0 0 1

Completati linia lui 26. Fie problema de programare liniara

Prima iteratie a algoritmului simplex este 3 5 1 6 0 0 0

B 0 40 1 0 1 2 1 0 0 0 16 2 1 3 0 0 1 0 0 48 1 1 2 0 0 0 1 f 0 0 0 0 0 0 0 0 3 5 1 6 0 0 0

Specificati pozitia pivotului. 27. Fie problema de programare liniara

[max]f = 3x 1 + 5x 2 + x 3 + 6x 4 + 0y 1 + 0y 2 + 0y 3

x 1 + x3 + 2x4 + y 1 = 40

2x 1 + x 2 + 3x 3 + y 2 = 16

x 1 + x2 + 2x3 + y 3 = 48

Ï

Ì

Ó

ÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔ

x i ≥ 0,i = 1,4,y i ≥ 0,i = 1,3

3, 5, 1, 6, 0, 0, 0

coloana lui a 4 , linia lui a 5

Prima iteratie a algoritmului simplex este 3 5 1 6 0 0 0

B 0 40 1 0 1 2 1 0 0 0 16 2 1 3 0 0 1 0 0 48 1 1 2 0 0 0 1 f 0 0 0 0 0 0 0 0 3 5 1 6 0 0 0

Calculati coloana lui din urmatorul tabel simplex. 28. Fie problema de programare liniara

A doua iteratie a algoritmului simplex este 3 5 1 6 0 0 0

B 6 20 0 1 0 0

0 16 2 1 3 0 0 1 0 0 48 1 1 2 0 0 0 1 f 120 3 0 3 6 3 0 0 0 5 -2 0 -3 0 0

Stabiliti care este vectorul care intra si respectiv care iese din baza. 29. Fie problema de programare liniara

Prin aplicarea algoritmului simplex se ajunge la urmatorul tabel simplex 3 5 1 6 0 0 0

B

1

2

2

1

intra a 2 , iese a 6

solutia obtinuta este cea optima si f max = 200, x o = 0,16,0,20ËÁÁ

¯˜̃ , y o = 0,0,32

ËÁÁ

¯˜̃

6 20 0 1 0 0

5 16 2 1 3 0 0 1 0 0 32 -1 0 -1 0 0 -1 1 f 200 13 5 18 6 3 5 0 -10 0 -17 0 -3 -5 0

Ce decizie se ia? 30. Fie problema de programare liniara:

max f = .

Care va fi forma standard a problemei de programare liniara.

31. Fie problema de programare liniara: max f =

Prima iteratie a algoritmului simplex este:

10 16 0 0 0 B

0 1200 2 5 1 0 0 0 300 1 3/2 0 1 0 0 600 4 1 0 0 1 0 0 0 0 0 10 16 0 0 0

Indicati coloana pivotului. 32. Fie problema de programare liniara:

max f =

Prima iteratie a algoritmului simplex este:

10 16 0 0 0 B

0 1200 2 5 1 0 0 0 300 1 3/2 0 1 0 0 600 4 1 0 0 1 0 0 0 0 0

max f = 10x 1 + 16x 2 + 0u 1 + 0u 2 + 0u 3

2x 1 + 5x 2 + u 1 = 1200

x1 + 1,5x 2 + u 2 = 300

4x1 + x 2 + u 3 = 600

Ï

Ì

Ó

ÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔÔ

x 1 ,x 2 ≥ 0, u 1 ,u 2 ,u 3 ≥ 0

a 2

intra a 2 , iese a 4

10 16 0 0 0 Stabiliti care este vectorul care intra in baza, respectiv care iese din baza.

33. Fie problema de programare liniara: max f =

Prima iteratie a algoritmului simplex este:

10 16 0 0 0 B

0 1200 2 5 1 0 0 0 300 1 3/2 0 1 0 0 600 4 1 0 0 1 0 0 0 0 0 10 16 0 0 0

Care este solutia optima pentru problema de programare liniara? 34. Fie problema de programare liniara:

, i=1,2,3 Dati baza initiala pentru algoritmul simplex.

35. Fie problema de programare liniara:

, i= 2 1 1 3 2

B 2 8 1 0 0 1 2 1 12 0 1 0 2 1 1 16 0 0 1 1 3

Calculati linia corespunzatoare lui . 36. Fie problema de programare liniara:

max f = 3200 x 0 = 0,200ÊËÁÁ ˆ

¯˜̃ ,

y=(200,0,400)

B = a 1 ,a 2 ,a 3ÌÓ

ÔÔÔÔ ˝

˛

ÔÔÔÔ

0 0 0 −2 −6

min f = 20 si x 0 = 0 8 4 0 4ÊËÁÁ

ˆ¯˜̃

, i=1,2,3 Precizati care este solutia optima.

43. Fie urmatoarea problema de transport Disponibil

70 10 20

Necesar 50 25 15 10 Folosind metoda coltului de NV stabiliti valoarea lui si a lui

44. Fie urmatoarea problema de transport Disponibil

5 6 2 3 70 2 2 1 4 10 6 8 3 4 20

Necesar 50 25 15 10 Folosind metoda costurilor minime(din tablou) stabiliti valoarea lui si a lui

45. Sa se scrie forma standard pentru problema de programare liniara:

max f = 4x1 + 10x 2 +9x 3 x1 + x 2 + 2x 3 ≤ 18 2 x1 + x 2 + 4x 3 ≤ 20 x1 + x 2 + x 3 ≤ 12 x i ≥ 0 ; i = 3,1

46. Fie urmatoarea problema de transport Disponibil

5 6 2 3 70 3 2 1 4 10 6 8 3 4 20

Necesar 50 25 15 10 Folosind metoda costurilor minime pe linie stabiliti valoarea lui si a lui

47. Fie urmatoarea problema de transport Disponibil

5 6 2 3 70 3 2 1 4 70 6 8 3 4 70

Necesar 50 75 25 60 Folosind metoda diagonalei (coltului N-V) determinati

x11=50, x33=10

x14=10,x32=20

max f = 4x 1 + 10x 2 +9x 3 +0y1+0y 2 +0y 3

x 1 + x 2 + 2x 3 + y1 = 18

2x 1 + x2+ 4x 3 + y 2 = 20

x 1 + x 2 + x 3 + y 3 = 12

x i ≥ 0 ; i = 3,1

y1 , y 2 , y 3 ≥0

x14=10, x32=15

60

48. Fie urmatoarea problema de transport Disponibil

5 6 2 3 70 3 2 1 4 70 6 8 3 4 70

Necesar 50 75 25 60 Folosind metoda diagonalei (coltului N-V) determinati

49. Fie urmatoarea problema de transport Disponibil

5 6 2 3 70 3 2 1 4 70 6 8 3 4 70

Necesar 50 75 25 60 Folosind metoda diagonalei (coltului N-V) determinati

50. Fie urmatoarea problema de transport Disponibil

5 6 2 3 70 3 2 1 4 70 6 8 3 4 70

Necesar 50 75 25 60 Folosind metoda diagonalei (coltului N-V) determinati

51. Să se rezolve problema de programare liniară [ ] 1 2max 50 25f x x= +

1 2

1 2

1 2

32 5

, 0

x xx xx x

+ ≤⎧⎪ + ≤⎨⎪ ≥⎩

52. Să se scrie şi să se rezolve duala problemei de programare liniară

[ ] 1 2min 6 10f x x= +

1 2

1 2

2 12 3x xx x+ ≥⎧

⎨ + ≥⎩

53. Fie problema de programare liniara: max f =

Prima iteratie a algoritmului simplex este:

10 16 0 0 0 B

0 1200 2 5 1 0 0

10

50

55

alt răspuns

[ ] 1 2max 3g y y= +

1 2

1 2

2 6

2 10

y y

y y

+ ≤

+ ≤ 1 0y = 2 3y = max 9g =

F

0 300 1 3/2 0 1 0 0 600 4 1 0 0 1 0 0 0 0 0 10 16 0 0 0

Solutia gasita este cea optima ?

54. Trei depozite aprovizioneaza cu produse de larg consum 4 magazine astfel: Disponibil

3 2 1 2 30 4 3 3 2 20 2 1 4 5 40

Necesar 10 15 15 40 Problema este echilibrata?

55. Forma standard a problemei de programare liniara

este

56. Se considera urmatoarea problema de transport: Disponibil

4 6 5 2 35 3 2 7 8 30 2 10 5 6 50

Necesar 20 25 45 25 Problema de transport este echilibrata ?

57. Se considera urmatoarea problema de transport: Disponibil

4 6 5 2 35 3 2 7 8 30 2 10 5 6 50

Necesar 20 25 45 25 O solutie initiala de baza determinata folosind metoda coltului de N-V este , ,

, , , , .

58. Se considera urmatoarea problema de transport: Disponibil

4 6 5 2 35

F

F

A

A

A

3 2 7 8 30 2 10 5 6 50

Necesar 20 25 45 25 O solutie initiala de baza determinata folosind metoda costului minim pe linie este , ,

, , , , .

59. Fie problema de programare liniară

( )

( )( )( )321

minmax0

cxzX

bAx

=≥=

cu ( )nmMA ,∈ , nmA <=rang , ( )tnxxx ,...,1= . Vectorul ( )tnxxx ,...,1= care satisface condiţiile (1) şi (2) se numeşte soluţie posibilă ?

60. Fie problema de programare liniară

( )

( )( )( )321

minmax0

cxzX

bAx

=≥=

cu ( )nmMA ,∈ , nmA <=rang , ( )tnxxx ,...,1= . O soluţie posibilă ( )tnxxx ,...,1= se numeşte soluţie de bază dacă coloanele

rii aa ,...,1

din matricea A corespunzătoare coordonatelor nenule

rii xx ,...,1

ale vectorului x sunt liniar dependente.

A