1. No category

PROBLEMA DE PROGRAMACIÓN ENTERA
TALLER PROGRAMACIÓN
ENTERA
Un ganadero tiene una finca de 240 hectáreas
y puede bombear del acuífero adyacente
400000 litros de agua durante el año. El
ganadero crío dos tipos de ganado. Una
cabeza de ganado de tipo 1 requiere 10000
litros de agua y 4 hectáreas durante el año, y
una cabeza del tipo 2 requiere 8000 litros de
agua y 8 hectáreas durante el año.
sigue
La ganancia del ganadero es de $400000
por cabeza del tipo 1 y $360000 por cabeza
de tipo 2.
¿cuántas cabezas de ganado del tipo 1 y
del tipo 2 debe criar el ganadero con el fin
de maximizar sus ganancias?.
SOLUCIÓN
X1 = Número de cabezas de ganado tipo 1.
X2 = Número de cabezas de ganado tipo 2.
F.O : Max Z = 400 X1 + 350 X2 ( por 1000).
s.a:
10 X 1 + 8 X2 ≤ 400
4X1 + 8 X2 ≤ 240
X1, X2 ≥≥ 0 ∈ Z (enteras)
Veamos
X2
70
El método de ramificación y acotamiento
empieza por resolver la relajación P.L del P.E.
60
10 X1 + 8X2 = 400
50
Así entonces la relajación PL será:
40
Max Z = 400X1 +360X2
10X1 +8 X2 ≤≤ 400
4X1 + 8X2
≤≤ 240
X1 , X2 ≥≥ 0
30
20
10
4X1 + 8X2 = 240
0
10
20
30
40
50
60
X1
Veamos
1
Relajación P.L
X2
70
60
X1 = 26.66
X2 = 16.66
Z = 16666.66
Solución óptima relajación P.L
10 X1 + 8X2 = 400
50
Debemos dividir la región
factible de la relajación P.L
40
óptimo de la
relajación P.L
30
Así entonces elegimos
arbitrariamente entre X1
y X2 para crear dos
subproblemas
20
10
4X1 + 8X2 = 240
0
10
20
30
40
50
60
X1
Veamos
Z=16000
X2
70
Así entonces :
Subproblema 2
Max Z = 400X1 +360X2
10X1 + 8 X2 ≤≤ 400
4X1 + 8 X2 ≤≤ 250
X1
≥≥ 27
X1 , X2 ≥≥ 0
60
Subproblema 1
50
Max Z = 400X1 +360X2
10X1 + 8 X2 ≤≤ 400
4X1 + 8 X2 ≤≤ 250
X1
≤≤ 26
X1 , X2 ≥≥ 0
40
Subproblema 1
30
20
Subproblema 2
10
Veamos
Solución óptima subproblema 2
Solución óptima subproblema 1
Debemos dividir la región
factible del subproblema 2
0
10
X1 = 27
X2 = 16.25
Z = 16650
X1 = 26
X2 = 17
Z = 16520
30
40
50
60
X1
problema 1
X1 = 26.66
X2 =16.66
Z = 16666.66
X1 ≥≥ 27
Subproblema 2
Recordemos que esta
elección es arbitraria.
Escogemos X2 para hacer
la división
20
X1 = 27
X2 = 16.25
Z = 1640
X1 ≤≤ 26
Subproblema 1
X1 = 26
X2 = 17
Z = 16520
Resumiendo
2
X2
70
Así entonces :
Subproblema 3
Max Z = 400X1 +360X2
10X1 + 8 X2 ≤≤ 400
4X1 + 8 X2 ≤≤ 250
X1
≥≥ 27
X2
≥≥ 17
X1 , X2 ≥≥ 0
60
Subproblema 4
Max Z = 400X1 +360X2
10X1 + 8 X2 ≤≤ 400
4X1 + 8 X2 ≤≤ 250
X1
≥≥ 27
X2
≤≤ 16
X1 , X2 ≥≥ 0
50
Subproblema 3
No tiene región
factible
40
30
20
10
Subproblema 4
0
Veamos
No
factible
50
60
X1
Subproblema 1
X1 = 26
X2 = 17
Z = 16520
Subproblema 4
X1 = 27.2
X2 = 16
Z = 16640
Resumiendo
X2
70
Así entonces :
40
X2 ≤≤ 16
X2 ≥≥ 17
Subproblema 3
Escogemos X1 para hacer
la división
30
Subproblema 2
X1 = 27
X2 = 16.25
Z = 16650
No factible
Debemos dividir la región
factible del subproblema 4
20
RELAJACIÓN PL
X1 = 26.66
X2 = 16.66
X1 ≥≥ 27
Z = 16666.66 X1 ≤≤ 26
X1 = 27.2
X2 = 16
Z = 16640
Solución óptima subproblema 4
Solución óptima subproblema 3
10
60
Subproblema 5
Subproblema 5
Subproblema 6
50
MaxZ = 400X1 +360X2
10X1 +8 X2 ≤≤ 400
4X1 + 8X2 ≤≤ 240
X1
≥≥ 27
X2
≤≤ 16
X1
≤≤ 27
X1 , X2 ≥≥ 0
MaxZ = 400X1 +360X2
10X1 +8 X2 ≤≤ 400
4X1 + 8X2 ≤≤ 240
X1
≥≥ 27
X2
≤≤ 16
X1
≥≥ 28
X1 , X2 ≥≥ 0
40
30
20
10
Subproblema 6
0
10
20
30
40
50
60
X1
3
Solución óptima subproblema 6
X1 = 28
X2 = 15
Z = 16600
Subproblema 2
Solución óptima subproblema 5
X1 =27
X2 = 16
Z = 16560
RELAJACIÓN PL
X1 = 26.66
X1 ≤≤ 26
X2 = 16.66
Z = 1666.66
Subproblema 1
X1 ≥≥ 27
X2 ≥≥ 17
X1 = 27
X2 = 16.25
Z = 16650
X1 = 26
X2 = 17
Z = 16520
X2 ≤≤ 16
Subproblema 4
X1 = 27.2
X2 = 16
X1 ≥≥ 28
Z = 16640
Subproblema 3
No factible
Subproblema 6
X1 = 28
X2 =15
Z = 16600
Solución
óptima
Resumiendo
X1 ≤≤ 27
Subproblema 5
X1 = 27
X2 = 16
Z = 16560
PROGRAMACIÓN ENTERA
DISCO
El administrador de Perseus de la
universidad quiere
tener la
posibilidad de accesar 5 archivos
diferentes donde se guarda la
información de registro y matricula
de los estudiantes. Estos archivos se
encuentran en diez discos como se
ilustra a continuación:
1
2
ARCHIVO 1
X
X
ARCHIVO 2
X
ARCHIVO 3
4
5
X
X
X
X
7
8
9
X
X
X
X
10
X
X
X
X
X
X
X
6
X
ARCHIVO 4
ARCHIVO 5
3
X
X
X
sigue
La Cantidad de almacenamiento requerido por cada
disco se da a continuación:
Disco 1
Disco 2
Disco 3
Disco 4
Disco 5
3 GB
5GB
1GB
2GB
1GB
Disco 6
Disco 7
Disco 8
Disco 9
Disco 10
4 GB
3GB
1GB
2GB
2GB
Formule un problema de programación entera que
determine un conjunto de discos que necesitan la mínima
cantidad de almacenaje, tal que cada archivo se
encuentra en por lo menos uno de los discos.
sigue
Por políticas
de organización de la
información en la universidad para un disco
dado hay que almacenar o bien todo el disco o
bien nada del disco; no es posible guardar
parte de un disco.
Adicionalmente, si se usa el disco 3 o el disco
5, entonces habrá que utilizar también el
disco 2.
Veamos
4
SOLUCIÓN:
1. Tomemos la variable de decisión:
Xi : Utilizar el disco i o no utilizarlo,
donde:
1, utiliza el disco i.
0, no utiliza el disco i.
Xi =
Con i= 1, 2, 3........10
3. RESTRICCIONES:
Archivo 1:
X1 + X2 + X4 + X5 + X8 + X9
≥1
Archivo 2:
X1 + X3
≥1
Archivo 3:
X2 + X5 + X7 + X 10
≥1
Archivo 4:
X3 + X6 + X8 + X 9
≥1
2. Medida de la eficiencia.
MIN Z : 3X1 + 5X 2 + X3 + 2 X4 + X5 + 4X 6 + 3X7 + X8 + 2 X9 + 2X10
Archivo 5:
X1 + X2 + X4 + X5 + X7 + X9 + X10 ≥ 1
sigue
Como no se puede almacenar parte del
disco
Xi es binaria
Como debe utilizarse el disco 2 si se utiliza
el 3 ó el 5 tenemos que:
a. X3 ≤ X2
b. X5 ≤ X2
FIN
5