1.4. Ejemplos de formulacin de modelos de PL.Ejemplo 1-3. PL en horarios para cubrir turnos de trabajo (HORAPRO).

Figura 1-3. Policas para vigilancia de un sector de la ciudad en ejemplo HORAPRO.Cada polica debe laborar 8 horas consecutivas. El periodo 1 sigue al 6.Formule un modelo de PL para determinar el nmero ptimo de policas.Ayuda para el anlisis:En este problema se conoce, que para fines de control, se divide el da completo en periodos de 4 horas de duracin, logrando continuidad de la vigilancia de policas los que deben trabajar durante dos periodos consecutivos. Tambin se sabe el requerimiento en nmero de policas para cada uno de los seis periodos; entonces la siguiente forma tabular puede ser buena ayuda para la comprensin del problema considerando a Xjcomo grupo de policas asignados parainiciarlos periodos j ( j = 1,2,...,6 ).

Figura 1-4. Inicio y permanencia de grupos X j de policas en los periodos j del da en ejemplo HORAPRO.Modelo de programacin lineal.1a parte.- Definicin de variables:

2a parte.- Funcin econmica.- Aqu debe pensarse en el menor nmero de policas necesarios para cumplir, por lo menos, los requeridos en cada uno de los seis periodos j:

3a parte.- Restricciones: La misma tabla da la combinacin de los grupos de policas Xjpara cubrir, como se observa, los requerimientos de cada periodo j.

4a parte.- Condiciones de signo, NO NEGATIVO:

Ejemplo 1-4. PL en la dieta de jugos (BEDIET).Un proveedor de bebidas dietticas debe preparar con las existentes de su bodega, un pedido de 500 litros de ponche diettico el cual debe contener por lo menos 20% de jugo de naranja, 10% de jugo de toronja y 5% de jugo de betabel. La siguiente tabla informa de 5 bebidas existentes con su contenido de jugos y el costo de las mismas. Qu cantidad de cada bebida deber de emplear el proveedor para cumplir el pedido a un costo mnimo? Formule un modelo de programacin lineal que represente este problema.

Figura 1-5. Informacin de bebidas almacenadas en ejemplo BEDIET.Modelo de programacin lineal.1a parte.- Definicin de variables:

2a parte.- Funcin econmica u objetivo:

3a parte: Sujeta a restricciones.-

Restriccin de proporcin de contenido de jugo:Para este tipo de restriccin es necesario convertir la informacin de contenido en por ciento (%) de jugo de la tabla a fraccin decimal de un slo litro del mismo, ya que la definicin de significado de las variables en la primera parte del modelo se hizo como litros de bebida j. Por lo tanto, la fraccin 0.40 400 mililitros de jugo de naranja multiplicado por XAlitros, es la contribucin de la bebida A (0.40XA) para cumplir el 20% (0.20 por litro de ponche) de jugo de naranja en la bebida pedida. Tambin 0.05XBes la contribucin de la bebida B y 1XC, es la contribucin de C (pura naranja) al ponche pedido. Las restricciones de toronja y betabel se formulan de la misma manera.

4a parte.- Condicin de signo para las variables:

Ejemplo 1-5. PL en la inversin de capital (INVECAP).Un banco desea establecer una poltica de prstamo para el siguiente trimestre y por tal motivo asign un presupuesto de 12 millones de dlares para prestarle a sus clientes. En la tabla siguiente se anotan los tipos de prstamo con el inters correspondiente y las probabilidades de no-recuperacin del capital prestado. Lo que no se puede recuperar no tiene intereses. Por competencia con otros bancos, se requiere asignar prstamos de al menos el 40% del total, a los tipos de prstamo 4 y 5. Con la habitacin debe prestarse al menos un 50% de la suma de los prstamos 1, 2, y 3. La poltica de banco es que la relacin total de los irrecuperables sea un mximo de 0.04. Formule un modelo de programacin lineal para este problema de inversin.

Figura 1-6. Informacin de tipo de prstamos bancarios en ejemplo INVECAP.Modelo de programacin lineal1a parte.- Definicin de variables:

2a parte.- Funcin objetivo:

En este problema, a la funcin Z a maximizar se le debe formular con la suma de las contribuciones de rendimiento de los cinco tipos de prstamo, pero descontando la fraccin de irrecuperables los cuales se estiman en la columna derecha de la tabla:

3a parte.- Sujeto a restricciones.

4a parte.- Condiciones de signo.

El conjunto de expresiones en negrita forma el modelo matemtico de programacin linealque se pide formular.Ejemplo 1-6. PL en la seleccin de mquinas para un proceso (MAQUIPRO).Una compaa tiene 3 tipos de mquinas procesadoras con diferentes caractersticas en cuanto a velocidad, precisin y costo de produccin. En la siguiente tabla se resumen las mismas:

Figura 1-7. Informacin de caractersticas de mquinas tipo j en ejemplo MAQUIPRO.Cada da de 8 horas deben producirse 500 piezas. Formule un modelo de programacin lineal para este problema:Modelo matemtico de programacin lineal.1a parte.- Definicin de variables.-Para este problema el estudiante puede razonar a partir de la informacin dada, que se conocen las caractersticas de las mquinas de procesar piezas, pero no cuntas utilizar de cada uno de los tres tipos, puesto que a las diferencias tcnicas entre ellas, se agrega el costo de operarlas. De este modo se define:Sea Xj= nmero de mquinas de tipo j ( j = 1, 2, 3 )necesarias para producir 500 piezas en un da de 8 horas a condicin de hacerlo con el menor costo.2a parte.- Funcin econmica.-La medida para decidir en este problema, es la conveniencia de cumplir la cuota de produccin de 500 piezas en la forma ms econmica posible; para ello es necesario que se involucren los costos asociados con cada tipo j de mquina calculando antes de la formulacin de la funcin Z, el costo Cjcorrespondiente; por lo tanto: Z mnima = suma de contribuciones de costo de los tres tipos de mquina.

Observe que los coeficientes Cjse obtienen sumando, al costo nominal de una hora de proceso, el costo correspondiente a la estimacin de piezas rechazadas, que para el caso de la mquina j =1 es de 10% 0.10 en fraccin decimal multiplicado por 30 piezas producidas en una hora, resulta en 3 piezas con defecto en una hora de proceso. Cada rechazo cuesta un dlar, entonces se suma este costo: 3(1 dlar) = $3, al nominal de $5 y as se tiene C1= $8. Los costos C2y C3se calculan con el mismo criterio.3a parte.- Sujeta a restricciones.-La cuota de produccin de 500 piezas en una jornada de 8 horas conviene convertirla a su equivalente para una sola hora, pues se puede observar que la informacin restante est en esos trminos. La produccin pedida constituye una importante condicin del problema y debe plantearse como restriccin u obligacin, la cual se construye a partir de las velocidades especificadas por mquina tipo j; pero las tasas anotadas son nominales, puesto que se estima un porcentaje de piezas aceptadas para los diferentes tipos j de mquina, en tal caso es necesario ajustar las velocidades o tasas de produccin de acuerdo a su eficiencia para plantear el requerimiento en trminos reales:Aj= Produccin real por mquina tipo j, debido a la eficiencia en piezas buenas.

Otra restriccin a considerar se refiere al nmero total de mquinas de tipo j que se tienen para este proceso de produccin, debindose plantear con desigualdad = 0 ).Anteriormente se determin la desigualdad que representa la restriccin para la materia prima 1 es:

Para mostrar todos los puntos solucin que la satisfacen, se traza la lnea que geomtricamente representa a la ecuacin lineal: 2/5X1+ 1/2X2, = 20 la cual debe ser recta, se calculan dos puntos pertenecientes a la misma y a continuacin se traza una lnea recta a travs de los mismos. Para ello, arbitrariamente se buscan los puntos sobre los ejes en que, por supuesto, se tiene el valor de cero para una de las variables, as al hacer X1= 0, se ubica sobre el eje X2y resolviendo la ecuacin en funcin de la variable X2, queda X2= 20, o tambin X2= 40; por lo tanto el punto (X1=0, X2=40) satisface la ecuacin anterior, pues es la interseccin de las rectas, eje X2y la que representa el recurso 1; alternativamente, para encontrar un segundo punto que satisfaga esta ecuacin se hace X2= 0 y se resuelve en funcin de X1. Al hacerlo se observa que 2/5X1= 20, es decir, X1=50, por lo que un segundo punto que tambin satisface la ecuacin es (X1=50, X2=0). Con estos dos puntos, se puede trazar la recta que se conoce comolnea de restriccin de la materia prima 1, mostrada en laFigura 1-19

Figura 1-19. La lnea recta de restriccin de la materia prima 1, ejemplo QUIMCAR.La desigualdad que representa a la restriccin de la materia prima 1 es:

Puede usted identificar las soluciones que satisfacen esta restriccin?. Observe primero, que cualquiera de la infinidad de puntos que forman la lnea recta de restriccin 2/5X1+ 1/2X2, = 20 debe satisfacer a la misma; pero dnde estn los puntos solucin que satisfacen la desigualdad: 2/5X1+ 1/2X2< 20?. Ahora considere dos puntos de solucin (X1=10, X2=10) y (X1=40, X2=30). LaFigura 1-19muestra que la primera solucin se ubica por debajo de la lnea de restriccin y la segunda queda por encima, entonces cul de estas soluciones satisface la restriccin del recurso 1? Para el punto (X1=10, X2=10), se tiene:

Dado que 9 es menor que 20 toneladas de materia prima 1 disponible, la combinacin o solucin, de productos X1=10 toneladas de cera automotriz, X2=10 toneladas de pasta pulidora satisface la restriccin del recurso 1, en este caso se califica a (10,10) comouna solucin factible. Por otro lado, para X1=40 y X2=30 se tiene:

31 es mayor que las 20 toneladas disponibles de recurso 1, por lo que la solucin X1= 40 toneladas de cera, X2= 30 toneladas de pasta, no satisface la restriccin, y por lo tanto la solucin (40,30)no es factible.Si una solucin particular no es factible, todas las dems soluciones del mismo lado de la lnea recta de restriccin tampoco lo sern. Si una solucin particular es factible, todas las dems soluciones del mismo lado de la lnea de restriccin sern factibles, por lo que solamente es necesario evaluar un punto de solucin para determinar cul es el lado de la lnea de restriccin que representa las soluciones factibles. En laFigura 1-20, el rea factible con todos los puntos que satisfacen la restriccin de la materia prima 1 se muestra sombreada.

Figura 1-20. Regin factible para la restriccin de la materia prima 1, ejemplo QUIMCAR.Se siente capaz de trazar una lnea de restriccin y localizar los puntos de solucin que son factibles?. Si as lo desea intente resolver la restriccin 2.Para el caso que necesite ms instruccin, a continuacin se muestra la identificacin de los puntos de solucin que satisfacen la restriccin de la materia prima 2:

Se empieza dibujando la lnea de restriccin correspondiente a la ecuacin 1/5 X2= 5, que es equivalente a X2= 25, simplemente se dibuja una lnea cuyo valor X2es 25, est lnea es paralela a X1y est a 25 unidades por encima del eje horizontal. En laFigura 1-21se dibuja la lnea recta que corresponde a la restriccin de la materia prima 2, la regin sombreada corresponde a todas las combinaciones de produccin que son soluciones factibles para la restriccin de la materia prima 2.

Figura 1-21. Regin factible de la restriccin de materia prima 2, ejemplo QUIMCAR.De manera similar, se puede diferenciar el conjunto de todas las soluciones factibles para la restriccin de la materia prima 3. LaFigura 1-22muestra la zona de puntos factibles. Como ejercicio prctico, pruebe trazar la regin factible de la restriccin de la materia prima 3 y verifquelo con este grfico.

Figura 1-22. Regin factible para la restriccin de la materia prima 3, ejemplo QUIMCAR.Ahora se tienen tres grficas por separado que muestran las soluciones factibles para cada una de las restricciones. En un problema de programacin lineal, se necesita identificar las soluciones quesatisfacensimultneamente todas las restricciones. Las grficas de lasFigura 1-20,Figura 1-21yFigura 1-22se pueden superponer para obtener una interseccin grfica de las tres restricciones. LaFigura 1-23muestra esta grfica de restricciones combinadas. La regin sombreada de esta figura incluye todos los puntos solucin que simultneamente, satisfacen todas las restricciones. Las soluciones que satisfacen simultneamente todas las restricciones del sistema se conocen como factibles, la parte sombreada se conoce como la regin de soluciones factibles, o simplementeregin factible. Cualquier punto en las fronteras de la regin factible, o bien en su interior, es un punto desolucin factible. Ahora que se ha identificado la regin factible, se puede seguir adelante con el mtodo de solucin grfica y determinar cul es la solucin ptima para el problema de QUIMCAR. Recuerde que la solucin ptima para un problema de programacin lineal es la solucin factible que aporte el mejor valor de la funcin objetivo.

Figura 1-23. Regin de soluciones factibles del problema ejemplo QUIMCAR.Se inicia el paso de optimizacin del procedimiento de solucin grfica volviendo a dibujar la regin factible en una grfica por separado. LaFigura 1-24muestra dicha grfica.El procedimiento para determinar la solucin ptima evaluando la funcin objetivo para cada una de las soluciones factibles, no es posible pues hay demasiadas, (de hecho, una infinidad). Por lo tanto, para identificar la solucin ptima no se debe utilizar un procedimiento de ensayo y error. En vez de intentar calcular la contribucin a la utilidad de cada solucin factible, se selecciona un valor arbitrario de la contribucin a la utilidad y se identifican todas las soluciones factibles (X1, X2) que dan el valor seleccionado.

Figura 1-24. Regin factible del problema ejemplo QUIMCAR.Por ejemplo, qu soluciones factibles dan una contribucin a la utilidad de 2400 dlares? Estas soluciones se dan por los valores de X1y X2de la regin factible que cumplan con la siguiente funcin objetivo que se puede simplificar para obviar clculos, as:

sta expresin es simplemente la ecuacin de una lnea recta, por lo que todas las soluciones factibles (X1, X2), con una contribucin a la utilidad de 24 dlares deben estar en esta lnea. Ya se aprendi como trazar una lnea de restriccin; el procedimiento para trazar la lnea de la funcin objetivo o de utilidad es el mismo. Haciendo X1=0, se tiene que X2debe ser 8; entonces, el punto de solucin (X1=0, X2=8) est en la recta. Similarmente, haciendo X2= 0, se tiene que el punto de solucin (X1=6, X2= 0), tambin est en la recta. Dibujando la lnea recta por estos puntos, se identifican todas las soluciones que tienen una contribucin a la utilidad de 24; una grfica de esta lnea de utilidad se presenta en laFigura 1-25que muestra un nmero infinito de combinaciones factibles de produccin que darn una contribucin de 24 a la utilidad.

Utilizando el procedimiento anterior para el trazado de rectas de utilidad y de restriccin, se trazan la lnea de utilidad de 72 y 120 que se presentan en la mismaFigura 1-25. Por supuesto, slo los puntos de las rectas de valor 24, 72 y 120 que estn dentro de la regin factible, deben considerarse como soluciones factibles para tal contribucin de utilidad.

Figura 1-25. Diferentes lneas de utilidad para el problema ejemplo QUIMCARDado que las rectas de utilidad son paralelas y de valor creciente conforme se alejan del origen, se pueden obtener valores mayores para la funcin objetivo, continuando el movimiento hacia fuera del conjunto factible pero mantenindose adentro del mismo, hasta alcanzar el (los) ltimo(s) punto(s) vrtice antes de salir. Dado que los puntos fuera de la regin factible no son aceptables, el (los) punto(s) vrtice en la regin factible que coincide(n) conla recta de utilidad mayor es una solucin ptimaal programa lineal.El estudiante debe identificar ahora, el punto de solucin ptimo para el problema ejemplo QUIMCAR. Utilice una regla y escuadra, mueva paralelamente la recta de utilidad tan lejos del origen como pueda, pero conservando el contacto en la zona factible. Cul es el ltimo punto de la regin factible? Este punto debe ser vrtice y corresponde a la solucin ptima, vea el grfico de laFigura 1-26. Los valores ptimos para las variables de decisin son ( X1, X2) = ( 25, 20 ).

Figura 1-26. Solucin ptima para el problema ejemplo QUIMCAR.Dependiendo del tamao y claridad de su grfica, se determinan los valores ptimos exactos de X1y X2leyendo directamente de la grfica. Pero observe en laFigura 1-23, la solucin ptima del ejemplo est en lainterseccinde las rectas de restriccin 1 y 3 que se pueden resolver para precisar los valores coordenados.

Por lo que los valores de las variables de decisin X1y X2debern satisfacer las ecuaciones de manera simultnea. Resolviendo en funcin de X1en (1)

Sustituyendo esta expresin (4) de X1en la ecuacin (3) y resolviendo en funcin de X2se obtiene

Sustituyendo X2=20 en la ecuacin (4) y resolviendo en funcin de X1, resulta

A pesar de que la solucin ptima para el problema est formada de valores enteros de las variables de decisin, esto no ser siempre el caso. La localizacin exacta del punto de solucin ptima esX1=25 y X2=20. Este punto identifica las cantidades ptimas de produccin para QUIMCAR en 25 toneladas de cera automotriz y 20 toneladas de pasta pulidora, con una contribucin a la utilidad de:

As, en un problema de programacin lineal con dos variables de decisin, se puede determinar el valor exacto de las variables de la solucin ptima, utilizando primero el mtodo grfico para identificar el punto que optimiza y despus resolviendo simultneamente las dos ecuaciones que generan el mismo.Trazo de lneas rectasUn aspecto importante del mtodo grfico es la posibilidad de trazar lneas rectas representando las restricciones y la funcin objetivo del programa lineal. El procedimiento ms sencillo para trazar la recta de una ecuacin, es encontrando dos puntos cualesquiera que la satisfagan y a continuacin trazando la recta a travs de dichos puntos. En el caso de la lnea recta de restriccin de la materia prima 1 del problema QUIMCAR

se identifican los dos puntos (X1= 0, X2= 40) y (X1= 50, X2= 0). Despus se traza la lnea recta de restriccin de la materia prima 1 a travs de estos dos puntos.Cuando en la ecuacin de restriccin slo aparece una variable, como es el caso de la materia prima 2 del problema (1/5 X2= 0, X2>= 0) correspondiente al primer cuadrante de la grfica, entonces no se puede fijar el primer punto (X1= 0, X2= -100), porque no hay escala para valores negativos en la grfica tal como es X2= -100. Siempre que se tengan dos puntos de la recta, con uno o ambos valores negativos, el procedimiento grfico obligado es incluir la escala negativa a los dos ejes coordenados horizontal y vertical, incluyendo los cuadrantes necesarios. En este ejemplo, se puede localizar el punto (X1= 0, X2= -100) extendiendo hacia abajo el eje vertical para incluir los valores negativos de X2. Una vez localizados los dos puntos que satisfacen la ecuacin y el conjunto de soluciones factibles para la nueva restriccin de ejemplo 2X2- 1X2= 0.

Figura 1-28. Soluciones factibles de la restriccin 1X1- 1X2>= 0Resumen del mtodo de solucin grfica en dos variables.1. Dibuje en un sistema de dos ejes cartesianos (por ejemplo X1para la coordenada horizontal y X2para la coordenada vertical) las lneas rectas correspondientes a cada una de las expresiones lineales del modelo de programacin lineal, identificando las mismas, calcule y anote las coordenadas (valores de X1y X2) para cada punto vrtice.2. Observe la direccin de las desigualdades para definir, individualmente, el conjunto de puntos de solucin factible de cada una de las restricciones y posteriormente, combinando todas ellas, por interseccin o traslape, definir y sealar el conjunto de puntos de solucin factible para todo el sistema de restricciones del problema.3. Con un valor arbitrario para la funcin Z, calcule las coordenadas de un punto perteneciente a cada uno de los dos ejes cartesianos, dando alternativamente el valor de cero a X1y X2de la funcin objetivo Z, ahora se traza una recta que pase por dichos puntos en los ejes, la cual muestra todos los valores posibles de X1y X2de la misma.4. Mueva la recta de la funcin objetivo Z paralelamente hacia valores mayores de la funcin, si el problema es de mximo, o bien, hacia valores menores, si el problema es de mnimo, hasta que coincida con un punto vrtice, antes de salir de la regin factible. La recta de la funcin objetivo se cuantifica con los valores ( X1, X2) al coincidir con el vrtice; su valor crecer o bien decrecer conforme a su traslado paralelo, segn sean los signos de sus trminos.5. Cualquier punto vrtice que sea solucin factible para el sistema de restricciones que coincida con la recta de la funcin objetivo que resulte con el valor mayor para un mximo o bien con el menor para un mnimo, segn el caso, es una solucin ptima.Variables de HolguraAdems de la solucin ptima y de su contribucin a la utilidad asociada, la administracin de QUIMCAR desea tener informacin de uso de las tres materias primas. Se puede obtener esta informacin reemplazando los valores ptimos de las variables (X1=25, X2=20) en las restricciones del programa lineal.

Figura 1-29. Material consumido: solucin ptima cera y pasta, ejemplo QUIMCAR.La solucin completa le indica a la administracin que la produccin de 25 toneladas de cera automotriz y de 20 toneladas de pasta pulidora requiere toda la materia prima disponible 1 y 3, pero solamente cuatro de las cinco toneladas de la materia prima 2. La tonelada de la materia prima 2 no utilizada se conoce comoholgura.En terminologa de programacin lineal,cualquier capacidad sin utilizar y ociosapara una restriccin igual o menor (