#include #include "opt.h" #define Debug 0 /* Simplex Method (linear programming) solve the canonical form of LP problem maximize c0 x0 + c1 x1 + ... + cn-m+1 xn-m+1 + d0 subject to a0,0 x0 + a0,1 x1 + ... + a0,n-m+1 xn-m+1 + xn-m = b0 a1,0 x0 + a1,1 x1 + ... + a1,n-m+1 xn-m+1 + xn-m+1 = b1 ...... am-1,0 x0 + am-1,1 x1 + ... + am-1,n-m+1 xn-m+1 + xn-1 = bm-1 inputs: m --- the number of equations n --- the number of variables m < n a --- coefficient matrix note that matrix a satisfies a[i][n-m+j] = 1 (when i=j) = 0 (when i \neq j) for all i=0,1,...,m-1 j=0,1,...,m-1 b --- constant vector note that b[i] >= 0 for all i=0,1,...,m-1 c --- coefficient vector note that c[n-m+j] = 0 for all j=0,1,...,m-1 d --- constant eps --- small value outputs: ox --- optimal solution ov --- optimal value return value: success : find optimal solution failure : diverge (optimal value = infinity) */ extern status LPsimplex (int m, int n, dbl a[], dbl b[], dbl c[], dbl *d, dbl eps, dbl ox[], dbl *ov) { int i, j; int *base; status st; base = allc(dbl, m); for (i=0; i 0 */ s = n; for (j=0; j eps) { s = j; break; } } if (s == n) { /* when c0 through cn-1 are all non-positive */ return(success); } #if Debug printf("col pivot = %d\n", s); #endif /* row pivot */ r = m; for (i=0; i 0 */ s = n; for (j=0; j eps) { s = j; break; } } if (s == n) { /* when c0 through cn-1 are all non-positive */ return(success); } #if Debug printf("col pivot = %d\n", s); #endif /* row pivot */ r = m; for (i=0; i