Lecture 08 - Resource Allocation as LP

IIT Kanpur July 201
20 followers
May 31, 2024
[Music]
[Music]
hello welcome to the lecture on linear
programming we will start by recapping
what we had done before so can you
remind me we were looking at linear
algebra right and the important things
which we want to remember is what is
linear Independence we are given a bunch
of vectors in a vector space What is
linear dependence what is linear
Independence and all of you know it
right that is fine and then once we have
this concept then we can talk about
Columns of a matrix as vectors and then
we can consider their rank which is
the independent columns number of
linearly independent columns or the
dimension of the span of those columns
or the dimension of the span of the rows
multiple ways we can say what is the
rank of a matrix right and then uh the
third thing which kind of allows us to
calculate or compute these things was
goian elimination and I think this is
this is a nice thing to know in general
not just for this course because this is
a very very strong tool it actually
tells you how your Solutions of axal to
b or axal to 0 looks
like right so what are the possibilities
for ax equal to
B there can be no solution
when will that be the case when B is not
in
the
the column space or span of The Columns
of a right otherwise there could be a
unique solution and unique solution will
happen
if rank is full rank is full rank is n
That means every Vector can be uniquely
represented as a linear combination of
my column vectors right and then if the
dimension spend is less but B is a
vector then it turns out that I will
have a large enough
space which is going to be the solution
and that can actually be described by
Godin elimination some of the variables
will be free some of them others can be
written down in terms of the free
variables right
so can you think of how the space will
look like uh can you tell me let's say
in two
Dimensions let's say I have one degree
of freedom
then my solution space will be
a point
Square line line it would be a line
right it would be a onedimensional space
that's what I want to emphasize right
it's not a set like a bounded set it is
going to be a space okay
good now I want to give you a slightly
more detailed introduction of linear
programming before we go for further we
will kind of see that this linear
algebra which we have seen is not good
enough to give us a solution we already
we need to know this but this is not
good enough for solving linear programs
okay but before that let's get
acquainted with linear programming more
okay remember I told
you the standard form
is such that
equality
constraints and X greater than equal to
zero right I told this and you accepted
it but now since you accepted it I will
ask a question what does it mean that
this is the standard
form and now I need a mathematical
definition right not the English
definition of standard that I am
familiar with
so I said standard form of L program you
said wonderful it is a standard form but
what did you get get out of it
everything can be reded into this okay
good
everything you mean to
say can
be
reduced depending on your per uh
preference
correct what does this mean
reduced you have two set of linear
programs linear program a this is an
optimization problem B there's another
optimization problem what does it mean
that a can be reduced to
B now see it's great we that is how
mathematics works right you have some
problem you formalize it and then the
next step is oh I can probably solve it
like this then you have some intuition
behind it so this is the intuition
behind it but then you need to follow
normalize it because we are
mathematicians right we are not
biologist chemist or whoever you want to
you know insult right so uh so since we
are mathematician we need to formally
make sense of of
this very good so it has to be something
like solution of
a
map to solution of B and once again you
are creating new terms and I will keep
asking what map 2 means but then we will
describe but now we getting closer and
closer right map seems much more
mathematical as compared to there is a
function or there is a process by which
I can take a solution of a and convert
it to solution of
B this was enough it was just a problem
but since this is an optimization
problem we have to take care of the is
it enough that solution of a is solution
of B
there must be a function to there is a
process let's say or a function but is
that
enough okay so yeah that will depend on
whether you want the arrow to be this
way this way or this
way but a also has an objective function
right so the solution of a should map to
the solution of B and right because why
are we doing all this the reason is that
instead of solving a we will just
solve B so somehow the idea is oh the
Optimal Solutions of a should map to
Optimal Solutions of
B and vice versa if you want to say that
they're equivalent or something right
okay good so that is the plan that's
what we want to kind of formally Define
and show that uh this is our standard
form but before before I do this I need
to talk about what could programming
B right
so linear programming is linear
constraints and linear objective
function right so it
is min / Max C transpose X such
that
all these kind of constraints could have
been possible all of
them yeah uh so they they
seem linear right and remember X greater
than equal to Z I can represent it
as this
right so these are the kind of possible
linear constraints I can
put okay and let's take some
examples okay so yes
uh uh the first example once
again would be resource
allocation and
now I write the linear
program and
you interpret it for me
okay
okay so let's say I have a linear
program like this
and X1 and X2 are the number of Dell
computers and Apple Computers you can
make
right so what what do you want X1 to be
Dell computers or Apple
computers 10 is higher than five right
so any same person will
say that apple is priced higher than
Dell right so this is the start X1 is
the number of Apple Computers you can
make X2 is the number of D computers you
can make this is
the profit you can make right and then
how do you want to interpret this your
interpretation let's see so this is not
math this is just Real World Knowledge
so what do you want let's say this
constraint to
be sorry material cost for building
which raw
material metal
okay okay so you have like uh 20 kgs of
metal are required for apple and 13 kgs
of metal required for Dell and then you
have total 95 kgs of metal okay what
about
this okay okay great so I see that some
people are not fan of Apple Computers
here and given such problem they will
only have X2 greater than zero and X1
equal to Z but uh let's say some of us
are business-minded
so uh fancy word
manpow for child
livs okay so so then uh it requires four
human beings because one for making it
at three for Designing the logo on the
top and then one for Dell uh and then we
you know we have 28 people uh in total
to work for us so if this is the case
this is basically the resource
allocation problem
right how is it
different from what you saw in the first
class mathematically remember what was
the first that was the the beer you were
supposed to make right like you had two
kind of dark and
light can you think of this uh you know
making Apple computers and Dell
computers not this linear program how is
it kind of different from that
problem which is going to make a lot of
difference as a linear
program
so here I would want X1 and X2 to be
very
good okay so in a sense the real life
problem is not a linear programming
problem okay so I'm not putting this
constraint so that's why this is almost
an approximate version of the problem I
wanted to
solve okay and the comment I want to
make here is that this is not an easy
constraint to
put this makes our life very very
difficult there are integer linear
programs there are just integer programs
and there are a lot of heuristics but we
don't have any nice way to solve integer
programs and actually many of the very
difficult problems as a computer sence
scientist would call them
NP heart problems can be formulated as
integer programming
problems okay so this is the first time
which I'm telling you I will probably
tell you more anytime you have this kind
of constraint in your Con in your
optimation problem kind of in
trouble we will see in many cases we can
still find an approximate solution this
would be one of the application I will
show to you but in general this makes
life difficult yes yeah so what you are
saying is that uh you solve this program
your X1 would be let's say 13.5 X2 would
be 12 uh .1 and you will say that oh 13
and 12 is the
answer but what if 1411 was the
answer what you have shown is that 13.5
and 12.1 you get the best solution of
this but it has not shown that the floor
is the best possibility so in that case
your point would be
you would say that oh it's at least
approximately correct so whatever is my
optimal you are not far away from it and
this will probably work in this case but
many of times you will have such program
and X1 X2 will just have a choice to be
either zero or
one and then rounding is going to make a
l lot of effect right if your only
choice is that you know uh think
of this constraint
as compared to this
constraint and suddenly rounding does
not seem like a great option and most of
these NP hard problems I was talking
about you have this kind of a
constraint okay and then does this uh
floor or ceiling or what we call
sometimes uh rounding work or not that's
a question in
itself
okay
cool okay
so for now we can assume
that we can make 13.5 Apple computers or
12.1 Dell computers okay and let's
generalize
this what do I mean by generalizing this
uh you can have so this is just to take
more and more examples of linear program
that's why I'm generalizing this I can
say that uh I have this rowy as
the market
cost of
uh yeah so let's say uh this will
index my uh
output so like in this case I will go
for from uh one and two uh one is Apple
two is Del
and J will be the raw
material right it will index the raw
material so then roow I is
the price of
IET uh
output gamma J is the
cost of jth raw
material
AIG J is
uh amount of
J needed
for one unit of
I and BJ is
the
inventory
limit for
G right okay can you write the linear
program now for the resource allocation
problem men or
Max
it's not exactly the resource allocation
problem which I had done before it has
one extra thing right so take care of it
it's not hard but yeah what is
extra
yes
this summation is
over so this is
saying use
of
so what will come
here yeah that's RI for
me summation
over summation
over
correct great right this is completely
fine
okay and now this will the first example
of converting into an equivalent program
which is the simplest thing I will just
say this is
CI sounds
good now you have the same
data and it can be interpreted in a
totally different
way
okay what is the problem
now cost of inventory okay what do I
mean by
that suppose this information is given
to you
okay and as the manager of the
inventory you want to assign a price to
whatever you
have and you want to minimize the total
price okay
but if you just want to minimize it you
will say everything is zero but
obviously if you make the price to be
too small you should be willing to sell
it in the Market at that
price
okay you understand and then the
competitor should not have any
advantage by buying from you instead of
the
market clear the minimizing the cost of
inventory uh think of it as you are the
manager and you want to say that for the
other way to say it is for whatever
production you want to do this is the
minimum cost I'm keeping this is the
minimum inventory cost I'm keeping
keeping you want to justify to your boss
why do you have this much inventory so
you're saying that the its expected cost
is actually the
minimum that's one way to think about it
okay so now if this is the case can you
write the linear program corresponding
to this
problem right so again what do you want
to
do uh objective is to assign
cost
YJ to each raw
material right
and when you do it what will be the cost
of your
inventory if YJ is the cost of each raw
material of one
unit you want to
minimize
sorry a
no there is no AIG here what is the cost
of inventory if one
unit uh uh the cost you're assigning as
YJ how much J do you
have BJ
right B
okay such that can your cost be less
than gamma uh gamma
J no if your cost is less than GMA J
then competitor will buy directly the
raw material from you instead of from
the
market this is not a very interesting
constraint what is the other interesting
constraint what can computer do they can
buy the raw material from you and build
the product
tie right so what should be the
constraint corresponding to that we
should not make sure that we are giving
added advantage to the
competitor what should be greater than
to sorry outut be yes good good so what
is the mathematics what is the
equation
summation over summation over J and this
is there for all the
products
okay and again we can do a slightly
non-trivial uh equ valence here we can
say that that
ZJ is YJ minus
G
remember CI was Roi
minus the cost of making uh product ey
right so this was in some sense The
Profit okay and even though I haven't
formally defined what reduced
means what equivalence means you are
still fine with the
substitution and actually should also be
fine if I just cancel this
term because optimizing this is same as
optimizing this program with some
constant attached to
it
clear so one step is yeah this inventory
value of inventory problem is not that
natural but if you take the leap then
this is the linear
program and so that that should be clear
to you but they should be absolutely
clear how this and this program are
equivalent in the sense at this point I
would just say that if I wanted to solve
this instead I will just solve
this and the advantages is that this is
much closer to
the
uh standard form than before
right gamma J is the market price and
why is is the actual price which you
suppose for you what is the cost of the
material right so you want to say that
oh even in the market it is 10 uh rupees
per but for me its value is 12 rupees or
something
so that's why there are two different YJ
is the variable gamma J is the fixed
market
cost does that answer your question
okay and now you saw same data but two
different linear
programs okay and to now advertise this
course in few weeks you will
see
that
what it means is that the best possible
profit you can make is going to be equal
to the minimum possible cost of your
inventory and I'm sure at this point you
don't see it right this seems like two
different problems but this is the in
some sense the power of linear program
we will see that how this optimization
problem and this optimization problem
are intrinsically
related and we will mathematically be
able to prove that yes uh the maximum
profit you can make should in some sense
be equal to
the uh imagined cost of my
inventory and this uh will be shown but
in few weeks and again if someone asks
me this is my favorite concept and I
will keep highlighting it and you will
see the power of dity again and again in
this
[Music]
course
[Music]
[Music]
