Glosario

En un espacio n-dimensional, el polítopo es la generalización de una figura geométrica que en un espacio bidimensional se denomina polígono y en uno tridimensional se denomina poliedro. En la optimización interesan los de la clase convexa, a los que groseramente se puede calificar como cerrados y que se construyen intersectando rectas, planos o hiperplanos que representan la frontera de las restricciones de un problema para conformar una representación geométrica de la región o espacio de soluciones factibles del problema. También se lo puede describir como un conjunto finito, al que también se califica como convexo, constituido por todos los puntos que representan soluciones factibles del problema.

En el método símplex, dada una solución óptima, los precios sombra miden la tasa de cambio en el valor de la función objetivo como consecuencia del cambio unitario o marginal de la constante o parámetro del lado derecho de una restricción. En la interpretación económica más común del método simplex, en la que el problema primal es un problema de asignación de recursos, los precios sombra son las variables del problema dual y representan el valor unitario (de ahí la denominación de precios) de adquirir los recursos usados para obtener la solución óptima. Aunque se los llama precios, no se trata de valores de mercado sino de valores imputados (de ahí la caracterización de sombra) en el contexto de la solución óptima.

En los algoritmos de optimización, en general, la prueba de optimalidad refiere a la condición que se debe comprobar al término de cada iteración para determinar si se ha encontrado la solución óptima buscada. En caso de verificarse dicha prueba, el algoritmo debe terminarse e informar el resultado encontrado. Obviamente, en caso contrario, se debe proceder a ejecutar otra de las iteraciones previstas en el algoritmo. En el caso particular del algoritmo símplex, si se usan las tablas símplex y el método bifásico, por ejemplo, la prueba de optimalidad puede expresarse de la siguiente manera: si, y solo si, cada coeficiente en la fila 0 (o en la fila 0' de la Fase I del método bifásico) es no-negativo, la solución óptima (o el final de la primera fase) ha sido encontrada.

En un espacio n-dimensional, los vértices son puntos que se definen por las intersecciones de n ecuaciones de frontera (i.e. 2 rectas en el plano, 3 planos en un espacio tridmensional, etc.). En la optimización, a estos vértices del polítopo de soluciones factibles también se los llama puntos extremos. Si al polítopo se lo concibe como un conjunto convexo, una definición más rigurosa diría que un punto extremo de un conjunto convexo S, en un espacio vectorial real, es un punto que pertenece a S pero que no se encuentra en ningún segmento de línea abierto (i.e. cuyos extremos no pertenecen al segmento) que una dos puntos cualquiera de S.