利用c++编写对偶单纯形法解决线性规划的算法程序

下面是利用C++编写对偶单纯形法解决线性规划的算法程序的基本框架：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = ; // 线性规划中变量的最大数量
const int MAXM = ; // 线性规划中约束的最大数量
const double INF = 1e9; // 无穷大

double c[MAXN+1], A[MAXM+1][MAXN+1], b[MAXM+1], v; // 线性规划的数据
int n, m; // 变量和约束的数量

void pivot(int r, int c) { // 高斯-约旦消元法
    b[r] /= A[r][c];
    for (int j = 0; j <= n; j++)
        if (j != c) A[r][j] /= A[r][c];
    A[r][c] = 1.0 / A[r][c];
    for (int i = 0; i <= m; i++)
        if (i != r && abs(A[i][c]) > 0) {
            b[i] -= A[i][c] * b[r];
            for (int j = 0; j <= n; j++)
                if (j != c) A[i][j] -= A[i][c] * A[r][j];
            A[i][c] = -A[i][c] * A[r][c];
        }
    v += c[c] * b[r];
    for (int j = 0; j <= n; j++)
        if (j != c) c[j] -= c[c] * A[r][j];
    c[c] = -c[c] * A[r][c];
}

double simplex() { // 对偶单纯形法
    while (true) {
        int c = 0;
        for (int i = 1; i <= n; i++)
            if (c[i] > c[c]) c = i;
        if (c == 0) break;
        int r = 0;
        for (int i = 1; i <= m; i++)
            if (A[i][c] > 0 && (r == 0 || b[i] / A[i][c] < b[r] / A[r][c])) r = i;
        if (r == 0) return INF;
        pivot(r, c);
    }
    return v;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lf", &c[i]);
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++)
            scanf("%lf", &A[i][j]);
        scanf("%lf", &b[i]);
    }
    printf("%.10f\n", simplex());
    return 0;
}

在上述程序中，`c[]`、`A[][]`、`b[]`、`n`、`m`、`v` 分别代表线性规划中的目标函数系数、约束系数、右端常数、变量数、约束数、目标函数值。`pivot()` 函数实现高斯-约旦消元法，`simplex()` 函数实现对偶单纯形法，`main()` 函数读入线性规划的数据并输出最优解。