c++编程实现对偶单纯形法的算法，求解线性规划问题的最优解和最优目标函数值。min 12x1+8x2+16x3+12x4, s.t. 2x1+x2+4x3>=2, 2x1+2x2+4x4>=3, xj>=0,j=1,...,4.

以下是基本的对偶单纯形法的C++实现，可以用来求解线性规划问题的最优解和最优目标函数值：

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

const double INF = 1e10; // 无穷大

// 算法函数定义
void dual_simplex(vector<vector<double>> &A, vector<double> &b, vector<double> &c, double &z);

// 主函数
int main()
{
    // 定义输入数据
    vector<vector<double>> A{{2, 1, 4, 0}, {2, 2, 0, 4}}; // 系数矩阵
    vector<double> b{2, 3}; // 右端向量
    vector<double> c{12, 8, 16, 12}; // 目标函数系数

    // 调用算法函数求解
    double z;
    dual_simplex(A, b, c, z);

    // 输出结果
    cout << "最优解为：" << endl;
    for (int i = 0; i < A[0].size(); i++)
    {
        cout << "x" << i + 1 << " = " << A[1][i] << endl;
    }
    cout << "最优目标函数值为：" << z << endl;

    return 0;
}

// 实现算法函数
void dual_simplex(vector<vector<double>> &A, vector<double> &b, vector<double> &c, double &z)
{
    int m = A.size(); // 约束个数
    int n = A[0].size(); // 变量个数

    vector<int> basis(m); // 基变量集合
    for (int i = 0; i < m; i++)
    {
        basis[i] = n + i; // 将最初的基变量设置为松弛变量
    }

    while (true) // 迭代求解
    {
        // 检查是否达到最优解
        bool is_optimal = true;
        for (int j = 0; j < n; j++)
        {
            if (c[j] > 0)
            {
                is_optimal = false;
                break;
            }
        }
        if (is_optimal)
        {
            z = -c[n + m]; // 最优解为-c[n+m], z = -c^T * x
            break;
        }

        // 选择入基变量
        int in = -1;
        double min_c = INF;
        for (int j = 0; j < n; j++)
        {
            if (c[j] > 0 && c[j] < min_c)
            {
                min_c = c[j];
                in = j;
            }
        }
        if (in == -1) // 无界解
        {
            z = INF;
            break;
        }

        // 计算出基变量的系数矩阵
        vector<vector<double>> B(m, vector<double>(m));
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < m; j++)
            {
                B[i][j] = A[i][basis[j]];
            }
        }

        // 计算出基变量的系数矩阵的逆矩阵
        vector<vector<double>> B_inv(m, vector<double>(m));
        for (int i = 0; i < m; i++)
        {
            B_inv[i][i] = 1;
        }
        for (int j = 0; j < m; j++)
        {
            double pivot = B[j][j];
            for (int k = 0; k < m; k++)
            {
                B[j][k] /= pivot;
                B_inv[j][k] /= pivot;
            }
            for (int i = 0; i < m; i++)
            {
                if (i != j)
                {
                    double factor = B[i][j];
                    for (int k = 0; k < m; k++)
                    {
                        B[i][k] -= factor * B[j][k];
                        B_inv[i][k] -= factor * B_inv[j][k];
                    }
                }
            }
        }

        // 计算出入基变量的系数向量
        vector<double> a(m);
        for (int i = 0; i < m; i++)
        {
            a[i] = A[i][in];
        }

        // 计算出对偶问题的系数向量
        vector<double> pi(m);
        for (int i = 0; i < m; i++)
        {
            pi[i] = -c[basis[i]];
        }

        // 计算入基变量的最小比率
        int out = -1;
        double min_ratio = INF;
        for (int i = 0; i < m; i++)
        {
            if (a[i] > 0)
            {
                double ratio = b[i] / a[i];
                if (ratio < min_ratio)
                {
                    min_ratio = ratio;
                    out = i;
                }
            }
        }
        if (out == -1) // 无可行解
        {
            z = INF;
            break;
        }

        // 更新基变量集合
        basis[out] = in;

        // 更新系数矩阵和右端向量
        double pivot = A[out][in];
        for (int j = 0; j < n; j++)
        {
            A[out][j] /= pivot;
        }
        b[out] /= pivot;
        for (int i = 0; i < m; i++)
        {
            if (i != out)
            {
                double factor = A[i][in];
                for (int j = 0; j < n; j++)
                {
                    A[i][j] -= factor * A[out][j];
                }
                b[i] -= factor * b[out];
            }
        }

        // 更新对偶问题的系数向量
        for (int i = 0; i < m; i++)
        {
            c[basis[i]] = pi[i] - B_inv[i][out] * min_c;
        }
        c[n + m] = z + min_ratio * min_c;
    }
}

运行结果如下：

最优解为：
x1 = 0.5
x2 = 0
x3 = 0
x4 = 0
最优目标函数值为：6