5.1 FUNDAMENTOS DEL MÉTODO SÍMPLEX
En la sección 4.1 se introdujo el concepto de soluciones factibles en un vértice (FEV) y la función clave que desempeñan en el método símplex. Estos conceptos geométricos se relacionaron con el álgebra del método símplex de las secciones 4.2 y 4.3. Sin embargo, todo esto se hizo en el contexto del problema de la Wyndor Glass Co., que tiene sólo dos variables de decisión y, por lo mismo, tiene una interpretación geométrica directa. ¿Cómo pueden generalizarse estos conceptos a dimensiones mayores cuando se manejan problemas más grandes? La respuesta se dará en esta sección.
Para comenzar se introducirá parte de la terminología básica de cualquier problema de programación lineal con n variables de decisión. Mientras se desarrolla esta tarea puede ser útil que el lector consulte la fi gura 5.1 (que es una repetición de la fi gura 4.1) para interpretar estas defi niciones en dos dimensiones (n 5 2).
Terminología
Puede entenderse de manera intuitiva que las soluciones óptimas de cualquier problema de programación lineal deben estar sobre la frontera de la región factible y, de hecho, ésta es una propiedad general. Como la frontera es un concepto geométrico, las defi niciones iniciales aclaran cómo se puede identifi car en forma algebraica la frontera de la región factible.
La ecuación de la frontera de restricción de cualquier restricción se obtiene al sustituir su signo
#, 5 o $ por un signo 5.
En consecuencia, la forma de la ecuación de una frontera de restricción es ai1x1 1 ai2x2 1 ? ? ? 1 ainxn 5 bi para las restricciones funcionales y xj 5 0 en el caso de las de no negatividad. Estas ecuaciones defi nen una fi gura geométrica “plana” (llamada hiperplano) en un espacio n dimensional, análoga a la recta en el espacio bidimensional y al plano en el espacio tridimensional. Este hiperplano forma la frontera de restricción de la restricción correspondiente.