Scribd
Upload
38 views34 pages

Optimization and Linear Programming 1

eng matrh

Uploaded by

AbdulSalam
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
38 views34 pages

Optimization and Linear Programming 1

eng matrh

Uploaded by

AbdulSalam
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/ 34
Programme 23 Frames Optimization ae and linear programming Learning outcomes When you have completed this Programme you will be able to: Describe an optimization problem in terms of the objective function and a set of constraints Algebraically manipulate and graphically describe inequalities Solve a linear programming problem in two real variables Use the simplex method to describe a linear programming problem in two real variables as a problem in two real variables with two slack variables @ Set up the simplex tableau and compute the simplex Use the simplex method to solve a linear programming problem in three real variables with three slack variables Introduce artificial variables into the solution method as and when the need arises Solve minimisation problems using the simplex method Construct the algebraic form of the objective function and the constraints for a problem stated in words Optimization and linear programming 941 Optimization An optimization problem is one requiring the determination of the GJ optimal (maximum or minimum) value of a given function, called the objective function, subject to a set of stated restrictions, or constraints, placed on the variables concerned. In practice, for example, we may need to maximise an objective function representing units of output in a manufacturing situation, subject to constraints reflecting the availability of labour, machine time, stocks of raw materials, transport conditions, etc. Linear programming (or linear optimization) Linear programming is a method of solving an optimization problem when the objective function is a linear function and the constraints are linear equations or linear inequalities. In this Programme, we shall restrict our considerations to problems of this type that form an important introduction to the much wider study of operational research. Let us consider a simple example, so move on to the next frame A simple linear programming problem may look like this: @) Maximise P=x+2y (objective function) subject to y<3 x+ys5 x-2y<2 x20;y20 The last two constraints, ie, x>O and y>0, apply to all linear programming (LP) problems and indicate that the problem variables, x and y, are restricted to non-negative values: they may have zero or positive values, but NOT negative values. These two constraints are often combined and written x, y > 0-or omitted altogether since they are taken for granted in all LP problems. Before we proceed, we will take a brief look at linear inequalities in general. (constraints) On, then, to Frame 3 942 Programme 23 B) Linear inequalities In most respects, linear inequalities can be manipulated in the same manner as can equations. (a) Both sides may be increased or decreased by a common term, eg. 2x12 . 2x43y>6 But NOTE this: (©) If both sides are multiplied or divided by a negative factor, eg, (-1), then the inequality sign must be reversed, i.e. > becomes < and vice versa. Here, then, is a short exercise, eg. Exercise Simplify the following inequalities so that each right-hand side consists of a positive constant term only. (a) 3x-S<4y (b) 2(x + 2y) <-8 (c) 4x—6y <-10 (d) 2x4+3>-(y+4) (©) —(x-3y+5) > 2x+4y-6 Check the results in the next frame (a) 3x-—4y <5 (b) -x-2y24 (©) -2x+3y>5 (d) -2x-y<7 (e) 3x+ys1 Graphical representation of linear inequalities Consider the inequality y — 2x < 3. We can add 2x to each side, so that yS2x+3, The equation y=2x+3 can be represented by a straight line divid- ing the x-y plane into two parts. For all points on the line, y=2r+3. For all points below the line, Optimization and linear programming 943 y<2xg3 & -. y <2x+3 indicates all points on or below the straight line, but excludes all points above it. We can indicate this exclusion zone by shading the upper side of the line. Arguing in much the same way, x—2y <2 can be rewritten as x y25- exclusion zone 1 and we can draw the line y=5-1 and shade in the Example 1 The problem we quoted earlier in Frame 2 was Maximise P=x+2y (objective function) subjectto y <3 x+yss x-2y<2 x20;y>0 (constraints) Now, on a common pair of x and y axes, we can represent the five constraints and shade in the exclusion zone for each. We then have the composite diagram 944 Programme 23 ‘The coordinates of all points on the boundary of the polygon OABCD, or within the figure so formed, satisfy the system of constraints. The set of variables for each such point is called a feasible point or feasible solution and the figure OABCD is the feasible domain or feasible polygon. Note these definitions. Our problem now is to find the particular point within this domain that makes the objective function P=x+2y a maximum. The equation can be rewritten as y=-3 +5 and this represents a set of parallel lines with different values of the intercept 5 If we draw one sample line of this set to cross the feasible polygon we have just obtained, we get, using P = 3 Optimization and linear programming 945 We can increase the value of P and hence raise the objective line up the page until it passes through the extreme point C. Any further increase in the value of P would take the line outside the feasible polygon and hence fail to conform to the given set of constraints. o 1 Ww ONS 5 In this example, then, point C gives the optimal solution. From the graph it can be seen that the line with maximal P passes through the point of intersection of the two lines y=3 and y=-x+45, This means that y=3, x =2 and so Pax =x+2y=8. A graphical method of solution is clearly limited to linear Programming problems involving two variables only, However, it is @ useful introduction to other techniques, so let us deal with another example. Example 2 Maximise = P=x+44y subject to —x +2y <6 Sx+4y < 40 xy>0 First of all, plot the appropriate straight line graphs to obtain the feasible polygon. This gives Co — The objective function P=x+4y can be expressed in the form y=—%4+2and its graph added to the feasible polygon, as before. We then obtain ‘The line y= which is 947 Optimization and linear programming From the graph it can be seen that the line with maximal P passes x through the point of intersection of the two lines y=> +3 and y=—410. Thatisx=4, y=5 and $0 Pax = x+4y = 24. As easy as that. Now this one, Example 3 Minimise subjectto —x+6y>24 2x-y<7 x+8y <80 xy20 It is very much as before. Complete it on your own. Pain =6 with x=6, y—S (3) To obtain the minimum optimal value of P, the graph of the objective function is, of course, lowered to the appropriate extreme point. In practice, linear programming problems usually contain many more variables than the two we have so far considered and a computational method is then required. One such technique is the simplex method and the remainder of this Programme will be devoted to the steps necessary to put it into practice. So move on to Frame 14 —kS———————— 948 — Programme 23 The simplex method The first step in the simplex method is to ensure that each constraint is written with a positive right-hand side constant term, Then we all inequalities as equations by the introduction of slack variables. For example, —x+2y<6 canbe written -x+2y+w; =6 and Sx+4y < 40 can be written Sx+4y +w2=40 where w; and w2 are positive (or zero) variables with unit coefficients, required to make up the left-hand side to the value of the right-hand side constant term. The new variables, w; and we, are called slack variables. Let us look again at the problem we solved earlier. Example 1 Maximise P=x+4y subject to —x+2y <6 Sx+4y <40 {as always, x, y > 0) The constraints now become —x+2y+w, =6 Sx+4y 9 +02 =40 and the objective function P—x — 4y =0 From this, we can now begin to form the simplex tableau (or table), So make a note of the above information — and then move on [ 15) Setting up the simplex tableau (a) Framework First construct a framework with the headings shown. x yw wo | b | check | Next, we enter, in the framework, the coefficients of the problem variables and of the slack variables in the constraints, together with the right-hand side constants in the column headed b. (Ignore the check column for the time being.) So we have Optimization and linear programming 949 Problem Slack (16) variables variables Const. xy mm] b | check er body unity matrix (b) Check colwnn The right-hand side column is included to provide a check on the numerical calculations as we develop the simplex, $0, for each row, total up the entries in that row, including the constant column, and enter the sum in the check column, Do that Basis | xy wi_wa |b | check G7) m |-121 0/6] 8 ws | S$ 4 0 1 |40| 50 (©) Starting basic solution The two constraints now contain four variables, but if we start by letting x and y each be zero, then we have the temporary solutions, w; = 6 and w2 = 40, and we indicate these variables in the extra left-hand side column, as shown. Note (1) The columns with the slack variables form a unity matrix. (2) There are now four variables, x, y, ws, w2 (n= 4). (3) There are two constraints (m = 2). (4) We put (nm) variables, Le. two variables (x and y), ‘equal to zero as a start. Finally, we have to deal with the objective function, $0 move on to the next frame (d) The objective function The objective function, P=x+4y, is (18) written P — x — 4y = 0 and the coefficients of this form the bottom row, or index row, of the tableau, thus Basis [xy wi we |b | check wy -—. 31°06 6 8 w | 5 4 0 1 |40] so P |-1 -40 0 |o0/]-s Complete your tableau, if you have not already done so, and then we will see how the computation Is carried out. 950 — Programme 23 Computation of the simplex 1 First we select the column containing the most negative entry in the index row: in this case —4. This is called the key columm and we enclose it as shown. y wi w2 |b | check wm |-1fz]1 of6] 6 m | s| 4/0 1 |40 | 50 7 -1\|-4)0 0 o|-5 [Basis | x 2 In each row, we now divide the value in the b column by the positive entry in the key column: the smaller ratio determines the key row. a 2 Enclose it as shown below. for 1 , r=s=3 PHTCRY RSs ., tow Lis the key row, row 2(w2), r=—p=10 pivot Basis | x y fm we |b | check wy Sta 2. Ons 8 | +—key row wz | S|4| 0 1 |40 | So P -1[-4] 0 0 | 0 }-s ‘The number at the intersection of the key column and key row is the key number or pivot: in this case the number 2. ‘We now divide all entries in the key row by the pivot to reduce the pivot to unity - which we then circle. The new version of the key row is sometimes called the main row. The rest of the tableau remains unchanged, so we then get ............ (20) unit pivot o Basis | x _y /wi We |b | check m |-} @4 0/3 4 |<— main row We 5 4 0 1 |40] 50 Pp |-1 -4 0 0 | 0 | -S |+—index key column So far, so good. Now we deal with the actual calculations. Next frame Optimization and linear programming 951 4 Using the main row, we now operate on the remaining rows of the tableau, including the index row, to reduce the other entries in the key column to zero, Note that the main row remains unaltered. The new value in any position in the other rows, including the » column and the check column, can be calculated as follows: New number = old number — the product of the corresponding entries in the main row and key column | @| 4 main row K is replaced by K — (A x B) BYK For example, in the second row (w2): $ is replaced by 5 —(-})(4)=S4+2=7 4is replaced by 4-(1)(4) =4-4=0 is replaced by 0-(})(4) =0-2=-2 lis replaced by 1—(0)(4) =1-0 40 is replaced by 40-(3)(4) =40-12=28 50 is replaced by S0-(4)(4) =S0-16=34 and, in the third row (P): -1 Is replaced by ~ 1— (—}) (-4)=-1-2=-3. Completing the operations for rows (w2) and (P), we have -4 40 70-2 Pp [-30 20 [a] 1 Now confirm that the new values in the check column are, indeed, the sums of the entries in the corresponding rows. If not, there is a mistake somewhere in the working to be corrected before we proceed. If all is well, move on to the next frame SSS 952 — Programme 23 5 Change of basic variables In its final form, the key column consists of a single 1 and the remaining entries zero, This is in the column headed y which indicates that the basic variable w; in the main row can be replaced by y. Basis | x y 4 we |b | check yee lah Ue Fees |S 4 w. | 70 -2 1/28] 34 Pp |=3.0° 2 0 [22] 1 Note that there are two columns containing a single 1 and the Test 0, These are headed y and w2 which are now also the basic varlables in the left-hand side column. Reading the values in the } column therefore gives a basic solution y= 3 and we = 28, and at this stage P = 12, Any variable not listed in the basis column is zeto. One basic solution at this stage is therefore x =0, y = 3, ‘Wo = 28. However, we are not finished, The index row (P) still contains another negative entry, so we have to repeat the simplex process using the same steps as before, Basis | xy wi we |b | check y |Fajt goo [3a] 4 w. |[ 7[o -2 1 [28 [34] |+ key row P {bajo 20 fz] nu tL_ key column Now divide the key row by the key number (7) to reduce the pivot to a unit pivot. This gives Basis yo Wr we check Y 32 30 [3 4 Wo @Mo -} 3 | 4 | ¥ | mainrow po [30 20 f[zi[u Using the main row, operate on the remaining rows (including the index ow) to reduce the other entries in the key column to zero, ‘Complete that stage and we have Optimization and linear programming 953 Be y we P iw 34 53 ‘Again, at this stage, check your working by totalling up the entries in each row and satisfy yourself that the sum agrees with the value in the check column. Note that wo in the basis column can now be replaced by x which was the heading of the column containing the last unit pivot. So finally, we have Basis |x y wi we |b | check y [Ol Bw] S|] F x |10-445]4 | ¥ Pp [oo § 3 [a] PR A new basic solution now emerges as x= 4, y= 5. Furthermore, since there is no further negative entry in the index row, this is also the optimal solution and the optimal value of P is given in the b column, i.e. Pmax = 24. For interest, you may wish to compare this result with that obtained in Frame 12. We have been through the simplex operation in some detail by way of explanation. Many problems involve more than just two variables, but the method of computation Is basically the same, being an iterative process which is repeated until the index row contains no negative entry, at which point the optimal value of the objective function has been attained. The problem we have just solved would normally look like this: Maximise P=x+4y subject to -x+2y <6 Sx+4y<40 (x, y>0) Entering slack variables, etc., this is written =x+2y4+ wr =6 Sx+4y 0 + =40 P-x-4y =0 ‘The complete tableau is given in the next frame | 2° 6 o i | 4 oof o y 0([ 3 io * 40 -1 -4 0 0| 0 ym |[-y) 24 0/3] 4 w: |[-7[0 —2 1 | 8 | 34 > [Esl o 20/2] n : (3 tao 7s, 4 wm |@ 0-35 / 4/ ¥# Pp [3 020|/2| y o1e HA] S| F xm | 1 0-33] 4] # P 00 $3 ila) Pax = 24 with x= 4, y=5 Now for another example — so move on to Frame 28 (28) Here is one for you to do on your own. The method is just the same as before so you will have no difficulty. Example 2 Maximise P= 4x+3y subject to -x+ y<4 x+2y<14 2+ y0) We have three inequalities this time, so we shall need to introduce three slack variables. Converting the inequalities into equations, we obtain 955 Optimization and linear programming ‘Then we set out the simplex framework with appropriate headings, i.e. [Basis ee we eae (30) I Remembering that the index row uses P— 4x — 3y = 0, we can set out the first tableau. Choosing x and y, as usual, to be zero for a start, we have Carry on now and complete the working on this first tableau. Check with the next frame 956 Programme 23 [ 32 ) Here is the working so far. (a) The basic variable (ws) of the unit pivot can now be replaced by the variable at the heading of the unit pivot (x). (b) We see there is still a negative value in the index row, so we repeat the process for this second tableau. Now you can finish it off Optimization and linear programming 957 Check to see if you agree. (33) Basis | x y wm we wy |b | check | m [ofa] 1 0 4 We oO; 3} 0 1 5 x 1] 3} 0 O 4 P [olal oo 2 wm [|O0 } 1 0 4 w |0 @ 0 § -4 x f -$ +- 0. 0 4} P [ot 0 0 2 Wi [OO Ra yw (0° 2 0 § =} x 1.0 =O -} qj P joo o 3 § [36 | The baste variable (wa) can now be replaced by y, being the heading of the unit pivot column. There is no further negative entry in the index row: therefore, the optimal value of P has been attained. <: Pox =36 with x=6,y=4, Note: We also see that w; = 6, since the unity matrix has headings x, y, Wy. The full result, therefore, is Pmax = 36 with = x=6,y=4, 1, =6, 2 =0,w3=0 though we do not normally require this extra information. The meaning of w; =0 and w2=0 is that the second and third constraints become X+2y=14 and 2x+y=16 respectively rather than x+2y< l4and 2x+y< 16. The meaning of w; = 6 gives the first constraint as —x + y < 14 rather than —x+y< 14, Now we will extend the simplex method to an example involving three problem variables. Next frame es 958 Programme 23 [ 34 ) Simplex with three problem variables Maximise P= pix+pay + pst subject to ayyx+ ayy +ai3z < by Gy X + Any +232 < be 3X + dyry + a332 < bs %yz20 Introducing slack variables we have AX + My2y + A132 + We =h AyyX + Azzy + 4232 +W2 =h ayX-+ Asay + 332 +ws=bs P—pxx— pry — Pst =0 If there is now a total of n variables and m constraints, then at least (n—m) variables are equated to zero. The remainder form the basic variable column entries. Equating x, y, z to zero, then, the basic variables are wy, W2, W3- Basis | x y Zz W. Wa Ws |b check wi a) a2 a 1 0 0 by We a @2 a3 O 1 O b2 Wa ay az a3 0 0 1 | by P| -m 2 -m 0 0 0 | 0 | ‘The variables in the basis column are the variables heading the unity matrix. The method is exactly as before, (a) Select the most negative entry in the index row to determine the key column. (b) Divide the entries in the constant column (b) by the corresponding positive entries in the key column. The smallest positive ratio determines the key row. (c) The entry at the intersection of the key column and the key row is the key number or pivot. (d) Divide each entry in the key row by the pivot to reduce the key number to a unit pivot. The revised key row is now called the main row. (e) Use the main row to operate on the remaining rows to reduce all other entries in the key column to zero. (®) Repeat steps (a) to (e) until no negative entry remains in the index row. Now for an example eee Optimization and linear programming 959 Maximise P= 2x+6y+4z subject to 2x + Sy+2z< 38 4x+2y+3z<57 x+3y+5z<57 xyz20 Rewriting the inequalities as equations gives 4x+2y+3z 0 +02 x+3y45z We also have P - 2x — 6y — 4z = ao Us cupoW letnp Sie sunples tableau ready for solution. That is ............ Basis |x yz wy Wa wy |B | check (37) oF oS oS Ono. )oe | a8 we 4 2 3 o 1 0 5s7 67 Ws 1 3 5 oo 1 57 67 F —2 -6 4 0 0 0 oO |-12 Now we just apply the normal simplex routine until there is no negative entry in the index row. Rernember: (1) to replace the basic variables as the problem variables become available at each stage, and (2) any variable not appearing in the basis column has zero value. Now you can work the solution right through and then check the result with the next frame. Take your time: there are no snags. eo Programme 23 =0,y=4,2=9. *. Prax = 60 with x Do you agree? If so, on to the next frame Example 2 Bx +4y +Sz P= Maximise subjectto 2x +4y+3z< 80 <48 4x+2y+ Zz x+ y+22<40 x ¥z20 It is much the same as before. Work through it carefully and then check with the next frame. 961 Optimization and linear programming a + = mi * ¥. 4 s 5 + 1 = = + \ a a ' a x + a e = 90 56 4s -12 90 56 © -12 -4 -3 [_ Basis P S,y=7,2=14. 2. Pmax = 113 with x Next frame further complication. Now let us meet 962 Programme 23 (4) Artificial variables So far, our approach to each problem has been the same. (a) We first of all convert the ‘less than’ inequalities into equations by the inclusion of slack variables. (b) If there are now n variables and m constraints, then at least (n - m) variables are equated to zero — usually x, y, z, etc. — so that the initial basic solution is given by the slack variables, the coefficients of which form the unity matrix in the tableau. (c) We then proceed by the simplex method to convert the basic solution to one containing the problem variables, the tableau entries for which now form a new unity matrix. (d) The method is repeated as necessary. When no negative entry remains in the index row, the value of P denoted in the constant column is the optimal value of the objective function, Now let us look at this example. Example 1 Maximise P=7x+4y subjectto 2x+ y<150 4x+3y < 350 x+ y2> 80 (x, y20) Converting the inequalities to equations, we have Also, of course, P—7x- 4y=0. NOTE that since the third constraint is a ‘greater than’ statement, we must subtract the slack positive variable (ws) to form the equation. Alternatively, we could have written the inequality as —x —y < —80 so that —x—y + ws = —80 and so x+y — wy = 80, Forming the first tableau, in the usual manner, we obtain Optimization and linear programming 963 Now we are stuck, for we do not have a unity matrix to start off with. The entry in the ws column {s —1 and not the necessary +1, and no amount of manipulation will help since the entries in the constant column (6) are, by definition, positive. So how can we find a starting technique? Let us restate the problem. Maximise P=7x+4y ( 44 J subject to 2x+ y+wy = 150 4x+3y + We = 350 zt+y —w;= 80 The trouble comes in the third constraint by virtue of the negative sign of the slack variable. To save the situation, we introduce a new small positive variable (w4) so that w,,w2 and ws will give rise to a unity matrix and the simplex computation can then proceed. Of Course, wg is ficticious, is extremely small and cannot appear in the final basic solution. To establish this, we include in the objective function a new term —Mwg, where M is an extremely large positive value which will ensure that w, will ultimately vanish. So we now write P=7x+4y —-Mws The new variable, wg, is called an artificial variable: it \s introduced solely so that the simplex procedure can be carried out; and it must not appear in the final basic solution listed in the basis column, ‘The third constraint above now becomes x+y — Wa + Wy = 80 Next frame _ 964 Programme 23 (45) We now have 2x+ y+wn = 150 4x+ 3y + We = 350 x+y —Wy+ we= 80 P=7x—4y +Mw= 0 Forming the tableau in the usual way: Basis x y Wi Wa Ws Wy @ is" ~0 w2 43 041 W4 110 0 P 7-4 0 0 Note that: (1) The columns headed w;,w2, ws now form the unity matrix. (2) There are now 6 variables and 3 constraints, i.e, n = 6 and m= 3. At least (nm — 1m), ie. 6 — 3 = 3, variables are put equal to zero. We start off with x, y, w3 as zero and w1,W2,W4 form the first basic solution with the values given in the b column. We now proceed in the normal way. Solve the first tableau and check the results so far in the following frame. Optimization and linear programming 965 b check 46) Basis | x y wy Wo Wa We om ay i tt 0 O40" as0 154 we 4/3 0 1 0 0 | 350 358 | if 10 o-1 1] 80 | 82 ep |i-7]-4 0 0 o mw o] M-11 wy @ 3 4 0 0 0 75 17 We 4 3 0 1 0 0 | 350 358 ws 1 1 0 O-1 1] 80 82 0 0 0M 0] M-11 x D077 0. 75 77 1 0 0 | so 50 o-1 1 5 s o 0 525 | M+528 The basic variable w; can be replaced by x and we continue as before to remove the further negative entry in the index row. Do that Basis | x y Wi We Ws Wa d x Viale F Seo yh 75 7 w, | 0 ‘| 21 0 0 30 50 ws Oo} | -4 0 -1 1 s 5 P 0 |- g 0 M S25 | M+S28 x or a a 75 7 w |0 1 -2 1 0 0 so so ws o @ -1 0 -2 a 10 10 P 0-4 %o 0 M S25 | M+528 x 10" “2 +0 -1 70 72 w |O 0 -1 1 2 -2 40 40 yw | 0 2 1 0 +2 2 10 10 Pp [o 0 3 0 -1 M+1 | s30 { m+s33 | The basic variable w, is now replaced by y (the column of the last unit pivot). We now have another negative entry in the index row, so we have to perform the simplex calculation yet again. For the next round, we get - 966 — Programme 23 Basis zy Wi Ww ws x 1. 0-1 OFT | wa 00-1 ats y 0 1 =1 0 |-2 P oo 3 o|-1 x 1c. -@- 3 we oo -} 4; @® y 01-1 0 -2 P 00 3 0-1 x 10 3 -} 0 w3 Wa oO=§ 2 1 y 01-2 1 «0 P 00> =a 4— 0 No further negative entry remains in the index row. The optimal solution has been found, i.e. Prax = $50 with x = 50, y = 50. In addition, we see that ws = 20 while w; = w2 = W4 = O since they do not occur in the basic variable column. Notice, also, that ws, the artificial variable, does not figure in the optimal solution — as indeed it must not. Next frame [ 49 ) Here is one for you to do in the same way. Example 2 Maximise P= 2x +Sy subjectto x+4y<60 3x+2y <40 x+ y212 (%,y20) Work right through it, just as before. The result ls Optimization and linear programming 4,y-14 Prax = 78 with x ge on Wt "3 ++ 2 1 2 + = + Pare +++) wand 1 % 4 = 2 g % ¥ = - altl|s tle > o Zle 2y}9 slit Se Lo SRG Oo ole gle olslelFl= 7/eJOs «l 25 (x,y>0) Inserting the slack variables and artificial variable as required, we have (52) 2x+3y+m 20 xt yo tw 31+ 5y P—8x-4y That is very much as before, so work through it and check with the next frame. 53 Here it is. Basis | xy Wi Wa Ws wy | Bb ‘check wr 2] 3 1 0 0 0 | 120 | 126 W2 tl} 10 1:0 0 | 45 48 wm |{[-3] 5 0 0-1 1] 25 27 Pp [is)-4 0 0 0 M o | m-12 w 0 11-2 0 0/ 30 30 xWwe 1 10 1 0 0] 45 48 oom o 8 0 3-1 1 | 160} 471 [-2 o 40 8 0 M | 360 | M+372 ‘There is no further negative entry in the index row, so it looks as though the optimal solution has been attained. However, the artificial variable w, still remains in the basic variable column at * and thus must be removed. Therefore, we take the entry at the junction of the y column and the ws row as the pivot and proceed to eliminate ws by simplifying the tableau a stage further. If we do that, we get ... Optimization and linear programming 969 | Basis x yw We Ws b check wi 011-2 0 #0 30 30 x bt Oo bo 10 45 48 + o[s| 0 -1 1 160 171 P 040 o M 360 | M+372 wi ori1-—2 0 0 30 30 x £.'2.'0 SO £0: 45 48 tie Ws o@Mo t-t 4 20 + P 040 8 0 M 360 | M+372 wi oo 1-¥ 4 -} 10 g 4 100 § 4 -3 2s 2B yw 010 j -} i 50 ip Pp [oo 0 # 3 M-}| 280 | M+ The artificial variable, ws, is now replaced by y in the basic variable column and the optimal solution has been reached. .. Pmax = 280 with x=25, y=20, Next frame Now here is one for you to deal with. (55) Example 4 Maximise P= 10x+2y subject to -x+2y< 60 5x+4y < 260 -x+8y> 80 (x,y 20) Work through it as before and see if you agree with the solution in the next frame. Programme 23 970 x+ 2+ Sx+4y —x+ By P—10x—2y +2 80 —wit We = 0 +Mws +e 3 8 8 ils 3 ={2[s 2 alloca = = = = cls a gigi a sige s 2/8 et RIO oO A/R/O OR NE | = S/S So FIO[S © wig) O [aR 4s ott] et I t ° wa Ss s 9 ° glo nm o/eo/o ew o]o|o ew o/o 1 eg slale eg slsle ¢ slsle« gla] = fle x f Pr =15. 430 with x=40, y Now for another example ‘eae Optimization and linear programming 971 a. This one is slightly different, so take note. Maximise P= 1ix+ 1Sy subjectto = 3x + Sy < 130 —4x+S5y> 25 x+S5y> 75 (2,y>0) In this problem, notice that there are two ‘greater than’ inequalities so that there will be two slack variables to be subtracted and two artificial variables to be incorporated. In the objective function, we can use the same factor, M, for both artificial variables, since neither of those two variables will appear in the final optimal solution. So, we have: 3x+ Sp+wy = 130 —4x+ Sy —wW2 + = 25 x+ Sy — Wy + wWs= 75 P—11x— 1Sy +Mw,+Mws= 0 Wi, 4, Ws Now form the unity matrix from which to start. The method is just the same as in previous examples, so finish it off. Programme 23 972 \s| t 8 8 3)8/8]5|./8 © =), + =/8]8[e/e|g 7 e]e]8 7] ale aaelglas aig had | © Llelo|-|z]o o alzlo ol/-|= eae Shane ele ” eo = - 7 =| - a ~ ‘ Flo|nlojzjo w ojzie TIS wT ag OT Ly slelelslele © slele efafe ~aalm|- 2 ole zlelelelele welel= ae]. oo Ato ot no El-Jole|o|- © clolno © ofolm o o]o lam aa —/ ar] FPP @»|sle = ~elele = clelosele ; «(Pht lale rise © «lele o xlolo o alo CT TT] dle ze els|z z elele g e}s|e > glale s gla|e = *le]¢ a x/s i 2 420 with x= 15, y=17. 25 and w; Prnax So there it is. Incidentally, also, ws Optimization and linear programming 973 Our examples on the use of artificial variables have so far concerned only two problem variables, x and y. The method, however, is exactly the same when more problem variables are involved, though, naturally, the solution then becomes somewhat longer. Here is one for you to work through: it brings in most of what we have covered and provides excellent revision. The result is given in the next frame, Example 6 Maximise P = 24x + 21y +30z subject to 124 4y +82 < 240 Bx+3y+32< 140 6x+2y+32>110 (x,y, 2>0) Prax = 750 with x= 10, y= 10,2=10 (60) The simplex technique is designed to maximise a given objective function in the light of stated constraints, However, a problem requiring the minimisation of an objective function (denoting costs, machine idling time, etc.) can easily be converted for solution by the same method. For this, move on to the next frame Minimisation If P denotes the objective function to be minimised, we write Q as the negative of this function. Qmx is then determined by the usual simplex method and, finally, the negative value of Qnax is the value of the required Prin. i.e. Write Q = —P. Determine Quax in the normal way. Then Prin =—(Qmax)- Example 1 Minimise P= —3x +4y subjectto x +3y12 (x, y>0) First write Q=—P, Le. Q=3x—4y, and maximise Q. Inserting the usual slack variables and artificial variable as needed, we have . . Sh

You might also like