I am trying to understand and put in application the Simplex method to solve the following LP:
$$ Minimize \qquad c^Tx$$ $$ S.t.: \qquad Ax = b$$ where $A$ is a set of $n$ random 6-dimensional vectors and $b$ is a non null 6-dimensional vector.
Using the Simplex method, I am trying to write the algorithm to find the set of coefficients $[x_1, x_2, ..., x_n]$ to apply to each $n$ vectors so that their sum equals $b$ and so that the sum $x_1+x_2+...+x_n$ is minimized, assuming the problem is feasible (I am running scipy.optimize's linprog with the simplex method solver to confirm that the problem is feasible before attempting).
I have been following different guides and explanations of the method, but while I could solve the simpler exemple LPs, I can't solve this larger problem : it often cycles around the same single pivot at each iteration, which I don't think is ever possible. I think I am confused between all the explanations I read, as they handled different problems and situations and as the rules each state seem to change depending on if the problem is a maximization or minimization one.
The following is what I understood I needed to do to handle this problem : is it correct in theory?
Problem reformulation (exemple with $n = 4$ for the sake of visibility, typically $n > 6$)
After modifying the constraints to obtain a positive $b$ (right-hand-side) value (applying *-1 when necessary): $$ Minimize \qquad x_1+x_2+x_3+x_4 $$ $$ S.t.: \qquad f_{1_x}x_1 + ...+f_{4_x}x_4 = t_{f_x}$$ $$ \qquad \ \ \qquad f_{1_y}x_1 + ...+f_{4_y}x_4 = t_{f_y}$$ $$ \qquad \ \ \qquad f_{1_z}x_1 + ...+f_{4_z}x_4 = t_{f_z}$$ $$ \qquad \ \ \qquad m_{1_x}x_1 + ...+m_{4_x}x_4 = t_{m_x}$$ $$ \qquad \ \ \qquad m_{1_y}x_1 + ...+m_{4_y}x_4 = t_{m_y}$$ $$ \qquad \ \ \qquad m_{1_z}x_1 + ...+m_{4_z}x_4 = t_{m_z}$$
Building the tableau
After introducing 6 artificial variables for each equality constraints, I get a tableau of this form:
$$ \begin{array}{c|lcr} & \text{$z$} & \text{$x_1$} & \text{$x_2$} & \text{$x_3$} & \text{$x_4$} & \text{$a_1$} & \text{$a_2$} & \text{$a_3$} & \text{$a_4$} & \text{$a_5$} & \text{$a_6$} & \text{$b$}\\ \hline \text{$z$} & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \text{$a_1$} & 0 & f_{1_x} & f_{2_x} & f_{3_x} & f_{4_x} & 1 & 0 & 0 & 0 & 0 & 0 & t_{f_x} \\ \text{$a_2$} & 0 & f_{1_y} & f_{2_y} & f_{3_y} & f_{4_y} & 0 & 1 & 0 & 0 & 0 & 0 & t_{f_y} \\ \text{$a_3$} & 0 & f_{1_z} & f_{2_z} & f_{3_z} & f_{4_z} & 0 & 0 & 1 & 0 & 0 & 0 & t_{f_z} \\ \text{$a_4$} & 0 & m_{1_x} & m_{2_x} & m_{3_x} & m_{4_x} & 0 & 0 & 0 & 1 & 0 & 0 & t_{m_x} \\ \text{$a_5$} & 0 & m_{1_y} & m_{2_y} & m_{3_y} & m_{4_y} & 0 & 0 & 0 & 0 & 1 & 0 & t_{m_y} \\ \text{$a_6$} & 0 & m_{1_z} & m_{2_z} & m_{3_z} & m_{4_z} & 0 & 0 & 0 & 0 & 0 & 1 & t_{m_z} \end{array} $$
The initial solution is basic, as out of $n+6$ variables, $n$ are set to $0$ ($x_1 = ... = x_n = 0$) and the 6 variables remaining ($a_{1:6} = t_{f/m_{x/y/z}} \geq 0$) aren't.
This initial basic solution is and always will be feasible, as $x_1 = ... = x_n = 0 \geq 0$ and all $a_{1:6} = t_{f/m_{x/y/z}} \geq 0$ : all variables are non-negative. We can begin pivoting.
Optimality condition
For a minimization problem, optimality is reached when no more positive entries lie in the objective row.
Pivot selection
For a minimization problem, the pivot column is the column where lies the greatest positive entry in the objective row. The pivot row is the row for which the value $(h_i / b_i, b_i>0)$ is the greatest, for all $h_i$ in the column $[h_0, h_1, ..., h_n]$.
Pivoting
The pivot's column is filled with $0$, except for the pivot value.
The pivot's row is divided by the pivot value.
All other rows follow this formula, ignoring pivot column's entries: $new = current - (value \ in \ pivot \ column \ in \ the \ same \ row * new \ pivot \ row)$
Repeat until optimality is reached
Assuming no degeneracy nor unboundness, for now.
Are there errors in there? Also, sorry if this is out of topic, I'm not sure if such questions are accepted here.
A lot of this is correct, but some things need to be tweaked.
For one thing, make sure you realize that $c^Tx$ is equal to $c_{1}x_{1} + ... + c_{n}x_{n}$, which is not generally the same as $x_{1} + ... + x_{n}$. And importantly, the objective function row in the tableau will not consist of $c_{i}$'s, but actually $-c_{i}$'s, since the equation $z=c_{1}x_{1} + ... + c_{n}x_{n}$ implies $z-c_{1}x_{1} - ... - c_{n}x_{n} = 0$.
Also, when the constraints are written in the form $Ax = b$, slack/excess/artificial variables are often already included in A, so they won't need to be introduced. If that's the case, the rest of this won't apply to you.
Supposing that those variables have not already been included and that you were correct to include artificial variables--there is a catch: the objective function is now incorrect, and the way we correct it depends on which method we use. If you're unfamiliar with both the Big-M and Two-Phase Methods, then it's safe to assume that you only need slack variables, which have already been included in $A$.
If we use the Big-M method, the objective function should read: $z=c_{1}x_{1} + ... + c_{n}x_{n} + Ma_{1} + ... + Ma_{6}$ (or $z=c_{1}x_{1} + ... + c_{n}x_{n} - Ma_{1} - ... - Ma_{6}$, in the maximization case), which should be rewritten as: $z-c_{1}x_{1} - ... - c_{n}x_{n} - Ma_{1} - ... - Ma_{6}=0$ (or $z-c_{1}x_{1} - ... - c_{n}x_{n} + Ma_{1} + ... + Ma_{6}=0$), and the tableau should be rewritten accordingly. You will then have to perform Gaussian elimination to make each $a_{i}$ basic, since they will no longer be basic after making the above change.
On the other hand, if we use the Two-Phase Method, your objective function will read $minimize \quad w = a_{1} + ... + a_{6}$, and you'll make each $a_{i}$ basic as in the previous paragraph. From there, Phase One consists of performing the Simplex Method as you've described it until all artificial variables have left the basis. Next, Phase Two consists of replacing the objective function row with $z-c_{1}x_{1} - ... - c_{n}x_{n}$ (leaving the RHS of the objective function alone--it may be non-zero) and solving using the standard Simplex Method in which you ignore artificial variable columns. You may simply erase those columns if you'd like.