noc19-mg45-lec23

IIT Kanpur July 201
20 followers
2 Video Views·Dec 3, 2023
[Music]
[Music]
welcome back my dear friends a very good
morning good afternoon good evening
wherever you are in this part of the
globe and as you know this is the da dm3
course which is data analysis and
decision-making three cores under and
Patil MOOC series and as you know this
da DM 3 course like dat m1 and the idiom
to this total duration is spread over 12
weeks and as you can see we are in the
fifth week 23rd lecture which is with
the third lecture in the fifth week and
this total contact Nam number of us for
this day DM 3 like dat em1 and em2 is
4:30 hours which when converted into
number of lectures is 60 because each
lecture is for half an hour and each
week considering this is the fifth week
we are already finish fourth week that
means four weeks so each week we have
five lectures of half an hour each and
after each week we have an assignment so
you have already completed four
assignments and we are with the 23rd
24th and 25th lecture you will go and
take the the fifth assignment and after
the whole course you will basically take
the final examination so if you remember
we are discussing about the simple
simplex method and I gave you how the
solution basically changes depending on
the entering and exiting variables
depending on whether you are trying to
do the maximization problem of the
minimization problem and based on that
decision like for the maximization
problem you bring everything on to the
right I would be repeating many things
time and again please bear with me so
you take the maximum in the negative
sense because it's you have brought onto
the right hand side that will be the
entering one depending on the fact that
it will increase the objective function
maximization to the maximum degree or
maximum quantum and that would be signal
become the pivot column
based on which you rotate rotate or
basically do the conversion and the
pivot row would with the one for that
variable which will leave the system
such that in the maximization problem
the decrease in the objective function
would be the least
hence we take the ratio on the
right-hand side which is the B value
I'll always consider that as the B value
we may trim a vector divided by its
corresponding coefficient that is the
unit based on width B divided by its
corresponding cell will give me per unit
reduction in the objective value if it's
a maximization problem and that would be
the exiting one exists a exiting one and
if there are more than two contenders
for the entering one you will take both
of them but also consider that the ratio
for which its minimum for the exiting
one's if one we can find out which
minimum we will take that if both of
them are the same then obviously you
have to basically use one of them but
intuitively it means that there are two
different corner points depending on
which you will get the maximization
concept we continue doing this absorbing
the fact that the the the base of the
matrix corresponding to the basic
variables which are there on the
leftmost column those corresponding cell
values would be one rest would be zero
such that when you put the basic
solution to the one value which you have
on the right-hand side that will give
you those exact solutions as that
putting them in an objective function
whether there's a slack or the surplus
or the actual variables will give you
the objective function maximum so we saw
that it it changed in our last example
we changed from zero to 30 from 30 to 36
and after 36 obviously any negative
values for the entering variables were
not there so here to basically stop
there and the minimization problem
obviously when I talk about the
minimization is just the reverse
that means if it's the minimization one
you are trying to basically find out
that the fall that the decrease in the
objective function
to happen the highest increasing
whatever it is and exiting one would
also be considered likewise and again
contenders for for two more two or more
points which are again telling and
exiting would be basically be clarified
that as at the two corner points you can
have same solution for two different
values of the corner points and for the
unboundedness we discussed that as you
keep changing the entering and exiting
ones the world would be not going out of
those x1 x2 x3 x4 whatever these
variables are depending on how many
slacks and surplus which you have and
how many actual real variables which you
have but the Z value will be unbounded
it will keep increasing for the
optimization problem if this
maximization and in the case if it is
minimization it keep decreasing so you
are discussing in the last day on the 26
second lecture so what is the directions
we considered so directions obviously
what I have been discussing after Ivan
again are the same thing which have been
detained inwards so the simplex
directions are constructed by increasing
the simp single non-basic solution now
remember the point important fact is
that it has to be a basic feasible
solution feasibility is very important
because if you find out the constraints
and the point satisfying is one of the
point which is actually plausible but it
is not inside the feasible region then
it doesn't make any sense in trying to
solve it and we have considered very
simple simple examples earlier the
single non basic variable leaving would
be leaving such that other non basic
solutions basic variables remain
unchanged so which is very important
because when you are changing from one
corner point to the other we are only
considering that there is a change of
one variable at a time because the
movements would be happening in such a
way that you would consider the
movements taking place that if in the
tableau if you saw so there was only one
very
which is entering so one enters
obviously to push out the other so that
would be only single one so the movement
of the corner points are such that there
is only one change which is happening in
the variables 0.15 number two you should
also remember that when we are
considering the entering in the existing
ones we are considering the simple
concept as I mentioned is dy DX will
take in the maximum on the minimum
direction depending on whether it's a
maximization problem and the
minimization problem but this D by DX I
didn't specify it should be the del Y
del X that is the partial
differentiation based on the fact that
when we change one of the variables with
respect to the others being kept fixed
we are trying to find out the rate of
change of the objective function which
is the maximization on the minimization
problem based on only one change that
means one basic one variable comes in
another variable goes out we are not
going to consider more than one in the
simplex method so that is very important
so here the point it mentions the
simplex direction are constructed by
increasing a single non-basic variable
which was not there in the basic
obviously it will one will be go coming
inside a one would be going out such
that other non-basic would be kept
unchanged because they keep changing
obviously you cannot find out in which
direction the rate of change is the
maximum of the minimum for the problem
of optimization and will compute the
unique corresponding change in the basic
variables as we did like x1 comes x3
goes out or x3 comes x4 goes out
whatever it is irrespective of the fact
whether X 1 X 2 X 3 are the slack or the
the surplus or the actual variables
whatever it is that would depend on how
the problem construction and how the
process procedure of solving the problem
occurs so the corresponding change in
the basic very basic variables would be
necessary to preserve the Equality
constraint because remember when we have
constructed the tableau the tableau has
been constructed in such a way that
additional sub
traction plus or a minus whatever if we
have put for the slack and surplus have
been done in such a way the Equality
sign holds for the right-hand side which
is the B values so if somebody is
entering somebody is is going out that
equality is always preserved if not what
the problem is if you remember in the
last class I mentioned that the values
of nth any stage when you stop you take
a snapshot the variables which are there
on the left hand side these are the
corresponding coordinates for that
corner point so when you equate them to
the right hand side which is B
corresponding to the fact that you have
obtained the identity matrix
corresponding to those X values only
equality sign would mean that those are
the exact values of XS such that when
you put them and find out an objective
function they would give you the exact
value of the objective function at that
point
so as you keep moving the equality sign
is it holds always and the new sets of
X's would be given by the new sets of
B's each you have once you find out this
X's you put them in the objective
function you have already got the
objective function which is maximization
and minimization as it is and then you
decide whether you want to proceed or
stop if no component is negative in
improving the simplex variable concept
which is true well you because you are
bringing from the left-hand side
add the current basic solution and the
solution can be if if if then non
negative ones are not there and if you
think that the sign is not changing and
one would always enter and one will
always go out and if this cycle
continues based on the fact that the
objective function will keep increasing
which means that you are slowly tending
to move more inside the first quadrant
away from point zero says that you would
not have any unique solution it will be
an unbounded one just reverse the
concept if you go into the third
quadrant or you basically I am trying to
solve the problem considering the dual
problem you will also see that as you
keep increasing or decreasing as the
case may be the objective function would
become more and more negative hence the
minimization problem would basically
mean that you basically go to minus
infinity
now the simplex method for for the
initialize the the whole overall
algorithm works very simply what I have
been talking about is in words I'll just
mention them in a step wise formula
formulation so whatever I discuss is
just a formalization of the the
procedure how you proceed
so we'll initialize so what you want to
initialize is that you want to find a
point from where you want to start so
what is that point that is a basic
feasible solution which I told that in
many of the cases is the point 0 based
on which you can proceed provided it is
feasible
so in initialization choose any static
feasible basis and construct the basic
solution X naught which is that
iteration point the stat t is equal to 0
considering that you are starting your
overall process at t is equal to 0 and
set the index at t is equal to 0 and
then move so T is just a counter it's
nothing to do with time so you will
basically change so as you're moving
along the counter around the corner
points T will change from 1 to 2 2 to 3
and so on and so forth so the simplex
Direction walkers like this construct
the simplex direction in which direction
you will move associated with here the
important point is associated with
increasing each non-basic variables and
compute the corresponding reduced cost
so deduced cost in the sense that you
will try to find out that as you're
moving remember one thing this is
important as you are moving you are
trying to move in the maximum possible
direction now the maximum possible
direction would always be where the del
Y del X or del F del X F is the
objective function X is basically any
one of the XS based on which you will
proceed is basically maximum or minimum
depending on how you are looking at the
problem for the maximization problem the
minimization problem so as that occurs
when you go to the next point the
content does or do dy/dx would
definitely be there in any one of these
X's but the rate of change of the
would now basically be increasing as an
adult as a decreasing rate so basically
you are trying to slowly reach the
objective function which is maximization
so you'll keep increasing in this but
the rate of change of this this equation
would happen at a slow rate now here
I'll just step aside and and tell a few
facts about about the initial assumption
which you took if you remember in linear
programming we assume that there is a
linearity in the addition and
subtraction of the object of the
variables that means one unit increase
one unit decrease in the variables XS
whatever the X is when I'd mentioned the
word X's or or B or or the Y's when it
is a dual problem remember I am talking
about the vectors because X is a set of
vectors similarly Y similarly B or a is
a matrix so any addition or subtraction
of any one of the X would always keep
increasing or decreasing your objective
function for the same common terms that
means in general we are not considering
or decreasing returns to scale or
increasing return to scale as there may
be the cases in one of the method which
is de a data envelope analysis which we
have considered a long time back in in
da DM to so as we construct the simple
rate and the simplex direction
associated with increasing each
non-basic variable then we will compute
the corresponding reduced cost and
produce in the direction where the
increase or decrease is happening in the
most of the minimum now you want to
check the optimality so if no simplex
direction in the direction where we are
moving is improving that means it is not
giving us a higher value of Y or Z as
the objective function that means you
remember we took the value of 30 then
increase to 36 now after 36 if you saw
technically there was no entering
variable consider that we do not
consider we ignore that we forcefully
bring one of them into the as the basic
solution and forcefully take one out out
in the basic solution which is
team on at the point of 36 say for
example be forced will you bring one and
forcefully take out one the result would
be 0.1 the objective function will
decrease from 36 point one point number
two that it would be in the case that
the slacks and the surplus which could
have been zero in in the actual
theoretical sense would now no more be
zero because they would be some extra
amount for either production plant one
or plant two or plant three or machine
one machine - however the problem has
been framed with the constants there
would be some extra amount clay for six
extra one has not been utilized or Italy
still to be unenclosed so those would be
coming into the picture because in that
case the variables based on which you
want to optimize would not reach their
actual maximum value in order to give
you the maximization of the minimization
problem so if no simply simplex
direction is improving for a
maximization on the minimization problem
then you'll stop you won't proceed
further else improving simple in the
simplex direction till it is possible
you will continue so you will check if
it does improve continue improving find
out the X at the point one means the
vector find out Z now after your final
set go to the tableau double check is
there any entering is there an exiting
answer is yes do that find out the value
of Z but obviously unboundedness and all
these things properties would be checked
but it will continue doing that till you
reach the unique solution stop it
step size if there is no limit on the
feasible moves in the simplest direction
which is important because in which
direction you will keep moving that is
not being given by the in the tableau
final W which you get so each time you
have some negative values in these in
the topmost 0th equation and it says
that somebody should enter somebody
should go out so if the keep keeps
happening you will find out the
variables basics variables and the
optimal case there is no optimality here
so the
rotation or the change of these
variables will be happening time and
again which will point to the fact that
your objective function will keep
increasing or T keep decreasing
depending on the maximization of the
minimization problem so it says that if
there is no limit on feasible moves in
the Assembly's direction then stop at
the solution is unbounded both in the
negative cells and the partitions else
choose the leaving variable and then
trading one and basically repeat the
process accordingly now we will consider
that if they are with lower bounds and
upper bounds so if you remember in the
initial case of the maximization minimum
dimension problem we had the example
where X was overall greater than zero so
which means that if you consider the
minimization and maximization bounds so
here the problem is like this you want
to minimize or maximize CX why I am
saying CX these are all vectors or
matrices that's why they are bold so if
I consider CX CX is basically I'd use so
this is c1 x1 plus dot dot please CN xn
and here we are considering because as
there is equally design we are
considering the slacks and surpluses are
all subsumed in this equation so it may
be possible out to this n n is 20
considered so the first 10 are the
actual variables while the next 10 like
11 12 13 14 15 out of the twenty fives
are all slacks and 16 17 18 19 20 out of
the surfaces so all these are subsumed
here now why this is equal to sign
because the moment I said that all are
subsumed in this equation it means that
even if whichever it is let me use so
even if they were this so these are bold
remember a and exit volt or this so all
of them any converted using the slacks
and the surfaces to the Equality sign so
you have now a x1 is greater than is
equal to B and
a ax is equal to B depending on slacks
and surpasses how they have been added
so obviously it would mean that the
matrix of size a is M cross n where the
rank would be the minimum of M and M and
we are taking the column operation
according me so rank is the lower on one
of the minimum of them and if you
remember and if you remember you had XS
greater than zero so now here basically
X's are between Ln u lower bound and
upper bound so obviously X 1 okay if I
write it here so this would be a 1 1
till a 1 in a M 1 M into X which is
there are n number of variables of s T
so you ought to need multiply that is
equal to 2
initially what was that M cross n for a
and n cross 1 for X so m cross n into n
cross 1 would give you m'kraan for B so
the matrix multiplication is valid now
if I look at the bounds so the bounds
are like this technically we already had
all greater than equal to 0 so what we
now actually have is L 1 is for the
first one L 2 is for the second one
seemingly last one all these things what
basically is given by the equation yeah
so what can be the plausible formulation
like say for example you are in a
factory and it says that in in in the
factory your total number of production
of X even if the constants are such that
you cannot produce more than 20 of the
first paint and then the first print has
to be produced in in in quantum of
minimum of five that means five liters
five turns five hundred thousand liters
whatever the case be you have to produce
for the paint one in the in the paint
manufacturing process and you cannot
move reduce more than say for example
ten tons or ten thousand liters or
whatever it is for paint one also so in
that case x1 which is the very well for
paint one would be bounded between five
and ten so it will be X 1 is greater
than equal to 5 is less than equal to 10
similarly you will have for paint to
paint 3 so N and so on depending on that
you can have the constraints also so now
the simplex method with the lower and
the upper amount so in the
initialization choose any starting
feasible basic solutions with initial
non-basic solution for the upper and
lower bounds so you will basically
consider the upper and lower bounds in
such a way so that they would be
asically give you the feasible solution
that means what you are doing is that
you would have the feasible set which is
fine but you chose choose the the upper
and lower bound and or you consider the
upper and lower bound in a sense that
they would be one of the sets in the as
the starting basic feasible solution
because obviously if it is a content if
it is a basic physics position it may be
possibility is the optimum solution now
you will consider the basic of the
current presentation to find out the
direction of the movement so the pricing
would basic this pricing is that as you
bring you on to the left hand side the
positive value on the name
the value would give you the overall
importance so the optimality so if new
or no improvement and the rule is found
then you will stop the iteration process
else you will choose the entering
non-basic video so again the same
concept they would be entering non-basic
it will throw out one or push out one of
the basic exiting existing one and
replace the entering one replaced the
exiting one and that will become the new
basic solution and then you find out the
values of B would be recalculated using
the pivot column pivot row the pivot
cell based on H you you do the
transformation as you are doing that
your 0th equation which is corresponding
to the Z value for the minimization or
if it is W for the maximum Z value for
the maximization and if it is W for the
minimization you will recalculate it and
do the calculations again so if no
improvement rule is found then stop else
choose the entering basic feasible basic
non-basic variable and decide on exiting
variable based on the rule of
maximization and minimization you
continue that you will construct the
direction in the simplex using the
representation as you have done it so
you will basically consider entering
exiting and entering is itting but also
consider that at what point you will
stop that will be dictated by the
entering and exiting one whether they
are actually feasible because there is
no non negative one then obviously to
mean in the case of maximization there
is no one who would replace any one of
the basic variables in order to improve
the objective function you will
determine the maximum and maximum
feasible step as allowed for
maximization and minimization in the
same way find out the rate of change of
the function again remember it is del y
del X del F del X so X is basically the
vector you will consider del Y del X 1
del y del X 2 del Y del X 3 del Y del
Del X n and change check the one for
which the rate of of the increase of the
function the maximum that's why you are
taking the value of the minus negative
being possible because if you
keep all of the other variable fixed
then you will try to find out that as
one unit of x1 or x2 or x3 changes what
is the additional profit which is going
to come to the objective function by
what unit it will change so that is
given by by the value of 5 or 3 whatever
was there in the maximization problem so
we will determine the maximum feasible
step as allowed for the maximization and
minimization and continue considering
the exiting ones based on the fact that
which one will live so that will leave
which will basically bring down an
object function the least if it is an
optimization maximization case you will
compute the new solution based on the
change in the objective function for the
maximization and minimization and you
will keep computing it in the same way
as you did for the tableau you'll keep
computing it till it is possible to
consider that there is one entering and
one exiting variables but obviously look
into the fact that entering and exiting
are not happening in such a way that
your actual objective function is
unbounded and obviously in that case it
unbounded means that you will keep
increasing till infinity both in the
positive sense or the negative sense now
this generic optimization problem I have
already stated I'll state this in very
simple terms so here the reason why I am
stating is that in all of the problems I
have been stating that the this
parameters based on which you are trying
to optimize are fixed but they need not
be if they are not faced which is what
your constraints may change like say for
example if you consider a machine 1 your
actual utilization is 8 hours so what if
it becomes 9 hours so if it is
deterministic we solve the problem a lot
accordingly if it is non deterministic
we will solve the problem in a like face
manner so again I'll state you have an
optimization problem with repetition of
one only if I is one in the first set
you have a deterministic one second set
you have a probabilistic one and we will
consider the solution in such a way that
it will be it will be possible for us to
find out the concept of the shadow
prices and the slacks and the surface in
such a way that we can comment
intelligently what is going on in the
simplex method with this I had closed
this twenty third lecture and continued
more discussion along the process as you
proceed for the simplex method have a
nice day and thank you very much
[Music]
[Music]
[Music]
