algorithmlinear-programmingsimplex

simplex algorithm shifting origin in linear programming


I am reading linear programming using simplex algorithm in Algorithms book Sanjoy Das Gupta.

text snippet

I am having difficulty in understanding about origin is shifted and equations are changing. For example if origin is shifted from (0,0) to (0, 3). Here i can understand that if point is (x1, x2) in (0,0) origin, then the same point is (x1-0, x2-3) at new origin. Here i am having confusion what is yi's pointing is it x1-0 = y1 and x2-3= y2. I am not getting how author got y1 - x1 and y2 - 3+ x1-x2 in below initial phase step ate end. Request to please explain.

enter image description here


Solution

  • Seems like a bad scan. I think that should read y1 = x1 and y2 = 3 + x1 − x2. The latter equation means that y2 is zero if and only if −x1 + x2 = 3 (i.e., constraint ③ is tight). Going between the two versions of the LP is just linear algebra.

    (TBH, I find this algebraic reasoning about the simplex method to be somewhat perplexing and prefer the geometric view of rolling a marble in a high-dimensional polytope.)