this is the part II of my adventure in the world of the SIMPLEX method (previous episode here).
Thanks to the suggestions I got, I could implement the two-phases SIMPLEX method to deal with problems in the form
$\max f = c^T x $
s.t.
$A x \leq b$
$A_{eq} x = b_{eq} $
$x_i \geq 0$, $\forall i$
To test the routine I created a function which generates (what I thought were) feasible LPs. The procedure is the following.
- First, generate a positive number $n$ (number of variables), a positive number $l$ representing the equality constraints, and a positive number $m$ representing the inequality constraints, with the conditions that
$l \cong n/3$, $m \cong n/3$
- Generate a positive vector $ x \in \mathbb R^n$
- Generate a random matrix $ A \in R^{l \times n}$
- Compute the vector $ b \in R^{l \times 1}$ as $b = A x + \tilde b$, with $\tilde b = round(rand([0,1]))$ such that $A x \leq b$ is satisfied (some with equality sign, some with strict inequality)
- Generate a random matrix $ A_{eq} \in R^{m \times n}$
- Evaluate the vector $ b_{eq} \in R^{m \times 1}$ as $A_{eq}x$ equality constraints are also satisfied.
- Generate a cost function $f \in \mathbb R^n$ with all positive or null elements.
- if $f^T x > 0 $ assign $f = -f$
Most of the times it works, but I don't have yet implemented infeasibility detection. So, first, is this procedure fair? to me it seems that all the constraints are satisfied.
and how can I detect infeasibility at the end of phase I of the SIMPLEX method? I noticed that in some final tableaus the RHS elements associated to some basic variables are negative, which sounds like an infeasibility detection. Is this true? how can I detect infeasibility / unboundness? I suspect there is still something weird as the problem
$\max p = -0.5116x_1 - 0.9847x_2 - 0.6619x_3 - 0.4476x_4 - 0.9183x_5$
subject to
$ 0.3417x_1 + 0.4581x_2 + 0.3819x_3 + 0.9788x_4 + 0.1806x_5 \leq 12.2376$ $ -0.2736x_1 + 0.1504x_2 - 0.4258x_3 + 0.1067x_4 + 0.1062x_5 = 1.2023$ $ -0.4892x_1 - 0.2337x_2 - 0.2130x_3 + 0.9547x_4 - 0.1664x_5 = 7.3083$
is feasible, with solution
$x_1 = 0, x_2 = 2.18392, x_3 = 0, x_4 = 8.18967, x_5 = 0$, but I get a non-sense solution
$x_1 = -10.0357, x_2 = -10.2668, x_3 = x_4 = x_5 = 0$.
What other checks can I implement to make sure I get positive, meaningful solutions?
Thanks a bunch!