Programación lineal

Definición

Es uno de los instrumentos utilizados en investigación operativa para el planteamiento y la resolución de problemas mediante la utilización de modelos matemáticos.

Así, el término programación hace referencia al procedimiento para resolver un problema para obtener un resultado óptimo. Y, el adjetivo lineal implica que todas las funciones o restricciones que intervienen en el modelo matemático han de ser lineales.

Formulación de un problema de programación lineal

Con carácter general un problema de programación lineal se puede plantear del siguiente modo:

Optimizar

Sujeto a:

x_i ≥ 0 i = 1, ..., n

Donde:

• — representa el vector de variables de decisión, es decir, las incógnitas del problema. Estas variables son números reales, aunque en la mayoría de los problemas se incluyen restricciones de no negatividad para que la solución óptima tenga sentido económico (x_i ≥ 0). En el caso de que la solución del problema sea un número entero, entonces, para calcular su valor se utiliza la programación entera.

  De forma genérica en un problema de programación lineal se incluyen n variables (x_i ≥ 0, i = 1, ..., n). Sin embargo, el número de incógnitas puede ser igual al número de restricciones, pero también puede ser mayor o menor.

• — representa la función objetivo que se quiere optimizar y se obtiene multiplicando las variables de decisión del problema por sus correspondientes coeficientes. Esta función objetivo indica lo que el decisor pretende conseguir y puede ser a maximizar o a minimizar. Cuando se maximiza el decisor buscará la solución que le permita obtener los mayores resultados posibles con las restricciones de recursos que dispone, mientras que, si es una función a minimizar entonces se buscará aquella solución que le proporcione los menores resultados posibles de acuerdo con las restricciones del problema.

  En los problemas de programación lineal sencillos, existe una única función objetivo, pero si el problema se plantea incluyendo dos o más objetivos (con independencia de que sean a maximizar o a minimizar) entonces la resolución de este tipo de problemas se lleva a cabo utilizando la programación multiobjetivo.

• — Sujeto a, indica cuales son las restricciones del decisor para conseguir su objetivo. Con el fin de indicar que los recursos disponibles son limitados y, por lo tanto, es necesario asignarlos de la forma más adecuada posible, estas restricciones se pueden plantear de dos formas: como restricciones de igualdad o como restricciones de desigualdad. Las restricciones de igualdad implican que se tienen que agotar todos los recursos disponibles para conseguir los objetivos. Las restricciones de tipo desigualdad a su vez suelen ser de tipo mayor o igual (≥) o de tipo menor o igual (≤). Las restricciones de tipo mayor o igual indican la cantidad de la que como mínimo se dispone y puede ser superada. Las restricciones de tipo menor o igual indican la cantidad de la que se dispone como máximo y, por lo tanto, no puede ser superada.

En el planteamiento general del problema la restricción se ha planteado como restricción del tipo ≤. Donde A representa la matriz de coeficientes de las restricciones del problema y c el vector de términos independientes. Tanto los elementos de A como los de c son conocidos. Además, el número de restricciones del problema es finito (de forma genérica se suele decir que se trabaja con m restricciones).

Solución gráfica de un problema de programación lineal

Para obtener la solución de un problema de programación lineal se supone que el modelo planteado es lineal y determinista, es decir, se conocen los parámetros del modelo. Además, las variables son reales y se cumplen las condiciones de no negatividad.

Partiendo de estos supuestos, la forma habitual de resolver este tipo de problemas es mediante la utilización del método simplex. Sin embargo, si el problema tiene solo dos variables de decisión y algunas restricciones entonces se puede utilizar un procedimiento gráfico para resolverlo.

Dado el siguiente ejemplo con una función objetivo a maximizar, dos variables de decisión (x₁ y x₂) y tres restricciones:

Max x₁ + 2x₂

Sujeto a: -2x₁ +x₂ ≤ 3

x₁ + x₂ ≤ 9

x₁ ≤ 6

x_i ≥ 0, i=1, 2.

Los pasos para la obtención de la solución gráfica son los siguientes:

a) Representar todas las restricciones del problema y obtener la región factible, la cual estará formada por el conjunto de puntos que cumplen simultáneamente todas las restricciones del problema. Si está región factible no está acotada entonces habrá soluciones factibles que harán la función objetivo tan grande o pequeña como se quiera. Si no existen valores que cumplan todas las restricciones, entonces el problema de programación lineal será infactible y no tendrá solución óptima. Para el ejemplo planteado anteriormente la región factible, representada utilizando el software winQSB, está dada por el área sombreada siguiente:

b) Seleccionar un punto de la región factible y en ese punto se representa la función objetivo.

c) Desplazar de forma paralela la función objetivo en la dirección en la que para ella se obtengan mejores valores, hasta un punto extremo o punto esquina de esta región factible. Este punto extremo de la región factible que proporciona el mejor valor a la función objetivo es la solución óptima. La solución óptima de un problema de este tipo no tiene porque ser única, así, en el caso de que exista más de una solución óptima, cada una de ellas se denominará solución óptima alternativa ya que todas ellas proporcionan el mismo mejor valor de la función objetivo.

En el ejemplo planteado existe una única solución óptima en la que las coordenadas del punto máximo serían: x₁=2 y x₂=7. Gráficamente está solución sería:

Aplicaciones

El ámbito de aplicación de la programación lineal es muy variado, ya que, se puede aplicar a cualquier problema en el que sea necesario la asignación de los recursos disponibles. Entre ellos se puede citar como ejemplos: en finanzas, para la selección de carteras de inversión; en economía, en la elección de los procesos de producción, de materias primas, de productos, asignación de recursos a las necesidades de un país, asignación de recursos humanos, en el planteamiento de la producción agrícola adecuada en un determinado territorio, etc.; en el ámbito de la empresa, para la asignación de recursos, asignación de personal, planeación de abastecimiento, distribución y comercialización de productos, etc.; en medio ambiente, para el control de la contaminación del aire, en el reciclado de desechos sólidos en medicina, en el diseño de diferentes tipos de terapias, etc.

Para la obtención de la solución en los problemas de programación lineal existen diferentes tipos de programas. Entre los programas que habitualmente se han ido utilizando para resolver este tipo de problemas se pueden destacar los siguientes: AMPL, MLP, GAMS, LINGO, LINDO, WINQSB, etc.