noc18-mg22 Lec 57-Linear Programming (Part-4)

IIT Kanpur July 201
20 followers
1 Video View·Dec 3, 2023
[Music]
so we have found the shadow price or the
dwell price of the input or resource
number one now let us also say that
these value remains constant for a
particular range of the input ones
capacity or the availability so for that
let us revisit the graph to understand
what is happening there so here as I
have already told you that if my input
or resource constraint line a B shifts
to aim in and then M prime n prime then
basically I am relaxing my constraint
and there can be another case where I
can also increase the strength in the
resource constraint by reducing the
availability of the input in that case
this line will shift backward parallel
to line m double Prime in double Prime's
so basically what I am trying to say
here is that that these movements of
this initial resource constraint for
input our resource number one which is
given by line a B is basically movements
along this input or resource constraint
line C D this is basically the resource
constraint line or boundary line for
input two so this is basically defining
the range of input one's usage within
which the shadow price or the dual price
of input one will remain constant so for
that let us have a look at a numerical
analysis okay so one can
find out the minimum input1 capacity
at Point C which is basically one corner
point in the feasible solution space
given by coordinates zero and two point
five okay so now we have to look at the
input constraint one use the technology
coefficients to write two times
key ones value is zero here plus one
times Q paws value is two point five
here at this point C so finally we get
two point five units of input ones use
right so we are done with one extreme
point C let us circle it now we move to
the other extreme point of the range in
which these movements parallel movements
of a beeline is permissible so for that
we can now talk about maximum input one
capacity at Point D so Point D is
basically given by the coordinate five
zero so now again we look at the input
constraint one so two times the value of
Q 1 which is 5 at Point D plus 1 times 0
which is the value of Q 2 at Point D so
we are talking about 10 right ok so that
means that we are talking about some
range which is given by 2 point 5 units
of
input one
and
ten units of input one
okay so if my input availability is
within two point five and ten then
basically in that range the shadow price
or the dual price will remain constant
and that is equal to 0.332 now let us
look at case number two which talks
about an increase in the availability of
resource number input number two so let
us also assume that here you hear also
the availability of resource to is
increased by only one unit so that will
have some impact on the technical
constants so let us write down the
technical change technical constants in
this case so here we will have the
technical constraints written as note
that there is no change in the first
technical constraint but there is a
change in the second technical
constraint of course I am assuming that
slack variable values are zero here at
the optimal solution so note the change
here so here earlier we had number five
so now it has gone up from five to six
so let me quickly jot down the solution
I don't want to spend a lot of time to
solve this we have already seen how to
solve so I can quickly write down
[Music]
the solutions
let us denote this by in to compare with
the old one okay so now basically we can
talk about that rate of change
as changing the z-star value divided by
the change in the availability of input
- and here in this case that is
basically equal to one point three three
four so here this is the shadow or dual
price for resource or input number two
okay so let us now move on to the case
number three of sensitivity analysis and
here we are going to study the
sensitivity of optimum solution
to a linear programming problem two
changes in the objective function
coefficient it implies unit profit in
the case of the primal problem or unit
cost in the dual problem so basically we
have to now talk about the suppose we
have this maximization type of objective
function where we have this linear
functional form
so here in the sensitivity analysis we
can also change the values of c1 and c2
to see what impact will it have on the
solution of the LP problem now to study
this case in greater detail let us take
help of an illustration that will help
us to understand this case in greater
detail so here is the hold graph that we
have used before and here is the old
maximization type problem that we have
solved before okay so here we have
already found that this point e
which is the intersection point of the
constraint for input one and two or the
boundary lines for input one and two
intersect each other and we have found
the optimum solution to be at to be
obtained at Point a and the optimum
solution was Q star 1 equal to 1 and Q
star 2 equal to 2 right so this is
basically the LP solution to this
problem
now we are going to study the
sensitivity analysis what if I say that
my net unit profit is now going to
change okay so let us start our analysis
with the objective function itself okay
so we have the objective function which
is given here now let me introduce a
concept called ISO profit line
okay so when we talk about isoprofit
line let us write the profit expression
in general terms okay so let me write c1
so the way we are writing our ISO profit
line expression we do not assume any
specific value of net unit profit p1 and
p2 so how to compute the slope of this
isoh profit line so now let us see how
this is going to be useful okay so let
us now go back to the graph so you can
see that the ISO profit line in this
case will actually pass through the
intersection point II right and that
will give the highest possible ISO
profit line that can be obtained by the
firm so let me assume that we have ISO
profit line that represents the original
profit expression so this one I am
talking about so although you know I
have not calculated the exact slope of
this ISO profit line I just you know
approximated it through this red broken
line so but note one thing that ISO
profit line so let me assume this
particular ISO profit line takes value Z
star equal to 8 if you remember that was
the initial solution right okay so now
you observe one thing that this ISO
profit line can actually tilt a little
bit around this red broken line and it
will still pass through the same point E
so let me draw one such line so I am
drawing this pink
line which is also an ISO profit line
which passes through the point E and
note that although the slope of these
new isoprofit line so this is my new ISO
profit line
new isoprofit line means that with new
set of objective function coefficients
hence the slope change so this new
isoprofit line although it has a
different slope but still it passes
through the same point E and hence the
LP solution does not change so we get
the same LP solution as we have obtained
before so which is precisely this and we
also get back the same Jetstar value
which is 8 okay but note that there is a
limit to this rotation so this rotation
of the original isoprofit line which is
given by the rate broken line is limited
by this green constraint line and the
blue constraint line so these are
basically the constraint lines
corresponding to input 1 and input 2
right so basically the change in slope
is limited and the upper limit and the
lower limit of this range is basically
dictated by the slope of these two
binding constraints line so to have some
comparison between the slopes
let us now work with the absolute values
of these slopes right so I will now just
take the mod value of all this so I will
ignore this negative sign and that
negative sign and negative sign here
okay
so basically if from the diagram I see
that my original isoprofit line which is
basically this red broken line and
changed isoprofit line which is
basically this pink line has to lie
between this input constraint lines the
green line and the blue line then that
means that this relation is valid they
have to satisfy this condition right
okay so basically what does this mean it
means that the p1 the ratio of p1 and p2
can lie between 1/2 and 2 such that any
small change in p1 and p2 which lies
within the range will have no impact on
the optimal ALP solution it will not
change the value of Q 1 star and Q 2
star and finally Z star okay so let us
talk about a simple numerical example to
understand
okay so suppose unit profit of a
commodity - is fixed at its current
level right so basically now I declare
that my p2 is 3 and that is not going to
change okay so only p1 is going to
change
so a question can be asked that how far
p1 can change so we can write
okay so how to approach this problem
easy so we have to first look at that
boundary condition
okay so we have to use this price
boundary condition in our problem so
here we know for sure that p2 will be
three so let us plug the value of p2
here so if we do so then we get this
range for p1 so if unit profit for
community one lies between 1.5 and 6
then the optimum solution to this LP
problem will not change okay so I hope
that this clarifies the sensitivity
analysis case number three which is
change in objective function coefficient
okay now we are going to give another
numerical
exercise
linear programming problem from its
Primal counterpart
pause Swampert ah so let us revisit the
same old primal problem that we had the
primal problem of a profit maximization
exercise of a farm and now let us
construct the dual LP problem from this
primal problem so this is primal now
let's have the dual of this
so duel will be a minimization exercise
and Z prime is basically a new linear
objective function which we need to
minimize now so remember that the number
of constraints in the primal problem
will be exactly equal to the number of
objective coefficients and variables in
the dual problem so here we have three
constraints so they are in the dual
problem we expect three decision
variables and three objective function
coefficients right so for each of these
inputs now we have a dual price which
will be the decision variable and the
parameters in the right-hand side of the
constraint which are basically four five
and twenty we now become the objective
function coefficients right so we write
for v1 plus 5v2
plus 20 v3 as the objective function now
let us write down the constraints so as
we know that the column vector that we
see here we will now become the row
vector right so we write 2 3 1 plus v2
plus 2 V 3 right and this sign of the
inequality will change from less than
equal to 2 greater than equal to and
this will be greater than equal to the
objective function coefficient for the
first decision variable so that is
basically two here in this case
similarly we can construct the second
constraint for the dual and this time it
will be V 1 + 2 V 2 + 5 V 3 greater than
equal to 3 right and of course needless
to say we have to have non negativity
constraints for my decision variables
which are basically the dual prices now
remember that in the previous solution
we found that our input number 3 is
somewhat special in the sense that it
has a non binding constraint
and if you remember our discussion
initial discussion on the dual price we
have said that any input which has a
non-binding constraint has zero dual
price
right why because this input is not
fully optimized so there is some surplus
left okay so if that is the case then we
know that even before we attempt to
solve the dual LP problem we know after
I that v3 is going to be equal to zero
right
so we can now simplify our dual LP
problem and rewrite it as
okay and I know I am NOT writing the Ock
well let me write so this will complete
our do a little pee problem now we will
see how graphically we can solve this
dual LP problem so of course we need to
first plot a two-dimensional solution
space where now the input prices or the
dual prices are going to be measured
along the axis so let me measure the one
the shadow price or the dual price for
input one along the horizontal axis and
v2 along the vertical axis okay so now
we need to plot the constraints right so
here first so now let us first plot the
boundary line for the constraint number
one this will be given by this green
colored straight line let me give it a
name too so a B okay now let me also
plot the boundary line for constraint
number two and now let me have this pink
line depicting that let me also name it
that we named it C and D
let me denote by CD okay fine so now
what will be the feasible region it is a
minimization problem right so basically
the firm will try to get down to ISO
cost line which is as minimum as
possible so by ISO cost line basically I
indicate to this expression Z prime this
linear function because this is
basically this can be given a cost
interpretation okay so here in this case
the feasible solution space will be
given by this shaded area
okay and note that there is an
intersection point given by say point e
and that basically satisfies both the
constraints and this is the point where
and I so cost line could be perceived
which will have the minimum possible
value okay so let me see at this point
e what would be the values of V 1 and V
2 so in other words what will be the
solution to this dual LP problem okay
fine so let me point out so this is
basically my constraint number one and
this is my constraint number two okay
and this pointy is basically my solution
to do a linear programming problem okay
so basically what we can do I mean how
to solve them numerically well I have
already ignored the third constant now I
have two constants here now I need to
use the linear form for these
constraints so basically I will have now
two V 1 plus V 2 equal to 2 and V 1 plus
2 V 2 equal to 3 so a system of
equations I get and you know that can be
easily solved so if we solve then we get
the values V 1 star equal to 0.33 3
approximately and we true start with has
a value 1 point 3 3 3 approximately so
now if I plug this V 1 star and V 2 star
in my dual objective function then I get
the optimized value of this objective
function J prime star which is 8 so I
get the same solution so this is
basically the solution to the dual
problem
[Music]
[Music]
