Método gráfico parte 2

Figura 1-22. Región factible para la restricción de la materia prima 3, ejemplo QUIMCAR.

Ahora se tienen tres gráficas por separado que muestran las soluciones factibles para cada una de las restricciones. En un problema de programación lineal, se necesita identificar las soluciones que satisfacensimultáneamente todas las restricciones. Las gráficas de las Figura 1-20, Figura 1-21 y Figura 1-22 se pueden superponer para obtener una intersección gráfica de las tres restricciones. La Figura 1-23 muestra esta gráfica de restricciones combinadas. La región sombreada de esta figura incluye todos los puntos solución que simultáneamente, satisfacen todas las restricciones. Las soluciones que satisfacen simultáneamente todas las restricciones del sistema se conocen como factibles, la parte sombreada se conoce como la región de soluciones factibles, o simplemente región factible. Cualquier punto en las fronteras de la región factible, o bien en su interior, es un punto de solución factible. Ahora que se ha identificado la región factible, se puede seguir adelante con el método de solución gráfica y determinar cuál es la solución óptima para el problema de QUIMCAR. Recuerde que la solución óptima para un problema de programación lineal es la solución factible que aporte el mejor valor de la función objetivo.

Figura 1-23. Región de soluciones factibles del problema ejemplo QUIMCAR.

Se inicia el paso de optimización del procedimiento de solución gráfica volviendo a dibujar la región factible en una gráfica por separado. La Figura 1-24 muestra dicha gráfica.

El procedimiento para determinar la solución óptima evaluando la función objetivo para cada una de las soluciones factibles, no es posible pues hay demasiadas, (de hecho, una infinidad). Por lo tanto, para identificar la solución óptima no se debe utilizar un procedimiento de ensayo y error. En vez de intentar calcular la contribución a la utilidad de cada solución factible, se selecciona un valor arbitrario de la contribución a la utilidad y se identifican todas las soluciones factibles (X₁, X₂) que dan el valor seleccionado.

Figura 1-24. Región factible del problema ejemplo QUIMCAR.

Por ejemplo, ¿qué soluciones factibles dan una contribución a la utilidad de 2400 dólares? Estas soluciones se dan por los valores de X₁ y X₂ de la región factible que cumplan con la siguiente función objetivo que se puede simplificar para obviar cálculos, así:

Ésta expresión es simplemente la ecuación de una línea recta, por lo que todas las soluciones factibles (X₁, X₂), con una contribución a la utilidad de 24 dólares deben estar en esta línea. Ya se aprendió como trazar una línea de restricción; el procedimiento para trazar la línea de la función objetivo o de utilidad es el mismo. Haciendo X₁=0, se tiene que X₂ debe ser 8; entonces, el punto de solución (X₁=0, X₂=8) está en la recta. Similarmente, haciendo X₂ = 0, se tiene que el punto de solución (X₁=6, X₂ = 0), también está en la recta. Dibujando la línea recta por estos puntos, se identifican todas las soluciones que tienen una contribución a la utilidad de 24; una gráfica de esta línea de utilidad se presenta en la Figura 1-25 que muestra un número infinito de combinaciones factibles de producción que darán una contribución de 24 a la utilidad.

Utilizando el procedimiento anterior para el trazado de rectas de utilidad y de restricción, se trazan la línea de utilidad de 72 y 120 que se presentan en la misma Figura 1-25. Por supuesto, sólo los puntos de las rectas de valor 24, 72 y 120 que están dentro de la región factible, deben considerarse como soluciones factibles para tal contribución de utilidad.

Figura 1-25. Diferentes líneas de utilidad para el problema ejemplo QUIMCAR

Dado que las rectas de utilidad son paralelas y de valor creciente conforme se alejan del origen, se pueden obtener valores mayores para la función objetivo, continuando el movimiento hacia fuera del conjunto factible pero manteniéndose adentro del mismo, hasta alcanzar el (los) último(s) punto(s) vértice antes de salir. Dado que los puntos fuera de la región factible no son aceptables, el (los) punto(s) vértice en la región factible que coincide(n) con la recta de utilidad mayor es una solución óptima al programa lineal.

El estudiante debe identificar ahora, el punto de solución ó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. ¿Cuál es el último punto de la región factible? Este punto debe ser vértice y corresponde a la solución óptima, vea el gráfico de la Figura 1-26. Los valores óptimos para las variables de decisión son ( X₁, X₂) = ( 25, 20 ).

Figura 1-26. Solución óptima para el problema ejemplo QUIMCAR.

Dependiendo del tamaño y claridad de su gráfica, se determinan los valores óptimos exactos de X₁ y X₂ leyendo directamente de la gráfica. Pero observe en la Figura 1-23, la solución óptima del ejemplo está en laintersección de las rectas de restricción 1 y 3 que se pueden resolver para precisar los valores coordenados.

Por lo que los valores de las variables de decisión X₁ y X₂ deberán satisfacer las ecuaciones de manera simultánea. Resolviendo en función de X₁ en (1)

Sustituyendo esta expresión (4) de X₁ en la ecuación (3) y resolviendo en función de X₂ se obtiene

Sustituyendo X₂ =20 en la ecuación (4) y resolviendo en función de X₁, resulta

A pesar de que la solución óptima para el problema está formada de valores enteros de las variables de decisión, esto no será siempre el caso. La localización exacta del punto de solución óptima es X₁ =25 y X₂ =20. Este punto identifica las cantidades óptimas de producción para QUIMCAR en 25 toneladas de cera automotriz y 20 toneladas de pasta pulidora, con una contribución a la utilidad de:

Así, en un problema de programación lineal con dos variables de decisión, se puede determinar el valor exacto de las variables de la solución óptima, utilizando primero el método gráfico para identificar el punto que optimiza y después resolviendo simultáneamente las dos ecuaciones que generan el mismo.

Trazo de líneas rectas

Un aspecto importante del método gráfico es la posibilidad de trazar líneas rectas representando las restricciones y la función objetivo del programa lineal. El procedimiento más sencillo para trazar la recta de una ecuación, es encontrando dos puntos cualesquiera que la satisfagan y a continuación trazando la recta a través de dichos puntos. En el caso de la línea recta de restricción de la materia prima 1 del problema QUIMCAR

se identifican los dos puntos (X₁ = 0, X₂ = 40) y (X₁ = 50, X₂ = 0). Después se traza la línea recta de restricción de la materia prima 1 a través de estos dos puntos.

Cuando en la ecuación de restricción sólo aparece una variable, como es el caso de la materia prima 2 del problema (1/5 X₂ <= 5), se resuelve en función de la única variable que aparece en la ecuación (para esta restricción, X₂ =25); es claro que en tal ecuación X₁ = 0 pues no está presente, así (X₁ =0, X₂ =25) representa el punto en el eje X₂ por donde debe pasar una recta paralela al eje X₁.

Todas las rectas de restricción y de funciones objetivo en los programas lineales de dos variables, se pueden trazar si se pueden identificar los puntos de la línea. Sin embargo, determinar dichos puntos no siempre es tan fácil como resultó en el problema QUIMCAR. Por ejemplo, considere la restricción:

Usando la forma de igualdad y haciendo X₁ = 0, se tiene que el punto (X₁ = 0, X₂ = -100) pertenece a la recta de restricción. Si X₂=0, se tiene el segundo punto (X₁ = 50, X₂ = 0) sobre la misma recta de restricción. Si se ha dibujado sólo la porción no negativa (X₁ >= 0, X₂ >= 0) correspondiente al primer cuadrante de la gráfica, entonces no se puede fijar el primer punto (X₁ = 0, X₂ = -100), porque no hay escala para valores negativos en la gráfica tal como es X₂ = -100. Siempre que se tengan dos puntos de la recta, con uno o ambos valores negativos, el procedimiento gráfico 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 (X₁ = 0, X₂ = -100) extendiendo hacia abajo el eje vertical para incluir los valores negativos de X₂. Una vez localizados los dos puntos que satisfacen la ecuación y el conjunto de soluciones factibles para la nueva restricción de ejemplo 2X₂ - 1X₂ <= 100, entonces se procede a su trazo, según se ve en la siguiente figura: .

Figura 1-27. Soluciones factibles de la restricción 2X₁-1X₂ <= 100

Considere ahora la restricción: 1X₁ - 1X₂ >= 0 mostrada en la Figura 1-28. El lado derecho con valor cero en esta desigualdad, identifica una línea recta que contiene o pasa por el punto vértice conocido como origen. Para determinar las soluciones que satisfacen la restricción como igualdad, primero se hace X₁ = 0 y se resuelve en función de X₂. El resultado muestra que el origen (X₁= 0, X₂ = 0) está en la recta de restricción. Al hacer X₂ = 0 y al resolver para X₁, resulta en el mismo punto. Pero se puede obtener otro punto de la recta, al dar a X₂ un valor cualquiera distinto de cero y entonces resolver en función de X₁. Por ejemplo, haciendo que X₂ = 100 y resolviendo en función de X₁, se encuentra que el punto (X₁ = 100, X₂ = 100) también pertenece a la recta. En ambos puntos (X₁=0, X₂= 0) y (X₁ = 100, X₂ = 100) se puede trazar la línea de restricción 1X₁-1X₂= 0 y pueden determinarse las soluciones factibles para 1X₁ - 1X₂ >= 0.

Figura 1-28. Soluciones factibles de la restricción 1X₁ - 1X₂ >= 0

Resumen del método de solución gráfica en dos variables.

1. Dibuje en un sistema de dos ejes cartesianos (por ejemplo X₁ para la coordenada horizontal y X₂ para la coordenada vertical) las líneas rectas correspondientes a cada una de las expresiones lineales del modelo de programación lineal, identificando las mismas, calcule y anote las coordenadas (valores de X₁ y X₂) para cada punto vértice.
2. Observe la dirección de las desigualdades para definir, individualmente, el conjunto de puntos de solución factible de cada una de las restricciones y posteriormente, combinando todas ellas, por intersección o traslape, definir y señalar el conjunto de puntos de solución factible para todo el sistema de restricciones del problema.
3. Con un valor arbitrario para la función Z, calcule las coordenadas de un punto perteneciente a cada uno de los dos ejes cartesianos, dando alternativamente el valor de cero a X₁ y X₂ de la función objetivo Z, ahora se traza una recta que pase por dichos puntos en los ejes, la cual muestra todos los valores posibles de X₁ y X₂ de la misma.
4. Mueva la recta de la función objetivo Z paralelamente hacia valores mayores de la función, si el problema es de máximo, o bien, hacia valores menores, si el problema es de mínimo, hasta que coincida con un punto vértice, antes de salir de la región factible. La recta de la función objetivo se cuantifica con los valores ( X₁, X₂ ) al coincidir con el vértice; su valor crecerá o bien decrecerá conforme a su traslado paralelo, según sean los signos de sus términos.
5. Cualquier punto vértice que sea solución factible para el sistema de restricciones que coincida con la recta de la función objetivo que resulte con el valor mayor para un máximo o bien con el menor para un mínimo, según el caso, es una solución óptima.

Variables de Holgura

Además de la solución óptima y de su contribución a la utilidad asociada, la administración de QUIMCAR desea tener información de uso de las tres materias primas. Se puede obtener esta información reemplazando los valores óptimos de las variables (X₁=25, X₂=20) en las restricciones del programa lineal.

Figura 1-29. Material consumido: solución óptima cera y pasta, ejemplo QUIMCAR.

La solución completa le indica a la administración que la producción 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 como holgura. En terminología de programación lineal, cualquier capacidad sin utilizar y ociosa para una restricción igual o menor (<=) se llama holgura asociada con la restricción, por lo que la restricción del recurso 2 tiene una holgura de una tonelada.

A menudo se agregan variables, conocidas como variables de holgura H_i, o bien X_i, (según la notación preferida) a la formulación de un problema de programación lineal para representar la capacidad ociosa. La capacidad sin utilizar no hace ninguna contribución a la utilidad, por lo que las variables de holgura que se incluyan en la función objetivo deben tener coeficientes iguales a cero. En general, las variables de holgura representan la diferencia entre los lados derecho e izquierdo de una restricción de tipo <=.

Una vez agregadas las variables de holgura a la representación matemática correspondiente al problema QUIMCAR el modelo matemático se convierte en:

Cuando todas las restricciones de un problema lineal se expresan en forma de igualdades, se dice que el modelo matemático está en forma estándar. En el problema QUIMCAR se observa que en la solución óptima (X₁=25, X₂ =20), el valor de las variables de holgura es:

Figura 1-30. Holguras de materia prima en ejemplo QUIMCAR.

Figura 1-31. Concepto físico de la holgura H₂ en ejemplo QUIMCAR.

También se puede utilizar el análisis gráfico para obtener la información de las holguras. Observe que al determinar la solución óptima de la Figura 1-26, el punto vértice que es intersección de la materia prima 1 y de la 3, restringen o limitan la región factible hasta ese punto vértice, por lo que la solución óptima requiere usar la totalidad de estos dos recursos. En otras palabras, la gráfica en Figura 1-23 muestra que en la solución óptima, la línea recta de restricción de la materia prima 2 no limita la región factible en ese punto vértice, por lo que se puede esperar algún sobrante (holgura) de este recurso.

Cuando en un gráfico se tienen rectas de restricción que sólo tocan un vértice del conjunto factible o bien ningún punto del mismo, se identifican como restricciones redundantes (sobrantes). En problemas con más de dos variables de decisión, se tienen métodos analíticos para detectar la redundancia.

En tal caso, la región factible se conserva igual, independientemente de que se incluya o no una restricción redundante del problema, por lo tanto se pueden eliminar sin que tengan ningún efecto sobre la solución óptima. Sin embargo, en la mayor parte de los problemas de programación lineal, las restricciones redundantes no se descartan porque no son reconocibles de inmediato como tales. El problema QUIMCAR no tiene restricciones redundantes pues todas las restricciones forman la frontera de la región factible.

Observaciones y comentarios

1. En la forma estándar de un programa lineal, los coeficientes para las variables de holgura son cero en la función objetivo, por lo tanto, las variables de holgura que representan recursos sin utilizar, no afectan el valor de la función y se pueden omitir. Pero en algunas aplicaciones, algunos o todos los recursos no utilizados pueden venderse para recuperar valores y contribuir a la utilidad. En estos casos las variables de holgura correspondientes se convierten en variables de decisión que representan el total de recursos a vender. Para cada una de estas variables, un coeficiente distinto de cero en la función objetivo reflejará la utilidad asociada con la venta de una unidad del recurso correspondiente.
2. Las restricciones redundantes no afectan la región factible; como consecuencia, pueden eliminarse de un modelo de programación lineal sin afectar la solución óptima. Sin embargo, si posteriormente se debe resolver el modelo de programación lineal con algunos cambios en los datos, una restricción previamente redundante se podría convertir en un recurso limitante, por lo que se sugiere conservar todas las restricciones del modelo de programación lineal, aun cuando se espere que una o más de ellas sean redundantes.

Puntos extremos y solución óptima

Suponga que la contribución a la utilidad de una tonelada de pasta pulidora se incrementa de 300 a 600 dólares, en tanto que la contribución a la utilidad de una tonelada de cera automotriz y todas las demás restricciones se mantienen sin modificación. La función objetivo se convierte en:

¿Cómo afecta este cambio de la función objetivo a la solución óptima del problema de QUIMCAR?. La Figura 1-32 muestra la solución gráfica del problema, utilizando la función objetivo modificada. Observe que las restricciones no tienen cambio, entonces la región factible es la misma; pero se han alterado las líneas rectas de utilidad para reflejar la nueva función objetivo.

Como se observa en la Figura 1-32, al mover la línea recta de utilidad de manera paralela, alejándola del origen, se encuentra la solución óptima. Los valores de las variables de decisión en este punto son X₁=18.75 y X₂ = 25. El aumento en la utilidad de la pasta pulidora ha creado un cambio en la solución óptima. De hecho, como quizás ya lo previó, se reduce la producción de la cera y aumenta la de pasta pulidora, porque ahora tiene una utilidad mayor.

Respecto de las soluciones gráficas de la Figura 1-26 y Figura 1-32 se debe hacer una observación importante: la solución óptima ocurre en alguno de los vértices o intersecciones de la región factible. En terminología de programación lineal, estos vértices se conocen como puntos extremos de la región factible, por lo que para este problema se tienen cinco vértices, es decir, cinco puntos extremos (Figura 1-32). Ahora se puede dar la observación siguiente sobre la localización de las soluciones óptimas.

Figura 1-32. Cambia óptimo: objetivo máximo Z = 400X₁ + 600 X₂, ejemplo QUIMCAR

Si existe la solución óptima de un problema de programación lineal, se puede encontrar en un punto extremo de la región factible del problema.

Esta propiedad significa que, si busca la solución óptima de un problema de programación lineal, debe limitarse a evaluar y comparar los puntos de solución correspondientes a los vértices de la región factible.