单纯形法求解线性规划问题c语言

单纯形法是一种求解线性规划问题的常用算法，它可以在有限步内找到最优解或确定问题无界或无可行解。下面是一个使用C语言实现单纯形法求解线性规划问题的示例代码：

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

#define MAX_N 100
#define MAX_M 100

double a[MAX_M + 1][MAX_N + MAX_M + 1];
int basis[MAX_M + 1];
int m, n;

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

int feasible() {
    while (1) {
        int r = 0, c = 0;
        for (int i = 1; i <= m; i++) {
            if (a[i][0] < a[r][0]) r = i;
        }
        if (a[r][0] >= 0) return 1;
        double minv = 1e9;
        for (int j = 1; j <= n + m; j++) {
            if (a[r][j] < minv) {
                minv = a[r][j];
                c = j;
            }
        }
        if (minv == 1e9) return 0;
        pivot(r, c);
    }
}

int simplex() {
    while (1) {
        int r = 0, c = 0;
        for (int j = 1; j <= n + m; j++) {
            if (a[0][j] > a[0][c]) c = j;
        }
        if (a[0][c] <= 0) return 1;
        double minv = 1e9;
        for (int i = 1; i <= m; i++) {
            if (a[i][c] > 0 && a[i][0] / a[i][c] < minv) {
                minv = a[i][0] / a[i][c];
                r = i;
            }
        }
        if (minv == 1e9) return 0;
        pivot(r, c);
    }
}

double simplex_solve(double *c, double *b, double **mat, double *x) {
    n = sizeof(c) / sizeof(double);
    m = sizeof(b) / sizeof(double);
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            a[i][j] = mat[i - 1][j - 1];
        }
        for (int j = n + 1; j <= n + m; j++) {
            a[i][j] = (i == j - n) ? 1 : 0;
        }
        a[i][n + m + 1] = b[i - 1];
    }
    for (int j = 1; j <= n; j++) a[0][j] = -c[j - 1];
    feasible();
    if (!simplex()) return -1;
    for (int i = 0; i < n; i++) {
        x[i] = 0;
        for (int j = 1; j <= m; j++) {
            if (basis[j] == i + 1) x[i] = a[j][0];
        }
    }
    return -a[0][0];
}

使用时，只需将线性规划问题转化为标准形式，即将约束条件通过引入松弛变量转化为等式，再将非负约束通过引入人工变量转化为等式，最后将优化目标函数转化为最大化问题，即可调用 `simplex_solve` 函数求解线性规划问题，其中 `c` 为目标函数系数向量，`b` 为约束条件右侧常数向量，`mat` 为约束条件系数矩阵，`x` 为最优解向量。