SLM_(1)

nPr = n (n – 1) (n – 2) .................. (n – r + 1) Corollary 1 The number of permutations of n different things taken all at a time is: n (n – 1) (n ––2) .................... ...3, 2, 1 The notation that is used for denoting this product of the first n natural number is n! or n and it is read as ‘factorial n’. Corollary 2: n! P= n r (n r)! CU IDOL SELF LEARNING MATERIAL (SLM)

120 Business Mathematics and Statistics ? nPr = n(n – 1) (n – 2) .............. (n – r + 1) n(n 1)(n 2)..........(n r 1)(n r)! = (n r)! n! = (n r)! Properties The number of n-permutations with k disjoint cycles is the signless Stirling number of the first kind, denoted by c(n, k). Permutation Type The cycles of a permutation partition the set Sn so the lengths of the cycles of a permutation V form a partition of n called the cycle type of V. There is a “1” in the cycle type for every fixed point of V, a “2” for every transposition, and so on. The cycle type of E = (125)(34)(68)(7) is (3,2,2,1) which is sometimes written in a more compact form as [112231]. The general form is [1D1 2D2…nDn], where a1, …an are the numbers of cycles of respective length. The number of permutations of a certain type is n! 1B1 2B 2 nBn B !B ! B ! 12 n

Conjugating Permutations In general, composing permutations written in cycle notation follows no easily described pattern – the cycles of the composition can be different from those being composed. However, the cycle structure is preserved in the special case of conjugating a permutation V by another permutation S, which means forming the product SVS–1. Here, SVS–1 is the conjugate of V and its cycle notation can be obtained by taking the cycle notation for V and applying S to all the entries in it. It follows that two permutations are conjugate exactly when they have the same type. Permutation order The order of a permutation is the smallest positive integer m so that Vm = id. It is the least . common multiple of its cycles lengths. For example, the order of (1 3 2) (4 5) is 2 3 = 6. CU IDOL SELF LEARNING MATERIAL (SLM)

Permutations and Combinations 121 Parity of a permutation Every permutation of a finite set can be expressed as the product of transpositions. Although many such expressions for a given permutation may exist, either they all contain an even or an odd number of transpositions. Thus, all permutations can be classified as even or odd depending on this number. This result can be extended so as to assign a sign, written sgn V, to each permutation, sgn V if V is even sgn V= –1and if V is odd. Then for two permutations V and S sgn VVSsgn V . sgn S. 6.2 Combinations The selections that can be made from a given number of things, by taking some or all those things without reference to the order of those things, is known as ‘combinations’. Here the difference between a selection and an arrangement should be carefully noted. An arrangement takes into consideration the order of the things, whereas a selection ignores such order and considers only the things taken. For example, AB and BA are two permutations of the letters A and B, whereas AB or· BA stands for one combination (selection) of the two letters A and B. In short, combinations refer to the number of things each selection contains whereas permutations refer to the order of those things. For instance, AB, BC, CA are three different combinations of the three letters A, Band C, but AB, BA, BC, CB, CA and AC are the six different permutations of the letters A, B, C. To show that the number of combinations of n different things taken r at a time is n(n 1)(n 2)..........(n r 1)

r! Let the number of combinations of n different things taken r at a time be denoted by nCr. Since each combination consists of r different things, each combination gives rise to r permutations. That is, the number of permutations of r different things in each combination would be r!. Therefore, the total number of permutations from nCr combinations would be r!(nCr). But we know that the number of permutations of n different things taken r at a time is n (n – 1) (n – 2) (n – r + 1) CU IDOL SELF LEARNING MATERIAL (SLM)

122 Business Mathematics and Statistics ? r! (nCr) = n (n – 1) (n – 2) ................... (n – r + 1) C= n(n 1)(n 2)..........(n r 1) r! nr We can also express nCr as under: n! C= n r (n r)! ? C = n(n 1)(n 2)..........(n r 1)(n r) nr r!(n r)! n! = r!(n r)! Corollary 1: nCr = 1 This is because n things can be selected out of n different things in one ,way only. Corollary 2: C= C n r n n–r R.H.S. = L.H.S. =

= n! C= n r r!(n r)! ? nCr = n! nCn–r = (n n r)!(n r) n! n!(n r)! n! (n r)!(n (n r)! Properties of nCr Each of the different groups of selections, which can be made by taking some or all of a number of given things or objects at a time is called a combination. In combination, order of appearance of things is not taken into account. CU IDOL SELF LEARNING MATERIAL (SLM)

Permutations and Combinations 123 Example: Three groups can be made with three different objects a, b, c taking two at a time, i.e., ab, bc, ac. Here, ab and ba are the same group. It is also clear that for each combination (selection or group) of two things, number of permutations (arrangements) is 2!. For example, for combination ab there are two permutations, i.e., ab and ba. Number of combinations of n different things taking r at a time (n t r): n! nCr = r!(n r)! Proof: Let the number of combinations of n different things taken r at time be nCr. Now, each combination consists of r different things and these r things can be arranged among themselves in r! ways. … (1) Thus, for one combination, number of arrangements is r! nCr … (2) But number of permutations of n different things taken r at a times is nPr From (1) and (2) we get n! Pro perti r! nC = nP = es of r r (n r)! nCr: n! = nP = r r!(n r)!

1. nC = nC . r n-r n! Proof: nC = r r!(n r)! n! nCn-r = (n r)!(n (n r)! n! nCr = (n r)!(r)! … (1) … (2) CU IDOL SELF LEARNING MATERIAL (SLM)

124 Business Mathematics and Statistics From equation (1) and (2) … (1) n! nCn-r = (n r)!(r)! = nCr Hence proved nCr = nCn-r. 2. nC = nC , then either x = y or x + y = n. xy Proof: nCx = nCy = nCn–y ( ' nCr = nCn–r) From (1) x=y x = n – y (or) x + y = n. 6.3 Interpretation of O! nCn = 1, from Cor. 1 n! But nCn = n!o! by putting r = n in the formula of nCr n! n!o! = 1 1

i.e., o! = 1, and this equality would be meaningless unless O! = 1 Therefore, we define o! as .unity. Similarly by putting r = 0 in the formula for nCr, we get n! C = =1 n n n!o! 6.4 Distribution in Groups The number of different ways in which p + q things can be divided into two separate groups, i.e., one group containing p things and the other containing q things, is: (p q)! p!q! CU IDOL SELF LEARNING MATERIAL (SLM)

Permutations and Combinations 125 Note the following: (1) If P = q, we get two equal groups and in this case the number of different ways of sub- division would be: (2p)! p! p! 2! In this formula we regard as different the possible orders in which 2 groups can occur in any single mode of division; and since there are 2! such orders, we get the formula as: (2p)! p! p! 2! (2) If 2q things are to be distributed equally between two men, then the number of ways of distribution would be: (2p)! [(p)!]2 Applications of Permutation and Combination (add this before 6.5) Functional Applications (i) The number of all permutations (arrangements) of n different objects taken r at a time,

1. When a particular object is to be always included in each arrangement is n-1Cr-1î r! 2. When a particular object is never taken in each arrangement is n-1CrîU (ii) If the sets A has m elements and B has n elements, then 1. The number of functions from A to B is nm. 2. The number of one-one functions from A to B is nPm, m d n. 3. The number of onto functions from A to B is nm –  ¬ ¬ žn­ m žn­ m mbn ž ­(n 1) ž ­ (n 2) ž- ž- Ÿ1 ® Ÿ 2® ¬ žn­ .m d n.4. The number of increasing (decreasing) functions from A to B is žž -­ Ÿm® CU IDOL SELF LEARNING MATERIAL (SLM)

126 Business Mathematics and Statistics 5. The number of non-decreasing (non-increasing) functions from A to B is ž m n 1¬- ž -¸ m d n. ž- Ÿm® 6. The number of bijections from A to B is n! if m = n. 7. The number of bijections from A to A such that f(x) = x “x e A is m! 111 (1)m ¯ ¡ 3! 4! ° ¡ °. ¡ 2! m! ° ¢± Example: Let A = {x1, x2, x3, x4, x5}, B = {y1, y2, y3, y4, y5}. Then, the number of one- one mappings, from A to B such that f(xi) = yi, i = 1, 2, …5 is Interpret: Here, we use the formula, the number of bijections from A to A such that f(x) = x 11 1 (1)m ¯ ¡° e A is ¡ ° ¡2! 3! 4! m! ° ¢±  1 ¬ ž1 1 Here required number of ways = 1­ 5!ž ž ­ ­ Ÿ 2! 3! 4! 5!® ¬ ž1 1 1 1 ­ = ­ 120ž ž ­ 2 6 24

Ÿ 120®  60205 1¬ =ž - 44. 120 ž - ž Ÿ - 120 ® Geometrical Applications:  Out of n non-concurrent and non-parallel straight lines the number of point of intersection  DUHnC‚ .    The number of straight lines passing through n points = nC‚ .  The number of straight lines passing through n points out of which m are collinear  nC‚ ±mC‚ + 1.  In a polygon, the total number of diagonals out of n points (no three points  are collinear) nC‚ – n = n(n-3)/ 2.  Number of triangles formed by joining n points is nC3. CU IDOL SELF LEARNING MATERIAL (SLM)

Permutations and Combinations 127   Number of triangles formed by joining n points out of which m are collinear are nCƒ – mC3.   The number of parallelogram in two systems of parallel lines (when 1st set contains in parallel lines and 2nd set contains n parallel lines) = nC2 × mC2. n  The number of rectangles of any size in a square of n × n is œr3 and number of squares r1 n of any size is œn2 . r1 6.5 Illustrative Examples Example 1: How many different numbers can be formed by taking 3 digits at a ti me out of 5 digits. 2, 4, 6, 8, 9 Using the formula: nPr = n (n – 1) (n – 2) ............... (n – r + 1) and putting n = 5, r = 3, we get 5P3 = 5(5 – 1)(5 – 2)

5×4×3 60 ª 60 different numbers can be formed. Example 2: Find the number of permutations of letters taken all at a time, that can be formed out of the word ‘watching’. How many of these permutations begin with Ow’ and end with ‘g’? Since there are 8 letters in the word ‘watching’, it is clear that there are 8! Permutations. If the letters ‘w’ and ‘g’ occupy fixed places then the number of permutations would be 6! Example 3: Find the number of different ways in which 5 students and 3 teachers can be arranged for a photograph (standing in a row) such that no two teachers stand together. CU IDOL SELF LEARNING MATERIAL (SLM)

128 Business Mathematics and Statistics All the 5 students can be arranged in 5! ways, that is, 5 × 4 × 3 × 2 × 1 = 120 ways. As there are six places between these 5 students, it follows that these places can be occupied by the 3 teachers in 6P3 ways, that is 120 ways. Therefore the total number of arrangements would be: 120 × 120 = 14400 Example 4: If 3(nP4) = 4(n–1P4) find n. 3n (n – 1) (n – 2) (n – 3) 4 (n – 1) (n – 2) (n – 3) (n – 4) (iv) 3n = 4 (n – 4) n = 16 Example 5: Find n, if nC5 = 2(nP4) n(n 1)(n 2)(n 3)(n 4) Now C = 54321 n5 and 2(nP4) = 2n(n – 1) (n – 2)(n – 3) n(n 1)(n 2)(n 3)(n 4) = 120 2n(n – 1) (n – 2) (n – 3) (iii) n – 4 = 2(120) = 240 = n = 244

Example 6: If nC5 = 8(nC4), find n n(n 1)(n 2)(n 3) Now nC5 = 120 8n(n 1)(n 2)(n 3) and 8(nC4) = 4  3  2 1 n(n 1) (n 2) (n 3) (n 4) Given, 5  4  3  2 1 8n(n 1) (n 2) (n 3) = 4321 = [n – nP5] = 4[nP5] n4 ? 5 =8 CU IDOL SELF LEARNING MATERIAL (SLM)

Permutations and Combinations 129 i.e., n – 4 = 40 ? n = 44 198 C 2x 5 C 5 , find x Example 7: If x 3 = C Now = 2x 5 C x3 2x(2x 1) (2x 2) (2x 3) (2x 4) = 5  4  3  2 1 x(x 1)(x 2) = 321 2x(2x 1) (2x 2) (2x 3) (2x 4) « 5  4  x(x 1)(x 2) 2  2  2  x(x 1) (x 2) 2x 1) (2x 3) 5  4  x(x 1) (x 2) 22x 1) (2x 3) = 5 = 22x 1) (2x 3) 198

55 22 i.e., 5 (2x – 1) (2x – 3) = 5 × 99 ? (2x – 1) (2x – 3) = 99 i.e., 4x2 – 8x + 3 = 99 i.e., 4x2 – 8x – 96 =0 i.e., x2 – 2x – 24 =0 i.e., (x = 6) (x + 4) = 0 ? x =6 CU IDOL SELF LEARNING MATERIAL (SLM)

130 Business Mathematics and Statistics 6.6 Summary At the outset, we understand the meaning, definitions and theorems related to permutations and combinations. Also, we find the interpretations of O! nCo, nCn and solve simple examples, given in the illustrative examples. also descriptive questions are tackled. 6.7 Key Words/Abbreviations nPr, n!, O!, nPn, nCr, nCo, nCn nCr = nCn–r, nCr + nCr–1 = n+1Cr 6.8 Learning Activity Work out examples at the end from Examples: ................................................................................................................................................. ................................................................................................................................................. 6.9 Unit End Questions (Short Answer Type and Descriptive) A. Short Answer Type Questions

1. Find the values of: (i) 9P4 (ii) 18P6 (iii) 16C5 (iv) 22C8 [Ans: (i) 3024 (ii) 13366080 (iii) 4368 (iv) 319770] 2. Find the number of permutations that can be made out of the letters of the word ‘Republican’. [Ans: 10 ] ? Find the number of combinations of 8 different things, taking 5 at a time. [Ans: 56] ? How many different arrangements can be made by taking 5 letters of the word ‘DEMOCRAT’? [Ans: 6720] 5. In how many ways can a team of eleven be chosen out of 14 players? [Ans: 364] 6. Find the number of ways a party of 5 can be chosen out of 12 persons. [Ans: 792] CU IDOL SELF LEARNING MATERIAL (SLM)

Permutations and Combinations 131 B. Descriptive Type Questions (ii) If each selection is to contain four books, find the number of selections that can be made from 10 different books when: = One specified book is always included (ii) One specified book is always excluded. [Ans: (i) 9C3 (ii) 9C4] 2. In how many ways can a committee consisting of 7 students and 3 teachers be formed from 12 students and 5 teachers? [Ans: 12C7 × 5C3] = From a committee consisting of a principal, a professor and 15 students a sub-committee of 7 persons is to be set up. Find the number of ways this can be done so as to include always the principal add the professor. [Ans: 15C5] 9! (iii) In how many ways can 9 things be divided equally among 3 persons. [Ans: (3!)3 ] (iv) Prove that nCr + nCr–1 = n+1Cr. (v) Find the number of ways in which 8 different examination papers can be arranged so that the best and the worst papers never come one after another. [Ans: 8! – 2 (7!)] = Prove that n+2Cr = nCr + 2nCr–1 + nCr–2 = There are twenty stations on a certain Rail way. What is the number of different kinds of single third class tickets to be printed if it should be possible to book a passenger from anyone station to any other? [Ans: 380]

= A group consists of four senior officers and six junior officers. Find the number of committees that can be set up if each committee should consist of three senior officers and four junior officers. [Ans: 60] 10. What is the number of ways of arranging n persons in a line so that two particular persons shall not be together? [Ans: (n – 2) n – 1] 11. How many numbers can be formed out of the digits 4, 5, 6, 9? How many of these numbers lie between 4000 and 6000? [Ans: 24, 12] z In how many ways can ten students be selected from a class of 100? In how many ways of these could two particular students be always included? 100! 98! [Ans: ,] 10!90! 8!90! CU IDOL SELF LEARNING MATERIAL (SLM)

132 Business Mathematics and Statistics 4. Farmers A, Band C together own 4 carts and 6 bullocks. If each cart requires one bullock only, find the number of different ways they can drive, each in a separate cart, to the town. [Ans: 2880] z Eight examination papers are to be set up in a certain order that is not to be divulged. It was discovered that this order was leaked out. In how many ways can the order be changed? [Ans: 40320] 6.10 References References of this unit have been given at the end of the book. ˆˆˆ

CU IDOL SELF LEARNING MATERIAL (SLM)

Linear Programming 133 UNIT 7 LINEAR PROGRAMMING Structure 7.0 Learning Objectives 7.1 Introduction 7.2 The Graphic Method 7.3 Simplex Method: Terminology and Procedure of Solving 7.4 Summary 7.5 Key Words/Abbreviations 7.6 Learning Activity 7.7 Unit End Questions (MCQ and Descriptive)

7.8 References 7.0 Learning Objectives After studying this unit, you will be able to:  Explain the meaning of Linear Programming (LP), requirements and the method of formulation of an LP and the steps.   Describe with reference to a given L.P.P. procedure.   Elaborate the graphic method of solving an L.P.P.   Learn the Simplex Method, terminology and procedure of solving   Explain ‘Duality’. CU IDOL SELF LEARNING MATERIAL (SLM)

134 Business Mathematics and Statistics 7.1 Introduction Managers with decision making authority, whether in business activities or commercial enterprises, will have to take the best possible decision from amongst a number of alternative possibilities. Such decisions may be taken with the main objective of maximizing profits, minimizing costs or reducing wastage, by making the efficient use of all the available resources. The allocation of resources amongst a number of activities in the best possible manner necessitates quantitative support through Operations Research. The subject of Operations Research is concerned with the analysis, condensation and presentation of data for the process of decision making. 7.1.1 Meaning Linear Programming is one of the mathematical techniques which is fundamental to Operations Research. This technique involves the optimization of a function which is called the “Objective Function”. This function is subject to a definite number of constraints. Linear Programming facilitates the selection of the best alternative from among the entire set of feasible alternatives. 7.1.2 Requirement Linear Programming is subject to the following requirements: z The objective Function should be quantitatively well-defined and identifiable. For example, the function can be relating to maximization of profits, minimization of losses, etc. z The activities and the resources should be quantifiable and distinctly identifiable. z The relationships between the Objective Function and the constraint inequalities should all be ‘linear’.

7.1.3 Formulation of l.P.P. Problem 1: (Formation of an L.P. Problem) An Engineering Company can manufacture two different producs P1 and P2, which have to pass through two machines E1 and E2. The details relating to the time required to process the products, the profit per unit and the available capacity of each machine are given in the following table: CU IDOL SELF LEARNING MATERIAL (SLM)

Linear Programming 135 Product Processing Time/Unit Profit/Unit Machine E1 Machine E2 P1 3 1 5 P2 2 1 4 Available hrs. per week 50 22 In order to maximize profit, a decision has to be taken as to how many units of P1 and P2 should be manufactured. For this purpose, we suppose as under: Let x1, x2 be the number of unis of P1 and P2 respectively to be manufactured. Here we call x1 and x2 as decision variables. The objective function and the constraints (in equalities) are formulated as: To maximise Profit Z=5×1+4×2 Subject to 3 × 1 + 2 × 2 d 50 x1 + x2 0 22 x1, x2 > 0 7.1.4 Steps For the formulation of an L.P. problem, the following steps need to be followed: 8. We identify the decision variables in the given problem and denote them by x1 and x2 9. We express the objective function in terms of the decision variables. The objective function is a linear function with the objective of either to maximize or minimize as the case may be.

10. We identify the limiting conditions and express them as inequalities in terms of the decision variables. 11. The decision variables cannot take negative values. Hence they must carry a value greater than or equal to zero. 4. The L.P. problem gets formulated when we express the objective function and the inequalities (constraints) as explained in the earlier steps. CU IDOL SELF LEARNING MATERIAL (SLM)

136 Business Mathematics and Statistics 7.1.5 Problem 2L A company produces three types of parts for automatic washing machines. It produces castings of the parts from a local foundary and then finishes the parts on drilling, shapping and polishing machines The selling prices of parts A , B and C are ` 8, ` 10 and ` 14 respectively. All parts made can be sold. Castings for parts A, B and C cost ` 5, ` 6 and ` 10 respectively. The company possesses only one of each type of machine. Costs per hour to run each of the three machines are z 20 for drilling. ` 30 for shaping and ` 30 for polishing. The capacities (parts for hour) for each part on individual machines are shown in the following table: Capacity per Hour Machine Part A Part B Part C Drilling 25 40 25 Shaping 25 20 20 Polishing 40 30 40 The manager of the company wants to know how many parts of each type to produce per hour in order to maximize profit for an hour’s run. Formulae the above as a linear programming problem. [M.B.A., Delhi] Solution: Suppose x1, x2 and x3 denote the number of units of parts A , B and C respectively, to be produced per hour. The hourly profit can be stated as Profit = (8 – 5)x1 – (20/25 + 30/25 + 30/40)x1

(10 – 6)x2 – (20/40 + 30/20 + 30/30)x2 (14 – 10)x3 – (20/25 + 30/20 + 30/40)x3 8. 0.25x1 + x2 + 0.95x3 Therefore the objective function would be a function of profit, denoted by Z. The L.P. problem here would be: Maximize 0.25x1 + x2 + 0.95x3 Subject to the constraints: x1/25 + x2/40 + x3/25 d 1 x1/25 + x2/20 + x3/20 d 1 x1/40 + x2/30 + x3/40 d 1 and x1 , x2 , x3 t 0 CU IDOL SELF LEARNING MATERIAL (SLM)

Linear Programming 137 7.2 The Graphic Method Linear Programming problems can be solved by using one of the following methods: \\emdash The Graphic Method \\emdash The Simple Method The Graphic Method can be used when the problem involves two variables. According to this method, at the outset, it is necessary to identify the problem involving the decision variables and the Objective Function along with the constraints. Based on these, a graph can be drawn so as to identify the feasible region. The optimal solutions can be obtained by finding the point within the feasible region which optimizes the Objective Function. Problem 3 explains the Graphic Method in dealing with a problem of maximization. The procedure of interpretation has also been explained. Problem 3: Using the Graphical Method for the solution of L.P. problems, calculate the value of x1 and x2, which would maximize P, where P = 6x1 + 7x2 Subject to, 2x1 + 3x2 d 12 2x1 + x2 d 8 x1 , x2 t 0 Solution:

Here, P = 6x1 + 7x2 is the Objective Function, which is subject to the following constraints; 2x1 + 3x2 d 12 … (1) 2x1 + x2 d 8 … (2) when x2 = 0, then value of x1 in the equation (1) becomes 2x1 + 0 = 12 x1 = 6 and when x1 = 0, then value of x2 in the equation (1) becomes 0 + 3x2 = 12 3x2 = 12 x 2=4 ? equation (1) passes through the points (6,0) and (0,4) CU IDOL SELF LEARNING MATERIAL (SLM)

138 Business Mathematics and Statistics Similarly, when x2 = 0, then value of x1 in the equation (2) becomes 2x1 + 0 = 8 x1 = 4 and when x1 = 0, then value of x2 in the equation (2) becomes 0 + x2 = 8 x2 = 8 = equation (2) passes through the points (4,0) and (0,8) Again, we know that x1 and x2 t 0 So we plot these two equations on a graph (see page 114) 8 2x1 + x2 8 7 x 26 5

4 C (0,4) 3 (3,2) 2 2x1 + 3x2 12 1 A (4,0) 0 1234 5 6 (0,0) x1 Fig. 7.1 CU IDOL SELF LEARNING MATERIAL (SLM)

Linear Programming 139 The values of x1 and x2 lie in the shaded portion shown in the graph. Thus, the values of x1 and x2 lie in the region bounded by the points OABC. The co-ordinates of these points are given below: O = (0,0) A = (4,0) B = (3,2) C = (0,4) Within the shaded region, there can be many different values of x1 and x2. We have to maximize the linear programming problem. So we need to find those values of x1 and x2 which maximize the value of P in the following equation P = 6x1 + 7x2 First, substitute the co-ordinates of the point O (0, 0), then P=0 Then, substitute the point A (4, 0) in the equation F P = 6x4 + 7x0 P= 24 Now substitute B (3,2) then value of P becomes

P = 6x3 + 7x2 P= 18+14 P= 32 Substituting C(0, 4), the value of P becomes P = 0 + 7x4 P= 28 From all the above calculations we see that the maximum value of P is 32 at the point B (3,2). So values of x1 and x2 are x1 = 3 and x2 = 2 Putting these values we get the maximum value of P = 6x1 + 7x2 4 Maximum P = 32 CU IDOL SELF LEARNING MATERIAL (SLM)

140 Business Mathematics and Statistics 7.3 Simplex Method: Terminology and Procedure of Solving 7. Simplex Method: It is a systematic procedure (an algorithm) for solving L.P. problems. 8. Basis: A set of variables that are in the solution (have positive non-zero values) and are listed in the solution column. These variables are also known as basic. 9. Slack Variable: It is a variable that is added to an inequality constraint, i.e., “less than or equal to” so as to convert the constraint into an equality. The value of this variable denotes the amount of unused resources. 10. Iteration: This stands for a sequence of steps leading from one basic feasible solution. It is an interactive procedure that repeats the same steps again and again. 11. Simplex Table: It is a table that is used for keeping tack of the calculations made at each iteration of the simplex procedure. 12. Cj: It is the row in the simplex table that contains the coefficients of the variables in the objective function, Here the subscript j refers to the column number in the Simplex Table. 13. Zj Row: A row in the Simplex Table the elements of which represent the decrease in the value of the objective function. (It represents the contribution loss per unit) if one writ of jth variable is brought into the solution. 14. Zj – Cj is the row that is called the Index row or net evaluation row. It contains the net profit or loss as a result of introducing one unit of the variable indicated in that column of the solution (jth variable). Positive values of Zj – Cj represent loss and negative values indicate gain by the introduction of jth variable in the solution. 15. ‘Pivot or Key Column: It is the column with the largest negative number in the Zj – Cj row (or the column with the largest positive number in the Cj – Zj row) of a maximization

problem. It is the column with the largest positive number in the Zj – Cj row (or the column with the largest negative number in the (Cj – Zj row) of a minimization problem. 16. Pivot or Key Row: It is the row corresponding to the variable that will leave the basis so as to provide room for the entering variable as indicated by the Key Column. This is the row having the smallest of the replacement ratios of the constraint rows. These CU IDOL SELF LEARNING MATERIAL (SLM)

Linear Programming 141 replacement ratios are obtained when the elements in the solution column are divided by the corresponding elements in the Key Column. z Pivot or Key Element: This element lies at the intersection of the Key Row and the Key Column. z Surplus Variable: A variable that is used for converting a “Less than” or “equal to” inequality constraint into equality by subtracting it from the L.H.S of the constraint. The value of this (surplus) variable is interpreted as the amount over and above required minimum level. z Artificial Variable: It is a variable that is added over and above the surplus variable when the constraints are of a greater than’ or ‘equal to’ type (3) so as to obtain as initial feasible solution to an L.P.P. these Artificial Variables are reduced to zero at optimality. z Basic Feasible Solution: It is a basic solution which satisfies the non-negativity requirement and exists in the feasible region as it corresponds to a comer point of the feasible region. z Unbounded Solution: This is found when replacement rows exhibit zero or infinite values. z Degeneracy: This is the case when there is a tie for replacement ratios for choosing the departing variables. z Algorithm: It is a systematic procedure in a formal manner for solving problems. 7.3.1 Problems relating to two variables including the case of mixed constraints Problem 4: Solve the following L.P.P. Maximise P > 45xl + 55x2

Subject to: 6x1 + 4x2 d 120 3xl + 10x2 d 180 x1, x2 t 0 CU IDOL SELF LEARNING MATERIAL (SLM)

142 Business Mathematics and Statistics Solution: Step (1): Using slack Variables S1 and S2, converting inequalities into equalities, we have 6x1 + 4x2 + 1.S1 + 0.S2 = 120 3x1 + 10x2 + 0.Sl + 1.S2 =180 and objective function is: P = 45x1 + 55x2 + 0.S1 + 0.S2 Step 2: We set up Basic Simplex Table 1. Coefficients in the objective function. p Cj 45 55 0 0 Prod S2 X 0 1 Xl 2 SI 0 0 a Sl 120 6 4 1 a S2 180 3 10 0 Zj 0 00 0 –45 -55 0 Zj – Cj Step 3: Calculation of Zj and Zj – Cj Zj = X1 = 6 (0) + 3 (0) = 0 Zj – Cj Sol = a X2 = 4 (0) + 10 (0) = a Values X1 = 0-45 = –45 S,=1(0)+0(0)=0 X2 =0–55=-55 S2=0(0)+1(0)=0 S1=0–0 = 0 S2=0–0=0

The negative values in the Zj – Cj row indicates scope for improvement. Step 4: Selecting the entering variable. ? We select the highest negative number –55 in the index row. ? Corresponding to the selected highest negative number -55 we see the corresponding column, called key column. Here column X2 is the key column. The entering variable is X2 and S2 is the departing variable. The element 4 in the key column is called intersecting element. CU IDOL SELF LEARNING MATERIAL (SLM)

Linear Programming 143 Table 2 Cj 45 55 0 0 Ratio P.Mix SrI. XX S S 12 1 2 S 0 1 120 6 4 1 0 120/4 = 30 0 S 2 180 3 10 0 1 180/10 = 18 Zj 0 0 0 Zj - Cj 0 -45 -55 0 0 We find the ratio 120/4 = 30 and 180/10 = 18. We select the smallest of these ratio, i.e., 18. And the row corresponding to this ratio is called the key row. The element at the intersection of the key row and key column is called the key element or Pivot element. Step 5: Effecting changes in the key row. Column Key Row Key Number Reduced Key Row Solution 180 180/10 = 18 X1 3 3/10 10 10 X 0 1 10/10 = 1 2 0/10 = 0 S 1/10 1 S2

Step 6: Effecting changes in the remaining row. Containing intersecting element 4. (1) (2) (3) (4) (5) Column Old Element Intersecting Replaced New Row Element Row Element Key Row (2) – (3) × (-l) Solution 120 18 48 X1 6 3110 24/5 X 41 0 24 01 S1 1 1/10 -2/5 S2 0 CU IDOL SELF LEARNING MATERIAL (SLM)

144 Business Mathematics and Statistics Using the respective Values as per steps 5 and 6 the [Table 3] would be: Cj 45 55 0 0 PM SOL X1 X2 S1 S2 Ratio 0 S1 48 24/5 0 1 –2/5 48y24/5 = 10 m KEY 0 1/10 ROW X 55 2 18 3/10 1 1 8y3/10 = 60 Zj 990 33/2 55 0 11/2 0 11/2 Zj – Cj 990 –57/2 0 Step 7: Now the key element is 24/5, the following are the calculations. Key Row Key Number Reduced Key Row 48 48 y 24/5 = 10 24/5 24/5 y 24/5 = 1 0 24/5 0 y 24/5 = 0 1 1/24/5 = 5/24 -2/5 –2/5 y 24/5 = –1/12 Step 8: