TOPIC5: LINEAR PROGRAMMING

LINEAR PROGAMMING

 

Linear Programming is the process of finding the extreme values (maximum and minimum values) of a function for a region defined by inequalities. 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. 

 

 

 

Example1

Find the maximum value of the function C = 6x + y subject to the constrains
x ≥ 0, y ≥ 0 , 5x + 3y ≤ 15.

 

Step 1: Objective function is C = 6x + y 
Step 2: Constraints are x ≥ 0, y ≥ 0 5x + 3y ≤ 15
Step 3: [Draw the graph.]
The feasible region determined by the given constraints is shown

 

 

 

Step 4: From the graph, the three vertices are (0, 0), (3, 0), and (0, 5).

Step 5: To evaluate the minimum, maximum values of C, we evaluate C = 2x + y at each of the vertices.

Step 6: [Substitute the values.]
At (0, 0) , C = 6(0) + (0) = 0

Step 7: [Substitute the values.]
At (3, 0) , C = 6(3) + (0) = 18

Step 8: [Substitute the values.]
At (0, 5) , C = 6(0) + (5) = 5

Step 9: So, the maximum value of C is 18.Answer is: 18.


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





 

 

Example3

 

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.

1. Formulate the problem of deciding how much of each product to make in the current week as a linear program.
2. 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 

 

 



This are the 3 question for you to try.

 

1. Y ≥ -2x + 5 
2. Y < 4x + 4
3.  Y > -4/5 x