I have been tasked with created a web-based machine for solving real-world issues using Linear Programming techniques, specifically at present, Danzig's Simplex Method. With this in mind I've found a rather nifty bit of C++ code that calculates the results, and with some considerable speed even on this particularly low-end machine.
However, I currently have nothing other than the console output itself attesting the result to be anywhere close to the correct solution for the given problem. Which is an issue if people are being asked to trust the result as being indicative of anything significantly more important than that some digits can be made to flash up on a computer screen.
I will spare you from the full details of the entire program, as it's fairly long, but here's the function responsible for taking the data, just for reference:
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;
}
I can also include the pivot table, formulation and optimisation functions if need be.
I would like to ask for specific techniques which might be employed to ensure that, given a set of coefficients and constraints, the C++ program returns the economic function correctly (I'll have to implement additional checking stages later when the data gets output to the web, but I'll cross that bridge when I come to it).
(For reasons of attribution, I note that the above code was created by Jean-Pierre Moreau in 1982. Coincidentally, 1982 happens to be my birth year, but that's probably not important right now.)
Proving the optimality of a solution to a linear programming problem is actually fairly easy. You need to check the solution for both primal and dual feasibility. This concept of duality is explained in any work about the simplex method or linear programming in general. For starters: https://en.wikipedia.org/wiki/Linear_programming