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