Capitulo 9 Programacion lineal entera 9.1 INTRODUCCION Los programas lineales enteros (PLE) son programas lineales en los cuales algunas o todas las variables estén restringidas a valores enteros (0 discretos). A pesar de décadas de exten- sas investigaciones, la experiencia de los cdlculos con PLE ha sido algo menos que satisfac- toria. A la fecha, no existe un programa de computadora de PLE que pueda resolver fos problemas de programacién entera de una manera uniforme, Este capitulo empieza con aplicaciones ilustrativas de la programacién entera y des- presenta los algoritmos de PLE. pu 9.2 APLICACIONES ILUSTRATIVAS En esta secci6n, fas aplicaciones de PILE empiezan con simples formulaciones y después avanzan a otras mas complejas. Por conveniencia, definimos un problema de emteros puro como uno en el cual todas las variables son enteros, $i sGlo algunas de las variables son en- teros, el problema es un programa de enteros mixto. Ejemplo 9.2-1 (PRESUPUESTO DEL CAPITAL.) Se estén evaluando cinco proyectos a lo largo de un horizonte de planificacién de tres afios. La siguiente tabla proporciona las utilidades esperacas para cada proyecto y los egresos anuales asociados, 367368 Cap.9 Programacién lineal entera Egresos (millones de délares)/anuales Utilidades Proyecto 1 2 3 (millones de 46 1 0 4 7 10 40 2 s) 9 2 20 . 7 4 1 15 8 6 10 30 “Fondos disponibles 25 (millones de délares) Determine los proyectos que se van a ejecutar a lo largo del horizonte de tres aftos. El problema se reduce a una decisi6n de “si-no” para cada proyecto. Defina la variable bi- 1, El proyecto j esta seleccionado 0, El proy cto j no esta seleccionado Por consiguiente, el modelo de PLE se da como Maximice z= 20x, + 40x, + 20x, + 15x, + 305 sujeta a Sx, + 4x; +345 + Tea t Bxy x) + Te, + 9x + axy + bry Br + 10x, + Oxy ry + 10K, My Xn By te =O, 1) La solucién entera 6ptima (obtenida con TORA) €s &) =x z= 95 (mi- Hones de détares). Le solucién muestra que se deben seleccionar todos los proyectos, menos el 5 Es interesante comparar Ja funcin continua de PL con la solucién de PLE. La éptima de la PL, que se obtiene reemplazando x, = (0,1) con 0 = x, = 1 para todas las j, nos da x, =.3789, 2 =) =.x,= 1,5 =.7368 y z = 108.68 (millones de délares).La solucién carece de significado, debido a que dos de las variables asumen valores fraccionales. Nos podemos sentir tentados a redon- dear la solucién, que nos da x; = x, = 1. La solucién resultante no es factible, debido a que se violan las restricciones. Més importante atin es que el concepto del redondeo no aplica aqui debido a que x, representa la decisién de “si-no”, para Ia cual los valores fraccionales carecen de significado.Sec.9.2 Aplicaciones ilustrativas 369 Serie de problemas 9.2a" 1, Enel modelo de presupuesto de capital del ejemplo 9.21, supongamos que se debe seleccionar el proyecto 5 si se selecciona cualquiera de los proyectos 1 0 3, Modi- fique el modelo para que incluya la nueva restriccién y encuentre la soluciGn éptima con TORA. 2. Cinco articulos deben ser cargados en un navio. El peso w,y el volumen 2, junto con el valor r, para el articulo i se tabulan a continuacién. Peso por unidad, Volumen por unidad, Valor por unidad, Articuloi ww, (toneladas) (a) 7, (100 délares) tS 4 4 2 8 8 7 3 3 6 6 4 2 El peso y el volumen maximo permitidos para la carga son 112 toneladas y 109 yd°, respectivamente. Formule el modelo de PLE y encuentre la carga mas valiosa utilizando TORA. Suponga que tiene siete botellas de vino Ilenas, siete medio Ilenas y siete vacias. Le gustaria dividir las 21 botellas entre tres individuos, de manera que cada uno reciba exactamente siete. Ademés, cada individuo debe recibir la misma cantidad de vino. Exprese el problema como una ecuaci6n de restricciones de PLE y encuentre una solucién utilizando TORA. (Sugerencia: utilice una funcién objetivo simulada, en la cual todos los coeficientes del objetivo son ceros.) 4. Un excéntrico jeque dejé un testamento para que se distribuya su rebaiio de came- los entre sus tres hijos: Tarek recibe por lo menos la mitad del rebaiio, Sharif obtiene por lo menos una tercera parte y Maisa recibe por lo menos una novena parte. El resto es para una organizacién de beneficencia. El testamento no especifica el ta- maiio del rebaiio, excepto para decir que se trata de un ntimero impar de camellos y que la obra de beneficencia mencionada recibe exactamente un camello. Oy Osix,=0 $2=1 six, > Oy Osix, ya= 1 six > Oy Osizs=0 Podemos asegurar que y, sera igual a1 si.x es positiva, tilizando la restricci6n My, j= 1,2,3 donde 4f es un valor suficientemente grande que no limitaré artificialmente el valor de x,, Debido a que yo puedo hacer alrededor de 200 minutos de Hamadas al mes, entonces x = 200 para todas las j y es seguro tomar M = 200, El modelo completo es Minimice z= 254; + 21x, + 22x, + 16y; + 25y2 + 18y5 sujets a372 Cap.9 — Programacién lineal entera La formulaci6n muestra que la tarifa mensual fija,j ésima, sera parte de la funcién objetivo zs6lo si y, = 1, lo que puede sticeder s6lo si x, > 0 (segiin las tres dltimas restricciones del mo- delo), Si x, = 0 en la 6ptima, entonces la minimizaci6n de z, junto con el hecho de que el coefi- ciente de y, es estrictamente positivo, obligaré a y, a ser igual a cero, como se desea. La solucién dptima nos da.x; = 200, y2 = 1 y todas las variables restantes igual a cero, lo que muestra que debo elegir 2 BabyBell como mi servicio de larga distancia, Observe que la informa- ci6n transmitida por y= 1 es redundante, ya que el mismo resultado es implicito por x, > 0 (= 200). De hecho, fa raz6n principal para utilizar y,, v2 € ys es tomar en consideraci6n la tarifa mensual fj En efecto, las tres variables binarias convierten un modelo de mal comportamiento (no linear) en una formulacién analiticamente controlable. Esta conversién ha sido el resultado de introducir las variables de enteros (binarias) en un problema que de otra manera serfa continuo. El concepto de la “tarifa fija” es tipico de lo que en fa literatura se conoce como pro- blema del cargo fijo Serie de problemas 9.26 1. La empresa Jobco esta planificando Ia produccién de 2.000 accesorios en tres méquinas. El volumen minimo del lote en cualquier maquina es de 500 accesorias. La siguiente tabla proporciona los datos pertinentes de las situaciones. Costo Costo de Capacidad Maquina delplan —producciénluniad —_(unidades) 1300 2 600 2 100 10 800 3 200 5 1200 Formule el problema como un PLE y encuentre la solucién éptima por medio de TORA. Oileo esta considerando dos sitios potenciales para perforaciones, para llegar a cua- tro objetivos (posibles pozos petroleros). La siguiente tabla proporciona los costos de preparacién en cada uno de los dos sitios y el costo de perforar del sitio i al obje- tivo j @=1,2,j=1234).Sec. 9.2 Aplicaciones ilustrativas 373 Costo de la perforacién (millones de détares) al objetivo ——_—— _Costo de la preparacién Sitio 1 2 3 4 (millones de délares) 1 2 1 8 5 2 4 6 3 1 6 Formule el problema como un PLE y encuentre la solucién éptima utilizando TORA. 3. Se estan considerando tres ubicaciones industriales para instalar unas plantas manu- factureras. Estas les envian su produccion a tres clientes. La oferta en las plantas y la demanda de los clientes, junto con el costo de transporte por unidad, desde las plantas hasta la ubicacién de ios clientes, se proporcionan en la siguiente tabla: 1 2 3 Oferta 1) $10 sis si2 | 1800 2| $17 S14 $20 | 1400 3/ $15 $10 sit | 1300 Demanda 12001700 1.600, Ademés de los costos de transporte, también se incurre en costos fijos, en una proporcidn de 10 000, 15 600 y 12 000 délares para las plantas 1,2 y 3, respectiva- mente, Formule ei problema como un PLE y encuentre la solueién éptima uti- lizando TORA. Ejemplo 9.2-3 (PROBLEMA DEL VENDEDOR VIAJERO.) El programa de produccién diaria en la compafiia Rainbow incluye lotes de pinturas blanca (B), amarilla (A), roja (R) y negra (N). Debido a que Rainbow utiliza las mismas instalaciones para los cuatro tipos de pinturas, es necesaria una limpieza a fondo de los fotes. La siguiente tabla resume el tiempo de limpieza en minutos cuando el color designado en el renglén va seguido del color desig- nado en la columna. Por ejemplo, cuando el blanco va seguito por el amarillo, el tiempo de limpieza es de 10 minutos. Debido a que un color no se puede seguir a sf mismo, se asigna a las entradas co- rrespondientes un tiempo de preparacién infinito. Determine la secuencia Gptima para la produc- cidn diaria de los cuatra colores, que minimizaré el tiempo total de limpieza asociado. EI tiempo de limpieza dado para Ia siguiente pintura es Pintura actual Blanca Amarilla Negra Roja Blanca © 0 7 15 Amarilla 20 ® 19 18,374 Cap.9 — Programacién lineal entera La figura 9~1 resume el problema. Cada pintura esta representada por un nodo y los arcos direccionales representan el tiempo de limpieza necesario para llegar de un nodo a otro. Por con siguiente, la situacién se reduce a determinar el ciclo mds corto que empieza en un nodo (pintura) y pasa a través de cada uno de los tres nodos restantes exactamente una vez, antes de regresa nodo inicial. Los problemas de este tipo se conocen ge: nente como el problema del vendes dor viajero, debido a que parafrasean la situacién en la cual una persona desea determinar el recorrido més corto para visitar n ciudades, en donde cada ciudad se visita exactamente una vez. Figura 9-1 Podemos resolver este problema enumerando en forma exhaustiva los seis [(4—1)! = 3! = 6] posibles ciclos de la red. La siguiente tabla muestra que BA -—>R->N-B es el ciclo 6ptimo. Cireulo de produccién Tiempo de limpieza total BrA+N+R+B 10+ 19 +254 45 99 BrA+R-N-B 104184204502 98 B+N+ATR +B 17+ 4+ 18 +45 = 124 B+N+RTA~B 7 +25 +40 +20 102 B+R+N7A+B 15 +204 46 +20= 99 B+R+A-N+B 40+ 19 +50 124 La enumeracién exhaustiva de los circulos sélo es practica para los problemas pequefios (por ejemplo, juna red de 11 nodos tiene 10! = 3 628 800 cfrculos). En consecuencia, es necesaria una formulaci6n mas eficiente. Defina y= 1 sise llega al nodo j desde el nodo iy cero de lo contrario, Una condicién necesaria para un recorrido (ciclo) es que la ciudad i s6lo conecte con una ciudad y que se Tlegue a la ciu- dad j exactamente desde una ciudad. Si dejamos que M sea un valor positivo suficientemente grande, podemos formular el problema de Rainbow como Minimice z= Mxpy + 10tu, + 17xpy + 15xpe + 20X4y + Mira + 19kaN + 1808 4 SOxyg + 4dr + Mi yy + 25tiyg + 45x qn + 404 + 20kpy + MtgeSec. 9.2 Aplicaciones ilustrativas 37 sujeta a Xap + Xpa + Xan + Xpn = 1 Xap + Xaa + Xan t Xae=1 ye + va + tw + Awe = 1 Xue + tga + Xan + tee = 1 Xpy + Xan + up + Xpu=1 Yaa + Xan t+ Awa + Xp = 1 Ann + Xan + Xn + tay = 1 Xae + tan + Iye + Xep=1 Xj = (0,1) para todas las i y j La solucién es un recorrido (ciclo) Excepto por el requerimiento de que la solucién debe ser un recorrido, la formulacién es ut modelo de asignacién, No hay ninguna garantfa de que la sola soci dptima de la asignacién pro duciré un reeorrido. Lo mas probable es que consistira de subrecorridos que unen subconjuntos de Jos nodos cercanos. Por esta raz6n, se han desarrollado algoritmos exactos basados en el model asignacién para resolver el problema. Estos algoritmos varian en cuanto a su complejidad y eficien cia en el aspecto de los cdlculos (véase Taha, 1975, paginas 304-316, para detalles). Serie de problemas 9.2¢ 1. Un gerente tiene un total de 10 empleados que trabajan en seis proyectos. Hay traslapes en las asignaciones, como lo muestra la siguiente tabla: Proyecto eee eaten 1 ek 2|x x x 3 x xX xX x 4 x x xX | roe 6 cg ay eg x a a x XxX 8 Peek 9 ay w)xX xX x376 Cap.9 — Programacién lineal entera El gerente se debe reunir con los 10 empleados una vez a la semana, para hablar de su progreso. En la actualidad, la reunién con cada empleado dura alrededor de 20 minutos, es decir, un total de tres horas y 20 minutos para los 10 empleados. Se sugiere reducir el tiempo total celebrando juntas de grupo, dependiendo de los proyectos que comparten los empleados. El gerente quiere programar los proyectos de tal manera que se reduzca el trafico (ntimero de empleados) que entran y salen de la sala de jun tas. ,Cémo debe programar los proyectos? 2. Un vendedor de libros que vive en Basin debe visitar una vez al mes a cuatro clientes, ubicados en Wald, Bon, Mena y Kiln. La siguiente tabla proporciona las distancias en miillas entre las diferentes ciudades: Basin Wald Bon Mena Kiln Bon | 220° 110° 0160185 Mena | 150 110 1600190} Kiln | 210 130185190 0 El objetivo es minimizar la distancia total que recorre el vendedor. Formule el problema como un PLE En el problema 2, supongamos que Wald, Bon, Mena y Kiln estén designadas como las ciudades 1,2,3 y 4 y que la “base” en Basin esta dividida en dos ciudades que se han designado como las ciudades 0 y 5. Por consiguiente, se inicia un recorrido en Ia ciudad 0, pasa (en algin orden) por 1, 2,3 y 4 y termina en 5. Defina v, para la ciudad i (i =0,1,...,5) de modo que 0 = v, = 5,y deje que x, = 1 sila ciudad i va seguida por la ciudad j en el recorrido y cero de lo contrario, Muestre que las restricciones 3. wu + Sx, 34, 8=0,1,.4, f=1, 2055 garantizan la eliminacién de todos los subrecorridos en la solucién del problema. Ejemplo 9.2-4 (PROBLEMA DE COBERTURA DE CONJUNTOS.) Con el fin de promover la seguridad de los estudiantes, el Departamento de Seguridad de la U de A se encuentra en proceso de instalar teléfonos de emergencia en ubicaciones selectas dentro de sus instalaciones El departamento quiere instalar un ntimero minimo de teléfonos, siempre y cuando cada una de las principales calles del campus cuente por lo menos con un teléfono. En la figura 9—2 se proporciona el mapa de las calles principales (A~K) en la universidad.Sec. 9.2 Aplicaciones ilustrativas Calle D Figura 9-2 37 Es l6gico instalar los teléfonos en las interseeciones de las calles, de manera que cada telé fono sirva por lo menos a dos calles. La figura 9-2 muestra que el trazo de las calles requiere w méximo de ocho ubicaciones para los telétonos, Defina x)= si hay un teléfono instalado en la ubicacién j y 0 de lo contrario, j= 1,2,..48 Las restricciones del problema requieren la instalacién de, por lo menos, un teléfono en cada un de las 11 calles (A a K). Asi, el modelo se convierte en Minimice 2 =x, 4% 4.15404 Xs 4x94) +X sujeta a yx 21 (Calle A) Qty 21 (Calle B) xe + Xs 1 (Calle C) (Calle D) (Calle E) (Calle F) (Calle G) (Calle H)378 Cap.9 Programacién lineal entera mm o+Xy (Calle Xs (Calle J) noth (Calle K) = OD, FHh 2.8 La solucién éptima del problema (obtenida con TORA), requiere ta instalacién de cuatro teléfonos en las imtersecciones 1,2, 5 y 7 El modelo anterior es tipico de lo que genéricamente se conoce como problema de cober- tura de conjuntos. En este modelo, todas las variables son binarias. Para cada restriccién, todos los coeficientes del lado izquierdo son 00 1 y el lado derecho es de la forma (= 1). La funcisn ob- jetivo siempre minimiza c,x; + car + ... + cytq en donde c, > 0 para todas las f= 1,2... . 1 En este ejemplo, c; = 1 para todas las j. Sin embargo, si c; representa el costo de instalacidn en la ubicacién j, entonces estos coeficientes pueden asumir otros valores aparte de 1 Serie de problemas 9.24 1. ABC es una compafiia de camiones LTL que diariamente entrega carga a cinco clien- tes, Se han elegido las siguientes rutas para llegar a los clientes. Rutal. 1 Ruta2. 4, Ruta3. 1, Ruta4. 2, Ruta. Ruta6. 1 Los segmentos de cada ruta los dicts fa capacidad del cami6n que entrega las cargas. Por ejemplo, en Ja ruta 1, el camién tiene la capacidad suficiente para entre- gar las cargas tinicamente a los clientes 1,2,3 y 4. La siguiente tabla proporciona las distancias (en millas) entre la terminal de camiones (ABC) y los clientes, ABC lg ABC| 0 10 12 16 9 8379 Sec.9.2 Aplicaciones ilustrativas El objetivo es hacerles las entregas diarias a los cinco clientes utilizando la dis- tancia de manejo mas corta, La sofucién puede ser tal que haya mas de una ruta que sirva al mismo cliente. Al poner en préctica la solucién, s6lo se utiliza una de estas rutas. Formule el problema como un PLE y resuélvalo utilizando TORA. 2, La U de A se encuentra en proceso de formar un comité para que maneje las quejas de los estudiantes. Las instrucciones recibidas de fa administraci6n son incluir por lo ‘menos una mujer, un hombre, ua estudiante, un administrador y un miembro del pro- fesorado. Diez personas han sido nominadas (identificadas, para simplificar, por las le- tras a alaj). La mezcla de estas personas en las diferentes categorias se da como sigue: Categoria Personas “Mujeres ad.cde Hombres f8ihyini Estudiantes abe] Administradores ef Miembros del profesorado d,g, hi La U de A desea formar el comité més reducido posible y, al mismo tiempo, garantizar la representaci6n de cada una de las cinco categorias. Formule el proble- ma como un PLE y encuentre la soluci6n 6ptima utilizando TORA. 3. El condado de Washington incluye seis poblaciones que necesitan servicios de ambu- lancia para urgencias. Las estaciones de las ambulancias pueden estar ubicadas en cualquiera de las seis poblaciones o en todas. Sin embargo, debido a la proximidad de algunas de esas poblaciones, una sola estacién puede servir a mas de una comunidad. La estipulacién es que la estacién debe estar a 15 minutos de distancia de las pobla ciones a las que sirve. La tabla a continuacién proporciona los tiempos de manejo, en minutos, entre las seis poblaciones. 14 18 10 32 2) 23 0 4 3B 2 3] 14 24 0 © 19 20 4/18 13° 60 0 55 17 5] 10 22 199 55 0 12 6] 32 1 2 17 12 o|380 Cap.9 — Programacién lineal entera Formule un PLE cuya solucién produciré el menor mimero posible de esta- ciones y sus ubicaciones. Encuentre la solucién utilizando TORA. 4, Los tesoros del rey Tut se estén exhibiendo en un museo en Nueva Orleans. La dis- tribucién fisica dei museo se muestra en la figura 9—3,con las diferentes salas unidas por puertas abiertas, Un guardia de pie en una puerta puede vigilar dos salas ad- yacentes, El museo quiere asegurar la presencia de los guardias en todas las salas, utilizando el menor nimero posible de ellos. Formule el problema como un PLE y encuentre la soluci6n 6ptima utilizando TORA. —} Figura 9-3 Ejemplo 9.2-5 (PROBLEMA DE RESTRICCIONES DE UNO U OTRO.) La empresa Jobco utiliza una sola maquina para procesar tres trabajos. Tanto el tiempo de proce- samiento como la fecha de entrega (en dfas) se proporcionan en Ia siguiente tabla, Las fechas de entrega se miden desde la fecha cero, que es la de inicio del primer trabajo. Tiempo de Fecha de Penalidad por Trabajo _procedimiento(d) —_entrega (d) _retraso(délares/d) 1 5 25 0 2 20 2 2 3 15 35 E] objetivo del problema es determinar la secuencia con penalidad minima por retraso para el procesamiento de los tres trabajos. Defina x, = fecha de terminacién en dias para el trabajo j (medida desde la fecha cero) El problema tiene dos tipos de restricciones: (1) las restricciones de no interferencia, que garan tizan que no se procesen dos trabajos en forma concurrente y (2) las restricciones de la fecha de entrega. Considere primero las restricciones de no interferencia. Dos trabajos, i y j, con tiempos de procesamiento p; y py no se procesaran en forma con- currente siSec.9.2 Aplicaciones ilustrativas 381 Ya seax, = + pjo bien x, =x; + p; dependiendo de si el trabajo j precede al trabajo i, o viceversa, Debido a que todos los problemas matematicos tratan tnicamente con restricciones si: ‘multéneas, transformamos las restricciones de uno u otro introduciendo la siguiente variable binaria auxiliar: [1,_ siiprecede a ¥~ 10, sijprecede ai Para que M sea lo suficientemente grande, a restris dos restrieciones simulténeas: 6n de uno w otra se convierte a las siguientes My, + (x ~ x) =p, and M(QL~ y,) + (4) ~ =P, La conversion garantiza que sélo una de las dos restricciones puede ser activa en cualquier momento determinado. Si yy = 0, a primera restriccidn es activa y la segunda es redundante (de- ido a que su lado izquierdo incluiré a.M, que es mucho més grande que p;).Si yy = 1,1a primera restriccién es redundante y la segunda es activa, Enseguida, se considera la restriccidn de la fecha de entrega. Dado que dj es la fecha de vencimiento para el trabajo j, dejamos que s; sea una variable no restringida, Por tanto, la res- triccién asociada es a+ p+ Si s, = 0,se satisface la fecha de entrega y sis, < 0, se incurre en una penalidad por el retraso. Utilizando la sustitucién estindar La restriceién se convierte en ats sp = 4D, El costo de la penalidad por el retraso es proporcional a 5; El modelo para el problema dado es Minimice z = 19s; + 1257 + 34s sujetaa ee + My stom — My * =x, + My; —m by My,s x, - x + Mya —n ty = My, % +53 2-20382 Cap.9 — Programacién lineal entera Xp Xn ty Sh 57, 5, 8 Yiw Vis Ya Las variables enteras yix, Yas ¥ Yas Se introducen para convertir las restricciones de uno u otro en restricciones simultineas, El modelo resultante es un PLE mixto. Para resolver el modelo, seleccionaritos M = 100,un valor que es mayor que la suma de los tiempos de procesamiento para las tres actividades. La soluci6n dptima (obtenida con TORA) es x, = 20, x, = 0, yx; = 25. Por consiguiente, la secuencia de procesamiento éptima es 2 -> 1 ~> 3. La solucién requiere la terminacién del trabajo 2eneltiempo0 + 5 25,y del trabajo 3en 25 + 15 = 40 5,del trabajo I enel tiempo = 20 + 5 = 2: dias, El trabajo 3 se demora por 40 ~ 35 = 5 dias después de su fecha de entrega, a un costo de 5 x $34 = 170 dolares. Serie de problemas 9.2e 1. Untablero de juego consta de nueve cuadros iguales. Se requiere que usted lene cada cuadro con un niimero entre el uno y el mueve, de tal manera que fa suma de los niimeros en cada renglén y en cada columuna sea igual a 15, Determine el mimero en cada cuadro para los siguientes casos (a) Ningunos dos nimeros adyacentes en cualquier renglén o en cualquier columna son iguales. (b) Los ntimeros en todos los cuadros son distintos. Exprese el problema como restricciones de PLE y resuélvalo con TORA. 2. Se utiliza una maquina para fabricar dos productos intercambiables. La capacidad dia- ria de la méquina puede producir cuando mucho 20 unidades del producto 1 y 10 unidades del producto 2, Como una alternativa, la maquina se puede ajustar para que produzca diariamente cuando mucho 12 unidades del producto 1 y 22 unidades del producto 2. El andlisis del mercado muestra que la demanda maxima diaria para los dos productos combinados es de 35 unidades. Suponiendo que las utilidades por unidad de los dos productos respectivos son 10 y 12 délares, ,eual de los dos arreglos de la maquina se debe seleccionar? Formule el problema como un PLE y encuentre Ja 6ptima utilizando TORA. (Nota: este problema bidimensional se puede resolver inspeccionando el espacio de la solucién grafica. Este no es el caso para el problema de n dimensiones.) 3. La empresa Gapeo fabrica tres productos, cuyos requerimientos diarios de mano de obra y de materia prima se proporcionan en la siguiente tabla: Mano de obra diaria Materia prima diaria Producto _requerida(horas/unidad) _requerida (libra/unidad) 1 3 4 4 3Sec. 9.2 Aplicaciones ilustrativas 383 Las utilidades por unidad de los tres productos son 35, 30 y 22 dolares, respecti- vamente, Gapeo tiene dos opciones para ubicar su planta. Las dos ubicaciones difieren primordialmente en la disponibilidad de mano de obra y de materia prima, segiin se muestra en la siguiente tabla: Ubicacién Mano de obra diaria disponibfe (horas) __ Materia prima diaria disponible (libras) 1 100 100 2 90 120 Formule el problema como un PLE mixto y utilice TORA para determinar la ubicacién éptima de la planta, 4, Considere el problema de programacién de trabajo del taller que fabrica dos pro- ductos finales utilizando una sola maquina. Las relaciones de precedencia entre las ocho operaciones se resumen en {a figura 9-4. Sea p; el tiempo de procesamiento para las operaciones j (=1,2,.. . ,2).Las fechas de entrega, medidas desde la fecha ini- cial, para los productos 1 y 2, son d; y ds, respectivamente. Una operaciGn, una vez iniciada, se debe terminar antes de que empiece otra. Formule el problema como un PLE mixto. Bo one Producto 1 CK Ones Oona Figura 9-4 5. La empresa Jaco es propietaria de una planta donde se fabrican tres productos, Los requerimientos de mano de obra y de materia prima para los tres productos se pro- porcionan en la siguiente tabla: a Mano de obra diaria Material prima daria Producto requerida (horas‘unidad) —_requerida (librastunidad) ee ——————— 2 4 3 3 5 6 Disponibilidad diaria 100 100 Las utilidades por unidad para los tres productos son de 25,30 y 45 ddlares, res- pectivamente, Si se quiera fabricar el producto 3, entonces su nivel de produccién384 Cap.9 Programacién lineal entera debe ser por lo menos de tres unidades diarias, Formule el problema como un PLE mixto y encuentre la mezcla 6ptima utilizando TORA. 6. Muestre la forma en la cual los espacios sombreados de la soluci6n en la figura 9~5 se pueden representar por medio de un conjunto de restricciones simulténeas, Des- pués utilice TORA para encontrar la solucién éptima que maximice z = 2x, + 3x) sujeta al espacio de la solucién dada en (a). @ © © Figura9-S 7. Supongamos que se requiere que cualquier k de Jas siguientes restricciones m debe ser activa: by i Bi Xp oes %y) Muestre cémo se puede representar esta condicién. 8. En la siguiente restriccion, el Jado derecho puede asumir uno de tos valores, by, Daye Bre by. on. BOR py 25 %,) Oby Muestre cémo se representa esta condi 9.3 ALGORITMOS DE SOLUCION DE LA PROGRAMACION ENTERA Los algoritmos del PLE se basan en explotar el fantastico éxito de Ja PL en los calculos con computadora, La estrategia de estos algoritmos implica tres pasos. Paso 1. Disminuya el espacio de la solucién del PLE, reemplazando cualquier variable binaria ycon la gama continua 0 = y = 1,y tachando las restricciones enteras en todas las variables enteras. El resultado de la disminucién es una PL regular. Paso 2. Resuelva la PL ¢ identifique su soluci6n 6ptima continua. Paso 3. Empezando desde el punto dptimo continuo, afiada restricciones especiales que modifiquen iterativamente e} espacio de la solucién del PL en una forma que a la larga rendir4 un punto extremo dptimo que satisfaga los requerimientos enteros,Sec.9.3 _Algoritmos de solucién de la programacién entera 385 Se han desarrollado dos métodos generales para generar las restricciones especiales a las que nos referimos en el paso 3. I. Método de ramificacién y acotamiento (R y A) 2. Método del plano cortante lae: Aunque ninguno de estos métodos es consistentemente efectivo para resolver los PL periencia con los célculos computarizados muestra que el método de ramificacién y acota- miento es mucho mas exitoso que el método del plano cortante, 9.3.1 Algoritmo de ramificacién y acotamiento (R y A) Los aspectos basicos del algoritmo de R y A se explicaran mediante un ejemplo numérico. Ejemplo 93-1. Considere el siguiente PLE Maximice z sujeta a 10x, + 6x, = 0 yentero del PLE se muestra en la figura 9-6 por medio de puntos. El restricciones enteras y su solucién 6ptima El espacio de ta soluci problema asociado de PL, PLO, se define quitando Is se da como x; = 3.75, x, = 1.25,yz = 23.75 6 Optima: x =3.75,x2 £223.75 o 1 2 3 4 %s 6 Figura 9-6386 Cap.9 — Programacién lineal entera Figura 9-7 Debido a que la solucién 6ptima no satisface los requerimientos enteros, el algoritmo de R y A modifica el espacio de la solucién de tal manera que a la larga identifica la ptima del PLE. Primero, seleccionamos una de las variables enteras cuyo valor en PLO no es entero. Al selec cionar arbitrariamente x, (= 3.75) la regién 3 < x, < 4 del espacio de la solucién en PLO ya no contiene valores enteros de x; y, por tanto, se pueden eliminar como no prometedores. Esto es equivalente a reemplazar la PLO original con dos nuevas PL, PLI y PL2, definidos como Espacio PLi = espacio PLO + (x, = 3) espacio PLO + (x, = 4) La figura 9-7 describe los espacios de PL1 y PL2. Los dos espacios contienen los misntos puntos enteros factibles del PLE original, lo que significa que tratar con PL1 y PL? es fo mismo que tratar con la PLO original Si seguimos eliminando inteligentemente las regiones que no incluyen soluciones enteras, imponiendo las restricciones apropiadas (tales como 3 < x, < 4),a la larga produciremos PLs cuyos puntos extremos 6ptimos satisfagan las restricciones enteras. En efecto, estaremos resol- viendo el PLE al tratar con una sucesién de PL (continuas). Las nuevas restricciones.x, = 3 y.x = 4,se exeluyen mutuamente, de manera que PL1 y PL2 se deben tratar como PL separados, como lo muestra la figura 9-8. Esta dicotomfa da origen al concepto de la ramificaci6n en el algoritmo de Ry A. En este caso, x, es a variable de ramificacién EI PLE 6ptimo se encuentra ya sea en PL1 0 en PL2, Por tanto, se deben examinar ambos subproblemas. Primero examinamos arbitrariamente PL1 (asociada con x, = 3 Espacio PL2 Maximice 2 = Sx, + 4x, sujeta a y+ mss 10x, + 6x, = 45Sec. 9.3 Algoritmos de solucién de la programacion entera 387 LPO Limite inferior (Gptimo) La soluci6n de PL1 (que se puede resolver de manera eficiente por medio del algoritmo de cota inferior de la seccién 7.5.2) produce la solucién éptima 153, 2yz La soluci6n de PLI satisface los requerimientos de enteros para x y x». Por consiguiente, se dice que PLI se debe sondear. Esto quiere decir que ya no es necesario investigar mas a PL1, porque no incluye ninguna solucién mejor de PLE. En este punto no podemos juzgar la “calidad” de la solucién entera de PL1, ya que PL2 puede producir una solucién entera mejor (con un valor més elevado de z). Todo lo que podemos decir es que z = 23 es una cota inferior sobre el valor objetivo (maximo) del PLE original. Esto significa que cualquier subproblema no examinado que no puede producir un valor objetivo mejor se debe descartar como no protuetedor. Si un subproblema no examinado puede producit una soluci6n entera mejor, entonces la cota inferior se debe actualizar posteriormente, Dada la cota inferior z = 23, examinamos PL2 (el tinico subproblema restante no exami- nado). Debido a que la 6ptima z = 23.75 en PLO y a que todos los coeficientes de la funcién obje- tivo son enteros, es imposible que PL2 (que es més restrictiva que PLO) produciré una solucién entera mejor. Como resultado, descartamos PL2 y concluimos que se ha sondeado. Elalgotitmo de R y A ahora esté completo, por que se han examinado y sondeado tanto PL1 como PL2 (la primera para producir una solucién entera y la segunda para mostrar que no puede producir una solucién entera mejor). Por ello, concluimos que la solucién 6ptima del PLE es Ia asociada con la cota inferior, a decir, x, = 3, x, = 2,y z = 23. Quedan dos preguntas sin respuesta en lo que se refiere a este procedimiento, 1. En PLO, ,podriamos haber seleccionado x; como la variable de ramificacién, en vez de.x,? 2. Cuando seleccionamos el siguiente subproblema que se iba a examinar, ber resuelto primero PL2 en vez de PL1? La respuesta a ambas preguntas es “si”. Sin embargo, Jos siguientes céleulos podrian diferir considerablemente. La figura 9~9, en la cual primero se examina PL2, iustra este punto. La sofuci6n.6ptima de PL2 es x, = 4, » = 83, y z = 23.33 (verifiquelo utilizando TORA) Debido a que x2 (= .83) no es entera, se sigue investigando mas PL2, creando los subproble-388 Cap.9 — Programacién lineal entera LPI 1P3 1P4 Q@ [ sinsoneion ] f= ns4 nes LPS 1P6 ©[a-4n © [Se soncicn Limite inferior Figura 9-9 mas PL3 y PLA utilizando las respect Oy. = 1,respectivamente, Esto quiere decir que ramificaciones x, Espacio PL3 = espacio PL2 + (x2 = 0) espacio PLO + (x, = 4) + (x, Espacio PL4 = espacio PL2 + (; = espacio PLO + (x1 = 4) + (x ‘Tenemos tres subproblemas pendientes que debemos examinar: PLL, PL3 y PL4. Supon- _gamos que primero examinamos arbitrariamente PLA, PL4 no tiene solucién, y entonces es son- deada. A continuaci6n, examinemos PL3. La solucién dptima es x, = 4.5,.x = 0,y z = 22.5. El valor no entero de x; (= 4.5) es conducente a las dos ramificaciones Syyala creacién de los subproblemas PLS y PL6 a partir de PL3 Espacio PLS = espacio PLO + (x, = 4) + (ve = 0) + (x; = 4) Espacio PL6 = espacio PLO + (x;Sec. 9.3 Algoritmos de solucién de la programacién entera 389 Ahora, los subproblemas PL1, PLS y PL6 siguen sin examinar. PL6 se sondea debido a que no tiene una solucidn factible. Después, PLS tiene la solucidn entera (x, = 4, x, = 0,2 = 20) y, por consiguiente, produce una cota inferior (z = 20) en la solucién 6ptima de PLE, Nos queda el subproblema PL1, cuya solucién también es entera (1, = 3, x» = 2,z = 23). Por tanto, la cota in- ferior se actualiza az = 23. Debido a que fodos los subproblemas se han sondeado, la solucién Optima estd asociada con la cota inferior més actualizada, es decir, x, = 3,x. = 2.yz = 23, La secuencia de la solucién en la figura 9~6 (PLO, PL2, PL4, PL3, PL6, PLS, PL1) es un escenario del peor caso que, sin embargo, puede ocurrir en la préctica. El ejemplo indica una de- bilidad principal del algoritmo de A y R: ,c6mo seleccionamos el siguiente subprobiema que debemos examinar y cémo elegimos su variable de ramificacin? En a figura 9~8, nos “tropezamos” con una buena cota inferior en el primer subproblema Jo que, por tanto, nos permite sondear PL2 sin céiculos posteriores y terminar la investigacion de Ry A-En esencia, terminamos e) procedimiento resolviendo solamente un subproblema. En la figura 9-9, tuvimos que examinar siete subproblemas antes de terminar el algoritmo de R y A. Aun cuando hay métodos heuristicos para mejorar la habilidad de R y A de “adivinar” cuél rami- ficacién puede conducir a una solucién mejorada de la PLE (véase Taha, 1975, pp. 154-171), no hay una teorfa s6lida que siempre producira resultado uniformes. Ahora resumimos el algoritmo de R y A. Suponiendo un problema de maximizacién, determinaremos una cota inferior inicial z = — en el valor objetivo éptimo de PLE. Deter- mine i = 0. Paso 1, (sondear/acotar). Seleccione PLi, el siguiente subproblema a ser examinado. Resuelva PLiy trate de sondearlo, utilizando una de tres condiciones. (a) El valor 6ptimo z de PLi no puede producir un mejor valor objetivo que la cota inferior actual (b) PLi produce una solucién entera factible mejor que la cota inferior actual. (©) PLino tiene una solucién factible. Se presentardn dos casos. (a) Sise sondea PLi, actualice la cota inferior si se encuentra una mejor solucién del PLE, Si se han sondeado todos los subproblemas, deténgase; el PLE 6p- timo esta asociada con la cota inferior actual, sj Ja hay. De otra manera, haga i= i+ 1Lyrepita el paso 1. (b) Sino se sondea PLi, vaya al paso 2 para efectuar la ramificacién, Step 2. (ramificacién). Seleccione una de las variables enteras x, cuyo valor éptimo x," em fa solucién de PLi no es un entero, Elimine la regisn [x,"] < x, < [xy] + 1 (donde [»] define el entero mas grande = v) creando dos subproblemas de PL que corresponden a lel y til+1 Determine i = i + 1,y vaya al paso 1 Los pasos dados aplican a los problemas de maximizaci6n. Para minimizaci6n, reem- plazamos la cota inferior con una cota superior (cuyo valor inicial es z = + % ). El algoritmo de R y A se puede extender directamente a los problemas mixtos (en los cuales s6lo algunas de las variables son enteros). Si una variable es continua, simplemente390 Cap.9 — Programacién lineal entera nunca la seleccionamos como una variable de ramificacién. Un subproblema factible pro- porciona una nueva cota sobre el valor objetivo si los valores de las variables discretas son enteros y el valor objetivo se mejora en relacién con la cota actual. Serie de problemas 9.3a 1. Resuelva el PLE del ejemplo 9.3—1 mediante el algoritmo de R y A,empezando con 4 como la variable de samificacién. Resuelva los subproblemas con TORA, utili- zando la opcién MODIFICAR para {as cotas superiores e inferiores. Inicie el pro- cedimiento resolviendo el subproblema asociado con x3 = [x."] 2. Desarrolle el arbol de R y A para cada uno de los siguientes problemas. Por como- didad, siempre seleccione x, como la variable de ramificaci6n en ef nodo 0. (a) Maximice z = 3x, + 2x; sujeta a (b) Maximice z = 2x, + 3x) sujetaa Sx; + Tx Ax, + Ox, Xy%) = y entero (©) Maximice ¢ = x, sujetaa 2x, + Sxz = 16 6x, + Sxy Xi.% = y entero (a) Minimice z = Sx, + 4x, sujeta a 3x, + 2x, 2x, + 3x, 2,,%2 = y entero (e) Maximice z sujeta a 2X4.) = y entero392 Cap.9 — Programacién lineal entera 2, Todas las restricciones deben ser del tipo (=), con todos los lados derechos nega- tivos, de ser necesario, Después, estas restricciones se convierten a ecuaciones, utilizando variables de holgura (continuas) en el lado izquierdo de las restricciones. condiciones, como lo demuestra Cualquier problema entero 0-1 puede satisfacer est el siguiente ejemplo. Ejemplo 93-2. Convierta el siguiente problema }-1 para satistacet los requerimientos iniciales del algoritmo aditivo. Maximice z= 3x, - 5x2 svjeta a x+ m=5 x, + 6x, = 4 X= (0, 1) Primero convertimos el problema a uno de minimizacién con todas las restrieciones (=) como sigue: (a) Multiplique z por ~1 para obtener la minimizaci6n de w = 3x, + Sx» 48) Convierta la ecuacién de restriccién en dos restricciones del tipo (=) atm sSy-m- mH =-5. (©) Multiplique ia segunda restriccién por ~1 para obtener 4x, — 6x2 = 4. ara obtener Utilizando las holguras s,, 3 y s5 para las tres restricciones, el problema se escribe como Minimice w = ~3x, + 5x2 sujetaa 1 ~ xj para cualquier x, con un coeficiente negative en la funcidn objetivo. Por consiguien- stituimos x, = 1 — %' y ajustamios el lado derecho de las restricciones conforme a ello. El te, su Igoritmo aditivo ahora trata con x," y x Igual que en la R y A, la ramificacién en el algoritmo aditivo también se basa en el em- pleo de una variable de ramificacién x). La principal diferencia es que las dos ramificaciones estin asociadas con las ecuaciones estrictas x) = yx; = 1 porque x, es una variable binaria. El acotamiento se trata de ja misma manera como en el algoritmo de R y A.en el sentido de que una solucién entera mejorada proporciona una cota supetior sobre el valor minimo de la funcidn objetivo,Sec. 9.3 Algoritmos de solucién de la programacién entera 393 E] desentrafiamiento de los subproblemas puede ocurrir en una de tres formas: 1, El subproblema no puede conducir a una solucién factible. 2. El subproblema no puede producir una cota superior mejor 3. Elsubproblema produce una solucién entera factible. Estas reglas son las mismas que en R y A. La principal diferencia es que no resolvemos una PL. En su lugar, utilizamos la heuristica. El siguiente ejemplo numérico demuestra el algoritmo aditivo y sus pruebas de sondeo. 30RITMO ADITIVO.) wuiente problema 0-1 Ejemplo 9.3-3 (ALS Resuelva el s Maximice w = 3y, +2y2— Sys ~ sujetaa wt nt wt Bt sd By By, ay My, - 6% + 3yy Mis Yar Yoo Yar J's = 1) El problema se puede poner en la forma inicial requerida por el algoritmo aditivo (véase el ejemplo 9.3-2), utilizando las siguientes operaciones (a) Multiplique la tuncién objetivo por ~1 (b) Multiplique ls tercera restriccién por —1 (©) Aitada las variables s,,52 y sy para convertir las tres restricciones en ecuaciones. (@) Sustituya yy = 1 = xyyp = 1 — Ys = 1 ~ X5.¥s = ZHY Ya = Xa para producir todos os coeficientes objetivo positivos La conversién da por resultado la siguiente funcién objetivo (jveriffquelo!): Minimice 2" = 3x, + 2x9 + 5x3 + 2vq+ 3x5 ~ 8 + 8con z,de manera que el y reemplacemos z Para mayor facilidad, ignoremos la constante — problema convertido resultante se lee como (;verifiquelo!) Minimice z = 3x, Sx, + 2x, + 34 sujeta a -y- mt uy t2u- ats = 1 Ix + 3x — dx, — 3x, +5, = -2 Mx, — 6 — 3x) — 3k, +5, = 1 Xa Xp Fy X= (0, 1) Debido a que el problema modificado busca la minimizacién de una funcién objetivo con todos los coeficientes positivos, una solucién inicial I6gica debe consistir en variables binarias304 Cap.9 Programacién lineal entera todas cero, En este caso, las holguras actuardn como variables basicas y sus valores los dan los Jados derechos de la ecuacién, La solucién se resume en la siguiente tabla: Como vera més adelante, la aplicacisn de las pruebas de sondeo en cada subproblema sélo re- queriré cambiar la columna mas a la derecha de la tabla simplex. Dada una solucién binaria inicial toda cero, la soluci6n de la holgura asociada es -1), Si todas las variables fueran no negativas, concluiriamos que la solucién binaria toda cero es 6p- tima, Sin embargo, debido a que algunas de las variables son no factibles (n snecesitamos elevar una o mds variables binarias al nivel 1 para lograr la factibilidad (0 concluimos que cl problema no tiene una solucién factible), La elevacién de una (o de algunas) de las variables binarias cero al nivel 1 ocurre en el al- goritmo aditivo una a fa vez. La variable elegida se llama variable de ramificacién y su seleccién se basa en el empleo de pruebas especiales. La variable de ramificaci6n debe tener el potencial de reducir Ia no factibilidad de las holguras. Si vemos [a tabla anterior, x, no se puede seleccionar como una variable de ramifi- cacidn, debido a que sus coeficientes de restriccién en la segunda y tercera restricciones son no negativos. Por tanto, la determinacién de x, = 1 s6lo puede empeorar la no factibilidad de s2 y 93 ‘A la inversa, cada una de las variables restantes tiene por lo menos un coeficiente de restriccién negativo en las restricciones 2 y 3,de alli que una combinacién de estas variables puede producir holguras factibles. Por consiguiente, podemos excluir @.x, y considerar a x), >, X« ¥ 5 como las \inicas candidatas posibles para la variable de ramificaci6n, La selecci6n de la variable de ramificaci6n entre las candidatas x,, x», %4 ¥ Xs, se basa en el empleo de la medida de no factibilidad de la holgura. Esta medida, que se basa en la suposicién de que una variable cero x; se elevard al nivel 1, se define como J, = > minl0,s;— aj) (5 Sy 8) = Gs — =o donde s, es el valor actual de la variable i y ay es el coeficiente de restriccién de la variable x, en De hecho, J, no es més que la suma de las variables negativas resultantes de elevar x al nivel 1. La formula, aparentemente complicada, se puede simplificar a I, = > (negativo s, valor dado396 Cap.9 — Programacién lineal entera que es no factible. Las candidatas para la ramificaci6n son x, %2 ¥ X3-Sin embargo, la elevaci6n de cualquiera de estas variables al nivel | empeoraré el valor de z en relaci6n a la cota superior ac- tual z = 3. Por consiguiente, todas las variables candidato se excluyen y el nodo 3 se sondca. Después, en el nodo restante 4, definido por x; = x4 = 0, tenemos ote Las variables x; y x se €xcluyen por medio de la prueba de la cota superior. (Observe que xs también se puede excluir debido a que no reduce [a factibilidad de la holgura). La variable fal- tante, x,, no puede ser excluida por la cota superior o por la promesa de factibilidad. Por tanto, x; es la variable de ramificacién, La figura 9~12 muestra la adicién de los nodos $ y 6 que emanan el nodo 4. En el nodo 5, tenemos 0 (55083) = (i525) = 2,-2.5). = 2 YX; yx) como las candidatas a la ramificaci6n. La variable x, se excluye por medio de la prueba de la cota superior y x5 se excluye por medio de las pruebas tanto de Ia factibilidad de la holgura como de la cota superior. Esto significa que el nodo 5 se sondea. FI nodo 6 es también sondeado debido a que ni x, ni xs pueden producir una mejor solucién factible. ase 2=3 (ondeada) (sondeada) 0 (sondeada) 2 (Gondeada) Figura 9-12 Ahora se han sondeado todos los nodos “pendientes” en la figura 9—12 y termina el algo- ritmo de R y A. La solucién éptima ests asociada con el nodo 1, es decir, x; = 1.z = 3,y todas las demas variables son cero. En términos de las variables originales, la soluci6n es y; = y2 = 1y Ys = Ya = Ys = Oconw = 5. La figura 9-12 muestra que, mientras mas pequeiio es el nimero de ramificaciones con- ducentes a un nodo sondeado, més eficiente es el algoritmo, Por ejemplo, el nodo 1 se define fi- jando una ramificaci6n (x; = 1) y su sondeo implica automaticamente de 2°"! = 16 soluciones binarias (todas aquellas que tienen x; = 1), A la inversa, el nodo 3 se define fijando dos varia- bles binarias y su sondco implicitamente implica de 2°-? = 8 soluciones binarias tinicamente.398 Cap.9 — Programacién lineal entera Resuelva el problema de presupuesto del capital del ejemplo 9.2~1 utilizando el z goritmo aditivo 4, Resuelva el siguiente problema suponiendo que sélo es vélida una de las dos res- tricciones dadas. Maximice z = x, + 2x; —3xy sujeta a 20x, + 15x, x5 = 10 12x, - 3x, + 4x, = 20 2h %a%5 = (0,1) 9.3.3 Algoritmo del plano cortante Igual que en el algoritmo de R y A, el algoritmo del plano cortante también empieza en la solucién continua éptima de la PL. Sin embargo, en vez de utilizar la ramificaci6n y el aco- tamiento, modifica el espacio de la soluci6n afladiendo sucesivamente restricciones especial- mente construidas (Ilamadas cortes). Primero demostramos la idea mediante un ejemplo grafico y después mostramos como se ponen en préctica los cortes algebraicamente. Fjemplo 9.3-4, ‘Demuestre gréficamente cémo se puede utilizar el algoritmo del plano cortante para resolver el siguiente PLE. Maximice z = 7x, + 10x, sujeta a -x,+3x,5 6 Try + x 35 X02 = Oyentero El algoritmo del plano cortante modifica el espacio de la solucién aftadiendo cortes que producen un punto extremo entero éptimo. La figura 9-13 proporciona un ejemplo de dos de €s08 cortes. Inicialmente, empezamos con la dptima continua dél (x,,.x3) = (43,34) y z = 665. A continuacidn, afladimos el corte I, que produce la éptima (continuo) (x, x3) = (44,3) con z = 62. Entonces aftadimos el corte II junto con el corte I las restricciones originales producen la éptima (x,,%) = (4,3) ¥ z = 58. La tiltima solucidn es toda entera, tal como se desea. Los cortes aitadidos no eliminan ninguno de los puntos enteros factibles originales, pero debe atravesar por lo menos un punto entero factible 0 no factible. Estos son los requerimientos basicos de cualquier corte. En general, se puede necesitar cualquier némero (finito) de cortes para llegar al punto e- tremo todo entero deseado. De hecho, el ntimero de cortes necesarios para producir Ia solucién entera deseada parece ser independiente del tamafo del problema, en el sentido de que un pro- blema con un numero reducido de variables y restricciones puede requerir més cortes que un problema mas grande.400 Cap.9 — Programacién lineal entera La solucién continua éptima es x, = 45, x) = 3}, =0,.44 = 0,y z = 663. El corte entero puro se desarrolla bajo Ia suposicién de que todas las variables son enteros. Observe también que, debido a que los coeficientes objetivo originales son enteros, entonces el valor de z asociado con una solucidn entera también debe ser entero, La informacién en la tabla simplex 6ptima se puede escribir en forma de ecuaciones come 6 3i : 4 t S54, = 66 eouasion zz + hay +55 ecuacion x32, + ecuacién xy: x ste ejemplo y a que todos tienen valores fraccionales Debido a que z, x4 ¥ x: deben ser enteros en en la tabla simplex dptima, cualquiera de las tres ecuaciones se puede wtilizar como un renglén generar el corte. Seleccionemos arbitrariamente la ecuaci6n para este propésito: 6 31 24S xy te x, 2222 Para construir el corte fraccional, cada uno de los coeficientes no enteros se divide en factores en- teros y fraccionales, siempre y cuando el componente fraccional sea estrictamente positivo. Por ejemplo, 66~ (zrenglén fuente) 1) La divisin en factores del renglén fuente z produce wf ++ 4 1\ (6 +3) Moviendo todos los componentes enteros al lado izquierdo y todos los componentes fraceionales al lado derecho, obtenemos 9 19 4 242m + 1X - 6 = —Fy- my +5 Bs 22 Debido a que x; y x; Son no negativos, entonces el lado izquierdo debe satistacer 19 19 22 Xz Son enteros, entonces (z + 2x; + Lx, — 66) también son enteros, 10 mismo Dado que z, x3 'x, + 4).Por consiguiente, bajo el requerimiento de enteros, la tiltima desigualdad que ( debe satisfacer io aeio eee Gp apt tz sO Este es el corte fraccional deseado, e implicito en su construcci6n estd el requerimiento de que todas las variables son enteros402 Cap.9 — Programacién lineal entera La tabla simplex es optima, pero no factible. Aplicamos el método simplex dual (véas laseccién 45) para recuperar la factibilidad, lo que nos da cién basic fact: bl xox xs 0 0 1 La tiltima soluci6n todavia es de no enteros en x, y x3, Entonces seleccionamos x, como el renglén fuente, es di El corte asociado es afladimos el corte Ia la tiltima tabla, obtenemos tible Xo % 8, 1 8, | Solucton 10 62404 Cap.9 — Programacién lineal entera sujeta a Oy entero 3. Resuelva los siguientes problemas por medio del corte fraccional y compare la ver- dadera solucién dptima entera con la solucién obtenida, redondeando la éptima continua (a) Maximice z = 4x; + 6x) + 2x, sujetaa Xy%2,X5 = 0 y entero (b) Maximice z = 3x, + x2 + 3x5 sujeta a + 2x, 4x, x, ~ Bx, + 2x SisXn.Xs = Oy entero 9.4 RESUMEN El factor mds importante que afecta los calculos en la programacién entera es el nimero de variables enteras, Debido a que los algoritmos disponibles no resuelven los problemas de PLE de manera uniforme, resulta ventajoso, desde el punto de vista de los calculos, reducir el ntimero de variables enteras en el modelo de PLE tanto como sea posible. Las siguientes su- gerencias pueden ser titiles: 1. Aproxime las variables enteras por medio de continuas, siempre que sea posible, 2. Para las variables enteras, restrinja sus gamas de factibilidad tanto como sea posible. 3. Evite el empleo de 1a no linealidad en el modelo. La importancia del problema entero en la practica todavia no ha sido alcanzada por algoritmos eficientes de solucién. Es improbable que se logre un nuevo avance teérico enSec.9.4 Resumen 405 el drea de la programaci6n entera. En su lugar, los nuevos adelantos tecnolégicos en las computadoras pueden ofrecer la mejor esperanza de mejorar la eficiencia de los algoritmos de PLE. BIBLIOGRAFIA Nemnauser, G.,y L. Wotsky, Znteger and Combinatorial Optimization, Wiley, Nueva York, 1988. Parker, G.,y R. RArbIN, Discrete Optimization, Academic Press, Orlando, FL, 1988. SALKIN, H.,y K. MATHUR, Foundations of Integer Programming, North-Holland, Nueva York, 1989. Tana, H., Integer Programming: Theory, Applications, and Computations, Academic Press, Orlando, FL, 1975 PROBLEMAS INTEGRALES mo Una compafiia urbanizadora es propietaria de 90 acres de terreno en un drea metropolitana en crecimiento, donde pretende construir edificios para oficinas y un centro comercial. La propiedad desarrollada se va a rentar durante siete afios y después ser vendida. El precio de venta de cada edificio se calcula en 10 veces mas de su ingreso operacional neto durante el tltimo afio de la renta. La compafifa calcula que el proyecto incluiré un centro comercial de 4.5 millones a construccién de tres edificios para oficinas de mu- de pies cuadrados. El plan maestro requiere cchos pisos y cuatro jardines. La compaiiia se enfrenta a un problema de programacién. Si un edificio se termina de- masiado pronto, puede permanecer desocupado; si se termina demasiado tarde, puede perder alos inquilinos potenciales, que elegirén otros proyectos. La demanda de espacio para oficinas a lo largo de los préximos siete afios, basada en estudios apropiados del mercado, es Demanda (miles de pies cuadrados) Espacio en rascacielos Espacio para jardines 1 200 100 2 220 110 3 242 266 133, 5 293 146 6 322 161 7 354 177406 Cap.9 — Programacién lineal entera ‘La siguiente tabla enumera las capacidades propuestas de los siete edificios: — Capacidad | Rasca- Capacidad Jardin (piescuadrados) | __cielos_(pies cuadrados) 1 00 | 1 350.000 2 60.000 2 450.000 3 75.000 3 350000 4 75.000 - - EL ingreso total bruto por la senta se calcula en 25 délares por pie cuadrado. Los gastos de operacién son de 5.15 y 9.75 délares por pie cuadrado para el jardin y los rascacielos, res- pectivamente. Los costos asociados de constraecicn son de 70 y 105 délares por pie cuadrado, respectivamente. Se calcula que tanto el costo de 1a construccién coma el ingreso por la renta se incrementarén a Ja tasa de inflacién aproximada del 4%. {Cémo debe \a compaiifa programar la construccién de los siete edificios? 9-2? En un concurso de gimnastas femeninas de la National Collegiate Athletic Association, las competencias incluyen cuatro eventos: salto con garrocha, barras desiguales, viga de equilibrio y ejercicios en el piso. Cada equipo puede participar en Ia competencia con seis gimnastas por evento, Se evalia a Jas gimnastas en una escala de 1 al 10, Las estadisticas pasadas del equipo de la U de A producen las siguientes calificaciones: Calificaciones de tas gimnastas de la U de A 12 3 4 5 6 Garrocha 9 8 8 4 10 Baras|7 9 7 8 9 5 | viso{9 8 100 9 9 8 | Piso [6 6 9 w 9 La calificacién total de un equipo se determina sumando las cinco mejores calificaciones individuales para cada evento. Una concursante puede participar como especialista en un evento o en una “ronda completa” de los cuatro eventos pero no en ambos. Se permite que una especialista compita cuando mucho en tres eventos y por lo menos cuatro participantes del equipo deben competir en todos, Determine un modelo de PLE que se pueda utilizar para se- leccionar a los equipos competidores y encuentre la solucién éptima utilizando TORA. 1 9-3° En 1990, habfa en operacién en Estados Unidos aproximadamente 180 000 centros de tele- ‘mercadotecnia, que empleaban a dos millones de personas. Para el aiio 2000,se calcula que mas de 700.000 compafifas emplearén aproximadamente ocho millones de personas en la telemer- *Basado en P.Ells y R. Com, “Using Bivalent Integet Programming to Select Teams of Intercollegiate Women's Gymnastic Competition”, Interfaces vol 14, nim.3,pp. 41-46, 1984 *Basado en T, Spencer, A. Brigandi, D- Dargon, y M. Sheehan, “AT&T's Telemarketing Site Selection § tem Olfers Customer Support”. Interfaces, vol. 20, nim. 1, pp. 83-96, 1990.Sec.9.4 Resumen 407 cadotecnia de sus productos La pregunta de cudntos centros de telemercadotecnia més se deben emplear y en dénde ubicarlos es de primordial importancia. La compajifa ABC esté en proceso de decidir el ntimero de centros de telemercadotecnia que debe emplear y sus ubicaciones. Un centro puede estar ubicado en una de varias areas can: didatas seleccionadas por Ia compafiia y puede servir (parcial o totalmente) a una o més éreas geograficas. Generalmente un area geogréfica se identifica por uno o més cédigos de drea (tele: fonicos). La telemercadotecnia de ABC se concentra en ocho cédigos de area: 501, 918,316,417 314, 816,502 y 606. La siguiente tabla proporciona las ubicaciones candidatas, las reas a las que sirven y el costo de establecer el centro. Ubicacién del centro Cédigos de! érea atendidos _Costo (délares) Dallas, TX 501, 918, 316, 417 500 000 Atlanta, GA 314, 816, 502, 606 800 000 Louisville, KY 918, 316, 417, 314, 816 400 000 Denver, CO 501, 502, 606 900 000 Little Rock, AR 417, 314, 816, 502 300 000 Memphis, TN 606, 501, 316, 417 450 000, St. Louis, MO 816, 502, 606, 314 550.000 Los clientes en todos los cédigos de area pueden tener acceso a cualquiera de los centros tas 24 horas del da. Los costos de comunicacién pot hora entre los centros y 10s c6digos del drea se propor: cionan en la siguiente tabla Del codigo del area A sol 918316417314 SGSCSODS«OG Dallas, TX sia 835——«SCD:SCSTSCSCSS.SCSIA «S20 Auanta, GA sis S18. S22 SIS 826— SMBs SDSS Louisville, KY -S22,—«$25.—=« $12 SY S30 SIT 826.85 Denver, CO $24 sid $14 $126 BIB «§30 Little Rock, AR $19. $23 $16 $23 SIL $28 $2 Memphis, TN $23 $17 $M $20 $23 ga S10. St. Louis, MO $17 S18 $12 $109 $22 FG $2. A ABC le gustarfa seleccionar entre tres y cuatro centros, ,Dénde deben ubicarse?