Investigación de operaciones

Método gráfico

Solución gráfica de programación lineal

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.

método_gráfico

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:

  1. Que realicemos todo el procedimiento de forma manual
  2. 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 1xy
Primera coordenada02500
Segunda coordenada41670

C1


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 2xy
Primera coordenada03000
Segunda coordenada20000

r2


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 3xy
Primera coordenada04000
Segunda coordenada15000

r3


Restricciones de no negatividad:

r4 y r5

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.

Cuando la función de la restricción (línea en el plano) pase por el punto (0, 0) este no servirá para evaluar la restricción. Recuerde que debe elegirse un punto que se encuentre en uno de los lados de la restricción.

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.

rf

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:

  1. Graficamente
  2. 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 coordenada4000(500)5000(0)2000000
Segunda coordenada4000(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 coordenada4000(1000)5000(0)4000000
Segunda coordenada4000(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.


Si deseas conocer más sobre los casos especiales en la programación lineal, ¡este post es para ti: Casos especiales en programación lineal mediante Método Gráfico! Descubre cómo se dan las situaciones de infactibilidad, infinitas soluciones óptimas y restricciones redundantes en esta técnica de modelado matemático. ¡Te sorprenderás de la relevancia de estos casos en la vida real!

Recomendamos que lean: Método gráfico mediante Python

Bryan Salazar López

Ingeniero Industrial y Magíster en Logística Integral especializado en productividad y modelamiento de procesos bajo dimensiones de sostenibilidad, industria 4.0, transformación digital y modelos de optimización. Docente universitario de pregrado y posgrado con experiencia en la enseñanza de estos temas. Fundador de Ingenieriaindustrialonline.com, un sitio en donde se recogen las aportaciones de investigaciones, artículos y referencias relevantes para la industria.

Un comentario

  1. Buenas tardes
    soy estudiante de Ingenieria de procesos y operaciones industriales; gracias por la informacion, realmente se me dificulta un poco aprender, a pesar de que esta bastante claro, me comprometo a darle otro repaso para poder comprender lo mas posible.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.

Botón volver arriba