25-08 TP6 -2021 Prog Entera

Vista previa del material en texto

CLASE PRACTICA: Investigación Operativa
Trabajo Practico Nº 6 – Programación Entera
Profesores: JTP. Ing. Néstor O. Cruz
AY1. Ing. Mariela E. Rodríguez
Facultad de Ingeniería
Universidad Nacional de Jujuy
Programación Entera
Que es la programación Entera?
✓ Un modelo de PE es aquel cuya solución optima tiene sentido solo si una parte o todas las
variables de decisión son valores enteros.
✓ Un problema se define como programa entero puro cuando todas las variables son enteras.
En caso contrario, es un programa entero combinado (PEC) que implica una combinación
de variables enteras y continuas.
✓ El método de Ramificación y Acotamiento divide el problema inicial en busca de que las
variables sean enteras. La división de las variables debe ser por sus enteros proximos.
Programación Entera - Ejemplo
Resultado:
Z = 14,4
X1 = 3,7
X2 =2,3
Ambas variables son continuas. X1= 3,7
X2=2,3
Programación Entera
Para encontrar la solución a un problema de programación
entera, debemos lograr que las variables sean enteras.
Como solución inicial vemos que si las variables X1 y X2
serian enteras tendríamos este resultado:
X1 = 3,7 si es entera X1 = 3
X2 = 2,3 si es entera X2 = 2
Zinf = 12
12 ≤ Z ≤ 14,4
El valor de Z no puede salir de estos limites.
Como el resultado de ambas variables tienen resultado
real. Vamos a empezar a restringir los valores hasta
hacerlas enteras por el método de Ramificación y
Acortamiento.
X1= 3,7
X2=2,3
Resultado:
Z = 14,4
X1 = 3,7
X2 =2,3
Seleccionaremos X1 para hacerla entera. Que sean
próximos al valor actual. Dividimos al problema en dos sub
problemas:
X1 = 3,7 si es entera X1 = 3
Problema 1:
Problema 2:
Programación Entera – Método de Ramificación y Acotamiento
MAXIMIZAR: Z = 2 X1 + 3 X2
5 X1 + 7 X2 ≤ 35
4 X1 + 9 X2 ≤ 36
X1 ≤ 3
X1, X2 ≥ 0
MAXIMIZAR: Z = 2 X1 + 3 X2
5 X1 + 7 X2 ≤ 36
4 X1 + 9 X2 ≤ 35
X1 ≥ 4 
X1, X2 ≥ 0
Resultado:
Z = 14,4
X1 = 3,7
X2 =2,3X1 ≥ 4X1 ≤ 3
En el gráfico vemos los dos convexos
Z= 14,4
X1= 3,7
X2= 2,3
Z inf = 12
Programación Entera – Método de Ramificación y Acotamiento
Z= 13,8
X1= 3
X2= 2,6
Z= 14,4
X1= 4
X2= 2,14
Resultado:
Z = 14,4
X1 = 3,7
X2 =2,3X1 ≥ 4X1 ≤ 3
12 ≤ Z ≤ 14,4
En el gráfico vemos los dos convexos
Programación Entera – Método de Ramificación y Acotamiento
Resultado:
Z = 14,4
X1 = 3,7
X2 =2,3
Z= 14,4
X1= 3,7
X2= 2,3
Z inf = 12
Z= 13,8
X1= 3
X2= 2,6
Z= 14,4
X1= 4
X2= 2,14
12 ≤ Z ≤ 14,4
Z= 14,4
X1= 4,2 
X2= 2
Z= 13,8
X1= 2,4
X2= 3
X2 ≥ 3
X2 ≤ 2
En el gráfico vemos los dos convexos
Programación Entera – Método de Ramificación y Acotamiento
Resultado:
Z = 14,4
X1 = 3,7
X2 =2,3X1 ≤ 4
Z= 14,4
X1= 3,7
X2= 2,3
Z inf = 12
Z= 13,8
X1= 3
X2= 2,6
Z= 14,4
X1= 4
X2= 2,14
12 ≤ Z ≤ 14,4
Z= 14,3
X1= 4,2
X2= 2
Z= 14
X1= 4
X2= 2
Z= 14,5
X1= 5
X2= 1,5
Z= 13,8
X1= 2,4
X2= 3
X1 ≥ 5
X2
En el gráfico vemos los dos convexos
Programación Entera – Método de Ramificación y Acotamiento
Resultado:
Z = 14
X1 = 4
X2 = 2
Z= 14,4
X1= 3,7
X2= 2,3
Z inf = 12
Z= 13,8
X1= 3
X2= 2,6
Z= 14,4
X1= 4
X2= 2,14
12 ≤ Z ≤ 14,4
Z= 14,3
X1= 3,7
X2= 2,3
Z= 14
X1= 4
X2= 2
Z= 14,5
X1= 5
X2= 1,5
Z= 13,8
X1= 2,4
X2= 3
MAXIMIZAR: Z = 2 X1 + 3 X2
5 X1 + 7 X2 ≤ 36
4 X1 + 9 X2 ≤ 35
X1 = 4 
X2 ≤ 2
X1, X2 ≥ 0
Z= 14
X1= 4
X2= 2
Solución Optima Entera
Las nuevas restricciones se determinan mediante el siguiente
procedimiento de tres pasos.
PASO I : En la tabla simplex final actual, seleccióne una (cualquiera) de
las variables no enteras y, sin asignar valores cero a las variables que no
sean básicas, considérese la ecuación de restricción representada por el
renglón de la variable elegida.
▪ Algoritmo de Plano de Corte (Ralph E. “Gomory”)
x1 x2 x3 x4 x5
x3 -1/2 0 1 -7/3 1/2 11/2
x2 1/2 1 0 -1 1/4 1
4 0 0 1 3/4 25/2
La tabla simplex Optima:
Paso 1
De la solución óptima como X3
* = 11/2, X2
*= 1, con cada una de las variables no
básicas X1
*, X4
* y X5
* igualadas a cero.
La asignación no entera para X3
* provino del primer renglón de la tabla, que
representa la restricción.
(1) 
EJEMPLO
−
1
2
𝑋1 + 𝑋3 −
7
3
𝑋4 +
1
2
𝑋5 =
11
2
PASO 2 Reescríbase cada coeficiente y constante fraccionarios de la ecuación
de restricción obtenida en el paso 1, como la suma de un entero y una fracción
positiva entre 0 y 1.
Escríbase ahora la ecuación de forma que:
• el lado izquierdo contenga solamente términos con coeficientes fraccionarios
(y una constante fraccionaria),
• mientras que el lado derecho contendrá sólo términos con coeficientes
enteros (y una constante entera). La ecuación (1) se vuelve:
(2) 
−
1
2
𝑋1 + 𝑋3 −
7
3
𝑋4 +
1
2
𝑋5 =
11
2
−1 +
1
2
𝑋1 + 𝑋3 + −3 +
2
3
𝑋4 + 0 +
1
2
𝑋5 = 5 +
1
2
1
2
𝑋1 +
2
3
𝑋4 +
1
2
𝑋5 −
1
2
= 5 + 𝑋1 − 𝑋3 + 3𝑋4
PASO 3 Hágase que el lado izquierdo de la nueva expresión de la ecuación
sea no negativo.
La desigualdad resultante es la nueva restricción.
De (2)
se tiene que
es la nueva restricción
1
2
𝑋1 +
2
3
𝑋4 +
1
2
𝑋5 −
1
2
= 5 + 𝑋1 − 𝑋3 + 3𝑋4
1
2
𝑋1 +
2
3
𝑋4 +
1
2
𝑋5 −
1
2
≥ 0 ó
1
2
𝑋1 +
2
3
𝑋4 +
1
2
𝑋5 ≥
1
2
EJEMPLO:
Maximice: z = 2x1 + 1x2
Sujeto a : 2x1 + 5x2 ≤ 17
3x1 + 2x2 ≤ 10
con: x1, x2 no negativos y enteros.
Sin tomar en cuenta las condiciones de enteros y aplicando el método 
simplex al PL resultante, se obtiene la tabla 1 como la tabla óptima, 
después de una iteración.
x1 x2 x3 x4
x3 0 11/3 1 -2/3 31/3
x1 1 2/3 0 1/3 10/3
0 1/3 0 2/3 20/3
(1)
Tabla 1
x1 x2 x3 x4
x3 0 11/3 1 -2/3 31/3
x1 1 2/3 0 1/3 10/3
0 1/3 0 2/3 20/3
La primera aproximación al programa (1), por lo tanto, es ,/x,/x 331310 *3*1 ==
0*4*2 == xx . *3*1 y xx son, ambas, no enteras. 
Seleccionando arbitrariamente *x1 , se considera la restricción representada 
por el segundo renglón de la tabla 1, renglón que define a *x1 , esto es: 
3/103/13/2 421 =++ xxx 
Escribiendo cada fracción como la suma de un entero y una tracción entre 0 
y 1, se tiene: 
142421 3o3)0()0(
3
1
3
1
3
2
3
1
3
1
3
2
xxxxxx −=−++=++++ 
Haciendo que el lado izquierdo de esta ecuación sea no negativo, se obtiene: 
12o0
3
1
3
1
3
2
4242 +−+ xxxx nueva restricción.
x1 1 2/3 0 1/3 10/3
Escribiendo ahora las restricciones del programa original (1) en las formas
sugeridas por la tabla 1 y agregando la nueva restricción, se genera el nuevo
programa:
maximícese: 4321 002 xxxxz +++= 
 con las condiciones: 
3
31
3
2
3
11
432 =−+ xxx 
 
3
10
3
1
3
2
421 =++ xxx (2) 
 12 42 + xx 
 con: todas las variables no negativas y enteras. 
x1 x2 x3 x4
x3 0 11/3 1 -2/3 31/3
x1 1 2/3 0 1/3 10/3
0 1/3 0 2/3 20/3
Se agregan a la desigualdad de restricción de (2) una variable superflua,
x5, y una variable artificial, x6, y luego se aplica el método de dos fases, con
x1, x3, y x6 como el conjunto inicial de variables básicas.
La tabla 2, óptima, se obtiene únicamente después de una iteración.
Seleccionando X2
* para generar la nueva restricción, del tercer renglón de
la tabla 2 se obtiene:
Tabla 2
1
2
𝑋4 +
1
2
𝑋5 −
1
2
≥ 0 ó 𝑋4 + 𝑋5 ≥ 1
𝑋1 = 3, 𝑋2 =
1
2
, 𝑋3 = 17/2 
𝑋4 = 𝑋5 = 0 
esto, combinado con las restricciones del programa (2) en las formas sugeridas
por la tabla 2, da el nuevo programa entero:
 maximícese: 54321 0002 xxxxxz ++++= 
 con las condiciones: 
2
17
6
11
2
5
543 =+− xxx 
 3
3
1
51 =+ xx (3) 
 
2
1
2
1
2
1
542 =−+ xxx 
 154 + xx 
 con: todas las variables no negativas y enteras. 
Dejando a un lado la condición de que las variables sean enteras y 
aplicando el método de dos fases al programa (3), con x1, x2, x3, y x7
(artificiales) como el conjunto básico inicial, se obtiene la tabla 3, óptima
x1 x2 x3 x4 x5 x6
x3 0 0 1 -13/3 0 11/6 20/3
x1 1 0 0 -1/3 0 1/3 8/3
x2 0 1 0 1 0 -1/2 1
x5 0 0 0 1 1 -1 1
0 0 0 1/3 0 1/6 19/3
Paso 1: Se inicia una nuevaiteración a partir de x1
*= 8/3 en la Tabla 3
X1 – (1/3) X4 + (1/3) X6 = 8/3 
Paso 2: X1+(-1+2/3)X4 +(1-2/3) X6 = 2+(2/3) 
 X1 - X4 + (2/3) X4 + X6 - (2/3) X6 = 2+(2/3) 
 (2/3) X4 - (2/3) X6 -(2/3) = 2 - X1 + X4 - X6 
Paso 3: (2/3) X4 - (2/3) X6 -(2/3) ≥ 0 ó (2/3)X4- (2/3)X6 ≥ 2/3
como la nueva restricción.
Tabla 3
Escribiendo ahora las restricciones del programa original (1) en las formas
sugeridas por la tabla 3 y agregando la nueva restricción, se genera el
nuevo programa:
x1 x2 x3 x4 x5 x6
x3 0 0 1 -13/3 0 11/6 20/3
x1 1 0 0 -1/3 0 1/3 8/3
x2 0 1 0 1 0 -1/2 1
x5 0 0 0 1 1 -1 1
0 0 0 1/3 0 1/6 19/3
Maximícese: 654321 x0x0x0x0xx2z +++++= 
Con las condiciones: 
3
20
x
6
11
x
3
13
x 643 =+− 
 
3
8
x
3
1
x
3
1
x 641 =+− (4) 
 1x
2
1
xx 642 =−+ 
 1xxx 654 =−+ 
 
3
2
x
3
2
x
3
2
64 − 
 Con: todas las variables no negativas y enteras. 
• Esto da como resultado un programa cuya
solución es entera: x1
*= 3, x2
*= 0 y z* = 6.
• Entonces, ésta es la solución óptima al
programa entero (1).
X1 X2 X3 X4 X5 X6 X7
Ck Xk bk 2 1 0 0 0 0 0
0 X3 11 0 0 1 0 0 -3 -7
2 X1 3 1 0 0 0 0 0 -1
1 X2 0 0 1 0 0 0 43862 43864
0 X5 0 0 0 0 0 1 0 43864
0 X4 1 0 0 0 1 0 -1 -2
Zj 6 2 1 0 0 0 43862 43862
Zj-Cj 0 0 0 0 0 43862 43862
Ejercicio para resolver en clase: Aplique Ramificación y acotamiento.
Maximizar: z = 5 x1 + 4 x2
Sujeto a : x1 + x2 ≤ 5
10x1 + 6x2 ≤ 45
con: x1, x2 no negativos y enteros.
Preguntas
Muchas Gracias