Fundamentos de la Programación Lineal: Proporcionalidad, Aditividad y Más

Fundamentos de la Programación Lineal

La programación lineal se basa en varios supuestos clave que permiten modelar y resolver problemas de optimización. Estos supuestos son:

Supuestos Básicos

• Proporcionalidad: La contribución de una variable de decisión en todas las relaciones es proporcional a su valor, y el factor de proporcionalidad es constante.

• Aditividad: El valor del objetivo y de cualquier restricción es igual a la suma de los aportes de las variables. La contribución de cualquier variable debe ser independiente de los valores de las otras. Esto implica que el objeto es separable, en una suma de funciones, cada una de las cuales es una expresión lineal de una única variable.

• Divisibilidad: Las variables de decisión se pueden dividir en cualquier nivel fraccionario. Por ejemplo, si se desea un patrón de embarque de cajas que minimice el costo, no tiene sentido obtener 2.31 cajas. En casos como este, la divisibilidad no se sostiene y el modelo lineal puede no corresponder al problema.

• Certidumbre: Cada parámetro que interviene en el problema se supone conocido con certeza. Las posibles variaciones, tanto en la función objetivo como en las restricciones que pueden ocurrir en la realidad, no son tomadas en cuenta por los métodos de resolución.

La proporcionalidad, aditividad y la certidumbre son consecuencias directas de la función misma de la linealidad, mientras que la divisibilidad es consecuencia de la continuidad exigida a la variable.

Si no se cumple alguno de los supuestos de proporcionalidad, aditividad o certidumbre, el modelo no es lineal.

Problema de Programación Lineal (PL)

Un problema de programación lineal busca optimizar (maximizar o minimizar) una función objetivo, la cual es una expresión lineal de las variables de decisión.

Cada variable está sujeta a una restricción de signo determinada. El objetivo de un problema de programación lineal es determinar una solución óptima.

Elementos de un Problema PL

Donde:

• X₁, ..., X_n son las variables de decisión.
• Z = C₁X₁ + ... + C_nX_n es la función objetivo.
• C₁, C₂, ... son los valores conocidos llamados coeficientes de costos.
• C_j (j=1, 2, 3, ...) es la variación que experimenta el objetivo por un cambio unitario.
• A_ij (i=1, 2, 3, ...) son constantes conocidas llamadas coeficientes.
• b₁, b₂, ... son constantes conocidas que constituyen el vector de recursos.

La no negatividad X_j > 0 (j=1, 2, 3, ..., n) puede derivar del problema, pero siempre debe introducirse para aplicar el método simplex.