tehnici-opt-new
Post on 27-Jul-2015
259 Views
Preview:
TRANSCRIPT
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
top related