The linear programming problem is changed into a set of simultaneous linear equations using slack variables.

After you set up the new matrix that has the slack variables you use Gaussian elimination with pivoting to solve it. If you know how to do that then a LP problem is similar.

Have you seen this?

]]>Cramers rule is a horror story. It grows factorially so a 4 x 4 would be awful.

I meant that it worked well for the 3X3 matrix on paper. The 4X4 matrix was the one that sprawled onto several pages, like you said.

The simplex method is for Linear programming and can be done using Gaussian elimination.

Could you explain a little more what you mean when you say it can be done using Gaussian elimination?

I will have to pick an algorithm for solving the 4x4 matrix in C++. Cramer's rule will work by "recursively" calling macros or functions, though that may be inefficient based on what you explained.

]]>The simplex method is for Linear programming and can be done using Gaussian elimination.

]]>On another forum, some people suggested Cramer's rule, which worked out beautifully for that given problem - it matched the derivations in the paper I was reading.

For a larger version of the system, my adviser suggested not solving it arbitrarily on paper because the solution spanned multiple pages - he suggested just giving it to Matlab to solve for given constant values (and implementing a solver for the C++ version).

The elimination process has been formalised into an algorithm called the Simplex Method. If you wanted to write a program to solve systems of equations, this would be worth knowing.

I had understood that the simplex algorithm optimizes a function based on a series of constraints and graphically moves along to get to that optimum. To implement gaussian elimination with the simplex algorithm, would you get rid of the min / max function and then only use equality instead of inequalities for the constraints? I'm not an expert on the simplex algorithm but would like to know.

Thank you for your feedback.

]]>Welcome to the forum.

Elimination will always 'solve' ** a system of equations like these. The numbers are called coefficients and if you cannot subtract straight away to eliminate a variable, then you can force it:

Say you have

2x + 3y + 4z = 20 ..................a

3x - 2y + 3z = 8 .....................b

x + y + z = 6 .........................c

If you do equation c times 4 and repeating equation a

4x + 4y + 4z = 24

2x + 3y + 4z = 20

subtract

2x + y = 4

You then do the same again with, say, b and c to eliminate z there too and you're down to two equations in x and y

Use the same process again to eliminate y and you can solve for x.

Another method is to use substitution.

Make z the subject of c, substitute the 'formula' for z in terms of x and y into the other equations, and, once again, you have two equations and two unknowns.

The elimination process has been formalised into an algorithm called the Simplex Method. If you wanted to write a program to solve systems of equations, this would be worth knowing.

Yet another approach is to use matrices.

The above equations can be written as

where

you need to know about matrix multiplication and also how to construct the inverse matrix, N

Then

** All these methods will 'solve' the equations but you won't necessarily get x = ? y = ? and z = ?

Sometimes a set of equations has no solution and it is even possible to get an infinite number of solutions. But the methods all have a way of showing when this is happening, so you have still got a solution even if it wasn't quite what you were expecting.

Bob

]]>You can do it by substitution or by using a CAS to do it for you.

]]>2x + 3y + 4z = 1

3x + 4y + 3z = 2

4x + 5y + 3z = 3

It has numerical constants in front of each term. You could use Gaussian elimination and solve for one, infinite, or no solutions. (The above example is completely random). It works because you can cancel terms out.

It's a bit less straightforward to find information on how to solve it when you have constants represented by symbols:

ua*x + ub*y + uc*z = 1

va*x + vb*y + vy*z = 2

x + y + z = 3

Here we want to solve for x, y, and z, each expressed in terms of ua/ub/uc/va/vb/vc only. You can't use elimination here because terms such as ua and va will not cancel out. (This example is slightly random too - I just need to learn the technique).

The only method I'm aware of is substitution, though it seems to spill onto multiple pages (the above system is simpler than what I need to solve). Is there any easier way to attack something like this? Any links to online references would be much appreciated.

]]>