Good morning, and welcome to this the lecture number 9 of the course Water Resource Systems, Modeling Techniques and Analysis. We have been discussing now, the linear programming problems. And in the previous lecture I introduced the general form of the linear programming problem; where we would be typically writing the objective function as maximize that, which is the linear function of the decision variables x 1, x 2 etcetera, x n subject to equality constraint. So, we will add slack variables or deduct surplus variable etcetera So, we convert a given linear programming problem in to a standard linear programming problem form, standard form of the linear programming problem. Then we went on to examine the graphical solution which in fact, e provides as with the motivation for the algebraic solutions In the graphical solution you recall that we retain the original constraints, let us say 3 x 1 plus 5 x 2 less than or equal to 12 or some this thing. And then identify first associated with each of this constraint we identify the binding region of the edge of the feasible space corresponding to that particular constraint Then if there is a feasible region exists, the feasible region being that particular region in which all the constraint is satisfied So, this is the intersecting region formed by all the constraints and because, we are talking about non negative variables x 1 greater than 0 x 2 greater than or equal to 0 etcetera, we are always looking at the solutions in the first quadrant in the graphical solution So, the graphical method is what we introduced in the previous class, previous lecture then we also introduce the General form of the LP, then towards the end of the lecture I was just leading to the Motivation for the simplex method. Now, the simplex method is the algebraic way of solving the linear programming problems, and it is an iterative way starting with a given solution we keep on improving the solutions, until no further improvement is possible in the solution Recall that in the Graphical method this is the exactly what we did. We identify a feasible region, then keep increasing Z value as long as we we have at least one point on Z line which is in the feasible region, that Z value is the feasible value or that solution is the feasible solution So, we keep on increasing the Z value until, no further increase in the Z value is possible without leaving the feasibility, feasible region that is the optimal solution, much the same way we do it, do in the algebraic manner We start with the solution and then keep improving the solutions until, no further improvement is possible without rending rendering one of the constraints to be violated, so that is the motivation for the simplex method What we will do now, is that we will take a simple two variable problem solve it with the graphical solution. And then see, how we can relate the graphical solution with the algebraic solution and how we lead to algebraic solution with the two variable problems So let us consider this problem, which I introduce towards the end of the previous lecture, we take maximize Z is equal to 6 x 1 plus 8 x 2, subject to 5 x 1 plus 10 x 2 less than or equal to 60, 4 x 1 plus 4 x 2 less than or equal to 40 and the non negativity constraints x 1 greater than or equal to 0, x 2 greater than or equal to 0 So, what do we do in the graphical method of solution first we identify a feasible region associated with these two constraints. Which means, we first take 5 x 1 plus 10 x 2 equal to 60 draw a line corresponding to that similarly 4 x 1 plus 4 x 2 equal to 40 draw a line corresponding to that and because, we are in the first quadrant We will then identify the feasible region form by these two constraints along with the non negativity conditions. So, this is what we do 4 x 1 plus 4 x 2 is equal to 40 corresponds

to this constraint, so this lying gives you the upper bound of this constraint 4 x 1 plus 4 x 2 less than or equal to 40 and we are looking to the left of this. So, this the constraint 4 x 1 plus this is the region given by the constraint 4 x 1 plus 4 x 2 less than or equal to 40 Similarly, 5 x 1 plus 10 x 2 equal to 60 is the bound on the constraint 5 x 1 plus 10 x 2 less than or equal to 60 and the intersecting region between the region of this constraint and this particular constraint will be this region, in which any point within the region will be a feasible solution and therefore, this region is called as the feasible region We will mark this points O as the origin where x 1 equal to 0 x 2 equal to O, A then we will also take B where this line is intersecting, this constraint is intersecting the x 2 axis, C where these two constraints are intersecting each other, and D where this constraint or this line is intersecting the x 1 axis and E where this constraint is intersecting the x 1 axis. So, we have six points now O, A, B, C, D and E, what is your objective, the objective is to obtain the maximum value of Z while satisfying these two conditions; which means that, we would like to be in this region or on the boundary in this region. And yet, maximize the value Z is equal to 6 x 1 plus 8 x 2 now that is our objective, let us look at all these points now Let us say, that we write the constraint in the general form that is, we will introduce the slack variable 5 x 1 plus 10 x 2 less than or equal to 60, I convert it as 5 x 1 plus 10 x 2 plus x 3 equal to 60 where x 3 is the slack variable Similarly, 4 x 1 plus 4 x 2 less than or equal to 40, I write as 4 x 1 plus 4 x 2 plus x 4 is equal to 40 where x 4 is the slack variable; remember you need to introduce different slack variables to different constraint and all these variables including the original x 1 and x 2 and the slack variables x 3 and x 4 where all non negative So, look at what we have done now, we had original two constraints and two variables and they were less than or equal to type of constraints, now we have converted them in to equality constraints. So, you have 2 equations now, but we have 4 unknowns So, we have 2 equations and 4 unknowns x 1, x 2, x 3 and x 4, these are the 4 unknowns, so because, we have more unknowns than the number of equations, that is you have n number of variables and n number of equations; what we can do is we can obtain solution for m number of variables that is two variables in terms of the remaining n minus m number of variables So, in this case we can obtain solution for two variables in terms of the other 4 minus 2 which is equal to two variables; let us say you can obtain x 1 and x 2 in terms of x 3 and x 4 Further, what we do is, we set n minus m variables to zero and then obtain the solution for the remaining m variable; in the example that we are talking about you had 2 equations and 4 unknowns. So, we can set two variables to zero and obtain the solution for the remaining 2, so this is the way we progress, because it is possible for us to solve for m variables in terms of remaining n minus m variable, the way we progress is we set n minus m variables to zero and obtain solutions for the m variables Now, a basic solution we define as the basic solution now these three definitions are important in the simplex algorithm, so let us go through it carefully. We set n minus m variables to zero and obtain the solution cores of the remaining for the remaining m variables. Such a solution where n minus m variables are set to zero and we obtain the solution for the remaining m variable is called as a basic

solution Then the m variables for which we obtain the solution are called as the basic variables So, these are variables we have not set to zero, the remaining n minus m variables we have set to zero. So, the variables for which we are seeking a solution in terms of the remaining n minus m variables, which have been set to zero are called as the basic variables So, the m variables whose solution is sought by setting the remaining n minus m variables to zero are called the basic variable the n minus m variables which are. In fact, been set to zero are called as the non basic variables, the n minus m variables which are set to zero are called the non basic variables. Remember it may, so happen that we may get the solution to be zero when we solve for this m variable we may get solutions for the some of these variables to be zero. But they were not apriority set to zero and therefore, they are not non basic variables. So, you have the n minus m variables which are set to zero are the non basic variables So, you have three concepts here, one is the basic variables whose solutions we are seeking in terms of the remaining n minus m variable The n minus m variables which have been set to zero are called as the non-basic variables, and the solution that you, so obtain for the m variable is called as a basic solutions We will revisit the example now, so this was the example you have 2 equations and 4 unknowns So, what we will now do is we will set 2 of the variables to zero and solve for the remaining 2 what are these remaining 2 they are 4 minus 2. So, n minus m variables you are setting to zero and you are solving for n number of variables which is 2, we will revisit the example now So, this was the example you have 2 equations and 4 unknowns, so what we will now do is we will set 2 of the variables to 0 and solve for the remaining 2, what are these remaining 2 they are 4 minus 2. So, n minus m variables you are setting to 0 and you are solving for n number of variables which is 2. Now, you can solve for x you can set x 1 and x 2 to 0 solve for x 3 and x 4, you can set x 1 and x 3 to 0 solve for x 2 and x 4 and so on So, how many ways you can do this there are m number of variables n I am sorry n number of variables out of which you want to choose m number of variables. So, this can be done in n C m ways, which is simply factorial n divided by factorial m into factorial n minus m. So, these are the number of ways are the number of solutions that are possible, number of basics solutions that are possible. What are the basic solutions, basic solutions are the solutions that are obtain by setting n minus m variables to zero and solving for the remaining n variables So, n C m is the number of basic solutions that are possible. So, in this particular problem then n is the number of variables which is 4, and m is the number of constraints or number of equations in this particular case which is 2. And therefore, you get 4 factorial divided by 2 factorial into 4 minus 2 factorial which is 6. So, six basic solutions are possible for this particular problem Let us see what the six basic solutions are, and then see how the basic solutions relate to the graph that you have just drawn. We identified O, A, B, C, D and E as the corner points of this particular space, O is the origin and then you have A as the intersecting intersection between this constraint and this axis and so on, so these are the corner points Let us now look at the basic solutions, as I said we will have six basic solutions; let us see which are the basic solutions, you have these two conditions 5 x 1 plus 10 x 2 plus x 3 is equal to 60 and 4 x 1 plus 4 x 2 plus x 4 is equal to 40 these are the 2 equations that you have What is the basic solution, the basic a basic solution is in this particular case we set 2 of the variables to 0 and solve for the remaining 2, let us say we set x 1 and x 2 is equal to 0. So, out of these four we keep setting 2 of the variables to 0 and solve for the remaining 2. So, x 1 equal to 0 and x 2 equal to 0 what happens x 1 is 0 x 2 is 0 therefore, x 3 will be 60 and x 4 will be

40, so this is the solution. And look at the graph this is the point where x 1 is equal to 0 x 2 is equal to 0 So, the point on the graph is O, is it a feasible solution? It is a feasible solution, because it is on the boundary of the feasible region So, we will say feasible solution yes, it is a feasible solution. Then we set x 1 is equal to 0 and x 3 is equal to 0, so I am setting x 1 is equal to 0 and x 3 is equal to 0 therefore, x 2 I will get it as 6 and from here you get x 4 as 60 Now, x 1 is 0, x 3 is 0 which means x 1 is 0 and x 2 is 6 that will be this point x 1 is 0 and x 2 is 6 that will be point A here, is it feasible yes. It is feasible because, it is on the corner point of the feasible region Then we will set x 1 is equal to 0 and x 4 is equal to 0, so x 1 is 0 x 4 is equal to 0 from this solution you get x 2 is equal to 10 here and x 3 is equal to minus 40. So, x 2 is 10 and x 3 is equal to minus 40 look at this point, this point has x 1 is equal to 0 and x 2 is equal to 10 so this is the point here, but this is beyond the feasible region and therefore, this is not a feasible point. And In fact, x 3 is negative and therefore, it is not feasible, so the point b on the graph corresponds to x 1 is equal to 0 and x 2 is equal to 10, but it leads to a non feasible solution Because, x 3 is negative and also as you can see here the point b is beyond the feasible region. Like this then we set x 1 is equal to 0 the I am sorry x 1 x 3 is equal to 0 x 4 is equal to 0 and solve for x 1 and x 2 8 and 2 you get point C here. And similarly, you set x 2 is equal to 0, x 4 is equal to 0 you get x 1 is equal to 10 and x 3 is equal to 10 by solving these 2 equations that correspond to point D here, and then you set x 2 is equal to 0 and x 3 is equal to 0 you get x 1 is equal to 12 and x 4 is equal to minus 8 which corresponds to this point E here, that is point E which is not-feasible So, these are the six basic solutions that you could obtain, the basic solutions are in this particular case the solutions obtain by setting any two of the variables to 0 and solving for the other two variables. So, these out of these six solutions which are the basic solutions, you see that four of them are feasible solutions and two of them are non-feasible solutions. So, in in any set of basic solutions some solutions may be feasible, some solutions may be in feasible or not feasible. The solutions the basic solutions which are feasible are called as basic feasible solutions In this case you get four basic feasible solutions and the basic solutions which are not feasible are called as the non basic feasible solutions So, these are important points that you must remember, all the basic fees basic solutions need not be feasible and the basic solutions which is also feasible is also called as the basic feasible solution. And all the corner points of the feasible region are basic feasible solutions, why they are basic, because you have set two variables to 0 to obtain this solution In this case you obtain it by a setting x 1 is equal to 0, x 2 is equal to 0 and in this case you obtain by setting x 1 is equal to 0 and may be x 3 or x 3 is equal to 0, like this each of this corner points are basic solutions and they are also feasible solutions, so these form the basic feasible solutions In fact, that leads us to the way we progress in the algebraic form of solutions, starting with one basic feasible solution we should be able to progress to next basic feasible solution, which means that from one corner of the feasible region

We should be able to move to the next corner of the feasible region from there to the next corner etcetera, each time ensuring that there is an improvement in the objective function and until there is no further improvement possible or you have exhausted all the corners If you want to enumerate exhaustively or that you attain such a point beyond which there is no further improvement in the objective function possible and that becomes the optimal solution. So, in this case you had the option of going from 0 that is O to D or O to A And then once you come to A, let us say you have the option of going only to C because, that is the next feasible, basic feasible solutions, if you came to D you had the option going only to c and so on. And if C was not the optimal then you may go from, if you are come from D to C you would go to A. So, the point is that starting with the initial basic feasible solution we should move to the next basic feasible solution, such that we achieve an improvement in the objective function value now that is whole basis for the algebraic solution which is the simplex method of solution Let us see how we do this, so as you saw in this particular case there were two constraints and two variables originally and then it became four variables, because we add slack variables associated with each of the constraint each of the in equality in equality constraints And therefore, to convert them in to in equality constraints we added slack variables therefore, we ended with four variables and that led to six basic solutions out of which four where basic feasible solutions As the size of the LP problem increases the number of basic solutions will be increasing also. And in fact, in many practical problems the number of basic solutions will be very large in fact, they will run in to thousand as I mention, so the basic solutions can be quite large for a practical problem. And the number of basic feasible solutions out of these many basic solution basic feasible solutions can be also very large and therefore, it is not practicable, it is not even right to do a exhaustive enumeration what I mean by that is, that we know that the solution is on the corner So, one easier and the straight forward way is to enumerate all the solutions here, obtain a solution at A, a solution at O A C and D and then look at which of these solutions is the maximum value, now that is the straight forward way of doing, it is the enumeration But enumeration becomes infeasible, enumeration becomes, in practical problems because, there are simply two many large number of basic variables. And therefore, as I just mention we must have a method by which we start with the particular basic feasible solution and move to the next basic feasible solution Such that, when we achieve this movement where also achieving an improvement in the objective function value; that means, objective function value should be continuously increasing as we are progressing from one point to another point in the basic feasible, from one basic feasible solution to another basic feasible solution, so that is the goal Let us see, how we do this now this is our original problem and where we had maximize Z is equal to 6 x 1 plus 8 x 2 this was the original objective function We introduced the slack variables x 3 and x 4, because these were not there in the earlier problem and they should not influence the objective function we write the objective function with these slack variables having a 0 coefficient; that means, irrespective of the values of the x 3 and x 4 in the final solution your Z value should not be affected So, you write the original objective function as Maximize Z is equal to 6 x 1 plus 8 x 2 plus 0 x 3 plus 0 x 4 and these are the constraints So, we must be able to sequentially generate solutions, now start with the initial basic feasible solution and then move to the next basic feasible solution So, let us see how we do this on this problem, the first step is to determine an initial

basic feasible solution the solution as to be basic, which means that in this particular case you will set two variables to zero and obtain the solution for the remaining two that is the basic solutions, and such a solution must be also be feasible in the sense that it should be one of the corner points. So, basic feasible solutions you choose one of the corner points, in most of the problems where you have one slack variable associated with each of the constraints the easiest way to obtain an an initial basic feasible solution is to set the original variables to zero In this particular case the original variables where x 1 and x 2, so set x 1 and x 2 is equal to 0 which means we have essentially starting from the origin which was point O. So, the initial basic feasible solution is is obtain in most cases by setting the original variables x 1, x 2 etcetera x n, you had the original variables x x 1 to x n to be 0. So, you are putting all the original decision variables n minus m variables to 0, so in this example we set x 1 equal to 0 and x 2 equal to 0 These variables which have been set to 0 will be non-basic variables and we obtain the basic variables as x 3 and x 4. So, by setting x 1 equal to 0 x 2 is equal to 0 which become, in fact the non-basic variables we write the basis as x 3 and x 4. So, x 3 and x 4 are the variables in the basis this is called as the basis, which constitutes a vector of basic variable then we use the constraints and solve for x 3 and x 4. So, we obtain solutions for the basic variables x 3 and x 4 by x setting 1 and x 2 to 0 So, we obtain x 3 is equal to 60 and x 4 is equal to 40, so this is the solution that we will get and this corresponds to point o on the graph so x 3 is equal to 60 x 4 is equal to 40 corresponds to point o on the graph and because we had x 1 equal to 0 x 2 is equal to 0 your Z value will be 0. Z is this x 1 is 0, x 2 is 0, x 3 is 60, x 4 is 40, but their coefficients are 0 therefore, Z value is 0 we are starting with the origin o here which is the initial basic feasible solution ok Now, so the initial basic feasible solution is obtain by setting the original variable x 1 and x 2 to 0, that is how that is how we obtain the initial basic feasible solution Starting with this initial basic feasible solution we should move to the next basic feasible solution, how we do, that we need to look at this basis. Now, this basis has two variables which is m number of variables out of these m number of variables in the next iteration or the next step exactly one of these either x 3 or x 4 goes out and exactly one of these x 1 and x 2 which are currently non-basic variables comes in. So, there are two decisions that you need to make, one is which among these has to go out, and which among these x 1 and x 2 has two come in to form a new basis Let us see how we do that, so we have to generate another basic feasible solution from the initial basic feasible solution, such that there is an improvement in the value of Z. So, the way we do is you have in the current step; you have a basis or a set of basic feasible, basic values, basic variables that are in this particular case x 3 and x 4. So, 1 currently non-basic variable which is either x 1 or x 2 must be selected to enter the current basis and one currently basic variable should make way for this entering variables So, we have to identify which among the currently non-basic variables enter the basis and which among the currently basic variables exits the basis, departures the basis. Now this

is what we do in this case, how we decide which among x 1 and x 2 should enter the basis You look at the objective function your objective function is 6 x 1 plus 8 x 2 plus 0 x 3 plus 0 x 4 and x 1 and x 2 are currently a 0 level, because they are non-basic variables. Now, we want to bring in either x 1 or x 2 and the question you are asking is whether I should bring in x 1 or I should bring in x 2 such that the improvement in the value of Z will be the fastest Look at the coefficients you have a coefficient of 6 for x 1 and a coefficient of 8 for x 2 and your objective is to increase the Z value the fastest. So, which one which variable would you brings in if you bring in x 1 then the rate at which it will increase is 6 times the value of x 1, where as if you bring in x 2 the rate at which it will increase is 8 times the value of x 2 And therefore, the rate at which Z increases will be higher if you bring in x 2 compare to the rate at which it increases if you bring in x 1 and therefore, you will bring in x 2 here in to the basis. So, because we are looking at the maximization of objective function we must look for that particular variable now between x 1 and x 2 which will increase the objective function values the fastest So, in this particular case, because x 2 has a higher coefficient, higher positive coefficient compare to the coefficient of x 1 you bring in x 2 Then we made a decision that between x 1 and x 2, we x 2 will come in to basis, now x 3 and x 4 where the basis, now out of x 3 and x 4 1 has to go either x 3 has to go or x 4 has to go, to make way for this entering variable which is the x 2, which among x 3 which between x 3 and x 4 should go out. Let us see what happen, you would like to increase the value of x 2 which is the entering variable as much as possible, so that your Z value keeps on increasing the Z value increases As you start increasing x 2 one of the other two variables which are in the basis now, that is x 3 and x 4 they will start decreasing, because of the nature of the constraint you start increasing x 2 one of the other variables will start decreasing in fact, both of them start decreasing. You just look at these the constraint was 5 x 1 plus 10 x 2 plus x 3 is equal to 60, 4 x 1 plus 4 x 2 plus x 4 is equal to 40, x 3 and x 4 are the basic variables x 1 is still 0 and you want to increase x 2 now You already made a decision that x 2 is coming in to the basis therefore, you would like to increase x 2, as you start increasing x 2, because of this constraint x 3 starts coming down as you starts increasing x 2, because of these constraint x 4 starts coming down One of these which is either x 3 or x 4 start will hit 0 earlier than the other variable, let us see which one hits 0 first, so from this I can write x 3 is equal to 60 minus 10 x 2 here, x 1 is still 0 remember and from this I will write x 4 is equal to 40 minus 4 x 2 So, x 3 will be 0 when x 2 is equal to 6, because of this and x 4 will be 0 when x 2 is 10 what does it mean, it means that as you start increasing x 2 from its current value of 0, x 2 was a non-basic variable you are just bringing it in to the basis. So, from its current value of 0 you start increasing x 2 as soon as x 2 reaches the value of 6, x 3 becomes 0 and if you further increase, then x 2 becomes x 4 becomes 0 when x 2 reaches 10 So, x 3 becomes 0 the moment x 2 reaches 6 and therefore, no further increase in x 2 will be possible, because x 3 one of the variables reach 0 already any further increase in x x 2 beyond 6 will make x 3 negative and therefore, it becomes in feasible. So, the maximum value in this particular iteration that you can

increase for x 2 will be 6 and that is decided by x 3 becoming 0 So, you look at that particular variable in the current basis which becomes 0 as the entering variable increases, which becomes 0 first and that is the variable that has to make way for the entering variable. So, between x 3 and x 4 we realize now, that as you start increasing the value of x 2, x 3 hits 0 first, before x 4 hits and therefore, x 3 has to depart and make way for the entering variable x 2, so this is how we decide which is the entering variable, which is the departing variable from the basis Let me just summarize what we did, first we start with the initial basic feasible solution and in the initial basic feasible solution Normally we start with the origin which is original decision variable x 1 x 2 etc x n set it to 0 in this particular example we set x 1 equal to 0 x 2 equal to 0. So, I starting with the origin that is the initial basic feasible solution and therefore, the basis will contain all the slack variables in this particular case the solution contain, the basis contain x 3 and x 4 as the basic vari variables. When we are moving to the next iteration or the next step we have to identify which among the currently non-basic variables can be brought into the basis, such that the objective function value for maximization increases the fastest And therefore, we look at the coefficient of the currently non-basic variables in the objective function, in this particular case you had 6 x 1 plus 8 x 2 as the objective function value and therefore, by bringing in x 2 in to the basis you will able to increase the Z value faster than you would have done if you have brought the a variable x 1 And therefore, you identify x 2 as the entering variable and which among the remaining two variable x 3 and x 4 has to depart from the basis, that you decide basis from which of these variables hits 0 first, as you start increasing the entering variable x 2, value of the entering variable x 2 and in this particular case we saw that x 3 hits 0 first and therefore, x 3 goes out and x 2 comes in. We reformulate the basis now by taking out x 3 and write the basis at x 2 and x 4 So, earlier we had x 3 and x 4 x 3 goes out x 2 comes in and therefore, the new basis is x 2 and x 4, this is the basis on which we move from one iteration to other iteration, one step to another step the simplex method then start starting with this basis Now, x 2 and x 4 we are obtaining solutions for x 2 and x 4 etc. I would argue to go to canonical form and the Gauss Jordon elimination method of simultaneous solutions etcetera So, we use those methods and from one iteration to another iteration we keeps solving from the new sets of variables in this particular case we solve for x 2 and x 4 in a iterative manner Each time converting the problem in to writing the problem in the canonical form using the Gauss Jordon elimination method and then keep solving the problem for the new basic variables this is done through a table or method a very elegant method and a very simple way of moving from one iteration to other iteration this is the simplex method So, we will demonstrate this with a simple example, but the basic principle remains the same the principle is that we start with the initial basic feasible solution and then keep on improving this solution by moving from one initial basic feasible solution to the next basic feasible solution. I repeat by moving from one basic feasible solution to the next feasible solution and in the graphical form any corner of the feasible region forms a basic solution So, we are moving from one corner to another corner to another corner etcetera, until we hit the optimal value. Now this is done through a table or form we will look at how we formulate simplex table or simplex table utilities called for each of the iterations

So, let us look at this problem now, maximizes Z is equal to 3 x 1 plus 5 x 2 this is the problem that I solved in the previous lecture using the graphical method. So, the same problem will consider and use the algebraic method to solve for this problem; you have Z is equal to 3 x 1 plus 5 x 2 subject to x 1 is less than or equal to 4, 2 x 2 less than or equal to 12 and 3 x 1 plus 2 x 2 less than or equal 18 and these are the non negativity conditions for x 1 and x 2 The first step is to convert the LP in to a standard form, and the standard form we will be using in this lecture is that the objective function we will have maximization form. So, write the objective function always as a maximization object objective function and all the constraints we write as equality constraints. So, we write the objective function which was Z is equal to 3 x 1 plus 5 x 2, so we write maximize is equal to 3 x 1 plus 5 x 2 convert the constraints in to equality form, so x 1 is less than or equal to 4 So, I write as x 1 plus x 3 equal to 4 with x 3 as a slack variable, 2 x 2 is less than or equal to 12, I write it as 2 x 2 plus x 4 equal to 12 with x 4 as a slack variable, 3 x 1 plus 2 x 2 is less than or equal to 18 I write it as 3 x 1 plus 2 x 2 plus x 5 equal to 18 with x 5 as a slack variable So, there are five variables, look at this x 1, x 2, x 3, x 4, x 5 there are five number of variables, there are three constraint or three equations. So, m is equal to 3 and n is equal to 5 So, the non-basic variable will be n minus m which is 5 minus 3 which is 2. So, you will have two non-basic variables three basic variables using these three equations you will solve for 3 variables. So, we need to start with an initial basic feasible solution as I mention when you have typically one slack variable associated with each of the constraint you set the initial variables, the original variables x 1 and x 2 to be 0. So, we start the initial basic, we obtain the initial basic feasible solution in most of the cases by setting the original variables to 0. So, x 1 is equal to 0 and x 2 is equal to 0 we set it,which means x 1 and x 2 are the non- basic variables which are set to 0 and then solve for x 3, x 4 and x 5 This is done through a tabular form will understand how we got it. So, as I said x 1 and x 2 are non-basic variables whose values are set to 0 and x 3, x 4 and x 5 are basic variables whose solution is sought. So, my initial basis will consist x 3, x 4 and x 5 that forms a initial basis and this will also lead to a basic feasible solution, because we are at the origin of the feasible region by setting x 1 equal to 0 and x 2 equal to 0 Now, this we do in tabular form, let us understand carefully how we do this, the objective function which was Z is equal to 3 x 1 plus 5 x 2 plus 0 x 3 plus 0 x 4 plus 0 x 5 we also treat it as one equation with Z minus 3 x 1 minus 5 x 2 minus 0 x 3 minus 0 x 4 minus 0 x 5 equal to 0. So, we write the objective function Z also as another equation So, we write it as Z minus 3 x 1 minus 5 x 2 minus 0 x 3 minus 0 x 4 minus 0 x 5 equal to 0 and you have this constraint x 1 plus x 3 equal to 4, 2 x 2 plus x 4 equal to 12, 3 x 1 plus 2 x 2 plus x 5 is equal to 18, so these sets of four equations, now the original 3 and the objective function and the equation corresponding to the objective function. These four equations we write it in a tabular form we use this convention from text book to text

book from, instructor to instructor these forms may be different, but we will strict to 1 form as for as this course is concern So, we write a column basis which consists of x 3, x 4, x 5 of basic variables and Z is always in the basis this is Z corresponding to the Z equation this is the objective function equation. So, we write Z and the other basic variables x 3 x 4 and x 5, and then we have how many rows four rows one corresponding to Z and three corresponding to each of the equations. So, we write row for Z us Nomenclate as 0 and row 0 and row one corresponding to this, row 2 corresponding to this, and row 3 corresponding to this, so you have row 0, 1, 2 and 3 Then we write the coefficients of Z in each of these rows. So, this column consists of coefficients of Z in each of this row. In the row 0 the coefficient of Z is 1 we write 1 here in all other rows there is no Z and therefore, in all other rows row number 1, row number 2 and row number 3 correspond to this equation, this equation, this equation respectively the coefficient of Z is 0 therefore, we write 0, 0, 0 So, this column we simply wrote the coefficients of Z in each of these rows 1, 0, 0, 0, then we write all the variables x 1, x 2, x 3, x 4, x 5, so these are variables of the problem, each of these columns we consist of the coefficients in that particular row of this particular variable. So, row 0 which is this row 0 has the coefficient of minus 3 for x 1 so we write minus 3, row one which is this row for clarity as well write, so this is row 1 and this row 2 and this is row 3 and this is row 0 So, x 1 has a coefficient of minus 3 in row 0 we write this, x 1 has the coefficient of 1 in row 1, so this coefficient is 1 I write that, x 1 has the coefficient of 1 in row 1 x 1 has the coefficient of 0 in row 3 so I write 3. So, I write 3 similarly you look at x 2 minus 5 0 plus 2 and plus 2. So, that is how you write x 2 the coefficient of x 2 similarly x 3 you look at x 3 has the coefficient of 0 then 1, 0 and 0 similarly, x 4 has the coefficient of 0 and in row 1 it has 0 and in row 2 it has 1 and 0 x 5 has the coefficient of 0, 0, 0 and 1 So, this is how you write the coefficients of each of the variables, and then you create another column which consists of the right hand side b I, that is for the each of the rows what the right hand side values are So, you had the row 0 the b i is 0 you just fill the right hand side values, for row 1 you had 4, for row 2 you had 12, for row 3 you have 18. So, b i correspond to the right hand side values, so this how you formulate the first of the simplex algorithm, simplex method So, in the first all you have done is reproduce the original problem with x 1 set to 0 and x 2 set to 0 in this particular example. And therefore, the original basis will consists of x 3, x 4 and x 5 and Z will be always in the basis, so we write the first column of basis as Z x 3, x 4 and x 5 then we use the row numbers as 0 corresponding to the Z row, 1 corresponding to the first constraint, 2 corresponding to the 2 constraint and 3 corresponding to the the third constraint and so on. Then we write the coefficients of each of the variables including the Z in each of these rows So, that constitutes these columns then the

b i column will consists of the right hand side values. So, you have 0, 4, 12, and 18 this will consist of any simplex table you any equation we provide us the solution, how? What is the solution, this is the variable and this is the value Z is equal to 0 x 3 is equal to 4, x 4 is equal to 12, x 5 is equal to 18 is the solution. And x 1 is equal to 0, and x 2 is equal to 0, because they are non basic variables remember any variable that are not there on the basis is the non-basic variables and therefore, its value will be 0 So, what is the solution that you are obtaining here from this table you obtain Z is equal to 0, x 3 is equal to 4, x 4 is equal to 12, and x 5 is equal to 18, and off course x 1 is equal to 0 and x 2 is equal to 0. This is how you read the solution for in any given, so we started with an initial basic feasible solution namely x 1 equal to 0, x 2 is equal to 0 and we obtain x 3 is equal to 4, x 4 is equal to 12, and x 5 is equal to 18 Now, the question that we have to ask at each iteration is is this optimal solution. So, the first question we need to ask is is this optimal solution, because we need to terminate if we are sure that these are this optimal solution we need to terminate. So, at every iteration we we resolve first whether the current solution is in fact the optimal solution If it is a optimal solution you terminate the computation, if it is non optimal solution then we need to ask for which among the currently in non-basic variables should enter the basis that is the first question, the next question is which among the currently basic variables should make way, should depart and make way for the entering variable So, we ask three questions typically is the current solution the optimal solution, how do we resolve that question, you look at these questions now, you have Z minus 3 x 1 minus 5 x 2 etc equal to 0 as long as in the 0 th row which is a Z row you have at least 1 coefficient which is negative the solution is not optimal, why because, if you have a negative coefficient it means that bringing that particular value you will able to increase the Z value further, the current value Z is 0 by bringing in x 1 or x 2 which have negative values you will able to increase the Z value further, because Z will be Z equal to 3 x 1 plus 5 x 2 and therefore, you can increase the Z value further So, the answer to the question whether the particular this particular solution is optimal, lies in the coefficients of Z in the 0 th row. If you have at least one variable with a negative coefficient it means that the solution is not optimal, because the solution can be further improved I repeat the answer to the question whether the current solution is optimal we lies in the coefficients of Z in the 0 th row If you have at least one coefficient which is negative in the particular format of solution, if you have at least one coefficient which is negative; that means, that the solution can be further improved and therefore, the solution is not optimal and then we ask the question this solution is not optimal and we have x 1 and x 2 are non basic variables x 3, x 4 and x 5 are the basic variables So, exactly one of these either x 1 or x 2 has to come in to the basis, exactly one of these x 3, x 4 or x 5 has to leave the basis So, the next question that we ask is which among the currently non-basic variables x 1 and x 2 should enter the basis, which is the entering variable is the question And we identifying the entering variable, then we ask the question which among the currently basic variable should depart to make way for the entering variable, so that we can write the new basis So, this is what we do when we go to the next iteration, we will continue this example in

the next lecture. So, essentially today in today lecture, we we are formulating the motivation, for we we initially started with the motivation for the simplex problem. And in the process introduced what are called as the basic solution and then we also identify the basic variables and the non-basic variables Remember you have n number of variables and m number of equations once you convert all, the in in equality constraints you have m number of equations and n number of variables including your slack variables, slack and surplus variables as may be So, you set m minus n variables to 0 and these variables which are force to take a vary of value of 0, which are being set prior to take a value of 0 are called as the non-basic variables and you solve for the remaining m number of variables and these variables for which we are seeking a solution in terms of remaining m number of variables which have been set to 0 are called as the basic variables So, the m number of variables which you are solving for the equations are called as the basic variables and the vector or the set of basic variables is called as the basis The basic variables which are also feasible are called as the basic feasible solution and in the simplex algorithm We start with an initial basic feasible solution and then move to a next basic feasible solution; when we are moving from one basic feasible solution to next basic feasible solution One, exactly one among the currently basic variables will enter the basis and one, exactly one currently basic variables will depart and way for the entering and this we do in a iterative manner in a tabular form and I have just shown how to write the first tableau, first tableau simply reproducing the problem; we treat as the max as the objective function also as one of the rows or one of the equations by writing Z equal to Let us say that 3 x 1 plus 5 x 2 as a case in our example, we write it as Z minus 3 x 1 minus 5 x 2 minus all other than the slack variables equal to 0. So, we also treat it as one of the rows along with the other equations we formulate for the initial tableau. So, I have just towards the end of the lecture I have just indicated how we write the first tableau, first simplex tableau starting with the first simplex tableau, we move on to the next simplex tableau if we are sure that, this is not the optimal solution And we have just seen that as long as have at least one negative coefficients in the Z row in the 0 th row it means that the solution is not optimal and therefore, the solution can be further improve. We will continue this discussion in the next class, thank you for your attention