| 43 | if (r == -1) return false; |
| 44 | Pivot(r, s); } } |
| 45 | DOUBLE Solve(VD &x) { |
| 46 | int r = 0; |
| 47 | for (int i = 1; i < m; i++) if (D[i][n + 1] < D[r][n + 1]) |
| 48 | r = i; |
| 49 | if (D[r][n + 1] < -EPS) { |
| 50 | Pivot(r, n); |
| 51 | if (!Simplex(1) || D[m + 1][n + 1] < -EPS) |
| 52 | return -numeric_limits<DOUBLE>::infinity(); |
| 53 | for (int i = 0; i < m; i++) if (B[i] == -1) { |
| 54 | int s = -1; |
| 55 | for (int j = 0; j <= n; j++) |
| 56 | if (s == -1 || D[i][j] < D[i][s] || |
| 57 | D[i][j] == D[i][s] && N[j] < N[s]) |
| 58 | s = j; |
| 59 | Pivot(i, s); } } |
| 60 | if (!Simplex(2)) return numeric_limits<DOUBLE>::infinity(); |
| 61 | x = VD(n); |
| 62 | for (int i = 0; i < m; i++) if (B[i] < n) |
| 63 | x[B[i]] = D[i][n + 1]; |
| 64 | return D[m][n + 1]; } }; |
| 65 | // Two-phase simplex algorithm for solving linear programs |
| 66 | // of the form |
| 67 | // maximize c^T x |
nothing calls this directly
no outgoing calls
no test coverage detected