Este post se titula Programación lineal. Conceptos básicos, y eso es porque hablaremos de los elementos mas importantes sobre el tema, con la limitación de espacio propia de un blog, como este.
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 la primera restricción ≤ 60
1.40*vd1 + 0.5*vd2 ≤ 90 segunda restricción
vd1 & vd2 restricción negativa ≥ 0
0.25, 1, 1.40, 0.5 son los coeficientes tecnológicos
65, 90 es la disponibilidad de recursos
Elementos importantes de la Programación lineal
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