Metodo simplex
Páginas: 2 (463 palabras)
Publicado: 23 de marzo de 2012
EL METODO SIMPLEX:
La idea general del método Simplex es comenzar en un punto extremo y desplazarse hacia un punto extremo adyacente con el objeto de mejorar el valor de la función objetivo,manteniendo la factibilidad. La manera más sencilla de seleccionar un punto extremo inicial es usar la base B constituida por variables de holgura y/o artificiales. De esta forma la base B inicial esla matriz identidad I que obviamente es una base. Los puntos extremos adyacentes se determinan intercambiando un vector de B con un vector no básico que moverá la solución hacia la optimalidad.
TablaSimplex en forma matricial
Expresemos el programa lineal en forma matricial:
Max z = CX
Sujeto a: (AI)X = b
X >= 0
Subdividamos el vector X en XI y XII, entonces el problema estándar sepuede escribir de la siguiente manera: (I)
1 -CI -CII z 0
0 A I XI = B
XII
En una iteración cualquiera, sea XB La representación de las variables básicas yB su base asociada,entonces XB representa a m elementos de X y B representa los vectores de (AI) correspondientes a XB, y sea CB el vector de elementos de C asociado a XB.
Entonces:
B XB = b y z = CBXB
o bien:
1 -CBz = 0
0 B XB B
La solución se puede expresar:
Z = 1 CBB-1 0 = CBB-1b
XB 0 B-1 B B-1b
Por lo tanto, aplicando este resultado, premultiplicando a (I) se obtiene
1 CBB-1 1 -CI -CIIZ CBB-1b
0 B-1 0 A I XI = B-1b
XII
Esta ecuación matricial se resuelve mediante la iteración simplex general (II):
Básica XI XII Solución
Z CBB-1A-CI CBB-1-CII CBB-1b
XB B-1AB-1 B-1b
Esta tabla muestra los detalles del cálculo del método simplex, es decir, si se conoce B se puede encontrar en cada paso B-1, por lo tanto XB y z.
Por ejemplo consideremos el métodosimplex con variables de holgura, en este caso, CII = 0 la solución básica inicial se identifica como:
XB = XII, CB = CII = 0, B = I, B-1 = I
Sustituyendo en (II) se obtiene el método simplex...
La idea general del método Simplex es comenzar en un punto extremo y desplazarse hacia un punto extremo adyacente con el objeto de mejorar el valor de la función objetivo,manteniendo la factibilidad. La manera más sencilla de seleccionar un punto extremo inicial es usar la base B constituida por variables de holgura y/o artificiales. De esta forma la base B inicial esla matriz identidad I que obviamente es una base. Los puntos extremos adyacentes se determinan intercambiando un vector de B con un vector no básico que moverá la solución hacia la optimalidad.
TablaSimplex en forma matricial
Expresemos el programa lineal en forma matricial:
Max z = CX
Sujeto a: (AI)X = b
X >= 0
Subdividamos el vector X en XI y XII, entonces el problema estándar sepuede escribir de la siguiente manera: (I)
1 -CI -CII z 0
0 A I XI = B
XII
En una iteración cualquiera, sea XB La representación de las variables básicas yB su base asociada,entonces XB representa a m elementos de X y B representa los vectores de (AI) correspondientes a XB, y sea CB el vector de elementos de C asociado a XB.
Entonces:
B XB = b y z = CBXB
o bien:
1 -CBz = 0
0 B XB B
La solución se puede expresar:
Z = 1 CBB-1 0 = CBB-1b
XB 0 B-1 B B-1b
Por lo tanto, aplicando este resultado, premultiplicando a (I) se obtiene
1 CBB-1 1 -CI -CIIZ CBB-1b
0 B-1 0 A I XI = B-1b
XII
Esta ecuación matricial se resuelve mediante la iteración simplex general (II):
Básica XI XII Solución
Z CBB-1A-CI CBB-1-CII CBB-1b
XB B-1AB-1 B-1b
Esta tabla muestra los detalles del cálculo del método simplex, es decir, si se conoce B se puede encontrar en cada paso B-1, por lo tanto XB y z.
Por ejemplo consideremos el métodosimplex con variables de holgura, en este caso, CII = 0 la solución básica inicial se identifica como:
XB = XII, CB = CII = 0, B = I, B-1 = I
Sustituyendo en (II) se obtiene el método simplex...
Leer documento completo
Regístrate para leer el documento completo.