Cómo plantear un problema de programación lineal + Ejemplos

Las empresas tienen como meta obtener la mayor rentabilidad en sus actividades; para ello debe aprovechar al máximo sus recursos disponibles, tales como talento humano, insumos, equipos, planta, dinero, entre otros. La programación lineal se presenta como una herramienta muy útil, para ayudar a encontrar la mejor solución en las empresas para lograr esta meta. En este post aprenderás cómo plantear un problema de programación lineal.

Cómo plantear un problema de programación lineal

Es importante mencionar que en este post abordaremos solamente los aspectos teóricos y el planteamiento de las ecuaciones de programación lineal. También puedes revisar las siguientes entradas:

La programación lineal hace referencia a varias técnicas de modelamiento matemático; para asignar, en forma óptima, los recursos limitados a distintas demandas que compiten por ellos.

Para entender este concepto, brindaremos un ejemplo con «The Avengers»:

Cómo plantear un problema de programación lineal

Imagina que para vencer a Thanos se requiere cierta cantidad de energía (como mínimo un poder de pelea de 81000), para lo cual dispones de diferentes vengadores con 3 niveles de energía. Thor, Hulk, Ironman, Starlord, Visión, Dr. Strange y Wanda tienen un nivel de energía 1 (poder de pelea de 7000); Capitán América, Black Panter, Spiderman, Soldado del Invierno, Máquina de Hierro, Groot, Drax y Ant Man tienen un nivel de energía 2 (poder de pelea de 5000); y finalmente Hawkeye, Black Widow, Rocket, Falcon, y Gamora tienen un nivel de energía 3 (poder de pelea de 4000).




Si durante la pelea utilizamos a un héroe de nivel 1, la destrucción en la tierra será de 500 km2 ; si utilizamos un héroe de nivel 2,  será de 325 km2 y si utilizamos un héroe de nivel 3, será de 250 km. Cada vengador adicional que participe suma al área de destrucción de la tierra de acuerdo a su nivel.

Determinar la cantidad de vengadores por nivel a utilizar para vencer a Thanos y minimizar la destrucción en la tierra. 

Por lo tanto el problema buscar elegir la asignación óptima de vengadores para derrotar a Thanos (demanda); minimizando la destrucción en la tierra y teniendo en cuenta la cantidad de vengadores disponibles (recursos limitados). La solución la encontrarás al final del post.

Como te puedes dar cuenta, los usos que se le puede dar a la programación lineal, dependen únicamente de que tan creativos podamos ser.

Como identificar un problema de programación lineal:

Para que un determinado problema se plantee mediante programación lineal debe cumplir las siguientes condiciones:

  • Tener restricciones o recursos limitados. Por ejemplo: cantidad limitada de trabajadores, número máximo de clientes que se puede atender o límite de capacidad de un proceso.
  • Buscar un objetivo explícito como maximizar los ingresos o minimizar los costos.
  • Linealidad, es decir, debe tener proporcionalidad. Las ecuaciones que generan las variables de decisión son lineales.
  • Homogeneidad (las características de las variables de decisión y de los recursos son iguales). Por ejemplo: todas las horas que trabaja una persona son igual de productivas o los productos fabricados en una máquina son idénticos.
  • Divisibilidad, es decir que los productos y recursos se pueden presentar en fracciones.
  • No negatividad, quiere decir que las variables de decisión deben ser positivas o cero; es decir no se puede fabricar una cantidad negativa de productos.

Cómo plantear un problema de programación lineal:

Un problema de programación lineal representa un proceso de optimización en el cuál encontraremos lo siguiente:

Variables de decisión:

Son las variables que están bajo el control de la persona que toma las decisiones. Sus valores óptimos se determinarán al resolver el problema.

Por ejemplo:

variable de decisión

Función objetivo:

Expresa matemáticamente el objetivo que se pretende alcanzar en la solución del problema; ya sea minimizar o maximizar. Por ejemplo: maximizar las utilidades de la empresa o minimizar los costos de producción.

Se representa de la siguiente forma:

ecuación variable de decisión

Donde:

X1, X2, X3, …, Xn = Variables de decisión

C1, C2, C3, …, Cn = Constantes

Restricciones:

Son las limitaciones que restringen las opciones permisibles para las variables de decisión

Cada restricción se expresa matemáticamente con cualquiera de estos signos:

  • Menor que o igual a (≤). Cuando existe un límite superior, por ejemplo: las horas extras de trabajo no pueden ser mayor a 2 horas diarias
  • Igual a (=). Indica una relación obligatoria, por ejemplo: el inventario final es igual al inventario inicial más la producción menos las ventas.
  • Mayor que o igual a (≥). Cuando existe un límite inferior, por ejemplo: la producción de cierto producto debe ser superior a la demanda pronosticada.

Cualquier problema de programación lineal debe presentar una o varias restricciones. Se debe considerar dentro de las restricciones la no negatividad de las variables de decisión.

Se representan de la siguiente forma:

ecuaciones restricciones

Donde:

X1, X2, X3, …, Xn = Variables de decisión

Amn y Bm = Constantes

Ejemplo:

Ahora mostraremos un caso donde se realizará el planteamiento del problema de programación lineal:

El chef principal (encargado de la parrilla) de “Tacoste”, está tratando de decidir cuál es la mejor manera de asignar las materias primas disponibles a los cuatro platillos especiales del viernes por la noche. La decisión se debe tomar temprano por la tarde porque tres de los platillos se deben empezar a preparar ya (albóndigas, tacos y picadillo).

Cómo plantear un problema de programación lineal

Este nombre me parece familiar…

La tabla que está en seguida contiene la información sobre los alimentos en inventario y las cantidades requeridas por cada platillo.

Cuadro 1 insumos

No hay otros hechos importantes para la decisión del chef. A continuación, se presenta la demanda de mercado estimada y el precio de venta.




cuadro 2 demanda

El chef quiere maximizar el ingreso porque ya ha comprado todos los materiales, los cuales están en el congelador.

Planteamiento:

Definimos las variables de decisión:

H = Número de Hamburguesas con queso a preparar el viernes

A = Número de Albóndigas a preparar el viernes

T = Número de Tacos a preparar el viernes

P = Número de porciones de picadillo a preparar el viernes

El objetivo del chef es maximizar los ingresos, los cuales calcularemos multiplicando el precio de venta unitario con las unidades correspondientes a cada platillo (variables de decisión) y sumándolos entre sí:

funcion objetivo problema

Ahora plantearemos las restricciones:

  • Respecto a los Insumos:

Cada platillo utiliza cierta cantidad de insumos. En la tabla nos muestran las cantidades disponibles de cada uno de ellos; por lo tanto, la preparación de los platillos está limitada por la cantidad de insumos disponibles.

Multiplicando la cantidad necesaria de insumo para producir un platillo por las unidades correspondientes a cada platillo (variables de decisión) y sumándolas entre sí; obtenemos la fórmula del consumo total de cada uno de los insumos. Este resultado debe ser menor o igual a la cantidad disponible.

ecuaciones insumos

  • Respecto a la Demanda:

Esta restricción hace referencia que la empresa no debe preparar una cantidad de platillos mayor a la que puede vender según lo indica la demanda esperada.

restricciones demanda

  • No negatividad:

Las variables de decisión no pueden tener valores negativos:

no negatividad

Todas las ecuaciones mostradas representan el planteamiento del problema de programación lineal. La solución final la encontrarás aquí.

Usos de la Programación Lineal

Entre los usos de la programación lineal tenemos:

Planificación Agregada de Ventas y Operaciones:

Se busca minimizar los costos de producción en un corto plazo (tres y seis meses) que logre satisfacer la demanda esperada. Las limitantes que se presentan son: la capacidad de producción esperada, el tamaño de la fuerza de trabajo y los niveles de inventario. Los costos asociados en este tipo de problema son los salarios normales y de tiempo extra, contrataciones y despidos, subcontratación y costo de manejo de inventarios.

Planificación de productos:

Trata de encontrar la mezcla óptima de productos, considerando que los productos requieren diferentes recursos y tienen distintos costos. Como ejemplo podemos encontrar la mezcla óptima de elementos químicos para gasolina, pinturas, dietas para el ser humano y alimento para animales.

Flujo de producción:

Determinamos el flujo óptimo para fabricar un producto que debe pasar en secuencia por varias estaciones de trabajo, donde estación tiene sus costos y características de producción.

Programación de transporte:

Sirve para programar múltiples recorridos de cierta cantidad de vehículos para atender a los clientes o llevar los materiales que se transportarán entre diferentes plazas. Cada vehículo puede tener diferente capacidad de carga y de desempeño.

Manejo de inventarios:

Encontrar la combinación óptima de productos que se tendrán en inventario dentro de una red de almacenes.

Programación de personal:

Cuando se requiere elaborar un plan de personal que permita atender la demanda variable esperada con el menor número posible de empleados.

Control de desperdicios:

Cuando se requiere cortar algunos materiales como el acero, cuero, tela o alguna lámina de material; mediante programación lineal se puede calcular cómo reducir el desperdicio al mínimo.

Estos son algunos de los usos más comunes donde se utiliza la programación lineal. En general, cualquier problema de optimización que cumpla las condiciones mencionadas puede ser resuelto con programación lineal.

Reflexión Final

Muchos problemas que presentan las empresas se pueden modelar como problemas de programación lineal; por lo tanto, el conocer los conceptos relacionados y el planteamiento correspondiente, brindará a los responsables, mejores herramientas para la toma de decisiones.

Queremos saber tu opinión respecto a este tema, así que esperamos tus comentarios y dudas al respecto. Puedes compartir en tus redes sociales utilizando las botoneras de la parte superior e inferior.

Finalmente, a continuación presentamos el planteamiento y solución al ejemplo presentado al inicio del post relacionado a Infinity War:

 

Cómo plantear un problema de programación lineal

Cómo plantear un problema de programación lineal

Nuestras variables de decisión serían:

X = Número de Vengadores de Nivel 1 a utilizar

Y = Número de Vengadores de Nivel 2 a utilizar

Z = Número de Vengadores de Nivel 3 a utilizar

Siendo la función objetivo minimizar la destrucción de la tierra:

Min(Destrucción) = 500X+325Y+250Z

Sujeto a las siguientes restricciones:

  • Vencer a Thanos: 7000X+5000Y+4000Z≥81000
  • Restricción de Disponibilidad Nivel 1: X≤7
  • Disponibilidad Nivel 2: X≤8
  • Disponibilidad Nivel 3: X≤5

La solución final al problema sería:

X = 3 (Elijo a Thor, Iron Man y Dr. Strange)

Y = 8 (Todos deben participar)

Z = 5 (Todos deben participar)


Referencias:

  • Krajewski, L., Ritzman, L. & Malhotra M, (2008). Administración de Operaciones. Procesos y Cadena de Valor (Octava ed.). Mexico, D.F.: Pearson Educación.
    Disponible en: Casa del Libro y Amazon
  • Chase, R. & Jacobs, F. (2014). Administración de operaciones. Producción y cadena de suministro (Decimotercera ed.). Mexico, D.F.: McGraw-Hill.