The Simplex2P class solves Linear Programming (LP) problems using a tableau based Simplex Algorithm. Given a constraint matrix a, limit/RHS vector b and cost vector c, find values for the solution/decision vector x that minimize the objective function f(x), while satisfying all of the constraints, i.e.,
minimize f(x) = c x subject to a x <= b, x >= 0
In case of a_i x >= b_i, use -b_i as an indicator of a ">=" constraint. The program will flip such negative b_i back to positive as well as use a surplus and artificial variable instead of the usual slack variable, i.e., a_i x <= b_i => a_i x + s_i = b_i // use slack variable s_i with coefficient 1 a_i x >= b_i => a_i x + s_i = b_i // use surplus variable s_i with coefficient -1 For each '>=' constraint, an artificial variable is introduced and put into the initial basis. These artificial variables must be removed from the basis during Phase I of the Two-Phase Simplex Algorithm. After this, or if there are no artificial variables, Phase II is used to find an optimal value for x and the optimum value for f.
Creates an MM-by-nn simplex tableau with -- [0..M-1, 0..N-1] = a (constraint matrix) -- [0..M-1, N..M+N-1] = s (slack/surplus variable matrix) -- [0..M-1, M+N..nn-2] = r (artificial variable matrix) -- [0..M-1, nn-1] = b (limit/RHS vector) -- [M, 0..nn-2] = c (cost vector)
Value parameters
a
the M-by-N constraint matrix
b
the M-length limit/RHS vector (input b_i negative for surplus)
Find the best variable x_l to enter the basis. Determine the index of entering variable corresponding to column l (e.g., using Dantiz's Rule or Bland's Rule). Return -1 to indicate no such column. t(M).argmaxPos (jj) // use Dantiz's rule (index of max positive, cycling possible) t(M).firstPos (jj) // use Bland's rule (index of first positive, FPE possible)
Find the best variable x_l to enter the basis. Determine the index of entering variable corresponding to column l (e.g., using Dantiz's Rule or Bland's Rule). Return -1 to indicate no such column. t(M).argmaxPos (jj) // use Dantiz's rule (index of max positive, cycling possible) t(M).firstPos (jj) // use Bland's rule (index of first positive, FPE possible)
Initialize the basis to the slack and artificial variables. Perform row operations to make cost row (t(M)) zero in artificial var columns. If b(i) is negative have a surplus and artificial variable, otherwise, just a slack variable.
Initialize the basis to the slack and artificial variables. Perform row operations to make cost row (t(M)) zero in artificial var columns. If b(i) is negative have a surplus and artificial variable, otherwise, just a slack variable.
Find the best variable x_k to leave the basis given that x_l is entering. Determine the index of the leaving variable corresponding to row k using the Min-Ratio Rule. Return -1 to indicate no such row.
Find the best variable x_k to leave the basis given that x_l is entering. Determine the index of the leaving variable corresponding to row k using the Min-Ratio Rule. Return -1 to indicate no such row.
Solve the LP minimization problem using two phases if necessary. Note: phase I is always minimization. Two phases are necessary if the number of artificial variables R > 0.
Solve the LP minimization problem using two phases if necessary. Note: phase I is always minimization. Two phases are necessary if the number of artificial variables R > 0.
Run the simplex algorithm starting from an initial BFS and iteratively find a non-basic variable to replace a variable in the current basis so long as the objective function improves. Runs a single phase and return the optimal vector x.
Run the simplex algorithm starting from an initial BFS and iteratively find a non-basic variable to replace a variable in the current basis so long as the objective function improves. Runs a single phase and return the optimal vector x.