Chapter 3 Sensitivity Analysis and Parametric Programming of Linear ProgrammingChapter 3 Sensitivity Analysis and Parametric Programming of Linear Programming 3.1 Introduction At the outset, the decision maker outlines the problem: the next phase is to reformulate the problem in such manner that is convenient for analysis. The conventional OR approach for doing this is to construct a mathematical mode! that represents the essence of the problem. Mathematical models are also idealized representations, expressed in terms of mathem: M symbols and expressions. Similarly, the mathematical model of a business problem is the system of equations and related mathematical expression that describe the essence of the problem. Thus if there are different related quantifiable decisions to be made, they are represented as decisions variables, whose respective values are to be determined, The appropriate measure of performance e.g. cost, profit, time is then expressed as a mathematical function of these decisions variables called as objective function, Any restrictions on the values, assigned to these decision variables are mathematically represented by means of inequalities or equalities. Such mathematical expressions representing the restrictions are called constraints. The coefficients of the objective function, constraint equations and right hand side constants are parameters of the model. ‘The most critical and challenging task of the model building process in OR is that of determining the appropriate values to be assigned to the parameters of the model. The success of the model depends on these values largely. In theoretical problems occurring in textbooks the values of the parameters are directly given, but for real life problems determining values of parameters require collection of relevant data, Collecting data for determining parameter values is very difficult task. Hence, values assigned to the parameters often are only rough estimates [32]. Thus, because of the ‘uncertainty about the true value of the parameters, it becomes necessary to analyze how the solution derived from the model would change, if the values assigned to the parameter were changed to other plausible values, While deriving the solution from model, the OR study seeks to find only one solution, which may or may not be required to be optimal. An optimal solution for the ‘original model may be far trom ideal solution for the real problem and hence the need of additional analysis. Such analysis, performed after finding an optimal solution is termed as post optimal analysis or sensitivity analysis, and it forms a very important part of OR 34study. This analysis is also referred as “what if analysis” since. it deals with some such questions, regarding what would happen to the optimal solution, if diferent assumptions, are made regarding future condition. 3.2, What is Sensitivity Analy’ ‘The term sensitivity analysis in Linear Programming refers to analysis of the effect of variations on the important parameters, which includes objective function coefficients, right hand side constants, and technological coefficients of constraint equ problem, is uncertain. The optimal solutions to these LP problems are obtained generally ions. In all LP models, much of the information, which is used in formulating the by Simplex method, which is based on the values of these coefficients, In practice the values of these coefficients are seldom known with absolute certainty, because many of them are functions of some uncontroilable parameters. For example cost of raw ‘materials, resources ete cannot be predicted with certainty before the problem is solved. Hence, the solution of a problem is not complete with the mere determination of the optimal solution. The optimal solutions to LP may be affected with variations in the values of the data coefficients. In order to develop an overall strategy to meet various contingencies, one needs to study how optimal solution will vary with variations in the input coefficients. This type of study for small variations in the input data is termed as sensitivity analysis or post optimality analysis. In short, sensitivity analysis is a technique for examining the effects of changes in model parameters on the optimal solution, 3.2.1 Importance of Identit For a mathematical model with specified values for all its parameters, the 1g Sensitive Parameters sensitive parameters are the parameters whose values cannot be altered without affecting ity analysis in determining those parameters of the model, which are, most critical or the optimal solution. The post optimality study wolves in conducting. sensi sensitive in determining the solution. The importance of identifying sensitive parameter lies in the fact that it helps in identifying such parameters whose values must be assigned with special care to avoid distortion in the output of the model under consideration, Normally, values assigned to the parameters are just an estimate of some quantity whose exact value is known only after the solution is implemented. Hence, identifying sensitive parameters helps in paying special attention to estimating each one ‘more cautiously. One then seeks a solution that remains particularly good one for all the various combinations of likely values of the sensitive parameters. 553.2.2 Aims of Sensitivity Analysis Sensitivity Analysis is an invaluable wol for addressing various managerial issues. Some of important reasons for performing sensitivity analysis are as under, 1) The primary focus of SA is to provide the decision maker with useful and easy to ‘understand managerial information in computationally efficient manner. 2) SA helps in obtaining valuable information regarding alternative course of action in the neighborhood of the optimal solution. Very often, this type of information is, ‘more significant and useful than the optimal solution itself. 3) Output of SA provides a powerful decision support system for the managerial staff. 4). Sensitivity analysis serves as a tool for obtaining information about the bottlenecks and degrees of freedom in the problem. [23] 5) For management science applications using LP models SA may be used to * Determine the responsiveness of the solution to changes or errors in controllable input values used in the model. ‘+ Test the responsiveness of model results, to changes, in uncontrollable inputs and thereby offer valuable information for analyzing the relative risk among alternative courses of action. + Provide systematic guidelines for allocation of scares organizational resources. 6) It increases reliability of model and solution by identifying those parameters that affect objective function value most. 7). Shadow prices in SA provide a mechanism for screening new activities for inclusion, which may not be included in the initial model formulation. It also helps in deciding whether additional resources be obtained and if'so, at what price? 3.3 Fundamental Principles of Sensitivity Analysis Consider LP solution if the following two conditions are satisfied standard form. The solution to LPP is termed as opti 1) The solution xs=B'b> 0, condition of feasibility. 2). The net evaluations corresponding to non basis variables are positive i.e. egbA ~ey9 0, condition of optimality. If the data in the Simplex table satisfies the above conditions then solution is optimal and the corresponding basis B is an optimal basis. Sometimes we have to modify the data in the problem, so itis useful to know how the optimal solution and the optimal basis vary with the changes in the data. For example, the change in values of b can influence the feasibility condition, the change in cost ¢ can influence the optitcondition and the change in the elements of technological matrix A can influence both the conditions. The sensitivity analysis helps in analyzing how these moditications in problem data affect the optimal solution. The basic theory of sensitivity analysis is to inspect whether the two conditions stated above are satisfied even after the change in the problem data and what are the accompanying anges in which these changes are valid. ‘The variations in LPP can be classified as due to parametric changes i.e. changes occurring due to variations in parameters of LPP like cost, resources or the technological coefficients and structural changes which occur due to addition, deletion of variables or constraints, 3.3.1 Sensitivity Analysis of Right Hand Side Terms ‘The Sensitivity Analysis of the optimal basis for the rhs elements determines within which range of rhs element the current of 1 objecti Consider LPP max z=c"x st Ax = b, x20. The right hand side of Ax=b generally wal basis remains optimal and what is the rate of change of the opti function value within the determined interval. represents the amount of resources available, One or more components of the right hand side ie. b can change for various reasons. The impact of these changes on optimal solution is analyzed by carrying out sensitivity analysis w.r.t vector b. The vector b consist of m components say bj,by..--bm Out of m available components of b we consider change only in one component say b,, holding others constant. Let the change ine resource be represented as 6,. While analyzing impact of , questions of interest are 1) What changes if 8, assumes a certain values? 2) What is the region of the values of 8, for which solution remains optimal for given basis? ‘The optimal solution is given by xe=B"b. As the optimal solution involves b, any change in the component of b will affect the optimal solution, As the elements in optimality criterion row are independent of changes in b. they will not change with change in b,. Now, the value of objective function corresponding to the given basis is given by zc'gxp=c'yB'b and hence the objective function value changes as component of b changes, Thus, observe that variation, in the value of r” resource, brings about change in the optimal solution value, which in effect changes the optimal value of the objective function, The criterion row elements or the dual solution remains unchanged, as they are independent of changes in b,. In other wards, the variations in b, influence the primal feasibility of the original optimal solution and the optimal value of objective function.Consider that right hand side term b, changed to b, + 8, and assuming that other problem data remains fixed , then the solution changes according to xa = B“(b+8) where b= (b},b2y---sbr--sbm)! and § =(0.0,... 8.0)", Let By be the element of B" in the i* row and column. ‘The range of 8, in which primal feasibility is maintained is then given by max; (-6)/ Bro) if there exist B,> 0: x= ~« _ifthere does not exist 8, > 0; min, (-b;/ Bi- 0 for all non-basis variables. The variation in the coefficients of objective function may occur due to change in profit or cost of either a basic variable or a non-basic variable. Thus, to determine the ranges of the cost coefficient it is useful to distinguish between cost coefficients associated with basic and non-basic variable. 3.3.2.1 Change in Cost Coefficient of Non-basie Variables Let x; be the non basic variable with objective function coefficient c; with vi n Ace ‘0 find, the range on the values of ¢; such that current optimal solution remains optimal .The change in value of ¢, brings about change in the net evaluation given by z,-C,. For solution, to be optimal we need 2,-¢, > 0 and it is clear that decrease in the value of ¢; has no effect on the present optimal sol . However, an increase in the value of c; beyond a certain limit will lead to violation of optimality. condition, Assuming that all other coefficients except cost coefficient c, remain fixed at their specified values, the interval of values of ¢,, within which basis B remains optimal is provided as 0 < A c < z- c% Where % = cpB™A, Therefore, cy has limits as 0 Sc, < c+ Ac, Further, since 2 = cyXs, is independent ofc, the value of objective function and the optimum solution remain unchanged. 3.3.2.2 Change in Cost Coefficient of Basie Variables Let cer be cost of basis variable xa, in basis set B i.e. cp is the coefficient of basic ovat le Xp, Which is changed to Ca, +Acay. As Cpr is changed, the optimality condition of ‘Simplex method is affected, The change in cost coefficient of basic variable introduces change in net evaluation of all non-basis variabies. Let it be denoted by z= ¢;, and is given by z'- oj = (zj— ¢;) +4 Acr for all non-basis variable and a; denotes element ine” row and j" column in optimal tableau. Thus, when cs, belongs to basis set we observe that change Ac, brings about variation to the amount equal t0 8;Ac, in the net evaluation corresponding to i" non- basis variable. So that optimality condition is maintained , each (z—¢) + Ac,> 0 for J € non basic variable set and thus each net evaluation corresponding to non basis iton Ac,. The ti j" non-basis variable is given by variable imposes a imposed by net evaluation corresponding to (%)- 6) +AgAer> 0 => Ace>-(\- 6) &y for ay >0 all je NB and (-G) + BjAer20 => Ace S-(z)~c))/ fy foray <0, all) ENB 60‘The limiting values for Ac; due to non-basis variables ean be positi , negative depending on sign of a5, Now, so that all net evaluations corresponding to all non basis variables are positive, the value Ac; is chosen as max { -(z)—e))/ aj for&y>0} < Aer 0, jE NB -2 + iFthere do not exist 3,>0 minj-(Z,-¢))/ aj, for yj <0, je NB +0 « if there do not exist <0 © The limits of cr are given by c/ + ¢, Sc, Sc; + ¢;" and the revised value of objective function is given by 2*= z+ xp-* Ac, wherec; < AG Sc," ‘The sensitivity analysis of cost coefficients of basic and non-basic variables is illustrated with example below Ex:3.2 Max z= 3xi+5x2 s.texrtyS1,2x;+3m2S1 and x1,x20 ‘The optimum solution to the given LPP is shown in simplex table below cp | Xp |X x XMS by ots [a [oO YT [3 [23 ~ (23 [1 0 18 | ze [vs [0 0 «(38 [58 Table 3.3.2.2.1 Let us consider cost coefficient of x: with value 3, which does not belong to basis set ‘Hence its range is given by Ac; < 1/3. Hence the range over which ¢ can vary -2$¢)5 10/3, Now, let us consider ca, which belongs to basis set. The range for ¢ is given by f= max {-1/3 /2/3 ,-5/3 / 1/3 ) = -1/2 and 2” = +00 as dy; < 0 do not exist, range over which es can vary isc -1/2 $e: maintaining optimality condition is given by - «0 < cy 0 to satisfy both optimality and feasibility con ions. 3.4.2 Sensitivity Analysis for Right Hand Side Terms It is most common to find the effect of change in value of the k" resource on ‘optimal solution, In this analysis, we find range of rhs values, for change in particular is based on feasibility of optimal basis. Main components are the elements of B'. As B"' is not resource, by ensuring that current basis remains optimal. This analysi directly available in Arsham approach, it is done by perturbing the ths. Therefore, initially the rhs has the form b + r'l where bx is resource value matrix, tx iS perturbed value matrix and Img is identity matrix. The perturbed optimal solution ‘obtained by performing pivoting operations on rhs. The coefficients of the perturbed rhs parameter, r, at optimum table provides B'. While carrying out sensitivity analysis of ths, only one change at a time is allowed ie. k" resource by is allowed to vary holding all other constant .Now to maintain feasibility , the condition b, +pan > 0 for all i should hold, sete -b)/ py for i= | tom. If none of the ry is zero then max -bj/pa forallis.t px >0 allowable decrease n= { “0 if pa > 0 does not exis min - bi/px forall ist. pa <0 allowable increase ny'= { +00 if pix < 0 does not exists 63Fat least one ry = 0 then to check feasibility, find smallest ry > 0 or the largest ny <0. Based on these ideas, Arsham proposed algorithmic procedure for performing sensitivity analysis of rhs terms. 3.4.3 Algorithm for Right Hand Side Terms In case of the rhs elements, the question is, within which range an rhs element can vary so that the current optimal basis stays optimal. Let us consider, only one change at a time in the k resource value say by, the algorithmic steps, due to Arsham[4], for finding the range in which by can vary so that current basis remains optimal are Step 1. ‘Set r;=0 for all i except i=k in all m perturbed equations. Step 2. Find all the n, values by setting by"=0 for i= ! tom Step 3. If the optimal solution is non degenerate ie. none of the n, value is zero and hence a) The allowable increase in. n, denoted by nis given by min{ qln>O} +0 if > 0 donot exist ) The allowable decrease denoted by given by max { ren 0 or the largest ry < 0 and then check the feasibility by substituting <0 oF >0 in given perturbed equations. Now either all feasible points 1,2 0 or, <0 and consequently 8) ifall feasible points r. 0 then allowable decrease is n= 0 and allowable increase n,* is min { %| n>-O} ‘boo if > O does not existb) ifall feasible points r, <0 then allowable decrease is { max {n/n <0} = = ify 0, The problem is reformulated by adding slacks Xs, x4 and rhs is perturbed by adding ry and rp to constraint | and 2 respectively, as Max z= 2x1+ Xp st 3xy¢ Sea Ixy Oy=15 Hn On (6x) + 2xa+ Oxy Ha =24+0rr#1P2 ‘The optimal solution obtained by using Arshams algorithm is shown below xpels [x fb in [re v4 [8 [34 [ia [ae x [1 [0 | =a saa [isa] 112] 528 & [0] o |-12] -704 FA S Table 3.4.3.1 ‘Now all ¢) <0 and thus unique optimum solution is obtained as xy=15/4, x2=3/4 with max 2.=33/4. Now, the perturbed optimal solution for given problei by 3/4 +1/4.r) — 18. 5/4 112.4, $5724. ry ‘Now upper and lower limits for by and b; can be obtained on application of Arshams algorithm, setting b,'=0 for i= 1 and 2. by =3/4 + WAy~ 18s. =0 I ba'= 15/4 -1/12.n) 45/24» =0 u 65To obtain range for bj, set F» = 0 in perturbed equations 1, H obtaining ry=-3 and r)= 45 3 and 0-45 csrange for by is 1I5-+0) 12 6 0 for all i < D and py > 0 for at least one i ¢ D then dual value accompanying the i" constraint can be regarded as positive shadow price ie. ut =5, 3) if py <0 for all i € D and pj <0 for at least one i € D then dual value ‘accompanying the i® constraint can be regarded as negative shadow price = 4) if there exits land k € D st. pj» py <0 then dual value accompanying the i* constraint has no interpretation. In view of this Arshams algorithm for right hand side terms (3.4.3) needs modification in step 4 which is provided as below. Step 4. IF the solution is degenerate i, at least one n= 0 then Case 1: if px=0 forall ¢ Dthen set us, with validity range for shadow price as, n’=min{n| 20} or +0 if, > O does not m= max{n|t\<0} or -co ifn <0 does not exist Case 2: If p20 for all ie D and py.>0 for at least one i ¢ D then set u;*=5, with validity range for positive shadow price as, n=O min (n|1,>0} forall inot ¢ D mK +0 ifn>0donotexist fori note D Case 3: if pa <0 for all i e D and py <0 for at least one i < D then set us, with validity range for negative shadow price as ces for i not < D =~ +2 ifr, < Odo not exits for i not e D 67Case 4 : there exits say 1 Dand q = D st. prepay <0 then there is no interpretation with associated shadow price n= 0 n=0 In non-degenerate case, the dual values simultaneously evaluates a reduetion as well as increase of the accompanying resource and this evaluation hold for a certain . The dual value can thus be interpreted as a shadow price yielding increase/decrease in the optimal value of the interval that contains present rhs value bj in its interi objective function per unit increase /decrease in the value of rhs value. However, when the optimal solution of LP model is degenerate, then there are several optimal basis providing the same optimal value but different optimal bases possibly provides different dual prices and validity ranges [26]. In addition, task of choosing right optimal tableau to gamer vali algorithm which collects the valid information on dual prices and validity range by information also becomes difficult. Knolmayer [25] has presented an considering fraction of all optimal tableaus that can be generated at primal degenerate solution case. The same is presented below, Knolmayers Algorithm 1. Determine the dual variables for which valid values are wanted. 2. Check, the signs of the coefficients in degenerate rows for all variables for which valid values are still missing. Store valid dual values, if all dual values found then stop. 3. Determine the left most column for which valid dual value is missing. If both shadow prices are, missing give priority to determination of negative shadow price. 4. Determine the uppermost coefficient for which the sign is inappropriate for the interpretation desired. Use the corresponding row as pivot row and determine pivot column using dual simplex criterion, Tie is resolved using leftmost column, 5. Execute the dual iteration and go to Step 2. The generation of complete and valid information regarding shadow prices and the ranges as suggested by Koltai and Terlakey [26], is illustrated, using modified Arshams algorithm and Knolmayers algorithm in case of primal degenerate optima. 68Ex:3.4 Max z=100x) + 150x9+ 160x3 st. U2xrtxztas SI slsi Ny S1OQIN;#N2ANG SISV.Xy#NG S100 and x1.x2,X:20 On applicati n of Arshams Push-and-Pull algorithm the optimal solution (primal degenerate) obtained for the example is shown below bysPape pale: [xs [x Pe[ehs [a [a fn [a x [1 fofo] 2]o]2]o] 50 | 2fol2]Jo « [ofoli]2][2]3]o] o [2 ]2]/3[o x [ofofof2]fo/r]it] 0 {2jolift x [o/1fofo [2/2 ]o| 00 | o |2/2]0 0] 00 |-120]-20 | -20] 0 | 20000 | 120 | 20 | 20 Table 3.4.4.1 “The perturbed optimal solution value is, max 2 = 20000 +120.r;+ 20.2 + 20.15 + Oy. The coefficients of r; provide shadow prices corresponding to by, The validity ranges for bi from table 3.4.4.1 is S00} - +09 if ex > 0 do not exist The allowable decrease is given by max {cy' | <0} + of ify’ <0 donot exist proceed to Step 5 Step 4 If.at least one ¢,=0 i.e. solution is degenerate then either all other feasible c,> 0 orall other feasible cy <0. a ifall feasible c > 0 then the allowabk { min {ey |e, > 0} ‘top fey > Odo not exist rease is e 1and the allowable decrease is a0 b. fall feasible <0 then the allowable increase and the allowable decrease is, max {cx | ce <0} -@ if <0 donot exist Step 5. The cost coefficient range for variable x, is lower limit 9) =cx+ 0 upper limit ®= cy + oy” ‘The working of algorithm is illustrated with example Ex:3.5 Consider max z= 2xy+ x2 s.t. 3x) + 5x2 15, 6xy + 2x2< 24 and x),x220. The problem is reformulated by adding slack variables x3, xy and ths is perturbed by adding ry and r. to constraint 1 and 2 respectively as shown under Max z = 2x) + x2 st. 3X) 4 Sxatt 1Xs+ Oxy=15 +14) 40% 6x) + 22+ Oxy +1xy= 24+ Or, try and xy,N2¥5X42 0 ed using Push-and-Pull method applied on coefficient The optimal solution ot matrix as well as perturbed rhs. oe [ox [ee m | [8 x b ~ fo [1 fia [aw [34 x |! fo [-m2 [se [ise s fo fo [-nz |-7s Table 3.4.5.1 Let cy',02,cs'u be the perturbations in cost ¢, for j=1 to 4 respectively .The coefficients of the objective function row for non bsic variables denoted by c’nn are given by c'n = enw —cay BA for each non basic column , here x; and xs are non basie . solving fore’; and c"s yields ©'5= (este3)-1/4(1+02)+ U2 246; y/12 — 02/4 + ey — W120 1Similarly o's=(Otes) - (-1/8)(1402)-5/244 2401 )°0 = S/2de+ c2/8 + c4- 7/24=0 u Equations 1 and Hf are obtained for non b: algorithm for performing sensitivity analysis of cost coefficients ¢) for j =I to4, For e1, variables x3 and xs. Now applying Set €2,63,¢3 each equal to 0 in equation | and II We get ci={1 , -7/5} The allowable increase in ¢, is ¢’= min{cy | c1>0} = I ax {oy}e1-<0}= -7/5 The cost coefficient range for cis given as ‘The allowable decrease in cy is ¢1* lower limit 91= ¢) +e)" =2~ 7/5 = 3/5 upper limit ®, = c+ 0)" = 2+ ‘The cost coefficient range for variable ¢) is 3/5 Sey <3 Forco, set ¢1, ¢3,¢4 each equal to 0 in and Il yielding cy =-1/3 ,¢2= 7/3 jin {cz | 2>0}=7/3 and —_cy*= max {e2|c2<0}=-1/3 sstange for ¢2 2/3 0} =1/12 and ¢y= <0 <. range for variable c3 is 0 <3 < 1/12 For cs , set er, ca’, 6s! each equal to 0 in I and Il yielding The allowable increase in cs is cy" 7/24 The allowable decrease in cs is cs" The cost coefficient range for variable os is -29 Sex <7/24 3.5 Parametric Programming The sensitivity analysis deals in study of effects of variations in the input coefficients when the coefficients are changed one at a time. Parametric programming considers the effects of simultaneous changes in data, where the coefficients change as a function of one parameter and hence it is termed as parametric programming. The parametric programming is simply an extension of sensitivity analysis, In parametric programming, we consider study of rhs and objective function parametric changes. 35.1 Parametric Right Hand Side Problem. ‘The rhs values in LPP represent limits on the available resources and the outputs. It is not necessary that all resources be independent of one another. Parametrie analysis of ris values can be used for situations in which, it may be possible to trade off the 3capacities among the constraints, In real life, we find that shortage of one resource may ead to shortages in other resourees at varying levels. This is true of the outputs as weil, In such problems, we are dealing with simultaneous changes in rhs values as a function of one parameter, and study their effects on the optimal solution. Consider a parametric rhs problem as max z= ex s.. AX=b+ ab” where b is ths vector, b’ the variation vector and a is an unknown parameter. As the value of changes, the values of the rhs constants change. The problem here is to determine the family of optimal solutions for all values of in the range -00 to + 99 The solution strategy involves in solving the given parametric ths LPP for some value, say @=ao, by ustial Simplex method. Now, further computational procedure involves, analysis of feasibility condition, as the parameter ot is changed. By increasing or decreasing value of @, obtain the initial interval as ay 0 min -q/p, for pi <0 © .ifall piso +o if all p=0 “The successive limits beyond cu 0 ax { -qi'p; } for pO yielding -200/3 corresponding to variable x2 and a, = min { -qj/pi } for pi <0 yielding 2 corresponding, for i= 1,23, and to determine limits test o1=1 to variable x6... The range of « for which above solution remain feasible is -200/3 < a = 2 with basic variable values as x2 = 100 +3/2c , xs = 230 ~ 2a, Xo= 20-100.and max z= 1350-7c.. Now as oy and cy are finite , inspect the range of rhs for «> 2. For a> 2, X6=20-100. < 0 and thus solutior infeasible. After deciding outgoing variable, check whether -ve value exists in row corresponding Xo, if it is not then infeasibility cannot be removed and hence solution to given LPP is infeasible beyond @ > 2. Ifat least one ve 15value exists in xq row .then select incoming vector by use of dual simplex criterion, as X= -2 is —ve incoming vector in place of xs is given by ming (2) ~ )/Xaj } = -1/2 which corresponds to x; and hence x, enters in place of xs, The pivot element for intable 3.5.1.2 obtaining new tableau is x6s ~-2 marked as ~ 6 dS 2 0 yo fo oly |e Pp x x [x [x Ne 2 |e [io [st w [i fo fo fo fw 3 [xu [a0 [2 o [i fo |i fo 0 [x |-l0 [5 0 fo |i |-2 faa 1360 [-Re [5 o |o jo |s2 |r Table 3.5.1.3 The limits of « for which xp; is feasible is given by a= 2 and ay 1S. and hence the range of feasibility for a is 2 105 gives feasibility for some change of basis. In this case variable x» becomes infeasible, but the row corresponding to it does not contain a negative element and hence dual simplex criterion fails to determine variable that replaces x2 and thus, for a>105 no feasible solution exists which ends the search on right of. Now investigate feasibility to the left of -200/3 0} oe 2 if p> Odo not exist Step 4 ifat least one a= 0 Let D be the set of index s.t. B' b +a Bb" =0 => D={ b= 0). The following cases ean arise ie. by (@) If pz 0 fori ¢ D and at least one p,>0 fori ¢ D then seta” =0 and min {ast pi> 0} for inote D +0 if pj>0 do not exist fori not € D (b) If p,<0 for ie D and pi<0 for at least one i € D then seta” =0 and max { SA. p,<0} fori not € D 7 x0 if p; <0 do not exist for i not « D Step 5 Determine whether to continue search Case (a) if a= +00 then search on rhs ends Case (b) if «°=-co then search on ths ends ‘The working of algorithm is illustrated with example Ex:3.7 Max z= 3x, +2x9 + 5xp st xj #2n2 +Ns $430 4x 3x1 HOx2 42x) < 460 - doe xi Hx 0x3 $420-da— and x20 ‘The problem is solved using Push-and-Pull algorithm, with optimal table as under bs [x "taal x [xs bon de [a = [14 |1 [0 im |-1@ [0 [10 [ip [aa ]o = (32 [0 [1 |o |i |o [230 Jo im Jo % [2 (0 [ozo ]1 T (20 [2 |1 fr 6 [4 |e |o [7 |2 Jo ‘Table 3.5.2.1 8 10043/20-0 X3= 23040 a H1/2A(-da)1O(-4ex) => 230-200 X= 20-20 +1(4o)+1(-4a) => 20-10. a=0 thus pr= 3/2, pp=-2 , pp=-10 and a values from above equations as -200/3, 115, 2 which are all non zero. «+ the maximum + ve step size in «is o ins st. p< 0} = min{15,2} =2 , which corresponds to variable xs -+ the maximum - ve step size in ais i> 0} = min{-200/3} =-200/3 . wi a= mines corresponds to variable x» the range of a for which above solution remains fe basic variable values as x2= 100 + 3/20 , x; 230 - 2a. , xs= 20-100 and the objective le is -200/3 < a <2 with the function value max z=1350-7ce, As a” and ot are finite, investigate feasibility on both sides. Let us start with ths first. Now, for o < -200/3, the variable x2 becomes negative ite x2 becomes infeasible, This infeasibi criterion by replacing x2 with a variable which has min{¢i/ i), ¢s/&js} = 8. This ean be removed by use of dual simplex minimum corresponds to variable xs, “. xs enters in place of xz with a1 = -1/4 as pivot element. bs [x [a [x [xe [xs [x n |e [pe Xs ryafojy2t. 0 [-400 7, -2/7 [oO % 7 2 v 0 | 40, 1 fo fo Xs T 4 V7 420 [of o 2 [sf o 7 4 SXs=400-2r HHO 400-60 = 0 X= 4304 HOH > — -430r0 = 0 3.5.21 No= 42040ry+0r2+Ly=> npFrom 3.5.2.1 we obtain « ={-200/3,-430.105} and pi=-6, p= 1, p= -4, As a values are non zero we have a= min{ ass.t. pj < 0}= min{-200/3,105} c= max {0 st, pi >0} = max{-430}= -430 which corresponds to variable x3. -200/3 which corresponds to variable xs. “The range for which above solution remains feasible is -430 < c < -200/3 with the basic variable value as xs = -400 - 6a, x3 430 + a, Xs = 420- da and max z= 2150+ Sa. As ct range has finite values, proceed further to investigate for a <-430, Now, for o <-430 variable x; becomes —ve ie. infeasible, and hence x3 can be removed from the basis, but row corresponding to variable x;, in table 3.5.2.2 do not contain a negative clement .ie, aj > 0 for j = 1,2,6. Thus, for range -2 2 by making basis change in table 3.5.2.1. Now for value a > 2, Xs <0 i.e. xe attains negative value and thus variable xg moves out of basis. The replacement of xg is replaced by xy and hence xq enters the basis with ay = -2 as pivot element, resulting in new basis solution shown. in table 3.5.2.3 bs [x |e [es |e |x nye |e ~ [i fi fo jo fo oo [im at cil % [32 fo |1 |o in diz fo = [1 fo jo | |-2 T | -02 |-072 3s fo 0 [3 Table 3.5.2.3 X2=105+0r;+0r+ W/4r=105-lae =0 39230407, +1/2r2+0r5=230-20 <0 Xe LOH F-L/2ry 1/2 =10+Sa=0 From 3.5.2.2 geta= (105, 115, 2}. As none of the a is zero min { s.t. p, <0} = 105 a= max { st. p> 0}=2 The above solution is feasible for the range of « as 2 105. For a >105 . variable x» becomes negative , but also observe that row corresponding to variable x3 in ‘Tyo has all Positive elements , therefore, have infeasible solution beyond a> 105. Range of a ‘Optimal Solution Opsimal Objective finction 1[-« 0, then the given solution is the optimal solution for any % © (2), Au] where hy, 2y are determined as max -0j /B; for B> 0 min -a /B, for B;< 0 l <0 ifallpj 0 ‘The procedure is terminated if 4 for <0 then is known from the simplex entering vector criterion that problem has no “00, hy=too, Now assume that 2, is finite, on / Bx maximum for > dy and hence stop. Ifat least one xi. > 0, then, we introduce variable xx into the basis and remove variable x; using the usual simplex outgoing variable criterion. Thus, it is possible to investigate systematically and solve the one parameter objective 81