SIMPLEX
DEGENERATIVO
UNIVERSIDAD NACIONAL FEDERICO
VILLARREAL
FACULTAD DE INGENIERIA INDUSTRIAL Y SISTEMAS
DOCENTE:
[Link] ALVARADO, JOSE.
INTEGRANTES:
-
ALEJANDRO SOPLINI, ERICK ABEL.
ABANTO ECHEGARAY, RONALD.
CRUZ ESTEBAN, ALEX.
CICLO / AULA:
TERCERO / A4-3
ndice
INTRODUCCION:............................................................................................. 3
1) MARCO TEORICO:....................................................................................... 4
1.1) DEGENERACION:.................................................................................. 4
1.2) CICLAJE:............................................................................................... 4
1.3) METODO DE PERTURBACION DE DANTZING.........................................4
1.4) METODO DE BLAND............................................................................. 4
2) MARCO PRCTICO:..................................................................................... 5
2.1) APLICACIN DEL MTODO DE PERTURBACIONES DE DANTZIG............5
2.2) APLICACIN DEL MTODO DE BLAND..................................................7
3) CONCLUSIONES........................................................................................ 9
4) RECOMENDACIONES................................................................................ 9
5) BIBLIOGRAFIA........................................................................................... 9
6) ANEXOS.................................................................................................... 9
INTRODUCCION:
Lo que trataremos a continuacin sern mtodos de resolucin en el caso
que se d un simplex degenerativo o un caso de ciclaje para poder romper
el ciclo creado y saber que variable de salida se ha de escoger , los cuales
se explicaran es las siguientes hojas.
1) MARCO TEORICO:
1.1) DEGENERACION: la degeneracin se da cuando una variable bsica
es cero y al mismo tiempo hay un empate cuando hay que determinar la
variable que sale.
1.2) CICLAJE: repeticin indefinida de la misma secuencia de bases.
Para poder evitar el ciclaje se pueden usar distintos mtodos como los:
Bland
Simplex generalizado
Dantzing
Los cuales se ver a continuacin
1.3) METODO DE PERTURBACION DE DANTZING
Gracias a este mtodo podemos evitar el fenmeno de ciclaje, haciendo una
eleccin adecuada de la variable de salida.
En primera instancia tenemos que elegir la variable bsica de entrada la
cual se seguir la siguiente indicacin:
Se selecciona aquella variable que tiene mayor costo reducido, lo cual se
puede ver en la funcin objetivo en la que elegiremos aquella variable que
nos d ms utilidad o en palabras simple aquella variable que tenga el
coeficiente ms alto no negativo y en caso tengan iguales coeficientes se
elegir a aquella con el ndice ms pequeo.
La cual llamaremos Xk.
Luego se selecciona la variable de salida de la siguiente manera:
Donde se comenzara por la menor i.
( X B )r ( X B) i
=
, ( X K ) i>0 , 1 i m.
( X k ) r ( X k) i
Si no hay empate en la variable de salida,
( X B) r
sale. De lo contrario se
sigue los siguientes pasos:
( XJ ) r ( X J ) i
=
, j k ,i S 0 .
( Xk ) r ( Xk ) i
Se elegir a aquella variable que d como resultado el mayor nmero ya sea
negativo o positivo.
Y as sucesivamente hasta encontrar una sola variable de salida.
1.4) METODO DE BLAND
La regla de Bland consiste en elegir las variables entrantes y salientes que
tengan el menor ndice, entre las candidatas. Para esta regla simple se sigue
el siguiente algoritmo.
Teorema de Robert G. Bland: Si en cada iteracin del cuadro de smplex se
selecciona la variable entrante como aquella de menor ndice entre las que
tenga menor ndice entres aquellas que tienen costo reducido positivo, y la
variable saliente de menor ndice entre las que logran el mnimo en la
prueba del cociente, entonces el algoritmo termina, pero sino se sigue con
el procedimiento conocido.
=min { i/ Xi , 1 i m }
2) MARCO PRCTICO:
2.1) APLICACIN
DANTZIG.
DEL
MTODO
DE
PERTURBACIONES
DE
Para el caso de la aplicacin del mtodo de perturbacin de dantzig
usaremos el siguiente problema
Minimizar:
3
1
x 0= x 120 x2 + x 36 x 4
4
2
Sujeto a:
1
x 8 x2 x3 +9 x 4 0
4 1
1
1
x 12 x 2 x + 3 x 4 0
2 1
2 3
x3 1
x j 0, j=1,2,3,4
Pasos:
1) Transformar a formato estndar.
Minimizar:
Sujeto a:
3
1
x 0= x 120 x2 + x 36 x 4 +0 x 5 +0 x 6+ 0 x 7
4
2
1
x 8 x2 x3 +9 x 4 + x 5=0
4 1
1
1
x1 12 x 2 x + 3 x 4 + x 6 =0
2
2 3
x 3+ x 7 =1
x j 0, j=1,2,3,4,5,6,7
2) Tabular para poder usar el mtodo simplex.
1ra TABLA.
Cj
Ck
0
0
Xk
X5
X6
0 X7
Zk
Zk-CJ
Bk
0
0
1
0
3/4
X1
1/4
1/2
-20
X2
-8
-12
0
0
3/4
0
0
-20
1/2
X3
-1
1/2
1
0
1/2
-6
X4
9
3
0
X5
1
0
0
X6
0
1
0
X7
0
0
0
0
6
0
0
0
0
0
0
1
0
0
al escoger
de salida nos da el siguiente resultado:
Vemos que
la variable
X1=0 en x5
X1=0 en x6
X1= no definido en x7
Por lo que vemos un empate entre las variables de salida x 5 y x6 para
poder decidir por cual optaremos usaremos el mtodo de
perturbaciones de Dantzig.
Entonces
s 0= { x 5 , x6 } , por tanto
Para x5
x 2 8
=
=32
x 1 1/4
Para x6
x 2 12
=
=24
x 1 1/2
Entonces segn el mtodo tenemos que escoger el mayor nmero ya
sea positivo o negativo.
Se
la x6
2da
Cj
Ck
0
3/
4
0
Zk
Zk-CJ
Xk
X5
Bk
0
3/4
X1
0
-20
X2
-2
X1
-24
X7
1
0
0
3/4
0
-18
1/2
X3
3/4
-1
-6
X4
15/
2
6
0
X5
1
0
X6
0
0
X7
0
1
3/4
1/4
0
9/2
0
0
0
3/2
1
0
21/
2
3/2
selecciona
por
esa
razn.
TABLA.
Para x5
x5
0
=
=0
x 3 3 /4
Para x1
x1 0
= =0
x 3 1
Para x7
x7 1
= =1
x3 1
Se escoger a x7 como variable de salida.
3ra TABLA.
Cj
Ck
0
0
X5
1
0
X6
0
0
X7
3/4
-6
X4
15/
2
6
3/4
-18
1/2
9/2
3/2
5/4
21/ 0
3/2
2
que
encontramos el valor mnimo de x0 el cual es
5/4
3/
4
1/
2
Zk
Xk Bk
X5 0
3/4
X1
0
-20
X2
-2
1/2
X3
0
X1 0
-24
X3 1
Zk-CJ
1/
2
2.2) APLICACIN DEL MTODO DE BLAND.
Maximizar: Z
Sujeto a:
x 1+ 4 x 2 8
x 1+2 x 2 4
3 x1 +9 x 2
Como
se
puede
apreciar
Cambio a formato estndar:
Maximizar:
Z =3 x 1 +9 x 2+ 0 x 3 +0 x 4
Sujeto a:
x 1+ 4 x 2+ x3 =8
Aplicando el mtodo Smplex:
Por lo tanto el Z. ptimo es 18.
3)CONCLUSIONES
-
una apropiada seleccin de la variable de salida nos ayuda a usar
un mnimo de procesos para el resultado ptimo.
Alejandro Soplini, Erick
Abel
Cuando desarrollamos un problema por el mtodo simplex y vemos
que es degenerativo, no necesariamente es de ciclaje.
Cruz Esteban, Alex Alcides
Existen dos formas bsicas de resolver un problema con
degeneracin, la del mtodo de perturbacin y la del mtodo de
Bland. En cualquiera de estas, se puede llegar a la conclusin que
el Z ptimo solo sea una solucin bsica factible (SBF).
Abanto Echegaray, Ronald
4)RECOMENDACIONES
-
lo primero es ver si es degenerativa o no en caso lo sea usar el
mtodo de Dantzig para prevenir el ciclaje y ahorrarnos tiempo y
Alejandro Soplini, Erick
procesos.
Abel
Al encontrarnos con un simplex degenerativo, debemos usar
mtodos que los hacen ms fciles de resolverla.
Cruz Esteban, Alex Alcides
Al desarrollar un problema de programacin lineal, tenemos que
percatarnos que si el problema se desarrolla de una manera
sencilla, ya no hay necesidad de aplicar los mtodos mencionados.
Abanto Echegaray, Ronald
5)BIBLIOGRAFIA
6)ANEXOS
-
Daniel A. Labrecciosa Miralles.2009. Estudio de Tecnicas Aplicadas
en la Implementacin del Mtodo Simplex. Proyecto de Grado
[Link]
[Link]
ml/Capitulo%20III/[Link]
[Link]
OperChave/DOCUMENTOS/Unidad4/[Link]
[Link]
mLineal1_6.pdf
[Link]
[Link]
inf_gestion/io/doc_col_grupo1/archivos/[Link]
[Link]
