MÉTODO SIMPLEX Formas equivalentes de un Modelo de Programación Lineal

MÉTODO SIMPLEX

Formas equivalentes de un Modelo de Programación Lineal.

        Después de la formulación de un problema de programación lineal, las siguientes etapas a considerar en el método para la obtención de la solución son, modificar el modelo y adaptarse a la forma canónica o bien a la forma estándar.  La primera es esencialmente útil para la teoría de la dualidad, y la segunda es para desarrollar el procedimiento general para solución de cualquier problema de programación lineal.

I)  Forma canónica.

         [pic 2]

Características:

1. La función objetivo es para maximizar.
2. Todas las restricciones son del tipo  ≤
3. Todas las variables de decisión son no-negativas.
4. El modelo se puede expresar matricialmente.

NOTA:  Si al menos una no se cumple no es forma canónica.

II) Forma estándar.

[pic 3]

Características:

1. La función objetivo puede ser para maximizar o bien para minimizar.
2. Todas las restricciones son igualdades.
3. El lado derecho de las restricciones son cantidades no negativas.
4. Las variables de decisión son no negativas.
5. El modelo se puede expresar matricialmente.

        La forma estándar es especialmente útil para la presentación de la información del problema de P.L.  y como preparación de la tabla para obtener la solución.

        Para resolver el problema por el método simplex, el modelo primero se lleva a la forma canónica y luego a la forma estándar. Es necesario para transformar el modelo a las formas mencionadas, conocer las siguientes reglas algebraicas, llamadas reglas de equivalencia:

Reglas de Equivalencia  (algebraicas):

1. Toda función objetivo de un modelo de programación lineal, cumple:

   [pic 4] o bien   [pic 5]

Ejemplo:

    Sea         Z = {-8, 0, 3, 11}  ;  (-Z) = {-11, -3,  0,  8,} 

 Entonces el         Max Z = 11 = - Min (- Z) = - (-11)  =  11

                     Min Z = -8 = - Max (- Z) = - Max[  (8)] = -8

1. Toda desigualdad invierte su sentido si se multiplica por   (- 1).

      sea:          aX ≤ b ⇒ - aX ≥ - b ; ó aX ≥ b ⇒ - aX ≤ - b

Ejemplo:        4 < 10    ⇒    -4 > -10    

1. Toda ecuación puede expresarse como un sistema de 2 desigualdades en sentido opuesto; esto es:

Si  aX = b   ⇒   aX ≤ b  y  aX ≥ b   ó    aX ≤ b  y  - aX ≤ - b  (reemplaza a la primera)

Ejemplo: Considere la ecuación 3X - 2 = 7, cuyas solución es X = 3; por lo tanto, si se descompone en dos desigualdades la solución del sistema es igual a la solución de la ecuación.

              3X - 2 = 7         ⇒    3X - 2  ≤  7     y      3X - 2  ≥  7          

                  X = 3      ⇒          X  ≤  3     y             X   ≥  3

                             X ∈ (- ∞, 3]  ∩  [3, ∞)  =  3

1. Toda restricción ≤ puede expresarse como una igualdad sumando una variable no negativa, al lado izquierdo de la restricción llamada variable de holgura.

Si:    aX  ≤  b    ⇒    aX  +  H   =  b   ;      H  ≥  0

Toda restricción del tipo  ≥  puede expresarse como una igualdad restando del lado izquierdo una variable no negativa llamada variable superflua o de superávit, esto es:

Si:    aX  ≥  b     ⇒     aX  -  S  =  b    ;      S  ≥  0        

1. Una variable libre (o no restringida en su valor) se puede expresar como la diferencia de dos variables no negativas.

Si X es libre   ⇒   X∈ [- ∞, ∞ ]

La variable libre se puede expresar como:

X = Y - Z       ;             Y ≥ 0  ,    Z ≥ 0                        

Por lo tanto:    

Si X < 0    ⇒     (Y - Z) < 0      ⇒    Y < Z

Si X = 0    ⇒     (Y - Z) = 0      ⇒    Y = Z

Si X > 0    ⇒     (Y - Z) > 0      ⇒    Y > Z

EJEMPLO  1:

Dado el siguiente modelo, determinar su forma canónica y su forma estándar.

[pic 6]

a) Forma canónica:

[pic 7]        [pic 8]

Haciendo el cambio de variables propuesto y escribiendo el modelo matricialmente:

...