| 134 | swap(basis[a], index[b]); |
| 135 | } |
| 136 | inline long double solve(){ /// simplex core |
| 137 | init(); |
| 138 | int i, j, k, l; |
| 139 | for (; ;){ |
| 140 | for (i = 1, k = 1; i <= m; i++){ |
| 141 | if ((ar[i][n] < ar[k][n]) || (ar[i][n] == ar[k][n] && basis[i] < basis[k] && (rand() & 1))) k = i; |
| 142 | } |
| 143 | if (ar[k][n] >= -EPS) break; |
| 144 | |
| 145 | for (j = 0, l = 0; j < n; j++){ |
| 146 | if ((ar[k][j] < (ar[k][l] - EPS)) || (ar[k][j] < (ar[k][l] - EPS) && index[i] < index[j] && (rand() & 1))){ |
| 147 | l = j; |
| 148 | } |
| 149 | } |
| 150 | if (ar[k][l] >= -EPS){ |
| 151 | solution_flag = INFEASIBLE; /// No solution is possible |
| 152 | return -1.0; |
| 153 | } |
| 154 | pivot(m, n, k, l); |
| 155 | } |
| 156 | for (; ;){ |
| 157 | for (j = 0, l = 0; j < n; j++){ |
| 158 | if ((ar[0][j] < ar[0][l]) || (ar[0][j] == ar[0][l] && index[j] < index[l] && (rand() & 1))) l = j; |
| 159 | } |
| 160 | if (ar[0][l] > -EPS) break; |
| 161 | for (i = 1, k = 0; i <= m; i++){ |
| 162 | if (ar[i][l] > EPS && (!k || ar[i][n] / ar[i][l] < ar[k][n] / ar[k][l] - EPS || (ar[i][n] / ar[i][l] < ar[k][n] / ar[k][l] + EPS && basis[i] < basis[k]))){ |
| 163 | k = i; |
| 164 | } |
| 165 | } |
| 166 | if (ar[k][l] <= EPS){ |
| 167 | solution_flag = UNBOUNDED; /// Solution is infinity, no finite solution exists |
| 168 | return -666.0; |
| 169 | } |
| 170 | pivot(m, n, k, l); |
| 171 | } |
| 172 | for (i = 1; i <= m; i++){ |
| 173 | if (basis[i] >= 0) val[basis[i]] = ar[i][n]; |
| 174 | } |
| 175 | solution_flag = 1; /// Successful completion |
| 176 | return (ar[0][n] * minmax_flag); /// Negate the output for MINIMIZE since the objective function was negated |
| 177 | } |
| 178 | } |
| 179 | long double obj[N],cons[N]; |
| 180 | |