PROGRAMACION LINEAL ENTERA
Luis Medina Aquino
PROGRAMACION LINEAL ENTERA
En muchos modelos algunas o todas las
variables de decisin deben ser enteras.
Estos modelos son conocidos como modelos
de programacin lineal entera (PLE).
PROGRAMACION LINEAL ENTERA
Clasificacin:
PROGRAMACION LINEAL ENTERA
PROBLEMA:
Boxcar es una nueva cadena de restaurantes de
comida rpida (fast-food) que est planificando
expandirse en Washington DC. An cuando la
comida es de alta calidad, la principal atraccin de
esta cadena de restaurantes es su diseo. En el
centro de la ciudad el interior del local se construy
de tal forma de parecerse al interior de un container,
mientras que en los suburbios los restaurantes se
construyeron al interior de verdaderos containers.
PROGRAMACION LINEAL ENTERA
La compaa dispone de US$2.7 millones para su
expansin. Cada restaurant en los suburbios
requiere US$200,000 en inversin, y cada local en el
centro requiere de US$600,000. Se proyecta que
luego de los gastos, la ganancia neta semanal en
los locales de los suburbios (que estarn abiertos
las 24 horas) ser en promedio US$1200. Los
restaurantes del centro abrirn slo 12 horas al da,
pero debido a una gran cantidad de clientes durante
las horas de trabajo las proyecciones indican que la
ganancia neta semanal ser de US$2000.
PROGRAMACION LINEAL ENTERA
La compaa desea abrir al menos 2 restaurantes en el
centro. Boxcar actualmente tiene 19 administradores.
Cada local en los suburbios requerir tres
administradores para su funcionamiento las 24 horas, y
se cree que con slo un administrador en el centro por
restaurante sera suficiente. Boxcar desea saber
cuntos restaurantes podra abrir para maximizar su
ganancia neta semanal.
PROGRAMACION LINEAL ENTERA
RESUMIENDO:
Boxcar debe decidir cuntos restaurantes debe abrir en
los suburbios y en el centro de Washington DC.
Desean maximizar su ganancia total semanal
promedio.
La inversin total no puede exceder US$2.7 millones
Se deben abrir al menos 2 restaurantes en el centro
Slo se cuenta con 19 administradores.
PROGRAMACION LINEAL ENTERA
FORMULACION:
Maximizar Z = 1200 X1 + 2000 X2
s.a.
200000 X1 + 600000 X2 <= 2700000
X2 >= 2
3 X1 + X2 <= 19
X1, X2 >= 0, enteros
PROGRAMACION LINEAL ENTERA
La solucin real del problema es:
X1 = 87/16 = 5.4375, X2 = 43/16 = 2.6875,
Z = US$ 11,900
La solucin entera podr ser solo redondear
simplemente los valores de la solucin real?
Posibles resultados del redondeo:
1. Los puntos pueden ser no-factibles
2. Los puntos pueden ser factibles pero no-ptimos
3. Los puntos pueden ser factibles y ptimos
PROGRAMACION LINEAL ENTERA
Solucin real del problema:
X1 = 5.4375, X2 = 2.6875, Z = US$ 11,900
Posibles redondeos:
X
1
X
2
Es
factible?
Maximizar Z = 1200 X1 + 2000
X2
s.a.
200000 X1 + 600000 X2 <=
2700000
X2 >= 2
3 X1 + X2 <= 19
X1, X2 >= 0,
enteros
PROGRAMACION LINEAL ENTERA
Solucin real del problema:
X1 = 5.4375, X2 = 2.6875, Z = US$ 11,900
Posibles redondeos:
X
1
X
2
Es
factible?
NO
---
Maximizar Z = 1200 X1 + 2000
X2
s.a.
200000 X1 + 600000 X2 <=
2700000
X2 >= 2
3 X1 + X2 <= 19
X1, X2 >= 0,
enteros
PROGRAMACION LINEAL ENTERA
Solucin real del problema:
X1 = 5.4375, X2 = 2.6875, Z = US$ 11,900
Posibles redondeos:
X
1
X
2
Es
factible?
NO
---
NO
---
Maximizar Z = 1200 X1 + 2000
X2
s.a.
200000 X1 + 600000 X2 <=
2700000
X2 >= 2
3 X1 + X2 <= 19
X1, X2 >= 0,
enteros
PROGRAMACION LINEAL ENTERA
Solucin real del problema:
X1 = 5.4375, X2 = 2.6875, Z = US$ 11,900
Posibles redondeos:
X
1
X
2
Es
factible?
NO
---
NO
---
NO
---
Maximizar Z = 1200 X1 + 2000
X2
s.a.
200000 X1 + 600000 X2 <=
2700000
X2 >= 2
3 X1 + X2 <= 19
X1, X2 >= 0,
enteros
PROGRAMACION LINEAL ENTERA
Solucin real del problema:
X1 = 5.4375, X2 = 2.6875, Z = US$ 11,900
Posibles redondeos:
X
1
X
2
Es
factible?
NO
---
NO
---
NO
---
SI
10000
Maximizar Z = 1200 X1 + 2000
X2
s.a.
200000 X1 + 600000 X2 <=
2700000
X2 >= 2
3 X1 + X2 <= 19
X1, X2 >= 0,
enteros
PROGRAMACION LINEAL ENTERA
La solucin entera del problema es: X1 = 4, X2 = 3,
Z = US$ 10.800
Nota: Imponer restriccin de enteros agrega dos
restricciones al problema: X1 entero y X2 entero. As
es que tal como vimos antes el valor de la funcin
objetivo NO puede mejorar. En un problema de
maximizacin esto significa que el valor de la
funcin objetivo disminuir o en el mejor de los
casos ser el mismo que el valor ptimo del
problema de programacin lineal en el dominio de
los reales.
APLICACIONES DE VARIABLES BINARIAS
VARIABLES BINARIAS
Se denominan variables binarias aquellas que estn
restringidas a dos valores nicamente, por lo
general estos valores son cero y uno.
Si Y < 1
Y>0
Y es entera
Entonces Y es una variable binaria {0,1}
APLICACIONES DE VARIABLES BINARIAS
DECISIONES DICOTOMICAS
Cuando se tienen solo 2 elecciones, la decisin se puede
representar por variables de decisin restringidas exclusivamente a 2 valores.
Yi = 1, si la decisin i es s
0, si la decisin i es no
Ejemplos: Debe emprenderse este proyecto i?
Debe hacerse esta inversin en particular?
Debe realizarse esta instalacin en este sitio en particular?
APLICACIONES DE VARIABLES BINARIAS
ALTERNATIVAS MUTUAMENTE EXCLUYENTES.
Si se tiene un conjunto de alternativas de decisin, pero
slo una decisin en el grupo puede ser si, se requiere de
este tipo de restricciones.
Yi 1 Exactamente una decisin en el grupo debe ser si.
Yi 1 Cuando mucho una decisin en el grupo puede ser
si.
En donde la suma se toma nicamente sobre las variables
del grupo
APLICACIONES DE VARIABLES BINARIAS
DECISIONES CONTINGENTES.
Se dice que una decisin es contingente cuando
depende de decisiones anteriores, en otras
palabras:
La decisin K es contingente con la decisin J
si se permite que K sea Si nicamente cuando J
es Si.
Esto sucede cuando la decisin K comprende una
accin consecuente que se volvera irrelevante o
imposible si la decisin J es no.
APLICACIONES DE VARIABLES BINARIAS
DECISIONES CONTINGENTES.
En forma de restriccin, escribiramos:
Yk < Yj
Si Yj = 1 Permite elegir libremente a Yk , o sea que
puede tomar el valor de cero o de uno segn
convenga a la funcin objetivo. Mientras que Yj = 0
fuerza a que Yk = 0
Matemticamente se escribira:
Yk - Yj < 0
APLICACIONES DE VARIABLES BINARIAS
RESTRICCIONES ALTERNATIVAS:
En ocasiones puede elegirse entre dos restricciones,
de manera que debe cumplirse una "o bien" la otra.
Ejemplo: 3 X1 + 2 X2 < 20, o bien, X1 + 3 X2 < 15
En un modelo de Programacin Lineal TODAS las
restricciones deben cumplirse para que ste tenga
solucin factible, esto se debe a que la presencia de
restricciones del tipo "o bien" crea un espacio de
soluciones no convexo.
APLICACIONES DE VARIABLES BINARIAS
RESTRICCIONES ALTERNATIVAS:
Lo anterior se puede evitar incorporando al modelo
variables binarias y definiendo a M como un
nmero suficientemente grande el cual, al sumarlo
a cualquiera de las restricciones, automticamente
estaramos eliminando esa restriccin porque sera
redundante.
APLICACIONES DE VARIABLES BINARIAS
RESTRICCIONES ALTERNATIVAS:
En el ejemplo:
3 X1 + 2 X2 < 20, o bien,
X1 + 3 X2 < 15
Podemos hacer redundante cualquiera de las dos al
agregarle M
3 X1 + 2 X2 < 20 + M
X1 + 3 X2 < 15
o bien
3 X1 + 2 X2 < 20
X2 + 3 X2 < 15 + M
APLICACIONES DE VARIABLES BINARIAS
RESTRICCIONES ALTERNATIVAS:
Como no sabemos cual de las dos alternativas
anteriores sea la mas conveniente, introducimos la
variable binaria Y, y dejamos que el proceso de
solucin asigne el valor mas conveniente para esta
variable, y al hacerlo seleccione automticamente
la mejor alternativa.
Y = 0, si se elimina la primera restriccin.
1, si se elimina la segunda restriccin.
APLICACIONES DE VARIABLES BINARIAS
RESTRICCIONES ALTERNATIVAS:
3X1 + 2X2 < 20 + M (1-Y) redundante para
Y = 0, y activa para Y=1.
X1 + 3X2 < 15 + M (Y ) activa para Y = 0, y
redundante para Y=1.
Reordenando los trminos (todas las variables del
lado izq.) quedara:
3X1 + 2X2 + MY < 20 + M
X1 + 3X2 - MY < 15
Y es binario {0,1}
APLICACIONES DE VARIABLES BINARIAS
RESTRICCIONES DE APORTACIONES
Suponga que se tienen las siguientes restricciones:
a) Si se compra el producto j, se deben adquirir
por lo menos 20 unidades.
b) No se pueden adquirir ms de 100 unidades del
producto j.
Sea Xj = unidades que se adquieren del producto j
Un intento por representar las restricciones de a) y
b) podra ser:
20 < Xj < 100
APLICACIONES DE VARIABLES BINARIAS
RESTRICCIONES DE APORTACIONES
Sin embargo, esta restriccin no representa las
condiciones ya que obliga a que la variable Xj tome
valores entre 20 y 100, y no considera la condicin
Si...
Si definimos una variable binaria Yj para
representar la decisin respecto a comprar o no
comprar el artculo j, tendremos:
Yj = 1, Indica que Si se compra el artculo j
Yj = 0, Indica que No se compra el artculo j.
APLICACIONES DE VARIABLES BINARIAS
RESTRICCIONES DE APORTACIONES
Podramos expresar las condiciones a) y b) de la
siguiente manera:
Xj < 100Yj
Xj > 20Yj
Si Yj = 0, obliga a que Xj sea 0, mientras que si
Yj = 1 permite que la variable Xj tome valores entre
20 y 100.
APLICACIONES DE VARIABLES BINARIAS
Ejemplo 1:
Cierta compaa industrial ha decidido expandirse
construyendo una nueva fbrica ya sea en Lima o en
Arequipa. Est considerando tambin la construccin de
un nuevo almacn en aquella ciudad que se seleccione
para la nueva fabrica. La informacin sobre cada
alternativa se muestran en la siguiente tabla. El capital
disponible para inversin es $ 35, 000, 000.
El objetivo es encontrar la combinacin de alternativas
que maximice el valor presente neto.
APLICACIONES DE VARIABLES BINARIAS
Valor presente
neto
Capital requerido
inversin
Fabrica en Lima
7 millones
20 millones
Fabrica en
Arequipa
5 millones
15 millones
Almacn en Lima
4 millones
12 millones
Almacn en
Arequipa
3 millones
10 millones
APLICACIONES DE VARIABLES BINARIAS
Planteamiento con variables binarias
Numero de
Decisin
Pregunta de
S o No
Variable
de
Decisin
Valor
Presente
Neto
Cap. Req. de
inversin (mills )
Se construye la
fabrica en Lima ?
Y1
20
Se construye la
fbrica en Arequipa?
Y2
15
Se construye el
almacn en Lima?
Y3
12
Se construye el
almacn en Arequipa ?
Y4
10
APLICACIONES DE VARIABLES BINARIAS
Sea:
Yi = 1, si la decisin i es Si donde i = 1,2,3,4
0, si la decisin i es No
Las primeras dos decisiones representan alternativas
mutuamente excluyentes.
Y1 + Y2 = 1
Las decisiones 3 y 4 son contingentes en relacin con las
decisiones 1 y 2.
Y3 - Y1 0
Y4 - Y2 0
APLICACIONES DE VARIABLES BINARIAS
Ejemplo 2:
Cierta compaa fabricante de pinturas tiene disponibles
tres procesos diferentes estandarizados para producir
pinturas blancas para casas. Cada proceso tiene unos
costos fijos y un costo de proceso por galn. La capacidad
de cada proceso es como sigue:
Proceso
Nmero
Costo
fijo
Costo
($ / galn )
Capacidad
mxima diaria
( galones )
$ 100
2000
200
3000
300
4000
APLICACIONES DE VARIABLES BINARIAS
La compaa espera una demanda diaria de 3500
galones. El problema es mostrar qu procesos usar y qu
capacidades con el fin de satisfacer su demanda diaria
con un costo total mnimo.
APLICACIONES DE VARIABLES BINARIAS
Formulacin del modelo
Variables de decisin.
Sea
Y1 = 1, Si el proceso 1 es
usado
Y2 = 0, Si el proceso 1 no es
usado
Y3 = 1, Si el proceso 2 es
usado
Las variables Y
Y2el
, Yproceso
0,1,Si
2 no esbinarias {0,1}
3 son variables
usado
1, Si el proceso 3 es
APLICACIONES DE VARIABLES BINARIAS
Variables de decisin.
Sea
X1 = Cantidad de galones que se produce en el
proceso 1
X2 = Cantidad de galones que se produce en el
proceso 2
X3 = Cantidad de galones que se produce en el
proceso 3
APLICACIONES DE VARIABLES BINARIAS
Funcin objetivo. El objetivo es escoger los procesos y
los niveles de produccin para satisfacer la demanda
diaria minimizando el costo total.
Sea Z una variable que denota el costo total.
Entonces
Z = 5X1 + 4X2 + + 100Y1 + 200Y2 +
3X3 300Y3
Costo total
Costo total fijo
variable de
produccin
APLICACIONES DE VARIABLES BINARIAS
Restricciones. Tenemos dos tipos de restricciones
sobre las variables de desicin. Para satisfacer la
demanda diaria:
X1 + X2 + X3 = 3500
Para no sobrepasar el lmite de capacidad:
Proceso 1: X1 2000
Proceso 2 :X2 3000
Proceso 3 :X3 4000
Observe que si usamos cualquier proceso a un nivel
positivo, tenemos que garantizar que se ha incurrido
tanto en los costos fijos como en los costos variables de
produccin.
APLICACIONES DE VARIABLES BINARIAS
Esto es, por ejemplo, si X1 > 0 (usamos el proceso 1)
entonces Y1 = 1 ( tenemos que seleccionar el proceso 1).
Esto lleva a las siguientes relaciones entre las variables
continuas Xj y las variables entera Yj.
Para proceso 1:
Si Y1 = 0, entonces X1 = 0.
Si Y1 = 1, entonces X1 = 0 o X1 = 1
APLICACIONES DE VARIABLES BINARIAS
Para proceso 2 :
Si Y2 = 0, entonces X2 = 0.
Si Y2 = 1, entonces X2 = 0 o X2 = 1
Para proceso 3:
Si Y3 = 0, entonces X3 = 0.
Si Y3 = 1, entonces X3 = 0 o X3 = 1
APLICACIONES DE VARIABLES BINARIAS
Cada conjunto de tres restricciones dadas antes,
simultneamente con la correspondiente restriccin de
capacidad, pueden ser combinadas en una sola
restriccin.
Para el primer conjunto de tres restricciones (proceso 1)
consideremos la desigualdad
X1 2000Y1
Observe que la desigualdad tambin incluye la restriccin
de capacidad para proceso 1.
APLICACIONES DE VARIABLES BINARIAS
El modelo completo quedara:.
PROBLEMA DE PROGRAMACION ENTERA
Minimizar Z = 5X1 + 4X2 + 3X3 + 100Y1 + 200Y2 + 300Y3
Sujeto a:
X1 + X2 + X3 = 3500
X1 2000Y1
X2 3000Y2
X3 4000Y3
Yi es binaria para i = 1, 2, 3
Xi 0 para i = 1, 2, 3
APLICACIONES DE VARIABLES BINARIAS
EJEMPLO 3.- Problema de presupuesto de capital
Cierta compaa tiene la oportunidad de invertir el
prximo ao en cinco proyectos diferentes, P1, P2, P3, P4 y
P5, cada uno con un beneficio neto estimado y un costo
esperado de inversin que se muestra en la tabla .
Proyecto Beneficio neto esperado
( 000 s )
nmero
Costo esperado
( miles)
$ 100
$ 60
80
40
70
20
60
40
90
50
APLICACIONES DE VARIABLES BINARIAS
Los diferentes requerimientos de cada proyecto (mano de
obra, equipo, etc.), hacen que los costos varen de
proyecto a proyecto. Adems, las obligaciones de
requerimientos de flujo de caja exigen que la Cia. no
pueda invertir en todos los cinco proyectos.
La Cia. estima que tendr una disponibilidad de caja en la
cantidad de $150000 para el prximo ao.
APLICACIONES DE VARIABLES BINARIAS
a) En cuales proyectos podra invertir la Cia. el
prximo ao?
Variables de decisin
Yj = 1, si el proyecto j es seleccionado (j = 1, 2, 3, 4, 5).
0, si el proyecto j no es seleccionado
Y1, Y2, Y3, Y4 y Y5 Son variables binarias
APLICACIONES DE VARIABLES BINARIAS
Funcin objetivo
La meta de la Cia. es seleccionar los proyectos
que maximicen la utilidad total esperada.
Sea Z = utilidad total esperada, entonces la
funcin objetivo es
Maximizar Z = 100Y1 + 80Y2 + 70Y3 + 60Y4 + 90Y5
APLICACIONES DE VARIABLES BINARIAS
Restricciones sobre las variables de decisin.
Cantidad disponible para inversin:
60Y1 + 40Y2 + 20Y3 + 40Y4 + 50Y5 150
APLICACIONES DE VARIABLES BINARIAS
b) Suponga que la gerencia ha decidido que
exactamente un proyecto debe ser seleccionado
del conjunto de proyectos P1, P3 y P5. Pero, los
proyectos P2 y P4 pueden ser seleccionados
sujetos a la restriccin de presupuesto. Cul
restriccin (o restricciones) necesita ser
agregada al modelo original?
APLICACIONES DE VARIABLES BINARIAS
Solucin.- Ya que uno de P1, P3, P5 y solo uno,
puede ser seleccionado, exactamente una de las
tres variables Y1, Y3 o Y5 puede tomar el valor de
uno.
Y1 + Y3 + Y5 = 1. Restriccin a ser agregada
APLICACIONES DE VARIABLES BINARIAS
c) Suponga que la Cia. ha decidido que no ms
de uno de los dos proyectos, P2 y P4, puede ser
seleccionado.
Cul
restriccin
adicional
necesita ser agregada al modelo original?
Solucin
Y2 + Y4 1. Restriccin a ser agregada
APLICACIONES DE VARIABLES BINARIAS
d) Suponga que la Cia. ha decidido que si P 3 es
seleccionado, entonces P4 tiene que ser
seleccionada.
Cul
restriccin
adicional
necesita ser agregada al modelo original?
Solucin
Y3 Y4. Restriccin a ser agregada
APLICACIONES DE VARIABLES BINARIAS
RESUMEN DEL MODELO DE PROGRAMACION
ENTERA
Maximizar Z = 100Y1 + 80Y2 + 70Y3 + 60 Y4 + 90Y5
Sujeto a
60Y1 + 40Y2 + 20Y3 + 40Y4 + 50Y5 150
Y 1 + Y3 + Y 5 = 1
Proyecto Beneficio neto esperado
Costo esperado
(
000
)
nmero
( miles)
Y 2 + Y4 1
1
$ 100
$ 60
Y3 - Y4 0
2
80
40
Yi es binaria para
3
70
20
i = 1, 2, 3, 4, 5.
s
60
40
90
50
GRACIAS
Ing.
Luis
Medina
