856 HIGHER ENGINEERING MATHEMATICS LINEAR 7. A manufacturer his two products I and II both of which are made in steps by machines A and B, The process times per n ndred for the two products on the two machines are * subject Product Mic A Mic B bject 1 4a Sirs 0 Shr 2hre ‘Set-up times are re sigible. For the coming period machine 4 has 100 hrs. and B has 80 hrs. The contribution for prouet I is Rs. 10 per 100 units and for product II is Re. 5 per 100 units, The ‘manufacturer is ir 1 market which can absorb both products as much as he can produce for the and me immediate period ch oad. Determine graphically, how much of products I and II, he should produce to. ‘maximize his contri ution, 8. A production maneg » wants to determine the quantity to be produced per month of praduets A and De B manufactured by” us firm. The data on resources required and availablity of resources are given solutic below De cures Requirements ee is calles Bese Product A Product B ccaeuainae De: Raw material (kg) 60 120 32,000 LPP ‘Machine hre/piece 8 5 600 a ‘Assembly man brs a 4 500 ee Sale pricepiece Re. 30 Ra, 40 by addi Formulate the prot i m as a standard LLP. Find product mix that would give maximum profit by Der ‘graphical technicue 8. A pineapple firm pro iuces two products : canned pineapple and canned juice. The specific mounts of materia, labour a 1d equipment required to produce each product and the availability of each of ‘these resources are s own in the table given below t Canned Juice Pineapple Available Resources Labour (man hrs) 3 20 120 Equipment (mie h-s) 1 23 69 Material (unit) 1 rr 49 ee Assuming one unit »: ch of canned juice and canned pineapple has profit margins of Rs. 2 and Re. 1 respectively. Formuli te this as L.P. problem and solve it graphically. Gadras, 1991 8) Solve the following L.P. pro lems graphically 10. Maximize Z = 3x » 2y subject to-2e + 8y <9, x 5y 2-20 and x,y20. 11, Minimize Z= x, + x, subject to 60x, + 30, 2 240, 90x, + 60; 2 300, 90x, + 180x, = 540 and aya Keraia, 1991) ac 12. Gal. Breweries Ltd. have two bottling plants one located at ‘G' and other at ‘J: Bach plant produces 7 ‘three drinks : whisk, beer and brandy. The number af bottles produced per day are'as follows an Planet Pantatd ee 1500 1500 © 3000 1000 Ma 2000 5000 suject ‘A market survey inci ates that during the month of July, there willbe a demand of 20,000 bottles of whiskey, 40,000 bot! s of beer and 44,000 bottles of brandy. The operating cost per day for plants at Gand J are Rs. 600 a id Rs. 400. For how many day’ each plant be run in July 0 as to minimize the oon Production cost, while still meeting the market demand, Solve graphically. eal A 27-5. GENERAL LINEAR I ROGRAMMING PROBLEM. ( woe Any L.P-P. problem i wvolving more than two variables may be expressed as follows Find the values of ta» variables x, x2, % Which maximize (or minimize) the objective ii function Thematics LINEAR PE 3S2aMMING 857 B.The Ze cyey +ephy +... 40m, @ subject to the constraints M+ Bae tot Oynhy Sy Gy) + Ogax, + + Gann S by | Mii) The Gmni81 * On 3t2 * noes + Btn Sy for the he non-nogativity restrictions duce to eee (i) ea fA ft of ales 0.84 Which safes the constrains ofthe LPP is eal ‘given nth oft by vounts ach of Re. 918) 991) sof sat the solution Def. Any solution to.a L.P-P. which satisfies the ‘non-negativity restrictions of the problem is called i's feasible solution, PoE (Any feasible solution which maximizes (or minimizes) the objective function of the LPP. is called its optimal solution. Som: 2f the constraints in i) may be equalities, some others may be inequalities of (<) type and zemalaing ones inequalities of @) type, The inequality conatranns changed to equalities ‘by addin; ‘or subtracting) non-negative variables to from the ek henrcs ‘of such constraints, Def. 4. If the constraints of a general L.P.P. be Zie7sS 0 = 1,2, ky then the non negative variables 9 which satisfy im Zaiay+6.=6; €= 1,2, ...h), are called slack variables Det. 5. If the constraints of a general L.P.P. be ZOF2b =A KD) then the nonnegtivevarabless which sat is ZAi~S=b) C=A, 441...) are called surplus variables, a 27-6. CANONICAL AND STANDARD FORMS OF LPP. After tho formulation of L.P., the next stop is to obtain its solution, But before any method its eleis: Jats solution, the probiem must be presented in a suitable forms Aree explain its followir ¢ two forms -—- () Canonical form. The general L.P.P. can always be expressed in the following form Maximise Z = cy, + 6989+ ons. + Ony subject to the constraints aj + ajat2 + nn. + dinfy $B; 51= 1, 2Qp.c..m Xt Xap, 20, £2 making some elementary transformations. This form of the L.P.P. is called ite canonical form and ls the following characteristics (® Objec ive function is of maximization type, Gi) All xnstraints are of (<) type, (iii) AN variables x are non-negative. ‘The car nical form is a format fora L.P-P. which finds its use in the Duality theory858 ENGINEERING MATHEMATICS @ Standard ‘orm, The general .P.P. can also be putin the follow form Maximize Z= Gr; +ept9 + ....e,% Subject tothe constraints aie, + ai9t9 + nt aigty =by 5 HAE. nty 20, Panam of LPP. is called its standard form and has the following characteristics : {® Objective fis ction is of maximization type (w) All constrait ts are expressed as equations ; (id Right han1 side of each constraint is non-negative (iv) All variabl>. are non-negative, Obs. Any LP.P. en be expressed in the standard form. As minimize Z=¢ x, +0944... rn, Ss equivalent to maxin ze. Z4=—2Z) =~ e.g. an.neqt ‘he objective function cin always be expressed in the maxin arog) Sealy Ge ataint can always bo converted to equalities by adding (or subtracting) the slack (or surplus) variables tthe left hand sides of such constraiat, So far, the decision variables x, x,....,, have been a smed tobe all non-negative, In actual practice, dunersatiables could «so be zero or negative: a variable is negative oon always be expressed as the ‘ference of two mon-u gative variables eg. a variables; con be eanee where x/20,x,"20 Example 27.10. Zonvert the folowing L.P-P. to the standard form Maximize Z= xy + 54 + 7x5, subject to S1~ Ap $5, $21 + Bey + Sug 2 11, dey 4.369 52, x1, 2520, As 43 is unrestr cied, let xg =x3'— 5" where 23',15"2 0. Now the given constraints can be expressed as Assam 6x, — 4x <5, Bey 4 ‘ep + Beg! ~ Bx s"> 11 +a + Bry — Seq" 2 4s a3, x9""2 0, {ntroducing the +1 tek/surplus variables, the problem in standard form becomes Maximize if = 3¢y + 5xp + Txy'— 7x” subject to 6x; — Arp +9, =5, 8k; + 2e9 + Sig’ — G9” —s=11, 4, + Bry’ — Sry” + 5g =2, Hy 5239/33", 81,89, 9520. Example 27-11, 2:press the following problem in the standard form Minimize Z= 3x1 + 4x subject to Bem x9 Seg =— 4, Bey + Sup 4:24 = 10, 21 Ay = 12, xy, x5, 2420. Hore sg x4 are the slack/surplus variables and x1, x, are the decision variables, As xp is unrestricted, let x2 -=29 ~xq” where xy’, x3" >0, « The problem in s:andard form is Maximize Z (+2) =—Bey — 4uy' + 4g” 27 cont Ith also verti met] step valu Jump simp prom « is for provi varie solut contai solutir solutic If soluti a the be is call Tr. the o result « L subse n a proble N subje: and ©sears istics slack ractice, as the an be x UNEARP2 GRAMMING 859 sutject to ttm" + Bey = 4 Bx, + By’ — Sy” +24 = 10 3 ~ dey + ey” =12 sa Y' 9"s 45, 24 20. 27,7. SI PLEX METHOD fon, neing Solving an L-P.P. graphically, the region of feasible solutions was found to be Tthe re met eay fertices and edges joining them. The optimal solution occured at sone seeee 1 the ort mal solution was not unique, the optimal pointe were on an edge. These observations also hol true for the general LPP. Essentially the problem is that oe finding the particular Wrathag ge convex region which corresponds to the optimal solution, The mar ‘commonly used Retied 2 locating the optimal vertex isthe simplex method. This method eweenn moving Step by sp from ane vertex to the adjacent one, Ofall the adjacent vertices there giving better Talks of the objective function over that of the preceding vertex is chiees mae method of Humping f om one vertex to the other is then repeated. Since the number of vertices finite, the ‘simplex svethod leads to an optimal vertex in a finite number of steps (2) In simplex method, an infinite number of solutions is reduced to a finite number of Promising solutions by using the following facts { When there are m constraints and (m +n) variables (m being < n), the starting solution Xs found ty setting n variables equal to zero and then solving the remaining m equations, solution it in L-PP., the variables must always be non-negative. Some ofthe base solutions may coneideref wuve variables. Such solutions are called base infeasible solutions and cherie ge be Eepeidered To achieve this, we start with a basic solution which ienon-negetive There ce basie Sejution taast always be non-negative. This is ensured by the feasible cradtor Such a solution in cnown as basic feasible solution. fail th: variables in the basic feasible solution are positive, then itis called non-degenerate solution 1d if some ofthe variables are zera it is called degenerate solution, (ii) At ew basi feasible solution may be obtained from the previous one by ‘equating one of re nasic ye tiables to zero and replacing it by a new non-basie variable. Theeli wien een ane ‘s called the outgoing variable while the new variable is hnown as the ineoming seriatie The inc ming variable must improve the value of the objective function which is engurws by the optimal-ty condition. This process is repeated tll no further improvenare i possible. The ‘resulting «9 ution is called the optimal basic feasible solution or simply optimal aehaticn (8) The simplex method is, therefore, based on the following two conditions x nets bility condition. It ensures that if the starting solution is basic feasible, the subsequen: will also be basic feasible, Tl Opti:nality condition. 1t ensures that only improved solutions will be obtained, sero ve shall elaborate the above terms in relation to the general linear programming problem in s‘andard form, ie. Maximie —— Z=eyxy+epty +... + c,3, ay subject to} ayxj+5 =, i and 420,520, A (2) an (3)860 - HIGHER ENGINEERING MaTHeWancs (0 Solution. 34 i solution ofthe general LPP iit eatatce the constraints (2), eee tts 21 tine Bealls lites oft pesecnld. ifit satisfies both {dg Constraints (2) and the non-negativity restrietions () The set S of all feasible solutions is called the feasible egion, A linear programme is said ube infeasible when the set S is empty. stig baste solu ion is the solution of the m basic variables when each of the n non-basic variables is equatec to zero Li) Basic feasivle solution is that basic solution which also satisfies the non-negativity restrictions (3), {2 Optimal sol: ion is that basic feasible solution which also. ‘optimizes the objective fimetion (2) while satisfying the conditions (2) and (3). Sif) Nen-degens ate basic feasible solution is that basic feasible solution which contains Grastly m non-zore asic variables. If any of the basic ceva becomes zero, it is called a degenerate basic fee ible solution. Example 27-1: Find all the basic solutions of the following system of equations identifying ‘meach ease the basic and non-basic variables 2) x + 4g = 1, 3p 4-29 + 5xy = 14, shuestigate whether he basic solutions are degenerate basic solutions or not. Hence find the basic feasible solutin. of the system, (North Bengal, 1989) fiance {hero are n +n =9 variables and there are m =2 constraints in this problem, a basic Solution can be obta red by seting any one variable equal oxen ‘and then solving the resulting Sauations, Also the -ctal number of basic solutions =" "C,, = 5p =3. ‘The characteristi's ofthe various basic solutions are as given below : [veer] 7 | Foo) paste | Nonbasie Values of basic Is the sol. seasibte 1} Isthe sol. | aa | variables | variables variables (Arealls;>02 | degenerate? | | | 1 | Xap 3 Bey +2; ay +xp=14 feta | a fatdey=tt q+ S2y= 14 ¥y=8,x5 No Yee [a eels 2 sepa Bx + B29 = 14 | 2 me12,x905/2 8 Ne L ; 2 | Ye io ‘The basic feasible s lutions are x= il 805,39: 05 (i) xy = ap = 0,25 =5/2 2 which are also non-dege aerate basic solutions. Example 2713. Fiid an optimal solution to the following LPP. by computing all basic solutions and then finai ig one that maximizes the objective fun vich Luneee sears LUNEARPRC ¢ RAMMING 861 nts (2) B84 Sepa 8g + gm 8,85 ~ Buy + 655 Tey =~3, xy ty 4g 2d 4 2 + 6g ~ xy =~ 3, xp 25 5 24 Jes both Max. Z= 2x, + y+ 455+ Teg (Kerala, 1995 § ; Caliewt, 1992) tions is Bc as eygere fut variables and two constraints, a hase solution ean be ebiaeg by setting empty. ofaat act ies equal to ero and then solving the resulting equations Ase eae ea n-basic of basic scl ttions = 4C, = 6 racteristcs ofthe various basic solutions areas given below ‘tivity T [ Tothe sot] T Lasic Non-basic Values of basic feasible ? Is the sol, action vaiables | variables variables (Are all | Value of Z| ‘optimal ? 200 atains 1 || sm Japucd Bde c8 led a | 2, | | £1=1,xg=2 ‘Yes: 8 No. on 46% | the 4-4/3, a m= -67713. | yy | _ basic Bonn femeo| te | | | | Ye | 0s | we 4] sas | | %2= 45/16, | 7/16 Yee | 102 No 5. | xa | y+ dey = Bey = 74 | Js se isers8 | ae-713 | oy | ; ~ | 6. spayn0 nyt eye 8 6x4~ 724" —3 | | x= 44/17, 4245/17 Yes | 289 Yor Hence the optimal basic feasible solution is #1701425 0,29 =-44/17, x4 = 45/17 and the maximum value of Z = 289, Problems 27.3 1. Reducs th following problom to the standard form Determine 120,220, x52 0 50 a8 to Maximizs 1+ Bip + Bry Subloc te she constraints 2x, — 519 6, ey + 26462525, 96,444 $3 2. Express th> following Z.P.P. in the standard form Minimize =n, + 2s) + 5x5 sublet te iy + ig 5,26 Bey + 45527, Be + sy 63, syn 3g 20862 _ HIGHER ENGINEERING WATHEMATICS 8. Convert the flls vin | vena 1g L.P.P. to standard form | of the Maximize Z = 2: ~ 249 + dry } variat Cette tit BE tS 8.244052 2,45; 24 - 6.2.20. | remai ‘iin allthe be lute othe flowing sree ones cues | constr At datyed Misnedees the un ‘5. Show that the fell. wing system of linear equations has two degenerate feasible basic ‘solutions and . St the non-degenerit base solution is net fata & 2B +4y~ 522, 94+ dey ay (North Bengal, 1988) S Find al the besic solutions tothe following problem Ic, Maximize Z=x - 3:5 + 3c, fanetio Subject to x= 26 + Sey =, de, Tand x, 20,220,420 Ite ‘Which ofthe basis lutions ae) non-dgencrate ba abe) enimal base feasible? In 27°8. WORKING PROCEDURE OF THE SIMPLEX METHOD ee inter inthe eine ofan inital basic feasible solution, an optimal solution to any LPP. ae by simplex method is 12 ind as follows : She? 1 (0 Chack whether the okective function i tobe masimsieed or minimized. on Wo Zens sear enee oe 2Ao(e minimized, ther convert it into a problem of maximization, by writing ne Minimize Z = Max nize (-2) choose { i) Check whether 2 16's are positive variable If any of the 4's is ‘P2gative, multiply both sides of that constraint by ~ 1 so as to make its is called Tight hand side posite intersee Step 2. Express the p-oblem in the standard form. violating re canateentaual te of constraints nto equations by introducings slack/surplus variables iteratior in the constraints givin; aquations of the for, 2 Gua81 + ata + aay + +644 069 +095 +. = by Drop Step 3. Find an init.ct basic feasible solution, value ur If there are m equat'cas involving n unknowns, then assign zero values to any (n — ‘m) of the element. variables for finding © so ution, Starting with a basic solution for which x, J=1,2,...,(n—m)y of key ro are each zero, find all s,. "all s; are > 0, the basic solution is feasible and non-degenerate, Ifone ed or more of the s, values me zero, then the solution is degenerate. as ‘Stor ‘The above informetins.is conveniently expressed in the following simplex table unbound 0 oo - aa “ 1% : = © Basis Hox. tye ay 82 83.8 Oe : ° 4 comomenest 0 0. subj ° % enimen eset 1 0. by Sol 8 431 32 035 ..0 Oty Step . . The Body matrix Unit matrix Step - = Byi de titles ety 49 ee. are called basic waribles and variables xy, 2,9 ote, are called nonbasie variables. Basis rfers tothe basic variables s,s, $9 6) Fow denotes the coefficientsmatics as and 1988) PP, its les n re ‘Step +. Apply optimality test Compute C)= 0-2; where Z;=Zey ay {Greer is called net evaluation row and indicates the per unit inerease in the objective function ihe variable heading the column is brought into the solution Wall Care negative, then the initial basic feasible solution is oprimal TF eve one G; is positive, then the current feasible solution is not optimal (ie, can be improved) end proceed to the next step, ‘Step 5 i) Identify the incoming and outgoing variables Jf thers are more than one positive C, then the incoming variable isthe one that heads the at the bottom. If more than one variable has the same maximuin ted arbitrarily as the incoming variable. eiqment. The 1 make all other elements of the key column zero by subtracting proper multiples of key row fim the other rows, dig ia bing but the sweopout process used to solve the linear equations. The operations performed are called elers ntary row operations.| ‘Step 6. Ch to step 4 and repeat the computational procedure until either an optimal (or an unbounded) s lution is obtained Example 27.14. Using simplex method Maximize Z= 5x; + 3x subject t» xy +p $2, 8x; + Bey 10, Sx, + Bxy $12, 21 x9 20. (Madras, 1993) Solution consists of the following steps Step 1. Check whether the objective function isto be maximized and all b's are positive The protloan being of maximization type and all 6's being 20, this step is not necessary. ‘Step 2. Exoress the problem in the standard form. By introc cing the slack variables 5, 6, 3, the problem in standard form becomes Max. :! = xy + 8x9 + 05; + Osy + Osy864 2 HIGHER ENGINEERING MATHEMATICS Subject & x1 +22 +9) + 052 +065 =2 Ai) 5x + 2x9 +05) + 59 + Osy = 10 (ai) 81 + Bp +05) +052 +53 = 12 (iti 02,81 89,5520. ‘Step 8. Find a7 initial basic feasible solution, There are thee equations involving five unknowns and for obtaining a solution, we assign a gid at¥ tH ofthe variables, We start with « base sae which we set 2 =0 SPEE2TO {this > sic solution corresponds to the origin in the srosh ca method). Substituting ¥1742=0in @), (i) and (i), we get the basic solution 81=2, 5210, 55=12 Since alleys 8 are positive, the base solution is als fessble and non-degenerate, + The basic fx sible solution is © (non-basic) and 5, = mex, «Initial basic 10, 53 = 12 (basic) 'asible solution is given by the following table 5 3 0 0 ° op Basis * 2 % 5 53 6 6 ° a @ 1 1 ° 0 2 me ° 5 2 0 1 0 10 105 ° 3 8 0 ° 1 2 128 ° o 0 ° 0 ° 5 3a ° ° 0 t Wor xy-colua n= 1), Z; aai1 = 0 (1) +0 (5) +0(8) =0 and ir secoltr '=2),Z)=Eep a2=0(1) +02) +08).0 Similarly £)(@)=0 (2) +0 (40) +0 (12) =0] ‘Step 4. Apply op'nality test £5 Gris positive under some columns, the intial basie feasible solution is not optimal (i, can bo improved) ani we proceed to the next step. Seep & ) Identi the incoming and outgoing variables, The above table shows that zy is the incoming variable a ite incremental contribution GE )is maximum ud the column in which t appears fa the key column (shown marked by an arrow at the bottom) Dividing the elon eats under b-column by the. ‘Corresponding elements of key-column, we find 21 as the bee ative 724) 9 is 2 in two rows. We, therefore, arbitcadi was the row containing of key row and the key column i. (1), is the hey eleriens 41 is therefore, the outgoing basic variable which will nu become non-basie Hiving desided thu t is to enter the solution, we have tried to find as to what maximum value; could have wit out violating the constraints, So Femoving s,, the new basis will contain 182 and 63 as the basi: variables. Cy ce ti th feasi relev the da model subjec St st subjeeIemarics li) Ai) Adit) tie, tion yan find sing | UNGAR FrOSRAMNANG (i) Tterate towards the optimal solution key elerient being unity, we retain ‘Tw ransform the initial set of equations with a b res'iu2 fons with a different basic feasible solution SRisam zero, we subtract proper multiples of key rex" dunet {ke elements of key row from the second row and third ro¥v. These become the second and the third Srrestcading value under eg column from 0 to 5, whi i the seco basie feasible solution is given by the following table ! 5 5 5 oo 0 | cp Basis xy 2 ees 43 ‘ e 5 n 1 1 1 0 0 2 ° o -3 5 1 o 0 0 0 5 -3 0 1 6 ‘ 5 5 Get 0 10 0 2 -5 0 0 As C; is either zero or negative under all column feasible vclution. This optimal solution is x, Example 2715. firm produces three pro. relevent cl ta is given below : s, the above table gives the optimal basic =2,x2=0 and maximum Z= 10, ducts which are processed on three machines. The | Time per unit (minutes) Machine capacity | : Product A Product B Product C | (minutes/day) | My 2 3 2 440 My 4 - 3 470 { My 2 5 ~ 430 ihe P* 0, this step is not necessary, ‘Step 2. i'xpress the problem in the standard form, I} By introducing the slack variables s), Max. Zim dey + 80 + 6x +051 + Osy +069 subject to Bey + Bp + Dep + 61 +059 + 089 = 440 Ae + Oy + Bey +08, +07 +059 = 470 2, 520. are non-negative. ‘62,89, the problem in standard form becomes :- HIGHER ENGINEERING MATHEMATICS 2e + Brg + 0x5 +05) +052 +53 = 430 2 5, 81,895 9520. ‘Step 3. Find ar initial basic feasible solution The basic (nor-legenerate) feasible solution is 2 =5 = 0 (non-basic) 51 440, 62 = 470, s5 = 430 (basic) Initial basie f-asible solution is given by the following table 5 4 3 0 0 0 mye ° 2 3 2 1 o 0 440 44ove 4 GO: @ 0 1 0 470 4708 2 5 o o o 1 48043070 o ° ° ° ° o 4 3 6 ° ° ° 4 ‘Step 4. Apply opt mality test. As Cis positive inder some columns, the initial basic feasible solution is not optimal and ‘we proceed to the meat step. ‘Step 5. (i) Identif the incoming and outgoing variables. ‘The above table s 1ows that x3 is the incoming variable while sy is the outgoing variable and (3) is the key element Gi) Herate towards the optimal solution, Drop sp and introduce x5 with its associated value 6 under cp column, Convert the key Stiaaakt $2 unity and make all other elements of key column zero. Then the second feasible solution is given by the table below : Gj 4 3 6 ° ° ° Ce 6 e a a 1-28 08808 380/04 6 ss wo 1 0 v0 4708 » % 2 5 ° ° ° 1 430 86 % 8 ° 6 o 2 o 940 Cees ° o 2 96 : - t Step 6. As Cys pes tive under the second column, the solution is not optimal and we proceed further, Now xis thes coming variable and s, isthe outgoing variable and (3) i the hey element for the next iteration, Drop s1 and intr uco x, with its associated value 3 under cg column. Coavert the key sub, type 1sTemancs 14072 7078 tal and Teand \e key asible co nent key LUNE! PROGRAMMING feat Rt to unity and make all other elements of the kee feas.Lle solution is given by the fallowing tabi *y column zero. Then tt 3809 70/8 1970/9 3200/3 8p x20. = Bey — dey 512 ict Express the problem in the standard form, By ia voducing the slack variables s,s» sq, the Problem in the standard form becomes Max, Zz 7 Bai ~ xy + Org + 05; + 5p + 059 = 12 ~ Ay + tp + Bg + Os; + Osp + 59 =10 F105, 81, 83,85 20. Step 3 Find initial basic feasible solution, ‘The be sic (non-degenerate) feasible solution is 21=%2=%5=0 (non-basic) ; 6, = 7, 29 = 12, 85 =10 (basio) Initial basie feasible solution is given by the table below : a eee eee Bos km kg on 7 1 0 87 ten a { a eae mere ret es oo o 0 6 6 eee eees 868 - HIGHER ENGINEERING MATHEMATICS ‘Step 4. Apply o:imality test. Ci Positive ander second column, the intial basic feasible solution ie not optimal and We proceed further. Step 5 (i) Ident. the incoming and outgoing variables. ‘The above table shows that xy is the incoming variable, 49 is the outgoing variable and (3) is the key element, (i) erate towards the optimal solution. Drop 83 and ia roduce x with its associated value 9 under ¢a column, Convert the key feaaont,t@ wnity ani make all other elements of the key eolume ses. Then the Second basic Feasible solution is giv m by the following table : 4 “1 3 -3 0 0 0 ce Basis Ber aan % od) ° ° 4 6) 0 war o V3 313 sue ° S - 22/89 3230 1 V3 76 ~ 38/1 Ey “4738 1 830 ° va 108 ~5/2 % -4 03 ela ° a0) g 3 0 “0 ° -1 un star subj a -1 3 3 ary 0 es Basis hon % nog 83 6 “1g loo 145 wo vw aus os oo Wess ws 8545 3 og Onn 326 45 0 3585 Zz -1 3 845 % oo uss g oo =975 -98 9 -8/5 Now since each C,s , therefore it gives the optimal solution 317 51/8 p= 58/5, x5 =0 (non-basic) and Zing, = 148/5 Hence Zin =~ 49/5, Example 27:17, Mac mize Z= 107; +25 +255 subject to the consirei its: 14:1 +45 ~ 6x + 9n,=7, Yess Jy 66955 86154-1520. 01 55 ay ng20, Solution consists oft flonng stop ‘Step 1. Check whether objective function is to be maximized and all b’s are non. ‘negative, Ste we proc ‘Ste, The is the k wy Dre to unity solution ca 107TT satics eo LUNEAR PEC GRAMMING 869 ne This set is not necessary. ‘Ster 2. Express the problem in the standard form. or® £4 is slack variable. By introducing other slack variables s, and sy the problem in standard form becomes ad (3) Max. Z= 07x +9 + 2xy + 0% + Os + 0sp reel 7 subjectto FEL t 9 x2 Bap 24+ 05, +00g=2 ekey aly, e Ha 16x, +9 2 6x5 + Oxy +5, + 059 =5 Bry ~ 4p —x5 + Org +05; +.89=0 — M4 Ha y,%q 81, 822 0. ‘Step 3 Find initial basic feasible solution. d The In sic feasible solution is AL 2 6 z _ 3 ther 5 _ 2 @ -1 1 9 ° 1 o & o ° ° ° o ° wt 2 ° ° ° _ : 1 Step 4 Apply optimality test. 6 As G; § positive under some columns, the initial basic feasible solution is not optimal and ie ‘we proceec.urther, S Step 5. \i) Identify the incoming and outgoing variables The akcve table shows that 2; is the incoming variable, y is the outgoing variable and (3) as is the key ol >ment, (ii) [erate towards the optimal solution. Drops: ind introduce x; with its associated value 107 under eg column. Convert key element to unity arc make all other elements of the key column zeros. Then the second basic feasible solution is g ven by the following table o 107 1 aigonera) 0 cp Basis xy Py amon 6 e ° x 0 78 -479 1 0 ws 78 ~21/4 ° . ° 35/6 “730 1 -16/3 5 15/2 107 -V3 -V73 0 0 va 0 ° 1: 0710778 10778 00 1073 1 0 1108 133 0 0 10778 1870 _ HIGHER ENGINEERING MATHEMATICS UNEA As Gis positive tnder some columns, the solution is not optimal. Here 19/9 being the 12 {arses Positive value fis the incoming variable. But all the values of 6 boing 0, will not enter the basis. Ta s indicates that the solution to the problem is unbounded ee gember that) heincoming variable isthe non basic variable corresponding tothe largest postive salue of Gand Hiei catecing varie eth basic-arible corresponding tthe los postive rato, obtained by Aivding the b-column elsr ents by the corresponding hey column ements} Problems 27-4 ning simplex method, sre the flowing LPP. : 1. Maximize Z=2, +3, ine subject to x, + 28, £10,052 55,0sx54 “ A Maximize Z = 44+ Oxy - subject to 2s, +. 50,2, +52p $100, 2, + Bey $90, x, 4,20 Gfadras, 1995 5) - 3. Maximize Z = 414 4, subject toy — 259 2, Bey +p 56,45 +26) $5,054.43 £2, sy0)20 4, Maximize Z = 101, + «y+ 2) subject tox +45 ~155 $10, 4, 445-435 $20, xy, 23,2520 Kerala, 1990) 7 WF Maximize Z=2 +29 + 3x5, wa subject to Sy + Rey oy $3, Oey ++ 2p $2, xy, sy 0g 20 (Madras, 1992) « 6. Minimize Z= 30; + 59+ dey Ps subject to 2x, + Boy 53, 2eg + 84g 510, Bx, + 2eq+ 4p 5 15,24, 29,2520 fa 7, Minimize Z =x; ~ 8. + 2x5, a Sbjct to Be p+ 2g $7, Bay + dp 12, ~ y+ y+ iy 5 10,249,392, 279.4) 8. Maximize Z = 4x, +63 + 42) + 6x4 Sot sabes tony + Rept 2+ hy $80, 2+ 289 +4 $60, Se, +36) ¢.55 +24 580,31 sy. 2420 feasible Kerale, 1991) ore) © rope Pradces procstsA and B and sell them ata profit of Rs. 2 and Rs, 3 each respectively Bach solving Product is proceased ca machines G and H. Product A requires 1 minute on G wed Peete oe @ Thang gPraduct 3 rocuires 1 minute on each ofthe machines, Machine © isnot saitetn we soe eae {han Bins. 40 mivda’ whereas the time constraint for machine His 10 hres Soe ioe simplex method for aimizing the profit, Step 10. cempany makes two types of products. Each product ofthe rt type requires twice as much labour Ste ‘second type only, the company can produce a total of er of the first and the second type to 150 and 250 tits eas type land Ta 5 for type Il, determine cee «teach type tobe produced to masimice (et correnne Na The owner of daicy is ying te determine the correct blend of two types of eed, Both contain various a Percentages of four e:s tial ingredients. With the following data determine the least cost blend ? _—— : Ste} Traredient Rprkeg in requirement in ‘ Feed 1 Feed 2 Min rea eau ce - @1 7 0 20 7 2 10 30 2 Then tk a 20 40 3 ) 4 30 0 6 b-colue Coot Rees.) 5 3 ceoeetes 1 the will sitive chine Type We Tine rsa — Mechine Type Available Time Productivity ira/uniy uh Mchine Type Nireleed Produst Product 2 Product y iia g machine 250 3 2 7 Lathe 150 ° 1 me 2 and 3. Find how much ntents of three types of fod and dat bination of food for minimum soee i Minin diy easement " = 50 10 190) heat or soyabeans, Each acre of com 182) and yields a profit of Rs 80, An acre of se cuts ee ageePate, Fequires 10 man-days of work and yields pooh ates oo ee farmer aah to Prepare, requires 8 man-deys of work nd yl Gena at should eae 00,2 Preparation and can count on 8000 manage af ee ion te shoul >e allocated to each crop to maximise prose 27-9. ARTIFICIAL VARIABLE TECHNIQUES iblewols avgaeen that the introduction of slack/eurpls variables provided the initia besie Seg el ion, But there are many problems wherein at least one af the esos of) 2) solving ways 24 S1eck variables fail to give such a solution. Thare are twe siete ‘ch solving such aroblems which we explain below uy (2) Manethod or Method of Penalties. This method is due to A. Charnes and consists of bs the following steps ‘Step 1. Ecpress the problem in standard form. ur Step 2, \1d non-negative variables to the left hand side of all those constraints which are of of theoe 2M: Such new variables are called artificial variables and the purpose of mesedeciig its in the final solution. For this purpose, we assign a very large penalty (-M) to these artif cial variables in the objective function, Step 8. Sclve the modified L.P.P. by simplex method, At any its ration of simplex method, one of the following three cases may arise : (© There ‘emains no artificial variable in the basis and the optimality condition is satisfied, Then the solu:ion is an optimal basic feasible solution to the problem, (i) Thete is at least one artificial variable in the basis at zero level (with zero value in Pcolumn) anu the optimality condition is satisfied. Then the solution is a degenerate optimal basic feasibl» solution.te 4 Continue ‘he simplex method until either an optimal basic feasible solution is obtained or an unbowa led solution is indicated. Obs. Example 27.18. UJ ¢ Charne's penalty method to +t Minimize 2 = 2x, +x, subject to is, +9 =3, dxy + 3x9 26, 21 +2xq $3, xy 2y20 Solution consists cf the following steps : Step 1. Express the sroblem in standard form. The second and thi:d inequalities are converted into equations by introducing the surplus and slack variables 1, s) respectively. aotee he Stst and s cond constraints boing of (=) and (2) type, we introduce two artificial variables Ay, Ay Converting the mini nization problem to the maximization form, the L.P-P. can be rewritten Max. Z’=~2e) — xp 4 05; +083 - MA; —MAy subject toy +x +081 +059 +A, + 04-8 Ani + Be, ~ 51 +05 +04; +g = 6 41+ 2x; +051 +5404, + dy =3 162,915 89, Ay Ag? 0 ‘Step 2. Obtain an ivi ial basic feasible solution. famivs variable ¢; i nota basic variable since its value is - 6. As negative quantities are Tet asble tx must be pevented from appearing inthe initial solution This ie deme by taking #1, each = 0, we obtain the initial basic feasible ¥1552=0,51=0;41=3,Ay 3a ‘Thus the initial simyiex table is , a o o Me a * 2 AL 6 ° 1 ° ° 1 2 ae 3 “a ° ° 6 ws 2 ° 1 ° 3 an uo ° _M ont Mat aM. ° ° LINEAR L 4 ok tothe p Her Ex, subject Sol Ste The Sysgre A. Thu: Me subject Sto Su isnot + nmeallo alue tion, ya, dis nis this tus ial LUNEAR PROS 2AMMING 873 Since Cis positive under =; and xy columns, this ia not an optimal tolation Step &. lterate towards optimal solution TIntroévce xy, and drop Ay from basis, = The sew simplex table is a y 2 1 0 0 7 Basis oxy = 8 2 A . ° -2 n 1 vs o 0 0 1 a a Aa ° 6 4 ° 1 2 ae ° 2 ° 38 o 1 2 6 % 2 2M 4 ° “Maw 373 G o | Aye 458M ag ° ° Since C; is positive under xy column, this is not an optimal solution. Introd ace xp and drop Ay ‘Then the revised simplex table is @ 2 =I ° ° o Bosie a = 8 a » 2 * 1 ° us ° 3 a = ° 1 6 0 6 o 8 ° ° 1 1 ° 5 2 a vs ° as _ og ° ° “us ° Since 2002 of Gis positive, this an optimal solution. Thus, an optimal basis feasible solution to the problen. is a 1/5, xp = 6/5, Max, Z' =-19/5, Hence the optimal value of the objective function is Win, Z=~Max. Z’ =~(-12/5) = 12/5 Example 27-19, Maximize Z=3x; + 2x, subject to the constraints : 2x; +, $2, Bx; +4xp 2 12, xy, 2920. Solution :onsists of the following steps : ‘Step 1. Exoress the problem in standard form, ‘The ineq, \lties are converted into equations by introducing the slack and surplus variables Sv satespectiv sly. Also the second constraint being of (2) type, we introduce the artificial variable A. Thus the 1..P-P. can be rewritten as Max. Z = {x + 2xp + 0s; +082 - MA subject to 2x, +29 +6) +089 + 0A =2, Bry + xp + 05-8 +A = 12, 22m 8,420 ‘Step 2. Fird an initial basic feasible solution. Surplus veriable is not a basic variable since its value is ~12. Since a negative quantity ‘snot feasible, must be prevented from appearing inthe initial solution. Ths is done by letting874 HIGHER ENGINEERING MATHEMATICS By taking te of ther non-basic variables x, and x, each feasible solution «= =0, we obtain the initial basic X15 22-5 ‘The initial simplex table is 0, ae 3 this is not an optimal solution, ‘Step 3. Ierate to vards optimal solution. Introduce x» and drop 5 The new sim ex table is a 7 3 2 ° 0 Me Z ‘ ca Basic * 2 a fe A 2 ” 2 1 1 ° ° aa 4 + ° 4 41 1 z your 2 eam u Me sna G na + 5M) ° ~e+an awe 0 Here each C; is a2gative and an artific ‘Thus there oxists a z52udo optimal solution to the problem 12) ¥e-hase ra sthod. This is another method to deal with the artificial variables wherein the LPP. is solved in two phases, Phase I. Step 1 Express surplus and artificial variables, ‘Step 2. Formulat» an artificial objective function B= Ay Ay Ay by assigning (-1) cost 19 each of the artificial variables Aj and zero cost to all other variables Step 2. Maximize .7* subject to the constraints of the original problem using the simplex ‘method. Then three ca: es arise : ial variable appears in the basis at non-zero level ‘he given problem in the standard form by introducing slack, 36 at least one artificial variable appears in the optimal basis at a Positive 28 this ease, the cr ginal problem dossn't possess any feasible solution and the procedure 0) Max. Z°= 0 cnt no artificial variale appears in the optimal basis, this case, a bas ¢ feasible solution is obtained and we proceed «, Phase II for finding the optimal basic feasible «lution to the original probtem Fed dn to the auxiliary L.P.P. is also a feasible solution to the original Problem with all artificiid variables set = 0, out solt the obje subyarics basic UNEARP3CE RAMMING 875 ‘To obt in a basic feasible solution, we prolong phase {for pushing all the antifclel variables Out of the l asis (without proceeding on to phase I1), {rage IL The basic feasible solution found at the end of phase I is used as the starting Spuition fn the original problem in this pahse ie. the final simplex table of shecs Ir ae as Eieaitial simplex table of phase IT and the artificial objective function is seplaced by the original objective function. Then we find the optimal solution Exam} le 2720, Use two-phase method to Mininire 2 = 7.5%, ~ 3x9 subject to ‘Ve constraints 3x; — xy ~ x9 23, x)—2) +x 22, 2h xp 2920. (Andhra, 1999) Phase ‘. Step 1. Express the problem in standard form. Introdu ing surplus variables s;, 8, and artificial variables Ay Ap, the phase I problem in standard frm becomes Max. 2" = Oxy + 0x2 + Oxy + 08; + 05 — A; —Ay subject to xy ~ 2-9-9) + 059 +Ay +04 =3 1-243 +051 ~99+ 0A; +Ay=2 24,2085, 815 82) Ay, Ag 20. Step 2. Lind an initial basic feasible solution. Setting 1 =x = 25 0, wehave .1)=3,4,=2 and Z*=-5 Initial simplex table is ° ° 0 ° 0 0 1d ee a e 4 Ate Oe) ° 1 ° 3 1 aA a 1 o 4 o 1 2 2 4 2 ° 1 toa ag 4 4 ° a ° ° 1 ‘As C; is positive under x; column, this solution is not optimal ‘Step 3. It rate towards an optimal solution. Making key element (3) unity and replacing A, by x, we have the new simplex table e 0 o ° ° oo ee Eas mw Ay > 6 ° s - -} 0 2 ° 2 0k : +3 1 1 yo 2 “boa L a 5 2 1 =i ° ee, 3 3 t Since G positive wader sy ands, elon, his solaton ao opinal876 _ HIGHER ENGINEERING MATHEMAnICS Making key ler ent (4/8) unity and replacing Ay by xy we obtain the revised simplex table @ ° 0 ° ° oa a B Basis xy 2 s a a" AL As 6 0 " 1 ° -1 1 4 5 ° 2 ° af 1 “ft 1 2 a ° ° ° ° ° ° ° G a ° ° o o 4 a Since all C;< 0, this table gives the optimal solution. Also" appears in the basis. Thus an optimal basic feasible soluti therefore to the or'ginal problem, has been attained Phase Il, Consiik ring the actual costs associated with the original variables, function is Max. Z'=~ 15/2c. + 8x9 + 0x5 + 06; + 0s - 04; ~ Oy subject to 8x, —29~59~51 +05 +A; + Ody =3, 2~42~:%3 +051 994 0Ay +Ay =2, Ye, ¥5, 51, 89, Ay, Ag 20 feasible solution thus obtained, will be an optimal basic feasible solution ‘mar = 0 and no artificial variable jon to the auxiliary problem and the objective ‘The optimal initi to the original LPP, Using final table »: phase I, the initial simplex table of phase II is as follows : @ 182 a ° ° ° ce Basis ” = = ’ 152 a a 12 ° v4 54 ° s o 1a 1 a 34 % 182 15/4 ° 158 7518 G ° 34 ° 158 Since all G £0, ts solution fe spinal Hence an optimal usc feasible solution tothe given problem ie =5/4.m4=02505/4 and min ete 27-10. EXCEPTIONAL (> \SES trary choice does'nt in any way affect the optimal solution re rie si outgoing variable, When more than one variable has the cone Teast Values of said ecers20? Ooliumn, ati fr the choice of outgoing variable eure Ips equal seas etal ratio are> choose any one ofthe prospective leary wand arbitrarily. Such ‘an arbitrary choice doesa t affect the optimal solution JF the equal values cf ratios are zero, the simplex method fails and we make use of the following degeneracy teck nique. LUNEA ‘ the b calle, iG solut: twoo L basic iterat of pro qT @ row. i matriy Gi EB subject So Sti Int Me Steation vest ble ing ast al ich he UNEAR PRO SRAMMING 877 {3 Te Beneracy. We know that a basic feasible solution is said to be degenerate if any of the basic variables vanishes. This phenomenon of getting a degenerate basic feasible oluna called de, neracy which may arise (0 at the initial state, when atleast one basic variable is zero in the initial basic feasible solution or (6) at any subsequent stage, when the least postive ratios under @-column are equal for two or mone rows, sanity ase; an arbitrary choice of one of these basic variables may result in one or more Pasic var-cbles becoming zero in the next iteration. At times, the same sequence of sumplog Srpestiena bested endlossly without improving the solution, These are termed as cycling type ofproblenu, Cycling occurs very rarely. Intact, cycling has seldom occurred in practical erobinns To avo d cycling, we apply the following perturbation procedure (© Divi le each element in the tied rows by the positive coefficients of the key column in that {() Cer spare the resulting ratios (fom lef to right first of unit matrix and then ofthe body ‘matrix, coliumn by column. (ii) T outgoing variable lies in that row which first contains the smallest algebraic rato, Examy le 27:21. Maximize Z=5x; + 3x9 subject to, +29 $2, 5x1 + 2p 5 10, 3x4 + Bxy < 12; xy, x9 20, Soluticn, Consists of the following steps : ‘Step 1 xpress the problem in the standard form. Introdu ing the slack variables s,s, sg, the problem in the standard form is Max. 11 = Sy +x + 05; + Osy + 053 1 +2 +9) + 05g +053 Bry + 2eg +05; + 59 + O55 Bey + Bp +08; + 05p + 55 = 12 1, 22,81, 89,8920. ‘Step 2. i'ind the initial basic feasible solution. The in:t al basic feasible solution is %1=22=0 (non-basic) 51 =2, 62 = 10, sg = 12 (basic) and Z=0, «Initia simplex table is @ 6 3 ° 0 ° e Basis * 2 * 2 ” 6 ° ° a 1 1 1 ° o 2 an ° ” © 2 ° 1 ° 10 106 ° a 8 8 ° ° 1 2 128 Zy=Eenay ° o ° ° ° 0 O=q- 5 a ° ° ° As G; is positive under xp columns, this solution is not optimal ‘Step 9. ‘torate towards optimal solution. #1 is ths incoming variable, But the first two rows have the same ratio under é-column, Therefore we apply perturbation method.878 HIGHER ENGINEERING MATHEMATICS First columa of the unit matrix has 1 and 0 in the tied rows. Divding these by the corresponding ele nents of the key column, wo get 1/1 and 0/5, s>-row gives the smaller tatie and ‘ therefore sy is the first outgoing variable and (5) is the key element, Thus the nev simplex table is © 5 3 ° ° 0 ce Basi 4 2 8 3 6 6 0 " ° (35) 1 ° ° ° 5 “1 1 25 ° 0 2 5 ° * ° ws ° 1 6 18/17 z 5 2 ° ° 10 G ° 1 ° ° 1 As Gyis positive under x column, this solution is not optimal, Making key cl ment (9/5) unity and replacing s, by xp, we obtain the revised simplex table ° 5 3 ° ° ° c Basis a 2 8 2 1 ° 8 2 ° 1 53 - ° ° 5 4 1 ° 2 we ° 2 ° ‘3 ° o ws ows 1 6 a 5 3 5 2 ° 10 G ° ° 8 ° {As 6,50 wd al columns, tis tale gives tho optimal sation, Hens an opinal Pook fonibl solution = 2,447 Oand ee Problems 275 Solve the following 1. > problems using M-method ' 1, Maximize Z =: + 2x5 + 3x5 subject to: 2x, -xp +25 $2, 8x, + dtp 426528, xy,29, 54520 2. Maximize Z subject to: x, + eg Bey $8, 20) +49 + ey = 12, 24, xp, 45 20 8, Maximize Z = 33, subject to: x; ~ 220, 22, + 84g <6, xy, x7 unrestricted 4, Minimize Z =a + d4y +5 subject to: x, + 2g + 4x52 12, Sey + 20y +452 8, xy, 29,2420. 5, Maximize 2 =, +24, + 3ry—x4 subject to: xy + 2xy + Bxy = 15, 2x; + x9 + 5x) =20, 10, x1, £0, 29,44 20 Rourkela, 1988) ‘Use two phase methed to solve the following L.P. problems 6. Minimize Z =1 + subject to= 22, 4 xp2 4,21 47x52 7, = ;20, (tactras, 1998) | tay 4 Sy xy b Uap tay tx 27 its pro sub; andee THEMATICS LINEAR? OGRAMMING. 879 by the 7, Maximize Z = 5x, + 3x, 8. Maximize Z = 5x, ~ dx, + dry, tatio and 1 swdject to: Bey +x 1,21 + 4x26, subject to :2ay + 2ey - xy 22, 4.2220, Bry 4x 53, x9 +25 <5, 9. Muximize Z = 5x, ~ dry + 3x, Fy Xp, X32 0. 842 ect to: 2ry + x, ~ Gry = 20, ° : 6x, + by + 105 < 76, ° 8x, ~ 8x + 6x5 $50, be 4,452.0. el Solve the following degenerate L.P. problems 10. Ma cimize Z = 9x, + 3x, LL, Maximize 2 = 2x; + 3x9 +1013 stbiect to: de; +258, 2r4 +4) $4, subject to ix, + 219 = 0,29 + x, m%20. 1 Xp, x5 20. x table: 27-11. (1) DUALITY CONCEPT —— One of the most interesting concepts in linear Programming is the duality theory. Every s linear grogramming problem has associated with it, another linear programming problem ipweiving the same data and closely related optimal solutions, uch eo Problems are said to be duals ofeach other. While one ofthese is called the primal, the other oe dual. Tie inportance of the duality concept is due to two main reasons. Firstly, if the primal Gontaing \ large number of constraints and @ smaller number ct variables, the labour of it Second 9: att be considerably reduced by converting it into the dual preblen cine then solving it Second'y, the interpretation of the dual variables from the ecat c= economic point of view V basic Maximize 2 = ey; +ept9 + nu. + cy. subject to he constraints aye, + ayg¥ + nn + ayy%y by, arty +2989 +n. + aagty S bp, G81 + OBE + oe + Ong Sy Fle Eppeeevvey hg 20, ‘To construct the dual problem, we adopt the following guidelines (The maximization problem in the primal becomes the minimization Problem in the dual and vice v2 sa, {¢° (S) ‘ype of constraints inthe primal become (2) type of constraints in the dual and vice {i The coofficients ¢1,c0.....4¢q in the objective function of the primal become bt» Bay... 9m in the objective function of the dual 1988) Go) The constants 83, Bp)... by in the constraints of the primal become c3, Capes bn the constrei ats of the dual. (oi {3+ primal has n variables and m constraints, the dual will have m variables and n ry the dat '« the transpose ofthe body matrix ofthe primal problem gives che body matrix of the dual880 _ HIGHER ENGINEERING MATHEMATICS (vi) The vari les in both the primal and dual are non-negative. Then the due! problem will be Minimize Ws: 949 + 6999+ ses +b subject to the cans raints ai) +agy2 4.0... Gn) 2ep yy] + 2079 + een +O 29, Apt + OBVQ + oe + Gyan 2 Epp Yay Yaron Im 20. Example 27-21. Write the dual of the following L.P.P. Minimize Z=341—2xy + 4x5, subject to xy + Sy +4xy 2 7, 6x, + x2 + Ixy? 4, 7xy ~ Bey x9 $10, 1 ~ Bg + 5xg 23, dy + eq ~ 2g 2 2, 2p, Xp, xy 20. Since the poll am is of minimization, all constraints should be of > type. We multiply the third constraint tlu oughout by 1 so that ~7x, + 2xp + xy 2-10, Let ¥1,2,95,)4 and yg be the dual variables associated with the above five constraints. Then the dual problein -s given by Maximize W= "yy + dy — 10yy + 3yq + 2y, subject to 33) + Gya— Tyg +34 + dys $3, By: +92 + 2y9—2y4 + Ty5 5-2, 41+ B92 +994 894-2955 4, 91,92, 99,I44¥52 0. (3) Formulatic n of dual problem when the primal has equality constraints. Consider the problem Maximize Z= > 21 +c9%9 subject to ayyxy + aygy=by, anne + anpte < by, xy, 2020. ‘The equality e> straint ean be written as 411 + Take S by and ayy, + ay9x9 2b, or anita ~ tata Sby and “aye, ~ aygep Sy, ‘Then the abov» problem can be restated as Maximize Z = +2) +09%9 subject to aqxy +aygty $y, -ay321 - aygry S~ by, ayes + O9t2 $y, Hy, 2220. Now we form the dual using yy,»;",72 as the dual variables, Then the dual problem is Minimize W=5 yy’ subject to ay, 9; 91") + Baya, (90+ aya er a2 Or ~91") + aaaye 2 ep, 9191" 9220. ‘The term (y;'~ 31") appears in both the objective function and all the constraints of the dual ‘This will always ha pen whenever there is an equality constraint in the primal. Then the new variable yy’ ~," (='3) becomes unrestricted in sign being the difference of two non-negative variables and the «t ove dual problem takes the form In thy Co sue the Writemanes tiply the ts. Then onsider > dual. gative UNEAE § ROGRAMMING 881 Minimize W=byy1 +byy9, suljectto arya +anvy22¢y,a91 + aps¥2 2 ep, ¥; unrestricted in sign, yp 20 In gen ral, ifthe primal problem is Neximize Z = e121 +909 + us Heyy subjectto —aqixy + ayptp + nn. + O3nty ait + Op2t + en + Oa 2 + Onan =By Hy Meeig 20, mitt + Gata + then t1» dual problem is Mrimize W=byy1 + by¥9 +... + Bp subjecs 0 ayy, +4212 + ns + Omi 2EH, M+ 42079 + oon + Oma 2 C0, QynV1 + Ag92 + ost Opn ey Yo Iau all Unrestricted in sign Thus the dual variables corresponding to equality constraints are unrestricted in sign Convers ly when the primal variables are unrestricted in sign, corresponding dal conctracs are equa'ites. Exa mple 27.23. Construct the dual of the L.P.P : Max mize Z = 4x, + 9x + 2x5, subject i Bay + 3g +25 $7, Bey Bq +4595, xy, xy, 2y20. Let: and yp by the dual variables associated with the first and second constraints, Then the duel problem is Mini nize W= 71 + 5y2, subicet to By1 + Bya 5 4, 995 — 2y0 $9, 293 + 4y0 <2, 91 20, y9 is unrestricted in sign, Problems 27.6 Write ths tuals ofthe following problems (1 ~ 4) 1, Me imize Z= 10s; + 134, + 19%5, suzsetto Gry + 8xy + B55 $26, dry + Beg + By 57, 2, 2,452 0. 2 Min mize Z= 2x, +4ry+ 855 suet to Bay day ng 211, 2 ~ Sey + 6p $7, 24 ~ Beg Beg 5} Sy + 2 + 255 25,425,752 0 8. Mex mize 2.=35, + 162, +725 subjetto sy —xp42528,-865 +2855 1,26, 29-1 4. Min mize 2 = 2x, + 3p + 4g ubjict to Rey + 8x, +8122, Sn, +25 + 25) =3, 2+ dey + Gry $5, x1, 720 and xy is unrestricted, tadras, 1996) 5. Obsein the dual problem of the following LPP Macmise ls) =2x) + 52+ 655 ule ct to Bx + Gry — x5 $3, Bey 4 xp +g 54,2) Sey 3551, = Be, ~ B59 +729 5 6,21,29. 5520. ‘Als verify that the dual of the dual problem is the primal problem. (tadras, 1991 8) #1 4920.882 HIGHER ENGINEERING MATHEMATICS 27:12. (1) DUALITY PRINCIPLE Ifthe prima! and the dual problems have feasible solutions then both have optimal solutions t and the optimal wsive of the primal objective function is equal to the optimal value of the dual objective function t« Mac. Z=Min. W | ‘This is the fund: mental theorem of duality. It suggests that an optimal solution to the primal problem can dircetly be obtained from that of the dual problem and vice-versa, (2) Working 1% les for obtaining an optimal solution to the primal (dual) problem from that of the dl 1al (primal) : ‘Suppose we hay already found an optimal solution to the dual (primal) problem by simplex | method, Rule 1. If the pr-mal variable corresponds to a slack starting variable in the dual problem, then its optimal va te is directly given by the coefficient of the slack variable with changed sign, in the C; row of the « ptimal dual simplex table and vice-versa. Rule Il Ifthe pr mal variable corresponds to an artificial variable in the dual problem, then its optimal value is cirectly given by the coefficient of the artifical variable, with changed sign, ‘ in the C; row of the cptimal dual simplex table, after deleting the constant M and vice-versa, On the other his d, ifthe primal has an unbounded solution, then the dual problem will not have a feasible solut on and vice-versa Now we shall werkout two examples to demonstrate the primal dual relationships. Example 27-2:. Construct the dual of the following problem and solve both the primal and the dual Maximize Z=2¢ +x, uN! fae subject to ~xj+ 2xp $2, 21 +39 $4,219, 21,2920. / 7 Solution using the primal problem. Since only two variables are involved, it is conveniont ‘ to solve the problem. sraphicaly. | i In the xy, xyplere, the five constraints show that the point (ey, x2) lies within the shaded | a region OABCD of Fiy 27-12. Values of the objective function Z = 2x, +2, at these cornere are (0) = , AE) = 7, AC) = 6 and Z(D) = 1. Hence the optimal solution is x; = 3, x9 = 1 and | Ps { 4 i ry @ Fig. 2712 Solution using :} ¢ dual problem. The dual problem of the given primal is | Minimize W= 211+ 4yy+3yq subject to “Vatye+¥32 2, Ii ty22 Lyn ye20. IEMATICS slutions hhe dual primal coblem ‘implex ‘oblem, dsign, a, then d sign, rsa, “ill not Wand rnient raded sare Land UNGAR OGRAMMING 883 ‘Stet 1. Express the problem in the standard form {ivr aveing the slack and the artical variables, the dual problem in the standard form is Mex, W = —2y, ~ Ayo 399 + sy + 0sq— MAy — Mag subjret to - 91 +¥9+y3~91+05y +Ay + Ody =2, 2y1 +92 + Oy + Os; ~ 99404; + Ay =1 ‘Ste 2 Find an initial baste feasible solution, ‘Setsig the non-basic variables , 9p, 93,5, #9, each equal to Zero, we get the initial basic feasible elution as N1=92=99= 8 (non-basic) ; Ay Aa =1. (basic) * Inicial simplex table is ee o 2 «4 @ po reams eae ar er eee ee ec 6 MA 1 Loo ° 1 ° 2 om Mo 2 wm 0 oa ° 1 1 ome 5M egy SMR Me ea wg ° 45 G13 positive under some columns, the initial solution isnot optimal ‘Step + Ierate towards an optimal solution. (@ Intr duce yz and drop Ag, Then the new simplex table is ese ° M fee wt . ° Moa og 2 wm 4 1 too » one 4| » 2 1 ° o 4 o 1 1 ow M8 ae ae 5 6-am 9 M3 M oM-4 9 7 AS G1 postive under om column, hl slation a opin i Now introduce yy and drop Ay, Then the revised sehen ig & ry 4 = ° ° oN = ite oy, ” n * 2 Ay As ° a ” “ ° 1 a 1 a 1 4 ” 2 1 ° ° ° 1 1 % 1 4 3 a 1 4 4 4 & a ° o 3 3-M iw As all C; 50, the optimal solution is attained, ‘Thus an «ptimal solution to the dual problem is »¥2=1,¥9= 1, Min, W=- Max. (W)=7,884 HIGHER ENGINEERING MATHEMATICS To derive the cp imal basic feasible solution to the primal problem, we note that the primal variables x;, x2 corre spond to the artificial starting dual variables Ay, Ag respectively. In the final simplex table of the dual problem, C; corresponding to A,, and Ag are 3 and 1 respectively after ignoring M. Thus ty rule II, we get opt. x; = 8 and opt. x2 = 1 Hence an optiru:l basic feasible solution to the given primal is, 53,3; ‘Obs. The validity ifthe duality theorem is therefore, checked since max. Z = min. W=7 from both the methods, Example 27.25. Using duality solve the following problem Minimize Z = 0x, + 05x) subject to xy 2 4, xp 26, x1 + 2xq220, 2x) +92 18, 24,920. The dual of the jiven problem is Max. W=4y, + 6y2 + 20y9 + 184, subject toy) + ¥3+2¥4 S07, yo + 2yq +4 $05, 91,92, 9994 20. ‘Step 1. Express te problem in the standard form. Introducing slac : variables, the dual problem in the standard form becomes Max. W= 4y1 + €y2 +2079 + 18y4 + Os, + Oss, subject to ¥1~ Wo +y3 + 2yq +8) + 0sg=0-7, Oya Ya + 2¥g +74 +081 + 82 = 0-5, 91,92, 999420. Step 2, Find an initial basic feasible solution. Setting non-basi : variables yi, yo, 93, 94 each equal to zero, the basic solution is Nye 2=99= = Gaon-basic); s,=0:7, s9=05 (basic) Since the basic v riables s,, s2 > 0, the initial basic solution is feasible and non-degenerate. ;max. Z=7, Initial simplex x ble is @ + * © wo ° Bais wt ® ° ° 8 1 ° 1 2 1 0 07 ona a ° 1 @ ° 108/26 4 ° ° ° o ° ° ° G ‘ 6 » wo ° : t ‘As G;is positive :n some columns, the initial basic solution is not optimal. Step 3, Iterate tovvards an optimal solution. (@ Introduce yg ad drop 62. Then the new simplex table is @ 4 ¢ 0 ww 0 ° - aoe te al pee) . ° o a ST aoe o wm 4 4 o Ww ow ow 4 ° 0 ww 0 wo 6 G 4 4 0 8 ° -t0 . 1 ob directly Using de LM 2. Ms oul 3. Me sul 4. Me sul 27.13. ( Ing by intr: primal- method) a basic method dual sir the erite we ee————_—_____.. HeManics primal the final ely ater both the erate m” ne de LINEAR 280 SAMMI 885 Asc ‘18 Positive under some of the columns, this solution je not optimal, @ Introduce y4 and drop s;. Then the revised simplex table is ee Basin yy ” a» x 8 2 8 18 u 2 4p ° 1 2% ano 20 no 49 oon 1 ° peat ne % wo soy 1988 tang 6 48 as ° O16 aa As ell ©’, this table gives the optimal solution, ‘Thus ¢2) optimal basic feasible solution is , Step 4. Verive optimal solution to the primal, We note that the primal variabl s2 Tespective y. In the final simplex $2 are ~16/: nd -22/3 respectively, 8 = 20, ¥4= 18, max. We 7.4 les 21, xp correspond to the slack starting dual variables s;, ‘able of the dual problem, C, values corresponding tos, and Thus, by rule I, we conclude that opt. x; = 16/8 and opt. x, Hence ar optimal basic feasible solution to 22/3; min. 2= 74, the given primal is Problems 27.7, Using duality s Ive the following problems (1 4) 1. Minimise Z=2s, + 919 +25, subject 10 y+ dup 2 Maximize Z = 24; +z, subject ts 24+ 2095 10,5 +2966, — 8. Maximiz> Z= 3x, + 2x9, + 2g 25, 86) 429+ 209 24 and xy, 2520, 22,21 ~ Dep 1, 25,2920, Apbiecs te sita2 1x1 42957, x, 6209510,2553, 1% 20, (Madras, 1996) 4. Maximian 1 35, + 209+ 51 subject te xy + 2p 7995 490,35, +20y $460, + Ay 5 420, sy, 27-13. (1) DUA. SIMPLEX METHOD 320. (Andhra, 1990)886 - HIGHER ENGINEERING MATHEMATICS ue, we first determine :le outgoing variable and then the incoming variable while in the case of regular simplex met od reverse is done. — (2) Working prc-cedure for dual simplex method : ‘Step 1. @) Conver the problem to maximization form, if tis not 80 (i) Convert 2) ty @ constraints, if any to (<) type by multiplying such constraints by 1 Gili) Express the groblem in standard form by introducing slack variables. Step 2, Find thei itial basi solution and express this information inthe form of dual simplex table Step 3. Test the nature of C= 6j—2; (@) all C,< 0 ex all b;2 0, then optimal basic feasible solution has been attained. ) all C0 er at least one b, <0, then go to step 4 (c) Ifany C20, the method fails. ‘Step 4. Mark th: outgoing variable. Select the row that contains the most negative b,. This ~ will be the key row 2d the corresponding basic variable is the outgoing variable. 7 Step 5. Tet the nature of hey row elements sates (a) all these el« ments are 2 0, the problem does not have a feasible solution. ‘ @) Ifat least one slement< 0, find the ratios ofthe corresponding elements of Crow to these § elements. Choose the smallest of these ratios. The corresponding column is the key column and outge the associated variab eis the incoming variable. $ Step 6, Ierate to./ards optimal feasible solution. Make the key element unity. Perform row hey operations asin the ~ gular simplex method and repeat iterations until either an optimal feasible 1 solution is attained o° there is an indication of non-existence of a feasible solution. fern Example 2726. Using dual simplex method i maximize - Sx1~ 2x, s subject to xy 4:ig2 1,xz +4pS7, x1 + 2x92 10, xy23, x12 0, 2220. (Madras, 1993) Pon Solution. consis of the following steps soluti ‘Step 1. (i) Convert the first and third constraints into (S) type. These constraints become sony 2 $-1,-m1- 285 10, (i) Bepress the >.oblem in standard form 2 Introducing slac} variables s,s, $5 4 the given problem takes the form ° Max, Z= — 3%, - xp +05; +08 + 083 + 054 0 subject to xy xp +0) = — Ixia tz=7, —x1~ 2p +99 —10, - y+ 473.210 Sy 89, 8958420. ° ‘Step 2. Find the initial basic solution ‘Setting the decis on variabl 1, x2 each equal to zero, we get the basic solution 1,99= -10, 0, =8 and Z=0.saris LUNEAR 22> SRaMMING 887 ase of + Ini ial solution is given by the table below 5 Sea ° ° ° <3 Basis * 4 8 4 8 1 ° 4 eee ° ° ° ° a 1 to 1 ° oe plex ° % a) ° 1 0-106 ° % ° 10 ° ° 13 2-2 yay ° oo ° o ° 0 6-4-4, “2000 ° ° ° t This Step 3. Test nature of C, Sisee sll Gj values are $0 and $= -1, 6,= - 10, the initial solution Ls optimal but infeasible. \Ve therefore, proceed further. Step 4. fark the outgoing variable hese Since o: is negative and numerically largest, the third row is the key row and 9 is the and outgoing vi iable Step 6 Valeulate ratios of elements in Crow tothe corresponding negative clementa of the row fey row. sible ‘These retios are —3/— = 1 (neglecting ratios corresponding to + ve or zero clements of ey row), Since the smaller ratio is 1, therelare, speslonr era key column and (2)is the cy element. ‘Step 6. lizrate towards optimal feasible sotution. a Gi Drap sy and introduce alongwith its associated value ~ 2 under cp column. Convert the Key clemen: to unity and make all other elements of the key columa Gan ‘Then the second solution is given by the table below o ~2 0 0 0 ° oo Jasio xy Py ‘3 % 6 ° 4888 HIGHER ENGINEERING MATHEMATICS Since all C, vals are <0 and 64 = ~ 2, this solution is optimal but infeasible. We therefore proceed further. (Gi) Mark the out oing variable Since bg is neget.ve, the fourth row is the key row and s, is the outgoing variable. (iii) Calculate r+ ios of elements in Cprow to the corresponding negative elements of the key ae This ratios is ~ 1/-3 4 (neglecting other ratios corresponding to +ve or 0 elements of key row), xycolumn is ‘le key column and : Gv) Drop s4.and i ttroduce x, with its associated value ~ 3 under the eg column. Convert the key element to unity ::nd make all other elements of the key column zero. Then the third solution is given by the table »elow 6 - ° ° ° ca Basis 4 aon 2 % " . ° 4 ° o 1 ° <1 0-1 6 ° * ° oo 1 1 1 ° 2 ° 1 0 ° ° 1 3 3 oy 1 o 0 ° -1 0-2 4 z -3 2 0 ° 3 4-8 ¢ ° oo ° ed Since all C; valves are < 0 and all b's are > 0, therefore this solution is optimal and feasible, ‘Thus the optimal so't tion is x, =4, x =8 and Zjae= — 18. Example 27:27. Ising dual simplex method, solve the following problem: Minimize Z=2c1+2xy +423 subject to 2 0, this solution is optimal and feasible, Thus the optimal solution is x O and max. Z’ = ~ 4/3 ie, min. 1, x= 2/8, x 8