Csdrhrt

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?

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