dsdsd

Prueba Optimizaci´n
o
Grupo de Optimizaci´n, Universidad De La Frontera
o
2er Semestre, 2012
Nombre:
Carrera:
1) Felipe tiene $2200 que los desea invertir en los pr´ximos 5 a˜ os. Al inicio
o
n
de cada a˜o, el puede invertir en dep´sitos de 1 o 2 a˜os. El banco paga
n
o
n
un 8% de inter´s por los de 1 a˜o y 17% por los de 2 a˜ os. Adem´s
e
n
n
a
el banco mundial ofrececertificados por 3 a˜os al inicio del segundo a˜ o
n
n
Estos certificados tienen un retorno de 27% al final del tercer a˜ o. Si
n
Felipe reinvierte su dinero disponible cada a˜o, formule un modelo de
n
optimizaci´n que muestre como obtener su ganancia m´xima al final del
o
a
quinto a˜o.
n
2) Considere el siguiente problema de programaci´n lineal:
o
min z = ct x
S.a
Ax ≤ b
x≥0
si se agreganvariables de holgura, el problema queda como sigue:
max
S.a

z = −x1 + x2
−4x1 + x2 + xh = 4
3
−4x1 + 3x2 + xh = 12
4
−x1 + x2 + xh = 6
5
x1 , x2 , xh , xh , xh ≥ 0
3
4
5

a) Demuestre que el punto x = (0, 4, 0, 0, 2)t es un punto extremal.
¯
b) Coloque el problema en forma expl´
ıcita con respecto a la SFB del
inciso anterior.
c) Encuentre la o las soluciones del problema pormedio del algoritmo
simplex.(Puede partir de la SFB encontrada en (a))
d) Ratifique la soluci´n encontrada en el inciso anterior resolviendo el
o
problema por el m´todo gr´fico.
e
a
e) Encuentre una funci´n objetivo de tal forma que el problema sea no
o
acotado.
f) Encuentre los puntos y direcciones extremales del problema y escriba
el punto x = (9, 8)t seg´n el teorema de Carathedory enfunci´n de
¯
u
o
los puntos y direcciones extremales del poliedro.
1

3) Resuelva el siguiente problema. En cada iteraci´n indique cual es la SFB,
o
y la base.
max
z = 2x1 + x2
S.a
10x1 + 10x2 ≤ 9
10x1 + 5x2 ≥ 1
x1 , x2 ≥ 0
4) Conteste cuidadosamente las siguientes preguntas:
a) ¿El problema auxiliar de las dos fases siempre es factible?.¿Por qu´?.
e
b) ¿Un zj −cj no b´sico iguala cero implica necesariamente la existencia
a
de soluci´n m´ltiple?.Explique
o
u
c) ¿El conjunto soluci´n de un problema de programaci´n linea siempre
o
o
es convexo?.Explique.
d) ¿El problema auxiliar siempre es acotado?.¿Por qu´?.
e
e) ¿Como darse cuenta en la tabla simplex cuando una SFB es degenerada?.¿Qu´ significa esto en la forma gr´fica?.
e
a
f) ¿El conjunto de direccionesinfinitas es un subconjunto del conjunto
de direcciones extremales?. ¿Por qu´?.
e

Puntaje

Preg 1
2

Preg 2
4

Con 9 puntos un 7
Con 0 puntos un 1
Con 5 puntos un 4

2

Preg 3
3

Preg 4
3

Resoluci´n
o
1) Definici´n de variables:
o
Sea xi j la cantidad de dinero que felipe invierte el a˜o i en el fondo j
n
(siempre que pueda).
Funaci´n objetivo:
o
Ganancia con el fondo1:
4

0, 08

xi1
i=0

Ganancia con el fondo 2:

3

xi2

0, 17
i=0

Ganancia con el fondo 3:

2

xi3

0, 27
i=0

Por lo tanto la funci´n objetivo es:
o
2

3

4

i=0

i=0

xi3

xi2 + 0, 27

xi1 + 0, 17

maxz = 0, 08

i=0

Restricciones:
A˜o 0:
n
x01 + x02 + x03 ≤ 2200
A˜o 1:
n
x11 + x12 + x13 ≤ 2200 − x02 − x03 + 1, 08x01
A˜o 2:
n
x21 + x22 +x23 ≤ 2200 − x12 − x13 − x03 + 1, 08(x01 + x02 ) + 1, 17x02
A˜o 3:
n
x31 +x32 ≤ 2200−x22−x23 +1, 08(x01 +x11 +x21 )+1, 17(x02 +x12 )+1, 27x03
A˜o 4:
n
2

3

i=0

i=0

2)

xi2 + 1, 27(x03 + x13 ) − x32 − x23

xi1 + 1, 17

x41 ≤ 2200 + 1, 08

a) Si la funci´n objetivo cambia por min z = −2x1 − x2 , el problema
o
esta en forma ´standar, y la matriz A, que es de rango 3, semuestra
e
a continuaci´n.
o


−4 1 1 0 0
A = −4 3 0 1 0
−1 1 0 0 1
3

Por lo tanto el punto extremal degenerado x = (0, 4, 0, 0, 2)t esta
¯
asociado a la base:


1 0 0
B = 3 1 0
1 0 1

Por lo tanto el punto x es un punto extremal degenerado porque.
¯
∗ Tiene m´s de n − m = 5 − 3 = 2 ceros.
a
∗ Es factible (Ax = b, x ≥ 0)
   
1
0
∗ El conjunto {3 , 0}...