\begin{slide}{Lineare Ungleichungen}

vgl. lineare Optimierung (engl. linear programming)

Terme wie bei Gleichungen, aber Formeln:
\begin{itemize}
\item Ungleichung $\to$ Summe $\ge$ Summe
\item Ungleichungssystem $\to$ Unleichung ( $\wedge$ Ungleichung)$^*$
\end{itemize}

Eigenschaften:
\begin{itemize}
\item Erfüllbarkeit ist entscheidbar (z. B. Simplex-Algorithmus)
\item Lösungsmenge ist Durchschnitt von Halbräumen
\item Lösungsmenge ist (leer oder) konvex
\end{itemize}

\end{slide}

\begin{slide}{Verfahren nach Fourier und Motzkin (I)}

  transformiert ein lin. Unglsys. in ein erfüllbarkeitsäquivalentes
  mit einer Variablen weniger.

  Beispiel: aus $(x+y\le 1 \wedge 2x+3y\ge 0)$ wird $(y \ge -2)$

  Das ist (wie schon Gauß für Gleichungssyst.) 
  ein Verfahren zur \emph{Quantor-Elimination}

  $(\exists x,y: x+y\le 1 \wedge 2x+3y\ge 0) \iff (\exists y: y \ge -2)$

\end{slide}

\begin{slide}{Verfahren nach Fourier und Motzkin (II)}

Elimination einer Variablen:
  \begin{itemize}
  \item wähle eine Variable $x$,
  \item stelle alle Ungl, in denen $x$ vorkommt, nach $x$ um
  \item wenn alle die Form ``$x \le \ldots$'' haben, dann \dots
  \item wenn $x \le G_1 \wedge \ldots$ und $x \ge K_1 \wedge \ldots$, dann \dots
  \end{itemize}
Fragen:
\begin{itemize}
\item Korrektheit
\item Komplexität
\end{itemize}
  
\end{slide}

\begin{slide}{Weitere Verfahren für Lin. Ungl.}

  \begin{itemize}
  \item Fourier-Motzkin 

    einfach, ineffizient
  \item Simplex-Methode

    recht einfach, meist effizient, \emph{aber keine Polynomialzeit}

  \item Ellipsoid-Methode

    kompliziert, Polynomialzeit
  \end{itemize}

\end{slide}

\begin{slide}{Implementierungen}

GNU Linear Programming Kit
\url{http://www.gnu.org/software/glpk/}
\url{http://www.cs.unb.ca/~bremner/docs/glpk/glpk_faq.txt}

\begin{itemize}
\item linear programming (lineare Optimierung)
\item (mixed) integer programming (ganzzahlige lin. Opt.)
\end{itemize}

Schnittstellen:
\begin{itemize}
\item Text (GNU MathProg $\subseteq$ AMPL)
\item API (C, Java)
\end{itemize}

Hausaufgabe: installieren, ausprobieren (Text-Schnittstelle)
\end{slide}
