3
$\begingroup$

A proof from An Introduction to Optimization By Edwin Chong and Zak

Theorem 15.1 Fundamental Theorem of LPP. Consider a linear program in standard form.

  1. If there exists a feasible solution, then there exists a basic feasible solution;
  2. If there exists an optimal feasible solution, then there exists an optimal basic feasible solution.

    Proof. We first prove part 1. Suppose that $x = [x_1,..., x_n]^T$ is a feasible solution and it has $p$ positive components. Without loss of generality, we can assume that the first $p$ components are positive, whereas the remaining components are zero. Then, in terms of the columns of $A = [a_1,..., a_p, . . . , a_n]$ this solution satisfies

    $x_1a_1+...x_pa_p=b$.

There are now two cases to consider.

Case 1: If $a_1, a_2,..., a_p$ are linearly independent, then $p \leq m$. If $p = m$, then the solution $x$ is basic and the proof is completed. If, on the other hand, $p < m$, then, since $rank A = m$, we can find $m—p$ columns of A from the remaining $n — p$ columns so that the resulting set of m columns forms a basis. Hence, the solution $x$ is a (degenerate) basic feasible solution corresponding to the above basis.

Case 2: Assume that $a_1, a_2,..., a_p$ are linearly dependent. Then, there exist numbers $y_i, i = 1, . . . , p $ not all zero, such that $y_1a_1+..y_pa_p=0$

We can assume that there exists at least one $y_i$ that is positive, for if all the $y_i$ are nonpositive, we can multiply the above equation by $-1$. Multiply the above equation by a scalar $\epsilon$ and subtract the resulting equation from $x_1a_1+...x_pa_p=b$ to obtain $(x_1-\epsilon y_1)a_1+....+(x_p-\epsilon y_p)a_p=b$

Let $y=[y_1,..y_p,0,..0]^T$.then Then, for any $\epsilon$

we can write $A[x-\epsilon y]=b$

Let $\epsilon$ = min{$xi/yi : i = 1,..., p, yi > 0$}. Then, the first $p$ components o f $x — \epsilon y$ are nonnegative, and at least one of these components is zero. We then have a feasible solution with at most $p — 1$ positive components. We can repeat this process until we get linearly independent columns of A, after which we are back to Case 1. Therefore, part 1 is proved.

We now prove part 2. Suppose that $x = [ x_1 , . . . , x_n]^T$ is an optimal feasible solution, and only the first $p$ variables are nonzero. Then, we have two cases to consider. The first case (Case 1) is exactly the same as in part 1. The second case (Case 2) follows the same arguments as in part 1, but in addition we must show that $x — \epsilon y$ is optimal for any $\epsilon$. We do this by showing that $c^Ty = 0$. To this end, assume $c^Ty \neq 0$. Note that for $\epsilon$ of sufficiently small magnitude ($|\epsilon|$ $ \leq$ min{$|\frac{x_i}{y_i}| : i = 1,... ,p, y_i > 0$}), the vector$x — \epsilon y$ is feasible. We can choose $\epsilon$ such that $c^Tx> c^Tx — \epsilon c^Ty =c^T(x-\epsilon y)$. This contradicts the optimality of x . We can now use the procedure from part 1 to obtain an optimal basic feasible solution from a given optimal feasible solution.

My question is for second part, how they defined the range for $\epsilon$ that $|\epsilon|$ $ \leq$ min{$|\frac{x_i}{y_i}| : i = 1,... ,p, y_i > 0$}.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.