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 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 defines a half-plane region on the -plane where the boundary of the region is given by the straight line . Drawing the region given by a constraint is an important skill for linear programming.

Let us draw the region given by the constraint . First, we need to draw the boundary line . We can rearrange this equation to write , 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 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 into the inequality. If the *equality* holds, then this indicates that the origin lies on the
line. For our example, substituting into the inequality
, we note that the left-hand side is
. Since the equality does not hold, , 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 . Substituting into the expression leads to

But since , which is contrary to our given inequality, the point does not satisfy the inequality . In other words, the origin does not lie in the region described by this inequality. This implies that the region given by the constraint 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.

### Theorem: Fundamental Theorem of Linear Programming

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 with the constraints

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

Let us denote the objective function by . 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

For different values of , this is the equation of a line with slope 3 and -intercept . For example, we graph this line for , , , and on top of the graph containing the feasible region. Note that

So, we have the lines with -intercepts for , for , for , and for .

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, 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 and it overlaps with the feasible region at the single point . Any line associated with would not overlap at all with the region, so is not achievable. This leads us to conclude that 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.

### Theorem: Linear Programming with Bounded Feasible Regions

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.

### How To: Using Linear Programming for 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

We substitute these points into the objective function to obtain

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 restricted to the shaded region is 3, which occurs when and . This agrees with our answer using the previous method.

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

### Example 1: Finding the Point That Maximizes the Objective Function given the Graph of the Constraints

Using linear programming, find the minimum and maximum values of the function given that , , , and .

### 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

Next, we substitute these values into the objective function :

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

So is the minimum value of (when and ), and 1 is the maximum value of (when and ).

### Example 2: Finding the Maximum Value of the Objective Function given the Constraints and Their Graph

Find the maximum value of the objective function given the constraints , , , , and .

### 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

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 :

The largest value from the list above is 24.

So the maximum value of the objective function is equal to 24, which occurs when and .

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.

### Example 3: Forming the Set of Inequalities and the Objective Function of a Linear Programming Real-World Problem

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 . 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 . The first worker works at least 5 hours a day, so we get the constraint

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 . The second worker works a maximum of 7 hours per day, so we get the constraint

Finally, we need to make sure that both and since it is not possible to produce a negative number of desks. Together, we have the constraints and the objective function:

### Example 4: Using Linear Optimization to Maximize Profit

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 and .

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 . Since the total cost cannot exceed $240, we get the constraint

We note that the origin satisfies the strict inequality ; since , so this inequality corresponds to the region containing the origin. Overlapping with the constraints and , 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 . Since the total time cannot exceed 8 hours (that is, ), we get the constraint

We note that the origin satisfies the strict inequality since , so this inequality corresponds to the region containing the origin. Overlapping with the constraints and , 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

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 is an obvious one. Another one is the -intercept of . We can compute this by setting :

So this vertex is . The -intercept of is another vertex. We can compute this by setting :

So this vertex is . 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

We can rearrange the first equation for to get . Substituting this into the second equation, we get

Substituting this back into . So we get the vertex . Hence, we get the four vertices

Finally, we substitute these vertices into the objective function to find the optimal point.

So the maximum profit is $768, which is achieved when and .

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 with the constraints

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 . Then we obtain the family of lines

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.

### How To: Checking for Solutions for Linear Programming with Unbounded Feasible Regions

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.

### Example 5: Forming Objective Functions to Minimize Cost given a Graph Representing the Constraints

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 . Since the farmer needs at least 18 units of nitrogen-based compounds, we get

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

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

Then the constraints are

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 . So the objective function is

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 , 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

Substituting these points into the objective function .

Since the smallest value above is 580, this is the minimum value for the objective function . Further, we note that this value occurs at , 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

The slope of this line is , which is between the slope of two boundary lines ( and ). We can graph a few lines corresponding to

We note that the smaller gets, the lower the line goes. The line associated with does not overlap at all with the feasible region, so this value of is not attainable. On the other hand, the lines associated with and 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 . So, substituting into the objective function, we obtain the minimum value

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.

### Key Points

- 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 and .
- 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.