Solving an LP problem with an upper limit for the variables

Question

Im trying to solve the Above LP. Now, can we apply just simplex considering that we can treat the upper bounds of the variables as constraints.

Meaning, we need to add $6$ slack variables, and it would be a bit harder to do the algorithm by hand. Now, the dual will give six variables as well, so it doesnt help much.

In my notes, it says to consider "bounded variable simplex method", but I haven't seen how this method works. how can we apply this method to solve this problem? Is it possible to solve it using the standard primal simplex?

Answer 1

Let's write down our simplex table, remembering our upper bounds for each variables.

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}\hline & x_1 & x_2 & x_3 & x_4 & x_5 & s & -z & RHS & \text{ratio} &UB \\ \hline -z & -2 & -4 & \color{blue}{-7} & -1 & -5 & 0 & 1 & 0 & - & - \\ \hline s & 3 & 5 & 11 & 2 & 7 & 1 & 0 & 10 & \frac{10}{11} & 1 \\ \hline \end{array}

At the beginning, we are at $(x_1,x_2,x_3,x_4,x_5)=(0,0,0,0,0)$. The entering variable would be $x_3$. since the minimum ratio is less than the upper bound, we will do a regular simplex pivot updating.

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}\hline & x_1 & x_2 & x_3 & x_4 & x_5 & s & -z & RHS & \text{ratio} &UB \\ \hline -z & -\frac1{11} & \color{blue}{-\frac9{11}} & 0 & \frac3{11} & -\frac6{11} & \frac7{11} & 1 & \frac{70}{11} & - & - \\ \hline x_3 & \frac3{11} & \frac5{11} & 1 & \frac2{11} & \frac7{11} & \frac1{11} & 0 & \frac{10}{11} & 2 & 1 \\ \hline \end{array}

Upon doing the simplex update, we reach $(0,0,\frac{10}{11},0,0)$. Our next entering variable is $x_2$. The difference from the previous step this time is the ratio is more than the upper bound. We will increment the $x_2$ by the upperbound amount, which is $1$. We will also update the RHS and mark $x_2$ as $\bar{x}_2$ to indicate that it is now non-basic.

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}\hline & x_1 & \bar{x}_2 & x_3 & x_4 & x_5 & s & -z & RHS & \text{ratio} &UB \\ \hline -z & -\frac1{11} & -\frac9{11} & 0 & \frac3{11} & \color{blue}{-\frac6{11}} & \frac7{11} & 1 & \frac{79}{11} & - & - \\ \hline x_3 & \frac3{11} & \frac5{11} & 1 & \frac2{11} & \frac7{11} & \frac1{11} & 0 & \frac{5}{11} & \frac57 & 1 \\ \hline \end{array}

Now, we arrive at $(0,1,\frac5{11},0,0)$. Our next entering variable is $x_5$, since the ratio is less than the upper bound, we do a regular simplex pivot updating.

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}\hline & x_1 & \bar{x}_2 & x_3 & x_4 & x_5 & s & -z & RHS & \text{ratio} &UB \\ \hline -z & \frac1{7} & -\frac3{7} & \frac67 & \frac3{7} & 0 & \frac5{7} & 1 & \frac{53}{7} & - & - \\ \hline x_5 & \frac3{7} & \frac5{7} & \frac{11}7 & \frac2{7} & 1 & \frac1{7} & 0 & \frac{5}{7} & - & - \\ \hline \end{array}

Now, we arrive at $(0,1,0,0,\frac57)$. Upon checking the reduced cost, we can see that we are optimal with objective value $\frac{53}{7}$.

R code to check the final solution:

> library(lpSolve)
> f.obj <- c(2,4,7,1,5)
> n = length(f.obj)
> f.con <- rbind(c(3,5,11,2,7), diag(n), -diag(n))
> f.dir <- rep('<=',2 * n+1 )
> f.rhs <- c(10,rep(1,n),rep(0,n))
> optimum <- lp(direction = "max", objective.in = f.obj, const.mat = f.con, const.dir = f.dir, const.rhs = f.rhs)
> optimum
Success: the objective function is 7.571429 
> optimum$solution
[1] 0.0000000 1.0000000 0.0000000 0.0000000 0.7142857