c++实现单纯性算法

纯性算法是一种求解线性规划问题的方法，它的基本思想是通过不断地移动可行解来逐步逼近最优解。下面是C++实现单纯性算法的一些步骤和代码示例：

1. 首先需要定义一个矩阵来存储线性规划问题的系数矩阵和约束条件矩阵，以及目标函数的系数向量和常数项。

const int MAXN = 1005;
const int MAXM = 1005;
const double INF = 1e9;
const double eps = 1e-8;

int n, m;
double a[MAXN][MAXM], b[MAXN], c[MAXM];

2. 然后需要实现单纯性算法的核心部分——找到一个入基变量和出基变量，以及计算新的可行解。

int simplex() {
    while (true) {
        int p = 0, q = 0;
        for (int i = 1; i <= m; i++) {
            if (c[i] > eps) {
                p = i;
                break;
            }
        }
        if (p == 0) return 0;
        double minv = INF;
        for (int i = 1; i <= n; i++) {
            if (a[i][p] > eps && b[i] / a[i][p] < minv) {
                minv = b[i] / a[i][p];
                q = i;
            }
        }
        if (q == 0) return 1;
        double t = a[q][p];
        for (int i = 1; i <= m; i++) {
            a[q][i] /= t;
        }
        b[q] /= t;
        for (int i = 1; i <= n; i++) {
            if (i != q && fabs(a[i][p]) > eps) {
                double t = a[i][p];
                for (int j = 1; j <= m; j++) {
                    a[i][j] -= t * a[q][j];
                }
                b[i] -= t * b[q];
            }
        }
        double t = c[p];
        for (int i = 1; i <= m; i++) {
            c[i] -= t * a[q][i];
        }
        b[0] += t * b[q];
    }
}

3. 最后需要在主函数中读入数据，调用单纯性算法求解线性规划问题，并输出最优解。

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
        cin >> b[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> c[i];
    }
    int res = simplex();
    if (res == 0) {
        printf("%.10f\n", -b[0]);
    } else {
        printf("Infeasible\n");
    }
    return 0;
}