Dekomposition

Lineare Optimierungsaufgaben der Praxis zeichnen sich häufig dadurch aus, daß ein Teil der Restriktionen eine besondere Struktur besitzt. Liegt eine Aufgabenstellung der Form L$$ \left\{ {\begin{array}{*{20}{c}} {z + {c^t}x = q} \\ {{H^1}x = {d^1}} \\ {{H^2}x = {d^2}} \\ {z\,\min imal,\,x \geqq 0} \\ \end{array} } \right\} $$ vor, so wird nun unterstellt, daß die Restriktionen H1x = d1 in spezieller Weise strukturiert seien. Im folgenden werden sie daher spezielle Restriktionen genannt. Ihre Besonderheit kann darin bestehen, daß die Matrix H1 z.B. aus sehr vielen Nullen und wenigen Elementen +1 oder -1 besteht, oderBlockdiagonalgestalt besitzt.