Algoritmo simplex

CLASES DE METODO GENERALIZADO DEL ALGORITMO SIMPLEX
Jorge Beyer

Max Z = C1 X + C2 X2 + .............. + Cn Xn
s.a :
a11 X1 + a12 X2 + ............... + a1n Xn ≤ b1

a21 X1 + a22 X2 + ............. + a2n Xn ≤ b2
. . . . . . . . . . . . . . .. . .
am1 X1 + am2 X2 + .............. + amn Xn ≤ bm

Xj  0 , j

Podemos escribir como:

a11 X1 + a12 X2 + ............... + a1n Xn ≤ b1

a21 X1 + a22 X2 + ............. + a2n Xn ≤ b2
. . . . . . . . . . . . . . . . . .
am1 X1 + am2 X2 +.............. + amn Xn ≤ bm

Z = C1 X + C2 X2 + .......... + Cn Xn

Si agregamos las variables de holguras

a11 X1 + a12 X2 + .......................... + a1n Xn + a1,n+1 Xn+1 = b1

a21 X1 + a22 X2 + ......................... + a2n Xn + a2,n+1 Xn+2 = b2

- - . .. . . . . . . . . 1

am1 X1 + am2 X2 + ....................... + amn Xn + am,n+m Xn+m = bm

Z = C1 X1 + C2 X2 +…+ Cn Xn + Cn+1 Xn+1+ Cn+2 X n+2 +… + Cn+m Xn+m

Esta forma la podemos ordenar y reescribir diferenciando una solución básica.Renumerando las variables y coeficientes del sistema de ecuaciones.

Luego:

X1 + a1,m+1 Xm+1 + a1,m+2 Xm+2 + ……..+ a1,n Xn = b1

X2 + a2,m+1 Xm+1 + a2,m+2 Xm+2 + ……..+ a2,n Xn = b2

. . . . . . . . .. .
2
Xm + am,m+1 Xm+1 + am,m+2 Xm+2 + ……..+ am,n Xn = bm
m m m
-Z + ( Cm+1 - ∑ Ci ai,m+1) Xm+1 +…+ ( Cn - ∑Ci ain) X n= - ∑ Ci bi
i=1 i=1 i=1
esta forma ofrece la ventaja que si hacemos :

Xm+1 + Xm+2 + ……..+ Xn = 0, se tiene una solución básica, pero no la óptima, luego debemos encontrar otra base mejor. Para pasar de la forma 1 a la 2 necesitamos un algoritmo que nos permitahacer cambios de base. Una de ellos, es el llamado “Algoritmo de Pivoteamiento”. Este consiste en los siguientes pasos:

1.- Seleccionar un término ars Xs en el sistema 1 talque ars ≠ 0, al cual lo llamaremos pivote.

2.- Sustituir la r-ésima ecuación por ella misma, pero multiplicada por (1/ars), lo que produce el coeficiente unitario (pivote) que estamos buscando.

3.-Para cada i en [1,m], sustituir la i-ésima ecuación por la suma de la misma con la r-ésima ecuación, ya modificada, pero ahora multiplicada por (-ais). Esto crea los ceros en los coeficientes ais en las restantes ecuaciones con variables Xs.

De esta forma se itera pasando de una base inicial a otra mejor, en el proceso de optimización de la solución.

Luego, pasar del sistema 1 al 2 es fácil,dado que solo se realizan operaciones de líneas entre ellas.

Entonces, haciendo las variables no básicas (Xm+1  Xn) igual a ceros, excepto una de ellas, como por ejemplo Xj = positiva.

Analizaremos primeramente lo concerniente a la factibilidad.

El sistema con todas las variables (Xm+1  Xn), excepto Xj, será:

X1 = b1 - a1j Xj

X2 = b2 - a2j Xj
. . . . . . .´...