Teoremas básicos de PL

La estrategia para solucionar los programas lineales contiene dos pasos principales: en primer lugar, delimitamos las combinaciones de las variables que cumplen las restricciones (conjunto factible), y a continuación identificamos cuál de ellas optimiza (hace máximo o mínimo) el valor de la función objetivo. La enumeración explícita de las soluciones no es una opción - especialmente en los problemas continuos -, de manera que empleamos algoritmos que reducen el tiempo y el esfuerzo requeridos para identificar la solución óptima. Estos algoritmos, incluyendo el simplex, se basan en un pequeño grupo de teoremas que describen las características del conjunto factible, las combinaciones que son soluciones potenciales y deben ser comprobadas, y las condiciones que debe reunir la solución óptima (en caso de que exista).

• Teorema 1: el conjunto factible es un conjunto convexo.
• Teorema 2: la función objetivo toma su máximo o su mínimo en un punto extremo del conjunto factible (o en una combinación lineal convexa de ellos)
• Teorema 3: si, dentro del conjunto factible es posible encontrar un número k≤m de vectores linealmente independientes y tales que λ1·P1 + λ2·P2 +...+λk·Pk = P0 (λi≥0), entonces el punto Λ = (λ1, λ2,... λk, 0, 0, ..., 0), es un punto extremo
• Teorema 4: si Λ = (λ1, λ2,... λn) es un punto extremo del conjunto factible, los vectores asociados con valores λi positivos forman un conjunto linealmente independiente, siendo positivos, como máximo, solo m de los citados valores 

De manera muy amplia, estos teoremas garantizan que la solución óptima de los modelos lineales (si existe) está situada en un punto extremo del conjunto de soluciones factibles, y que esta solución óptima es una combinación lineal formada por (como mucho) m procesos de decisión, siendo m el número de restricciones del modelo; esto permite reducir radicalmente el espacio de búsqueda y diseñar algoritmos que nos ayudarán a hallar la solución óptima de manera rápida y eficiente, sin necesidad de enumerar explícitamente todas y cada una de las posibles combinaciones que verifican las restricciones. Posiblemente el algoritmo más común es el simplex.