Copyright | (c) Alberto Ruiz 2010 |
---|---|
License | GPL |
Maintainer | Alberto Ruiz |
Stability | provisional |
Safe Haskell | None |
Language | Haskell98 |
This module provides an interface to the standard simplex algorithm.
For example, the following LP problem
maximize 4 x_1 - 3 x_2 + 2 x_3 subject to
2 x_1 + x_2 <= 10
x_2 + 5 x_3 <= 20
and
x_i >= 0
can be solved as follows:
import Numeric.LinearProgramming prob = Maximize [4, -3, 2] constr1 = Sparse [ [2#1, 1#2] :<=: 10 , [1#2, 5#3] :<=: 20 ]
>>>
simplex prob constr1 []
Optimal (28.0,[5.0,0.0,4.0])
The coefficients of the constraint matrix can also be given in dense format:
constr2 = Dense [ [2,1,0] :<=: 10 , [0,1,5] :<=: 20 ]
Note that when using sparse constraints, coefficients cannot appear more than once in each constraint. You can alternatively use General which will automatically sum any duplicate coefficients when necessary.
constr3 = General [ [1#1, 1#1, 1#2] :<=: 10 , [1#2, 5#3] :<=: 20 ]
By default all variables are bounded as x_i >= 0
, but this can be
changed:
>>>
simplex prob constr2 [ 2 :>=: 1, 3 :&: (2,7)]
Optimal (22.6,[4.5,1.0,3.8])
>>>
simplex prob constr2 [Free 2]
Unbounded
The given bound for a variable completely replaces the default,
so 0 <= x_i <= b
must be explicitly given as i :&: (0,b)
.
Multiple bounds for a variable are not allowed, instead of
[i :>=: a, i:<=: b]
use i :&: (a,b)
.
- simplex :: Optimization -> Constraints -> Bounds -> Solution
- exact :: Optimization -> Constraints -> Bounds -> Solution
- sparseOfGeneral :: Constraints -> Constraints
- data Optimization
- data Constraints
- type Bounds = [Bound Int]
- data Bound x
- (#) :: Double -> Int -> (Double, Int)
- data Solution
Documentation
simplex :: Optimization -> Constraints -> Bounds -> Solution Source #
exact :: Optimization -> Constraints -> Bounds -> Solution Source #
Simplex method with exact internal arithmetic. See glp_exact in glpk documentation for more information.
sparseOfGeneral :: Constraints -> Constraints Source #
Convert a system of General constraints to one with unique coefficients.
data Constraints Source #