introduction to Operation Research

linear Programming

1. Operations Research

2. Content What linear Programming Three basic components of linear programming (LP) Steps of Mathematical Linear Programming model Two-Variable Model LP Model 4.1. Example 1 4.2. Example 2 Graphical LP Solution 5.1. Example 1 5.2 Example 2

3. LINEAR PROGRAMMING (LP) linear programming(LP) : is a technique for optimization of a linear objective function, subject to linear equality and linear inequality constraints. Linear programming determines the way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model and given some list of requirements represented as linear equations.

4. Three basic components of linear programming (LP) All OR models, LP included, consist of three basic components: Decision variables that we seek to determine. Objective (goal) that we need to optimize (maximize or minimize). Constraints that the solution must satisfy. The proper definition of the decision variables is an essential first step in the development of the model.

5. Basics In the case of linear programming (LP), the objective function and the constraints are all linear functions of the decision variables. Linear function: for example: Y = X 1 + X 2 Linear constraints are linear functions that are restricted to be “less than or equal to ” ” equal to” Or “greater than or equal to ” a constant.

6. Steps of Mathematical Linear Programming Model Step 1 : Identify the decision variables of the problem Step 2: Construct the   objective function as an LP combination of the decision variables Step 3: Identify the constraints of the problem such as resource limitation, interrelation between variables

7. Example 1 A factory produces two types of products A and B. Each unit of A requires 50 minutes of processing time on machine one and 30 minutes on machine two. Each unit of B requires 24 minutes on machine one and 33 minutes on machine two Machine one is going to be available for 40 hours and machine two is available for 35 hours The profit per unit of A is $25 and the profit per unit of B is $30. Company policy is to determine the production quantity of each product in such a way as to maximize constrain Objective

8. Solution 1. Define the decision variables. X1 : the number of product A to be produced. X2 : the number of product B to be produced. Clearly X1, X2 ≥ 0 2. Write the objective in terms of the decision variables. The factory gets a profit of $25 for product A and $30 for product B. the objective function is to maximize profit (P). P= 25 X 1 + 30 X 2

9. Solution 3. Write the constraints in terms of the decision variables. If we produce X1 units of A and X2 units of B , machine one should be used for 50 X 1 + 24 X 2 minutes Since each unit of A requires 50 minutes of processing time on machine one and each unit of B requires 24 minutes of processing time on machine one On the other hand, machine one is available for 40 hours or equivalently for 2400 minutes This imposes the following constraint: 50 X 1 + 24 X 2 ≤ 2400.

10. Solution Similarly, machine two should be used for 30 X 1 + 33 X 2 minutes since each unit of A requires 30 minutes of processing time on machine two and each unit of B requires 33 minutes of processing time on machine two. On the other hand, machine two is available for 35 hours or equivalently for 2100 minutes. This imposes the following constraint: 30X 1 +33 X 2 ≤ 2100.

11. Solution Maximize : P= 25 X 1 + 30 X 2 Subject to : 50 X 1 + 24 X 2 ≤ 2400. 30X 1 +33 X 2 ≤ 2100. X 1 ,X 2 ≥ 0

12. Example 2 Reddy Mikks problem: The goal of Reddy Mikks is to maximize (i.e., increase as much as possible) the total daily profit of both paints. The following table provides the basic data of the problem:

13. Example 2 = Tons produced daily of exterior paint = Tons produced daily of interior paint Profit from exterior paint = 5 thousand dollars) Profit from interior paint = 4 1thousand2 dollars Step 1 : formulate objective function Letting represent the total daily profit (in thousands of dollars), the objective (or goal) of Reddy Mikks is expressed Maximize = 5 + 4  

14. Step 2 : construct the constraints that restrict raw material usage and product demand. Thus, the raw material constraints are: 6 4 24 (RM of M1) + 2 6 (RM of M2)   first restriction on product demand stipulates that the daily production of interior paint cannot exceed that of exterior paint by more than 1 ton 1 second restriction limits the daily demand of interior paint to 2 tons 2  

15. Solution The complete Reddy Mikks model is Maximize = 5 + 4 Subject to 6 4 24 (1) + 2 6 (2) 1 (3) 2 (4) , ≥ 0 (5)  

16. Linear Optimization Models Developing an Optimization Model 1. Define the decision variables. 2. Identify the objective (goal) that we need to optimize (maximize or minimize). 3. Identify all appropriate constraints that the solution must satisfy. 4. Write the objective function and constraints as mathematical expressions. Characteristics of Linear Optimization Models The objective function and all constraints are linear functions of the decision variables All variables are continuous (fractional values are allowed)

17. Example 2 Niki holds two part-time jobs, Job I and Job II . She never wants to work more than a total of 12 hours a week . She has determined that for every hour she works at Job I , she needs 2 hours of preparation time, and for every hour she works at Job II , she needs one hour of preparation time, and she cannot spend more than 16 hours for preparation. If Niki makes $40 an hour at Job I , and $30 an hour at Job II , how many hours should she work per week at each job to maximize her income ?

18. Objective Let the number of hours per week Niki will work at Job I = x Let the number of hours per week Niki will work at Job II = y Now we write the objective function. Since Niki gets paid $40 an hour at Job I, and $30 an hour at Job II, her total income I is given by the following equation. Z=40x+30y

19. Constraints Our next task is to find the constraints. The second sentence in the problem states, "She never wants to work more than a total of 12 hours a week." This constraint translates mathematically to: x+y≤12

20. Constraints The third sentence states, "For every hour she works at Job I, she needs 2 hours of preparation time, and for every hour she works at Job II, she needs one hour of preparation time, and she cannot spend more than 16 hours for preparation." The translation follows. 2 x + y ≤16 The fact that x and y can never be negative is represented by the following two constraints: x≥0, and y≥0.

21. Objective and constraints Z=40x+30y x+y≤12 2x+y≤16 x≥0;y≥0

22. Solution x+y≤12 2x+y≤16 x 12 y 12 x 8 y 16

23. Constraint 1 x+y≤12 (0,12) (12,0)

24. Constraint 2 2x+y≤16 (0,16) (8,0)

25. All Constraints x+y≤12 2x+y≤16

26. Feasible region To determine the correct side, designate any point not lying on the straight line as a reference point. If the chosen reference point satisfies the inequality, then its side is feasible; otherwise, the opposite side becomes the feasible half-space. The origin (0, 0) is a convenient reference point and should always be used so long as it does not lie on the line representing the constraint. x+y≤12 0+0 ≤12 2x+y≤16 2(0)+0 ≤16

27. Determination of the Feasible Solution Space Infeasible space

28. The vertices of the Feasible Solution Space In practice, a typical LP may include hundreds or even thousands of variables and constraints . Of what good then is the study of a two-variable LP? The answer is that the graphical solution provides a key result: The optimum solution of an LP, when it exists, is always associated with a corner point of the solution space, thus limiting the search for the optimum from an infinite number of feasible points to a finite number of corner points.

29. The vertices of the Feasible Solution Space Infeasible space C D A B

30. Determine the optimum point The values of x and y associated with the optimum point C are determined by solving the equations associated with lines (1) and (2): x+y≤12 *2 2x+2y=24 2x+2(8)=24 - 2x+16=24 2x+y≤16 *1 2x+y= 16 2x=24-16 x=8/2 y=24-16 X=4 y=8

31. The vertices of the Feasible Solution Space A (0,0) B (0,12) C (4,8) D (8,0) C D B A

32. The maximum (or minimum) value of the objective function (X,Y) F(X,Y)=40x+30y Max (0,0) 40(0)+30(0) (0,12) 40(0)+30(12) 360 (8,0) 40(8)+30(0) 320 (4,8) 40(4)+30(8) 400 (X,Y) F(X,Y)=40x+30y Min (0,0) 40(0)+30(0) (0,12) 40(0)+30(12) 360 (8,0) 40(8)+30(0) 320 (4,8) 40(4)+30(8) 400 The solution is X = 4 and Y = 8 with z = 40*4+30*8 = 400. Therefore, we conclude that Niki should work 4 hours at Job I, and 8 hours at Job II.

33. Example 2 Use graphical method to solve the following linear programming model. Maximize z = 5x 1 + 4x 2 subject to 6x 1 + 4x 2 ≤ 24 6x 1 + 3x 2 ≤ 22.5 x 1 + x 2 ≤ 5 x 1 + 2x 2 ≤ 6 -x 1 + x 2 ≤ 1 x 2 ≤ 2 x 1 , x 2 ≥

34. Solution 6x 1 + 4x 2 ≤ 24 6x 1 + 3x 2 ≤ 22.5 x 1 + x 2 ≤ 5 x 1 + 2x 2 ≤ 6 -x 1 + x 2 ≤ 1 x 2 ≤ 2 x 1 4 x 2 6 x 1 3.75 x 2 7.5 x 1 5 x 2 5 x 1 6 x 2 3 x 1 -1 x 2 1 x 1 x 2 2

35. Constraint 1 6x 1 + 4x 2 ≤ 24 (0,6) (4,0)

36. Constraint 2 6x 1 + 3x 2 ≤ 22.5 (0,7.5) (3.75,0)

37. Constraint 3 x 1 + x 2 ≤ 5 (0,5) (5,0)

38. Constraint 4 x 1 + 2x 2 ≤ 6 (0,3) (6,0)

39. Constraint 5 -x 1 + x 2 ≤ 1 (0,1) (-1,0)

40. Constraint 6 x 2 ≤ 2 (0,2)

41. All Constraints 6x 1 + 4x 2 ≤ 24 (0,6) (4,0) 6x 1 + 3x 2 ≤ 22.5 (0,7.5) (3.75,0) x 1 + x 2 ≤ 5 (0,5) (5,0) x 1 + 2x 2 ≤ 6 (0,3) (6,0) -x 1 + x 2 ≤ 1 (0,1) (-1,0) x 2 ≤ 2 (0,2)

42. Feasible region To determine the correct side, designate any point not lying on the straight line as a reference point. If the chosen reference point satisfies the inequality, then its side is feasible; otherwise, the opposite side becomes the feasible half-space. The origin (0, 0) is a convenient reference point and should always be used so long as it does not lie on the line representing the constraint. 6x 1 + 4x 2 ≤ 24 6(0) + 4(0) ≤ 24 6x 1 + 3x 2 ≤ 22.5 6(0) + 3(0) ≤ 22.5 x 1 + x 2 ≤ 5 (0) + (0) ≤ 5 x 1 + 2x 2 ≤ 6 (0) + 2(0) ≤ 6 -x 1 + x 2 ≤ 1 -(0) + (0) ≤ 1 x 2 ≤ 2 (0) ≤ 2

43. Determination of the Feasible Solution Space Infeasible space 6x 1 + 4x 2 ≤ 24 6x 1 + 3x 2 ≤ 22.5 x 1 + x 2 ≤ 5 x 1 + 2x 2 ≤ 6 -x 1 + x 2 ≤ 1 x 2 ≤ 2

44. The vertices of the Feasible Solution Space In practice, a typical LP may include hundreds or even thousands of variables and constraints . Of what good then is the study of a two-variable LP? The answer is that the graphical solution provides a key result: The optimum solution of an LP, when it exists, is always associated with a corner point of the solution space, thus limiting the search for the optimum from an infinite number of feasible points to a finite number of corner points .

45. The vertices of the Feasible Solution Space A B C D E F

46. Determine the optimum point The values of x and y associated with the optimum point E are determined by solving the equations associated with lines (1) and (4): 6x 1 + 4x 2 ≤ 24 *1 6x1 + 4x2 ≤ 24 6x 1 + 4(1.5) ≤ 24 - 6x 1 + 12x 2 ≤ 36 6x 1 + 6 ≤ 24 x 1 + 2x 2 ≤ 6 *6 -8x 2 = -12 6x 1 ≤ 24 - 6 x 2 = -12/-8 6x 1 ≤ 18 x 2 = 1.5 x 1 ≤ 18/6 x 1 = 3

47. The vertices of the Feasible Solution Space A (0,0) B (0,1) C (1,2) D (2,2) E (3,1.5) F (3.75,0) A B C D E F

48. The maximum value of the objective function (X 1 ,X 2 ) F(X,Y)=5x 1 + 4x 2 Max (0,0) 5(0) + 4(0) (0,1) 5(0) + 4(1) 4 (1,2) 5(1) + 4(2) 13 (2,2) 5(2) + 4(2) 18 (3,1.5) 5(3) + 4(1.5) 21 (3.75,0) 5(3.75) + 4(0) 18.75 The solution is X 1 = 3 and X 2 = 1.5 with z = 5*3 + 4*1.5 = 21. (X 1 ,X 2 ) F(X,Y)=5x 1 + 4x 2 Min (0,0) 5(0) + 4(0) (0,1) 5(0) + 4(1) 4 (1,2) 5(1) + 4(2) 13 (2,2) 5(2) + 4(2) 18 (3,1.5) 5(3) + 4(1.5) 21 (3.75,0) 5(3.75) + 4(0) 18.75