Programación lineal

La programación lineal es un bloque de Matemáticas Aplicadas a las Ciencias Sociales II: traduce problemas reales de optimización de recursos (producción, costes, beneficios) a un modelo matemático resoluble gráficamente, y aparece con mucha frecuencia en la prueba de Matemáticas Aplicadas a las Ciencias Sociales II de la PAU. Este cuestionario repasa la construcción de la región factible como la intersección de los semiplanos definidos por un conjunto de restricciones lineales —un conjunto convexo, propiedad que resulta clave para que el problema tenga solución bien definida—.

Se trabaja en profundidad el teorema fundamental de la programación lineal: si una función objetivo lineal $f(x,y)=ax+by$ alcanza un valor óptimo (máximo o mínimo) sobre una región factible acotada, dicho óptimo se encuentra necesariamente en al menos uno de los vértices de la región. Este resultado es lo que permite resolver el problema evaluando la función objetivo únicamente en los vértices, en lugar de estudiar infinitos puntos de la región.

Se practica la resolución completa de problemas de maximización y minimización mediante el método gráfico: identificar los vértices de la región factible resolviendo los sistemas de ecuaciones de las rectas que se cortan, y evaluar la función objetivo en cada uno de ellos para determinar el óptimo —ejemplificado con problemas como maximizar $3x+2y$ sujeto a $x\ge 0,y\ge 0,x+y\le 4$, o minimizar $x+y$ con restricciones de tipo $x\ge 2,y\ge 2,x+y\ge 6$—.

Se abordan también los casos especiales: regiones factibles no acotadas, donde la función objetivo puede no tener máximo (tendiendo a infinito) aunque sí pueda tener mínimo según su dirección; restricciones redundantes, cuya eliminación no altera la región factible definida por las demás; y el caso de una región factible vacía, que indica que el sistema de restricciones es incompatible y el problema no tiene solución factible. Se incluye también el caso curioso en que la función objetivo es constante a lo largo de un lado entero de la región (cuando sus rectas de nivel son paralelas a esa recta frontera), situación en la que el óptimo se alcanza en todo un segmento, no solo en un vértice.

Con diez preguntas de cálculo directo y comprensión conceptual, este test prepara al alumnado para resolver con seguridad los problemas de optimización lineal del examen de acceso a la universidad.

• Construir la región factible de un problema de programación lineal a partir de un conjunto de restricciones
• Aplicar el teorema fundamental de la programación lineal para localizar el óptimo en los vértices de la región factible
• Resolver problemas de maximización y minimización mediante el método gráfico evaluando la función objetivo en los vértices
• Reconocer las consecuencias de una región factible no acotada o vacía sobre la existencia de solución óptima
• Identificar restricciones redundantes y el caso especial de óptimo alcanzado en un segmento completo de la región

Si una función objetivo f(x,y)=ax+by debe ser maximizada en una región factible acotada y convexa, el teorema fundamental de la programación lineal establece que si existe una solución óptima, esta se encuentra en al menos uno de los vértices de la región factible. — Dada la función objetivo f(x,y)=3x+2y sujeta a x≥0, y≥0, x+y≤4, evaluando los vértices (0,0), (4,0) y (0,4), el valor máximo es 12 en el punto (4,0).