3

I had asked a question, which can be found here :
Computing the optimal combination

And had been suggested Linear programming. I have looked up Linear programming and the Simplex method. But all the examples that I have come across have inequality constraints which are converted into equalities using slack variables. The simplex method then interchanges the basic and the non basic variables to obtain an optimal solution.

But my problem is :

minimize :
x1 + x2 + ... + xn

subject to :
a1*x1 + a1*x2 + a1*x3 + ... + a1*xn = c1;
a2*x1 + a2*x2 + a2*x3 + ... + a2*xn = c2;
a3*x1 + a3*x2 + a3*x3 + ... + a3*xn = c3;

Now I don't know how I can apply the simplex method here as I don't have any basic variables here.
Also I can't just solve the linear equations as I have n variables and 3 equations.
Can someone suggest me a way out here?

Improve this question
2
  • Voting to close. This isn't a programming question as that term is generally used on SO. This is a question about the application of the simplex method for linear programming. Commented Jun 25, 2013 at 4:41
  • It was a programming question. Please see the link in the question. I ran into this confusion over the suggested method, so i thought i'd ask it here so people might be able to suggest an alternative programming technique, if linear programming shouldn't work. Commented Jun 25, 2013 at 4:44

4 Answers 4

Reset to default
5

You can rewrite each of your equations into two inequalities:

a1*x1 + a1*x1 + a1*x3 + … + a1*xn ≤ c1
a1*x1 + a1*x1 + a1*x3 + … + a1*xn ≥ c1

This assumes that the coefficients labeled a1 are actually different; otherwise your whole LP would be highly interdependent and either trivial to solve or not solvable at all. Next you add slack variables to turn the inequalities into equalities again:

a1*x1 + a1*x1 + a1*x3 + … + a1*xn + y1a = c1    y1a ≥ 0
a1*x1 + a1*x1 + a1*x3 + … + a1*xn - y1b = c1    y1b ≥ 0

Now these y1a and y1b are your initial basic variables, and you can start pivoting. Either to find an optimal solution if the initial basic solution is already feasible, or to find a feasible solution if not.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Thanks! Could you please explain the conversion of minimization to maximization as well ? I think you just negate the variables in the objective function. i.e the aforementioned function should become maximize : -x1 -x2 -x3 ... -xn. Right ? If so how does simplex proceed now ? It has to choose a nonbasic variable for which the the coefficient in the objective function is positive, right?
Or maybe you use duality. But I haven't been able to understand that. Could you please explain that if that is applicable ?
@user1925405: A step-by-step introduction to the simplex method would exceed the scope of an SO answer, imo. If resources available online are not enough, I suggest you grab obtain a copy of the book Introduction to Algorithms by Cormen et al. As far as I remember, the simplex description in there was pretty understandable. Short answer, though: Switching between maximizing and minimizing means negating the objective function, right. If there is a specific step of the simplex method which you don't understand, posting a new question with explicit (and preferrably simple) numbers might help.
2

In the textbook

"Combinatorial Optimization" by Kenneth Steiglitz and Christos Papadimitiou

you can find a detailed, self-contained description of the simplex algorithm. If I recall correctly, for the case of only equality constraints given but no basis, an artificial basis with additional artificial variables of cost zero each are introduced. Intuitively, this is like "glueing" an identity matrix on one side of the constraint matrix. Then, the simplex algorithm is started to "drive out" the artificial basis, i.e. it iterates until none of the artificial variables are contained in the basis anymore, which means that a basis of the original formulation is found.

Improve this answer

Comments

1

You don't have to do it yourself, that's why modeling languages exist. I suggest you try out either either GLPK or SCIP.

They have their own modeling language, GLPK has GNU MathProg and SCIP has ZIMPL, so you can conveniently code your LP problem. Read the documentation.

A related question is this.

Improve this answer

Comments

1

Linear programming will work on this problem. Don't describe the constraints using two inequalities, just feed it to a solver like GLPK. For example, you can write it in a few lines of GMPL:

param k, n;
param a{1..k}{1..n};
param c{1..k};
var x{1..n}, >= 0;

minimize cost : sum{i in 1..n} x[i];
s.t. constraints{j in 1..k} : sum{i in 1..n}(a[j][i] * x[i]) = c[j];

As you stated it here, however, your model probably has no optimum: without the non-negativity constraints, it is only an underdetermined linear system, with an unbounded solution. I assume that x must stay non negative and that the constraints are a bit more complex, as in your linked post.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.