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?
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.
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.
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.
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.
