Simplex Algorithm

[Albert Chan]

Hi, ftneek

It is not just a shortcut (as in hack), there is no lost of information.
Row operations represent *exactly* the original problem, but with less variables to handle.
We are adding equal amount to both side. All constraints, even cost function is unaffected.

> m := [[1,2,0,1,20], [2,1,1,0,10], [-1,4,-2,3,40], [1,4,3,2,0]]
> m2 := remove_eq_c(m, 3)[1]

\(\left(\begin{array}{ccccc}
0 & 1 & \frac{-1}{3} & \frac{2}{3} & 10 \\
1 & 0 & \frac{2}{3} & \frac{-1}{3} & 0 \\
0 & 0 & \frac{11}{3} & \frac{-1}{3} & -40
\end{array}\right) \)

Once variable are unrelated to cost function, it automatically becomes "slack".
You can adjust them whatever you want, to fit your need (max or min)

Yes, identity matrix on the "wrong" side, but it does not matter.
(if you prefer, swap columns to make identity matrix look right)

We don't need any more slack variables.

> simplex2(m2, [2,1], 4, 0, 0)

\([35,[5,0,0,15],\left(\begin{array}{ccccc}
0 & \frac{3}{2} & \frac{-1}{2} & 1 & 15 \\
1 & \frac{1}{2} & \frac{1}{2} & 0 & 5 \\
0 & \frac{1}{2} & \frac{7}{2} & 0 & -35
\end{array}\right) ]\)

ftneek Wrote:If an artificial variable remains a basic variable at the final tableau, then the system contains a redundant equation. This should be easy enough to check. But do you have any suggestions about how to present this information to the user?

Problem matrix of 4 rows, Solution matrix of 3 rows --> 1 redundant "=" constraint.