Subjects
Grades
Solving an Optimization Problem
Concept sheet | Mathematics
Secondary
5
Table of contents
- Top of page
- Steps to Solve an Optimization Problem
- The Scanning Line
- Examples of Optimization Problems
- Special Cases
- The Optimal Vertex is Not On a Solid Line
- The Solution Must Have Coordinates That Are Integers
- The Solution Is One Side of the Polygon of Constraints
- There Is More Than One Function to be Optimized
- See Also
When solving an optimization problem, look for a solution that maximizes or minimizes the function to be optimized, which is defined according to an objective. This is done by respecting constraints that are represented by a system of inequalities. On the Cartesian plane, these inequalities form a polygon of constraints and one or more vertices of this polygon corresponds to the solution sought.
Steps to Solve an Optimization Problem
-
Identify the variables.
To determine the variables, we look for elements which may vary, and not the element being optimized. Problems that are studied in high school only ever contain 2 variables.
-
Translate the constraints into a system of inequalities.
Each constraint is associated with a single inequality. In addition, if the variables represent quantities that cannot be negative, non-negative constraints must be set so there are only positive values. Here is a table containing some expressions that are regularly found in constraints, as well as the inequalities they represent.
|
Symbol |
Expressions |
|---|---|
|
|x<y| |
“|x| is less than |y|,” “|x| is smaller than |y|,” “|x| is (strictly) less than |y|,” etc. |
|
|x\leq y| |
“|x| is less than or equal to |y|,” “|x| is smaller than or equal to |y|,” “|x| is a maximum of |y|,” “|x| is at most equal to |y|,” “|x| is not more than |y|,” etc. |
|
|x>y| |
“|x| is greater than |y|,” “|x| is more than |y|,” “|x| exceeds |y|,” “|x| is (strictly) greater than |y|,” etc. |
|
|x\geq y| |
“|x| is greater than or equal to |y|,” “|x| is a minimum of |y|,” “|x| is at least equal to |y|,” “|x| is at least as much as |y|,” etc. |
-
Establish the rule of the function to be optimized |\boldsymbol{(z).}|
The rule of the function to be optimized can be written as |z=ax+by+c,| where |x| and |y| are the problem’s variables and |z| represents the quantity to be maximized or minimized. It is common for |z| to represent cost or revenue. In these cases, it is possible to use another variable, like |C| or |R.|
-
Graph the polygon of constraints.
To do so, graph all the inequalities on the Cartesian plane. The polygon of constraints is the common region on the Cartesian plane determined by the intersection of the solution sets of all the inequalities.
-
Determine the coordinates of the vertices of the polygon of constraints.
To find the coordinates of a vertex, take the equations of the 2 boundary lines that form the vertex and solve the system of equations. To do this, use the comparison method, the substitution method or the elimination method.
-
Find the optimal vertex (using a table or a scanning line).
Replace |x| and |y| in the function to be optimized with the coordinates of each point found in the previous step. Creating a table to compile all the outcomes is helpful. A scanning line can be used to reduce the number of vertices that need to be evaluated. The different |z| values must be then analyzed to determine the most advantageous one according to the objective.
-
Give a complete answer.
To answer the question, write a complete sentence containing the |(x,y)| pair that maximizes or minimizes the function, as well as the |z| value associated with this pair.
The Scanning Line
The scanning line technique is a way of reducing the number of vertices to evaluate when finding the optimal solution.
The scanning line is a line with a slope of |-\dfrac{a}{b}| that ‘scans’ the Cartesian plane, where |a| and |b| are the parameters of the function to be optimized |(z=ax+by+c).|
When the scanning line is slid along the Cartesian plane, the first and last vertices of the polygon of constraints it touches are the points that will either minimize or maximize the situation.
In the animation below, you can change parameters |a| and |b| of the function to be optimized using the sliders. You can also move the vertices of the polygon of constraints and slide the scanning line. To do so, simply move the green dot placed on the scanning line. When the scanning line is moved, its slope will always stay the same.
Examples of Optimization Problems
Here is a complete example of an optimization problem. In this problem, the optimal solution is found using a table.
Melanie makes a living from her herd of |30| goats, each of which produces at most |20| litres of milk per week. She uses this milk to create |2| products that she sells at the market: yogurt and cream.
It takes |1.5\ \text{L}| of milk to make |1\ \text{L}| of yogurt. It also takes |6\ \text{L}| of milk to produce |1\ \text{L}| of cream.
Given the demand for her products, Melanie must produce at least |3| times more yogurt than cream and must produce at least |200\ \text{L}| of yogurt per week.
She sells her yogurt at the market for |\$36| per litre and her cream for |\$10| per litre.
How many litres of yogurt and litres of cream should Melanie produce per week to maximize her income?
See solution
In this 2nd example, a constraint was added. This means adding a new inequality that will change the polygon of constraints.
Victor sells skateboards. His professional skateboards cost |\ $300| and his standard skateboards cost |\ $50.| Due to his finances and the size of his store, he needs to respect certain constraints regarding the quantity of skateboards available in the store. The polygon below illustrates these constraints.
|x:| number of professional skateboards
|y:| number of standard skateboards
Victor wants to have a big sale next weekend. His sales consultant, John, suggests that he should have no more than |80| professional boards in stock at his store.
Should Victor follow John’s advice?
See solution
Special Cases
When finding an optimal solution for a situation, it is possible to encounter some special cases.
The Optimal Vertex is Not On a Solid Line
When the constraints have strict inequality symbols |<| or |>,| the lines themselves are not included in the solution set. The graph will indicate this using a dotted line. If the vertex that optimizes the function is located on one or more dotted lines, the solution must be rejected since it does not respect all of the constraints. Test the points near and around this vertex that are part of the solution set and then choose the best one.
The Solution Must Have Coordinates That Are Integers
Depending on the context, sometimes the values of |x| and |y| must be integers. This is the case when |x| and |y| represent, for example, a number of objects, a number of animals or a number of people. However, the coordinates of the vertices of the polygon of constraints are not necessarily integers. When this happens, choose the point that has integer coordinates, that is part of the solution set, and that optimizes the situation.
In the following example, vertex |A| and |B| do not have integer coordinates. If |A| is the vertex that optimizes the function |z,| then the point with integer coordinates that is the optimal solution and respects the context is either |(7,2)| or |(6,3).|
The Solution Is One Side of the Polygon of Constraints
Sometimes, 2 vertices of the polygon optimize the function and give the same |z| value. When this is the case, it means that all the points located on the segment connecting these two vertices are optimal solutions. Therefore, there are several possible answers.
In the following example, vertices |A(3,6)| and |C(-1,-1)| both maximize the function with a |z| value of |3.| So, all the points on the segment |\overline{AC}| maximize it as well. Point |D(0,0.75)| is proof because it also yields a |z| of |3.|
|
Vertex of the polygon |
Function rule to be optimized |
Value of |\boldsymbol{z}| |
|---|---|---|
|
|A(3,6)| |
|z=-7(3)+4(6)| |
|3| |
|
|B(4,-3)| |
|z=-7(4)+4(-3)| |
|-40| |
|
|C(-1,-1)| |
|z=-7(-1)+4(-1)| |
|3| |
|
|D(0, 0.75)| |
|z=-7(0)+4(0.75)| |
|3| |
There Is More Than One Function to be Optimized
When a situation has several optimal solutions, the context sometimes provides an additional function to be optimized. This eliminates some of the solutions and makes it possible to find the one that optimizes both functions.
In the following example, there are 2 functions to be optimized. Start by finding the solutions that maximize the quantity of supplies to transport. Among these solutions, determine the one that minimizes the purchase cost.
Supplies are transported for disaster victims in 2 types of containers: bags and crates.
The polygon below represents the constraints associated with the number of bags and the number of crates that can be used.
Each bag can hold |10\ \text{kg}| of supplies and each crate can hold |25\ \text{kg}.| We want to maximize the quantity of supplies to deliver to the people affected by the disaster. In addition, bags can be purchased for |\$2\ | each and crates can be purchased for |\$8\ | each. The expenses associated with purchasing these containers must also be minimized.