## Schlüsselwortarchiv

Du betrachtest das Archiv des Tags Linear Programming.

• ## Linear (binary) integer programming in Matlab

So, sup­pose you’re in uni­ver­si­ty, it’s that time of the year again (i.e. exams) and you already have writ­ten some of them. Some are still left though and you won­der: How hard can you fail — or: how good do you have to be — in the fol­low­ing exams giv­en that you do not want your mean grade to be worse than a giv­en val­ue.

## Linear programming

Say you’re in Ger­many and the pos­si­ble grades are [1, 1.3, 1.7, 2, .. 4] (i.e. a closed inter­val) with 1 being the best grade and 4 being only a minor step to a major fuck­up. Giv­en that you’ve already writ­ten 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 round­ed to 2 on your diplo­ma), but there still are 9 more exams to write, the ques­tion is: Which worst-case grades can you have in the fol­low­ing exams and what would that imply for the oth­ers?

This is what’s known to be a lin­ear pro­gram­ming or lin­ear opti­miza­tion prob­lem, and since the val­ues (here: the num­ber of grades) are con­strained to be dis­crete val­ues, it’s inte­ger pro­gram­ming.

The goal of lin­ear pro­gram­ming is to find the argu­ments $x$ of the objec­tive func­tion $f(x)$ such that $f(x)$ is max­i­mized, giv­en some con­straints on $x$ . In Mat­lab, all lin­ear pro­gram­ming func­tions try to min­i­mize the cost func­tion, so the prob­lem is for­mu­lat­ed 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}

Obvi­ous­ly, max­i­miz­ing an objec­tive func­tion is the same as min­i­miz­ing it’s neg­a­tive, so $\mathrm{max} \, f(\vec{x}) = -\mathrm{min} \left(\, -f(\vec{x}) \right)$ . In Mat­lab, these kind of prob­lems can be solved with the linprog func­tion.