diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/gui/graphicsview/qsimplex_p.cpp | 96 | ||||
-rw-r--r-- | src/gui/graphicsview/qsimplex_p.h | 7 |
2 files changed, 99 insertions, 4 deletions
diff --git a/src/gui/graphicsview/qsimplex_p.cpp b/src/gui/graphicsview/qsimplex_p.cpp index b3997fa..86b10b4 100644 --- a/src/gui/graphicsview/qsimplex_p.cpp +++ b/src/gui/graphicsview/qsimplex_p.cpp @@ -146,6 +146,13 @@ bool QSimplex::setConstraints(const QList<QSimplexConstraint *> newConstraints) constraints << c; } + // Remove constraints of type Var == K and replace them for their value. + if (!simplifyConstraints(&constraints)) { + qWarning() << "QSimplex: No feasible solution!"; + clearDataStructures(); + return false; + } + /////////////////////////////////////// // Prepare variables and constraints // /////////////////////////////////////// @@ -515,11 +522,21 @@ qreal QSimplex::solver(solverFactor factor) // Remove old objective clearRow(0); - // Set new objective + // Set new objective in the first row of the simplex matrix + qreal resultOffset = 0; QHash<QSimplexVariable *, qreal>::const_iterator iter; for (iter = objective->variables.constBegin(); iter != objective->variables.constEnd(); ++iter) { + + // Check if the variable was removed in the simplification process. + // If so, we save its offset to the objective function and skip adding + // it to the matrix. + if (iter.key()->index == -1) { + resultOffset += iter.value() * iter.key()->result; + continue; + } + setValueAt(0, iter.key()->index, -1 * factor * iter.value()); } @@ -532,7 +549,9 @@ qreal QSimplex::solver(solverFactor factor) } #endif - return factor * valueAt(0, columns - 1); + // Return the value calculated by the simplex plus the value of the + // fixed variables. + return (factor * valueAt(0, columns - 1)) + resultOffset; } /*! @@ -578,4 +597,77 @@ void QSimplex::collectResults() } } +/*! + \internal + + Looks for single-valued variables and remove them from the constraints list. +*/ +bool QSimplex::simplifyConstraints(QList<QSimplexConstraint *> *constraints) +{ + QHash<QSimplexVariable *, qreal> results; // List of single-valued variables + bool modified = true; // Any chance more optimization exists? + + while (modified) { + modified = false; + + // For all constraints + QList<QSimplexConstraint *>::iterator iter = constraints->begin(); + while (iter != constraints->end()) { + QSimplexConstraint *c = *iter; + if ((c->ratio == QSimplexConstraint::Equal) && (c->variables.count() == 1)) { + // Check whether this is a constraint of type Var == K + // If so, save its value to "results". + QSimplexVariable *variable = c->variables.constBegin().key(); + qreal result = c->constant / c->variables.value(variable); + + results.insert(variable, result); + variable->result = result; + variable->index = -1; + modified = true; + + } + + // Replace known values among their variables + QHash<QSimplexVariable *, qreal>::const_iterator r; + for (r = results.constBegin(); r != results.constEnd(); ++r) { + if (c->variables.contains(r.key())) { + c->constant -= r.value() * c->variables.take(r.key()); + modified = true; + } + } + + // Keep it normalized + if (c->constant < 0) + c->invert(); + + if (c->variables.isEmpty()) { + // If constraint became empty due to substitution, delete it. + if (c->isSatisfied() == false) + // We must ensure that the constraint soon to be deleted would not + // make the problem unfeasible if left behind. If that's the case, + // we return false so the simplex solver can properly report that. + return false; + + delete c; + iter = constraints->erase(iter); + } else { + ++iter; + } + } + } + + return true; +} + +void QSimplexConstraint::invert() +{ + constant = -constant; + ratio = Ratio(2 - ratio); + + QHash<QSimplexVariable *, qreal>::iterator iter; + for (iter = variables.begin(); iter != variables.end(); ++iter) { + iter.value() = -iter.value(); + } +} + QT_END_NAMESPACE diff --git a/src/gui/graphicsview/qsimplex_p.h b/src/gui/graphicsview/qsimplex_p.h index 5ec13c3..66ea739 100644 --- a/src/gui/graphicsview/qsimplex_p.h +++ b/src/gui/graphicsview/qsimplex_p.h @@ -63,7 +63,7 @@ struct QSimplexVariable QSimplexVariable() : result(0), index(0) {} qreal result; - uint index; + int index; }; @@ -95,7 +95,8 @@ struct QSimplexConstraint QPair<QSimplexVariable *, qreal> helper; QSimplexVariable * artificial; -#ifdef QT_DEBUG + void invert(); + bool isSatisfied() { qreal leftHandSide(0); @@ -119,6 +120,7 @@ struct QSimplexConstraint } } +#ifdef QT_DEBUG QString toString() { QString result; result += QString::fromAscii("-- QSimplexConstraint %1 --").arg(int(this), 0, 16); @@ -167,6 +169,7 @@ private: void combineRows(int toIndex, int fromIndex, qreal factor); // Simplex + bool simplifyConstraints(QList<QSimplexConstraint *> *constraints); int findPivotColumn(); int pivotRowForColumn(int column); void reducedRowEchelon(); |