The vocabulary of a linear program
Before turning the crank, it helps to pin down the words, because the simplex literature uses them inconsistently. The feasible region is the set of all combinations that satisfy every constraint. The objective function is the equation you want to optimize, which in the factory is the revenue. The constraints are the inequalities that limit you, such as the flour, sugar, and chocolate available.
One more rule matters for the method to run: every variable must be greater than or equal to zero. In the factory that is natural, since you cannot make a negative amount of cookie or donut mix. Writing $c \ge 0$ and $d \ge 0$ alongside the resource constraints is what pins the region into the first quadrant.
Put simply, the constraints together with the non-negativity assumption on the variables are what carve out the feasible region. The objective function is separate: it is not part of the region, it is the score you compute at points in the region. The job of the simplex algorithm is to find a vertex on the edge of the feasible region where that score is as large as possible.
Related cards
Video Content
Tasks
Card Info
- Topic: Simplex algorithm, StatQuest
- Difficulty: Intermediate
- Completed: 0 users