programming = Hl ipcar PFO , Chapter 4 Linear Programming - III (Simplex Method) Introduction Simplex Method special Cases in Simplex Solved Problems Minimization Duality Problems involving Mixed Constraints More Special Cases in Simplex 9 Simplex Case Studies 4.10 Sensitivity Analysis Concept Questions Exercise apter 3 we have seen how to solve a LPP by graphical method. hical method, we first formulate the problem and then we ent the constraint lines on graph. From the constraint lines, we find the Feasible region of solution. The optimal solution is at one of the corners of the Feasible region. raphical method can be used only for a two variable problem (Xi: &X). br Another method of solving a LPP is simplex method. Simplex : thod is an iterative method, It involves a number of iterations ofOperations Research (8Ms) 70 " implex algorithm. It is a step by step eee from one feasity simplex a } ‘ : i Sion to another until we reach optima se s a It means, in simplex method we keep.on improving the SOlinti means, every step and finally reach optimal solution. 4.2 SIMPLEX METHOD: Maximization: Example 1: ve Max. Z = 100 X; + 80 Xz Subject to constraints: 6X1 + 4X2 $7200 2X, +4X2 < 4000 «+ Resource II», Xi, X2 20, Find optimal solution by simplex method. Solution: 3 Now we will see each step of simplex method in detail: Step 1: Formulation of LPP If the formulation is not given, the LPP formulation. In the above example, we should convert the given d the LPP formulation is given. Max.Z = 100X, +80X, Subject to constraints: 6X1+4X2 < 7200 2X1+4X2 < 4000 Step 2: Converting the LPP formulation in standard form. Standard form me ; ‘ans introducing slack variables in the formulation, eas Slack Variable: A sk V jack vari source. Slack vari; lable is repres ©; Our Ist constraint ig —> OX 44%) < 7209 It means able represenis unutilized capacity iented by ‘S', (Si, Sp ete). ae «+» Resource! 5 re source Thas Capacity of 7200 units, alter’ production, som i a, WE ey MY le capaci rey ins i “ ee represented by slack variable § pe eee — Heng ©, NOW We ¢ 6X1 44X24, On write Constraint 1 . as: 7200)sar Programming «Il 3 n This means out of 7200 units available of resource I, (6 eve for production and 51 is the unutilized capacity, tase ‘apacity, ifany Same way, we can write the 2™ constraint as — 9X1 + 4X2 +S2 = 4000 : the unutili ed capaci Where 5 Since Si and Sz are slack variables (which represent unutilized bacity of resources), their profit coefficient is zero. , ty of 2nd resource, if any gndard form: Objective function: Max. Z = 100X; + 80X2 + 0S; + 0S; Subject to constraints: 6X1 +4X2+S1 = 7200 2X1 + 4X2+S2 = 4000 Xt, Xa, Sy S 20 sp 3: Writing 1* simplex table (Initial Basic Feasible Solution) The structure of simplex table is as given below: Table 4.1 Replacement Xi Xz St Se Ratio Row 1 Row2 4=G-% In our standard form, we have 4 variables Xi, X2, Si, S2. Hence, we have 4 columns for Xi, X2, Si, S2- Similarly there are 2 constraints, the constraints. _ ‘Basis’ contains 3 columns; c, X & b. x =basis variables (variables present in the basis) b =solution values or quantity of basis variables. . ¢ =contribution or profit of basis variables. C) Row: The row in simplex table which represents -contribution of each variable in the objective function. Fe Row: The row in simplex table which represents the di “the value of the objective function, if 1 unit of that v ‘brought in the solution. hence, we have two rows for profit or jecrease in ariable isOperations Research (Ms) (ey (5) (A=Cj-Z)) Row: The row in simplex table which represents they increase in the objective function, if 1 unit of that variable is broughy : in the solution. a y Hence, positive value of A indicates gain or increase in profit and iicates decrease in profit or loss, a 72 negative value of A ind ‘a’ is pronounced as ‘delta’. Test of optimality in simplex: : A simplex solution is optimal when there is no posit A (Cj Z) value in the solution. All A values are either negative zero. (6) Key column (Incoming variable): The variable which has maximum positive (Cj - Zj) value, called incoming variable for next table. In the next simplex table, this variable will enter the basis and will replace one of the existing basis variables. Key column => Max. + | (7) Key Row (Outgoing variable): The variable which goes out of the solution in the next table. It teplaced by incoming variable in the basis. 3 To find Key Row, we need to find replacement ratios for all b variables. The formula of replacement ratio is (b column) + (key column). Rati b ©=KC| [Key Row = Min. + Ratio Initial Basic Feasible Solution: = Table 4.2 : 100 | 80/50 0] Replacement Se Si S Ratio 4 1 0 4 0 1 a . variables are always slack variables, iy sc tPe Solution) the basis V2" i activity (X: = 0, X2 = 0). Hence oy ue that there is no proovs “a Capacity is unutilized.:. ° X* column is $15),programming - ar POE Constraints: 6X1 + 4X2 + [Ss 2X1 + 4X2 + ince all capacities are unutilized, hence $1 = 7200 and S2 = 4000. Hence, the ‘D’ column values are 7200 and 4000. profit of slack variables is zero, hence ‘C’ column is 0,0. The Cj Row is written as per objective function. Max. Z = 100X; + 80X2 + 0S; + 0Sz Hence, Cj row values are 100, 80, 0, 0. 4s constraint is: 6X14 4X2 41S; = 7200 Hence, coefficients of X1, Xz, Si, Sz are 6, 4, 1, 0 (Values in Ist | 2r constraint is: 2X1 + 4X2 +S2 = 4000 Hence, coefficients of X1, Xz, ‘Si, S2 are 2, 4, 0, 1 (values in 2nd | row). Initial Basic Feasible Solution (continued): Table 4.3 Go 100 | 80 0 0 | Replacement x | ov |fx]] x | ss | & Ratio s, |Lz200 | T6 4 1 0 | 7200/6 =1200]} > S | 4000 | | 2 4 0 4000/2 = 2000 Z> 0 0 0 0 A=G-Z-> 100} | 80 | 0 0 i "Calculation for Z; Row: j= {'C’ column] x [Each Variable column] For X; :(0 x 6) + (0x 2)=0 For X2:(0 x 4) + (0x 4) =0 For; : (0.x 1) + (0x0) =0 For Sz: (0x 0) + (0x 1) =I} ow opeatbeseis (g) Calculation for (4 = C)~Z;) Row: From the Cj value of each column, subtract Zj value. Sof X; =100-0=100 Sof X: =80-0=80 Sof S; =0-0=0 Sof S =0-0=0 After calculating all 4 values, we can see that value is for variable Xr, raxisnum Hence, It means in next simplex table, X; will enter the solution. () Calculation for Replacement Ratio: 1 a PD olumn Replacement ratio =~ o Hence, RR for RRin Minicom positive ratio is 120), forS_ * simetiex date HiMES ee “Yayyming «Hl - prontl igimptex Table (continued): ____ Table 4.5 | 100 |[ 80 0 07 b/X | | Xf % 5 & re 1 wall ive | o | 180 | 0 | 873" |] -1/3 | 1 00> 100 |{200/3]| 50/3 | 0 Zo 0 |L4or3}} -50/3| 9 t of New values for 2"4 Table: Calculations Iues for key Row: ulation: New va Old Values New values = Key Element| To find new values, we divide old values by key element. Our key row for 1st Table =S Our key element for Ist Table = 6 Old values of $1 _, 7200.6 4 10 Key element = 6 E New values (7200/6 = 1200, 6/6=1, These are the new values for X Because X: has replaced Si. calculation: New values for No calc = 1200, 1, 2/3, 1/6, 0 4/6 =2/3, 1/6=1/6, 0/6 =0) | 1 LOW. n-key row. ‘Corresponding key New values = old values — Column value x New values of Ke Our Non-key row is Sz For Sa, Corresponding key column value = 2 «(in Table 43) /, New values of Sz = dvatis - {"Ketvaoe Nae 4000 — (2*1200) = 1600 2 = (291) 0 4 57 (2:x2/9): Operations Research (g 0 - (2x1/6) =-1/3 1 - (2x0) =1 Hence, new values for S; row are = 1600, 0, 8/3, -1/3, 1 Calculation of Z): for Xx (100 x 1) + (0x 0) = 100 for Xa (100 x 2/3) + (0 x 8/3) = 200/3 for Si: (100 x 1/6) + (0 x - 1/3) = 100/6 = 50/3 for Sx (100 x 0)+(0x1)=0 Calculation of A: ForX: :100-100 =0 For Xz :80-200/3 = 40/3 ForS; :0-50/3 =-50/3 ForS: :0-0 =0 Key column: Max. + A’= 40/3 —<———— :. [Key column =x beolumn bb Replacement Ratio = Key column = x9 : 12 Ratio for X; = Fe 12003 = 1800 7 1600 3 Ratio forS; = 8/3 = 1600 xg = 600 Key Row: — Min. +Ratio = 600 -. [KeyRow = 5, Key Element = Intersection of w& S2= 8/3) 34 Simplex Table: Table 4.6 Go 100 | 80 [0 | 0 | Replaceme c x bt x De Ts Sr Ratio 100 xX 80 Now the ba (Xz replaces $;) iS vari ables in 3 Simplex table will be Xi a The corresponding ‘c’ values are “199° foy X1 and '80' for Xetil jamming prow ear jmplex Table (continued): 4 simple’ Table 4.7 100. [8 [0 | oT MSIEX Es lms, 1] 0 | 4-44 Oo | 1 [=i TES <| y> 100 [80 [15 175 4=G-4> 0 0 | -i5 | —5 Calculations of New values for 3 Table: ) New values for Key Row: (© (For Xz, because Xz has replaced $:) _ Old values (of S:) New values =""Key Element 1600 0 8/3 -1/3.1 New values =" g73 = (1600 0 8/3 -1/3 1)x3/8 = 600, 0, 1, -1/8, 3/8 These are new values of Xz row. (2) New values for Non-key Row (X;): Corresponding _ New values} Old values." { KC. value * of Key Fe 1200 — (2/3 600) = 800 1 = (2/30) 1 2/3 - (2/3%1) =0 1/6 — (2/3x-1/8) = 1/4 0 = °(2/3«3/8) =-1/4 For Xi corresponding key column valtie = 2/3 New values of X; are - 800, 1, 0, 1/4, -1/4 Calculation of Z;: for X: (100 x 1) + (80 x 0) = 100 for Xz: (100 x 0) + (80 x 1) = 80 for Si: (100 x 1/4) + (80 x- 1/8) = 15 for “Se: (100 x — 1/4) + (80 x 3/8) =5 Calculation of A: ForX; : 100-100 =0 ForX. : 80-80 =078 Fors; : 0-15 =-15 For S2 0-5 =-5 4 : = All G,- Z; values are either zero or negative. There is no positive 4. Hence, solution is optimal. Optimal Solution: Optimal product mix: (‘b’ values) P Pa X= No.of units of A = 800 X= No. of units of B = 600 Optimal profit: (‘C’ x ‘b’ values) 2 Max. Z = (100 x 800) + (80 x,600) = Rs. 128,000 Note: (1) ‘Optimal Product Mix’ means the solution values ie. quanti values of variables. quantity values are always zero. Si and Sz are not in the basis. 2 Hence, S; and S2 are non-basis variables. ©. S:=OandS:=0. (2) ‘Optimal Profit’ can be calculated by multiplying the quanti values of basis variables (‘b’ column) by their respective Pp! coefficients (‘C’ column). <. Optimal Profit = ‘C’ column x ‘b’ column (3) Concept of Shadow price of resources: Shadow price of resource means value of one extra unit ° resource. It is the maximum price the company should pay ! procuring extra resources from market. It also indicates profitabill! or profit contribution of each resource (per unit). Shadow price = ‘Z/’ value of slack variables In the above example, Z value of S = 15 Z, value of S2=5 : S; is slack of Resource Land $2 is slack of Resour Shadow price of Resource T= Rg 15/unit : Shadow price of Resource = Rs. S/oar Programming, Il ine? Availability of Resource 1 is 7200 units Hence, profit generated by Resource { = Availability of Resource II is 4000 units Hence, profit generated by Resource ff = . Total profit = 108,000 + 20000 ait Gator were This corresponds with our Optimal profit calcul solution. 7200 «15 = Rs 108,000 lated in Optimal -xample 2: Padma Ltd. makes three different kinds of chairs. All can b rofitably in this company, but the company’s monthly fad Sine nstrained by the limited amount of labour, wood and ae A rable ach month. The director will choosé the combination of cing ae ximize his’ revenue in view of the information given in the following ible: Input ‘Arm Chair | Executive | Officer | Monthly Chair Chair Availability bour (hours) 12 7 9 1260 food (Board feets) 22 18 16 19008 ww (kg) 2 4 3 396 ling Price (in Rs.) 4000 2000 5000 Formulate the above problem as a linear programming problem and” Ive it by Simplex Method. . (MU, Oct. 2004) olution: P formulation: ~ Let X; = No. of Arm chairs X2 = No. of Executive chairs X3 = No. of Officer chairs Max. Z = 4000X: + 2000X2 + 5000Xs Subject to constraints: , 12X, + 7X2 + 9X3 < 1260 ..- labour 22X; + 18X2 + 16X3 < 19008 «+. wood 2X1 +4X2+3X3 < 396 scews X1, Xz, X32 0 dard form: ‘Adding one slack variable in each constraint: 4 Max. Z = 4000X1 + 2000X2 + 5000Xa + 051 Subject to constraints: +052 + OSs80 22X1 + 18X2 + 16X3 + [Sz = 19008) | ee Xa, X2, Xa, Si, S2, $3, = 0 Initial Basic Feasible Solution: + 12X1 + 7X2 + 9X + [Si = 1260 2X1 + 4X2 + 3X3 + ($3 = 396 In the 1* SimpleX Table, basis variables will be slack variab (Si, Sa, Ss). i Table 4.8 Go 4000 | 2000 | 5000 | 0 | o Co] Xe | be [exis Raga aa sleeer hg: ae se ec 9 1 0 © | S& | 19008] \ 22 [ys [a6 0 1 i ee | 4 [3° 0 0 uo 0 0 0 0 0 A=G-Z> 4000 | 2000 | [5000] | 9 i t Z calculation: ‘C’ column x ‘variable’ column for X: (012) + 0x22) + 0x2) =9 for Xar x7) + 0x18) 4(0x4)=9 for Xa: x9) + (0x16) + (0x3) =9 for Si: x1) +0x0)+(0x0)=9 for Sx 0x0) +0x1)+@x0)=9 for Sx: 00) +x0)+0x1)=9 Max. positive G-Z =s000 «- [Key Column =x, . | Replacement ratio =-Beolumn ey column = 3g Min. positive ratio = 132, [Key Row =S. Key Element = Intersection Of Xs & Sy . [Key Element = 3programming = Il amplex Table: lew values for Non-key Rows: For Si: : Corresponding key column value = 9 New values = 1260 - (9132) =72 12 ey (9'x2/3) =6 yf - (9x4/3) =-5 9. - (9x1) =0 a! - (9x0) =1 0 = (9x0) =0 0 - (9x1/3) =-3 for Sa: Corresponding key column value = 16 8 4 -9 0 0 1 |8/4=2 0 0 0 0 0 9 4 0 0 0 7 Key Column = X1Operations Resear 86 2nd Simplex Table: wuideD o> Side fed © xa ve fon | men iase 0 fis, @ 0 2 1 fe Po — ot fatto ols to 0 |f-10]] 0 | ZS 9 |\ova}] 0 t «6-4 0 — 0 | -9/4 ‘ote: This Table is also Degenerate because in ‘B’ colui =0} : Table 4.13 9 4 0 0 0 Xr X Sr S Sa 0 7 1/2 | -1/2 0 1 0 -V/8 | 3/8 0 0 0 5 -6 14 9 4 | 7s | uss | 0 - ~ i | 9 7/8 |-11/8] 0. No positive 4A Optimal Solution Note: There 's no Degeneracy in the e is zero, optimal solutionopramming Ml =A Product Mix: e the following Linear Programming problem by simplex Max. Z = 3X1 +5X2 1+2X2+Xs = 12 {>, Xs, Xa, Xs 2 0 degeneracy occur in this problem? (MU, Apr. 2003) fon: problem is already in standard form. In each constraint, there is ‘a variable whose profit contribution is zero. ‘can rewrite the problem as: dard form: Max. Z = 3X1+5X2+ 0X3 + OXs + OXs ject to > Xi+[G_=4 X2+ [Xi_=6 3X1 +2X2+[Xs_= 12 1, X2, X3,X4,Xs5_ =O & Xsare slack variables. the 1s Simplex Table, basis variables will be Xs, Xa and Xs.Mperations Research (p 88 ast Simplex Table: Table 4.14 Go 3 : f fa x b Xi X2| | Xs 0 ae ere [3 0 oF 6 0 1 0 0 Doe | Baz 3 Ze 0 Z- 0 0 0 A=G-Z> 3 5 0 + Key Column = Xz s _ There is a tie in Replacement ratio for Minimum positive ratio. Note: , This is a case of degeneracy in simplex. Degeneracy in simplex means for 1 incoming outgoing variables. select the key Row for which key element is higher. Hence, we will select Xs as key Row as its Key Key Row = xs Key Element = 2 24 Simplex Table: . Table 4.15 Goi 3 5 0 0 cS x b xX RG X3 X oes 0 1 0 2 0 0 1 5 at 0 0 5 0 0 [i el 0 No positive 4 value All C,- Z values are either zero or negative, Hence, solution is optimal.amming ror a - pgenerale solution. There is degeneracy in the solution a de f basis variables (X1) has quantity value (b) of zero. ype . X. =4 X =0 X =6 Max. Z =(0*4) + (00) +(5 +6) | profit opti ee nace mneracy in simplex occurs in any one of the following conditions: There is a tie in Minimum positive replacement ratios, OR p) There is a zero value in the quantity (b) column. ecial Case: Alternate Optimal Solution in Simplex mple 5: solve thod. jote: Dege he following Linear Programming problem by simplex Max. Z =3X1 + 2X2 + 5X3 “Subject to : Xi +2X2+2X%3 <8 3X1 +2X2+ 6X3 = 12 2X, +3X2+ 4X3 S12 Xi, X2,X3_ 20 Identify alternate optimal solution, if any. (MU, Oct. 2005) _ Max. Z = 3X1 + 2X2 + 5X3 + 051 + 0S2 + OSs ubject to : X1+2X2.+2X3+[Si =8 3X1 + 2X2 + 6X3 +[S, = 12) 2X1 + 3X24 4X34[S3_ =12, Xu Xa, Xs, Si, S23 = 090 4 Simplex Table: Table 4.16 Tg 2 5 0 0 C- Lae |e |e ol 1 2 2 o o |S 8 == [eto as (oe 2 te 4 peel cena] 2 2 ‘ 2 f as 0 0 0 0 0 GLAS 3 2. 5 0 0 Tis Key Column = X3 KeyRow . =& Key Element = 6 24 Simplex Table: : Table 4.17 Go 3 2 5 0 0 c | x | be] & | eee Ss | & {0 Ss 4 0 || 4/3 | 0 1 | -1/3, [3 |» Le hata ea 0 | 1/6 | o | s | 4 o.|| 5/3 | 0 0 |-2/3 | Zo 5/2 5/3 5 0 5/6 4=G-Z> 1/2\| 1/3] 0 0 |-5/6 T ao ae Key Column =X, Key Row =X [Key Element _=1/2 314 Simplex Table: — Table 4,18 2 | Bee [a0 X Xs 4/3 2/3. 5/3 ae3 ning - " prow ine F Ave 1 Cj — Z value: nositive A. Al j Values are either zero 6 ptimal. F negative. Hence: niso y tion: = imal solu opt can xX: =4 S =4 Max. Z =(0x4) + (3x4) + (0x4 jn the optimal solution, X2 is a non-basis variable. A value for X:=0. E asis variable has A = 0 in opti oa en any non basis varia enero Bera Wher jternate optimal solution, ptimal solution, it means ore is A zi find alternate optimal solution: wwe write 3° simplex Table (i.e. Optimal Table) again. A of X: = 0. Hence, it means X2 can enter the solution while retaining the same max. Z(optimal profit). " Table 4.19 3 2 5 0 0 0 xX X2 X3 Si Se Ss RR. 0 II 4/3 0 1 ]-1/3| 0 1 |] 2/3} |. 2 o | 1/3 | 0 6 0 5/3*|| 0 oO [-2/3] 1 |) 12/5=24> 3 2 [te 0." | [sooo] 50 | 1400 t Key Column =i KeyRow =i Key Element _=200 264 Simplex Table: Table 4.37 Go 4000 | 50 | 1400 e |x] > | m ] y | ys 4000 | y, | 1/50} 1 | 1/200 }[ 1/5 9 S 1 0 {3/2 {| 20" Z> 4000 | 20 |} 800 4=G-Z> 0 30 600 t Key Column = Key Row Key Element = 3¢ Simplex Table: Table 4.38 So 4000 | 50 [ 1400] 0 0 cf x [by Py Py Ps | & pesooon ey a 1 [Fnoo| 0 | avi00 |=1/100 | 1400 | _ys J 1/20) 0 | 3/ao [a [-1/a0] 1/20 =e ass wo [CS a) Aso a> 1-5 | o | -s5 [| -30pomnming Ml 2 105 aitive A. AUC) = Z values are ¢ te sare either zero ¢ 4 is optimal zero or negative. Hence, Solution: i : X; = Shadow price of S) = 5 units Hunits of product A = 5 F X2 = Shadow price of S) = 30 units nits of product B = 30 Min. Z = 4X1 43X2 = (4 «5) + (3 x 30) nal Cost = Rs. 110 ff; Artificial variable method (Big M Method) fg method, we directly write the standard form for the ation problem without converting it in Dual. tandard form, we introduce surplus variable and artificial Bjus variable: It is a variable subtracted from the LHS of a ‘>’ fat to convert it into equality. Hcial variable: It is a variable added to the LHS of 2 “2’ Bat to convert it into equality. This is in addition to surplus 4100X2 = 4000 X1+2X%2_ = 50 2 (0X) +40X2 = 1400 form: Min, Z = 4X1 +3X2-+ 0S1 + 0S2 + 0S3 + MAx + MA2+ MAs to: 2001 + 100X2— Si + | At | 1X +2X2-S2+[Az_=50 | 40X; + 40X2~ $a + [As_= 1400 ion is ‘M’ for Coefficient of Artificial variable in objective functi tion problem. (M stands for infinity). : variables for 1% Simplex Table will be Artificial Variables As) a ERR =Operati é Ba ps att Research ang ble method, Test of optimality is All C,~ o Artificial varial A i j In tive. Key column is that variable for whi be either zero or positive value is maximum negative. This concept is exactly opp’ Other calculations such as in the same manner. osite of Maximization method. — Z, C- Zand Replacement Ratio a 4s Simplex Table: Table 4.39 G7 4 3.].0 |} 0} 0}M]M ii clx]b | x | x | S| S| Ss | Ar] Az [As m | Ar [Roo [aor [woo [-To To fit 3 ie lf | IL 2, | 0: (si or | 0. | 2 m | As |1400|/ 40 |] 40 | o | 0 | -2] 0 | o. ZO 241M]| 142M |-M]|-M|-M]| M M a=G-g> |f4-|[3- | mM] mM |My] o] 0 |241M|| 142M. 5 - aot X1 = (M x 200) + (M x 1) + (M x 40) = 241M G-Zof X: =4-241M Zot Xo =(M x 100) + (M x2) + (M x 40) = 142M G- Gof X. =3-142M = Max. Negative Cj-Z; =4-241M {-241M>-— 142M} . [Key Column =X Key Row = Ai Key Element = 200] Since, A1 goes out, from n : eu " ext T: late values for Ay. ‘able, we need not calcul "i {Note: Any Artificial variable, once it goes out of the solution, enters again.}407 Table 4.40 0 0 0 M Mi|M RR s ~ 7 | _ al) S» Sa AY Ad Aa ee 4 -1/200] 0 | 0 o|o | #0 | ee eee ee ee et 1/200 | -1 | 0 1 {0 ]|20-| 7s | 0 | 1 ~o | a | 20 | _i [-M|-M uM{[ Ml 50 I 41M *°200 | cee |e eM 0 | a 50 5 aL | 200M J Key Column = X2 (Max. Negative Value) Key Row 2 Key Element 5/2. out, values for column of Az need not be calculated Table 4.41 a] 73%| 0 0) cine aaa | MUM. ER x )x] s | & | S| a] & | & 7 {0 |-s1solf 173 |] © 0 | 30 o | 1 | 1/300|/-2/3|| 0 0 | -30 a toot 27s [oval =) 1 |b aT 3 | 2 | 2. | M M ac0m eid : 2m | 40M seein | ORE * roam meee M 0 oo | 35 2M | 40M 1 | 3 I ie - Key Column = 52 (Max. Negative value) Key Row Aa [Key Element = 40/3 see108 Since As goes out, from 4! Simplex Table values for column 6 need not be calculated. a 4% Simplex Table: Table 4.42 eS 4° [73> |Fco 0 iS x b | xX | %& Si S 4 X_ | 5 1 0 |-1/100] 0 3 X2_| 30 0 1_|1/100| 0 o |S | 15 | 0 0 {1/100} 1 Zo 4 [| 3 [-1/00] 0 a=q-Z> | 0 | 0 [1/100] 0 | 1/20 No negative 4. All CG; — Z; values are either zero or positive. He solution is optimal. Optimal Solution: X =5 X. =30 S =15 3 Min.Z = (4x5) + (8x30) + (0x15) : Optimal Cost_=Rs. 110 Example 12: Solve the following Minimization LPP by simplex method. Min.Z = 25X: +30Xe Subject to: 4X1 4+3X2 = 60 2X1 +3X2 = 36 XX. 20 Solution: We’ will solve the LPP fi a pa ekelech first by Dual method and then by Arfilicl® Solution by both methods is given only for understanding PUP ()_ ‘Simplex of Dual’ Method: Min. Max Z* Subject to: Subject to: 4X, + 3X2 = 60 4yr+2y2 $25 2X) + 3X2 “Standard Form of Dual Max. Z! = 60y1 + 36y2 +05, 4 0S;ming 60. 36 0 0 Tt Key Column =yi KeyRow = =S1 Key Element _=4 Table 4.44 60 36 0 0 RR. b yi yz Sr Sr 25/4 1 1/2 V4 0 50/4 45/4 0 3/2* || -3/4 1 15/24 60 30 15 0 0 6 -15 0 Tt Key Column = y2 KeyRow = Sz Key Element_=3/2 Table 4.45 60. 36 0 0 RR. b yi y2 Si Sz 10/4 1 0 1/2_| -1/3 15/2 0 uy -1/2 | 2/3 60 36 12, 4 0 0 -12 =a [TC- Operations Research (8 No positive A. All C - Zj values are either zero or negative solution is optimal. Optimal Solution: Xi = Shadow price of S; = X2 = Shadow price of S2=4 Min. Z = 25X1 + 30X2 = (25 x 12) + (30 + 4) = 420 : Optimal Cost_= Rs. 420 ee—_ . Operations hese W : CH any alues are either zero iy No positive A, ALG: Z, values are e! her ZeFO OF Negatiy, olution iS optimal Hen, Optimal a : . Shadow price of Sy = 12 uy = Shadow price of S 4 Min. Z 2 25X1 + 30X2 95 x 12) + (30 +4) = 420 Optimal Cost 9.420 (ip Arti cial | Variable Method: Standard Form: Min. (Big M Method) = 25X1 + 30X2 + O51 + 0S2 + MAi + MA; Subject to: i 43X51 + [= 0) 2X + 3X2- S2 + Az = 36 1# Simplex Table: Table 4.46 Basis variables for 1* Simplex Table will be Ai & Az. Go 25 | 30 | 9 o |] M| M4] RR _ x b Xr X2 Si So Ar Ad M AL 60 cu 3 =1 i} : 0 b- M Ar 36 2 3 0 -1 0 1 18 Zo on || 6M -M | -M M M A=G-Z> 25-|| 30- | M | M 0 0 6M || 6M. =a, — Key Column =X; (Max. Negative Value) Key Row =Ai Key Element =4 As A; goes out, from next table we need not calculate column values for Ai.snoar Programming «It v ~ simplex Table: 111 Tablesa7 x — se teh ee b | x | » aa 3+ Simplex Table: As Ao goes out, from next for Az. Table 4.48 table we need not calculate column values Key Column =X: Key Row Key Element = 3/2 =A; Go 25 | 30 0 0 M [™M [RR] ic x |b x X Ss S Av | A | 3 |x | 2 9 |-12} v2 [7 1 130 X 4 0 1 | 1/3 -2/3 | Zo 25 [30 | -5/2 |-15/2 ; | L 4=G-Z3 0 o | 5/2 | 15/2 1 No negative A All Cj - Z; value are either Zero or Positive. Hence, Solution is optimal. Optimal Solution: Xi =12 X. =4 Optimal cost = Rs. 420 Min. Z = (25 x 12) + (30 x 4) = Rs. 420 |Operations Resear, (8M 2, Je 13: : : ets dual of following pl te Min. Z 2 8X1 + 10% Subject to: 6X1. 49% = 36 1X + 6X2 = 48 Solution: Dual of the LPP: Max. Z* = 36y1 + 48y2 Subject to: oyti2y2 $8 gyi t6y2 £10 Example 14: Write dual of following LPP. Min.Z =3Xi+ 5X2 Subject to: 12X1 + 6X2 = 72 8X, +10X2 < 80 Solution: To write dual of Minimization problem, we need all constraints as “>" type. Hence, we multiply second constraint by ~ 1. Now the constraints will be: 12X1 + 6X2 = 72 -8X:-10X,; =-80 2. Dual of the LPP: Max. Z* = 72y: - 80y2 Subject to: 12y:-8y2 <3 6yi- ly, <5 Example 15: Write dual of following LPP: Min.Z = 60X, + 80X2 Subject to: 4X) +6X. 224 6X1 +3X. = 18programming ~ Nt meat POR M3 ution: qhe second constraint is equality, We can write it as oXi + 3X2 S Wand 6X, + 3X2 = 18 Now, since we need all constraints in "=" type, we multiply ‘<’ ponstraint by — L 6X +3) s18 will become > -6i-3 2-18 Primal Dual Min. Z = 60% + 80X2 Max Z* = 24y;— 18y2 + 18yy Subject to: Subject to: 4X +6X2. = 24 4yi-6y2+6ys < 60 | -6X1-3X2. 2-18 6y:-3y2+3ys < 80 \ 6X1 +3X2 218 yuynys 20 In the Dual, if we rewrite y2 & ysas > ys =y2-ys then the Dual will be: Dual: Max. Z* = 24y1 + 18ys Subject to: 4yi+6y: = 60 by: +3ys =< 80 Since both y2 and ys are positive values, hence (y2 — ys) can be positive, zero or negative. It means ys is unrestricted in sign. Hence, in Primal if there is an equality constraint, than in Dual there is one variable which is unrestricted in sign. 4.6 DUALITY: Every linear programming problem has a mirror image associated with it, If the original problem is maximization, the mirror image is minimization and vice versa. The original problem is called ‘primal’ and the mirror image is called ‘dual’. The format of simplex method is such that when we obtain optimal Solution of any one out of primal or dual, we automatically get optimal solution of the other.114 \ 1 t aoe amples method, we alse Rel optimal sof, » solve dual by 81M] Moy eg. If we 80 s explained with example, an of primal. ae : Conversion of primal into dual is sof Dual Problem: dual is primal. al has a solut of both the solutions is equal, asible (.¢. solution Not feasible) tution (infinite-solution), ‘ uae fon, then the other also fing (2) Ifeither the primal or du solution. The optimal value (3) If any of the primal or dual is infe then the other has an unbounded sol Advantages of Duality: @ If primal problem contains a large n a smaller number of columns [variables], computational procedure by converting it into dual. Solution of the dual helps in checking computational accuracy of the primal. (3) Economic int decision making. Economic Interpretation of Dual: Suppose we have a maximization prol the problem is to maximize total profi resources. The dual of this problem would be minimization. The objective of dual would be minimization of cost. Suppose a company produces three products A, B é& C using two raw materials R; and R2. number of rows [constraints] and we can reduce the @) terpretation of the dual helps the management in blem (primal). The objective of it with optimal utilization of A B c (Requirement/unit) Total Availability Ri an ai | ais, TT Ro aa an | ax 12 Profit/unit Pi P2 P3 LPP formulation of above problem will be: Max. Z = P1-Xi + PaX2 + Pa-X3 Subject to constraints: au x1 +ai2-X2+a13°xX3 aai- Xi +.a22°X2-+a23°X3 S12 X1, X2, X30roan 14 i ir © wher? xp xno any of Unis LPP formation i oxtuice three products A, B, C whose profit contribution decision varlablos representing, products A, 1,6 ne TM We can pr or unit 8 known, We have {wo resources Rj, Ry whose capacities are known. veumit consumption ay, diz, eer I known. Pe ; Er we want to know how to allocate resources to maximize total fi. Pye dual ofthe above problem will be Minzt =n yuk nly Subject to constraints: ausyibaay2 2 pi aa yi tans y2 = p2 airyi bans ye2 2 yiry2 20 ‘To interpret this dual problem, consider the first constraint, any taasy2 2 pi pris the unit profil of Ist product A. ari and az1 are quantities of two resources required to proditce one unit of A. pris in rupees and ay), 21 are in physical units. Since both the sides of the equation should be in same unit (i.e. rupees) yi and y2 will be price of two resources Ry and Ro. _ Hence, an: y1 = Total economic value of Ri to manufacture 1 unit of A. a+ y2 = total economic values of Ry to manufacture 1 unit of A, Conclusion is that total economic value of inputs should be at least {qual to profit of one unit of product. We can interpret constraint no. 2 and 3 of the dual in the same manner, 47 PROBLEMS INVOLVING MIXED CONSTRAINTS: Minimization (Mixed constraints): Eample 16: Min. Z = 3X1 + 8X2 Subject to: Se Xy+X2 = 200 :116 a x X> Xi, X2 Solution: Standard Form: s 80 = 60 20 Operations Research (8m SN, ky Min. Z = 3X, + 8X2 + 0S; + 0S2 + MAi +MA, Subject to: (3) In ‘>’ Xi +X2+[Ar_= 200 Xi+{Si_=80 X2-S2+[A2 = 60 Xa, Xa, Si, Sz, Ar, Az, = 0 Note: To convert in standard form, (1) In’=’ constraint, only artificial variable is (2) In“S’ constraint, onl: variable is added. (-S, + A») In 1" Simplex Table, added. (+A,) y slack variable is added. (+S,) constraint, surplus variable is subtra icted and artificial basis variables will be Av Si & Ap. 1st Simplex Table: \\ Table449 / Go 3 8 0 0 M | M Col xX | bilexm ix S Seims| Ai AS RR Mis | Ar |feb0r ity 1 0 0 1 0 200 OES: eo" 0 a 0 0 0 Infinity M | A |Leo | o a OMe) 0 1 60> Za MM oho M | M 4=G-Z5 3-M |p -2 0 M 0 0 t Key Column =x; Key Row =A) Key Element = 1Se peagrarnming = Ul ., ww? re gimnple® Table: ir or SE as Table 4.50 My ore | al | i J 40 oa Se ie : 80 > a —_|_ tnsiniy | J | | Key Column =X KeyRow =; Key Element =1 3" Simplex Table: Table 4.51 Go Sys 0 0 M|M RR | rc x b XM |X Sy Sy anes | M] A 60 0 0 -1 1] a> | 3 | % | so} 1] o 1 0 Infinity | 8 X 60 0 sl 0 -60 | Za 3 | 8 |-w+3] M-s | c 4=G-Z> 0 | 0 |.M-3 |-M+s | iti Key Column : Key Row | Key Element 4% Simplex Table: Table 4.52 oa 3 8 0 o | Mf[MJRR i G. ig exe [lbs af ign cate) Sf Sa Ae [Aa Os] Se Ff Ore 0 | iid (EE cre | To [ee | EO | | 8 [| ~ | 120] 0 ra |= = 0 Zo 3 8 5 I 7 0 5 on A=G-Z> 0Operations Research 18 (OMS | No negative A. All CG) ~ Z values are either Zero or positive, 144, Ba : ce, solution is optimal. we a 5 RTA =e Optimal Solution: xX =80 | X2 = 120 s2 = 60 Min. Z = 3X1 + 8X2 Min. Z ‘= (3 x 80) + (8 x 120) = Rs. 1200 Maximization (Mixed Constraints): —~ Example 17: Max. Z = 4X1 + 5X2—- 3X3 Subject to: Xi+X2+X3 =10 Xi-X, 21 2X1 + 3X2+X3 < 30 Xi, X2,X3 20 Solution: Standard Form: Max. Z = 4Xi + 5X2—3Xs + 0S; + 0S2— MA — MA Subject to: z Xi+X2+X3+/[A: =10 Xi-X2- Sit+[Az =1 2X1 +3X2+X3+[S2 -=30 X1, Xz, Xa, Si, Sz, Ar, An = 0 Note: To convert in standard form, (1) In‘=‘ constraint, only artificial variable is added. (+Ai) (2) In ‘2’ constraint, surplus variable is subtracted and artificial variable is added. (- S; + Az) (3) In’s’ constraint, only slack variable is added. (+82). In maximiation problem, coefficient of artificial variable it objective function is —M. (In Minimization problem it is-+M.)Meas “eg pgimtplex Table: ve ns 2M M ti Maximum positive C)-Z)=4+2M ». [Key Column =X; KeyRow =Ag Key Element =1 -ml} oo | —-mM : eS" SeyeM 0 oe Te | 24 Simplex Table: Table 4.54 G3 4 5 -3 0 a lee Hairs | calles [ aa ee aio cer a -M| Ai |L9 0 Toa Tallomies) = 4 Xt il 1 -1 0 “1 0 i = | se] 28 fo. es ea s|c2].1 |e ye Z> 4 |-ol|-m | -m [-0 |-M aa i L =G-4> 0 |pm-l|3+[M+] 0 | 0 ae 9 M 4 T Maximum positive C= 2)=2M-1 Key Column = KeyRow — =AtOperations Research (Bis) 88 ) (Nk) 3x Simplex Table: | A=G-Z> 0 0 |-15/2}-1/2| 0 | No positive A. All Cj - Zj values are either zero or negative. Hence, solution is optimal. Optimal Solution: Xi =11/2 S. =11/2 Xs is not produced. : 9) (432) (od? Max.Z =|5xp)+{4xq J+l0Oxg | X2 =9/2 | | | : sr 89 | Max. Z = Optimal profit = Rs. | | 4.8 MORE SPECIAL CASES IN SIMPLEX: (1) Unbounded Solution: Example 18: : Max. Z = 60X: + 20X2 Subject to: 2X +4X_ > 120 8X + 6X2 = 240 XX. 20 | Solution: Standard form: Max. Z = 60X; + 20X2 + 0S; + 0S2— MA, — MA, Subject to: 2X1 +4X2-Si +A, = 120 8X1 + 6X2-S2+A2 = 240 X1, Xo,$1, Se Ay Ar = 0 When we solve this LPP by simplex method, we will get following values in 4" Simplex Table:£ ramming - Il pat POE ie 121 Table 4.56 Go wel] 6] et 7 uw | aw ae spp [Ta |e | SH | Se [PAA 20 | 0 | 1 |[-4] 4 60 60 1 2 |l-1/2] 0 ~ 120 60 | 120 [[-30] 0 a a=Q-Z> 0 - 100 30 0 t Max. positive Cj - Z; = 30 Key Column = 5S; But there is no positive Replacement Ratio. It means there is an Entering variable, but there is no outgoing variable. Hence, the solution is unbounded or infinity. The value of Z (Profit) keeps on increasing infinitely. (Q) Infeasible Solution: Example 19: Max. Z =3Xi + 2X2 Subject to: Xit+X. <4 2X1+X2 210 Xi,% 20 Solution: Standard Form: . Max. Z = 3X1 + 2X2 +05; + 0S2-MAi Subject to: M+X2+S =4 2X1+X2-S2+Ar =10 X1, Xo, Si, Sz, Ar 20 ' , When we solve this LPP by simplex method, we will get following Yalues in 24 Simplex Table: Table 4.57 a a 2 0 0 [-M] RR is (oof erxan [aos |X Xe ee ee 1 -—M| A 2 0 — 3 | 3+ Ze To |main| NEES 0 [-1-M [-3-2M) -* meios Operations Research (Bry) thy No positive A value. All C= Z values are cither zero or negative. Hence, test Of optimality is satisfied. So, the solution appears to be optimal. But an Artificial variable (Ay) is present in the basis, which has objective function coefficient of — M (Infinity). Hence, the solution is infeasible (not feasible). Infeasibility occurs when there is no solution which satisfies al] 4), constraints of the LPP. 4.9 SIMPLEX CASE STUDIES: : Example 20: (MUL, April 2011) A business problem is formulated and expressed below as an Lpp. Xi & X2 are the production volumes of products A & B respectively. The resources required for producing these products are R; & R2. Total profit aS eae . Objective function: Maximize Z = 10X1 + 4X2 Subject to the resource constraints, L 20X; + 10X2 < 1200. 40X1 + 10X2 < 1600. XX. 20 Simplex algorithm of LPP, applied to the above problem yielded the following feasible solution. G 10 4 0 0 © Vv x |. X& Si So bi 0 Si 0 5 1 -1/2 [400 10 x 1 1/4 0 1/40 [40 (a) Please improve the above solution to optimality. (b) Study the solution found by you and answer the following questions with justification: (i) _ Is the solution found by you infeasible? ‘ (ii) Is this a case of multiple optimal solutions (alternate optima)? (ii) What is the product mix and the maximum profit? Gv) Calculate the percent utilization of resources Ri & R2. (v) If one unit of Rz becomes unavailable what is the reduction in maximum profit?programming - W it tp} 4 70) | OE OZ Ratie 80 160 | | | Jj pets 7) a RoG-% 9 ara 0 ~1/4 Positive A value. +, Solution is not optimal. Maximum positive A = 6/4 Key Column = Xz Minimum positive Ratio = 400/5 = 80 :. Key Row = S; -. Key Element = 5 G> 10 4 0 0 cjvijb | x% | %& | s [os [Ratio 4 j.% | 8 | o | a [avs [ino jo” |. x1_| 20 0 |-1/20[ 1/20 4 to | 4 [3/0] 170 A=G-% 0 0 [-3/10]-1/10 No positive A. +. Optimal solution. ny |Ans. (i) No. The solution is not infeasible. It is a feasible solution. There is no Artificial variable in the solution. Also, the ‘b’ values ie. the quantity values are not negative. Ans.: (ii) Non-basis variables in the solution are S; and Sp, AofS;=-3/10 AofS.=-1/10 + (iii) Optimal Product mix: X2 = 80 units = No. of units of B X1 = 20 units = No. of units of A No zero A for any Non-basis variable. +. There is no alternate optimal solution.124 Operations Research (Bas) (ty Optimal profit Max. Z = (4 x 80) + (10 x 20) = & 520 Ans. (iv) S) and $2 are non-basis variables. It means R; and Rp are scarce resources. *. Both Ry and Rz are used 100%. No unutilized capacity for Ry and Ro. Ans. (v) Shadow price of Re = Zj of S2 =1/10=0.1 If unit of Ro becomes unavailable, reduction in maximum profit will be € 0.1 per unit. Example 21: vo A company produces two products A and B. It uses three machines for production Mi, Mz and Ms. Profit per unit is Rs. 3 for A and Rs. 5 for B. Capacities of the machines are 4, 6 and 12 hrs. respectively. Following simplex solution is obtained. Based on this solution, answer the questions given below. Table 4.58 Go 3 5 0 0 0 Cc x b x | % | S& So Ss 0 Si 4 1 0 1 0 0 0 Sz o |-3/2{ 0 0 ema 1/2) 5 X2 6 [3/72 | 1 0 o [| 172 Z> 15/2,]_5' 0 0 [| 5/2 A=G-Zj> -9/2| 0 0 0 [5/2 X represents A, X2 represents B and Sy, S2, S3 are slack variables for Mi, M2, Mo. Questions: (a) Is this optimal solution? (b) Is this unique solution? (c) Is the solution infeasible? (d)_ Is there degeneracy in the solution? (e) What is the optimal product mix and how much is optimal profit? () How much is the minimum increase required in profit of A so that it can be prodticed? (g) Which resources are scarce and which are abundant? (h) If additional capacities of Mi, Mz & Mz are to be procured. What is the maximum price company should pay for each hour of Mu, M2 & M3?e naming - Hl neat PrOBla™ tine Ci 125 ) anew product C is to be introduced in the 1 contribution of Rs. 4. It requires 2 hrs on Mi, thr on esa give M3. Should it be produced or not? , on M2 & 2 hts on If due to maintenance, My is shut d. ® effect on profit? clown for 2 hrs? What will be solution: i itive A. All G)~Z; values are ei a) There is no posit j~ 4 values are either ae \ Hence, solution is optimal. ero or negative, (b) X: & Ss are non-basis variables. A values of xi & s3 are ~ 9/2 and - 5/2 respectively. There is no zero A value for any non-basis variable. Hence, there is no alternate optimal solution. Soiution is unique. (2 The solution is not infeasible. There is no artificial variable present "in the basis of the solution. The solution is feasible. (@) Quantity value (b value) of s; = 0 Hence, the solution is de; in the solution. (e) Out of two products A (Xi) and B (X2), only B (X2) is present in the basis of the solution. Hence, only product B (X2) is produced. Product A (X:) is not produced. generate solution. There is degeneracy Optimal product mix: Xz. = 6 units 6 units of product B are produced. Optimal profit: 5x6 =Rs.30 -9 (A value of Xi (product A) = TE It means, if company produces 1 unit of product A it will incur 9 loss of Rs. 2 Hence, present profit of product A (which is Rs. 3) should be 9 increased by Rs. 5 - 9 1 New profit should be =3 +9 = 9 = Rs. 7.5. re i sis of the solution. {8) S, and S) are present in the basis o ; Siis eee machine Mi and S2 is slack of machine Mp. Hence M, and Mzare abundant resources. SsOperations Research (BMS) (Nx 8 sd 8: 20 Hence, unutilized capacity of Mi = 4 hrs. = Zero hrs. unutilized capacity of M2 = Zero : tally a scarce resource; because there is no (it means, Mo i unutilized capacity). Syis a non-basis variable. Itmeans Sy = 0. Hence, there is no unutilized capacity for Ms. So Mz is scarce resource. (hk) Shadow prices of Mi, Mz, M3 are: Mi: Rs. Zero (Z; of Si) Mz: Rs. Zero (Z; of S2) Ms: Rs. 3 = Rs. 2.5 (Zj of Ss) Hence, the maximum price company should pay for 1 extra hour of Mi, Mz, Ms is Rs. zero, Rs. zero & Rs. 2.5 respectively. Gi) New Product C gives contribution of Rs. 4. Its resource requirement Mi: 2hrs, Mo: Lhr, Ma: 2hrs. To find production cost, we multiply the resource requirement on each resource by its corresponding shadow price. Cost of production = (2 x 0) + (1 x 0) + @ x 3) =Rs.5 Since, cost of production is more than contribution, the product C should not be produced. It will be a loss making product. Shadow price of Ms = Rs. It means value of 1 hour of Mg is Rs. 2.5. Hence, if M3 is shut down for 2 hrs, company will incur loss of Rs. 5. Example 22: : A company produces 3 products P, Q and R. It uses 3 resources Ri, Re & Rs. The profit per unit for P, Q, R is Rs. 30, Rs. 40 and Rs. 20 ‘ respectively. Capacity of resources Ri, Rz and R is 10,000, 8,000 and 1,000 unit respectively. Following simplex solution is obtained, Based. on this: solution, answer the questions given below with justificati : Pe eae as Rs. 2.5ie tine -. ar programming 0 0 _[-35/a[ -574 | -5/2|_0 Xi, Xa Xs represent products P, Q, R. Si, Sz, Ss represent slack variables of resources Ri, R2, Rs. Questions: @ (b) io) @ (e) (f) ®) () (i) An: (a) (b) © (ad) Is this optimal solution? Is there alternate optimal solution? Is the solution feasible? Is the solution degenerate? What is the optimal product mix and optimal profit? Jf the company wants to produce product R, what should be the minimum increase in profit of R. Which resources are scarce & which are abundant? How much is the profit contribution per unit for resources R, R2& Rs. If anew product ‘T’ is to be introduced which can give profit pf Rs. 25 per unit. It requires 8 units of Ri, 4 units of Rz and 6 units of Rs should it be produced. swers: There is no positive A. All C, - Z values are either zero or negative. Hence, solution is optimal. In the optimal solution, Xs, S1 and S2 are non-basis variables. Their A values are — 35/4, - 5/4,- 5/2 respectively. No no-basis variable is having zero 4 value. Hence, there is no alternate optimal solution. Solution is unique. The solution is feasible. ; : There is no artificial variable present in the basis of the solution. All quantity values are positive. ‘There is no value of zero quantity. Hence, solution is not degenerate.os” Operations Resea, 6 128 rc (85) (ec) Optimal product mix: X; = No. of units of Pp =250 X2 = No. of units of Q X; (product R) is not produced. Optimal Profit: Max Z_ = (30 x 250) + (40 x 625) = Rs. 32,500 -35 (f) A of X3 (product R) = 4 <. Minimum increase required in profit of product R = ps 25 (Rs. 8.75) ‘ Present profit of R = Rs. 20 New profit R should be = 20+ 8.75 = Rs. 28.75 (g) Abundant Resources: Ss is present in the basis. Ss is slack variable of resource Rs. <. Rsis abundant resource. unutilized capacity of R3 = 125 units Scarce resources: S1 & Sz are non-basis variables. Hence, resources Rr and Rz are scarce resources. (h) Shadow prices of resources: Ri :Rs.5/4 Re :Rs.5/2 Rs : Rs. zero +. Profit contribution per unit for Ri, Rz, Rs: Ri. :Rs.5/4=Rs. 1.25 Ro :Rs.5/2=Rs. 2.50 R3_: Rs. zero (i) Profit of new product T = Rs. 25 Cost of new Product = Shadow price x requirement 5 5 Cost =(Fx8 +Gx4)+0<61 =Rs. 20 Since profit is greater than cost, the new product may be produced.146 row). Thy negative Nene extend up to infinity as there Hene Operations Research FCH (has) ( NK) ix happens when there 1s We positive ratio, All the ratios are for infinity iy nature, 0, IL is not possible Lo proce a wanit mee Je to find an optimal solution to an unbounded pp . C1theF 24, wed to the next table, Ht means the soluy uming variable, but no outgoing y, ¢, Lis not possi 2) Explain slack, surplus and artificial variables in simplex, Ans. formulation ins (a) (b) ©) Slack, surplis and artificial variables are used to convert the Lpp andard form. Slack variable: It is represented by vs" and it is added to the LHS of , “Yess than or equal to” constraint to convert it in standard form, ty represents unutilized capacity of a resource. Its coefficient in the objective function . Surplus variable: It is also represented by “s”. It is subtracted from the LHS of a “greater ‘than or equal to” constraint to convert it in standard form. Its coefficient in the objective function = zero. Artificial variable: It is represented by “A”. It is added to the LHS of 2 “greater than or equal to” constraint to convert it in standard form. Its coefficient in the objective function is “M” which represents infinity. “M" has positive (+) sign in Minimization problem and negative (-) sign in Maximization problem. (3) Whatare key column, key row and key element in a simplex table? Ans.: (a) (b) () Key column: It represents the incoming or entering variable for the next simplex table. In Maximization problem, key column is the column with maximum positive A value. In Minimization problem, key column is the column with maximum negative A value. Key row: It represents the outgoing or departing variable in the simplex table. It is the basis variable which has the minimum positive ratio. In the next simplex table, this outgoing variable is replaced with the incoming variable. Key element: It is the value in the simplex table which is at the intersection of key column and key row. (4) What are basis and non-basis variables in a simplex table? Ans.: * (a) (by » variables which are nota part of that particular solution. - solution by replacing one of the basis variables with one Basis variables: Ba which are present in the basis of that simplex table. Thes variables which are in that particular solution. Non basis variables: Non basis variables in a, simplex table ™ variables which are not in the basis of that simplex table: These ar variables in'a simplex table mean those variables e are the ean the the improve the In the test of optimality, we détermine if it is possible to i r y Ze E ‘of the:non- basis variables.i 2 mming - Hl get Pree 147 what is meant by scarce and abundant resources in a simplex solution? o sources can be cla ‘ified as scarce resources and abundant resources. ans: Ri fay) Scarce resources: These are the resources whiclr are completely Zonsumed in the production process. Hence, there is no unutilized capacity for these resources. Full capacity is utilized. It means the slack quantity of scarce resources is zero, Stack variable representing this resource is absent in the basis of optimal solution. (») Abundant resources: These are resources which are not consumed completely in the production process. There is some unutilized capacity, full capacity is not used. It means there is some slack quantity which is equal to the unutilized capacity. Slack variable representing this resource is present in the basis of optimal solution. The quantity of slack variable determines the unutilized capacity of the resource. (6 How do you detect degeneracy in a simplex solution? Degeneracy (or degenerate solution) occurs in simplex in following (a) There is a tie in the key row. There are two equal minimum positive replacement ratios. It means there are actually two outgoing variables for one incoming variable. OR (b) The quantity value of a basis variable is zero. It means the variable is in the solution as a basis variable, but with zero quantity. It means in reality, it is a non-basis variable. (7) Explain what is meant by an infeasible solution in simplex. ‘Ans.: Infeasible means not possible. In sim lex, infeasibility occurs in two Ps Pp ty cases: af ; (a) In the quantity column, there is a negative value. It means a basis variable is: having negative quantity, which is not possible as any variable can take either zero or positive value. (b) An artificial variable present in the solution as a basis variable. It is not possible as coefficient of artificial variable is infinity. (8) How to detect and find alternate optimal solution or multiple optimal solutions in simplex? Ans: 3s ‘fo Qsieet alternate optimal solution, we check the A’ values of the non basis variables in the last (ie, optimal) table. If any non-basis 4 value is equal to zero, it means there is an alternate optimal solution. (>) To find alternate optimal solution, we should take the column of non- basis variable having zero 4 value as the key column. Then we calculate ratios and select the minimum positive ratio as the key row. The next table that we obtain is the alternate optim? solution. ”148 Operations Research (ats) yy (9) What is meant by shadow price of a resource? Ans. Shadow price of a resource means “the value of ane extra unit of the resource”. In other words, it is the profit contribution made by one unit of the resource, Hence, it is the maximum price that should be paid for one unit of that resource, Shadow price is found in the “Zj” row under the slack variables, E.g. if the Zj value of slack variable S1 is 5, it means the shadow price of resource no. 1 is Rs. 5. Hence, the company should pay at the most Rs. 5 to acquire one extra unit of that resource. The shadow price of an abundant resource is always zero, because there is unutilized capacity.