Topic 8: Linear Programming & Exercise

LINEAR PROGRAMMING

Introduction of Linear Programming
Linear programming is the process of taking various  linear inequalities relating to some situation and finding the best value obtainable under those conditions. A typical example would be taking the limitations of materials and labor and then determining the best production level for maximal profits under those conditions.

In real life, linear programming is part of a very important area of mathematics calles "optimization techniques". This field of study are used every day in the organization and allocation of resource. These real life systems can have dozens or hundreds of variable or more. in algebra through you will only work with the simple (and graph able) two variable linear case. 

The general process for solving linear-programming exercises is to graph the inequalities (called the "constraints") to form a walled-off area on the x,y-plane (called the "feasibility region"). Then you figure out the coordinates of the corners of this feasibility region (that is, you find the intersection points of the various pairs of lines), and test these corner points in the formula (called the "optimization equation") for which you're trying to find the highest or lowest value.

Formula of linear Programming

Y > Mx + C M = gradient C = y-intercept

 Example 1:


A company makes two products (X and Y) using two machines (A and B). Each unit of X that is produced requires 50 minutes processing time on machine A and 30 minutes processing time on machine B. Each unit of Y that is produced requires 24 minutes processing time on machine A and 33 minutes processing time on machine B.
At the start of the current week there are 30 units of X and 90 units of Y in stock. Available processing time on machine A is forecast to be 40 hours and on machine B is forecast to be 35 hours.
The demand for X in the current week is forecast to be 75 units and for Y is forecast to be 95 units. Company policy is to maximize the combined sum of the units of X and the units of Y in stock at the end of the week.

• Formulate the problem of deciding how much of each product to make in the current week as a linear program.
• Solve this linear program graphically.

Solution

Let

• x be the number of units of X produced in the current week
• y be the number of units of Y produced in the current week

then the constraints are:

50x + 24y <= 40(60) machine A time

The objective is: maximize (x+30-75) + (y+90-95) = (x+y-50)
i.e. to maximize the number of units left in stock at the end of the week
It is plain from the diagram below that the maximum occurs at the intersection of x=45 and 50x + 24y = 2400

30x + 33y <= 35(60) machine B time

x >= 75 - 30

i.e. x >= 45 so production of X >= demand (75) - initial stock (30), which ensures we meet demand

y >= 95 - 90

i.e. y >= 5 so production of Y >= demand (95) - initial stock (90), which ensures we meet demand. 

The objective is: maximize (x+30-75) + (y+90-95) = (x+y-50)
i.e. to maximize the number of units left in stock at the end of the week
It is plain from the diagram below that the maximum occurs at the intersection of x=45 and 50x + 24y = 2400 

Example 2:

A company manufactures two products (A and B) and the profit per unit sold is £3 and £5 respectively. Each product has to be assembled on a particular machine, each unit of product A taking 12 minutes of assembly time and each unit of product B 25 minutes of assembly time. The company estimates that the machine used for assembly has an effective working week of only 30 hours (due to maintenance/breakdown).
Technological constraints mean that for every five units of product A produced at least two units of product B must be produced.

• Formulate the problem of how much of each product to produce as a linear program.
• Solve this linear program graphically.
• The company has been offered the chance to hire an extra machine, thereby doubling the effective assembly time available. What is the maximum amount you would be prepared to pay (per week) for the hire of this machine and why?

Solution

Let
x_A = number of units of A produced
x_B = number of units of B produced
then the constraints are:
12x_A + 25x_B <= 30(60) (assembly time)
x_B >= 2(x_A/5)
i.e. x_B - 0.4x_A >= 0
i.e. 5x_B >= 2x_A (technological)
where x_A, x_B >= 0
and the objective is
maximize 3x_A + 5x_B
It is plain from the diagram below that the maximum occurs at the intersection of 12x_A + 25x_B = 1800 and x_B - 0.4x_A = 0 

Example 3:

If the objective function of the previous exercise had been:

f(x,y) = 20x + 30y

f(0,500) = 20·0 + 30 · 500 = $15,000       Maximum

f(500, 0) = 20·500 + 30·0 = $10,000

f(375, 250) = 20·375 + 30·250 = $15,000     Maximum

In this case, all the pairs with integer solutions of the segment drawn in black would be the maximum.

Below is the video to show you how to solve the linear programming with the graph. 

Exercise

Remember when (x) you can choose your own number

1)  Y ≥ -2x + 5

2) Y < 4x + 4

3) Y > -4/5 x