how do you solve linear programming word problems

Linear Programming Word Problems

Solution of exercise 1, solution of exercise 3.

Step 1 - Identify the decision variables

x = number of lamps L 1

y = number of lamps L 2

Step 2 - Write the objective function

Write the objective function .

Step 3 - Write the set of constraints

Write the constraints as a system of inequalities .

Convert the time from minutes to hours.

20 min = 1/3 h

30 min = 1/2 h

10 min = 1/6 h

As the number of lamps are natural numbers, there are two more constraints:

Step 4 - Choose the method to solve the problem

We will solve this problem graphically.

Step 5 - Construct the graph

Find the set of feasible solutions that graphically represent the constraints .

Represent the constraints graphically.

Solve the inequality graphically:

Take a point on the plane, for example (0,0).

Step 6 - Find the feasibility region of the graph

The area of intersection of the solutions of the inequalities would be the solution to the system of inequalities, which is the set of feasible solutions.

Step 7 - Find the optimum point

Calculate the coordinates of the vertices from the compound of feasible solutions.

The optimal solution, if unique, is a vertex . These are the solutions to systems:

Calculate the value of the objective function at each of the vertices to determine which of them has the maximum or minimum values.

In the objective function, place each of the vertices that were determined in the previous step .

Step 2 - Write the objective function .

Step 3 - Identify the constraints

Step 6 - Find the feasibility region

The grey highlighted area represents the feasibility region.

Calculate the value of the objective function at each of the vertices to determine which of them has the maximum or minimum values. It must be taken into account the possible non-existence of a solution if the compound is not bounded.

Did you like this article? Rate it!

I am passionate about travelling and currently live and work in Paris. I like to spend my time reading, gardening, running, learning languages and exploring new places.

Linear Programming Examples

Steps to solve a linear programming problem, linear programming, linear programming problems and solutions, cancel reply.

Your comment

Current ye@r *

Leave this field empty

Please help to do this qutions, Ethio Manufacturing, a renowned company in Ethiopia, specializes in producing two types of products: Product A and Product B, with the primary objective of maximizing its total profit. Each unit of Product A yields a profit of 5 Birr, and each unit of Product B yields a profit of 4 Birr. The company is constrained by limited resources in two vital departments: Department A, with 60 hours of available production time, where producing one unit of Product A consumes 3 hours and one unit of Product B consumes 2 hours; and Department B, with 72 hours of available production time, where producing one unit of Product A takes 4 hours and one unit of Product B takes 3 hours. Questions 1. Formulate the Linear Programming Problem (LPP): 2.Graphically analyze the LPP to determine the optimal production quantities of Product A and Product B that maximize Ethio Manufacturing’s profit. Identify the coordinates of the optimal solution point. 3. Apply the simplex method to find the optimal solution for Ethio Manufacturing’s LPP. Present the initial tableau, pivot steps, and the final solution. Explain each step in the simplex method. 4. Determine the dual problem for Ethio Manufacturing’s LPP and present the dual problem’s objective function and constraints. 5a. Discuss the changes in objective-function coefficients (cj) of the optimal basic feasible solution 5b. Discuss the effect of discrete change in the avaliabilty of resources from [60, 72 ]T to [70, 50]T

Hi pls hw d u obtain d constraints in for truck type B in exercise 1

Wow, this is so understandable but to some point tho. I don’t really understand how you plot the graph. Pls can you put me through

hello, I have a question regarding on the constraints given in exercise 3. Should it be x + y leq 200 3x + y leq 100 x geq 20 y geq 10

Since it has been stated that in offer A, the package consists of one shirt and a couple of pants while in offer B, it is consists of three shirts and a pair of pants?

Can you please help to answer these problem?

Formulate the mathematical model of the given problems. Use a table as preliminary phase in the formulation of the model.

1. A farmer has 40 hectares of farm on which to plant rice and corn. The rice needs 4 units of insecticide and 2 units of fertilizer per hectare, while corn requires 3 units of insecticide and 6 units of fertilizer. He has at least 90 units of insecticide and at least 120 units of fertilizer available. His average profit per hectare on rice is P15,000.00 and P10,000.00 on corn. How many hectares of each crop should he plant to maximize his average profit? 2. B-meg Company wants to mix exactly 700 pounds of a special kind of dog food. There are two principal ingredients in the mixture, both sources of protein P1 and P2. The first source of protein, P1 costs P50 a pound and P2 costs P80 per pound. Chemical constraints dictate that the mixture contains not more than 500 pounds of P1 and must contain at least 300 pounds of P2. How many pounds of each ingredient must be utilized in order to minimized the cost?

400 of P1, and 300 of P2.

Nice topic that I want learn

It is a nice work and is very useful for us.

Please can you help me solve this problem… ABC retail oparete in two locations A and B. The demand for a product in location A is 200 net, while in location B is 300 units. The production cost per unit in location A is 50 naira and location B is 40 naira. The company can produce a minimum of 400 units considering transportation cost of 10 naira per unit from location A to B. Formulate the linear programming problem to minimize the total cost of the retail of ABC.

• A linear programming word problem - with a surprise twist!

Today, I thought I'd tackle a problem from one of the most "popular" courses (read "required for almost all majors") at this school - finite math . For those of you who haven't heard of this course before, finite math is actually an amalgam of miscellaneous topics from probability theory, linear algebra, and stats, created by math departments at various universities as a way to introduce college freshmen to rigorous, analytical thinking. It's not a real field of mathematics, in the sense that you won't find any professional mathematicians who specialize in "finite mathematics." However, there are mathematicians who specialize in the topics introduced in this course, such as combinatorics and probability.

One of the topics covered in finite math ("finite", by those in the know) is linear programming. This is basically a fancy term for a constrained optimization problem consisting of linear constraints and a linear objective function. In this blog post, I will tackle the following problem, which I actually found on Yahoo Answers . Despite the title of the problem, it actually does not require calculus (though it could be solved with calculus). To restate the problem:

Example: Kustom Kars does van conversions. The custom conversion requires 15 hours of shop time, 8 hours of painting time, and 1 hour of inspection time. The deluxe conversion requires 12 hours of shop time, 12 hours of painting time, and 1.5 hours of inspection time. There are 90 hours of shop time, 72 hours of painting time, and 10 hours of inspection time available during the coming two weeks. How many conversions of each type should Kustom Kars perform assuming that each custom conversion results in $175 profit and each deluxe conversion results in $ 225 profit? What is the maximum profit ?

This is typical of these sorts of problems, where they present the information in paragraph form - i.e., the dreaded "word problem." The first thing we need to do is extract the relevant data. Notice that there are two types of numbers they give us: time (in hours) and profit (in dollars). One of these types of quantities is going to give us our constraints, while the other will tell us how to formulate the objective (if you don't know what "constraint" and "objective" mean, please take a moment to review your notes/textbook).

I've highlighted the key phrases that will help us distinguish which is which. "Time available" is a dead giveaway that we're looking at information for our constraints. We are constrained by the amount of time available . "Maximum profit," on the other hand, is talking about the objective function - our objective is to maximize profit.

The next step is to identify our variables. This is the part where I think a lot of students get caught up, in linear programming and word problems in general. The key here is to look at the objective function - profit, in this case. Which of the things mentioned in the problem will ultimately be used to calculate our profit? Well, let's take a look at this sentence: "each custom conversion results in $175 profit and each deluxe conversion results in $ 225 profit..." So, profit depends on the number of custom conversions and the number of deluxe conversions . These, my friends, are our variables.

Let's call the number of custom conversions \(x\) and the number of deluxe conversions \(y\) . Since we know how much profit they earn from each of these, we can write our objective function:

So our goal is to maximize \(P(x,y)\) . Great! Next, we have some constraints. These are given by the 2nd, 3rd, and 4th sentences of the problem: "The custom conversion requires 15 hours of shop time, 8 hours of painting time, and 1 hour of inspection time. The deluxe conversion requires 12 hours of shop time, 12 hours of painting time, and 1.5 hours of inspection time. There are 90 hours of shop time, 72 hours of painting time, and 10 hours of inspection time available..."

The easiest way to handle this data is to create a table:

From this, we can extract our constraints. First, notice that there are three "ingredients" that go into each type of conversion. Each of these ingredients can be expressed in terms of the number of conversions of each type that the company does:

Next, notice that there is a limit to the total shop time, painting time, and inspection time (bottom row of the table). This lets us construct the inequalities:

I've labeled these \(A\) , \(B\) , and \(C\) . I've also added two more "trivial" (actually, very important) constraints: \(x\geq 0\) and \(y\geq 0\) . These are important because we can't have a negative number of conversions. Between the objective function and these inequalities, we have a fully formed constrained optimization problem . In other words, we've transformed a situation in the real world into the world of math, where we can use everything we know about math to solve the problem, and then bring our answer back into the real world.

To solve this problem, we start by graphing the constraints. To do this, we first convert our inequalities into equalities. These equalities are basically equations of lines. Since lines can be completely defined by two points, all we need to do is find two points for each equation and draw a line between them. The easiest way to find two points is to first set \(x=0\) and solve for \(y\) , and then set \(y=0\) and solve for \(x\) . So, let's do that for each inequality constraint:

So for line \(A\) , we get the points \((0, 7.5)\) and \((6, 0)\) . For \(B\) , we get:

And for \(C\) , we get:

Plotting these six points, and drawing lines through the corresponding pairs of points for each constraint, we get this graph:

Since we're looking for the values of \(x\) and \(y\) that maximize profit, our solution will be a point on this graph. But, not just any point! It must be a point that obeys our constraints. Which points obey our constraints, you ask? To answer this question, we will identify what's known as the feasible region . Notice that the lines we just drew actually carve up the x-y plane into several pieces (some of which may not be completely bounded!) The feasible region is going to be one of these pieces, in which all points obey our constraints. The easiest way to find the feasible region is by picking a test point from each region, and plugging it into the constraints. If the point satisfies all the constraints, then that region is our feasible region.

We can also hazard a guess that, since all of our constraints involve "less than or equal to," that the feasible region will be the lower left hand section, above the \(x\) and \(y\) axes. To confirm this, pick the test point \((2, 2)\) :

Great! The point \((2, 2)\) (in red) satisfies all the constraints, so the region in which it lies is our feasible region. Notice that this region can also be looked at as a polygon (in this case, a quadrilateral). I've labeled the vertices of this polygon \(P\) , \(Q\) , \(R\) , and \(S\) , for reasons which will become clear in a moment.

Ok, now that we have our feasible region, how do we find the point that corresponds to our optimal solution? Well, we have a theorem called the maximum principle, which for 2D linear programming problems like this, tells us that the optimal solution (if it exists) will lie on one of the vertices (also known as corner points ) of the feasible region.

So, all we have to do is to test each of these points in our objective function, and find the point that gives us, in this case, the maximum profit. Well to do this, we need the coordinates of each point. The coordinates of \(P\) , \(Q\) , and \(S\) are easy: \(P\) is the origin, and \(Q\) and \(S\) are the same points that we used to construct lines \(A\) and \(B\) . But what about point \(R\) ? Well, \(R\) is simply the intersection of lines \(A\) and \(B\) . To find the intersection of two lines, recall that we need to solve them as a system of equations:

The easiest way to solve this is by subtracting the two equations, and then back-substituting:

Now that we have our four corner points, we can plug them into the objective function and find the profit for each \((x, y)\) pair:

Alright, so we just pick point \(R\) because that gives us the highest profit, right? No. Be careful. Remember that \(x\) and \(y\) correspond to real things - the number of custom and deluxe conversions. We can't have 2.57 jobs - or we'd have some very irate customers! We need to round these to whole numbers, such that they still satisfy all of the constraints. We could round to \((2, 4)\) , \((3, 5)\) , \((3, 4)\) , or \((2, 5)\) . Well, the only one of these points that won't violate one of our constraints is \((2, 4)\) , so we will update R with this point:

Once we round \(R\) to the nearest whole number, we need to recompute profit. Now, it's not the optimal point anymore - point \(S\) now gives us the highest profit! In a sense, we've introduced another constraint to the problem, namely, that \(x\) and \(y\) be integers. This type of constraint is actually a topic in of itself, integer programming, which we won't get into today. Suffice it to say, we've found the optimal solution to the problem: Kustom Kars (terrible name by the way), should do 0 custom conversions and 6 deluxe conversions for a profit of $1350.

Hope everyone enjoyed that!

Update (thanks to reddit user zifyoip ): when dealing with integer problems, rounding the non-integer points no longer guarantees us an optimal solution. For this problem it happened to work, but in general the best we can say is that the optimal profit is at least $1350. Thanks!

Like this article? Check out more posts about Finite Math....

• Probability with combinations
• How to understand and solve Leontief input-output model (technology matrix) problems
• Going steady (state) with Markov processes

• HW Guidelines
• Study Skills Quiz
• Find Local Tutors
• Demo MathHelp.com
• Join MathHelp.com

Select a Course Below

• ACCUPLACER Math
• Math Placement Test
• PRAXIS Math
• + more tests
• 5th Grade Math
• 6th Grade Math
• Pre-Algebra
• College Pre-Algebra
• Introductory Algebra
• Intermediate Algebra
• College Algebra

Linear Programming: An Example & A Word Problem

Intro How-To Word Problems More Examples Four Variables

Linear programming is often viewed as being quite difficult but, especially in our two-variable context, it's not so much that the process is hard, so much as that the process requires you to bring so many topics together to solve any one given exercise.

Content Continues Below

MathHelp.com

You'll need to be good at graphing straight lines, understanding inequalities (in a graphing context), solving systems of linear equations (to find corner points), and evaluation (to find the maximum / minimum of the optimization equation). So make sure that you're solid on these topics before attempting these exercises.

What are the steps for linear programming?

To solve linear-programming exercises:

Advertisement

• Solve the inequalities for y , if possible.
• For each inequality, use the "equals" version to graph the lines. For instance, y −  x + 4 ≤ 0 would convert to y =  x  − 4 for graphing.
• Graph each of the equation lines, and then shade according to the inequality symbols. The overlap is the feasibility region (that is, it's the area within which all valid solutions will lie).
• Pair up the equations for lines that cross each other in order to create systems of linear equations; solve these systems for the coordinates of the corners (that is, for the coordinates of the vertices) of the feasibility region.
• Test each corner's coordinates in the optimization equation they gave you.
• If you're needing to maximize, then take the corner that gives the largest answer to the optimization equation; otherwise, take the corner that gives the smallest answer.
• If the system of inequalities arose from a word problem, then go back and make sure that you are interpreting the values correctly according to the context.

Let's do another exercise that's just the inequalities and equations, before we try a word problem.

• Given the following constraints, maximize and minimize the value of z = −0.4 x + 3.2 y .

Okay; this system has a *lot* of inequalities. Four of the inequalities have one variable isolated on one side of the inequality symbol, which is the easier format for graphing. So now I'll solve the fourth and fifth constraints to isolate a variable:

The feasibility region looks like this:

Take note of the purple line for x  = 0 and the red line for y  = 0 . These are the y - and x -axes, respectively. When you deal (in later word problems) with situations based on real physical situations, you will almost always have the contraints that neither x nor y can be negative. So you should expect to see these constraints on a regular basis.

Also notice the vertical light green line for x  = 5 . Any time you have one variable that's set equal to just a number, then you'll have a vertical or horizontal line.

From the graph, I can see which lines cross to form what corners, so I know which lines to pair up in order to verify the vertex coordinates. I'll start at the top of the shaded area and work my way clockwise around the edges:

y = − x + 7

− x + 7 = x + 5

y = (1) + 5 = 6

corner point at (1, 6)

y = −(5) + 7 = 2

corner point at (5, 2)

[nothing to do]

corner point at (5, 0)

y = (−½} x + 2

(0) = (−½) x + 2

(½) x = 2

corner point at (4, 0)

y = (−½) x + 2

y = (−½)(0) + 2

y = 0 + 2 = 2

corner point at (0, 2)

y = (0) + 5 = 5

corner point at (0, 5)

Now I'll plug each corner point into the optimization equation, z = −0.4 x  + 3.2 y :

(1, 6):   z = −0.4(1) + 3.2(6) = −0.4 + 19.2 = 18.8 (5, 2):   z = −0.4(5) + 3.2(2) = −2.0 + 6.4   =   4.4 (5, 0):   z = −0.4(5) + 3.2(0) = −2.0 + 0.0   = −2.0 (4, 0):   z = −0.4(4) + 3.2(0) = −1.6 + 0.0   = −1.6 (0, 2):   z = −0.4(0) + 3.2(2) = −0.0 + 6.4   =   6.4 (0, 5):   z = −0.4(0) + 3.2(5) = −0.0 + 16.0 = 16.0

The max and min points are the points that give the largest and smallest values, respectively, when plugged into the optimization equation. Looking at my list, I see that my answer is:

maximum is 18.8 at (1, 6)

minimum is −2 at (5, 0)

When you are given the inequalities, linear-programming exercise are pretty straightforward, if perhaps sometimes a bit time-consuming. The hard part is usually the word problems, where you first have to figure out what the inequalities actually are. So I'll show how to set up some typical linear-programming word problems.

How do you solve linear programming word problems?

To solve a linear-programming word problem:

• Read through the entire exercise.
• Figure out what the exercise is asking for, using your translation skills.
• Pick variables to stand for the unknowns; label them clearly.
• Create inequalities for the various stated constraints. Don't forget to add the "understood" constraints when, in context, the variables cannot be negative.
• Create the optimization equation.
• Solve the linear programming system.
• Interpret the algebraic solution in terms of the original context.

Let's take a look at how this works in practice.

• At a certain refinery, the refining process requires the production of at least two gallons of gasoline for each gallon of fuel oil. To meet the anticipated demands of winter, at least three million gallons of fuel oil a day will need to be produced. The demand for gasoline, on the other hand, is not more than 6.4 million gallons a day.   If gasoline is selling for $1.90 per gallon and fuel oil sells for $1.50 /gal, how much of each should be produced in order to maximize revenue?

The question asks for the number of gallons which should be produced, so I should let my variables stand for "gallons produced".

x : gallons of gasoline produced y : gallons of fuel oil produced

(How did I know which variable to assign to the values? I didn't. There is no one right way. I could have used other variables, or reversed how x and y were matched up; it wouldn't have mattered. The numerical answer would still have been the same.)

Since this is a "real world" problem, I know that I can't have negative production levels, so the variables can't be negative. This gives me my first two constraints: namely:

Since I have to have at least two gallons of gas for every gallon of oil, then:

If you're not sure about this inequality — and many people have emailed with questions about this, so you wouldn't be alone — then try plugging some numbers in. For instance, if they make three gallons of fuel oil, so y  = 3 , then they have to make at least twice as many gallons of gasoline. "Twice as many" as three is six. Then x  ≥ 6 , and 6 = 2 y .

Keep plugging in numbers until the inequality makes sense to you.

The winter fuel-oil demand condition says that y  ≥ 3,000,000 ; note that this constraint eliminates the need for the " y  ≥ 0 " constraint. (Yes, one constraint can alter or eliminate another constraint. Real life is messy. Just go with it.) The gas demand condition says that x  ≤ 6,400,000 .

I need to maximize revenue R . The revenue from each of gas and fuel oil is the product of the per-gallon price and the number of gallons sold; the total revenue is the sum of the revenue from each. So the optimization equation is R  = 1.9 x  + 1.5 y . Then the model for this word problem is as follows:

R = 1.9 x + 1.5 y , subject to:

x ≤ 6,400,000

y ≥ 3,000,000

y ≤ (½) x

Using a scale that counts by millions (so " y = 3 " on the graph means " y is three million"), the above system graphs as follows:

Taking a closer look, I can see the feasibility region a little better:

To complete the exercise, plug the coordinates of the corner points — at (6.4 m , 3.2 m ) , (6.4 m , 3 m ) , and (6 m , 3 m ) — into the optimization equation.

You should get a maximal solution of R  = $16.96 m at ( x ,  y ) = (6.4 m , 3.2 m ) .

URL: https://www.purplemath.com/modules/linprog2.htm

Page 1 Page 2 Page 3 Page 4 Page 5

Standardized Test Prep

College math, homeschool math, share this page.

• Terms of Use
• Privacy / Cookies
• About Purplemath
• About the Author
• Tutoring from PM
• Advertising
• Linking to PM
• Site licencing

Visit Our Profiles

Lesson LINEAR PROGRAMMING PROBLEMS AND SOLUTIONS 1

Linear Programming

In these lessons, we will learn about linear programming and how to use linear programming to solve word problems.

Related Pages Linear Programming Graphing Linear Inequalities Systems of Linear Inequalities

Many problems in real life are concerned with obtaining the best result within given constraints. In the business world, people would like to maximize profits and minimize loss; in production, people are interested in maximizing productivity and minimizing cost. However, there are constraints like the budget, number of workers, production capacity, space, etc. Linear programming deals with this type of problems using inequalities and graphical solution method.

Example: On the graph below, R is the region of feasible solutions defined by inequalities y > 2, y = x + 1 and 5y + 8x < 92. Find the greatest value of 2y + x which satisfies the set of inequalities, where x and y are integers.

Solution: We are looking for integer values of x and y in the region R where 2y + x has the greatest value. We could substitute all the possible (x , y) values in R into 2y + x to get the largest value but that would be too long and tedious.

A better method would be to find the line 2y + x = c where x and y are in R and c has the largest possible value. In this case, the equation 2y + x = c is known as the linear objective function .

Solving Linear Programming Problems

Now, we have all the steps that we need for solving linear programming problems, which are:

Step 1: Interpret the given situations or constraints into inequalities.

Step 2: Plot the inequalities graphically and identify the feasible region.

Step 3: Determine the gradient for the line representing the solution (the linear objective function).

Step 4: Construct parallel lines within the feasible region to find the solution.

Example: Joanne wants to buy x oranges and y peaches from the store. She must buy at least 5 oranges and the number of oranges must be less than twice the number of peaches. An orange weighs 150 grams and a peach weighs 100 grams. Joanne can carry not more than 3.6 kg of fruits home. a) Write 3 inequalities to represent the information given above. b) Plot the inequalities on the Cartesian grid and show the region that satisfies all the inequalities. Label the region S. c) Oranges cost $0.70 each and peaches cost $0.90 each. Find the maximum that Joanne can spend buying the fruits.

Solution: a) at least 5 oranges: x ≥ 5 oranges less than twice of peaches: x < 2y not more than 3.6 kg: 150x + 100y ≤ 3600 ⇒ 3x + 2y ≤ 72

The maximum value is found at (5,28) i.e. 5 oranges and 28 peaches. Therefore, the maximum that Joanne can spend on the fruits is: 70  × 5 + 90 × 28 = 2870 cents = $28.70.

It also possible to test the vertices of the feasible region to find the minimum or maximum values, instead of using the linear objective function. The following videos gives examples of linear programming problems and how to test the vertices.

Linear Programming Example:

Maximize C = x + y given the constraints, y ≥ 0 x ≥ 0 4x + 2y ≤ 8 2x − y ≤ 0

Solving for Maxima-Minima

Maximize C = x + y given the constraints, − 3x + 2y ≤ 6 3x + y ≤ 3 y ≥ 0

Linear Programming Steps and Example

• Graph the inequalities and find the vertices.
• Compute the function at the vertices. Largest = Max, Smallest = Min.

Problem: Constraints are 240 acres of land. Profit $40/acre corn, $30/acre oats. Have 320 hrs available. Corn takes 2 hrs of labor per acre, oats requires 1 hr. How many acres of each should be planted to maximize profits?

How to solve a word problem using linear programming?

First, find the equation that needs to be maximized or minimized as well as create the corresponding inequalities and then solve.

Example: A rancher is mixing two types of food, Brand X and Brand Y, for his cattle. If each serving is required to have 60 grams of protein and 30 grams of fat, where Brand X has 15 grams of protein and 10 grams of fat and costs 80 cents per unit, and Brand Y contains 20 grams of protein and 5 grams of fat and costs 50 cents per unit, how much of each type should be used to minimize cost to the rancher?

Linear Programming Word Problem

Example: A refinery produces both gasoline and fuel oil, and sells gasoline for $1 per gallon and fuel oil for $0.90 per gallon. The refinery can produce at most 600,000 gallons a day, but must produce at least two gallons of fuel oil for every gallon of gasoline. At least 150,000 gallons of fuel oil must be produce each day to meet current demands. How much of each type of fuel should be produced to maximize daily profits?

We welcome your feedback, comments and questions about this site or page. Please submit your feedback or enquiries via our Feedback page.