Programacion lineal

Programacion lineal

miércoles, 23 de mayo de 2012

Método gráfico


El método gráfico se emplea para resolver problemas que presentan sólo 2 variables de decisión. El procedimiento consiste en trazar las ecuaciones de las restricciones en un eje de coordenadas X1, X2 para tratar de identificar el área de soluciones factibles (soluciones que cumplen con todas las restricciones).
La solución óptima del problema se encuentra en uno de los vértices de esta área de soluciones creada, por lo que se buscará en estos datos el valor mínimo o máximo del problema.

Procedimiento:

Primero considere la infinidad de puntos que constituyen en conjunto el plano y los cuatro cuadrantes convencionalmente aceptados, para dividirlo en zonas caracterizadas por la combinación de signo que se puede dar, a los valores medidos con números reales. Para lograr los cuadrantes en el plano se utilizan los ejes cartesianos con escala de medición de valores de las variables del problema; por ejemplo, se puede asignar el eje horizontal de abscisas para la medición de valores de la variable X1; también se puede asignar el eje vertical de ordenadas, para la medición de valores de la variable X2. La localización de cualquier punto en este espacio plano requiere de una distancia horizontal (X1) y de una distancia vertical (X2) denotado como par ordenado o vector (X1, X2). Un punto sobre el eje X1 corresponde a X2=0 y un punto sobre el eje X2 corresponde a X1=0, que son las ecuaciones respectivas de los ejes horizontal y vertical. Dichos ejes se cruzan en el punto (X1, X2) = (0, 0), el cual se conoce como origen.
Si la ecuación tiene sólo dos variables, el gráfico de la misma sobre el plano es una línea recta, es decir, se requiere un espacio de dos dimensiones, la horizontal y la vertical, para graficar tal ecuación; pero la representación geométrica de una ecuación en tres variables, requiere un espacio de tres dimensiones. En tal caso, a los ejes X1 y X2, se les agrega un tercer eje X3 como tercera dimensión, que pasa por el origen hacia el observador. Los gráficos de la Figura A y Figura B muestran lo anterior para una ecuación 
cualquiera:





Figura A. Gráfico de una ecuación en dos dimensiones.

Figura B. Gráfico de una ecuación en tres dimensiones.
El método gráfico proporciona la oportunidad de visualizar algunos de los conceptos importantes de la programación lineal. Pero tiene una gran limitación referente, a que sólo es posible aplicarlo en problemas muy pequeños; para este curso se limita el método gráfico aplicado a problemas con sólo dos variables. El método gráfico para resolver problemas que se han modelado con programación lineal consiste en asignar un eje cartesiano para cada una de las dos variables involucradas; de esta manera se asigna, por ejemplo, el eje horizontal como escala para los distintos valores que pueda tener la variable X1; también se puede asignar el eje vertical con su respectiva escala para ubicar los distintos valores que puede tomar la variable X2. Un sistema con dos ejes cartesianos, horizontal y vertical, permite representar en un espacio plano las líneas rectas que geométricamente hablando representan cada expresión matemática lineal con sólo dos variables. Las restricciones y condiciones de signo del problema, representan al sistema que debe graficarse en un plano y después se valora en el mismo la función económica Z, con la cual se busca un punto del sistema que maximice o bien minimice su valor.
Para mejor comprensión del método gráfico de solución de problemas modelados con programación lineal, se presenta el siguiente ejemplo que se detalla lo suficiente para el voluntarioso estudiante de esta técnica poderosa en su aplicación. Posteriormente se presentan otros ejemplos con el propósito de profundizar en la enseñanza e intentar mayor avance en el aprendizaje.


Ejemplo:

QUIMCAR es una empresa que elabora varios productos químicos. En un proceso de producción en particular se utilizan tres recursos como materia prima de dos productos: una cera automotriz y una pasta pulidora, que se usan en la pintura de la carrocería a vehículos automotores y se distribuye para su venta al menudeo a varias empresas distribuidoras. Para producir la cera y la pasta se utilizan tres recursos, según se muestra en la siguiente tabla, en la cual se observa que una tonelada de cera es una mezcla de 2/5 de tonelada del recurso 1 y 3/5 de tonelada del 3. Por otro lado, una tonelada de pasta es la mezcla de 1/2, 1/5 y 3/10 de tonelada de los recursos 1,2 y 3, respectivamente.
La producción de la cera automotriz y la pasta pulidora está restringida a la disponibilidad de los tres recursos. Para el periodo de producción anual, se tienen disponibles las cantidades siguientes de cada una de las materias primas.



Figura 1-15. Recursos disponibles para la producción en ejemplo QUIMCAR.



Figura 1-16. Material requerido para cera y pasta pulidora en ejemplo QUIMCAR.

El departamento de contabilidad ha analizado las cifras de producción, asignando los costos correspondientes para ambos productos, llegó a precios que resultan en una contribución a la utilidad de 400 dólares por cada tonelada de cera automotriz y de 300 dólares por cada tonelada de pasta pulidora, producidas. La administración, después de analizar la demanda potencial, ha concluido que los precios establecidos aseguran la venta de toda la cera y pasta que se produzca.
El problema es determinar: 1º.-Un conjunto de expresiones matemáticas o modelo, representando el objetivo y restricciones del problema descrito. 2º.- Resolver en forma gráfica y determinar cuántas toneladas de cera y pasta debe producir la empresa para maximizar la contribución total a la utilidad.
Definición de las variables y función objetivo
Como ya se apuntó anteriormente, los problemas de programación lineal tienen un objetivo ya sea de máximo o bien de mínimo. En este problema, el objetivo es de maximizar la contribución a la utilidad y se plantea en forma matemática introduciendo alguna forma simple de notación, como sigue:

1a. Parte.-Definición de variables.-
Es importante precisar la unidad de medida:




2a. parte.- Función objetivo.-
La contribución a la utilidad se origina de: (1) la que proviene de la producción de X1 toneladas de cera automotriz, y (2) la que proviene de la producción de X2 toneladas de pasta pulidora. Dado que se gana 400 dólares por cada tonelada de cera producida, la empresa gana $400 X1 si se producen X1 toneladas de cera. También, en vista de que se gana 300 dólares por cada tonelada de pasta producida, la empresa gana$300 X2 si se producen X2 toneladas de pasta. Identificando con Z la contribución total a la utilidad y eliminando el signo de dólares se tiene:






El problema es encontrar la combinación de producción que maximice la contribución total a la utilidad. Esto es, se deben determinar los valores para X1 y X2 que den el valor más elevado posible de Z. En terminología de programación lineal, se nombran a X1 y a X2 como las variables de decisión. Dado que el objetivo de maximizar la utilidad es una función de éstas, entonces se dice que Z = 400 X1 + 300 X2 es la función objetivo, que también se puede escribir abreviando los coeficientes a unidades que significan cientos de dólares por tonelada producida, como sigue:






Cualquier combinación de producción de cera y pasta se conoce como una solución al problema. Sin embargo, únicamente aquellas soluciones que satisfagan todas las restricciones se conocen comosoluciones factibles o posibles. La combinación específica de producción factible, que resulte en la contribución mayor a la utilidad, se conoce como la combinación de producción óptima, o simplemente, la solución óptima. Pero primero se requiere conocer todas las restricciones del problema y posteriormente se muestra un método para definir gráficamente, en el plano de dibujo, el espacio en que se ubican el conjunto de puntos de solución factible.
3a. Parte.- Restricciones de materia prima.
La cantidad de materia prima disponible, condiciona o sujeta el valor de la función objetivo para cumplirse con los tres recursos limitados, calculando las posibles soluciones en las cantidades de cera y pasta que se pueden producir. Según la información de producción (vea la tabla), se sabe que cada tonelada de cera automotriz utiliza 2/5 toneladas del recurso 1, por lo que el total de toneladas del mismo utilizado en la producción de X1 toneladas de cera es 2/5X1; además, cada tonelada de pasta usa 1/2 tonelada del recurso 1, como resultado, X2 toneladas de pasta usan 1/2 X2 toneladas de recurso 1, entonces el consumo total de toneladas de recurso 1 para producir X1 de cera y X2 de pasta está dado por






Debido a que se tiene un máximo de 20 toneladas de materia prima 1 disponible, la combinación de producción a decidir debe satisfacer la restricción






La relación anterior es una desigualdad que anota las contribuciones al consumo de recurso 1, utilizadas en la producción de X1 toneladas de cera y de X2 toneladas de pasta, que debe ser menos que o igual a 20 toneladas disponibles.
La tabla indica que el recurso 2 no es requerido por la cera, pero si por la pasta pues cada tonelada producida de ésta requiere 1/5 tonelada de las 5 disponibles, se expresa así:






Si desea, ahora verifique por sí mismo que la restricción para la materia prima 3 es






Hasta aquí se han definido, las restricciones de materia prima; sólo falta establecer que las toneladas de cera y pasta no puede ser un número negativo.
4a parte.- Condiciones de valor no negativo para las variables:



Esto asegura valores no negativos de las variables de decisión como solución al problema presente, se conocen como restricciones de no negatividad y son una característica general de los problemas de programación lineal.
Modelo matemático del problema de Quimcar.
La formulación matemática o modelo simbólico, representa en forma abstracta, el objetivo y las restricciones del problema, trasladados del mundo real a un conjunto de relaciones matemáticas. El modelo completo del problema es:




Ahora sólo falta encontrar la combinación de productos cera y pasta expresados como toneladas de X1 y X2 que satisface todas las restricciones y también resulte en un valor máximo de la función objetivo, comparado con el valor de cualquier otra solución factible, lo que significa la solución óptima del problema.
Este modelo matemático del problema es programación lineal, tiene una función objetivo y restricciones, todas con la característica especial de que son una función lineal de las variables de decisión.
Las funciones matemáticas en las cuales sólo una de las variables aparece elevada a la primera potencia como un término independiente, se conocen como funciones lineales. La función objetivo 4X1 + 3X2 es lineal, porque cada una de las variables de decisión aparece en un término por separado con exponente 1. Si la función objetivo se presentara como 4X21 + 3X32, no se trataría de una función lineal. Por la misma razón, el número de toneladas de la materia prima 1 requerida, 2/5X1+1/2X2 , también es una función lineal de las variables de decisión. Similarmente, el lado izquierdo de todas las desigualdades de restricción son funciones lineales, así la formulación matemática del problema anterior se identifica como un programa lineal.

Solución gráfica

Un problema de programación lineal con sólo dos variables de decisión se puede resolver de manera gráfica sobre el espacio plano. Se inicia este procedimiento de solución desarrollando una gráfica que despliegue las posibles soluciones (valores X1 y X2) para el problema QUIMCAR. En la Figura 1-17 aparecen los valores de X1 sobre un eje horizontal y los valores de X2 sobre uno vertical. De esta manera se divide el plano o papel de trabajo, en cuatro espacios limitados por los ejes, formando así los cuadrantes 1, 2, 3 y 4. Cualquier punto de la gráfica puede quedar identificado por un par de valores X1 y X2, que representa la posición del punto con respecto de los ejes X1 y X2. Cada par (X1, X2) corresponde a un punto solución de esta manera se tendría una infinidad de ellos en el plano considerado. Pero para la solución particular en la que X1 = 0 y X2 = 0, se ubica un punto vértice identificado como origen para ambos ejes.



Figura 1-17. Algunos puntos solución para el problema QUIMCAR.
El siguiente paso es mostrar, qué puntos corresponden a soluciones factibles del programa lineal. Tanto X1 como X2 deben ser de valor no negativo, por lo que sólo es necesario considerar la porción de la gráfica en donde X1 >= 0 y X2 >= 0, lo que se conoce como primer cuadrante. En la Figura 1-18 las flechas indican el primer cuadrante, o sea, la región donde estos requisitos de no negatividad quedan satisfechos para la solución buscada.



Figura 1-18. Gráfica del primer cuadrante. Cumple las restricciones de no negatividad ( >= 0 ).
Anteriormente se determinó la desigualdad que representa la restricción para la materia prima 1 es:




Para mostrar todos los puntos solución que la satisfacen, se traza la línea que geométricamente representa a la ecuación lineal: 2/5X1 + 1/2X2, = 20 la cual debe ser recta, se calculan dos puntos pertenecientes a la misma y a continuación se traza una línea recta a través 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 X2 y resolviendo la ecuación en función de la variable X2, queda ½ X2 = 20, o también X2 = 40; por lo tanto el punto (X1=0, X2=40) satisface la ecuación anterior, pues es la intersección de las rectas, eje X2 y la que representa el recurso 1; alternativamente, para encontrar un segundo punto que satisfaga esta ecuación se hace X2 = 0 y se resuelve en función de X1. Al hacerlo se observa que 2/5X1 = 20, es decir, X1=50, por lo que un segundo punto que también satisface la ecuación es (X1=50, X2=0). Con estos dos puntos, se puede trazar la recta que se conoce como línea de restricción de la materia prima 1, mostrada en la Figura 1-19



Figura 1-19. La línea recta de restricción de la materia prima 1, ejemplo QUIMCAR.
La desigualdad que representa a la restricción de la materia prima 1 es:




¿Puede usted identificar las soluciones que satisfacen esta restricción?. Observe primero, que cualquiera de la infinidad de puntos que forman la línea recta de restricción 2/5X1 + 1/2X2, = 20 debe satisfacer a la misma; pero ¿dónde están los puntos solución que satisfacen la desigualdad: 2/5X1 + 1/2X2 < 20?. Ahora considere dos puntos de solución (X1 =10, X2 =10) y (X1 =40, X2 =30). La Figura 1-19muestra que la primera solución se ubica por debajo de la línea de restricción y la segunda queda por encima, entonces ¿cuál de estas soluciones satisface la restricción 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 combinación o solución, de productos X1=10 toneladas de cera automotriz, X2=10 toneladas de pasta pulidora satisface la restricción del recurso 1, en este caso se califica a (10,10) como una solución 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 solución X1 = 40 toneladas de cera, X2 = 30 toneladas de pasta, no satisface la restricción, y por lo tanto la solución (40,30) no es factible.
Si una solución particular no es factible, todas las demás soluciones del mismo lado de la línea recta de restricción tampoco lo serán. Si una solución particular es factible, todas las demás soluciones del mismo lado de la línea de restricción serán factibles, por lo que solamente es necesario evaluar un punto de solución para determinar cuál es el lado de la línea de restricción que representa las soluciones factibles. En la Figura 1-20 , el área factible con todos los puntos que satisfacen la restricción de la materia prima 1 se muestra sombreada.



Figura 1-20. Región factible para la restricción de la materia prima 1, ejemplo QUIMCAR.
¿Se siente capaz de trazar una línea de restricción y localizar los puntos de solución que son factibles?. Si así lo desea intente resolver la restricción 2.
Para el caso que necesite más instrucción, a continuación se muestra la identificación de los puntos de solución que satisfacen la restricción de la materia prima 2:

Se empieza dibujando la línea de restricción correspondiente a la ecuación 1/5 X2 = 5, que es equivalente a X2 = 25, simplemente se dibuja una línea cuyo valor X2 es 25, está línea es paralela a X1 y está a 25 unidades por encima del eje horizontal. En la Figura 1-21 se dibuja la línea recta que corresponde a la restricción de la materia prima 2, la región sombreada corresponde a todas las combinaciones de producción que son soluciones factibles para la restricción de la materia prima 2.



Figura 1-21. Región factible de la restricción de materia prima 2, ejemplo QUIMCAR.
De manera similar, se puede diferenciar el conjunto de todas las soluciones factibles para la restricción de la materia prima 3. La Figura 1-22 muestra la zona de puntos factibles. Como ejercicio práctico, pruebe trazar la región factible de la restricción de la materia prima 3 y verifíquelo con este gráfico.


La segunda parte se continuara en la siguiente entrada.

No hay comentarios:

Publicar un comentario en la entrada