So, suppose you’re in university, it’s that time of the year again (i.e. exams) and you already have written some of them. Some are still left though and you wonder: How hard can you fail – or: how good do you have to be – in the following exams given that you do not want your mean grade to be worse than a given value.
Linear programming
Say you’re in Germany and the possible grades are [1, 1.3, 1.7, 2, .. 4] (i.e. a closed interval) with 1 being the best grade and 4 being only a minor step to a major fuckup. Given that you’ve already written four exams with the grades 1, 1, 1.3 and 1 and that you do not want to have a mean grade worse than 1.49 in the end (because 1.5 would be rounded to 2 on your diploma), but there still are 9 more exams to write, the question is: Which worst-case grades can you have in the following exams and what would that imply for the others?
This is what’s known to be a linear programming or linear optimization problem, and since the values (here: the number of grades) are constrained to be discrete values, it’s integer programming.
The goal of linear programming is to find the arguments \(x\) of the objective function \(f(x)\) such that \(f(x)\) is maximized, given some constraints on \(x\). In Matlab, all linear programming functions try to minimize the cost function, so the problem is formulated as
\(\begin{align}
\underset{x}{\mathrm{min}} \, f(\vec{x}) \, \mathrm{such}\,\mathrm{that} \, \left\{\begin{matrix} \underline{A}\cdot \vec{x} \leq \vec{b} \\ \underline{A}_{eq} \cdot \vec{x} = \vec{b}_{eq} \end{matrix}\right.
\end{align}
\)
Obviously, maximizing an objective function is the same as minimizing it’s negative, so \(\mathrm{max} \, f(\vec{x}) = -\mathrm{min} \left(\, -f(\vec{x}) \right)\). In Matlab, these kind of problems can be solved with the linprog function.
