Linear Programming Tutorial With Python Example

This would be a practical tutorial providing a step by step way to solve a given linear programming program using Python. So normally, you will be expected to find the values of certain variables that would maximize or minimize a function called the cost function (objective function).

Let’s take a typical example:

1. Example – Simplified Diet Problem
2. Solution Using Python

1. Example – Simplified Diet Problem

Find the number of units of each category of food that would minimize the total cost of the food but meet the daily nutrient requirements.

• The five foods are: Apples, Bananas, Carrots, Dates and Eggs
• The nutrients are: Protein, Vitamin C, Iron

According to Kindson in this video, to be to model this problem you need to determine 4 things, namely:

1. the variables
2. the goal of the problem (either minimization or maximization)
3. the cost function
4. the constraints

So let’s determine these things:

the variables (or unknowns)

Since we need to find quantity of each food, we can represent the variables as the first letter of each food. So let’s call them A, B, C, D, E

the goal of the problem (either minimization or maximization)

This is clearly indicated in the problem we want to minimize the cost. Therefor the goal is minimization

the cost function

Since we know the variables, the cost function is a function of the variables ie f(A, B, C, D, E). Since we know the cost per unit(the last column, we simply multiply each food by the unit cost. Therefore we have

f(A, B, C, D, E) = 8A + 10B + 3C + 20D + 15E

the constraints

We are given the minimum daily requirement (the last row), so we multiply the nutrient per unit with the each food and make sure it is greater than or equal to the min. daily requirement. So we have 3 constraints:

• Protein:        0.4A + 1.2B + 0.6C + 0.6D + 12.2E >= 70
• Vitamin C:   6A + 10B + 3C + D >= 50
• Iron:             0.4A + 0.6B + 0.4C + 0.2D + 2.6E >= 12
• A, B, C, D, E >= 0

In summary, we are expected to find minimum of f(A, B, C, D, E) subject to the 4 constraints.

2. Solution with Python

We can easily solve this problem in Python following 6 simple steps. Also note that to be able to use the linear_solver, you must have ortools installed (using pip install ortools)

1. import the necessary modules

# import modules
from ortools.linear_solver import pywraplp

2. declare a linear programming solver

# create solver
solver = pywraplp.Solver.CreateSolver('GLOP')

3. create the variables

# Create your variables
a = solver.NumVar(0, solver.infinity(), 'a')
b = solver.NumVar(0, solver.infinity(), 'b')
c = solver.NumVar(0, solver.infinity(), 'c')
d = solver.NumVar(0, solver.infinity(), 'd')
e = solver.NumVar(0, solver.infinity(), 'e')

4. define the constraints

# Create your constraints
solver.Add(0.4*a + 1.2*b + 0.6*c + 0.6*d + 12.2*e >= 70)
solver.Add(6*a + 10*b + 3*c + d >= 50)
solver.Add(0.4*a + 0.6*b + 0.4*c + 0.2*d + 2.6*e >= 12)
print('Constraints =', solver.NumConstraints())

5. define your cost function (objective function)

# Pass the cost function
solver.Minimize(8*a + 10*b + 3*c + 20*d + 15*e)

6. call the solver and print out your results

#Call the Solver
solver.Solve()

# print out the values
print('Objective value =', solver.Objective().Value())
print('A = ', a.solution_value())
print('B = ', b.solution_value())
print('C = ', c.solution_value())
print('D = ', d.solution_value())
print('E = ', e.solution_value())

Watch the Linear Programming Video