How does the Simplex method of solving LPs use the starting solution?

530 Views Asked by At

Say one looks at the LP (in slack form) and sees that assigning $0$s to all the non-basic variables doesn't give a valid solution but some other non-trivial assignment of values to the non-basic variables does form a valid assignment.

How (or Can) the Simplex method exploit such an observation?

Can you kindly give or link to some such example?

1

There are 1 best solutions below

7
On

If you know a feasible solution, it's easy to either find a basic feasible solution with at least as good objective value, and then start the simplex method from there, or show the problem is unbounded. Namely, if $S$ is the set of variables (including slack variables) with value $0$ in your feasible solution, move from that feasible solution in a direction where the variables in $S$ stay $0$ and the objective increases until some other variable hits $0$. Then add that variable to $S$ and continue.

EDIT

Here's a small example. Suppose you want to maximize $f = x_1 + 2 x_2 + 3 x_3$ subject to $$ \eqalign{ x_1 - x_2 + s_1 &= 3\cr -x_1 + x_3 + s_2 &= 4\cr x_1 + x_2 - x_3 + s_3 &= 1\cr x_1,x_2,x_3,s_1,s_2,s_3 &\ge 0} $$ and you happen to notice that $x_1 = 1, x_2 = 1, x_3 = 1, s_1 = 3, s_2 = 4, s_3 = 0$ is a feasible solution.

The only variable that is $0$ here is $s_3$. Let's move from that solution in a direction where $s_3$ stays $0$. We can take $x_1 = 1 - t$, $x_2 = 1 + t$, $x_3 = 1$ (which keeps $s_3 = 0$), $s_1 = 3 - x_1 + x_2 = 3 + 2 t$, $s_2 = 4 + x_1 - x_3 = 4 - t$, and $f = 6 + t$. Since we want to increase the objective, we let $t$ increase. We find that $x_1$ hits $0$ at $t = 1$. At this point we have $x_1 = 0$, $x_2 = 2$, $x_3 = 1$, $s_1 = 5$, $s_2 = 3$, $s_3 = 0$, $f = 7$.

Now let's try changing $x_2$, keeping $x_1 = 0$ and $s_3 = 0$. The equations (with $x_1 = 0$ and $s_3 = 0$) say $$ \eqalign{ - x_2 + s_1 &= 3\cr x_3 + s_2 &= 4\cr x_2 - x_3 &= 1\cr}$$ so if we take $x_2 = 2 + t$ we'll have $s_1 = 5 + t$, $x_3 = 1+t$, $s_2 = 3-t$ and $f = 7 + 5 t$. So again let $t$ increase and we hit $s_2 = 0$ at $t = 3$. At this point $x_1 = 0$, $x_2 = 5$, $x_3 = 4$, $s_1 = 8$, $s_2 = 0$, $s_3 = 0$ and $f = 22$.

The equations with $x_1 = 0$, $s_2 = 0$ and $s_3 = 0$ don't permit any changes, so our process of improvement has finished. We now rewrite the system so $x_2, x_3, s_1$ are the basic variables and $x_1, s_2, s_3$ are nonbasic (this can be done with a pivot operation where $s_1$ enters the basis and $x_2$ leaves), and start the simplex method from there.