CU-BCA-SEM-I-Mathematics

Cross-entropy, the cost function that we use a lot to estimate a probability distribution over the goal, is one of the most well-known probabilistic models. Bayesian inference and maximum a posteriori (MAP) are two more prominent probabilistic model uses. Simulation: When deriving a probability distribution is not possible, simulation is employed to approximate one. It obtains numerical results through repeated random sampling. The concept is to harness chance to solve issues that are otherwise deterministic. Simulation offers a wide range of applications, including generating draws from various probability distributions, numerical integration, reinforcement learning, option pricing, and so on. 3. Applications in real life Operations research is applied to a lot of real-world use cases. ● Your task (assigning Uber drivers to customers) ● Time management (scheduling multiple TV shows together to achieve the maximum views possible) ● Financial Planning and Analysis (asset allocation, risk management, derivatives pricing, portfolio management, etc.) ● YouTube's Smart Bidding, an automated bidding system for algorithmic advertising (determining how much incremental value can be attributed to a particular impression and how much we should pay for it.) ● Science of Pricing (airline ticket pricing) 201 CU IDOL SELF LEARNING MATERIAL (SLM)

● Scheduling (master planning the routes of buses so that as few buses are needed as possible) ● Facility Site (choosing the best location for new facilities like warehouses and factories). ● Network Optimization (packet routing) These OR brain teasers are very frequent in tech interviews, at least in FAAMG. Personally, I was asked two out of three below. ● N Queen Problem: How to place N queens on an N x N chessboard so that no two of them attack each other. Two queens should not be on the same row, column, or diagonal. 202 CU IDOL SELF LEARNING MATERIAL (SLM)

● shortest round trip? In mathematical terms, given a directed, edge-weighted graph, what is the shortest cyclic path that visits each node in the graph exactly once? 203 CU IDOL SELF LEARNING MATERIAL (SLM)

● Stigler Diet: is named after economics Nobel laureate George Stigler, who computed an inexpensive way to fulfill basic nutritional needs given a set of foods. It is a classic linear optimization problem. How do we select a set of foods that will satisfy a set of daily nutritional requirement at minimum cost? 204 CU IDOL SELF LEARNING MATERIAL (SLM)

7.2 OBJECTIVE FUNCTION A general LP problem could be formulated as given in the following. Where A = coefficient matrices 205 CU IDOL SELF LEARNING MATERIAL (SLM)

c = original cost vector b = vector of constants on the right hand side of equation or inequality constraints x = vector of problem variables z = scalar objective function The optimization problem is stated as a minimization to be consistent with most books on optimization. We can solve a maximization problem by noting that maximizing (z) is equivalent to minimizing (-z). Also, by convention the values of the right hand sides of the equations and ≥ 0. We can always achieve a positive right hand side by multiplying inequalities are positive (bi the equation or inequality by (-1). Recall that multiplying by (-1) changes the sense of an inequality, e.g., less than to greater than. We want to convert to a formulation involving only equalities, since a corner point is defined by equalities (the original equations and a subset of active equalities). Converting to equalities can be achieved by adding a variable to any inequality. This variable has the value of the difference between the left-hand side value (depending on the variable values) and the right hand side value (a constant). These variables are termed slack variables, which are limited to be ≥ 0). By adding one slack variable to each inequality (but not to equalities), non-negative (inequalities are converted to equalities. When this addition has been completed, all relationships among variables are equalities. Examples are given in the following. 206 CU IDOL SELF LEARNING MATERIAL (SLM)

Unfortunately, the terminology is not consistent among references. We will use the term “slack” for a variable added to convert an inequality to an equality, regardless of the sign of its coefficient, plus or minus. Some references use “slack” when the coefficient is +1 and either “surplus” or “excess” variable when the coefficient is –1. 7.3 OPTIMIZATION The selection of basic and non-basic variables determines the set of inequalities that are active. 207 CU IDOL SELF LEARNING MATERIAL (SLM)

It is shows the importance of the active set in finding the optimum and gives insight into the optimum corner point. In the example shown, only one set of active constraints gives the minimum objective. The optimum corner point is determined from the gradient of the objective and constraints. Note that this criterion enables us to determine the optimum from local information; we do not have to evaluate all or any other corner points. When the specified condition is satisfied, no movement along a constraint can improve the objective function. We know for an LP that the optimum must be at a corner point and a local optimum is also global; therefore, the corner point is the global optimum. The principles of optimization and the special features of linear programming result in the following concepts for identifying the optimum. 208 CU IDOL SELF LEARNING MATERIAL (SLM)

● Formulate the problem as a general LP optimization problem ● Add slack variables to convert inequalities to equalities ● Separate variables into basic and non-basic ● Choose as the optimum the basic variable selection that provides a feasible solution with the optimum value of the objective function These principles provide us with excellent insight into the LP method. 7.4 SUMMARY ● Optimization methods are used in many fields of study to find solutions that maximise or minimise some study parameters, such as minimising costs in the production of a good or service, maximising profits, minimising raw material in the development of a good, or maximising production. ● A probabilistic model generates a probability distribution, while a deterministic model generates a single probable event outcome. ● Simulation-based optimization (also known as simply simulation optimization) integrates optimization techniques into simulation Modeling and analysis. Because of the complexity of the simulation, the objective function may become difficult and expensive to evaluate. Usually, the underlying simulation model is stochastic, so that the objective function must be estimated using statistical estimation techniques (called output analysis in simulation methodology). 209 CU IDOL SELF LEARNING MATERIAL (SLM)

7.5 KEYWORDS • Basic solution: a basic solution is any solution of a linear programming problem satisfying certain specified technical conditions. • Gradient : The gradient of the objective function is contained within the cone of the gradients of the active constraints at the optimum corner point. • Slack variable: a slack variable is a variable that is added to an inequality constraint to transform it into equality. • Basic variables : the basic variables can be defined as the m variables which can take any value other than zero • Probabilistic modelling: Probabilistic Modeling is a statistical technique used to take into account the impact of random events or actions in predicting the potential occurrence of future outcomes. 7.6 LEARNING ACTIVITY 1. What are the types of optimization problem? ___________________________________________________________________________ _____________________________________________________________________ 2. Which technique is mainly used to solve optimization problems? ___________________________________________________________________________ _____________________________________________________________________ 210 CU IDOL SELF LEARNING MATERIAL (SLM)

7.7 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. How do you optimize a function? 2. Why do we need optimization techniques in real life? 3. How do you optimize a design? 4. What is optimization in design process? 5. What are design variables in optimization? Long Questions 1. Explain the objective function with example. 2. Classify the optimization techniques. 3. Explain optimization and its techniques. 4. Define optimization and write the application of optimization techniques. 5. Explain the three elements of an optimization problem. B. Multiple Choice Questions 1. Feasible region is the set of points which satisfy a. The objective functions b. Some the given constraints c. All of the given constraints 211 CU IDOL SELF LEARNING MATERIAL (SLM)

d. None of these 2. Of all the points of the feasible region for maximum or minimum of objective function the points must be a. Inside the feasible region b. At the boundary line of the feasible region c. Vertex point of the boundary of the feasible region d. None of these 3. Objective function of a linear programming problem is a. a constraint b.function to be optimized c.A relation between the variables d. None of these 4. What is the objective function of a structural design problem? a. Bending b. Loads c. Bondage d. Costs 212 CU IDOL SELF LEARNING MATERIAL (SLM)

5. What is a constraint? a. Response b. Parameter c. Limitation d. Principle Answers 1-c, 2-c, 3-b. 4-d, 5-c 7.8 REFERENCES References book ● Taha, H.A., “Operations Research: An Introduction”, 9th Edition, Pearson Education, Asia, New Delhi, 2016. ● Vittal, P.R, “Allied Mathematics”, Reprint,Margham Publications, Chennai. ● Venkata chalapathy, S.G, “Allied Mathematics”, Margham Publications, Chennai. Textbook references ● Singaravelu, A. “Allied Mathematics”, Meenakshi Agency, Chennai. ● Hennoy G.V. and Srivastava U.K., “Operation Research for Management”, Wiley Eastern,1994. ● Bazara M.J., Jarvis and Sherali H., “Linear Programming and Network Flows”, John Wiley,1990. 213 CU IDOL SELF LEARNING MATERIAL (SLM)

● Philip D.T. and Ravindran A., “Operations Research”, John Wiley, 1992. ● Hillier and Libeberman, “Operations Research”, Holden Day, 1986. 214 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT - 8: DIFFERENT TYPES OF LINEAR PROGRAMMING (L.P.) PROBLEMS 1 STRUCTURE 8.0 Learning Objectives 8.1 Introduction 8.2 Different types of linear programming (L.P.) problems 8.3 Mathematical formulation of L.P. 8.4 Summary 8.5 Keywords 8.6 Learning Activity 8.7 Unit End Questions 8.8 References 8.0 LEARNING OBJECTIVES After studying this unit, you will be able to: ● Formulate linear programs ● Describe the geometry of linear programs. ● Describe the graphical solution approach. ● Describe computer solutions of linear programs. 215 CU IDOL SELF LEARNING MATERIAL (SLM)

● Use linear programming models for decision making. 8.1 INTRODUCTION In Mathematics, linear programming is a method of optimizing operations with some constraints. The main objective of linear programming is to maximize or minimize the numerical value. It consists of linear functions which are subjected to the constraints in the form of linear equations or in the form of inequalities. Linear programming is considered an important technique that is used to find the optimum resource utilization. The term “linear programming” consists of two words as linear and programming. The word “linear” defines the relationship between multiple variables with degree one. The word “programming” defines the process of selecting the best solution from various alternatives. Linear Programming is widely used in Mathematics and some other field such as economics, business, telecommunication, and manufacturing fields. In this article, let us discuss the definition of linear programming, its components, a simplex method with linear programming problems. Linear programming (LP) or Linear Optimization may be defined as the problem of maximizing or minimizing a linear function that is subjected to linear constraints. The constraints may be equalities or inequalities. The optimization problems involve the calculation of profit and loss. 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. 216 CU IDOL SELF LEARNING MATERIAL (SLM)

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. Some of the assumptions taken while working with linear programming are: ● The number of constraints should be expressed in the quantitative terms ● The relationship between the constraints and the objective function should be linear ● The linear function (i.e., objective function) is to be optimized Components of Linear Programming The basic components of the LP are as follows: ● Decision Variables ● Constraints ● Data ● Objective Functions Characteristics of Linear Programming The following are the five characteristics of the linear programming problem: ● Constraints: The limitations should be expressed in the mathematical form, regarding the resource. ● Objective Function: In a problem, the objective function should be specified in a quantitative way. ● Linearity: The relationship between two or more variables in the function must be linear. It means that the degree of the variable is one. 217 CU IDOL SELF LEARNING MATERIAL (SLM)

● Finiteness: There should be finite and infinite input and output numbers. In case, if the function has infinite factors, the optimal solution is not feasible. ● Non-negativity: The variable value should be positive or zero. It should not be a negative value. ● Decision Variables: The decision variable will decide the output. It gives the ultimate solution of the problem. For any problem, the first step is to identify the decision variables. 8.2 DIFFERENT TYPES OF LPP The Linear Programming Problems (LPP) is a problem that is concerned with finding the optimal value of the given linear function. The optimal value can be either maximum value or minimum value. Here, the given linear function is considered an objective function. The objective function can contain several variables, which are subjected to the conditions and it has to satisfy the set of linear inequalities called linear constraints. In Linear programming, the term “linear” represents the mathematical relationship that is used in the given problem (Generally, linear relationship) and the term “programming” represents the method of determining the particular plan of action. The linear programming problems can be used to get the optimal solution for the following scenarios, such as manufacturing problems, diet problems, transportation problems, allocation problems and so on. Different Parts of the LP Model 1. Decision Variable: Variables which are changeable & going to impact the decision function. Like the profit function is effected by both sales and price, now which one of these two is changeable, will be our decision variable. 218 CU IDOL SELF LEARNING MATERIAL (SLM)

2. Objective Function: Linear function of the objective, either to Maximize or minimize, like Maximize Profit, sales, production etc. and Minimize Cost, Loss, energy, consumption, wastage etc. 3. Constraints: Any kind of limitation or scarcity explained through a function like Limitations of raw materials, time, funds, equipment's etc. Non-Negative Constraints will also be there which will remain non-negative all the time. 8.3 FORMULATION OF LPP It is an important optimization (maximization or minimization) technique used in decision making is business and everyday life for obtaining the maximum or minimum values as required of a linear expression to satisfying certain number of given linear restrictions. Linear Programming Problem (LPP) The linear programming problem in general calls for optimizing a linear function of variables called the objective function subject to a set of linear equations and/or linear in equations called the constraints or restrictions. Objective Function The function which is to be optimized (maximized/minimized) is called an objective function. Constraints The system of linear in equations (or equations) under which the objective function is to be optimized is called constraints. Non-negative Restrictions 219 CU IDOL SELF LEARNING MATERIAL (SLM)

All the variables considered for making decisions assume non-negative values. Mathematical Description of a General Linear Programming Problem Formulation of an LP Problem: 1. Recognize the decision variables and assign symbols to them like X, Y, Z & so on). Now these are the quantities we wish to find out. 2. Express all the constraints in terms of inequalities in relation the decision variable. 3. Formulate the objective function in terms of the decision variables. 4. Add the non-negativity condition/constraints. A general LPP can be stated as and the non-negative restrictionsxl, x2,….., xn ≥ 0 Methods to Solve Linear Programming Problems 220 CU IDOL SELF LEARNING MATERIAL (SLM)

The linear programming problem can be solved using different methods, such as the graphical method, simplex method, or by using tools such as R, open solver etc. Here, we will discuss the two most important techniques called the simplex method and graphical method in detail. Example: Calculate the maximal and minimal value of z = 5x + 3y for the following constraints. x + 2y ≤ 14 3x – y ≥ 0 x – y ≤ 2 and x, y ≥ 0 Solution: The three inequalities indicate the constraints. The area of the plane that will be marked is the feasible region. The optimization equation (z) = 5x + 3y. You have to find the (x,y) corner points that give the largest and smallest values of z. To begin with, first solve each inequality. x + 2y ≤ 14 ⇒ y ≤ -(1/2)x + 7 3x – y ≥ 0 ⇒ y ≤ 3x x–y≤2⇒y≥x–2 Here is the graph for the above equations. 221 CU IDOL SELF LEARNING MATERIAL (SLM)

Now pair the lines to form a system of linear equations to find the corner points. y = -(½) x + 7 y = 3x Solving the above equations, we get the corner points as (2, 6) y = -1/2 x + 7 y=x–2 Solving the above equations, we get the corner points as (6, 4) y = 3x y=x–2 Solving the above equations, we get the corner points as (-1, -3) 222 CU IDOL SELF LEARNING MATERIAL (SLM)

For linear systems, the maximum and minimum values of the optimisation equation lie on the corners of the feasibility region. Therefore, to find the optimum solution, you only need to plug these three points in z = 3x + 4y When the point (2, 6) : z = 5(2) + 3(6) = 10 + 18 = 28 When the point (6, 4): z = 5(6) + 3(4) = 30 + 12 = 42 When the point (–1, –3): z = 5(-1) + 3(-3) = -5 -9 = -14 Hence, the maximum of z = 42 lies at (6, 4) and the minimum of z = -14 lies at (-1, -3) Example 2: Let us look at this diet problem, A house wife wishes to mix two types of food F1 and F2 in such a way that the vitamin contents of the mixture contain at least 8 units of vitamin A and 11 units of vitamin B. Food F1 costs E60/Kg and Food F2 costs E80/kg. Food F1 contains 3 units/kg of vitamin A and 5 units/kg of vitamin B while Food F2 contains 4 units/kg of vitamin A and 2 units/kg of vitamin B. Formulate this problem as a linear programming problem to minimize the cost of the mixtures, 223 CU IDOL SELF LEARNING MATERIAL (SLM)

Solution: Let’s follow the steps given to formulate and LP: 1. The kgs of the F1 and F2 in the mixture are our decision variables. Suppose the mixture has X Kg of Food F1 and Y Kg of food F2. 2. In this example, the constraints are the minimum requirements of the vitamins. The minimum requirement of vitamin A is 8 units. Therefore 3X + 4Y ≥ 8. Similarly, the minimum requirement of vitamin B is 11 units. Therefore, 5X + 2Y ≥ 11 3. The cost of purchasing 1 Kg of food F1 is E60. The cost of purchasing 1 Kg of food F2 is E80. The total cost of purchasing X Kg of food F1 and Y Kg of food F2 is C = 60X + 80Y, which is the objective function. 4. The non-negativity conditions are X ≥ 0, Y ≥ 0 Therefore the mathematical formulation of the LPP is: Minimize: C = 60X + 80Y Subject to: 224 CU IDOL SELF LEARNING MATERIAL (SLM)

3X + 4Y ≥ 8 5X + 2Y ≥ 11 and X ≥ 0 , Y ≥ 0 Example 3: Solution: 225 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 4: Solution: 226 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 5: 227 CU IDOL SELF LEARNING MATERIAL (SLM)

Solution: 228 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 6: Solution: 229 CU IDOL SELF LEARNING MATERIAL (SLM)

230 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 7: Solution: 231 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 8: 232 CU IDOL SELF LEARNING MATERIAL (SLM)

Solution: 233 CU IDOL SELF LEARNING MATERIAL (SLM)

8.4 SUMMARY ● To determine the ideal production levels for maximum profit in specific circumstances, taking into account the restrictions of labour and supplies is a real-time example. ● It falls under the heading of optimization techniques, which is a crucial branch of mathematics. ● The steps of defining a Linear Programming problem generically: o Identify the decision variables o Write the objective function o Mention the constraints o Explicitly state the non-negativity restriction o For a problem to be a linear programming problem, the decision variables, objective function and constraints all have to be linear functions. If all the three conditions are satisfied, it is called a Linear Programming Problem. 8.5 KEYWORDS • Constraints: The limitations should be expressed in the mathematical form, regarding the resource. • Objective Function: In a problem, the objective function should be specified in a quantitative way. 234 CU IDOL SELF LEARNING MATERIAL (SLM)

• Linearity: The relationship between two or more variables in the function must be linear. It means that the degree of the variable is one. • Finiteness: There should be finite and infinite input and output numbers. In case, if the function has infinite factors, the optimal solution is not feasible. • Non-negativity: The variable value should be positive or zero. It should not be a negative value 8.6 LEARNING ACTIVITY 1. A doctor wishes to mix two types of foods in such a way that the vitamin contents of the mixture contain at least 8 units of vitamin A and 10 units of vitamin C. Food ‘I’ contains 2 units/kg of vitamin A and 1 unit/kg of vitamin C. Food ‘II’ contains 1 unit/kg of vitamin A and 2 units/kg of vitamin C. It costs Rs 50 per kg to purchase Food ‘I’ and Rs 70 per kg to purchase Food ‘II’. Formulate this problem as a linear programming problem to minimize the cost of such a mixture. ___________________________________________________________________________ _______________________________________________________________ 2. One kind of cake requires 200g of flour and 25g of fat, and another kind of cake requires 100g of flour and 50g of fat. Formulate this problem as a linear programming problem to find the maximum number of cakes that can be made from 5kg of flour and 1 kg of fat assuming that there is no shortage of the other ingredients used in making the cakes. 235 CU IDOL SELF LEARNING MATERIAL (SLM)

___________________________________________________________________________ _______________________________________________________________ 3. Write the general form of LPP. ___________________________________________________________________________ _____________________________________________________________________ 8.7 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. What is meant by LPP? 2. Explain how one can calculate LPP? 3. What are the various advantages of LPP? 4. Who is credited with the development of LPP? 5. Define the decision Variable. Long Questions 1. Explain the formation of linear programming problem. 2. A calculator company produces a handheld calculator and a scientific calculator. Long-term projections indicate an expected demand of at least 150 scientific and 100 handheld calculators each day. Because of limitations on production capacity, no more than 250 scientific and 200 handheld calculators can be made daily. To satisfy a 236 CU IDOL SELF LEARNING MATERIAL (SLM)

shipping contract, a minimum of 250 calculators must be shipped each day. If each scientific calculator sold, results in a 20 rupees loss, but each handheld calculator produces a 50 rupees profit; then how many of each type should be manufactured daily to maximize the net profit? 3. Let us look at this diet problem, A house wife wishes to mix two types of food F1 and F2 in such a way that the vitamin contents of the mixture contain at least 8 units of vitamin A and 11 units of vitamin B. Food F1 costs E60/Kg and Food F2 costs E80/kg. Food F1 contains 3 units/kg of vitamin A and 5 units/kg of vitamin B while Food F2 contains 4 units/kg of vitamin A and 2 units/kg of vitamin B. Formulate this problem as a linear programming problem to minimize the cost of the mixtures. 4. A furniture company produces inexpensive tables and chairs. The production process for each is similar in that both require a certain number of hours of carpentry work and a certain number of labour hours in the painting department. Each table takes 4 hours of carpentry and 2 hours in the painting department. Each chair requires 3 hours of carpentry and 1 hour in the painting department. During the current production period, 240 hours of carpentry time are available and 100 hours in painting is available. Each table sold yields a profit of E7; each chair produced is sold for a E5 profit. Find the best combination of tables and chairs to manufacture in order to reach the maximum profit. 237 CU IDOL SELF LEARNING MATERIAL (SLM)

5. A manufacture makes two types of toys A and B. Three machines are needed for this purpose and the time(in minutes) required for each toy on the machines is given below: Each machine is available for a maximum of 6 hours per day. If the profit on each toy of type A is Rs. 7.50 and that on each toy of type B is Rs. 5, show that 15 toys of type A and 30 of type B should be manufactured in a day to get maximum profit. B. Multiple Choice Questions 1. ---------- specifies the objective of goal of solving the LPP. a. Objective function b. Decision variables c. Constraints d. Opportunity costs 2. The type of constraint which specifies maximum capacity of resource is ------or equal to constraint. 238 CU IDOL SELF LEARNING MATERIAL (SLM)

a. Less than b. Greater than c. Less than or greater than d. All of these 3. In linear programming --------------- represents mathematical equation of the limitations imposed by the problem a. Objective function b. Decision variable c. Redundancy d. Constraints 4. ------------- are the entities whose values are to be determined from the solution of the LPP a. Objective function b. Decision variable c. Constraints d. Opportunity costs 5. Objective function is expressed in terms of the ------- a. Number 239 CU IDOL SELF LEARNING MATERIAL (SLM)

b. Symbols c. Decision variable d. None of the above Answers 1-b, 2-a, 3-a. 4-d, 5-c 8.8 REFERENCES References book ● Taha, H.A., “Operations Research: An Introduction”, 9th Edition, Pearson Education, Asia, New Delhi, 2016. ● Vittal, P.R, “Allied Mathematics”, Reprint,Margham Publications, Chennai. ● Venkata chalapathy, S.G, “Allied Mathematics”, Margham Publications, Chennai. Textbook references ● Singaravelu, A. “Allied Mathematics”, Meenakshi Agency, Chennai. ● Hennoy G.V. and Srivastava U.K., “Operation Research for Management”, Wiley Eastern,1994. ● Bazara M.J., Jarvis and Sherali H., “Linear Programming and Network Flows”, John Wiley,1990. ● Philip D.T. and Ravindran A., “Operations Research”, John Wiley, 1992. 240 CU IDOL SELF LEARNING MATERIAL (SLM)

● Hillier and Libeberman, “Operations Research”, Holden Day, 1986. 241 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT - 9: DIFFERENT TYPES OF LINEAR PROGRAMMING (L.P.) PROBLEMS 2 STRUCTURE 9.0 Learning Objectives 9.1 Introduction 9.2 Graphical method 9.3 Solution for problems in two variables 9.4 Summary 9.5 Keywords 9.6 Learning Activity 9.7 Unit End Questions 9.8 References 9.0 LEARNING OBJECTIVES After studying this unit, you will be able to: ● Use the graphical way to solve an LP problem. ● Know what terminology like extreme points, infeasibility, redundancy, and many solutions mean. ● Using the graphical method, demonstrate the solution of LPP. 242 CU IDOL SELF LEARNING MATERIAL (SLM)

● Interpret an LP model's solution. ● Linear Programming Applications in Industry and Business 9.1 INTRODUCTION The graphical method is used to optimize the two-variable linear programming. If the problem has two decision variables, a graphical method is the best method to find the optimal solution. In this method, the set of inequalities are subjected to constraints. Then the inequalities are plotted in the XY plane. Once, all the inequalities are plotted in the XY graph, the intersecting region will help to decide the feasible region. The feasible region will provide the optimal solution as well as explains what all values our model can take. Let us see an example here and understand the concept of linear programming in a better way. 9.2 GRAPHICAL METHOD Graphical Method to solve an LPP The graphical method of solving a linear programming problem can be used when there are only two decision variables. If the problem has three or more variables, the graphical method is not suitable. In that case we use the SIMPLEX METHOD which will be discussed separately in the next PPT or in Classroom. Let’s understand some important definitions and concepts before moving on with the Graphical Method: 1. Solution: A set of decision variables values which satisfy all the constraints of an LPP. 243 CU IDOL SELF LEARNING MATERIAL (SLM)

2. Feasible solution: Any solution which also satisfies the non-negativity limitations of the problem. 3. Optimal feasible solution: Any feasible solution which maximizes or minimizes the objective function. 4. Feasible Region: The common region determined by all the constraints and non- negativity limitations of an LPP. 5. Corner point: A point in the feasible region that is the intersection of two boundary lines Steps for solving LPP through Graphical Method 1. Formulate the LPP problems and develop objective function along with all the constraints function. 2. Graph the feasible region and find the corner points. The coordinates of the corner points can be obtained by either inspection or by solving the two equations of the lines intersecting at that point. 3. Make a table listing the value of the objective function at each corner point. 4. Determine the optimal solution from the table in step 3. If the problem is of maximization (minimization) type, the solution corresponding to the largest (smallest) value of the objective function is the optimal solution of the LPP Important Definitions and Results 244 CU IDOL SELF LEARNING MATERIAL (SLM)

a. Solution of a LPP A set of values of the variables xl, x2,…., xn satisfying the constraints of a LPP is called a solution of the LPP. b. Feasible Solution of a LPP A set of values of the variables xl, x2,…., xn satisfying the constraints and non-negative restrictions of a LPP is called a feasible solution of the LPP. c. Optimal Solution of a LPP A feasible solution of a LPP is said to, be optimal (or optimum), if it also optimizes the objective function of the problem. d. Graphical Solution of a LPP The solution of a LPP obtained by graphical method i.e., by drawing the graphs corresponding to the constraints and the non- negative restrictions is called the graphical solution of a LPP. e. Unbounded Solution If the value of the objective function can be increased or decreased indefinitely, such solutions are called unbounded solutions. 9.3 PROBLEMS IN LPP BY GRAPHICAL METHOD Example1: Solution: 245 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 2: Solution: 246 CU IDOL SELF LEARNING MATERIAL (SLM)

247 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 3: Solution: 248 CU IDOL SELF LEARNING MATERIAL (SLM)

249 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 4: Solution: 250 CU IDOL SELF LEARNING MATERIAL (SLM)