Lecture 20 - Chapter 2: Manufacturing
May 2018 edited February 2020 in MIT 2019: Lectures
Last time I rapidly sketched some applications of resource theories to chemistry and scheduling. If you're interested we can dig into these more deeply once we've learned more of the math in Chapter 2. For now let's look at one more application:
Manufacturing. Companies often have to solve puzzles like this, though usually much harder:
Puzzle 58. You are making two kinds of computers: laptops and desktops. Each kind of computer needs 1 processing chip. A laptop also needs 1 memory chip, while a desktop needs 2 memory chips. You have 10,000 processing chips and 15,000 memory chips. Each laptop you make will give $750 of profit, while each desktop will give $1000 of profit. What is the most profit you can make?
Of course this problem is simplified in many ways. We can make it a tiny bit more realistic by recognizing that it also takes time to make computers:
Puzzle 59. Everything in Puzzle 58 still holds, but now your workers have only 25,000 minutes to make all the computers. It takes 4 minutes to make each laptop, and 3 minutes to make each desktop. Now what is the most profit you can make?
These puzzles secretly involve resource theories. The resources you're starting with are:
processing chips
memory chips
You are trying to transform these into some other resources:
and then transform these into yet another resource:
So, we can write some "reactions", as we did last time for chemistry:
$$ \textrm{[processing chip]} + \textrm{[memory chip]} + 4 \textrm{[minute]} \to \textrm{[laptop]} $$ $$ \textrm{[processing chip]} + 2 \textrm{[memory chip]} + 3 \textrm{[minute]} \to \textrm{[desktop]} $$ $$ \textrm{[laptop]} \to 750\textrm{[profit]} $$ $$ \textrm{[desktop]} \to 1000 \textrm{[profit]} $$ Then we can ask what profits are reachable if you start with
$$ 10000 \textrm{[processing chip]} + 15000 \textrm{[memory chip]} + 25000 \textrm{[minute]} .$$ This shows that the second puzzle is a special case of the "reachability problem" that I described in Lecture 19. So is the first puzzle.
However, you don't need to know anything about the reachability problem to solve these puzzles! Ordinary math and some careful thought are enough.
I won't do these puzzles for you, but here's a hint. Let \(x\) be the number of laptops you make, and let \(y\) be the number of desktops. You are trying to maximize some function of \(x\) and \(y\), namely your profit. However, there are some constraints on \(x\) and \(y\). So, draw the region in the \(x y\) plane that's allowed by these constraints, and use that to help you see which choice of \(x\) and \(y\) maximizes the profit.
If you do this, you'll have reinvented the basic idea of "linear programming". (If you already know about linear programming, or these puzzles seem very easy, please let other students post their answers first: it's great for people to invent math on their own.)
Why is this idea called "linear programming"? It's because your profit is a linear function of \(x\) and \(y\), and all your constraints are equations or inequalities involving linear functions of these variables. This makes things easier.
Many industries use linear programming to solve problems involving enormous numbers of variables. Linear programming is good for many things, including routing, scheduling, and assignment problems.
Because of this, there's been an enormous push to improve algorithms for linear programming. Some of the basic ideas go back to Fourier: in 1827 he figured out how to eliminate variables from a system of linear inequalities. But linear programming really took off in 1939 when the economist Leonid Kantorovich developed it as a method to reduce costs for the Soviet army and increase losses incurred to the enemy in World War II. About the same time, the American economist T. C. Koopmans figured out how to formulate many economics problems as linear programming problems. Kantorovich and Koopmans later shared the Nobel prize in economics for this work.
One of the most important developments came around 1947 when George Dantzig, working for the US Air Force, was trying to find the best assignment of 70 people to 70 jobs. To do this he reinvented linear programming and invented the first efficient algorithm to solve these problems: the simplex algorithm.
The simplex algorithm runs in polynomial time on average, but in the worst case it can take exponential time. The first polynomial-time algorithm for linear programming was found by Leonid Khachiyan in 1979: it's called the ellipsoid algorithm. But this method is very slow in practice. A better polynomial-time algorithm is Karmarkar's algorithm, discovered around 1984. AT&T tried to patent this algorithm, and that led to a big legal fight about whether math can be patented!
Given all this hard work, it's unlikely that resource theories will help anyone with linear programming... at least in the short run. It's more likely that seeing linear programming as part of the subject of resource theories will give us new ideas, by making new connections apparent. That's how category theory often works.
There are also applications of resource theories to other aspects of economics - as well as thermodynamics and quantum computation. But all these take more work to explain, so next time I'll just dive into the math of resource theories. If you want to get ready, read Section 2.2.1 of Seven Sketches. I'm eager to get started!
Michael Hong
Puzzle 59 I get a maximum $7,750,000 at 1000 Laptops and 7000 Desktops.
Here is the Geogebra file I used to get my answer.
Comment Source:**Puzzle 59** I get a maximum $7,750,000 at 1000 Laptops and 7000 Desktops. Here is the [Geogebra file](https://ggbm.at/qdcJNnFd) I used to get my answer.
@Michael Hong My toy code agrees :).
Comment Source:@Michael Hong My toy code agrees :).
Michael Hong - wow, that's great!
Can someone create a nice picture emphasizing the allowed region in the \(xy\) plane and level curves (really lines) of the profit function \(p(x,y) = 750 x + 1000 y\)? This will make it really clear what's going on.
How many of the people reading this have already studied problems of this sort? I never took a course on linear programming myself.
Comment Source:Michael Hong - wow, that's great! Can someone create a nice picture emphasizing the allowed region in the \\(xy\\) plane and level curves (really lines) of the profit function \\(p(x,y) = 750 x + 1000 y\\)? This will make it really clear what's going on. How many of the people reading this have already studied problems of this sort? I never took a course on linear programming myself.
I think all economists have been exposed to linear and nonlinear programming, though possibly only at a theoretical (as opposed to computational) level.
Comment Source:I think all economists have been exposed to linear and nonlinear programming, though possibly only at a theoretical (as opposed to computational) level.
Jared Summers
An introductory operations research course was required as part of my CS degree, I'm trying to remember all it covered but I do know it covered linear programming.
Comment Source:An introductory operations research course was required as part of my CS degree, I'm trying to remember all it covered but I do know it covered linear programming.
I have been taught how to solve these kind of linear programming problems in CS class. It can be solved with the simplex method which is about as simple as it sounds.
It would be delightful to reproduce a beginner's introduction, but I can't do it single handed (on a mobile phone) shortly before I fall asleep.
Looking at the respective Wikipedia page I get the feeling that it's not much fun for people who haven't done this before:
https://en.wikipedia.org/wiki/Simplex_algorithm
The first 4 equations specify profit slopes (gradients) in 3-space. (Or maybe imagine families of planes intersecting the axies at...)
The available resource spec is practically a (we may use) less-than (these resources) relation, or a plane dividing our 3-space into two half-spaces: one where the allowed values live, and the other stuff we're not interested in. That's our simplex.
Edit: It might be a better idea to think of it as three planes orthogonal to the axies, and of the gradients as vectors. Sorry, some assembly may be required, it's been a while.
We have to find the maximal vector a•laptops + b•desktops smaller than that plane.
Since it's an integer mixed linear programming problem, we may have to try a few combinations (a,b), and for this there's a closely related technique:
https://en.wikipedia.org/wiki/Cutting-plane_method
A page which might be slightly more fun.
Comment Source:I have been taught how to solve these kind of linear programming problems in CS class. It can be solved with the simplex method which is about as simple as it sounds. It would be delightful to reproduce a beginner's introduction, but I can't do it single handed (on a mobile phone) shortly before I fall asleep. Looking at the respective Wikipedia page I get the feeling that it's not much fun for people who haven't done this before: https://en.wikipedia.org/wiki/Simplex_algorithm The first 4 equations specify profit slopes (gradients) in 3-space. (Or maybe imagine families of planes intersecting the axies at...) The available resource spec is practically a (we may use) less-than (these resources) relation, or a plane dividing our 3-space into two half-spaces: one where the allowed values live, and the other stuff we're not interested in. That's our simplex. Edit: It might be a better idea to think of it as three planes orthogonal to the axies, and of the gradients as vectors. Sorry, some assembly may be required, it's been a while. We have to find the maximal vector a•laptops + b•desktops smaller than that plane. Since it's an _integer_ mixed linear programming problem, we may have to try a few combinations (a,b), and for this there's a closely related technique: https://en.wikipedia.org/wiki/Cutting-plane_method A page which might be slightly more fun.
Here's my first-cut, simplest, simplex haskell code:
https://github.com/jimstutt/Simplex/blob/master/src/Simplex.hs
Comment Source:Here's my first-cut, simplest, simplex haskell code: https://github.com/jimstutt/Simplex/blob/master/src/Simplex.hs
Sophie Libkind
I made a fun plot of the level curves using Python in a Google Colab Notebook. It was neat to see the bounding lines representing the constraints from the number of processors, memory chips, and minutes. Based on their slopes, I think the bounding lines from left to right correspond to memory chips, processors, and minutes.
Comment Source:I made a fun plot of the level curves using Python in a <a href="https://colab.research.google.com/drive/1gECqYfziXUaI26GFXsFwk8GEHBLVLj7N#scrollTo=2E3zAKbvz8aO">Google Colab Notebook</a>. It was neat to see the bounding lines representing the constraints from the number of processors, memory chips, and minutes. Based on their slopes, I think the bounding lines from left to right correspond to memory chips, processors, and minutes.
Marius Furter
How many of the people reading this have already studied problems of this sort?
Systems Biologists studying metabolic networks use exactly this procedure for constraint-based modeling they call flux balance analysis (FBA).
The first step is to write the stoichiometric coefficients (negative for reactants, positive for products) in a matrix format, where each row represents a reaction and each column represents a compound. For our above example this matrix would thus look like this:
$$ \begin{bmatrix} p.chip & m.chip & minute & laptop & desktop & profit \\ -1 & -1 & -4 & 1 & 0 & 0 \\ -1 & -1 & -3 & 0 & 1 & 0 \\ 0 & 0 & 0 & -1 & 0 & 750 \\ 0 & 0 & 0 & 0 & -1 & 1000 \end{bmatrix} $$ One then computes the constraint space, which corresponds to a polygonal shape in n-dimensional space (where n is the number of compounds) bounded by the linear equations from the matrix. When computed using all reactions in an organism's metabolism, this constraint space corresponds to all metabolic states an organism can be in that don't violate the conservation of mass.
Since this system of equations underdetermined in practice (i.e all points within the boundaries are valid solutions), one needs a further 'objective' function to obtain a unique solution. This objective function is generally a maximization or minimization performed on one or more of the variables. Geometrically, the solution will be located on a vertex, edge, plane, ect. of the constraint space depending on how determined it is. In economics, this usually means maximizing profit (for our example \( z=750 \text{ laptop} + 1000 \text{ desktop} \)). In the case of biological organisms, what objective function should be used is less obvious and usually depends on the situation being studied (e.g an organism with sufficient nutrients may try maximizing biomass production, while a starving organism may not).
Comment Source:John wrote: > How many of the people reading this have already studied problems of this sort? Systems Biologists studying metabolic networks use exactly this procedure for constraint-based modeling they call flux balance analysis (FBA). The first step is to write the stoichiometric coefficients (negative for reactants, positive for products) in a matrix format, where each row represents a reaction and each column represents a compound. For our above example this matrix would thus look like this: $$ \begin{bmatrix} p.chip & m.chip & minute & laptop & desktop & profit \\\ -1 & -1 & -4 & 1 & 0 & 0 \\\ -1 & -1 & -3 & 0 & 1 & 0 \\\ 0 & 0 & 0 & -1 & 0 & 750 \\\ 0 & 0 & 0 & 0 & -1 & 1000 \end{bmatrix} $$ One then computes the constraint space, which corresponds to a polygonal shape in n-dimensional space (where n is the number of compounds) bounded by the linear equations from the matrix. When computed using all reactions in an organism's metabolism, this constraint space corresponds to all metabolic states an organism can be in that don't violate the conservation of mass. Since this system of equations underdetermined in practice (i.e all points within the boundaries are valid solutions), one needs a further 'objective' function to obtain a unique solution. This objective function is generally a maximization or minimization performed on one or more of the variables. Geometrically, the solution will be located on a vertex, edge, plane, ect. of the constraint space depending on how determined it is. In economics, this usually means maximizing profit (for our example \\( z=750 \text{ laptop} + 1000 \text{ desktop} \\)). In the case of biological organisms, what objective function should be used is less obvious and usually depends on the situation being studied (e.g an organism with sufficient nutrients may try maximizing biomass production, while a starving organism may not).
Sophie wrote in :
I made a fun plot of the level curves using Python in a Google Colab Notebook.
That's really cool!
Can someone create a nice picture emphasizing the allowed region in the xy plane and level curves (really lines) of the profit function p(x,y)=750x+1000y? This will make it really clear what's going on.
Here's a picture of the constraints acting on production assuming \(10000 \textrm{[processing chip]} + 15000 \textrm{[memory chip]} + 25000 \textrm{[minute]} \) :
Red: p.chips, Blue: m.chips, Green: minutes, Green shading: Allowed area
I can't think of a nice way to include the profit in this graph without adding another axis. Maybe someone else has a good idea.
Edit: Just noticed that Sophie's heat map nicely solves this.
Comment Source:Sophie wrote in : > I made a fun plot of the level curves using Python in a Google Colab Notebook. That's really cool! John wrote: > Can someone create a nice picture emphasizing the allowed region in the xy plane and level curves (really lines) of the profit function p(x,y)=750x+1000y? This will make it really clear what's going on. Here's a picture of the constraints acting on production assuming \\(10000 \textrm{[processing chip]} + 15000 \textrm{[memory chip]} + 25000 \textrm{[minute]} \\) : ![](https://docs.google.com/uc?id=1RuVe6XDAM3uLbDQQIKaI6lPU0BZArvME) Red: p.chips, Blue: m.chips, Green: minutes, Green shading: Allowed area I can't think of a nice way to include the profit in this graph without adding another axis. Maybe someone else has a good idea. Edit: Just noticed that Sophie's heat map nicely solves this.
Comment Source:> I made a fun plot of the level curves using Python in a [Google Colab Notebook](https://colab.research.google.com/drive/1gECqYfziXUaI26GFXsFwk8GEHBLVLj7N#scrollTo=2E3zAKbvz8aO). It was neat to see the bounding lines representing the constraints from the number of processors, memory chips, and minutes. Based on their slopes, I think the bounding lines from left to right correspond to memory chips, processors, and minutes. This is amazing!
Thanks, Marius and Sophie! This is great! This is exactly what I'm hoping for: people jumping in and creating nice pictures and software to add to my verbal explanations.
Marius seems to have chosen desktops to be the \(x\) coordinate and laptops to be \(y\), opposite from what Sophie and I are doing. I mention this in case anyone is puzzled.
Comment Source:Thanks, Marius and Sophie! This is great! This is exactly what I'm hoping for: people jumping in and creating nice pictures and software to add to my verbal explanations. Marius seems to have chosen desktops to be the \\(x\\) coordinate and laptops to be \\(y\\), opposite from what Sophie and I are doing. I mention this in case anyone is puzzled.
Marius wrote:
One way is to include the level curves of profit as faint lines of the form
$$ 750 x + 1000 y = p $$ for various values of the number \(p\). The line for maximum profit will go through the upper right corner of the shape you drew in green.
Comment Source:Marius wrote: > I can't think of a nice way to include the profit in this graph without adding another axis. Maybe someone else has a good idea. One way is to include the level curves of profit as faint lines of the form \[ 750 x + 1000 y = p \] for various values of the number \\(p\\). The line for maximum profit will go through the upper right corner of the shape you drew in green.
Pierre Prado
This topic resonates with this, for me: la.mathworks.com/help/fuzzy/what-is-sugeno-type-fuzzy-inference.html
Thanks for all for the interesting discussion
Comment Source:This topic resonates with this, for me: la.mathworks.com/help/fuzzy/what-is-sugeno-type-fuzzy-inference.html Thanks for all for the interesting discussion
Yep I confirm in CS I was taugh to run Simplex by pen and pencil
Comment Source:Yep I confirm in CS I was taugh to run Simplex by pen and pencil