3
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ I'm entering the path of compreension, thank you $\endgroup$ – edward locke Mar 25 at 23:29
  • $\begingroup$ Can you give me tips on how to choose the auxiliary objective function (w1 + w2)? Because so far i used z=-x0 and x1 + x2 + x3 +x4 +x0 = 1, and I don't know how my thought process should be like choosing how many variables I'm going to add on the auxiliary problem $\endgroup$ – edward locke Mar 25 at 23:33
  • $\begingroup$ @edwardlocke That's how the two-phase simplex method works. I'll edit my answer to give a general idea, but if you Google it you should be able to find an explanation anywhere. $\endgroup$ – David M. Mar 26 at 2:32
1
$\begingroup$

To add to the above answer by @David, simplex method starts from a feasible basis and one of the easiest ones that we start with (especially in problems that have inequality constraints) is the identity matrix that comes from adding slack/surplus variables. In your example, you already have your initial identity matrix! You can use any of your variables as the initial basis and use simplex algorithm (not even the 2-phase method.) Just make sure to modify the objective function coefficients in your simplex tableau, since those coefficients for basic variables are zero.

If you think about it, the answer that David gave at the end of phase 1, is essentially the same thing.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.