Operation research unit1 introduction and lpp graphical and simplex method

Operation research unit1 introduction to OR, classification of OR models,LPP methods:LPP graphical and simplex method

1. Linear Programming UNIT – I OPERATION RESEARCH Dr. Loveleen Kumar Bhagi Associate Professor School of Mechanical Engineering LPU

2. Dr. L K Bhagi, School of Mechanical Engineering, LPU 2 Operation Research Models A Model is an ideal representation of real system. System can be problem, process, operation, object or event. Operations Research Model as some sort of mathematical or theoretical description of various variables of a system representing some aspects of a problem on some subject of interest or inquiry. The model enables to conduct a number of experiment involving theoretical subjective manipulations to find some optimum solution to the problem on hand.

3. Dr. L K Bhagi, School of Mechanical Engineering, LPU 3 Operation Research Models A Model is an ideal representation of real system. System can be problem, process, operation, object or event. Operations Research Model as some sort of mathematical or theoretical description of various variables of a system representing some aspects of a problem on some subject of interest or inquiry. The model enables to conduct a number of experiment involving theoretical subjective manipulations to find some optimum solution to the problem on hand.

4. Dr. L K Bhagi, School of Mechanical Engineering, LPU 4 Operation Research Models Mathematical and Descriptive models Static and Dynamic Models

5. Dr. L K Bhagi, School of Mechanical Engineering, LPU 5 Mathematical Model A mathematical model is a description of a system using mathematical concepts and language. Mathematical models employ a set of mathematical symbols, i.e., letters, numbers etc. to represent a system. Here, the variables are related together by means of mathematical equations to describe the behavior or properties of the system. The solution of the problem is then obtained by applying well developed mathematical techniques to the model. Operation Research Models Mathematical and Descriptive models

6. Dr. L K Bhagi, School of Mechanical Engineering, LPU 6 Descriptive Model A descriptive model explains or gives a description of the system giving various variables, constraints and objective of the system or problem. The drawback of this model is as we go on reading and proceed; it is very difficult to remember about the variables and constraints, in case the problem or description of the system is lengthy one. Operation Research Models Mathematical and Descriptive models

7. Dr. L K Bhagi, School of Mechanical Engineering, LPU 7 A static model is one in which the decision variables do not involve sequences of decisions over multiple periods. A dynamic model is a model in which the decision variables do involve sequences of decisions over multiple periods. Operation Research Models Static and Dynamic Models

8. Dr. L K Bhagi, School of Mechanical Engineering, LPU 8 Operation Research Models Classification by Structure Classification by Nature of Environment (Degree of Certainty) Classification by utility or Function Classification Based on Time Reference Classification Based on Method of Solution

9. 9 Dr. L K Bhagi, School of Mechanical Engineering, LPU 1. Iconic Models (Physical model) These models are scaled version of the actual object and explain all the features of the actual object. For example a toy of a car is an iconic model of a real car. In fact a globe is an iconic model of the earth. These models may be of enlarged version or reduced version. As far as OR is concerned, is of less use. The advantages of these models: are It is easy to work with an iconic model in some cases, these are easy to construct and these are useful in describing static or dynamic phenomenon at some definite time. The limitations are, we cannot study the changes in the operation of the system. For some type of systems, the model building is very costly. It will be sometimes very difficult to carry out experimental analysis on these models. Operation Research Models Classification by Structure

10. 10 Dr. L K Bhagi, School of Mechanical Engineering, LPU 1. Iconic Models (Physical model) These models are scaled version of the actual object and explain all the features of the actual object. For example a toy of a car is an iconic model of a real car. In fact a globe is an iconic model of the earth. These models may be of enlarged version or reduced version. As far as OR is concerned, is of less use. The advantages of these models: are It is easy to work with an iconic model in some cases, these are easy to construct and these are useful in describing static or dynamic phenomenon at some definite time. The limitations are, we cannot study the changes in the operation of the system. For some type of systems, the model building is very costly. It will be sometimes very difficult to carry out experimental analysis on these models. Operation Research Models Classification by Structure

11. 11 Dr. L K Bhagi, School of Mechanical Engineering, LPU 2 . Analogue Model In this model one set of properties are used to represent another set of properties. Say for example, blue color generally represents water. Whenever we want to show water source on a map it is represented by blue color. Contour lines on the map is also analog model. These are also not much used in operations research. The best examples are warehousing problems and layout problems. Operation Research Models Classification by Structure

12. 12 Dr. L K Bhagi, School of Mechanical Engineering, LPU 3. Symbolic Models or Mathematical Models In these models the variables of a problem is represented by mathematical symbols, letters etc. To show the relationships between variables and constraints we use mathematical symbols. Hence these are known as symbolic models or mathematical models. These models are used very much in operations research. Operation Research Models Classification by Structure

13. 13 Dr. L K Bhagi, School of Mechanical Engineering, LPU Depending on the use of the model or purpose of the model, the models are classified as Descriptive, Predictive and Prescriptive models. Operation Research Models Classification by Utility or Function

14. 14 Dr. L K Bhagi, School of Mechanical Engineering, LPU Descriptive model The descriptive model simply explains certain aspects of the problem or situation or a system so that the user can make use for his analysis. It will not give full details and clear picture of the problem for the sake of scientific analysis. Descriptive models explain various operations in non mathematical language e.g. Observation, Survey, Questionnaire etc. Operation Research Models Classification by Utility or Function

15. 15 Dr. L K Bhagi, School of Mechanical Engineering, LPU Predictive model These models represent a relationship between dependent and independent variables and hence measure ‘ cause and effect ’ due to changes in independent variables. These models building on the data collected, can predict the approximate results of the situation under question. For example, basing on your performance in the examination and the discussions you have with your friends after the examination and by verification of answers of numerical examples, you can predict your score or results. Operation Research Models Classification by Utility or Function

16. 16 Dr. L K Bhagi, School of Mechanical Engineering, LPU Prescriptive (or Optimization) models These models provide the ‘best’ or ‘optimal’ solution to problems using an appropriate course of action (strategy) subject to certain limitations on the use of resources. For example, in mathematical programming, models are formulated for optimizing the given objective function, subject to restrictions on resources in the context of the problem under consideration and non-negativity of variables. These models are called prescriptive models because they prescribe what the decision maker have to do. Operation Research Models Classification by Utility or Function

17. 17 Dr. L K Bhagi, School of Mechanical Engineering, LPU Depending on the environment in which the problem exists and the decisions are made, and depending on the conditions of variables, the models may be categorized as Deterministic models and Probabilistic models. Operation Research Models Classification by Nature of Environment ( Degree of Certainty)

18. 18 Dr. L K Bhagi, School of Mechanical Engineering, LPU Deterministic models If all the parameters, constants and functional relationships are assumed to be known with certainty when the decision is made, the model is said to be deterministic. Thus, the outcome associated with a particular course of action is known, i.e. for a specific set of input values, there is only one output value which is also the solution of the model. Linear programming models are example of deterministic models. Operation Research Models Classification by Nature of Environment ( Degree of Certainty)

19. 19 Dr. L K Bhagi, School of Mechanical Engineering, LPU Probabilistic models In these models, the values of variables, the final outcome of a certain course of action cannot be predicted accurately because of element of probability. For Example: Insurance against risk of fire, accidents, sickness, etc., Operation Research Models Classification by Nature of Environment ( Degree of Certainty)

20. 20 Dr. L K Bhagi, School of Mechanical Engineering, LPU Static models Static models represent a system at a particular point of time and do not take into account changes over time. For example, an inventory model can be developed and solved to determine an economic order quantity assuming that the demand and lead time would remain same throughout the planning period. Operation Research Models Classification Based on Time Reference

21. 21 Dr. L K Bhagi, School of Mechanical Engineering, LPU Dynamic models Dynamic models take into account changes over time, i.e., time is considered as one of the variables while deriving an optimal solution. Operation Research Models Classification Based on Time Reference

22. 22 Dr. L K Bhagi, School of Mechanical Engineering, LPU Analytical models These models have a specific mathematical structure and thus can be solved by the known analytical or mathematical techniques. Any optimization model (which requires maximization or minimization of an objective function) is an analytical model. Operation Research Models Classification Based on Method of Solution

23. 23 Dr. L K Bhagi, School of Mechanical Engineering, LPU Simulation models These models have a mathematical structure but cannot be solved by the known mathematical techniques. A simulation model is essentially a computer-assisted experimentation on a mathematical structure of a problem in order to describe and evaluate its behavior under certain assumptions over a period of time. Simulation models are more flexible than mathematical models and can, therefore, be used to represent a complex system that cannot be represented mathematically. Operation Research Models Classification Based on Method of Solution

24. Methodology of Operations Research

25. 25 Dr. L K Bhagi, School of Mechanical Engineering, LPU Every OR specialist may have his/her own way of solving problems. However, the effective use of OR techniques requires to follow a sequence of steps. Methodology of Operations Research

26. 26 Dr. L K Bhagi, School of Mechanical Engineering, LPU Methodology of Operations Research Reference: Operations research theory and applications by J. K. Sharma

27. Linear Programming problem (LPP)

28. Linear Programming problem (LPP) linear relationship among variables in a model. That is, a given change in one variable causes a proportional change in another variable.

29. Linear Programming problem (LPP) refers to the mathematical modelling and solving of a problem that involves the use of limited resources, by choosing a particular strategy among the given strategies (alternatives) in order to achieve the desired objective.

30. 30 Dr. L K Bhagi, School of Mechanical Engineering, LPU In 1947, during World War II, George B Dantzing while working with the US Air Force, developed LP model, primarily for solving military logistics problems. But now, it is extensively being used in all functional areas of management, airlines, agriculture, military operations, education, energy planning, pollution control, transportation planning and scheduling, research and development, health care systems, etc. Though these applications are diverse, all LP models have certain common properties and assumptions – that are essential for decision-makers to understand before their use. Operation Research Models Linear Programming problem (LPP)

31. 31 Dr. L K Bhagi, School of Mechanical Engineering, LPU The linear programming problems (LPP) helps to find the best optimal solution of a linear function (also, known as the objective function) which are placed under certain constraints (set of linear inequality constraints) Operation Research Models Linear Programming problem (LPP)

32. 32 Dr. L K Bhagi, School of Mechanical Engineering, LPU Linear programming (LP) or Linear Optimization may be defined as the problem of maximizing or minimizing a linear function which is subjected to linear constraints. The constraints may be equalities or inequalities. The optimization problems involve the calculation of profit and loss. Operation Research Models Linear Programming problem (LPP)

33. 33 Dr. L K Bhagi, School of Mechanical Engineering, LPU Linear programming problems are an important class of optimization problems, that helps to find the feasible region and optimize the solution in order to have the highest or lowest value of the function. Linear programming is the method of considering different inequalities relevant to a situation and calculating the best value that is required to be obtained in those conditions. Operation Research Models Linear Programming problem (LPP)

34. 34 Dr. L K Bhagi, School of Mechanical Engineering, LPU The following are some important assumptions made in formulating a linear programming model: It is assumed that the decision maker here is completely certain (i.e., deterministic conditions) regarding all aspects of the situation, i.e., availability of resources, profit contribution of the products, technology, courses of action and their consequences etc. Operation Research Models Linear Programming problem (LPP)

35. 35 Dr. L K Bhagi, School of Mechanical Engineering, LPU The following are some important assumptions made in formulating a linear programming model: It is assumed that the relationship between variables in the problem and the resources available i.e., constraints of the problem exhibits linearity. Operation Research Models Linear Programming problem (LPP)

36. 36 Dr. L K Bhagi, School of Mechanical Engineering, LPU The following are some important assumptions made in formulating a linear programming model: We assume here Fixed Technology. Fixed technology refers to the fact that the production requirements are fixed during the planning period and will not change in the period. Operation Research Models Linear Programming problem (LPP)

37. 37 Dr. L K Bhagi, School of Mechanical Engineering, LPU The following are some important assumptions made in formulating a linear programming model: It is assumed that the profit contribution of a product remains constant, irrespective of level of production and sales. Operation Research Models Linear Programming problem (LPP)

38. 38 Dr. L K Bhagi, School of Mechanical Engineering, LPU The following are some important assumptions made in formulating a linear programming model: It is assumed that the decision variables are continuous. It means that the companies manufacture products in fractional units. For example, company manufacture 2.5 vehicles, 3.2 barrels of oil etc. This is referred too as the assumption of divisibility. Operation Research Models Linear Programming problem (LPP)

39. 39 Dr. L K Bhagi, School of Mechanical Engineering, LPU The following are some important assumptions made in formulating a linear programming model: It is assumed that only one decision is required for the planning period. This condition shows that the linear programming model is a static model, which implies that the linear programming problem is a single stage decision problem. Operation Research Models Linear Programming problem (LPP)

40. 40 Dr. L K Bhagi, School of Mechanical Engineering, LPU The following are some important assumptions made in formulating a linear programming model: All variables are restricted to nonnegative values (i.e., their numerical value will be ≥ 0). Operation Research Models Linear Programming problem (LPP)

41. OR >LPP > T1 Dr. L K Bhagi, School of Mechanical Engineering, LPU 41

42. OR >LPP > T1 A manufacturer produces two types of models M1 and M2. Each model of the type M1 requires 4 hrs of grinding and 2 hours of polishing; whereas each model of the type M2 requires 2 hours of grinding and 5 hours of polishing. The manufacturers have 2 grinders and 3 polishers. Each grinder works 40 hours a week and each polisher works for 60 hours a week. Profit on M1 model is Rs.3.00 and on model M2, is Rs.4.00. Whatever is produced in a week is sold in the market. How should the manufacturer allocate his production capacity to the two types of models, so that he may make the maximum profit in a week? Dr. L K Bhagi, School of Mechanical Engineering, LPU 42

43. Decision Variables : Let and be the number of units of M1 and M2 model. Objective function: Since the profit on both the models are given, we have to maximize the profit. Constraints: There are two constraints one for grinding and the other for polishing.   Dr. L K Bhagi, School of Mechanical Engineering, LPU 43 OR >LPP > T1

44. Objective Function : Max (Z) = 3 + 4 Constraints : No. of hrs. Available on each grinder for one week is 40 hrs. There are 2 grinders. Hence the manufacturer does not have more than 2 x 40 = 80 hrs of grinding. M1 requires 4 hrs of grinding and M 2, requires 2 hours of grinding.   Dr. L K Bhagi, School of Mechanical Engineering, LPU 44 OR >LPP > T1

45. Objective Function : Max (Z) = 3 + 4 Constraints : there are 3 polishers, the available time for polishing in a week is given by 3 x 60= 180. M1 requires 2 hrs of polishing and M2, requires 5 hrs of polishing.   Dr. L K Bhagi, School of Mechanical Engineering, LPU 45 OR >LPP > T1

46. Finally, we have Max (Z) = 3 + 4 Subject to 4 + 2 ≤ 80 2 + 5 ≤180   Dr. L K Bhagi, School of Mechanical Engineering, LPU 46 OR >LPP > T1

47. Objective Function : Max (Z) = 3 + 4 Constraints : The grinding constraint is given by 4 + 2 ≤ 80 The Polishing constraint is given by 2 + 5 ≤180   Dr. L K Bhagi, School of Mechanical Engineering, LPU 47 OR >LPP > T1

48. OR >LPP > T2 Dr. L K Bhagi, School of Mechanical Engineering, LPU 48

49. OR >LPP > T2 Dr. L K Bhagi, School of Mechanical Engineering, LPU 49

50. OR >LPP > T2 Dr. L K Bhagi, School of Mechanical Engineering, LPU 50

51. OR >LPP > T2 Dr. L K Bhagi, School of Mechanical Engineering, LPU 51

52. OR >LPP > T2 Dr. L K Bhagi, School of Mechanical Engineering, LPU 52

53. OR >LPP > T3 A research laboratory has two melts A and B of copper (Cu), Nickel (Ni) and Zinc (Zn) alloy to make up a new alloy. The composition of metals are as follows. Melt Composition (Parts) Cu Ni Zn A 3 2 1 B 2 2 1 To make up a new alloy at least 15 kg of copper, 10 kg of nickel, and 6 kg of zinc are needed. Melt A cost Rs 45 per kg and melt B cost Rs 50 per kg. Formulate the L.P.P. for the quantities of each melt to be used to minimized cost. Dr. L K Bhagi, School of Mechanical Engineering, LPU 53

54. OR >LPP > T3 Dr. L K Bhagi, School of Mechanical Engineering, LPU 54 The above data can be tabulated as follows.

55. OR >LPP > T3 Dr. L K Bhagi, School of Mechanical Engineering, LPU 55 The above data can be tabulated as follows.

56. OR >LPP > T3 Dr. L K Bhagi, School of Mechanical Engineering, LPU 56 The above data can be tabulated as follows.

57. OR >LPP > T3 Dr. L K Bhagi, School of Mechanical Engineering, LPU 57 The above data can be tabulated as follows.

58. OR >LPP > T3 Dr. L K Bhagi, School of Mechanical Engineering, LPU 58 The above data can be tabulated as follows.

59. OR >LPP > T3 Dr. L K Bhagi, School of Mechanical Engineering, LPU 59 Decision Variables Formulate the L.P.P. for the quantities of each melt to be used to minimized cost. Let and be the quantity of melt A and B respectively. Therefore, and can be treated as decision variables .  

60. OR >LPP > T3 Dr. L K Bhagi, School of Mechanical Engineering, LPU 60 Objective Function Formulate the L.P.P. for the quantities of each melt to be used to minimized cost. Since cost per kg melt of product A and B are given and we have to minimize the cost. Min (Z) = 45 + 50  

61. OR >LPP > T3 Dr. L K Bhagi, School of Mechanical Engineering, LPU 61 Constraints To make up a new alloy at least 15 kg of copper, 10 kg of nickel, and 6 kg of zinc are needed.

62. OR >LPP > T3 Dr. L K Bhagi, School of Mechanical Engineering, LPU 62 Constraints To make up a new alloy at least 15 kg of copper, 10 kg of nickel, and 6 kg of zinc are needed.

63. OR >LPP > T3 Dr. L K Bhagi, School of Mechanical Engineering, LPU 63 Constraints To make up a new alloy at least 15 kg of copper, 10 kg of nickel, and 6 kg of zinc are needed.

64. OR >LPP > T3 Dr. L K Bhagi, School of Mechanical Engineering, LPU 64 Constraints To make up a new alloy at least 15 kg of copper, 10 kg of nickel, and 6 kg of zinc are needed.

65. OR >LPP > T3 Dr. L K Bhagi, School of Mechanical Engineering, LPU 65

66. OR >LPP > T4 A factory is engaged in manufacturing three products A, B and C which involve lathe work, grinding and assembling. The cutting, grinding and assembling times required for one unit of A are 2, 1 and 1 hours respectively. Similarly they are 3, 1 and 3 hours for one unit of B and 1, 3 and 1 hours for one unit of C. the profits on A, B and C are Rs. 2, Rs. 2 and Rs. 4 per unit respectively. Assuming that there are available 300 hours of lathe time, 300 hours of grinder time and 240 hours of assembly time, which of the following represents the set of constraints for the equivalent L.P.P. formulated from the above data? Dr. L K Bhagi, School of Mechanical Engineering, LPU 66

67. OR >LPP > T3 Dr. L K Bhagi, School of Mechanical Engineering, LPU 67 2x1 + x2 + x3 ≤300, 3x1 + x2 + 3x3 ≤300, x1 + 3x2 + x3 ≤240 (b) 2x1 + 3x2 + x3 ≤300, x1 + x2 + 3x3 ≤300, x1 + 3x2 + x3 ≤240. (c) 2x1 + x2 + x3 ≥300, 3x1 + x2 + 3x3 ≥300, x1 + 3x2 + x3 ≥240 (d) 2x1 + x2 + x3 ≥300, 3x1 + x2 + 3x3 ≥300, x1 + 3x2 + x3 ≥240

68. LPP Graphical Method

69. Dr. L K Bhagi, School of Mechanical Engineering, LPU 69 Working Rule Convert all constraints into equations. Plot the graph of equations and apply the conditions given in constant. Identify feasible region (that satisfy all constraints). Find its corners (extreme points). Test the maximum or minimum value of objective function on these corners. Solution of objective function will lie on corner points. Operation Research Models LPP Graphical Method

70. Dr. L K Bhagi, School of Mechanical Engineering, LPU 70 Solve LPP by Graphical method Maximize Subject to constraints:   Operation Research Models LPP Graphical Method -Prob 1 RHS Values Should Always be Positive

71. Dr. L K Bhagi, School of Mechanical Engineering, LPU 71 Solve LPP by Graphical method Maximize Subject to constraints: Convert all constraints into equation ...(1) …(2)   Operation Research Models LPP Graphical Method -Prob 1

72. Dr. L K Bhagi, School of Mechanical Engineering, LPU 72 Solve LPP by Graphical method Maximize Subject to constraints: Convert all constraints into equation ...(1) …(2) Points on line 1 Points on line 2 Plot the Graph   Operation Research Models LPP Graphical Method

73. Dr. L K Bhagi, School of Mechanical Engineering, LPU 73 Solve LPP by Graphical method Maximize Subject to constraints: Convert all constraints into equation ...(1) …(2) Points on line 1 Points on line 2 Plot the Graph   Operation Research Models LPP Graphical Method

74. Dr. L K Bhagi, School of Mechanical Engineering, LPU 74 (50, 0) 20 80 60 40 20 40 60 80 100 (0,100) B O     1 (0, 0) A     Less than Sign means the area towards origin

75. Dr. L K Bhagi, School of Mechanical Engineering, LPU 75 (50, ) 20 80 60 40 20 40 60 80 100 (0, 80) (80, 0) C D O     2 (0, 0)    

76. Dr. L K Bhagi, School of Mechanical Engineering, LPU 76 (50, 0) 20 80 60 40 20 40 60 80 100 (0, 80) (80, 0) C A B D E O     1 2 (0, 0) (0,100)

77. Dr. L K Bhagi, School of Mechanical Engineering, LPU 77 (50, 0) 20 80 60 40 20 40 60 80 100 (0,100) (0, 80) (80, 0) C B D E O     1 2 Condition given in constants i.e. So, Feasible region OAEDO   Feasible region (0, 0) A

78. Dr. L K Bhagi, School of Mechanical Engineering, LPU 78 To find the coordinate of two lines intersection point E, solve it algebraically ...(1) …(2) Subtract eq. 1 & 2 …. Put in eq 2   Operation Research Models LPP Graphical Method

79. Dr. L K Bhagi, School of Mechanical Engineering, LPU 79 (50, 0) 20 80 60 40 20 40 60 80 100 (0,100) (0, 80) (80, 0) C B D E O     1 2 Condition given in constants i.e. So, Feasible region OAEDO   Feasible region (0, 0) A (20, 60)

80. Dr. L K Bhagi, School of Mechanical Engineering, LPU 80 Test for optimality Operation Research Models LPP Graphical Method Corner Points (0,0) = 0 (50,0) = 50x50 + 0 = 2500 (20, 60) = 50x20 + 18x60 = 2080 (0, 80) = 0 + 18x80 = 1440 Corner Points (0,0) = 0 (50,0) = 50x50 + 0 = 2500 (20, 60) = 50x20 + 18x60 = 2080 (0, 80) = 0 + 18x80 = 1440 Optimal Solution , and = 2500  

81. Dr. L K Bhagi, School of Mechanical Engineering, LPU 81 Solve LPP by Graphical method Maximize Subject to constraints: Convert all constraints into equation … 1 … 2 …3   Operation Research Models LPP Graphical Method – Prob 2

82. Dr. L K Bhagi, School of Mechanical Engineering, LPU 82 Points on line 1 Points on line 2 Points on line 3 Plot the Graph   Operation Research Models LPP Graphical Method

83. (0, 0) Dr. L K Bhagi, School of Mechanical Engineering, LPU 83 (200, 0) 100 400 300 200 100 200 300 400 500 (300, 0) C G     1 2 (0,500) 500 B O (500, 0) (0,250) E H I F 3 A (0, 450) D

84. (0, 0) Dr. L K Bhagi, School of Mechanical Engineering, LPU 84 (200, 0) 100 400 300 200 100 200 300 400 500 (300, 0) C G     1 2 (0,500) 500 B O (500, 0) (0,250) E H I Feasible region F 3 A (0, 450) D Condition given in constants i.e. So, Feasible region OAIFO  

85. Dr. L K Bhagi, School of Mechanical Engineering, LPU 85 To find the coordinate of two lines intersection point I … 1 … 2 …3 Subtract eq. 1 & 3 …. Put in eq 1 or 3 187.5   Operation Research Models LPP Graphical Method

86. Dr. L K Bhagi, School of Mechanical Engineering, LPU 86 Test for optimality Operation Research Models LPP Graphical Method Corner Points (0,0) = 0 (200,0) = 20000 (125, 187.5) = 20000 (0, 250) = 1000 Corner Points (0,0) = 0 (200,0) = 20000 (125, 187.5) = 20000 (0, 250) = 1000

87. (0, 0) Dr. L K Bhagi, School of Mechanical Engineering, LPU 87 (200, 0) 100 400 300 200 100 200 300 400 500 (300, 0)     1 (0,500) 500 B O (500, 0) (0,250) E I Feasible region F 2 A (0, 450) Condition given in constants i.e. So, Feasible region OAIFO  

88. Dr. L K Bhagi, School of Mechanical Engineering, LPU 88 Test for optimality Operation Research Models LPP Graphical Method Corner Points (0,0) = 0 (200,0) = 20000 (125, 187.5) = 20000 (0, 250) = 1000 Corner Points (0,0) = 0 (200,0) = 20000 (125, 187.5) = 20000 (0, 250) = 1000 That means, All the points lying on AI line are the Optimal Solution for the LPP So, LPP has infinite number of solutions all of which yield the same result

89. Dr. L K Bhagi, School of Mechanical Engineering, LPU 89 Solve LPP by Graphical method Maximize Subject to constraints: 1   Operation Research Models LPP Graphical Method – Prob 3

90. Dr. L K Bhagi, School of Mechanical Engineering, LPU 90 Solve LPP by Graphical method Minimize Subject to constraints: 1   Operation Research Models LPP Graphical Method – Prob 3 Points on line 1 Points on line 2 Plot the Graph  

91. Dr. L K Bhagi, School of Mechanical Engineering, LPU 91         1 1 2 2     1    

92. Dr. L K Bhagi, School of Mechanical Engineering, LPU 92         1 1 2 2     1    

93. Dr. L K Bhagi, School of Mechanical Engineering, LPU 93         1 1 2 2     1    

94. Dr. L K Bhagi, School of Mechanical Engineering, LPU 94         1 1 2 2     1     Feasible region      

95. Dr. L K Bhagi, School of Mechanical Engineering, LPU 95         1 1 2 2     1           B C A D

96. Dr. L K Bhagi, School of Mechanical Engineering, LPU 96 Test for optimality Operation Research Models LPP Graphical Method – Prob 3 Corner Points A - (0, 1.5) = 0 + 6 = 6 B - (2, 0.5) = 10 + 2 = 12 C - (∞, ∞) = ∞ + ∞ = ∞ D - (0, ∞) = 0 + ∞ = ∞ Corner Points A - (0, 1.5) = 0 + 6 = 6 B - (2, 0.5) = 10 + 2 = 12 C - (∞, ∞) = ∞ + ∞ = ∞ D - (0, ∞) = 0 + ∞ = ∞ So, Decision variables (0, 1.5) and Key variable is 6

97. Dr. L K Bhagi, School of Mechanical Engineering, LPU 97 Solve LPP by Graphical method Max Subject to constraints: 1   Operation Research Models LPP Graphical Method – Prob 4 Points on line 1 Points on line 2 Plot the Graph  

98. Dr. L K Bhagi, School of Mechanical Engineering, LPU 98         1 1 2 2     1     Feasible region      

99. Dr. L K Bhagi, School of Mechanical Engineering, LPU 99 Test for optimality Operation Research Models LPP Graphical Method – Prob 4 Corner Points A - (0, 1.5) = 0 + 6 = 6 B - (2, 0.5) = 10 + 2 = 12 C - (∞, ∞) = ∞ + ∞ = ∞ D - (0, ∞) = 0 + ∞ = ∞ Corner Points A - (0, 1.5) = 0 + 6 = 6 B - (2, 0.5) = 10 + 2 = 12 C - (∞, ∞) = ∞ + ∞ = ∞ D - (0, ∞) = 0 + ∞ = ∞ An unbounded solution of a linear programming problem is a situation where objective function is infinite .

100. Dr. L K Bhagi, School of Mechanical Engineering, LPU 100 Solve LPP by Graphical method Maximize Subject to constraints:   Operation Research Models LPP Graphical Method – Prob 5

101. Dr. L K Bhagi, School of Mechanical Engineering, LPU 101 Solve LPP by Graphical method Maximize Subject to constraints:   Operation Research Models LPP Graphical Method – Prob 6

102. Dr. L K Bhagi, School of Mechanical Engineering, LPU 102 Solve LPP by Graphical method Maximize Subject to constraints: 100 ,   Operation Research Models LPP Graphical Method – Prob 7

103. Simplex Method

104. Dr. L K Bhagi, School of Mechanical Engineering, LPU 104 Operation Research Models LPP Simplex Method

105. Dr. L K Bhagi, School of Mechanical Engineering, LPU 105 Operation Research Models LPP Simplex Method

106. Dr. L K Bhagi, School of Mechanical Engineering, LPU 106 Operation Research Models LPP Simplex Method

107. Dr. L K Bhagi, School of Mechanical Engineering, LPU 107 Operation Research Models LPP Simplex Method

108. Dr. L K Bhagi, School of Mechanical Engineering, LPU 108 Operation Research Models LPP Simplex Method

109. Dr. L K Bhagi, School of Mechanical Engineering, LPU 109 Operation Research Models LPP Simplex Method

110. Dr. L K Bhagi, School of Mechanical Engineering, LPU 110 Operation Research Models LPP Simplex Method

111. Dr. L K Bhagi, School of Mechanical Engineering, LPU 111 Operation Research Models LPP Simplex Method

112. Dr. L K Bhagi, School of Mechanical Engineering, LPU 112 Operation Research Models LPP Simplex Method

113. Dr. L K Bhagi, School of Mechanical Engineering, LPU 113 Comparison between Graphical and Simplex Methods The graphical method is used when we have two decision variables in the problem. Whereas, in Simplex method, the problem may have any number of decision variables. In graphical method, the inequalities are assumed to be equations, so as to enable to draw straight lines. But in Simplex method, the inequalities are converted into equations by: Adding a SLACK VARIABLE in maximisation problem and subtracting a SURPLUS VARIABLE in case of minimisation problem. Operation Research Models LPP Graphical Method

114. Dr. L K Bhagi, School of Mechanical Engineering, LPU 114 Comparison between Graphical and Simplex Methods In graphical method, the areas outside the feasible area (area covered by all the lines of constraints in the problem) indicates idle capacity of resource where as in Simplex method, the presence of slack variable indicates the idle capacity of the resources. Operation Research Models LPP Graphical Method

115. Dr. L K Bhagi, School of Mechanical Engineering, LPU 115 Operation Research Models LPP Simplex Method – Prob 5

116. Dr. L K Bhagi, School of Mechanical Engineering, LPU 116 Operation Research Models LPP Simplex Method – Prob 5 Two products E and F are processed through three machines P, Q and R. The processing time per unit, machine hours available and profit per unit are given below. Machine Processing Time Available Hours Product E Product F P 2 3 1500 Q 3 2 1500 R 1 1 1000 Profit Per Unit 10 12 Formulate appropriate LPP and Solve it by simplex method. Also state the shadow price per hour for each of the machines P, Q and R

117. Dr. L K Bhagi, School of Mechanical Engineering, LPU 117 Operation Research Models LPP Simplex Method – Prob 5 Machine Processing Time Available Hours Product E Product F P 2 3 1500 Q 3 2 1500 R 1 1 1000 Profit Per Unit 10 12

118. Dr. L K Bhagi, School of Mechanical Engineering, LPU 118 Operation Research Models LPP Simplex Method – Prob 5

119. Dr. L K Bhagi, School of Mechanical Engineering, LPU 119 Operation Research Models LPP Simplex Method – Prob 5

120. Dr. L K Bhagi, School of Mechanical Engineering, LPU 120 Operation Research Models LPP Simplex Method – Prob 5

121. Dr. L K Bhagi, School of Mechanical Engineering, LPU 121 Operation Research Models LPP Simplex Method – Prob 5

122. Dr. L K Bhagi, School of Mechanical Engineering, LPU 122 Operation Research Models LPP Simplex Method – Prob 5

123. Dr. L K Bhagi, School of Mechanical Engineering, LPU 123 Operation Research Models LPP Simplex Method – Prob 5

124. Dr. L K Bhagi, School of Mechanical Engineering, LPU 124 Operation Research Models LPP Simplex Method – Prob 5

125. Dr. L K Bhagi, School of Mechanical Engineering, LPU 125 Operation Research Models LPP Simplex Method – Prob 5

126. Dr. L K Bhagi, School of Mechanical Engineering, LPU 126 Operation Research Models LPP Simplex Method – Prob 5

127. Dr. L K Bhagi, School of Mechanical Engineering, LPU 127 Operation Research Models LPP Simplex Method – Prob 5

128. Dr. L K Bhagi, School of Mechanical Engineering, LPU 128 Operation Research Models LPP Simplex Method – Prob 5

129. Dr. L K Bhagi, School of Mechanical Engineering, LPU 129 Operation Research Models LPP Simplex Method – Prob 5

130. Dr. L K Bhagi, School of Mechanical Engineering, LPU 130 Operation Research Models LPP Simplex Method – Prob 5

131. Dr. L K Bhagi, School of Mechanical Engineering, LPU 131 Operation Research Models LPP Simplex Method – Prob 5

132. Dr. L K Bhagi, School of Mechanical Engineering, LPU 132 Operation Research Models LPP Simplex Method – Prob 5

133. Dr. L K Bhagi, School of Mechanical Engineering, LPU 133 Operation Research Models LPP Simplex Method – Prob 5

134. Dr. L K Bhagi, School of Mechanical Engineering, LPU 134 Operation Research Models LPP Simplex Method – Prob 5

135. Dr. L K Bhagi, School of Mechanical Engineering, LPU 135 Operation Research Models LPP Simplex Method – Prob 5

136. Dr. L K Bhagi, School of Mechanical Engineering, LPU 136 Operation Research Models LPP Simplex Method – Prob 5

137. Dr. L K Bhagi, School of Mechanical Engineering, LPU 137 Operation Research Models LPP Simplex Method – Prob 5

138. Dr. L K Bhagi, School of Mechanical Engineering, LPU 138 Operation Research Models LPP Simplex Method – Prob 5

139. Dr. L K Bhagi, School of Mechanical Engineering, LPU 139 Operation Research Models LPP Simplex Method – Prob 5

140. Dr. L K Bhagi, School of Mechanical Engineering, LPU 140 Operation Research Models LPP Simplex Method – Prob 5

141. Dr. L K Bhagi, School of Mechanical Engineering, LPU 141 Operation Research Models LPP Simplex Method – Prob 5

142. 142 Z max = 6X+8Y X+Y ≤ 10 2X +3Y ≤ 25 X +5Y ≤35 X, Y ≥ 0 Add slack variable to convert constraint equation into equality Z = 6X+8Y+0S 1 +0S 2 +0S 3 X+Y+S 1 =10 2X +3Y+S 2 = 25 X +5Y+S 3 = 35 X,Y, S 1 , S 2 , S 3 ≥ 0 Operation Research Models LPP Simplex Method – Prob 6

143. 143 Cj 6 8 X Y S 1 S 2 S 3 RHS (b) S 1 S 2 S 3 10 25 35

144. 144 Cj 6 8 X Y S 1 S 2 S 3 RHS (b) S 1 S 2 S 3 1 1 1 10 25 35

145. 145 Cj 6 8 X Y S 1 S 2 S 3 RHS (b) S 1 S 2 S 3 1 2 1 1 3 5 1 1 1 10 25 35

146. C j 6 8 θ X Y S 1 S 2 S 3 RHS (b) S 1 S 2 S 3 1 2 1 1 3 5 1 1 1 10 25 35 10 25/3 7 Z j C j - Z j 6 8 146 Key Column: decides incoming variable Key Row: decides outgoing variable Max Profit potential 8

147. C j 6 8 θ X Y S 1 S 2 S 3 RHS (b) S 1 S 2 S 3 1 2 1 1 3 5 1 1 1 10 25 35 10 25/3 7 Z j C j - Z j 6 8 147 Key Column: decides incoming variable Key Row: decides outgoing variable Max Profit potential 8 Key Element

148. 1/5 1 1/5 35/5 = 7

149. 149 C j 6 8 θ X Y S 1 S 2 S 3 RHS (b) 8 S 1 S 2 Y 1 2 1/5 1 3 1 1 1 1/5 10 25 7

150. 150 C j 6 8 θ X Y S 1 S 2 S 3 RHS (b) 8 S 1 S 2 Y 1 2 1/5 1 3 1 1 1 1/5 10 25 7

151. 151 C j 6 8 θ X Y S 1 S 2 S 3 RHS (b) 8 S 1 S 2 Y 1 2 1/5 1 3 1 1 1 1/5 10 25 7 Old Row

152. Dr. L K Bhagi, School of Mechanical Engineering, LPU 152 Old Row − KCE X MKR = NR 1 − 1 X 1/5 = 4/5 1 − 1 X 1 = 1 − 1 X = 1 − 1 X = − 1 X 1/5 = − 1/5 10 − 1 X 7 = 3

153. 153 C j 6 8 θ X Y S 1 S 2 S 3 RHS (b) 8 S 1 S 2 Y 1 2 1/5 1 3 1 1 1 1/5 10 25 35/5 = 7 Old Row

154. Dr. L K Bhagi, School of Mechanical Engineering, LPU 154 Old Row − KCE X MKR = NR 2 − 3 X 1/5 = 7/5 3 − 3 X 1 = − 3 X = 1 − 3 X = 1 − 3 X 1/5 = −3 /5 25 − 3 X 7 = 4

155. 155 C j 6 8 θ X Y S 1 S 2 S 3 RHS (b) 8 S 1 S 2 Y 4/5 7/5 1/5 1 1 1 -1/5 -3/5 1/5 3 4 7 Z j C j - Z j

156. 156 C j 6 8 θ X Y S 1 S 2 S 3 RHS (b) 8 S 1 S 2 Y 4/5 7/5 1/5 1 1 1 -1/5 -3/5 1/5 3 4 7 Z j C j - Z j

157. 157 C j 6 8 θ X Y S 1 S 2 S 3 RHS (b) 8 S 1 S 2 Y 4/5 7/5 1/5 1 1 1 -1/5 -3/5 1/5 3 4 7 15/4 20/7 35 Z j 8/5 8 8/5 56 C j - Z j 22/5 -8/5 56

158. 158 C j 6 8 θ X Y S 1 S 2 S 3 RHS (b) 6 8 S 1 X Y 4/5 1 1/5 1 1 5/7 -1/5 -3/7 1/5 3 20/7 7 Z j C j - Z j

159. 159 C j 6 8 θ X Y S 1 S 2 S 3 RHS (b) 6 8 S 1 X Y 1 1/5 1 1 -4/7 5/7 1/7 -3/7 1/5 5/7 20/7 7 Z j C j - Z j

160. 160 C j 6 8 θ X Y S 1 S 2 S 3 RHS (b) 6 8 S 1 X Y 1 1 1 -4/7 5/7 -1/7 1/7 -3/7 2/7 5/7 20/7 45/7 5 -20/3 45/2 Z j 6 8 22/7 - 2/7 480/7 C j - Z j -22/7 2/7 30/7 – 8/7 =22/7 -18/7+ 16/7 = -2/7 120/7 + 360/7 = 480/7 Key Column Key Row Max Profit potential Key Element

161. 161 C j 6 8 θ X Y S 1 S 2 S 3 RHS (b) 6 8 S 1 X Y 1 1 7 -4 5/7 -1/7 1 -3/7 2/7 5 20/7 45/7 Z j C j - Z j

162. 162 C j 6 8 θ X Y S 1 S 2 S 3 RHS (b) 6 8 S 1 X Y 1 1 7 -4 5/7 -1/7 1 -3/7 2/7 5 20/7 45/7 Z j C j - Z j

163. 163 C j 6 8 θ X Y S 1 S 2 S 3 RHS (b) 6 8 S 1 X Y 1 1 7 3 -4 -1 -1/7 1 2/7 5 5 45/7 Z j C j - Z j

164. 164 C j 6 8 θ X Y S 1 S 2 S 3 RHS (b) 6 8 S 1 X Y 1 1 7 3 -4 -1 -1/7 1 2/7 5 5 45/7 Z j C j - Z j

165. 165 C j 6 8 θ X Y S 1 S 2 S 3 RHS (b) 6 8 S 1 X Y 1 1 7 3 -2 -4 -1 1 1 5 5 5 Z j C j - Z j

166. 166 C j 6 8 θ X Y S 1 S 2 S 3 RHS (b) 6 8 S 1 X Y 1 1 7 3 -2 -4 -1 1 1 5 5 5 Z j 6 8 2 2 70 C j - Z j -2 -2 70 Therefore, X =5 Y= 5 Z= 70

167. Dr. L K Bhagi, School of Mechanical Engineering, LPU 167

168. Dr. L K Bhagi, School of Mechanical Engineering, LPU 168

169. Dr. L K Bhagi, School of Mechanical Engineering, LPU 169

170. Dr. L K Bhagi, School of Mechanical Engineering, LPU 170

171. Dr. L K Bhagi, School of Mechanical Engineering, LPU 171

172. Dr. L K Bhagi, School of Mechanical Engineering, LPU 172

173. Dr. L K Bhagi, School of Mechanical Engineering, LPU 173

174. Dr. L K Bhagi, School of Mechanical Engineering, LPU 174

175. Thank you