lites (a) NS OSHNNOA TALES and the atottets Bana Val lo The values O and 1 under x, gy 7NOMES under one unit of the same produ t th ict in the in OF x a led pit fr ang unt oF produet 9 with no ghed® mi isso e048 10% 40, According) =F ap A similar interpretation, may be given for th, ev Thesubsition rates under Sy are 973.1 SY material will entail losing 2/3 unite oe Bains a ; sats of product pF Against iable x, Broquites 3 ke of raw material, reducing meat Baining 179 gat These imply eleasine vould ne of raw material gi of it wi Product of raw would need 1 kg of Al since one unig Will releage NCUA ince one ut Bet = uct The loss of 2/3 unit of x» and the ain duet A requires 2 S while adding 17 ui a £1033. This is indicated by 4, = gia! Y/2 tit of, Would resutag eof material. ia i Ma net | Inasimilar way, it may be observeq that the vay O88 85 x 2/3) _ (49 12) = respect tox, and.x1, Tespectively, Withdraw alues 1/3 an, 4 and addition of 1/3 unit of produce The labour while addition of 1/3 unit of go TB of labour as desired. These chan, and gain of 35 x 1/3 = % 35/3 Anhour ofan 2 METS ini re £ B would con = = 2 hours of Bes shall cause a ny Out, resulting o j let reductj ig iN a net relea: ~~ 88 indicated by the a. yar on OfE 25/3 Sant . indicate the quantity 19 Such a product. (©) What would be the effect on the solution of each of the following: (0) obtaining an order for 6 units of product A, which has to be met. (i) an increase of 20 percent capacity in the fabrication department, (@) Leta), x, and.x5 represent the number of units of products A, B and C, respectively. The given problem can be expressed as an LPP as follows: Maximise Z= Sx, + 10x, + 8x3 Contribution Subject to 3x) + Sy + xy $ 60 Axy + xy + Any S$ 72 Fabrication hours Finishing hours80 © Quantitative Techniques in Management 2xy + Any + 5x3 $ 100 Packaging hours xytn ag 2 0 Introducing slack variables, the augmented problem can be written as Maximise Z= Sx, + lx + 8x3 + 0S; + OS; + 0S Subject to Bry + Sry + 2x3 +S, = 60 dy, + diy + 4x3 +S, = 72 xy + dry + 5xy + Sy = 100 Xa X3, Sp, Sy Sy 20 The solution to the problem using simplex algorithm is contained in Tables 3.7-3.9, TABLE 3.7 Simplex Tableau 1: Non-optimal Solution Basis x x % 5 Sy 5 bi bilay Ss 0 3 s* 2 1 0 0 60 12 & Outgoing varabg 0 4 4 4 0 1 0 n 18 S 0 2 4 5 0 0 1 10025 4 510 8 0 0 0 Solution 0 0 0 6 = 72100 4 5 10 8 0 0 0 tT Incoming variable TABLE 3.8 Simplex Tableau 2: Non-optimal Solution Basis * my on S&S bh blay x 10 3/5 1 ms us 0 o 2 30 0 8/5 0 1Us* as 1 0 24 10 © Outgoing variable Ss 0-25 0 175-4 0 1 52 260117 5 a) 8 0 0 0 Solution 0 2 0 Onur 24g 52: 4, - 0 4 2 0 0 t Incoming variableLinear Programming W: Simplex Method # 84 solution » -13 0 0 ea es 7 ding (0 Simplex Tableau 3, the optimal solution is x; = 0, x» = 8, x = 10. Thus, it calls for roduing 8 and 10 units of products B and C respectively, each day This mix would yield a Peribution of 5X x 10=% 160, 5 being equal to 18, an equal number of hours shall connie in the packaging department Evidently the optimal solution does not require the production of ‘product A. It can be explained as ‘The production of one unit of 4 requires giving up 1/3 units of B (x,) and 2/3 units of C (x3) it profit rates as 10 and 8, respectively, for these, the loss of profit would be 10 x 1/3 + 8 x Acco follows: swith the unit 33 = 2613. Reduction of x and.xy, together with production of one unit of, would cause a net release 2 9/3 hours in the packaging deparment as shown here: r Units produced Capacity used a Hours per unit producec ‘apacily us = (reduced) (released) A 2) 1 2 B mf (1B) 43) c 5 (213) (10/3) Net change (8/3) However, the released capacity would not affect the profit because the unit profit for its nil. Hence, the total loss of profit necessitated by substitution = 10/3 + 16/3 + 0 = 26/3. With a profit contribution of er unit of product being € 5, the net loss per unit equals 11/3, the difference of the two as given by the Aj value. ), To determine the effect on solution of each of the two changes, we proceed as follows: (i) To meet the demand of 6 units of product A, the necessary changes may be known by reference to the substitution rates given in column headed x; in the following table. © lariable Original value Change New value h 8 - 3x6) = 6 5 10 - Bx) = 6 Ss 18 - (813 x6) - 34 Zz 160 - (113 x6) = 1388 2 © Quantitative Techniques in Management Thus, forcing output of 6 units of product A would cause a reduction of profit by |), x % 22 leading to a total profit equal to & 138. M would cause a reduction in the output of rod Bby 2 units and product Cby 4 units. Of course, it will result in a lower ilsation of acy hours by 16 hours. . (1) Addition of capacity in fabrication would cause the following changes in the solution (brainey ‘through substitution rates in column headed S}) Variable Original value Change New value 3 (x12) R % 10 + (1312) 6 5 18 + (13x12) s n Zz 160 + (23x12) a 168 Thus, adding 12 hours of fabrication would raise the output of product B by 4 units and requ, the output of product Cby 4 units and release 4 hours in te packaging department. This wont, have a net effect of incveasing profit by ® 8 L 3.4 SOLUTION TO MINIMISATION PROBLEMS The solution procedure for the linear; Programming problems that have the objective function of the tainimisation 2P« is similar fo the one forthe maximisation problems, except for some differences. To illustrate, let ye again consider Example 2.2. Example 3.3 Minimise Z= 40x, + 24x Total cost Subject to 20x, + 50%) 2 4,800 Phosphate requirement 80x, + 50x, 7,200 Nitrogen requirement X20 Following the approach already discussed, we first introduce some new variables to convert inequalities ofthe System into equations. The variable required for converting a greater than’ type of inequality into an equation 's called surplus variable and itrepresents the excess of what is generated (given by the LHS of the inequality) over the requirement (shown by the RHS value 6), With surplus variables, 5; and S,, respectively for the fing and the second constraints, the augmented problem shall be Minimise Z= 40x, + 24x +05, + 05; Subject to 20x) + 50x. - $, = 4,800 80x, + 50x) ~ 5; = 7,200 Xi%51, 520 Now, as soon as we proceed tothe next step we experience a problem lke this. We may reall thatthe simplex method begins with an initial solution obtained by setting each ofthe decision variables equal to zero, Now, 'f'we set x and x, equal to zero in this problem, we get S, = 4,800 and S, = 7,200, which is not a feasibleLUnear Programming I: Simplex Method 83 all the solution as it violates the non-negativity restriction. In terms of the simplex tableau, when secured information, we observe that we do not get identity because unlike in case of slack variables, the cocffic values of surplus variables $; and 5» appear as minus one (-1), [.35_BIc-M METHOD na case where an identity is not obtained, as in the problem under : Sena a Variant ofthe simplex method called the Bi ig-M method LOS Discuss the ream is employed. In this method, we add artificial variables into the model Method for sol aoe to obtain an initial solution. However, unlike slack or surplus variables, Programming problem: artifical variables have no tangible relationship withthe decision problens Their sole purpose is t provide an inital soltion tothe given problem ‘When articial variables are introduced in the problem under consideration, its constraints appear as 20x, + 50x) S, +4, = 4,800 80x + 50x, ~ 5, + 4, = 7,200 {tis significant to understand thatthe artificial variables, which are not seen to disturb the equations already obiained since they ate not ‘real’, are introduced for the limited purpose of obtaining an initial solution and are required for the constraints of *>” type, or the constraints with ‘=’ sign. It is not relevant whether the objective function is of the minimisation or the maximisation type. Obviously, since artificial variables do not represent any quantity relating to the decision problem, they must be driven out of the system and must not show in the final solution (and if at all they do, it represents a situation of infeasibility, which is discussed later in this chapter). This can be ensured by assigning an extremely high cost to them. Generally, a value M is assigned to each artifical variable, where M represents a number higher than any finite number. For this reason, the method of solving the problems where artificial variables are involved i¢ termed ac the Big-M Method. Thus, when the problem is of the minimisation nature, we assign in the objective function a Coefficient of +M to each of the artificial variables. On the other hand, for the problems with the objective function of maximisation type, each of the artificial variables introduced has a coefficient Mf Note that it is attempted to prohibit the appearance of artificial variables in the solution by assigning these coefficients: an extremely large value when the objective is to minimise and an extremely small (negative) value when it is desired to maximise the objective function. For our present example, the objective function would appear as Minimise Z> 40x, + 245 + 05, + 0S, + Md, + Mdy Iris to note that the initial solution obtained using artificial variables is not a feasible Problem. Itonly gives a starting point andthe artificial variables are driven out in the simplex algorithm. Infact, as long as an artifical variable is included in the and only a solution to the problem that does not include an artificial variable feasible solution to the problem. solution to the given the normal course of applying basis, the solution is infeasible in the basis, represents a basic The initial simplex tableau giving the initial solution to our problem is given in Table 3.10.84 * Quantitative Techniques in Management TABLE 3.10 Simplex Tableau 1: Non-optimal Solution Basis By Sees ba AM 20 50" 0 ! 0 4,800 6 a a A A 1 0 Tense 6g 5 40 24 oo _ Solution 0 0 0 0 4,800 7,200 4 40-100M — 24-100M uM a : t For the minimisation problem, the optimal solution is indicated when the values in the 4, row are zero Positive. The presence of negative A, values indicates that the solution can be improved i. henever an LPP has some constraints involving >’ or =” signs, we need to introduce artificial variable have identity in the simplex tableau, to enable us to obtain an initial solution. The artificial variables are like Catalysts that only enable us to begin with a solution. They are expected to be eliminated in the successive iterations of obtaining improved solutions. To ensure this, we assign in the objective function a coefficient equa, (to M (big-M) to each artificial variable for a minimisation problem and ~M in case of a maximisation Problem, Revised Solution To obtain a revised simplex tableau, the incoming variable is selected to be the one with the most negative 4 value and the column headed by this variable is called, as before, the key column, The selection of the key row (and the outgoing variable) is done exactly the same way 28 for maximisation problems. Thus, excluding the b;/ay ratios for which a, is zero or negative, we select the row which has the least quotient. Finally, the revised simplex tableau is derived in the same way as discussed earlier. We proceed in this manner unt optimal solution is obtained. In respect of our problem, the initial solution is not feasible and hence not optimal. Here the incoming variable is x» while A, is the outgoing variable. The revised tableau is given in Table 3.11. Ina similar way, we proceed until the optimal solution is obtained. Table 3.13 contains the optimal solution TABLE 3.11 Simplex Tableau 2: Non-optimal Solution Basis x n Ss Ss A a b byfay % 24 25 1 150 0 150 0 96 240 A, M 60* 0 1 a ct 1 2,400 Moe A 40d oO MM Solution 0% Oo 0 2400 4 0 2 -—M oo MM- 2 0Unear Programming Il: Simplex Method @ 85 TABLE 3.12 Simplex Tableau 3: Non-optimal Solution Basis x % Si S Ay Ar by bifay mo 0 1 asso ws 1/150 80 3,000 “40 U 0 60* 1601/60 1/60 402400 — | ¢ 40 24 0 0 M M Solution 40 80 0 0 0 0 5 38 y 0 0 os 375 M+ z Mee Table 3.13 Simplex Tableau 4: Optimal Solution Basis x n Ss & Ay Ab 4, oO ws 1 0 -1/50 0 1/50 144 x 0 60 0 1 -1 <1 1 2,400 9 40 24 0 0 M M Solution 0 144 2,400 0 0 o 4 8/5 0 0 1225 M M- 12/25 Itmay be noted that the solutions given in Tables 3.10 and 3.11 are both infeasible. The solution in Table 3.10 gives x; = 0 and x2 = 0 which violates both the constraints while the solution given in Table 3.11 indicates x; = Oand x2 = 96, that does not satisfy the first constraint. The solution given in Table 3.12 is feasible since there is no artificial variable in the basis but is not optimal while the one in Table 3.13 is optimal (and, of course, feasible). According to the optimal solution, the objective function value is Z=40x0+24x 144 +0 2,400 +0x0+0xM+0xM=% 3,456 The value of S, = 2,400 indicates the surplus phosphate ingredient obtained by buying the least cost mix. Problem with Mixed Constraints Let us consider a problem with mixed constraints. Exampt Solve the following LPP. Maximise 25 2x + 4x Subject to 2x, + Xo $18 3x; + 2x2 2 30 Xq + 2x, = 26 Xs, X20 After introducing the necessary slack, surplus and artificial variables, the augmented problem is given here:8b e Quantitative Techniques in Management Maximise Z= Ix, + xy + OS) + OS, ~ MA, ~ MA, Subject t pe dey tx tS, = 18 3xy + 2p - Sp +A, = 30 xy + 2xy + 26 X15 82, Sis Say Ayn 20 The solution 4s contained in Tables 3.14-3.16. TABLE 3.14 Simplex Tableau 1: Non-optimal Solution Basis x n Ss Ss A Ay by bay s 0 2 1 1 0 18 1 aM 3 2 0 + 1 o 30 3 42s 1 2 0 0 o L 6 be S 2 4 0 0 —M —M Solution 0 0 18 0 30 26 4 aM+2 aM +4 0 M 0 0 L 1 TABLE 3.15 Simplex Tableau 2 Non-optimal Solution Basis n a & Ss 4) A maevay Shae: © 32 0 1 0 =I 108 aM ca 0 o -1 +1 2} 24 12 1 0 0 0 2 13 26 o 2 4 0 0 -M -M Solution ° B 3 ° 4 0 4 2M 0 0 -M 0 -2-2M t TABLE 3.16 Simplex Tableau 3: Optimal Solution — a a Si % A, A & s 0 0 1 34 3/4 va 2 x 1 o ° “un 1 iA a m4 ° L ° uw a4 34 2 6 2 4 0 0 ar 7 Solution 2 2 2 0 A 4 0 ° 0 Gh i ea The optimal solution tothe problems x;=2.and.,=12, $,=2and other Variables = 0. The objective function value is 2x2+4 x 12 = 52.