Linear programming
I saved the best for last. Linear programming is one of the coolest
things I know.
Linear programming is used to maximize something given some
constraints. For example, suppose your company makes two products,
shirts and totes. Shirts need 1 meter of fabric and 5 buttons. Totes need
2 meters of fabric and 2 buttons. You have 11 meters of fabric and 20
buttons. You make $2 per shirt and $3 per tote. How many shirts and
totes should you make to maximize your profit?
Here you’re trying to maximize profit, and you’re constrained by the
amount of materials you have.
Another example: you’re a politician, and you want to maximize the
number of votes you get. Your research has shown that it takes an
average of an hour of work (marketing, research, and so on) for each
vote from a San Franciscan or 1.5 hours/vote from a Chicagoan. You
need at least 500 San Franciscans and at least 300 Chicagoans. You have
219
Epilogue
50 days. It also costs you $2/San Franciscan versus $1/Chicagoan. Your
total budget is $1,500. What’s the maximum number of total votes you
can get (San Francisco + Chicago)?
Here you’re trying to maximize votes, and you’re constrained by time
and money.
You might be thinking, “You’ve talked about a lot of optimization topics
in this book. How are they related to linear programming?” All the
graph algorithms can be done through linear programming instead.
Linear programming is a much more general framework, and graph
problems are a subset of that. I hope your mind is blown!
Linear programming uses the Simplex algorithm. It’s a complex
algorithm, which is why I didn’t include it in this book. If you’re
interested in optimization, look up linear programming!
Epilogue
I hope this quick tour of 10 algorithms showed you how much more is
left to discover. I think the best way to learn is to find something you’re
interested in and dive in. This book gave you a solid foundation to do
just that.
|