Solving a linear program in case of an equality constraint

Question

I had asked a question, which can be found here :
https://stackoverflow.com/questions/17232596/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?

Answer 1

Your problem can be succinctly stated as $$\begin{align} \min \sum\limits_{i=1}^n x_i\\ \text{subject to}\\ \sum\limits_{i=1}^na_{ij}x_i&=b_j,\quad j=1,2,3.\tag{1} \end{align}$$ I am going to assume also that $x_i\geq0$. If not, then you can make the substitution $x_i=x_i^+-x_i^-$ where $x_i^+,x_i^-\geq0$ to get into this form.

A computationally efficient method to solve such a problem, when there is no obvious basis is to introduce artificial variables $A_j\geq0$ to provide an initial basis. Equation $(1)$ is then rewritten as $$ \sum\limits_{i=1}^na_{ij}x_i+A_j=b_j,\quad j=1,2,3.\tag{2} $$

The two-phase simplex method then applies the regular simplex algorithm to two problems in succession.

Problem $1$: $\min W=\sum_{j=1}^3A_j$ subject to $(2)$.

This problem minimises the sum of the artificial variables that were introduced into the basis and the optimal value for $W$ can be used to determine feasibility. If $W>0$, then at least one $A_j>0$, which means that $(1)$ has no solution; thus the problem is infeasible and do not proceed to problem $2$. If $W=0$, then $(1)$ has at least one solution. Furthermore, the optimal basis for problem $1$ provides an initial basis for problem $2$.

Problem $2$: $\min Z=\sum\limits_{i=1}^nx_i$ subject to $(1)$, using the initial basis found in problem $1$.

This problem then solves the original minimisation problem using the basis generated in problem $1$. Note that $(1)$ can be used in place of $(2)$ as all $A_j=0$.

Answer 2

You have to use the Big M method to solve this problem, in this case in the standard form you only add the artificial variable to the constraints and you don't add the slack variable (since there is no surplus in equality) after that you proceed with the simplex table as you will usually do in the Big M method.

I hope that was of help.

Regards.