Bernhard Kabelka - Lineare Algebra und analytische Geometrie II: "Lineare Optimierung

Ganzzahlige lineare Optimierung

Für die ganzzahlige lineare Optimierung gilt: Sei

$\begin{array}{c| ccc| c}& x_{m+1} & *s & x_{m...... & *s & \widetilde{c}_n & -\widetilde{c} \\\end{array}$

ein optimales Tableau mit $\widetilde{s}_1 in Q\ N$ . Dann erfüllt jedes zulässige ganzzahlige Programm die Ungleichung

$(\widetilde{a}_{1,m+1} -[\widetilde{a}_{1,m+1}]) * x_{m......+n}]) * x_{m+n} >= \widetilde{s}_1 -[\widetilde{s}_1]$