Lecture 01 - Linear Programming, an Example

IIT Kanpur July 201
20 followers
1 Video View·May 31, 2024
[Music]
[Music]
hello welcome to the course on linear
programming and its applications to
computer science this is the first
lecture I am your instructor rajat mital
the TA for this course is tufan
mahapatra let's talk about some basic
things for this course to start
with first thing
is the way to Communication in this
course will be through the NP
portal please remember during this
course you might have multiple doubts
all these doubts might be the doubts for
other students also so feel free to ask
your questions on nptel Portal this way
in one go we can answer questions of
many of you so please ask questions on
nptel
Portal second
thing we will be giving
you weekly
assignments I think they are very
important please make sure that you do
it on time this will keep a check on
your progress in the course if you are
uh if you are not able to solve these
weekly assignments please ask questions
the NP portal let us know so that we can
help you
out there will be a final exam in April
uh people who have registered for this
exam will have to give this exam and we
can talk about it more later but these
are the ways in which you will be
evaluated and for any communication
the communication would be done through
the NP
portal so with these uh small procedural
things lined out let's get
started today is the first lecture I
want to keep it light and I want to talk
about what is linear programming or give
an
introduction to the primary personality
in this course what it means is we are
going to answer three things
what
why and
how anytime we see a new thing these are
the three questions generally which come
to our mind what why and how so we want
to
answer what is linear
programming
why should we learn
it and finally how are we going to learn
it the plan for today is to answer these
three
questions to start with the first
question
uh the formal definition will say that
this
is a class
of optimization
problems
where
constraints
and objective function is linear
this would be the formal definition of
linear programming but this is pretty
loaded there are a lot of words here
which you wouldn't understand so let's
not worry about
it I would say let us start with an
example the good thing is that you might
have already seen this example before in
your high school we will just see how it
relates to the entire theory of linear
programming so uh the example I'm going
to take is a
is is from
this category of problems called
resource allocation problems the
particular example I'm taking
is taken from the course
notes by Robert set quick from Princeton
University
let's talk about this example uh think
of yourself as an owner of a brewery
okay so your Brewery can make two kind
of
beers it can make
either a dark
beer or a light
beer it turns out
these two kind of beers need different
kind of resources to be made okay so
generally uh beer let's say needs three
components
corn
hop and
barley to make 1 liter of dark beer I
need 5 kg of
corn 4 G of hop and 35
kges of
barley on the other side if I want to
make light
beer it requires 15 kg of
corn 4 kg of hop and 20 kg of bar okay
so I can write the units here but
they're not going to be very useful I
will keep them in the same unit
everywhere and it turns out
that in terms of profit a dark beer
gives you 15 rupees for per liter and
the light beer gives you 20
rupees so uh this is clear we have we
can make two kind of beers dark or light
the dark beer requires corn hop barley
in this much amount Light beer requires
them in a different amount and the
profit from these two are
different also we have our
inventory the inventory
has 480 kgs of
corn 160
G of hop
and 90 kg of
obviously as a businessman you want to
maximize your profit right so the
question becomes if this is how much the
amount of corn hop barley you need for
dark and Light beer and this is the
profit how to utilize your your
inventory in the most profitable way
this is the
question I will let you stare at it for
a while but you can realize that this is
a pretty common problem this this could
arise in almost any
industry where you have some resources
there are some constraints over how much
resources you can use and you want to go
into the most profitable
situation
right how would we want to solve
it now let's see one of the situation
could be that we say that let's try and
see if we just make dark
beer right how much profit can we can we
have if we just focus on making dark
beer it turns out that if you're going
to make the dark beer baray is going to
be the bottleneck that means baray will
run out the first it turns
out for dark beer we can make only 34 L
of it because after making 34 L barley
will run out and this will amount to the
profit of uh
34 into 15 which is 510
rupees right this is if you are only
making dark beer if you were making
light beer then it will turn out that we
are going to finish corn the
first so if we make
the light beer we can make only 32 L of
it
because corn will be the bottleneck
after 32 uh kgs of uh 32 L of Light beer
my corn will get
over my profit will be 32 into
20 640
rupees okay
so if we make just dark beer we get a
profit of 510 rupees if you make just
Light beer
we take make a profit of 640 rupees and
you might feel that making light beer is
the
best but what about a combination can we
do better can it happen that you know in
this case corn is running out and making
light beer in making a dark beer barley
is running out can we make a combination
so that we can make more F so to
actually solve the question we have to
ask a harder
question
is there a
combination which gives more
profit right and it indeed does it it's
actually very easy to see suppose in the
light beer I'm only going to make 31 l
of Light
beer that will free up 50 15 kg of
corn 1 lit less so I will I will have 15
kg of corns free this will allow me to
make three more liters of dark
beer so then you will actually see that
I can also make you can check yourself
but you can make 31 l of Light
beer and 3 lit of dark
beer and this will give you much more
profit than
640 right so this will give you 620 + 45
this will give you 665 rupees of
profit so it is indeed true that there
are combinations of these which can give
me more profit but is this the
best probably we can make 20 L of Light
beer and more dark beer and get more
profit where to
stop right so to answer this question we
will go into the mathematics of it and
this is something which you have seen in
even high school let's write it as a
system of
equations so let's
say X and Y are two variables which
denote how much dark and Light beer we
want to
make so let's say this is
the amount of dark beer in liter and
this is the amount
of
light now these three numbers will give
a constraint on how much X and Y we can
build
obviously in terms of
con 5x + 15 y should be less than 480
this is the constraint imposed by cor
because we have
480 kgs of corn 5 * number of uh a liter
of dark beer times 5 plus number of
Light beer time 15 this is the amount of
cor we will spend and the amount of cor
spent should be less than 480
GS
similarly 4x + 4 y should be less than
160
G
this is the amount of
hop and for the last one B will
say
35x
+ 20
y should be less than 11
190
and then the amount of
profit is
15x +
2 okay great now we have been able to
formulate our problem in terms of
variables as a mathematical equation
what is our problem we want to make sure
that our X and Y satisfy these
conditions
look at all X and Y which satisfy these
conditions such
that this quantity is
maximum so we want
to maximize this
quantity though we have forgotten a
small
thing if you think about it we have
another constraint the simple constraint
says that X and Y both should be
positive
numbers because X is the amount of dark
beer I cannot make min-2 L of dark beer
so
then I should say x and y greater than
equal to
zero let's say this is my set of
constraints
now the problem is quite clear
mathematically we want to maximize 15x +
20 y such that it satisfies these four
equations look at all possible X and Y
in this world which satisfy these
equations and we ask which of that X and
Y actually maximizes this
profit
how should we solve
this given your background in these
equations you remember that we can plot
these
equations on a
plane so let's plot these equations on a
plane and see if we can get an
answer
in this two- dimensional plane let's say
x
is should I say sorry Y and X remember
this is the amount of dark beer we are
making this is the amount
of light we are
making and actually uh these meanings
are not really important right now the
only thing which is important to us
is
how to
maximize 15x + 20 y such that these
equations are satisfied their internal
me meaning of what is X what is y why is
this equation there we can forget about
it so if we concentrate on solving these
equations then let's see how does this
equation look like on this
diagram we have done this before you
have seen how to draw this equation
before so the first equation can be
simplified to be x + 3 y less than equal
to 96 I first draw the
line x + 3 y = 9
okay if I write this 9 x + 3 y =
96 You observe that everything in this
part everything below this line
satisfies our first
constraint so that means we are looking
at all X and y's which lie below this
line that is is great we can write other
equations also
again this is x + y less than
40 which looks
like this so this
is x + y less than equal to 40 and the
last equation
becomes
7 x + 4
y =
238 I can plot all these lines and I
know that I'm interested in X and y's
which fall below these
lines but obviously X and Y are positive
should so they should lie in the what we
call as the first quadrant that means in
this space so everything in this
quadrant which is lying below all these
lines that's easy to
identify that is this
area so at least geometrically our
problem becomes slightly
simpler look at all X comma
y in the in the Shaded
region find
point
where
20
Y is
maximum so you see that we had a word
problem we first converted it into a set
of
equations once we converted into a set
of equations we can draw it and now we
have a geometric picture what we want to
do is look at all X and
Y in this region and
ask where is this quantity
maximum this is interesting how should
we find this
out there are a few key observations
which will really help us out so uh
please pay
attention look at 15x + 20 Y in itself
the value of the profit gives me an
equation right so I can think of what
are the points where 15x + 20 Y is equal
to 0 what are the points where
15x + 20 Y is equal to 5 is equal to 100
so on and so forth
right it's easy to see 15x + 20 y = 0 is
a line like
this because it has to pass through the
origin with a certain slope
my uh diagrams are not really accurate
but they are just to give you an idea of
how we will proceed towards the solution
and now you will notice that as I move
this
line uh as I draw a parallel line to it
my value of 15x + 20 y
increases so this was the line at the
origin if I move it like this its value
increases
it will probably be 15x + 20 y = 90 or
something if on the contrary if you move
on this side keeping the line parallel
the line uh the 15x + 20 y will become
negative as tan mentioned so great now
we are one more step uh ahead in our
solution we had this region where we
want to find the
solution this line line when it moves up
it increases the profit this line when
it moves down it decreases the
profit what do you want to
do how far can we move this line such
that it still intersects our
region that will be the answer to our
problem so not notice that this is a
continuous region so what we will do is
we will start moving this line up until
it keeps intersecting with our feasible
region when it stops intersecting or
when when it's the last time and it has
an intersection with that feasible
region that's the maximum
profit so let me just write this
observation because this is kind of an
important
observation move line 15 + x + 2
y first
quadrant up
till it
has at least one point
of
intersection
good the thing now to notice and which
is again a very very important
observation is that at the point when
this line leaves this area it will be
intersecting with the one of the points
which we call the
vertex of this
area when you move the line it cannot
leave where it is just intersecting with
any other internal point it will only
leave with a when it is leaving a Vertex
so that
means we
notice the line leaves the feasible
region at a
vertex and my claim is we are done now
we have solved our problem
how previously we wanted to find out
among all such points which one is the
which is the point which maximizes 15x +
20 y we had infinite points here and you
want to figure out where is 15x + 20 y
maximum but by noticing the geometry of
the solution we realized that the
maximum has to lie at one of these Five
Points
and this observation is critical not
just for this problem but for solving
such problems in
general the best point where the profit
is
maximized is one of the
vertices of
the shaded
region once you notice this your problem
is simple you have equation of these
lines you can find all these Five
Points just calculate the profit at all
these five points and compare now it is
very
easy
they are intersection of our
constraints so they are easy to
find compare their
profit and actually you can ignore this
point you would know that the maximum
won't lie
here this is I think I can leave it as
an exercise for you if you do do this
exercise you will find out
that x = 12 and Y is equal 28 is going
to be one of the
vertices and in this case your profit
will be much higher than 510 or 7 6 uh
40 it is going to
be 740
rupees remember if you were only making
dark beer we were making 510 rupees of
profit you were making only light beer
we were making
640 uh rupees profit But Here We Get
Much More Much More
profit and again this was uh possible we
were able to find this because we had
this nice geometry we had this nice
observation that the best solution will
be on one of the vertices and you can
calculate this vertex
this
is generally called The graphical
method to solve linear
program before I erase this figure let
me ask you a
question is the best solution always
unique
here we would we we can see that there
is only one vertex where the leaving
line will touch the feasible region
so it will
be like this and there is only one point
of intersection when my line leaves the
feasible region is that always true so
as Tuan said this is not necessary it
might happen that the feasible
region was like
this and my leaving
line would have looked like this in that
case every point on this would have been
our best solution any point on this line
would have give us the maximum profit
in this case we were lucky there was
only a unique solution but there might
be a geometry where we might have more
than one solution but let's not worry
about it let's just
see what does it mean for this
course we had a resource allocation
problem we solved by a graphical
method this was
your first
example of a linear
program
and if my knowledge is accurate about
the current curriculum many of you have
seen this in your high
school so we have a linear program we
have a way to solve it why do we need a
course on
it
all of you or most of you have solved
linear programs using graphical method
before so then great we are done what
else to teach in linear
program let me point it
out the equations we solved were very
special we had only two
variables and we
had very few
equations most of the time when you
encounter a resource allocation problem
in real life you are going to
have many
variables and many equations when I say
many variables I mean thousands of
variables and then the picture I drew
just now on the board you have to draw
it in Thousand Dimension uh plane and I
don't think any of us can do that so the
real world problems are not as simple as
our Brewery problem there you will have
thousands of variables more than
thousands of equations and then the
graphical method is not sufficient to
solve anything
so this course is going to tell you how
to solve linear
programs even if you have lot of
variables and lot of equations and not
just that what are the real life
applications of solving such
[Music]
[Music]
things
[Music]
