El método gráfico es una técnica de solución de problemas de programación lineal que se utiliza principalmente para casos con dos variables. Aunque no es muy práctico para una gran cantidad de variables, es muy útil para interpretar y analizar los resultados y la sensibilidad del problema. Sin embargo, en casos donde se requiera un mayor número de variables, es posible emplear otras técnicas como la proyección en un plano.
El método gráfico se basa en la representación gráfica de las restricciones del modelo de programación lineal, lo que permite determinar el polígono solución o región factible. Según el teorema fundamental de la programación lineal, si existe una solución que cumple con las restricciones del modelo, se encontrará en uno de los vértices de la región factible.
El método gráfico es una técnica que ha sido objeto de debate entre distintos autores a lo largo de la historia. Algunos de ellos han señalado que esta metodología presenta ciertos supuestos o limitaciones.
Uno de los supuestos más conocidos es que no permite realizar un análisis de sensibilidad en el caso de cambios simultáneos en el lado derecho de las restricciones o en los coeficientes de la función objetivo. Otro supuesto es que no se pueden considerar variables binarias en el modelo.
Sin embargo, con el avance de la tecnología, es posible utilizar herramientas como GeoGebra para superar estas limitaciones y realizar análisis de sensibilidad con cambios simultáneos y considerar variables binarias en el modelo. Por lo tanto, estos supuestos ya no son válidos en la actualidad.
Consideraciones previas
Es necesario recordar que el método gráfico es un método de solución, y por tanto, una etapa previa corresponde al modelamiento matemático.
El problema
Vamos a utilizar un problema técnicamente formulado con el objetivo de abordar cada una de las fases del método gráfico.
La fábrica de Hilados y Tejidos «Salazar» requiere fabricar dos tejidos de calidad diferente Estándar y Premium; se dispone de 500 Kg de hilo a, 300 Kg de hilo b y 108 Kg de hilo c. Para obtener un metro de Estándar diariamente se necesitan 125 gr de a, 150 gr de b y 72 gr de c; para producir un metro de Premium por día se necesitan 200 gr de a, 100 gr de b y 27 gr de c. El Estándar se vende a $4000 el metro y el Premium se vende a $5000 el metro. Si se debe obtener el máximo beneficio, ¿Cuántos metros de Estándar y Premium se deben fabricar?
Modelamiento mediante programación lineal
Como lo se hamencionado anteriormente, la base para utilizar el método gráfico corresponde al modelo matemático de programación lineal:
Variables
x: Cantidad de metros diarios de tejido tipo Estándar a fabricar
y: Cantidad de metros diarios de tejido tipo Premium a fabricar
Restricciones
0,12x + 0,2y <= 500 Kg de hilo “a”
0,15x + 0,1y <= 300 Kg de hilo “b”
0,072x + 0,027y <= 108 Kg de hilo “c”
x >= 0 Restricción de no negatividad
y >= 0 Restricción de no negatividad
Función objetivo
Zmax = 4000x + 5000y (Maximizar los ingresos totales dados en $)
Solución mediante método gráfico
Paso 1: Graficar las restricciones
El proceso para encontrar la solución factible comienza con la representación gráfica de las restricciones; cada una de ellas debe representarse de tal manera que se vayan limitando las posibles soluciones del modelo.
En este punto, debemos considerar dos posibilidades:
- Que realicemos todo el procedimiento de forma manual
- Que utilicemos un software gráfico que simplifique las operaciones matemáticas
En este caso, mostraremos toda la metodología para realizar el procedimiento manual, al mismo tiempo que utilizaremos un software gráfico para representar cada fase del método.
Cada restricción corresponde a una función lineal, lo que significa que gráficamente se representa mediante una línea en el plano cartesiano. Para trazar una línea en el plano cartesiano es necesario conocer al menos dos puntos de la función.
Para comenzar a trazar las restricciones es esencial igualar las restricciones a cero, de esta manera podremos usar el despeje de las ecuaciones para iniciar la tabulación que nos dará las coordenadas para dibujar cada una de las gráficas.
Igualamos las restricciones a cero:
0.12x + 0.2y = 500 (Restricción 1)
0.15x + 0.1y = 300 (Restricción 2)
0.072x + 0.027y = 108 (Restricción 3)
x = 0 (Restricción 4)
y = 0 (Restricción 5)
Iniciamos con la Restricción 1: Hallamos las primeras dos coordenadas. Para hallar las coordenadas, regularmente llevamos una de las variables a cero, para de esta manera despejar más fácilmente la segunda.
Cuando x = 0
0,12(0) + 0,2y = 500
0,2y = 500
500/0,2 = y
2500 = y
y cuando y = 0
0,12x + 0,2(0) = 500
0,12x = 500
x = 500/0,12
x = 4167
| Restricción 1 | x | y |
| Primera coordenada | 0 | 2500 |
| Segunda coordenada | 4167 | 0 |
Seguimos con la Restricción 2:
Por ejemplo, cuando x = 0
0.15(0) + 0.1y = 300
0.1y = 300
y = 300/0.1
y = 3000
Cuando y = 0
0.15x + 0.1(0) = 300
0.15x = 300
x = 300/0.15
x = 2000
| Restricción 2 | x | y |
| Primera coordenada | 0 | 3000 |
| Segunda coordenada | 2000 | 0 |
Seguimos con la Restricción 3:
Por ejemplo, cuando x = 0
0.072x + 0.027y = 108
0.072(0) + 0.027y = 108
0.027y = 108
y = 108/0.027
y = 4000
Cuando y = 0
0.072x + 0.027(0) = 108
0.072x = 108
x = 108/0.072
x = 1500
| Restricción 3 | x | y |
| Primera coordenada | 0 | 4000 |
| Segunda coordenada | 1500 | 0 |
Restricciones de no negatividad:
Paso 2: Encontrar el área solución (Polígono solución)
Después de que todas las restricciones sean representadas gráficamente, el siguiente paso consiste en encontrar el área factible o polígono solución; que no es otra cosa más que la región en la que todos los puntos satisfacen la totalidad de las restricciones, es decir, son factibles.
Para delimitar el área factible, es necesario determinar el sentido de las restricciones. Aquí me detengo un poco; ya que prefiero explicarlo en detalle. Cada línea que representa una restricción divide el plano cartesiano en dos semiplanos: En un lado y en el otro lado de la restricción. Bien, solo los puntos del uno de los lados pueden considerarse como factibles.
Si queremos encontrar el área factible, debemos empezar por encontrar el lado factible de cada una de las restricciones; esto es lo que yo llamo: evaluar el sentido de las restricciones.
Veamos un ejemplo para la primera restricción.
Evaluar el sentido de la Restricción 1
Esto es muy sencillo, solo debemos evaluar un punto cualquiera del plano cartesiano, debe corresponder a uno de los lados de la restrición. Si se satisface o no la restricción, sabremos el sentido de la misma.
0,12x + 0,2y <= 500
Es normal que queramos simplificar el proceso aritmético, y es común utilizar el punto de coordenadas (0, 0):
0,12(0) + 0,2(0) <= 500
0 <= 500
¡Verdad!
Dado que 0 es menor o igual a 500, podemos afirmar que de ese lado de la restricción se encuentran los valores que la satisfacen.
La región en verde representa el área en la que se encuentran todos los puntos que satisfacen la restrición 1.
Para encontrar la región factible, el procedimiento debe repetirse para cada una de las restricciones del problema. Dado que todas las restricciones deben cumplirse, la región factible será el resultado de la intersección de todas las regiones factibles de cada una de las restricciones del modelo.
El área sombreada de la gráfica anterior corresponde a la regín factible.
Paso 3: La búsqueda de la solución óptima
Una vez que se ha encontrado la región factible que cumple con todas las restricciones del modelo, el siguiente paso es encontrar la solución óptima. Es importante diferenciar entre factibilidad y optimalidad.
La solución óptima dependerá del criterio de optimización de la función objetivo y, de acuerdo al teorema fundamental de la programación lineal, se encuentra en uno de los vértices del área factible. Tecnicamente, en los vértices se encuentra la solución óptima para cualquier criterio de optimización: El valor mínimo (minimización) y el valor máximo (maximización).
Hay principalmente dos procedimientos para encontrar la solución óptima:
- Graficamente
- Evaluando todos los vértices (Fuerza bruta)
Graficamente
Este método requiere de la representación gráfica de la función objetivo. Por lo menos dos veces.
Es necesario graficar la función objetivo y encontrar el sentido en el cual se acerca al criterio de optimización. ¿Cómo lo hacemos? En cada caso, necesitamos dos puntos para graficar la primera línea que representa a la función objetivo; estos dos puntos deben dar como resultado el mismo Z. Veamos:
Zmax = 4000x + 5000y
| Función objetivo (Z1) | 4000(x) | 5000(y) | z |
| Primera coordenada | 4000(500) | 5000(0) | 2000000 |
| Segunda coordenada | 4000(0) | 5000(400) | 2000000 |
Ahora, podemos intentar con otra representación de la función objetivo que se acerque aún más al criterio de optimización: Maximizar; es decir, un Z2 mayor a Z1. Veamos:
| Función objetivo (Z2) | 4000(x) | 5000(y) | z |
| Primera coordenada | 4000(1000) | 5000(0) | 4000000 |
| Segunda coordenada | 4000(0) | 5000(800) | 4000000 |
Now, we can try with another representation of the objective function that gets even closer to the optimization criterion: Maximize; that is, a Z2 greater than Z1. Let’s see:
Se puede ver cómo la función objetivo se aproxima al criterio de optimización (aumenta) mientras se desplaza hacia arriba. El siguiente paso es encontrar el último vértice del área factible (en dirección ascendente en este caso), donde una línea paralela a la función objetivo no corta el polígono factible. En este punto se encontrará la solución óptima.
Utilice la barra de desplazamiento de GeoGebra para desplazar la función objetivo. Verá que el último vértice en el que la función objetivo no corta el área factible es el que se da por la intersección de la Restricción 2 y la Restricción 3 (Vértice C). Este punto corresponde a la solución óptima.
Para encontrar el valor de esta coordenada es necesario resolver una ecuación lineal 2×2, y se pueden considerar varios métodos de solución, como:
- Método de sustitución
- Método de igualación
- Método de reducción o Eliminación
- Método de eliminación Gauss
- Método de eliminación Gauss-Jordán
- Método de determinantes
Hay muchos métodos disponibles, pero uno de los más utilizados es el método de reducción o eliminación, que es muy fácil de aplicar.
El método de reducción o eliminación consiste en igualar los coeficientes de una de las variables multiplicando una o ambas ecuaciones, teniendo en cuenta que estos coeficientes queden iguales pero con signos contrarios.
Ecuación 1 0,12x + 0,2y = 500
Ecuación 2 0,15x + 0,1y = 300 multiplicamos por (-2)
Ecuación 3 (2*(-2)) -0,30x – 0,2y = -600
Sumamos 1 y 3 -0,18x = -100
Despejamos «x» x = -100 / (-0,18)
x = 555,55
Luego reemplazamos x = 555,55 en cualquiera de las dos ecuaciones originales con el objetivo de despejar «y».
Ecuación 1 0,12x + 0,2y = 500
Reemplazamos «x» 0,12(555,55) + 0,2y = 500
Despejamos «y» 66,666 + 0,2y = 500
0,2y = 500 – 66,666
0,2y = 433,334
y = 433,334 / 0,2
y = 2166,67
De esta forma hemos obtenido los valores para «x» y «y».
x: Cantidad de metros diarios de tejido tipo Estándar a fabricar
y: Cantidad de metros diarios de tejido tipo Premium a fabricar
Cantidad de metros diarios de tejido tipo Estándar a fabricar = 555,55
Cantidad de metros diarios de tejido tipo Premium a fabricar = 2166,67
La contribución obtenida (reemplazando las variables en la función objetivo) es de:
Zmax = 4000x + 5000y
Zmax = 4000(555,55) + 5000(2166,67)
Zmax = $13.055.550
Ahora podemos comparar los resultados con los obtenidos mediante resolución en Excel, pero recuerden que el método de búsqueda de la solución óptima en el método gráfico que utilizamos es geométrico y que existe una forma mucho más compleja pero igualmente efectiva, que es el método de iteración por vértice. Este consiste en hallar todas las coordenadas de los vértices y luego evaluar la función objetivo en cada coordenada. Cada coordenada nos proporciona un valor en «x» y otro en «y», luego reemplazamos estos valores en la función objetivo «4000x + 5000y = ?» y evaluamos los resultados seleccionando el mayor valor.
