Forma estándar de PL

Publicado en Ciencias administrativas Etiquetado con

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