Tip:
Highlight text to annotate it
X
So, let revise the steps for the right hand side parametric transportation problem; so,
as I told you that, if this is the parameter delta for the right hand side values s
i's and v j's; so, we first solve for solve for delta equal to 0, so that is what write
it, you can check that these are the dual variables sometimes, so this these are
your u i's and these are your v j's, you can verify that the current solution shown here
in the table is an optimal solution for delta equal to 0.
So, once we have that, then we try to allocate according to the delta; so, you see that,
here this is the cell which is common to both, so here this will become minus
delta; and then in this case you have 3 delta 2 delta, so the maximum I can allocate here
would be 2 delta, so plus 2 delta, so you use the same principle, so this is 2
delta then I have to come down because this needs to be satisfied.
So, therefore, this will be plus delta 7 plus delta, then because this is 16, so I must
have and there is a minus here, so this becomes minus delta and that is it; so, we
have taken care of all the see this is this so for the delta, you see this is 3 delta,
these adds up to 0 then this adds up to minus delta and that is it.
So, this is now accordingly because its already optimal the u's and v j, so you see that the
c bars are all non-negative, so this is an optimal solution; so, determine
the interval, so for example, interval for delta such that the current basis is optimal.
So, you have to just maintain non negativity of the variables, because
optimality is already satisfied; so, from here you get that delta has to be less than
or equal to 4; and here delta has to be less than or equal to 9, so the positive part
I have taken care off, because these two numbers tell me that delta should be less than or
equal to 4; and from here delta cannot be less than minus 7, and this is
delta must not be less than minus 4. So we choose this the maximum 1 of the 2,
maximum of minus 7 and minus 4, that gives you the lower limit for this; so, for all
values of delta in this interval your
current solution is optimal. Now, if we choose delta greater than 4, so the moment you do
this the variable x 1 2 becomes negative; and in the last lecture also I
had gone through the steps of the, so that means, we now the we apply dual simplex.
Yes, I am deliberately repeating this algorithm, because it requires a little bit of understanding;
and, so we did it last time, so you have to apply dual simplex
algorithm, and so that because the optimality conditions are satisfied if the feasibility
which gets violated; so, when delta is greater than 4, that means this is going
to become negative, so this must leave the basis.
So, now, we need to quickly write out the see bars, because to apply the dual simplex
algorithm I need the relative prices; therefore, this would be 3 4 minus 1,
hence this is 8, because 7 minus 7 is 0, and this is 9, so this is 1; and so, in fact you
should verify that the optimality condition is satisfied, so this difference this is 6
8 minus 6 is 2, and this 1 is 8.
So, this will be 11, this is 3, and here this one is 9 minus 4, this 5, then 3, so this
is 6, and this is 9, so this is 9, now here 11, so 18 minus 11 is 7, this is 4, and this
number is 2. So, you are applying the dual simplex algorithm, remember we have to, so
x 1 2 because delta greater than 4, this variable will become negative, so
this needs to go out of the basis and they up went to determine the incoming variable;
you can go back to in the simplex algorithm I had given in detail, so you
have to now compute these ratios and here see this is Y i j, that means, if you are
considering i jth non-basic variable here to enter the basis; then you must have
the so capital Y i j, as we were saying is the vector ;so the components of these will
be the numbers ,which will be used to express the a i jth column in terms of the
basic columns. So, here I need to know the Y i j the 1 2
1, 2 component of the vector Y i j, and this has to be less than 0; and in fact, we know
that this is always equal to minus 1,
because these numbers are either 0 1 or minus 1. So, when you take this minimum ratio, this
actually amounts to choosing the minimum, because this is minus 1, so
minus minus cancels and so you have to choose that non-basic variable to enter the basis
so which the corresponding Y i j 1 2 is equal to minus 1
So, among all the C i j bars, so that means, I will and since I do not have that kind of
simplex tableau representation here; so, I do not know the numbers before I
need to compute them; so we will what we will do is, so I will start with this smallest
C i j bar and see for example here, this is the 1; and if you want to express
this in terms of the basic columns, I have the expression here, so a 1 5 can be written
as because you form theta loop, so this will be a 1 2 3 2, this, and this, see the
theta loop is this; therefore, it will be A 12 minus A 32 plus A 35 and here you see
the corresponding component the Y 15 12 is equal to 1; therefore, this is cannot
be candidate for consideration here, that means it cannot be a candidate for coming
into the basis. So, I will give you a simple rule, that means,
if this variable is to leave the basis, then you can check for yourself that all these
the non-basic variables in this row
and the non-basic variables in this column; all of them will have the corresponding component
Y i j 1 2 equal to plus 1; therefore, I can simply rule out these
non-basic variables and these non-basic variables. So, that is done, therefore your work becomes
simpler; and now, you will so this 2 is also gone; so, the next smallest C i j bar is this
and I will try to consider this;
and you can now verify check verify that; So, this will be Y, this is 1 2 3 4 4 5, 4
5 1 2 is also 1, therefore this is not a candidate for coming into the basis; so, now I
go to the next highest value of C i j bar, which is 3 here, which is this; and so, try
to make a theta loop here, and again you can see that, so this is 2 5 Y 2 5 I think
you can also verify is equal to over may be we will just quickly check what will be the
loop here; if you want to make the loop, here this will be this, and then so
you cannot go here you have to come here write. So, this will be this, this will be this,
the loop will be will have to yes I am saying that you come here from here, then you come
here, we then go here, and I come
here, I come here, then here, here, so it is a big loop, but anyway just verify that
this is also 1; you are using this because you are coming from here to here going
this way, then this, this way, then you're coming here, here, and then this, and then
this going.
So, you just verify then the sign of so Y 2 5 1 2 will be 1, so this is also out; so,
that means, now, I go to the next highest C i j bar value which is 4 here; and let us
quickly see if this will qualify for coming in into the basis; so here what would be your
theta loop, theta loop would be may be its come out to be a big 1 here also
that see you have this, this, and you can see that from here this will be plus minus.
Let us see it may be I can just verify for yourself, so this is Y 3 1, Y 3 1, so even
this 1 will not come I have just made the calculations and that count spent time on
it; so, what I am saying is that, Y 4 3, Y 4 3 1 2 is equal to actually 0, I think that
is where it comes out to be Y 4 3 1 2 is 0, so this does not figure in the loop that
you make with this 1, just verify for this. So, finally, what turns out is that 3 1, so
this is the next 1, next highest we will consider this now; and let us see what would be the
loop for this, the loop would be
you will have to go this, then you can come here, you can come here, you can go here,
then here, and here, and this I will form the node this is like this, this one,
this, and here this one, then you come here, and this is the loop, I will just draw it
only for you. So, then you see this will come at level theta,
then this will be minus theta, plus theta, minus theta, plus theta, and you wanted to
look at the sign; therefore, for you
see for example, this start with this plus minus plus minus; now, we know that your Y
3 1 one 2 is equal to minus 1, so this one qualifies to so that means the
variable x 3 1 qualifies to come into the basic solution becomes a basic variable and
we just have to make sure see here you want to make this 0.
So, theta will be equal to delta minus 4, which will be non-negative for delta greater
than or equal to 4; remember we are now choosing delta to be greater than or
equal to 4; so, theta will is at the level delta minus 4 and once you put theta equal
to delta minus 4, this will become 0, and you can now just update your solution
say, for example, this will become delta minus 4, and this is minus theta, so 7 plus delta
minus delta plus 4, so this will become 11, you can update your current
basic feasible solution and then once you updated then you have to compute.
And remember the choice of the incoming variable such that your optimality criteria will be
satisfied; therefore, you just have to update the current basic feasible
solution and that will be optimal for some interval of value delta. So, for example,
here what will happen is that, this one this got this got change to 9 minus delta
and let see this 1 would be what here 8 minus delta plus 4, so this is this is 12 minus
delta this not help me. So, here for example, what would be this look
at this number here, this will be plus theta, so this is minus theta, so this 1 will become
5 minus delta plus 4 which is
9 minus delta; so, this particular variable will become 9 minus delta and you can verify
that the new basic feasible solution is optimal for 4 less than or equal to
delta less than or equal to 9, so do this verification for yourself; and now, you see
that because your get and write the numbers here, 15 plus 3 delta 9 minus delta 4
14 minus delta and this was 2. So, you see this number will become infeasible
for delta greater than 9 and since the demands can be either positive or zeros; so, here
you see that this problem is
not feasible for delta greater than 9 so on this side you have done your computation the
computations are complete, because you have the interval minus 4 to 4 for
delta and then 4 to 9; so, if you want to now find out what happens for delta less than
minus 4, then you see that this particular variable will become negative and
so you will again do the same exercise while trying to remove this from the basis and then
you will find out which variable will enter the basis; and here you see
that 15 plus 3 delta, this has to be non-negative, so that tells you that delta should be greater
than or equal to minus 5. So, that means, the next interval the next
basic feasible solution when you do the same exercise for delta less than or equal to minus
4, so the next interval will be
minus 5 to minus 4 and therefore this will complete.
So, I just wanted to show you that how you translate; we have discuss the dual simplex
algorithm in detail, I just wanted to translate it to the transportation array,
and you see that the disadvantage is there that you do not have these computations write
display to you on the board, but advantages are obviously there, therefore
one can continue using this.
So, let me now discuss the parametric cos in the transportation problem; again just
trying to translate the simplex algorithm and how you read it on the
transportation array that is all the difference otherwise we have already discuss the theory,
so but let me explain to you; so, here you see this is C i j, that means,
your cos r C i j plus lambda C i j star, so parameterized by lambda; and therefore, when
you compute the relative price with respect to lambda it is going to be the
relative price respect to the C i j, and then lambda times the relative the c bars with
respect to the star cos C i j star. So, that means, you have to now compute two
sets of basic variables, this would be for the dual that may u i v j and u i star v j
star, so you will do that
computation; and so I am writing them here see this is v j v j star so v j v j star this
is given to you, then u i u i star are given here, this is it will crowded anyway, so
this is this, and then this is C i j c i j star, then I have written here the C i j bar
and the C i j bar star and the circle numbers of course give you the basic feasible
solution. So, now, if you look at these numbers, all
of them here for the non-basic this, and this, and here this is 1 is positive, this is positive,
this is positive, and here of
course non-negative positive, and this is positive, and this is positive. So, the current
solution that are you are seeing on the tableau is optimal for lambda equal to
0; and so, we will now try to find out the interval for lambda for which the current
solution is continues to be optimal for all values of lambda in that interval, and
so for that we compute the lower number of the interval and the upper lambda upper bar
and the formula is of course for C i j bars star greater than 0; therefore,
just look at the C i j bar stars which are positive and you have only how many this one
is there. So and minus 3 you will get that, then for
example here this is 0, this is the 1 so 2 by 3, so minus 2 by 3, and then I think you
have one more number for which it is
positive, this one so this will be minus 7; and so, you choose the max of these numbers,
so that the current solution remains optimal, and therefore be the number
comes out to be minus 2 by 3; and similarly, when you want to compute the upper bar from
lambda, then this we corresponds to C i j bar star less than 0.
So, for all the cells for which the C i j bar star is less than 0, this we have computed,
and obviously you see that this will be the lowest number you choosing the
minimum, because for all others since you are doing minus C i j bar, and the this is
also negative the ratio will be positive, so here this will be 0.
And therefore, you see that the current interval for lambda, so lambda belonging to minus 2
by 3 and 0, the current solution is optimal; and when you put lambda
equal to minus 2 by 3, you see you will have an alternate optimal solution for this, for
this particular cell where did you have 2 by 3, this one.
So, this particular cell the relative price C i j bar lambda will become 0, and so it
will be a candidate for coming into the basis, so alternate optimal solution; and
similarly, for lambda equal to 0 which is here, so the when you put lambda equal to
0 this particular cell will also have its relative price as equal to 0, and so this
will be a candidate for coming into the basis.
So, you can now proceed on either side, when you put lambda equal to minus 2 by 3, this
particular variable will be a candidate for coming into the basis, you do
that, do the iteration, and then again you will get an interval for lambda, which will
be below the number; the lower bar would be less than minus 2 by 3, the upper
bar will be minus 2 by 3; and similarly, here you will get it, so then you can do the analysis
for the whole of the interval for lambda varying from minus infinity to
infinity. So, essentially, it just that the computations
are over here, one you do you have to just make an extra this thing calculation, the
dual solution has to be computed;
because you see for the basic variables, the C i j bar lambda must be 0, so what we are
doing is, we are choosing u i j v j's are that this number is also 0 and star v j
star, so that this number is also 0. So, therefore, when you combine the two things,
you get the whole thing the new relative price with respect to lambda is 0, so this the idea;
so, you do this
computation, then you compute the C i j bar, the C i j bar star, and then you just find
out the interval for lambda for which the current solution is optimal and then
you know how to proceed either side and then you can do the analysis for the whole of the
interval for lambda. So, the next topic is the bounded variable
transportation problem; and again one could skip it in the sense that, you will you have
already worked out the details for
the linear programming problem, but here again may be through an example, I will try to give
you the details here.
But before we go to the bounded transportation problem, remember I did tell you that, we
also want to look at so to find a starting before we go to bounded
variable problem, that also look at this to find a starting basic feasible solution, this
was our this thing; so, I gave you the north-west corner rule north-west corner
rule, this was the simplest one I showed you; and then the they are some many more but we
will look at so this is min-cost method, I will discuss with you in a
minute; and then the third is the Vogel's approximation method; so, let us look at min-cost
method; it is very simple, I will write over the steps here.
So, the idea here is min-cost method; so, you start with begin with all cells unallocated,
so the idea is simple; when you choose select the cell with min cost, with
minimum C i j, so out of all these C i j's you one can programming for the a nicely,
so simply we have to scan the all the cost and c which is the minimum smallest
one; then allocate as much as possible, which means that, will you have to look at the row
number and the column number as much as possible. Then cross out row or the column which has been
satisfied; and then you have to revise or update the right hand side numbers, that means,
a supply and the
demand; and so, you cross out the row or the column which has been satisfied update; and
then repeat from step 2 for the reduce matrix. So, very simple and we can quickly go through
this example, see here of course, if you have tie, you can do it arbitrarily, no problem,
and you may device your
own methods of making the tile, but remember you have to you have to cross out a row or
a column at each step, so that you end up with the m plus n minus 1
basic cells. So, let us begin with this one, though you have 1, 1 here, I will just choose
this one, and here you see the minimum of 30 and 40 is 30; so, this is it, and
what we are saying is, you have cross out this row. And now, in the reduce matrix, we
look again for the minimum cost, this one is still there, the number this has
to be updated to 10; then in this case, this is 20 and 24, so this is 20, I will allocate
here, and this was out, and this one now reduces to 4; so, keep updating the
right hand side. And now, again look for the smallest one,
so you have two of them, so I will choose this, and you can only allocate 4 units, so
this is out, and this remains this
reduces to 32; then I again have this is the smallest cost, and here I can make an allocation
of 20, so this is gone this is 14; fine, now, quickly scan where you do
not have much choice here now, and this is the only row left, and we will start with
the minimum 1 here 5, so you can make an allocation of 14, then you go to 6
here, 34 you can do I should, so this becomes how much 48; so, now you have how much now
48 means 32. So, we either mistake somewhere, because I
cannot allocate..., 32 here, but then you are left with 10 here, are the numbers came?
Just make sure, 60 and 70, 130,
34, 461, 164, and then numbers on this side, this is 120, 140, 164, so the numbers are
ok, there have we made a mistake; let us we quickly check, this is 30, so I
satisfied this demand 30, and so that made it 10, then here you satisfied this demand,
so 20, so that became 4, then I went to this one, so this one have 4.
Therefore, I put 3 here, so then 4 here, that means, so this becomes 32, this is gone, this
is..., this row is also gone, then we choose this 20, so that means, here this
20 is gone, you left with 14, so I can go up and make an allocation of 14 here; if I
do that, then this is thirty 4, so how much is that 48, so the arithmetic is wrong,
so 48 and 90, so this has to be 42. So, 42 and therefore I will allocate 32 here,
and this is 10. Now, all the rows and the columns constraints are satisfied; and you
see the thing is that, you show this
is a this is a starting feasible solution, because how many cells you have 1, 2, 3, 4,
5, 6, 7, 8, and because you were all passing out a row or a column, you will not
have a loop anywhere present in these basic cells, and so this is the basic feasible solution.
You can quickly compute the cost here; what is the cost? Quickly, 30, then 70, six fours
are 14 144, and 15 twos are 30, 0, 15 3 so 4 7, please make sure that
mathematics is 15 twos are 30, 15 threes are 45, so this is 48, then 70, and you have here
20 plus 8 28, 20 plus 8, and then finally 40; and I will tell you the reason
why I am doing it, so this is 4, and 8 12 to 1 6, 7 7 14, 14 and 822 22 and 10 32 and
36 63 3 4 8, 862 is the cost I suppose. So, this is no problem, but the only argument
against this method was that, it only works by the minimum cost, it chooses the minimum
cost cell at each iteration;
so, the omal came off with the idea is that, if this is not enough because it is possible
that you know see in a row you have to make certain allocations, because you
may have to make more than one allocation; and in that case, if the minimum is very small,
but the next minimum is very high, or the other cost are very high, then
later on you may be post make an allocation in a cell which is a very high cost.
So, this just to going by the minimum cell minimum cost cell is not enough; and so, here
upto go he suggested another method for starting or using a starting basic
feasible solution; and I will try to demonstrate somewhere, we will write down this thing that
the minimize minimum min min-cost method give me starting feasible
solution with cost 862. Let us see what Vogel's approximation method will give me; so I will
write out the steps here.
Now, this is Vogel's approximation method; min-cost, so this we will keep on record;
so, here the idea is that, of course, you begin with begin with all cells are
allocated; then you will compute for all rows and columns; compute the difference in the minimum and
next minimum or next smallest I should say next smallest
cost, make it smallest between the smallest and next smallest cost; so, against each row
and each column I will write out the difference between the smallest cost
then the next smallest. And then choose the one, so third step, so
let the row or the column with maximum difference; see, you see the logic here, you will choose
that row or column
which is maximum difference, so that whatever possible you can maximum possible you can
allocate in that row or column, so that you may not have to go to the
cell with because the next cell, since the difference will be highest among all rows
and columns. See, you at least able to here make maximum possible allocation
to a cell with minimum cost and the next highest to cell you may not have to use at all, so
this is what we it is doing, and iteratively it is ruling out; so, every time it
selects row or a column which has a maximum difference among the cost which are left out.
So, select the row or column with a maximum difference; and then you do the same thing
here, cross out a row or column which is satisfied, I am not writing the
whole thing but it is understood which is satisfied, this is satisfied; then you update
the update the right hand side; once you updated, then here you just have to
make sure that make maximum possible allocation make maximum possible allocation to see...,
what I want to say is that, if the only cell left in the row or a
column to the only cell only cell left in a row or a column, you understand; see, before
I go on to compute the differences, if its only cell present in a row or a
column and that constraints is not satisfied, then obviously you have to make an allocation
there, because the constraints have to be satisfied there that in a row or
a column.
Then you just go back, repeat update, you have to repeat the steps from a 2 onwards
with respect to the reduce matrix. So, let us now go through the Vogel's
approximation method; as we said, we first compute the differences, so there is numbers
are spend to be fine, but will manage. So, here for example, the difference is 2,
minimum smallest and next smallest; then here the difference is 3; here the difference is
1; then here the difference is 1;
and this case, for the columns, that the difference is 1 here and 2 here, and maybe I can remove
this, once we know the method I am writing here, let me just
remove this; so, here it is 2 and 4 and 6, difference is 2, this is 1, and not a very
good example for Vogel's method, but any way it will show then works.
So, maximum difference, this is 1; so, maximum difference you have to choose, you can either
go for this one or this one, so there is no problem, you can break the
tie in any way. So, suppose, I choose this row, and the smallest cost here is 2, so I
can make an allocation of 20; you might again here see for example, I could
have chosen this as a column, and then here this could have been so not a different, because
this what I have been the smallest cell and here also I would have
made an allocation of 20. Suppose, you had a choice, suppose, this number
was bigger, then I could have chosen Vogel the tie by choosing this column, because now
I would have been able
to make..., but if not necessary that it will really work; but one can have empirical rules
for breaking the tie in the Vogel's approximation method, and lot of
people have done overcome this to the able to prove the official; but the thing is that,
you cannot prove anything analytically anyway, so here I choose this, and
then I update this number which becomes 70 and this is out right.
So I cross out this column, because the column constraint has been satisfied. Now, these
numbers will change, because now we difference here will be 1, see only
the column numbers will change, sorry the row numbers, the column numbers will remain
intact, so I do not have to worry here, this will be the same, and then
here it is same. So, therefore, this is a next one; this is
the column with the highest difference between the smallest and the next smallest cost; so,
here this cell is 2, and I can
choose this to be 20, so this will get updated to 14, and this is out; so, once a row get
cross the column numbers will change, the column differences to be just have
to be careful; so, here this number will become 2, it was 1 and 3, so this is 2, why I am
looking at this? I do not have to compute for this, so we go here, because
this row has been ruled out; so, 1 and 3 this is 2 remains, 2 and 6 and 8, this remains
2, and here now the difference here is 7, because this is out so 2 and 9 the
difference is 7. And here the difference could be 5 and 8,
which is 3, so we will choose this column; and here the minimum cell is this one, I can
make an allocation of 24 here. So,
now, this is ruled out, and this gets updated to 12; so, once a row has been ruled out,
then these numbers will again change; for example, these two are there, so
this is 6 now, this is 6, here the difference is 7, because these two rows 7; and here the
difference is 6 9 and 15; and here the difference is 3; the row numbers
remain in fact, because I ruled I have crossed out the row; fine now, again this will be
the one with a maximum difference, and here the minimum cell is this, and
the allocation you can make is 34, and so this gets ruled out, and this number will
be 36 here. Take care, please careful about that, so this
is 36; now, your row numbers can change these remains same as they are; actually, if you
see that you know we are
still not in the statement a single cell is left out the row or a column these will have
to 2 2. So, now, here these numbers will change, so 1 and 8 this number is 7, 1
and 8, then 7 and 5 this is 2, and then 3 and 14, these are the only 2, I do not have
to worry about it. So 7 and 2, and here the numbers are 6 6 and
3; so, we will choose this row; and here the smallest cell is this one, and the allocation
that you can make is 40 and
30, so this will be 30 and so this gets ruled. Now, you have only three cells left, and this
one is 10, so we have no choice, but to make allocations here, because
these three column numbers are left out; and let us see they should add up to so 26 plus
10 36, this is 36, so I will make an a allocation of 10 here, 12, and 14, so
that takes care of your all the rows and the column constraints. And we can quickly compute...,
by the way this cost is 722, I had made a mistake of computing a 6
into 34 is 24 and then 6 threes are 18, so 204, I do not out 2, so this is that I cost
for the minimum cost please make the correction.
So, let now compute the cost for the Vogel's approximation method; so, cost for Vogel's
approximation method; so, this is how much? 30 plus 40 plus 70, that is
204, when 15 12 fives are 6, 60 so 0 12, 180, then 70 again, and 48, and 40; so, let us
add up the 12 1 8 9 9 7 are 16 16 eight's 24 24 and 10 34 38 8 3 5 and 6; I
suppose, this should be a case, just make sure that your solution is correct; fine,
so, 682, so there is a definitely..., this is less than 722; so, obviously, it will make
a
difference; but then again one can always choose numbers, so that we because you have
to do more work here, remember so the moments approximation method
you had; but let me point out something here, I have computed your dual solution here 2
7 6 6 5 and this, this is your dual solution. And if you verify this solution
is probably an optimal solution, quickly do it fine.
So, this is minus 4, so 3 plus minus 4 is 7; so, if we do it, this is 13 because as
0, then this is 9 and 9, so the and here it would be minus 2, so 3 this would be 3 0;
so,
alternate optimal solution possible, if this is optimal, we will just verify; then this
is 6, because 6 minus 4 is 2, and this one is here is 13, and quickly here this is
minus 1; so, this is 9, this is 4, so 5, and 1, and this is 3; you see the solution is
optimal, and their our alternate optimal solutions because you have zeros here. So,
that is... And this is why empirically people have shown
that the Vogel's method; and that is why it is called an approximation method, because
they feel that this is
definitely give you either it will give you an optimal solution or it will give you solution,
which is close to the optimal solution. And for very large transportation problems,
Vogel's approximation is the solution obtain by the Vogel's method is treated as you know
near optimal; so, when you
know very large in the sense that, you have a few thousand markets and sources, then instead
of going, so that means, we have a feeling that the difference
between the optimal solution and the solution obtain by Vogel's method is negligible then
you will go for the Vogel's method. So you do more work for the method, but then
you may get 1 also if you can spent time, you can use this as a starting feasible solution
basic feasible solution and
the simplex algorithm; then may be in a few iterations will give you the optimal solution.
So, again as I said nothing can be proved analytically, but this is all
empirical evidence to say that the thing will give you solution which is close to the optimal
solution. So, this is all about the people of try to
create data, so that you can show that Vogel's approximation method will always give you
good solution; but again one can
sit down and create the tableau or a cost structure for which it may not give you a
very good solution; if may give you as bad the solution as the matrix minimum
or the north-west corner rule, so nothing can be said, but any way I just now that you
should be familiar with the different methods of computing starting basic
feasible solution.
So, as I said the bounded variable transportation problem, again we do not have to spend much
time on it, just may be show you one or two iterations to show you
how the..., because the choices for theta will now be more than 1, so we can just revise
quickly bounded variable transportation problem. So, now, the upper bound constraint, that
means, your problem would be minimize, Z equal to summation C i j x i j or more on the arcs
subject to sigma x i j
summation j varying from 1 to m is S i i varying from 1 2 to m and summation x i j i varying
from 1 to m is your demand d j for j varying from 1 2 to n, and we
have the added constraint u i j. So, we cannot send more than u i j amount
on a... Now, you see the first thing that get and dangered is the feasibility, the existence
of a..., because once we said
that see this condition that summation S i i varying from 1 to m is summation d j j varying
from 1 to n was enough to ensure a basic feasible solution to the
transportation problem. But now you see this may be satisfied, but still it is possible,
we are upper bound constraints may be such that you see at a source I you
have S i units available, and you have all these arcs going to different markets; but
if the capacities of these markets of these arcs do not add up to S i, they are less
than S I, then you cannot send all the material from here, because you have to use these arcs
which are going to the different markets; and if these capacities are
low enough, so that they do not add up to a number S i, and I cannot use up all the
supply here; and that means, some demand will left unsatisfied, because I am
assuming the sigma S i sigma d j, so a sufficient condition for a feasible solution is....
So, that means, one can always verify, again it is not a necessary condition, it is only
a sufficient condition; so, sufficient condition for existence of a basic feasible
solution would be that, summation u i j j varying from 1 to n from the ith source to
all possible markets, this number should be greater than or equal to S i, i varying
1 to m; and similarly, for each market, for each demand point, the upper bounds on the
arcs incoming arcs should be such that they add up to more than what is
demand it at that point. So summation u i j i varying from 1 to m should
also be greater than or equal to d j, j varying from 1 2 to n; and here, let me just mention
that, the it is not
necessary see the u i j's for some arcs may be infinity, because the number the that may
be no upper bound restriction on the arc, so that is understood.
So, here u i j's may be finite or infinite numbers, but this will ensure if this summation
condition as satisfied, then you know that you will be able to find the
problem is feasible essentially. So, that takes care of the fact that, your problem
would be feasible; if you have that condition is satisfied again, it is not necessary;
now, what else? So, we need therefore, we will work with this, so working basis of m
plus n minus 1 cells. So, why? So that so you also that means, you
can always ensure a working basis of m plus n minus 1 cells, as such that the non-basic
cells are either 0 or at their
upper bound; so, their either at 0 level or at their upper bound; and so, we can always
maintain, because I prove it to you for the simplex algorithm that, you can
have m plus n minus 1 cells in the basis. But here please we do not have to go through
the so a trouble of making the transformation, because we will simply put a either and put
a square around a
non-basic cell at its upper bound, so I am saying that you put square around a non-basic
cell that its upper bound.