Lecture 02 - Introduction to Linear Programming

IIT Kanpur July 201
20 followers
May 31, 2024
[Music]
[Music]
first formalize now what is a linear
program we have seen an example of it so
we are almost there let's just formalize
uh what a linear program is to do that I
have to Define
optimization in
general okay optimization
simply
is
maximization or
minimization and you would realize that
most of the problems in this world are
optimization problems you want to
maximize the number of marks in this
course you want to maximize the amount
of money you will get in your uh
placement or in your jobs you want to
maximize the amount of Peace you have in
this world right so many difficult
problems like how to live your life how
to solve world peace all of those are in
general an optimization problem
mathematically if I want to write it I
have I I have some variable I have
something which I can change I want to
figure out what is this
variable this need not be a single
quantity this could be a list of
variables I want to maximize or minimize
a function of X in the case of be
problem it was 15x + 20
y such that I have some
constraints
and so
on so a very general optimization
problem is maximum minimize some
function of our variables such that sub
constraints are satisfied and as I told
you there are almost all problems can be
written as optimization problems and
that means solving such optimization
problems is very very hard we had no
hope of solving optimation problems in
general
great we are stuck we have very
important
problems we don't know how to solve it
what should we
do and I think this is a golden rule of
research if you can't solve a problem
simplify
it so what is the next step we
ask are there
classes or
subset of optimization
problems which can be
solved if we can't solve abimation
problems in general Are there specific
kind of problems which we can solve
but then what specific kind should we be
looking
at and this is more of
a question about Humanity rather than a
question about
mathematics you have these big set of
problems which you can't solve and now
I'm asking are there subsets which we
can solve what kind of subset should we
be looking
at I would say simply put
uh a class
of optimization problems are
interesting or we should consider that
class which satisfies three properties
one they should be
solvable if you can't solve them then
you know studying them is not very help
help
ful but then we can take a very very
simple instance of it and solve it
obviously they are useful if many
applications can be derived from this
class of
applications another way to put it
is many situations I would
say real
life can be
modeled by this class so this class is
not just easy it is also useful there's
a point of solving these equations
because there are uh there are issues
there are problems in your life which
need to be solved and which can be
solved by this particular class of
optimization
problems and the third reason is not
really a Humanity concern but I would
say as a
mathematician and as we go into deeper
into this Theory you will realize it's
also a concern for us as a mathematician
which is
that this class of
problems should have a I would
say beautiful
structure now this is pretty vague but
just to give you an example in the case
of problems we talked about in that we
had a nice geometry where the solutions
were all continuous to uh aligned with
each other and then we found that the
solution was at a Vertex this was one
example but having this kind of a
structure really tells us much more
about the solution set rather than just
giving us the
value I can't uh uh explain it more than
this if you are familiar with this word
you will see this Duality theory for
linear programming which will tell you
what I mean by having a beautiful
structure inside the class of
problems it turns out we have a
candidate and you shouldn't be surprised
what would be the
candidate linear programming this is
what we have been talking
about there is a subset of optimization
problems which satisfy all these
three
checks all three
properties and this is called linear
programming that
means we are going to have efficient
solution we will see
that many
applications the names of them I will
give it to you today and many of them we
will see it in this course especially in
computer
science and it has beautiful structure
as I said which is exemplified by what I
call The Duality
the and just to
emphasize what is linear programming
it's a subass of optimization problem
where your optimization function is
linear and your constraint
are
also
linear
if you are confused about linearity
remember our problem
was such that constraints
like
160 to I think
98 so
on all these are linear
constraints right uh in general if you
have X1 X2 xn then a linear function
is A1 X1 A2
X2 plus a and xn a linear constraint
is a and
xn equal to less than equal
to Su
B okay so these are simplest kind of
constraints simplest kind of objective
function when we restrict our attention
to these kind of
constraints and these kind of objective
functions we get this very nice class of
linear programming which is going to be
have efficient solution many application
and very nice
structure this is why we are learning
linear programming just uh
to uh just to set the notation remember
for an optimization problem
we maximize
minimize
some objective function in this case the
objective function was 15x + 20
y
under some
constraints here there were five
constraints three equations and X
greater than equal to z y greater than
equal Z five constraints and then we
have what we
call the feasible set the feasible set
is set of all X such that X satisfies
all
constraints
so we want to find the best X from the
feasible set the objective function
which maximize or
minimizes in the feasible set that is
the problem of optimization and now for
the linear programming our objective
function as well as constraints are
linear so so this question is answered
this
is optimization
problems with
linear
objective as well
as
constraints this was the major part of
the first lecture and
now we want to answer the other two
questions why do we want to learn linear
programming and how are we going to
learn linear programming now why is
already written this is an interesting
class of problems which have which we
can solve which have many applications
and has beautiful structure now one
thing which I can which I can give you
more details about is the application so
let me tell you in
brief the amount of areas where linear
programming has made an
impact so if I want to just write out a
list of of
things where linear programming is
important
obviously the first one we have
seen which is resource
allocation this is used in
management portfolio management can be
solved by linear programming in many
cases this
occurs in finance
production line optimization this occurs
in
manufacturing Network
design in
Telecommunications
machine learning complexity
Theory computer
science so this is just a small list you
can grab from the internet but the point
here is that there are so many diverse
areas where linear programming has been
helpful another way to emphasize the
importance of linear programming is by
saying the number of departments in a
university which can be offering this
course so if you are taking a linear
programming
course
obviously you can be a computer
scientist you can be a mathematician
you can be a
economist you can be an electrical
engineer you can be a guy in
finance so on and so
forth so there are at least six or seven
departments in every University which
offer this linear programming course so
this shows the breadth or the the
diversity of applications which this
simple class of optimation problems
span so it's really really uh uh ous you
can you can find linear programming
almost in any any
place many many problems can be framed
as linear programming and solving them
is important for multiple departments
but for
us we will be concentrating on the
aspect of computer
SCI it turns
out there are many
many uh uh areas in itself in computer
science where we can apply linear
programming
tactics of
obviously
algorithms and in general theory of
computing
then machine
learning
algorithmic game
theory
Network
design so even in just one area out of
this there are multiple sub areas where
uh linear programming makes an
impact in this course once we have
learned what is linear programming we
will see its many applications in such
areas so we will briefly talk about some
of the basics in this area and then show
how certain problems in this areas can
be modeled as a linear
program we have answered
what why because it's a small uh set of
it's a simple set of problems which
arise many many times in different
different areas that's so we should know
how to solve these these problems that's
why
and in terms of
how you will
see that we have these linear programs
uh we will write these standard forms
the first
thing to learn would be linear algebra
and I will talk about it very soon once
we understand the
basics we will talk
about convexity Theory and all these are
small steps which arise very naturally
when you want to understand linear
programs
this will give us some of the solution
methods and then the rest of the course
will be focused on or half of the course
will be focused on
applications and see
this is the
plan to
understand linear
programming before I finish this lecture
I just want to uh to tell you why we
want to understand linear algebra but
before that let me just clarify one of
the things
in terms
of
uh algorithms for linear
programs this is uh something uh I I
already said that we can solve them
efficiently so let me just mention that
the first or the the most prominent
method by which people solve linear
programming is called Simplex
method we will see it in this
course this is
not
efficient and efficient means polinomial
time if you are familiar with uh time
complexity and stuff it is not efficient
uh in all
cases there's lot of research in finding
modifications of Simplex method which is
efficient for all cases but still we
don't have such uh
modification the first efficient
method was called
ellipsoid
algorithm this was given
by leonet
Kian this was around 1970s I
think and the method of choice now if
you want to really Solve IT efficiently
if you don't have weird cases is
called interior Point
method this was long series of work but
one of them was given by
karer this was I think in
1980s so this is the method in practice
most of the time this is theoretically
efficient but it's very hard to
implement people don't use it this is
useful in practice as well as it is
provably
efficient we will look at
this and if time permits some idea will
be given
here but this is just to tell you that
linear programs are efficiently
solvable
okay we almost done let's just see what
will be the next lecture about as I said
to understand linear programming we have
to understand linear algebra so why
linear
algebra remember our problem to start
with the example was this such
that I might be slightly off with the
coefficient but it look like this
right y greater than equal to Z the
other
way since I said that linear
programming linear programming is a set
of problems where you have linear
objective for function and linear
constraints then I can think
of my constraint
as suppose I had n
variables X1 to
xn uh in my equations if I have n
variables my maximation might will look
like C1 X1 plus C2 X2 plus CN xn I'm
writing down a general problem in a
particular instance we would know the
value of C C1 C2 CN and you would like
to figure out the value of X1 X2 xn in
this case X this is X1 this is X2 C1 is
15 C2 is
20 such that I can have conditions like
A1 X1 + A2 X2 plus a n xn less than
equal to B1 some conditions like this
then I can also have conditions like B1
X1 B2
X2 uh sorry I should say
uh M1 let's say
M2 I can also have conditions like D1
X1 D2
X2 DN xn equal to M3 so on
right generally the problems would look
like
this
but again by some small trickery we can
change all our constraints to be of this
kind and this we will learn very soon in
the third or fourth lecture even though
at this point I allow my constraints to
be less than equal greater than equal
equality there is a way to convert
between these constraints so actually I
can
say that any general problem will look
like this is my first
constraint
uh
and this is
my MTH
constraint but this equalent is possible
if you have this
constraint in
addition great than Z so yes from the
what we have discussed till now a linear
program will look like this
but you will very soon see that I can
change it into these kind of equation I
can only worry about equality
constraints if this greater than equal
to zero constraint is
there and we'll prove it uh in in next
few lectures so great so then any linear
program actually looks like this and if
I want to write it succinctly I can
think of X as my Vector of variables
I can think of C as my cost Vector which
which keeps all the constants here and
my
constraints I
can write
them as
a
matrix and if I write it like this then
I
can write this what I call the standard
form of linear
program
simply the standard form is
actually maximize C transpose X if I
take the dot product between these two
vectors I will get C1 X1 + C2 X2 plus CN
xn and this
equations will
become such that a x equal to B where X
is positive
that means all X1 X2 xn are
positive this is called the standard
form of linear
program what it means is whatever linear
program you take it can be viewed like
this
equivalently let me warn you this is not
the only standard form we will look at
many other standard forms the point is
if there is a standard form then any
linear program can be transported to
this standard
form now coming back to why do we need
linear
algebra if you look at
this uh in terms of words you want to
look at get all solutions
here which optimize C transpose X
so all X such
that axal to b x than equal to
Z and
then
find Max of C transpose X
all
these
X's right remember this is what we
called the feasible region or feasible
set so if these are the two
steps that means I should first
concentrate
on
finding the feasible set that
means all X's such that axal to B and X
greater than equal to
Z we want to find all such exes such
that a x equal to B and X greater than
equal to
Z as a student of mathematics you should
automatically light up your eyes should
light up and say oh this I have seen
seen before this is just a set of linear
equations which we have solved for
centuries we already know how to deal
with this this is a central
problem in linear
algebra so our technique should be what
do we know about solving xal to B and
then extend it to find the feasible set
of all X's for ax equal to B and X great
than equal to
Z
that is the plan now for next two
lectures we'll be looking at linear
algebra that means how to describe the
solutions of xal to B once we know that
we'll go back to our linear programs
learn more about it and then apply these
tools to the feasible set axal to b x
great than equal to Z this will allow us
to have a an efficient solution for
linear Pro
s so in next lectures we will be
covering linear algebra in other words
how to solve ax equal to thank
[Music]
[Music]
you
[Music]
