HUMBOLDT-UNIVERSITÄT ZU BERLIN
MATHEMATISCH-NATURWISSENSCHAFTLICHE FAKULTÄT II
INSTITUT FÜR MATHEMATIK
PROF. PHD. ANDREAS GRIEWANK
DR. NIEPAGE
JAN RIEHME

Humboldt-Universität zu Berlin, Institut für Mathematik, Unter den Linden 6, D-10099 Berlin

Übungsaufgaben zur Vorlesung Mathematik für Informatiker III
Serie 4 (Abgabe: bis 3.1.2006)

Lineare Optimierung

Aufgabe 1:

$\Vert.\Vert _1$-Approximationsaufgabe

Formulieren Sie für das überbestimmte lineare Gleichungssystem

$$Ax = b, \quad A \in I\!\!R^{m\times n}, \quad b\in I\!\!R^m, \quad m > n$$

die $\Vert.\Vert _1$-Approximationsaufgabe

$$\min_{x \in I\!\!R^n} \Vert Ax - b \Vert _1$$

als lineares Optimierungsproblem. (10 Punkte)

Hinweis: Die $\Vert.\Vert _1$-Norm ist definiert durch $\Vert v\Vert _1 = \sum_{i=1}^m \vert v_i\vert$ für $v \in I\!\!R^m$.

Aufgabe 2:

Modellierung einer linearen Optimierungsaufgabe

Eine Großstadt hat für ein Bauprojekt in den nächsten fünf Jahren jeweils zum Jahresbeginn den folgenden Finanzbedarf:

Jahr	1	2	3	4	5	Bemerkung
Finanzbedarf	10	8	6	4	2	in Mio.

Man will sich diese Mittel über die Ausgabe langfristiger Anleihen beschaffen. Zu Beginn eines jeden Jahres können solche Anleihen an Anleger verkauft werden (Fester Einheitskurs: 1 je Anteilsschein). Alle Anleihen werden nach genau sechs Jahren (vom jetzigen Zeitpunkt an gerechnet) von der Stadt an die Anleger ausbezahlt. Dabei ist die Verzinsung jeweils in der Rückzahlung bereits enthalten. Der Rückzahlungskurs wurde wie folgt festgesetzt:

Aufgenommen im Jahr	1	2	3	4	5
Rückzahlungskurs (in%)	150	140	131	122	114

Die Stadtverwaltung steht nun vor der Frage, ob man nicht vielleicht Anleihen auf Vorrat ausgeben soll, also wie die Ausgabemengen der fünf Anleihen zu bemessen sind.¹ Die Stadt kann noch nicht benötigte Mittel zu jeweils 7% Verzinsung jährlich (von Jahr zu Jahr) anlegen.

Formulieren Sie ein lineares Optimierungsproblem zur Bestimmung der Ausgabemengen. (15 Punkte)

Zusatzaufgabe: Löse das lineare Optimierungsproblem mittels Standardsoftware ( Matlab, Maple, ...). Interpretiere/Begründe das Ergebnis.(5 Punkte)

Aufgabe 3:

Lineare Optimierungsaufgabe

Lösen Sie das folgende Problem graphisch und mit dem Simplex-Algorithmus (per Hand, erste zulässige Ecke sei $(x_1, x_2) = (0,0)$):

$$\begin{array}{rrcrcl} \max & 4x_1 & + & x_2\\ & -x_1 & + & x_... ...\le & 4 \\ & \multicolumn{3}{r}{x_1, x_2} & \ge & 0 \end{array}$$

(je 10 Punkte)

Aufgabe 4:

Duales Programm für allgemeines LP

Schreiben Sie das LP in allgemeinster Form

$$\begin{array}{rcccl} \multicolumn{5}{l}{\max c^T x + d^T y} \... ...& \ge & b \\ Ex & + & Fy & = & g \\ & & x & \ge & 0 \end{array}$$

in der Form

$$\begin{array}{l} \max \bar{c}^T \bar{x} \\ \bar{A}\bar{x} \le \bar{b}, \end{array}$$

bilden Sie davon das duale Programm und schreiben Sie dieses wieder mit Gleichungen, $\le$- und $\ge$-Ungleichungen, vorzeichenbeschänkten und -unbeschränkten Variablen. (15 Punkte)

Aufgabe 5:

Dualität zweimal

Sei $A \in I\!\!R^{m\times n}$ und $b \in I\!\!R^m$. Betrachten Sie das zum primalen Programm (P)

$$\begin{array}{l} \max c^T x \\ Ax \le b \end{array} \qquad \qquad (P)$$

gehörende duale Programm

$$\begin{array}{l} \min u^T b \\ u^T A = c^T \\ u \ge 0. \end{array} \qquad \qquad (D)$$

Transformieren Sie (D) in die Form $\max d^T z$, $Mz \le r$. Bilden Sie nun davon das zugehörige duale Programm (DD). Transformieren Sie (DD) in die Form $\max d^T z$, $Mz \le r$ und vergleichen Sie mit (P). (15 Punkte)

Aufgabe 6:

Ganzzahliges Lineares Optimierungsproblem

Betrachtet wird das sogenannte Rucksackproblem:

$$\begin{array}{r@{\;}l} \max\; w^T x \\ v^T x& \le V\\ x& \le b\\ x &\in Z\!\!\!Z_+ \end{array}$$

mit $x\in Z\!\!\!Z^n_+$, $0 < w \in I\!\!R^n$, $0 < v \in I\!\!R^n$, $0 < b \in Z\!\!\!Z^n$ und $0 < V \in Z\!\!\!Z$.

Wenn $V$ das Gesamtvolumen des Rucksacks, $v_i$ das Volumen des $i$-ten Gegenstandes (i=1,...,n) und $w_i$ dessen Wert sowie $b_i$ die zur Verfügung stehende Anzahl bezeichnet, so besteht das Rucksackproblem darin, den Rucksack mit einer Kombination der Gegenstände so zu befüllen, dass der enthaltene Wert maximal wird ohne das Volumen $V$ des Rucksacks oder die Vorratsschranken $b_i$ der Gegenstände zu verletzen.

Löse das Rucksackproblem mit $V=15$ und

i	1	2	3	4
$w_i$	5	6	7	8
$v_i$	4	5	6	7
$b_i$	2	1	2	2

mittels einem speziell an das Rucksackproblem angepassten Branch & Bound - Algorithmus. (Siehe Übungen bzw. Informationen unter http://www.mathematik.hu-berlin.de/$\sim$gaggle/MATHINF).

(25 Punkte)