Today, we consider the decomposition algorithm and we explain this decomposition algorithm
using this example.
This problem is the linear programming problem, maximization objective with four variables
and six constraints and all Xj greater than or equal to 0. We can solve this using any
of the techniques of linear programming that we have learnt till now, but we are going
to introduce a newer version of simplex or a new technique which is called the decomposition
of algorithm which is going to be used to solve this problem.
Let us take a closer look at this set of constraints. There are six constraints, but we observe
that the first two constraints involve only the first two variables. The next two constraints
involve the next two variables, X3 and X4, and these two constraints have all the variables.
One of the things we can do is that, if we relax the problem which means we remove some
of the constraints by relaxing the problem. If we relax these two constraints and look
at only the other four, though we realize that this problem can be split into two linear
programming problems: one of which will be maximize 6X1 plus 5X2 subject to these two
constraints; The other will be maximize 3X3 plus 4X4, subject to these two constraints,
by removal of certain number of constraints from the problem, or by relaxing the problem
by removing the constraints. The given problem can be decomposed into more
than one linear programming problem, more than one independent linear programming problem.
So, we exploit that idea. The first thing is that, if we remove these two and solve
the resultant linear programming problem and if it turns out that the optimum solution
to the resultant problem satisfies this, then it is also optimum to the original problem.
More often that will not happen. We will also have to consider these two constraints.
The method that we will adopt is first, remove these two constraints and treat them as two
independent problems and then ensure that the solution obtained to those independent
problems, also in some way or the other meet these constraints so that the optimum solution
can be obtained. Now, before we even proceed further, let us
see, why we are doing this? If we were to solve this as a linear programming
problem, every iteration of the simplex method, would involve all the six constraints, so
it would involve six basic variables and every iteration is to invert a 6 into 6 matrix.
But, if on the other hand, we remove these two and then decompose the problem into two
problems, each having two constraints then in each iteration in principle we are inverting
a 2 into 2 matrix. We are actually inverting two 2 into 2 matrices. We also have to have
some relationship between these constraints and the other one; therefore, there is one
more binding constraint that is added. Effectively, we will be looking at 2 plus
2 plus 3, original problem has 6, but then we will be looking at 2 plus 2 plus 3. We
also understand that inverting a 6 into 6 matrix is a little more computationally intensive
compared to inverting a 2 into 2, another 2 into 2 and another 3 into 3. So, computing
time required to solve this problem becomes lesser, particularly when we write computer
programs and solve. These two constraints which are taken out
are called the master problem constraints, so these are called master problem constrains.
These two are the sub problem constraints which we call as I and II. So, this is a sub
problem constraint, this is another sub problem constraint and so on. Now, the two sub problems
are maximizing 6X1 plus 5X2, subject to this and maximize 3X3 plus 4X4 subject to this.
Actually in every iteration we need to solve this as well as this. Instead, what we will
do to make our computation simpler, we will simply note down the corner points associated
with this and the corner point associated with this so that depending on the objective
function which we will see we will modify slightly depending on the objective function
by a simple substitution of the corner points. We can get the optimum solution quickly, because
we are illustrating this on the blackboard, in a classroom environment.
Ordinarily, every time the sub problem is solved, it should have been solved by the
simplex algorithm. Let us first identify the corner points associated with this and the
corner point associated with this because it is a 2 into 2 problem. We can actually
solve it by the graphical method and try to find out the corner points.
So, the first set of corner points. To do that, we have X1 plus X2, so this is X1 plus
X2 equal to 5. 3X1 plus 2X2 equal to 12 will look like this. This is the corner point (4,0),
this is the corner point (0,0), this is the corner point (0,5) and this will be the corner
point (2,3). These are the four corner points associated with this.
So, we will simply write the four corner points for our reference here; (0,0), (4,0), (0,5)
and (2,3) are the four corner points associated with this. Now, let us find out the corner
point associated with the second one.
This will be the X3 axis, this will be X4 axis, X3 plus 2X4 less than or equal to 8.
2X3 plus X4 less than or equal
to 10. This will be the point (5,0), this is the point (0,0), this is the point (0,4),
this will be the point (4,2).
The four corner point associated with this are: (0,0), (5,0), (0,4) and (4,2), so, these
are the corner points associated with. Now, let us understand one more principle before
we apply the decomposition algorithm.
Now, suppose we have a feasible region like this for a given problem, let us assume that
this is the feasible region. Now, if we add a constraint into this problem, the first
thing that can happen is the feasible region can reduce or the feasible region will remain
the same. These two things can happen. Let us assume that the feasible region reduces,
so let us say, the feasible region comes somewhere here, because of the additional constraint.
If this were the optimum solution before the introduction of the constraint and because
of the introduction of the constraint this optimum solution becomes infeasible. Once
again, it has to be in one of the corner points, now the new optimum solution has to be in
one of these corner points, in these 5 corner points now that we have.
Now, if this were the optimum solution, then this was not a corner point in the first case,
when the new constraint was not added, because the corner point was here. Now this point,
if it is the optimum solution can always be represented as a convex combination of this
point as well as this point because of the convexity property of the feasible region
to a linear programming problem. Any point on the feasible region can always be represented
as a convex combination of one or more corner points. If we expand it to higher dimension
then it becomes convex combination of one or more corner points.
For example, this point can always be represented as lambda1 into this plus lambda2 into this
where lambda1 plus lambda2 is equal to 1. Similarly, any point inside, can also be represented
as a convex combination of the given corner points. As we add more and more constraints
in the feasible region can reduce and the final optimum solution can even be a point
which is inside this need not be on the boundary. Since, any point inside the region can be
represented as a convex combination of corner points, it is enough to look at those corner
points and try to identify which of the corner points are finally going to be part of that
combination, which will eventually give the optimum solution.
What we can do is let us say, we kind of remove this; we get this feasible region, whose corner
points are known here. By the addition of these two, the optimum solution is going to
come into some point inside the feasible region, which is bounded by these corner points. But
please note that these corner points are given as X1, X2, X3 and X4, even though, the solution
to this each point has its own X1, X2, X3. X4. Fact is by the addition of these two,
if the optimum shifts and comes to a point inside the region, it still can be represented
as a combination of these corner points that we are going to have. That is another idea
we will use in the decomposition algorithm. Now, Let us look some little bit of theory
with respect to the decomposition and then we proceed to solve this problem.
Let us assume that the given problem is actually a minimization problem, minimize CX, our example
is maximization; we will see later how we modify this. But right now let us look at
a minimization problem which is of the form minimize CX subject to AX equal to b and X is an element of X. What do we mean
by that?
What we mean by this is if we take this example, this is the maximization problem, but this
can be written as a minimization problem by simply saying minimize minus 6X1 minus 5X2
minus 3X3 minus 4X4.
I have not even written X greater than or equal to 0, I also have to explain, what is
this x and what is this X. So, we could use, let us call this as some small x minimise
Cx, Ax equal to b, x belongs to X, let us use this notation that way. Now, when we apply
this to this the minimize Cx is intact, because that is the same as this, minimize minus 6X1
minus 5X2 minus 3X3 minus 4X4. Now, Ax equal to b or actually the master constraints so
these two are the ones that are associated with this Ax equal to b.
Now, x belongs to X, it simply means that this X represents the set of corner points
of these two. In some sense x belongs to X, comes out of this. If we consider this problem,
minimize Cx, subject to Ax equal to b, x belongs to X, this is the master problem constraints.
These are the corner points of the sub problems. Now, we have also said that, every point is
going to be represented as a convex combination of the corner points. What we are going to
do is this x will be written as some lambdaj Xj, where Xj are these corner points. When
we write this the problem will now reduce to minimize sigma Cj, lambdaj, Xj subject
to A lambdaj Xj less than or equal to b, sigma lambdaj is equal to 1, because it is represented
as a convex combination of the corner points.
For example here, when we said that this can be written as lambda1X1 plus lambda2X2, where
X1 and X2 are corner points, lambda1 plus lambda2 equal to 1. This can also be written
as lambda1X1 plus lambda2X2 plus lambda3X3, lambda1 plus lambda2 plus lambda3 equal to
1. When we start represent it, introduce the lambda and start representing it as the combination
of the corner points, we need the linking constraint which is sigma lambdaj equal to
1.
Since every point inside this region also has to satisfy the master constraints so the
point itself is lambdaj Xj, so it will satisfy the constraint sigma A lambdaj Xj less than
or equal to b or equal to b depending on how the problem is defined. When we say here,
it is equal to b, it means the inequalities have been converted to equations.
Here, we simply retain the inequalities as it is, we may say plus a slack variable equal
to b or plus a surplus variable if it were greater than or equal to constraint; Therefore,
the problem reduces to something like this. Now, for this problem, we are actually trying
to solve the only difference being all these Xjs are corner points, which are given here.
Any point X, inside this region, which actually satisfies this set of constraints, optimizes
this objective and has this lambda. Now, this is the solution to the problem.
The problem now becomes one of not solving for the Xjs, but solving for the lambdas.
The lambdas now become decision variables, because the Xjs are known corner points, these
are the corner points. So, the lambda has become the decision variables for this. Now,
this one I have written in a certain form, we may put a summation here in which case
we can put sigma aij lambdaj Xj is equal to bi. We can either write it as individual constraints
or keep the whole thing as the vector. In principle, what I am trying to explain
here is that these Xjs are the corner points, so at any point inside, which will be the
solution, is now represented as sigma lambdajXj and therefore this problem gets, rewritten
in this format. I have also explained this equation versus inequality.
When I write an equation here, I assume that the inequalities have been already converted
to an equation, where the addition of suitable slack variables or surplus variables. When
I write an inequality here, I assume that we are yet to add, the slack variable or the
surplus variable. If we want to be consistent with these two, we can even say that, Xj equal
to bi, which means, that we have added the slack variables and surplus variables associated
with this.
Now, as I said the focus now shifts on finding out the lambdaj which become the variables
or which are essentially the weights that are associated with each corner point.
Now, we can start solving this problem by doing a few things, if we are able to get
a feasible solution to the problem, for example, this is the convenient example, where all
these constraints are less than or equal to constraints. Therefore the point 0, 0, 0,
0 is basic feasible for this. Particularly, when we leave out both these, we have four
constraints on the point 0, 0, 0, 0 is basic feasible. We could start with lambda1 equal
to 0, 0, 0, 0, which is a corner point. So, we can start with lambda1 for this. Now, these
two are the master problem constraints and these two constraints are also less than or
equal to constraints. The corresponding slack variables can be added here. We can add an
S1 here and we can add an S2 here, so S1 and S2 automatically qualify to be basic variables.
So, we can start solving this problem, with the basis, which comprises of S1, S2 and lambda1.
The first basis we can have for this is as follows.
It is given by S1, S2, lambda1 still have S1, S2, lambda1 and right hand side we will
have the identity matrix 1 0 0, 0 1 0, 0 0 1, with values bi, bi are 7 and 17. The right
hand side values are 7 and 17 and for this constraint, the right hand side value is 1,
so it is 1.
We have also defined lambda1, this is our first starting point, it will be 0, 0, 0,
0, which comes out of these two. Now, because we have a basic feasible solution with 0,
0, 0, 0, we can start this, otherwise we may have to introduce an artificial variable for
this and then begin with the artificial variable. Right now, we are going to solve this numerical
example and the point 0, 0, 0, 0 is basic feasible. We simply start with the lambda1
which is 0, 0, 0, 0, which takes weight equal to 1. The current basic feasible solution
to the problem is actually the solution 0, 0, 0, 0.
We have to find out Cj minus Zj or Zj minus Cj, which will be 0 0 0 and 0 here. Now, this
is the starting basis as far as this problem is concerned, which means this basic feasible
solution has one corner point which is the point 0, 0, 0, 0. Right now, this has a solution
with Z equal to 0, so if we substitute 0, 0, 0, 0 here, we will get the solution Z equal
to 0. We need to verify whether this solution is
optimum. Now in order to verify whether this solution is optimum we need to find out whether
there is an entering variable. We have not written the entire table, we have written
only that part of the simplex table which contains the basis matrix b, the right hand
side and the Zj minus Cj under b which can always give us the dual variables. We know
by now, that Zj minus Cj the way the notation that we have used, particularly in the earlier
course on the fundamentals of O.R, where we covered linear programming extensively. We
also mentioned that if we use Zj minus Cj and if we do not have artificial variables,
exactly under the identity matrix, the beginning identity matrix we can always read the solution
to the dual of this problem. This helps us in reading the solution of the dual directly.
Now, several corner points are possible, in fact, right here, there are four here and
there are four here, sixteen corner points are possible. Now, we have to check for all
the sixteen Cj minus Zjs. If they cannot enter, then we have reached the optimal solution.
So, one way is to generate all the sixteen and then try and find out the Cj minuss Zj
associated with all the sixteen. For example, we had a much larger problem,
it was decomposed into three sub problems and let us say, there were five corner points
in each, then we are looking at 5 into 5 into 5, 125 variables. We do not want to store
all the corner points and then verify, whether these corner points can enter. Instead, what
we do is we try and follow the column generation idea that we saw in the cutting stock problem.
Then check that if there is a corner point that can enter the basis, if there is a lambda
that can enter the basis, because each corner point is associated with the lambda. If there
is a lambda that can enter the basis, we now generate that corner point and say that this
corner point can enter the basis with the certain lambda. We follow the column generation
idea and we do not explicitly store all the combinations of the corner points.
How do we generate, an entering corner point or entering lambda. In order to enter, we
have we need to make sure that Zj minus Cj, so, it is a minimization problem.
Zj minus Cj, since it is a minimization problem, a positive Zj minus Cj will enter the basis.
We have seen for maximization problem, a Positive Cj minus Zj will enter. For a minimization
problem, a positive Zj minus Cj will enter. Please remember, we have defined this problem
as the minimization problem. It is only incidental, our numerical illustration is a maximization,
but this problem is a minimization problem where a positive Zj minus Cj will enter. If
there is a j, if there is a corner point, whose Zj minus Cj is greater than 0, then
such a j can enter. Now, what is this Zj. Zj equal to yPj, Zj is always equal to CB
b inverse Pj, so that will be equal to yPj minus Cj is greater than 0 where y is the
associated dual variable.
Now, in this problem, if we look at this primal, here we have as many constraints as the master
constraints. In our illustration two constraints, this will give rise to two dual variables.
This is always a single constraint, so this will give rise to one dual variable. We will
now, instead of calling the dual variable by y which is the customary notation, we would
now introduce dual variables w and alpha where since there are two constraints here we will
have w1 and w2 and there is one constraint here we will have alpha.
What happens here is this y becomes (w, alpha). What is Pj? Pj is an entering column yPj,
CB b inverse Pj, so yPj is entering column.
The entering column right now, any entering column here, will be of the form, aXj, 1 because
the lambdaj is the variable. So you need to take this variable outside, so the entering
column will be of the type aXj, 1.
You will have w alpha into AXj, 1, minus Cj should be greater than 0 and this is Cj now
becomes CjXj from here, because lambdaj is the variable. So, Cj becomes Cj Xj greater
than 0. Let me explain this again. In order for a new variable to enter the basis, because
it is minimization problem, in general, Zj minus Cj should be greater than 0. In general
Zj is written as yPj minus Cj greater than equal to 0, where y is the dual variable,
Pj is the entering column and Cj is the objective function coefficient of the entering variable,
now, all these are general equations. We are adapting this to the problem on hand.
Now, because our problem is structured specifically this way there are as many constraints here
as in the master problem where we have to introduce dual variable w, this will be w1,
w2, w is the vector, this is always a single constraint, so introduce an alpha. So y becomes
w alpha. If there is an entering lambdaj, lambdaj is the variable, Xj is not, so if
there is an entering lambdaj, then the coefficient will be aXj 1, so we will get aXj 1.
Remember that, this is in matrix, this is the single thing so there will be two ws.
There will be two values coming here, there is 1 alpha, there is just a 1, minus Cj is
the objective function coefficient of the entering variable. The entering lambda will
have an objective function coefficient of CXj or CjXj greater than or equal to 0.
Now, this can be expanded to wA minus C into Xj plus alpha greater than 0. We also know
that this Xj is the corner point corresponding to this and this, because every X is written
as lambdajXj, where Xj is the corner point. Therefore, because Xj is the corner point,
Xj has to satisfy this and this, set of constraints. What we want to do now is if there is an Xj,
which satisfies this and this and has a value wA minus CXj plus alpha greater than 0, then
such a corner point can enter the basis with an associated lambdaj.
We do the usual thing of this being strictly greater than, we say that we now want to maximize
wA minus C into Xj, subject to Xj belongs to some X, where this X is the set of corner
points. Then, we find out such an Xj and then enter the corresponding lambdaj into the solution.
For a given objective function this is equivalent to solving the two sub problems. With this,
bit of theory, let us go back and see whether there is an entering corner point whose lambda
has to enter the basis.
To do that, we go back and now check. We want to find out wA minus C into Xj plus alpha.
So, let us write this wA minus c�. Now, from this solution. We also said that this
being a simplex table and this being the identity matrix, there are no artificial variables
and we are computing Zj minus Cj, Zj minusminus Cj will automatically give us the values of
the dual. These two values will be w1 and w2, because they correspond to S1 and S2.
S1 and S2 were obtained from this and w is the dual variable for this, so w1 and w2 are
seen here, alpha is seen here, alpha corresponds to this. Alpha corresponds to this lambda1.
Alpha is seen here so from this right now, the ws are all 0.
We want to maximize this right now, the ws are all 0, so, wA minus C Xj, they are all
0, plus alpha. Right now, we will have maximize minus CXj. Alpha is also 0. Now, remember
the original problem is minimize Cx, this problem has to be written as minimize minus
6 minus 5 minus 3 minus 4. The C vector is minus 6 minus 5 so this is C. Because the
given maximization problem has to be written as a minimization problem, because the theory
this is derived for a minimization problem, so the C vector becomes minus 6 minus 5 minus
3 minus 4. Maximize minus CXj will now become maximize
6X1 plus 5X2 plus 3X3 plus 4X4, subject to X belonging to this. So, this is decomposed
into two problems. The first problem being maximized 6X1 plus 5X2, subject to this constraint
and the second one is to maximise 3X3 plus 4X4, subject to this constraint. So, we now
have to solve two linear programming problems. One is a 2 into 2 problem, the other is a
2 into 2 problem, to get the solution to this, subject to the condition, that Xj belongs
to corner point. Because these two are linear programming problems and we know the corner
points of the feasible region. Ordinarily, this is not the best way to solve this; each
one has to be solved as an LP as we go through iterates. Because we are solving a much smaller
problem and each of the sub problems has only two constraints and it is a 2 into 2, we have
simply stored the corner points, just to make the ease of computation possible for us.
In practice when we are actually solving a very large LP, we will not a priori compute
all the corner points and keep it. At every stage, we will be solving a linear programming
problem within the decomposition. Let me again repeat, only to make the computation simple,
I have just written down all the corner points. Since we know all the corner points, we can
go back and find out what is the best value. So (0, 0) will give 0. (4, 0) will give 24.
(0, 5) will give 25 (2, 3) will give 27, 6 into 2 is 12 plus 5 into 3 is 15. This gives
the optimum solution (2, 3). Second one is 3X3 plus 4X4, so 3X3 is 15, here it is 16,
now 4 into 3 is 12, plus 2 into 4 is 8, is 20. So, (4, 2) is optimal, this is 27, this
is 20, so Z equal to 47. So value of Z is equal to 47 and the corner point (2, 3, 4,
2) enters the basis. So, the first corner point that will enter the basis is lambda2
which is (2, 3, 4, 2).
We now know the entering corner point which is 2, 3, 4, 2, but we have to find out the
leaving variable.
In order to find out the leaving variable, we need to find out Pbarj. So, Pbarj is equal
to b inverse Pj and this is always b inverse, so Pbarj equal to b inverse Pj. Right now,
b inverse is I, so Pbarj equal to Pj. What is Pj? Any entering Pj is AXj, 1. So, this
is Pj, this is equal to AXj 1. Now we have to compute AXj and 1.
AXj is equal to, A comes from the master problems, please note this is the master constraint;
this is the AXj equal to b. So A is 1 1 1 1, 2 1 1 3, 1 1 1 1, 2 1 1 3 into Xj is 2
3 4 2 so this gives us 2 plus 3 is 5 plus 4 is 9 plus 2 is 11, 4 plus 3 is 7 plus 4
is 11 plus 6 is 17. So AXj 1 is 11 17 1.
We have found out the entering column, which is Pbarj, so we just write the entering column
here. This is our lambda2, which is 11 17 and 1 with value equal to 47. The positive
Zj minus Cj will enter the basis, so this lambda1 with lambda2 with 11 17 and 1 enters
the basis. Now, we have to find out the leaving variable and to find the leaving variable,
we will compute a theta. Note that, theta is right hand side divided by the entering
column. So, it is 7 divided by 11, 17 divided by 17 and 1 divided by 1, so minimum theta
leaves the basis. Therefore this will leave the basis and this is your pivot element.
We need to perform one simplex iteration. So we will go back here, to continue with
the simplex iteration. Now, the variable S1 is replaced by the variable lambda2, so you
have lambda2 S2 and lambda 1 with Zj minus minus Cj. Now, divide every element of the
pivot by the pivot element, so we need 1 0 0 here, so divide by the pivot element, you
get 1 by 11 0 0, 7 by 11, 1. Now we need a 0 here, so this minus 17 times
1 will give me 0. So 0 minus 17 into 1 by 11, is minus 17 by 11 1 0. This minus 17 times
this, 17 into 7 is 119. So, 17 minus 119 by 11, 17 into 11 is 187.
17 minus 17 into 7 by 11, this is 187 minus 119 by 11 which is 68 by 11.
We get 68 by 11 here. This will become 0 and we need another 0 here, so, this minus this
will give us 0. So, minus 1 by 11 0 1, 1 minus 7 by 11 is 4 by 11 and a 0 here. We also know
that, we can do the same kind of row operation to try and get a new Zj minus Cj, what we
need is a 0 here. This minus 47 times 1 is 0, so this minus 47 times, is minus 47 by
11 0 0. This minus 47 times, so 47 into 7, is 329. We get minus 329 by 11. This is the
solution.
Now, what is this basic feasible solution tell us, right now from 0 0 0 0, this has
moved to a new point, which is given by lambda1 is equal to 4 by 11, lambda2 is equal to 7
by 11, which, the present point that we are looking at is 4 by 11 into (0, 0, 0, 0) plus
7 by 11 into lambda2, which is (2, 3, 4, 2). This is all 0, so the point is 14 by 11, 21
by 11, 28 by 11 and 14 by 11. This is the point we are right now looking at. What is
the value of the objective of a function? 6X1, 14 into 6 is 84, 5X2, 155 plus 84 is
189, 28 into 3 is another 84, so, 189 plus 4, is 193, 273 plus 56 is 329. So we get 329
by 11, which is the value of the objective function, right now.
From here we have moved on to one iteration and which means from the corner point (0,
0, 0, 0), we have now moved to a corner point 14 by 11, 21 by 11, 28 by 11, 14 by 11, if
we look at the entire problem. But we have not look at the entire problem at a time,
we have arrived this corner point in a slightly different way, by getting this as a convex
combination of two corner points (0, 0, 0, 0) and (2, 3, 4, 2), with weights 4 by 11
and 7 by 11.
When we reached here, we have actually generated an entering column by solving a sub problem.
The sub problem turned out to be solving two independent linear programming problems in
this case. We will not store all the corner points now. We need to check whether this
corner point is optimum, in order to do that, we need to check whether any other lambda
can enter the basis. For any lambda to enter the basis, we again need to find out maximize
wA minus cXj plus alpha. Subject to these two sets of corner points or subject to the
Xj satisfying this and this, both means the same. We now go back and try to solve these
two sub problems. From this, we know that w is minus 47 by 11, 0. So, w is minus 47
by 11.
Then minus 47 by 11, 0 into A is 1 1 1 1, 2 1 1 3, so we are first finding out wA, this
is (minus 47 by 11, minus 47 by 11, minus 47 by 11, minus 47 by 11), this is wA because
0 into 2 1 1 3 is 0. Now, wA minus C equal to minus 47 by 11, minus 47 by 11, minus 47
by 11, 47 by 11, minus c is (minus 6, minus 5, minus 3, minus 4) plus alpha and alpha
is right now at 0. We go back and simplify this. So, this is
6 minus 47 by 11, this is 19 by 11, 66 minus 47 is 19. Now this is 5 minus 47 by 11, which
is 8 by 11. This is 3 minus 47 by 11, which is minus 14 by 11 and 4 minus 47 by 11 is
minus 3 by 11. We now have to solve a problem which maximizes 19 by 11 X1 plus 8 by 11 X2
minus 14 by 11 X3 minus 3 by 11 X4, subject to these two constraints. The sub problem
that we generate now is decomposed into two linear programming problems, which again have
to be solved separately by using the simplex algorithm. But as explained earlier, since
these are all small sized problems, we have stored the corner points and by substituting
the corner points into this, we can find out the objective function value and the optimum
solution. When we look at 19X1 plus 8X2 and minus 14X3
and minus 3 11X4, it is fairly obvious that (0, 0) is an optimum solution to this. You
are maximizing minus 14 by 11 X3 minus 3 by 11 X4, which is minimizing that, therefore
(0 0) is optimum here. For this is concerned, we look at 19X1 plus 8X2 to begin with. This
would give us 0, this is 19 into 4 which is 76, this is 8 into 5 is 40, this is 19 into
2 is 38. So, 38 plus 24 is 62. The point (4, 0) is optimal here. This has 76 by 11, this
is 0, so with Z equal to 76 by 11 we had. So the point 4 0 0 0 enters the basis with
Z equal to 76 by 11. What we do now here, is we enter this point 4 0 0 0 into the basis,
but before we enter that, we have to find out Pbarj and then we need to enter.
Pbarj equal to B inverse Pj and in order to find out Pj we need to do AXj 1, so Pj will be, so first
we do AXj, so AXj is 1 1 1 1, 2 1 1 3 into 4 0 0 0. 1 into 4, plus 1 into 0, plus 1 into
0, plus 1 into 0, is 4. 2 into 4 is 8, so we get 4 8. Now, AXj 1 which is Pj is 4 8
1. Now Pbarj equal to B inverse Pj.
Pbarj is equal to B inverse Pj. This is B inverse, can always be read from this, 1 by
11 minus 17 by 11 minus 1 by 11, 0 1 0, 0 0 1 into 4 8 1. This would give us 4 by 11,
minus 68 by 11 plus 8 which is 20 by 11, 88 minus 68 is 20 by 11. This is minus 4 by 11
plus 4, which is 40 by 11. So, minus 4 by 11 plus 0 plus 1 equal to plus
7 by 11. You get plus 7 by 11. Now, the corner points 4 0 0 0, which will take value lambda3,
will enter the basis with the entering column 4 by 11, 20 by 11, 7 by 11 and with Zj minus
Cj value of 76 by 11. Let us enter that, so what we do now is the kind of keep this column
as some kind of dynamic column, because what we got from here is already available here,
I will erase this as well and I will notionally say ,that another lambda3 is entering the
basis here.
Lambda3 is entering the basis, with values 4 by 11, 20 by 11, 7 by 11 and with a positive
Zj minus Cj value of 76 by 11. Now, we know that variable lambda3 are corner point 4 0
0 0, enters the basis using a variable lambda3. We now need to the find out the leaving variable,
where the leaving variable could any of these three, which is found out by the minimum theta
role. Minimum theta is right hand side divided by the entering column, so 7 by 11 divided
by 4 by 11 is 7 by 4. 68 by 11 divided by 20 by 11 is 68 by 20, which is 34 by 10, which
is 17 by 5 and this is 4 by 7. Now, clearly 4 by 7 is the minimum of the
three, because this is more than 1, this is more than 3 and this is less than 1 so this
variable leaves the basis. When this variable leaves the basis, we need to perform one,
more simplex iteration, where we replace lambda1 with lambda3 and continue with the simplex
algorithm. But before we continue with the simplex algorithm let us again take a very
quick recap of what actually has happened.
What we did was, in this we started with this large linear programming problem and we realised
that by leaving out a certain sets of constraints, the problem is decomposable into smaller size
problems. Those constraints that go out constitute what is called the master problem and the
other constitutes the sub problem. We also exploited the convex combination property
and then we re-wrote the formulation.
Now based on this formulation, we had been carrying out the simplex algorithm and we
have come up to the variable lambda3. We will continue the discussion in the next session.
