Programación lineal. Conceptos básicos.

Haciendo un ligero esbozo histórico, diré que la programación lineal, es una técnica que surgió en el primer tercio del siglo XX, y fue desarrollada, aplicándola a situaciones reales  para resolver problemas relacionados, con la programación, el transporte, y logística en los años, de la segunda guerra mundial.

Su creador fue el matemático ruso L. Kantorovich, y su aplicación inicial tuvo que ver con una optimización de los programas de  fabricación.

Sin embargo su aceptación, se extendió rápidamente a la economía y para 1950  el matemático estadounidense George Dantzig creó el primer algoritmo.

La programación lineal en esencia, es una función compleja que intenta determinar a partir de un conjunto de variables conocida, su influencia optima en determinados resultados.

Componentes de un problema de programación lineal

Las variables de decisión:

Son las cantidades, volúmenes o comportamientos, que se intentan estimar, como resultado.

La función objetivo:

Es la expresión matemática que intenta optimizar (maximizar o minimizar), algún valor numérico que representa ganancias, costos, cantidad de producción, volumen de inversión, etc;

Su razón de ser es evaluar, en qué medida cada variable de decisión contribuye al valor neto de una actividad económica especifica.

Coeficiente de la función:

Expresa la cantidad en la que el valor de la función objetivo cambiaría cuando se modifica una unidad de una variable de decisión, viene dada por el coeficiente de función objetivo correspondiente.

Restricciones:

Las restricciones son ecuaciones que limitan o definen la cantidad total de un recurso particular, que es necesario o requerido para llevar a cabo las actividades que decidirían el nivel de optimización de las variables de decisión.

Restricciones no negativas.

Una condición obligatoria de este tipo de restricciones, es que tienen que ser positivas con independencia, de que el objetivo de la función sea maximizar o minimizar el valor.

La solución óptima de un problema de programación lineal, es aquella que satisfaga mejor las restricciones.

Esto quiere decir que de todas las soluciones factibles, será óptima aquella que en el caso de una necesidad de maximización, el valor de la función objetivo sea el mayor posible, o sea el máximo.

Por el contrario, si nos encontramos ante un problema de minímización , la solución más adecuada será aquella donde la función objetivo ofrezca el mínimo.

Recursos disponibles

Constituyen los materiales, recursos, o elementos que participan en la ecuación y sobre los que se aplica la misma

Coeficientes tecnológicos

Cuando intentamos prever el futuro a través de la programación lineal, es importante considerar las limitaciones técnicas que nos impone la realidad objetiva y el entorno.

Los coeficientes tecnológicos, son elementos de referencia que conocemos y sobre los que se mueve el fenómeno que necesitamos estimar.  

La estructura de un problema de programación lineal debería ser algo como esto

Maximize  20* vd1 + 18*vd2; subject to
0.25*vd1 + 1*vd2  ≤60
1.40*vd1  + 0.5*vd2 ≤ 90 where vd1 & vd2 ≥ 0

Aquí podemos identificar los diferentes componentes:

vd1 y vd2 son las variables de decisión

Maximize  20* vd1 + 18*vd2 es la función objetivo

20* vd1  y  18*vd2 son los coeficientes de la función

0.25*vd1 + 1*vd2  ≤  60 es la primera restricción

1.40*vd1  + 0.5*vd2  ≤  90 es la segunda restricción

vd1 & vd2  ≥ 0 es la restricción negativa

0.25, 1, 1.40, 0.5 son los coeficientes tecnológicos

65, 90 es la disponibilidad de recursos

Elementos importantes

Potenciación

Partimos de considerar que las variables de decisión, siempre tienen una potencia de uno.

La condición critica

Para poder aplicar un problema  de programación lineal, es necesario tener definidas: la función objetivo, la disponibilidad de recursos y las variables de decisión positivas relacionadas entre sí.

Dualidad

Todo problema de programación lineal, puede convertirse a  su par correspondiente,  capaz de dar la misma solución factible de la función objetivo.

Esto lo puede hacer de modo automático el programa con el que trabajemos, pero conocer su esencia es importante.

Cuando se trata, por ejemplo de un problema de maximización, por lógica todas las restricciones asociadas con su función objetivo serán del tipo “menor que igual a” la disponibilidad de recursos dada, (podría ser solo “igual a”, en el caso de una   restricción en particular restringida)

Si eso no sucediese y alguna restricción fuera del tipo “mayor que igual a” lo recomendable es convertir la solución a una forma canónica (multiplicar por un “menos”) para que la restricción del problema de maximización se transforme en “menor que igual a” .

Por oposición si fuera un problema de minimización, entonces todas las restricciones asociadas con la función objetivo deben tener restricciones “mayor que igual a” a la disponibilidad de recursos considerada, a menos que exista alguna restricción que particularmente no esté restringida (tipo “igual a”), lo adecuado es multiplicar por -1, para convertirlas. 

Antes de la dualidad

Antes de proceder con un ejercicio de dualidad es necesario que las variables de decisión sean igual  mayor que cero, de no ser asi necesitan ser transformadas de forma canonical.

En Python podemos trabajar los problemas de programación lineal con Ipsolve.

Por ultimo, decir que la programación lineal, se basa en la creación de modelos cuando el problema que necesitamos resolver tiene solo funciones lineales, esto es :

Tenemos variables de decisión conocidas y queremos saber que influyen en un problema dado.

Dicho de otro modo: el concepto programación lineal  no se enmarca dentro de la programación de computadoras, sino que se refiere a escoger una vía de solución cuando el modelo matemático del problema contiene solo funciones lineales

Este articulo, pretende solo ser un esbozo de los conceptos más básicos de la solución a problemas de programación lineal.

Espero modestamente que este artículo, sirva de ayuda a alguien.

Gracias

“… y yo tenia respuesta a todas sus preguntas, incluso a las que aún no se ha hecho.”

Y