La fórmula
max cᵀx sujeto a Ax ≤ b, x ≥ 0
Por qué funciona
El símplex se apoya en un hecho geométrico que lo cambia todo: las restricciones lineales encierran una región con forma de poliedro, y el óptimo de una función lineal sobre ese poliedro está siempre en un vértice. Eso convierte un problema con infinitos puntos posibles en uno con un número finito de candidatos. El algoritmo empieza en un vértice y va saltando al vecino que más mejore el objetivo, y se para cuando ninguno mejora: entonces ese vértice es el óptimo. La regla de Bland, que elige siempre la primera columna válida, garantiza que el método no se quede dando vueltas.
Cómo resolverlo a mano
- Escribe el objetivo y las restricciones con un coeficiente por variable
- Añade una variable de holgura a cada restricción para volverla una igualdad
- Entra la variable que más mejora el objetivo y sale la que primero se agota
- Repite hasta que ninguna columna mejore el resultado
Lo que conviene saber
La forma estándar que resuelve esta página pide restricciones de menor o igual con límites positivos y variables no negativas, que es la del noventa por ciento de los problemas de clase. Con una restricción de mayor o igual, o con un límite negativo, haría falta el símplex de dos fases, y aquí se avisa en vez de dar un resultado equivocado. La columna de holgura es la parte más útil del resultado y la que menos se mira: dice cuánto sobra de cada recurso en el óptimo, y las restricciones que se agotan del todo son las únicas que de verdad limitan el resultado. Ampliar cualquier otra no sirve de nada.