Handling Upper Bounds in Simplex

John Mitchell

Consider the linear programming problem

\begin{displaymath}
\begin{array}{lrrcrcl}
\min &&& c^Tx \\
\mbox{subject to} &&& Ax &=& b \\
&0 & \leq & x &\leq & u
\end{array}\end{displaymath}

Could introduce slack variables s to get standard form:

\begin{displaymath}
\begin{array}{lrrcrcl}
\min & c^Tx \\
\mbox{subject to} ...
...s & = & u \\
& \multicolumn{3}{r}{x,s} &\geq & 0
\end{array}\end{displaymath}

Instead, modify the pivot rules and work with the original tableau.

A variable can be nonbasic at either its lower bound or its upper bound.

If it is at its upper bound, it can enter the basis if its reduced cost is positive. The variable will be decreased.

in the minimum ratio test, ensure that no variable exceeds its upper bound.

Example


\begin{displaymath}
\begin{array}{lrcrcrcrcl}
\min &&&& - & 2x_3 & - & 3x_4 \\
...
... x_3 & \leq & 5 \\
&&&&& 0 & \leq & x_4 & \leq & 1
\end{array}\end{displaymath}

Have basic feasible solution:

Nonbasics:
x3=0, x4=1
Basics:
x1=3, x2=3. Note how x4 impacts these values.

Since x4 is at its upper bound and has a negative reduced cost, we don't bring x4 into the basis. Instead, x3 enters the basis.

Calculate the simplex direction:
We are increasing x3, so the changes in the basic variables are given by the negatives of the entries in the x3 column of the tableau. Direction is

\begin{displaymath}
\Delta x = (-1,1,1,0)
\end{displaymath}

Minimum Ratio Test

Taking a step of length t in the simplex direction gives a new point:

\begin{displaymath}
\left[ \begin{array}{r}x_1\\ x_2\\ x_3\\ x_4 \end{array}\rig...
...t]
+
t \left[ \begin{array}{r}-1\\ 1\\ 1\\ 0\end{array}\right]
\end{displaymath}

Need to keep x within its bounds.

x1 is decreasing. Need $t \leq 3$ to keep $x_1 \geq 0$.

x2 is increasing. Need $t \leq 1$ to keep $x_2 \leq 4$.

x3 is increasing. Need $t \leq 5$ to keep $x_3 \leq 5$.

So choose t=1. x2 leaves the basis at its upper bound.

Tableaus

1.

\begin{displaymath}
\begin{array}{l\vert r\vert rrrr\vert lrr}
\multicolumn{3}{r...
...ox{Values}} & 3 & 3 & 0 & \multicolumn{1}{r}{1} \\
\end{array}\end{displaymath}

Initial value of objective is z=0-3(1)=-3.

x3 enters the basis. By the minimum ratio test, x2 leaves the basis at its upper bound.

2.

\begin{displaymath}
\begin{array}{l\vert r\vert rrrr\vert lrr}
\multicolumn{3}{r...
...ox{Values}} & 2 & 4 & 1 & \multicolumn{1}{r}{1} \\
\end{array}\end{displaymath}

Value of objective is z=2-2(4)-1(1)=-5.

x4 enters the basis and decreases. Thus, x1 decreases and x3 increases.

The value of the minimum ratio for the basic variables is 2.

The incoming basic variable also provides an upper bound on the maximum possible step length. Since we require $x_4 \geq 0$, the step length must be $\leq 1$.

Thus, the pivot is to keep x4 nonbasic, but switch it from being nonbasic at its upper bound to nonbasic at its lower bound.

3.

\begin{displaymath}
\begin{array}{l\vert r\vert rrrr\vert lrr}
\multicolumn{3}{r...
...ox{Values}} & 1 & 4 & 3 & \multicolumn{1}{r}{0} \\
\end{array}\end{displaymath}

This tableau is in optimal form.

Optimal value of objective is z=2-2(4)=-6.

x2 is at its upper bound, and decreasing x2 will increase the objective function value.

x4 is at its lower bound, and increasing x4 will increase the objective function value.



 
John E. Mitchell
2004-10-01