BBA102_BCM102_Business Mathematics and Statistics

Determinants 95 5.1 Introduction Meaning and Definition of a Determinant The expression ab' – a'b is represented by ab a' b ' which is called a determinant of the second order. It has two rows a, b and a', b' and two columns a, a' and b, b'. The expression ab' – a'b is called the expansion of the determinant. ab a' b ' a, b, a' , b' are called the elements, ab' and – a'b are called the terms of the expansion. The first ab’ is called the leading term. Example 1: Evaluate 78 59 The expansion is 7 × 9 – 8 × 5 = 63 – 40 = 23 Example 2: Simplify x+8 x  1 x+6 x  3 The expansion is (x + 8) (x – 3) – (x – 1) (x + 6) = x2 + 5x – 24 – (x2 + 5x – 6) = x2 + 5x – 24 – x2 – 5x + 6 = – 18 5.2 Simultaneous Equations Simultaneous Equations can be solved conveniently by using determinants. The procedure is explained in the solution of the following equations: CU IDOL SELF LEARNING MATERIAL (SLM)

96 Business Mathematics and Statistics a1x + b1y + c1 = 0 … (1) a2x + b2y + c2 = 0 … (2) Multiplying eqn. (1) by b2 and eqn (2) by b1, we have, a1b2x + b1b2y + c1b2 = 0 …(3) a2b1x + b1b2y + c2b1 = 0 … (4) Subtracting eqn (4) from eqn (3), we get (a1b2 – a2b1) x + c1b2 – c2b1 = 0 ? (a1b2 – a2b1) x = b1c2 – b2c1 b1c2  b2c1 provided a1b2 – a2b1 0 x = a1b2  a2b1 Similarly, y= c1a 2  c2a1 a1b2  a 2b1 xy1 Therefore, b1c2  b2c1 c1a2  c2a1 a1b2  a2b1 provided a1b2 – a2b1 0 Using determinants, we can write the above as x = y =1 b1 c1 c1 a1 a1 b1 b2 c2 c2 a2 a2 b2 Example 3: Using determinants, solve =1 2x – 3y = 3 2 3 52 5x + 2y = 36 The given equation can be written as 2x – 3y – 3 = 0 5x + 2y – 36 = 0 ?x = y 3 3 3 2 2 36 36 5 CU IDOL SELF LEARNING MATERIAL (SLM)

Determinants 97 ? x = y =1 108 + 6  15 + 72 4 + 15 x = y = 1 ? 114 57 19 ? x = 114/19 = 6 y = 57/19 = 3 5.2 The Linear Equations in Two Unknowns Given three equations, we proceed to find the condition that they are satisfied by the same values of x and y. Suppose the given equation are l1x + m1y + n1 = 0 y … (1) l2x + m2y + n2 = 0 … (2) l3x + m3y + n3 = 0 … (3) Solving (2) and (3) we get, x= =1 m2 n2 n2 l2 l2 m2 m3 n3 n3 l3 l3 m3 provided l2m3 – l3m2 0 ? x= m2 n2 and n2 l2 m3 n3 y = n3 l3 l2 m2 l2 m2 l3 m3 l3 m3 If these values of x and y are to satisfy equation (1), then the condition is: m2 n2 n2 l2 + n1 = 0 l1 m3 n3 + m1 n3 l3 CU IDOL SELF LEARNING MATERIAL (SLM)

98 Business Mathematics and Statistics l2 m2 l2 m2 l3 m3 l3 m3 i.e., l1 m2 n2 + m1 n2 l2 + n1 l2 m2 =0 m3 n3 n3 l3 l3 m3 or l1 m2 n2 – m1 l2 n2 + n1 l2 m2 =0 m3 n3 l3 n3 l3 m3 n2 l2 = n2l3– n3l2 = – (n3l2 – n2l3) because n3 l3 l2 n2 = – l3 n3 Thus the condition is l1 (m2n3 – m3n2) – m1 (l2n3 – n2l3) + n1 (l2m3 – l3m2) = 0 The left hand side of the above expression is written in the form l1 m1 n1 l2 m2 n2 l3 m3 n3 Which is called a determinant of the third order. The expression l1 (m2n3 – m3n2) – m1 (l2n3 – n2l3) + n1 (l2m3 – l3m2) is called the expansion of the above determinant. It may be noted that a determinant of the third order has to be expanded in terms of the determinants of the second order. Example 4: Expand l ab amc bcn CU IDOL SELF LEARNING MATERIAL (SLM)

Determinants 99 The expansion is mc ac am l c –a b n +b c n b = 1 (mn – c2) – a (an – bc) + b (ac – bm) = lmn – lc2 – a2n + abc + abc – b2m = lmn + 2 abc – a2n – b2m – c2l Example 5: Evaluate: 345 534 453 The determinant 34 54 53 =3 –4 +5 3 4 3 4 5 5 = 3 (9 – 20) – 4 (15 – 16) + 5 (25 – 12) = 3 (– 11) – 4 (– 1) + 5 (13) = – 33 + 4+ 65 = 36 Example 6: Are the following equations consistent? x + 2y + 3 = 0 3x + 5y + 7 = 0 7x – 4y – 15 = 0 The above equations would be consistent only if the determinanat. 12 3 is zero 35 7 7  4 15 CU IDOL SELF LEARNING MATERIAL (SLM)

100 Business Mathematics and Statistics Verifying, we use 1 (– 75 + 28) – 2 (– 45 – 49) + 3 (– 12 – 35) i.e., – 75 + 28 + 188 – 141 i.e., 216 – 216 =0 Hence verified. The given equations are consistent. Example 7: Solve 1x 7 2 5 4 = 0 x 7 15 Expanding the determinants, we have, 1 (– 75 + 28) – x (– 30 + 4x) + 7 (14 – 5x) = 0 i.e., – 47 + 30 – 4x2 + 98 – 35x = 0 i.e., – 4x2 – 5x + 51 = 0 i.e., 4x2 + 5x – 51 = 0 i.e., 4x2 – 12x + 17x – 51 = 0 i.e., 4x (x – 3) + 17 (x – 3) = 0 i.e., (4x + 17) (x – 3) = 0 ? x = – 17/4 and x = 3 5.4 Theorems on Determinants Theorem 1 : The value of a determinant is not altered if the rows and columns are interchanged. Consider the determinant x1 x2 x3 D = y1 y2 y3 z1 z2 z3 CU IDOL SELF LEARNING MATERIAL (SLM)

Determinants 101 Let the determinant that is obtained by interchanging rows and columns be denoted by D', that is, x1 y1 z1 D' = x2 y2 z2 x3 y3 z3 We shall prove that D’ = D. Expanding the determinant D', we get, D' = x1 (y2z3 – y3z2) – y1 (x2z3 – x3z2) + z1 (x2y3 – x3y2) = x1 (y2z3 – y3z2) – x2 (y1z3 – y3z1) + x3 (y1z2 – y2z1) =D ? D' = D Hence the theorem is proved. Theorem 2: If two rows or two columns of a determinant be interchanged then the determinant is altered in sign only. x1 x2 x3 Suppose, D = y1 y2 y3 z1 z2 z3 Let the determinant that is obtained by interchanging first and second rows of D be denoted by D', then y1 y2 y3 D' º x1 x2 x3 z1 z2 z3 To show that D' = – D, Now D' = y1 (x2z3 – x3z2) – y2 (x1z3 – x3z1) + y3 (x1z2 – x2z1) = { x1 (y2z3 – y3z2) – x2 (y1z3 – y3z1) + x3 (y1z2 – y2z1) } = –D Hence the theorem is proved. CU IDOL SELF LEARNING MATERIAL (SLM)

102 Business Mathematics and Statistics Theorem 3: If in a determinant, two rows (or two columns) are identical then the value of the determinant is zero. Suppose D denotes the determinant which has two rows identical Let D' denote the determinant obtained by interchanging the two identical rows. Then, by virtue of theorem 2, it follows that D' = – D … (1) In fact D' is the same as D, as the two rows that are interchanged are identical. Thus, D' = D … (2) From results (1) and (2) it follows that D= –D ? 2D = 0 ? D = 0 Hence the theorem is proved. Theorem 4:If all the elements of one row (or column) of a determinant are multiplied by a member ‘p’ then the value of the determinant is multiplied by ‘p’. x1 x2 x3 Consider, D = y1 y2 y3 z1 z2 z3 Let D' = px1 px2 px3 y1 y2 y3 z1 z2 z3 i.e., the elements of the 1st row of D are multiplied by ‘p’. To show that D' = p (D) Now D' = px1 (y2z3 – y3z2) – px2 (y1z3 – y3z1) + px3 (y1z2 – y2z1) = p { x1 (y2z3 – y3z2) – x2 (y1z3 – y3z1) + x3 (y1z2 – y2z1)} i.e., D' = pD Hence the theorem is proved. CU IDOL SELF LEARNING MATERIAL (SLM)

Determinants 103 Theorem 5: In each element of any row (or column) be expressed as the sum of two terms, thenthe determinant can be shown to be equal to the sum of two other determinants. Consider, x1  l1 x2 + l2 x3 + l3 y1 y2 y3 z1 z2 z3 In this determinant each element of the first row, is expressed as the sum of two terms. Expanding this determinant, we get, (x1 + l1) (y2z3 – y3z2) – (x2 + l2) (y1z3 – y3z1) + (x3 + l3) (y1 z2 – y2z1) = { x1 (y2z3 – y3z2) – x2 (y1z3– y3z1) + x3 (y1z2 – y2z1) } = { l1 (y2z3 – y3z2) – l2 (y1z3 – y3z1) + l3 (y1z2 – y2z1) } x1 x2 x3 l1 l2 l3 = y1 y2 y3 + y1 y2 y3 z1 z2 z3 z1 z2 z3 Hence the theorem is proved. Similarly, if each element of a row or column be expressed as the sum of three terms then the determinant can be expressed as the sum of three other determinants. In this way this theorem can be extended. Theorem 6: The value of a determinant is not changed by adding to the elements of any row (or column) the same multiples of the corresponding elements of any other row (or column). x1 x2 x3 Consider, D = y1 y2 y3 z1 z2 z3 Let D' be the determinants that is obtained by adding to the elements of the first row of D, the multiples pz1, pz2, pz3 of the corresponding elements of the third row. Here ‘p’ is a certain constant. ? D= x1 + pz1 x2 + pz2 x3 + pz3 y1 y2 y3 z1 z2 z3 CU IDOL SELF LEARNING MATERIAL (SLM)

104 Business Mathematics and Statistics To show that D’ = D Now D' = x1 x2 x3 pz1 pz2 pz3 y1 y2 y3 z1 z2 z3 + y1 y2 y3 By theorem 5. z1 z2 z3 x1 x2 x3 z1 z2 z3 = y1 y2 y3 + p y1 y2 y3 By theorem 4. z1 z2 z3 z1 z2 z3 x1 x2 x3 = y1 y2 y3 + p × 0 (By theorem 3) z1 z2 z3 = D ? D' = D Hence the theorem is proved. By extending this theorem, we can, similarly show that, x1 + my1 + pz1 x2 + my2 pz2 x3 + my3 + pz3 y1 y2 y3 z1 z2 z3 x1 x2 x3 = y1 y2 y3 z1 z2 z3 Here m and p are constants. Example 8: Show that xy yz zx =0 yz zx xy zx xy yz CU IDOL SELF LEARNING MATERIAL (SLM)

Determinants 105 Adding the sum of the 2nd and 3rd rows to the 1st row, we get 000 = 0, since yz zx xy zx xy yz all the elements of the 1st row are zero. Example 9: Prove that a a2 bc b b2 ac = (a – b) (b – c) (c – a) (ab + bc + ca) c c2 ab Subtracting 2nd row from the 1st row and 3rd row from the second, we get ab a2  b2 bc  ac bc b2  c2 ac  ab c c2 ab l a + b c = (a – b) (b – c) l b + c - a c c2 ab Subtracting 2nd row from the 1st row, we get 0 ac a c (a – b) (b – c) l b  c a c c2 ab = (a – b) (b – c) (a – c) 0l l l b  c a c c2 ab = (a – b) (b – c) (a – c) { – (ab + ac) + (c2 – bc – c2) } = (a – b) (b – c) (a – c) (– ab – ac – bc) = (a – b) (b – c) (c – a) (ab + bc + ca) CU IDOL SELF LEARNING MATERIAL (SLM)

106 Business Mathematics and Statistics Example 10: Prove that x+ z x x = 4 xyz y z+x y z x+y z Subtracting the sum of the second and third rows from the first row, we get 0 2z 2y y zx y z z x y 0z y = –2 y z + x y z z x+y yy y z+x = + 2z z x + y – 2y z z = 2z { y (x + y) – yz } – 2y { yz – z (z +x) } = 2z (xy – yz + y2) – 2y (yz – zx – z2) = 2xyz – 2yz2 + 2y2z – 2y2z + 2xyz + 2yz2 = 4xyz Example 11: Prove that x + y + 2z x y z y  z + 2x y = 2 (x + y + z)3 z x z + x + 2y Let x + y + z = k, so that x + y + 2z = k + z, y + z + 2x = k + x and z + x + 2y = k + y k+z x y L.H.S. = z k+x y z x k+y CU IDOL SELF LEARNING MATERIAL (SLM)

Determinants 107 Subtracting 2nd row from the 1st row and 3rd row from the 2nd, we get k k 0 o k k z x k+y Adding 1st column to the second column k0 0 l0 0 o k  k = k2 o l l z x+z k+y z x+z k+y = k2 (k + y) + (x + z) = k2 (x + y + z + k) = (x + y +z)2 2 (x + y + z) = 2 (x + y + z)2 Crammer’s Rule Cramer’s Rule is a handy way to solve for just one of the variables without having to solve the whole system of equations. The point of the Rule: instead of solving the entire system of equations, you can use Cramer’s to solve for just one single variable. Let’s use the following system of equations: 2xyz  x±y±z  xyz  We have the left-hand side of the system with the variables (the “coefficient matrix”) and the right-hand side with the answer values. Let DEH WKHGHWHUPLQDQW RIWKH FRHIILFLHQW PDWUL[RI WKH above system, and let DxEH WKH GHWHUPLQDQW IRUPHG E\\ UHSODFLQJ WKHx-column values with the answer-column values: CU IDOL SELF LEARNING MATERIAL (SLM)

108 Business Mathematics and Statistics System of Coefficient Answer Dx: coefficient equations matrix’s column determinant with determinant answer-columnvalues in x-column 2x  1y 1x 3 21 1 ª3º 31 1 1x  1y 1z 0 D 1 1 1 ««0»» Dx 1 1 1 1x  2y  1z 0 «¬0¼» 12 1 12 1 6LPLODUO\\DyDQGDzwould then be: 23 1 213 Dy 1 0 1 Dz 1 1 0 10 1 120 Evaluating each determinant (using the method explainedhere), we get: 21 1 D 1 1 1 = (–2) + (–1) + (2) – (–1) – (–4) – (1) = 3 12 1 31 1 Dx 0 1 1 = (–3) + (0) + (0) – (0) – (–6) – (0) = –3 + 8 = 3 02 1 23 1 Dy 1 0 1 = (0) + (–3) + (0) – (0) – (0) – (3) – 3 = – 6 10 1 213 Dz 1 1 0 = (0) + (0) + (6) – (–3) –(0) – (0) = 6 + 3 = 9 120 Cramer’s Rule says that x D[·Dy D\\·D, and z D]·D. That is: x 3/3 y –6/3 ±, and z 9/3  CU IDOL SELF LEARNING MATERIAL (SLM)

Determinants 109 That’s all there is to Cramer’s Rule. To find whichever variable you want (call it “ß” or “beta”), just evaluate the determinant quotient Dß·D. Inverse of a Square Matrix Let A be a square matrix of order n. If there exists a square matrix B of order n such that AB = BA = I, then B is called the inverse of A and we denote it by A–1. If a square matrix A has inverse, then A is said to invertible. We know that A. (adj A) = (adj A). A = |A| In § adj A · § adj A · Ÿ A.©¨ |A| ¹¸ = ©¨ |A| ¹¸. A = In Thus, we get 1 A–1 = . adj A |A| A square matrix A is invertible if and only if A z 0 is non-singular, i.e. if |A| z 0. Also the inverse of a square matrix is always unique. Properties of Inverse (a) If A and B are two matrices of order n such that AB = I, then A–1 = B and B–1 = A. (b) If A and B are two non-singular matrices of order n, then (AB)–1 = B–1 . A–1 (not A–1 B–1) (c) Inverse of inverse is the original matrix i.e., (A–1)–1 = A (d) The inverse of the transpose of a matrix is the transpose of its inverse. i.e., (A')–1 = (A–1)' (e) If A is a non-singular matrix of order n and In is the unit vector the A . A–1 = A–1. A = I. (f) The inverse of an identity matrix is the identity matrix it self. i.e., In–1 = In. FHG KJIExample 1: Find the inverse of the matrix A = FGH –34JIK 2 –4 –1 3 Solution: A = 2 –1 |A| = 6 – 4 = 2 0 ? A–1 exists. CU IDOL SELF LEARNING MATERIAL (SLM)

110 Business Mathematics and Statistics The cofactors of aij are C13 = –1 C23 = 0 C11 = 3 C12 = –(–1) = 1 C33 = 1 C21 = –(–4) = 4, C22 = 2 GHF JIK? 31 (Cij) = 4 2 and F I3 1 GH KJadj A = (Cij)’ = 1 2 Inverse of A is given by A–1 = 1 . adj A |A| FGH JIK? A–1 = 1 31 2 42 F I1 3 3 G JExample 2: Find the inverse of the matrix 1 4 3 HG KJ1 3 4 F I1 3 3 G JSolution: Let A = 1 4 3 GH KJ1 3 4 |A| = 1(7) – 3(1) + 3(–1) = 1 0 ? A–1 exists. The cofactors are : C11 = 7, C12 = –1, C21 = –3, C22 = 1, C31 = –3, C32 = 0, F7 I–1 –1 G? The cofactor matrix, (Cij) = –3 J1 0 JK0 1 GH –3 F I7 –3 –3 G Jadj A = (Cij)' = –1 1 0 GH KJ–1 0 1 Inverse of A is given by A–1 = 1 . adj A |A| CU IDOL SELF LEARNING MATERIAL (SLM)

Determinants 111 ? F I F I7 –3 –3 7 –3 –3 G J G JA–1 = 1 –1 1 0 = –1 1 0 HG KJ HG JK1 –1 0 1 –1 0 1 Difference between Matrices and Determinants Matrices Determinants 1. $PDWUL[RUPDWULFHVLV D UHFWDQJXODU JULG RI $GHWHUPLQDQWLVDFRPSRQHQWRIDVTXDUHPDWUL[DQG numbers or symbols that is represented in a row it cannot be found in any other type of matrix. ... and column format. $GHWHUPLQDQWLVDQXPEHUWKDWLVDVVRFLDWHGZLWKD VTXDUHPDWUL[ 2. Matrix is the set of numbers which are covered Determinants is also set of numbers but it is covered by two brackets. by two bars. 3. It is not necessary that number of rows will be But it is necessary that number of rows will be equal equal to the number of columns in matrix. to the number of columns in determinant. 4. Matrix can be used for adding, subtracting and Determinant can be used for calculating the value multiplying the coefficients. of x, y and z with Cramer’s Rule. 5.5 Summary We study the meaning and definition of a ‘Determinant’ along with the simple illustrative examples. We learn the method of evaluation of a determinant and solving a determinant. the six different theorems on determinants explain their usage in proving certain determinant examples. 5.6 Key Words/Abbreviations Consistence, Linear equations, Expansion, addition of determinants as explained in the theorems. 5.7 Learning Activity Study the theorems carefully and work out the examples given at the end under (MCQ and Descriptive). ................................................................................................................................................. ............................................................................................................................................... CU IDOL SELF LEARNING MATERIAL (SLM)

112 Business Mathematics and Statistics 5.8 Unit End Questions (MCQ and Descriptive) A. Descriptive Type: Short Answer Type Questions 1. Explain the method of finding the determinant of a square matrix. 2. Distinguish between (a) Matrix and Determinant, (b) Minor and Cofactor 3. Evaluate the following: (a) 5 12 , 1 –3 (c) 7 2 , x2  x 1 x (b) , 01 (d) x 1 3 20 41 x 1 4. Evaluate the following: 132 11 1 3 1 –1 1234 (a) 4 1 1 (b) 1 0 –1 (c) 5 2 3 4321 53 2 (d) 2143 1 –2 1 83 1 3214 5. Show that the following matrices are singular. F I6 –3 2 F I3 4 5 G J(a) A = 2 –1 2 G J(b) X = –4 7 8 HG JK–10 5 2 HG JK6 8 10 6. Are the following equations consistent? [Ans: Yes] x+y+2=0 [Ans: k = 3] 2x + 3y + 1 = 0 x + 4 –7 = 0 7. Find k so that the following equations may be simultaneously true x + ky – 3 = 0 (2k + x) + y – 5 = 10 3x – y + 11 = 0 8. Prove that xyz 2x 2x 2y y  z  z 2y = (x + y + z)3 2z 2z z  x  y CU IDOL SELF LEARNING MATERIAL (SLM)

Determinants 113 9. Show that 111 = (x – y) (y – z) (z – x) xyz x2 y2 z2 10. Prove that ª y + z x  z x  yº «y  z z + x y  x» = 8xyz «¬z  y z  x x + y »¼ 11. Show that 1 w w2 = 0 and also w w2 1 w2 1 w 1 w3 w2 =3 w3 1 w w2 w 1 where w is one of the imaginary cube roots of unity. 12. Prove that x+1 x+m x+n y+1 y+m y+n = 0 z+1 z+m z+n 13. Show that x2 + 1 2x + 1 3 = (x – 1)3 2x + 1 x + 2 3 1 11 14. Show that (y + z)2 x2 x2 = 2xyz (x + y + z)3 y2 (z + x)2 y2 z2 (x + y)2 z2 CU IDOL SELF LEARNING MATERIAL (SLM)

114 Business Mathematics and Statistics 15. If a a2 a3 + 1 = 0, show that abc = – 1 b b2 b3 + 1 c c2 c3 + 1 16. Solve 1+x 1x 1x [Ans: x = 0 , x = 3] [Ans: x = 2, – or 3] 1x 1x 1x =0 1x 1x 1x 17. Solve 1x 3 =2 2x 4 3x  2 4 2x 6  x 18. Prove that x yz z+y = (x + y + z) (x2 + y2 + z2) x+z y zx xy y+x z 19. Show that m+ n l  m l n + 1 m  n m = 3 lmn – 13 – m3 – n3 l+m nl n 20. Are the following equations consistent? y–x+z=0 3x + 7y – 3z = 0 4x + y + z = 0 CU IDOL SELF LEARNING MATERIAL (SLM)

Determinants 115 21. Without directly expanding the determinant, but using only the well-known properties, prove that ab l a a1b bc l b = b1c ca l c c1a 22. Solve x+a b c c x+b a =0 a b x+c 23. Prove that a2 2ab b2 is a perfect square. b2 a2 2ab 2ab b2 a2 24. Without actual expansion, but by using properties of determinants, prove that a2 a bc a3 a2 l b2 b ca = b3 b2 l c2 c ab c3 c2 l 25. Solve for x =0 lll axa bbx 26. Show that a2 a l b2 b l = – (a – b) (b – c) (c – a) c2 c l CU IDOL SELF LEARNING MATERIAL (SLM)

116 Business Mathematics and Statistics 27. Express the square of the determinant a1 b1 0 a2 b2 0 a3 b3 0 as a third order determinant. Now obtain the value of this third order determinant. 28. Find the value of the determinant ab0 c0a 0cb and then express its square as a third order determinant. What is its value? 29. Write down the determinant. ap + bq ar + bs cp + dq cr + ds as the sum of four determinants and hence prove that it equals to the product of the two determinants, namely ab pq cd × r s 30. Solve the following system of equation by Cramer’s Rule. 2x + y + z = 7 3x – y – z = –2 x + 2y – 3z = – 4 5.9 References References of this unit have been given at the end of the book. ˆˆˆ CU IDOL SELF LEARNING MATERIAL (SLM)

Permutations and Combinations 117 UNIT 6 PERMUTATIONS AND COMBINATIONS Structure 6.0 Learning Objectives 6.1 Introduction 6.2 Combinations 6.3 Interpretation of O! 6.4 Distribution in Groups 6.5 Illustrative Examples 6.6 Summary 6.7 Key Words/Abbreviations 6.8 Learning Activity 6.9 Unit End Questions (MCQ and Descriptive) 6.10 References 6.0 Learning Objectives After studying this unit, you will be able to: z Explain the meanings of ‘permutation’ and ‘combination’. z Elaborate the notation nPr and nCr and the related theorem for finding the value of nPr and nCr where r d n. z Describe the interpretation of nCo, nCn, O! and the rules and corollories. z Illustrate the method of solving related examples with reference to illustration examples. CU IDOL SELF LEARNING MATERIAL (SLM)

118 Business Mathematics and Statistics 6.1 Introduction In the modern world of business, commerce and industry, we come across certain practical problems which involve a number of different arrangements (Permutations) and selections (Combinations) of men, materials and things. Major business decisions are more often dependent upon a wise and judicious choice of the different arrangements or selections. The success of such decisions depends upon the thorough study of the different permutations and combinations. A study of the theoretical principles and problems of permutations and combinations is not only amusing but also useful. For instance, if there are two vacancies of salesmen in a firm, i.e., a vacancy of a junior salesman and that of a senior salesman and the management interviews three applicants A, B, C then the management can take anyone of the following six possible decisions in filling up the two vacancies. These six possible arrangements, that is, AB, BA, BC, CB, CA and AC are known as the ‘permutations’ of three applicants A, B, C taken two at a time. Junior Salesman Senior Salesman A B B A B C C B C A A C Thus the different arrangements that ·can be made by taking some or all of a number of things, are known as ‘Permutations’. To give another example, if three different numbers, i.e., 2, 5 and 6 are given and we are required to find the number of permutations of these three numbers taking two at a time then the following would be the different permutations. 26, 56, 62, 65, 26 On the other hand, if we are required to find the number of permutations of the three numbers 2, 5, 6 taking all the three numbers at a time, then the permutations would be: 256, 562, 625, 526, 652, 265 CU IDOL SELF LEARNING MATERIAL (SLM)

Permutations and Combinations 119 Narration: P is a notation that is used to denote the number of permutations of n different things, when r things are taken. at a time. For example, if 2 things are taken at a time out of 3 different things, then the number of different permutations would be 3P2 and in this case 3P2 = 6. There is a fundamental theorem which forms the basis of certain general propositions in Permutations. This theorem can be stated as: If there are m ways of performing an operation and after the operation has been performed in anyone of the m ways, if a second operation can be performed in n ways then the number of ways of performing the two operations would be mn. To show that the number of permutations of n different things taken r at a time is n (n – 1) (n – 2) .................. (n – r + 1) Suppose there are r different blank spaces, each of which has to be filled up by any of the n different things. 123 ........ r (n) (n – 1) (n – 2) (n – r + 1) There are n ways to filling up the first space and when it has been filled up by anyone of the n things, then there being (n – 1) things remaining, it follows that the second space can be filled up in (n – 1) ways. Similarly the third space can be filled up in (n – 2) ways and proceeding in, that manner it is clear that the rth space can be filled up in (n – r + 1) ways. Therefore, the number of ways of filling up all the r blank spaces, would be: 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! nPr = (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 2B2ynBn B1!B2 !yBn ! 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 VVS sgn 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) nCr = n(n 1)(n  2)..........(n  r 1) r! We can also express nCr as under: n! nCr = (n  r)! ? nCr = n(n  1)(n  2)..........(n  r  1)(n  r) 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: nCr = nCn–r n! L.H.S. = nCr = r!(n  r)! n! R.H.S. = nCn–r = (n  n  r)!(n  r) n! = n!(n  r)! n! ? nCr = (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. Thus, for one combination, number of arrangements is r! nCr … (1) But number of permutations of n different things taken r at a times is nPr … (2) From (1) and (2) we get n! r! nCr = nPr = (n  r)! n! = nPr = r!(n  r)! Properties of nCr: … (1) 1. nCr = nCn-r. … (2) n! Proof: nCr = r!(n  r)! n! nCn-r = (n  r)! (n  (n  r)! n! nCr = (n  r)!(r)! CU IDOL SELF LEARNING MATERIAL (SLM)

124 Business Mathematics and Statistics From equation (1) and (2) … (1) nCn-r = n! = nCr (n  r)!(r)! Hence proved nCr = nCn-r. 2. nCx = nCy, then either x = y or x + y = n. 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., = 1, and this equality would be meaningless o! unless O! = 1 Therefore, we define o! as .unity. Similarly by putting r = 0 in the formula for nCr, we get n! nCn = n!o! = 1 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 – Ÿžžžn1®¬­­­­ (n 1)m  Ÿžžžn2®¬­­­­ (n  2)m ym b n 4. The number of increasing (decreasing) functions from A to B is žžŸžmn ®¬­­­­ .m d n. 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!  ¡¢¡¡ 1  1  1 y  (1)m ±¯°°° . 2! 3! 4! 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 e A is ¢¡¡ ¡ 1  1  1 y  (1)m °°±¯° 2! 3! 4! m! Here required number of ways = 5!Ÿžžž 1  1 1  51!¬®­­­ 2! 3! 4! = 120žžŸž 1  1  1  1210¬®­­­ 2 6 24 = 120 žŸžž 60  20  5 1®¬­­­  44. 120 Geometrical Applications: z Out of n non-concurrent and non-parallel straight lines the number of point of intersection DUHnC‚ . z The number of straight lines passing through n points = nC‚ . z The number of straight lines passing through n points out of which m are collinear nC‚ ±mC‚ + 1. z In a polygon, the total number of diagonals out of n points (no three points are collinear) nC‚ – n = n(n-3)/ 2. z Number of triangles formed by joining n points is nC3. CU IDOL SELF LEARNING MATERIAL (SLM)

Permutations and Combinations 127 z Number of triangles formed by joining n points out of which m are collinear are nCƒ – mC3. z 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 z 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) ? 3n = 4 (n – 4) ? n = 16 Example 5: Find n, if nC5 = 2(nP4) Now nC5 = n(n 1)(n  2)(n  3)(n  4) 5u 4u3u 2u1 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) ? n – 4 = 2(120) = 240 ? n = 244 Example 6: If nC5 = 8(nC4), find n Now nC5 = n(n 1)(n  2)(n  3) 120 and 8(nC4) = 8n(n 1)(n  2)(n  3) 4u3u 2u1 Given, n(n 1) (n  2) (n  3) (n  4) 5u 4u3u 2u1 8n(n 1) (n  2) (n  3) = 4u3u 2u1 = [n – nP5] = 4[nP5] n4 ? 5 =8 CU IDOL SELF LEARNING MATERIAL (SLM)

Permutations and Combinations 129 i.e., n – 4 = 40 ? n = 44 2x C5 198 Example 7: If x C3 = 5 , find x Now = 2x C5 x C3 2x(2x 1) (2x  2) (2x  3) (2x  4) = 5u 4u3u 2u1 x(x 1)(x  2) = 3u2u1 2x(2x 1) (2x  2) (2x  3) (2x  4) = 5 u 4 u x(x 1)(x  2) 2 u 2 u 2 u x(x 1) (x  2) 2x 1) (2x  3) = 5 u 4 u x(x 1) (x  2) 22x 1) (2x  3) =5 22x 1) (2x  3) 198 = 55 22 i.e., (2x – 1) (2x – 3) = × 99 55 ? (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 ] 3. Find the number of combinations of 8 different things, taking 5 at a time. [Ans: 56] 4. 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 1. If each selection is to contain four books, find the number of selections that can be made from 10 different books when: (i) 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] 3. 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] 4. In how many ways can 9 things be divided equally among 3 persons. 9! 5. Prove that nCr + nCr–1 = n+1Cr. [Ans: (3!)3 ] 6. 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!)] 7. Prove that n+2Cr = nCr + 2nCr–1 + nCr–2 8. 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] 9. 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] 12. 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? [Ans: 100! , 98! ] 10! 90! 8! 90! CU IDOL SELF LEARNING MATERIAL (SLM)

132 Business Mathematics and Statistics 13. 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] 14. 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: z Explain the meaning of Linear Programming (LP), requirements and the method of formulation of an LP and the steps. z Describe with reference to a given L.P.P. procedure. z Elaborate the graphic method of solving an L.P.P. z Learn the Simplex Method, terminology and procedure of solving z 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: (i) 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. (ii) The activities and the resources should be quantifiable and distinctly identifiable. (iii) 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 P1 Machine E1 Machine E2 5 P2 4 Available hrs. per week 31 21 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: 1. We identify the decision variables in the given problem and denote them by x1 and x2 2. 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. 3. We identify the limiting conditions and express them as inequalities in terms of the decision variables. 4. The decision variables cannot take negative values. Hence they must carry a value greater than or equal to zero. 5 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 ` 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: Machine Part A Capacity per Hour Part C Part B 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 = 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: (i) The Graphic Method (ii) 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 x2 = 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 6 2 5 4 C (0,4) 3 B (3,2) 2x1 + 3x2 12 2 1 A (4,0) 0 12 34 5 67 (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 ? 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 ? Maximum P = 32 CU IDOL SELF LEARNING MATERIAL (SLM)

140 Business Mathematics and Statistics 7.3 Simplex Method: Terminology and Procedure of Solving 1. Simplex Method: It is a systematic procedure (an algorithm) for solving L.P. problems. 2. 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. 3. 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. 4. 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. 5. Simplex Table: It is a table that is used for keeping tack of the calculations made at each iteration of the simplex procedure. 6. 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. 7. 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. 8. 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. 9. ‘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. 10. 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. 11. Pivot or Key Element: This element lies at the intersection of the Key Row and the Key Column. 12. 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. 13. 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. 14. 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. 15. Unbounded Solution: This is found when replacement rows exhibit zero or infinite values. 16. Degeneracy: This is the case when there is a tie for replacement ratios for choosing the departing variables. 17. 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 S2 Prod Xl X2 SI 0 1 a Sl 120 6 4 1 0 0 a S2 180 3 10 0 Zj 0 0 0 0 Zj – Cj –45 -55 0 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. (i) We select the highest negative number –55 in the index row. (ii) 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 Cj P.Mix SrI. Table 2 0 0 Ratio S1 120 S1 S2 0 S2 180 45 55 1 0 120/4 = 30 0 0 X1 X2 0 1 180/10 = 18 Zj 0 64 Zj - Cj 3 10 0 0 00 -45 -55 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 X2 10 10 10/10 = 1 S1 0 S2 1 0/10 = 0 1/10 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 X1 120 4 18 48 X2 6 3110 24/5 S1 4 S2 1 1 0 0 0 1 1/10 -2/5 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 00 0 X2 S1 S2 Ratio 55 PM SOL X1 0 1 –2/5 48y24/5 = 10 m KEY 1 0 1/10 ROW Zj – Cj S1 48 24/5 X2 18 3/10 55 1 8y3/10 = 60 0 Zj 990 33/2 0 11/2 990 –57/2 0 11/2 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: Intersecting Element Replaced Key Row New Element Old Element Row (3) (4) (2) – (3) × (4) 10 18 – 3/10 × 10 = 15 (2) 1 3/l0 – 3/10 × 1 = 0 18 1 – 3/l0 × 0 = 1 3/l0 3/10 0 0 – 3/10 × 5/24 = –1/16 1 5/24 1/10 – 3/10 (–1/12) = 1/8 0 –1/12 1/10 Using the respective rules obtained in steps 7 and 8, he have (Table 4) as follows: Cj 45 55 0 0 P.M. Sol X1 X2 S1 S2 X1 10 1 0 5/24 –l/12 X2 15 0 1 –1/16 1/8 Zj 1275 45 1275 0 55 225/24 – 55/16 -45/12 + 55/8 Zj – Cj 0 9.38 – 3.44 = 5.94 6.88 – 3.75 =3.13 We get X1 = 10, X2 = 15 CU IDOL SELF LEARNING MATERIAL (SLM)