Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

To quote my Linear Programming textbook,

One way of getting around [the obstacles that arise when an LPP has an infeasible origin] uses a so-called auxiliary problem,

$\min x_0$
subject to $\sum_{j=1}^na_{ij}x_j-x_0\leq b_i\quad(i=1,2,\dots,m)$
$\quad\quad\quad\quad\quad\quad x_j\geq 0\quad (j=0,1,\dots,n)$

[...] It is easy to see that the original problem has a feasible solution if and only if the auxiliary problem has a feasible solution with $x_0=0$.

Bold mine.

That is not easy for me to see. I can follow how to do it and I can do it on my own, but I don't quite see why that if-and-only-if relationship holds. Can anyone help shed light?

share|improve this question
add comment

1 Answer 1

up vote 3 down vote accepted

The question in the body of your post differs slightly from the question in the title. The question in the body is concerned only with why the existence of a feasible solution to one of the two problems implies the existence of a particular feasible solution to the other problem. A feasible solution is, of course, simply a point that satisfies all the constraints. The question in the title is concerned with a systematic method for finding a basic feasible solution to use as a starting point for the simplex method. Answering this is slightly more involved, since it requires explaining how that solution is actually obtained. Note that the objective function of the original problem has nothing to do with either of these questions since they are concerned only with the satisfaction of constraints.

The statement in the body of your post,

It is easy to see that the original problem has a feasible solution if and only if the auxiliary problem has a feasible solution with $x_0=0$.

can be changed to

It is easy to see that the original problem has a feasible solution if and only if the auxiliary problem has an optimal solution with $x_0=0$.

since, if the constraint $x_0\ge0$ must be satisfied, then $x_0=0$ certainly minimizes the objective function $x_0$. The point of introducing the auxiliary problem is that there is a systematic method for finding a basic feasible solution to it: choose $x_0=\max(\{-b_i\mid 1\le i\le m\})$ and $x_j=0$, $1\le j\le n$. (Since we are assuming the origin to be infeasible, at least one of the $b_i$ must be negative, so $x_0$ will be positive.) Essentially what we have done is to increase the dimensionality of the problem by $1$ (from $n$ to $n+1$) in order to make it easier to find a starting solution. The simplex method will now give an the optimal solution to the auxiliary problem, which we know will have $x_0=0$. Assuming the quoted statement, we can drop $x_0$ to get a basic feasible solution to the original problem. This addresses the question in your title since we can always get a starting solution by this method. Using this solution, the simplex method will now produce a feasible solution that maximizes the original objective function (if such a solution exists).

To prove the quoted statement, you need to do two things: (1) show that a feasible solution to the auxiliary problem of the form $(x_0,x_1,x_2,\ldots,x_n)=(0,a_1,a_2,\ldots,a_n)$ has the property that $(a_1,a_2,\ldots,a_n)$ is a feasible solution to the original problem, and (2) show that any feasible solution $(a_1,a_2,\ldots,a_n)$ to the original problem can be used to create a feasible solution $(0,a_1,a_2,\ldots,a_n)$ to the auxiliary problem. Notice that $x_0=0$ satisfies the constraint $x_0\ge0$ in the auxiliary problem, so we only have to think about the remaining constraints. The key is that the remaining constraints of the auxiliary problem reduce to the constraints of the original problem when $x_0$ is set to $0$.

In greater detail: goal (1) is accomplished by assuming that $(0,a_1,a_2,\ldots,a_n)$ is a feasible solution to the auxiliary problem. If this solution is plugged into the auxiliary constraints, all terms involving $x_0$ are $0$, and we see that $(a_1,a_2,\ldots,a_n)$ satisfies the constraints of the original problem, and is therefore a feasible solution to the original problem.

Goal (2) is accomplished by assuming that $(a_1,a_2,\ldots,a_n)$ is a feasible solution to the original problem, which means that it satisfies all of the inequalities of the original problem. Trying $(0,a_1,a_2,\ldots,a_n)$ in the constraints of the auxiliary problem, we again see that the $x_0$ terms drop out, reducing them to the constraints of the original problem. Since $(a_1,a_2,\ldots,a_n)$ was assumed feasible for the original problem, these constraints hold.

share|improve this answer
    
Thanks very much, that cleared it up completely –  crf May 26 '12 at 20:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.