Standard form: making every constraint a less-than-or-equal
The simplex algorithm is written to expect every constraint in the same direction, using the less-than-or-equal sign. Constraints that arrive in another form get rewritten first so the algorithm never has to branch into special cases.
A greater-than-or-equal constraint, such as making at least 5 kg of mix, $x \ge 5$, is flipped by multiplying both sides by $-1$, which reverses the inequality direction. An equality, such as making exactly 15 kg, $x = 15$, is split into two inequalities that sandwich it: $x \le 15$ together with $x \ge 15$. The second one still has the wrong direction, so you multiply it by $-1$ as well. Now both pieces are less-than-or-equal.
The reason for all this rewriting is not cosmetic. Forcing a single uniform sign means each step of the algorithm follows one recipe, with no checking for different possibilities depending on which way a constraint points. Uniform input is what keeps the procedure short.
Related cards
Video Content
Tasks
Card Info
- Topic: Simplex algorithm, StatQuest
- Difficulty: Intermediate
- Completed: 0 users