Definition of Operations Research (OR): Operations Research (OR), also known as operational research or management science, is a field of study that applies mathematical, analytical, and scientific methods to help individuals and organizations make better decisions and solve complex problems. OR focuses on modelling, analyzing, and optimizing various processes and systems to improve efficiency, resource allocation and decisionmaking. It often involves the use of computer-based simulations, mathematical models, and data analysis techniques to provide visions and solutions. Scope of Operations Research: The scope of Operations Research is wide-ranging and includes various domains and industries. Here are some key aspects within the scope of OR: 1. Mathematical Modelling : OR involves the development of mathematical models that represent real-world systems, allowing for the analysis of complex interactions and relationships. 2. Optimization: A core aspect of OR is optimization, which seeks to find the best possible solutions among a set of alternatives, considering constraints and objectives. This applies to problems like resource allocation, cost minimization, and performance maximization. 3. Decision Support: OR provides decision-makers with tools, insights, and recommendations to make informed choices. It assists in evaluating different strategies and assessing the consequences of decisions. 4. Problem Solving: OR is applied to a wide range of problems, including logistics, supply chain management, production scheduling, project management, healthcare operations, and more. 5. Resource Allocation: OR helps organizations allocate limited resources, such as time, money, and personnel, efficiently to achieve desired outcomes. 6. Transportation and Logistics: OR plays a crucial role in optimizing transportation routes, vehicle scheduling, inventory management, and warehouse operations for businesses and logistics companies. 7. Manufacturing and Production: OR techniques are used to optimize production processes, quality control, and inventory management in manufacturing industries. 8. Finance and Investment: OR is applied to portfolio optimization, risk assessment, and financial modeling to make investment decisions and manage assets effectively. 9. Healthcare: OR is used in healthcare to optimize hospital operations, patient scheduling, healthcare facility design, and resource allocation. 10.Energy and Utilities: OR assists in optimizing energy production, distribution, and consumption, as well as resource allocation in the energy sector. 11.Environmental Management: OR addresses environmental issues, including waste management, pollution control, and sustainable resource allocation. 12.Public Policy and Government: OR techniques are employed in public policy and government decision-making, such as urban planning, disaster management, and infrastructure development. 13.Marketing and Customer Analytics: OR is used to analyze consumer behavior, optimize marketing campaigns, and make pricing decisions. 14.Telecommunications: OR optimizes network design, capacity planning, and service delivery in the telecommunications industry. 15.Agriculture: OR aids in optimizing crop planning, resource allocation, and supply chain management in agriculture. 16.Human Resources: OR assists in workforce planning, scheduling, and talent management within organizations. In summary, Operations Research is a multipurpose field that applies quantitative and analytical methods to a wide array of problems across various sectors. Its scope is continually evolving as it adapts to new challenges and technological advancements, making it a valuable discipline for improving decision-making and resource management in both public and private sectors. The historical development and evolution of Operations Research (OR) can be traced through several key milestones and periods. OR emerged as a discipline during the mid-20th century and has since evolved and expanded in response to changing societal needs and advancements in technology. Here's an overview of its historical development: 1. World War II and the Birth of Operations Research (1930s-1940s):  OR has its roots in military operations during World War II. The British Royal Air Force and the U.S. military faced complex logistical and strategic challenges.  Mathematicians and scientists were recruited to analyze and solve these problems, leading to the birth of OR.  Notable contributions include the British "Operational Research Section" and the American "Operations Research Group." 2. The Formation of OR Societies (1950s):  After World War II, the principles and methodologies of OR were applied to civilian sectors, including industry, transportation, and government.  In 1952, the Operations Research Society of America (ORSA) was founded, followed by the formation of the UK Operational Research Society in 1953.  These societies promoted the exchange of knowledge and research in OR. 3. Growth and Methodological Developments (1950s-1960s):  OR expanded rapidly during this period, with increasing applications in business, logistics, and engineering.  Linear programming, developed by George Dantzig in the late 1940s, became a prominent tool for optimization problems.  Other methodological advancements included queuing theory, game theory, and dynamic programming. 4. OR in Industry and the Business World (1970s-1980s):  OR continued to grow in the private sector, particularly in industries like manufacturing, finance, and telecommunications.  Companies realized the value of OR for improving operations, reducing costs, and enhancing decision-making.  The field of management science also emerged during this period, focusing on business-related problems. 5. Technological Advancements (1990s-Present):  The advent of computers and powerful software tools significantly expanded the capabilities of OR.  Simulation, optimization algorithms, and data analytics became more accessible and widely used in various applications.  OR played a critical role in supply chain management, healthcare, finance, and transportation. 6. Interdisciplinary and Global Expansion (21st Century):  OR increasingly became an interdisciplinary field, collaborating with computer science, data science, and artificial intelligence.  OR expanded globally, with OR societies and practitioners in many countries.  Applications extended to areas like environmental sustainability, energy management, and social policy. 7. Current and Future Trends:  OR continues to evolve with advancements in machine learning, big data analysis, and AI-driven optimization.  It plays a crucial role in addressing complex global challenges, such as climate change, healthcare crises, and urbanization. In summary, Operations Research has a rich history that began with its military origins during World War II. Over the decades, it has grown into a diverse and interdisciplinary field with applications spanning various industries and sectors. OR's adaptability and problem-solving capabilities have made it an essential tool for addressing complex challenges in an ever-changing world. Its evolution is likely to continue as technology and societal needs evolve further. Linear programming problem The Russian Mathematician L.V. Kantorovich applied mathematical model to solve linear programming problems. He pointed out in 1939 that many classes of problems which arise in production can be defined mathematically and therefore can be solved numerically. This decision making technique was further developed by George B. Dantziz. He formulated the general linear programming problem and developed simplex method (1947) to solve complex real time applications. Linear programming is one of the best optimization technique from theory, application and computation point of view. Definition: Linear Programming Problem(LPP) is a mathematical technique which is used to optimize (maximize or minimize) the objective function with the limited resources. Mathematically, the general linear programming problem (LPP) may be stated as follows. Maximize or Minimize Z = c1 x1 + c2 x2 + … + cn xn Subject to the conditions (constraints) Short form of LPP Some useful definitions: Objective function: A function Z=c1 x1 + c2x2 + …+ cnxn which is to be optimized (maximized or minimized) is called objective function. Decision variable: The decision variables are the variables, which has to be determined xj , j = 1,2,3,…,n, to optimize the objective function. Constraints: There are certain limitations on the use of limited resources called constraints. Solution: A set of values of decision variables xj, j=1,2,3,…, n satisfying all the constraints of the problem is called a solution to that problem. Feasible solution: A set of values of the decision variables that satisfies all the constraints of the problem and non-negativity restrictions is called a feasible solution of the problem. Optimal solution: Any feasible solution which maximizes or minimizes the objective function is called an optimal solution. Feasible region: The common region determined by all the constraints including non-negative constraints xj ≥0 of a linear programming problem is called the feasible region (or solution region) for the problem. Mathematical formulation of a linear programming problem: The procedure for mathematical formulation of a linear programming problem consists of the following steps. (i) Identify the decision variables. (ii) Identify the objective function to be maximized or minimized and express it as a linear function of decision variables. (iii) Identify the set of constraint conditions and express them as linear inequalities or equations in terms of the decision variables. Example 10.1 A furniture dealer deals only two items viz., tables and chairs. He has to invest Rs.10,000/- and a space to store atmost 60 pieces. A table cost him Rs.500/– and a chair Rs.200/–. He can sell all the items that he buys. He is getting a profit of Rs.50 per table and Rs.15 per chair. Formulate this problem as an LPP, so as to maximize the profit. Solution: (i) Variables: Let x1 and x2 denote the number of tables and chairs respectively. (i) Objective function: Profit on x1 tables = 50 x1 Profit on x2 chairs = 15 x2 Total profit = 50 x1+15x2 Let Z = 50 x1+15 x2 , which is the objective function. Since the total profit is to be maximized, we have to maximize Z=50x1+15x2 (iii) Constraints: The dealer has a space to store atmost 60 pieces x1+x2 ≤ 60 The cost of x1 tables = Rs.500 x1 The cost of x2 tables = Rs. 200 x2 Total cost = 500 x1 + 200 x2 ,which cannot be more than 10000 500 x1 + 200 x2 ≤ 10000 5x1+ 2x2 ≤ 100 (iv) Non-negative restrictions: Since the number of tables and chairs cannot be negative, we have x1 ≥0, x2 ≥0 Thus, the mathematical formulation of the LPP is Maximize Z=50 x1+15x2 Subject to the constrains x1+x2 ≤60 5x1+2x2≤100 x1, x2≥0 Example 10.2 A company is producing three products P1, P2 and P3, with profit contribution of Rs.20,Rs.25 and Rs.15 per unit respectively. The resource requirements per unit of each of the products and total availability are given below. Formulate the above as a linear programming model. Solution: (i) Variables: Let x1 , x2 and x3 be the number of units of products P1, P2 and P3 to be produced. (ii) Objective function: Profit on x1 units of the product P1 = 20 x1 Profit on x2 units of the product P2 = 25 x2 Profit on x3 units of the product P3 = 15 x3 Total profit = 20 x1 +25 x2 +15 x3 Since the total profit is to be maximized, we have to maximize Z= 20 x1+25 x2 +15 x3 Constraints: 6x1 +3 x2 +12 x3 ≤ 200 2 x1 +5 x2 +4 x3 ≤ 350 x1 +2 x2 + x3 ≤ 100 Non-negative restrictions: Since the number of units of the products A,B and C cannot be negative, we have x1, x2, x3 ≥ 0 Thus, we have the following linear programming model. Maximize Z = 20 x1 +25 x2 +15 x3 Subject to 6 x1 +3 x2 +12 x3≤ 200 2x1+5x2 +4 x3 ≤ 350 x1+2 x2 + x3≤ 100 x1, x2, x3 ≥ 0 Example 10.3 A dietician wishes to mix two types of food F1 and F2 in such a way that the vitamin contents of the mixture contains at least 6units of vitamin A and 9 units of vitamin B. Food F1 costs Rs.50 per kg and F2 costs Rs. 70 per kg. Food F1 contains 4 units per kg of vitamin A and 6 units per kg of vitamin B while food F2 contains 5 units per kg of vitamin A and 3 units per kg of vitamin B. Formulate the above problem as a linear programming problem to minimize the cost of mixture. Solution: (i) Variables: Let the mixture contains x1 kg of food F1 and x2 kg of food F2 (ii) Objective function: cost of x1 kg of food F1 = 50 x1 cost of x2 kg of food F2 = 70x2 The cost is to be minimized Therefore minimize Z= 50 x1+70x2 (iii) Constraints: We make the following table from the given data 4x1+5x2 ≥6 (since the mixture contains ‘atleast 6’ units of vitamin A ,we have the inequality of the type ≥ ) 6x1+3x2 ≥9(since the mixture contains ‘atleast 9’ units of vitamin B ,we have the inequality of the type ≥ ) (iv) Non-negative restrictions: Since the number of kgs of vitamin A and vitamin B are non-negative , we have x1, x2 ≥0 Thus, we have the following linear programming model Minimize Z = 50 x1 +70x2 subject to 4 x1+5x2≥6 6 x1+3x2≥9 and x1, x2≥0 Example 10.4 A soft drink company has two bottling plants C1 and C2. Each plant produces three different soft drinks S1,S2 and S3. The production of the two plants in number of bottles per day are: A market survey indicates that during the month of April there will be a demand for 24000 bottles of S1, 16000 bottles of S2 and 48000 bottles of S3. The operating costs, per day, of running plants C1 and C2 are respectively Rs.600 and Rs.400. How many days should the firm run each plant in April so that the production cost is minimized while still meeting the market demand? Formulate the above as a linear programming model. Solution: (i) Variables: Let x1 be the number of days required to run plant C1 and x2 be the number of days required to run plant C2 Objective function: Minimize Z = 600 x1 + 400 x2 (ii) Constraints: 3000 x1 + 1000 x2 ≥ 24000(since there is a demand of 24000 bottles of drink A, production should not be less than 24000) 1000x1 + 1000 x2 ≥ 16000 2000x1+ 6000 x2 ≥ 48000 (iii) Non-negative restrictions: Since be the number of days required of a firm are non-negative, we have x1, x2 ≥0 Thus we have the following LP model. Minimize Z = 600 x1 + 400 x2 subject to 3000 x1 + 1000 x2 ≥ 24000 1000 x1 + 1000 x2 ≥ 16000 2000 x1 + 6000 x2 ≥ 48000 and x1, x2 ≥0 Solution of LPP by graphical method After formulating the linear programming problem, our aim is to determine the values of decision variables to find the optimum (maximum or minimum) value of the objective function. Linear programming problems which involve only two variables can be solved by graphical method. If the problem has three or more variables, the graphical method is impractical. The major steps involved in this method are as follows (i) State the problem mathematically (ii) Write all the constraints in the form of equations and draw the graph (iii) Find the feasible region (iv) Find the coordinates of each vertex (corner points) of the feasible region. The coordinates of the vertex can be obtained either by inspection or by solving the two equations of the lines intersecting at the point (v) By substituting these corner points in the objective function we can get the values of the objective function (vi) If the problem is maximization then the maximum of the above values is the optimum value. If the problem is minimization then the minimum of the above values is the optimum value Example 10.5 Solve the following LPP Maximize Z = 2 x1 +5x2 subject to the conditions x1+ 4x2 ≤ 24 3x1+x2 ≤ 21 x1+x2 ≤ 9and x1, x2 ≥ 0 Solution: First we have to find the feasible region using the given conditions. Since both the decision variables x1 and x2 are non-negative ,the solution lies in the first quadrant. Write all the inequalities of the constraints in the form of equations. Therefore we have the lines x1+ 4x2=24 ; 3x1 + x2 = 21; x1 + x2= 9 x1+ 4x2= 24 is a line passing through the points (0 , 6) and (24 , 0). [(0,6) is obtained by taking x1=0 in x1 + 4x2 = 24 , (24 , 0) is obtained by taking x2 = 0 in x1+ 4x2 = 24]. Any point lying on or below the line x1 + 4x2 = 24 satisfies the constraint x1 + 4x2≤ 24 . 3x1 +x2= 21 is a line passing through the points (0, 21) and (7, 0). Any point lying on or below the line 3 x1 + x2 = 21 satisfies the constraint 3 x1 + x2 ≤ 21. x1+ x2 = 9 is a line passing through the points (0 , 9) and ( 9 , 0) .Any point lying on or below the line x1 + x2 = 9 satisfies the constraint x1+ x2 ≤ 9. Now we draw the graph. The feasible region satisfying all the conditions is OABCD.The co-ordinates of the points are O(0,0) A(7,0);B(6,3) [ the point B is the intersection of two lines x1+ x2= 9 and 3 x1+ x2= 21];C(4,5) [ the point C is the intersection of two lines x1+ x2 = 9 and x1+ 4x2 = 24] and D(0,6). Maximum value of Z occurs at C. Therefore the solution is x1 =4, x2 = 5, Z max = 33 Example 10.6 Solve the following LPP by graphical method Minimize z = 5x1+4x2 Subject to constraints 4x1+ x2 ≥ 40 ; 2x1+3x2 ≥ 90 and x1, x2 > 0 Solution: Since both the decision variables x1 and x2 are non-negative, the solution lies in the first quadrant of the plane. Consider the equations 4x1+x2 = 40 and 2 x1+3 x2 = 90 4x1+x 2 = 40 is a line passing through the points (0,40) and (10,0).Any point lying on or above the line 4x1+x2= 40 satisfies the constraint 4x1+ x2 ≥ 40. 2x1+3x2 = 90 is a line passing through the points (0,30) and (45,0). Any point lying on or above the line 2 x1+3x2= 90 satisfies the constraint 2x1+3x2 ≥ 90. Draw the graph using the given constraints. The feasible region is ABC (since the problem is of minimization type we are moving towards the origin. The minimum value of Z occurs at B(3,28). Hence the optimal solution is x1 = 3, x2 = 28 and Zmin=127 Example 10.7 Solve the following LPP. Maximize Z= 2 x1 +3x2 subject to constraints x1 + x2 ≤ 30 ; x2 ≤ 12; x1 ≤ 20 and x1, x2≥ 0 Solution: We find the feasible region using the given conditions. Since both the decision variables x1 and x2 are non-negative, the solution lies in the first quadrant of the plane. Write all the inequalities of the constraints in the form of equations. Therefore we have the lines x1+x2=30; x2 =12; x1= 20 x1+x2 =30 is a line passing through the points (0,30) and (30,0) x2 = 12 is a line parallel to x1–axis x1 = 20 is a line parallel to x2–axis. The feasible region satisfying all the conditions x1+ x2≤ 30; x2≤ 12 ; x1≤ 20 and x1, x2 ≥ 0 is shown in the following graph. The feasible region satisfying all the conditions is OABCD. The co-ordinates of the points are O(0,0) ; A(20,0); B(20,10) ; C(18,12) and D(0,12). Maximum value of Z occurs at C.Therefore the solution is x1 =18, x2= 12, Z max = 72 Example 10.8 Maximize Z = 3x1 + 4x2 subject to x1 – x2 < –1; –x1+x2 < 0 and x1, x2 ≥ 0 Solution: Since both the decision variables x1, x2 are non-negative ,the solution lies in the first quadrant of the plane. Consider the equations x1– x2 = –1 and – x1 + x2 = 0 x1– x2 =–1 is a line passing through the points (0,1) and (–1,0) –x1 + x2 = 0 is a line passing through the point (0,0) Now we draw the graph satisfying the conditions x1 – x2 < –1; –x1+x2 < 0 and x1, x2≥0 There is no common region(feasible region) satisfying all the given conditions. Hence the given LPP has no solution. Exercise 10.1 1. A company produces two types of pens A and B. Pen A is of superior quality and pen B is of lower quality . Profits on pens A and B are Rs 5 and Rs 3 per pen respectively. Raw materials required for each pen A is twice as that of pen B. The supply of raw material is sufficient only for 1000 pens per day . Pen A requires a special clip and only 400 such clips are available per day. For pen B, only 700 clips are available per day . Formulate this problem as a linear programming problem. 2. A company produces two types of products say type A and B. Profits on the two types of product are Rs.30/- and Rs.40/- per kg respectively. The data on resources required and availability of resources are given below. Formulate this problem as a linear programming problem to maximize the profit. 3. A company manufactures two models of voltage stabilizers viz., ordinary and auto-cut. All components of the stabilizers are purchased from outside sources , assembly and testing is carried out at company’s own works. The assembly and testing time required for the two models are 0.8 hour each for ordinary and 1.20 hours each for auto-cut. Manufacturing capacity 720 hours at present is available per week. The market for the two models has been surveyed which suggests maximum weekly sale of 600 units of ordinary and 400 units of autocut . Profit per unit for ordinary and auto-cut models has been estimated at Rs 100 and Rs 150 respectively. Formulate the linear programming problem. 4. Solve the following linear programming problems by graphical method. (i) Maximize Z = 6x1 + 8x2 subject to constraints 30x1+20x2 ≤300;5x1+10x2 ≤110; and x1, x2 > 0 . (ii) Maximize Z = 22x1 + 18x2 subject to constraints 960x1 + 640x2 ≤ 15360 ; x1 + x2 ≤ 20 and x1 , x2 ≥ 0 . (iii) Minimize Z = 3x1 + 2x2 subject to the constraints 5x1+ x2≥10; x1+ x2≥6; x1+ 4 x2 ≥12 and x1, x2≥0. (iv) Maximize Z = 40x1 + 50x2 subject to constraints 30x1 + x2 ≤ 9 ; x1 + 2x2 ≤ 8 and x1 , x2 ≥ 0 (v) Maximize Z = 20x1 + 30x2 subject to constraints 3x1 + 3x2 ≤ 36 ; 5x1 + 2x2 ≤ 50 ; 2x1 + 6x2 ≤ 60 and x1 , x2 ≥ 0 (vi) Minimize Z = 20x1 + 40x2 subject to the constraints 36x1 + 6x2≥ 108, 3x1 + 12x2≥ 36, 20x1 + 10x2 ≥ 100 and x1 , x2≥ 0