Clase # 15
PROGRAMACIN ENTERA
FORMULACIN
1. PROGRAMACIN ENTERA: P.E.
Programacin Lineal con la restriccin adicional
de que los valores de las variables de decisin son
enteros. (vs suposicin de divisibilidad)
P.E Pura: Todas las variables de decisin tienen
valores enteros.
P.E Mixta (PEM): Algunas de las variables de
decisin tienen valores enteros. Las dems
toman valores reales o continuos (cumplen con la
suposicin de divisibilidad).
2. PROGRAMACIN BINARIA: P.B.
(Programacin Dual o Programacin 0-1)
Utiliza variables binarias:
Slo tiene 2 alternativas posibles
si la decisin j es si.
si la decisin j es no.
Xj =
Las Xj son variables de decisin restringidas a
tomar valores 0,1.
PEM: Panacea de la optimizacin
3. Ejemplo 1: Programacin Binaria
La CALIFORNIA MANUFACTURING CO.
est analizando la posibilidad de expansin.
Fbrica: Construccin de una fbrica en Los
Angeles o en San Francisco, o tal vez en ambas
ciudades
Almacn: Construccin de un almacn a lo
sumo, pero la decisin est restringida a que si
hay almacn es porque hay fbrica en ese sitio.
Veamos
# de
decisin Pregunta s o no
Variable VNP
Capital
de
Beneficio Requerido
decisin ($ milln) ($ milln)
Construir fbrica
en Los Angeles?
X1
Construir fbrica
en San Francisco?
X2
Construir almacn
en Los Angeles?
X3
Construir almacn
en San Francisco?
X4
Capital disponible: $10 millones
Formulacin del modelo:
Variables de decisin.
La variable de decisin Xj es tal que:
1 se construye.
Xj =
0 no se construye.
j = 1, 2, 3, 4.
14-6
Funcin objetivo.
Max Z = 9 X1 + 5 X2 + 6 X3 + 4 X4
Como las variables de decisin son
adimensionales, Z tiene unidades de
[$ millones]
Restricciones
Alternativas mutuamente excluyentes: max 1 almacen
X3 + X4 1
Alternativas condicionales o contingentes
X3 X1
X4 X2
Se construye el almacn solo
si se construye la fbrica
6X1 + 3X2 + 5X3 + 2X4 10
Capital
disponible
Xj [0,1] para j= 1, 2, 3, 4.
El modelo completo ser:
Max Z = 9 X1 + 5 X2 + 6 X3 + 4 X4
X3 + X4 1
+ X3
-X1
-X2
+ X4 0
6X1 + 3X2 + 5X3 + 2X4 10
Xj [0,1] para j= 1, 2, 3, 4.
4. VARIABLES AUXILIARES BINARIAS
4.1 Seleccionar una de dos restricciones.
Slo una (cualquiera) de las 2 restricciones
debe cumplirse. La otra puede o no cumplirse,
pero no se requiere que lo haga.
Aplicacin prctica:
Casos en que se tienen 2 tipos de recursos
alternativos para un cierto propsito.
Ejemplo:
o bien 3 X1 + 2X2 18
o X1 + 4X2 16
Veamos
X2
3 X1 + 2X2 = 18
8
7
6
5
4
X1 + 4X2 = 16
3
2
1
X1
0
10
12
14
16
Formulacin: Para lograr lo enunciado
anteriormente el modelo puede formularse as:
O una de las dos
Una de las dos
3 X1 + 2X2
18 + M
3 X1 + 2X2
18
X1 + 4X2
16
X1 + 4X2
16 + M
Esto se lleva a la forma equivalente
3 X1 + 2X2
18 + My
X1 + 4X2
16 + M (1-y)
y [0,1]
4.2 Deben cumplirse K de N restricciones.
Seleccionar K de N restricciones
Considere la situacin en la que el modelo
completo incluye un conjunto de N
restricciones posibles entre las que slo K de
ellas se deben cumplir. (suponga que K < N).
Las N-K restricciones que no se eligen quedan
eliminadas del problema, aun cuando por
coincidencia las soluciones factibles puedan
satisfacer algunas de ellas.
Veamos
Se tienen N restricciones del tipo
f1 ( x1 , x2 , ........., xn ) d1
f2( x1 , x2 , ........., xn ) d2
fN( x1 , x2 , ........., xn ) dN
14-14
La formulacin equivalente del requerimiento de
que K de estas restricciones se deban cumplir ser:
f1 ( x1 , x2 , ........., xn ) d1+ My1
f2( x1 , x2 , ........., xn ) d2 + My2
fN( x1 , x2 , ........., xn ) dN + MyN
N
i=1 yi = N-K
Yi = 0 indica que la
restriccin se cumple
yi [0,1] para i = 1, 2, ..., N.
14-15
4.3 Funciones con N valores posibles.
Considere la situacin en la que una funcin
dada tome cualquiera de N valores dados.
Denotemos este requisito as:
f ( x1 , x2 , ..., xn ) = d1 , o d2 , ..., o dN
El caso especial en que f(x) sea lineal, se tiene:
f (x1, x2, ..., xn ) =
ajj=1
Xj = d1 o d2 ...
sigue
14-16
La formulacin equivalente
requerimiento ser:
de
este
f ( x1 , x2 , ........., xn ) = d y
j
j=1 j
N
i=1 yi = 1
yi [0,1] para i= 1,2,....., N.
14-17
4.4 El Problema de costo fijo.
Es bastante comn incurrir en un costo fijo cuando se
emprende una actividad.
Por ejemplo: Cuando se inicia una corrida de un lote
de produccin y deben prepararse las instalaciones.
(existen algunos costos fijos y otros variables).
El costo total de la actividad j puede representarse
por una funcin de la forma:
fj (Xj) =
kj + cjXj
si Xj > 0
si Xj = 0
sigue
14-18
La F. O.: Minimizar Z = f1(x1)+ f2(x2) + ... + fn(xn)
Puede expresarse como:
n
Min Z =
j=1(cjXj + kjYj)
Usando variables auxiliares binarias
Yj =
1
0
si Xj > 0
si Xj = 0 .
s. a.
Restricciones originales
Xj MYj
Yj binaria
14-19
4.5. Condicionales de umbral
Para que cierta variable X1 pueda tomar un valor positivo,
es necesario que otra variable X2 exceda cierto valor
umbral a
X1 MY
X2 aY
Donde M es un nmero positivo grande
Y es una variable binaria.
Si Y =1 X2 ,cumple el umbral
20
4.6. Intervalos de Encendido-Apagado(On-Off)
X tome el valor de 0 est en el intervalo fijo
entre a y b.
ay X by
y es una variable binaria.
Si y =1, X est en el rango, de lo contrario es 0
21
5. Ejemplo 2: P.E.M
La divisin de investigacin y desarrollo de una
compaa manufacturera ha desarrollado 3 nuevos
productos y dispone de 2 plantas para fabricarlos.
Se quiere evitar la diversificacin excesiva de la lnea
de productos y por ello solo se fabricarn mximo 2
de los 3 productos desarrollados, y slo se utilizar
una de las plantas.
sigue
14-22
Horas por unidad
Horas disponibles
de Producto
Planta
por semana
30
40
Miles de US$
Unidades por semana
Ganancia
unitaria
Ventas
potenciales
Pasemos ahora a formular el modelo
14-23
Variables de decisin.
Xj: Tasa de produccin del producto j
J = 1, 2, 3
Funcin objetivo.
Max Z = 5X1 + 7X2 + 3X3
14-24
Restricciones
3X1+ 4X2 + 2X3 30
Planta 1
4X1+ 6X2 + 2X3 40
Planta 2
X1
X2
producto 1
producto 2
X3 9
producto 3
Xj 0 para j = 1, 2, 3.
14-25
Not UD algo raro
en la formulacin del modelo?
Faltan restricciones !!!
CULES?
Pueden usarse variables binarias para formular
adecuadamente algunas restricciones.
Veamos
14-26
Recuerde que slo se pueden fabricar hasta 2 de
los 3 productos.
Se introducen 3 variables auxiliares binarias:
y1, y2, y3 tales que:
1 si Xj > 0 se puede cumplir
Yj =
(se puede producir j)
0 si Xj = 0 se debe cumplir
(no se puede producir j)
para j = 1, 2, 3.
sigue
14-27
Con la ayuda de la M grande puede obtenerse:
X1 My1
X2 My2
X3 My3
y1+ y2 + y3 2
yi es binaria para i = 1, 2, 3
14-28
Recuerde que slo se puede utilizar una de
las 2 plantas.
Se introduce la variable binaria y4 tal que:
1
Y4=
si
4X1+ 6X2 + 2X3 40
Debe cumplirse (se elige la planta 2)
si
3X1+ 4X2 + 2X3 30
Debe cumplirse (se elige la planta 1)
sigue
14-29
Con la ayuda de la M grande puede obtenerse:
3X1+ 4X2 + 2X3 30 + My4
4X1+ 6X2 + 2X3 40 + M (1- y4)
y4 es binaria
La formulacin del modelo completo ser:
14-30
Max Z = 5X1 + 7X2 + 3X3
s.a
X1
7
5
X2
X1
0 X
2
X3
- My1
- My2
X3 - My3
0
0
y1+ y2 + y3
3X1+ 4X2 + 2X3 - My4
30
4X1+ 6X2 + 2X3 - M(1- y4)
40
yi es binaria para j = 1, 2, 3, 4
Xj 0 para todo j
14-31