Programación entera: Variables
Programación lineal entera:
Modelos de programación lineal entera pura
Modelos de programación lineal entera mixta
Introducción
Muchas veces, algunas o todas las variables de decisión
deben restringirse a valores enteros.
Por ejemplo:
– El número de aeronaves que se compró este año.
– El número de máquinas que necesita para
producción.
– El número de viajes que ha realizado un agente de
ventas.
– El número de policía que se asignó a la vigilancia
nocturna.
Introducción
• Variables enteras son requeridas cuando el modelo
represente una única decisión (no una operación en
proceso).
• Los modelos de Programación Lineal Entera (PLE) son
mucho más difíciles de resolver que los modelos de
Programación Lineal (PL).
• Los algoritmos que resuelven los modelos lineales
enteros no entregan resultados de análisis de
sensibilidad.
Clasificación
Los modelos de PLE pueden clasificarse como sigue:
– Solo de enteros, es decir, todas las variables se
restringen a enteros.
– De binarios, todas las variables son 0 o 1.
– De variables mixtas, algunas variables son
enteras, pero no todas.
Programación entera: Variables
Actividades
• Los alumnos evalúan distintos casos para
que determinen cuáles de ellos
corresponden a los modelos de
Programación lineal entera y a qué tipo
corresponden.
Programación entera: Problema ejemplo
Una empresa está pensando invertir en cuatro proyectos diferentes,
cada proyecto se finaliza a lo más en 3 años.
Los flujos de caja requeridos en cada año junto con el Valor Presente
Neto de cada proyecto, concluidos los años de ejecución, y las
disponibilidades de recursos financieros se resumen en la siguiente
tabla:
Proy 1 Proy 2 Proy 3 Proy 4 Disp. Recursos
Año 1 10 8 6 12 30
Año 2 8 15 4 0 15
Año 3 18 0 16 0 12
V.P.N. 35 18 24 16
Interesa determinar en cuáles proyectos invertir de modo de conseguir el
mayor V.P.N. de la inversión.
En este caso, la decisión a tomar es invertir o no invertir en los proyectos. Se
verá cómo se plantearía el modelo.
Programación entera: Variables de decisión
𝟏, 𝒔𝒊 𝒔𝒆 𝒊𝒏𝒗𝒊𝒆𝒓𝒕𝒆 𝒆𝒏 𝒆𝒍 𝒑𝒓𝒐𝒚𝒆𝒄𝒕𝒐 𝒊
𝒙𝒊 = 𝒄𝒐𝒏 𝒊 = {𝟏, 𝟐, 𝟑, 𝟒}
𝟎, 𝐬𝐢 𝐧𝒐 𝒔𝒆 𝒊𝒏𝒗𝒊𝒆𝒓𝒕𝒆 𝒆𝒏 𝒆𝒍 𝒑𝒓𝒐𝒚𝒆𝒄𝒕𝒐 𝒊
Si >= 0, Cantidad no invertida en el periodo i (i=1,2)
Programación entera: Problema ejemplo
Función objetivo:
Max 35x1 + 18x2 + 24x3 + 16x4
Restricciones (tres alternativas):
1) Reinvirtiendo el dinero no utilizado en un período:
Año1: 10x1 + 8x2 + 6x3 + 12x4 + s1 = 30
Año2: 8x1 + 15x2 + 4x3 + s2 = 15 + s1
Año3: 18x1 + 16x3 + s3 = 12 + s2
xi {0,1} i = 1,2,3,4
Sj>=0 j=1,2,3
Programación entera: Problema ejemplo
Función objetivo:
Max 35x1 + 18x2 + 24x3 + 16x4
Restricciones (tres alternativas):
2) Sin invertir el dinero no utilizado en un período, pero utilizando el
retorno de los proyectos concluidos:
Año1: 10x1 + 8x2 + 6x3 + 12x4 30
Año2: 8x1 + 15x2 + 4x3 15 + 16x4
Año3: 18x1 + 16x3 12 + 18x2
xi {0,1} i = 1,2,3,4
Programación entera: Problema ejemplo
Función objetivo:
Max 35x1 + 18x2 + 24x3 + 16x4
Restricciones (tres alternativas):
3) Reinvirtiendo el dinero no utilizado en un período y, también el
retorno de proyectos concluidos:
Año1: 10x1+ 8x2 + 6x3 + 12x4+ s1 = 30
Año2: 8x1 + 15x2+ 4x3 + s2 = 15 + s1 + 16x4
Año3: 18x1 + 16x3 + s3 = 12 + s2 + 18x2
xi {0,1} i = 1,2,3,4
Sj>=0 j=1,2,3
Programación entera: Problema ejemplo
Aumentando nuevas restricciones:
a) Se debe invertir en al menos 1 de los 3 primeros proyectos:
x1 + x2 + x3 >= 1
b) El proyecto 2 no puede ser tomado a menos que el proyecto 3 sí
sea tomado:
x2 <= x3
c) Se puede tomar el proyecto 3 ó 4 pero no ambos:
x3 + x4 <= 1
d) No se puede invertir en más de dos proyectos:
x1 + x2 + x3 + x4 <= 2
Programación entera: Problema ejemplo
Una universidad está programando las clases para el próximo
semestre académico y requiere buscar la mejor asignación posible de
profesores a los distintos cursos que se deben dictar. Considere que
existen 5 profesores: A, B, C, D, E y 5 cursos (asignaturas): C1, C2,
C3, C4, C5. Adicionalmente, los profesores han manifestado sus
preferencias por dictar los distintos cursos en una escala de 1 a 10,
donde 10 es la máxima puntuación y 1 la mínima puntuación o
preferencia. Se asume que cada profesor es apto para dictar cualquier
curso, independiente del puntaje de su preferencia. La siguiente tabla
resume las puntuaciones que asigna cada profesor a cada curso:
PROFESORES
CURSOS A B C D E
C1 5 8 5 9 7
C2 7 2 3 6 8
C3 9 10 8 9 8
C4 8 7 9 7 8
C5 6 9 9 10 5
Programación entera: Problema ejemplo
Se ha establecido como criterio que cada profesor debe dictar sólo un
curso y a la vez que cada curso obviamente debe tener un profesor. En
base a lo anterior se desea encontrar la asignación de profesores que
maximice el total de las preferencias.
Variables de Decisión:
Programación entera: Problema ejemplo
Función Objetivo: Maximizar el total de las preferencias de los
profesores
Donde P(i,j) corresponde a una forma sintética de resumir los
parámetros del modelo, es decir, P(i,j) es la preferencia del profesor i
(en una escala de 1 a 10) por dictar el curso j. Por ejemplo, P(D,C3)=9.
Restricciones:
Programación entera: Lote Mínimo
Condición: Si un determinado producto “A” se fabrica, deben producirse al
menos m unidades y como máximo M unidades. Entonces entre las
restricciones del problema encontraremos:
Xa ≤ M Ia
Xa ≥ m Ia
La variable Ia es entera binaria y solo puede adoptar los valores 0 ó 1.
La variable M es un número cuyo valor es sustancialmente mayor al resto de los
valores del modelo o una cota superior para el valor de Xa.
El valor m es la cantidad mínima a fabricar de Xa cuando se produce alguna
unidad de Xa.
Es decir que Xa puede ser: Xa = 0 ó m ≤ Xa ≤ M
Cuando Ia = 0 las restricciones se reducen a: Xa ≤ 0 y Xa ≥ 0 con lo que Xa = 0.
Cuando Ia = 1 las restricciones se reducen a Xa ≤ M y Xa ≥ m.
Programación entera: Lote Mínimo
El siguiente es un ejemplo de cómo debe incorporarse a un modelo de PL la
condición: X2 = 0 ó 4000 ≤ x2 ≤ 10000.
Max Z= 8 x1 + 5 x2
Restricciones:
1 x1 + 4 x2 < 32000
4 x1 + 3 x2 < 37000
3 x1 - 2 x2 < 15000
2 x1 + 1 x2 > 4000
x2 < = 10000 Ia
x2 > = 4000 Ia
NN: x1 y x2 >= 0; Ia ϵ {0,1}
Programación entera: Exclusión de Alternativas
Se exige que de entre dos o más productos solamente se fabrique uno de
ellos.
Entre las restricciones del problema encontraremos:
Xa ≤ M*Ia
Xb ≤ M*Ib
Ia + Ib = 1
Las variables Ia e Ib son enteras binarias y solo pueden adoptar los valores 0 ó
1.
La variable M es un número cuyo valor es sustancialmente mayor al resto de
los valores del modelo o una cota superior para los valores que puedan
adoptar Xa y Xb.
Como Ia + Ib = 1, Ia e Ib no pueden ser simultáneamente iguales a 1.
Si Ia = 1; entonces Xa ≤ M y Xb = 0
Si Ib = 1; entonces Xb ≤ M y Xa = 0
Programación entera: Exclusión de Alternativas
El siguiente es un ejemplo cómo debe incorporarse la condición
de exclusión para dos productos.
Max 8 x1 + 5 x2
Restricciones:
1 x1 + 4 x2 < 32000
4 x1 + 3 x2 < 37000
3 x1 - 2 x2 < 15000
2 x1 + 1 x2 > 4000
x1 <= 100000*Ia
x2 <= 100000*Ib
Ia+Ib=1
NN: x1 y x2 >= 0; Ia, Ib ϵ {0,1}
Programación entera: Activación de Restricciones
Puede ser de interés que una restricción exista en el modelo si se están
produciendo unidades de determinado producto, y que la restricción esté
ausente si no se están produciendo unidades de ese producto.
Entre las restricciones del problema encontraremos:
Xa ≤ M*Ia
Σ aj Xj ≤ (1- Ia)*M+ b
Como en los casos anteriores, la ecuación Xa – M Ia ≤ 0 (con Ia binaria y
entera) hace que Ia sea igual a 1 solamente cuando Xa es distinto de cero.
Cuando Ia=1 la restricción se reduce a:
Σ aj Xj ≤ b
Cuando Ia=0 la restricción queda como:
Σ aj Xj ≤ M + b
Siendo M un número muy grande en comparación con el resto de los
coeficientes del modelo, la restricción queda en la práctica inactiva.
Programación entera: Activación de Restricciones
El siguiente es un ejemplo de cómo debe incorporarse la condición de
Activación de Restricciones..
Max 8 x1 + 5 x2
Restricciones:
1 x1 + 4 x2 < 32000
4 x1 + 3 x2 < 37000
2 x1 + 1 x2 >4000
3 x1 - 2 x2 < =15000 + 100000(1- Ia)
x2 <= 100000 Ia
NN: x1 y x2 >= 0; Ia ϵ {0,1}
Programación entera: Costos Fijos
Es posible que existan costos fijos atribuibles a un determinado producto.
Es decir, costos que existen si se produce alguna unidad de ese producto y
que no existen en caso contrario.
Aquí también puede recurrirse al empleo de variables enteras binarias para
modelar la situación.
El funcional deberá incluir una variable entera binaria multiplicando al
coeficiente que representa los costos fijos:
Z = a1 x1 + ..... aj xj + CF Ij + ....an Xn.
Entre las restricciones encontraremos: xj ≤ M Ij
De esta forma si xj es mayor que cero se activa Ij adoptando el valor 1 y el
coeficiente CF aparecerá en el funcional.
En caso contrario si xj = 0 la variable entera Ij = 0 y el coeficiente CF no
aparece afectando al funcional.
Programación entera: Activación de Restricciones
Decisiones contingentes:
X3-X1<=0
Además, X3 y X1 ϵ {0,1}
Activar una u otra restricción:
3X1 + 2X2 <= 18 + Ia M
X1 + 4X2 <= 16 + (1-Ia)M
M muy grande y Ia ϵ {0,1}
Ejemplo Adicional de Aplicación
Una empresa de juguetes está considerando la puesta en marcha de tres nuevos modelos de juguetes (1,
2 y 3) para su posible inclusión en la próxima campaña de Navidad.
La preparación de instalaciones para la fabricación de estos modelos costaría 25000 €, 35000 € y 30000 €
respectivamente, y la ganancia unitaria sería de 10 €, 15 € y 13 € respectivamente.
La empresa dispone de tres plantas de producción para la elaboración de estos modelos, pero para evitar
gastos sólo en una de ellas se producirían los juguetes, dependiendo la elección de la maximización de las
ganancias.
El número de horas que se precisa para producir cada juguete en cada planta es:
Las plantas disponen al día 500, 600 y 630 horas de producción respectivamente.
La gerencia ha decidido desarrollar al menos uno de los tres juguetes.
Elaborar un modelo de programación lineal para el caso propuesto maximizar el beneficio total.
