Duality in Linear Programming “Man is simply 10 recognise that there are different approaches for solving problems” 5:1. INTRODUCTION Associated with every linear programming problem (maximization or minimization) there always exist another Linear Programming problem which is based upon the same data and having the same solution. The original problem is called the primal problem while the associated one is called its dual problem. It is important to note that either of the two linear programming problems can be tweated as primal and the other as its dual. The two problems, thus, constitute a primal-dual pair. The concept of duality is based on the fact that any linear programming problem must be first put in its standard form before solving the problem by simplex method. Since, all the primal-dual computations are obtained directly from the simplex table, it is logical that we define the dual that may be constituent with the standard form of the primal. ($2 GENERAL PRIMAL-DUAL PAIR Based on the standard form of primal, there are two important primal-duial pairs : Definition 1. (Standard primal problem) Maximize z= c)x; + €2%z +... + CyXq subject to the constraints + xy + Qk, + oon + Uinky = By 4205 Dual Problem Minimize 2* = byw, + byw; +. + by Wy subject to the constraints : ayy + yyy + one + Oy Wy 2 655 w; (= 1, 2... m) unrestricted are the primal variables, w,’s the dual variables and the other constants have their Note that usual meanings. Definition 2. (Standard primal problem) Minimize z= ¢)X) +,¢2%z +. + Cy%q Subject to the constraints : bs i FFL Bown aya, + apr, + on. + dint a Dual Problem 3 Maximize 2 = bjw; + b2W, +... + DyWy subject t0 the constraints : yw, + dyyWy + oa. + yy Wy S C3 w; (i = 1, 2, ....m) unrestricted. Scanned with CamScanneree q 130 OPERATIONS Res: ARCH Remark. From the above definitions one may easily observe the following: there is a dual variable. (a) For every primal constraint (b) For every primal variable, there is a dual constraint (6) The coefficients of the dual variables in the const primal variables except that they are transposed, i... columns im pri rows in the dual coefficient matt, (a) The number of dual constraints is exactly equal to the number of primal variables. whereas the number of dual variables is exactly equal to the number of primal constraints. (e) The objective coefficients of the primal variables become the right-hand side cont tte of dual vsasinte whereas the right-hand side constants of the dual constraints become the objective coefficients of the primal problem. The information regarding the primal-dual objective, variables may be summarized in the following table : Itints are the same as the coefficients of the nal coefficient matrix become the type of constraints and the signs of the dul Standard primal ~ ‘Dual objective Objective Constraints Variables ‘Maximization ‘Minimization 2 Unrestricted Minimization Maximization s Unrestricted f . FORMULATING A DUAL PROBLEM Various steps involved in the formulation of a primal-dual pair are > Step 1. Put the given linear programming problem into its standard form. Consider it as the primal problem. Step 2. Identify the variables to be used in the dual probl equals the number of constraint equations in the primal. Step 3. Write down the objective function of the dual, using the right-h primal constraints. If the primal problem is of maximization type, vice-versa. Step 4. Making use of dual variable identified in Step 2, write the constraints for the dus! problem. (a) If the primal is a maximization prob’ m, the dual constraints must be all of “2° type. Ife primal is a minimization pfoblem, the dual constraints must be all of ‘<" type. “(b) The column coefficients of the primal constraints become the row coefficients of the du constraints. (c) The coefficients of the primal objective function becomes the right-hand side constants of dual constraints. (d) The dual variables are defined to be unrestricted in sign. Shep 5. Using steps 3 and 4, write down the dual of the given L.P.P. lem. The number of these variables and side constants of the the dual will be a minimization problem and yf the: ‘Note : ‘The dual constraint corresponding to an artificial variable in the standard form of the primal is always redundant, heuce it is never necessary to consider the dual constraint associated with an artificial variable. Remarks, 1. If the given linear programming problem is in its eanonical form, the primal-dual pat is said to be symmetric. ; Fit the given linear programming problem is in its standard form, the primal-dual pair is said to be unsymumetric. Scanned with CamScannerDUALITY IN LINEAR PROGRAMMING 131 5:4, PRIMAL-DUAL PAIR IN MATRIX FORM ndard Primal Problem Definition 1. (Standard primal probl ind x7 © Re La ne contra fem). Find xT © RY so as to maximize z= ex, ¢€ RY Ax=b and x20, bT Rm where A isan mxn real matrix, ual Problem. Find w? eR” ae . D ind WT © R so as.t0 minimize 2x = blw, be RM subject to the constraints : a Alw 2 cl ce RY ‘ where AT is the transpose of an mn real matrix A and w is unrestricted in sign, Definition 2. (Standard primal problem). Find x7 € R" so as to minimize subject to the constraints : = ex, ce RY ; Ax=b and x20, ble RM where A is an mXn real matrix, ind wT @ Re ; Dual Problem. Find w" € RY, so as to maximize 2 = bTw, b € RM subject to the constraints: uv i Alw scl ce R" where AT is the transpose of an mn real matrix A and w is unrestricted in sign. SAMPLE PROBLEMS $0 Formulate the dual of the following linear programming problem : v Maximize z = 5x, + 3x, subject to the constraints : 3xy + Sky $ IS, Sxy + 2xz $10, x) 20 and xy 20. Solution. Standard Primal, Introducing slack variables s, 2 0 and s 2 0, the standard linear programming problem i Maximize z = Sx, + 3x + 0's, + O's, subject to the constraints : Bry + Say + 51 + Og = 15, Sxy + 2ey + O51 + 52 = 10, xp, xy 51. 52 20 Dual. Let w, and w, be the dual variables corresponding to the primal constraints. Then, the dual problem will be : Minimize z* = 15w, + 10w, subject to the constraints : Bw, + Sw 25, Sw) + 2) 23 Ww, + Ow, 20 o jy, 8 ae Op w, 20 and. w = 5 w and w, unrestricted (redundant). ‘The dual variables “Ww, and w, unrestricted” are dominated by w, 2 0 and w, > 0, Eliminating redundancy, the restricted variables are w, 2 0 and w, 2 0. (2. Write the dual of the L.P.P. : : Minimize. z = 4%) + 6x, + 18%; subject to the constraints xy + 3xq 23, Xp + 2p ZS-and xp, xy xy 2 0. [Delhi B.Sc. (Stat,) 2006] Solution. Standard Primal. Introducing surplus variables s, 2 0 and s,°2 0, the standard form of the L.P.P. is: Minimize z xy + Bry — 5) = 3s Oxy + ap + ty - = Ax, + 6x + 18x, + 0-5, + 0-5, subject to the constraints Xp Age Be Sy 82:20 ATTN A Scanned with CamScanner E s32 OPERATIONS RESEARCH Dual. If, and wy be the dual variables corresponding to each primal constraint. the dual problem will be 3w, + Sw subject to the constraints + Maximize z* wy + Oy $4, Buy + wy $6, Owe + 22 S 1B: wy, + Oo $0, and Ow - w2 5% w, and wy unrestricted (redundant). Eliminating redundancy, the dual problem is : Maximize zt = 31, + 502 wy $4, 3wy + wy $6, 2og S185 . aa ramming problem: 503, Write the dual ofthe following lear Pre Te constants: /S Minimize 2 = 3x, ~ 2x2 xy + Sry + 43 27 Oxy + 32+ Ses 24 Ixy ~ 2x — 3 $10, ay — 2x + SH 2S fxy + 7xq — 2x3 22, 4 2H 4g 20, 120 Solution. Standard Primal. Introducing surplus variables 1 20, 2 20 42 slack variable s, > 0, the standard form of L-P.P. is : : = Pye 3x, — Dey + Any + 05, + OS + Oe + Os subject to the constraints : aint : subject to the constr 0. w, 20 and 22 0, ss 2 0 anda Minimize z 3x + 5m + 45-1 = 7 6+ mt3g-2=4 10 Tx -2n- t= ay - 2a + Sty - 54 = 3 Ary + Trg - 2x3 - 55 = 2 20. is Xp 236 Sts Sos Sh St $5 ponding to the five primal constraints 3, 4, 5) are the dual variables corres} standard primal L.P.P. is : + 2ws subject to the constraints : Dual, If w,(j = 1, 2 in the given order, the dual of the st Maximize zt = 7w, + 4w, + 10w, + 3¥% Bw, + wy + Tws + wy + dws $3 Sw + Wz — 2ws ~ 2Wg + Tws S -2 4wy + 32 - Wy + Sy — 2ws S 4 wy $0, =, $0, w $0, — my $0, ws $0 w= 1 23,4, 5) ate unrestricted in sign. Eliminating redundancy, the dual variables are : w, > 0, w, 2 0, ws $0, ws 2 O and ws 2 0. Note. In the primal, if we multiply the third constraint throughout by —1, the dual variable w3 will be 2 0 insteadof < 0. /; 504/ Obtain the dual of the following LP.P. : _/ Maximize % = 2x, + 3x, + x; subject to the constraints : dry + 3iy +45 = 6 a 42mg + SR = 45 Xp Xp 520 Madras BE. 19) Solution. Clearly, the given linear programming problem is in stai idering i standard primal, its dual is : indard form, Considering it as Minimize 2* 4wy + Wz 22, 30, + 2wy 23, wy + Sw2 21; wy and wy are unrestricted, where w, and w, are dual variables. , 6w, + 4 subject to the constraints : Scanned with CamScannerSW ~ DUALITY IN LINEAR PROGRAMMING 133 505, Obtain the dual problem of the following primal problem : Minimize z = x; ~ 3x, ~ 2x, subject to the constraints : Bxy - x2 + 2x3 S 7, 2ey - dey 2 12, 4x) + 3xy + Bxy = 10 X42 20 and x; is unrestricted, [Delhi B.Sc, (Stat.) 1995} Solution. Standard Primal. Introducing a slack variable s, 2 0 and a surplus variable 5, 2 0, the primal problem is restated as Minimize z = ex subject to the constraints : Ax where x = [ty 254" sy he = (1, -3, -2, 2,0, 0), b 3-1 221 «0 2 -4 0 0 0 -1}, when x3 = ay - 345”. 4°38 80 0 Dual. If w = (wy, wz, ws) are the dual variables, the dual problem of the prima Maximize z* = b and x20, (7, 12,10] and A Tw + 12Ww, + 10w; subject to the constraints : Biv, + 2wy - 403 S 1 . = Wy = dey + By S—3 > wy + 4g — 3s 23 2m, + 8wy S-2 =2w, - 83S 2 wy $0 -w, 50 wi. w2 and w3 unrestricted. Eliminating redundancy, dual variables are w, < 0, w, > 0 and ws unrestricted. This is re-written as follows : } 3 -2m ay = 2 Jomso and w) > 0 Maximize z* = 7w, + 12w + 10w, subject to the cons Buy + avy — 4¥y S 1, wy + 4g — 303 2 3, —2wy - Bw, ts: wy $0 and wz 20, wy unrestricted. Note. In the primal, if we multiply the first inequation by -1; the dual variable w; will be 2 0 instead of $0. PROBLEMS Formulate dual of the following L.P.P. (@) Maximize z= 4x, + 2x, subject to the constraints : x) +23 4-42-25 20 and 20. (Annamalai MBA. (Nov.) 2009) (6) Maximize z = 2000x + 3000y subject to the constraints : Gx + 9y $100, 2 + y $20; x20 and y20, (Osmania M.BA. (Sept.) 2001) 50J-Formulate the dual of the following L.P.P. : Maximize z = 10x, + 8x2 subject to the constraints : ‘ ay + 2ey 2S, 2p EIA Ky HID e A x, 20 and x; is unrestricted, [Osmania M.B.A. 1999) ‘S08. Obtain the dual problem of the following L.P.P. Maximize f(x) = 2x) + Sxq + Gry. subject to the constraints : Sey + 6%; — ay $3, -24 ty tae $4, Sy +H AQ SL, 3k = By + Try $6 ay ty ay 20. Scanned with CamScanner134 / OPERATIONS egg, Find the dual of the following Lp.p, : Maximize te lys A subject to the constraints NSH SI ay 4 ay 0, ‘ 4 unrestricted 510. Obtain the ys dy sm: ge and 4, unreste in the dual of the following linear Programming problem Maximize 2416 Bey + gy subject ta the constraints 1 MOM, Hy Oy Ody Sy 1, Obtain the dual problem of the following LPP, Maximize z= xj ~ 2x + Bey subject tthe constraints: = 2 + 420. Madre HE, yy tay 2 dey ede 6 ey BE tae ty 2 S12. Obtain the dual of the following finear programming problem : Minimize z= xy + ty + xy subject to the constraints : ay = ny 6 Any Sy 2g 3, Beh 44. % 2:0 andy unrestricted. [Garkwal M.Sc. (Mat) rp, 513. Give the dual of the following L.P.P. + Minimize z= 2x; + 3xq + 4ry subject to the constraints = 2 tI S22 Ite Iya 4 4 4g + OH SS yy 422.0 and xy is unrestricted. S14. Maximize z = Gx, + Gr +43 + Tg + Sts subject (0 : fey # ey + ty 6 Seg ry 2 Dey Hay t Udy + Ot + 9 = sy Ap ty My 20, 5 unrestricted, 5 DUALITY THEOREMS Theorém S41. The dual of the dual is the primal. Proof. Let the primal L.P.P, be to determine x7 € R" so as to Maximize f(x) = ex, ¢ € RY subject to the constraints : Ax=b and x20, ble R" where A is an m x1 real matrix. The dual of this primal is the L.P.P. of determining w” € RM" so as to Minimize f(w) = b’w, b’ € R” subject to the constraints : ATw 2 c7, w unrestricted, ¢ € RY, Now, introduce surplus variables s 2 0 in the constraints of the dual and write w = w; -™%> where w, 2 0 and w, 2 0. The standard form of dual then is to Minimize g (w) = bT(w, ~ w; bY € R™ subject to the constraints AT(w, - 2) - 1,8 = 07, ce R" wy, wz and s 2 0, Considering this linear programming problem as our standard primal, the associated dual proble™ will be to Maximize f(y) = ey, ¢ € R" subject to the constraints : (ANTY SDT), <(AT YY s -bhy, : -y $0 (=> yz 0) and y unrestricted, ad Scanned with CamScanner135 DUALITY IN LINEAR PROGRAMMING Eliminating redundancy, the dual problem may be re-written as : Maximize f(y) = cy, ¢ € R" subject to the constraints = Ay sb aye) = Ay=b, bre R” y20. ‘This problem, which is the dual of the dual problem, is just the primal problem we had started with. ‘This completes the proof. aid 52 (Weak Duality Theorem). Let x, be a feasible solution to the primal problem Maximize f(x) = ex subject to: Ax c? and Bote” 2 0. Now, if we let B+! c,” = w,, the above become ATW, 2 cT and wy 2 0, Wo’ € R". This means that w, is a feasible solution to the dual problem. Moreover, the corresponding dual objective function value is, yo for all j (in matrix form) bl w, = wT b = eg Bb = cg Xp = Xo Thus, given an optimal solution x, to the primal, there exists a feasible solution w, to the dual such the ex, = b’w,. Similarly, starting with w,, the existence of x, can be proved. Corollary. f/x, is an optimal solution to the primal, an optimal solution to the dual is given by W, = B+ ep, where B is the primal optimal basis. Note, Obserye that B-! ep represents optimum z; - cj under primal slack columns. theorem $45 (Fundamental Theorem of Duality). If the primal or the dual has a finite optimum sofution, then the other problem also possesses a finite optimum solution and the optimum values of the objective functions of the two problems are equal. Proof. Consider the primal-dual pair Primal. Maximize f(x) = ex subject to: Ax Sb and x > 0. Dual. Minimize g(w) = b’w subject to: ATw >" and w>0. (Necessary condition). Let a feasible solution x, (w,) be an optimum solution to the primal (dual) problem. It then follows from Theorem 5-4 that there exists a feasible solution w, (x) to the dual (primal) problem, such that ex, = b w,. It now follows from Theorem 5-3 that w, must be optimal, , This proves the necessity of the condition. nee It follows from Theorem 5-3. Atheorems$6 (Existence Theorem), If either the primal or the dual problem has an unbounded objective function value, then the other problem has no feasible solution, _ Proof. Let the given primal problem have unbounded solution. Then for any value of the objective function, say +0», there exists a feasible solution say x yielding this solution, is cx — ex, If possible, let the dual problem have a feasible solution. Then from Theorem 5-2, for each feasible solution w, of the dual, there exists a feasible solution x, to the primal such that €% S bY w,, That is, bY w, —> e. Now as b is constant and w, has to satisfy the constraint ‘ _ Scanned with CamScannerDUALITY IN LINEAR PROGRAMMING “7 ar My % e% therefore the dual objective function b’w, must be finite. This contradicts the result bé'w, — ©. Hence the dual problem has no feasible solution. i By a similar argument it can be sho bounded solution, the Rey ale aaa shown that when the dual has an unboun Standard results on duality can be primal Dual problem Feasible Solution _ No Feasible Solution In the following section we shall see how the above existence theorem helps us in the relationship between the optimum values of the primal and dual variables. Dual Unbounded Unbounded or Infeasible understanding 5:6. COMPLEMENTARY SLACKNESS THEOREM em 5-7 (Complementary Slackness). Let x, and w, be the feasible solutions to the primal { max. e'x | Ax Sb, x 20) and its dual { min, btw | Alw 2 cl, w 20} respectively. Then, a is is that necessary and sufficient condition for x, and w, 10 be optimal to their respective probler wa (b = Ax) £0 and xF(Alw, = ef) = 0. Proof, Necessity. Let a = w,'(b - Ax) and B = x,"(AMW, ~ 6%). Since Xp Wy are feasible solutions to the primal and dual respectively, we have a20, B20 and at+Pew,'b- xe 0. But since ct 2 O and i > 0, this Now, if x» ®, are optimal, then ex, = b'w, so that a + B gives a = O and B = 0. ‘Thus the conditions are necessary. Sufficiency. Let the given conditions hold for the feasible solutions x, and w,. That.is, a = 0 and B = 0. Then O- a+ Pawth- xfer = cx, = DP = x, and w, are optimal, Thus the conditions are sufficient, Corollary 1. If x° and w° be feasible solutions to the primal and dual problems respectively, then they will be optimal if and only if we Fairy = 0 fen PCE ae? ~ a and jet Proof, From the above theorem, x° and w° will be optimal, if and only if wol(b - Ax) = 0 and x,7(€" ~ ATw,) = 0. Consider the first set of conditions. Since each term in the summation w,"(b ~ Ax, is non-negative, it follows that = Fags) = 0, Scanned with CamScanner| 1 38 OPERATIONS RESEARe, Similarly, the second set of conditions is equivalent to Jeb al orollary 2. For optimal feasible solutions of the primal and dual systems, whenever the jy variable is strictly positive in either system, the ith relation of its dual is an equality, " Proof. It follows from corollary 7, that wer 0a E ayxp = (ith primal relation) and a9 > 0 => E ain? th dual relation Corollary 3. For optimal feasible solutions of he primal and dual systems, whenever ith relation A either system 1s satisfied as a strict inequality, then the ith variable of its dial vanishes, Proof. If follows from corollary J that ayxP we =0 and E ayw? > 6 > xP =0. i a Remarks. The conditions of corollary 1 can also be written as WP ty = 0 and 9. = 0 where ¥y41 is the ith slack variable in the primal problem and Wj iS the jth surplus variable in the dual, Thus, the theorem relates the variables of one problem to the slack or surplus variables of the other. The above relations are called ‘complementary slackness’ because they imply that whenever a st DUALITY AND SIMPLEX METHOD. Since any L.P.P. can be solved by using simplex method, the method ig applicable to both the primal as well as to its dual. The fundamental theorem of duality suggests that an optimum solution vo te associated dual can be obtained from that of its primal and vice versa. If primal is a maximization problem, then following are the set of rules that govern the derivation of the optimum solution : Rule 1. Corresponding net evaluations of the starting primal variables = Difference between the left and right sides of the dual constraints associated with the starting primal variables. Rule 2, Negative of the corresponding net evaluations of the starting dual variables ‘ = Difference between the left and right sides of the primal constraints associated with dual starting variables: Rule 3. If the primal (dual) problem is unbounded, then the dual (primal) problem does not have any feasible solution. be Note. In rule 2, dual problem is to be solved by changing the objective from minimization to the maximization. : ‘Scanned with CamScannerDUALITY IN LINEAR PROGRAMMING 199 . SAMPLE PROBLEMS 515,Ose duality to solve the following LP.P. : , Ae = 2t, + xy subject to the constraints ¢ Hy + 2xy $10. 5) + xy $6, xy ~ 22 $2 ay - WH ST tH ZO [Delhi B.Sc. (Stat.) 2006) Solution. The dual problem of the given primal is Minimize :* = 10w, + 61 + 2w, + wy subject to the constraints : Wy # wy + wy + wg 22, Dy # wy = wy — 2g 2 vy wa 2 0. ; . fy = wy — 2g 2 Dewy wae wae 2 O- a Iodocing surplus variables s, 2 0, 5 2 0 and artificial variables A, 2 0. A2 2 0 a” initial basic feasible solution is Ay = 2 and Ay :- 1. (The primal constraints associated with sj. S2» A, and Ay are: =x, $0, S 0.x, $ Mand x; $ M). The iterative simplex tables are : Initial Hteration, Introduce y, and drop ys. fe Yo. Sa y Yo Ys % Ys Yo -M ‘7 2 1 1 1 ' -l a -M_oYs ' ® 1 -1 2 0 ea st 3M ~3MH10-2M46 2 Met M. M., First Iteration. Introduce y, and drop yy. y Ys ¥s Yo In 2 =I U2 12 -l 0 212 Ma 73M 2M MSM Second Iteration, Introduce yz and drop yi. ey We yu Ya yy vs Ys Ys v1 1 oO 13 1 413 23 3 23 -13 1 1 aD 0 -13 “18 -18 13. 13 12 0 3 0 5B. 14/3 83 M-14/3_ M-8/3 Final Iteration. Optimum Solution. oo Ye a yt yn A ¥ Ys Ys y Ys o2 vs WW 0 1 32-12 Wa nm -In 4 x 32 3R 1 0 “2-12 -1R 1n 2 zo =10 2 0 0 1 4 2 M4 M-2 m feasible solution to the dual problem is 2 and wy = 1/2; mi ‘Thus, an optimu wy = 0. 2 (10) = 10, ‘Also, the primal constraints associated withthe dual variables Ay and Ay are x, $M and x, cy = 230, where cg=(2 5 0} ‘Thus, we get a, = 430, a, = 460 and a, = 480. (ii) The z-row gives : 4 = egy, — cy = 2b, + 5by-3 => 2b + Sby = 7 cy = Cpyy cg = 1-0 = 1 2 = CaYs- 52 -$4$-0=2 To obtain the values of by, 6) and by, we perform iteration on the starting primal table = Initial Iteration, Introduce y3 and drop ys. 3 2 5 0 o 0 Ss 8 v1 y Ys ¥ Ys ¥6 0 Ys 1 2 1 1 0 0 0 Ys 3 0 ® 0 1 0 0 Yo 1 4 0 0 0 1 3 2 aod oO oO oO First Iteration. Introduce y2 and drop Ys. Sa ye XB vt Yo ¥3 M4 Ys. ¥6. 0 Ya 200 -12 @ 0 1 =1n 0 5 ‘3 230 312 0 1 0 12 0 0 Yo 480. 1 4 0 0 0 1 1150 oR. 2 0 0 5/2 oO Second Iteration. Optimum Solution. SB Ya XB yi ¥2 ¥3 Ys Ys ¥6 2 Yo 100 14 1 0 12 =4 0 5 y 230 3 0 1 0 12 0 0 Ye 80 4 0 0 2 In 1 1350. 4 0 0 1 2 0 “Comparing it with the given optimal table, we get 3/2 and by = -4, b (Note that the values of ¢, ¢ (iii) The dual problem is Minimize 2° wy + 3uy +52 -1/4, by are also readily available.) = a,w, + 430, + a3Ww3 subject to the constraints : 3, 2wy + wy + 405 22, wy + 2wy + Ows 2S w, 20, W220 and w; 20. The dual constraints associated with the starting primal variables Xy Xs and x, are w, 2 0, 2 0 and ws 2 0. Scanned with CamScanner“ 142 OPERATIONS REseaq icy formation : Thus. we have the following Starting primal variables 5 a Left minus right sides of the associated dual constraint m- 0 3-0 __Net evaluation primal optimal table £2. g Thus using Rule J we get y= Ww, - 0 => wy = C3 O=wy-0 = wy The optimal dual objective is Min, z* = 1,350 = aw" + dW". PROBLEMS Write down the dual of the following L.P.P. and solve : 8xy + 4xy_ subject to the constraints = ry + 2ty $30, 2x; + dey S24 ay, 22 20. [Osmania M.B.A, 209) 518/Maximize z $19. Minimize z= 15x, + 10x, subject to the constraint Buy + Sey 2S, Sup + 2s 23, ty HBO. pam mize z = Sxj + 2xy subject to the constraints br, + 26 dy, 43K 21 Hy HH ZH Hy ZO [Sambalpur MBA 1994) 521. 2x, + 9x + xy subject to the constraints : xy + dey + Dey 25, Srp ty + ey 24 and a, ay Hy 2 0. 522, Consider the following L. Maximize z= x; + 5x + 3x5 subject to the constraints : ay + Dey tay = 3. Dey ay AS ye ty ay 2 0. (a) Write the associated dual problem. (6) Given the information that the optimal basic variables are x and x3, determine the associated optimal dual solution, Given the L.P.P. . 7 Maximize z = 2x; + 4rp + 4xy — 3xq subject to the constraints : BPR EEA a Hh Hy = BE Kt ty ay 20. Use the dual problem to verify that the basic solution (x), x2) is not optimal. 524. Find the optimal value of the objective function for the following problem by only inspecting its dual Minimize z = 10x; + 4xy + Sxy + x4 subject to the constraints : Sty ~ Try + Bey + O.Sxy 2 150; 720 (f= 1, 23,4) (Karnataka: B.E. (Prod) 1994) 525. Use duality to solve the following L.P.P. : Maximize z= x1 = 47 + 3iy + 2xy subject to the constraints : yt Bab yn SQ ST a rag IQ S-2; 20 GL 234). [Wethi B.Se. (Math) 195) 526, Use’duality in solving the L.P.P. : Minimize z = 2xy ~ ap + xy + Sry - 3x5 subject to the constraints : an + ly tay ty = 8 Ay ty tea 2: HPO (= 2345). 527. Consider the problem : ~ Maximize = = 2x ~ 5x3 subject to the.constraints : By tay 2 Dy tay $y S 6 my — ay + Sty =O; ty ay 20. () Write its dual, : (i) Solve the primal and then find the solution of the dual. [Delhi B.Sc. (Stat) 1986) Scanned with CamScannera OPERATIONS RESEARCH Since, the total value of reso Rs. 7.67 while the profit ince urce required by a unit of product A is Rs. 7! l i associated is only Rs. 4, obviously it should not be produced. In case a unit of Product ‘A is produced, the manufacturer will incurr a loss of (Rs. 7.67 - Rs. 4), ie. of Rs. 3.67- For Product B and C, the value of resources required for their production is * Product B Product 9g 3 hours @ Rs. 0. = Rs. 0 2 hours @ Rs.0_ = Rs. 4 hours @ Rs, 5/3= Rs. 20/3 2 hours @ Rs. 5/3 = Rs- tos T hours @ Rs. 4/3= Rs. 4/3 3 hours @ Rs. 43 = Rs. 83 Total; Rs. 24/3 = Rs. 8.00 Total: Rs. 18/3 = Rs. 6.00 = Rs, 80 profit per unit = Rs. 6.00 Profit per unit = Rs. 8.00 =e 60 Clearly, for each of the product B and C, the opportunity cost is equal PROBLEMS vitamins A, B and C for the (0 and 32 units, respectively. ‘One unit of F; contains 14, mins conscious housewife wishes to ensure certain minimum intake of family, The minimum daily needs of the vitamins A. B and C for the family are 60. 4 For the supply of these vi i fusewife relies on two fresh foods Fy and Fa. One tt TO, and 4 units of vitamins A, B and C respectively. One unit of Fa coma’ 4, 8 and 16 units of the three respectively. F; costs Rs. 3 per unit and Fy Rs. 2 per unit. The problem is 10 find how many units of each food the housewife should buy every day to keep her food bill as low as possible. (@) Formulate it as a Tinear programming problem to minimise the total cost; {@) Write the dual of the problem as formulated in (a) and present the econeini” Wht {© Solve the dual by using simplex method and read therefrom the answer {0 the primal. 1536, An electronies firm is undecided a5 to the most profitable mix for its products. The products now smanaferured are tansisiors. resistors, and electron tubes, with a profit (per 100 units) of Rs. 100, Rs. 60 and Randi recpectively. To produce a shipment of transistors containing 100 units requires 1 hour of engineering Fee airect labour, and 2 hours of administration service. To produce 100 resistors requires 1 hour, Frcs aod 2 hours of engineering, direct labour and administration time, respectively, To produes one shipment Ana and (LOO units) requies 1 hour of engineering, 5 hours of direct labour and 6 hours of administration Sect hours of engineering services available, 600 hours of direct labour and 300 hours of administration Whar is the most profitable product mix? Write the dual of the given problem, use it to check the optimal sole and give its economic interpretation. : [Delhi M.B.A. (Nov.) 2005] interpretation of the dual. 49. DUAL SIMPLEX METHOD Dual simplex method is applicable to those linear programming probl. ith infeasil otherwise optimum solution. The method may be summarized i follows. me eat sn eee Step 1. Write the given. linear programming problem in its standard form and obtain a starting basic solution. 7 Step 2. (a) If the current basi ion is feasil si ui? int basic solution is feasible, use simplex method to obtain an optimum (b) If the‘current basic solution is infeasible, i.e., values of basic variables are < 0, go to the next step. Step 3. Check whether the solution is optimum. (a) If the solution is not optimum, ad ifici inti oe ston )ptimum, add an artificial constraint in such a way that the condition of (6) If the solution is optimum, go to next step. Step 4. Select the basic variable havin; i Step 4. ig the most negative value. This basic vari leaving vatiable and the row comesponding to it becomes the kay row. siuatie beeomen Scanned with CamScannerpeta mm QUALITY IN LINEAR PROGRAMMING "ag icients in the key row. vector is the one with Step 5. Obtain the ratios of the net evaluations to the corresponding coeffi tor becomes the ignore the ratios ‘associated with positive and zero denominators. The entering lgnernallest absolute value of the ratios. Column corresponding to the entering Vee key column. ‘step 6. Reduce the leading clement into unity and all other entrie elementary row operations. ‘ ‘Step 7. Go to Step 2 and repeat the procedure until an optimum ba 1s of the key column to zero by sic feasible solution is attained. SAMPLE PROBLEMS ie dual simplex method to solve the following LP.P. Minimize 2 = 3x, + x2 subject to the constraints : ky +x B dy ey toy 2 2 Mp ZO. MAS 1990] Solution. Converting the given constraints into < type, introduce slack variables s; 2 0 and 5, 2.0. An initial basic (infeasible) solution of the modified linear programming problem will be Land s) = -2. ‘The iterative dual simplex tables are : Initial eration. Drop y, and enter >. C7 Ye Xp yt M3 Ya 0 v3 = “1 1 0 o ya 2 2 0 1 Ga 0 3 0 0 mum but infeasible solution has 0 and xp) (= 51) < 0, %m (= &2) < 0 an opti feasible optimum solution, we sel the basis as follows : 1, -2} = Since all zj - ¢j 2 been attained. In order to obtain a basis and non-basis vector to enter Since, min {xj Xa<0} = min (I JJect a basis vector to leave the xp) i basis vector yg will leave the bas Further, since max J the non-basis vector Y2 ao4 — mar{ bl et (- 222% { Wi vy <0 = ma oa} 4} al 7 will enter the basis. First Iteration. Drop y3 and enter Ys. oH Yo Xs y Ya ¥3 va 0 ¥3 13 -1B 0 1 ap 1 yo 23, 23 1 0 “13 @-4) 213 78 0 0 18 In the above table, (= xp), and min {pe 501 $ OF = a4, } * { 13,1 } om { my US Op aa aa} eo? ‘Thus y, leaves the current basis and non-basis y, enters the basis. Scanned with CamScanner4 150 OPERATIONS RESEARC,, Final Iteration, Optimum Solution. So Yo Na Mn 0 Ye 1 1 A - y 1 te aT =) 2 ——_——_——— — imum basic feasib|. Tr is now apparent that since all z — cj 20 and also all xy 2 0 a” OP! ° solution has been reached. Hence, the optimum basic feasible solution to the given L-P.P. pel = 0 and x = 1 with minimum z = ~max 2* PROBLEMS yroblems = Use dual simplex method to solve the following linear programming proble! 538 Minimize z = x1 + % subject to the constraints: v dey #24 Hy tT BT te EO 39. Minin teat subject to the constraints > nas ue 2x a pz ox Bi 2020 [Annamalai MBA (Nor.) 2003) nth 540. Maximize z= -2x, ~ x2. subject to the constraints : fry tay 28 de, + 3n 26 + 22 = 10x, + 6x + 2x3. subject t0 the constraints = ay 22 sty 20 [MS. Tirunvelli BSc. (Math) 19%) xy 4,20. [Madras B.E. (Mech.) 177) S41. Minimize eta ty eh inte 542. Minimize z = 6x; + 7x, + 3xy + Sxq_ subject to the constraints : ve tg = ny + tg 2 12, ay + Sty ~ ty 210, 2ny + Sy +p + G28 By Aa ty He 2 0. ae _ [Meerut M.Sc. (Math.) 1993) $43. Use dual simplex method to solve the L-P.P. : ay Minimize z = 3x, + 2x2 + 23 + 4xq subject to the constraints : Day + hay + Sey + mg 21, Bey — ay + Ty 42D Sey + Dy Hay + GZS. He Hy EO. [Garhwal M.Se. (Sath.) 2002) ‘54, Solve the following linear programming problem by dual simplex method : Minimize z= 2x, + 9xp + 24xy + Bry + Sxs subject to the constraints : Pe ee ee ee ee ee er ee oe 545, Maximize z= 2x, + x2 + x3 subject to the constraints : Dy, + 3p - Sry = 4, may + 9K, QZ. dy + Gry + By SB Ty Hy Hy 2 OL [Hint : Since the initial solution is infeasible and also not optimum, add an artificial constraint ay +g +45 5M (where M>0 is a large number). With the help of this additional constraint, eliminate .x from the objective function and constraints of the given problem.) 546, Use dual simplex method to solve the L.P. Minimize z = x) + 2x + 3xy subject to the constraints : tH 24 ty Hg SB HZ Ayan ZO 547. Using artificial constraint, solve the following L.P.P. by dual simplex method. Maximize x = 2ry subject to the constraints : may + Dey = 2 ZB M4 HH SA Wy ay t dy S105 ty 4 20, Scanned with CamScanner