Tehnici De Optimizare Grile Raspunsuri

Tehnici de optimizare Programare liniara MULTIPLE CHOICE 1. Fie problema de programare liniara:

[max] f = 5 x1 + 10 x2 + 20 x3  x1 + 2 x2 + 3 x3 ≤ 5   2 x1 + x2 + x3 ≤ 4 x + 2x + 2x ≤ 6 2 3  1 xi ≥ 0, i = 1,3 Sa se aduca la forma standard pentru simplex. [max] f = 5 x1 + 10 x2 + 20 x3 a.

 x1 + 2 x2 + 3 x3 + x4 ≤ 5   2 x1 + x2 + x3 + x5 ≤ 4 x + 2x + 2x + x ≤ 6 2 3 6  1 xi ≥ 0, i = 1,6

b.

[max]f = 5x 1 + 10x 2 + 20x 3 + 0x 4 + 0x 5 + 0x 6 ÏÔÔ ÔÔ x 1 + 2x 2 + 3x 3 + x 4 = 5 ÔÔ ÔÔ ÔÌÔÔ 2x 1 + x 2 + x 3 + x 5 = 4 ÔÔ ÔÔÔ x 1 + 2x 2 + 2x 3 + x 6 = 6 Ó x i ≥ 0,i = 1,6

[max] f = 5 x1 + 10 x2 + 20 x3 c.

 x1 + 2 x2 + 3 x3 − x4 = 5   2 x1 + x2 + x3 − x5 = 4 x + 2x + 2x − x = 6 2 3 6  1 xi ≥ 0, i = 1,6 [max] f = 5 x1 + 10 x2 + 20 x3 + Mx4 + Mx5 + Mx6

d.

 x1 + 2 x2 + 3 x3 + x4 = 5   2 x1 + x2 + x3 + x5 = 4 x + 2x + 2x + x = 6 2 3 6  1 xi ≥ 0, i = 1,6

1

2. Fie problema de programare liniara

[max] f = 5 x1 + 10 x2 + 20 x3  x1 + 2 x2 + 3 x3 ≤ 5   2 x1 + x2 + x3 ≤ 4 x + 2x + 2x ≤ 6 2 3  1 xi ≥ 0, i = 1,3 Prima iteratie a algoritmului simplex este 5 CB X a B B 1 a4 0 5 1 a5 4 2 0 a6 0 6 1 fj 0

∆j =cj −f j

5

10 a2 2 1 2 0

20 a3 3 1 2 0

0 a4 1 0 0 0

0 a5 0 1 0 0

0 a6 0 0 1 0

10

20

0

0

0

10 a2 2 1 2 0

20 a3 3 1 2 0

0 a4 1 0 0 0

0 a5 0 1 0 0

0 a6 0 0 1 0

10

20

0

0

0

Pivotul se afla pe linia corespunzatoare lui a. a 4 b. a 5 c. a 6 3. Fie problema de programare liniara

[max] f = 5 x1 + 10 x2 + 20 x3  x1 + 2 x2 + 3 x3 ≤ 5   2 x1 + x2 + x3 ≤ 4 x + 2x + 2x ≤ 6 2 3  1 xi ≥ 0, i = 1,3 Prima iteratie a algoritmului simplex este 5 CB XB a1 B a4 0 5 1 a5 0 4 2 a6 0 6 1 fj 0

∆j =cj −f j

5

Stabiliti care este vectorul care iese, respectiv vectorul care intra in baza a. intra a 3 , iese a 4 b. intra a 3 , iese a 5 c. intra a 3 , iese a 6 d. intra a 1 , iese a 6 e. intra a 1 , iese a 5

2

4. Fie problema de programare liniara

[max] f = 5 x1 + 10 x2 + 20 x3  x1 + 2 x2 + 3 x3 ≤ 5   2 x1 + x2 + x3 ≤ 4 x + 2x + 2x ≤ 6 2 3  1 xi ≥ 0, i = 1,3 Care este solutia optima pentru problema de programare liniara? 10 o ÊÁÁÁ 5 ˆ˜˜˜ o ÊÁÁÁ 7 8 ˆ˜˜˜ Á a. maxf = , x = ÁÁ 0,0, ˜˜˜ , y = ÁÁÁ 0, , ˜˜˜ ÁË ÁË 3 3 ˜¯ 3 3 ˜¯ ÁÊÁ 7 8 ˜ˆ˜ 100 o ÁÊÁÁ 5 ˜ˆ˜ b. maxf = , x = ÁÁÁ 0,0, ˜˜˜˜ , y o = ÁÁÁÁ 0, , ˜˜˜˜ ÁË ÁË 3 3 ˜¯ 3 3 ˜¯ 100 o ÊÁÁÁ 7 8 ˆ˜˜˜ o ÊÁÁÁ 5 ˆ˜˜ c. maxf = ,x = ÁÁÁ 0, , ˜˜˜ , y = ÁÁÁ 0,0, ˜˜˜˜ ÁË 3 3 ˜¯ ÁË 3 3 ˜¯ d. alt raspuns 5. Fie problema de programare liniara [max]f = 7x 1 + 8x 2 ÏÔÔ ÔÔ ÔÔ 2x 1 + x 2 ≤ 5 ÔÌÔ ÔÔÔ x + 2x ≤ 4 2 Ó 1

x 1 ,x 2 ≥ 0 Forma standard pentru simplex a problemei de programare liniara este a. [max]f = 7x 1 + 8x 2 c. [max]f = 7x 1 + 8x 2 + My 1 + My 2 ÔÏÔÔ ÔÏÔÔ ÔÔ 2x + x + y = 5 ÔÔ 2x + x + y = 5 Ô 1 Ô 1 2 1 2 1 ÌÔÔ ÌÔÔ ÔÔÔ x 1 + 2x 2 − y 2 = 4 ÔÔÔ x 1 + 2x 2 + y 2 = 4 Ó Ó b.

x 1 ,x 2 ≥ 0,y 1 ,y 2 ≥ 0 [max]f = 7x 1 + 8x 2 + 0y 1 + 0y 2 ÏÔÔ ÔÔ ÔÔ 2x 1 + x 2 + y 1 = 5 ÔÌÔ ÔÔÔ x + 2x + y = 4 2 2 Ó 1

d.

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

x 1 ,x 2 ≥ 0,y 1 ,y 2 ≥ 0 [max]f = 7x 1 + 8x 2 − My 1 − My 2 ÏÔÔ ÔÔ ÔÔ 2x 1 + x 2 + y 1 = 5 ÔÌÔ ÔÔÔ x + 2x + y = 4 2 2 Ó 1 x 1 ,x 2 ≥ 0,y 1 ,y 2 ≥ 0

3

6. Fie problema de programare liniara [max]f = 7x 1 + 8x 2 ÏÔÔ ÔÔ ÔÔ 2x 1 + x 2 ≤ 5 ÔÌÔ ÔÔÔ x + 2x ≤ 4 2 Ó 1

x 1 ,x 2 ≥ 0 Prima iteratie a algoritmului simplex este: CB 0 0

B a3 a4 fj

XB 5 4 0

7 a1 2 1 0

8 a2 1 2 0

0 a3 1 0 0

0 a4 0 1 0

7

8

0

0

7 a1 2 1 0

8 a2 1 2 0

0 a3 1 0 0

0 a4 0 1 0

7

8

0

0

∆j Pivotul se afla pe coloana corespunzatoare lui a. a 1 b. a 2 c. a 3 d. a 4 7. Fie problema de programare liniara [max]f = 7x 1 + 8x 2 ÏÔÔ ÔÔ ÔÔ 2x 1 + x 2 ≤ 5 ÔÌÔ ÔÔÔ x + 2x ≤ 4 2 Ó 1

x 1 ,x 2 ≥ 0 Prima iteratie a algoritmului simplex este: CB 0 0

B a3 a4 fj

XB 5 4 0

∆j

Stabiliti care este vectorul care intra, respectiv vectorul care iese din baza a. intra a 1 , iese a 3 b. intra a 2 , iese a 3 c. intra a 1 , iese a 4 d. intra a 2 , iese a 4

4

8. Fie problema de programare liniara [max]f = 7x 1 + 8x 2 ÏÔÔ ÔÔ ÔÔ 2x 1 + x 2 ≤ 5 ÔÌÔ ÔÔÔ x + 2x ≤ 4 2 Ó 1

x 1 ,x 2 ≥ 0 Aplicandu-se algoritmul simplex se ajunge la un moment dat la: 7 8 CB XB a1 a2 B a3 0 3 0 3 8

a2

fj

2

2 1

16

2 4

1 8

0 a3 1 0

0 a4 1 − 2 1

0

2 4

∆j Linia lui ∆ j este a. b. c. d.

3, 0, 0, -4 -3, 0, 0, 4 7, 8, 0, 0 -7, -8, 0, 0

9. Fie problema de programare liniara [max]f = 7x 1 + 8x 2 ÏÔÔ ÔÔ ÔÔ 2x 1 + x 2 ≤ 5 ÌÔÔ ÔÔ x + 2x ≤ 4 ÔÓ 1 2

x1,x2 ≥ 0 Aplicandu-se algoritmul simplex se ajunge la un moment dat la: 7 8 CB XB a1 a2 B a3 0 3 0 3 8

a2

2

2 1

1

0

0 a4 1 − 2 1

fj

16

2 4

8

0

2 4

3

0

0

-4

∆j Pivotul se afla pe coloana lui a. a 1 b. a 2 c. a 3 d. a 4

5

0 a3 1

10. Fie problema de programare liniara [max]f = 7x 1 + 8x 2 ÏÔÔ ÔÔ ÔÔ 2x 1 + x 2 ≤ 5 ÔÌÔ ÔÔÔ x + 2x ≤ 4 2 Ó 1

x1,x2 ≥ 0 a. b. c. d.

problema are optim infinit; solutia optima este f max = 54, x o = ÁËÊ 2,5 ˜¯ˆ , y o = ÊÁË 0,0 ˆ˜¯ solutia optima este f max = 22, x o = ÁËÊ 2,1 ˆ˜¯ , y o = ÊÁË 0,0 ˆ˜¯ solutia optima este f max = 29, x o = ÁËÊ 3,1 ˆ˜¯ , y o = ÊÁË 0,0 ˆ˜¯

11. Fie problema de programare liniara [min]f = 6x 1 + 7x 2 ÏÔÔ ÔÔ ÔÔ −x 1 + x 2 ≥ 1 ÌÔÔ ÔÔÔ x − 2x ≤ 1 2 Ó 1

x 1 ,x 2 ≥ 0 Matricea asociata formei standard este ÊÁ ˆ˜ ÁÁ ˜ ÁÁ −1 1 1 0 ˜˜˜ ˜˜ a. A = ÁÁ ÁÁ ˜ Á 1 2 1 0 ˜˜¯ Ë ÁÊÁ ˜ˆ˜ ÁÁ −1 1 1 0 ˜˜˜ Á b. A = ÁÁ ˜˜ ÁÁ ˜ Á 1 −2 0 1 ˜˜¯ Ë

c.

d.

ÊÁ ÁÁ Á A = ÁÁÁ ÁÁ Á Ë ÊÁ ÁÁ Á A = ÁÁÁ ÁÁ Á Ë

1

1

1

1

2

0

−1

1

−1

1

−2

0

12. Fie problema de programare liniara [min]f = 6x 1 + 7x 2 ÏÔÔ ÔÔ ÔÔ −x 1 + 5x 2 ≥ 1 ÌÔÔ ÔÔÔ x − 2x ≥ 1 2 Ó 1

x 1 ,x 2 ≥ 0 Duala acestei probleme de programare liniara este a. [max]g = 6y 1 + 7y 2 c. ÏÔÔ ÔÔ ÔÔ −y 1 + 5y 2 ≥ 1 ÌÔÔ ÔÔ y − 2y ≥ 1 ÔÓ 1 2 b.

y 1 ,y 2 ≥ 0 [max]g = y 1 + y 2 ÏÔÔ ÔÔ ÔÔ −y 1 + 5y 2 ≥ 6 ÔÌÔ ÔÔÔ y − 2y ≥ 7 2 Ó 1

d.

y 1 ,y 2 ≥ 0

[max]g = y 1 + y 2 ÏÔÔ ÔÔ ÔÔ −y 1 + y 2 ≤ 6 ÌÔÔ ÔÔÔ 5y 1 − 2y 2 ≤ 7 Ó y 1 ,y 2 ≥ 0 [max]g = y 1 + y 2 ÏÔÔ ÔÔ ÔÔ −y 1 + y 2 ≥ 6 ÔÌÔ ÔÔÔ 5y − 2y ≥ 7 2 Ó 1 y 1 ,y 2 ≥ 0

6

ˆ˜ ˜ 1 ˜˜˜ ˜˜ ˜ 0 ˜˜¯ ˜ˆ˜ 0 ˜˜˜ ˜˜ ˜ 1 ˜˜¯

13. Fie problema de programare liniara [min]f = 4x 1 + 5x 2 + 6x 3 ÏÔÔ ÔÔ ÔÔ x 1 + 2x 2 + x 3 ≥ 2 ÔÌÔ ÔÔÔ 2x + x + x ≥ 1 2 3 Ó 1

x 1 ,x 2 ,x 3 ≥ 0 Duala acestei probleme de programare liniara este: a. [max]g = 2y 1 + y 2 c. ÏÔÔ ÔÔÔ y 1 + 2y 2 ≥ 4 ÔÔ Ô 2y + y ≥ 5 ÌÔ 1 2 ÔÔÔ ÔÔ y + y ≥ 6 ÔÓ 1 2 b.

y 1 ,y 2 ≥ 0 [min]g = 2y 1 + y 2 ÏÔÔ ÔÔ y 1 + 2y 2 ≤ 4 ÔÔ ÔÔ ÔÌÔÔ 2y 1 + y 2 ≤ 5 ÔÔÔ ÔÔÓ y 1 + y 2 ≤ 6

d.

y 1 ,y 2 ≥ 0

[min]g = 2y 1 + y 2 ÏÔÔ ÔÔÔ y 1 + 2y 2 = 4 ÔÔ Ô 2y + y = 5 ÌÔ 1 2 ÔÔÔ ÔÔ y + y = 6 ÔÓ 1 2 y 1 ,y 2 ≥ 0 [max]g = 2y 1 + y 2 ÏÔÔ ÔÔ y 1 + 2y 2 ≤ 4 ÔÔ ÔÔ ÔÌÔÔ 2y 1 + y 2 ≤ 5 ÔÔÔ ÔÔÓ y 1 + y 2 ≤ 6

y 1 ,y 2 ≥ 0

14. Fie problema de programare liniara [max]f = 2x 1 − x 2 + 3x 3 + 2x 4 + 3x 5 ÏÔÔ ÔÔ 3x 1 + 2x 3 + 5x 4 ≥ 4 ÔÔ ÔÔ ÌÔÔ 2x 1 + x 2 − x 3 + x 4 = 1 ÔÔ ÔÔ ÔÔÓ x 1 + 2x 3 + 2x 4 + x 5 = 5

x i ≥ 0,i = 1,5 Matricea asociata formei standard are prima linie: a. 3 0 2 5 0 1 b. 3 2 5 4 c. 3 0 2 5 0 -1 d. alt raspuns

7

15. Fie problema de programare liniara [max]f = 7x 1 − 8x 2 + 3x 3 + 2x 4 + 2x 5 ÏÔÔ ÔÔ 3x 1 + x 3 + x 4 ≤ 4 ÔÔ ÔÔ ÌÔÔ 2x 1 − x 3 + x 4 + x 5 = 1 ÔÔ ÔÔ ÔÔÓ x 1 + x 2 + 2x 3 + 2x 4 = 5

x i ≥ 0,i = 1,5 Dupa ce se aduce la forma standard se obtine primul tabel simplex: 7 -8 3 2 CB XB a1 a2 a3 a4 B 4 3 0 1 1 1 2 0 -1 1 2 1 1 2 2 Baza initiala pentru algoritmul simplex este a. B = {a 6 ,a 2 ,a 5 } b. B = {a 2 ,a 6 ,a 5 } c. B = {a 2 ,a 5 ,a 6 } d. B = {a 6 ,a 5 ,a 2 }

2 a5 0 1 0

0 a6 1 0 0

5 a5 0 0 1

0 a6 1 0 0

16. Fie problema de programare liniara [max]f = 2x 1 + 2x 2 + 3x 3 + 2x 4 + 5x 5 ÏÔÔ ÔÔ 3x 1 + x 3 + x 4 ≤ 4 ÔÔ ÔÔ ÌÔÔ 2x 1 + x 2 − x 3 + x 4 = 1 ÔÔ ÔÔ ÔÔÓ x 1 + 2x 3 + 2x 4 + x 5 = 5

x i ≥ 0,i = 1,5 Dupa ce se aduce la forma standard se obtine primul tabel simplex: 2 2 3 2 CB XB a1 a2 a3 a4 B a6 0 4 3 0 1 1 a2 2 1 2 1 -1 1 a5 5 2 1 0 2 2 Linia lui f j este a. b. c. d.

12, 9, 2, 8, 12, 5, 0 0, 2, 2, 3, 2, 5, 0 0, 9, 2, -2, 12, 5, 0 alt raspuns

8

17. Fie problema de programare liniara [max]f = 2x 1 − x 2 + 3x 3 + 2x 4 + 3x 5 ÏÔÔ ÔÔ 3x 1 + x 3 + x 4 ≤ 4 ÔÔ ÔÔ ÌÔÔ 2x 1 + x 2 − x 3 + x 4 = 1 ÔÔ ÔÔ ÔÔÓ x 1 + 2x 3 + 2x 4 + x 5 = 5

x i ≥ 0,i = 1,5 Dupa ce se aduce la forma standard se obtine tabelul simplex: 2 -1 3 CB XB a1 a2 a3 B a6 0 4 3 0 1 a2 -1 1 2 1 -1 a5 3 2 1 0 2 fj 5 1 -1 7 ∆j

1

0

-4

2 a4 1 1 2 5

3 a5 0 0 1 3

0 a6 1 0 0 0

-3

0

0

2 a4 1 1 2 5

3 a5 0 0 1 3

0 a6 1 0 0 0

-3

0

0

Pivotul se afla pe coloana lui a. a 1 b. a 2 c. a 3 d. a 4 18. Fie problema de programare liniara [max]f = 2x 1 − x 2 + 3x 3 + 2x 4 + 3x 5 ÏÔÔ ÔÔ 3x 1 + x 3 + x 4 ≤ 4 ÔÔ ÔÔ ÌÔÔ 2x 1 + x 2 − x 3 + x 4 = 1 ÔÔ ÔÔ ÔÔÓ x 1 + 2x 3 + 2x 4 + x 5 = 5

x i ≥ 0,i = 1,5 Dupa ce se aduce la forma standard se obtine tabelul simplex: 2 -1 3 CB B XB a1 a2 a3 a6 0 4 3 0 1 a2 -1 1 2 1 -1 a5 3 2 1 0 2 fj 5 1 -1 7

∆j

1

0

-4

Ce decizie se ia? a. s-a obtinut solutia optima x o = ÊÁË 0,1,0,0,2ˆ˜¯ b. problema are optim infinit c. solutia obtinuta nu este optima, a 1 intra in baza, a 5 iese din baza d. solutia obtinuta nu este optima, a 1 intra in baza, a 2 iese din baza

9

19. Fie problema de programare liniara [max]f = 2x 1 − x 2 + 3x 3 + 2x 4 + 3x 5 ÏÔÔ ÔÔ 3x 1 + x 3 + x 4 ≤ 4 ÔÔ ÔÔ ÌÔÔ 2x 1 + x 2 − x 3 + x 4 = 1 ÔÔ ÔÔ ÔÔÓ x 1 + 2x 3 + 2x 4 + x 5 = 2

x i ≥ 0,i = 1,5 Atunci a. problema are optim infinit ÊÁ 1 11 5 ˆ˜˜ Á b. f max = , x 0 = ÁÁÁÁ ,0,0,0, ˜˜˜˜ ÁË 2 2 2 ˜¯ 11 0 ÊÁÁÁ 1 3 ˆ˜˜˜ Á c. f max = , x = ÁÁ ,0,1,0, ˜˜˜ ÁË 2 2 2 ˜¯ ÁÊÁ 1 11 3 ˜ˆ˜ d. f max = , x 0 = ÁÁÁÁ ,0,0,0, ˜˜˜˜ ÁË 2 2 2 ˜¯ 20. Se considera problema de transport: B1 B2 B3 N1 2 1 3 N2 1 4 2 N3 3 5 4 Necesar 30 40 60 O solutie initiala de baza obtinuta prin metoda coltului N-V este a. x 11 = 20, x 21 = 10, x 22 = 35, x 32 = 5, x 33 = 60, in rest x ij = 0 b.

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

c.

x 11 = 30, x 21 = 10, x 22 = 15, x 32 = 5, x 33 = 60, in rest x ij = 0

d.

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

21. Se considera problema de transport: B1 B2 B3 N1 2 1 3 N2 1 4 2 N3 3 5 4 Necesar 30 40 60 O solutie initiala de baza obtinuta prin metoda costului minim pe linie este a. x 12 = 40, x 21 = 30, x 23 = 15, x 32 = 10, x 33 = 45, in rest x ij = 0 b.

x 12 = 20, x 21 = 15, x 23 = 15, x 32 = 20, x 33 = 50, in rest x ij = 0

c.

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

d.

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

10

Disponibil 20 45 65

Disponibil 20 45 65

22. Fie problema de programare liniara [min]f = 6x 1 + 8x 2 ÏÔÔ ÔÔ ÔÔ 5x 1 + 2x 2 ≥ 7 ÔÌÔ ÔÔ 3x + x ≥ 4 2 Ó 1

x 1,2 ≥ 0 Duala acesti probleme de programare liniara este c. a. [max]f = 6x 1 + 8x 2 ÏÔÔ ÔÔ ÔÔ 5x 1 + 2x 2 ≥ 7 ÌÔ ÔÔÔ 3x + x ≥ 4 ÔÓ 1 2 b.

x 1,2 ≥ 0 [max]f = 7x 1 + 4x 2 ÏÔÔ ÔÔ ÔÔ 5x 1 + 3x 2 ≥ 6 ÌÔ ÔÔ 2x + x ≥ 8 ÔÓ 1 2

d.

x 1,2 ≥ 0

[max]f = 7x 1 + 4x 2 ÏÔÔ ÔÔ ÔÔ 5x 1 + 3x 2 ≤ 6 ÌÔ ÔÔÔ 2x + x ≤ 8 ÔÓ 1 2 x 1,2 ≥ 0 [max]f = 7x 1 + 4x 2 ÏÔÔ ÔÔ ÔÔ 5x 1 + 3x 2 = 6 ÌÔ ÔÔ 2x + x = 8 ÔÓ 1 2 x 1,2 ≥ 0

23. Fie problema de programare liniara [max]f = 3x 1 + 5x 2 + x 3 + 6x 4 ÏÔÔ ÔÔ x 1 + x 3 + 2x 4 ≤ 40 ÔÔ ÔÔ ÌÔÔ 2x 1 + x 2 + 3x 3 ≤ 16 ÔÔ ÔÔ ÔÔÓ x 1 + x 2 + 2x 3 ≤ 48

x i ≥ 0,i = 1,4 Matricea sistemului restictiilor este ÊÁ 0 1 2 ˆ˜ ÁÁÁ ˜˜˜ ÁÁ ˜˜ Á a. A = ÁÁÁ 1 3 0 ˜˜˜˜ ÁÁ ˜ ÁÁ 1 2 0 ˜˜˜ ÁË ˜¯ ÊÁ 1 1 2 ˆ˜ ÁÁ ˜˜ ÁÁ ˜˜ ÁÁ ˜ Á b. A = ÁÁ 2 1 3 ˜˜˜˜ ÁÁÁ ˜˜ ÁÁ 1 1 2 ˜˜˜ Ë ¯ ÁÊÁ 1 0 1 2 ˜ˆ˜ ÁÁ ˜˜ ÁÁ ˜˜ Á c. A = ÁÁÁ 2 1 3 0 ˜˜˜˜ ÁÁ ˜ ÁÁ 1 1 2 0 ˜˜˜ ÁË ˜¯ ÁÊÁ 1 1 1 2 ˜ˆ˜ ÁÁ ˜˜ ÁÁ ˜˜ Á d. A = ÁÁÁ 2 3 3 0 ˜˜˜˜ ÁÁ ˜ ÁÁ 1 1 2 1 ˜˜˜ ÁË ˜¯

11

24. Fie problema de programare liniara [max]f = 3x 1 + 5x 2 + x 3 + 6x 4 ÏÔÔ ÔÔ x 1 + x 3 + 2x 4 ≤ 40 ÔÔ ÔÔ ÌÔÔ 2x 1 + x 2 + 3x 3 ≤ 16 ÔÔ ÔÔ ÔÔÓ x 1 + x 2 + 2x 3 ≤ 48

x i ≥ 0,i = 1,4 Forma standard a problemei de programare liniara este a. [max]f = 3x 1 + 5x 2 + x 3 + 6x 4 ÏÔÔ ÔÔ x 1 + x 3 + 2x 4 = 40 ÔÔ ÔÔ ÌÔÔ 2x 1 + x 2 + 3x 3 = 16 ÔÔ ÔÔ ÔÔÓ x 1 + x 2 + 2x 3 = 48 b.

c.

d.

x i ≥ 0,i = 1,4 [max]f = 3x 1 + 5x 2 + x 3 + 6x 4 ÏÔÔ ÔÔ x 1 + x 3 + 2x 4 ≥ 40 ÔÔ ÔÔ ÌÔÔ 2x 1 + x 2 + 3x 3 ≥ 16 ÔÔ ÔÔ ÔÔÓ x 1 + x 2 + 2x 3 ≥ 48 x i ≥ 0,i = 1,4 [max]f = 3x 1 + 5x 2 + x 3 + 6x 4 + My 1 + My 2 + My 3 ÏÔÔ ÔÔ x 1 + x 3 + 2x 4 + y 1 ≤ 40 ÔÔ ÔÔ ÌÔÔ 2x 1 + x 2 + 3x 3 + y 2 ≤ 16 ÔÔ ÔÔ ÔÔÓ x 1 + x 2 + 2x 3 + y 3 ≤ 48

x i ≥ 0,i = 1,4,y i ≥ 0,i = 1,3 [max]f = 3x 1 + 5x 2 + x 3 + 6x 4 + 0y 1 + 0y 2 + 0y 3 ÏÔÔ ÔÔ x 1 + x 3 + 2x 4 + y 1 = 40 ÔÔ ÔÔ ÌÔÔ 2x 1 + x 2 + 3x 3 + y 2 = 16 ÔÔ ÔÔ ÔÔÓ x 1 + x 2 + 2x 3 + y 3 = 48 x i ≥ 0,i = 1,4,y i ≥ 0,i = 1,3

12

25. Fie problema de programare liniara [max]f = 3x 1 + 5x 2 + x 3 + 6x 4 ÏÔÔ ÔÔ x 1 + x 3 + 2x 4 ≤ 40 ÔÔ ÔÔ ÌÔÔ 2x 1 + x 2 + 3x 3 ≤ 16 ÔÔ ÔÔ ÔÔÓ x 1 + x 2 + 2x 3 ≤ 48

x i ≥ 0,i = 1,4 Prima iteratie a algoritmului simplex este CB XB a1 a2 B a5 0 40 1 0 a6 0 16 2 1 a7 0 48 1 1 Linia lui ∆ este a. 3, 5, 1, 6, 0, 0, 0 b. -3, -5, -1, -6, 0, 0, 0 c. 3, 5, 1, 6, M, M, M d. 3, 5, 1, 6, -M, -M, -M

a3 1

a4 2

a5 1

a6 0

a7 0

3 2

0 0

0 0

1 0

0 1

1 a3 1

6 a4 2

0 a5 1

0 a6 0

0 a7 0

3 2 0 1

0 0 0 6

0 0 0 0

1 0 0 0

0 1 0 0

26. Fie problema de programare liniara [max]f = 3x 1 + 5x 2 + x 3 + 6x 4 ÏÔÔ ÔÔ x 1 + x 3 + 2x 4 ≤ 40 ÔÔ ÔÔ ÌÔÔ 2x 1 + x 2 + 3x 3 ≤ 16 ÔÔ ÔÔ ÔÔÓ x 1 + x 2 + 2x 3 ≤ 48

x i ≥ 0,i = 1,4 Prima iteratie a algoritmului simplex este 3 5 CB X a a B B 1 2 a5 0 40 1 0 a6 0 16 2 1 a7 0 48 1 1 f 0 0 0 ∆j 3 5 Pivotul se afla pe a. coloana lui a 3 , linia lui a 5 b. coloana lui a 3 , linia lui a 6 c. coloana lui a 4 , linia lui a 5 d. coloana lui a 4 , linia lui a 6

13

27. Fie problema de programare liniara [max]f = 3x 1 + 5x 2 + x 3 + 6x 4 ÏÔÔ ÔÔ x 1 + x 3 + 2x 4 ≤ 40 ÔÔ ÔÔ ÌÔÔ 2x 1 + x 2 + 3x 3 ≤ 16 ÔÔ ÔÔ ÔÔÓ x 1 + x 2 + 2x 3 ≤ 48

x i ≥ 0,i = 1,4 Prima iteratie a algoritmului simplex este 3 5 CB XB a1 a2 B a5 0 40 1 0 a6 0 16 2 1 a7 48 1 1 0 f 0 0 0 ∆j 3 5

1 a3 1

6 a4 2

0 a5 1

0 a6 0

0 a7 0

3 2 0 1

0 0 0 6

0 0 0 0

1 0 0 0

0 1 0 0

0 a5

0 a6 0

0 a7 0

1 0 0 0

0 1 0 0

Coloana lui a 1 din urmatorul tabel simplex este 1

1

2

2

3

a.

b.

1

1

2

c.

1

2 1

28. Fie problema de programare liniara [max]f = 3x 1 + 5x 2 + x 3 + 6x 4 ÏÔÔ ÔÔ x 1 + x 3 + 2x 4 ≤ 40 ÔÔ ÔÔ ÌÔÔ 2x 1 + x 2 + 3x 3 ≤ 16 ÔÔ ÔÔ ÔÔÓ x 1 + x 2 + 2x 3 ≤ 48

x i ≥ 0, i = 1,4 A doua iteratie a algoritmului simplex este 3 5 CB XB a1 a2 B 1 a4 6 20 0 2

0 0

a6 a7 f ∆j

16 48 120

2 1 3 0

1 a3 1

6 a4 1

2

1 1 0 5

3 2 3 -2

2

0 0 6 0

Stabiliti care este vectorul care intra si respectiv care iese din baza a. intra a 1 , iese a 7 b. intra a 2 , iese a 6 c. intra a 2 , iese a 7 d. intra a 1 , iese a 6

14

1

0 0 3 -3

29. Fie problema de programare liniara [max]f = 3x 1 + 5x 2 + x 3 + 6x 4 ÏÔÔ ÔÔ x 1 + x 3 + 2x 4 ≤ 40 ÔÔ ÔÔ ÌÔÔ 2x 1 + x 2 + 3x 3 ≤ 16 ÔÔ ÔÔ ÔÔÓ x 1 + x 2 + 2x 3 ≤ 48

x i ≥ 0, i = 1,4 Prin aplicarea algoritmului simplex se ajunge la urmatorul tabel simplex 3 5 1 6 0 CB XB a1 a2 a3 a4 a5 B 1 1 1 a4 6 20 0 1 2

5 0

a2 a7 f ∆j

16 32 200

2 -1 13 -10

2

1 0 5 0

3 -1 18 -17

0 a6 0

0 a7 0

1 -1 5 -5

0 1 0 0

2

0 0 6 0

0 0 3 -3

Ce decizie se ia? a. problema are optim infinit; b. solutia obtinuta nu este ce optima: intra a 3 in baza si iese a 7 c. solutia obtinuta este cea optima si f max = 200, x o = ÁËÊ 0,16,0,20 ˜¯ˆ , y o = ÁËÊ 0,0,32 ˜¯ˆ d. solutia obtinuta este cea optima si f max = 172, x o = ÁËÊ 20,16,32,0 ˜¯ˆ , y o = ÁËÊ 0,0,0 ˜¯ˆ 30. Fie problema de programare liniara: max f = 10x 1 + 16x 2 . ÔÏÔÔ ÔÔÔ 2x 1 + 5x 2 ≤ 1200 ÔÔ ÌÔÔ x 1 + 1,5x 2 ≤ 300 ÔÔ ÔÔ 4x + x ≤ 600 ÔÓ 1 2 x 1 ,x 2 ≥ 0 Forma standard a problemei de programare liniara va fi a. max f = 10x 1 + 16x 2 + Mu 1 + Mu 2 + Mu 3 c. max f = 10x 1 + 16x 2 − Mu 1 − Mu 2 − Mu 3 ÏÔÔ ÏÔÔ ÔÔ 2x 1 + 5x 2 + u 1 = 1200 ÔÔ 2x 1 + 5x 2 + u 1 = 1200 ÔÔÔ ÔÔÔ Ô Ô ÌÔÔ x 1 + 1,5x 2 + u 2 = 300 ÌÔÔ x 1 + 5x 2 + u 2 = 300 ÔÔ ÔÔ ÔÔÔ ÔÔÔ 4x + x + u = 600 4x 1 + x 2 + u 3 = 600 1 2 3 ÓÔ ÓÔ x 1 ,x 2 ≥ 0, u 1 ,u 2 ,u 3 ≥ 0 x 1 ,x 2 ≥ 0, u 1 ,u 2 ,u 3 ≥ 0 b. max f = 10x 1 + 16x 2 + 0u 1 + 0u 2 + 0u 3 d. max f = 10x 1 + 16x 2 − 0u 1 − 0u 2 − 0u 3 ÏÔÔ ÏÔÔ ÔÔ 2x 1 + 5x 2 + u 1 = 1200 ÔÔ 2x 1 + 5x 2 − u 1 = 1200 ÔÔÔ ÔÔÔ Ô Ô ÔÌÔÔ x 1 + 1,5x 2 + u 2 = 300 ÔÌÔÔ x 1 + 5x 2 − u 2 = 300 ÔÔ ÔÔ ÔÔ 4x + x + u = 600 ÔÔ 4x + x − u = 600 1 2 3 1 2 3 ÓÔ ÓÔ x 1 ,x 2 ≥ 0, u 1 ,u 2 ,u 3 ≥ 0 x 1 ,x 2 ≥ 0, u 1 ,u 2 ,u 3 ≥ 0

15

31. Fie problema de programare liniara: max f = 10x 1 + 16x 2 ÔÏÔÔ ÔÔ 2x 1 + 5x 2 ≤ 1200 ÔÔ Ô ÌÔÔ x 1 + 1,5x 2 ≤ 300 ÔÔ ÔÔÔ ÔÓ 4x 1 + x 2 ≤ 600

x 1 ,x 2 ≥ 0 Prima iteratie a algoritmului simplex este: 10 CB XB a1 B a 0 1200 2 3 a 0 300 1 4 a 0 600 4 5 fj 0 ∆j =cj −f j

10

Pivotul se va afla pe coloana corespunzatoare lui: a. a 1 d. b. a 2 e. c. a 3 32. Fie problema de programare liniara: max f = 10x 1 + 16x 2 ÔÏÔÔ ÔÔÔ 2x 1 + 5x 2 ≤ 1200 ÔÔ ÌÔÔ x 1 + 1,5x 2 ≤ 300 ÔÔ ÔÔ 4x + x ≤ 600 ÔÓ 1 2 x 1 ,x 2 ≥ 0 Prima iteratie a algoritmului simplex este: 10 CB XB a1 B a3 0 1200 2 a4 0 300 1 a5 0 600 4 fj 0

∆j =cj −f j

10

16 a2 5 3/2 1 0

0 a3 1 0 0 0

0 a4 0 1 0 0

0 a5 0 0 1 0

16

0

0

0

16 a2 5 3/2 1 0

0 a3 1 0 0 0

0 a4 0 1 0 0

0 a5 0 0 1 0

16

0

0

0

a4 a5

Stabiliti care este vectorul care intra in baza, respectiv care iese din baza a. intra a 2 , iese a 3 d. intra a 1 , iese a 3 b. intra a 2 , iese a 4 e. intra a 1 , iese a 4 c. intra a 2 , iese a 5

16

33. Fie problema de programare liniara: max f = 10x 1 + 16x 2 ÔÏÔÔ ÔÔ 2x 1 + 5x 2 ≤ 1200 ÔÔ Ô ÌÔÔ x 1 + 1,5x 2 ≤ 300 ÔÔ ÔÔÔ ÔÓ 4x 1 + x 2 ≤ 600

x1,x2 ≥ 0 Prima iteratie a algoritmului simplex este: 10 CB XB a1 B a 0 1200 2 3 a 0 300 1 4 a 0 600 4 5 fj 0 ∆j =cj −f j

10

16 a2 5 3/2 1 0

0 a3 1 0 0 0

0 a4 0 1 0 0

0 a5 0 0 1 0

16

0

0

0

Care este solutia optima pentru problema de programare liniara? a. max f = 3200 x 0 = ÊÁË 0,200 ˆ˜¯ , c. nu are solutie b.

y=(200,0,400) max f = 3400 x 0 = ÁÊË 0,400 ˜ˆ¯ , y=(200,0,400)

34. Fie problema de programare liniara: minf = 2x 1 + x 2 + x 3 + 3x 4 + 2x 5 ÏÔÔ ÔÔ x 1 + x 4 + 2x 5 = 8 ÔÔÔ Ô ÌÔÔ x 2 + 2x 4 + x 5 = 12 ÔÔ ÔÔÔ x + x 4 + 3x 5 = 16 ÓÔ 3 x i ≥ 0, i=1,2,3 Baza initiala pentru algoritmul simplex este ÏÔ ¸Ô a. B = ÌÔ a 1 ,a 2 ,a 5 ˝Ô Ó ˛ ÏÔ ¸Ô b. B = ÔÌ a 1 ,a 2 ,a 3 Ô˝ Ó ˛ ÏÔ ¸Ô c. B = ÔÌ a 1 ,a 3 ,a 4 Ô˝ Ó ˛

17

d. e.

ÏÔ ¸Ô B = ÌÔ a 2 ,a 3 ,a 4 ˝Ô Ó ˛ nu are baza initiala

35. Fie problema de programare liniara: minf = 2x 1 + x 2 + x 3 + 3x 4 + 2x 5 ÔÏÔÔ ÔÔÔ x 1 + x 4 + 2x 5 = 8 ÔÔ ÌÔÔ x 2 + 2x 4 + x 5 = 12 ÔÔ ÔÔÔ ÔÓ x 3 + x 4 + 3x 5 = 16 x i ≥ 0, i=1,5

CB 2 1 1

XB 8 12 16 ∆j =cj −f j

B a1 a2 a3

2 a1 1 0 0

1 a2 0 1 0

1 a3 0 0 1

3 a4 1 2 1

2 a5 2 1 3

Linia corespunzatoare lui ∆ j = c j − f j este a.

2

1

1

3

2

c.

0

0

0

6

b.

2

1

1

5

8

d.

0

0

0

−2

36. Fie problema de programare liniara: min f = 2x 1 + x 2 + x 3 + 3x 4 + 2x 5 ÏÔÔ ÔÔ x 1 + x 4 + 2x 5 = 8 ÔÔÔ Ô ÌÔÔ x 2 + 2x 4 + x 5 = 12 ÔÔ ÔÔÔ x + x 4 + 3x 5 = 16 ÓÔ 3 x i ≥ 0, i=1,2,3 Precizati care este solutia optima a. min f = 12 si x 0 = ÊÁÁ 0 4 4 8 0 ˆ˜˜ Ë ¯ 0 Ê ˆ Á ˜ b. min f = 16 si x = Á 4 0 4 8 0 ˜ Ë ¯

18

c. d.

2 −6

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

0

0

8

8

4

0

4 ˆ˜˜ ¯ 4 ˆ˜˜ ¯

37. Fie problema de programare liniara: min f =x 1 + 2x 2 + x 5 ÔÏÔÔ 2x 1 + x 2 + x 3 ≥ 1 ÔÔ ÔÔ Ô −x 1 + 3x 2 ≤ 0 ÌÔÔ ÔÔ ÔÔÔ ÔÓ 2x 1 + 2x 2 + x 3 + x 4 + x 5 = 5

x i ≥ 0, (∀)i = 1,5 Forma standard a problemei este : a. minf = x 1 + 2x 2 + x 5 + y 1 ⋅ 0 − y 2 ⋅ 0 ÏÔÔ ÔÔ 2x 1 + x 2 + x 3 + y 1 = 1 ÔÔÔ Ô −x 1 + 3x 2 − y 2 = 0 ÌÔÔ ÔÔ ÔÔÔ 2x + 2x 2 + x 3 + x 4 + x 5 = 5 ÓÔ 1 x i ≥ 0, (∀) i = 1,5 y j ≥ 0, (∀)j = 1,2 b.

c.

minf = x 1 + 2x 2 + x 5 − y 1 ⋅ 0 − y 2 ⋅ 0 ÏÔÔ ÔÔ 2x 1 + x 2 + x 3 − y 1 = 1 ÔÔÔ Ô −x 1 + 3x 2 − y 2 = 0 ÌÔÔ ÔÔ ÔÔÔ 2x + 2x 2 + x 3 + x 4 + x 5 = 5 ÓÔ 1 x i ≥ 0, (∀)i = 1,5, y j ≥ 0, (∀)j = 1,2

minf = x 1 + 2x 2 + x 5 + y 1 ⋅ 0 + y 2 ⋅ 0 ÏÔÔ ÔÔ 2x 1 + x 2 + x 3 − y 1 = 1 ÔÔÔ Ô −x 1 + 3x 2 + y 2 = 0 ÔÌÔÔ ÔÔ ÔÔ 2x + 2x + x + x + x = 5 2 3 4 5 ÓÔ 1 x i ≥ 0, (∀)i = 1,5y j ≥ 0, (∀)j = 1,2

38. Fie problema de programare liniara: min f =x 1 + 2x 2 + x 5 ÏÔÔ ÔÔ 2x 1 + x 2 + x 3 ≥ 1 ÔÔÔ Ô −x 1 + 3x 2 ≤ 0 ÌÔÔ ÔÔ ÔÔÔ 2x + 2x 2 + x 3 + x 4 + x 5 = 5 ÓÔ 1 x i ≥ 0, (∀)i = 1,5 Matricea asociata problemei scrisa in forma standard este: ÊÁ 2 1 1 ÊÁ 2 0 0 −1 0 ˆ˜˜˜ ÁÁ ÁÁ ÁÁ ˜˜ ÁÁ ÁÁ ˜˜ Á a. A = ÁÁÁ −1 3 0 0 0 0 −1 ˜˜˜ c. A = ÁÁÁÁ −1 ÁÁ ˜˜ ÁÁ ÁÁ 2 2 −1 −1 1 0 ÁÁ 2 0 ˜˜˜ ÁË ÁË ¯ ÊÁ 2 1 1 0 0 −1 0 ˆ˜ ÊÁ 2 ÁÁ ˜˜ ÁÁ ÁÁ ˜˜ ÁÁ ÁÁ ˜˜ Á b. A = ÁÁÁ −1 3 0 0 0 0 1 ˜˜˜ d. A = ÁÁÁÁ −1 ÁÁ ˜˜ ÁÁ ÁÁ 2 2 1 1 1 0 0 ˜˜ ÁÁ 2 ÁË ˜¯ ÁË

19

1

1

0

0

−1

3

0

0

0

0

2

1

−1

−1

0

1

1

0

0

1

3

0

0

0

0

2

1

1

1

0

0 ˆ˜˜˜ ˜˜ ˜ 1 ˜˜˜˜ ˜˜ 0 ˜˜˜ ¯

0 ˆ˜˜˜ ˜˜ ˜ 1 ˜˜˜˜ ˜˜ 0 ˜˜˜ ¯

39. Fie urmatoarea problema de programare liniara: maxf = 3x 1 + 4x 2 + x 3 ÔÏÔÔ ÔÔÔ 5x 1 − x 2 + 2x 3 + x 4 = 7 ÔÔ ÌÔÔ x 1 + 2x 2 − x 3 − x 5 ≥ 4 ÔÔ ÔÔÔ ÔÓ 3x 1 + 2x 2 + 4x 3 ≤ 2 xi ≥ 0 Matricea asociata formei standard este ÊÁ 5 −1 2 1 0 0 0 ˆ˜˜˜ ÁÁ ÁÁ ˜˜ ÁÁ ˜ Á c. a. A = ÁÁ 1 2 −1 0 −1 −1 0 ˜˜˜˜ ÁÁ ˜˜ ÁÁ 3 2 ˜ 4 0 0 0 1 ˜˜ ÁË ¯ ÁÊÁ 5 −1 2 1 0 0 0 ˜ˆ˜ ÁÁ ˜˜ ÁÁ ˜˜ Á b. A = ÁÁÁ 1 2 −1 0 1 −1 0 ˜˜˜˜ d. ÁÁ ˜˜ ÁÁ 3 2 ˜ 4 0 0 0 1 ˜˜ ÁË ¯ 40. Fie urmatoarea problema de programare liniara: maxf = 3x 1 + 4x 2 + x 3 ÏÔÔ ÔÔ 5x 1 − x 2 + 2x 3 + x 4 = 7 ÔÔÔ Ô ÔÌÔÔ x 1 + 2x 2 − x 3 − x 5 = 4 ÔÔ ÔÔ 3x + 2x + 4x = 2 1 2 3 ÓÔ xi ≥ 0 Prima iteratie a algoritmului simplex este: Prima iteratie pentru aceasta problema este: 3 4 1 CB XB a1 a2 a3 B a4 0 7 5 -1 2 u1 -M 4 1 2 -1 u2 -M 2 3 2 4 ∆j =cj −f j

ÊÁ 5 ÁÁ ÁÁ Á A = ÁÁÁÁ 1 ÁÁ ÁÁ 3 ÁË ÊÁ 5 ÁÁ ÁÁ Á A = ÁÁÁÁ 1 ÁÁ ÁÁ 3 ÁË

0 a4 1 0 0

−1

2

1

0

0

2

−1

0

−1

1

2

4

0

0

0

−1

2

1

0

0

2

−1

0

−1

1

2

4

0

0

0

0 a5 0 -1 0

-M u1 0 1 0

-M u2 0 0 1

Linia corespunzatoare lui ∆ j = c j − f j este: a. b.

3+4M;4+4M;1+3M;0;-M;-M-1 3+4M;4+4M;1+3M;0;-M;0,0

c. d.

20

-3+4M;-4+4M;-1+3M;0;M;M-1 -3-4M;-4-4M;1-3M;0;-M;-M+1

0 ˆ˜˜˜ ˜˜ ˜ 0 ˜˜˜˜ ˜˜ 1 ˜˜˜ ¯ 0 ˜ˆ˜˜ ˜˜ ˜ 0 ˜˜˜˜ ˜˜ 1 ˜˜˜ ¯

41. Fie urmatoarea problema de programare liniara: maxf = 3x 1 + 4x 2 + x 3 ÔÏÔÔ ÔÔÔ 5x 1 − x 2 + 2x 3 + x 4 = 7 ÔÔ ÌÔÔ x 1 + 2x 2 − x 3 − x 5 = 4 ÔÔ ÔÔÔ ÔÓ 3x 1 + 2x 2 + 4x 3 = 2 xi ≥ 0 Prima iteratie pentru aceasta problema este:

CB B -M a4 -M u1 u2 0 ∆j =cj −f j

XB 7 4 2

3 a1 5 1 3

4 a2 -1 2 2

1 a3 2 -1 4

0 a4 1 0 0

0 a5 0 -1 0

-M u1 0 1 0

-M u2 0 0 1

Pentru prima iteratie a algoritmului simplex stabiliti ce vector intra in baza respectiv care iese din baza a. intra a 1 iese a 4 c. intra a 2 iese a 4 b. intra a 1 iese u 2 d. intra a 2 , iese u 2 42. Fie problema de programare liniara: min f =x 1 + 2x 2 + x 5 ÔÏÔÔ ÔÔÔ 2x 1 + x 2 + x 3 ≥ 1 ÔÔ −x 1 + 3x 2 ≤ 0 ÌÔÔ ÔÔ ÔÔÔ ÔÓ 2x 1 + 2x 2 + x 3 + x 4 = 5 x i ≥ 0, (∀)i = 1,5 Solutia problemei este a. min f =-1/2 x 1 = 0;x 2 = 0;x 3 = 1;x 4 = 4;x 5 = 0 b. min f =0 x 1 = 0;x 2 = 0;x 3 = 1;x 4 = 4;x 5 = 0

c. d.

43. Fie urmatoarea problema de transport B1 B2 D1 D2 D3 Necesar 50 25

min f =0 x 1 = 1;x 2 = 0;x 3 = 0;x 4 = 0;x 5 = 4 min f =1/2 x 1 = 1;x 2 = 0;x 3 = 1;x 4 = 0;x 5 = 4

B3

B4

15

10

Folosind metoda coltului de NV stabiliti valoarea lui x 11 si a lui x 33 a. x 11 =50, x 32 =5 c. x 11 =50, x 33 =10 b. x 11 =20, x 32 =10 d. x 11 =50, x 32 =20

21

Disponibil 70 10 20

44. Fie urmatoarea problema de transport B1 B2 D1 5 D2 2 D3 6 Necesar 50 25

B3 6 2 8

B4 2 1 3

15

3 4 4

Disponibil 70 10 20

10

Folosind metoda costurilor minime(din tablou) stabiliti valoarea lui x 14 si a lui x 32 a. x 14 =10, x 32 =25 c. x 14 =10,x 32 =20 d. x 14 =15,x 32 =20 b. x 14 =5,x 32 =25

22

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

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

a.

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

b.

max f = 4x 1 + 10x 2 +9x 3 x 1 + x 2 + 2x 3 + y 1 = 18 2x 1 + x 2 + 4x 3 - y 2 = 20 x 1 + x 2 + x 3 - y 3 = 12 x i ≥ 0 ; i = 1,3 y 1 <0; y 2 , y 3 >0

c.

min f = 0 x 1 + x 2 + 2x 3 + y 1 = 18 2x 1 + x 2 + 4x 3 + y 2 = 20 x 1 + x 2 + x 3 + y 3 = 20 x i ≥ 0 ; i = 1,3 y1 , y 2 , y 3 ≥ 0

d.

alt raspuns

23

46. Fie urmatoarea problema de transport B1 B2 D1 5 D2 3 D3 6 Necesar 50 25

B3 6 2 8

B4 2 1 3

15

3 4 4

Disponibil 70 10 20

10

Folosind metoda costurilor minime pe linie stabiliti valoarea lui x 14 si a lui x 32 a. x 14 =10, x 32 =15 c. x 14 =10,x 32 =20 d. x 14 =15,x 32 =20 b. x 14 =5,x 32 =25 47. Fie urmatoarea problema de transport B1 B2 D1 5 D2 3 D3 6 Necesar 50 75

B3 6 2 8

B4 2 1 3

25

3 4 4

Disponibil 70 70 70

3 4 4

Disponibil 70 70 70

3 4 4

Disponibil 70 70 70

60

Folosind metoda diagonalei (coltului N-V) determinati x 34 a. 40 c. 80 b. 50 d. 60 48. Fie urmatoarea problema de transport B1 B2 D1 5 D2 3 D3 6 Necesar 50 75

B3 6 2 8

B4 2 1 3

25

60

Folosind metoda diagonalei (coltului N-V) determinati x 33 a. 40 c. 10 b. 50 d. 60 49. Fie urmatoarea problema de transport B1 B2 D1 5 D2 3 D3 6 Necesar 50 75

B3 6 2 8

2 1 3 25

Folosind metoda diagonalei (coltului N-V) determinati x 11 a. 40 c. 80 b. 50 d. 60

24

B4

60

50. Fie urmatoarea problema de transport B1 B2 D1 5 D2 3 D3 6 Necesar 50 75

B3 6 2 8

B4 2 1 3

25

3 4 4

Disponibil 70 70 70

3 4 4

Disponibil 70 70 70

3 4 4

Disponibil 70 70 70

60

Folosind metoda diagonalei (coltului N-V) determinati x 22 a. 40 c. 55 b. 50 d. 60 51. Fie urmatoarea problema de transport B1 B2 D1 5 D2 3 D3 6 Necesar 50 75

B3 6 2 8

B4 2 1 3

25

60

Folosind metoda diagonalei (coltului N-V) determinati x 12 a. 40 c. 20 b. 50 d. 60 52. Fie urmatoarea problema de transport B1 B2 D1 5 D2 3 D3 6 Necesar 50 75

B3 6 2 8

B4 2 1 3

25

60

Folosind metoda diagonalei (coltului N-V) determinati costul de transport a. 665 c. 500 b. 765 d. 400

25

53. Fie problema de programare liniara [min]f = 7x 1 + 8x 2 ÏÔÔ ÔÔ ÔÔ 2x 1 + x 2 ≥ 5 ÔÌÔ ÔÔÔ x + 2x ≥ 4 2 Ó 1

x 1 ,x 2 ≥ 0 Duala sa este a. [max]g = 5u 1 + 4u 2 ÔÏÔÔ ÔÔ 2u 1 + u 2 ≤ 7 ÌÔÔ ÔÔ u + 2u ≤ 8 ÔÓ 1 2 b.

c.

u 1 ,u 2 ≥ 0 [max]g = 5u 1 + 4u 2 ÏÔÔ ÔÔ Ô 2u 1 + u 2 = 7 ÔÌÔÔ ÔÔÓ u 1 + 2u 2 = 8

d.

u 1 ,u 2 ≥ 0

[max]g = 7u 1 + 8u 2 ÏÔÔ ÔÔ Ô 2u 1 + u 2 ≤ 5 ÌÔÔ ÔÔ u + 2u ≤ 4 ÔÓ 1 2 u 1 ,u 2 ≥ 0 [max]g = 5u 1 + 4u 2 ÏÔÔ ÔÔ Ô 2u 1 + u 2 ≥ 7 ÔÌÔÔ ÔÔÓ u 1 + 2u 2 ≤ 8 u 1 ,u 2 ≥ 0

54. Fie problema de programare liniara [min]f = 7x 1 + 8x 2 ÏÔÔ ÔÔ ÔÔ 2x 1 + x 2 ≥ 5 ÌÔÔ ÔÔÔ x + 2x ≥ 4 2 Ó 1

x 1 ,x 2 ≥ 0 Forma standard este a. [min]f = 7x 1 + 8x 2 + My 1 + My 2 ÏÔÔ ÔÔ ÔÔ 2x 1 + x 2 − y 1 = 5 ÌÔÔ ÔÔÔ x + 2x − y = 4 2 2 Ó 1 b.

c.

x 1 ,x 2 ≥ 0,y 1 ,y 2 ≥ 0 [min]f = 7x 1 + 8x 2 + 0y 1 + 0y 2 ÔÏÔÔ ÔÔ 2x + x + y = 5 Ô 1 2 1 ÌÔÔ ÔÔÔ x + 2x + y = 4 2 2 Ó 1

d.

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

[min]f = 7x 1 + 8x 2 + 0y 1 + 0y 2 ÏÔÔ ÔÔ ÔÔ 2x 1 + x 2 − y 1 = 5 ÌÔÔ ÔÔÔ x + 2x − y = 4 2 2 Ó 1 x 1 ,x 2 ≥ 0,y 1 ,y 2 ≥ 0 [min]f = 7x 1 + 8x 2 + 0y 1 + 0y 2 ÔÏÔÔ ÔÔ 2x + x − y = 5 Ô 1 2 1 ÌÔÔ ÔÔÔ x + 2x + y = 4 2 2 Ó 1 x 1 ,x 2 ≥ 0,y 1 ,y 2 ≥ 0

26

55. Fie problema de programare liniara [min]f = 7x 1 + 8x 2 ÏÔÔ ÔÔ ÔÔ 2x 1 + x 2 ≥ 5 ÔÌÔ ÔÔÔ x + 2x ≥ 4 2 Ó 1

x 1 ,x 2 ≥ 0 Matricea problemei in forma standard este ÊÁ ˆ ÁÁ 2 1 −1 0 ˜˜˜ Á ˜˜ a. ÁÁÁ ˜˜ ÁÁ ˜˜ 1 2 0 −1 Ë ¯ ÊÁ ˆ˜ ÁÁ 2 1 1 0 ˜˜ ˜˜ b. ÁÁÁÁ ˜˜ ÁÁ ˜˜ 1 2 0 1 Ë ¯

c.

d.

ÊÁ ÁÁ 2 ÁÁ ÁÁ ÁÁ Ë1 ÊÁ ÁÁ 2 ÁÁ ÁÁ ÁÁ Ë1

ˆ˜ 1 −1 ˜˜˜˜ ˜˜ ˜ 2 −1 ˜¯ ˆ˜ −1 −1 0 ˜˜˜˜ ˜˜ ˜ −2 0 −1 ˜¯

56. Fie problema de programare liniara [min]f = 7x 1 + 8x 2 ÏÔÔ ÔÔ ÔÔ 2x 1 + x 2 ≥ 5 ÌÔÔ ÔÔÔ x + 2x ≥ 4 2 Ó 1

x1,x2 ≥ 0 Matricea problemei in forma standard pentru simplex, cu baza artificiala este ÊÁ ˆ ÊÁ ˆ ÁÁ 2 1 −1 0 1 0 ˜˜˜ ÁÁ −2 1 −1 0 −1 0 ˜˜˜ Á ˜ Á ˜˜ ˜˜ a. ÁÁÁ c. ÁÁÁ ˜˜ ÁÁ ˜˜˜ ÁÁ ˜˜ 1 2 0 −1 0 1 1 2 0 −1 0 1 Ë ¯ Ë ¯ ÁÊÁ ˜ˆ˜ ÁÊÁ ˜ˆ˜ Á 2 −1 −1 0 1 0 ˜˜ Á 2 1 1 0 1 0 ˜˜ ˜˜ ˜˜ b. ÁÁÁÁ d. ÁÁÁÁ ˜ ˜ ÁÁ 1 −2 0 −1 0 1 ˜˜ ÁÁ −1 −2 0 −1 0 1 ˜˜ Ë ¯ Ë ¯ 57. Într-o problemă de programare liniară dacă prin aplicarea algoritmului simplex după un

anumit număr de intrări toate diferenŃele c j − z j , j ∈ J satisfac criteriul de optimalitate, dar baza mai conŃine variabile artificiale nenule, problema iniŃială a. nu are soluŃie optimă b. are soluŃie optimă c. are optim infinit 58. Să se determine

[max ]z = 4 x1 − x 2 + 3x3

pe mulŃimea soluŃiilor nenegative ale sistemului 4 x1 − x 2 − 6 x3 ≤ 4 .   x1 − x 2 + 5 x3 ≤ 3 a.

z opt =

88 11

b.

z opt =

88 13

c.

27

z opt =

70 13

d.

z opt =

70 11

59. Să se determine programul optim pentru problema de programare liniară

4 x1 − x 2 − 6 x3 ≤ 4   x1 − x 2 + 5 x3 ≤ 3 .  x ≥ 0, i = 1,2,3  i [max]z = 4 x1 − x 2 + 3x3 19 3 7 x2 = 3 4 x3 = 13 x1 = a.

b.

19 x1 = 3 x2 = 0 x3 =

c.

4 13

4 x1 = 3 x2 = 0 x3 =

4 3 7 x2 = 3 19 x3 = 3 x1 =

d.

19 3

60. Problema de programare liniară

[max]z = x1 + 2 x2 + 2 x3 + x 4 1   x1 − x 2 + 2 x 4 = 1   x 2 + x3 − x 4 = 1  x ≥ 0, i = 1,2,3,4  i 

a.

are soluŃie optimă z opt = 3

b. c. d.

nu are optim finit nu are soluŃie altă variantă

61. O soluŃie a problemei de programare liniară

[max]z = 5 x1 + 3x2 + 2 x3  x1 + 2 x 2 + 3x3 ≤ 2 3 x + 2 x + x ≤ 1  1 2 3  2 x1 + x 2 ≤ 3  xi ≥ 0, i = 1,2,3

este

a.

1 x1 = 8 x2 = 0 x3 =

5 8

b.

x3 =

1 8 3 x2 = 8 x3 = 0

x1 = −

x1 =

1 x1 = − 8 x2 = 0

c.

4 8

28

d.

3 8 4 x3 = 8 x2 =

1 8

62. Duala problemei de programare liniară

[max]z = 5 x1 + 3x2 + 2 x3  x1 + 2 x 2 + 3x3 ≤ 2 3 x + 2 x + x ≤ 1  1 2 3  2 x1 + x 2 ≤ 3  xi ≥ 0, i = 1,2,3

este

a.

b.

c.

[min ]z = 2 y1 + y 2 + 3 y3  y1 + 3 y 2 + 2 y 3 ≤ 5 2 y + 2 y + y ≥ 1  1 2 3  3 y1 + y 2 ≤ 3  y i ≥ 0, i = 1,2,3 [max]z = 2 y1 + y 2 + 3 y3  y1 + 3 y 2 + 2 y 3 ≥ 5 2 y + 2 y + y ≥ 3  1 2 3  3 y + y ≥ 2 2  1  y i ≥ 0, i = 1,2,3 [min ]z = 2 y1 + y 2 + 3 y3  y1 + 3 y 2 + 2 y 3 ≥ 5 2 y + 2 y + y ≤ 3  1 2 3  + ≥ 3 y y 2 2  1  y i ≥ 0, i = 1,2,3

63. Fie problema de programare liniară

− x1 + x 2 + x3 = 1 x − x + x = 1  1 2 4  x + x + x 2 5 = 2  1  xi ≥ 0, 1 ≤ i ≤ 5 [max]z = 2 x1 − x 2 + 3x3 − 2 x4 + x5 Dacă tabloul simplex pentru prima iterată este 2 -1 3 -2 B a3 cB xB a1 a2 a4

1 a5

3

a3

1

-1

1

1

0

0

-2 1

a4 a5

1 2

1 1

-1 1

0 0

1 0

0 2

Să se indice vectorul care intră în bază şi vectorul care pleacă din bază. a. intră vectorul a 2 în locul vectorului a 5 b. c. d.

intră vectorul a 2 în locul vectorului a 4 intră vectorul a1 în locul vectorului a 4 intră vectorul a1 în locul vectorului a 3

29

64. Să se aducă la forma standard următoarea problemă de programare liniară

 x1 − x 2 = 5 x − 2x ≥ 1  2 3  2 x1 − 3x 2 + 2 x3 ≥ −4  xi ≥ 0, i = 1,2,3 [max]z = 3x1 − x2 + 4 x3

a.

b.

c.

d.

 x1 − x 2 = 5 x − 2x + x = 1  2 3 4  2 x1 − 3x 2 + 2 x3 − x5 = −4  xi ≥ 0, i = 1,2,3,4,5 [max]z = 3x1 − x2 + 4 x3  x1 − x 2 + x 4 = 5 x − 2x − x = 1  2 3 5  2 x1 − 3x 2 + 2 x3 + x6 = 4  xi ≥ 0, i = 1,2,3,4,5,6 [max]z = 3x1 − x2 + 4 x3  x1 − x 2 = 5 x − 2x − x = 1  2 3 4  − 2 x1 + 3x 2 − 2 x3 + x5 = 4  xi ≥ 0, i = 1,2,3,4,5 [max]z = 3x1 − x2 + 4 x3  x1 − x 2 = 5 x − 2x + x = 1  2 3 4  − 2 x1 − 3 x 2 − 2 x3 − x5 = 4  xi ≥ 0, i = 1,2,3,4,5 [max]z = 3x1 − x2 + 4 x3

30

65. Să se aducă la forma standard programul liniar:

[ max ] f=6x1 + 10x2  x1 − x2 ≤ 1  −2 x1 + x2 ≤ 2 x , x ≥ 0  1 2

a.

[ max ] f=6x1 + 10 x2 + 0 ⋅ x3 + 0 ⋅ x4

b.

 x1 − x2 + x3 = 1  −2 x1 + x2 + x4 = 2   xi ≥ 0, i = 1, 4 [ max ] f=6x1 + 10 x2 + 0 ⋅ x3 + 0 ⋅ x4

c.

[ max ] f=6x1 + 10x2

d.

 x1 − x2 = 1  −2 x1 + x2 = 2   xi ≥ 0, i = 1, 2 [ max ] f=6x1 + 10x2  − x1 + x2   2 x1 − x2

 x1 − x2 − x3 = 1  −2 x1 + x2 − x4 = 2   xi ≥ 0, i = 1, 4

≥ −1 ≥ −2

66. Să se scrie matricea sistemului de restricŃii ataşată programului liniar:

[ min ] f=3x1 + 2x2

 2x1 + x2 + x3 = 10  − x1 + 2 x2 + x4 = 20  xi ≥ 0, i = 1, 4  a. b.

 2 A=  −1  2 A=  −1

1 1 2 1 1 1 0 2 0 1

c. d.

31

 2 A=  −1  2 A=  −2

1 1 10  2 1 20 1 1 1 10   2 0 1 20 

67. Să se aducă la forma standard programul liniar :

[ max ] f

= 2 x1 − x2 + 3x3

 x1 + x2 + 2 x3 ≤ 8 2 x + x + x ≤ 12  1 2 3  x + 3x + x ≤ 7 2 3  1  x ≥ 0, i = 1,3  i a. [ max ] f = 2 x1 − x2 + 3x3

c.

 x1 + x2 + 2 x3 = 8 2 x + x + x = 12  1 2 3  x + 3x + x = 7 2 3  1  x ≥ 0, i = 1,3  i

b.

[ max ] f

[ max ] f

= 2 x1 − x2 + 3x3 + 0 ⋅ x4 + 0 ⋅ x5 + 0 ⋅ x6

=8  x1 + x2 + 2 x3 +x 4 2 x + x + x + x = 12 5  1 2 3  x + 3x + x + x6 = 7 2 3  1  x ≥ 0, i = 1, 6  i

= 2 x1 − x2 + 3x3

d.

 x1 + x2 + 2 x3 ≥ 8 2 x + x + x ≥ 12  1 2 3  x + 3x + x ≥ 7 2 3  1  x ≥ 0, i = 1,3  i

[ max ] f

= 2 x1 − x2 + 3x3 + 0 ⋅ x4 + 0 ⋅ x5 + 0 ⋅ x6

=8  x1 + x2 + 2 x3 − x 4 2 x + x + x − x = 12 5  1 2 3  x + 3x + x − x6 = 7 2 3  1  x ≥ 0, i = 1, 6  i

68. Fie programul (S) :

 x1 + 2 x2 − x3 =8  − x4 = 10 2 x1 + x2   xi ≥ 0 i=1,4 Atunci : a.

Vectorul X 1 = ( 5,1, −1,1) este o soluŃie posibilă deoarece verifică ecuaŃiile sistemului

b.

(S); Vectorul X 2 = ( 5, 0, −3, 0 ) este o soluŃie de bază degenerate;

c. d.

Sistemul (S) nu admite soluŃii de bază nedegenerate; Vectorul X 1 = ( 5,1, −1,1) este o soluŃie de bază nedegenerată, iar vectorul

X 2 = ( 5, 0, −3, 0 ) este o soluŃie posibilă.

32

69. Să se scrie tabloul simplex ataşat problemei de programare liniară la iteraŃia iniŃială :

[ max ] f=3x1 − 2 x2 + x3 + 2 x4 + 0 ⋅ x5

=6  2x1 + x2 − x = 10  1 − 2 x3 + x4 3x + x3 + x5 = 8  1  x ≥ 0 i=1,5  i a)

B

CB

XB

3

-2

1

2

1

a1

a2

a3

a4

a5

-2

a2

6

2

1

0

0

0

2

a4

10

-1

0

-2

1

0

8 8

3 -6

0 -2

1 -4

0 2

0

-9

0

-5

0

-1

3

-2

1

2

1

a1

a2

a3

a4

a5

a5 0

fj f j − cj

1

b)

B

CB

XB

-2

a2

6

2

1

0

0

0

2

a4

10

-1

0

-2

1

0

8 8

3 -6

0 -2

1 -4

0 2

1 0

9

0

5

0

1

3

-2

1

2

1

a1

a2

a3

a4

a5

a5 0

fj cj − f j c)

B

CB

XB

3

a1

6

2

1

0

0

0

-2

a2

10

-1

0

-2

1

0

8 -6

3 11

0 3

1 5

0 -2

1 1

8

5

4

-4

0

a3 1

fj f j − cj d)

33

B

CB

XB

3

-2

1

2

0

a1

a2

a3

a4

a5

3

a1

6

2

1

0

0

0

1

a3

10

-1

0

-2

1

0

8 28

3 5

0 3

1 -2

0 1

1 0

2

5

-3

-1

0

a5 0

fj f j − cj

a. b. c. d.

a b c d

34

70. Să se scrie tabloul simplex ataşat programului liniar la iteraŃia iniŃială :

[ max ] f

= 5 x1 + 4 x2 + 3x3

 x1 + 2 x2 + 2 x3 ≤ 10 2 x + x ≤8  1 2  2 x2 − x3 ≤ 8   x1 , x2 , x3 ≥ 0 a)

B

CB

XB

5

4

3

0

0

0

a1

a2

a3

a4

a5

a6

10

a1

5

1

2

2

1

0

0

8

a2

4

2

1

0

0

1

0

3 116

0 26

2 44

-1 12

0 10

0 8

1 8

-21

-40

-9

-10

-8

-8

10

8

8

0

0

0

a1

a2

a3

a4

a5

a6

a3 8

fj cj − f j b)

B

CB

XB

5

a4

10

1

2

2

1

0

0

4

a5

8

2

1

0

0

1

0

8 116

0 13

2 20

-1 7

0 5

0 4

1 3

-3

-12

1

-5

-4

-3

a6 3

fj cj − f j c)

B

CB

XB

5

4

3

0

0

0

a1

a2

a3

a4

a5

a6

0

a4

10

1

2

2

1

0

0

0

a5

8

2

1

0

0

1

0

8 0

0 0

2 0

-1 0

0 0

0 0

1 0

5

4

3

0

0

0

a6 0

fj cj − f j d)

35

B

CB

XB

5

4

3

0

0

0

a1

a2

a3

a4

a5

a6

0

a4

10

1

2

2

1

0

0

0

a5

8

2

1

0

0

1

0

8 0

0 0

2 0

-1 0

0 0

0 0

1 0

-5

-4

-3

0

0

0

a6 0

fj f j − cj a. b. c. d.

a b c d

71. Să se aplice criteriul de optimalitate programului liniar de maxim care are tabloul simplex la iteraŃia k :

B

CB 3

a3

5

a1

XB 3

4

5

4

3

0

0

0

a1

a2

a3

a4

a5

a6

0

3 4 1 2 11 4

1

1 2

−

1 4 1 2 1 − 4

0

1

0

0

0 0

1 2

a6 fj cj − f j

11 29

0 5

0

19 4

3

3 4

0

−

3 2 −

3 2

0

1

7 4 −

7 4

0

0

a.

SoluŃia X = ( 3, 4,11, 0, 0, 0 ) este optimă, algoritmul ia sfârşit;

b.

SoluŃia X = ( 0, 0,3, 4,11, 0 ) nu este optimă, deoarece nu toate diferenŃele sunt pozitive;

c.

SoluŃia X = ( 4, 0,3, 0, 0,11) este optimă , algoritmul ia sfârşit;

d.

Problema nu are optim finit, deoarece nu există diferenŃe ∆ j = c j − f f > 0 .

t t

t

36

72. Să se aplice criteriul de intrare în baza pentru programul liniar de maxim , care are tabloul simplex ataşat :

B

CB

XB

3

1

-1

2

0

1

a1

a2

a3

a4

a5

a6

0

a5

8

2

1

1

0

1

0

1

a6

13

-1

2

-2

0

0

1

5 23

3 5

-1 0

1 0

1 2

0 0

0 1

-2

1

-1

0

0

0

a4 2

fj cj − f j a.

Vectorul a2 intră în bază, întrucât corespunde unei valori f 2 = 0 , iar a2 nu apare în

b.

baza B ; Vectorul a3 intra în bază, întrucât corespunde celei mai mare diferenŃe negative

∆ 3 = c3 − f 3 ; c.

În bază intră vectorul a5 , întrucât ∆ 5 = c5 − f5 este singura diferenŃă nulă

d.

corespunzatoare unui vector aflat în baza B ; Vectorul a1 intra în bază întrucât corespunde celei mai mari valori f j .

73. Să se aplice criteriul de ieşire din bază pentru programul liniar căruia îi corespunde tabelul simplex de mai jos :

B

CB

XB

6

10

7

0

0

0

a1

a2

a3

a4

a5

a6

θ

0

a4

200

1

1

2

1

0

0

200

0

a5

600

2

1

0

0

1

0

600

800 0

0 0

2 0

-1 0

0 0

0 0

1 0

400

6

10∗

7

0

0

0

a6 0

fj cj − f j a.

Iese din baza vectorul a4 , întrucât îi corespunde cel mai mic raport θ =200;

b.

Iese din baza vectorul a5 , întrucât îi corespunde cel mai mare raport θ =600;

c.

Iese din baza vectorul a6 , întrucât, valoarea x5 = 800 este cea mai mare valoare din

d.

vectorul X B ; Toate afirmaŃiile de mai sus sunt false.

37

74. Să se scrie prima iteraŃie din tabloul simplex ataşat problemei de programare liniară extinsă :

[ max ] f

= 20 x1 + 10 x2 + 30 x3 + 20 x4

specificând şi o soluŃie iniŃială de bază X B . a) X Bt = (1000,800,500, 0, 0, 0, 0 )

B

CB

XB

θ

20

0

0

0

a2

30↓ a3

a4

a5

a6

a7

20

10

a1 0

a1

1000

1

2

1

1

1

0

0

1000

0

a2

800

0

1

1

1

0

1

0

800

500 0

1 0

0

1

0 0

500

0

0 0

1

0

0 0

20

10

30∗

20

0

0

0

a3 0

fj cj − f j

b) X Bt = ( 0, 0, 0, 0,1000,800,500 )

B

CB

XB

θ

20

10

30

20

0

0

0

a1

a2

a3

a4

a5

a6

a7

0

a5

1000

1

2

1

1

1

0

0

1000

0

a6

800

0

1

1

1

0

1

0

800

500 0

1 0

0 0

1 0

0 0

0 0

0 0

1

500

20

10

30∗

20

0

0

0

a7 0

fj cj − f j

c) X Bt = ( 0, 0, 0, 0,1000,800,500 )

B

CB

XB

θ

20

10

30

20

0

0

0

a1

a2

a3

a4

a5

a6

a7

0

a5

1000

1

2

1

1

1

0

0

1000

0

a6

800

0

1

1

1

0

1

0

800

500 0

1 0

0 0

1 0

0 0

0 0

0 0

1

500

-20

-10

-30

-20

0

0

0

a7 0

fj f j − cj

d) Altă variantă. a. b. c. d.

a b c d

38

75. Să se scrie a doua iteraŃie a tabloului simplex de mai jos ataşat unei probleme de programare liniară (pentru maxim) :

B

CB

0

a4

0 0

a5

2

1

-3

0

0

0

a1

a2

a3

a4

a5

a6

6

1

1

2

1

0

0

10

2

1

3

0

1

0

7

1

1

1

0

0

1

0

0

0

0

0

0

0

2∗

1

-3

0

0

0

XB

θ 6 1 10 2 7 1

a6 fj cj − f j a)

B

CB

a4

0 2

a1

0

XB

2

1

-3

0

0

0

a1

a2

a3

a4

a5

a6

1 2 1 2 1 2

1 2 3 2 1 − 2

1

−

1 2 1 2 1 − 2

1

0

5

1

2

0

10

2

1

3

0

1

0

0

0

-6

0

-1

0

0 0

0 0 1

a6 fj cj − f j b)

B

CB

XB

2

1

-3

0

0

0

a1

a2

a3

a4

a5

a6

0

a4

2

0

1

1

2

-1

0

2

a1

5

1

1 2

3 2

0

1 2

0

1

-1

a6 0

fj cj − f j

4 10

0 5

1

-3

0

-1

3

0 0

1

2 0

-6

0

-1

0

c)altă variantă; d)

39

θ

θ

B

CB

0

a4

1

a2

0

XB

2

1

-3

0

0

0

a1

a2

a3

a4

a5

a6

1 2 1 2 1 2

1 2 3 2 1 − 2

1

0

5

1

2

0

a6 5

fj cj − f j

a. b. c. d.

1 1

1 2 1 2

3 2 9 − 2

1 2 1 2 1 − 2

−

1 0 0

0

0

0

1 0

1 2 1 − 2

0

θ

0

a b c d

76. Să se continue algoritmul simplex pentru programul liniar cu maxim f obiectiv al cărui tabel la iteraŃia k , este dat mai jos :

[ max ] f B

CB

0

a4

4

a1

0

= 4 x1 + x2 − 2 x3 XB

4

1

-2

0

0

0

a1

a2

a3

a4

a5

a6

3 2 1 2 1 2

−

1

−

cj − f j a. b.

1 2 1 2 1 − 2

0

10

1

7

0

40

4

2

6

0

2

0

0

-1

-8

0

-2

0

a6 fj

3 2 3 2 1 − 2

8

0 0

θ

0 0 1

Intră în bază vectorul a2 şi iese a4 ; problema nu admite un optim finit;

c.

f opt = 40 pentru X = (10, 0, 0 ) .SoluŃia este degenerată;

d.

f opt = 40 pentru X = (10, 0, 0 ) .SoluŃia este nedegenerată.

t t

40

77. Să se scrie dualul programului liniar :

[ min ] f

= 8 x1 + 10 x2

 2x1 + x2 ≥ 3   3x1 + 4 x2 ≥ 7  x ≥ 0, x ≥ 0 2  1 a.

[ max ] g = 8 y1 + 10 y2

b.

 2y1 + 3 y2 ≤ 3   y1 + 4 y2 ≤ 7  y ≥ 0, y ≥ 0 2  1 [ max ] g = 3 y1 + 7 y2  2 y1 + 3 y 2 ≤ 8   y1 + 4 y 2 ≤ 1 0  y ≥ 0, y ≥ 0 1 2 

c.

Altă variantă ;

d.

[ max ] g=3y1 + 7 y2  2 y1 + y 2 ≤ 8   3 y1 + 4 y 2 ≤ 7  y ≥ 0, y ≥ 0 1 2 

41

78. Se dă tabloul simplex ataşat dual unui program liniar de maxim la iteraŃia k are următorul tabel :

B

CB

8

a2

6

a1

YB

3 4 2 3

10

gj cj − g j

6

8

0

0

a1

a2

a3

a4

0

1

1

1

0

2

6

8

20

3

0

0

-20

-3

−

3 2 5 2

Să se completeze tabloul simplex la iteraŃia următoare şi să se scrie soluŃiile problemelor primară şi duală. a)

B

CB

0

a3

6

a1

YB

3 4 5 6

5

gj cj − g j

3 5 Y = ,  4 6 a.

t

6

8

0

0

a1

a2

a3

a4

0

1

1

-1

2

0

-6

12

0

-33

12

-4

0

33

X= ( 0, 33)

3 2 11 − 2 −

t

a

3 2 b. Algoritmul ia sfârşit. SoluŃia optimă a dualei este g opt = 10 pentru Y =  ,  4 3 soluŃia optimă a primalei este f opt = 10 pentru X= ( 3,20 ) ;

t

iar,

c.

Algoritmul ia sfârşit. Problema duală nu are un optim finit, întrucât, toŃi ∆ j = c j − g j

d.

sunt negative sau zero; Algoritmul ia sfârşit. SoluŃia optimă a dualei este g opt = 10 pentru

2 3 Y = ,  3 4

t

,iar,soluŃia optimă a primalei este f opt = 10 pentru X= ( 20, 3) . t

42

79. Să se scrie forma standard a dualului problemei de programare liniară:

[ max ] f

= 20 x1 + 10 x2 + 30 x3 + 20 x4

 x1 + 2 x2 + x3 + x4 ≤ 1000  x2 + x3 + x4 ≤ 800  x + x3 ≤ 500  1

xi ≥ 0

(i = 1, 4 )

a.

[ min ] g = 1000 y1 + 800 y2 + 500 y3

b.

y3 ≥ 20  y1 + 2 y + y ≤ 10  1 2 yi ≥ 0 i = 1, 3   y1 + y2 + y3 ≥ 30  y1 + y2 ≥ 20 [ min ] g = 1000 y1 + 800 y2 + 500 y3 + 0 ( y5 + y6 + y7 )

c.

y3 + y4 = 20  y1 + 2 y + y + y5 = 10  1 2 yi ≥ 0 i = 1, 7  + y6 = 30  y1 + y2 + y3  y1 + y2 + y7 = 20 [ min ] g = 1000 y1 + 800 y2 + 500 y3 + 0 ( y4 + y5 + y6 ) + M ( u1 + u2 + u3 + u4 )

(

(

= 20  y1 + y3 − y4 + Mu1 2 y + y − y5 + Mu 2 = 10  1 2  − y6 + Mu3 = 30  y1 + y2 + y3  y1 + y2 − y7 + Mu4 = 20 d.

altă variantă

43

yi ≥ 0 uj ≥ 0

)

)

( i = 1, 7 ) ( j = 1, 4 )

80. Se consideră dualul unui program liniar de maxim şi tabloul simplex ataşat la iteraŃia k . Atunci:

B

CB

5

4

2

0

0

a1

a2

a3

a4

a5

1 5 1 − 5

−

3 5 3 − 5

7 10 7 − 10

XB

1 5

a1 a3

2

fj

1 0

19

43

cj − f j

5 0

3 10 11 15 59 10 19 − 10

0

1

2 0

1 10 3 5

a.

Algoritmul continuă până când toŃi ∆ j = c j − f j ≥ 0 ∀j = 1,5

b.

Algoritmul se opreşte. SoluŃia optimă a primalei este: f max = 43 X t = (1,19, 0, 0, 0 ) ,

c.

Algoritmul se opreşte. SoluŃia optimă a dualei este:

7 19   3 Y t =  − , − , 0, − , 0  g min = 43 5   5 10 d.

Algoritmul se opreşte. SoluŃia optimă a primalei este:

X t = (1, 0,19, 0, 0 )

f max = 43

81. Să se rezolve problema de programare liniară

[ max ] f

= 50 x1 + 25 x2

 x1 + x2 ≤ 3   x1 + 2 x2 ≤ 5 x , x  1 2 ≥0 a.

x1 = 50, x2 = 0, f max = 2500

b.

x1 = 30, x 2 = 50, f max = 2750

c. d.

x1 = 10, x2 = 20, f max = 1000 alt răspuns

44

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

[ min ] f

= 6 x1 + 10 x2

 x1 + 2 x2 ≥ 1  2 x1 + x2 ≥ 3 a.

[ max ] g = y1 + 3 y2

c.

[ max ] g = y1 + 3 y2

 y1 + 2 y2 ≤ 6  2 y1 + y2 ≤ 10 y , y ≥ 0  1 2 y1 = 3 b.

 y1 + 2 y2 ≤ 6  2 y1 + y2 ≤ 10 y1 = 0 y2 = 3 g max = 9

y2 = 0

g max = 18

[ max ] g = 6 y1 + 10 y2  y1 + 2 y2 ≤ 1  2 y1 + y2 ≤ 3 y1 = 3 y2 = 2

d.

[ max ] g = y1 + 3 y2  y1 + 2 y2 ≤ 6  2 y1 + y2 ≤ 10 y1 = 5 y2 = 0

g max = 38

83. Fie problema de transport

A1

A2 A3

B3

B2

B1

2

1

3

5

3

1

2

4

3

7 8 5

6 7 7 Utilizând metoda diagonalei o soluŃie este a. x11 = 6 ; x12 = 1 ; x 22 = 2 ; x 23 = 6 ; x32 = 5 b.

x11 = 6 ; x 21 = 1 ; x 22 = 2 ; x32 = 7

c.

x11 = 6 ; x12 = 1 ; x 22 = 6 ; x 23 = 2 ; x33 = 5

d.

x11 = 6 ; x12 = 1 ; x 22 = 4 ; x 23 = 2 ; x33 = 7

84. Fie problema de transport

B1 A1 A2 A3

B3

B2 2

1

3

5

3

1

2

4

3

7 8 5

6 7 7 Utilizând metoda costurilor minime o soluŃie este a. x12 = 7 ; x 21 = 1 ; x 22 = 7 ; x 31 = 5 b.

x11 = 6 ; x12 = 1 ; x 23 = 7 ; x 31 = 5

c.

x12 = 7 ; x 22 = 1; x 23 = 5 ; x31 = 7

d.

x12 = 7 ; x 21 = 1 ; x32 = 7 ; x33 = 5 45

g max = 5

85. Fie problema de transport

B1 A1 A2 A3

B3

B2

B4

1

2

2

3

2

2

1

4

3

2

2

1

70 10 20

50 25 15 10 Urilizând metoda diagonalei o soluŃie de bază este f = 120 f = 145 a. b. f = 125 c.

d.

f = 135

d.

f = 135

86. Fie problema de transport

A1

A2 A3

B3

B2

B1

B4

1

2

2

3

2

2

1

4

3

2

2

1

70 10 20

50 25 15 10 Urilizând metoda diagonalei o soluŃie de bază este f = 110 f = 130 a. b. f = 125 c. 87. Fie problema de transport cu o tabelă iniŃială

A1

1 50

A2 A3

B3

B2

B1

B4

2

2

3

2

1

4

20 2

5 3

2

5 2

10

1 10

50 25 15 10 Să se justifice că f = 135 nu este soluŃie optimă. a. toŃi δ ij ≥ 0 b.

toŃi δ ij < 0

c.

o singură valoare δ ij < 0

46

70 10 20

88. Pentru soluŃia problema de transport

A1

B3

B2

B1

1 50

2

B4 2

3

20 2

A2

2

1

4

5 3

A3

5

2

2

1

10

10

50 25 15 dacă δ 32 < 0 o soluŃie îmbunătăŃită este f = 110 a. b. f = 130

70 10 20

10 f = 125

d.

f = 115

15 30 15 Utilizând metoda diagonalei o soluŃie de bază este f = 150 f = 165 a. b. f = 160 c.

d.

f = 155

d.

f = 140

d.

f = 95

c.

89. Fie problema de transport

A1

A2 A3

B3

B2

B1

2

3

1

4

1

2

3

2

5

10 20 30

90. Fie problema de transport

A1

A2 A3

B3

B2

B1

2

3

1

4

1

2

3

2

5

10 20 30

15 30 15 Utilizând metoda costurilor minime o soluŃie de bază este f = 115 f = 120 a. b. f = 110 c. 91. Pentru soluŃia problema de transport

2

A1

3

1

10

10 4

A2 A3

B3

B2

B1

1

2

20

20 3 15

2 10

5

30

5

15 30 15 dacă δ 23 < 0 , o soluŃie îmbunătăŃită este f = 110 a. b. f = 115

47

c.

f = 90

92. Fie problema de transport cu o tabelă iniŃială

2

A1

3

1

10

10 4

A2 A3

B3

B2

B1

1

2

2

5

20

20 3 15

10

30

5

15 30 15 Să se justifice că f = 110 este soluŃie optimă. a. toŃi δ ij ≤ 0 b.

un δ ij < 0 şi restul pozitivi

c.

toŃi δ ij > 0

93. Fie problema de transport. O soluŃie iniŃială a problemei este: Centre de consum Depozite

B1

B2

B3

B4

Disponibil

A1

10

0

20

11

15

A2

12

7

9

20

25

A3

0

14

16

18

5

Necesar

5

15

15

10

a b

Atunci: a. b. c. d.

Problema este echilibrată a = 35 , b = 45 Problema este neechilibrată a = 45 , b = 45 Problema este echilibrată , a = b = 45 Altă variantă

48

94. Fie problema de transport

Disponibil

B1 B2

B3

A1

10

1

15

30

A2

12

5

7

40

Necesar

20

15

40

Notăm: m-numărul centrelor de consum n-numărul depozitelor m

n

a = ∑ ai

b = ∑ bj

,

i =1

j =1

Atunci: a. b. c. d.

m = 3 , n = 2 , a = 70 , b = 75 m = 2 , n = 3 , a = 75 , b = 70 m = 2 , n = 3 , a = 70 , b = 75 altă variantă

95. Aplicând metoda costului minim din tabel să se determine o soluŃie iniŃială de bază pentru programul de transport având tabloul alăturat.

B1 10

A1 x11

25 15

x12 6

A2 x21

Necesar

Disponibil

B2

20

15 25

x22 20

a.

x11 = 0 , x12 = 15 ,x 21 = 20 , x 22 = 5 , f = 570

b.

x11 = 15 , x12 = 0 , x 21 = 5 , x 22 = 20 , f = 480

c. d.

x11 = 0 , x12 = 20 , x 21 = 15 , x 22 = 5 , f = 465 altă variantă

49

96. Folosind metoda costului minim să se determine o soluŃie iniŃială de bază a problemei de transport:

B1

B2 10

A1 x11

0

x12

x21

x22

x32

15

7

9 25

x23

14

A3

20

x13

12

A2

Disponibil

B3

16

x33

18 5

x34

Necesar 5

a.

 x11 = 15   x21 = 0 x = 0  31

15

x12 = 0

x13 = 0

x 22 = 15

x 23 = 10

x 32 = 0

x 33 = 5

10

c.

altă variantă

d.

 x11 = 0   x21 = 0 x = 5  31

f 0 = 435 b.

 x11 = 0   x21 = 0 x = 5  31

x12 = 15

x13 = 0

x 22 = 15

x 23 = 10

x 32 = 0

x 33 = 5

f 0 = 355

x12 = 15

x13 = 0

x 22 = 0

x 23 = 15

x 32 = 0

x 33 = 0

f 0 = 405

97. Să se scrie soluŃia de bază f 0 pentru problema de transport după aplicarea metodei costului minim din tabel: 15 10

0 25

20 15

13 5

17 0 a.

f 0 =238

b.

f 0 = 410

c.

f 0 = 800

d.

f 0 = 1225

12 0 40 3

18 30

5 10

50

98. Folosind metoda costului minim pe linie să se determine o soluŃie iniŃială de bază a problemei de transport a cărui tablou este:

B1

B2 15

A1

35

x11

0

x21

a.

b.

15

x22

30

30

x23

35

x12 = 15  x11 = 0   x21 = 30 x 22 = 20 f 0 = 1095  x11 = 0   x21 = 15

50

x13

15

Necesar

0

x12

A2

Disponibil

B3

15

x13 = 35 x 23 = 0

x12 = 35

x13 = 15

x 22 = 0

x 23 = 15

f 0 = 1675 c.

altă variantă

d.

 x11 = 30   x21 = 0

x12 = 0

x13 = 20

x 22 = 35

x 23 = 0

f 0 = 450 99. Folosind metoda costului minin pe linie să se scrie o soluŃie iniŃială de bază pentru problema de transport:

B1

B2 50

A1

x11

10

x12 30

A2

x21 x31

40 100

x13 20

x22 0

A3

Disponibil

B3

50 100

x23 40

x32

10 50

x33

Necesar 80

70

100

a. b.

Problema de transport nu admite o soluŃie iniŃială de bază Altă variantă

x12 = 0

x13 = 0

c.

 x11 = 30  X :  x21 = 30 x = 0  31

x 22 = 10

x 23 = 50

x 32 = 30

x 33 = 0

 x11 = 0  X :  x21 = 10  x = 30  31

x12 = 30

x13 = 0

x 22 = 30

x 23 = 50

x 32 = 0

x 33 = 0

d.

51

100. Aplicând metoda colŃului N-V să se determine o soluŃie iniŃială de bază a problemei de transport : a. b.

c.

d.

Toate variantele sunt false

 x11 = 20  X :  x21 = 50  x = 10  31  x11 = 80  X :  x21 = 0 x = 0  31  x11 = 0  X :  x21 = 0  x = 80  31

x12 = 20

x13 = 0

x 22 = 30

x 23 = 20

x 32 = 40

x 33 = 80

x12 = 20

x13 = 0

x 22 = 50

x 23 = 50

x 32 = 0

x 33 = 50

x12 = 80

x13 = 20

x 22 = 50

x 23 = 50

x 32 = 0

x 33 = 20

f 0 = 5900

f 0 = 8200

f 0 = 5300

101. După aplicarea metodei costurilor minime, o problemă de transport are tabloul de mai jos şi soluŃia iniŃială de bază corespunzătoare f 0

B1 A1 A2

B2 7

0

B3 1

30 9

10

3 0

2 30

4 50

3 8 12 30 0 0 Verificarea optimalităŃii presupune evaluarea unor cicluri δ i j = ci j − xi j asociate celulelor libere

A3

şi ale căror moduri corespund componentelor bazice. Să se precizeze câte cicluri δ i j se pot determina şi să se evalueze δ11 a.

3 cicluri ; δ11 =2

b.

4 cicluri : δ11 =-2

c.

4 cicluri ; δ11 =2

d.

4 cicluri ; δ11 = -1

102. Fie trei soluŃii iniŃiale de baza x10 , x02 , x03 corespunzătoare funcŃiilor de eficienŃă

f 01 = 1200 , f 02 = 800 , f 03 = 1000 Care dintre aceste soluŃii consideraŃi că trebuie aleasă drept soluŃie iniŃială de bază? a.

x02 ,deoarece f 02 are cea mai mică valoare

b.

x01 ,deoarece f 01 are cea mai mare valoare

c. d.

x03 ,deoarece f 03 este o valoare medie Toate variantele sunt corecte

52

tehnici de optimizare logice TRUE/FALSE 1. Fie problema de programare liniara: max f = 10x 1 + 16x 2 ÏÔÔ ÔÔ 2x 1 + 5x 2 ≤ 1200 ÔÔÔ Ô ÌÔÔ x 1 + 1,5x 2 ≤ 300 ÔÔ ÔÔÔ ÔÓ 4x 1 + x 2 ≤ 600 x 1 ,x 2 ≥ 0 Prima iteratie a algoritmului simplex este: 10 CB XB a1 B a3 0 1200 2 a4 0 300 1 a5 0 600 4 fj 0

F

∆j =cj −f j

10

16 a2 5 3/2 1 0

0 a3 1 0 0 0

0 a4 0 1 0 0

0 a5 0 0 1 0

16

0

0

0

Solutia gasita este cea optima.

F

2. Trei depozite D 1 ,D 2 ,D 3 aprovizioneaza cu produse de larg consum 4 magazine B 1 ,B 2 ,B 3 ,B 4 astfel: B1 B2 B3 B4 Disponibil D1 3 2 1 2 30 D2 4 3 3 2 20 D3 2 1 4 5 40 Necesar 10 15 15 40 Problema este echilibrata.

F

3. Forma standard a problemei de programare liniara [min]f = 3x 1 + 5x 2 ÏÔÔ ÔÔ ÔÔ x 1 − 2x 2 ≤ 3 ÌÔÔ ÔÔÔ 2x + 5x ≥ 9 2 Ó 1

x 1 ,x 2 ≥ 0 este [max]f = 3x 1 + 5x 2 ÏÔÔ ÔÔ ÔÔ x 1 − 2x 2 ≤ 3 ÌÔÔ ÔÔÔ 2x + 5x ≥ 9 2 Ó 1 x 1 ,x 2 ≥ 0

1

F

4. Forma standard a problemei de programare liniara [min]f = 3x 1 + 5x 2 ÏÔÔ ÔÔ ÔÔ x 1 − 2x 2 ≤ 3 ÌÔÔ ÔÔÔ 2x + 5x ≥ 9 2 Ó 1

x 1 ,x 2 ≥ 0 este [min]f = 3x 1 + 5x 2 ÏÔÔ ÔÔ ÔÔ x 1 − 2x 2 = 3 ÔÌÔ ÔÔÔ 2x + 5x = 9 2 Ó 1 x 1 ,x 2 ≥ 0

F

5. Forma standard a problemei de programare liniara [max]f = 5x 1 + 4x 2 ÏÔÔ ÔÔ ÔÔ x 1 + 2x 2 ≤ 3 ÔÌÔ ÔÔ 3x − 4x ≥ 9 ÔÓ 1 2

x 1 ,x 2 ≥ 0 este [max]f = 5x 1 + 4x 2 − My 1 − My 2 ÔÏÔÔ ÔÔ x + 2x + y = 3 Ô 1 2 1 ÌÔÔ ÔÔÔ 3x 1 − 4x 2 − y 2 = 9 Ó x 1 ,x 2 ≥ 0,y 1 ,y 2 ≥ 0

T

6. Forma standard a problemei de programare liniara [max]f = 5x 1 + 4x 2 ÏÔÔ ÔÔ ÔÔ x 1 + 2x 2 ≤ 3 ÌÔÔ ÔÔÔ 3x − 4x ≥ 9 2 Ó 1

x 1 ,x 2 ≥ 0 este [max]f = 5x 1 + 4x 2 + 0y 1 + 0y 2 ÏÔÔ ÔÔ ÔÔ x 1 + 2x 2 + y 1 = 3 ÔÌÔ ÔÔÔ 3x − 4x − y = 9 2 2 Ó 1 x 1 ,x 2 ≥ 0,y 1 ,y 2 ≥ 0

2

T

7. Se considera urmatoarea problema de transport: B1 B2 N1 4 6 N2 3 2 N3 2 10 Necesar 20 25 Problema de transport este echilibrata.

T

8. Se considera urmatoarea problema de transport: B1 B2 B3 B4 Disponibil N1 4 6 5 2 35 N2 3 2 7 8 30 N3 2 10 5 6 50 Necesar 20 25 45 25 O solutie initiala de baza determinata folosind metoda coltului de N-V este x 11 = 20, x 12 = 15, x 22 = 10, x 23 = 20, x 33 = 25, x 34 = 25, x 13 = x 14 = x 21 = x 24 = x 31 = x 32 = 0.

T

9. Se considera urmatoarea problema de transport: B1 B2 B3 B4 Disponibil N1 4 6 5 2 35 N2 3 2 7 8 30 N3 2 10 5 6 50 Necesar 20 25 45 25 O solutie initiala de baza determinata folosind metoda costului minim pe linie este x 11 = 10, x 14 = 25, x 21 = 5, x 22 = 25, x 31 = 5, x 33 = 45, x 12 = x 13 = x 23 = x 24 = x 32 = x 34 = 0.

T

B3 5 7 5 45

B4 2 8 6 25

Disponibil 35 30 50

10. Fie problema de programare liniară

(1) (2) (3)

Ax = b X ≥0 max(min )z = cx t cu A ∈ M (m, n ) , rang A = m < n , x = ( x1 ,...,xn ) . t

Vectorul x = ( x1 ,...,xn ) care satisface condiŃiile (1) şi (2) se numeşte soluŃie posibilă.

T/F

11. Fie problema de programare liniară

(1) (2) (3)

Ax = b X ≥0 max(min )z = cx t

cu A ∈ M (m, n ) , rang A = m < n , x = ( x1 ,...,xn ) . t

O soluŃie posibilă x = ( x1 ,...,xn ) se numeşte soluŃie de bază dacă coloanele ai ,...,air din 1 matricea A corespunzătoare coordonatelor nenule xi ,...,xir ale vectorului x sunt liniar 1 dependente.

3

F

12. Fie problema de programare liniară

(1) (2) (3)

Ax = b X ≥0 max(min )z = cx

t cu A ∈ M (m, n ) , rang A = m < n , x = ( x1 ,...,xn ) şi x o soluŃie de bază. Dacă x are şi coordonate nenule ea este o soluŃie degenerată.

T

13. Fie problema de programare liniară

(1) (2) (3)

Ax = b X ≥0 max(min )z = cx t

cu A ∈ M (m, n ) , rang A = m < n , x = ( x1 ,...,xn ) . O soluŃie posibilă care satisface (3) se numeşte soluŃie optimă.

F

14. 1. Următoarea problemă de transport este echilibrată

B1 A1 A2 A3

1

2

4

3

1

2

5

6

1

6

F

4

5 15 10

10

15. Următoarea problemă de transport este echilibrată

B1 A1 A2 A3

B3

B2

B4

1

3

1

2

2

4

1

3

3

2

4

2

30

F

B3

B2

25

15

20

16. Următoarea problemă de transport nu este echilibrată

B1 A1 A2 A3

20

B3

B2

1

2

3

2

1

4

3

1

2

35

10 25 35

15

4

15 25 20

F

17. Fie o problemă de transport. Pentru determinarea soluŃiei de bază prin metoda costurilor

minime în primul pas se determină componenta x kh pentru care c kh = min c ij şi se ia x kh = max (a k , bh ) , unde a1 ,..., a m sunt cantităŃile disponibile iar b1 ,..., bn cererile corespunzătoare.

T

18. Fie o problemă de transport unde a1 ,..., a m sunt cantităŃile disponibile, b1 ,..., bn cererile şi

c ij costurile. Utilizând metoda diagonalei se alege în primul pas componenta bazică

x11 = min (a1 , b1 ) modificând concomitent valorile lui a1 şi b1 .

T

19. Problema de transport

B1 A1 A2 A3

B3

B2

1 50

2

B4

2

3

20 2

2

1

4

5 3

50 are soluŃie multiplă

5

2

2

1

10 25

10 15

10

5

70 10 20