Linear Programming

Loading...

Del curso dictado por University of California San Diego

Advanced Algorithms and Complexity

204 calificaciones

University of California San Diego

Advanced Algorithms and Complexity

204 calificaciones

Curso 5 de 6 en SpecializationData Structures and Algorithms

You've learned the basic algorithms now and are ready to step into the area of more complex problems and algorithms to solve them. Advanced algorithms build upon basic ones and use new ideas. We will start with networks flows which are used in more typical applications such as optimal matchings, finding disjoint paths and flight scheduling as well as more surprising ones like image segmentation in computer vision. We then proceed to linear programming with applications in optimizing budget allocation, portfolio optimization, finding the cheapest diet satisfying all requirements and many others. Next we discuss inherently hard problems for which no exact good solutions are known (and not likely to be found) and how to solve them in practice. We finish with a soft introduction to streaming algorithms that are heavily used in Big Data processing. Such algorithms are usually designed to be able to process huge datasets without being able even to store a dataset.

De la lección

Linear Programming

Linear programming is a very powerful algorithmic tool. Essentially, a linear programming problem asks you to optimize a linear function of real variables constrained by some system of linear inequalities. This is an extremely versatile framework that immediately generalizes flow problems, but can also be used to discuss a wide variety of other problems from optimizing production procedures to finding the cheapest way to attain a healthy diet. Surprisingly, this very general framework admits efficient algorithms. In this unit, we will discuss some of the importance of linear programming problems along with some of the tools used to solve them.

Introduction5:09

Linear Programming8:40

Linear Algebra: Method of Substitution5:36

Linear Algebra: Gaussian Elimination10:32

Conoce a los instructores

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering

Hello everybody, welcome back to our unit on linear programming.

Today, what we're going to do is we're sort of going to put everything on sort

of a more solid, rigorous basis.

So remember last time what we did is we had this factory problem,

where what we wanted to is we wanted to maximize.

In terms of M and W, this 200M + 100W, this is linear expression.

Subject to the following list of linear inequality that they had dissatisfied.

And so in general, basically, just this is where the linear programming is.

It says we want to find real numbers, x1 through xn that satisfy

a bunch of linear inequalities, so a11x1 + a12x2 +...,

is at least to b1, and then a bunch more of those.

And subject to these constraints, we would like a linear objective function,

v1x1 + v2x2 + etc., to be as large or possibly as small as possible.

To clean up the notation a bit,

we're really going to store this by having a matrix A that encodes the coefficients

of all these inequalities along with vectors b and v.

And our output should be a vector x and Rn.

Such that A times x is at least b.

And what I mean by this is that if you multiply the matrix A by the vector x,

then you get a new vector where the first component of that is bigger than

the first component of b.

The second component is at least the second component and so on and so forth.

And note that if you just unroll what that means it's

exactly the system of linear inequalities that we had on the previous slide.

Now subject to this constrain, we would like v * x to be as large or

as small as possible.

So linear programming turns out to be incredibly useful because them

are an extraordinary number of problems that can be put into this framework.

To begin with the factory example that we solved in the last lecture

was exactly of this form.

Optimize a linear function with respect to some linear inequality constraints.

But there's a ton more problems that fit into this.

One of them is the diet problem,

which was studied by George Stigler in the 1930s and 40s.

And intuitively, it's a very simple problem.

How cheaply can you purchase food for a healthy diet?

This is really important if you say, need to feed and army full of soldiers for

example and you want to be cheap.

So how do you do this?

Well, you got a whole bunch of variables for

every type of food that you could possibly eat.

You need to know how many servings per day of that food you're going to have.

So you've got a variable x of bread, x of milk, x of apples, so on and so forth.

And then you've got a bunch of constraints.

Firstly, for each type of food,

you need to have a non-negative number of servings of that food.

It wouldn't do to have minus three servings of bread a day.

And additionally, you need to have enough nutritional content,

you need to have sufficiently many calories per day.

So many calories do you have?

That's just the (Cal / serving bread) x bread + (Cal

/ serving milk) x milk + so on and so forth over every type of food.

And this should be at least 2,000 or whatever your minimum calories per day for

your diet is.

And in addition to this constraint,

we have another similar looking constraint for each other nutritional need.

Vitamin C, protein, What have you.

And so we have a bunch of linear inequalities as our constraints on these

variables.

And subject to these constraints, we want to minimize our total cost.

And the cost of our diet is the (cost of serving a bread) x bread

+ (cost of serving milk) x milk+ so on and so forth.

So we want to minimize a linear function of these variables,

subject to a bunch of linear inequality constraints.

This is a linear problem.

You can solve it and

it would tell you in some sense the cheapest diet that you could live on.

Unfortunately, I should worn you that actually doing this is maybe not

the best idea.

When you solve this, the solution tends to optimized for

a few very efficient foods for getting calories and protein.

And then maybe a few random things to like

fill in your other dietary needs very cheaply.

But I mean It might say that you should eat mostly potatoes and

peanut butter and then a bunch of vitamin pills or something.

And so, these tend not to produce diets you'd

actually want to consist entirely on.

But maybe if you want to think about what can I do to eat more cheaply,

it's something to look at.

So another problem that fits very nicely in this linear programming formulation

is network flow.

It turns out that the network flow problems that we discussed in the last

lecture are actually just a special case of linear programing problems.

So if you want to solve max flow, then you've got a bunch of variables, f sub e,

the flow along each edge e.

And they satisfy some constraints, for

each edge e, f sub e if between 0 and the capacity of the edge.

And then for every vertex that's not a source or

a sink, you have conservation of flow.

So the total flow into that vertex is the same as the total flow out of that vertex.

Now when you first look at this, this might not seem

to be an inequality, it's an equality, not an inequality.

But you could actually just write it by writing down two linear inequalities.

You could say the flow into the vertex is at least the flow out of the vertex.

And on the other hand,

the flow into the vertex is at most the flow out of the vertex.

And so we put these two inequalities together,

it's equivalent to this one equality.

So once we put these constraints on, we now have an objective function we'd like

to subject to these constraints, maximize the flow.

That's the total flow going out of sources minus the total flow going in to sources,

which is a nice linear function.

And so this maximal problem is just a special case.

When you phrase it this way, it's exactly a linear problem.

Now a lot of the time, when you look at a linear program, it's exactly what I said.

You're subject to these constraints, there's a unique

maximum value which attains the best possible value of the objective function.

However, there are a couple of edge cases that you need to keep in mind where things

don't quite work out this way.

The first is you could actually have a system where there is just no solution.

You could have constrains say x is at least 1, y is at least 1, and

x + y is at most 1.

If you have the system of constrains which is graphed here,

there's actually no solution.

Because if x and y are each at least 1, x + y needs to be at least 2.

So there's no solution to the system, so

you can't even start with trying to find a maximum.

It could also be the case that even though your system has solutions

there's no actual optimum.

And a way that this could happen is as follows,

if you have the system where x is at 0, y is at least 0,

x- y is at least 1, there's actually no maximum value for x here.

Basically, the region is graphed here, but it says you could higher and higher and

higher up.

x is actually unbounded in this system.

And so in some sense, your solution should say that there's no maximum.

Now just to review this I've got three pretty simple systems here,

each with two equations and two unknowns.

Now one of these systems has no solution.

One of them has solutions but no solution with a maximum x value, it's unbounded.

And the third one actually does have a unique maximum x value.

And so I'd like you to take a little while to think about which one of these

is which.

Okay, so if we actually graph these three systems, A it turns out has no solution.

One equation says we're supposed to be bigger than one,

the other one says we have to be less than zero, you can't do both of those.

B if you write it down does have a unique maximum at I think x equals one and

a half, as plotted there, it's the red point.

And C, although it does have plenty of solutions, if you graph this region.

You'll note that you sort of slide up along this line,

x equals y, you can make the x value as large as you want.

And so there is our R solutions, but there's no max.

In any case, that's all that I had to say about this

basic introduction to linear programs.

Come back next time and we'll start by looking at a special case of dealing with

linear equalities rather than inequalities.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2018 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play