Ejercicio N°2
Investigación de Operaciones
2). Para el siguiente problema, resuelve utilizando la programación entera por el
método de Branch and Bound. 20 puntos:
Máx. Z = 6x1 + 9x2
s.a
2x1 + x2 ≤ 15
4x1 + 10x2 ≤ 45
x1 ≥ 0, x2 ≥ 0, enteras,
a) Encontrar la solución óptima con tableu Simplex o en Solver de Excel. 10
puntos
b) Ramificación desde x1 para encontrar la Solución Entera. 10 puntos
Solución:
a) La solución con Solver del problema,
Máx. Z = 6x1 + 9x2
s.a
2x1 + x2 ≤ 15
4x1 + 10x2 ≤ 45
x1 ≥ 0, x2 ≥ 0
Implementando se obtiene,
Variables Restricciones
X1 6,5625 15 ≤ 15
X2 1,875 45 ≤ 45
función objetivo: Z= 56,25
La solución óptima es x1=6.56 y x2=1.88 con Z0=56.25.
b) Se ramifica x1=6.56, se tienen los subproblemas, P1 con x1 ≤ 6 y P2 con x1 ≥ 7.
Todas las ramificaciones se resuelven con Solver.
Solver para P1
Variables Restricciones
X1 6 14,1 ≤ 15
X2 2,1 45 ≤ 45
6 ≤ 6
función objetivo: Z1= 54,9
Solución es x1=6 y x2=2.10 con Z1=54.9. Se ramifica ahora en x2=2.10 con la restricción
x2 ≤ 2 y x2 ≥ 3, en los subproblemas P3 y P4 respectivamente.
Solver para P2
Variables Restricciones
X1 7 15 ≤ 15
X2 1 38 ≤ 45
7 ≥ 7
función objetivo: Z2 51
La solución es x1=7 y x2=1 es entera, con Z2=51. Es candidato a la solución óptima.
Solver para P3
Variables Restricciones
X1 6 14 ≤ 15
X2 2 44 ≤ 45
6 ≤ 6
2 ≤ 2
función objetivo: Z3 54
La solución es x1=6 y x2=2 es entera con Z3=54, como Z3>Z1, entonces este es el nuevo
candidato a la solución.
Solver para P4
Variables Restricciones
X1 3,75 10,5 ≤ 15
X2 3 45 ≤ 45
3,75 ≤ 6
3 ≥ 3
función objetivo: Z4 49,5
La solución es x1=3.75 y x2=3 con Z4=49.5. Como Z4 < Z3, entonces no es necesario
ramificar en x1 ya que el valor de la función objetivo no va mejorar.
Así, se tiene que la solución óptima del problema de programación entera es X1=6 y x2=2
con valor de Z=54.
Gráficamente se obtiene el siguiente árbol, para obtener la solución.
P0 x1=6.56 P2 x1=7
x2=1.88 Z=56.25 x2=1 Z=51
P1 x1=6
P3 x1=6 x2=2.1 Z=54.9 P4 x1=3.75
x2=2 Z=54 x2=3 Z=49.5
1) Se nos plantea la siguiente función a Maximizar. 20 puntos:
Función Objetivo:
Max Z = 7X1 + 3X2 + 3X3
Sujeto a:
X1 <= 1.000
X2 <= 1.000
X3 <= 1.500
60X1 + 25X2 + 20X3 <= 100.000
X1 , 3X2 , 3X3 >= 0
a) Resolver con método simplex con tableu. 20 puntos
b) Plantee el Modelo Dual. 10 puntos
Solución:
a) Agregamos las variables de holgura, se obtiene:
Max Z= 7X1 + 3X2 + 3X3
Sujeto a
X1 + S1 = 1.000
X2 + S2 = 1.000
X3 + S3 = 1.500
60X1 + 25X2 + 20X3 + S4 = 100.000
X1,X2,X3,X4,S1,S2,S3,S4 >= 0
Aplicando el Método Simplex:
Interacción 0
base X X2 X3 S1 S2 S3 S4
1
Z -7 -3 -3 0 0 0 0 0
S1 1 0 0 1 0 0 0 1000
S2 0 1 0 0 1 0 0 1000
S3 0 0 1 0 0 1 0 1500
S4 6 25 20 0 0 0 1 10000
0 0
Entra X1 sale S1
Interacción 1
base X X2 X3 S1 S2 S3 S4
1
Z 0 -3 -3 7 0 0 0 7000
X1 1 0 0 1 0 0 0 1000
S2 0 1 0 0 1 0 0 1000
S3 0 0 1 0 0 1 0 1500
S4 0 25 20 -60 0 0 1 4000
0
Entra X2 sale S2
Interacción 2
base X X2 X3 S1 S2 S3 S4 Cb
1
Z 0 0 -3 7 3 0 0 1000
0
X1 1 0 0 1 0 0 0 1000
X2 0 1 0 0 1 0 0 1000
S3 0 0 1 0 0 1 0 1500
S4 0 0 20 -60 -25 0 1 1500
0
Entra X3 sale S4
Interacción 3
base X X2 X3 S1 S2 S3 S4 Cb
1
Z 0 0 0 -2 - 0 3/20 1225
3/4 0
X1 1 0 0 1 0 0 0 1000
X2 0 1 0 0 1 0 0 1000
S3 0 0 0 3 5/4 1 -1/20 750
X3 0 0 1 -3 - 0 1/20 750
5/4
Entra S1 sale S3
Interacción 4
base X1 X2 X3 S1 S2 S3 S4
Z 0 0 0 0 1/12 2/3 7/60 12750
X1 1 0 0 0 -5/12 -1/3 1/60 750
X2 0 1 0 0 1 0 0 1000
S1 0 0 0 1 5/12 1/3 -1/60 250
X3 0 0 1 0 0 1 0 1500
Ya no hay más variables de entrada.
La solución óptima es X1=750, X2=1000 y X3=1500. Para un valor máximo de 12750
b) El primal es
Max Z = 7X1 + 3X2 + 3X3
Sujeto a:
X1 <= 1.000 (Y1)
X2 <= 1.000 (Y2)
X3 <= 1.500 (Y3)
60X1 + 25X2 + 20X3 <= 100.000 (Y4)
X1 , 3X2 , 3X3 >= 0
Así, el dual es:
Min 1.000Y1 + 1.000Y2 +1.500 Y3 + 100.000Y4
Sujeto a
Y1 + 60Y4 >= 7
Y2 + 25Y4 >= 3
Y3 + 20Y4 >= 3
Y1,Y2,Y3,Y4 >= 0
