]>
gitweb.michael.orlitzky.com - dead/census-tools.git/blob - bin/linear_programs/midatl
4 Solve an example problem with lp_solve.
7 from math
import acos
, sin
, cos
12 # Basically, add '../src' to our path.
13 # Needed for the imports that follow.
14 site
.addsitedir(os
.path
.dirname(os
.path
.abspath(sys
.argv
[0])) + '/../../src')
16 import LinearProgramming
19 class Facility(object):
21 def __init__(self
, fac_id
, fac_capacity
, fac_latitude
, fac_longitude
):
23 self
.capacity
= fac_capacity
24 self
.latitude
= fac_latitude
25 self
.longitude
= fac_longitude
27 def distance(self
, other_facility
):
28 return 3963.0 * acos(sin(self
.latitude
/57.2958) * sin(other_facility
.latitude
/57.2958) + cos(self
.latitude
/57.2958) * cos(other_facility
.latitude
/57.2958) * cos(other_facility
.longitude
/57.2958 - self
.longitude
/57.2958))
31 class Consumer(Facility
):
32 def __init__(self
, fac_id
, fac_capacity
, fac_latitude
, fac_longitude
):
33 super(Consumer
, self
).__init
__(fac_id
,
38 class Producer(Facility
):
39 def __init__(self
, fac_id
, fac_capacity
, fac_latitude
, fac_longitude
):
40 super(Producer
, self
).__init
__(fac_id
,
45 f
= open('midatl.csv', 'r')
46 f
.readline() # Skip the header
55 fac_capacity
= float(row
[2])
56 fac_latitude
= float(row
[3])
57 fac_longitude
= float(row
[4])
60 c
= Consumer(fac_id
, fac_capacity
, fac_latitude
, fac_longitude
)
63 p
= Producer(fac_id
, fac_capacity
, fac_latitude
, fac_longitude
)
68 lp
= LinearProgramming
.LinearProgram()
70 # Loop through the consumer/producer pairs, calculating costs
71 # (distances) and adding them to the array of objective function
73 lp
.objective_coefficients
= []
75 for c_idx
in range(0, len(consumers
)):
76 for p_idx
in range(0, len(producers
)):
77 distance
= consumers
[c_idx
].distance(producers
[p_idx
])
78 lp
.objective_coefficients
.append(distance
)
81 num_cols
= len(lp
.objective_coefficients
)
83 lp
.constraint_matrix
= []
87 for c_idx
in range(0, len(consumers
)):
88 demand
= consumers
[c_idx
].capacity
91 lp
.inequalities
.append(LinearProgramming
.GE
)
93 demand_row
= [0]*num_cols
94 offset
= c_idx
* len(producers
)
95 for idx
in range(0, len(producers
)):
96 demand_row
[offset
+idx
] = 1
98 lp
.constraint_matrix
.append(demand_row
)
100 for p_idx
in range(0, len(producers
)):
101 supply
= producers
[p_idx
].capacity
102 lp
.rhs
.append(supply
)
104 lp
.inequalities
.append(LinearProgramming
.LE
)
106 supply_row
= [0]*num_cols
108 for idx
in range(0,len(consumers
)):
109 offset
= p_idx
+ len(producers
)*idx
110 supply_row
[offset
] = 1
111 lp
.constraint_matrix
.append(supply_row
)
113 lp
.type = LinearProgramming
.MINIMIZE
115 [v
,x
,duals
] = lp
.solve()
117 print 'Optimal objective function value: ', v
118 print 'Optimal solution vector: ', x