Linear.Simplex.Util

Helper functions for performing the two-phase simplex method.

Documentation

isMax :: ObjectiveFunction -> Bool

Is the given ObjectiveFunction to be Maximized?

getObjective :: ObjectiveFunction -> VarConstMap

Extract the objective (VarConstMap) from an ObjectiveFunction

simplifySystem :: [PolyConstraint] -> [PolyConstraint]

Simplifies a system of PolyConstraints by first calling simplifyPolyConstraint, then reducing LEQ and GEQ with same LHS and RHS (and other similar situations) into EQ, and finally removing duplicate elements using nub.

simplifyObjectiveFunction :: ObjectiveFunction -> ObjectiveFunction

Simplify an ObjectiveFunction by first sorting and then calling foldSumVarConstMap on the VarConstMap.

simplifyPolyConstraint :: PolyConstraint -> PolyConstraint

Simplify a PolyConstraint by first sorting and then calling foldSumVarConstMap on the VarConstMap.

foldSumVarConstMap :: [(Integer, Rational)] -> [(Integer, Rational)]

Add a sorted list of VarConstMaps, folding where the variables are equal

displayTableauResults :: Tableau -> [(Integer, Rational)]

Get a map of the value of every Integer variable in a Tableau

displayDictionaryResults :: DictionaryForm -> [(Integer, Rational)]

Get a map of the value of every Integer variable in a DictionaryForm

createObjectiveDict :: ObjectiveFunction -> Integer -> (Integer, VarConstMap)

Map the given Integer variable to the given ObjectiveFunction, for entering into DictionaryForm.

tableauInDictionaryForm :: Tableau -> DictionaryForm

Converts a Tableau to DictionaryForm. We do this by isolating the basic variable on the LHS, ending up with all non basic variables and a Rational constant on the RHS. (-1) is used to represent the rational constant.

dictionaryFormToTableau :: DictionaryForm -> Tableau

Converts a DictionaryForm to a Tableau. This is done by moving all non-basic variables from the right to the left. The rational constant (represented by the Integer variable -1) stays on the right. The basic variables will have a coefficient of 1 in the Tableau.

extractObjectiveValue :: Maybe (Integer, [(Integer, Rational)]) -> Maybe Rational

If this function is given Nothing, return Nothing. Otherwise, we lookup the Integer given in the first item of the pair in the map given in the second item of the pair. This is typically used to extract the value of the ObjectiveFunction after calling twoPhaseSimplex.