CU-BCA-SEM-I-Mathematics (1)

2  5  4  0 (  1)(  4)  0   1,4. So, the Eigen values of A3 are 13, 43 (ie) 1, 64. Example: 12  8  6 2   6 7  4 Find the sum and product of the Eigen values of the matrix A=  2  4 3  Solution: Sum of the Eigen values = Sum of the main diagonal elements = 8 + 7 + 3 = 18 Product of the Eigen values =A 8 6 2  4  8[21 16]  6[18  8]  2[24 14]  0  6 7 3 2 4 Example: 13  3 1 1  A  1 5 1 Two of the Eigen values of  1 1 3  are 3 & 6. Find the Eigen values of A-1 and -5A. Solution: Sum of Eigen values = Sum of main diagonal elements. Let us consider the 3rd Eigen value be λ 36 353   11 9 2 Eigen values are 2, 3, 6. Hence Eigen values of A-1 are ½, 1/3, 1/6. Eigen values of -5A are -10,-15,-30. Example: 14 If one of the Eigen vectors of a matrix  6  2 2  (2 -1 1) T Find the corresponding Eigen value. A   2 3  1  2  1 3  is Solution: 101 CU IDOL SELF LEARNING MATERIAL (SLM)

If λ is an Eigen value then A  IX  0  6   2 2  2   2 3  1   1  0  2 1 3    1  2(6-λ) +2+2 =0 λ = 8. Example: 15 1 7 5 0 2 9 What is the sum of squares of the Eigen values of 0 0 5 Solution: The Eigen values of a triangular matrix are just the principal diagonal elements of the matrix. 1 7 5 A  0 2 9 Given matrix is 0 0 5 1 7 5  0 2 9 0 A  I  0 0 0 5   The sum of squares of Eigen values are = 12+22+52 = 1+4+25 = 30 Example: 16 If 2, 2, 3 are Eigen values of the matrix A, find the eigen values of adjoint of A, where  3 10 5  A   2  3  4  3 5 7  Solution: A The Eigen value of adjoint of a matrix = Eigen value of A Here A  12 The eigen value of adjoint of A = 12 6 , 12  6 , 12  4 2 2 3 Example: 17 102 CU IDOL SELF LEARNING MATERIAL (SLM)

2 1 1 A  1 3 1 Two of the Eigen values of 1 2 2 are equal to 1 each. Find the Eigen values of A-1 Solution: Sum of the Eigen values = Sum of the main diagonal elements. Let us consider the 3rd Eigen value be λ 11  23 2  72  5 Eigen values are 1, 1, 5. Hence Eigen values of A-1 are 1,1,1/5. 5.5 SUMMARY ● This chapter explains what linear algebra is and how it relates to vectors and matrices in this Linear Algebra course. ● We'll go over what vectors and matrices are and how to use them to solve problems, as well as the thorny problem of Eigenvalues and Eigenvectors. ● To utilise these to do interesting things with datasets, such as rotating photos of faces and extracting eigenvectors to investigate how the Pagerank algorithm works. ● By the end of this course, you'll have an intuitive grasp of vectors and matrices that will help you bridge the gap between linear algebra problems and machine learning. 5.6 KEYWORD • Homogeneous: made up of parts that are all of the same type. • Eigen Values : Eigenvalues are the special set of scalar values that is associated with the set of linear equations most probably in the matrix equations. • Eigen vectors: Eigenvectors are a special set of vectors associated with a linear system of equations (i.e., a matrix equation) that are sometimes also known as characteristic vectors, proper vectors, or latent vectors • Trace : The sum of the principal diagonal elements is called the Trace of the matrix 103 CU IDOL SELF LEARNING MATERIAL (SLM)

• Trivial solution : the system of equation in which the determinant of the coefficient matrix is not zero but the solution is x=y=z=0 is called trivial solution 5.7 LEARNING ACTIVITY 0 1 1  1 0  1 1. Find the sum and product of the Eigen values of the matrix. 1  1 0  ___________________________________________________________________________ _______________________________________________________________ 2. If sum of two Eigen values of a 3 X 3 matrix is equal to its trace. Find the determinant value of the matrix. ___________________________________________________________________________ ___________________________________________________________________ 5.8 UNIT END QUESTIONS A. Descriptive Questions Short Questions  8  6 2   6 7  4 1. Find the sum and product of the Eigen values of the matrix A=  2  4 3   6  2 2    2 3  1 2. The product of two Eigen values of the matrix A =  2  1 3  is 16.Find the third Eigen value.  2 1 0 0 3 4 3. Find the Eigen values of the inverse of the matrix A = 0 0 4 4. If the sum of two Eigen values and trace of 3x 3 matrix A are equal.Find the value of A.  2 2 1 1 3 1 5. Two Eigen values of matrix A = 1 2 2 are equal to 1 each. Find the Eigen value of A-1. Long Questions 104 CU IDOL SELF LEARNING MATERIAL (SLM)

A   1 11 3 1. Find the Eigen value and Eigen vector of  2 0 1 0 2 0 2. Find the Eigen value of adj (A) if A = 1 0 2  2 2 1 A  1 3 1 3. Two Eigen values of the matrix 1 2 2 equal to 1 each. Find the third Eigenvalue. 4. Find the Eigen values and Eigen vectors of the matrix  3 1 4  1 1 3 (i)A   0 2 6 (ii)A   1 5 1    0 0 5  3 1 1  5. Find the Eigen values and Eigen vectors of the matrix  7  2 0  A   2 6  2  0  2 5  B. Multiple Choice Questions 1. Find the Eigen vector for value of λ=-2 for the given matrix. A  3 5 3 1 a.  01 b.  11 c.   11  d.  1  0 105 CU IDOL SELF LEARNING MATERIAL (SLM)

2. Find the Eigen vector for value of λ=3 for the given matrix.  3 0 5  A   2 3  4  3 5 7   1  1 a.  2   1 1 b.  2   1  1 c.   2  1  2 d.  2  3. Which of the following is not a necessary condition for a matrix, say A, to be diagonalizable? a. A must have n linearly independent Eigen vectors b. All the Eigen values of A must be distinct c. A can be an idempotent matrix d. A must have n linearly dependent Eigen vectors 1 0 6 A  0 5 0 4. Find the trace of the matrix 0 4 4 a. 0 b. 10 c. 4 d. 1 106 CU IDOL SELF LEARNING MATERIAL (SLM)

5. The determinant of the matrix whose eigen values are 4, 2, 3 is given by, _______ a.9 b.24 c.5 d.3 A 3 2 1 2 6. Obtain the Eigen value of A where a. 1, -4 b. -1, 4 c. 1, 4 d. -1, -4 1 0 0  0 3  1 7. The product of the Eigen values of matrix 0 1 3  is a. 6 b. 7 c. 8 d. 9 1 1 1     1 1 1  8. The sum of the Eigen values of the matrix  1 1 1 are a. 3 b. -3 c. 2 d. -2 9. For a given matrix A of order three, A  32 and two of its Eigen values are 8 and 2. Find the sum of the Eigen values. a. 12 b. 13 c. 14 d. 15 107 CU IDOL SELF LEARNING MATERIAL (SLM)

 3 1 1  A  1 5 1 10. Two of the Eigen values of  1 1 3  are 3 & 6 then the Eigen values of A-1 are a. ½, -1/3, 1/6. b. ½, 1/3,- 1/6. c. -½, 1/3, 1/6. d. ½, 1/3, 1/6. Answers 1-b, 2-a, 3-d, 4-b, 5-b, 6-c, 7-c, 8-b, 9-a, 10-d. 5.9 REFERENCES References book ● 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. ● N. Herstein, Topics in Algebra, John Wiley and Sons, 2015. ● Gilbert Strang, Introduction to linear algebra, Fifth Edition, ANE Books, 2016. 108 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT - 6: LINEAR PROGRAMMING 1 STRUCTURE 6.0 Learning Objectives 6.1 Introduction 6.2 Model in Linear Programming 6.3 Related terminology such as constraints 6.4 Manipulating a Linear Programming Problem 6.5 Summary 6.6 Keywords 6.7 Learning Activity 6.8 Unit End Questions 6.9 References 6.0 LEARNING OBJECTIVES After studying this unit, you will be able to: ● Identify the role of mathematical models in operations decision making. ● Understand how to construct the constrained optimization models. ● Describe the advantages and disadvantages of using optimization models. ● Describe the assumptions of linear programming. 6.1 INTRODUCTION Operations Research: Linear programming was created during World War II, when the need for a method to maximise resource efficiency was critical. New war-related projects demanded attention, causing resources to be spread thin. “Programming” was a military word for actions such as efficiently preparing schedules and optimally deploying soldiers. The Simplex technique of optimization was created by George Dantzig, a member of the United States Air Force, in 1947 to give an efficient approach for solving programming problems with linear structures. Experts from a range of domains, particularly mathematics and economics, have since developed and investigated the theory underpinning \"linear programming.\" Assumptions 109 CU IDOL SELF LEARNING MATERIAL (SLM)

Before we get too focused on solving linear programs, it is important to review some theory. For instance, several assumptions are implicit in linear programming problems. These assumptions are: 1. Proportionality The contribution of any variable to the objective function or constraints is proportional to that variable. This implies no dis5 counts or economies to scale. For example, the value of 8x1 is twice the value of 4x1, no more or less. 2. Additivity The contribution of any variable to the objective function or constraints is independent of the values of the other variables. 3. Divisibility Decision variables can be fractions. However, by using a special technique called integer programming, we can bypass this condition. Unfortunately, integer programming is beyond the scope of this paper. 4. Certainty This assumption is also called the deterministic assumption. This means that all parameters (all coefficients in the objective function and the constraints) are known with certainty. Realistically, however, coefficients and parameters are often the result of guess-work and approximation. The effect of changing these numbers can be determined with sensitivity analysis 6.2 MODEL IN LINEAR PROGRAMMING A diagram of a system, theory, or phenomena that accounts for its known or inferred qualities and can be used to investigate its characteristics further. System: A group of items that are functionally connected, particularly: The human body is seen as a physiologically functional unit. An organism in its entirety, particularly in terms of its vital activities or functions. The neurological system and the skeletal system are two examples of physiologically or physically complementary organs or parts. A collection of mechanical or electrical components that interact. A communication, transit, or distribution network made up of structures and channels. A collection of computer software, hardware, and data transmission devices that function together. The study of mathematical models for large organisational systems is known as operations research (OR). Optimization is a subset of OR that employs mathematical approaches such as linear and nonlinear programming to determine optimal values for system variables. Linear Programming: 110 CU IDOL SELF LEARNING MATERIAL (SLM)

A single objective function, which represents either a profit to be maximised or a cost to be minimised, and a set of constraints that limit the decision variables are typically used. The decision variables' objective function and constraints are all linear functions. Software that can solve problems with millions of variables and tens of thousands of constraints has been developed. Network Flow Programming The linear programme is a subset of the more generic linear programme. The transportation problem, the assignment problem, the shortest path problem, the maximum flow problem, and the minimal cost flow problem are among the problems covered. There are extremely efficient algorithms that are many times more efficient than linear programming in terms of computer time and space utilisation. Integer Programming Some of the variables are required to take on discrete values. NP-hard: Most problems of practical size are very difficult or impossible to solve. Nonlinear Programming The objective and/or any constraint is nonlinear. In general, much more difficult to solve than linear. Most (if not all) real world applications require a nonlinear model. In order to be make the problems tractable, we often approximate using linear functions. Models Dynamic Programming A DP model is a representation of a process that includes states, decisions, transitions, and returns. The procedure starts at a point where a decision is taken. A transition to a new state occurs as a result of the decision. A return is realised based on the starting state, ending state, and decision. The process progresses through a series of states until it reaches a final state. The goal is to determine which sequence optimizes the total return. It is possible to handle objectives with very general functional forms, and a global optimal solution is always found. The \"Curse of Dimensionality\" states that the number of states grows exponentially as the problem's dimensions increase. Models Stochastic Processes In many practical situations the attributes of a system randomly change over time. 111 CU IDOL SELF LEARNING MATERIAL (SLM)

Examples include the number of customers in a checkout line, congestion on a highway, the number of items in a warehouse, and the price of a financial security to name a few. The model is described in part by enumerating the states in which the system can be found. The state is like a snapshot of the system at a point in time that describes the attributes of the system. Events occur that change the state of the system. Models Stochastic Processes In many real-world circumstances, a system's characteristics alter at random throughout time. Customers in a checkout line, traffic on a highway, the amount of things in a warehouse, and the price of a financial security are just a few examples. Enumerating the states in which the system can be found is one way of describing the model. The state is a snapshot of the system at a specific point in time that describes the system's characteristics. Events occur that cause the system's state to change. Consider a system with an Automated Teller Machine (ATM). The number of customers at or waiting for the machine is the status. The linear measure of the system's movement is time. Events are arrivals and departures. Models Markov Chains A stochastic process that can be monitored at regular intervals, such as once a day or once a week, can be described by a matrix that specifies the probability of shifting from one state to another in one time interval. The process is known as a Markov Chain if this matrix does not change over time. A range of system metrics that can be used to examine and evaluate a Markov Chain model can be computed using computational approaches. Markov Processes The duration of all state-changing activities is exponentially distributed in a continuous time stochastic process. Time is a constant variable. A matrix depicting the pace of transition from one state to the next completely describes the process. The rates are the parameters of the exponential distributions that they are connected with. The analytical outcomes resemble those of a Markov Chain. Simulation It's not always easy to get a closed form expression for a stochastic system's behaviour. Simulation is a technique for estimating statistical measures of complicated systems that is very generic. The random variables in a system are modelled as though they were known. The variables' values are then picked at random from their known probability distributions. 112 CU IDOL SELF LEARNING MATERIAL (SLM)

The system response is seen once for each replication. One can derive statistics on the findings by simulating a system in this way for many replications and recording the responses. The statistics are used in the evaluation and planning of the project. Time Series and Forecasting A time series is a collection of observations of a random variable that occurs on a regular basis. Typically, they're used to feed into OR decision models. An inventory model, for example, necessitates forecasts of future demand. For example, a university department's course scheduling and staffing model involves projections of future student inflow. For example, projections of river flows for the near future are required in a model for delivering warnings to the population in a river basin. Inventory Theory Inventories are materials that have been stored, are being processed, or are now being processed. When should raw materials be ordered, and how much should be ordered? When should a production order be sent to the factory? What level of safety stock should a retailer keep on hand? In a manufacturing process, how is in-process inventory managed? Reliability Theory Attempts to quantify the likelihood of a system failing. Probability modelling is fundamentally an issue of estimating reliability. In the telecommunications and networking business, this is extremely significant. Operations R: An Overview. 6.3 RELATED TERMINOLOGY SUCH AS CONSTRAINTS A linear program consists of a set of variables, a linear objective function indicating the contribution of each variable to the desired outcome, and a set of linear constraints describing the limits on the values of the variables. The \"answer\" to a linear program is a set of values for the problem variables that results in the best -- largest or smallest -- value of the objective function and yet is consistent with all the constraints. Formulation is the process of translating a real-world problem into a linear program. Once a problem has been formulated as a linear program, a computer program can be used to solve the problem. In this regard, solving a linear program is relatively easy. The hardest part about applying linear programming is formulating the problem and interpreting the solution. Linear function: All of the equations in a linear program must, by definition, be linear. A linear function has the following form: a0 + a1 x1 + a2 x2 + a3 x3 + . . . + an xn = 0 In general, these are called the coefficients of the equation; they are also sometimes called parameters. The important thing to know about the coefficients is that they are fixed 113 CU IDOL SELF LEARNING MATERIAL (SLM)

values, based on the underlying nature of the problem being solved. The x's are called the variables of the equation; they are allowed to take on a range of values within the limits defined by the constraints. Note that it is not necessary to always use x's to represent variables; any label could be used, and more descriptive labels are often more useful. Linear equations and inequalities are often written using summation notation, which makes it possible to write an equation in a much more compact form. The linear equation above, for example, can be written as follows: Decision Variables: In a linear programme, the variables are a collection of values that must be found in order to solve the problem; the problem is solved once the best values for the variables have been established. Because the challenge is deciding what value each variable should take, the variables are sometimes referred to as decision variables. The variables usually describe the amount of a resource to use or the intensity of an activity. One of the most difficult and/or critical tasks in framing a problem as a linear programme is specifying the variables of the problem. Sometimes creative variable definition can be used to dramatically reduce the size of the problem or make an otherwise non-linear problem linear. As mentioned earlier, a variety of symbols, with subscripts and superscripts as needed, can be used to represent the variables of a linear program. As a general rule, it is better to use variable names that help you remember what the variable represents in the real world. For this general introduction, the variables will be represented -- very abstractly -- as X1 , X2 , . . ., Xn . Objective Function: In a linear programming issue, the goal is to maximise or minimise a numerical value. This value could be the expected net present value of a project or a forest property; or it could be the project's cost; it could also be the amount of wood produced, the expected number of visitor-days at a park, the number of endangered species saved, or the amount of a specific type of habitat to be preserved. Linear programming is a very broad approach, and its applications are only limited by human creativity and imagination. The objective function indicates how much each variable contributes to the value to be optimized in the problem. The objective function takes the following general form: where 114 CU IDOL SELF LEARNING MATERIAL (SLM)

ci = the objective function coefficient corresponding to the ith variable, and Xi = the ith decision variable. The coefficients of the objective function indicate the contribution to the value of the objective function of one unit of the corresponding variable. For example, if the objective function is to maximize the present value of a project, and Xi is the ith possible activity in the project, then ci (the objective function coefficient corresponding to Xi ) gives the net present value generated by one unit of activity i. As another example, if the problem is to minimize the cost of achieving some goal, Xi might be the amount of resource i used in achieving the goal. In this case, ci would be the cost of using one unit of resource i. Constraints: Constraints define the possible values the variables of a linear programming problem may take. They typically represent resource constraints, or the minimum or maximum level of some activity. They take the following general form: where Xi = the ith decision variable, aj, i = the coefficient on Xi in constraint j, and bj = the right-hand-side coefficient on constraint j. Note that j is an index that runs from 1 to m, and each value of j corresponds to a constraint. Thus, the above expression represents m constraints (equations, or, more precisely, inequalities) with this form. Resource constraints are a common type of constraint. In a resource constraint, the coefficient aj, i indicates the amount of resource j used for each unit of activity i, as represented by the value of the variable Xi . The right-hand side of the constraint (bj ) indicates the total amount of resource j available for the project. Non-negativity Constraints: Linear programme variables must always have non-negative values for technical reasons (i.e., they must be greater than or equal to zero). This non-negativity requirement will be fair — even necessary — in most circumstances, when the variables represent the levels of a set of activities or the amounts of some resource used. If you really want to let a variable take on a negative value, there are some formulation \"tricks\" you can do. These techniques, however, are outside the scope of this course. In any case, the non-negativity constraints are part of all LP formulations, and you should always include them. They are written as follows: Xi 0 i = 1, 2, . . ., n where 115 CU IDOL SELF LEARNING MATERIAL (SLM)

Xi = the ith decision variable. 6.4 MANIPULATING A LINEAR PROGRAMMING PROBLEM Many linear problems do not follow the canonical form described in the introduction at first, which is crucial when considering the Simplex algorithm. Inequalities may be used as constraints, variables may not have a non-negative constraint, or the problem may desire to maximise rather than minimise z. Now we'll look at how to transform problems into the proper shape. Inequalities in Constraints We begin by addressing the problem of converting all constraints in a linear programming problem to stringent equalities. We eliminate this concern by adding new variables to the problem that indicate the difference between the left and right sides of the restrictions. Inequalities are transformed into equalities by subtracting a slack variable from a \"greater than or equal to\" constraint or by adding an excess variable to a \"less than or equal to\" constraint. For example, the constraint 4x1 + x2 ≤ 3 becomes 4x1 + x2 + e1 = 3 with the addition of e1 ≥ 0. If the constraint were originally 4x1 + x2 ≥ 3, the additional surplus variable s1 must be subtracted (4x1 + x2 − s1 = 3) so that s1 can be a strictly nonnegative variable. Linear Program: We can reduce the structure that characterizes linear programming problems into the following form: Minimize c1x1 + c2x2 + · · · + cnxn = z Subject to a11x1 + a12x2 + · · · + a1nxn = b1 a21x1 + a22x2 + · · · + a2nxn = b2 ............... am1x1 + am2x2 + · · · + amnxn = bm x1, x2, . . . , xn ≥ 0. In linear programming z, the expression being optimized is called the objective function. The variables x1, x2 . . . xn are called decision variables, and their values are subject to m + 1 constraints (every line ending with a bi , plus the non-negativity constraint). A set of x1, x2 . . . xn satisfying all the constraints is called a feasible point and the set of all such points is called the feasible region. The solution of the linear program must be a point (x1, x2, . . . , xn) in the feasible region, or else not all the constraints would be satisfied. The following example from Chapter of Winston illustrates that geometrically interpreting the feasible region is a useful tool for solving linear programming problems with two decision variables. 116 CU IDOL SELF LEARNING MATERIAL (SLM)

The linear program is: Minimize 4x1 + x2 = z Subject to 3x1 + x2 ≥ 10 x1 + x2 ≥ 5 x1 ≥ 3 and x1, x2 ≥ 0. We plotted the system of inequalities as the shaded region in Figure 1. Since all of the constraints are “greater than or equal to” constraints, the shaded region above all three lines is the feasible region. The solution to this linear program must lie within the shaded region. Recall that the solution is a point (x1, x2) such that the value of z is the smallest it can be, while still lying in the feasible region. Since z = 4x1 + x2, plotting the line x1 = (z − x2)/4 for various values of z results in isocost lines, which have the same slope. Along these lines, the value of z is constant. In below Figure, the dotted lines represent isocost lines for different values of z. Since isocost lines are parallel to each other, the thick dotted isocost line for which z = 14 is clearly the line that intersects the feasible region at the smallest possible value for z. Therefore, z = 14 is the smallest possible value of z given 4 the constraints. This value occurs at the intersection of the lines x1 = 3 and x1 + x2 = 5, where x1 = 3 and x2 = 2. 117 CU IDOL SELF LEARNING MATERIAL (SLM)

6.5 SUMMARY ● Constraints are limitations or restrictions placed on the decision factors. ● The decision variables in all linear programmes should always be non-negative. This means that decision variables should have values that are larger than or equal to 0. ● A linear programming problem is one in which we have to find optimal value (maximum or minimum) of a linear function of several variables (called objective function) subject to certain conditions that the variables are non-negative and satisfying by a set of linear inequalities with variables, are sometimes called division variables. ● The common region determined by all the constraints including non-negative constraints x,y>0 of a linear programming problem is called the feasible region for the problem. The region other than the feasible region is called an infeasible region. The feasible region is always a convex polygon. ● Points within and on the boundary of the feasible region represent feasible solutions of the constraints. Any point outside the feasible region is called an infeasible solution. ● Any point in the feasible region that gives the optimal value of the objective function is called the optimal feasible solution. ● A feasible region of a system of linear inequalities is said to be bounded, if it can be enclosed within a circle. Otherwise, it is called unbounded. 6.6 KEYWORDS • Objective function: The objective function is a function in the LPP which is to be optimized. • Constraints: The linear inequalities or equations or restrictions on the variables of a linear programming problem are called constraints. • Isocost line : An isocost line is a curve which shows various combinations of inputs that cost the same total amount • Feasible solution: A feasible solution to a linear program is a solution that satisfies all constraints. • Feasible region: The feasible region in a linear program is the set of all possible feasible solutions 118 CU IDOL SELF LEARNING MATERIAL (SLM)

6.7 LEARNING ACTIVITY 1. What are the three components of LPP? ___________________________________________________________________________ _____________________________________________________________________ 2. How do you identify constraints in linear programming? ___________________________________________________________________________ _____________________________________________________________________ 6.8 UNIT END QUESTIONS A. Descriptive Questions Short Questions: 1. What are the constraints in an LPP? 2. Why is it important for an objective and its constraints to be linear? 3. What do you mean by the objective function and constraints in linear programming? 4. What are the objectives of linear programming problems? 5. What are your constraints? Long Questions: 1. Explain the linear programming with examples. 2. Write brief notes about the importance of linear programming. 3. Explain the characteristics of LPP. 4. Explain the LPP and its limitations. 5. Explain the role of LPP in project constraints with examples. B. Multiple Choice Questions 1. The objective of linear programming for an objective function is to a. maximize or minimize b. Subset or proper set modelling c. Row or column modelling d. Adjacent modelling 2. For a linear programming equation, the convex set of equations is included in the region a. Feasible solutions 119 CU IDOL SELF LEARNING MATERIAL (SLM)

b. Diposed solutions c. Profit solutions d. Loss solutions 3. The linear programming used to optimize mathematical procedure and is a. Subset of mathematical programming b. dimension of mathematical programming c. linear mathematical programming d. All of these 4. In linear programming, the objective function and objective constraints are a. Solved b. Linear c. Quadratic d. Adjacent 5. A set of values of decision variables which satisfies the linear constraints and nn- negativity conditions of a L.P.P. is called its a. Unbounded solution b. Optimum solution c. Feasible solution d. None of these Answers 1-a, 2-a, 3-a. 4-b, 5-c 6.9 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. 120 CU IDOL SELF LEARNING MATERIAL (SLM)

● 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. ● Hillier and Libeberman, “Operations Research”, Holden Day, 1986 121 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT - 7: LINEAR PROGRAMMING 2 STRUCTURE 7.0 Learning Objectives 7.1 Introduction 7.2 Objective function 7.3 Optimization 7.4 Summary 7.5 Keywords 7.6 Learning Activity 7.7 Unit End Questions 7.8 References 7.0 LEARNING OBJECTIVES After studying this unit, you will be able to: ● Describe the fundamentals of linear programming, as well as its benefits and drawbacks. ● Examine the findings, paying special attention to sensitivity and the diagnosis of uncommon events. ● Describe an optimization study from conception to conclusion, including the creation of a formal report. 7.1 INTRODUCTION In mathematics, a linear programming problem is a system for determining the maximum or lowest value of any variable in a function; it is also known as an optimization problem. LPP aids in the development and solution of a decision-making problem using mathematical methods. The problem is usually expressed as a linear function that must be optimised while adhering to a set of restrictions. The most common application of LPP is in counselling management on how to make the most efficient and effective use of limited resources. In mathematical terms, the problem above can be written as: Maximize F(X1, X2, …, Xn)Such that it meets the constraints C1, C2, …, Cm This type of formulation is called optimization or mathematical programming. 122 CU IDOL SELF LEARNING MATERIAL (SLM)

There is an objective function to be maximized (i.e. profit) or minimized (i.e. cost, loss, risk of some undesirable event, etc.) X’s are the decision variables. They are the things we can adjust. For example, each X can be a driver. Xi=1 means the driver i is selected and will be sent to the customer. Xi=0 means he is not selected. C’s are the constraints. For instance, each car has a distance from potential customers. Drivers can drive only for so many hours a day. Each road has a speed limit and each car has a maximum number of passengers it can take. This is the most common example of Operations Research. Most of the problems in OR fall into one of the three problem categories. 1. Optimization ● Mathematical programming: We choose decision variables (drivers to dispatch), an objective function (maximising profit), and a set of constraints (physical, technological, economic, environmental, legal, societal, etc.) similar to the Uber example above. Then we use mathematics to solve them. ● Numerical optimization: There are two types of numerical optimization: gradient- based and non-gradient-based. One of the most prominent optimization methods in Machine Learning is the Gradient Descent, which is a gradient-based (as the name suggests) optimization. Non-gradient algorithms (derivative-free optimization) include Bayesian optimization, Cuckoo search, Genetic algorithms, and many others. ● Non-gradient algorithms are used when the objective function is not smooth, or a closed form of the objective function is not available. Optimization and Machine Learning are inextricably linked. Many machine learning tasks are expressed as the minimising of a loss function. The optimization algorithm minimises the loss on the training set during training. However, the ultimate purpose of machine learning is to reduce the amount of data that is lost. As a result, Machine Learning is a problem of optimization with the goal of \"generalisation.\" 2. Probabilistic Modeling: A probabilistic model generates a probability distribution, while a deterministic model generates a single probable event outcome. 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 123 CU IDOL SELF LEARNING MATERIAL (SLM)

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) ● 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. 124 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? ● 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? 125 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 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. 126 CU IDOL SELF LEARNING MATERIAL (SLM)

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. 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. 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. 127 CU IDOL SELF LEARNING MATERIAL (SLM)

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. ● 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). 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. 128 CU IDOL SELF LEARNING MATERIAL (SLM)

• 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? ___________________________________________________________________________ _____________________________________________________________________ 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 129 CU IDOL SELF LEARNING MATERIAL (SLM)

a. The objective functions b. Some the given constraints c. All of the given constraints 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 5. What is a constraint? a. Response b. Parameter c. Limitation d. Principle Answers 1-c, 2-c, 3-b. 4-d, 5-c 130 CU IDOL SELF LEARNING MATERIAL (SLM)

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. ● Philip D.T. and Ravindran A., “Operations Research”, John Wiley, 1992. ● Hillier and Libeberman, “Operations Research”, Holden Day, 1986. 131 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. ● 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 132 CU IDOL SELF LEARNING MATERIAL (SLM)

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. 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. ● 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. 133 CU IDOL SELF LEARNING MATERIAL (SLM)

● 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. 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 134 CU IDOL SELF LEARNING MATERIAL (SLM)

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 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 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 135 CU IDOL SELF LEARNING MATERIAL (SLM)

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. 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) 136 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, 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. 137 CU IDOL SELF LEARNING MATERIAL (SLM)

4. The non-negativity conditions are X ≥ 0, Y ≥ 0 Therefore the mathematical formulation of the LPP is: Minimize: C = 60X + 80Y Subject to: 3X + 4Y ≥ 8 5X + 2Y ≥ 11 and X ≥ 0 , Y ≥ 0 Example 3: Solution: 138 CU IDOL SELF LEARNING MATERIAL (SLM)

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

Example 5: Solution: 140 CU IDOL SELF LEARNING MATERIAL (SLM)

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

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

Solution: 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. 143 CU IDOL SELF LEARNING MATERIAL (SLM)

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. • 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. ___________________________________________________________________________ _______________________________________________________________ 3. Write the general form of LPP. ___________________________________________________________________________ _____________________________________________________________________ 144 CU IDOL SELF LEARNING MATERIAL (SLM)

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 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 145 CU IDOL SELF LEARNING MATERIAL (SLM)

profit. Find the best combination of tables and chairs to manufacture in order to reach the maximum profit. 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. 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 146 CU IDOL SELF LEARNING MATERIAL (SLM)

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 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. ● Hillier and Libeberman, “Operations Research”, Holden Day, 1986. 147 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. ● 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 148 CU IDOL SELF LEARNING MATERIAL (SLM)

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. 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 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. 149 CU IDOL SELF LEARNING MATERIAL (SLM)

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: Example 2: 150 CU IDOL SELF LEARNING MATERIAL (SLM)