Методы тестирования результатов расчета Simplex (Linear Programming)

Мне было поручено создать веб-машину для решения реальных задач с использованием методов линейного программирования, в частности, в настоящее время, симплекс-метода Данцига. Имея это в виду, я нашел довольно изящный кусочек кода 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 год — мой год рождения, но сейчас это, вероятно, не важно.)

0

Решение

Доказательство оптимальности решения задачи линейного программирования на самом деле довольно легко. Вам необходимо проверить решение на предмет первичной и двойной выполнимости. Эта концепция двойственности объясняется в любой работе о симплекс-методе или линейном программировании в целом. Для начинающих: https://en.wikipedia.org/wiki/Linear_programming

0

Другие решения

Для проверки результатов вы можете использовать любой нелинейный метод оптимизации (например, Квазиньютон с ограничениями границ). Существует множество математических пакетов (Octave, MathLab, MathCAD, SciLab и т. Д.), Которые могут вам помочь. Если вы хотите получить решение по коду программы, попробуйте посмотреть на MINPACK (https://en.wikipedia.org/wiki/MINPACK)

0

По вопросам рекламы [email protected]