Lösung des Optimierungsproblems

Man berechne das binomiale Ideal

$\begin{displaymath} I_A = \langle x^\alpha - x^\beta \mid \alpha, \beta \in {\mathbf N}^n,\; A(\alpha - \beta) = 0\rangle. \end{displaymath}$

Im Beispiel:

$\left\{\left( \begin{array}{r} -2\\ 1\\ 3\\ -9 \end{array}\right), \left( \begin{array}{r} -4\\ 0\\ 7\\ -13 \end{array}\right)\right\}$ ist eine Basis der Lösungsmenge .

Daraus errechnet man

$\begin{displaymath} I_A = \langle x_3 x_4^5 - x_2^2, x_1^2 x_4^9 - x_2 x_3^3, x_1^2 x_2 x_4^4 - x_3^4, x_1^2x_2^3 - x_3^5 x_4\rangle. \end{displaymath}$

Satz:

$\beta$ ist optimale Lösung der Aufgabe $\Leftrightarrow \mbox{ NF}(x^\beta\mid I_A) = x^\beta$ .
Wenn $\alpha$ Lösung, i.e. $A\alpha = b$ und $x^\beta = \mbox{ NF}(x^\alpha \mid I_A)$ , dann ist $\beta$ optimale Lösung.

NF bezeichnet die Normalform bzgl. einer Gröbnerbasis für die Monomenordnung: $x^\alpha < x^\beta \Leftrightarrow c \alpha < c \beta$ oder $c \alpha = c\beta$ und $x^\alpha < x^\beta$ .

Im Beispiel:

$\alpha = \left( \begin{array}{c} 3\\ 7\\ 11\\ 5 \end{array}\right)$

$\mbox{ NF}(x_1^3 x_2^7 x_3^{11} x_4^5 \mid I_A) = x_1 x_2^6 x_3^{15}x_4$

also

$\beta = \left( \begin{array}{c} 1\\ 6\\ 15\\ 1 \end{array}\right)$

ist eine optimale Lösung.

Karlsruhe

http://www.singular.uni-kl.de/