Linear Programming Problems: Make Life Easier

linear programming problemsLinear what?! When you hear the words linear programming problems, your mind may just go blank. And yes, the name itself is a mouthful, but actually, linear programming is just really neat method of using math to find out how to best do something, like how much stuff to buy or make. It involves something called ‘constraints’ which is a system of linear inequalities. Basically, when you want to minimize cost and maximize profit, sometimes the only way to go about doing that accurately is solving it as a linear programming problem.

For a great foundation, here is a course called Algebra 1 that introduces basic algebraic skills and principles that would really come in handy in solving linear programming problems.

If you’ve ever wondered where it all started, as I’m sure you have, this way of finding answers to pertinent issues was actually developed for solving military logistics problems in World War II. These days, it is extensively used in business for maximizing profits and minimizing costs.It helps to clearly understand linear programming concepts and apply this correctly. Knowing basic concepts in math doesn’t hurt either. By the way, for a great math foundation, here is a course called Beginning Algebra: Building a Foundation that makes a great refresher course as well!

Situations that benefit from linear programming problems include material utilization decisions, quality control decisions purchasing decisions, exploration of oil deposits, fluid blending problems, product mix decisions, marketing, physical distribution decisions, warehousing decisions, production planning and long range planning. This attracts the attention of many practicing executives since many problems that come with managing companies usually have to do with making big decisions under limitations or constraints. Since linear programming deals with optimizing objectives desired in circumstances that involve limitations, it does not come as much of a surprise that this particular math equation comes in extremely useful especially in the area where big business is concerned.

More specifically, the process of taking various linear programming unequal amounts that relate to specific circumstances is called linear programming. Finding the best obtainable value with the given conditions is what you attempt to solve for.  This is the field of math that is concerned with minimizing or maximizing linear functions that have constraints. To solve for problems of linear programming, you need to meet the constraint requirements in a way that minimizes or maximizes the objective functions. It is important to solve these types of problems and in many fields like economics, business and operations research, is quite useful.  Some of these problems even come out in standardized tests in school. By the way if you are getting ready for the SAT’s here is an article called SAT Math Practice Problems: Getting Ready for One Tough Test that could help.

AKA Optimization Techniques 

In the real world, linear programming problems is part of an important mathematics area called optimization techniques. This math subject is used in everyday resource allocations, especially in companies that have to do with logistics. Generally, the process involved for solving linear optimization problems is to chart the inequalities in a graph. By the way, the term used to refer to an inequality is a ‘constraint.’ When graphing these, you need to form an area on the plane of x and y and wall this off. This is then called the region of ‘feasibility.’ You then need to find the feasibility region’s corner coordinates. Another way of saying this is to find where all the pairs intersect points. Once you see where each point intersects, a formula is used for testing the points, called an ‘optimization equation,’ which helps you find the lowest or the highest value. Studying for the ACT? Here is a course called The ACT Math Test Made Easy which you might want to take as it includes all types of math problems that usually appear in the ACT.

Linear Programming Problem #1:

Find the minimal and maximal value of z = 4y + 3x when under these constraints:

14 > 2y + x

0 < 3x – y

2 > x – y

Those inequalities above are the constraints. The plane area where these get marked off will be the region of feasibility. The optimization equation formula is z = 3x + 4y.  What I need to do is to find the corner points (x and y) of the region of feasibility that return the smallest and the largest values of z. The first thing I need to do is to solve each of the inequalities for the equivalent forms that are more easily graphed:

14 > x + 2y  à   -1/2 x + 7 > y

0 < 3x – y    à    3x > y

2 > x-y        à      x-2 < y

Next, plot this on a graph:

Linear Programming Problems

From the graph, you can see where the crossed lines are forming the corners. This way, you know which lines to make into pairs in order for the coordinates to get verified:

x= 5, y = 0x=5, y= -x + 7y= x+5, y= -x + 7
(you don’t need to do anything)2=-(5) + 7 =7x+5 = -x + 72x=2X=16=(1) + 5=y
Corner at (5,0)Corner at (5, 2)Corner at (1, 6)

 

x= 0, y = x+5x = 0, y = -(1/2) x+2y = 0, y = -(1/2) x+2
5= (0) +5 = y-(1/2) (0) + 2 = y0 + 2 = y2 = y0 = -(1/2) x + 2(1/2) x = 2X = 4
Corner at (0, 5)Corner at (0, 2)Corner at (4, 0)

 

Remember the optimization equation? The one that was: z = -0.4x + 3.2y? I will plug each of the corner points into this:

(0, 5):  z = –0.4(0) + 3.2(5) = –0.0 + 16.0 = 16.0

(0, 5):  z = –0.4(0) + 3.2(5) = –0.0 + 16.0 = 16.0

(0, 5):  z = –0.4(0) + 3.2(5) = –0.0 + 16.0 = 16.0

(0, 5):  z = –0.4(0) + 3.2(5) = –0.0 + 16.0 = 16.0

(5, 2):  z = –0.4(5) + 3.2(2) = –2.0 + 6.4   =   4.4

(1, 6):  z = –0.4(1) + 3.2(6) = –0.4 + 19.2 = 18.8

Then the maximum is at (5, 0) which equals -2 and the maximum is at (1, 6) at 18.8

Even if they are a bit long, the linear programing problems are pretty straightforward once you have the inequalities given. The word problems are usually the hard part since you need to figure out what numbers stand for inequalities. Here is a typical linear programming word problem:

Linear Programming Problem #2

Say you need to buy some new filing cabinets. You know that it is $10 per unit to buy Cabinet X, which holds 8 cubic feet of files and requires floor space of 6 square feet.  On the other hand, it is $20 for every unit of Cabinet Y which requires floor space of 8 square feet and holds about 5 cubic feet of files. For this purchase, you have been given $140 but don’t really have to spend all of it. The space in the office only has room for a maximum of seventy-two square feet of furniture. To maximize the volume of files you can store, how many of what model do you need to buy?

The variables will then be:

x= cabinet x purchased pieces

y= cabinet y purchased pieces

Where: x > 0 and y > 0

Because I need to consider the space allowed in the office and yet attempt to maximize volume of storage, the optimization equation will be the volume and the constraints will be floor space:

Volume:

v = 8x + 12y

Space:

6x + 8y < 72, or y < – (3/4) x + 9

Cost:

10x + 20y < 140, or y < – (1/2) x + 7

You can then graph this:

Linear Programming Problems

You should obtain a maximal volume of 100 cubic feet by buying eight of model X and three of model Y when you test the corner points at:

(12, 0)

(0, 7)

and

(8, 3)

Linear Programming Problem #3:

A company that makes calculators also produces graphing calculators and scientific calculators. When making projections for the long term, indicate a demand expectation of at least eighty graphing calculators and a hundred scientific calculators daily. Due to the production capacity’s limitations, no more than 170 graphing calculators and 200 scientific calculators can be created each day. For a shipping contract to be satisfied, at least a total of 200 calculators need to be delivered daily.

If each of the graphing calculators produces a $5 profit but each scientific calculator results in a loss of $2, how many of each type need to be made every day for net profits to be maximized?

My variables will need to stand for the optimal number of calculators, since this is what the question asks for:

x= produced number of scientific calculators

y= produced number of graphing calculators

I will have 2 constraints since they can’t produce calculators in negative numbers:

x > 0

and

y > 0

This exercise also gives maximums: y < 170 and x < 200. Also, in these cases, I can’t ignore these other constraints, since I already have that y > 80 and x > 100. The minimum requirement for shipping also gives me 200, x + y, so in other words – x + 200 < y. The optimization equation of 2x + 5y = R will be my Revenue Relation. So the system is entirely:

R = –2x + 5y, subject to:

y > –x + 200

80 << 170

100 < x < 200
To graph the feasibility region:

Linear Programming Problems

You should obtain the maximum value of R = 650 at (x, y) = (100, 170) when you test the corner points at:

(100, 100)

(120, 80

(200, 80)

(200, 170)

and

(100, 170)

Linear Programming Problem #4:

The process of refining needs two gasoline gallons produced for every gallon of oil fuel at a certain refinery. So that all the demands will be met come wintertime, a minimum of 3 million fuel oil gallons will be needed to be made daily. On the other hand, only 6.4 million gallons is the daily demands of gasoline.  If fuel sells for 1.50/gallon and gas sells for $1.90 per gallon, how much production of each gallon is needed for revenue to be maximized?

Since the question is asking for how many gallons are needed to be produced, each variable will then be for ‘produced gallons.’

x will stand for gallons of gasoline

y will stand for produced gallons of oil

Being a problem in the real world, obviously you can’t have negative levels of production and there can be no negative variables. This gives me the constraints, which are:

x > 0

and

y > 0

There are at least 2 gas gallons for every oil gallon, so: x > 2y

This is what I will use for graphing, as it is more manageable:

(1.2) x > y

The gas demand says 6,400,000 > x while the demand for winter says that 3,000,000 > y so this constraints gets rid of the need of the previous constraint y > 0. Revenue (R) needs to be maximized as well so the equation for optimization is:

1.9x + 1.5y = R. This word problem would then have this model:

1.9x + 1.5y + R subject to:

0 < x

6,400,000 > x

3,000, 000 < y

(1/2) x > y

The scale is counting by the million so on the graph, y = 3 is actually y = 3 million:

Linear Programming Problems

At: (x, y) = (6.4m, 3.2m), you should get a maximal solution of R = $16.96m when testing the corner points at (6m, 3m), (6.4m, 3,) and (6.4m, 3.2m)

Hope this helps! For more math techniques that come in handy, especially when making graphs, here is a course called Geometry you might want to check out.