Solve simplex problem with $x_1 + x_2 + x_3 + x_4 =1$ as restriction

computer sciencelinear programmingoptimizationsimplex

So, there's this problem:

maximize

$$6x_1 + 8x_2 + 5x_3 + 9x_4$$

subject to

$$x_1+x_2+x_3+x_4 = 1 \;\text{ knowing that }\;
x_1, x_2, x_3, x_4\geq0$$

The solution is obvious: since the sum of all variables must be 1, $x_4 = 1$ gives the highest value to the objective function

BUT
the simplex method goes wrong when I use it. There's a negative value on the axuliary equations, which means it is an infeasible dictionary, therefore I should use two phases method. But this one goes wrong as well, as there are too many variables to replace the original objective function with slack variables.

But the problem HAS a solution, it's obvious, I just can't find it through simplex method.
Can anyone help me?

Here's how the 2 phases method gave:

first dictionary:

\begin{align*} z&= -x_0\\
w_1 &= 1 -x_1 -x_2 -x_3 -x_4 +x_0\\
w_2 &= -1 +x_1 +x_2 +x_3 +x_4 +x_0
\end{align*}

second dictionary:

\begin{align*} z&= -1 +x_1 +x_2 +x_3 +x_4 -w_2\\
w_1 &= 2 -2x_1 -2x_2 -2x_3 -2x_4 +w_2\\
x_0 &= 1 -x_1 -x_2 -x_3 -x_4 +w_2
\end{align*}

third dictionary:

\begin{align*} z&= -w_1 -w_2\\
x_1 &= 1 -x_2 -x_3 -x_4 +\frac{w_2}{2} – \frac{w_1}{2}\\
x_0 &= \frac{w_1}{2} +\frac{w_2}{2}
\end{align*}

this is supposed to be optimal but there's no way I'll be able to convert $6x_1 + 8x_2 + 5x_3 + 9x_4$ using those auxiliary equations

Best Answer

I'm not familiar with the "dictionaries" nomenclature, but here's how I would address this.

To solve the problem with the simplex method, you start with the auxiliary (phase I) problem: $$ \begin{array}{rl} \min&w_1+w_2\\ \text{s.t.}&x_1+x_2+x_3+x_4+w_1-w_2=1\\ &x,w\geq0 \end{array} $$ This problem has (uncountably) many optimal solutions, but let's say it finds $x_1=1$ with all other variables equal to zero.

This gives you an initial feasible solution $x=(1\;0\;0\;0)$ to plug into the simplex method to solve your main (phase II) problem: $$ \begin{array}{rl} \min&6x_1+8x_2+5x_3+9x_4\\ \text{s.t.}&x_1+x_2+x_3+x_4=1\\ &x\geq0 \end{array} $$ The simplex method will then find the optimal solution you're looking for.

The general two-phase simplex method takes an LP of the form: $$ \begin{array}{rl} \max&c^\text{T}x\\ \text{s.t.}&Ax=b\\ &x\geq0 \end{array} $$ and finds a feasible solution by solving the auxiliary problem $$ \begin{array}{rl} \min&w^++w^-\\ \text{s.t.}&Ax+w^+-w^-=b\\ &w^\pm,x\geq0 \end{array} $$ The reason this problem is a good idea is because:

  1. It has an easy-to-find initial feasible solution: take all the $x$ variables equal to 0, $$ w^+_i=\begin{cases}b_i,&\text{if }b_i\geq0,\\0,&\text{otherwise}\end{cases},\quad w^-_i=\begin{cases}b_i,&\text{if }b_i\leq0,\\0,&\text{otherwise}\end{cases},\quad $$
  2. It's optimal objective value is zero if and only if the original problem is feasible.

I encourage you to Google & read more!

Note: a helpful way (for me) to think of the auxiliary problem is as a linearization of the nonlinear problem: $$ \begin{array}{rl} \min&\displaystyle\sum_{i=1}^n|w_i|\\ \text{s.t.}&Ax+w=b\\ &x\geq0 \end{array} $$ i.e. you introduce slack variables $w$ then try to make them equal to zero.

Related Question