# How to solve simplex problem with $x_1 + x_2 + x_3 + x_4 =1$ as restriction?

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

• Maybe include how the two phase went wrong. – coffeemath Mar 24 at 15:24
• that's true, I added those in edit, thank you – edward locke Mar 24 at 15:33

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.

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.