programación lineal (PL o LP) básicaprogramación lineal (PL o LP) básica
Definición: PL ó LP es Opt{cx: Ax = b, x >= 0}. (Otras formas de restricciones son posibles, tales como Ax <= b.). Se permiten cotas generales para las variables originales (esto es, previas a las transformaciones introducidas por los sistemas de cómputo, que llevan a la forma Ax + y = b). Las variables y se denominan variables lógicas, que abarcan los casos de una variable floja, de exceso o artificial, dependiendo de la forma de la restricción original. La forma de cómputo introduce automáticamente cotas a las variables lógicas. Algunas cotas pueden ser infinitas (esto es, ausentes) y cuando esto pasa se considera libre a la variable de decisión (estructural) o a la variable lógica, cuando ambas cotas son infinitas en valor absoluto.
Las variables no-negativas del vector x se denominan variables de decisión originales, los coeficientes A están en una matriz y b es un vector que implica una cota o RHS (right hand side, término de la derecha). c es el vector de coeficientes de costo en los problemas de minimización. cx es el polinomio lineal denominado función objetivo que se extremiza (maximiza o minimiza) y que indica el objetivo de la optimización. Ax = b (con signo igual u otros) son las restricciones, que suelen ser inecuaciones hasta que se las transforma en ecuaciones con la ayuda de las variables lógicas. Toda optimización se define como la búsqueda del máximo beneficio para una dada situación. El máximo beneficio está medido por cx y la dada situación por Ax = b (con signo igual u otros). Se obtiene matematicamente dandole el valor mejor de todos a las variables de decisión, al arbitrio del optimizador. La interpetación geométrica es que la dada situación es un poliedro o hiperpoliedro con varias aristas y que para satisfacer la maximización el método va saltando de "esquina" en "esquina", invariablemente subiendo hacia la "esquina" más alta del hiperpoliedro, encontrando allí que ya no tiene hacia donde saltar. Esta descripción se relaciona con la forma clásica (Simplex) de resolver los problemas de programación lineal.
5.may.1999
Pulsar tecla de vuelta
Glosario de Carlos von der Becke.