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.