Simplex method in prime how to use the constrains maximise s.t. constraints.

[Albert Chan]

(11-10-2023 04:05 PM)Albert Chan Wrote:  max(c) = -min(-c), but I don't want to think about this either.
On the cost function, it does maximze if last element is positive.

There may be situations that c has non-zero offset.
We could solve for c without offset, then add it later, but I don't want to worry about it.

To make room, cost direction (max or min) moved outside the matrix, as 2nd argument.

Code:

simplex_le(a, dir) :=
BEGIN
 LOCAL b := col(a,0);
 a := concat(delcol(a,len(a[0])),identity(len(a)))
 a := replace(a,{1,len(a[0])},transpose(b));
 IF dir>0 THEN a[0] := -a[0] END /* maximize */
 a := simplex(a);
 IF dir>0 THEN a[1] := -a[1] END /* undo flip */
 return a;
END;

Quote:Minimize Z = -2x - 3y - 4z

Constraints:
3x + 2y + z = 10
2x + 5y + 3z = 15
x, y, z >= 0

With 2 equations and 3 unknown, we can knock down 2 variables.

> xyz := solve(3x+2y+z=10 AND 2x+5y+3z=15 ,[x,y,z])[0]

[1/11*z+20/11, -7/11*z+25/11, z]

> simplify([-2,-3,-4] * xyz)

(-25*z - 115)/11

Z is minimized if z is maximized. From y, max(z) = (25/11) / (7/11) = 25/7
min(Z) = (-25*(25/7) - 115)/11 = -130/7

Lets solve min(Z) with simplex_le(), noted that Z has an offset.
Constraint x≥0 --> 20/11 ≥ -1/11*z
Constraint y≥0 --> 25/11 ≥ 7/11*z

Note that [a|b] matrix, we evaluate a*x - b
Same for cost function, Z = (-25*z - 115)/11 input as [-25,115]/11

> simplex_le([[-1,20], [7,25], [-25,115]/11], −∞)

[−18.5714285714, [25/7, 165/7, 0], ...]

We get the same thing if we do row operations, without affecting cost function.

> m := [[3,2,1,10], [2,5,3,15], [-2,-3,-4,0]]
> m[1] /= m[1][1]
> m := pivot(m,1,1)
> m[2] /= m[2][2]
> m := pivot(m,2,2)

\(\left(\begin{array}{cccc}
1 & 0 & \frac{-1}{11} & \frac{20}{11} \\
0 & 1 & \frac{7}{11} & \frac{25}{11} \\
0 & 0 & \frac{-25}{11} & \frac{115}{11}
\end{array}\right) \)