Linear programming

1. Linear programming

Great work handling constraints. We've had a taste of linear constrained optimization problems, now it's time to look at linear programming.

2. Linear programming

In linear programming both the objective functions and the constraints have a linear relationship. As opposed to linear constrained optimization where we may find a mix of linear or nonlinear elements.

3. Product mix

Let's imagine a factory that works with two types of machines, A and B, to create food-safe containers. It has 4 of machine A and 3 of machine B and all can operate for 30 hours per week. There is demand to create bottles for drinks and cups for yogurt.

4. Maximize profit

Our optimization problem is to maximize profit. B is the quantity of bottles and C is the quantity of cups. Our profit per box of bottles and cups is 480 and 510 dollars, respectively. This is our objective function. Bottles require machine A to run 1.5 hours per box, and cups need machine A for 1.3 hours. Given the limit of 30 hours per week and 4 units of machine A, our constraint for bottles is 4 times 30. The same reasoning yields the constraint for machine B. We also include a non-negativity constraint, since we can't produce negative units.

5. Using PuLP

It's time to solve. We will use PuLP, a Python library for linear optimization. It is more intuitive than SciPy as we don't need to negate any functions here. We start by importing the PuLP module. Next we define a model. To do that, we use the constructor LpProblem that takes two arguments. The first is a string, the name of the model. The second, set here to be LpMaximize, indicates whether the problem is a minimization or a maximization. Next, we define the variables. The quickest way is with the constructor LpVariable, providing a name for the variable. Here, we create B and C. Note we set lowBound=0 to indicate the variables are non-negative. Next, the objective. We use += to add the objective to the model information. To add the constraints, we provide the formulas followed by a comma and string that is the constraint name, M for machine and the A or B for the machine type.

6. PuLP model output

To verify the model is defined as intended, we print it and inspect the output. PuLP defines the model we wanted! Now let's look at solving.

7. Solving with PuLP

To find the solution, we type model.solve(). Printing the full status will result in a large output, which we haven't shown here for brevity. The important part is the number at the bottom. If the number is 1 then we have a solution. Finally, to get the optimal values for the problem we use value on model.objective and call .varValue on each variable. To maximize our profit to just over 40 thousand dollars, we need to make approximately 63 boxes of bottles and 18 boxes of cups.

8. Handling multiple variables and constraints

An efficient approach when dealing with multiple variables and constraints is to use vectors, matrices, and list comprehensions. Looking at the same bottles and cups problem, we'll define a variables in one go with a vector of 2 elements using LpVariable.dicts(). The first argument is the name, the second argument is the dimension, a range of 2 for the two elements or the string variables as a list, and the third argument is the lower bound for any element, our non-negativity constraint. LpVariable.matrix() can also be used depending on the variables. The syntax to define a 2-by-2 matrix is provided and saved as the variable A. Note that the lists range(2), range(2) are themselves in parentheses. We can then use list comprehension and LpSum to define the objective function. This may seem longer for two variables, but would save time if we had many more! The constraints can be defined the similarly using variables B and C.

9. Let's practice!

Let's practice!

Create Your Free Account

By continuing, you accept our Terms of Use, our Privacy Policy and that your data is stored in the USA.