1) La característica principal es la solución entera, no cabe lugar para soluciones en fracciones o decimales, esto a su vez la diferencia
de la programación lineal
Este tipo de programación se clasifica en dos grupos, programación entera pura (PEP) y programación entera mixta (PEM)
3) Programación entera pura (PEP)
4) b. Ramificación y acotamiento
5) a. Para tomar una decisión toma valores de 0 y 1
6) Maximizar
Z=50 x1 +5 x 2
Sujeto a:
10 x 1+25 x 2 ≤ 55
x1 , x2 ≥ 0
Solución
Graficamos 10 x 1+25 x 2 ≤ 55
Obtenemos las cotas
10 x 1+25 x 2=55 x1 =0 10 x 1+25 x 2=55 x2 =0
10 ( 0 ) +25 x 2=55 10 x 1+25 ( 0 )=55
25 x 2=55 10 x 1=55
55 55
x 2= =2.2 x 1= =5.5
25 10
A=( 0 , 2.2 ) B=( 5.5 , 0 )
Evaluamos los puntos extremos
Z A =50 ( 0 ) +5 ( 2.2 )=11
Z B=50 ( 5.5 ) +5 ( 0 ) =275
Solución optima
x 1=5.5 x 2=0 Z=275
De aquí vemos que la solución no es entera, por lo tanto ramificamos en x 1 ≤ 5 x 1 ≥ 6
Z=50 x1 +5 x 2 Z=50 x1 +5 x 2
10 x 1+25 x 2 ≤ 5 5 10 x 1+25 x 2 ≤ 5 5
x1 ≤ 5 x1 ≥ 6
x1 , x2 ≥ 0 x1 , x2 ≥ 0
Solución no factible
x 1=5
x 2=0,2
Z=251
Ramificamos a x 2 en x 2 ≤ 0 x 2 ≥ 1
Z=50 x1 +5 x 2 Z=50 x1 +5 x 2
10 x 1+25 x 2 ≤ 5 5 10 x 1+25 x 2 ≤ 5 5
x1 ≤ 5 x1 ≤ 5
x2 ≥ 1 x2 ≤ 0
x1 , x2 ≥ 0 x1 , x2 ≥ 0
x 1=3 x 1=5
x 2=1 x 2=0
Z=155 Z=250
Hemos encontrado una solución entera en el punto G (5,0) con Z=250 por lo tanto podemos tomar este punto como la solución
optima y factible
7) Resuelva
Z=60 x1 +100 x 2
Sujeto a:
2 x1 +3 x 2 ≤ 7
4 x1 +3 x 2 ≤ 10
x1 , x2 ≥ 0
Resolvemos por el método grafico apoyados con el software Geogebra
Obtenemos los puntos extremos A, B y C
En el punto A se tiene que x 1=0 En el punto C se tiene que x 2=0
2 ( 0 ) +3 x 2=7 4 x1 +3 ( 0 ) =10
3 x 2=7 4 x1 =10
7 10
x 2= x 1=
3 4
A= 0 ,( 73 ) C= ( 52 , 0)
En el punto B se tiene la intersección de 2 x1 +3 x 2=7 y 4 x1 +3 x 2=10 resolvemos
7 2
2 x1 +3 x 2=7 → x 2= − x 1
3 3
Sustituimos en
4 x1 +3 x 2=10 → 4 x 1 +3 ( 73 − 23 x )=10
1
4 x1 + ( 7−2 x1 ) =10
2 x1 =10−7
3
x 1=
2
Tenemos
7 2 7 2 3 4
x 2= − x 1 = −
3 3
=
3 3 2 3 ()
B= ( 32 , 43 )
Evaluamos los punto A, B y C
7 7 optimo
A= 0 ,( ) 3
Z=60 ( 0 ) +100 ()
3
=233,33
B= ( 32 , 43 ) Z=60 ( 32 )+100( 43 )=223,33
C= ( 52 , 0) Z=60 ( 52 )+100 ( 0 ) =150
Entonces se tiene
P0
x 1=0
x 2=7 /3
Z=233,33
La solución x 2=7 /3 no es entera por tanto ramificamos en x 2 ≤ 2 x2 ≥ 3
x2 ≤ 2 x2 ≥ 3
Z=60 x1 +100 x 2 Z=60 x1 +100 x 2
2 x1 +3 x 2 ≤ 7 2 x1 +3 x 2 ≤ 7
4 x1 +3 x 2 ≤ 10 4 x1 +3 x 2 ≤ 10
x1 , x2 ≥ 0 x1 , x2 ≥ 0
Tenemos la solución óptima en el punto E (0.5 , 2) Solución no factible
x 1=0 , 5
x 2=2
Z=23 0
Ramificamos x 1=0,5 en x 1 ≤ 1 x1 ≥ 2
x1 ≤ 1 x1 ≥ 2
x2 ≤ 2 x2 ≤ 2
Z=60 x1 +100 x 2 Z=60 x1 +100 x 2
2 x1 +3 x 2 ≤ 7 2 x1 +3 x 2 ≤ 7
4 x1 +3 x 2 ≤ 10 4 x1 +3 x 2 ≤ 10
x1 , x2 ≥ 0 x1 , x2 ≥ 0
Tenemos la solución óptima en el punto G (1 , 1.667) Tenemos la solución óptima en el punto I (2 , 0.667)
x 1=1 x 1=2
x 2=1,667 x 2=0,667
Z=226,667 Z=186,667
Se toma la solución en el punto G y ramificamos en x 2 ≤ 1 x 2 ≥ 2
x2 ≤ 1 x2 ≥ 2
x1 ≤ 1 x1 ≤ 1
x2 ≤ 2 x2 ≤ 2
Z=60 x1 +100 x 2 Z=60 x1 +100 x 2
2 x1 +3 x 2 ≤ 7 2 x1 +3 x 2 ≤ 7
4 x1 +3 x 2 ≤ 10 4 x1 +3 x 2 ≤ 10
x1 , x2 ≥ 0 x1 , x2 ≥ 0
Tenemos la solución óptima en el punto E (0.5 , 2)
x 1=0,5 Tenemos la solución óptima en el punto A (0 , 2.33)
x 2=2 x 1=0
Z=230 x 2=2,33
Z=233,33
Tenemos que las soluciones obtenidas equivalen a puntos seleccionados anteriormente, por tanto se debe tomar el punto donde Z
sea máxima y que el resultado sea entero
F ( 0,2 ) Z=60 ( 0 ) +100 ( 2 )=200 Punto optimo y Solución
K ( 1,1 ) Z=60 ( 1 )+ 100 ( 1 ) =160
J ( 2,0 ) Z=60 ( 2 )+ 100 ( 0 )=120
