What kind of constraint which do not contribute to the boundary of the feasible solution region?

Table of Contents Show

In this explainer, we will learn how to find the optimal solution of a linear system that has an objective function and multiple constraints.

Linear programming is a technique used to find the maximum or the minimum of a given quantity under restrictions. Here, the quantity to be optimized is called the objective function, and the restrictions are called the constraints.

In linear programming, the objective function is a linear function of the variables. In other words, for a two-variable linear programming problem, an objective function should take the form 𝑝(𝑥,𝑦)=𝛼𝑥+𝛽𝑦+𝛾, for some constants 𝛼, 𝛽, and 𝛾.

Constraints of linear programming are given as a collection of linear inequalities, meaning that they are inequalities of the form 𝑎𝑥+𝑏𝑦+𝑐≤0 for some constants 𝑎, 𝑏, and 𝑐. Inequalities in constraints are generally not strict, and the optimal solution of a linear programming problem, if it exists, lies on a boundary. There can be any number of inequalities given as constraints for one linear programming problem.

Each constraint of the form 𝑎𝑥+𝑏𝑦+𝑐≤0 defines a half-plane region on the 𝑥𝑦-plane where the boundary of the region is given by the straight line 𝑎𝑥+𝑏𝑦+𝑐=0. Drawing the region given by a constraint is an important skill for linear programming.

Let us draw the region given by the constraint 4𝑥−𝑦+1≤0. First, we need to draw the boundary line 4𝑥−𝑦+1=0. We can rearrange this equation to write 𝑦=4𝑥+1, which gives the standard equation of a line. This line has 𝑦-intercept 1 and positive slope 4. We first graph this line on the 𝑥𝑦-plane.

This line divides the 𝑥𝑦-plane into two regions. To decide which region satisfies the given constraint, we can select any point outside the line to test whether the point satisfies the given constraint. It is advisable to select the simplest possible point for this purpose. If the origin (0,0) is not on the boundary line, then this is always the simplest choice. We can check whether or not the origin lies on a line by substituting (𝑥,𝑦)=(0,0) into the inequality. If the equality holds, then this indicates that the origin lies on the line. For our example, substituting (0,0) into the inequality 4𝑥−𝑦+1≤0, we note that the left-hand side is 4⋅0+1=1. Since the equality does not hold, 4⋅0+1≠0, the origin does not lie on the line.

Now, we can check whether or not the origin lies inside the region given by the constraint by testing the strict inequality 4𝑥−𝑦+1<0. Substituting (0,0) into the expression 4𝑥−𝑦+1 leads to 4(0)−0+1=1.

But since 1>0, which is contrary to our given inequality, the point (0,0) does not satisfy the inequality 4𝑥−𝑦+1<0. In other words, the origin (0,0) does not lie in the region described by this inequality. This implies that the region given by the constraint 4𝑥−𝑦+1≤0 is the one that does not include the origin. This region is shaded in the graph below.

In linear programming, multiple constraints are provided so that the resulting region is the overlapping region between each individual region. For example, consider the three constraints below.

When we combine three constraints, we obtain the triangular overlapping region pictured below.

In linear programming, multiple linear constraints are overlapped to produce a region with a polygonal boundary. This overlapping defined by all provided constraints is called the feasible region, and the vertices of the polygonal boundary are called the extreme points.

We say that a region on the 𝑥𝑦-plane is bounded if it can fit inside some circle. Otherwise, we say that the region is unbounded. The feasible region defined by a collection of constraints may be either bounded or unbounded. An example of an unbounded feasible region is given in the diagram below.

We note that, no matter how large the radius of a circle is, this region cannot fit inside the circle. Hence, the shaded region in the diagram above is unbounded.

If a linear programming problem has an optimal solution, then the solution occurs on the boundary (that is the lines and the vertices). Moreover, if a boundary line containing an optimal solution has a vertex (or vertices), then the solution will occur at one of the vertices.

To understand this principle better, we will think through an example together. Let us find the maximum value of −3𝑥+𝑦+2 with the constraints 𝑥+𝑦−1≤0,𝑦≥0,𝑥≥0.

From our previous discussions, we have the triangular feasible region pictured below.

Let us denote the objective function by 𝑝=−3𝑥+𝑦+2. We want to find the largest possible value for 𝑝, while we restrict 𝑥- and 𝑦-values so that (𝑥,𝑦) is inside the triangular feasible region. We can solve the equation for the objective function for 𝑦 to write 𝑦=3𝑥+𝑝−2.

For different values of 𝑝, this is the equation of a line with slope 3 and 𝑦-intercept (0,𝑝−2). For example, we graph this line for 𝑝=1, 𝑝=2, 𝑝=3, and 𝑝=4 on top of the graph containing the feasible region. Note that 𝑝=1⟹𝑦=3𝑥−1,𝑝=2⟹𝑦=3𝑥,𝑝=3⟹𝑦=3𝑥+1,𝑝=4⟹𝑦=3𝑥+2.

So, we have the lines with 𝑦-intercepts (0,−1) for 𝑝=1, (0,0) for 𝑝=2, (0,1) for 𝑝=3, and (0,2) for 𝑝=4.

Each of the red lines graphed above represents different values of the objective function as indicated. We notice that all red lines have the same slope. Different values of 𝑝 only affect the 𝑦-intercepts. So the family of lines representing the objective function are all parallel.

If a line has any overlap with the feasible region, even at a single point, then there is a pair (𝑥,𝑦) within the feasible region that can produce the value of the objective function associated with the line. If a line does not overlap with the feasible region, even at a single point, then that value of 𝑝 is not achievable from the feasible region. For example, 𝑝=4 does not overlap with the shaded region above, so this value cannot be achieved.

So, the task of finding the maximum value of 𝑝 from the feasible region is reduced to the task of finding the red line associated with the highest value of 𝑝. We can slide a line with slope 3 up and down the feasible region until it loses contact with the region. Since sliding upward is associated with increasing values of 𝑝 in this example, we look at the highest line in contact with the shaded region.

We see that this line is associated with 𝑝=3 and it overlaps with the feasible region at the single point (0,1). Any line associated with 𝑝>3 would not overlap at all with the region, so 𝑝>3 is not achievable. This leads us to conclude that 𝑝=3 is the maximum value of the objective function within the feasible region.

In our example, we were searching for the “last line” in contact with the feasible region. If such a line exists, then it must pass through a boundary line of the region. Also, if the line contains a vertex (or vertices), then the “last line” must overlap with the line on a vertex. This provides an intuitive justification for the fundamental theorem of linear programming.

Although it is good to keep this geometric intuition in mind when solving linear programming problems, there is a simpler algorithmic method when the feasible region is bounded. Remember that a bounded region means that it can fit inside some circle. The feasible region from our previous example is a bounded region as illustrated below.

If the feasible region is bounded, then the maximum and the minimum of a linear objective function must exist. Also, we note that the boundary line of any bounded polygonal region must contain two vertices. This is because a line without two vertices will extend toward infinity so that it cannot fit inside any circle. This leads to the following statement.

A linear programming problem with a nonempty bounded feasible region must have a solution at one of the vertices of the region.

In other words, we can solve any linear programming problem with bounded feasible regions by checking for the optimal value among the vertices. This leads to the following method for solving a linear programming problem with bounded feasible regions.

Consider a linear objective function 𝑝(𝑥,𝑦) with a collection of linear constraints. Assume that the feasible region is bounded. To find the maximum or the minimum value of 𝑝(𝑥,𝑦) under the given constraints, we follow the steps below.

Graph the feasible region from constraints.
Find all vertices.
Substitute the coordinates of each vertex into the objective function.
The largest value from the previous step is the maximum value, and the smallest value is the minimum value.

Let us use this method for our previous example. From the feasible region, we note that the vertices are (1,0),(0,1),(0,0).

We substitute these points into the objective function 𝑝(𝑥,𝑦)=−3𝑥+𝑦+2 to obtain 𝑝(1,0)=−3⋅1+0+2=−1,𝑝(0,1)=−3⋅0+1+2=3,𝑝(0,0)=−3⋅0+0+2=2.

The largest value of the objective function from the list above is 3, so this is the solution to this example. In other words, the maximum value of −3𝑥+𝑦+2 restricted to the shaded region is 3, which occurs when 𝑥=0 and 𝑦=1. This agrees with our answer using the previous method.

Let us consider a few linear programming examples with finite feasible regions using this method.

Using linear programming, find the minimum and maximum values of the function 𝑝=4𝑥−3𝑦 given that 𝑥≥0, 𝑦≥0, 𝑥+𝑦≤9, and 𝑦≥5.

Answer

In this example, the graph of the feasible region is provided. We notice that the feasible region is bounded (i.e., it fits inside some circle). We recall that if the feasible region is bounded, then the linear objective function has its maximum and minimum values at one of the vertices. The steps for identifying the maximum and minimum values are as follows.

Graph the feasible region from constraints.
Find all the vertices.
Substitute the coordinates of each vertex into the objective function.
Identify the solution.

Since the graph of the feasible region is provided, we proceed to find the vertices. From the graph, we note the vertices of the triangular feasible region to be (0,5),(0,9),(4,5).

Next, we substitute these values into the objective function 𝑝=𝑝(𝑥,𝑦)=4𝑥−3𝑦: 𝑝(0,5)=4⋅0−3⋅5=−15,𝑝(0,9)=4⋅0−3⋅9=−27,𝑝(4,5)=4⋅4−3⋅5=1.

From the list above, the largest value of 𝑝 is 1, and the smallest value of 𝑝 is −27.

So −27 is the minimum value of 𝑝 (when 𝑥=0 and 𝑦=9), and 1 is the maximum value of 𝑝 (when 𝑥=4 and 𝑦=5).

Find the maximum value of the objective function 𝑝=2𝑥+6𝑦 given the constraints 𝑥≥0, 𝑦≥0, 𝑥+𝑦≤6, 3𝑥+𝑦≤9, and 𝑥+2𝑦≤8.

Answer

We are given the graph of three shaded regions, corresponding to the constraints. The overlapping region is the brown quadrilateral with a vertex at the origin. This is the feasible region for the given linear programming problem.

From the provided picture, we can tell that the vertices are (0,0),(0,4),(2,3),(3,0).

We recall that if the feasible region is bounded (i.e., it fits inside some circle), then the maximum and minimum values must occur at one of these vertices. We substitute the coordinates of each vertex into the objective function 𝑝=𝑝(𝑥,𝑦)=2𝑥+6𝑦: 𝑝(0,0)=2⋅0+6⋅0=0,𝑝(0,4)=2⋅0+6⋅4=24,𝑝(2,3)=2⋅2+6⋅3=22,𝑝(3,0)=2⋅3+6⋅0=6.

The largest value from the list above is 24.

So the maximum value of the objective function 𝑝 is equal to 24, which occurs when 𝑥=0 and 𝑦=4.

Linear programming can be used in real-life problems to find optimal solutions. In the next few examples, we will consider word problems involving real life situations.

In a workshop, two workers produce two types of iron desks: type A and type B. One worker builds the desks and the other sprays them. It takes the first worker 4 hours to build one desk of type A and 3 hours to build one desk of type B. It takes the second worker 3 hours to spray one desk of type A and 4 hours to spray one desk of type B. The first person works at least 5 hours a day, and the other works a maximum of 7 hours a day. If the workshop earns a profit of 60 LE from each desk (of either type), determine the objective function and inequalities required for calculating the number of desks of each type to be produced every day to maximize the profit 𝑝.

Answer

Let us define the key variables for this problem. We define 𝑥 to be the number of type A desks produced and 𝑦 to be the number of type B desks produced. The workshop earns 60 LE for each desk of either types, so the profit 𝑝 is given by 𝑝=60𝑥+60𝑦. This is the objective function to maximize for this example.

Next, let us examine the first worker’s time. It takes the first worker 4 hours to build one desk of type A and 3 hours to build one desk of type B. So the total number of hours spent by the first worker is given by 4𝑥+3𝑦. The first worker works at least 5 hours a day, so we get the constraint 4𝑥+3𝑦≥5.

Now, let us examine the second worker’s time. It takes the second worker 3 hours to spray one desk of type A and 4 hours to spray one desk of type B. So the total number of hours spent by the second worker is given by 3𝑥+4𝑦. The second worker works a maximum of 7 hours per day, so we get the constraint 3𝑥+4𝑦≤7.

Finally, we need to make sure that both 𝑥≥0 and 𝑦≥0 since it is not possible to produce a negative number of desks. Together, we have the constraints and the objective function: 𝑥≥0,𝑦≥0,4𝑥+3𝑦≥5,3𝑥+4𝑦≤7,𝑝=60𝑥+60𝑦.

A small company dyes shirts to be either solid-color or tie-dye shirts, and they want to decide how many shirts of each color to prepare for an upcoming sale. They have a budget of $240. Purchasing each shirt costs $2. It costs $0.50 to dye a shirt with a solid color and $1.50 to produce a tie-dye shirt. They only have 8 hours to prepare all the shirts, and it takes 2 minutes to dye a solid-color shirt and 10 minutes to dye a tie-dye shirt.

They want to maximize their profit, knowing that they make $8 profit for each solid-color shirt and $10 for each tie-dye shirt.

Let 𝑥 represent the number of solid-color shirts and 𝑦 represent the number of tie-dye shirts.

Which of the following shows the feasible region?

State the objective function.

How many of each type of shirt should the company produce to maximize profit?

Answer

Part 1

We need to identify the constraints for this problem first. Let 𝑥 represent the number of solid-color shirts and 𝑦 represent the number of tie-dye shirts. Since we cannot have a negative number of shirts, we must have 𝑥≥0 and 𝑦≥0.

Next, let us examine the total cost. Each shirt costs $2 to purchase, but there is an additional cost for dying. A solid-color shirt costs $0.50 to dye, so the overall cost is $2.50 per solid-color shirt. A tie-dye shirt costs $1.50 to dye, so the cost is $3.50 per tie-dye shirt. Then the total cost (in dollars) is given by 2.5𝑥+3.5𝑦. Since the total cost cannot exceed $240, we get the constraint 2.5𝑥+3.5𝑦≤240.

We note that the origin (0,0) satisfies the strict inequality 2.5𝑥+3.5𝑦<240; since 2.5⋅0+3.5⋅0<240, so this inequality corresponds to the region containing the origin. Overlapping with the constraints 𝑥≥0 and 𝑦≥0, we get the following shaded region.

Let us now examine the total time. It takes 2 minutes to dye a solid-color shirt and 10 minutes to dye a tie-dye shirt. So the total time (in minutes) is given by 2𝑥+10𝑦. Since the total time cannot exceed 8 hours (that is, 8×60=480minutes), we get the constraint 2𝑥+10𝑦≤480.

We note that the origin (0,0) satisfies the strict 2𝑥+10𝑦<480 inequality since 2⋅0+10⋅0<480, so this inequality corresponds to the region containing the origin. Overlapping with the constraints 𝑥≥0 and 𝑦≥0, we get the following shaded region.

Overlapping these two regions, we obtain the feasible region below.

Part 2

We want to maximize the profit. We are given that they make $8 profit for each solid-color shirt and $10 for each tie-dye shirt. Then the profit 𝑝 is given by 𝑝(𝑥,𝑦)=8𝑥+10𝑦.

This is the objective function to maximize.

Part 3

We recall that a linear programming problem with a bounded feasible region must have an optimal solution occur at a vertex. The feasible region graphed in part 1 has four vertices. The origin (0,0) is an obvious one. Another one is the 𝑦-intercept of 2𝑥+10𝑦=480. We can compute this by setting 𝑥=0: 2⋅0+10𝑦=480⟹10𝑦=480⟹𝑦=48.

So this vertex is (0,48). The 𝑥-intercept of 2.5𝑥+3.5𝑦=240 is another vertex. We can compute this by setting 𝑦=0: 2.5𝑥+3.5⋅0=240⟹2.5𝑥=240⟹𝑥=96.

So this vertex is (96,0). The final vertex is the point of intersection of the two lines, whose equations are provided. So we need to solve the system of linear equations 2𝑥+10𝑦=480,2.5𝑥+3.5𝑦=240.

We can rearrange the first equation for 𝑥 to get 𝑥=240−5𝑦. Substituting this into the second equation, we get 2.5(240−5𝑦)+3.5𝑦=240⟹600−12.5𝑦+3.5𝑦=240⟹−9𝑦=−360⟹𝑦=40.

Substituting this back into 𝑥=240−5𝑦=240−5⋅40=40. So we get the vertex (40,40). Hence, we get the four vertices (0,0),(0,48),(96,0),(40,40).

Finally, we substitute these vertices into the objective function 8𝑥+10𝑦 to find the optimal point. 𝑝(0,0)=8⋅0+10⋅0=0,𝑝(0,48)=8⋅0+10⋅48=480,𝑝(96,0)=8⋅96+10⋅0=768,𝑝(40,40)=8⋅40+10⋅40=720.

So the maximum profit is $768, which is achieved when 𝑥=96 and 𝑦=0.

The company should produce 96 solid-color shirts and zero tie-dye shirts to maximize its profit.

So far, we have examined examples where the feasible region is bounded. In this case, the solution to the linear programming problem is guaranteed to exist, so we can follow the set algorithm to identify the solution.

However, in the case of unbounded feasible regions, a solution does not have to exist. In such cases, we need to graph the family of lines associated with different values of objective functions to check whether or not a solution exists.

For example, let us maximize the objective function 𝑝=−3𝑥+𝑦+2 with the constraints 𝑥+𝑦−1≥0,𝑦≥0,𝑥≥0.

This feasible region is graphed below.

We note that the shaded region is unbounded because it cannot fit inside any circle. As before, we can solve the objective function for 𝑦 to get 𝑦=3𝑥−2+𝑝. Then we obtain the family of lines 𝑝=1⟹𝑦=3𝑥−1,𝑝=2⟹𝑦=3𝑥,𝑝=3⟹𝑦=3𝑥+1,𝑝=4⟹𝑦=3𝑥+2.

Graphing these lines on top of the feasible region, we get

We note that, no matter how large 𝑝 gets, the associated line will still overlap with the feasible region. This implies that 𝑝 can be as large as we want, even under the constraints. In this case, we say that there is no maximum value of the objective function. In other words, a solution for the linear programming does not exist.

In some cases, the solution of a linear programming problem may exist despite an unbounded feasible region. There are several methods we can use to check whether or not the problem has the optimal solution.

Let 𝑝=𝑝(𝑥,𝑦) be the objective function over an unbounded feasible region. Then

if 𝑝 is bounded from below (i.e., 𝑝≥𝐶 for some constant 𝐶), then 𝑝 has the minimum value on the feasible region;
if 𝑝 is bounded from above (i.e., 𝑝≤𝐶 for some constant 𝐶), then 𝑝 has the maximum value on the feasible region;
if the above conditions are unclear, then we should graph a family of lines corresponding to the objective function to see whether or not the optimal value is attainable.

If we can determine that the optimal value exists, then we can follow the previous algorithm for bounded feasible regions to identify the optimal value.

In the last example, we consider an example of linear programming with an unbounded feasible region.

A farmer can improve the quality of his produce if he uses at least 18 units of nitrogen-based compounds and at least 6 units of phosphate compounds. He can use two types of fertilizers: A and B. The cost and contents of each fertilizer are shown in the table.

The Fertilizer	Number of Units of Nitrogen-Based Compounds per Kilogram	Number of Units of Phosphate Compounds per Kilogram	Cost for Each Kilogram (LE)
A	3	2	170
B	6	1	120

Given that the graph represents the constraints in this situation, find the lowest cost the farmer can pay for fertilizer while providing sufficient amounts of both compounds.

Answer

Let us begin by deriving the constraints represented in the diagram. Let 𝑥 be the amount (in kilograms) of fertilizer A used, and let 𝑦 be the amount (in kilograms) of fertilizer B used. Then, based on the provided table, the amount of nitrogen-based compounds is given by 3𝑥+6𝑦. Since the farmer needs at least 18 units of nitrogen-based compounds, we get 3𝑥+6𝑦≥18.

The amount of phosphate compounds is given by 2𝑥+𝑦. Since the farmer needs at least 6 units of phosphate compounds, we get 2𝑥+𝑦≥6.

Since we cannot have negative amount of fertilizers used, we also need the constraints 𝑥≥0 and 𝑦≥0.

Then the constraints are 3𝑥+6𝑦≥18,2𝑥+𝑦≥6,𝑥≥0,𝑦≥0.

This is the purple shaded region in the provided graph.

Next, let us determine the objective function. The farmer wants to minimize the cost used for fertilizers. Based on the provided table, the total cost of fertilizers is given by 170𝑥+120𝑦. So the objective function is 𝑐=170𝑥+120𝑦.

There are two different ways to finish this problem. Since the feasible region is unbounded (i.e., it does not fit inside any circle), we must first check whether or not the problem has a solution.

Method 1

We begin by noting that the objective function represents cost, which cannot be negative. So 𝑐≥0, meaning that 𝑐 is bounded from below. We recall that, if an objective function is bounded from below, then it has the minimum value on the feasible region. So the solution exists.

We recall that if a solution to a linear programming problem exists, then it must occur on a boundary line. Further, if each boundary line contains a vertex, then the solution must occur at one of the vertices. In the provided graph, we note that the vertices are (0,6),(2,2),(6,0).

Substituting these points into the objective function 𝑐(𝑥,𝑦)=170𝑥+120𝑦. 𝑐(0,6)=170⋅0+120⋅6=720,𝑐(2,2)=170⋅2+120⋅2=580,𝑐(6,0)=170⋅6+120⋅0=1020.

Since the smallest value above is 580, this is the minimum value for the objective function 𝑐. Further, we note that this value occurs at (𝑥,𝑦)=(2,2), which we predicted using the graph.

Method 2

Alternatively, we can verify that the solution exists by graphing a family of lines for the objective function. For this method, we begin by rearranging the objective function for 𝑦 to get 𝑦=−1712𝑥+𝑐120.

The slope of this line is −1712, which is between the slope of two boundary lines (−12 and −2). We can graph a few lines corresponding to 𝑐=120⟹𝑦=−1712𝑥+1,𝑐=720⟹𝑦=−1712𝑥+5,𝑐=1200⟹𝑦=−1712𝑥+10.

We note that the smaller 𝑐 gets, the lower the line goes. The line associated with 𝑐=120 does not overlap at all with the feasible region, so this value of 𝑐 is not attainable. On the other hand, the lines associated with 𝑐=720 and 𝑐=1200 both overlap with the feasible region, so they can be attained. We can tell by observing this picture that there must be the smallest value 𝑐 which gives us the “last line” before the line exits the feasible region completely.

In fact, by sliding parallel lines up and down the feasible region, we can tell that this “last line” must overlap with the feasible region at the vertex (2,2). So, substituting (2,2) into the objective function, we obtain the minimum value 𝑐(2,2)=170⋅2+120⋅2=580.

We note that this agrees with our answer from method 1.

So, the lowest cost the farmer can pay for fertilizer while providing sufficient amounts of both compounds is 580 LE by using 2 kg of fertilizer A and 2 kg of fertilizer B.

Linear programming is a technique used to find the optimal value (min/max) of a linear objective function, given a collection of linear constraints.
For physical variables that cannot be negative, remember the constraints 𝑥≥0 and 𝑦≥0.
We can check whether a given linear programming problem has a solution in the following ways:
- If the feasible region is bounded, then the maximum and the minimum exist.
- If the objective function is bounded from below, then the minimum exists.
- If the objective function is bounded from above, then the maximum exists.
- If none of the above applies, we should graph a family of lines for the objective function to check whether the optimal value is attainable.
If the linear programming has a solution, the solution must occur on the boundary. If, in addition, each boundary line contains a vertex (or vertices), then the solution must occur at a vertex.
If a solution of linear programming exists, then we can find the solution using the following steps:
- Graph the feasible region from constraints.
- Find all the vertices.
- Substitute the coordinates of each vertex into the objective function.
- Identify the solution.