Programación Lineal
La programación lineal es una técnica matemática que se utiliza para maximizar
o minimizar una función objetivo, la cual se expresa como una función lineal de varias
variables, por ejemplo, f(x,y) = ax + by. Este método es fundamental en la optimización
de recursos y se aplica en diversas áreas como la economía y la ingeniería.
Requerimientos de un modelo de programación lineal
Para formular un modelo de programación lineal, es necesario cumplir con ciertos
requerimientos. Aquí están los más importantes:
1. Función objetivo: Debe definirse una función lineal que se desea maximizar o
minimizar. La función objetivo se puede expresar en la forma: Z = c 1 x 1 + c 2 x 2 +
… + = c n x n donde Z es la función objetivo, c i son coeficientes constantes y x i
son los variables de decisión.
2. Variable de decisión: Se deben identificar las variables que afectarán la función
objetivo. Estas variables deben ser no negativas (en la mayoría de los casos), es
decir, deben cumplir con x i ≥ 0
3. Restricciones: Un conjunto de restricciones lineales que delimitan las
posibilidades de las variables de decisión. Las restricciones son expresiones
lineales que limitan los valores que pueden tomar las variables y se expresan en
la forma a 1 x 1 + a 2 x 2 + … + a n x n ≤ b o ≥ o =, donde a i son coeficientes
constantes y es un recurso o límite.
4. Linealidad: Tanto la función objetivo como las restricciones deben ser lineales.
Esto significa que cada término es una constante multiplicada por una variable,
sin exponentes, productos de variables o funciones no lineales.
5. No negatividad: Las variables de decisión, en la mayoría de los casos, deben ser
no negativas (es decir, x i ≥ 0). Esto representa que no se pueden tomar valores
negativos en este contexto.
6. Coherencia y realidad: El modelo debe ser coherente con la realidad del
problema que se quiere resolver y debe reflejar adecuadamente las relaciones
entre las variables.
Al cumplir con estos requerimientos, es posible utilizar diversos métodos de
solución, como el método simplex o la programación entera, para encontrar la mejor
solución al problema planteado.
Supuestos básicos de la programación lineal
La programación lineal (PL) se basa en varios supuestos fundamentales que son
esenciales para la validez y aplicabilidad de los modelos de PL. Estos supuestos son:
1. Linealidad: Tanto la función objetivo como las restricciones deben ser
funciones lineales. Esto implica que la relación entre las variables es aditiva y
que no hay términos y que no hay términos cuadráticos, cúbicos, exponentes, ni
productos de variables. Por ejemplo, si x 1 y x 2 son variables de decisión, la
expresión a 1 x 1 + a 2 x 2 es lineal, mientras que x 21 + 2 x2 no lo es.
2. Aditividad: Las contribuciones de cada variable en la función objetivo y en las
restricciones se suman de manera aditiva. Esto significa que el efecto de cambiar
una variable no depende del nivel de las otros variables en el contexto del
modelo.
3. No negatividad: Las variables de decisión deben ser no negativas. En muchas
aplicaciones, esto es lógico porque muchas cantidades en la vida real no pueden
ser negativas (por ejemplo, cantidades producidas, recursos utilizados).
Generalmente se establece que x i ≥ 0.
4. Certidumbre: Los coeficientes en la función objetivo y en las restricciones son
conocidos y constantes. Esto implica que no hay incertidumbre o variabilidad en
la información utilizada para formular el modelo. Por ejemplo, los costos,
recursos y restricciones son determinados sin ambigüedad.
5. Escalabilidad: Las relaciones y los resultados del modelo son válidos sin
importar la escala de las variables. Esto significa que, si todas las variables se
multiplican por una constante positiva, las relaciones y resultados siguen siendo
válidos.
6. Suma de componentes: Las variables se pueden dividir en componentes que
aportan individualmente a la función objetivo o a las restricciones. Esto permite
que se considere la contribución específica de cada variable.
7. Puntos extremos o vértices: Las soluciones óptimas para los modelos de
programación lineal se encuentran en los vértices del conjunto factible, que es la
región definida por las restricciones. Esto se relaciona con el concepto de
convexidad en la geometría.
Estos supuestos son cruciales para que las técnicas de programación lineal, como el
método simplex o la programación entera, sean efectivas y produzcan soluciones válidas
dentro del contexto del problema que se está abordando. Si alguna de estas condiciones
no se cumple, puede ser necesario emplear otros métodos de optimización más
complejos, como la programación no lineal o métodos heurísticos.
Formulación de un problema de programación lineal (PL)
La formulación de un problema de programación lineal implica traducir un
problema real en un modelo matemático que incluya una función objetivo, variables de
decisión y restricciones. A continuación, los pasos para formular un problema de
programación lineal, junto con un ejemplo práctico.
1. Definir el problema: Comprender el contexto y los objetivos que se desean
alcanzar.
2. Identificar las variables de decisión: Determinar qué cantidades se necesitan
definir para resolver el problema. Deben ser mensurables y relevantes para la
decisión.
3. Establecer la función objetivo: Definir una función que se debe maximizar o
minimizar, utilizando las variables de decisión identificadas. Se debe expresar en
términos lineales.
4. Formular las restricciones: Identificar las limitaciones o condiciones que
afectan al problema. Estas restricciones deben expresarse como ecuaciones o
inecuaciones lineales en función de las variables de decisión.
5. Definir las condiciones: Especificar que las variables de decisión son no
negativas, cuando sea posible.
Ejemplo práctico:
Una empresa produce dos tipos de productos, A y B. El objetivo de la empresa es
maximizar las ganancias.
Datos:
Ganancia por cada unidad de producto A: $5
Ganancia por cada unidad de producto B: $3
La empresa tiene una capacidad de producción de 100 unidades en total.
La producción de producto A requiere 1 hora de trabajo, y la producción de
producto B requiere 2 horas de trabajo.
La empresa tiene 80 horas de trabajo disponible.
1. Definición del problema: Maximizar las ganancias produciendo los productos
A y B, respetando las restricciones de capacidad de producción y de tiempo de
trabajo.
2. Identificación de variables de decisión:
x 1: Número de unidades producidas del producto A.
x 2: Número de unidades producidas del producto B.
3. Establecer la función objetivo: Maximizar la ganancia total: Z = 5 x 1 + 3 x 2
4. Formular las restricciones:
Restricción de capacidad de producción: x 1 + x 2 ≤ 100
Restricción de tiempo de trabajo: 1 x 1 + 2 x 2 ≤ 80
5. Definir las condiciones: x 1 ≥ 0 x 2≥ 0
Modelo final: El problema de programación lineal puede ser formulado de la
siguiente manera:
Maximizar: Z = 5 x 1 + 3 x 2
Sujeto a:
x 1 + x 2 ≤ 100 (capacidad de producción)
x 1 + 2 x 2 ≤ 80 (tiempo de trabajo) x 1 ≥ 0 x 2 ≥ 0
Este modelo se puede resolver utilizando métodos de programación lineal, como
el método simplex, para encontrar los valores óptimos de x 1 y x 2 que maximicen la
ganancia Z.