Outline

Optimierung

Lösung

Singular

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 $Ay =
0$.

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:

  1. $\beta$ ist optimale Lösung der Aufgabe $\Leftrightarrow
\mbox{ NF}(x^\beta\mid I_A) = x^\beta$.
  2. 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/