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.