# Linear Programming in Python

I am going to solve a problem with linear programming in this tutorial. Linear programming (LP) is an optimization technique used to find the best solution to a problem by maximizing or minimizing an objective function with respect to constraints. LP is mainly used to in planning to achieve the best result given constraints.

LP is used in mathematics, business, economics and engineering, it is used for planning, routing, scheduling, assignment, and design. Linear programming assumes that a problem can be represented as a matematical model with linear relationships. A LP-problem is represented with an objective function, variables that can be modified and constraints. I am using Python and the `pulp` library in this tutorial.

## Production Planning

A company produces chairs, tables and stools. Through license agreements, the company has also been given the opportunity to manufacture a maximum of 1,200 shelves per month. Drying of painted furniture is a narrow section, you can only paint and dry a certain number of chairs, tables, stools and shelves per month. The goal is to find the optimal product mix to produce during each month.

I have structured and solved the problem in OpenOffice Calc. The factory has three operations (Plaining, Grinding and Drying) and a license constraint. I have standardized the resource claim for drying in order to get a normalized resource constraint for all products. The goal function is to maximize the total contribution margin (TCM), the sum of volume times the goal coefficient.

## Code

The code below shows an implementation of a linear programming solution to a production planning problem. The problem is created and solved with `pulp`, output from a run is shown below the code.

``````# Import libraries
import pulp

# The main entry point for this module
def main():

# Create a problem
# Either LpMinimize (default) or LpMaximize
problem = pulp.LpProblem('Maximize-TCM', pulp.LpMaximize)

# Products
products = ['Chair', 'Table', 'Stool', 'Shelf']

# Contribution margins
cm = {'Chair':12, 'Table':18, 'Stool':16, 'Shelf':30}

# Resource consumption
plaining = {'Chair':5, 'Table':10, 'Stool':12, 'Shelf':12}
grinding = {'Chair':6, 'Table':3, 'Stool':4, 'Shelf':5}
drying = {'Chair':1, 'Table':1.25, 'Stool':1, 'Shelf':2.5}
license = {'Chair':0, 'Table':0, 'Stool':0, 'Shelf':1}

# Create decision variables (values that can be modified by solver)
# Category: Integer, Binary or Continuous(default)
volume = pulp.LpVariable.dicts('Volume', products, lowBound=0, upBound=None, cat='Integer')

# Objective function
problem += pulp.lpSum([cm[i] * volume[i] for i in products])

# Constraints
problem += pulp.lpSum([plaining[i] * volume[i] for i in products]) <= 27000
problem += pulp.lpSum([grinding[i] * volume[i] for i in products]) <= 18000
problem += pulp.lpSum([drying[i] * volume[i] for i in products]) <= 5000
problem += pulp.lpSum([license[i] * volume[i] for i in products]) <= 1200

# Print problem
print(problem)

# Write problem data to an .lp file
problem.writeLP('plots\\production.lp')

# Solve the problem by using PuLP's choice of Solver
problem.solve()

# Print the status of the solution
print('Status: {0}\n'.format(pulp.LpStatus[problem.status]))

# Print each variable with optimal value
print('Volumes')
for v in problem.variables():
print(v.name, "=", v.varValue)
print()

# Print the optimal goal value
print('Total Contribution Margin (TCM) = {0}\n'.format(pulp.value(problem.objective)))

# Tell python to run main method
if __name__ == '__main__': main()``````

## Output

``````Maximize-TCM:
MAXIMIZE
12*Volume_Chair + 30*Volume_Shelf + 16*Volume_Stool + 18*Volume_Table + 0
SUBJECT TO
_C1: 5 Volume_Chair + 12 Volume_Shelf + 12 Volume_Stool + 10 Volume_Table
<= 27000

_C2: 6 Volume_Chair + 5 Volume_Shelf + 4 Volume_Stool + 3 Volume_Table
<= 18000

_C3: Volume_Chair + 2.5 Volume_Shelf + Volume_Stool + 1.25 Volume_Table
<= 5000

_C4: Volume_Shelf <= 1200

VARIABLES
0 <= Volume_Chair Integer
0 <= Volume_Shelf Integer
0 <= Volume_Stool Integer
0 <= Volume_Table Integer

Status: Optimal

Volumes
Volume_Chair = 1132.0
Volume_Shelf = 1200.0
Volume_Stool = 0.0
Volume_Table = 694.0

Total Contribution Margin (TCM) = 62076.0``````
Tags: