Мне было поручено создать веб-машину для решения реальных задач с использованием методов линейного программирования, в частности, в настоящее время, симплекс-метода Данцига. Имея это в виду, я нашел довольно изящный кусочек кода 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;
}
Я также могу при необходимости включить сводную таблицу, функции формулирования и оптимизации.
Я хотел бы попросить конкретные методы, которые могут быть использованы для обеспечения того, чтобы при заданном наборе коэффициентов и ограничений программа C ++ правильно возвращала экономическую функцию (Мне придется реализовать дополнительные этапы проверки позже, когда данные поступят в Интернет, но я перейду этот мост, когда приду к нему).
(Из соображений авторства отмечу, что приведенный выше код был создан Жаном-Пьером Моро в 1982 году. По совпадению, 1982 год — мой год рождения, но сейчас это, вероятно, не важно.)
Доказательство оптимальности решения задачи линейного программирования на самом деле довольно легко. Вам необходимо проверить решение на предмет первичной и двойной выполнимости. Эта концепция двойственности объясняется в любой работе о симплекс-методе или линейном программировании в целом. Для начинающих: https://en.wikipedia.org/wiki/Linear_programming
Для проверки результатов вы можете использовать любой нелинейный метод оптимизации (например, Квазиньютон с ограничениями границ). Существует множество математических пакетов (Octave, MathLab, MathCAD, SciLab и т. Д.), Которые могут вам помочь. Если вы хотите получить решение по коду программы, попробуйте посмотреть на MINPACK (https://en.wikipedia.org/wiki/MINPACK)