0
$\begingroup$

I have a programming problem, which I've expressed as the following system of equations. I'm trying to solve these equations using the Simplex method.

-2x1 + -2x2 + -2x3 + -2x4 + -2x5 + -2x6 + 1x7 + 1x8 + 1x9 + 1x10 = 0

x8 - x1 - x5 - x6 = 0
x9 - x1 - x2 - x4 = 0
x7 - x2 - x3 - x5 = 0
x9 - x2 - x1 - x4 = 0
x7 - x3 - x2 - x5 = 0
x10 - x3 - x4 - x6 = 0
x9 - x4 - x1 - x2 = 0
x10 - x4 - x3 - x6 = 0
x7 - x5 - x2 - x3 = 0
x8 - x5 - x1 - x6 = 0
x8 - x6 - x1 - x5 = 0
x10 - x6 - x3 - x4 = 0

x7 = 121561
x8 = 123007
x9 = 122957
x10 = 124807

(with x1,x2,x3,x4,x5,x6,x7,x8,x9,x10 >= 0)

Now, I know one solution is (because I've generated the problem):

x1 = 43195
x2 = 39955
x3 = 43397
x4 = 39807
x5 = 38209
x6 = 41603

My equations are all valid for this solution, but this system isn't yet solvable using the simplex method.

From my understanding of the method, I need to square the matrix of equations using slack variables, and define a target function using those slack variables.

Now, the teaching material I have shows how to introduce slack variables to convert inequalities to equalities, but I don't quite understand how to apply that to this system, which already only has equalities.

How many slack variables would I add to be able to solve this system, and what would my target function be?

$\endgroup$
5
  • $\begingroup$ Why do you want to use the simplex method to solve a system of linear equations? There is nothing to minimize or maximize here. $\endgroup$
    – Gonçalo
    Apr 19 at 8:58
  • $\begingroup$ What method would you suggest? $\endgroup$
    – Lg102
    Apr 19 at 9:05
  • $\begingroup$ How would I apply that here, with more equations than variables? $\endgroup$
    – Lg102
    Apr 19 at 9:55
  • $\begingroup$ @Gonçalo The variables are all required to be non-negative. If the system of equations has more than one solution, Gaussian elimination by itself won't necessarily enable to you to find one which satisfies the non-negativity requirement. $\endgroup$ Apr 19 at 10:39
  • $\begingroup$ My bad. I overlooked this detail. $\endgroup$
    – Gonçalo
    Apr 20 at 3:41

1 Answer 1

1
$\begingroup$
  • Several of your equations are duplicates, and can therefore be eliminated from the system. The $11^\text{th}$ $\ (x_8-x_5-x_1-x_6=0)\ $ and $12^\text{th}$ $\ (x_8-x_6-x_1-x_5=0)\ $ are duplicates of the $2^\text{nd}$ $\ (x_8-$$\,x_1-$$\,x_5-$$\,x_6$$\,=0)\ $, the $5^\text{th}$ and $8^\text{th}$ are duplicates of the $3^\text{rd}$, the $6^\text{th}$ and $10^\text{th}$ are duplicates of the $4^\text{th}$, and the $9^\text{th}$ and $13^\text{th}$ are duplicates of the $7^\text{th}$.
  • Your last four equations simply state the values of the variables $\ x_7\ $ to $\ x_{10}\ $, so you can eliminate them from the system by substituting the values for them into the other equations.

After carrying out the above steps, you will end up with the following system of equations, which I have written in matrix form: $$ \pmatrix{1&1&1&1&1&1\\ 1&0&0&0&1&1\\ 1&1&0&1&0&0\\ 0&1&1&0&1&0\\ 0&0&1&1&0&1\\}\pmatrix{x_1\\x_2\\x_3\\x_4\\x_5\\x_6}=\pmatrix{246166\\123007\\122957\\121561\\124807} $$ You now have $5$ equations in $6$ unknowns, for which you want a non-negative solution. Finding a non-negative solution of a system of linear equations is precisely what phase I of the Simplex method is designed to do. To implement this, you relax the equalities in the above equations to inequalities, introduce $5$ more non-negative variables (in this case, called "artificial variables" rather than "slack variables"), one for each equation, defined by $$ \pmatrix{s_1\\s_2\\s_3\\s_4\\s_5}=\pmatrix{246166\\123007\\122957\\121561\\124807}-\pmatrix{1&1&1&1&1&1\\ 1&0&0&0&1&1\\ 1&1&0&1&0&0\\ 0&1&1&0&1&0\\ 0&0&1&1&0&1\\}\pmatrix{x_1\\x_2\\x_3\\x_4\\x_5\\x_6}\ , $$ and solve the linear programming problem \begin{align} \text{Minimize}&\ z=s_1+s_2+s_3+s_4+s_5\\ \text{Subject to}&\left\{\begin{array}{}{\pmatrix{1&1&1&1&1&1\\ 1&0&0&0&1&1\\ 1&1&0&1&0&0\\ 0&1&1&0&1&0\\ 0&0&1&1&0&1\\}\pmatrix{x_1\\x_2\\x_3\\x_4\\x_5\\x_6}+\pmatrix{s_1\\s_2\\s_3\\s_4\\s_5}=\pmatrix{246166\\123007\\122957\\121561\\124807}\\ 0\le x_i,\ \text{ for }\ i=1,2,\dots6, \ 0\le s_i,\ \text{ for }\ i=1,2,\dots5. }\end{array}\right. \end{align} This is a problem to which the Simplex algorithm can be applied directly. It's in the form that George Dantzig, the inventor of the Simplex method, called "standard". For some reason, modern terminology seems to have departed from Dantzig's original, and now applies the term "standard" to maximization problems rather than minimization problems. However, since either of these forms is easily converted to an equivalent version in the other, this difference in terminology is neither here nor there when it comes to solving the problem.

If the above optimization problem has a solution with $\ z=0\ $ (and hence $\ s_i=0\ $ for all $\ i\ $), then the values of the variables $\ x_1\ $ to $\ x_6\ $ in the optimal solution will give you a solution to your original system of equations and inequalities. On the other hand if the optimal solution of the above linear programming problem has $\ z>0\ $, then it tells you that your original system of equations and inequalities has no solution.

On the other hand, in this case you can in fact also solve the original system by adopting the suggestion Gonçalo made in the comments to apply Gaussian elimination. While this isn't quite sufficient just by itself, a little bit of extra work will enable you to find solutions to the original system of equations and inequalities.

Applying Gaussian elimination to the above system of equations reduces it to the following equivalent system: $$ \pmatrix{1&0&0&0&1&1\\ 0&1&0&0&0&-1\\ 0&0&1&0&1&1\\ 0&0&0&1&0&-1\\ 0&0&0&0&0&0\\}\pmatrix{x_1\\x_2\\x_3\\x_4\\x_5\\x_6}=\pmatrix{123007\\-1648\\123209\\1598\\0}\ . $$ The last equation here tells you that the matrix of coefficients of the original system has rank $4$, but the equations are nevertheless consistent. The fourth equation tells you that $\ x_4=1598+x_5\ $, and the second tells you that $\ x_2=x_6-1648\ $, and hence that $\ x_6\ge1648\ $ ( since $\ x_2\ge0\ $). The first equation tells you that $\ 0\le$$\,x_1=$$\,123007-$$\,x_5-$$\,x_6\ $, and hence that $\ x_5+x_6\le123007\ $, while the third tells you that $\ 0\le x_3=123209-x_5-x_6\ $, and hence that $\ x_5+x_6\le123209\ $. But since this last inequality is weaker than the one arising from the first equation, it's redundant.

Thus, we can finally deduce that if $\ x_5,x_6\ $ are any pair of real numbers satisfying \begin{align} 1648&\le x_6\le123007\ \ \text{and}\\ 0&\le x_5\le123007-x_6\ , \end{align} and \begin{align} x_1&=123007-x_5-x_6\\ x_2&=x_6-1648\\ x_3&=123209-x_5-x_6\\ x_4&=1598+x_5\ , \end{align} then $\ x_1,x_2,x_3,x_4,x_5,x_6\ $ will be non-negative numbers satisfying the original system of equations.

$\endgroup$
1
  • $\begingroup$ This is wonderfully clear, thank you very much! $\endgroup$
    – Lg102
    Apr 21 at 14:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .