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

Question

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

Answer 1

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

Answer 2

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