Simplex（线性规划）计算输出的测试方法

Question

我的任务是创建一个基于网络的机器来使用线性规划技术解决现实世界的问题，特别是目前，Danzig 的单纯形法。考虑到这一点，我发现了一些相当漂亮的 C++ 代码来计算结果，即使在这台特别低端的机器上也有相当快的速度。

但是，我目前除了控制台输出本身之外什么都没有证明结果接近给定问题的正确解决方案。如果人们被要求相信结果表明比某些数字可以在计算机屏幕上闪烁更重要的事情，这就是一个问题。

整个程序的细节我就不说了，因为它比较长，这里是负责取数据的函数，仅供参考：

void Data() {
    double R1, R2;
    char R;
    int I, J;
    printf("\n LINEAR PROGRAMMING\n\n");
    printf(" MAXIMIZE (Y/N) ? "); scanf("%c", &R);
    printf("\n NUMBER OF VARIABLES OF ECONOMIC FUNCTION ? "); scanf("%d", &NV);
    printf("\n NUMBER OF CONSTRAINTS ? "); scanf("%d", &NC);
    if (R == 'Y' || R == 'y')
        R1 = 1.0;
    else
        R1 = -1.0;
    printf("\n INPUT COEFFICIENTS OF ECONOMIC FUNCTION:\n");
    for (J = 1; J <= NV; J++) {
        printf("       #%d ? ", J); scanf("%lf", &R2);
        TS[1][J + 1] = R2 * R1;
    }
    printf("       Right hand side ? "); scanf("%lf", &R2);
    TS[1][1] = R2 * R1;
    for (I = 1; I <= NC; I++) {
        printf("\n CONSTRAINT #%d:\n", I);
        for (J = 1; J <= NV; J++) {
            printf("       #%d ? ", J); scanf("%lf", &R2);
            TS[I + 1][J + 1] = -R2;
        }
        printf("       Right hand side ? "); scanf("%lf", &TS[I + 1][1]);
    }
    printf("\n\n RESULTS:\n\n");
    for (J = 1; J <= NV; J++)  TS[0][J + 1] = J;
    for (I = NV + 1; I <= NV + NC; I++)  TS[I - NV + 1][0] = I;
}

如果需要，我还可以包括基准 table、公式和优化函数。

我想询问具体的技术，可以用来确保在给定一组系数和约束的情况下，C++ 程序returns 经济函数正确（稍后当数据输出到网络时，我将不得不实施额外的检查阶段，但当我到达它时我会穿过那座桥）。

（为了注明出处，我注意到上面的代码是由Jean-Pierre Moreau在1982年创建的。巧合的是，1982年恰好是我的出生年份，但现在这可能并不重要。）

Answer 1

要检查结果，您可以使用任何非线性优化方法（例如具有边界约束的拟牛顿法）。有很多数学包（Octave、MathLab、MathCAD、SciLab 等）可以为您提供帮助。如果您想通过程序代码获得解决方案，请尝试查看 MINPACK (https://en.wikipedia.org/wiki/MINPACK)

Answer 2

证明线性规划问题解的最优性实际上相当容易。您需要检查解决方案的原始可行性和双重可行性。这种对偶性的概念在任何关于单纯形法或一般线性规划的著作中都有解释。对于初学者：https://en.wikipedia.org/wiki/Linear_programming

Simplex（线性规划）计算输出的测试方法

Methods of testing Simplex (Linear Programming) calculation output

c++

testing

linear-programming

data-integrity

simplex-algorithm