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

[ftneek]

(11-11-2023 01:43 AM)Albert Chan Wrote:  There may be situations that c has non-zero offset.

Yes, the offset actually goes in the last position of the objective function row. So where your +/- argument was for min/max. I'm glad you noticed and made a fix, I forgot to mention it.

Example 3.1.1 from the mentioned textbook:

Xcas > lpsolve(-3x1+2x2+x3-x4+x5+87,[4x1-x2+x4-x5+x6=6,-7x1+8x2+x3-x7=7,x1+x2+4x4-4x5=12],assume=lp_nonnegative)
->1441/17

> simplex2([[4,-1,0,1,-1,1,0,1,0,0,6],[-7,8,1,0,0,0,-1,0,1,0,7],[1,1,0,4,-4,0,0,0,0,1,12],[-3,2,1,-1,1,0,0,0,0,0,-87],[0,0,0,0,0,0,0,1,1,1,0]],{8,9,10},10,3,0)
>Ans(1)
1441/17

Note I think there is a bug with my wrapper simplex() method, sometimes the artificial variable counter is not updated. So far the bad effect is for some systems with artificial variables. But also note that simplex2() works as intended with the correct arguments. I need to determine a correct (and hopefully efficient) way to identify artificial variables without false positives, as that would have a bad effect for systems without artificial variables. But with symbolic input or a list of constraint symbols, this task should be much easier.

If you want to help me debug/think of a better way to detect artificial variables... The simplex wrapper assumes the matrix is in standard form. The search should probably start from the right, since slack/artificial variables are generally added to the end of the matrix. A slack variable is chosen for the I-th basic variable if a column has a single 1 in position of the I-th row. An artificial variable should be identified if there are 2 1's in the column: in the position of the current row number, and the last position of the column. But be cautious, it is possible for the coefficients of the objective function to be 1 (and there is a 1 in position of current row, and there is no artificial row). We should stop looking in a row if a basic variable was identified for it. When looking for next bv, we need not check columns of previously identified bv. We should stop looking for basic variables if size(b0) equals the number of constraints. We should only call simplex2() if we have enough basic variables when the search is complete.

I think this is worth finding the correct way to do because the size of the matrix grows much larger when using the <= + >= method. But I have 3 major assignments due this weekend , so it will be a little while before I can really find a fix, especially since simplex2() works fine.

As for "knocking down" the variables, I'm not sure I understand what you did at the moment. It seems the min value may be the same, but it doesn't seem to have the same solution when applying simplex regularly.

(11-11-2023 01:43 AM)Albert Chan Wrote:  > simplex_le([[-1,20], [7,25], [-25,115]/11], −∞)
[−18.5714285714, [25/7, 165/7, 0], ...]

> simplex2([[3,2,1,1,0,10],[2,5,3,0,1,15],[-2,-3,-4,0,0,0],[0,0,0,1,1,0]],{4,5},5,2,0)
[-130/7,[15/7,0,25/7,0,0],...]
This problem should have one solution at x1=15/7,x2=0,x3=25/7.

I just want to mention one last thing for now. Artificial variables are not always required to solve a problem, but they give a starting point for the simplex method. If you randomly choose a set of starting basic variables, there's a chance it will not result in a feasible solution (does not satisfy some constraint). Thus we use slack and artificial variables as a starting point.