3.5: Applications of Linear Programming - Mathematics

In the previous section we looked at the Simplex method, a procedure for solving linear programming problems with many variables. In the remainder of this chapter, we will focus on setting up the objective function and constraints and interpreting the solution, and omit the details of solving.

Example (PageIndex{1})

A catering company is to make lunch for a business meeting. It will serve ham sandwiches, light ham sandwiches, and vegetarian sandwiches. A ham sandwich has 1 serving of vegetables, 4 slices of ham, 1 slice of cheese, and 2 slices of bread. A light ham sandwich has 2 serving of vegetables, 2 slices of ham, 1 slice of cheese and 2 slices of bread. A vegetarian sandwich has 3 servings of vegetables, 2 slices of cheese. and 2 slices of bread. A total of 10 bags of ham are available, each of which has 40 slices; 18 loaves of bread are available, each with 14 slices; 200 servings of vegetables are available, and 15 bags of cheese, each with 60 slices, are available. Given the resources, how many of each sandwich can be produced if the goal is to maximize the number of sandwiches?


We wish to maximize the number of sandwiches, so let:
(x=) number of ham sandwiches
(y=) number of light ham sandwiches
(z=) number of vegetarian sandwiches

The total number of sandwiches is given by: (quad S=x+y+z)

The constraints will be given by considering the total amount of ingredients available. That is, the company has a limited amount of ham, vegetables, cheese, and bread.

In total, the company has (10(40)=400) slices of ham, (18(14)=252) slices of bread.
200 servings of vegetables, and (15(60)=900) slices of cheese available. At most, the
company can use the above amounts.

There are two sandwiches that use ham-the first requires 4 slices of ham and the second requires only 2, per sandwich, and the total number of slices of ham cannot exceed 400

[4 x+2 y leq 400 onumber]

Each sandwich requires 2 slices of bread so:

[2 x+2 y+2 z leq 252 onumber]

The ham sandwiches have 1 and 2 servings of vegetables, respectively, and the vegetarian sandwich has 3 servings of vegetables. So,

[1x + 2y + 3z leq 200 onumber]

Both ham sandwiches require one slice of cheese, and the vegetarian sandwich requires two slices of cheese, so,

[1x + 1y + 2z leq 900 onumber]

Our final setup is:

Maximize: (S = x + y + z)

Subject to:

[ egin{align*} 4x + 2y & leq 400 2x + 2y + 2z &leq 252 2x + 2y + 2z &leq 252end{align*} onumber]

Solving this, we get

Optimal Solution:

[S = 126; quad x = 100, quad y = 0, quad z = 26 onumber]

We find that 100 ham sandwiches, 26 vegetarian sandwiches, and 0 light ham sandwiches should be made to maximize the total number of sandwiches made.

Notice that this will effectively use up all of the bread, which is the first to go.

Example (PageIndex{2})

A factory manufactures three products, A, B, and C. Each product requires the use of two machines, Machine I and Machine II. The total hours available, respectively, on Machine I and Machine II per month are 180 and 300. The time requirements and profit per unit for each product are listed below.




Machine I




Machine II








How many units of each product should be manufactured to maximize profit, and what is the maximum profit?


As usual, we start by defining our variables:
(A=) number of units of product A manufactured

(B=) number of units of product B manufactured

(C=) number of units of product B manufactured

We are trying to maximize profit. Producing (A) units of item A will result in a profit of (20 A), producing (B) units of item (B) will profit (30 B), and (C) units of item (C) will profit (40 C), giving our objective function:

[P=20 A+30 B+40 C onumber]

Next we consider the time available on each machine to establish constraints. Producing A units of item A will require 1A hours on Machine 1, producing B units of item B will require 2B hours, and producing C units of item C will require 2C hours. Together these need to not exceed the 180 hours available. This leads to the constraint:

[1A + 2B + 2C leq 180 onumber]

We can construct a similar constraint using the hours on Machine 2:

[2A + 2B + 4C leq 300 onumber]

Our final setup is:

Maximize (P = 20A + 30B + 40C)

Subject to:

[egin{align*} 1A + 2B + 2C &leq 180 2A + 2B + 4C &leq 300 A geq 0, quad B geq 0, &; C geq 0 end{align*} onumber]

Solving this:

Optimal Solution:

[P = 3300; A = 120, B = 30, C = 0 onumber]

We will maximize profit at $3300 by producing 120 units of item (A), 30 units of item (B), and no units of item (C).

In addition to maximization problems, linear programming can also be used to solve minimization problems. When done by-hand, these would require a modification of the Simplex method shown in the last section, but these problems can be solved by most technologic methods.

Example (PageIndex{3})

A company is creating a meal replacement bar. They plan to incorporate peanut butter, oats, and dried cranberries as the primary ingredients. The nutritional content of 10 grams of each is listed below, along with the cost, in cents, of each ingredient. Find the amount of each ingredient they should use to minimize the cost of producing a bar containing a minimum of 15g of each ingredient, at least 10g of protein and at most 14g of fat.

Peanut Butter, 10g

Oats, 10g

Cranberries, 10g

Protein (grams)




Fat (grams)




Cost (cents)





We start by introducing variables:

(p =) number of 10g servings of peanut butter

(a =) number of 10g servings of oats

(c =) number of 10g servings of cranberries

The total cost, (C), of producing the bar, in cents, will be (C=6 p+1 a+2 c).

Our first constraints come from the requirement for (15 mathrm{~g}) of each ingredient, which is (1.5) servings (1.5 servings at (10 mathrm{~g}) per serving (=15 mathrm{~g}) ). Constructing those constraints (p geq 1.5, a geq 1.5, c geq 1.5)

Next we look at the nutritional components. For protein, (p) servings of peanut butter will contain (2.5 p) grams of protein. Likewise, (a) servings of oats will have (1.7 a) grams of protein, and (c) servings of cranberries will have (0 c) grams of protein. Together, these need to be at least 10 grams, giving the constraint (2.5 p+1.7 a+0 c geq 10)

We can construct a similar constraint for fat, in this case noting we want the fat to be at most (14 mathrm{~g}) :
(5 p+0.7 a+0.1 c leq 14)

We can now have our complete problem:


[C=6 p+1 a+2 c onumber]
Subject to:
[egin{align*} 2.5 p+1.7 a+0 c &geq 10 5 p+0.7 a+0.1 c &leq 14 p geq 1.5, a geq 1.5, c &geq 1.5end{align*}]

Turning to technology, we get a solution:

Optimal Solution:

[C=15.6765; quad p=1.5, quad a=3.67647, quad c=1.5 onumber]

Interpreting that result, the minimum cost of to produce the bar will be about (15.7) cents, by using 15 grams of peanut butter, (36.8) grams of oats, and 15 grams of dried cranberries.

Verifying our conditions, we can see that our recipe contains at least (1.5) servings of each ingredient. The protein content will be (2.5(1.5)+1.7(3.68)+0(1.5) approx 10) grams.
The fat content will be (5(1.5)+0.7(3.68)+0.1(1.5) approx 10.2) grams.

Exercise (PageIndex{1})

A factory manufactures three products, (A, B), and (C). Each product requires a certain number of hours of manufacturing, assembly and finishing time, shown below, along with the total time available and profit. Find production levels to maximize profit.




Total Hours





















Our problem setup is:

Maximize :

[P = 175A + 130B + 40C onumber]

Subject to:

[egin{align*} 4A + 5B + 2C &leq 300 7A + 4B + 1C &leq 250 4A + 5B + 1C &leq 200 end{align*} ]

Solving this, we get the solution:

Optimal Solution:

[P = 7907.89; A = 18.4211, B = 5.26316, C = 100 onumber ]

Rounding down, producing (A = 18), (B = 5), and (C = 100) would use 297 hours of manufacturing, 246 hours of assembly, and 197 hours of finishing and have profit of $7800. We could fiddle with a few other nearby integer solutions:

(A = 18, B = 5), and (C = 101): Profit $7840

(A = 18, B = 6), and (C = 98): Profit $7850

(A = 19, B = 4), and (C = 101): Profit $7885

As you can see, finding optimal integer solutions is a harder problem.

In some cases we have to be clever with how we create our constraints to maintain the correct form of a linear programming problem while still meeting the requirements of the actual application.

Example (PageIndex{4})

A distribution company needs to ship products from its two warehouses to three retailers. Warehouse A has 1000 products in stock, and Warehouse B has 1200 products. Retailer 1 needs 700 products, Retailer 2 needs 500 products, and Retailer 3 needs 600 products The cost to ship a product from each warehouse to each retailer is shown below. Find the number of products the company should ship from each warehouse to each retailer to minimize shipping costs.

Retailer 1

Retailer 2

Retailer 3

Warehouse A




Warehouse B





To start this problem, we first need to define our variables. Since there are six different routes, we will need to define six variables:

(A_1=) the number of products shipped from Warehouse A to Retailer 1

(B_1=) the number of products shipped from Warehouse B to Retailer 1

(A_2=) the number of products shipped from Warehouse A to Retailer 2

We can similarly define variables (B_2, A_3) and (B_3).

Our objective function is the total shipping cost. Shipping (A_1) items from Warehouse (A) to Retailer 1 will cost $3 per item, so a total cost of (3A_1). Doing the same for the other variables gives our total cost equation:

[C = 3{A_1} + 4{B_1} + 5{A_2} + 7{B_2} + 8{A_3} + 5{B_3} onumber]

We know that Warehouse (A) has 1000 products in stock, so the total number of items shipped out of Warehouse (A) needs to be no more than 1000. Likewise Warehouse B can’t ship more than 1200 items. These give the constraints:

[egin{align*}A_1 + A_2 + A_3 leq 1000 {B_1} + {B_2} + {B_3} leq 1200end{align*}]

Retailer 1 needs 700 products. While is technically a strict equality, we can set it up as an inequality, indicating the total number of product arriving at retailer 1 needs to be at least 700 products. Since we’re minimizing cost, there’s no way we’d end up shipping more than 700 items to the retailer. Setting up this constraint, and similar ones for the other three retailers:

[egin{align*} {A_1} + {B_1} geq 700 {A_2} + {B_2} geq 500 {A_3} + {B_3} geq 600 end{align*}]

Our final problem setup is:


[C = 3{A_1} + 4{B_1} + 5{A_2} + 7{B_2} + 8{A_3} + 5{B_3} onumber]

Subject to:

[ egin{align*}{A_1} + {A_2} + {A_3} leq 1000 {B_1} + {B_2} + {B_3} leq 1200 {A_1} + {B_1} geq 700 {A_2} + {B_2} geq 500 {A_3} + {B_3} geq 600 {A_1} geq 0,{B_1} geq 0,{A_2} geq 0,{B_2} geq 0,{A_3} geq 0,{B_3} geq 0end{align*}]

Solving this, we get the solution,

Optimal Solution:

[C = 7800; A_1 = 500, B_1 = 200, A_2 = 500, B_2 = 0, A_3 = 0, B_3 = 600 onumber]

Important Topics of this Section

Setting up the objective and constraint equations for an application

Interpreting the solution to a linear programming question

Linear programming

Linear programming (LP, also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (also known as mathematical optimization).

More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints. Its feasible region is a convex polytope, which is a set defined as the intersection of finitely many half spaces, each of which is defined by a linear inequality. Its objective function is a real-valued affine (linear) function defined on this polyhedron. A linear programming algorithm finds a point in the polytope where this function has the smallest (or largest) value if such a point exists.

Linear programs are problems that can be expressed in canonical form as

Here the components of x are the variables to be determined, c and b are given vectors (with c T ^> indicating that the coefficients of c are used as a single-row matrix for the purpose of forming the matrix product), and A is a given matrix. The function whose value is to be maximized or minimized ( x ↦ c T x mapsto mathbf ^mathbf > in this case) is called the objective function. The inequalities Axb and x0 are the constraints which specify a convex polytope over which the objective function is to be optimized. In this context, two vectors are comparable when they have the same dimensions. If every entry in the first is less-than or equal-to the corresponding entry in the second, then it can be said that the first vector is less-than or equal-to the second vector.

Linear programming can be applied to various fields of study. It is widely used in mathematics, and to a lesser extent in business, economics, and for some engineering problems. Industries that use linear programming models include transportation, energy, telecommunications, and manufacturing. It has proven useful in modeling diverse types of problems in planning, routing, scheduling, assignment, and design.

Application of Linear Programming Approach for Determining Optimum Production Cost

Cost optimization problem deals with that problem which aims to find out the most appropriate ways to fulfill the demand of a particular product of any manufacturing company with minimum cost. Linear programming is one of the most appropriate techniques for scheduling the optimum cost of manufacturing. In this study, the production schedule of a bicycle manufacturing company is taken into account. The mathematical formulation of the problem under consideration is performed by using a linear programming approach. An operations research software, TORA (Temporary-Ordered Routing Algorithm), has been used in solving the problem and analyzing the results. Results reveal that a specific schedule has a great impact on optimizing the production cost.



Author Biographies

Department of Mathematics, University of Barisal, Barisal-8200, BANGLADESH

Department of Mathematics, University of Dhaka, Dhaka-1000, BANGLADESH

Department of Mathematics, University of Barisal, Barisal-8200, BANGLADESH

Department of Management Studies, University of Barisal, Barisal-8200, BANGLADESH


Andawei, M. E. 2014. Application of linear programming in multi-design selection. The International Journal of Engineering and Science (IJES). 3(1): 52-55.

Anieting, A. E., V. O. Ezugwu and S. Ologun. 2013. Application of Linear Programming Technique in the Determination of Optimum Production Capacity. IOSR Journal of Mathematics (IOSR-JM). 5(6): 62-65.

Baker, K. R. 2011. Optimization modeling with Spreadsheets, Hoboken, Wiley.

Balogun, O. S., E. T. Jolayemi, T. J. Akingbade and H. G. Muazu. 2012. Use of Linear Programming for Optimal Production in a Production Line in Coca-Cola Bottling Company, Ilorin. International Journal of Engineering Research and Applications. 2(5): 2004-2007.

Buresh-Oppenheim, J., S. Davis and R. Impagliazzo. 2011. A Stronger Model of Dynamic Programming Algorithms. Algorithmica. 60: 938-968.

Felix, M., M. Judith, M. Jonathan and S. Munashe. 2013. Modeling a Small Farm Livelihood System using Linear Programming in Bindura, Zimbabwe. Research Journal of Management Sciences. 2(5): 20-23.

Ibitoye, O., A. K. Olusegun, G. Kellikume and K. Kayode. 2015. Entrepreneur Decision Making Process and Application of Linear Programming Technique. European Journal of Business, Economics and Accountancy. 3(5): 1-5.

Tesfaye G., T. Berhane, B. Zenebe and S. Asmelash. 2016. A linear programming method to enhance resource utilization case of Ethiopian apparel sector. International Journal for Quality Research. 10(2): 421–432.

Veselovska, I. L. 2014. A Linear Programming Model of Integrating Flexibility Measures into Production Processes with Cost Minimization. Journal of Small Business and Entrepreneurship Development. 2(1): 67-82.

What are the applications of linear algebra?


It is the study of decoding and encoding of the secret messages. Using electronic transactions and communications, solid encryption methods can be applied. Those methods involve modular arithmetic to decode/encode the messages. And the simpler encoding methods apply using the concept of matrix transformation.

I mentioned above that the linear algebra concept is used to decode the secret message (a cryptography method).


A fourth edition has just been announced, but I am told that the bookstore received the older edition. See the authors' list of errata for corrections that are tailored to your copy of the book.

Recommended Reading: There are quite a few good linear algebra books in circulation see the textbook lists for some examples. Whenever you feel stuck when reading our text, feel free to consult alternative treatments. Reading several discussions of one topic is often illuminating. One excellent book is Linear Algebra Done Right by Sheldon Axler.

3.5: Applications of Linear Programming - Mathematics

We now need to discuss the section that most students hate. We need to talk about applications to linear equations. Or, put in other words, we will now start looking at story problems or word problems. Throughout history students have hated these. It is my belief however that the main reason for this is that students really don’t know how to work them. Once you understand how to work them, you’ll probably find that they aren’t as bad as they may seem on occasion. So, we’ll start this section off with a process for working applications.

Process for Working Story/Word Problems

  2. READ THE PROBLEM AGAIN. Okay, this may be a little bit of overkill here. However, the point of these first two steps is that you must read the problem. This step is the MOST important step, but it is also the step that most people don’t do properly.

You need to read the problem very carefully and as many times as it takes. You are only done with this step when you have completely understood what the problem is asking you to do. This includes identifying all the given information and identifying what you are being asked to find.

Again, it can’t be stressed enough that you’ve got to carefully read the problem. Sometimes a single word can completely change how the problem is worked. If you just skim the problem you may well miss that very important word.

Let’s start things off with a couple of fairly basic examples to illustrate the process. Note as well that at this point it is assumed that you are capable of solving fairly simple linear equations and so not a lot of detail will be given for the actual solution stage. The point of this section is more on the set up of the equation than the solving of the equation.

Okay, let’s start off by defining (p) to be the minimum required score on the third exam.

Now, let’s recall how grades are set. Since there are no weights or anything on the grades, the grade will be set by first computing the following percentage.

Since we are using the standard scale if the grade percentage is 0.9 or higher the student will get an A. Likewise, if the grade percentage is between 0.8 and 0.9 the student will get a B.

We know that the total possible points is 350 and the student has a total points (including the third exam) of,

[4 + 8 + 7 + 7 + 9 + 78 + 83 + p = 196 + p]

The smallest possible percentage for an A is 0.9 and so if (p) is the minimum required score on the third exam for an A we will have the following equation.

This is a linear equation that we will need to solve for (p).

[196 + p = 0.9left( <350> ight) = 315hspace<0.25in>,,,, Rightarrow hspace<0.25in>,,,p = 315 - 196 = 119]

So, the minimum required score on the third exam is 119. This is a problem since the exam is worth only 100 points. In other words, the student will not be getting an A in the Algebra class.

Now let’s check if the student will get a B. In this case the minimum percentage is 0.8. So, to find the minimum required score on the third exam for a B we will need to solve,

[196 + p = 0.8left( <350> ight) = 280hspace<0.25in>,,,, Rightarrow hspace<0.25in>,,,p = 280 - 196 = 84]

So, it is possible for the student to get a B in the class. All that the student will need to do is get at least an 84 on the third exam.

We will first define (x) to be the height of the set of shelves. This means that 4(x) is width of the set of shelves. In this case we definitely need to sketch a figure so we can correctly set up the equation. Here it is,

Now we know that there are 72 feet of wood to be used and we will assume that all of it will be used. So, we can set up the following word equation.

It is often a good idea to first put the equation in words before actually writing down the equation as we did here. At this point, we can see from the figure there are two vertical pieces each one has a length of (x). Also, there are 4 horizontal pieces, each with a length of 4(x). So, the equation is then,

[egin4left( <4x> ight) + 2left( x ight) & = 72 16x + 2x & = 72 18x & = 72 x & = 4end]

So, it looks like the height of the set of shelves should be 4 feet. Note however that we haven’t actually answered the question however. The problem asked us to find the dimensions. This means that we also need the width of the set of shelves. The width is 4(4)=16 feet. So the dimensions will need to be 4x16 feet.

Pricing Problems

The next couple of problems deal with some basic principles of pricing.

First, let’s define (p) to be the cost that the store paid for the calculator. The stores markup on the calculator is 15%. This means that 0.15(p) has been added on to the original price ((p)) to get the amount the calculator is being sold for. In other words, we have the following equation

that we need to solve for (p). Doing this gives,

[1.15p = 78.50hspace <0.5in>Rightarrow hspace<0.5in>p = frac<<78.50>><<1.15>> = 68.26087]

The store paid $68.26 for the calculator. Note that since we are dealing with money we rounded the answer down to two decimal places.

This problem is pretty much the opposite of the previous example. Let’s start with defining (p) to be the price of the shirt before the sale. It has been marked down by 35%. This means that 0.35(p) has been subtracted off from the original price. Therefore, the equation (and solution) is,

[eginp - 0.35p & = 15.00 0.65p & = 15.00 p & = frac<<15.00>><<0.65>> = 23.0769end]

So, with rounding it looks like the shirt was originally sold for $23.08.

Distance/Rate Problems

These are some of the standard problems that most people think about when they think about Algebra word problems. The standard formula that we will be using here is

All of the problems that we’ll be doing in this set of examples will use this to one degree or another and often more than once as we will see.

Let’s let (t) represent the amount of time that the cars are traveling before they meet. Now, we need to sketch a figure for this one. This figure will help us to write down the equation that we’ll need to solve.

From this figure we can see that the Distance Car A travels plus the Distance Car B travels must equal the total distance separating the two cars, 500 miles.

Here is the word equation for this problem in two separate forms.

We used the standard formula here twice, once for each car. We know that the distance a car travels is the rate of the car times the time traveled by the car. In this case we know that Car A travels at 100 mph for (t) hours and that Car B travels at 70 mph for (t) hours as well. Plugging these into the word equation and solving gives us,

So, they will travel for approximately 2.94 hours before meeting.

For this problem we are going to need to be careful with the time traveled by each car. Let’s let (t) be the amount of time that the slower travel car travels. Now, since the faster car starts out 1 hour after the slower car it will only travel for (t - 1) hours.

Now, since we are repeating the problem from above the figure and word equation will remain identical and so we won’t bother repeating them here. The only difference is what we substitute for the time traveled for the faster car. Instead of (t) as we used in the previous example we will use (t - 1) since it travels for one hour less that the slower car.

Here is the equation and solution for this example.

[egin100left( ight) + 70t & = 500 100t - 100 + 70t & = 500 170t & = 600 t & = frac<<600>><<170>> = 3.529412>end]

In this case the slower car will travel for 3.53 hours before meeting while the faster car will travel for 2.53 hrs (1 hour less than the slower car. ).

Let’s start off by letting (r) be the speed of the boat on the right (the slower boat). This means that the boat to the left (the faster boat) is moving at a speed of 2(r). Here is the figure for this situation.

From the figure it looks like we’ve got the following word equation.

Upon plugging in the standard formula for the distance gives,

For this problem we know that the time each is 5 hours and we know that the rate of Boat A is 2(r) and the rate of Boat B is (r). Plugging these into the work equation and solving gives,

[egin100 + left( r ight)left( 5 ight) & = left( <2r> ight)left( 5 ight) 100 + 5r & = 10r 100 & = 5r 20 & = rend]

So, the slower boat is moving at 20 mph and the faster boat is moving at 40 mph (twice as fast).

Work/Rate Problems

These problems are actually variants of the Distance/Rate problems that we just got done working. The standard equation that will be needed for these problems is,

As you can see this formula is very similar to the formula we used above.

Let (t) be the time that it takes both machines, working together, to stuff a batch of envelopes. The word equation for this problem is,

We know that the time spent working is (t) however we don’t know the work rate of each machine. To get these we’ll need to use the initial information given about how long it takes each machine to do the job individually. We can use the following equation to get these rates.

Let’s start with Machine A.

Plugging these quantities into the main equation above gives the following equation that we need to solve.

So, it looks like it will take the two machines, working together, 1.875 hours to stuff a batch of envelopes.

Let (t) be the amount of time it would take John to clean the office complex by himself. The basic word equation for this problem is,

This time we know that the time spent working together is 3.5 hours. We now need to find the work rates for each person. We’ll start with Mary.

Now we’ll find the work rate of John. Notice however, that since we don’t know how long it will take him to do the job by himself we aren’t going to be able to get a single number for this. That is not a problem as we’ll see in a second.

Notice that we’ve managed to get the work rate of John in terms of the time it would take him to do the job himself. This means that once we solve the equation above we’ll have the answer that we want. So, let’s plug into the work equation and solve for the time it would take John to do the job by himself.

So, it looks like it would take John 11.67 hours to clean the complex by himself.

Mixing Problems

This is the final type of problems that we’ll be looking at in this section. We are going to be looking at mixing solutions of different percentages to get a new percentage. The solution will consist of a secondary liquid mixed in with water. The secondary liquid can be alcohol or acid for instance.

The standard equation that we’ll use here will be the following.

Note as well that the percentage needs to be a decimal. So if we have an 80% solution we will need to use 0.80.

Okay, let (x) be the amount of 50% solution that we need. This means that there will be (x + 10) gallons of the 40% solution once we’re done mixing the two.

Here is the basic work equation for this problem.

Now, plug in the volumes and solve for (x).

So, we need 5 gallons of the 50% solution to get a 40% solution.

Let (x) be the amount of water we need to add to the 40% solution. Now, we also don’t how much of the 40% solution we’ll need. However, since we know the final volume (75 liters) we will know that we will need (75 - x) liters of the 40% solution.

Here is the word equation for this problem.

Notice that in the first term we used the “Amount of acid in the water”. This might look a little weird to you because there shouldn’t be any acid in the water. However, this is exactly what we want. The basic equation tells us to look at how much of the secondary liquid is in the water. So, this is the correct wording. When we plug in the percentages and volumes we will think of the water as a 0% percent solution since that is in fact what it is. So, the new word equation is,

Do not get excited about the zero in the first term. This is okay and will not be a problem. Let’s now plug in the volumes and solve for (x).

[eginleft( 0 ight)left( x ight) + left( <0.4> ight)left( <75 - x> ight) & = left( <0.15> ight)left( <75> ight) 30 - 0.4x & = 11.25 18.75 & = 0.4x x & = frac<<18.75>><<0.4>> = 46.875>end]

So, we need to add in 46.875 liters of water to 28.125 liters of a 40% solution to get 75 liters of a 15% solution.

Math 401: Applications of Linear Algebra, Fall 2019

“Linear Algebra and Its Applications” by Gilbert Strang
Other supplementary materials will be posted.

C- or better in one of MATH 240 or MATH 461 or MATH 341

There will be 5 homework. Each one is 40 points. You will need to use Matlab for some problems.

You need to submit homework online through ELMS. Only PDF files are accepted.

Do 11.3 using this photo:Halloween (The size is 650𴦉, not squared! There are 433 singular values including zeros).
For (a)-(g), you need to convert to grayscale first.
Note: Because the size is not squared, you have to use Ex 11.6 to answer part (g) about the compression ratio (I mentioned how to do it in the class).

Also add this as part (h):
Use SVD to compress R, G and B channels by keeping 50 singular values and then stack back to get a compressed colored image and print it. (Scale R, G and B values between 0 and 1, do SVD, get new matrices and then multiply 255 to get back RGB values)

8.3.1 (using the simplex method for both problems), then interpret both problems in terms of shopper and druggist as on page 380 and 392.

Solve the above two problems by hand.

Use Matlab to solve the production planning problem on Page 380.

8.4.1 (set up the corresponding linear programming problem, solve it in Matlab, and then find the cut)

Problem 8 on page 36 (book page 262) of this pdf (use Matlab)

2 exams (100 points each) + a final (100 points, not cumulative).
The lowest one will be counted as half

Homework: 5吤=200
Exams: 250
Total: 450
Grades will be A=90-100%, B=80-90%, C=70-80%, D=60-70%. These cutoffs may be subject to change as the course progresses.

Makeup Exams:
There will be no make-up exams. With legitimate excuses, the next exam score will be scaled to cover the missing exam. For example, If you missed exam 1, then:
Your exam 1 score=your exam 2 score/ class average of exam 2 × class average of exam 1

If you are a student with a recognized disability, I’m pleased to discuss academic arrangements with you. Please see me as early in the term as possible.
Academic Integrity:
You are expected to read carefully and adhere to the following instruction provided by the Student Honor Council:

Course Schedule
We will cover at least Chapter 2-12.

Comparison of different methods for Least Squares:

Supplementary material (only section 11.2):

This is one issue here in the choice of signs for eigenvectors for SVD in Justin’s notes.
You can find explanation here (page 3):

So I prefer using the book of Math 240:
It also explains pseudoinverse and reduced SVD.

Besides the book, just read the transportation problem and the assignment problem on section 8.2 of this pdf
If the availability is bigger than the requirement, then you need to change the equation signs to the inequality signs for constraints that correspond to availability.

The book doesn’t contain a good example for Game Theory.
Look at this link for a concrete example which uses linear programming to solve a game theory problem.
Note: we use column for play A and row for play B. You should check max of column min and min of row max for homework 5.

Karush–Kuhn–Tucker (KKT) conditions (Lagrange multipliers for inequalities)

This will be the probably easiest notes about KKT online:
Note that g_i(x) <= 0 should also be in “Inequality constraints”.

Those conditions are really called Primal feasibility, Dual feasibility Complementary slackness as in:

You can also watch this YouTube video:
But the above notes is already very clear and readable.

Once you set up the dual problem which is a QP optimization problem, then you can solve it in Matlab:

Since QP (quadratic programming) is NLP (nonlinear programming) problem, I won’t talk about it in the class.

Linear Program Solver

Linear Program Solver (LiPS) is an optimization package oriented on solving linear, integer and goal programming problems.
The main features of LiPS are:
● LiPS is based on the efficient implementation of the modified simplex method that solves large scale problems.
● LiPS provides not just an answer, but a detailed solution process as a sequence of simplex tables, so you can use it for studying/teaching linear programming.
● LiPS gives sensitivity analysis procedures, which allow us to study the behaviour of the model when you change its parameters, including: analysis of changes in the right sides of constraints, analysis of changes in the coefficients of the objective function, analysis of changes in the column/row of the technology matrix. Such information may be extremely useful for the practical application of LP Models.
● LiPS provides methods of goal programming, including lexicographic and weighted GP methods, which are oriented on multi-objective optimisation.

Lesson All about Linear Programming

Units serve as guides to a particular content or subject area. Nested under units are lessons (in purple) and hands-on activities (in blue).

Note that not all lessons and activities will exist under a unit, and instead may exist as "standalone" curriculum.

TE Newsletter

One application of linear optimization is space allocation and efficient facility usage.


Engineering Connection

In order to design the best solution to a problem, engineers frequently aim to maximize the quantity of a particular design element (such as a material) or minimize a quantity (such as cost). To do this, they design within a set of constraints that are sometimes given by the client and other times simply the limitations of the amounts and types of available resources. During the engineering design process, it can be helpful to predict the expected outcomes of different approaches before creating and testing prototypes. While not every situation is suitable for quick and accurate prediction, certain scenarios are ideal. For instance, when every constraint can be fit to a linear mathematical model, then a technique known as “linear programming” can be used to find the optimum solution. Examples of engineering applications of linear programming include optimizing the energy use cost in a building system analysis, material analysis of a truss, and space optimization in city planning, office design and grocery store shelves.

Learning Objectives

After this lesson, students should be able to:

  • Describe linear programming as finding the “best” solution to a problem.
  • Define and apply the following engineering design terms: constraint, feasible, optimize.
  • Use linear programming to solve example real-world engineer design problems.

Educational Standards

Each TeachEngineering lesson or activity is correlated to one or more K-12 science, technology, engineering or math (STEM) educational standards.

All 100,000+ K-12 STEM standards covered in TeachEngineering are collected, maintained and packaged by the Achievement Standards Network (ASN), a project of D2L (

In the ASN, standards are hierarchically structured: first by source e.g., by state within source by type e.g., science or mathematics within type by subtype, then by grade, etc.

NGSS: Next Generation Science Standards - Science

HS-ETS1-3. Evaluate a solution to a complex real-world problem based on prioritized criteria and trade-offs that account for a range of constraints, including cost, safety, reliability, and aesthetics, as well as possible social, cultural, and environmental impacts. (Grades 9 - 12)

Do you agree with this alignment? Thanks for your feedback!

Alignment agreement: Thanks for your feedback!

Alignment agreement: Thanks for your feedback!

Alignment agreement: Thanks for your feedback!

Common Core State Standards - Math

Do you agree with this alignment? Thanks for your feedback!

Do you agree with this alignment? Thanks for your feedback!

Do you agree with this alignment? Thanks for your feedback!

International Technology and Engineering Educators Association - Technology
  • Students will develop abilities to use and maintain technological products and systems. (Grades K - 12) More Details

Do you agree with this alignment? Thanks for your feedback!

Do you agree with this alignment? Thanks for your feedback!

State Standards
Colorado - Math
  • Linear measure, angle measure, area, and volume are fundamentally different and require different units of measure. (Grade 7) More Details

Do you agree with this alignment? Thanks for your feedback!

Worksheets and Attachments

More Curriculum Like This

Student groups work with manipulatives—pencils and trays—to maximize various quantities of a system. They work through three linear optimization problems, each with different constraints and construct mathematical arguments for why their solutions are the best ones before attempting to maximize a di.

Students learn about the first attempts at machine learning and specifically about the perceptron model—a simplified model of a biological neuron.

Learn the basics of the analysis of forces engineers perform at the truss joints to calculate the strength of a truss bridge known as the “method of joints.” Find the tensions and compressions to solve systems of linear equations where the size depends on the number of elements and nodes in the trus.

Students learn about nondestructive testing, the use of the finite element method (systems of equations) and real-world impacts, and then conduct mini-activities to apply Maxwell’s equations, generate currents, create magnetic fields and solve a system of equations. They see the value of NDE and FEM.

Pre-Req Knowledge

A familiarity with graphing linear inequalities.


(Be ready to write on the classroom board. Have ready printouts of a problem statement to hand to each student. To do this, cut apart enough copies of the Lesson Problem Statement each sheet has the problem statement written five times. Alternatively, write the problem statement on the classroom board. In addition, have ready copies of the Linear Programming Practice Problems Worksheet, one per student. Also make sure students have pencils and calculators handy.)

(IF STUDENTS HAVE previously completed the Optimizing Pencils in a Tray activity, read the following paragraph.) A few class periods ago, we experimented with some pencils of varying lengths to see if we could determine how many pencils of each size were needed to maximize a few quantities such as number of pencils in the tray, or total length of pencils in the tray. Engineers frequently want to maximize quantities like these, or minimize quantities, such as cost, in order to determine the best solutions to problems. It turns out that if the situation is well-defined, a more efficient, analytical approach can be taken to find the answer. We are going to examine a similar problem to the one we solved last time in this new way.
(IF STUDENTS HAVE NOT previously completed the Optimizing Pencils in a Tray activity, read the following paragraph.) When creating a solution to an engineering design problem, engineers want to determine the best possible solution. Sometimes, the best solution may be the cheapest one or perhaps the strongest one. It turns out that if the situation is well-defined, an efficient, analytical approach can be taken to maximize a quantity like strength, or minimize a quantity like cost. We are going to examine a problem to learn about this method.

(Show students a written copy of the following problem, either by handout or writing it on the classroom board.) Here’s the problem statement. Your objective is to place some pencils in a tray such that they are stable. This means that you must align the long axes of the pencils with the groove in the tray. You know that a golf pencil (x) is 3.5-inches long and a regular pencil (y) is 7.5-inches long. The tray has room for no more than 52.5 linear inches of pencils (the groove is 52.5 inches long). How many of each pencil are needed in order to maximize the total number of pencils in the tray? (If students rapidly arrive at the intuitive solution—to just use as many of the short golf pencils as fit [15 of them]—tell them the following.) Although that sounds reasonable, instead of guessing the answer, we are going to develop a process to guarantee the correct solution AND give us a mathematical method that can be used for more complicated problems that are not as straightforward to guess.

In this problem, many different ways are possible to place pencils in the tray. For instance, we could place two long pencils, five short pencils, one of each, etc. We could try each one of these options and come up with a solution that way (trial and error), but in order to do that we would need a list of all the possible options. If we could define for ourselves which combinations of pencils are possibilities, we would have a much clearer perspective on the problem. In order to do that, we want to look at the limiting cases. What numbers of pencils either don’t make sense or are not allowed in this problem?

(If students struggle to respond at this point, call attention to a number line. Either point to one in your classroom or draw one on the board. Remind them of the following.) X represents the number of golf pencils and Y represents the number of regular pencils, but without further information, X and Y are just variables that represent numbers. This means they can take any value on the number line. Do any values on the number line not make sense for either the number of golf pencils in the tray (X) or the number of regular pencils in the tray (Y)?

(It is important that students come up with the following two restrictions.) Yes, that’s right: X cannot be negative, and Y cannot be negative. This is because having a negative number of pencils in a tray does not make sense. (Students may also come up with the restriction that X and Y must be integers because the problem does not permit us to cut the pencils into pieces or sharpen them to be shorter. This restriction is not critical to solving the problem since it has been designed to produce integer solutions already, but is a valid discussion point, so acknowledge it as such if it is suggested.)

(Write the word “constraints” on the board and underline it.) I’m going to write down your ideas so I don’t lose track. For now, I’m just going to call them “constraints.” By “constraint” we just mean a rule or restriction—something that must be obeyed in solving a problem—and I think that is a good description for all of your ideas so far. (If desired, make note of the term “constraint” on a class vocabulary list elsewhere on the board.)

(Write “X cannot be negative” below the underline, and “Y cannot be negative” under that. Also write “X must be an integer” and “Y must be an integer” IF students came up with those ideas.) So far, we have that X cannot be negative and Y cannot be negative. What are some ideas you have for different ways to write these statements? For example, how could you rephrase these statements using different words, or represent them using numbers and symbols?

(Ultimately, we want to get to the inequalities X ≥ 0 and Y ≥ 0. If students come up with X or Y must be positive as an alternate rephrasing, ask them the following.) Do all the positive numbers and all the negative numbers taken together represent everything on the number line? (See if students provide the following response.) Zero is neither positive or negative, and so saying X or Y must be positive leaves out zero, which perfectly meets the original constraint that X or Y cannot be negative, since zero is not negative. A way to say “either positive or zero” more cleanly is to say “non-negative.” (Write “X must be non-negative” and “Y must be non-negative” next to the original two constraints IF students choose to rephrase before coming up with mathematical symbol representations.) Yet another way to say “either positive or zero” is “at least zero.” (Write this on the board next to the original constraints as well.) What do you remember about how to write “at least zero” using a symbol and the number zero? (If students struggle, remind them that it has something to do with the word “inequality.” Expect them to eventually get to X ≥ 0 and Y ≥ 0. Once they do, write this next to the corresponding verbal representations.)

Great! This is pretty cool, since now we have managed to come up with some concise math notation out of a wordy word problem. Seeing X ≥ 0 and Y ≥ 0 reminds me of something. What do you remember about graphing inequalities? (Expect students to recall that you first graph the line represented by the inequality, which is dashed if there is no “or equals” and solid otherwise, then shade the appropriate side of it.) I’m going to graph these inequalities to see if it helps me get a better handle on what combinations of pencils are allowed. (Graph the inequalities. Refer to Figure 1 to see how the lines for these are shown as lines AC and AB, respectively, although the shading, which would be to the right and above these lines, respectively, is not shown.) Hmmm… So if I graph these two inequalities, I am left with all of quadrant 1. I feel like this cannot be right though, because quadrant 1 contains some really large ordered pairs that I don’t think make sense in this problem. For instance, (1000, 1000) exists in this quadrant, but I don’t think I could possibly fit 1,000 golf pencils and 1,000 regular pencils in a 52.5-inch slot. What ideas do you have about how we may be able to get through this dilemma?

Figure 1. Graph of feasibility for the pencil tray problem.

(Expect students to come up with the limitation that the total length of pencils must be less than 52.5 inches. Write this under “constraints” as the third item in the list.) We know that X is the total number of golf pencils, which are each 3.5-inches long, and that Y is the total number of regular pencils, which are each 7.5-inches long. We should be able to write this as 3.5x + 7.5y ≤ 52.5. (Write this next to the third verbal constraint.) I can graph this one the same as the others, but I just need to isolate Y first. When I do, I get y ≤ -7/15*x + 7. (Graph this inequality. The line for this inequality can be seen as line BC in Figure 1, although the shading, which would be to the lower left of this line, is not shown.) Oh, now the shaded region is a triangle! This makes a lot more sense since now that I cannot include those really big values.

The shaded region is the area of the coordinate plane containing coordinate pairs that meet all three constraints. Let’s not just call it the “shaded region” anymore since that is pretty vague. Let’s start calling it the “feasibility region.” What does feasible mean? (See what students think.) “Feasible” has a similar meaning to “plausible” or “possible.” This is a fitting name since the values in the feasibility region are all the possible values that X and Y can take. (Write “feasibility region” on the class vocabulary list.)

(Note: The graph of this feasibility region along with the intersection points is shown in Figure 1. The optimization equation is z = x + y. In this case, point B is the winner, since the values of z for points A, B and C are 0, 15 and 7, respectively. Note that the total length of the tray has been changed from the Optimizing Pencils in a Tray associated activity. This is because 52.5, as also explained in the Lesson Background section, is the minimum length that allows for the intersection points to be integers, since in the case in which the total length is 18.5 inches, the maximum number of pencils would be 5.29 golf pencils. Only integer quantities were allowed however, which is why 52.5 was chosen as the length instead.)

Now we finally have a well-defined set of possible combinations of pencils. This means we can start to think about what the problem is really asking, which is the question at the end of the word problem. “How many of each pencil should you use in order to maximize the total number of pencils on the tray?” So we want to maximize something, and the thing we want to maximize is the total number of pencils on the tray. Let’s call the total number of pencils on the tray “Z.” What ideas do you have for how we can write a mathematical definition for “Z” using the variables we already know? (Expect students to come up with z = x + y, or the sum of the number of golf pencils and the number of regular pencils.) Okay, yes, I think that z = x +y is an equation that describes our situation pretty well. Let’s call it the “maximization equation” since it is the equation describing the quantity we want to maximize. Sometimes though, we don’t want the most and would rather have the least. For instance, what if Z represented cost instead of length? Would you rather have the highest possible cost or lowest possible cost? Since sometimes we want to minimize quantities like cost and sometimes we want to maximize quantities such as length, let’s call Z the “optimization equation.” Optimize means “to create the best solution for,” which can include both maximization and minimization cases. (Add “optimization equation” to the class vocabulary list. Also write and underline “optimization equation” and write z = x + y below it.)

Now that we have everything set up, all we have to do is “plug and chug.” We have the equation we want to maximize and a set of possible X and Y coordinate pairs to use. We just need to plug each possible coordinate pair into the optimization equation and figure out which makes Z the biggest. With such a big feasibility region, that may be the most time-consuming part of this problem!

Fortunately, I know a way to take a massive shortcut. It has been mathematically proven that both the maximum value and the minimum value of an optimization equation each take place on one of the endpoints of the feasibility region. The endpoints are the points where the various inequality lines intersect. (Add “endpoints” or “corner points” to the class vocabulary list.) In this case, we have three such points. They are (0, 0), (0, 7) and (15, 0). (This corresponds to points A, C and B, respectively, in Figure 1.) This means we only need to plug each of these three values into Z and see which value is the largest. We should get z (0, 0) = 0 + 0 = 0, z (0, 7) = 0 +7 = 7 and z (15, 0) = 15 + 0 = 15. In this case, 15 is the largest value, which means that (15, 0) is the coordinate pair representing the solution. This means that in order to have the greatest number of pencils in the tray, we should place 15 golf pencils and 0 regular pencils. This makes sense since we could fit into the tray the most pencils by using only the shortest pencils. Note that if for some reason we wanted to minimize the number of pencils instead of maximize it, the entire problem would have been the same, with the only difference that we would choose (0, 0) as the solution coordinate pair since z (0, 0) = 0 was the minimum value produced out of the three.

The type of problem we just solved is called “linear programming.” Only two common ways exist to make this type of problem more difficult. One is by increasing the number of constraints to something larger than three. This means you may have four or five, etc., inequality lines on your graph. The other way is by making the optimization equation slightly more complicated than z = x + y. For instance, z = 2x-3y. Besides these two changes, the problems generally look the same.

Now, I’m going to give you a chance to work through some linear programming practice problems that represent real engineering design problems. (Hand out the worksheets.) Each person needs to fill out his/her own worksheet, however you may discuss the problems amongst the people at your table if you want to bounce ideas off of someone. If you get stuck and your table group also does not have any ideas for how to move forward, then raise your hand and I will come by to get you moving again.

(Write the following example problems on the board, which are the same problems on the worksheet. Refer to the Linear Programming Practice Problems Answer Key for the answers with the work shown.)

Problem 1: A storage solutions company manufactures large and small file folder cabinets. Large cabinets require 50 pounds of metal to fabricate, and small cabinets require 30 pounds, but the company has only 450 pounds of metal on hand. If the company can sell each large cabinet for $70 and each small cabinet for $58, how many of each cabinet should it manufacture in order to maximize income? (Answer: 15 small cabinets.)

Problem 2: You are a civil engineer designing a bridge. The walkway needs to be made of wooden planks. You are able to use either Sitka spruce planks (which weigh 3 pounds each), basswood planks (which weigh 4 pounds each), or a combination of both. The total weight of the planks must be between 600 and 900 pounds in order to meet safety code. If Sitka spruce planks cost $3.25 each and basswood planks cost $3.75 each, how many of each plank should you use to minimize cost while still meeting building code? (Answer: 150 basswood planks.)

Lesson Background and Concepts for Teachers

Constraints are linear inequalities graphed on the x-y plane. The intersection area of all inequalities is called the “feasibility region.” The “optimization equation” is a function of x and y that you wish to maximize or minimize. It has been proven that the maximum and minimum values of the optimization equation are always at the intersection points of the inequalities (the “corners” of the feasibility region). Because of this, if the problem involves discrete quantities (as most do), it is important to design the constraints such that their intersection x and y coordinates are both multiples of the smallest discrete unit. This is typically 1, in which case the coordinates of intersection must be integers, although a problem could be designed such that the smallest discrete unit is something other than 1. For example, the problem might involve purchasing objects that are packaged and sold in half-pound quantities (in which case the intersection coordinates of the constraints are multiples of ½) or perhaps in pairs like socks (in which case the intersection coordinates of the constraints are multiples of 2).

Also note that if the optimization equation is linearly dependent on any single constraint, then all points on the portion of the line representing that constraint between the two interior intersection points on that line are valid solutions. This means that both intersection points on this line have the same value and this value is the maximum or minimum.

Also note that if any constraint is linearly dependent on two other constraints, it is simply another line that intersects the feasibility region at only the intersection of the two other constraints, and therefore does not create a new corner point. If any constraint is linearly dependent on more than two other constraints, all points on that line are outside the feasibility region as defined by the other constraints, so it also does not create any new corner points. In both cases above, the constraints are adding no new information, which is why they either only intersect the feasibility region at a pre-existing corner point, or not at all.

Lastly, note that in most linear programming problems, two of the constraints are x >= 0 and y >= 0, since in problems involving objects, negative quantities are not allowed.

Associated Activities

  • Optimizing Pencils in a Tray - Student groups work with two sizes of pencils and a tray to maximize various quantities of the system. They work through three linear optimization problems with different constraints. They construct mathematical arguments for why their solutions are the best ones. Consider conducting this activity before the Linear Programming lesson.

Lesson Closure

What are some examples of when engineers want to optimize a quantity? (See what ideas students have.) Aerospace engineers who design spacecraft to fit in the payload fairing (nose cone) of the launch vehicle. Civil and architectural engineers who plan cities within the boundaries of a particular plot of land. Electrical and computer engineers who design circuit boards that fit inside the newest slim smartphone, tablet or laptop. Civil and environmental engineers who plan human-created waterways that are big enough to carry the water needed by a city during peak demand. Mechanical engineers who design engines that are small enough to fit into lawnmowers, cars, golf carts, go-karts and other equipment and appliances. What’s the key thing to remember? If the constraints are linear—that is, x and y are not raised to a power other than 1, or stuck inside another function such as sine—then linear programming can be used to design the optimal solution.


constraint: A limitation or restriction—something that must be obeyed in solving a problem. A restriction on possible values of x and y.

feasibility: Plausible or possible.

feasibility region: The intersection area of all constraints when graphed as inequalities. The values in a feasibility region are all the possible values of X and Y.

linear programming: A method to determine the best outcome in a design situation in which the requirements are represented by linear relationships. Also called linear optimization.

optimization equation: The function of x and y that you wish to maximize or minimize.

optimize: To select the best solution, with regard to some criterion, from a set of alternatives.


Example Problems: As a class, students work through the Lesson Problem Statement about maximizing the total number of pencils that fit in a tray, given two lengths of pencils, guided by the teacher (as fully explained via the Introduction/Motivation section). Then, students individually work through two problems presented in the Linear Programming Practice Problems Worksheet. Review students’ answers and work to gauge their comprehension of the concepts.



Supporting Program


This activity was developed by CU Teach Engineering, a pathway to STEM licensure through the Engineering Plus degree program in the College of Engineering and Applied Science at the University of Colorado Boulder.

End Notes

I hope you enjoyed reading this article. I have tried to explain all the basic concepts under linear programming. If you have any doubts or questions feel free to post them in the comments section. For easy understanding, we have broken this long article into a shorter course format – Linear Programming for Data Science Professionals

I have explained each concept with a real-life example. I want you to try them at your end and get hands-on experience. Let me know what you think!

Watch the video: Τι δεν σου είπαν στο σχολείο για τον επαγγελματικό προσανατολισμό. Spyros Michaloulis. TEDxAUEB (November 2021).