Programas Lineales de Enteros 0 - 1 Estas variables están referidas con frecuencia como variables binarias. En muchas aplicaciones, las variables binarias pueden ser de mucha utilidad para modelar situaciones de todo-o- nada. Algunos ejemplos podrían incluir el tomar en cuenta un costo fijo, construir una nueva planta, o comprar un novel mínimo de cierto insumo para recibir descuento por cantidades.

Ejemplo: Considere el Siguiente Problema del Morral Maximizar 11X1 + 9X2 + 8X3 + 15X4 Sujeto a: 4X1 + 3X2 + 2X3 + 5X4 8, y cualquier Xi es 0 ó 1. Dado que este es un problema pequeño en tamaño, existen 4 variables que cada una puede tener 2 valores, existen 24 = 16 posibilidades. Probando todas las 16 posibilidades de forma tal de identificar una solución óptima (si es que existe alguna) es un trabajo tedioso. Por lo tanto se debería utilizar el software de Programación Lineal de Enteros para resolver este problema y otros de mayor escala.

El Problema de Viaje del Vendedor Un vendedor debe visitar las ciudades 1, 2,..n, y su viaje comienza y debe finalizar en Ciudad Hogar. Dejemos que Cij sea el costo de viajar de la ciudad i a la ciudad j, el cual es dado. El problema es determinar una orden óptima para viajar las ciudades de tal forma que el costo sea mínimo. Considere el siguiente Problema de Viaje del Vendedor:

La formulación de programación lineal es: Min 30x01 + 45x02 +65x03+ 80x04 + 25x12 + 50x13+ 50x14+ 40x23+ 40x24 + 35x34 +30X10 +45X20+ 25X21 +65X30 + 50X31+ 40X32 + 80X40+ 50X41+ 40X42 +35X43

Sujeto a:X01+ X02+ X03+ X04=1X01+ X02+ X03+ X04=1

x10+ x12+ x13+ x14=1x20+ x21+ x23+ x24=1x30+ x31+ x32+ x34=1x40+ x41+ x42+ x43=1X10+ X20+ X30+ X40=1X01+ X21+ X31+ X33=1x02+ X12+ X32+ X42=1X03+ X13+ X23+ X43=1X04+ X14+ X24+ X34=1Todos los Xij = 0, ó 1

La solución a este problema de programación lineal produce los sub-viajes (0, 1, 2). Necesitamos introducir un rompedor de viajes tal como

X01 + X10 + X12 + X21+ X02 + X20 2Agregando esta restricción adicional y resolviendo, necesitamos otro rompedor de viaje, el cual es:

X01 + X10 1,Agregando este, el camino óptimo es: Ciudad Hogar a la ciudad 1, de ciudad 1 a ciudad 2, de ciudad 2 a ciudad 4, de ciudad 4 a ciudad 3 y de ciudad 3 a ciudad hogar, con una longitud total de 195 unidades.

Aplicaciones al Presupuesto de Capitales Suponga que una compañía de Investigación y Desarrollo (R & D) tiene una cantidad de dinero disponible para invertir de D Dólares. La compañía ha determinado que existen N proyectos de inversión alternativas y que por lo menos dj dólares deben ser invertidos en el proyecto j si se decide que dicho proyecto amerita la inversión. La ganancia neta que la compañía podría obtener si invierte en el proyecto j es Pj dólares. El dilema de la compañía es que no puede invertir en todos los N proyectos porque dj D. Por lo tanto, la compañía debe decidir en cual proyecto invertir de forma tal de maximizar su utilidad. Para resolver este problema al asesor formula el siguiente problema: Dejemos que Xj = 1, si la compañía invierte en el proyecto j, y Xj = 0 si no lo hace.El monto total a ser invertido es por lo tanto dj Xj, y dado que este monto no puede exceder D dólares, tenemos la restricción siguiente:

dj Xj D La utilidad total será Pj Xj. Por lo tanto la compañía desea un problema 0-1: Maximizar Z= Pj Xj

Sujeto a: dj Xj D, Xj = 0, OR 1.

Problemas de Horarios Para utilizar el trabajo como recurso lo más eficiente posible, es importante analizar los requerimientos de mano de obra varias veces al día. Esto es especialmente cierto en grandes compañías en las cuales las demandas de los clientes son repetitivas, pero cambian significativamente durante diferentes horas. Por ejemplo, se necesitan más operadores telefónicos durante el horario comprendido desde el medio día hasta las 2:00p.m. y también desde la media noche hasta las 2:00 a.m. Sin embrago, muchos de estos operadores deben estar en servicio desde tempranas horas de la mañana. Dado que dichos empleados normalmente trabajan jornadas de 8 horas de trabajo, sería posible planificar sus horarios de trabajo de tal manera que una simple jornada pueda cubrir dos o más de estos “periodos pico” de demanda. Mediante el diseño de horarios inteligentes, la productividad del operador incrementaría, generando un grupo de trabajo menos numeroso, y una reducción de gastaos de nómina. Entre otros ejemplos en el cual los modelos de horario de empleados tienen bastante utilidad se encuentran los conductores de autobuses, controladores de tráfico aéreo, y las enfermeras. El

siguiente es un ejemplo de problema y desarrollo de un modelo de programación lineal para el horario de trabajo de enfermeras. Los hospitales enfrentan constantemente problemas con el horario de trabajo de sus enfermeras. Un modelo de planificación de horarios es un problema de programación de enteros para minimizar el número total de trabajadores sujeto a un número específico de enfermeras durante cada período del día.

Período Turno del DíaNúmero

Requerido de Enfermeras

1 8:00 - 10:00 102 10:00 - 12:00 83 12:00 - 02:00 94 02:00 - 04:00 115 04:00 - 06:00 136 06:00 - 08:00 87 08:00 - 10:00 58 10:00 - 12:00 3

Dado que cada enfermera trabaja jornadas de 8 horas diarias, el/ ella puede comenzar a trabajar al comienzo de cualquiera de los primeros cinco períodos: 8:00, 10:00, 12:00, 2:00 ó 4:00. En este ejemplo, no consideramos los períodos que comienzan a en horas impares tales como las 9:00, 11:00, etc. Adicionalmente, no se necesita ninguna enfermera que comience a trabajar después de las 4:00, dado que su horario se extendería hasta después de la media noche cuando no son necesarias. Cada período es de 2 horas, por lo tanto cada enfermera que se presente a trabajar en el período t trabajará también t + 1, t + 2, y t + 3 --- es decir, 8 horas consecutivas. La pregunta es: ¿Cuantas enfermeras se deben reportar a trabajar durante cada período de forma tal de cumplir los requerimientos especificados en la tabla anterior? Para modelar este problema, dejemos que Xt sea la variable de decisión la cual denota el número de enfermeras que comenzaran a trabajar en el período t. La fuerza laboral total, la cual deseamos minimizar es Xt. Durante el período de tiempo 1, por lo menos 10 agentes deben estar al servicio, por lo tanto debemos tener X1 10. Similarmente, los requerimientos en el período 2 solo pueden ser cubiertos por X1 + X2 8. De esta forma, escribimos los requerimientos para los períodos restantes. Estos son:

X1 + X2 + X3 9,X1 + X2 + X3 + X4 11, X2 + X3 + X4 + X5 13, X3 + X4 +X5 8, X4 + X5 5, X5 3, Todas las variables son enteros.

Note que X1 no es incluida en la restricción para el período de tiempo 5, dado que las enfermeras que comienzan en el período 1 no están trabando para el período 5. Adicionalmente, observe que podría ser necesario tener un número mayor de enfermeras que el requerimiento en algunos períodos. Por ejemplo, vemos que la primera restricción muestra que el número de enfermeras que comienzan a trabajar en el período 1 debe ser por lo menos 10. Todas estas enfermeras estarán trabajando para el período 2, pero solo 8 agentes las requieren. Por lo tanto igualmente si X2 = 0, existirán 2 enfermeras extras trabajando durante el período 2.

Enfermeras Requeridas por Turno

 Comienzo de Turno 8-10 10-12 12- 2 2- 4 4- 6 6- 8 8-10Enfermeras Requeridas 10 8 9 11 13 8 5 Enfermeras Asignadas 10 10 18 20 13 13 5 Variable X1 X2 X3 X4 X5 X6 X7

Enfermeras Comenzando en Turno 10 0 8 2 3 0 0                Total de Enfermeras Requeridas 23            

               

Aplicaciones al Mercadeo Suponga que existen 5 periódicos diferentes que son publicados en cierto país, cada periódico cubre algunas de las nueve regiones del país, tal y como es mostrado en la tabla siguiente

# de Periódico

Región Cubierta

Costo por Publicidad

Beneficios por Publicidad

12345

1,2,32,3,64,5,65,7,86,8,9

34375

1210141916

El problema del gerente de mercadeo es encontrar el costo mínimo total de forma tal que la publicidad alcance a todas las áreas del país. Este problema puede ser formulado como una programación lineal de tipo 0- 1:

Minimizar   C = 3y1 +  4y2 + 3y3 + 7y4 + 5y5

s.a.              y1    1       (Región 1)                    y1   +   y2    1       (Región 2)                                y1         +    y2    1       (Región 3)                    y3           1       (Región 4)                                      y3   +   y4    1       (Región 5)                              y2 + y3             + y5    1       (Región 6)                                                  y4      1       (Región 7)                                                  y4 + y5    1       (Región 8)                                                          y5    1       (Región 9)                                       yj = 0 ó 1,  para todos los j's

La solución óptima es hacer publicidad en los periódicos 1, 3, 4, y 5 con un costo total de $18,00. Esta solución es el costo mínimo asociado con la cobertura en cada una de las nueve áreas.

El Problema de Recorte de Reservas Suponga que un almacén de maderas ofrece laminas de 10 metros, las cuales son cortadas en 3 metros, 4 metros y 5 metros dependiendo de las exigencias de los clientes. La lámina de madera de 10 metros puede ser cortada en 6 patrones sensibles tal y como se muestra en la tabla siguiente:

Patrón # 3 metros 4 metros 5 metros Desperdicio (Mts.)

1 3 0 0 12 2 1 0 03 1 0 1 24 0 1 1 15 0 2 0 26 0 0 2 0

Existen otros patrones posibles pero que no son sensibles; por lo tanto, se podría cortar una lámina de madera de 10 metros en una de 3 metros y una de 4 metros dejando un desperdicio de 3 metros. Esto no tendría sentido dado que 3 metros de desperdicio podrían ser utilizados como una pieza de 3 metros, así como se muestra en el patrón 2. Si algún cliente ordena 50 láminas de 3 metros, 65 de 4 metros, y 40 de 5 metros. La pregunta sería cuantas láminas de 10 metros se necesitan para cortar estas órdenes, y que patrón se debería utilizar? Para modelar este problema de decisión, denotemos por yj el número de láminas de 10 metros a cortar de acuerdo al patrón j, j =1, ... , 6. Sea la demanda 50(3) + 65(4) + 40(5) = 610 metros, la cantidad de láminas realmente cortadas es:

10(y1 + y2 + y3 + y4 + y5 + y6), y por lo tanto el desperdicio total es:

10(y1 + y2 + y3 + y4 + y5 + y6) - 610. Esto implica que cuando nosotros:

Minimizamos y1 + y2 + y3 + y4 + y5 + y6, el número total de láminas de 10 metros que necesitan ser cortadas, también minimizamos el desperdicio total, y vise versa. El número real de láminas de 3 metros obtenidas en el proceso de cortar es:

3y1 + 2y2 + y3, y por lo tanto:

3y1 + 2y2+ y3 50 debe mantenerse con el objetivo de satisfacer la demanda por láminas de 3 metros. De forma similar,

y2 + y4 + 2y5 65 para satisfacer la demanda de láminas de 4 metros y

y3 + y4 + 2y6 40para las láminas de 5 metros. Dado que las variables yj deben ser enteros no negativos, j = 1, ... 6, podemos resumir la formulación de cortar las reservas como:

P: Min   z = y1 +  y2 + y3 + y4 + y5 + y6                (Láminas de 10 metros)s.t.             3 y1 + 2y2 + y3    50      (Láminas de 3 metros)                            y2     +    y4 + 2y5    65      (Láminas de 4 metros)                                   y3 + y4     + 2y6    40     (Láminas de 5 metros)    yj son enteros no negativos, j = 1, .., 6

La solución óptima a este problema, utilizando software, es cortar un total de 65 láminas de 10 metros y utilizar 25 veces el parámetro # 2 y 20 veces cada uno de los parámetros #5 y #6. El desperdicio total sería 25 x 0 +20 x 2 + 20 x 0 = 40 metros. El ejemplo anterior ilustra una instancia simple del problema de cortar reservas o cortar pérdidas, el cual es ampliamente utilizado cuando se debe minimizar la cantidad de desperdicio. Este ejemplo se refiere a una situación unidimensional (la longitud de la lámina).

Una Aplicación a la Ingeniería: Mezclando Substancias Una compañía de químicos esta produciendo dos tipos de sustancias (A y B) que requieren tres tipos de materia prima (I, II, y III). Los requerimientos en la composición de las tres sustancias así como también la utilidad son mostrados a continuación:

Sustancia ComposiciónUtilidadpor kg

A No mas de 20% de I No mas de 10% de II Por lo menos 20% de III

10

B No mas de 40% de I No mas de 50% de III 8

La cantidad de material disponible así como también los costos de tratamiento se muestran a continuación:

Materia Prima Monto Disponible (Kg) Costos de Procesamiento /Kg

I 400 4II 500 5III 300 6

El problema de la compañía es encontrar cuanta sustancia producir, y a que nivel de composición de forma tal de maximizar la utilidad. Dado que tenemos 2 sustancias y tres materiales, introducimos 6 (=2 x 3) variables de decisión xij, i = A, B, y j = I, II, III. Por ejemplo, xBIII es el monto de materia prima III en la sustancia B. La función objetivo es maximizar la utilidad menos los costos de procesamiento: max 10(xAI+xAII+xAIII) + 8(xBI+xBII +xBIII) - 4(xAI +xBI) - 5(xAII +xBII) - 6(xAIII+xBIII) Re-escribiendo esto en términos de las 6 variables de decisión, el problema equivalente es: max: 6xAI + 5xAII + 4xAIII + 4xBI + 3xBII + 2xBIII Las restricciones de materiales son: xAI + xBI         400xAII + xBII       500xAIII + xBIII      300. La composición de lasa restricciones son: 0,2(xAI + xAII+ xAIII)          xAI 0,1(xAI + xAII + xAIII)          xAII 0,2(xAI + xAII + xAIII)          xAIII 0,4(xBI + xBII + xBIII)          xBI 0,5(xBI + xBII + xBIII)          xBIIII De la primera desigualdad en la tabla anterior, se puede derivar la restricción siguiente: 0 -0,8xAI + 0,2xAII + 0,2xAIII Por lo tanto nuestro problema tiene cinco restricciones de la tabla anterior mas tres restricciones de materiales, y una función objetivo. Adicionalmente, requerimos que las variables de decisiones, xij, tome solo valores de enteros no-negativos. Utilizando su paquete de computadora, la solución óptima es: xAI = 85, xAII = 42, xAIII = 299, xBI = 306, xBII = 458, xBIII = 1, con una ganancia total de 4.516. Esto significa que la compañía debería producir 426 kg de la sustancia A y 765 kg de la sustancia B. De los 400 kg del material I solo 391 kg es usado, mientras que todos los 500 kg del material II y todos los 300 kg del material III son utilizados