Programación Lineal (Método Gráfico)

El Método Gráfico (resolución gráfica) constituye una excelente alternativa de representación y resolución de modelos de Programación Lineal que tienen 2 variables de decisión. Para estos efectos existen herramientas computacionales que facilitan la aplicación del método gráfico como los softwares TORA, IORTutorial y Geogebra, los cuales se pueden consultar en detalle en Cómo Resolver Gráficamente un Modelo de Programación Lineal con TORACómo Resolver Gráficamente un Modelo de Programación Lineal con IORTutorialCómo Resolver Gráficamente un modelo de Programación Lineal con Geogebra, respectivamente. En este contexto a continuación presentamos un compendio de ejercicios de Programación Lineal resueltos a través del método gráfico.

Ejercicios Resueltos del Método Gráfico en Programación Lineal

Ejercicio N°1: Una empresa vitivinícola ha adquirido recientemente un terreno de 110 hectáreas. Debido a la calidad del sol y el excelente clima de la región, se puede vender toda la producción de uvas Sauvignon Blanc y Chardonay. Se desea conocer cuánto plantar de cada variedad en las 110 hectáreas, dado los costos, beneficios netos y requerimientos de mano de obra según los datos que se muestran a continuación:

variedad-vinos-programacion

Suponga que se posee un presupuesto de US$10.000 y una disponibilidad de 1.200 días hombre durante el horizonte de planificación. Formule y resuelva gráficamente un modelo de Programación Lineal para este problema. Detalle claramente el dominio de soluciones factibles y el procedimiento utilizado para encontrar la solución óptima y valor óptimo.

Variables de Decisión:

  • X_{1} : Hectáreas destinadas al cultivo de de Sauvignon Blanc
  • X_{2} : Hectáreas destinadas al cultivo de Chardonay

Función Objetivo:

Maximizar 50X_{1}+120X_{2}

Restricciones:

  • X_{1}+X_{2}\leq 110
  • 100X_{1}+200X_{2}\leq 10.000
  • 10X_{1}+30X_{2}\leq 1.200
  • X_{1},X_{2}\geq 0

Donde las restricciones están asociadas a la disponibilidad máxima de hectáreas para la plantación, presupuesto disponible, horas hombre en el período de planificación y no negatividad, respectivamente.

El siguiente gráfico muestra la representación del problema de la empresa vitivinícola. El área achurada corresponde al dominio de soluciones factibles, donde la solución básica factible óptima se alcanza en el vértice C, donde se encuentran activas las restricciones de presupuestos y días hombre. De esta forma resolviendo dicho sistema de ecuaciones se encuentra la coordenada de la solución óptima donde X_{1}=60X_{2}=20 (hectáreas). El valor óptimo es V(P)=50(60)+120(20)=5.400 (dólares).

metodo-grafico-vitivinicola

Ejercicio N°2: Un taller tiene tres (3) tipos de máquinas A, B y C; puede fabricar dos (2) productos 1 y 2, todos los productos tienen que ir a cada máquina y cada uno va en el mismo orden: Primero a la máquina A, luego a la B y luego a la C. La siguiente tabla muestra:

  • Las horas requeridas en cada máquina, por unidad de producto
  • Las horas totales disponibles para cada máquina, por semana
  • La ganancia por unidad vendida de cada producto

tabla-maquinas-y-requerimie

Formule y resuelva a través del método gráfico un modelo de Programación Lineal para la situación anterior que permite obtener la máxima ganancia para el taller.

Variables de Decisión:

  • X_{1} : Unidades a producir del Producto 1 semanalmente
  • X_{2} : Unidades a producir del Producto 2 semanalmente

Función Objetivo:

Maximizar X_{1}+1,5X_{2}

Restricciones:

  • 2X_{1}+2X_{2}\leq 16
  • X_{1}+2X_{2}\leq 12
  • 4X_{1}+2X_{2}\leq 28
  • X_{1},X_{2}\geq 0

Las restricciones representan la disponibilidad de horas semanales para las máquinas A, B y C, respectivamente, además de incorporar las condiciones de no negatividad.

Para la resolución gráfica de este modelo utilizaremos el software GLP cual abordamos en el artículo Problema de Planificación Forestal resuelto con Graphic Linear Optimizer (GLP). El área de color verde corresponde al conjunto de soluciones factibles y la curva de nivel de la función objetivo que pasa por el vértice óptimo se muestra con una línea punteada de color rojo.

glp-metodo-grafico

La solución óptima es X_{1}=4X_{2}=4 con valor óptimo V(P)=1(4)+1,5(4)=10 que representa la ganancia para el taller.

Ejercicio N°3: Una compañía elabora dos productos diferentes. Uno de ellos requiere por unidad 1/4 de hora en labores de armado, 1/8 de hora en labores de control de calidad y US$1,2 en materias primas. El otro producto requiere por unidad 1/3 de hora en labores de armado, 1/3 de hora en labores de control de calidad y US$0,9 en materias primas. Dada las actuales disponibilidades de personal en la compañía, existe a lo más un total de 90 horas para armado y 80 horas para control de calidad, cada día. El primer producto descrito tiene un valor de mercado (precio de venta) de US$9,0 por unidad y para el segundo este valor corresponde a US$8,0 por unidad. Adicionalmente se ha estimado que el límite máximo de ventas diarias para el primer producto descrito es de 200 unidades, no existiendo un límite máximo de ventas diarias para el segundo producto.

Formule y resuelva gráficamente un modelo de Programación Lineal que permita maximizar las utilidades de la compañía.

Variables de Decisión:

  • X_{1} : Unidades a producir diariamente del Producto 1
  • X_{2} : Unidades a producir diariamente del Producto 2

Función Objetivo:

Maximizar (9-1,2)X_{1}+(8-0,9)X_{2}=7,8X_{1}+7,1X_{2}

Restricciones:

  • \frac{X_{1}}{4}+\frac{X_{2}}{3}\leq 90
  • \frac{X_{1}}{8}+\frac{X_{2}}{3}\leq 80
  • X_{1}\leq 200
  • X_{1},X_{2}\geq 0

La primera restricción representa las limitantes de horas de armado diariamente. La segunda restricción la disponibilidad de horas para labores de control de calidad (también diariamente). La tercera restricción establece una cota superior para la producción y ventas diarias del Producto 1. Adicionalmente se incluyen las condiciones de no negatividad para las variables de decisión.

El dominio de soluciones factibles tiene 5 vértices que corresponden a los candidatos a óptimos del problema. En particular el vértice óptimo es D de modo que la solución óptima es X_{1}=200X_{2}=120 con valor óptimo V(P)=7,8(200)+7,1(120)=2.412 que corresponde a la utilidad máxima para la empresa.

metodo-grafico-produccion

Importante: A la fecha de esta publicación disponemos de más de 70 artículos relativos a la Programación Lineal los cuales recomendamos revisar, donde se aborda la resolución gráfica de este tipo de modelos como también la resolución a través de algoritmos como el Método Simplex y la implementación computacional con herramientas como Solver, What’sBest! y OpenSolver, entre otras.

En el siguiente tutorial de nuestro canal de Youtube se explica un ejemplo adicional con todos los elementos del método gráfico en Programación Lineal:

Qué es la Programación Entera

¿Qué es la Programación Entera?: Un modelo de Programación Entera es aquel cuya solución óptima tiene sentido solamente si una parte o todas las variables de decisión toman valores restringidos a números enteros, permitiendo incorporar en el modelamiento matemático algunos aspectos que quedan fuera del alcance de los modelos de Programación Lineal.

En este sentido los algoritmos de resolución de los modelos de Programación Entera difieren a los utilizados en los modelos de Programación Lineal, destacándose entre ellos el Algoritmo de Ramificación y Acotamiento (o Branch & Bound), Branch & Cut, Planos Cortantes, Relajación Lagrangeana, entre otros.

Los modelos de Programación Entera se pueden clasificar en 2 grandes áreas: Programación Entera Mixta (PEM) y Programación Entera Pura (PEP).

categorías programación entera

Programación Entera Mixta (PEM)

A esta categoría pertenecen aquellos problemas de optimización que consideran variables de decisión enteras o binarias pero no de forma exclusiva. De esta forma un problema de PEM puede considerarse como un híbrido entre distintas categorías de modelamiento, siendo un caso típico aquel que considera la mezcla de variables enteras y variables continuas (estas últimas características de los modelos de Programación Lineal). A modo de ejemplo los siguientes artículos que hemos abordado en el Blog dan cuenta de modelos de Programación Entera Mixta:

  1. Incorporación de Costos Fijos
  2. Problemas de Localización y Transporte
  3. Problema de Generación Eléctrica

Programación Entera Pura (PEP)

En esta categoría encontramos aquellos modelos de Programación Entera que consideran exclusivamente variables de decisión que adoptan valores enteros o binarios. Un ejemplo de ello son las siguientes aplicaciones:

  1. Problema de Asignación
  2. Problema de Corte de Rollos
  3. Selección de Invitados a una Boda
  4. Programación de la Explotación Forestal
  5. Problema de la Mochila

Notar que en los problemas anteriores (PEP) el conjunto de las soluciones factibles (o dominio de soluciones factibles) es finito. Esto ocurrirá generalmente con los problemas de Programación Entera (puros).

Adicionalmente resulta interesante hacer un contrastes entre las propiedades de un modelo de Programación Lineal (PL) y uno de Programación Entera (PE). A continuación se presentan 2 modelos de optimización que se diferencian únicamente en que al segundo de ellos (PE) se le exige que las variables de decisión adopten valores enteros.

comparación pl y pe

Para los problemas propuestos realizamos una representación gráfica haciendo uso del software Geogebra. El dominio de soluciones factibles del Problema Lineal (PL) corresponde al área achurada de color verde. Por otro lado el dominio de soluciones factibles del Problema Entero (PE) es enumerable y corresponde a las coordenadas denotadas por A, E, F, B, G, H, I, J, K, C, L, M, D (que es un subconjunto del dominio de factibilidad del PL). En este caso en particular la solución óptima de ambos problemas coincide (en el vértice C), no obstante, perfectamente podrían ser distintas (bastaría con modificar los parámetros del problema).

dominio lineal y entero

En este contexto y dada la naturaleza de los problemas propuestos, el valor óptimo del Problema Lineal (PL) será una cota superior del valor óptimo del Problema Entero (PE). También se concluye que el dominio de soluciones factibles de un modelo de Programación Lineal (cuando existe) representa un conjunto convexo (los problemas de Programación Lineal son convexos) y en el caso del problema de Programación Entera Pura su conjunto de soluciones factibles es discreto.

Adicionalmente según tratamos en el artículo Por qué no aparece el Informe de Confidencialidad (o Informe de Sensibilidad) en Solver de Excel se debe tener en cuenta que en la utilización de software para la resolución computacional del modelos de Programación Entera no tendremos acceso a los reportes de sensibilidad como en el caso de la implementación de modelos de Programación Lineal. De esta forma ante la necesidad de analizar el impacto en los resultados ante la modificación de los parámetros del problema será necesario reoptimizar ante la información que brinde el o los nuevos escenarios.

resultados solver sin informe de sensibilidad

Es importante destacar que las aplicaciones de la Programación Entera no reemplaza la versatilidad que ofrece el disponer de modelos de Programación Lineal. Más aún, se pueden considerar estas categorías de modelamiento matemático como complementarias en el ámbito de la Investigación de Operaciones.

En este sentido en términos abstractos los modelos de Programación Entera imponen un desafío mayor al momento de la resolución en comparación a las propiedades simplificadoras que están asociadas a los problemas de Programación Lineal. De esta forma se espera que el tomador de decisiones sea capaz de evaluar la relación rigurosidad del modelado con el costo (complejidad) de la resolución del mismo.




GeoGebra Calculadora Gráfica para Android

En este oportunidad queremos compartir con nuestros usuarios una noticia reciente que de seguro será de interés para quienes en alguna oportunidad han utilizado la versión web o instalado en sus computadores el popular software Geogebra. El software Geogebra permite entre otras cosas hacer representaciones gráficas de funciones (lineales y no lineales), lo cual hemos abordado ampliamente en la resolución de modelos de Programación Lineal mediante el Método Gráfico, construir Histogramas para análisis estadístico, realizar pruebas de hipótesis, entre otros análisis.

En este contexto hemos recibido un correo de notificación de parte del Equipo de GeoGebra informando que se encuentra disponible para su descarga gratuita GeoGebra Calculadora Gráfica el cual es compatible con smatphones y tablets con sistema operativo Android y que prontamente estará disponible para los usuarios de iPhone.

email geogebra

El programa se puede descargar desde Google Play en https://play.google.com/store/apps/details?id=org.geogebra.android tal como se muestra a continuación:

GeoGebra Calculadora Gráfica para Android

A la fecha de este artículo GeoGebra Calculadora Gráfica cuenta con el orden de 10.000 descargas y una valoración (puntuación) de 4,8. Adicionalmente no requiere mayores privilegios para su instalación. Todo esto sin duda constituye un excelente respaldo respecto a la calidad de este programa el cual hemos tenido el privilegio de utilizar durante varios años con excelentes resultados.

Una de las ventajas de la versión para Android de GeoGebra es la posibilidad de exportar los archivos a Dropbox, OneDrive, Google Drive, enviar por correo electrónico, entre otros. Esto permite respaldar fácilmente los archivos que utilicemos en nuestro smartphone o tablet para ser utilizado posteriormente (la siguiente imagen muestra la utilización del programa para la representación gráfica de un modelo de Programación Lineal).

geogebra-android

Te recomendamos decididamente descargar GeoGebra Calculadora Gráfica y desde ya te agradecemos compartir tu experiencia en su utilización, dejándonos un comentario al final de este artículo.




Análisis de Sensibilidad (Método Gráfico)

El Análisis de Sensibilidad en Programación Lineal permite analizar el impacto en los resultados del modelo (solución óptima y valor óptimo) en aquellos casos donde uno o varios parámetros sufren modificaciones en relación a sus valores originales, sin la necesidad de resolver nuevamente el problema (sin reoptimizar). En dicho contexto en el siguiente artículo presentamos un ejemplo de dicho análisis para un problema de optimización lineal que considera 2 variables de decisión.

Ejemplo Análisis de Sensibilidad (Método Gráfico)

Un productor tabaquero posee 85 hectáreas (ha) de terreno para plantar dos variedades de tabacos Virginia y Procesado. La variedad Virginia tiene un ingreso de 9.600 USD/ha y necesita 3 horas/ha de uso de maquinaria y 80 horas/ha de mano de obra. Además, el Estado limita su explotación a 30 ha como máximo. La variedad Procesado tiene un ingreso de 7.500 USD/ha y utiliza 2 horas/ha de uso de maquinaria y 60 horas/ha de mano de obra. La cooperativa local le ha asignado un máximo de 190 horas de uso de maquinaria y solo se dispone de 5.420 horas de mano de obra a 12 USD/hora.

Formule y resuelva gráficamente un modelo de Programación Lineal que permita determinar cuánto se debe plantar de cada variedad de tabaco de manera de maximizar la utilidad total.

En primer lugar definimos el modelo de optimización para este problema. Esto consiste en identificar las variables de decisión, función objetivo y restricciones. Detalle de este procedimiento aplicado a problemas de 2 variables puede ser consultado en el artículo Programación Lineal (Método Gráfico).

Variables de Decisión:

  • X1 = Número de Ha a plantar de la variedad Virginia
  • X2 = Número de Ha a plantar de la variedad Procesado

Función Objetivo:

Maximizar (9.600 – 960)X1 + (7.500 – 720)X2 = 8.640X1 + 6.780X2

Restricciones:

  1. X1 ≤ 30
  2. X1 + X2 ≤ 85
  3. 3X1 + 2X2 ≤ 190
  4. 80X1 + 60X2 ≤ 5.420
  5. X1, X2 ≥ 0

Una representación gráfica del problema para el productor de tabaco se puede realizar a través del software Geogebra:

solución método gráfico

Sabemos según el Teorema Fundamental de la Programación Lineal que en caso de existir solución óptima ésta se encontrará en un vértice o en un tramo en la frontera del dominio de soluciones factibles (en el ejemplo área achurada en color verde). Adicionalmente podemos apreciar que no es tan evidente que el vértice C reporte una mayor utilidad en la función objetivo que el vértice D, por lo cual, inspeccionaremos ambos puntos.

En el caso del vértice C éste se encuentra en la intersección de las restricciones 2 y 4. La coordenada respectiva se obtiene al resolver el siguiente sistema de ecuaciones:

X1 + X2 = 85
80X1 + 60X2 = 5.420

De donde X1=16X2=69, lo cual reporta un valor en la función objetivo de V(P)=8.640*(16)+6.780(69)=606.060.

Análogamente en el caso del vértice D las restricciones activas son 3 y 4:

3X1 + 2X2 = 190
80X1 + 60X2 = 5.420

Luego de resolver el sistema lineal anterior se obtiene X1=28 y X2=53, lo cual reporta un valor en la función objetivo de V(P)=8.640*(28)+6.780(53)=601.260.

En consecuencia la solución óptima del problema es X1=16X2=69, con valor óptimo V(P)=8.640*(16)+6.780(69)=606.060.

Una vez resuelto el escenario original a continuación se presentan algunos análisis adicionales que representan por separado modificaciones en los coeficientes de la función objetivo y restricciones del problema.

Intervalo Variación Coeficiente Función Objetivo

Determine cuánto podría variar la utilidad por hectárea del tabaco Virginia, manteniendo constante la utilidad por hectárea del tabaco procesado, de forma que la actual solución óptima no cambie. Para este caso determine el intervalo de variación de la utilidad total.

Sea en términos generales la función objetivo Z=C1X1+C2X2, donde inicialmente en el ejemplo C1=8.640 y C2=6.780. La pendiente de las curvas de nivel de la función objetivo es -C1/C2. De este modo se conserva la actual solución óptima (vértice C) en la medida que:

-\frac{4}{3}\leq-\frac{C_{1}}{C_{2}}\leq -1
\frac{4}{3}\geq \frac{C_{1}}{C_{2}}\geq 1
\frac{4}{3}\geq \frac{C_{1}}{6.780}\geq 1
9.040\geq C_{1}\geq 6.780

En este caso la utilidad por hectárea del tabaco Virginia puede variar entre 6.780 USD y 9.040 USD, de tal forma que el actual nivel de producción (solución óptima) sería el mismo. Lo anterior permite concluir que el intervalo de variación para la utilidad total será 576.300\leq Z\leq 612.460.

Precio Sombra (Método Gráfico)

Si se pudiese contratar más mano de obra disponible en el mercado, ¿Cuántas horas de mano de obra en total estaría dispuesto a utilizar? ¿Cuál sería el aporte adicional de esas horas extras que utilizaría en términos monetarios? Responda lo anterior utilizando el concepto de Precio Sombra.

Para calcular gráficamente el precio sombra necesitamos identificar la máxima y mínima variación para el lado derecho de la restricción de mano de obra que permita garantizar que se conserva la actual base óptima (restricciones activas originales). En este sentido en el caso de aumentar el lado derecho de dicha restricción la solución óptima podrá ser encontrada manteniendo las restricciones activas (e incorporando una adicional) hasta la coordenada (20,65) que es donde se interceptan la segunda y tercera restricción. En el caso de disminuir la disponibilidad de horas en mano de obra se mantiene la base óptima hasta el vértice B cuya coordenada es (0,85). De esta forma se obtiene el precio sombra de la siguiente forma:

precio sombra método gráfico

En consecuencia el lado derecho de la restricción 4 (disponibilidad de mano de obra) puede variar entre [5.100, 5.500] y se conservan las actuales restricciones activas. Adicionalmente dado que en el óptimo actual se utilizan 5.420 horas de mano de obra se deben contratar 80 horas adicionales (de modo de alcanzar las 5.500 horas). Luego, la variación de 80 horas adicionales implicaría un aumento en la utilidad total de 80*USD93=7.440USD.




Ejemplo del Cálculo del Punto de Equilibrio

En todo negocio un aspecto imprescindible consiste en evaluar la ganancia potencial de un producto o servicio, ya sea nuevo o existente. Se considera que los costos asociados a la producción de un producto o prestación de un servicio se puede dividir básicamente en 2 categorías: costos fijos (independientes del volumen de producción dentro de un rango de producción relevante) y costos variables (que varían directamente con el volumen de producción, asumiendo una relación lineal o proporcional). En este contexto el punto de equilibrio determina cuál debe ser el número de unidades vendidas que permite equiparar los ingresos totales con los costos totales, es decir, aquel volumen de ventas que evita pérdidas y ganancias.

Dado lo anterior queda de manifiesto la importancia de la evaluación del punto de equilibrio. El análisis se enfoca a responder preguntas del tipo:

  1. ¿Las ventas pronosticadas resultan ser suficientes para evitar pérdidas?

  2. ¿Cuánto debe bajar el costo variable unitario para alcanzar el punto de equilibrio, dadas las condiciones actuales de precios y proyecciones de ventas?

  3. ¿Cuál es el impacto del precio unitario en la obtención del punto de equilibrio?

  4. ¿Cuánto deben bajar los costos fijos para estar en una situación sin ganar o perder?

Sea CT=F+cQ el costo total de producir un bien o prestar un servicio, donde F es el costo fijo y cQ los costos variables (c es el costo unitario y Q la cantidad vendida). Adicionalmente sea IT=pQ el ingreso total, donde p es el precio unitario. El punto de equilibrio en términos de las unidades vendidas esta dado por:

formula-punto-de-equilibrio

Ejemplo Cálculo del Punto de Equilibrio

Una clínica esta evaluando un nuevo examen que reportará ingresos de $200 por paciente. El costo fijo anual será de $100.000 y los costos variables son de $100 por paciente. ¿Cuál es el punto de equilibrio para este servicio?.

Al evaluar en la fórmula anterior obtenemos lo siguiente:

ejemplo-punto-de-equilibrio

Es decir, si se realizan 1.000 exámenes (asumiendo un examen por paciente) los ingresos totales igualan a los costos totales, evitando tanto pérdidas como ganancias. De forma complementaria con la ayuda de Excel se puede evaluar de forma sencilla tanto los ingresos como costos totales para distintos niveles de actividad (en este caso número de exámenes o pacientes). La línea azul representa el ingreso total en miles de $ (eje vertical) para distintos valores de números de pacientes (eje horizontal). La línea roja representa el costo total donde resulta de particular interés observar que su valor es de $100 (mil) en el caso de cero pacientes (costo fijo).

punto-de-equilibrio-excel

Una representación alternativa del ejemplo anterior hemos desarrollado con Geogebra, la cual se muestra a continuación. El área achurada de color rojo representa la pérdida, es decir, cuando el número de pacientes es menor al punto de equilibrio, por el contrario el área achurada de color verde representa la ganancia, en la cual se incurre cuando el nivel de pacientes supera el punto de equilibrio.

grafica-punto-de-equilibrio