Qué es la programación lineal

Resolver un problema de programación lineal consiste en hallar la mejor solución para un conjunto de restricciones dadas. en nuestro caso, todas las ecuaciones serán rectas (por eso el nombre). Lo más habitual es haber realizado problemas de optimización sobre una sola función, p. ej. hallar máximos y mínimos de . Por el contrario, en programación lineal:
  1. Son varias las restricciones que tenemos que considerar.
  2. Son restricciones abiertas, se trata de desigualdades, p. ej.
  3. La solución se encuentra en la intersección de todos los semiplanos que generan las desigualdades.
  4. Puede haber más de una solución óptima.
Visto lo anterior, ya tenemos algunas pistas de lo que tendremos que hacer en un problema de PL:
  1. Tendremos una serie de restricciones, desigualdades, que nos dan las condiciones de contorno. Se tratará de frases del tipo, ...como máximo produce 300 uds..., ...como mínimo debe ingerir 30mg de vitamina..., ...se dispone de 200h de trabajo para el proceso...
  2. La solución de un problema de PL consite en maximizar o minizar una función objetivo
  3. Las soluciones se encuentran la intersección de todos los semiplanos que generan las desigualdades. El área definida por esta intersección se llama región factible. La región factible puede ser abierta o cerrada
    1. Si la región factible es abierta, el problema tiene solución óptima si:
      • Piden minimizar y la región factible es abierta hacia arriba.
      • Piden maximizar y la región factible se abre hacia abajo
      • En otro caso, no hay solución óptima.
    2. Si la región factible es cerrada, el problema puede maximizarse y minimizarse
  4. Para cualquier región factible, la solución óptima siempre está en la frontera (borde) de la región factible. En concreto, se alcanza en los vértices. La función objetivo (o la paralela a ella que da la SO) nunca puede cortar a la región factible.
  5. Si hay dos vértices que dan la misma solución óptima, es solución óptima cualquiera de los puntos contenidos en el segmento definido por esos vértices.