Chapter 4.14, Problem 6P

Explanation of Solution

Proof:

In certain linear programming, some variables are allowed to be unrestricted in sign as required for the appropriate formulation of the problem,

In such cases, the simplex algorithm will no longer be valid even though the formulation is appropriate. The reason for the above is that to apply the simplex algorithm, all the variables are required to be non-negative.

Therefore, such unrestricted in sign variable ${\text{x}}_{\text{i}}$ is defined in terms of two variables, ${\text{x}}_{\text{i}}\text{'}$ and ${\text{x}}_{\text{i}}\text{''}$ as given below,

${\text{x}}_{\text{i}}={\text{x}}_{\text{i}}\text{'}-{\text{x}}_{\text{i}}\text{''}$

The sign restriction for each of the variable holds as:

${\text{x}}_{\text{i}}\text{'}\ge 0$ and ${\text{x}}_{\text{i}}\text{''}\ge 0$

The ${\text{x}}_{\text{i}}$ is expressed as the difference of two non-negative variables. So, now the simplex method can be applied.

It is already known that the simplex method generates number of pivots before arriving at an optimal solution. At the end of the solution, the user will either of ${\text{x}}_{\text{i}}>0,{\text{x}}_{\text{i}}<0$ and ${\text{x}}_{\text{i}}=0$

The ${\text{x}}_{\text{i}}$ must follow any one of the three cases for any of the basic solution in any of the pivot. The three cases are given below,

Case 1: When ${\text{x}}_{\text{i}}>0$

As stated above, ${\text{x}}_{\text{i}}={\text{x}}_{\text{i}}\text{'}-{\text{x}}_{\text{i}}\text{''}$. So, the this case is possible if ${\text{x}}_{\text{i}}\text{'}>0$ and ${\text{x}}_{\text{i}}\text{'}\text{'}>0$. That is,

$\begin{array}{c}{\text{x}}_{\text{i}}={\text{x}}_{\text{i}}\text{'}-{\text{x}}_{\text{i}}\text{''}\\ {\text{=x}}_{\text{i}}\text{'}\end{array}$

Case 2: When ${\text{x}}_{\text{i}}<0$

As stated above, ${\text{x}}_{\text{i}}={\text{x}}_{\text{i}}\text{'}-{\text{x}}_{\text{i}}\text{''}$. So, the this case is possible if ${\text{x}}_{\text{i}}\text{'}=0$ and ${\text{x}}_{\text{i}}\text{'}\text{'}>0$