Scribd
Upload
135 views

Linear Programming

Uploaded by

Yashfeen Falak
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
135 views

Linear Programming

Uploaded by

Yashfeen Falak
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
You are on page 1/ 98
LINEAR INEQUALITIES IN TWO VARIABLES } CH APTER INTRODUCTION he We are already familiar with equations in one variable and two variables. We have also -olved some statement problems by translating them in the form of equations, But it is not ways possible to translate a word problem in the form of an equation. Instead of it we may et certain statements involving a sign of inequality ie., < (less than); > (greater than); (less than or equal to) and > (greater than or equal to) which are called inequations or qualities. In this chapter, we shall study linear inequalities in two variables. Their study is very luseful in solving problems pertaining to various branches of science, mathematics, statistics, economics, etc. 3.2, LINEAR INEQUALITIES IN TWO VARIABLES Se ee Let a, b,c be any three real numbers. Then the equation ax + by = c is called a linear equation in two variables x and y whereas the inequalities ax +by Sc, ax + by 2c, ax +by care called linear inequalities or linear inequations in two variables x and . An ordered pair (x, y,) is said to be solution of ax + by c. These two parts are called closed half-planes. The regions in xy-plane representing ax + by c are known asopen half-planes, These haltplanes are also known as the solution sets of the corresponding inequations. 33. GRAPHICAL SOLUTION OF LINEAR INEQUATIONS IN TWO VARIABLES Consider the following inequations : . @ x4 2y>9 (ii) Qe +3y <12 The set of solutions of () is (0, 1), (1, Dy (2,2) woe ete. } The set of solutions of iis (6 O14 0), , 0) 4, I) pone ee, The solutions Biven above are o] . aoe ty Sets of solutions can be represented 9 sian plane by a region Containing th. Do Values of their *Coordinates and J-coordinates satisfying the 8iven ing "Presentation of the solution on cartesian pli “quations, btained by substituting the Suitab] N a carte; © Values of. ; Nation, lane is called the graphical Solutio, n ot, For drawi ng the graph of a linear inequation, to obtain its solution ate &mployed ; Set, the fo), 4 Ming Draw the 8raph of the @quation ax + by =¢, whi the plane in ty ich is a straight line in 2Y plane Parts known as half planes, 2 diy i it should be shaded. If le given equation ig ed, then the Tequired graph is that half plane which does not Contain the chy Point and that should be shaded, The shaded Tegion Tepresents the Tequired Plane is called the 8raph and the set tion 8et of the given j of points On this } nequation, + Solve x + 4y> 8 graphically, Solution. The given inequation isx+dy>g The corresponding linear equation is x + 4y=8 Putting y = 0 in (2), we getx=8 and putting =D) (2) *=0 in (2), we get y =2 aia} Thus, the line representing (2) passes’ through the points (8,0) and (0, 2). Plotting these points and joining them by a dotted line 4 ‘extended on both sides) we get the graph of J 3 tine (2) 8s shown fig. 3.1. This line divides Wy; the ay plane into two half planes, a Yj Now consider the point 0(0, ' thse Ll oe , 0). Putting it in the given inequation i.e, x +4y > 8, we get 0 + 4(0) > 8, which is not true, 4.65 Fig. 3.1 :. The open half plane which does not i oa . the given inequation. contain the origin (shown shaded) is the graph of Note that the points lying on x + 4y = 8 do not constitute a part of the graph of the given inequation. _ EXAMPLE 2. Sketch the graph of 3x + 2y <6. (KU. 2015, 14) Solution. The given inequation is 3x + 2y <6 (1) ‘The corresponding linear equation is 3x + 2y =6 (2) Putting y = 0 in (2), we getx=2 and putting x =0 in (2), we gety =3 Thus, the line representing (2) passes through the points (2, 0) and (0, 3). Plotting these points and joining them by a line (extended on both sides), we get the graph of the line (2) as shown in fig. 3.2. This line divides the xy plane into two half planes. | |\etemeiita ANNA My =)—_—___— 5 i in the given inequation i.e.) 3x 4.9 D y it in the given inequa’ ; ie Now consider the point O(0, 0). Putting a 0+ 0.6, which is true, ining the origin (shown shaded) is the graph The closed half plane containing the origin (sho iy nequation i r+ 2y = itute a part Note that the points lying on the line 3x + 2y = 6 also constitute Part of the ar, ‘ the given inequation. EXAMPLE 3. Represent the Solution, The given inequation is 8y- 5x <380 The corresponding linear equation is 3y-5x =30 following inequality graphically : 3y - 5x < 30 Putting y = 0 in (2), we getx=—6 and putting x= 0 in (2), we get y = 10, Thus the line representing (2) meets. x-axis at (- 6, 0) and y-axis at (0, 10). Plotting these Points and joining them by a dotted line (extended on both sides), we get the graph of line (2). This line divides the xy-plane into two half planes, Now consider a point O(0, 0), Putting it in the given inequation Le., By ~ Bx < 30, we get 30)-5(0) < 30, which is true, : The open half plane which contains the origin is the 8raph of the given inequation (shown shaded in fig. 3.3), Note that the Points lying on the line 38y — 5x = 30 do not constitute a Part of the graph of the given inequation, EXAMPLE 4, Draw the &raph 3x~ by +820, Solution. The given inequation ig Bt ~5y 4830 wl The corresponding linear equation is Br ~ 5y + 8-9 @ INEQUALITIE — LINEAR INEQUALITIE “TWO ‘VARIABLES | nee re 3.5 The table of values of. €q. (2) is: 1 4 i) Plotting these points and joinin, ui : 8 them with ali ivides the xy-plane into two am half planes, ‘©, we get the graph of line (2). This line Fig. 3.4 Now consider a point O00, 0). Putting it in the given inequation ie., 3x — 5y +8 20, we get 3(0) - 5(0) +8 > 0, which is true, ‘Thus the closed half, plane containin; inequation. smememoasancol EXERCISE 3.1 the following inequalities graphically ig the origin (shown shaded) is the graph of the given Woyad. 2 Qy— By <5 2x <6 Sy, e 9 FOP 0<2x—5y +10 ina RAs AENNDANTE } ANSWERS formas win . INEAR INEQUALITIES IN-TWO)VARIABIBS||— recy 4. SYSTEM OF LINEAR INEQUATIONS AND THE GI (APH OF ITS SOLUTION SET If we have two or more linear inequations i in two variables, then these constitute a system _ linear inequations. _Alinear inequation is also called linear constraint a as sit restricts our hoice for the values of x and For finding the solution set ofa system of linear inequations, we first find the half planes hich are the graphs of given ‘inequa ions separately as explained in Art. 3.3, Thei intel tion common portion) of these half planes represents the solution of the given_ system of equations, se cacmmerennt Ea It may be noted that the solution set.of simultaneous linear inequations may be an empty et or it may be the region bow: ded 1 by the str¢ the straightlines correspondi g to linear in inequations or or EXAMPLE 1. Exhibit graphically the solution set of linear inequations Bx + 4y 212, y>1, x20. Solution. First we consider the given linear inequations as linear equations, i.e., 3x + dy = 12 2 ~) wel (2) a (8) _ oa 3.8 —— Graph of 8 * tyr Tet patting Y= oin (we get x= 4and putting vin we gety = 3. Thus, the line representing (1) passes through the points (4, 0) and (0. 3). Plotting these points and joining them with a line extended oF both sides) we get the graph of line (1). Now the point (0, 0) does not satisfy the inequation ar + dy > 12. Thus the closed half plane, not containing the origin, is the graph of inequation 3x + 4y 2 12. Graph of y 21: The line y = lis parallel to x-axis at a distance. 1 unit above the origin. Now the y2l. e the line y = 1. i on the right side of y-axis. n of the abov Q(0, 0) does not satisfy the jnequation Thus y > 1 represents the closed half plane abov Graph of x20: x2 0 represents the closed half plane The solution set of the given system of inequations is the intersectio: planes as shown by the shaded region in fig. 3.5. EXAMPLE 2. Find. graphically the solution set of ‘inequations bx +3y<0 3Bx-4y+7>0. Solution. First we consider the given linear inequations to be linear equations ie., 5x + 8y=0 3x -4y+7=0 Graph of 5x + 3y < 0: The table of values satisfying (1) is 0 3 -3 | 0 -5 | Plotting the: i joini se points and joining them with a dotted line, we get the graph of 5x + 99 LINEAR INEQUALITIES IN TWO VARIABLES Now consider the point (1, 1), Putting it in the given inequation Le., 5x + 3y <0, we get 5 +3 < 0, which is not true. The open half plane not contain- ing the point (1, 1) is the graph of the inequation 5x + 3y < 0. Graph of 3x-4y +7>0 : The table of values satisfying (2) is -1,|.3 —5 4 —2 Plotting these points and joining them with dotted line, we get the graph of bx-4y +7=0 Now consider the point (0, 0). Putting it in 8x — 4y +7 > 0, we get 0-0+7>0, which is true. Pa -. The open half containing (0, 0) is the graph of the inequation 3x —4y+7>0. The solution set of the given system of. inequations is the intersection (common portion) of the above half planes shown shaded in fig. 3.6. EXAMPLE 3. Find the solution set of the system of following linear inequations graphically : x+y<6 x21 y2l Solution. Consider the given linear inequations as linear equations x+y=6 (1) x=1 (2) yel +B) Graph of x + y < 6 : Putting x = 0 in (1), we get y = 6 and putting y = 0 in (1), we get =6, Thus the line representing (1) passes through the points (6, 0) and (0, 6). Plotting these points angi nd joining them, we get the graph of x + y =6 ~~ —EE 3.1 y Of etomitsof BUSINESS y, Now, the point O(0, 0) satisfies the inequation x + y < 6. Thus th a yS6. iB tie containing the origin is the graph of the inequation x + y < 6. Closeq, hal Graph of > 1: The inequation x2 1 represents the closed half plan e n the vg line v= 1. Graph of y = 1: The inequation y 2 1 represents the closed half pl lane aboy, 4 vel. The intersection of the above half planes (i.e., the shaded portion 8 shown ing represents the solution set of the given system of inequations. Fig. 3.7 EXAMPLE 4. Verify that the solution set of the following linear inequations is em x—-2y20, a-ys-2, x20, yz. Solution. First we consider the given linear inequations to be linear equations Le, x-2y=0 Q-y=-2 x=0 : F y=0 7 pt Graph of x —2y 20: Putting x =0 in (1), we gety = 0 ie., the line passes throu? origin. Putting x = 2 in (D), we gety=1. al 2 fs int Thus, the line representing (1) passes through the origin as well as the Pp? we get the graph of x — ay = Plotting these points and joining them with a line, | LINEAR INEQUALITIES IN TWO VARIABLES Pg Consider any point say (1, 0). Putting it in x 2y > 0, we have 1 — 2(0) > 0, which is true. Thus the closed half plane containing the point (1, 0) is the graph of the inequation . Qy 2 0. x2 Graph of 2x ~—y <~ 2: Putting x = vel Thus the line representing (2) passes through the points (— 1, 0) and (0, 2), Plotting these points and joining them with a line, we get the graph of ax-y=-2 Now the point O(0, 0) does not satisfy the inequation 2x —y <~ 2. Thus the closed half plane not containing the origin is the graph of the inequation 2x —y <-2. 0 in (2), we get y = 2 and putting y = 0 in (2), we get Graph of x 20: The inequation x > 0 represents the closed half plane on the right of y-axis. Graph of y > 0: The inequation y2o0 represents the closed half plane above the x-axis, The solution set of the given system is the intersection of half planes of the inequation in the system, which is empty (as there is no common portion). Thus the solution set of the given linear inequation is empty. EXAMPLE 5. Find graphically the solution set of the linear inequations Bx+y <6 x+y <4 x <2 y<4 x,y 20. Solution. First we consider the given linear inequations to be linear equations i.e., Bx+y=6 ~ A) (2) | +(3) | 4) (5) ~(6) Graph of 3x +9 <6: Putting x= 0in (1), we get y =6 (1), we get x=2 y= 6 passes through the points (2, 0) and (0, 6). Plot (extended on both sides), we get the graph of line and putting y=9 in Thus, the line 3x + : ig them with a line nsider the point (0, 0). Putting it in y $6, we get 0+0<6, and joinin, Now co: the linear inequation 3x + which is true. . The closed half plane containing (0, 0) is the graph of the inequation 3x + y <6. Graph of x +y <4: Putting x = 0 in (2), we get y = 4 and putting y = 0 in (2), we get x = 4. Thus the line x + y = 4 passes through the points (4, 0) and (0, 4). Plotting these points and joining them with a line (extended on both sides), we get the graph of line (2). Now the point (0, 0) satisfies the inequation xt+ys4 .. The closed half plane containing (0, 0) is the graph of the inequation x + y <4 Graph of x <2 : x =2isa line parallel to y-axis at a distance of 2 units to the Tl y-axis. x < 2 is represented by the closed half plane to the left of x = 2. Graph of y < 4 : y = 4is a line parallel to x-axis at a distance of 4 units abo" x-axis. y <4 is represented by the closed half plane below the line y = 4. Graph of x 2 0: The inequation x > 0 is represented by the closed half plane 00 the y-axis. : Graph ofy = 0 : The inequation y > 0 is represented by the closed half plane aber X-axis. The solution set of the given system of inequations is the intersection (common port? the above half planes as shown shaded in fig. 3.9. {{fENBRUNEQUAUEMTESUNWORVARIABiRS)|§ PLE 6. Given the inequations EXAM! nequations X+ 222, Br+y 23, de + By > 6, S20 Evhibit the solution set graphically, Solution. Any point (x, y) Satisfying Thus points of the required solui Table for x + 2y = 2: g the inequalities x > 0, y > 0 lies in the first quadrant. tion set must lie in the first quadrant. x 0 2 al y 0 05 Table for 3x +y =3: x ear veut Ls 0 Table for 4x + 3y =6: [5.0 [18-18 ys 2 0 4 Now the point (0, 0) does not satisfy either of the inequalities x + 2y > 2, 3x4 y23and 4x + By 26. Thus the solution set of above ‘inequation ns do not contain the origin ie,, it is away from origin. : Fig. 3.10 Hence (x;y) of solution set must lie somewhere in the shaded region which is unbounded | 88 shown in, fig. 3.10. . —_— Eas | EXAMPLE 7. Exhibit graphically the solution set of the linear constraint, : 2xv + 3y-12>0, x-y +220, Bx-dy +1220, xs4 yee Solution. First we consider the given linear constraints as linear uation, ; 1 be 2v + 8y—12=0 2v-y+2=0 3x - 4y + 12=0 x=4 ya2 Graph of 2x + 3y-12>0: Putting x = 0 in (1), we get y = 4 and putting y = 0 in (1), we get xr=6. Thus, the line representing 2x + 3y -12=0 meets the coordinate axes at (0, 4) and (6, 0). Plotting these points and joining them with a thick line, we get the graph of 2x + 3y-12=0. Now, the point O(0, 0) does not satisty the inequation 2x + 3y - 12 > 0. Thus, the closed half plane not containing the origin is the graph of inequation 2x + 3y — 12>0. Fig. 3.11 Graph of 2x—y+22>0: Putting x = 0 in (2), we gety =2 and Putting y = 0 in (2), we x=-1. Thus, the line 2x —y + 2 = 0 meets the co-ordinate axes at (0, 2) and (-1, 0). ine, We get the graph of 2x —y +e Plotting these points and Joining them with a thick li Now, the point O(0, 0) satisfies the inequation 2 ~y+2>0, Thus, the closed half plane containing the origin is the 8raph of the inequat! xe —y +220. Graph of 3x —4y + 12>0: Putting x = 0 in (3), we ety =3and Putting y = 0 in (3), etx =— 4. Thus, the line 3x — 4y + 12 = 0 meets the coordinate axes at (0, 3) and (~ 4, 0) Plotting these points and joining them with a thick line, a oe 7 -4y +12=0. Now, the point O(0, 0) satisfies the inequation 3x ~ 4y + 19 20, 2° Dh of the inequali? Thus, the closed half plane containing the origin is the dy + 1220. [| LEAR ECS TWO Vantanugg (aa | MIABL 1 sea ot dll Graph of x< 4: The constra; ‘aint x < renp, the line x = 4. *S4 represents the closed half plane on the left of Graph of y>2: The fonstraint repre, yed Presents the closed half plane above the line The intersection of above hal asshown in fig. 3.11 (shaded port EXAMPLE 8, Find the fplanes represent the er}... an on), Present the Solution set of given linear constraints linear in MeqUalities fop wh: ae ¢S for whieh the shaded area in fig. 312 is a solution Ser Similarly, for the line — ‘Ix + 4y=14, the shaded region andthe origin leon the same half i plane and (0, 0) satisfies the inequation ~ Tx + 4y< 14, i Thus ~ 7x + 4y < 14 is the linear inequation corresponding to ~ 7x + 4y = 14, iy Further, for the line 2x + 3y = 8, the shaded re gion and the origin lie on the opposite half planes and (0, 0) satisfies the inequation 2x + 3y <3, Thus 2x + 3y > 3 is the linear inequation corresponding to 2x + 3y = 3, Wote this step] Again, for the line x — 6y = 3, the shaded region and the origin lie on the same half plane and (0, 0) satisfies the inequation x - 6y <3. | Thus x~ Gy <3 is the linear inequation corresponding to x - 6y = 3. | . Also, the shaded region lies only in first quadrant, i *20, y20 — Thus the linear inequalities are 8x + 4y $18 ~ T+ 4ys4 2x + By23 x- bys3 x20, y20. 4. r+ 2y sg” Wty <8 : x, 920 (KU, 2013] : 7 Qe+y-320! x-Q4+1<0 x y20. | 10. 6x+ 5y < 150 x+4y <80i> ey 84 12, 842/208 9 nay c5t 0 + By $63 Bx+y $15 asym x<6 ned x+by 25 4 ys y2Q x<4 JEQUALITIES IN TWO ya\ RIN 0 VARIABLE: TABI fA S ae u >> 13: IN te i ered i ety 15, fae 3 » 18x + 1, dy < 840 ip et Be + By < 399 css Be dy 5 480 <3 , r20 xy 20 . yeo é sind the linear inequations for whieh ich the shad. edd are ui) ain the follow following figures ia the solution set : @ CHAPTER 1. INTRODUCTION ON In business, there are i esources are limites . Many sit; ‘longs Concerned with the pr bl i u “Mec and the pro le. ow t Pro| m of planning. The naximum producti to © best use of these Tesources go i ction otto give te ces 80 as to yield 0.7 to Sve the max; Sees for ‘Planning’ and sj . Senta refers to the pri srticular plan of action from AONB Several availahlenjer ilable al natives, Lineay’ eforiaie hat all relationships involved in a particular probleme €8.’Linear’ stands for indie: 1 technique for determin, tin ae e- ae for deter — em are linear. Thus Ing au hedule of i n optimum, Se) nterdepend, resources, Linea, itions will be helpful j the meaning of Li : anes = Ane: near P; more clear: ths aeaning of Linear rogramming — Definitions “Linear Programmi; ng is the analysis of Problems in which a linear ‘function of a variables is to be maximised (or minimized) when those var restraints in the Orm of linear jz a inequalities.” roe mu “Linear Programming is only one aspect of what has been ei management where, n all programmes are desi effects in the realisat alled a system approach to igned and evaluate ton of business objectives,” d in terms of their ultimate id purchase, but he has to choose the best ali ternative. So ping all those in mind and also the experience of last session he he has m; ‘any constraints and kee has to pl ‘an his purchase. Cae): Suppose he can invest not more than @ 100 in purchasing pen and note boo suppose that each pen costs him %2 and note book %1:50. If he invests % 100 to pu and y note books, then we have 2v + 1-50y < 100, We assume that he could sell all pen and note books and selling price of pen inty that of note book is $175 i.e., he is making a profit of 70-650 on a pen an, uy) a note book, then the profit function is 0.50x + 0-25y. It is observed from past that ny 4 note books sold during last year is not more than 30 and number of pen sold werg My three times the number of note books. Then we can impose the following constraints Qe + 1-5y <100 y <30 rhe x 2 3y. Also, we have x > 0, y > 0, since the number of items cannot be less than zero, Fig. 4.1 Possible values of (x, y) satisfying th make maximum Profit, we must havt owing the number of pens, tht We represent the above inequations on graph. All onditions lie in the shaded region (fig. 4.1). In order to 1aximum value of profit function i.e., 0-50x + 0-25y. The table sh. umber of note books, cost and profit is as follows : | INEAR PROGRAMMING \ en) | Now, itis clear from table that if he invests 100 by keeping 44 pens and 8 note books he earns ¢ 24-00 as profit but ifhe invests 8 99 and keeps 45 pons and 6 note books profil is again 224.00, Naturally he wil invest oss amount for same profit. In this example we had fixed the investment at % 100 and calculated the conditions to achieve maximum profit. We can reverse our problem by fixing the profit and then calculate the investment. Suppose the shopkeeper fixes his profit at % 24 as minimum, then 0:50x +0. Qy 224 x20 y20 In the same manner, we can find 2x + 1-5y for minimum investment. So, alinear programming includes a set of simultaneous linear inequations which represent the conditions of the problem and a linear function which expresses the objective function of the problem. Thus, linear programming can be defined as that branch of mathematics which deals with the optimization (maximization ormintmization) of a linear function of a number of = a ana variables subject to a number of conditions on the variables, in the form of lin the variables of the optimization function. = “—"—— nana ‘The linear function which is to be optimized subject bp the given conditions on the variables of the function is called the objective function and the system of inequalities or equalities eee nE 4 equalities | sae the conditions under which optimization is to be accomplished are called constraints. straints which describe that the variables involved are non-negative are, Tal jon-negativity restri Senet inequations in inequation 4.3. DIFFERENT TYPES OF LINEAR PROGRAMMING PROBLEMS (LP.P.) The following types of problems have become classical illustrations in linear programming : 7 SS programming: a Problems : In these problems, we have to determine the amount of different kit of constituents which should be included in a diet so as to minimize the cost of the desired diet such that it contains a certain minimum amount of each constituent. 2, Optimal Product Line Problems : In these problems, we have to determine the a different producis which should be produced an sold by a firm when each product réquités‘a fixed manpower, machine hours, labour hours per unit of the product, ete in order to make maximum profit. 3, Transportation Problems: In these problems, we havefo devermine a transportation ) Cried : or a commodity from different plants or factories situated at different locations to different markets at different locations i way that the tot nifimiim, subject to the constraints as regards the demand of ead each Plant or r factory. — 4s / 4. Javeytment Problems In these problems, we determine the amoun . be invpéted j6 a number oflfixed incomesccurities yo as to maximize the return on thie: Nek s ai ee, 5. Blending Problems : In these problems, we have to determine the num x quanti of the available raw material of different.compositions and Prices, hig blended for making one nil of a desired product, SS 4.4, MATHEMATICAL MODEL OF LINEAR PROGRAMMING PROBLEMS (a) Let Zbe inoue fonction defined by Z= 6,8; +6 +. G%, Where's an Con (6) Let (a,;) be mn constants and let (b;) be a set of m constants such that, 41 Xy + OyQXy t orssee + Opp hy (S, =, 2) by yyy + yg Ky + sssees + Ogg Ly (S, =, 2) by yy Xy + yoo + esses. + Onn (S =, 2) On (c) Let x, 20, x) >0,......,%, 20. The problem of determining the values of x, ty) ....... x, which makes Z Minin, maximum and which satisfies (b) and (c) is called the general linear. programming proble (Objective Function. The linear function, Z = ¢,x, + ¢yx) +....+ €n% 5 Which ig minimized or maximized is called the..objective. function, of the ge linear programming variables. = ble m1. The variables Hy Nyy very X, are called deg (i) Constraints. The inequalities (6), which are the restrictions on the variable called the constraints of the general L.P.P. (ai) Non-negative restrictions. The set of inequalities (c) fe, x, 20, x, 20,..¢ usually known as the set of non-negative restrictions of the general L.P.P. (wv) Solution. The set of values of unknowns x,, Xyy «+5 X, Which satisfy the constr of general L.P.P. is called a solution to the general L.P-P. . 4.5. MATHEMATICAL FORMULATION OF LINEAR PROGRAMMING PROBLEMS We have already introduced the concept of general linear programming problem (L Now we shall discuss the formulation of linear programming problems, The mathem# formulation of the problem is the process of transforming the given description of a dee problem into a mathematical form. There is no set rule to formulate linear progralt! problems. The following working rule will be helpfal in the formulation of linear progra™! problems : {INGAR PROGRAMMING )}}——— ag Working Rute () mevery LPP, ¢ "tain decisions are to be made whieh are represented by decision ariables. These decision y, v ‘riables are the quantities whose values are to be determined. We first identity these variables and denote them by x), i) Identify the objective function a and express it as a linear function of the decision variables. (iti) After expressing the objective function as a linear function of the decision variables, find the type of optimization (maximization or minimization) and identify the type uf the objective function, (iv) Identify the set of constraints stated in terms of decision variables and express them as linear inequations or equations. (v) Add the non- negativity restrictions on the decision variables. SOLVED EXAMPLES { EXAMPLE 1. A furniture firm man ufactures chairs and tables, each requiring the use of three machines A, B and C. Production of one chair requires 2 hours on machine A, 1 heur.on, machine Band J hour on ma hine C. Each table requires 1 hour each on machines A and Band. 3 hours on machine C. The profit realized by selling one chair is #30 while for a table it is € 60. ‘The total time available per week on machine Ais 70 hours, on machine B is 40 hours, and on machineC is 90 hours. Develop a mathematical formulation so as to find the number of chairs and tables that should be made per week so as to maximize the profit. Solution. First, we construct a table for the given data : A 2 I pe ; B 1 1 40 Cc A 3 90 et Profit per unit (in 2) 30 60 Letx chairs andy tables be produced per week to maximize the profit. etx chairs 7 Let Z denote the total profit, The profit on selling one chair is € 30 and profit on selling one table is % 60. Thus the total Profit on selling x chairs and y tables is (30x + 60y) = —— j . Z = 30x + 60)’ ¥ Also, it is given that a chair requires 2 hours on machine A and a table Tequiros machine A. Therefore, the total time taken by machine A to produce x chairs andy hy (2v +) hours. This must be less than or equal to total hours available per week oy may i i which is 70 hours. \ Q+y <70 The total time taken by machine B to produce x chairs andy tables is (x +) hours ay total time available per week on machine B is 40 hours. x+ys40 The total time taken by machine C to produce x chairs andy tables is (x + 8y) hours andy total time available per week on machine C is 90 hours. x + 38y<90 Since the number of chairs and tables produced cannot be negative, therefore x20 and y>0 Hence, the mathematical formulation of the given LPP is as follows : Maximize Z = 30x + 60y, subject to the constraints 2x +y <70 xty $40 x + 3y $90 and 420,720. EXAMPLE 2. A firm can produce three types of cloth say A, B and C. Three kinds of wool are required for it, say red wool, green wool and blue wool. One unit length of type A cloth needs | 2 yards of red wool and 3 yards of blue wool; one unit length of type B cloth needs 3 ‘yards of red wool, 2 yards of green wool and 2 yards of blue wool, and one unit length of type C cloth needs 5 yards of green wool and 4 yards of blue wool. The firm has only a stock of 8 yards ofred wool, 10 yards of green wool and 15 yards of blue wool. It is assumed that the income obtained from one init length of type A cloth is 3-00; from type B cloth is 75-00 and from type C cloth is €4.00. | formulate the problem as a linear programming problem so as to maximize the Profit of the fim y using the available material. Solution. For clear understanding of the problem, first we ta. . p construct a table for the given eee) | Hements of Bosinpgs (69) ‘ Z = 30x + 60y i i on machine A and a table po. Also, it is given that a chair requires 2 hours ee _ . machine A. Therefore, the total time taken by machi 8 ay available y (2c +) hours. This must be less than or equal to total hours Per Week on 7 “8 which is 70 hours. Qe +y $70 The total time taken by machine B to produce x chairs and y tables is (x +y) hour, total time available per week on machine B is 40 hours. xt+y<40 The total time taken by machine C to produce x chairs andy tables is (x + 3y) hours ; total time available per week on machine C is 90 hours. «+ 38y<90 Since the number of chairs and tables produced cannot be negative, therefore x20 and y>0 Hence, the mathematical formulation of the given LPP is as follows : Maximize Z = 30x + 60y, subject to the constraints Wty <70 x+y <40 % + By <90 od 20, y 20, LINEAR PROGRAMMING “ag Kinds of wool Types of cloth Stock of wool available with the firm (in yards) Income from one unit length of cloth (in 2) Let us assume that the firm produces 21, %y, %, yards of the clothes A, B and C respectively. Let Z denote the total profit of the firm, -. Total profit in ® of the firm is given by Z = 8x, + By + 4. Total quantity of red wool required to prepare x, yards of cloth A, x. yards of cloth B and x, yards of cloth C is (2.x, + 3.x. + 0.25) yards Since the stock of red wool available is only 8 yards 2x, + Bx, <8 Similarly, total quantity of green wool required to prepare x, yards of cloth A, x, yards of doth B and x, yards of cloth C is (0.x, + 2%, +5.x5) yards. Since the stock of green wool available is only 10 yards 2rry + Ba <10 Again, total quantity of blue wool required to prepare x, yards of cloth A, %, yards of cloth Band x, yards of cloth C is (3.x, + 2.2) + 4.5) yards. Since the stock of blue wool available is only 15 yards Bx, + 2x. + deg $15 Hence, the linear programming formulation for the given problem is as follows: Maximize Z = 3x, + Sit, + 4v,, subject to the constraints 2x, + Buy <8 Dery + Bary $10 Bey + Oey + dx, S15 ot 4,20, x20, 420. [Since firm cannot produce negative quantities] v0 units of Pe 400 units of carbohyare iF, which costs #2 per unil and F,, which cosig RA per unit, A unit of food F, contains 10 units of carbohydrate, 20 units of fat and 15 units of protein; a unit of food Fy contains 25 units of carbohydrate, 10 units of fat and 20 units of protein. Formulate the problem as @ linear programming problem, $0 as to find the minimum cost for a diet that consists of mixture of these two foods and also meets the minimum nutrition ~ requirements. EXAMPLE 3. A diet is 60 contain atleast 300 units of proteins. Two foods are available t we construct a table for the given data: Solution. Firs! Minimum requirement Food (F ;) Carbohydrates 10 400 | Fat 20 500 Proteins 15 300 ——+— : Cost per unit 2 x4 | units of food F, and x, units of food F. costs % 4, therefore total cost Let us assume that the diet contains >, Since one unit of food F costs 2 and one unit of food F, x, units of food F, and x units of food F, is % (2x, + 4X). y Let Z denote the total cost function. ? ‘Then the total cost is given by Z = 2x, + Axo Since each unit of food F, contains 10 units of carbohydrates, contains 10x, units of carbohydrates. ‘A unit of food F, contains 25 units of carbohydrates, thus x. units of food F, contat thus x, units of food f 26x, units of carbohydrates. Thus, x, units of food F, and x, units of food F, contain (10x, + 25x.) units of ‘carbohydrate The minimum requirement of carbohydrates is 400 units. 10x, + 25x, 2400 Similarly, x, units of food F, and x, units of food F., contain (20x, + 10x) units of fat. minimum requirement of fat is 500 units. 20x, + 10x, 2500 Again, x, units of food F, and x, units of food F, contain (15x, + 20x.) units of prot minimum requirement of proteins is 300 units. * 15x, + 20x, > 300 Also, 2,20 and = x,20 Here we have to minimize the total cost Z, Hence, the mathematical formulation of the given LPP is as follows : Minimize Z = 2x, + 4x9, subject to constraints . 10x, + 25x, 2400 20x, + 10x, >500 15x, + 20x, 2300 Xyy Ly 20. EXAMPLE 4. The objective of a diet problem is to ascertain the quantities of certain foods ideration at should be eaten to meet certain nutritional requirements at a minimum cost. The consi < limited to milk, butter and eggs, and to vitamins A, B, C. The number of milligrams of each of ined within a unit of each food is given below : hese vitamins conta roblem ? What is the linear programming formulation for this p Solution. Let the daily diet consists of x, litres of milk, x, kg. of butter and x, dozens of et Z be the total cost per day. er day (in 2) is given by Z=*, (xy tq 10x) mg. which eggs. Li Then, total cost p 4 1-10x, + 0-503 should be at least Total amount of vitamin A in the daily diet is equal to 1 mg. x +X + 10x, 21 of vitamin B and C in th Ox, + 100x, + 10x4) mg- and the e daily diet are respectively Similarly, total amount eir minimum requirements are J (1002, + 10x, + 10x,) mg. and (1 50 mg. and 10 mg. respectively. 00x, + 10x, + 105 250 10x, + 100%, + 10x, 2 10 and ing formulation for the given diet problem is as follows Hence, the linear programm) » 410 - aT La e constraints et ws Minimize Z =x, + 1-10x, + 0-505, subject to th wy ty + 10¥3 7 1 I ‘ 100x, + 10x, + 10x, 250 “ oe) 10x, + 100x, + 10% * 10 y and Xp Xp XB 20 If, butter and eggs cannot b, ney | 5.0"? [-- Quantities of mi i 3 Aand B, EXAMPLE 5. A medicine company has factories at two place’ From they vis made fo i ies situated at P, nd R. The monthly requir, \ $2 nade to each of its three agencles 5, while i moi rivety 40, 40 and 50 packets of the medic supply is 1 i nsporte ic packets respectively The transportation Cost per the agencies are respec of the factories atAand Bare 60 and 70 from the factories to the agencies are. given below * 7! + packet (in) 70 ce Transportation cost per ‘i a > ae m 2 is 5 Formulate the above problemas @ linear, programming. problem, to find how many pol from each factory be transported to each agency 80 that the cost of transportation is minimu| formation can be represented diagramatically as follows : Solution. The given in Agency R 50 Fig. 4.2 Let us assume that fact u s ory at A tran: packets of medicines to agency at Q. apprts = packets of amediaiesite ageney at F amt LINEAR PROGRAMMING ot tion ¢; Since the total produc! nts tatcan betray gt A fact, the amber a Also, “20, yo 0 60-x-y 20, *20, y>0 “+y <60, x20, y>0 The requirement of agency at Pig 40 factory at A. The remaining (40 — x) packe Similarly, (40 —y) packets will have t The total capacity of factory at B is 70 packets, Thus, a: packets to agency at P and 70-(40-x+40-y)=(x+y Also, si x+y-1020 * 40, y<40, x+y2>10 Let Z be the total transportation cost, = Bx + dy + 8660-2») + 440—2) + 2140 —¥) + 5 +y —10) ie, Z = 8x + 4y +370 Hence, the mathematical formulation of the given L.P.Pis as follows : Minimize Z = 3x + 4y + 370, subject to constraints x+y <60 x $40 y $40 x+y 210 x,y 20. 46. ADVANTAGES OF LINEAR PROGRAMMING «i 1. Linear programming is very useful in improving the knowledge and skill of managers and executives, i ii i init i f productive factors. It indicates 2. Linear Programming helps in attaining the optimum use o r factors. how one can utilize these factore most effectively by a better selection and distribution of these elements, In this way, more efficient use of manpower and machine can be obtained by the use “flinear Programming. a2) | ema BUSINES, 3. Linear programming improves the quality of decisions. A person hayi, n ! of the relationships within basic equations, inqualities or constraints can h leg, ny indivi ave ay about the problems and its solution. Thus the individual who makes use of jin, i alt ear ty Drop, methods becomes more objective than subjective. a 4, It highlights the problems faced during the production processes, They, . i e le others remain idle for some are Sity, eign Ky highlighting these problems and overcoming them rn \ When some machines cannot meet the demand whil Linear programming helps in 5. Although linear programming gives possible and practical solutions, th other constraints appearing outside the problem which must be taken into insiian iy c, It is not always possible that all the goods produced can be r old as sales, demand et se it allows modifi programming method can handle such situations also becau: Li Cation ‘ mathematical solutions. 4,7. LIMITATIONS OF LINEAR PROGRAMMING programming can be used when there is only one objective of the man; 1. Linear mization of cost. But i i in cases Mh, This objective may be either maximization of profit or mini the management has multiple goals, this technique fails 2, Linear programming can be used only in the situations where the objective functio,, the constraints can be expressed in the terms of linear equations. Non-linear, quadratieq, or higher degree equations cannot be considered in the L.P.P. P., there should be some fixed number of constraints. Otherwise the calculaty 3. InL.P. will not be correct. 4. According to the linear programm) whearas sometimes it happens that s For example, in finding how many machines 0: values of decision variables x, and x, are meaniny values, rounding the solution to the nearest integer h situations we have to use special methods. ‘ective function and constraints in lines! dy i.e., these are assumed to be known with ing problem, the solution variables can have al ome of the variables can have only integral va f different types should be produced, only integr| gful. Except when the variables have la will not yield an optimal solution. value, overcome suc! hat the coefficient of obj during the period of stu‘ fe situations it may not happen. Jes are assumed to be limited. Buti | nt, inter-relationship between thet | decisions to achieve som | Sf 5. It is assumed 1 programming do not’ change certainty. However, in real lif 6. In the application of linear programming the variabl real life problems where huge number of ‘variables are prese! is very complicated and the problem is to be reduced to meaningful optimal solutions. These reductions create doubt about the optimality of the results 0 problems. } EXERCISE 4.1 { TED AE ye the mathematical st of} Give the ‘atement of linear programming pss briefly the steps to formulas, a line: hy the various types Machines 100 A's, 200 B's and 50 C's but not more than 150 maximize profit. eblen @ A factory produces two products P, and P.. Each of the product P, requires 2 brs for moulding. 3 brs for grinding and + brs for polishing, and esch of the product P, requires 4 hr for moulding. 2 brs fer grinding and 2 hrs for poli machine for 24 hrs and polishi of P, and the factory can sell all that it produ problem to maximize the profit. e profit is ¥ 5 per unit of P, and tS per unit Formulate the problem as linear programming making two products A and B. The cast of producing one unit of praduets Aand B are aply at least 200 units of . Acompany i As per the agreement, the company has to 360 and & SO respectively. product B to its regular customers. One unit of product A requires one machine hour wheres product B has machine hours availeble abundantly within the company. Total machine hours available for product A are 400 hours. One unit of each product A and B requires one Isbour hour each and total of 500 labour hours ble. The company wants to minimize the exst of production by satisfring the given requirements. Formulate the problem as a LP.P, \ and Band sells them at a profit off 2 on type A and M, and M, Type A requires one minute of res one minute on M, and ene minute ov 8. A firm manufactures two types of products ®3on type B. Each product is processed on two machines Processing time on M, and two minutes on M,; type B requi M.. The machine M, is available for net more then 6 hours # available for 10 hours during any working day, Fermulate the prot the profit. Q minutes while machine M, is Jem as a LPP so as to may mize 7 Vitamins 1 ANG D APG TOUTE TEE UW GHTeT TENE 100ds I, ar 14nd F.. One y vitamin A and 3 units of vitamin B. One unit of food F, contaj nit F fog, vitamin B. One unit of food F, and F, cost % 5 and g ie ce of Vite Ong, moquiremeut tora person of vitunin A and B iy 40 and 60. s TeSPectively. meds thing in excess of daily minimum requirement, of vitamin ha "spectively : optimuny mixture ef food Fy and Fy at the minimum cost wa ino hang : ich m requirement of vitamin Ay Pe ‘ 1 iad B. Formulate this as a LPP. Cots the 4 o Et dw. Po maintain his health a person must fulfil certain mini dL: mum daily requ; ‘equirem, aad the person's dict consists of only two foo items, I an wl a sists of two food i land 7 » Land II, wh . ie shown in the table below : ent 8 fp 64, ‘obiee aia ah i ice and Dutrien, Me H Moy of nutrients, Assuming that ther § that there are only three ki ) ° kinds of nui Food I (per unit) Food II, Minimum daily # Tequi. (per unit) z “duivemen for the nutrient Calcium Protein Calories What combination of two food items will satisfy the daily requirement and entail the ieee Formulate this as a LPP. ‘Anil wants to invest at most < 12000 in bonds A and B. According to the rules, he has to invest least = 2000 in bond A and at least % 4000 n bond B. If the rate of interest on bond A is Sere annum and the rate of interest on bond B is 10% per annum, how much money should he investi) aximum yearly income. Formulate this as L-P.P. ‘ at each of the two places P and Q. From these locatio ‘of the three depots situated at A, B and C. The week! 5, band 4 units ofthe commodity while the producti scetively § and 6 units. The cost of transportation | earn m; ns, a certait There is a factory located commodity is delivered to each ments of the depots are respectively nd Q are respe! require’ capacity of the factories at Pa unit is given below: Cost (in D _— A 16 10 problem 5 rder that the tr To ; 9 as to find how many units g| iz | pane, F 's should program ansportatiOn C0st is mininnam ? . the above as a linear # ‘ate the abo’ + a aeAE Sh Ol ened 2y + dz, subject to constrain, s ji ‘ ae pes 200052012 HAE 2500 109 i qc bx + 8s subject (0 constraints * S160; y 200; 6° yer) © 20, Ax 4 2y 8 24) dy + ay 13s y | iio Gov + 8Oy, subject to constraints yy : : esi? x + 8y, subject to constraints» ¢y . 500; 5 400;y > an9, 5 \ punii2e 2 = bx + 2-50y, subject to constraints ¥ 4005254 y G09, 5, ” 4 = ge 24y 2405 Sx HRV z= 60 y20. , unionize 7. = 0-60x + 1.00y. subject to constraints yor + 4y 220; Sw + by 220; 2x + 6y 213 wus asimize 7, 0-08x + 0:10y, subject to ici oe Ie eye 12000, «22000, y 24000, x,y>0. Ty +190, subject to constraints Minimize Z =~ ¥<5,y.<5, 420, y20 {TION OF LINEAR PROGRAMMING pros.en : a Tosolve a linear i : ; o a oa en problem, we have to find its optimal solution. I there are twg methods for solvins li i: Seema soon sn Een gang ovgrenmig potion: a eometrical (or Graphical Method) 2 Simplex Method “Ifthe objective functi i i i ction contains only two variables, then it can be easily solved by graphical f three or more variables, then the aethod. However if the objective function is a function o simplex method is used. iy graphical method Joa Gen scope of stud: below oe the graphical method of solving a linear programming problem, we give mejmportant definitions and terms which shall ur further study - ch satisfy the constraint ts of By Ly x, whi 9 th general L.P.P. mined by all the ronstraints (including (K.U.2013] | cA oe Region. The common region determ! | the non-negative constraints) ofthe P . al _ a 4.16 region, the ts. In the feasible 3. Corner poin _ called the corner points: 4, Feasible Solution. ‘Any set of the values of the variables » 7 satisties all the constraints ‘and the.non-negative reatrictiona af ij feasible solution to the general L.P.P, In other words, every point in yh. ofa LP.Pis called the feasible solution of the given LPP. he fecal 5. Infeasible Solution. Any point whieh lies outside the feasible region ig N feasible solution does not. satisfy the constraint i, a Mts ofp ofthe solution, The point of inf linear programming 6, Optimal Feasible Solu maximizes) the objective func’ solution to the Unbounded Solu unbounded solution i words, if the feasible r problem. asible solution which optimizes (1p; LPP. is called an optima | > tion. Any fe tion of a general ming problem (L.P.P.) is said to}, | not bounded inn spect. hay, then the L.P.P. i general L. ‘on. A linear program f the feasible region is jon is an open plane, 7. In other t an unbounded solution. ic Solution. If a giv asolution ding the valu Basic solution. Th 1 variables and m-linear struc) ed after setting any ”-m vat variables from the m-const les which are pre-assigned: ther variables are called h; en L.P.P. involves (provided it exists) obtain’ es of the yemaining 1” e n-m variab 8 Bas constraints, then tu zero and fin called a Ned non-basic vari equal equations is value are ca: variables. Incase a basic solution involves negative value(s), Solution. ables whereas the o' thenit termed as Basic Infeas satifies all the li A basic solution which ples is called a I ble Solution (BFS). the varial s of non-negativity of 9. Basic Feasi| constraints an' Feasible Solution. Basic feasible solution: Non-degenerate B basic feasible solution, solution. @ Degenerate BFS: Inc aBFSis called Degen a BFS is said to be a no variables as is the num ution if one oF m d the condition pes: ariables have positive val Non-degen¢ s are of following two ty! ues | @ FS : If all the basic v: then such a BFS is called a s takes zero value, thet ase any of ‘the basic variable: rate solution. n-degenerate sol ber of structura ore basic val ution if it involves as ! ] linear constraints 0 In other words, riables have zero val positive basic LP.P. and ad the BFS. — -"N legenerate sol {ANBAR PROGRAMMING | 10, Redundant Constraints, The constraints which are less restrictive and do not affect the feasible region are known as redundant constraints. These constraints are not useful for optimal solution as these are not the part of feasible region. 1. Convex Polygon. A convex polygon is a closed region such that the line segment, joining any two arbitrary points of the region always lies entirely within this region. The feasible region of L.P.P is always a convex polygon. (i) Ww) The region shown in fig. 4.3 (i) is a convex = polygon whereas the region shown in fig. 4.3 (ii) is not a convex polygon. Ifthe feasible region of a L.P.P. is bounded, then it is always a convex polygon and the maximum or minimum values of the objective function must occur only at some vertex of this convex polygon. 4.9. GRAPHICAL METHOD OF SOLVING A LINEAR PROGRAMMING PROBLEM There are two techniques of solving a L.P.P. by graphical method. 1. Corner (Extreme) Point method 2, Iso-Profit or Iso-Cost method 4.9.1. Corner Point Method This method of solving a L.P.P. is based upon following theorem. Extreme Point Theorem. An optimum solution of a L.P.P, if it exists, occurs at one of the extreme (or corner) points of the convex polygon of the set of all feasible solutions. To solve a L.P.P. by corner point method, we first determine the convex polygon Tepresenting the set of all feasible solutions. If the L.P.P attains an optimal solution then by above theorem, one of the corner points (vertices) of the convex polygon gives the optimal solution, Tn some cases it may happen that two vertices of the convex polygon give the optimal value of the objective function. In such cases, all the points on the line joining these two vertices give ‘he optimal value and the L.P-P is said to have infinitely many optimal solutions. The L.P-P is ‘aid to have no solution if the convex polygon is an empty set point method can be spi \ it y, Pp. by corner- i Jution of a L.P. The process for the so following steps : 3 : bee ae given L.P.P. in mathematical form (if it is not given go), Step 1. Formulate the tions. constraints as equa’ feach equality which is a straight line. gion of each inequality. The common shaded Portion x called the feasible region. The region so obtained is I sents the set of all feasible solutions of the L.p p ny er points (vertices) of the convex Polygo ts of the set of all feasible solution, of Step 2. Consider all the Step 3. Draw the graph 0 Shade the required re; the region of solution, convex polygon which repre: Step 4. Determine the co-ordinates of the corn vertices are known as the extreme poin L.P.P. Find the value of the objective function at each of. the vertices of the convex po) on Step 6. The point where the objective function attains its optimum (maximum or min; nin, Step 5. value is the optimal solution of the given L.P.P. 4.9.2. Iso-Profit or Iso-Cost Method ee profit or los easing directi Again, if we move th " " e e same line i - Sees direction towards the origin till it parallel to itself through eo. 5 co-ordinates of this vertex will give e sses through a vertex of asible region in the decreas an iso-cost line where e sive the minimum value the convex pol; be very point will yield the same mj of the objective f lygon, then minimum ¢, ‘unction. This line! ‘Ost. ft Thus, for solution ry 180- ethod, we pr, ws . ofa L. ir or hod, P.P. by Iso-profit Iso-cost: met x e proc > eed as fe : ‘ollo 1. Obtain the feasib) : le-region b; : discussed in Art. 4.9.1 gion by employing steps 1 to 4 bral : ed in 9.1, sane _-% Obtain the coordin: in the coordinates of the corner Points (verti, oints (vertice; © cor, A : iner Point method # _3. Give some 5 s) : - - convenient val of the fea: xy-plane, Yalue to Z (say Z,) and draw the graph “asible region cae ‘ap ton. 4. If the objecti RO Of the jj ao jective function i : ane, g ined il line and obtain a ting i et nination, then draw |, ~ 0: The constraint x > 0 represents the closed half plane on the right of J-axis, Graph of y > 0: The constraint y > 0 represents the closed half plane above the x-axis. > Din fig 4 8 the ‘ ( 4:20 F d region ag the above half planes, i.e., the on ies eta te Saye is bounded. Thus, the convex pi sa feasible region, whic] : iven L.P.P. . ; feasible soins ofthe Ni ner points (vertices) of feasible region are O10, 0), : f the cor The coordinates of A i » Al d by solving the equate ints have been obtaine ation, 38). These points o P(44, 16) and D(0, ing li i usly. corresponding intersecting lines simultaneously. Now, Z= 6x + lly The value of Z at 000, 0) =6 x0+17 x0=0 The value of Z at A(52, 0) = 6 x 52+11x0= 312 The value of Z at P(44, 16)=6x 444 11x 16 me Value OFZ at D0, $8) = 60411 x38» Thus Z is maximum at P(44, 16) and Max, 7 = 440 is dd on = 4 9 = 16s the optimal solution of the given L.PP and the optimal value off is 440, Type - I: Spltion of Minimization Probleme with all ‘>> PLE 2. Solve the following lncay, ‘Progran de +y >20 2x + By >30 % 20, Solution, The given objective function is Z = 18x + 10y Consider the given linear constraints as linear equations i.e, () ++(2) Graph of 4 +9220: Putting x=0.n 1), we gety =20 and putting =0 in (1), we get 5. en the line representing (1) passes through the points (6, 0) and (0, 20). Plotting these nts and joining them, we get the graph of 4y 4 y= 20, z Now, the point 0(0, 0) does not Satisfy the in, ce equation 4x + y 2 20, Thus, the closed half jane not containing the origin is the graph of the inequation 4x + > 20, Graph of 2x+3y 230: Putting x =0 in (2), we get y = 10 and putting y = 0 in (2), we gtx= 15 ‘Thus, the line representing (2) passeg thr. ‘ough the points (15, 0) and (0, 10). Plotting these prints and joining them, we get the graph of 2r 4 3y = 39, Now, the point 0(0, 0) does not satisfy the inequation 2r + 3y > 30. Thus, the closed half plane not containing the origin is the graph of the inequation 2x + 3y > 30. Graph of x20: The constraint x2 0 represents the losed half plane on the right of the ypaxis. Graph of y 20: The constraint y > 0 Tepresents the closed half plane above the x-axis. The intersection of the above half planes ie,, the shaded region as shown in fig. 4.5 is the feasible region of the given L.P.P., which is unbounded. The co-ordinates of the corner Points (vertice: and C(0, 20). These points have been obtained intersecting lines simultaneously, 8) of the feasible region are A(15, 0), BOS, 8) by solving the equations of the corresponding eta ii oo Elements of BUSH s ! 7 = 180 + 10 5, 0) 4.22, 270 Now, pre value of Zat ACL = 18(15) + 10(0) = 18(3) + 10(8) = 134 v The value of Zat BO, 8) = “phewilue of Z at C(0, 20) = 180 + 10(20) = 200 i AC aserve that the smallest value of Z is 134. ” ~ Minimum value of Z = 184, when x =3,9 =8 optimal valu iy . . and the a le of |! \. rence, the optimal solution of the given LPP. isx= 32" g2n NY ye ; Z= 134. ae . paints Type - I: Linear Programming Problems with Mixed Const | straints involve either the sj ” In the problems discussed so far, itis son that all the const" ye linear const “8 . .<’ or the sign >’. But there may be Linear Programming problems in. which OO ar the si ou : do not involve a single sign of inequality. Ip other words, some constrain} oS ign ‘Sans some other involve the sign ‘’ (It is also possible that some jinear constraints may e representa | jea8 by ordinary equations). In such a situation W° say that the give? L.P.P. has mixed constrain, | The graphical method of finding the optimal solution of an L.P.P. with mixed constraints js , same as discussed earlier. \ d oad EXAMPLE 3. Solve the following L.P.P. by graphical method : inter i | Minimize Z = 20x + 10y, subject to the constraints | x + 2y<40 ~ | 3x +y230 da + By 2 60 and x,y20. Solution. jecti j (. foe The objective function is Z = 20x + 10y DU. ‘onsider the give i given constraints as equations i.e., x+2y=40 3x + y= 30 i 4x + 3y = Graph oj y= 60 : +2407 fx + 2y< 40: Puttin : . Thus, the li: ig x = Oin (1) 7 ine representi » We get y = 2 ing ( y = 20 and putti . ing y = 0 in (1),¥ these points 1 i pints and joining th ) passes thr inequation x + 2y < ra em we get the graph of. ough the points (0, 20) a inequation x + 2y < 49 Thus, the closed x + 2y =40.N , 20) and (40, 0).? 2y < 40, sed half plane contains ow, the point 0(0, 0) satis! ing the origin i igin is the graph! TORI [ > J a 4,23) 3x +230; Putting x = 0in (y Graph af ae aa i in (2), we got.y = 30 and putting y = 0 in (2), we Bet 210. THUS joining them we 6 (2) ses through the pints (0) and (10 Plotting st ints enoation es Tie ioe of 3x +y = 30, Now, the point 0(0, 0) does not he ine’ veut. Anus, the closed h e ini iin is the cis " ye inogustion Bx +230, half plane not containing the origin is the grap | ‘du + 8y 2 60: Putting x = 0i Graph of 8+" ing x= Oin 8), we goty =20 and puttingy = Vin (3), we Bet gs thus the aa ae asses through the points (0, 20) and (15, 0). Plotting these points anion ay>60 a ae of 4x + 8y = 60, Now, the point 0(0, 0) does not satisfy ire ineaation * 3y > 60. Thus, the closed half plane not containing the origin is the graph of the jnequation dy + By 2 60. Graph of x = 0: The constraint x 2 0 represents the closed half plane on the right of axis Graph ofy 20: The constraint y > 0 represents the closed half plane above the x-axis. The ee of = ov hatte ice, the shaded region as shown in fig. 4.6 is the asible region which is bounded. Thus, the convex polygon EP Be a even LPP. polygon EPQA represents the set of all ‘The coordinates of the corner points of the feasible region are E(15, 0), P(6, 12), Q(4, 18) and A(40, 0). ‘These points have been obtained by solving the equations of the corresponding intersecting lines simultaneously. fe feasi (15, 0) Fig. 4.6 Now, Z= 20x + 10y The value of Z at E(15, 0) = 20x 15 +10 x 0= 300 The value of Z at P(6, 12) = 20 x 6 + 10 x 12 = 240 The value of Z at A(40, 0) = 20 x 40 + 10 x 0 = 800 The value of Z at QU, 18) = 20 x 44 10 x 18 = 260 Thus, Z is minimum at P(6, 12) and Min, Z = 240. ar value of Zig > tim Hence x = 6,» = 12 is the optimal solution of the given L.P.F and op ally bY using Corner | EXAMPLE 4, Solve the | Re | tas well as by iso-profit method : hice following linear programming problem grap | poin 2x + y, subject to the constraints 5x + 10y <50 x+yel a ys4 x-ys0 x, y20 Maximize Z = {K.U. 2013] Solution. The given objective function isZ=2e+y sider the given linear constraints as linear equati | Ep (| xeyed ow mr) vat =) 7 ol) x-y=0 Con: Graph of 5x + 10y <50: Puttingx=0™ (a), we gety = Sand putting y = 0 in (1), wep x= 10. Thus, the line representing ( 1) passes through the points (10, 0) and (0, 5). Plotting thes points and joining them, we get the graph of 5x + 10y = 50. Now, the point O(0, 0) satisfies the inequation 5x + 10y < 50. Thus, the closed half pla: containing the origin is the graph of the inequation 5x + 10y < 50. Graph ofx+y21: Putting x = 0 in (2), we get y = 1 and putting y = 0 in (2), we getz=| ; ‘Thus, the line representing (2) passes through the points (1, 0) and (0, 1). Plotting th points and joining them, we get the graph of x+y =1. Now, the point 00, 0) does not satisfy the inequation x + y > 1. Thus, the closed half ie} not containing the origin is the graph of the inequation x + y 2 ie Gi : « | raph of'y <4: The constraint y < 4 represents the closed half plane below the liney* Graph of x- 7 ‘ ee | 7 . fx-y <0: Putting x = 0 in (4), we get y = 0 and putting x = 1 in (4), we get" us, the line i y these points madgiukee dudes (4) passes through the origin as well as point (1 1), Pi g them (extended on both sides), we get the graph of x- = 0. > Ra Consider any point (1, 0). Putting it in x—y <0, we have 1-0 <0, which is not true. Thus the closed half plane not containing the point (1, 0) is the graph of the inequation x —y 2 0. Graph of x 20: The constraint x > 0 represents the closed half plane on the right of the y-axis. Graph of y 20: The constraint y > 0 represents the closed half plane above the x-axis. The shaded bounded region ABCDE as shown in fig 4.7 is the feasible region of the given LPP. Fig. 4.7 Solution by Corner Point Method : The coordinates of the corner points of the feasible region are A(0, 1), »(3.2). 10 é c (2 2) » D(2, 4) and E (0, 4). These points have been obtained by solving the equations of the 3° 3 “orresponding intersecting lines simultaneously. Now, Z=w+y The value of Z at{A(p, 1)=2x0+1=1 1 cay (eT 1,1_3 The value of Z ap (2.5) =2*5'o "9 10 10 10 10 qT oY | TOY 10 ne value ofZ at (22, 10) an 4.26 ©§ ———_$_$_____--_-_ _ |; heneats of asin The value of Z at D(2, 4)=2x2+4=8 The value of Z at K(0, 4)=2x0+4=4 Thus, Z is maximum at C [ 10 2) and Max. Z = 10. Hence x = 10 ye e is the optimal solution of the given L.P.P and Ptimay : Zis WW, —~ a a {Solution by Iso-Profit Method‘ We give a convenient eonstant value, say 2 to Z and draw the dotted line 2y +729 P,Q,). which passes through the points (1, 0) and (0, 2). z Now, we go on drawing dotted lines parallel to line P,Q, in the increasing direction an, from the origin until we get a line which is farthest from the origin and having atleast one na : . : cae : i common to the feasible region. Here P,Q, is the required line which passes through the vad 3 si 10 10) : C 5 | of the feasible region. [The co ordinates of C can be obtained by solving (1) und (4) simultaneously a . 10) | 10 . 20.10 10 10 Maximum value of Z = 2 (3) t+— = 4-10 =—,y= 3 gf Ag Eg atx y=, EXAMPLE 5, Minimize Z = 3x + 5y, subject to the constraints : —2x+y3: Putting *=0 in (2), We get y = Grap! the line representing (2) Passes thy 3, Thus, ugh the d joining them we get the 8raph of y +y=3, an Sand Puttin, Points (0, 3) points eint O10, 0) does not satisty the Now, a origin is the graph of the not = ofx-2y <2: Putting x = mhue.theline representing 4 ot and joining them we get ¢ po BY = 0 in (2), we get and (3, 0). Plotting these inequation a4 inequation Xty>3, Pin), we gety = _ land putting y = 0 in (3), we Bet (3) passes through the points (0, ~])and (2, 0), Plotting these N€ Sraph of x — 2y=2. the inequation 2 Qy © inequation x-2 <2 Graph of x > 0: The constraint x = 0 represents the closed half plane on the right of rai yeaxis. *. Thus, the closed half plane ew te ne OD ene <2, Thus, the closed half plane ; igin i e h of th ining the origin is the grap] containing Graph of y>0: The constraint y > 0 represents the closed half plane above the x-axis. Fig. 4. 8 i i ion of the given L.P.P. The shad d unbounded region as shown in fig. 4.8 is the feasible regio: Shaded unboun: To aoe eS ) of the feasible region are A(0, 4), C(O, 3) and i rtices) o © Co-ordinates of the corner points (ve oe a3): Now -Or re »y solvii imultaneously] inates of P are obtained by solving (2) and (3) simulta (The co-ordinates o; Z = 8x 4 5y he 20= 20 The value of Z at A(O, 4) = 3(0) + 5(4) = 0+ ~4; Putting = 0in (a) . zed » We Bet y = 4 ang putting y = 0 in (2), we get. Thus, the line representin, : 6 (2) passes th; points and joining them, we get the raph fk Now, the point O(0, 0) does Not satisfy th not containing the origin is the 8raph of the i; Graph of x <5: The Constraint x < 5 represents the closed half pl: =5. x ugh wpe Points (4, 0) and (0, 4), y=4, Plotting these © Mequation x +> 4, Thus, the closed half plane nequation x + yz, closed half plane above the x-axis. .e., the shaded Portion as shown in fig. 4.9 is the feasible region, which is bounded, Thus, the region ABCDEF represents the set of all feasible solutions. Fig. 4.9 tices) of the feasibl have been obtaine Je region are A(4, 0), BO, = i tions o} The co-ordinates of the corner points (ve oeving the cata -ordin: a a De, 5), E(O, 5) and F(0, 4). These points e 5 j;multaneously. “responding intersecting lines simu’ Hl Ts el int O(0, 0) satisfies the; : : Now, the point he inne the inequation x+y <8, Thus, theclosed half plane containing neon gin is the graph of the inequation x + ys8. a . x +y24: Putting x = 0; Graph of x + ine * = 0 in (2), we get y = 4 and putting y = 0 in (2), we get 24 # Thus, the line representing (2) passes thro ints and joining them, we get the graph Ofx+y = int O(0, 0) does not sati anaes Now, the point J(0, 0 not satisfy the ine atic if containing the origin is the graph of the ieqesiaee ae ae 4. Thus, the closed half plane Graph of x <5: The constraint x <5 represents the c 5. Graph of y <5: The constraint y < 5 represents ugh the points (4, 0) and (0, 4). Plotting these 4, losed half plane on the left of line Fi the closed half plane below. the line y2d. Graph of x 2 0: The constraint x > 0 represents the closed yore Graph of y 20: The constraint y > 0 represents the closed half plane above the x-axis. The intersection of the above half planes ie., the feasible region, which is bounded. Thus, the region solutions. half plane on the right of the shaded portion as shown in fig. 4.9 is the ABCDEF represents the set of all feasible Fig. 4.9 Os ae co-ordinates of the corner points (vertices) of the feasible region are A(4, 0), B(5, 0), +5), B(0, 5) and F(0, 4). These points have been obtained by solving the equations of “sponding intersecting lines simultaneously. Now, W=x-7y + 190 The value of W at A(4, 0) = 4 ~ 7(0) + 190 = 194 The value of W at B(5, 0) = 5 7(0) + 190 = 195 The value of W at C5, 3) = 5 — 7(3) + 190 3 — 7(5) + 190 = 158 0-715) + 190 = 155 0 — 74) + 190 = 162 whenx = 0 andy =5: The value of W at D(3, 5) = The value of W at E(0, 5) = The value of W at F(O, 4)= imal Solutions, Minimum value of W = 155, Fi i ti Type -IV: Linear Programming Problems having Multiple Op’ a ution j i fut Linear programming problems which have more than one ae a ee cal L.P.P. with multiple optimal solution. In case the constant coefficient al ceuaiita net are proportional to the corresponding coefficients in one of the ee an LER, oe and an optimal solution satisfies this constraint equation, then e ft ne i iti mult solutions (of course, infinitely many optimal solutions are determine| y a x q - thet segment of the boundary line of the said constraint which forms @ part of the feast le region the L.P.P.) EXAMPLE 7. Solve the following linear programmi ng. problem graphically 5 xr Maximize Z=* +)» subject to the constraints ¢ Qx-y +120 xt+ysd3 xs2 and x yz0 [K.U. 2015,! Solution. The objective function is Zaxty Consider the given constraints as equations, Less ax-y=-1 J xtye8 nad ° : ‘ ey =oin ih" Graph of 2x —y + 1>0: Putting x= Qin (1), we gety = 1 and puttingy 1 . lee a} pe - S Thus, the line representing (1) passes through the points (0, 1) an 2 i : ost these points and joining them we get the graph of 2x—y + 1=0. Now, the point OCD J taining the origin 5 e the inequation 2x —y +120. Thus, the closed half plane con’ eae yt et. _ «=

You might also like