#include #include "opt.h" #define Debug 1 /* Find one feasible solution Find x (>=0) s.t. Ax = b (matrix A and vector b are arbitrary) extern status LPfeasiblesolution (int m, int n, dbl a[], dbl b[], dbl eps, dbl ox[]) inputs: m = number of equations n = number of variables a = coefficient matrix (m,n) b = constants (m,1) eps : small value outputs: ox : feasible solution (if exists) return value success : feasible solution is found failure : not found */ static void buildfeasibilitytableau (m, n, a, b, aextend, cfeas, dfeas, base) int m, n; dbl *a, *b, *aextend, *cfeas, *dfeas; int *base; { int i, j; for (i=0; i= 0.00) continue; matrixrowscalar(m, n, a, i, -1.00); b[i] = -b[i]; } for (i=0; i -eps) { LPsimplexsolution(m, n, b, &dfeas, base, ox, &dfeas); return success; } else { return failure; } } /* Two Phase method maximize cx + d subject to Ax = b x >= 0 (matrix A, vector b, vector c, and scalar d are arbitrary) extern status TwoPhasemethod (int m, int n, dbl a[], dbl b[], dbl c[], dbl *d, dbl eps, dbl ox[], dbl *ov) inputs: m = number of equations n = number of variables a : (m,n) coefficient matrix b : (m,1) constants c : (1,n) coefficients of objective function *d : constant of objective function eps : small value outputs: ox : (m,1) optimal solution *ov : optimal value return value success : find optimal solution failure : diverge error : no feasible solution */ static void buildtwophasetableau (m, n, a, b, c, d, aextend, cextend, cfeas, dfeas, base) int m, n; dbl *a, *b, *c, *d, *aextend, *cextend, *cfeas, *dfeas; int *base; { int i; buildfeasibilitytableau(m, n, a, b, aextend, cfeas, dfeas, base); for (i=0; i -eps) ) { /* no feasible solution */ return error; } /*** 2nd phase ***/ reducetwophasetableau(m, n, a, c, aextend, cextend); st = LPsimplextableau(m, n, a, b, c, d, eps, base); if (st == success) { LPsimplexsolution(m, n, b, d, base, ox, ov); } return st; }