Tip:
Highlight text to annotate it
X
So, let me give you a few references for would all the material that we have been discussing
so far and that we will discuss later on, and if they are some other I will give you
later on. So, first focus linear and combinatorial programming Katta Murthy, it is a classic
book and the mathematical treatment of whose subject is very - what shall I say - very
complete and deeply done, very rigorously done.
So, if you are not very mathematically imply, may be you can come back to it for some result
or something, fine. So, this is the book by K J Murthy, then the other one is linear programming
in network flows. This also has reasonably good treatment quite in detail, and about
network close we will also be discussing on and off as an application of linear programming
problem of the theory and so on. Then finally, combinatorial optimization algorithms and
complexity as you see, this is a little not exactly in our area, but the first few chapters
are very well done and they illustrate the theory of linear programming simplex algorithm
and duality. So, you can also refer to this problem and
then you can see the applications of linear programming problems to combinatorial optimization
problem, so therefore, I have given you these references.
So, let us continue with our discussion of the dual simplex algorithm, dual simplex algorithm
I had almost completed with you. The only thing is that I should have pointed it, out
and probably it was all clear that, you know, in the dual simplex algorithm, you see you
have a dual feasible basis and then, see what we said is that we must have complementary
slackness conditions being satisfied at each iteration, which means therefore, and that
the primal and feasible, primal and dual solutions that we handle at each time are complementary
pair; that means, if B is a basis for P then, we know that B inverse b is a primal solution
not necessarily feasible, but in any case, therefore, that means, some components are
negative here. So, this is a primal solution and then the
dual solution that we handle is C B B inverse, so therefore this is a complementary pair
that is what I want to, because we keep working with the same basis - complementary solutions.
I have just stressing it again though we have been using it in this way, so this is what
we have to note here. Now, I will go to another variant of the simplex
algorithms which is the primal-dual problem method - primal-dual algorithm. So, the earlier
name for the dual simplex the name was very suggestive, what we were doing was, we were
following the simplex algorithm, but applying it to the dual problem and maintaining the
primal tabular. And here, I would like you to when you get more familiar with the algorithm
and with the theory, then you can actually see that each iteration, you are actually
solving, so if you side by side you keep the dual problem and maintain it tableau, then
you see that all the pivoting and everything that you do in the dual simplex algorithm,
you are actually doing it for the dual problem with the simplex algorithm.
Now, here this is different name this is primal-dual algorithm and this also gets generated from
the complementary slackness conditions. And I will again use the canonical form the linear
programming problem and the dual problem, so the canonical form is, form of LPP. So,
this is as we see minimize Z equal to C transpose x subject to A x greater than or equal to
b, x greater than or equal to 0 and the dual is, so this your P, your D is maximize psi
equal to b transpose y subject to A transpose y less than or equal to C, y greater than
or equal to 0.
So, let us see, the complementary slackness conditions would be, this is x j transpose
A j transpose y minus C j is equal to 0 for all j varying from 1 to n. And this is y i
times a i x minus bi, so this is the row, this is the column of the matrix a, this is
0 for all i varying from 1, 2 to m. So, let me just start developing the algorithm
then we come back and discuss to the other aspects. So, say for example, you have this,
and now let us say suppose, y is a dual feasible solution - any dual feasible solution I am
not even saying it has to be basic feasible solution and this was also, remember, where
I prove the complementary slackness conditions, I nowhere ever use the fact that x and y are
basic feasible primal and dual pair, I just said that they are both feasible for the respective
problems. So, here also, suppose y is a dual feasible solution, then define J is equal
to j in index such that A j transpose y is equal to C j; that means, all the dual constraints
which are satisfied as equality. So, this is the index set given a feasible
solution y, I just collect the find out the index set where the indices represent the
dual constraints which are satisfied as equality. Now, the idea is, you see if I want to satisfy
the complementary slackness conditions here, what do I need, again I am repeating this
that if this constraint to satisfied as equality then my x j transpose can be anything 0, non-zero
right, because as it is this is 0, so the product will be 0, but if this is satisfied
as strict inequality then I must have x j equal to 0.
So, here again, we are trying to find primal solution, given a dual feasible solution I
am trying to find a primal solution which was satisfy the complementary a primal feasible
solution which will satisfy the complementary slackness condition. So, once I am able to
find a primal feasible solution, satisfying the complementary slackness conditions, then
I know that I have an optimal pair. So, therefore, once I have this, that means I can only allow
those x j's to be positive whose indices are here, so define j this. Now, we try to find
a primal feasible solution x such that x j is 0 for j not belonging to this; that means, I will
be looking for a primal feasible solution from among the x j's whose indices are here.
So, that means, I need to now define, so I will define a restricted primal problem, we
call it RP. So, restricted primal problem would be minimize, may be write something
else z bar as c transpose x subject to A x greater than or equal to b, x j greater than
or equal to 0 for j belonging to this, and x j equal to 0 for j not belonging to J. This
is my restricted primary problem, so I want to solve this if I can get a feasible solution
here, then I am done. So, that means, I start with some dual feasible
solution and then I define this restricted primal problem such that when I find a feasible
solution here, this together with that y will satisfy the complementary slackness conditions
and so I will have optimality. So, that means, now can you see that this is a feasibility
problem, the restricted primal problem is purely a feasibility problem; I want to find
a feasible solution. So, therefore, you can see that, to obtain a feasible solution for
RP if I obtain a feasible solution for RP to obtain this, we use phase 1 the obvious
method because, I do not know whether this problem is feasible or not so therefore, I
will use phase 1, so what would be my phase 1.
So, phase 1 would be minimize, some other thing you can write here Z double bar may
be, it is equal to minimize this equal to summation x a i; i varying from 1 to m, subject
to A x subject to so this is yes, you will have to write minus x s plus x a is equal to b. And
you have your x s, x a, x a are all non-negative and your x j is 0 for j not belonging to J
and x j greater than equal to 0 for j belonging to J.
See your phase 1, I have added artificial variables, first I converted to equality system
and then I will add artificial variables. And obviously, if the optimal solution here comes out to be 0 - if
this comes out to be 0; that means, I have a feasible solution to the original problem
from among the regular variables and therefore I am done. And if this problem is not feasible;
that means, the optimal solution here would be greater than 0.
So, anyway, so we will refer to the restricted primal as this problem, so this is the one
in order because I am now formulating this problem as a feasibility problem and therefore,
I am calling this is. The corresponding dual would be restricted dual would be what? It
would be maximize, you can say something like this equal to yes.
So, let us just define the dual here, this would be maximize b transpose y bar did I
write the dual somewhere here? Yes, the dual is here, so maximize b transpose y subject
to, you see here, your matrix is actually, A minus I and I, and you had x, x s and x
a this was the thing, when you take the transpose, it becomes A transpose minus i i times y bar,
and this is less than or equal to, so the coefficients are - I am writing the dual here
- so all these are 0s and this one is 1, so this is the vector of 1s m dimensional vector
of 1s and since you have equations here, your variables are unrestricted.
So, y bar are unrestricted, this is your dual and let us rewrite it, so to rewriting it
gives which implies that your problem is actually max phi equal to b transpose y bar subject
to A transpose y bar less than or equal to 0, y bar greater than 0 because minus y bar
less than 0 implies y bar and y bar less than or equal to 1, where again this is a vector
of 1s, this is your restricted dual problem. Now, what are the possibilities? I solve the
restricted primal as I said, so the outcomes are, either this value is 0 - the optimal
value is 0 - or it is positive, because my variables are non-negative, so this cannot
be negative.
So, let us see what are the implications of the two outcomes, so possible outcomes are,
1 minimum is Z double bar, which is equal to summation x a i; i varying from 1 to m
is greater than 0. Let me consider the case, this because I will have to continue with
that is equal to 0, this implies that we have obtained a feasible solution for P and by complementary slackness condition
by complementary slackness theorem, this solution is also optimal, so we are done.
In case the value comes out to be 0, we are done, because we have found a feasible solution
and that is what we and it is optimal, so that what is we were looking for. So, the
second outcome would be that minimize a minimum of Z double bar is greater than 0.
So, if this is greater than 0; that means that there are artificial variables in the
basis at positive level, so you do not have a feasible solution for the actual problem
- this one, because this not be satisfied as equality, this itself would be greater
than b and so you do not have, well, what will you have if you are minus x was equal
to b so they will not be satisfied as equality greater or less we cannot say, but it any
case, this will not satisfy the constraints as inequality, because some x a positives
are present.
So, therefore, we need to, so that means, that this particular dual feasible solution
y will not click, it is not enough to give you a feasible solution for the original primal,
so we need to modify.
So, this implies that the current RP is not
able to produce feasible solution for P. So, need to therefore, we need to modify the dual
solution Y. And how do we modify it? You see here what is happening is, that since the
optimal value this is greater than 0. This implies that this is also get as a 0 remember
at optimality, the two objective function values must be the same, so b transpose y
bar is 0 our dual problem is a maximization problem.
So, if I modify the present dual solution with respect to our y bar over used here,
yes, I have used y bar, this is b transpose y bar is 0, therefore, consider the solution
y plus theta y bar. Now, b transpose y plus theta y bar is b transpose y plus theta b
transpose y bar, which is greater than b transpose y. So, this solution seems to be a good candidate
because it is increasing the value of the dual objective function but I need. So, if
we can chose ok here, sorry, theta should be greater than 0, because then only this
could be positive, this is positive, theta positive therefore, this is greater than b
transpose y. If we can chose theta such that y plus theta
y bar is dual feasible, then y plus theta y bar is a good candidate. Remember, we are
trying to modify the dual solution and then look for another primal solution which will
satisfy the complementary slackness conditions along with this new candidate is a good candidate
for the modified dual solution. So, I how do I make sure or how can I say that, I can
chose a theta, now that means, you want A j transpose y plus theta y bar to be less
than or equal to C j, yes. Now, you look at the see y bar is a solution to the restricted
dual and you have a transpose y bar less than or equal to 0 here.
So, therefore, if a particular j, see here, yes, sorry, I should have because this is
restricted dual, I should have said here, this is for j belonging to J. Remember, because
we are only considering the columns that you have here, columns that are present here are
only corresponding to the j e J, for x j, this is a correct, x j is equal to 0 for j
not belonging to J, so since x j is 0 those columns are absent from here. And therefore,
when I take write the dual, the columns here would be missing. So, for j in J you are A
j transpose y bar is less than or equal to 0 anyway yes, so this is less than or equal
to 0, we want to choose, so we want this, the question mark.
Now, for if j belongs to J, then A j transpose y bar is less than or equal to 0 and y is
already dual feasible, this implies that for theta greater than or equal to 0, this constraint
is satisfied, for theta greater than 0 all dual constraints correspond j belonging to
J will be satisfied for theta non-negative will be satisfied. So, if the problem is when
j is not in J, because then I do not know about the sign of A j transpose y bar.
So, let us see what is happening here, so if A j transpose, so for j not belonging to
J, if A j transpose y bar is greater than 0, then what do we require? From here, if
you look at it theta must been, because A j transpose y bar will be positive when I
divide by the inequality will not change. So, what we are saying is, that your theta
should be less than or equal to yes, C j minus A j transpose y divided by A j transpose y
bar. And therefore, if we chose, so chose theta
as the smallest of these as minimum C j minus A j transpose y upon A j transpose y bar where,
A j transpose y bar is greater than 0, then chose theta this, then to ensure that y plus
theta y bar is a dual feasible solution. And what is happen? Because the j does not belong
to J and I am choosing theta as the minimum of this. So, you see, if this minimum occurs
for, let us say, j equal to k if this minima occurs for j equal to k, then at least for
one extra column a new column has come in to J, because for that particular column are
that, suppose, now these are small exercise are which suppose, minima was it can be for
more than 1 j also, A j transpose y on A j transpose y bar is greater than 0, this is
occurring for C k minus A k transpose y on A k transpose y bar.
If you are, this is this, theta is this, then you see that A k transpose y plus theta y
bar will be equal to C k. Just from the definition because that is your theta, so when you write
it here, this come out to be equal to C k, it was that y bar this is cancel A k transpose
y bar will cancel with this, and you will be left with and this will cancel, so you
will have simply C k. So, that means, you have one more index in J and also, therefore,
there is a hope that you can find a new with the change J, with the change set of columns,
you are restricted primal changes the definition restricted primal will have extra column and
the hope fully, you can find a primal feasible solution, if you cannot then you again continue
with the process.
So, diagrammatically, as Papadimitriou is also shown in his book is that what is happening
is, you see, you can show a very nice flow diagram. So, you have a primal here, then
I define the dual, so this is my dual, then I have a feasible solution here y for the
dual with respect to this dual feasible solution I define the restricted primal, the restricted
primal gives rise to a restricted dual. And then, with the restricted dual because obviously,
if restricted primal is not able to yield feasible solution for the primal then I will
go to the restricted dual and from here, I will have a y bar which will be a solution
to the restricted dual, then using this I will modify my, so your flow diagram is this.
So, you modify your dual solution, then with the new dual solution you have a new restricted
primal with the new restricted primal you solve it, if you cannot find a feasible solution
for the primal, then you will again go the restricted dual, and then again, so this cycle
can continue. So, of course, in any algorithm when you define, you want to make sure that
it will converge in a finite number of steps and it will give you the required answer.
So, let us see why we can be sure that it will be finite algorithm, see here let me
rewrite the problem again, see if you consider the extended version of the minimize of the
primal problem which is C transpose x subject to A x minus x s plus x a equal to b; x, x
s and x a are all non-negative. See, what is happening is that at every, because
my restricted primal in the restricted primal I drop some columns, then I have this system,
so when I solve the restricted primal I am working with the basic feasible solutions
of this extended system which again is a finite number, because the number of constraints
is m, number of variables becomes n plus 2 m; m here and m here. So, this is the number
instead of being n plus n this is now the number of variables is n plus 2 m, but does
not matter you still know that the number of basis is finite number and all of them
may not be feasible, so anyway have a number of this feasible basis that you consider is
much smaller than the combination from chose n plus 2 m from that we chose m columns.
And also, when you are solving the restricted primal we use it is possible the degeneracy
for the restricted primal when you are solving the degeneracy may occur, and so cycling can
place but with the Bland's rule for anti-cycling if you follow Bland's rules for anti-cycling,
then we ensure that no basis is repeated more than once. So, therefore, the algorithm will
be finite, because at each iteration will have only one particular basis for this extended
system.
So, if you just look at the extended system, then you can say that the algorithms is finite.
And obviously, as we said that either the minima will come out to be 0 in that case,
we have an optimal solution or yes. Now, what are the things see professor if your original
problem is infeasible, how will you found that, so how will you recognize remember,
look at this condition here, I am saying that for j not in J, A j transpose y, bar they
should be at least 1 j not in J for which A j transpose y bar is greater than 0.
So, let me write it out that if there is no such j or which your A j transpose y bar is
greater than 0; that means, for all j, A j transpose y bar is less than or equal to 0.
Then what do you conclude? The dual is unbounded because after all restricted dual your simply
restricting you are not using all the constraints, so it is a greater version of the dual problem.
So, let me write it out here, so the algorithm will either converge in a finite number of
steps, number of iterations or conclude that the dual problem is unbounded, well I can
in fact, make a better statement it is unbounded out. See, if at some iteration if A j transpose
y bar is less than or equal to 0 for all j, this implies that y bar plus theta y bar is
feasible for all theta greater than 0. Now, yeah, for any value of theta, because
A j transpose y bar is less than or equal to 0, the constraints will continue to be
satisfied, no matter what value theta has, what positive value theta has, so therefore,
this is feasible and since, b transpose y bar is greater than 0 this implies that your
b transpose y plus theta y bar will go to plus infinity as theta goes to infinite. So,
the value becomes from as big as you wish I had using a corresponding theta very large
is and so the dual problem is unbounded and therefore, so this implies that the primal
is infeasible. So, you have; that means, now the algorithm is complete because it will
either tell you that there is an optimal feasible solution, and it will find it for you, or
it will tell you that the problem is infeasible, so you cannot or does anything about it just
stop there. Now, at another just a small aspect that I
wish to point out here is, that yeah, so will have to write the restricted primal again.
So, I will continue while so showing you that actually the idea is that, when we want to
now translate this algorithm into the tabular form, you want to make sure that not too many
extra computations have to be made. So, I will start with the tableau formulation after
that, so let me begin by considering this example here.
Now, I just want to point out one thing that, see your restricted primal was yeah, I need
to write it here and then I will take it out restricted primal was minimized may be I wrote
this equal to summation x a i; i varying from 1 to m, subject to A x minus x s plus x a
equal to b where we said that your x j is 0 for j not belonging to J and x j is greater
than or equal to 0 for j in J, and others your x s and x a are greater than or equal
to 0. Now, if the restricted dual needed here on the side.
So, restricted dual you had maximize, this is equal to b transpose y bar, subject to,
so we said that, I will just look at so you write a transpose y bar is less than or equal
to 0. Because for the regular variables the coefficients are 0, and then the other one
said that y bar should be greater than or equal to 0, and y bar is less than or equal
to 1 where this is a vector of all ones of n dimension. Now, you see, when you look at
the optimal solution to the restricted dual and to the restricted primal, the corresponding
pair then remember complementary slackness conditions have to be satisfied.
So, here, if a particular what I am saying is that, if x j is in the optimal basis of
RP, this implies, and assuming it is positive, I am with this implies or even see as long
it is in the optimal basis it is a basic variable, this will imply that your A j transpose y
bar will be 0, because complementary slackness conditions requires that if a particular variable
here is positive in the optimal solution, then the corresponding dual constraint must
be satisfied as equality, which means that and remember, here we were only permitting
those x j s to take positive values which for which they corresponding index is in J;
that means, the dual constraint is already satisfied as equality.
So, therefore, this implies that A j transpose of y plus theta y bar will be equal to C j,
because A j transpose y bar is 0 and A j transpose y is equal to C j, because j was in capital
J. So, that is, this implies that any basic variable in the optimal solution of RP will continue to satisfy the corresponding
dual constraint as equality. So, therefore, we can if whatever a tableau
I have at the optimal solution here, and I can and when then because I have modified
my a dual solution, so a new column has to be added in the as a possible candidate for
being in the basis, then I do not have to change my competitions and you see, the whole
basic a solution here, basic feasible solution for the restricted primal, the continue to
be the corresponding variables continue to be in the index, the indices continue to be
in j and therefore, I can just take off from there, so this is the beauty.
So, therefore, I do not have to again reformulate, because my restricted primal gets reformulated,
it does not mean that I have to start from the beginning or fresh all my computation,
so I will try to demonstrate to you all that well, I am doing this. So, here, if you take
this and your x 1, x 2, x 3, x 4 is non-negative, so in the theory of the primal-dual algorithm
is beautiful because you see that probably well aspects of linear programming theory
are used here. And beautifully crafted algorithm, and later on I hope to be able to excite you
about it by giving you very interesting examples. So, let us see, now we want to work out this
example and I will try to demonstrate the algorithm for you.
So, you have this and let me formulate it has an equality problem, so this would be
in the standard form, so this is minimize z equal to x 1 plus 2x 2 plus 3x 3 plus 4x
4 subject to x 1 plus 2x 2 plus 3x 3 plus x 4 minus x 5 is equal to 2, And here, x 1
minus x 2 plus x 3 minus 3x 4 minus x 6 is equal to 3. And all x x j non-negative for
all j, so let us write the dual, so this is your primal problem, what is your dual? So
the dual would be maximize here this is yeah. So, the dual would be, we have been using
the psi is 2y 1 plus 3y 2 subject to so the transpose this will be y 1 plus y 2 less than
or equal to 1, then 2y 1 minus y 2 is less than or equal to 2 in 3 and 1, so 3y 1 plus
2 is less than or equal to 3 and 1 n minus 3, so this is y 1 minus 3y 2 is less than
or equal to 4. And since, you can then here you have so this comes out as minus y 1 is
less than or equal to 0, minus y 2 less than or equal to, which imply that your variables
are non-negative because originally I started with greater than or equal to constraint.
Now, the question is, how do I get a starting dual feasible solution, you see that all these
numbers are non-negative. So, therefore, y 1 equal to 0, y 2 to is easily available dual
feasible solution and of course, you can see some here also, the corresponding basis see the corresponding
basis is what? This is minus e 1, minus e 2, because here the if you take this as the
basis this gives a solution to the set of equations that is, but it will be x 5 equal
to minus 2 x 6 equal to minus 3. So, therefore, this basis gives you a solution to the primal
constraints, but it is not feasible, but it the corresponding because this is the coefficients
here are 0s C Bs are 0s, therefore, the corresponding dual solution which is, C B B inverse is 0,
0, because C Bs are 0s. So, therefore, that will they are complementary
pair as we want and since they are complementary pair, they satisfy the complementary slackness
conditions. So, we are done, we have a starting dual feasible solution and so now try to define
your j, what is your J, the dual constraints which are satisfied as equality by this so
you see that only these two constraints are satisfied as equality, so therefore, your
J contains 5 and 6 only - the indices are 5 and 6.
So, now what would be your restricted primal; that means, your restricted primal you would
drop all these columns, so my restricted primal would be yes - so let me write it here only
- your restricted primal would be minimize and I will add the artificial variables, so
it will be minimize Z double bar equal to x a 1 plus x a 2 and subject to minus x 5
plus x a 1 is equal to 2, and minus x 6 plus x a 2 will be equal to 3 and all variables
are non-negative.
So, this is my restricted primal and I need to write the restricted dual also, yeah, so
let me now get into the tabular form. So, this is your restricted primal, so what we
will do is, we will put these dots here to indicate that because I will need the other
columns later on when I want to induct them into the basis, so I will carry the whole
tableau and I do the computations so that when I need a particular column I will already
be in that form. So, now let us read the things carefully,
so I am writing the restricted primal, so this is 0, 0, see, I am writing the original
objective function; the original objective function these are the coefficients, then
for the restricted primal this is 0, 0 ,1, 1 and this is my tableau. This is my current
starting feasible solution for the restricted primal yeah, not in - I mean - for the extended
restricted primal. So, therefore, I need to make 0s here, in order to be able to continue
with this simplex algorithm to solve the restricted primal I do that here, you see I add the last
two rows and subtract from here, so you can see that this does not change because it is
already 0, 0 here. So, this is the thing which this row will
change and you should be minus if I add and subtract so minus 5. So, currently the restricted
primal objective function value is 5, because this always gives you minus of the objective
function value fine. So, now this is optimal because you see that for the restricted primal,
the objective, the C j minus Z j is respect to the restricted primal objective function
are non-negative. So, this right now is the optimal solution for the restricted primal
and you can see that the objective function value for the restricted primal is the positive,
therefore, I do not have a feasible solution for my original primal problem, and let us
be careful here see, remember I would need the I will show you the computation. So, for
example here, and this one, this is your C j minus Z j, the top row always gives you
the C j minus Z j and here, what you have these entries as, remember you want the entries
A j transpose y bar. So, here, in the restricted primal, the regular
variables have 0 coefficient. So, this should also read as your C j minus z j for the restricted
primal, but the C j s are 0s therefore, these numbers quantities here, will give you the
simply the minus Z j s. So, minus Z j s are simply A j transpose y bar, because your y
bar is C B B inverse so therefore, the transpose of you takes C B into B inverse A j.
So, that gives you the, so these are your minus A j bar, here these are, so therefore
negative of the unit A j transpose y bar and remember, now, you have 2 decide which column
to enter it is, so the ratio was you had to take the minimum ratio of C j minus Z j divided
by A j transpose y bar said that A j transpose y bar is greater than 0. This was the criteria
deciding the column which will enter the basis, so all I have to do is to look at this row
and divide by the corresponding negative entry here, because well of course, this these are
the ones which correspond to plus A j transpose y bar.
So, therefore, 1 by 2 is the ratio 2 by 1 and 3 by 4, so this is the smallest 1; that
means, this is the column, which is going to enter the basis the first column, and then
I do the regular now I have an extra column added and I want to continue and as I told
you that the same basis. So, here, of course, your original basis was consisting of the
artificial variable, so no problem. Now, this one comes into the basis, I will pivot it
so the ratio again I take 2 by 1, 3 by 1, so this is your minimum ratio.
So, we pivot on this, I pivot on this, I make 0's here and here, and this table shows you
the corresponding computations. And let us see, now of course, you should have also the
other step that which we shows here, is that you know the ratio the minimum ratio was 1
by 2. And remember, your modifying this by y bar and so originally this was 0, 0 your
theta is half, the minimum ratio and what is your y bar, the dual solution, see the
dual solution would be available here, your C B B inverse, so that is 1, 1 so this is
half, half. See, during the lecture, one cannot keep on
repeating of the details, but I have we have already pointed it out for you that whenever
you have an identity matrix starting in the column, then whatever you have on the top
and for the coefficients are 0. See, in the original objective function these coefficients
are 0s, therefore, they do not appear, but anyway, since this is your identity matrix,
this will be your C B B inverse the dual solution.
So, therefore, you have half, so this your current dual solution, you can check that
this is a feasible for your problem. So, at each step you must keep checking that you
have feasible solutions for your these thing.
So, now you have this current thing, so let us see, do you have an optimal solution for
the restricted primal? No, you have to see, you have something negative here, so you have
a negative entry here which means that you are you are you know A 5 transpose y bar is
greater than 0 remember this show this. So, we need to pivot on this one also, and therefore,
what would be this thing see the only entry positive entry here is 1, so I will pivot
on this one yeah. And the ratio of course here again is half, so theta is again half
and A j transpose y bar is positive here, so you pivot on this one and you pivot, you
would have to multiply this by half and subtract.
So, multiply this row by half and subtract, and that will give you, so let me just quickly
show you the computations here yeah. So, this would be half times you are doing, so this
is 0 minus 3 by 2, this is 0, this is, 0 this is half time minus 2, this is 3, that is for
your subtracting, hold on, so we are subtracting therefore, half times you have to subtract.
So, this would become 3, sorry, this will be 3 then half, so that will become 2, yeah.
And this would be a minus 2 so that will be 7, this will become 0, and here it will be
half add that again this will be 1, and this am not concerned.
So, half you are subtracting this becomes minus 3 yes, and then, you simply add this
to this, therefore, this will be 0, 0, 0, 0, 0, 0 and what is happening here? This is
also 0. So, you see, the restricted primal objective function value is 0. And this remains
as it is I simply add this here, so this is 1, minus 1, 1 minus 3, 0, 0, and you are adding
this, this becomes 3 and this remains as it is 0, minus 3, minus 2, minus 4, 1 minus 1
and this remains is 1. So, you see the restricted primal objective
function value is 0, therefore, you have arrived at there you have a feasible solution for
the original primal problem which tells you that x 1 is 3 and this one corresponds to
x 5 is 1.
So, you can quickly verify that this is a feasible solution for this problem in the
objective function values 3 and you can also see that the corresponding dual solution would
be 0, 1 as I told you, because you had another rubbed of the calculations, you had half remember
your solution was half, half then you had this and you had minus 1, 1 has the dual solution,
so the theta was half, so this becomes 0, 1. This becomes your dual solution, please
sit down and just go through the calculations and verify for yourself that the calculations
are ok.
So, this is a new dual solution, the value of the objective function you can see here
is 3, it is a feasible solution, the objective function value for the primal is also 3, so
you have an optimal solution. The last table, the things will not a little very clear.
So, let me just revisit, so what I am saying that this was the last but one tableau and
you see, as we said that this row corresponds to your phase 1, so therefore, are the restricted
primal, so the this things are minus A j transpose w bar and since you are A j's for x 5 and
x 6 are minus e 1, minus e 2. So, therefore, this will correspond to for the slack variables
this will rather surplus variables, this comes out to be w 1 bar and w 2 bar.
So, what would have here is, this is your restricted dual solution. And this in the
same way I have shown the computations that for the slack surplus variables, this gives
you the dual solution for the original problem. And then, you see here, in the tableau also
we have marked that our current basic feasible solution consists of the first column and
the last column, and the basic variables are x 1 and x a 2.
So, we can begin from here, because for these two the dual constraints would be satisfied
as equality. So, then here you see, this is the one which is negative, because for x 5
and so plus the A j transpose w bar would be positive, so I need to take the ratio this
is the only one so there is no need take a ratio I know that this is has to enter the
basis. And after that, your calculations are because I will just pivot it on this one and
then I showed you that, you add this half time to subtract and what could get is finally,
the objective function value here become 0 because when you add this this becomes 0 in
fact, everything becomes 0 here. And so that ends your restricted primal phase and you
have an optimal solution to the restricted primal with 0 objective function therefore,
the corresponding solution that you have here after the pivoting is the primal feasible,
it is already dual feasible, so you have an optimal solution.
So, yes, therefore, one can without actually if because it was possible to get a feasible
solution by inspection for the dual problem, things became quite simple. And you put go
head and solve. Of course, one would want to compare make comparisons between the dual
simplex in the primal-dual algorithms. So, one obvious comparison which I pointed
out in the beginning was that for the dual simplex algorithm, you have to start with
the dual basic feasible solution. whereas, for the primal-dual, you do not need to have
a dual basic feasible solution any dual feasible solution would do the job because all you
need is to have your J index set and once you have your J, you can define your restricted
primal and then you can continue with the dual algorithm.
So, that is a lot of saving. So, this is one of the comparisons and then, we will also
I will try to show you situations where sometimes dual simplex algorithm is a very natural need,
it comes very naturally. Similarly, we will want to show that primal-dual algorithm also
is very naturally required in some situations and in fact, primal-dual algorithm has been
very useful in solving and another class of optimization problems, which we call as combinatorial
optimization problem. So, I will try to give you some blimps into those situations also.
Now, therefore, the only thing now we really need to address therefore, I say that my treatment
of the two algorithms; the dual simplex in the primal-dual algorithm is complete, would
be in the absence of being able to obtain a dual feasible solution by inspection of
by some other means, they should also be definite method because if problems are very large,
then I should have a definite method of being able to compute a starting dual feasible solution.
So, I will try to in the next lecture; give you an idea as to how one can obtain in any
situation I can always have a starting dual feasible solution and then proceed with the
algorithm either of the dual simplex or the primal-dual algorithm.