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:

[pic 9]       [pic 10]

b) Forma estándar:

La función objetivo queda igual, sin hacer el cambio de variables pertinente, transformaremos las desigualdades en igualdades

[pic 11]

Explicación:

Se convierte el lado derecho de la desigualdad en un valor no-negativo antes de convertir las restricciones en igualdad.

• La primera restricción es del tipo ( ≤ ), lo que implica por la regla cuatro de equivalencia agregar una variable de holgura para convertirla en una igualdad (note que el lado derecho de la restricción es no-negativo)
• La segunda restricción ya es una igualdad con el lado derecho no-negativo, por lo que queda igual.
• La tercera restricción es del tipo ( ≥ ) pero el lado derecho es negativo, lo que nos obliga antes de convertirla en igualddad multiplicarla por ( - 1), esto hace que el tipo de desigualdad cambie a ( ≤ ). Es entonces una variable de holgura la que se debe de agregar.

[pic 12]

Proponemos el mismo cambio de variables que se propuso para la forma canónica

[pic 13]

Sustituyendo las variables y escribiendo matricialmente la forma estándar del modelo:

 [pic 14] [pic 15]

[pic 16]

PROCEDIMIENTO DEL MÉTODO SIMPLEX

        Para aplicarlo, el modelo debe estar en forma canónica, y el lado derecho de las restricciones deben de ser valores  no-negativos.

EJEMPLO:

I.-  Forma canónica.

[pic 17]

II.- Estandarizando la forma canónica.

[pic 18]

        Considerar el sistema de ecuaciones lineales pasando todas las variables al lado izquierdo (igualando a cero la unción objetio).

III.-                     [pic 19]

...