|
|
Re: Go from any vertex to any other vertex in one Simplex method pivot.
Posted:
Jan 20, 2013 9:53 AM
|
|
"analyst41@hotmail.com" <analyst41@hotmail.com> writes:
>Consider the LP
>
>Max Z =3D x1 + x2
>
>such that
>
>0<=3Dx1 <=3D1
>0<=3Dx2 <=3D 1.
>
>If you start from (Z,x1,x2) =3D (0,0,0) to go the optimum (Z,x1,x2) =3D
>(2,1,1) you need two pivots, because you can't go 'through" the unit
>square under the Simplex method.
>
>If you do the variable transformation
>
> y1 =3D x1 +x2
> y2 =3D x1 =96 x2
>
> x1 =3D (y1 + y2)/2
> x2 =3D (y1 =96 y2)/2
>
>The LP becomes
>
>Max Z =3D y1
>
>Such that
>
>0<=3D y1+y2 <=3D 2
>0 <=3D (y1 =96 y2)<=3D 2
>
>After introduing slack variables t1,t2,s1,s2, we get
>
>Z -y1 =3D 0
> t1 - y1 - y2 =3D 0
> s1 + y1 + y2 =3D 2
> t2 - y1 + y2 =3D 0
> s2 + y1 - y2 =3D 2
>
>The BFS corresponding to this table
>
>(Z,t1,t2,s1,s2,y1,y2) =3D (0,0,0,2,2,0,0) corresponds to (Z,x1,x2) =3D
>(0,0,0) in the original LP.
>
>Now a single pivot on y1 in row 3 produces the optimal table
>
>Z +s1 +y2 =3D 2
> t1 +s1 =3D 2
> s1 +y1 +y2 =3D 2
> t2 +s1 +2y2 =3D 2
> -s1 + s2 -2y2 =3D 0
>
>The BFS corresponding to this table
>
>(Z,t1,t2,s1,s2,y1,y2) =3D (2,2,2,0,0,2,0) corresponds to (Z,x1,x2) =3D
>( 2,1,1) in the original LP.
>
>Thus, the optimum is reached in one pivot.
>
>Any ideas to generalize to n dimensions would be appreciated.
based on the dual variables you could do _in the original problem!_
what is known as ''multiple inactivation'' in NLP. Indeed, change of the basis
consists in 'inacvtivating' one constraint (outgoing variable) and immediately
activating a newly active constraint (the incoming variable).
In the usual LP, going from one vertex to the next results in a rank one update
of the basis matrix (and/or its inverse). If you do multiple inactivating,
a corresponding multiple rank update must be done, and little is won.
also, with multpiple inactivation, the next point is not necessarily a vertex
hence you get a considerable different algorithm.
this might be the reason that no one considers this in current software.
hth
peter
|
|
