Investigación De Operaciones

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 paradesarrollar el procedimiento general para solución de cualquier problema de programación lineal.

I) Forma canónica.
Max Z = CX
s.a. AX ( b
X ( 0

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 puedeexpresar matricialmente.
NOTA: Si al menos una no se cumple no es forma canónica.

II) Forma estándar.

Max
ó ( Z = CX
Min
s.a. AX = b
X ( 0

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 modeloprimero 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 programación lineal, cumple:
Max Z = - Min (-Z), o bien Min Z = - Max (-Z)

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


2. Toda desigualdad invierte su sentido si se multiplica por (- 1).
sea: aX ( b ( - aX ( - b ; ó aX ( b ( - aX ( - b

Ejemplo: 4 < 10 ( -4 > -10


3. Toda ecuación pude expresarse como un sistema de 2desigualdades 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


4. 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 unaigualdad 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


5. 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.

Min Z = -X1 + 2X2 + X3
s.a....