Chapter 29: Linear Programming: Formulations, Algorithms, and Duality

Welcome to Last Minute Lecture.

This free chapter overview is designed to help students review and understand key concepts.

These summaries supplement, not replace, the original textbook and may not be redistributed or resold.

For complete coverage, always consult the official text.

Have you ever thought about how sometimes you're faced with a really, like, complicated problem?

Like maybe trying to allocate resources as effectively as possible.

Or even something more complex, like how a politician can win an election when they only have so much money to spend on their campaign.

It often feels like you're just kind of guessing, you know, just sort of throwing things at the wall and seeing what sticks.

But what if there was like a more systematic way, a way to find not just a solution, but the best possible solution?

That'd be amazing.

That's what we're going to dive into today.

Linear programming.

Ooh, I like it.

A really powerful tool for making the best decisions, even when you're juggling a ton of different factors.

It's like having a secret weapon.

Exactly.

And, you know, we've got this chapter here that really unpacks the whole thing in a way that's actually, believe it or not, pretty easy to understand.

So good.

It starts with a really fun example, this political campaign scenario.

I love a good campaign story.

Right.

And then it takes us through all these cool real -world applications and even the math behind it.

That's great, because I think sometimes people get scared off by the math.

Yeah, but we're going to try to keep it light and focus on the big aha moments.

All right.

Okay, so picture this.

You've got this politician, right?

And they're running for office in a place with three very different kinds of districts,

urban, suburban, and rural.

Okay, that's realistic.

Right.

And to make things interesting, let's say they have four main campaign promises.

Let's hear them.

Number one, preparing for a zombie apocalypse.

Now we're talking.

Number two,

dealing with laser sharks.

Whoa, hold on, laser sharks?

Laser sharks, it's a thing.

Okay, I'm intrigued.

Number three, building flying car highways.

Sounds expensive.

It is, it is.

And finally, number four,

dolphin voting.

Dolphin voting, is that even possible?

Well, that's what we're going to find out.

All right, all right, I'm hooked.

So each of these issues naturally appeals to different groups of voters in those different districts.

Of course.

And of course, each one costs a certain amount of money to promote.

Right.

Now our politician has specific targets for how many votes they need to win in each district.

Okay.

And they're working with a limited budget, so their goal is pretty simple.

They want to hit those vote counts while spending as little money as possible.

I see, so it's all about efficiency.

Exactly.

The chapter even mentions how someone might try to solve this by just kind of guessing and tweaking different spending amounts.

Trial and error.

Yeah, and you might stumble upon a strategy that works.

But how do you know if it's the cheapest way to do it?

That's a good point.

That's the power of linear programming.

Yeah.

It gives us a systematic way to find the absolute best solution, guaranteed.

Okay, I'm ready to learn how to do that.

So the first step is formulating the problem as a linear program.

Okay.

And the chapter does a great job of breaking this down into three parts.

Right.

The first thing we need to do is define what are called the decision variables.

Decision variables.

Basically, these are the things that the politician has control over.

So what they can actually change.

Precisely.

In this case, it's how much money in thousands of dollars they decide to spend on each of those four campaign promises.

I see.

So we can give them names, like buy one for zombie apocalypse prep.

Makes sense.

Buy two for laser sharks.

Naturally.

Buy three for flying cars.

Okay.

And buy four for dolphin voting.

Got it.

So those are our decision variables.

All right.

What's next?

The next crucial piece is defining the constraints.

Constraints.

These are the limitations or requirements that the solution has to satisfy.

Gotcha.

In our political campaign example, the main constraints are those minimum vote counts in each district.

Right, because they have to win those districts.

Exactly.

The chapter lays these out as inequalities.

Inequalities.

Like, for example, Inequality 29 .1 says that they need at least 50 ,000 urban votes to win that district.

Okay, I get it.

Then there's Inequality 29 .2, which says they need at least 100 ,000 suburban votes.

And finally, Inequality 29 .3 says they need at least 25 ,000 rural votes.

So they can't go below those numbers.

Exactly.

Those are the hard limits.

And there's another set of constraints that are sort of obvious but important to include mathematically.

Oh, those?

The non -negativity constraints.

Non -negativity.

Basically, you can't spend a negative amount of money on any of these campaigns.

Well, yeah, that makes sense.

Right.

It seems silly, but mathematically we need to specify that each of those decision variables by one, by two, by three, and by four, they all have to be greater than or equal to zero.

Okay, I see.

So that's like a real -world constraint, making sure the math doesn't go haywire.

Exactly.

Now, the third and final ingredient in formulating a linear program is defining the objective function.

The objective function.

This basically captures the goal that we're trying to achieve.

What are we optimizing for?

That's exactly it.

For our politician, they want to minimize the total amount they spend on advertising.

Keep those costs down, yeah.

Right.

And the chapter expresses this really simply as by one plus by two plus by three plus by four.

So just add up all the spending on each issue.

Precisely.

That sum is what we want to make as small as possible.

Makes sense.

So there you have it.

Those are the three main pieces of a linear program.

Decision variables, constraints, and objective function.

Got it.

And now that we've seen it in this concrete example, the chapter goes on to show us the more general, formal way of writing it all down.

Okay, is this where it gets scary with the math?

Well, it might look a bit intimidating at first, but the main idea is just that it's way to represent any linear program.

I see.

So instead of using those specific names like a one by two, et cetera, it uses these more generic symbols like C for the coefficients in the objective function,

the numbers that are multiplying each of those variables, and then it uses B for the constants on the right hand side of those inequalities.

Like those minimum vote numbers.

Exactly.

And it also uses these AJ symbols for the coefficients within the inequalities themselves.

Okay.

Starting to get a little lost.

It's okay.

Don't worry too much about the details.

The important takeaway for you, our listener, is that it's just a way to write it in a more general form.

And for those of you who are comfortable with matrices and vectors, the chapter even shows how to express it all in an even more compact way.

Matrices.

Like those grids of numbers.

Exactly.

They use symbols like A, B, C, and X to represent everything.

Okay.

Well, that's a bit beyond me, but I trust you.

The key is this makes it much easier to handle really big complex problems with lots of variables and constraints.

So it's like a more powerful notation.

Exactly.

So now that we have a sense of what a linear program looks like, let's dig into some key definitions that the chapter lays out.

Right.

Definitions time.

First up, we have the concept of a feasible solution.

In plain language, this is just a set of values for our decision variables that actually works.

So it satisfies all those constraints.

Exactly.

It doesn't violate any of the rules.

Okay.

So in our political example, a feasible solution would be a specific spending plan so much on zombies, so much on laser sharks, and so on, that achieves all the required vote counts and doesn't involve any negative spending.

It's a valid strategy.

That's it.

Now, on the flip side, an infeasible solution is one that doesn't work.

It breaks the rules.

It does.

It might fail to meet one or more of the constraints.

Like maybe they don't get enough votes in one of the districts.

Or maybe they somehow manage to spend negative money on laser sharks, which of course isn't possible.

Right.

That would be infeasible.

Okay.

Next up, we have the objective value.

Objective value.

This one's pretty straightforward.

It's just the value of the objective function for a given feasible solution.

So once you have a solution that works,

you plug it into that objective function and see what you get.

Exactly.

In our example, it would be the total advertising cost for that particular spending plan.

So lower is better in this case.

Right.

Because we're trying to minimize costs.

Okay.

Got it.

And then the holy grail, the thing we're really after, is the optimal solution.

Optimal sounds important.

It is.

This is the feasible solution.

Remember, it has to be a solution that actually works, that gives us the very best possible objective value.

So for our politician,

it would be the spending plan that gets them elected while spending the least amount of money.

You got it.

Clue.

The chapter also introduces this idea of the feasible region.

Feasible region.

Think of it like this.

It's the set of all possible feasible solutions.

So like all the different spending plans that would actually work.

Exactly.

It's the entire space of possibilities that satisfy all the constraints.

Okay, so if you could visualize it, it would be like the area where all the good solutions live.

That's a great way to put it.

Now, there are a couple of things that can happen when you're trying to solve a linear program.

Oh, things can go wrong.

Well, not exactly wrong, but sometimes there's no solution or there's no best solution.

Interesting.

The first possibility is that the problem is infeasible.

Infeasible.

This means there's just no combination of decision variables that can satisfy all the constraints at the same time.

So like no matter what they do, they can't win.

In a sense.

Yeah.

Imagine, for example, that those vote targets were just way too high.

Like even if they spent every single dollar they had on every single issue, they still wouldn't be able to reach all those vote goals.

That would be a tough election to win.

It would be impossible.

That's an infeasible linear program.

What's the other possibility?

The other possibility is that the problem could be unbounded.

Unbounded.

This means that while there are feasible solutions, there's no limit to how good the objective value can get.

So like they could keep getting better and better.

Exactly.

Imagine, for example, if we were trying to maximize something like profit, and we found that we could just keep increasing one of the variables forever without ever violating any of the constraints.

And that would just keep increasing the profit.

Yeah, it would keep going up and up without any ceiling.

That sounds almost too good to be true.

It often is.

In practice, if you encounter an unbounded linear program, it usually means there's something wrong with how the problem was set up in the first place.

Okay, so those are the things to watch out for.

Exactly.

Now the next big question is, how do we actually solve these linear programs?

Yeah, how do we find those optimal solutions?

Well the chapter touches on a few different algorithms, the methods that computers use to do this.

Algorithms?

Sounds complicated.

They can be, but luckily we don't have to get into the nitty gritty details.

It mentions things like ellipsoid algorithms and interior point algorithm.

Okay, those are words.

The main thing to know is that these are what computer scientists call polynomial time algorithms.

Polynomial time.

It means basically that the time it takes to solve the problem doesn't get ridiculously long as the problem gets bigger.

That's good.

Yeah, it scales in a more manageable way.

And then there's the simplex algorithm.

This one's super popular and tends to work really well in practice.

Even though it's not technically polynomial time in every single case.

That's right, there are some weird edge cases where it can get bogged down.

Interesting.

But for the vast majority of problems, it's a real workhorse.

Okay, so that's how computers do it.

But is there a way for us regular folks to get a feel for how these solutions are found?

There is.

The chapter gives this really cool geometric interpretation focusing on a simplified example with just two variables.

Two variables, so like x and y on a graph.

Exactly.

When you only have two variables, each of those inequality constraints defines a line.

And the feasible region, remember that's the set of all the solutions that work, becomes a polygon.

A polygon.

Like a shape with straight sides.

Exactly.

It's the area on the graph that satisfies all those inequalities at the same time.

And then the objective function when you set it equal to some value also represents a line on this graph.

So finding the best possible solution is like finding the line that represents the best outcome, like the lowest cost for our politician that still touches that feasible polygon.

Trying to picture it in my head.

It's definitely easier to see visually, but the chapter has some nice diagrams.

Okay, I'll take that.

Now here's the really cool part.

For most linear programs, the optimal solution occurs at a vertex of that feasible polygon.

A vertex, like a corner.

You got it.

Think about it.

If you could improve the objective value by moving along one of the edges of the polygon, you'd keep going until you hit a corner.

That makes sense.

Because at that point, you can't go any further without breaking one of the rules.

That's exactly it.

And this idea, even though we're visualizing it with just two variables, extends to problems with many more variables as well.

So even in higher dimensions.

Precisely.

In those cases, the feasible region becomes a more complex shape called a simplex, but the key takeaway is the same.

The best solution often lies at one of its corners.

That's a powerful insight.

It means we can focus our search on those special points instead of having to look everywhere.

Now what makes linear programming so amazing is that it can be used to model all sorts of real -world problems.

Oh, I'm ready for some real -world examples.

The chapter gives several really interesting ones.

Let's start with finding single source shortest paths.

Single source shortest paths.

It's basically a problem in networks.

Imagine you have a bunch of points connected by paths.

Like a roadmap?

Exactly.

And each path has a certain length or cost associated with it.

Like the distance or the toll you have to pay.

Right.

The goal is to find the shortest path, the one with the lowest total cost from a starting point called the source, to any other point in the network.

I see.

Now believe it or not, this can be formulated as a linear program.

Really?

How does that work?

The trick is to maximize the shortest path weight to our destination while making sure that the shortest path weight to any point is less than or equal to the shortest path weight to a neighboring point plus the cost of the connection between them.

This is called the triangle inequality.

Okay.

That sounds kind of technical.

It is.

But the key takeaway is that we can translate this problem of finding the best route into an optimization problem with linear constraints.

Wow.

That's pretty cool.

The next example the chapter gives is the problem of maximum flow.

Maximum flow.

This is about finding the maximum amount of stuff like water, data, or traffic that you can push through a network.

Okay.

You have a starting point, the source, and an ending point, the sink.

And the connections between them have capacities, meaning they can only handle a certain amount of flow.

Like pipes with different diameters.

Exactly.

The goal is to find the absolute most you can send from the source to the sink without exceeding the capacity of any of the connections.

So like maximizing the throughput of the whole system.

Precisely.

And again, this can be formulated as a linear program.

I'm starting to see a pattern here.

You should.

The objective is to maximize the flow out of the source.

Okay.

And the constraints make sure that the flow on each connection doesn't go above its capacity.

Right.

That the flow going into any point equals the flow coming out of it.

So no stuff gets lost or created along the way.

Exactly.

And of course, the flow is always non -negative.

Right.

Because you can't have negative flow.

So with linear programming, we can model all these limitations and find the absolute best way to maximize the flow through the system.

That's really useful for all sorts of things like logistics and transportation.

Absolutely.

And then the chapter takes it a step further with minimum cost flow.

Minimum cost flow.

Now, in addition to those capacities, each connection also has a cost per unit of flow.

So like, it costs money to send things along certain paths.

Exactly.

Now, the goal is to find the cheapest way to send a specific amount of flow from the source to the sink.

So you still have to meet a certain demand, but you want to do it as cheaply as possible.

You got it.

The objective function becomes minimizing the total cost while still respecting those capacity constraints and the rules about flow conservation.

So it's like a more realistic version of the maximum flow problem.

Exactly.

And it's still solvable using linear programming.

Impressive.

Finally, the chapter throws in multi -commodity flow.

Multi -commodity, that sounds intense.

It is.

Imagine now that you have multiple different types of stuff that all need to share the same network.

Like different kinds of goods being shipped on the same roads.

That's a great example.

Each commodity has its own starting point, its own destination, and its own demand.

I see.

And the tricky part is the total flow of all those commodities on any given connection can't exceed its capacity.

Right, because they're all sharing the same limited resources.

Exactly.

In these cases, the main question is often just whether it's even possible to satisfy all those demands.

So just figuring out if it can be done at all.

That's right.

And you can still model this with linear programming.

Okay, my mind is officially blown.

Now hold on, because it gets even more mind -bendy as we move into the concept of duality.

Duality.

What's that?

This is a really deep and elegant idea in linear programming.

I'm intrigued.

The basic concept is that every linear program, what we call the primal problem, has a corresponding related linear program called the dual problem.

A dual problem?

Like a mirror image?

Kind of.

If the primal problem is about maximizing something, the dual problem is about minimizing something related.

The coefficients in the objective function of the primal become the constants on the right -hand side of the constraints in the dual.

They swap roles.

Exactly, and vice versa.

Even the direction of the inequalities gets flipped.

So it's like a complete transformation.

It is.

Now the big question is, why do we care about this dual problem?

Yeah, what's the point?

Well, the chapter gives a really nice intuitive explanation.

You can think of the dual problem as trying to find the smallest possible upper bound on the optimal value of the original primal problem.

So like, putting a ceiling on how good the solution to the original problem can possibly be.

That's a great way to think about it.

But how do the solutions to these two problems actually connect?

That's where these key duality results come in.

Duality results?

Yeah, like theorems and stuff.

Okay, hit me with them.

The first one is called weak linear programming duality.

It's called weak because it's a bit more basic than the strong version.

Basically it says that the objective value of any feasible solution to the primal problem is always less than or equal to the objective value of any feasible solution to the dual problem.

So like, one gives you a lower bound and the other gives you an upper bound.

Exactly, they kind of sandwich the true optimal value.

And this leads to a really handy corollary.

A corollary?

Yeah, like a consequence of that theorem.

It says that if you find feasible solutions to the primal and dual problems that have the same objective value, then you know for sure that both of those solutions are optimal.

Oh, that's a nice shortcut.

It is, you don't have to search any further.

Cool.

But the real star of the show is linear programming duality, also known as strong duality.

Strong duality.

Sounds serious.

It is a big deal.

This theorem says that if both the primal and dual problems are feasible and their optimal values are finite, then those optimal values must be equal.

So the best you can do in one problem is exactly the same as the best you can do in the other.

Precisely.

It's a really deep and powerful connection.

Wow.

And the chapter mentions that the proof of this theorem relies on something called Farkas's Lemma.

Farkas's Lemma.

Don't worry too much about the details, but it's basically about whether systems of linear inequalities have solutions or not.

Okay, I'll trust the mathematicians on that one.

Building on all this, the chapter concludes with the fundamental theorem of linear programming.

Fundamental theorem.

That sounds important.

It is.

It tells us that any linear program in standard form can only have three possible outcomes.

Three.

One, it has an optimal solution with a finite objective value.

Like in our politician example.

Exactly.

Two,

it's infeasible, meaning there's no solution that works.

Like if those vote targets were just impossible to reach.

Right.

And three,

it's unbounded, meaning there's no limit to how good the objective value can get.

So you can just keep making it better and better forever.

At least theoretically.

Okay.

So those are the only possibilities.

Now, just when you thought we were done, the chapter throws in a little twist at the end.

Uh oh.

A twist.

It briefly talks about integer linear programming.

Integer.

It means that all the decision variables have to be integers, whole numbers.

So no fractions or decimals allowed.

Exactly.

And as you might imagine, this can make things a lot harder.

Yeah, because in the real world, you often can't just do things in fractions.

Like you can't spend half a dollar on advertising or build half a highway.

Right.

And unfortunately, there's no known efficient way to solve integer linear programs in general.

So it's much harder than regular linear programming.

It is.

It's a good reminder that seemingly small changes can have a big impact on complexity.

Definitely.

Now throughout this deep dive, we've encountered a ton of important terms and concepts.

Yeah, it's been quite a journey.

And just to reiterate, we've touched on all the key ones that the chapter lays out in its glossary.

Linear programming itself, objective function,

decision variables, constraints, feasible and infeasible solutions,

objective and optimal values, feasible region,

bounded and unbounded infeasible LPs, standard form, simplex, vertices,

primal and dual LPs, weak and strong duality, complementary slackness, integer LP, and even Farkas's lemma.

Wow, that's a lot to digest.

It is, but hopefully you now have a better grasp of the core ideas behind linear programming.

I definitely feel like I've learned a lot.

So let's recap the big takeaways.

We started with the basic idea of linear programming as a way to optimize something while staying within certain limits, maximizing or minimizing something subject to constraints.

We saw how to take a real world problem like our political campaign and turn it into a linear program, identifying those decision variables, constraints and the objective function.

We learned about feasible and optimal solutions, the feasible region and the algorithms that computers use to solve these problems.

And that cool geometric interpretation with the corners of polygons and simplexes.

We explored all sorts of amazing applications like shortest paths, maximum flow and multi -commodity flow.

Showing how versatile linear programming can be.

Then we went into the fascinating realm of duality with primal and dual problems and those powerful duality results.

Weak and strong duality, yeah.

And we finish up with the fundamental theorem and the challenges of integer linear programming.

It's really impressive how such a seemingly simple framework can handle so much complexity.

So for you, our listener, as you go about your day, I want to challenge you to think about the different situations where you're trying to achieve a goal while facing certain limitations.

Yeah, like what are you trying to optimize in your own life?

Exactly.

What are your decision variables?

What are the constraints?

Framing things in this way can really help you understand the structure of a problem and potentially find better solutions.

And remember, this deep dive is just the beginning.

There's a whole world of linear programming out there to explore.

We only scratched the surface.

So keep learning, keep exploring and see what amazing things you can do with this powerful tool.

And with that, we can confidently say that we've covered all the major points, theories, findings and examples from the chapter on linear programming that we set out to discuss today.

Thanks for joining us on this deep dive.

We'll see you next time.