Nature runs on two important concepts, Systems and Optimization. This can be seen in almost every aspect of life. God operates the world using systems and optimization. By these concepts most problems can be solved. In this tutorial we will pick the concept of optimization and narrow it down a bit.
So what is optimization?
Optimization, refers the act of making the most out of something or doing the most with less.
What then is the Purpose of Optimization and what are the benefits?
The main purpose of optimization is to obtain the best result or output from a given input relative to a set of constraints – that is either maximizing a profit or minimizing a cost/loss.
The benefits of optimization are enormous. These include maximizing certain factors such as productivity,efficiency,longevity,profitability,etc
Optimization just like systems saves ourselves a lot of time and energy when dealing with problems. Based on these two we can classify how we solve problems by either defining the problem as a systems problem or optimization problem.
Since we are talking about optimizationi in this article,we will shift our attention to optimization problems.
What is an optimization problem?
An Optimization Problem is the problem of finding the best solution from all feasible solutions. An optimization problem consists of maximizing or minimizing a real function by systematically choosing input values from within an allowed set and computing the value of the function.
Types of Optimization Problems
There are various ways we can classify an optimization problem. Some of them include the following.
- Type of variables
- Continuous Optimization Problem(with continuous variable)
- Discrete Optimization Problem ( with discrete variables)
- Convex or Non Convex
- Linear or Non Linear Optimization Problem
There are different forms of optimization techniques among them include linear optimization or linear programming,machine learning,etc .
Not every problem can be solved with linear optimization, there are problems that can be solved with other techniques such as ML or Mixed Integer Linear Programming, Non-Linear Programming,Dynamic Programming and the rest.
Let us move on to what linear programming is.
As we already learnt, linear programming is a form of optimization. It is a method used to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships.
So how do you know if a problem is linear/identifying linearity?
First of all,most problems that have these two features can be classified as a linear problem and requires linear optimization to solve them.
- Proportionality: how each variable contributes to the objective function or constraints must be proportional to the value of the variable
- Additivity:The value of an objective function or constraint function is the sum of the contributions of each variable.( fxn = sum(variables))
Let us define some basic terms used in linear programming
- Objective Variables
- Decision Variables:they are the variables which will decide my output, what q
- Objective Function:the objective/goal of making decisions, what we want to achieve (maximize/minimize)
- Constraints:the restrictions or limitations on the decision variables. They usually limit the value of the decision variables.They shape how you obtain the objective.
- Non-negativity restriction: For all linear programs, the decision variables should always take non-negative values. Which means the values for decision variables should be greater than or equal to 0.
Steps For Solving Linear Optimization Problem
- Define Objective Variables and Decision Variables
- Create Objective Functions
- Define Constraints
Okay let us move beyond the theory part and see how to do linear programming in code. Most programming languages have their own libraries and packages for performing linear programming, and in our case we will be using these Python packages
Julia also have a nice package for optimization know as JuMP which we will discuss later in the future.
Introduction to Linear Programming with Pulp
Pulp is a powerful python library for linear programming or optimization. It makes it easier to find the optimal solution when given a linear problem. Once the objective function ,decision variables and constraints have been defined it is quite easy to use Pulp to get the optimal solution and their respective variables.
Let us see how to work with Pulp
pip install pulp
As we learnt earlier, we will use the 3 steps to help us arrive at our solution. Let us apply it to this example.
A tech company makes two products (X and Y) using two machines (A and B). Each unit of X that is produced requires 50 minutes processing time on machine A and 30 minutes processing time on machine B. Each unit of Y that is produced requires 24 minutes processing time on machine A and 33 minutes processing time on machine B.
At the start of the current week there are 30 units of X and 90 units of Y in stock. Available processing time on machine A is forecast to be 40 hours and on machine B is forecast to be 35 hours. The demand for X in the current week is forecast to be 75 units and for Y is forecast to be 95 units. Company policy is to maximize the combined sum of the units of X and the units of Y in stock at the end of the week.
Formulate the problem of deciding how much of each product to make in the current week as a linear program.
Solve this linear problem.
Let us see how to solve this problem using our steps
Step 1 : Defining the Objective Variables
Let X be the unit of X products made and
Y be the unit of Y products made.
import pulp # Define Variables X = pulp.LpVariable('X',lowBound=0) Y = pulp.LpVariable('Y',lowBound=0)
Step 2: Create the Objective Function
Company policy is to maximize the combined sum of the units of X and the units of Y in stock at the end of the week. Hence we will have to sum all the unit of X produced from the start (30 unit) till the end of the week which was predicted to be 70 unit and then add that to the sum of all the unit of Y produced from the start of the week till the forecast stock (90 to 95). Hence we already know the forecast value of both X and Y so we can add them as
X + Y = (75-30) + (95-90)X + 45 + Y +5= X + Y -50
# Objective Fxns m = pulp.LpProblem("Maximum Profit",pulp.LpMaximize) m += X+Y-50
The += means that keep on adding the values of the variables till you get the optimal solution.
Step 3: Define the Constraints
From the case above we realize that there are certain constraints. One of the difficulties in linear programming is in how to identify the constraints and put them in an equation.
Machine A has only 40 hours and it takes 50 minutes to produce X (50*X)and 24 minutes to produce Y (24*Y) hence we can set that us our constraints for machine A and do likewise for machine B.
Since we have our time limit in hours we will convert it to minutes by multiplying by 60minutes.
# Constraints m += 50*X + 24*Y <= 40*60 m += 30*X + 33*Y <= 35*60 m += X >= 75 - 30 m += Y >= 95 - 90
You can also check for the entire problem to see a summary of what you have created and check for the status also.
# Get the status pulp.LpStatus[m.status]
Check the problem equations
Maximum_Profit: MAXIMIZE 1*X + 1*Y + -50 SUBJECT TO _C1: 50 X + 24 Y <= 2400 _C2: 30 X + 33 Y <= 2100 _C3: X >= 45 _C4: Y >= 5 VARIABLES X Continuous Y Continuous
After these you can rely on the power of Pulp to generate an optimal solution by calling solve() on the model created.
# Find the Optimal Variables/Optimal Solution Points for var in m.variables(): print(var.name,"=>",var.varValue)
X => 45.0 Y => 6.25
Alternatively you can get the optimal values using the varValue attribute on the variable you defined above after solving it.
Upon inserting these values into our initial objective function equation we will get our optimal number. But we can use pulp to help us do that by
# What you get when you plug in the X,Y into our objective function pulp.value(m.objective)
You can see from what we have learnt that pulp is quite powerful and accurate especially when you are able to define the objective function and the constraints.
You can check out this link for examples of linear problems and their solutions using pulp.
You can also check the video tutorial below.
Thanks For Your Attention
By Jesse E.Agbe(JCharis)