单纯形法C语言程序代码

下面是一个使用单纯形法求解线性规划问题的C语言程序代码示例：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_N 20
#define MAX_M 20
#define INF 1e9

double a[MAX_M+1][MAX_N+1]; // 系数矩阵
int n, m; // 变量数和约束数
int basis[MAX_M+1]; // 基变量
double c[MAX_N+1]; // 目标函数系数
double v; // 最优解

void pivot(int r, int s) {
    int i, j;
    double t = a[r][s];
    a[r][s] = 1.0;
    for (j = 0; j <= n; j++) {
        a[r][j] /= t;
    }
    for (i = 0; i <= m; i++) {
        if (i != r) {
            t = a[i][s];
            a[i][s] = 0.0;
            for (j = 0; j <= n; j++) {
                a[i][j] -= a[r][j]*t;
            }
        }
    }
    basis[r] = s;
}

int simplex() {
    int i, j, s;
    while (1) {
        s = 0;
        for (j = 1; j <= n; j++) {
            if (c[j] > c[s]) {
                s = j;
            }
        }
        if (c[s] <= 0) {
            return 1; // 最优解
        }
        double min_ratio = INF;
        int r = -1;
        for (i = 1; i <= m; i++) {
            if (a[i][s] > 0) {
                double ratio = a[i][0]/a[i][s];
                if (ratio < min_ratio) {
                    min_ratio = ratio;
                    r = i;
                }
            }
        }
        if (r == -1) {
            return 0; // 无界解
        }
        pivot(r, s);
    }
}

int main() {
    int i, j;
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; i++) {
        scanf("%lf", &c[i]);
    }
    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++) {
            scanf("%lf", &a[i][j]);
        }
        scanf("%lf", &a[i][0]);
    }
    for (i = 1; i <= n; i++) {
        c[i] = -c[i];
    }
    for (i = 1; i <= m; i++) {
        a[i][n+i] = 1.0;
        basis[i] = n+i;
    }
    n += m;
    if (simplex()) {
        v = a[0][0];
        printf("%.8f\n", v);
    } else {
        printf("无界解\n");
    }
    return 0;
}

该程序使用了单纯形法求解标准形式的线性规划问题。其中，输入数据包括变量数和约束数，目标函数系数和约束条件的系数矩阵及右侧常数。输出数据为最优解或无界解。在程序中，使用了一些辅助函数，如 pivot() 函数实现了单纯形法的主要步骤，simplex() 函数是整个算法的主要函数，实现了单纯形法的迭代过程。