Optimizacion

Tarea 3
Optimización

Programación lineal:
Análisis de sensibilidad
Simplex
Dualidad
Programación entera

Problema 1
Tenemos el siguiente problema de programación lineal:
Max Z=-5x1+5x2+13x3
sujeto a:
-x1+x2+3x3≤20 (1)
12x1+4x2+10x3≤90 (2)
xi≥0, i=1,2,3

El problema se resuelve con simplex y se tienen los siguientes datos:
XB=x2;x5
b=2010
(B*)-1=10-41

a) Se pideanalizar que sucede si b1, es decir el lado derecho de la restricción (1) cambia a 30.

Podemos hacer el caso general, y ver entre que valores se puede variar b1 para que la base siga siendo la misma.
Para esto necesitamos ver para que valores de b1 se cumple la siguiente desigualdad:

(B*)-1*b≥0
10-41*b1 10=b1 90-4*b1≥0 =>b1≥0 y b1≤22,5
0≤b1≤22,5

Es decir mientras el valor de b1esteentre 0 y 22,5 se mantendrá la base que se tiene, como se pide analizar que pasa si cambia a 30, podemos decir que esto afectará nuestra base y por lo tengo nuestro optimo.

b) En este punto lo que se quiere analizar es el coeficiente de x3 en la función objetivo, se quiere saber que pasa si este cambia a 8. Para analizar esto lo primero que hay que notar es que x3 no pertenece a la base, porlo tanto lo que se desea analizar es un costo reducido, es decir, se quiere analizar cuanto puede variar sin modificar la base que se tiene. Para esto debemos analizar la siguiente desigualdad:

c3=c3-cb*B*-1*A.3≥0

c3≥cb*B*-1*A.3
c3≥ [5,0]* 10-41*3 10=15
Por lo tanto al cambiar el valor del costo de 13 a 8, no produce cambio alguno ya que para que afecte la solución óptima, el valor de estecoeficiente debería aumentar en más de 15.

c) En este punto se pide analizar que pasa si los coeficientes de la variable x1, (c1,a11, a21) cambian a (-2,0,5) respectivamente.
Primero, como sabemos que se trata de una variable no básica haremos el mismo análisis que realizamos para la variable anterior para el costo reducido, pero cambiando también los valores nuevos que se modificaron enlas restricciones, es decir a11, a21 :

c1=c1-cb*B*-1*A.1≥0

c1≥cb*B*-1*A.1
c1≥ [5,0]* 10-41*0 5=0
Por lo tanto si se cambian los coeficientes a11, a21 a 0 y 5 respectivamente, se requiere que el c1 sea mayor o igual a 0 para que la base se modifique, como el valor que se le asigna es -2, la base no varia.

Problema 3
Utilice el método de ramificación y acotamiento (branch and bound) pararesolver el siguiente problema:
Max Z=2x1-x2+5x3-3x4+4x5
sujeto a:
3x1-2x2+7x3-5x4+4x5≤6
x1-x2+2x3-4x4+2x5≤0
xi binario, i=1,2,3,4,5
Para resolver este problema con el método de ramificación y acotamiento, primero debemos resolver el problema relajado que sería:
Problema 0
X1=0,66
X2=1
X3=1
X4=1
X5=1
Z=6,3

Problema 0
X1=0,66
X2=1
X3=1
X4=1
X5=1
Z=6,3

MaxZ=2x1-x2+5x3-3x4+4x5
sujeto a:
3x1-2x2+7x3-5x4+4x5≤6
x1-x2+2x3-4x4+2x5≤0
xi≥0 ; x1≤1 ; i=1,2,3,4,5

X1=1
X1=1
X1=0
X1=0

Problema 2
X1=1
X2=1
X3=0,85
X4=1
X5=1
Z=6,28

Problema 2
X1=1
X2=1
X3=0,85
X4=1
X5=1
Z=6,28

Problema 1
X1=0
X2=0
X3=1
X4=1
X5=1
Z=6

Problema 1
X1=0
X2=0
X3=1
X4=1
X5=1
Z=6

X3=0
X3=0
X3=1
X3=1

Problema 4
X1=1
X2=1
X3=1
X4=1
X5=0,75Z=6 = incumbente

Problema 4
X1=1
X2=1
X3=1
X4=1
X5=0,75
Z=6 = incumbente

Problema 3
X1=1
X2=0
X3=0
X4=0,75
X5=1
Z=3,75< incumbente

Problema 3
X1=1
X2=0
X3=0
X4=0,75
X5=1
Z=3,75< incumbente

Por lo tanto el máximo se alcanza cuando (x1,x2,x3,x4,x5) = (0,0,1,1,1); donde la función objetivo tiene un valor de 6.
Problema 5

Se tiene el siguiente problema
MaxZ=8x1+14x2+30x3+50x4
sujeto a:
x1+2x2+10x3+16x4≤800 1(horas-máquina mezclador)
3x12+2x2+4x3+5x4≤1000 2(horas-máquina vibrador)
1x12+0.6x2+x3+2x4≤340 (3)(horas-hombre inspección)
xi≥0, i=1,2,3,4

El problema se resolvió utilizando simplex, con lo cual se obtuvieron los siguientes resultados:
Valor optimo=6000 |   |   |
Variables | Valor variable | Costo reducido |
x1...