Engineering Python 18B: Linear Programming using PuLP


Welcome to Engineering Python. This is a Python programming course for engineers. In this video, I’ll talk about how to use
PuPL to solve Linear Programming problems. Linear programming (LP) is a method to find
the best outcome, such as the maximum profit or the minimum cost, in a mathematical model
represented by linear relationships. Each Linear programming problem consists of
the following components. An objective function, which is a linear function
we wish to maximize or minimize. Decision variables or control variables, which
are controllable variables that influence the objective function. Constraints, which are a set of linear restrictions
on the decision variables. We will use this example that involves chairs
and tables to demonstrate how to model and solve linear programming problems. This is a modified version of the Giapetto’s
Woodcarving problem in Wayne Winston’s textbook, Operations Research: Applications and Algorithms. A company named Giapetto manufactures two
types of furniture: chairs and tables. The manufacturer wants to maximize their weekly
profit. Each chair will bring in $20 of profit. Each table will bring in $30 of profit. A chair requires 1 hour of finishing labor
and 2 hours of carpentry labor. A table requires 2 hours of finishing labor
and 1 hour of carpentry labor. Each week, Giapetto has only 100 finishing
hours and 100 carpentry hours available. To build the model, we need to introduce two
decision variables, x1 and x2. They are the numbers of chairs and tables
produced each week. The objective function is the profit. z is equal to 20 dollars per chair times the
number of chairs plus 30 dollars per table times the number of tables. st means subject to. The first constraint is the finishing hours. The total finishing hours for the chairs and
the tables should be less than or equal to 100. The second constraint is the carpentry hours. The total carpentry hours for the chairs and
the tables should be less than or equal to 100. Both numbers should be greater than or equal
to 0. We cannot make a negative number of chairs
or tables. Next, we need to implement the model in Python
using PuLP. PuLP is a Linear Programming modeler written
in Python. It uses Linear Programming solvers such as
CPLEX and GUROBI to solve the formulated problems. PuLP is not automatically installed with Anaconda. To install PuLP, in a Command Prompt, type
in the following: pip install pulp. After the installation, we import everything
from pulp. This block of code will create the linear
programming model. The first statement uses the LpProblem function
to create a maximization problem named Giapetto. The second statement creates the decision
variable x1. It’s lower bound is 0. The third line creates the decision variable
x2. It’s lower bound is also 0. Next, we add the objective function to this
problem. It’s 20 times x1 plus 30 times x2. Then, we add the two constraints. This is the finishing constraint, and this
is the carpentry constraint. At the end, we display the LP problem we just
created to check if it’s what we wanted. Giapetto is the name of the problem. This is a maximization problem. This is the objective function. It’s subject to constraint 1 and constraint
2. We have two variables x1 and x2. By default, these two variables are continuous
non-negative numbers. This is a correct model. Now we solve this model with the default solver
using the problem’s solve method. We print out the solution status. When we see the word Optimal, we know the
optimal solution is found. The value function will show the optimal solution:
x1, x2, and the objective function’s value. It turns out, we should make 33.33 chairs,
33.33 tables, and the highest possible weekly profit is 1666.66 dollars. We can also plot the feasible region of this
linear programming problem. This program is titled giapetto_feasible.py. I’ll not explain the source code in detail. I’ll just explain this figure generated by
the program. The horizontal axis is x1 and the vertical
axis is x2. This blue line is the finishing constraint. Feasible points are below this line. This orange line is the carpentry constraint. Feasible points are below this line as well. This green line is the sign restriction for
x1. Feasible points are on the right side of this
line. This red line is the sign restriction for
x2. Feasible points are above this line. The intersection of these feasible points
is this blue shaded area. This is the feasible region. According to the simplex method, the optimal
solution is one of these four corner points. It turns out this is the optimal point. x1 is 33.33, x2 is 33.33, and the objective
function at this point is 1666.66 dollars. In reality, we cannot make 33.33 chairs or
tables. So, both x1 and x2 must be integer numbers. We change the original model to this integer
linear programming model. x1 and x2 must both be integers. In this program, we need to specify that the
category of x1 is Integer. We do the same for x2. This is the formulated problem. We see that x1 and x2 are now both integers. After we solve the problem, the optimal solution
is x1 is 32 chairs, x2 is 34 tables. The total profit is 1660 dollars. Note the Integer Linear Programming problem
solution is not just the rounded solutions of the continuous Linear Programming solution,
33 chairs, 33 tables, and 1650 dollars. There is actually another way of solving this
small-scale integer linear programming problem. We can check every integer data point in the
feasible region and compare the corresponding objective function. The optimal solution is the data point that
will give the largest objective function value. This algorithm is implemented in giapetto_colormap.py. Again, I will not explain the source code. I leave it to you for practice. I’ll just explain this figure generated by
the program. In this figure, the value of each data point
is color coded. Dark red means large values, and dark blue
means small values. The optimal point is located in this region
near the intersection of the finishing constraint and the carpentry constraint. Let’s zoom in and move it to a different location
so there is no overlapping. The optimal solution is this point, x1 is
32 and x2 is 34. PuLP is not the only optimization package
in Python. You can also check pyOpt, another Python-based
object-oriented package that is capable of solving nonlinearly constrained problems. If you are interested in learning more about
Operations Research, you can watch my Operations Research Open Course on YouTube. This is a comprehensive introduction to optimization
theory and applications. The topics include Linear Programming, Nonlinear
Programming, Decision Making, Game Theory, Inventory Theory, Markov Chains, Dynamic Programming,
Queuing Theory, and many more. Okay, that was how to use PuPL to solve Linear
Programming problems. The course materials are available on YouTube
and GitHub. You can watch the course videos in sequence. If you like this video, please subscribe and
share. I’m Yong Wang. Thanks for watching.

Leave a Reply

Your email address will not be published. Required fields are marked *