Forma estándar de PL
El empleo de las soluciones básicas para resolver el modelo general de PL requiere poner el problema en una forma estándar, cuyas propiedades son:
– Todas las restricciones (con excepción de las restricciones de no negatividad sobre las variables) son ecuaciones con un lado derecho no negativo.
– Todas las variables son no negativas.
– La función objetivo puede ser del tipo de maximización o de minimización.
1. Conversión de desigualdades a ecuaciones. Una desigualdad del tipo<=5 (se convierte a una ecuación aumentando su lado izquierdo con una variable de holgura (superávit) (vease la sección 2.3.3 para las definiciones de holguras y superávit).
Ejemplo de: restricción.
2x1 + 2x2 £ 3
es equivalente a x1 + 2x2 + s1 = 3
donde la holgura s1 >_ 0.
Ejemplo de restricción.
3x1 + x2 ³ 5
es equivalente a
3x1 + x2 – s1 = 5
donde el superávit S 1 ? 0.
El lado derecho de una ecuación siempre se puede hacer no negativo, multiplicando 1, ecuación por -1, de ser necesario. También observamos que una desigualdad ( £ ) se convierte a ( ³ )multiplicando ambos lados por -1. Por ejemplo, 2 < 4 se convierte en -2 > -4 cuando multiplicamos ambos lados por -1.
2. Conversión de una variable no restringida a variables no negativas. Una variable x; no restringida se puede expresar en términos de dos variables no negativas, utilizando la sustitución
| x j = x +j – x –j , x +j , x –j | ³ 0 | |||
| Por ejemplo, | para | xj | = -5, dejamos que | x +j = 0 yx –j = 5 . Si x; = +5, entonces |
| tenemos x +j = 5 | y x –j | = 0 . En ambos casos, x +j | y x –j son no negativas, como se desea. | |
La sustitución se efectúa en todas las restricciones y en la función objetivo. Después de resolver el problema en términos de x +j y x –j , el valor de la variable original se determina en. onces mediante una sustitución hacia atrás.
3. Conversión de maximización a minimización. La maximización de una función f (x1 , x2 ,K, xn ) es equivalente a la minimización de f (x1 , x2 ,K, xn ) , en el sentido de que ambos problemas producen los mismos valores óptimos de x1 , x2 ,K, y xn .
Fuente: Apuntes de Investigación de operaciones de la UNIDEG
