APPLIED OPERATIONAL RESEARCH FOR MANAGEMENT NOTES 1 ANNA UNIVERSITY CHENNAI UNIT I INTRODUCTION TO LINEAR PROGRAMMING (LP) INTRODUCTION Operations Research (OR) (a term coined by McClosky and Trefthen in 1940) was a technique that evolved during World War II to effectively use the limited military resources and yet achieve the best possible results in military operations. In essence you can state that OR is a technique that helps achieve best (optimum) results under the given set of limited resources.

Over the years, OR has been adapted and used very much in the manufacturing sector towards optimization of resources.That is to use minimum resources to achieve maximum output or profit or revenue. Learning Objectives The learning objectives in this unit are 1.

To formulate a Linear programming problem (LPP) from set of statements. 2. To solve the LPP using graphical method ( For 2 variables) 3. To solve the LPP using primal simplex method ( For > 2 variables and all 2 variables and all mixed constraints) 5. To solve the LPP using dual simplex method ( For > 2 variables and the solution is infeasible) 6.

We also have a look at the effect of changing the values of parameters on the decision variables (Sensitivity Analysis)Applications of Operations Research in functional areas of Management The models of OR can be used by economists, statisticians, administrators and technicians both in defence and in business. In general OR can be applied in all the functional areas of Management namely. , Accounting, Construction, Facilities Planning, Marketing, Finance, Personnel, Research and Development and Production.

DBA 1701 NOTES 2 ANNA UNIVERSITY CHENNAI Accounting Assigning audit teams effectively Credit policy analysis Cash flow planning Developing standard costs Establishing costs for byproducts Planning of delinquent account strategyConstruction Project scheduling, Monitoring and control Determination of proper work force Deployment of work force Allocation of resources to projects Facilities Planning Factory location and size decision Estimation of number of facilities Hospital planning International logistic system design Transportation loading and unloading Warehouse location decision Finance Building cash management models Allocating capital among various alternatives Building financial planning models Investment analysis Portfolio analysis Dividend policy making Production Inventory control Marketing balance projection Production schedulingProduction smoothing Marketing Advertising budget allocation Product introduction timing Selection of Product mix Deciding most effective packaging alternative Organizational Behavior / Human Resources Personnel planning Recruitment of employees Skill balancing Training program scheduling Designing organizational structure more effectively APPLIED OPERATIONAL RESEARCH FOR MANAGEMENT NOTES 3 ANNA UNIVERSITY CHENNAI Purchasing Optimal buying Optimal reordering Materials transfer Research and Development R & D Projects control R & D Budget allocation Planning of Product introductionIn general solution to an OR problem will have the following stages. 1. Formulating the problem 2. Constructing a mathematical model based on the formulation 3. Solving the problem based on the model. 4. Checking whether the solution is optimal and feasible 5. Iterate till optimal and feasible solution is reached.

We have two new terms “optimal” and “feasible”. Optimal means the best possible solution under the given conditions and feasible means a practical solution. Therefore optimal and feasible solution means that the suggested solution must be both practical to implement and the best one under the given conditions.All types of problems in OR can be categorized as either MINIMIZING or MAXIMIZING type. We will focus on MINIMIZING costs, time and distances while we will be interested in MAXIMIZING revenue, profits and returns. So you must be very careful in identifying the type of problem while deciding upon the choice of algorithm to solve the given problem.

With this brief introduction I think it is time we get going with the real content. As I had mentioned earlier the first stage in solving a problem through OR models is to formulate the given problem statement into an Linear Programming Problem or Model (LPP) 1. FORMULATION OF LINEAR PROGRAMMING PROBLEM (LPP) Example 1. 1 Elixir paints produces both interior and exterior paints from two raw materials M1 and M2. The following table provides the data DBA 1701 NOTES 4 ANNA UNIVERSITY CHENNAI Table 1.

1 The market survey restricts the market daily demand of interior paints to 2 tons. Additionally the daily demand for interior paints cannot exceed that of exterior paints by more than 1 ton. Formulate the LPP. Solution: The general procedure for formulation of an LPP is as follows 1. To identify and name the decision variables.That is to find out the variables of significance and what is to be ultimately determined. In this example the quantity (In tons) of exterior (EP) and interior paints (IP) to be produced under the given constraints to maximize the total profit is to be found.

Therefore the EP and IP are the decision variables. The decision variables EP and IP can be assigned name such as EP = x1 and IP =x2. 2. To the frame the objective equation. Our objective is to maximize the profits by producing the right quantity of EP and IP. For every ton of EP produced a profit Rs 5000/- and for every ton of IP a profit of Rs 4000/- is made.

This is indicated as 5 and 4 in table 1. 1 as profit in thousands of rupees. We can use the values of 5 and 4 in our objective equation and later multiply by a factor 1000 in the final answer. Therefore the objective equation is framed as Max (Z) = 5 x1 + 4 x2 Where x1 and x2 represent the quantities (in tons) of EP and IP to be produced.

3. To identify the constraints and frame the constraint equations In the problem statement there are constraints relating to the raw materials used and there are constraints relating to the demand for the exterior and interior paints.Let us first examine the raw material constraints. There are two types of raw materials used namely APPLIED OPERATIONAL RESEARCH FOR MANAGEMENT NOTES 5 ANNA UNIVERSITY CHENNAI M1 and M2. The maximum availability of M1 every day is given as 24 tons and the problem (refer table 1.

1) states that 6 tons of M1 is required for producing 1 ton of exterior paint. Now the quantity of exterior paint to be produced is denoted as x1, so if 6 tons of M1 is required for producing 1 ton of exterior paint, to produce x1 tons of exterior paint (6 * x1) tons of M1 is required.Similarly the problem states that 4 tons of M1 is required for producing 1 ton of interior paint. Now the quantity of interior paint to be produced is denoted as x2, so if 4 tons of M1 is required for producing 1 ton of interior paint, to produce x2 tons of exterior paint (4 * x2) tons of M1 is required. But the total quantity of M1 used for producing x1 quantity of exterior paint and x2 quantity of interior paint cannot exceed 24 tons (since that is the maximum availability).

Therefore the constraint equation can be written as 6 x1 +4 x2 < = 24In the same way the constraint equation for the raw material M2 can be framed. At this point I would suggest that you must try to frame the constraint equation for raw material M2 on your own and then look into the equation given in the text. To encourage you to frame this equation on your own I am not exposing the equation now but am showing this equation in the consolidated solution to the problem. Well now that you have become confident by framing the second constraint equation correctly (I am sure you have), let us now look to frame the demand constraints for the problem.The problem states that the daily demand for interior paints is restricted to 2 tons. In other words a maximum of 2 tons of interior paint can be sold per day.

If not more than 2 tons of interior paints can be sold in a day, it advisable to limit the production of interior paints also to a maximum of 2 tons per day (I am sure you agree with me). Since the quantity of interior paints produced is denoted by x2, the constraint is now written as x2 = 0 All the four special cases have been shown as charts 1. 3, 1. 4, 1.

5 and 1,6 respectively.I would urge to first try to draw the charts on your own, then compare it with the charts shown in the text and then see whether it matches with the titles mentioned in the case heading. Chart 1.

3 DBA 1701 NOTES 16 ANNA UNIVERSITY CHENNAI Chart 1. 4 APPLIED OPERATIONAL RESEARCH FOR MANAGEMENT NOTES 17 ANNA UNIVERSITY CHENNAI Chart 1. 5 DBA 1701 NOTES 18 ANNA UNIVERSITY CHENNAI Chart 1.

6 Now that you have become experts in solving 2 variable problems through the graphical method we shall learn to solve through the simplex method. 1. 3 INTRODUCTION TO SOLUTIONS TO LPP THROUGH SIMPLEX METHOD.

The LP problems that involve more than 2 variables cannot be solved by graphical method but will have to make use of the simplex algorithm. Brace yourselves and fasten your seat belts since the simplex method is going to call for the best of concentration from your end. We will first solve a 2 variable problem through simplex method and then go on to solve a three variable problem. At this point I would like to introduce four types of simplex algorithms or methods APPLIED OPERATIONAL RESEARCH FOR MANAGEMENT NOTES 19 ANNA UNIVERSITY CHENNAI which we will familiarize ourselves with shortly. The methods are 1.

Primal Simplex 2. Big – M (or) Penalty 3. Two Phase and 4.

Dual Simplex method The first three methods that is, Primal simplex, Big – M and Two phase methods are adopted to solve when there is a initial feasible solution formulated and then the algorithms work towards achieving optimality in the consequent iterations. That is these three methods start from a feasible but non-optimal solution and iterate towards feasible and optimal solution. But if there exists an optimal but infeasible solution, then the dual simplex method would be adopted to achieve feasibility while still maintaining optimality.That is the dual simplex method starts from optimal but infeasible solution and proceeds to achieve an optimal and feasible solution. Well the above information is just an introduction so don’t get too disturbed if you are not able to immediately understand all that is said about the above methods, you are soon going to be masters in these methods as we progress through the course. However I would urge you to read a little more carefully from this point. The primal simplex method is adopted when all constraints are = 0 Do you recognize this problem?This is the same problem that we first formulated and then solved graphically. We shall now solve the same problem through primal simplex method for you to appreciate (or not to) the same.

Solution The first step here is to convert all the inequalities in the constraint equations into equalities. On examining the constraint equations you will notice that they are all of < = type. That is, the left hand side (LHS) of the equation is less than the right hand side (RHS). So we need to add a quantity (as variables) to the LHS in each of the equations that will help alance both sides and replace the inequalities into equalities. You will agree that x1 and x2 are variables in the problem.

Additionally let us introduce slack variables (s) to each of the equations to balance and introduce the equality sign. Considering the first constraint, 6×1 + 4×2 < = 24 Let us introduce a slack variable (s1) to the LHS and balance the equation. Hence the constraint equation can now be written as 6×1 + 4×2 + s1 = 24 Similarly we can introduce slack variables s2, s3, s4 for the constraints 2, 3 and 4 respectively.Therefore the constraints are now written as x1 + 2×2 + s2< = 6 x2 + s3 < = 2 x1 + x2 + s4< = 1 APPLIED OPERATIONAL RESEARCH FOR MANAGEMENT NOTES 21 ANNA UNIVERSITY CHENNAI We now have six variables (two original variables and four slack variables introduced by us). We must understand that the slack variable introduced by us have no weight-age in the objective Z equation. Therefore the coefficients of the slack variables in the objective Z equation will be 0 (Zero). The number of variables (n) = 6 The number of constraint equations (m) = 4Therefore the number of non-basic variables in the problem will be n-m = 6 – 4 = 2 If 2 out of 6 variables are non-basic variables then the number of basic variables = 4 We have to now identify the basic and the non-basic variables.

In our earlier discussion we had stated that in the primal simplex method we will start with a feasible solution and then iterate towards optimality. A sure feasible solution to the problem is with the assumption that x1 =0 and x2 =0. Yes, this is a feasible but not optimal solution.

We start with this assumption and then determine better values for x1 and x2 that will give us the optimal solution.If we substitute the values of x1 =0 and x2 =0 in the four constraint equations, then we get s1 = 24, s2 = 6, s3 = 2, s4 = 1. Therefore s1 = 24, s2 = 6, s3 = 2, s4 = 1 are going to be starting points of our solution and are known as the basic variables. The non basic variables are x1 =0 and x2 =0. All the variables in the Z equation are brought to the LHS and are written like this Z – 5 x1 – 4 x2 – 0 s1- 0 s2 – 0 s3 – 0 s4 = 0 We have already mentioned that the coefficients of the slack variables are zero in the objective equation.We must now frame the initial simplex table as given under. Name the columns like this : Basis, x1 , x2 , s1 , s2 , s3 , s4 , Solution and Ratio.

That is the first column must always be named as the basis, then all the participating variables must be listed, then the solution column and finally the ratio column. Under the basis column, the Z variable and the basic variables are listed. Please remember the basic variables will change with every iteration (as variables enter or leave the basis) and the variables that are not under the basis column as all non-basic variables.In this problem, since the initial basic feasible solution has started with s1 , s2 , s3 , s4 as the basic variables they are appearing in the basis in the initial simplex table. This table represents the initial basic feasible solution. DBA 1701 NOTES 22 ANNA UNIVERSITY CHENNAI Table 1.

4 – Initial simplex table On close observation you will understand that the values in the Z row represent the coefficients of the existing variables in the objective Z equation where the RHS =0. Similarly the values of s1 are the coefficients of the first constraint equation where the solution or RHS = 24.In similar fashion, the values in the rows s2, s3, and s4 represent the 2nd, 3rd and 4th constraint equations respectively. Having framed the initial simplex table, let us now find the variable that will enter the basis (know as entering variable and abbreviated as EV). Only the variables that are not part of the basis (That is the non-basic variables) can qualify to be an EV. Now to choose and EV from the non-basic variables (we have two non-basic variables x1 and x2 in this problem) I suggest you read the optimality condition once again and then return to this page.Trusting that you have read the optimality condition, let me refresh the statement for you in a simple form. The optimality condition says that the entering variable in a maximizing problem is the variable with the most negative coefficient in the objective Z equation.

Going by this condition and observing the objective Z equation in the initial simplex table, you find that -5 is the most negative coefficient. Therefore x1 will be the entering variable. In-order to identify the leaving variable; let us refresh our memory with the feasibility condition.The feasibility condition states that “for both maximizing and minimizing problems, the leaving variable is the current basic variable having the smallest intercept (a minimum ratio with strictly positive denominator) in the direction of the entering variable. A tie may be broken arbitrarily”.

Examine the EV column and the solution in table 1. 4. There are four basis variables in this stage s1, s2, s3, and s4. Therefore one of them is going to be the leaving variable. The values in the EV column (also known as the pivotal column) for the four basic variables will be the denominators.

Hence if there are any negative values in the EV column then such basic variables need not be considered for leaving the basis. The corresponding solution column will be the numerator. Now select the least ratio by dividing the solution column by the EV column. That is for s1 it is 24/6, for s2 it is 6/1, for s3 it is 2/ 0 and we need not consider s4 since it has a negative denominator.

These values are filled and shown in table 1. 5 below APPLIED OPERATIONAL RESEARCH FOR MANAGEMENT NOTES 23 ANNA UNIVERSITY CHENNAI Table 1. 5 – Initial simplex table with EV and LV identifiedBased on the feasibility condition where the least ratio with a strictly positive denominator is to be chosen, we choose s1 to be the leaving variable (LV). The leaving variable row is also known as the pivotal row.

The Pivotal row (LV row) and the Pivotal Column (EV column) are shown in italics in table 1. 3. The element which is the junction of the EV column and LV row is known as the pivotal element. Now the pivotal element (PE) in this case is 6. You can refer to the table 1.

3 to identify the pivotal element. In the next iteration s1 would not be in the basis and x1 would have entered the basis.This is shown in the table below. Table 1. 6 – I Iteration empty table Now we can perform the iteration to improve upon the solution towards optimality using the change of basis by Guass-Jordan method.

The new pivotal equation or row (NPR) = old pivotal row / pivotal element. The new variable (x1) that has entered the basis is the new pivotal row. The LV row is the old pivotal row and the pivotal element has already been identified as 6 (the element in the junction of EV column and LV row). Now divide every element of the old pivotal row (that is the leaving variable row) by 6 (the pivotal element).The resulting new pivotal row is shown in table 1. 7 DBA 1701 NOTES 24 ANNA UNIVERSITY CHENNAI Table 1. 7 – I Iteration table – with new pivotal row values. The other rows in the basis are computed as follows.

New Equation = Old Equation – (its EV column coefficient) * the NPR I shall show how the Z equation is computed. Please refer to the Table 1. 5 to get the old Z equation. The values are The EV column coefficient of the Z equation is -5. We will have to multiply this value (-5) to the NPR and then subtract it from the old Z equation.Alternatively what we will do is to add a negative sign to the EV column coefficient and convert it into (+5), then multiply it with all elements of the NPR and then add to the old Z equation to get the new Z equation. Let us see how this is done.

The NPR is (already computed in table 1. 7) The EV column coefficient is -5. With a negative sign added, it now becomes +5.

If the NPR values are multiplied by the +5 value, the resulting row is Now this row is to be added to the old Z equation to get the new Z equation. The values are shown in the table 1. 8APPLIED OPERATIONAL RESEARCH FOR MANAGEMENT NOTES 25 ANNA UNIVERSITY CHENNAI Table 1. 8 – Computing new Z equation The computed new Z equation is filled in the I iteration table.

Table 1. 9 – I Iteration table – with new Z equation Similarly the new s2 equation can be computed Table 1. 10 – Computing new s2 equation The new s2 equation is filled in the I iteration table and is shown in Table 1. 11. DBA 1701 NOTES 26 ANNA UNIVERSITY CHENNAI Table 1.

11 – I Iteration table – with new s2 equation We next compute the s3 equation using a similar procedure. Table 1. 12 – Computing new s3 equationThe computed s3 equation is now filled in the I iteration table and is shown in table 1. 13. Table 1. 13 – I Iteration table – with new s3 equation We finally compute s4 which is also a basic variable.

The computation of s4 is shown in the table 1. 14 below. Table 1. 14 – Computing new s4 equation The computed new equation is now filled in the I iteration table and the same is shown in table 1. 15 below APPLIED OPERATIONAL RESEARCH FOR MANAGEMENT NOTES 27 ANNA UNIVERSITY CHENNAI Table 1. 15 – I Iteration table – with new s4 equation The I-iteration table is now ready.We have to check whether optimality has been reached. The optimality condition states that if the coefficients of the non-basic variables in the Z equation are non-negative in a maximizing problem, then optimality is reached.

The coefficients of the Z equation are From the above table, it is seen that there is a negative coefficient and the corresponding variable is x2. Therefore we know that optimality has not been reached. We shall now proceed to the next iteration (that is II iteration). We have to identify the EV at this stage.

The procedure is similar to what we had followed earlier.There is only one negative coefficient and the corresponding variable is x2. Hence x2 will be the EV. To find out the LV variable examine the Solution column and the x2 column. The values in the solution column will be the numerator and the corresponding values (only positive values) in the x2 column will be the denominator. Find the least positive ratio from the existing basic variables.

The one with the least positive ratio will be the LV. The ratios are shown in table 1. 16 below. Table 1. 16 – I Iteration table – with EV and LV variable highlighted DBA 1701 NOTES 28 ANNA UNIVERSITY CHENNAIFrom table 1. 16 it is seen that the least positive ratio is 3/2 and this corresponds to variable s2.

Therefore the leaving variable (LV) is s2. Remember that the Z equation will not be considered for LV as it must never leave the basis. As we already know, the EV column is the pivotal column and the LV is the pivotal row. You very well know that the pivotal element is 4/3. We shall proceed to the II- iteration just the way we proceeded with the I-iteration.

We first compute the NPR using the procedure as explained in the Iiteration. The NPR is as shown in table 1. 17. Table 1. 7 – II Iteration table – with new pivotal row I shall now give the blank formats for you compute the Z, x1, s3 and s4, rows. You can try the calculations and try to fill the values in the blank spaces provided.

You can cross check your answers with the II- iteration table that I have shown below. I would encourage you to do the calculations sincerely since this is the place where you would have plenty of scope to commit errors. So if the calculations done by you match with the answers that I have shown in the II –iteration table 1. 21, then your levels of confidence would go up.To start with, try calculating the new Z equation.

Then you proceed to calculate the other variables. Table 1. 18 – Computing new Z equation Now you may check with table 1. 21 to see if your calculations of new Z equation match with the values given in the II-iteration table. Now you can proceed to calculate the new s3 equation and fill in the blank spaces.

APPLIED OPERATIONAL RESEARCH FOR MANAGEMENT NOTES 29 ANNA UNIVERSITY CHENNAI Table 1. 19 – Computing new s3 equation Now you may check with table1. 21, to see if your calculations of the new s3 equation match with the values given in the II-iteration table.Now you can proceed to calculate the new s4 equation and fill in the blank spaces. Table 1.

20 – Computing new s4 equation Since we have calculated all the required variables (rows) for the II iteration table, let us look at the II iteration table (that is table 1. 21). Table 1.

21 – II Iteration table – with calculated values On having a close look at the Z equation in the table 1. 21, you will understand that since all coefficients are non-negative (zero values are neither positive nor negative) we have reached an optimal and feasible solution.The calculated values of x1 = 3 and x2 = 3/ 2 are underlined in the table. For these values of x1 and x2 the value of the objective function Z = 21. You may remember that this is the same solution we have got through the graphical method for the same problem. DBA 1701 NOTES 30 ANNA UNIVERSITY CHENNAI How are you feeling after reading through this procedure? If you are excited to try out a problem similar to the one just solved, here’s one for you. Since we have fairly become familiar with the simplex procedure for two variables, let us now proceed to solve a three variable problem.

Don’t worry the procedure is exactly the same as in a two variable problem. So you can try the problem and cross check the answers for each iteration from the table given in the text. Example 4: Max Z = 22 x + 30y + 25z Subject to: 2x + 2y + z < =100 2x + y + z < = 100 x + y + 2 z < = 100 x, y , z > = 0 . Solution We had earlier solved a similar two variable problem by first converting the inequalities into equalities by including slack variables in the constraint equations with a < = sign. We will adopt a similar procedure in this problem also.Include a slack variable in each of the constraint equations and convert them into equalities.

2x + 2y + z + s1 =100 2x + y + z + s2 = 100 x + y + 2 z + s3= 100 Now there are six variables (n) in all and there are three constraint equations(m). Therefore the number of non-basic variables (n-m) is three. Obviously the three non-basic variables would be x, y and z. By the procedure for starting with a feasible solution we assume the values of the non-basic variables to be zero. That is x=y=z = 0. If the nonbasic variables are = zero, then the basic variables s1= 100, s2 =100 and s3 =100.We can now proceed to frame the initial simplex table. At this point I would encourage you to prepare the table on your own and then check with the table in the text.

It would help you to keep solving as you read the text. As we had done in the previous problem let us bring all the elements in the Z equation to the LHS and keep the RHS = 0. Z – 22 x – 30y – 25z – 0 s1 – 0 s2- 0 s3 = 0 APPLIED OPERATIONAL RESEARCH FOR MANAGEMENT NOTES 31 ANNA UNIVERSITY CHENNAI Table 1.

22 – Initial simplex table Since this is maximizing problem, the EV will be y. And in the direction of the EV column, the ratios are calculated.Since the minimum ratio is 50, the LV variable is s1. Now proceed to calculating the NPR and all the other variables in the next iteration using the procedure that I had explained in the previous problem and check whether the values that you have calculated match with the values shown in the table below.

Table 1. 23– I Iteration table I trust that you would have calculated and checked with the I-iteration table. On observing the table we find that optimality is not reached (since all non-basic variables are not no-negative). There is a negative coefficient for z.Therefore z will be the EV now.

And in the direction of the EV the ratios are calculated. Since 100/3 is the least positive ratio, the LV is s3. Now proceed to prepare the next iteration table using the usual procedure. Table 1. 24 – II Iteration table DBA 1701 NOTES 32 ANNA UNIVERSITY CHENNAI On observing the table we find that all the coefficients in the objective Z equation are non-negative. Therefore we can conclude that optimality is reached along-with feasibility. The calculated values are x = 0 (since optimality is reached with x in the basis), y = 100/3 and z = 100/3.

The objective Z value is 5500/ 3. You can cross check the value of Z by substituting the value of x, y and z in the objective equation and see whether the value works out to be 5500/3. It is shown as 22 * 0 + 30* 100/3 + 25 * 100/3 = 5500 /3. Well now that we have solved both two and three variable problems through the primal simple method it is time for us to move to problems with mixed constraints. As mentioned earlier in the text, problems with mixed constraints can be either solved by Big- M (also known as Penalty method) or by 2-Phase method.We will solve the same problem by both methods so that you can appreciate the relative merits and de-methods of the two methods. 1.

3. 2 – Big-M or Penalty Method. We will try to understand the algorithm using an example. Example 5: Min Z = 4×1 + x2 Subject to: 3×1 + x2 = 3 4×1 + 3×2 > = 6 x1 + 2×2 < = 4 x1, x2 >= 0 Solution: We see here that the problem has mixed constraints. That is all of them are not of < = type like the problems that we solved through primal simplex method. In case of problems with mixed constraints, the Big – M or Penalty method can be used to solve.We have to introduce an artificial variable ‘A’ wherever there is a constraint with ‘=’ sign.

For constraints with ‘>=’ sign, an artificial variable ‘A’ and a surplus variable ‘s’ would have to be introduced. And for constraints with ‘< =’ sign, slack variables would be introduced. The coefficients of the artificial variable ‘A’ in the objective Z equation is a large positive integer denoted by “M”. The coefficients of the slack and surplus variables in the objective Z equation are zero. The coefficient of the artificial, surplus and slack variables in the constraint equations wherever they appear are equal to1.

Therefore the inequalities in the constraint equations are now transformed as APPLIED OPERATIONAL RESEARCH FOR MANAGEMENT NOTES 33 ANNA UNIVERSITY CHENNAI 3×1 + x2 + A1 = 3 4×1 + 3×2 + A2 – s1 = 6 x1 + 2×2 + s2 = 4 From the above equations it is seen that A1 and A2 are artificial variables, s1 is surplus variable and so is subtracted (because the LHS is > = RHS) and s2 is a slack variable. In the constraint equations we find that there are 6 variables (n) and 3 equations (m). Therefore the number of non-basic variables is n-m=3. We can conveniently state that x1 and x2 are two non-basic variables.

But how do we decide the other non-basic variable? We will have to first choose the three (because if there are three non-basic variables then obviously the remaining are basic variables) basic variables. It is also simple logic that the number of basic variables is equal to the number of constraint equations (since each basic variable makes the presence of its constraint equation felt in the initial feasible simple table). Therefore our choice of basic variables would be to ensure that all the constraint equations are present in the initial feasible simplex table. For he first constraint equation ‘A1’ is basic variable. For the second constraint equation we can either choose ‘A2’ or ‘s1’ to be the basic variable. But it is advisable to choose ‘A2’ as a basic variable (due to a positive coefficient). And in the third constraint we have no choice but to choose ‘s2’ as the basic variable. We have now decided on the basic variables.

They are A1, A2 and s2. Therefore the non-basic variables will be x1, x2 and s1. As is always the practice let us assume that the non-basic variables are equal to zero (to start with a basic feasible solution).Then the basic variables will be A1 = 3, A2 = 6 and s2 = 4. The objective Z equation is transformed as Min Z = 4×1 + x2 + M A1 + M A2 + 0 s1 + 0 s2 This is re-written as Z – 4×1 – x2 – M A1 – M A2 – 0 s1 – 0 s2 = 0 We now prepare the initial basic simplex table. Table 1.

25 – Initial simplex table (un-modified) DBA 1701 NOTES 34 ANNA UNIVERSITY CHENNAI Now which is the EV? If you have said x1 then you are absolutely WRONG? Because this is a minimizing problem and so the EV is the variable with the most positive coefficient in the Z equation. There is no variable with a positive coefficient in the Z equation.Also we find that there is some inconsistency in the solution of the Z equation. The coefficients of the artificial variables in the objective Z equation are ‘M’, and the artificial variables are not equal to zero. Therefore the solution in the Z equation would be in terms of ‘M’ and not zero. We have to transform the objective Z equation as per the under-mentioned procedure. Multiply the A and A rows of the initial simplex table by ‘M’ (that is the coefficient of the artificial variables) and then add it to the existing Z equation. We now have the modified initial simplex table with the new Z equation.

All other rows are the same as the un-modified table. Table 1. 26- Initial simplex table – with new Z equation (modified) Now we have to identify the EV, which is the variable with the most positive coefficient in the objective Z equation. Choose a large positive value for M, something like 100.

Then for x1 it is 700 – 4 and for x2 it is 400 – 1. So the coefficient for x1 is the most positive. Therefore x1 is the EV. We find the LV as per the known procedure (that is the least positive ratio). The LV is A1. We now proceed to the next iteration table using the well known procedure.May I once again encourage you to calculate the NPR and the other rows and then check with the table values given below. APPLIED OPERATIONAL RESEARCH FOR MANAGEMENT NOTES 35 ANNA UNIVERSITY CHENNAI Table 1.

27 – I -Iteration table On observing the table we find that the non-basic variables are still positive. Therefore optimality is not reached. The new EV will be x2 and the new leaving variable will be A2.

Going ahead to the next iteration with our known procedure, the II iteration table is shown below. Table 1. 28 – II -Iteration table Have we reached the optimal solution?If you say yes, well I must say that you are once again mistaken.

Although it appears as though optimality has been reached, it is not so. Looking carefully you will find that x1, x2, and s2 are in the basis. Therefore they are the basic variables now. This means the non-basic variables in this iteration are s1, A1 and A2. Out these non-basic variables we find that s1 has a positive coefficient. Therefore s1 is the EV and s2 is the LV (based least positive ratio).

We now proceed with the next iteration (I know you are hoping we reach the final iteration).The calculated table is shown below. DBA 1701 NOTES 36 ANNA UNIVERSITY CHENNAI Table 1. 29 – III -Iteration table We now find that all the non-basic variables in the objective Z equation are nonpositive (since this is a minimizing problem). Therefore we have reached optimality. The values are x1= 2/5, x2= 9/5 and Z = 17/5. We will now try to solve the same problem through the 2-Phase method and this will help you decide which is simpler for you to solve.

1. 3. 3 – Two-Phase Method. In the Two-Phase method the problem is solved in two stages or phases.In Phase – I, we find a basic solution of the resulting equation that minimizes the sum of the artificial variables.

If the minimum value of the sum is positive, then we conclude that the LPP has no feasible solution, else we proceed to Phase –II. In Phase – II, we use the feasible solution obtained in Phase I as a starting basic feasible solution for the original problem. Again don’t worry yourself too much if you don’t understand the above statements at this point. I shall explain clearly with an example that we will now solve.

Example: Min Z = 4×1 + x2 Subject to: 3×1 + x2 = 3 4×1 + 3×2 > = 6 1 + 2×2 < = 4 x1, x2 >= 0 Solution: In this problem we have mixed constraints and so let us use artificial, slack and surplus variables (as we did in Big-M method) to convert the inequalities into equalities. The three constraint equations APPLIED OPERATIONAL RESEARCH FOR MANAGEMENT NOTES 37 ANNA UNIVERSITY CHENNAI 3×1 + x2 = 3 4×1 + 3×2 > = 6 x1 + 2×2 < = 4 are re-written as 3×1 + x2 + A1 = 3 4×1 + 3×2 + A2 – s1 = 6 x1 + 2×2 + s2 = 4 where A1 and A1 are artificial variables, s1 is a surplus variable and s2 is a slack variable. This is similar to what we had done in Big-M method.Now instead of using the original objective equation we frame a new objective equation which minimizes the sum of the artificial variables present in the constraint equations. There are two artificial variables A1 and A2.

Therefore the new objective equation to be used in Phase-I is written as Min (R) = A1 + A2 We now solve for the new objective equation and the existing constraints. The nonbasic and basic variables are identified similar to the Big-M method. For the first constraint equation ‘A1’ is basic variable.

For the second constraint equation we can either choose ‘A2’ or ‘s1’ to be the basic variable.But it is advisable to choose ‘A2’ as a basic variable (due to a positive coefficient). And in the third constraint we have no choice but to choose ‘s2’ as the basic variable. We have now decided on the basic variables. They are A1, A2 and s2. Therefore the non-basic variables will be x1, x2 and s1.

As is always the practice let us assume that the non-basic variables are equal to zero (to start with a basic feasible solution). Then the basic variables will be A1 = 3, A2 = 6 and s2 = 4. The objective equation is re-written as R – A1 – A2= 0 We now frame the initial simplex table for Phase-I. Table 1. 0 – Initial simplex table (un-modified) Again here we find that there is no variable with the most positive coefficient in the objective equation. Also we find that there is inconsistency in the solution value (situations similar to the Big-M method). Therefore we multiply the A1 row and A2 row by the DBA 1701 NOTES 38 ANNA UNIVERSITY CHENNAI coefficients of the artificial variables and add them to the existing objective equation. Unlike in the Big-M method, where the coefficients were a large positive integer M, here the coefficients of the artificial variables in the objective equation are 1.

Therefore the new objective equation ( R ) is calculated as shown below. We now write the new R equation in the modified initial simplex table and proceed to solve the problem. Table 1. 31– Modified Initial simplex table with new R equation Now we have the variable x1 with the most positive coefficient 7, and so this becomes the EV. The LV is again the variable with the least positive ratio with a strictly positive denominator in the direction of the EV (as we have done in the previous problems).

Hence the LV is A1. We now proceed to the next iteration by calculating the NPR and other rows as we had done in the previous problems.The I-Iteration table is shown below for your verification (needless to say that you would have done the calculations and are referring to the table below for just cross-checking) Table 1. 32 – I Iteration Table APPLIED OPERATIONAL RESEARCH FOR MANAGEMENT NOTES 39 ANNA UNIVERSITY CHENNAI On observing the I iteration table we find that there is a positive coefficient in . Therefore optimality is not reached. Since there is a positive coefficient in x2, this becomes the EV for the next iteration.

The LV (by our known principles) is A2. We now proceed to the next iteration and the calculated values are shown in the table below.Table 1. 33– II Iteration Table On careful observation of the II iteration table we find that there are no positive values in the objective equation. Therefore we can conclude optimality is reached in Phase- I. Also we find that the solution value in the Objective R equation is non-positive, therefore we can proceed to Phase –II. Phase II We now use the feasible solution (omitting the artificial variables) obtained in Phase I and continue with the original objective equation. The feasible solution table from phase I without the artificial variable columns is shown below.

Table 1. 34 – Feasible Solution Table from Phase I (without artificial variables) We now replace the objective R equation with the original Z equation. The original Z equation was Min (Z) = 4 x1 + x2 + 0s1 + 0 s2 This is re-written as Z – 4 x1 – x2 – 0s1 – 0 s2 = 0 Therefore the new initial table for Phase II is prepared as given below. DBA 1701 NOTES 40 ANNA UNIVERSITY CHENNAI Table 1. 35 – Initial Table (unmodified) for Phase II (with original Z equaton) We once again find that there is no positive coefficient in the objective equation to be selected as the EV.Also there is no consistency in the solution value (since x1 = 3/5 and x2 = 6/5). So we multiply the x1 and x2 row with their coefficients (4 and 1) from the objective Z equation and add the same to the existing Z equation.

We shall now write the new Z equation in the modified table. Table 1. 36 – Initial Table (modified) for Phase II (with original Z equaton) We find that there is a positive coefficient for s1 .

So this is the EV. The LV is s2 . We proceed to the next iteration with the usual procedure. The next iteration table is shown for your verification.

APPLIED OPERATIONAL RESEARCH FOR MANAGEMENTNOTES 41 ANNA UNIVERSITY CHENNAI Table 1. 37 – I Iteration Table for Phase II We find that there are all the coefficients in the objective Z equation are non-positive. Therefore we have reached optimality. The solution values are x = 2/5, x = 9/5 and Z = 17/5. Now that we have done both Big-M and 2-Phase method for a mixed constraint problem, you can decide to adopt any one of the methods (unless otherwise specified) to solve a mixed constraint problem. The algorithms that we have so far learnt have started with a feasible solution and then proceeded towards optimality.

Suppose we have a situation where the initial basic solution resembles optimality, that is all the non-basic variables in a maximizing problem are nonnegative and all non-basic variables in the minimizing problem are non-positive in the objective Z equation, then we have to adopt a procedure known as the DUAL SIMPLEX METHOD. 1. 3. 4 Dual Simplex Method To adopt the dual simplex method, the starting table must have an optimum objective row with at-least one infeasible ( = 3 4 x1 + 3 x2 > = 6 x1 + x2 < = 3 x1, x2 > = 0 Solution: Let us convert all the constraint equations to < = type .

The third constraint equation is already < = type but we will have to multiply the first and the second constraint equations throughout by (-1) in-order to convert them into a = 3 4×1 + 3×2 >= 6 x1 + x2 = 0 New Constraints:S -3×1 – x2 +s1 = -3 -4×1 – 3×2 +s2 =-6 x1 +x2 +s3 = 3 Z – 3×1 – 2×2 -0s1 -0s2 -0s3 =0 Var (n) = 5 CE (m) = 3 NBV =2 (x1, x2) S1 = -3; s2 = -6 ; s3 =3; DBA 1701 NOTES 46 ANNA UNIVERSITY CHENNAI 1. 4 PRINCIPLE OF DUALITY Write the dual of 2×1 + 3×2 + x3 = 2 y1 + 3y2 + y3 >= 4 y1 , y2 ,y3 >=0 2) Write the dual of the following primal Max (Z) = 2×1 +x2 x1 +2×2 =3 -3×1-x2