diff options
-rw-r--r-- | packages/glpk/src/Numeric/LinearProgramming.hs | 41 |
1 files changed, 24 insertions, 17 deletions
diff --git a/packages/glpk/src/Numeric/LinearProgramming.hs b/packages/glpk/src/Numeric/LinearProgramming.hs index 25cdab2..5de8577 100644 --- a/packages/glpk/src/Numeric/LinearProgramming.hs +++ b/packages/glpk/src/Numeric/LinearProgramming.hs | |||
@@ -12,7 +12,8 @@ This module provides an interface to the standard simplex algorithm. | |||
12 | 12 | ||
13 | For example, the following LP problem | 13 | For example, the following LP problem |
14 | 14 | ||
15 | @maximize 4 x_1 - 3 x_2 + 2 x_3 | 15 | |
16 | maximize 4 x_1 - 3 x_2 + 2 x_3 | ||
16 | subject to | 17 | subject to |
17 | 18 | ||
18 | 2 x_1 + x_2 <= 10 | 19 | 2 x_1 + x_2 <= 10 |
@@ -20,40 +21,46 @@ subject to | |||
20 | 21 | ||
21 | and | 22 | and |
22 | 23 | ||
23 | x_i >= 0@ | 24 | x_i >= 0 |
25 | |||
24 | 26 | ||
25 | can be solved as follows: | 27 | can be solved as follows: |
26 | 28 | ||
27 | @import Numeric.LinearProgramming | 29 | @ |
30 | import Numeric.LinearProgramming | ||
28 | 31 | ||
29 | prob = Maximize [4, -3, 2] | 32 | prob = Maximize [4, -3, 2] |
30 | 33 | ||
31 | constr1 = Sparse [ [2\#1, 1\#2] :<=: 10 | 34 | constr1 = Sparse [ [2\#1, 1\#2] :<=: 10 |
32 | , [1\#2, 5\#3] :<=: 20 | 35 | , [1\#2, 5\#3] :<=: 20 |
33 | ] | 36 | ] |
37 | @ | ||
38 | |||
39 | >>> simplex prob constr1 [] | ||
40 | Optimal (28.0,[5.0,0.0,4.0]) | ||
34 | 41 | ||
35 | \> simplex prob constr1 [] | ||
36 | Optimal (28.0,[5.0,0.0,4.0])@ | ||
37 | 42 | ||
38 | The coefficients of the constraint matrix can also be given in dense format: | 43 | The coefficients of the constraint matrix can also be given in dense format: |
39 | 44 | ||
40 | @constr2 = Dense [ [2,1,0] :<=: 10 | 45 | @ |
46 | constr2 = Dense [ [2,1,0] :<=: 10 | ||
41 | , [0,1,5] :<=: 20 | 47 | , [0,1,5] :<=: 20 |
42 | ]@ | 48 | ] |
49 | @ | ||
43 | 50 | ||
44 | By default all variables are bounded as @x_i >= 0@, but this can be | 51 | By default all variables are bounded as @x_i >= 0@, but this can be |
45 | changed: | 52 | changed: |
46 | 53 | ||
47 | @\> simplex prob constr2 [ 2 :=>: 1, 3 :&: (2,7)] | 54 | >>> simplex prob constr2 [ 2 :>=: 1, 3 :&: (2,7)] |
48 | Optimal (22.6,[4.5,1.0,3.8]) | 55 | Optimal (22.6,[4.5,1.0,3.8]) |
49 | 56 | ||
50 | \> simplex prob constr2 [Free 2] | 57 | >>> simplex prob constr2 [Free 2] |
51 | Unbounded@ | 58 | Unbounded |
52 | 59 | ||
53 | The given bound for a variable completely replaces the default, | 60 | The given bound for a variable completely replaces the default, |
54 | so @0 <= x_i <= b@ must be explicitly given as @i :&: (0,b)@. | 61 | so @0 <= x_i <= b@ must be explicitly given as @i :&: (0,b)@. |
55 | Multiple bounds for a variable are not allowed, instead of | 62 | Multiple bounds for a variable are not allowed, instead of |
56 | @[i :=>: a, i:<=: b]@ use @i :&: (a,b)@. | 63 | @[i :>=: a, i:<=: b]@ use @i :&: (a,b)@. |
57 | 64 | ||
58 | -} | 65 | -} |
59 | 66 | ||
@@ -86,7 +93,7 @@ infixl 5 # | |||
86 | (#) = (,) | 93 | (#) = (,) |
87 | 94 | ||
88 | data Bound x = x :<=: Double | 95 | data Bound x = x :<=: Double |
89 | | x :=>: Double | 96 | | x :>=: Double |
90 | | x :&: (Double,Double) | 97 | | x :&: (Double,Double) |
91 | | x :==: Double | 98 | | x :==: Double |
92 | | Free x | 99 | | Free x |
@@ -149,28 +156,28 @@ extract sg sol = r where | |||
149 | 156 | ||
150 | obj :: Bound t -> t | 157 | obj :: Bound t -> t |
151 | obj (x :<=: _) = x | 158 | obj (x :<=: _) = x |
152 | obj (x :=>: _) = x | 159 | obj (x :>=: _) = x |
153 | obj (x :&: _) = x | 160 | obj (x :&: _) = x |
154 | obj (x :==: _) = x | 161 | obj (x :==: _) = x |
155 | obj (Free x) = x | 162 | obj (Free x) = x |
156 | 163 | ||
157 | tb :: Bound t -> Double | 164 | tb :: Bound t -> Double |
158 | tb (_ :<=: _) = glpUP | 165 | tb (_ :<=: _) = glpUP |
159 | tb (_ :=>: _) = glpLO | 166 | tb (_ :>=: _) = glpLO |
160 | tb (_ :&: _) = glpDB | 167 | tb (_ :&: _) = glpDB |
161 | tb (_ :==: _) = glpFX | 168 | tb (_ :==: _) = glpFX |
162 | tb (Free _) = glpFR | 169 | tb (Free _) = glpFR |
163 | 170 | ||
164 | lb :: Bound t -> Double | 171 | lb :: Bound t -> Double |
165 | lb (_ :<=: _) = 0 | 172 | lb (_ :<=: _) = 0 |
166 | lb (_ :=>: a) = a | 173 | lb (_ :>=: a) = a |
167 | lb (_ :&: (a,_)) = a | 174 | lb (_ :&: (a,_)) = a |
168 | lb (_ :==: a) = a | 175 | lb (_ :==: a) = a |
169 | lb (Free _) = 0 | 176 | lb (Free _) = 0 |
170 | 177 | ||
171 | ub :: Bound t -> Double | 178 | ub :: Bound t -> Double |
172 | ub (_ :<=: a) = a | 179 | ub (_ :<=: a) = a |
173 | ub (_ :=>: _) = 0 | 180 | ub (_ :>=: _) = 0 |
174 | ub (_ :&: (_,a)) = a | 181 | ub (_ :&: (_,a)) = a |
175 | ub (_ :==: a) = a | 182 | ub (_ :==: a) = a |
176 | ub (Free _) = 0 | 183 | ub (Free _) = 0 |
@@ -188,7 +195,7 @@ mkBounds n b1 b2 = fromLists (cb++vb) where | |||
188 | | otherwise = error $ "simplex: duplicate bounds for vars " ++ show (gv'\\nub gv') | 195 | | otherwise = error $ "simplex: duplicate bounds for vars " ++ show (gv'\\nub gv') |
189 | rv | null gv || minimum gv >= 0 && maximum gv <= n = [1..n] \\ gv | 196 | rv | null gv || minimum gv >= 0 && maximum gv <= n = [1..n] \\ gv |
190 | | otherwise = error $ "simplex: bounds: variables "++show gv++" not in 1.."++show n | 197 | | otherwise = error $ "simplex: bounds: variables "++show gv++" not in 1.."++show n |
191 | vb = map snd $ sortBy (compare `on` fst) $ map (mkBound2 . (:=>: 0)) rv ++ map mkBound2 b2 | 198 | vb = map snd $ sortBy (compare `on` fst) $ map (mkBound2 . (:>=: 0)) rv ++ map mkBound2 b2 |
192 | cb = map mkBound1 b1 | 199 | cb = map mkBound1 b1 |
193 | 200 | ||
194 | mkConstrD :: Int -> [Double] -> [Bound [Double]] -> Matrix Double | 201 | mkConstrD :: Int -> [Double] -> [Bound [Double]] -> Matrix Double |