Mathematik III - TU Chemnitzpeju/skripte/wiinf/wiinf3.pdf · x ∈ R3, auf denen der Gewinn zu maximieren ist. Um die Grenzen der zur Verfugung stehenden¨ Rohstoﬀmengen nicht zu

Skript zur Vorlesung

Mathematik III

fur Wirtschaftsinformatiker

WS 2006/07

Peter Junghanns

2

Inhaltsverzeichnis

8 Lineare Optimierung 5

8.1 Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

8.1.1 Ein Gewinnmaximierungsproblem . . . . . . . . . . . . . . . . . . . . . . 5

8.1.2 Ein Kostenminimierungsproblem (Transportoptimierung) . . . . . . . . . 6

8.2 Eine Standardaufgabe der linearen Optimierung . . . . . . . . . . . . . . . . . . . 7

8.3 Grafische Betrachtungen bei zwei Entscheidungsvariablen . . . . . . . . . . . . . 9

8.4 Der Simplex-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

8.5 Endlichkeit des Simplex-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . 18

8.6 Die Zwei-Phasen-Methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

8.7 Dualitat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

8.8 Ubungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

9 Kryptographie 35

9.1 Grundprobleme der Kryptographie . . . . . . . . . . . . . . . . . . . . . . . . . . 35

9.1.1 Geheimhaltung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

9.1.2 Authentifikation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

9.1.3 Anonymitat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

9.1.4 Protokolle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

9.1.5 Vermeidung von Ubertragungsfehlern (Prufziffernverfahren) . . . . . . . . 36

9.2 Zahlentheoretische Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

9.2.1 Der Euklidische Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . 37

9.2.2 Zahlenkongruenzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

9.2.3 Quadratische Reste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

9.2.4 Der diskrete Logarithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

9.3 Kryptologische Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

9.3.1 Symmetrische Verschlusselung . . . . . . . . . . . . . . . . . . . . . . . . 43

9.3.2 Asymmetrische Verschlusselung (Public-Key-Kryptographie) . . . . . . . 44

9.3.3 Einwegfunktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

9.3.4 Die digitale Signatur (Die elektronische Unterschrift) . . . . . . . . . . . . 44

9.3.5 Der RSA-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

9.4 Protokolle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

9.4.1 Protokolle zur Authentikation . . . . . . . . . . . . . . . . . . . . . . . . . 47

9.4.2 Vereinbarung eines geheimen Schlussels . . . . . . . . . . . . . . . . . . . 48

3

4 INHALTSVERZEICHNIS

9.4.3 Das ElGamal-Signaturverfahren . . . . . . . . . . . . . . . . . . . . . . . . 499.4.4 Shamirs No-Key-Protokoll . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

9.5 Ubungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

10 Graphentheorie 5310.1 Grundbegriffe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5310.2 Bipartite Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5410.3 Wege und Kreise. Die Adjazenzmatrix . . . . . . . . . . . . . . . . . . . . . . . . 5510.4 Eulersche Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5610.5 Baume und Geruste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5610.6 Regulare Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5710.7 Hamiltonsche Graphen. Kurzeste Wege . . . . . . . . . . . . . . . . . . . . . . . . 5710.8 Optimale Geruste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6010.9 Ubungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

Kapitel 8

Lineare Optimierung

8.1 Beispiele

8.1.1 Ein Gewinnmaximierungsproblem

In einem Betrieb werden drei verschiedene Produkte P1, P2, P3 produziert. Beim Verkauf desProduktes P1 wird ein Gewinn von 150e pro Stuck, bei P2 von 350e und bei P3 von 500eerzielt. Fur das Produkt Pj wird der Rohstoff Aj benotigt.

Der Betrieb kann pro Woche hochstens mit 10 Mengeneinheiten (ME) des Rohstoffs A1 , 8 MEdes Rohstoffs A2 und 5 ME des Rohstoffs A3 beliefert werden. Fur ein Stuck des Produktes P1

werden 0.1 ME A1 , des Produktes P2 0.2 ME A2 , des Produktes P3 0.25 ME A3 verarbeitet.

Im Betrieb arbeiten 10 Hilfsarbeiter (HA) und 5 Facharbeiter (FA) zu je 40 Stunden pro Woche.Die Produktion beinhaltet insgesamt funf verschiedene Arbeitsgange AGj , j = 1, . . . , 5 . DerStundenaufwand der einzelnen Arbeitsgange pro Stuck der einzelnen Produkte ist der folgendenTabelle zu entnehmen.

P1 P2 P3

AG1 FA 0.0 0.7 2.0HA 0.5 0.8 0.0

AG2 FA 0.0 1.3 2.0HA 1.0 0.7 0.0

AG3 FA 0.0 1.0 3.0HA 0.0 1.0 0.0

AG4 FA 0.0 1.0 2.0HA 1.0 1.0 0.0

AG5 FA 1.0 5.0 9.0HA 3.5 4.5 4.0

Die Maschine fur AG1 kann maximal 30 Stunden pro Woche genutzt werden. Fur AG2 stehenMaschinen im Umfang von maximal 60 Stunden pro Woche zur Verfugung, fur AG3 und AG4

jeweils im Umfang von maximal 40 Stunden.

5

6 KAPITEL 8. LINEARE OPTIMIERUNG

Es stellt sich nun die Frage, wieviel Stuck jedes der Produkte der Betrieb pro Woche herstellensollte, um den Gewinn zu maximieren. Dabei werden naturlich gleichzeitig die Fragen nach derHohe des maximalen Gewinns und den zu bestellenden ME Rohstoffe zu beantworten sein.

Wir versuchen vorerst, das Problem in eine Formelsprache zu bringen. Dazu bezeichnen wir mitξj die zu produzierende Stuckzahl des Produktes Pj , und setzen x = [ξ1, ξ2, ξ3]

T ∈ R3 . Der

Gewinn (in e) betragt dann

g(x) = 150 ξ1 + 350 ξ2 + 500 ξ3 . (8.1)

Die aufgefuhrten Einschrankungen an die Produktion beschreiben dabei die Menge D ⊂ R3 der

x ∈ R3 , auf denen der Gewinn zu maximieren ist. Um die Grenzen der zur Verfugung stehenden

Rohstoffmengen nicht zu uberschreiten, muss fur alle x ∈ D gelten

0.1 ξ1 ≤ 10 , 0.2 ξ2 ≤ 8 , 0.25 ξ3 ≤ 5 . (8.2)

Pro Woche verfugt der Betrieb uber 400 HA-Stunden und 200 FA-Stunden. Entsprechend obigerTabelle mussen also fur x ∈ D die Bedingungen

ξ1 + 9 ξ2 + 18 ξ3 ≤ 200 und 6 ξ1 + 8 ξ2 + 4 ξ3 ≤ 400 (8.3)

erfullt sein. Die Einschrankungen an die Maschinenverfugbarkeiten liefern die Restriktionen

0.5 ξ1 + 1.5 ξ2 + 2ξ3 ≤ 30 , ξ1 + 2 ξ2 + 2ξ3 ≤ 60 , 2 ξ2 + 3ξ3 ≤ 40 , ξ1 + 2 ξ2 + 2ξ3 ≤ 40 . (8.4)

Schließlich sind noch die Nichtnegativitatsbedingungen

ξj ≥ 0 , j = 1, 2, 3 , (8.5)

aufzufuhren.

Die Aufgabenstellung lautet also: Man maximiere die Funktion g : R3 −→ R , die durch (8.1)

gegeben ist, auf der Menge

D =x = [ξ1, ξ2, ξ3]

T ∈ R3 : x genugt (8.2) − (8.5)

.

8.1.2 Ein Kostenminimierungsproblem (Transportoptimierung)

Ein Transportunternehmen verfugt uber drei Lagerhallen mit den Lagermengen (in ME) L1 =10 , L2 = 6 und L3 = 7 . Vier Abnehmern entsprechen die Nachfragemengen A1 = 8 , A2 = 6 ,A3 = 4 und A4 = 5 . Die folgende Tabelle gibt die Transportkosten je ME (in Tausend e) vonder Lagerhalle Lj , j = 1, 2, 3 , zum Abnehmer k = 1, 2, 3, 4 an.

Abnehmer k 1 2 3 4

L1 3 4 2 5

L2 6 7 1 2

L3 5 4 3 2

8.2. EINE STANDARDAUFGABE DER LINEAREN OPTIMIERUNG 7

Bezeichnet man mit ξjk die Liefermenge von Lj zum Abnehmer k , so ist die Summe der Trans-portkosten laut obiger Tabelle gleich

K(X) = 3 ξ11 + 4 ξ12 + 2 ξ13 + 5 ξ14

+ 6 ξ21 + 7 ξ22 + ξ23 + 2 ξ24 (8.6)

+ 5 ξ31 + 4 ξ32 + 3 ξ33 + 2 ξ34 ,

wobei X =[

ξjk

] 3 4

j=1,k=1. Die Aufgabe besteht nun darin, diese Kosten durch entsprechende

Wahl der ξjk zu minimieren. Da die Summe der Lagermengen gleich der Summe der Nachfrage-mengen ist, mussen die X ∈ R

3×4 , auf denen die Kostenfunktion K(X) zu minimieren ist, denGleichungen

ξj1 + ξj2 + ξj3 + ξj4 = Lj , j = 1, 2, 3 , (8.7)

genugen. Um die geforderten Nachfragemengen einzuhalten, sind weiterhin die Gleichungen

ξ1k + ξ2k + ξ3k = Ak , k = 1, 2, 3, 4 , (8.8)

zu erfullen. Ferner sind naturlich wieder die Nichtnegativitatsbedingungen

ξjk ≥ 0 , j = 1, 2, 3 , k = 1, 2, 3, 4 , (8.9)

einzuhalten.

Die Aufgabenstellung lautet also: Minimiere die Funktion K : R3×4 −→ R , die durch (8.6)

gegeben ist, auf der Menge

D =

X =[

ξjk

] 3 4

j=1,k=1∈ R

3×4 : X genugt (8.7) − (8.9)

.

8.2 Eine Standardaufgabe der linearen Optimierung

Um Systeme von Ungleichungen effektiv aufschreiben zu konnen, fuhren wir auf dem linea-ren Raum R

n eine partielle Ordnungsrelation ein. Wir sagen, dass fur zwei Vektoren x =[ξk

] n

k=1∈ R

n und y =[

ηk

] n

k=1∈ R

n die Ungleichung x ≤ y gilt, wenn alle Ungleichungenξk ≤ ηk , k = 1, . . . , n , erfullt sind. Im weiteren sei stets n ≥ 2 .

Wir betrachten die Problemstellung aus dem Abschnitt 8.1.1. Mit den Bezeichnungen

c =

150350500

∈ R

3 , A =

0.1 0 00 0.2 00 0 0.251 9 186 8 4

0.5 1.5 21 2 20 2 31 2 2

∈ R9×3 und b =

1085

20040030604040

∈ R9


lassen sich die Gewinnfunktion (8.1), die Restriktionen (8.2)-(8.4) und die Nichtnegativitatsbe-dingungen (8.5) kurz in der Form

g(x) = cT x = 〈x, c〉 (Zielfunktion),

Ax ≤ b (Restriktionen)

undx ≥ Θ (Nichtnegativitatsbedingungen)

schreiben. Damit ist die Standardform der Maximierungsaufgabe der linearen Optimierung er-kennbar. Sie lautet:

• Gegeben sind ein Vektor c =[

γk

] n

k=1∈ R

n , eine Matrix A =[

αjk

] m n

j=1,k=1∈ R

m×n

und ein Vektor b ∈ Rm .

• Gesucht ist ein Vektor x∗ ∈ D , so dass

g(x) ≤ g(x∗) ∀x ∈ D (8.10)

gilt, wobei die Zielfunktion g und die Menge D ⊂ Rn durch g(x) = cT x und D =

x ∈ Rn : Ax ≤ b, x ≥ Θ gegeben sind.

Von einer linearen Optimierungsaufgabe spricht man hier deshalb, weil sowohl die Zielfunktiondurch ein lineares Funktional g : R

n −→ R , x 7→ 〈x, c〉 , auf Rn als auch die linken Seiten der

Restriktionsungleichungen durch eine lineare Abbildung A : Rn −→ R

m , x 7→ Ax , beschrie-ben werden. Die ξk , k = 1, . . . , n , nennt man Entscheidungsvariable und die Menge D nenntman den zulassigen Bereich. Die Eintrage γk im Vektor c werden Zielfunktionskoeffizien-ten genannt. Die x ∈ D heißen zulassige Losungen, ein x∗ ∈ D , welches (8.10) genugt, eineoptimale Losung.

Wir definieren nun die sog. Schlupfvariablen ηj , j = 1, . . . ,m , uber y =[

ηj

] m

j=1und

y = b − Ax . Fur x ∈ D gilt offenbar y ≥ Θ . Wir setzen c =[

γ1, . . . , γn, 0, . . . , 0]T ∈ R

n+m ,

A =

α11 · · · α1n 1 0

......

. . .

αm1 · · · αmn 0 1

∈ R

m×(n+m) und x =

ξ1...ξn

η1...

ηm

∈ Rn+m .

Die Restriktionen Ax ≤ b und die Nichtnegativitatsbedingungen x ≥ Θ lassen sich jetzt in derForm A x = b und x ≥ Θ und die Zielfunktion x 7→ cT x in der Form x 7→ cT x schreiben.

Die Matrix A hat n + m Spalten, von denen auf jeden Fall m linear unabhangig sind. Diemaximale Anzahl linear unabhangiger Spalten einer Matrix nennt man den Rang dieser Matrix(in Zeichen: rank(.)). Es gilt also rank(A) = m .

8.3. GRAFISCHE BETRACHTUNGEN BEI ZWEI ENTSCHEIDUNGSVARIABLEN 9

Somit haben wir die folgende Standardaufgabe der linearen Optimierung erhalten, wobei wirn + m wieder durch n ersetzen und annehmen konnen, dass alle Eintrage des Vektors b positivsind:

• Gegeben sind ein Vektor c =[

γk

] n

k=1∈ R

n , eine Matrix A =[

αjk

] m n

j=1,k=1∈ R

m×n

mit

rank(A) = m < n , (8.11)

und ein Vektor b ∈ Rm mit b ≥ Θ .

• Gesucht ist ein Vektor x∗ ∈ D , so dass

g(x) ≤ g(x∗) ∀x ∈ D (8.12)

gilt, wobei die Zielfunktion g und der zulassige Bereich D ⊂ Rn durch g(x) = cT x und

D = x ∈ Rn : Ax = b, x ≥ Θ gegeben sind.

Das Transportoptimierungsproblem aus Abschnitt 8.1.2 lasst sich sofort in dieser Form schreiben,

wenn man ein X =[

ξjk

] 3 4

j=1,k=1∈ R

3×4 uber ξ1 = ξ11 , ξ2 = ξ12 , . . . , ξ12 = ξ34 mit einem

x =[

ξk

] 12

k=1∈ R

12 identifiziert. Dabei sind dann n = 12 und m = 7 sowie

c = −

342567125432

, A =

1 1 1 1 0 0 0 0 0 0 0 00 0 0 0 1 1 1 1 0 0 0 00 0 0 0 0 0 0 0 1 1 1 11 0 0 0 1 0 0 0 1 0 0 00 1 0 0 0 1 0 0 0 1 0 00 0 1 0 0 0 1 0 0 0 1 00 0 0 1 0 0 0 1 0 0 0 1

und b =

10678645

.

8.3 Grafische Betrachtungen bei zwei Entscheidungsvariablen

Wir betrachten eine Maximierungsaufgabe in Standardform fur n = 2 und m = 3 , wobei

c =

[2025

], A =

1 11 21 0

und b =

406025

.

Ausfuhrlich geschrieben:

g(x) = 20 ξ1 + 25 ξ2 −→ Max ,


wobeiξ1 + ξ2 ≤ 40 ,

ξ1 + 2 ξ2 ≤ 60 ,

ξ1 ≤ 25 ,

ξ1 ≥ 0 ,

ξ2 ≥ 0 .

Wir stellen zuerst den zulassigen Bereich D grafisch dar. Offenbar ist D gleich dem Durchschnittdes ersten Quadranten Q =

x ∈ R

2 : x ≥ Θ

mit den Halbebenen L(1, 1; 40) , L(1, 2; 60) undL(1, 0; 25) , wobei

L(α, β; δ) =x ∈ R

2 : α ξ1 + β ξ2 ≤ δ

ist. Dass L(α, β; δ) (falls |α|+ |β| > 0 gilt) eine der beiden Halbebenen ist, die durch die GeradeG(α, β; δ) =

x ∈ R

2 : α ξ1 + β ξ2 = δ

begrenzt werden, ergibt sich leicht aus der Beziehung

L(α, β; δ) =⋃

δ0≤δ

G(α, β; δ0) .

Es ergibt sich in unserem Beispiel folgendes Bild:

10 30 50

10

20

30

40

D

Auf der Geraden G(20, 25; δ) ist die Zielfunktion g(x) konstant gleich δ . Diese Gerade schneidetdie ξ2-Achse bei δ/25 . Wir haben also unter allen Geraden G(20, 25; δ) , die mit D wenigstenseinen Punkt gemeinsam haben, die mit maximalem δ zu suchen.

8.4. DER SIMPLEX-ALGORITHMUS 11

10 30 50

10

20

30

g(x)=500

g(x)=900

x*

D

Die Zielfunktion g(x) nimmt auf D den maximalen Wert 900 an, und zwar im Punkt

x∗ =

[2020

].

8.4 Der Simplex-Algorithmus

Wir bereiten die Beschreibung des Simplex-Algorithmus zur rechnerischen Losung eines linea-ren Optimierungsproblems in der Standardversion (8.11), (8.12) durch einige Definitionen undgrundlegende Aussagen vor.

Definition 8.1 Eine Teilmenge F ⊂ Rn heißt konvex, wenn mit zwei beliebigen Punkten

x1, x2 ∈ F auch die gesamte Verbindungstrecke

x1x2 =λx1 + (1 − λ)x2 : 0 ≤ λ ≤ 1

zu F gehort. Fur eine beliebige Anzahl von Vektoren x1, . . . , xp ∈ Rn und beliebige Zahlen λk ∈

[0, 1] mit

p∑

k=1

λk = 1 nennt man

x = λ1x1 + · · · + λpx

p

eine konvexe Linearkombination (oder kurz: Konvex-Kombination) der Vektoren xk , k =1, . . . , p . Diese konvexe Linearkombination heißt echt, wenn dabei alle λk positiv sind, d.h.λk > 0 , k = 1, . . . , p , gilt.

Satz 8.2 Der zulassige Bereich einer linearen Optimierungsaufgabe (LOA) ist konvex.


Ist der zulassige Bereich D einer LOA eine beschrankte Menge, so spricht man von einem kon-vexen Polyeder.

Definition 8.3 Es sei F ⊂ Rn eine konvexe Menge. Ein Punkt x ∈ F heißt Ecke von F , wenn

er nicht eine echte konvexe Linearkombination zweier verschiedener Punkte x1, x2 ∈ F ist.

Ein konvexes Polyeder im Rn mit n+1 Eckpunkten, welches nicht in einem (n−1)-dimensionalen

Unterraum des Rn liegt, nennt man Simplex.

Die folgenden zwei Theoreme bilden die Grundlage fur den Simplex-Algorithmus.

Theorem 8.4 Der zulassige Bereich D einer LOA besitzt hochstens endlich viele Ecken. IstD 6= ∅ , so besitzt D wenigsten einen Eckpunkt. Ist der zulassige Bereich D beschrankt, so nimmtdie Zielfunktion ihr Optimum in mindestens einer Ecke von D an. Ist der zulassige Bereichnicht beschrankt, nimmt aber die Zielfunktion ihr Optimum auf D an, so ist mindestens eineEcke Optimalpunkt.

Theorem 8.5 Es seien A ∈ Rm×n mit rank(A) = m < n und ak ∈ R

m , k = 1, . . . , n , dieSpalten von A . Fur ein

x =[

ξk

] n

k=1∈ D = x ∈ R

n : Ax = b, x ≥ Θ

bezeichnen wir mit ℓ(x) die Menge aller Spalten von A , die zu positiven Eintragen von x gehoren,d.h.

ℓ(x) =ak : k ∈ 1, . . . , n , ξk > 0

.

Dann ist x ∈ D genau dann eine Ecke von D , wenn das System ℓ(x) linear unabhangig ist. Zujeder Basis

B =y1, . . . , ym

⊂ S(A) :=

ak : k = 1, . . . , n

des Rm existiert hochstens eine Ecke x ∈ D mit ℓ(x) = B .

Eine Basis B des Rm mit ℓ(x) ⊂ B nennt man eine Basis zur Ecke x . Die Ecken von D

nennt man auch zulassige Basislosungen. Ist dabei die Zahl der Elemente von ℓ(x) kleinerals m (d.h. ℓ(x) ist noch keine Basis des R

m), so spricht man von einer entarteten zulassigenBasislosung.

Sind z.B. die letzten m Spaltenan−m+1, . . . , an

der Matrix A linear unabhangig, so kann

man mittels des Gaußschen Algorithmus (siehe Abschnitt 6.5) die Gleichung Ax = b auf dieaquivalente Form A1x = b1 =

[β1

j

] m

j=1bringen, wobei A1 die Gestalt

A1 =

α111 · · · α1

1,n−m 1 0

......

. . .

α1m1 · · · α1

m,n−m 0 1

(8.13)


hat. Nehmen wir an, dass alle β1j , j = 1, . . . ,m , nichtnegativ sind, so ist x1 =

[ξ1k

] n

k=1mit

ξ1k = 0 , k = 1, . . . , n − m , und ξ1

n−m+j = β1j , j = 1, . . . ,m , eine Ecke von D . Die ξn−m+j ,

j = 1, . . . ,m , nennt man dabei die Basisvariablen der zulassigen Basislosung x1 . Die Ba-sisvariablen einer zulassigen Basislosung entsprechen also den Spalten der Matrix A , die einezugehorige Basis im R

m bilden. (Im Fall einer entarteten zulassigen Basislosung muss eine solcheBasis nicht eindeutig festgelegt sein!) Der Wert g(x1) der Zielfunktion auf dieser Ecke ist danngleich

g(x1) = γn−m+1β11 + · · · + γnβ1

m . (8.14)

Wir stellen uns nun die Frage, wie man eine (benachbarte) Ecke von D finden kann, auf der derWert der Zielfunktion großer (bzw. wenigstens nicht kleiner) als auf x1 ist. Dazu suchen wir eineNichtbasisvariable ξk0 (d.h. k0 ∈ 1, . . . , n − m) und tauschen diese gegen eine Basisvariableξk1 (d.h. k1 ∈ n − m + 1, . . . , n) aus. Dabei mussen wir zusatzlich die Bedingung einhalten,dass die neue Basislosung x2 =

[ξ2k

] n

k=1von Ax = b zulassig bleibt.

1. Wahl von k0 :

Da Ax = b aquivalent zu A1x = b1 ist, muss also unter Berucksichtigung von (8.13) gelten

ξ2n−m+j = β1

j −n−m∑

k=1

α1jkξ

2k = β1

j − α1jk0

ξ2k0

, j ∈ 1, . . . ,m ,

ξ2k0

≥ 0 ,

ξ2j = 0 , j ∈ 1, . . . , n − m \ k0 .

Fur den entsprechenden Zielfunktionswert erhalten wir unter Verwendung von (8.14)

g(x2) =

n∑

j=1

γjξ2j

= γk0ξ2k0

+m∑

j=1

γn−m+j(β1j − α1

jk0ξ2k0

)

=

m∑

j=1

γn−m+jβ1j − ∆1

k0ξ2k0

= g(x1) − ∆1k0

ξ2k0

mit

∆1k =

m∑

j=1

γn−m+jα1jk − γk . (8.15)

Die Großen ∆k , k = 1, . . . , n , werden Optimalitatsindikatoren genannt. Es gilt namlichfolgender Satz.

Satz 8.6 Die zulassige Basislosung x1 ist genau dann optimal, wenn ∆1k ≥ 0 fur alle

k = 1, . . . , n gilt.


Offenbar ist ∆1k = 0 fur k = n − m + 1, . . . , n , automatisch erfullt. Ist also

min∆1

k : k = 1, . . . , n − m

< 0 ,

so wahlt man den Index k0 ∈ 1, . . . , n − m so, dass ∆1k0

< 0 ist. Man konnte z.B. dasAuswahlkriterium

∆k0 = min ∆k : k = 1, . . . , n − m (8.16)

verwenden.

2. Wahl von k1 :

Damit x2 zulassig ist, mussen noch die Bedingungen

ξ2n−m+j = β1

j − α1jk0

ξ2k0

≥ 0 , j = 1, . . . ,m ,

erfullt werden. Da die β1j , j = 1, . . . ,m , als nichtnegativ angenommen wurden und ξ2

k0

ebenso nichtnegativ zu wahlen ist, hat man k1 = n − m + j1 so zu bestimmen, dass

β1j1

α1j1k0

= min

Ωj :=

β1j

α1jk0

: j ∈ 1, . . . ,m , a1jk0

> 0

(8.17)

gilt. Was ist, wenn α1jk0

≤ 0 fur alle j = 1, . . . ,m gilt? Dazu der folgende Satz.

Satz 8.7 Existiert in einer zulassigen Basislosung x1 eine Nichtbasisvariable ξk0 mit ne-gativem Optimalitatsindikator ∆1

k0und der Eigenschaft α1

jk0≤ 0 , ∀ j = 1, . . . ,m , so ist

die LOA (8.11), (8.12) nicht losbar, d.h. die Zielfunktion g(x) ist auf D nach oben unbe-schrankt.

Beispiel 8.8 Wir betrachten die LOA aus Abschnitt 8.3. Dazu uberfuhren wir diese mittels derSchlupfvariablen η1 =: ξ3 , η2 =: ξ4 und η3 =: ξ5 in eine LOA der Gestalt (8.11), (8.12)

g(x) = 20 ξ1 + 25 ξ2 −→ Max ,

ξ1 + ξ2 + ξ3 = 40 ,

ξ1 + 2 ξ2 + ξ4 = 60 ,

ξ1 + ξ5 = 25 ,

ξk ≥ 0 , k = 1, . . . , 5 .

Wir haben also m = 3 und n = 5 . Außerdem ist die Matrix schon von der Gestalt (8.13), und

x1 =

00406025

mit g(x1) = 0


ist zulassige Basislosung. Als Optimalitatsindikatoren erhalten wir

∆11 = −20 und ∆1

2 = −25 ,

so dass das Kriterium (8.16) k0 = 2 liefert. Neue Basisvariable wird also ξ2 , so dass nebenξ21 = 0 die Gleichungen

ξ23 = 40 − ξ2

2 , ξ24 = 60 − 2 ξ2

2 , ξ25 = 25

erfullt sein mussen. Damit x2 zulassig bleibt, kann ξ22 maximal gleich 30 sein, so dass ξ4 zur

Nichtbasisvariablen wird. Wir erzeugen schließlich mittels des Gaußschen Algorithmus in derzweiten Spalte (weil k0 = 2) des Gleichungssystem den zweiten Einheitsvektor als Koeffizienten-vektor:

0.5 ξ1 + ξ3 − 0.5 ξ4 = 10 ,

0.5 ξ1 + ξ2 + 0.5 ξ4 = 30 ,

ξ1 + ξ5 = 25 .

Wir erhalten als zulassige Basislosung

x2 =

03010025

mit g(x2) = 750

und die entsprechenden Optimalitatsindikatoren

∆21 = 25 · 0.5 − 20 = −7.5 , ∆2

4 = 25 · 0.5 − 0 = 12.5 .

Also wird ξ1 neue Basisvariable und

ξ32 = 30 − 0.5 ξ3

1 , ξ33 = 10 − 0.5 ξ3

1 , ξ35 = 25 − ξ3

1 .

Fur die Zulassigkeit von x3 ist also ξ31 ≤ 20 zu erfullen, und somit wird ξ3 Nichtbasisvariable.

Der Gaußsche Algorithmus liefert

ξ1 + 2 ξ3 − ξ4 = 20 ,

ξ2 − ξ3 + ξ4 = 20 ,

2 ξ3 + ξ4 + ξ5 = 5

und damit als zulassige Basislosung

x3 =

2020005

mit g(x3) = 900 .


Die entsprechenden Optimalitatsindikatoren

∆33 = 20 · 2 + 25 · (−1) − 0 = 15 und ∆3

4 = 20 · (−1) + 25 · 1 − 0 = 5

sind samtlich positiv, was nach Satz 8.6 bedeutet, dass x3 optimal ist.

Zur ubersichtlichen Realisierung des eben beschriebenen Algorithmus verwendet man ein sog.Simplextableau, welches in dem Fall, dass die aktuelle Matrix von der Gestalt (8.13) ist, wiefolgt aussieht:

ξ1 · · · ξn−m ξn−m+1 ξn−m+2 · · · ξn

BV cBV γ1 · · · γn−m γn−m+1 γn−m+2 · · · γn xBV Ω

ξn−m+1 γn−m+1 α111 · · · α1

1,n−m 1 0 · · · 0 β11

ξn−m+2 γn−m+2 α121 · · · α1

2,n−m 0 1 · · · 0 β12

......

......

......

.... . .

......

ξn γn α1m1 · · · α1

m,n−m 0 0 · · · 1 β1m

∆11 · · · ∆1

n−m ∆1n−m+1 ∆1

n−m+2 · · · ∆1n g(x1)

In der ersten Spalte stehen die Bezeichnungen der Basisvariablen, in der zweiten die Werte derentsprechenden Zielfunktionskoeffizienten, in der vorletzten Spalte die Werte der Basisvariablender aktuellen zulassigen Basislosung und in der letzten Zeile die Optimalitatsindikatoren ∆k

(gleich dem Skalarprodukt aus der Spalte cBV und der k-ten Spalte der aktuellen Matrix ver-mindert um γk , siehe (8.15)) sowie der aktuelle Zielfunktionswert (gleich dem Skalarproduktaus den Spalten cBV und xBV ).

Im Beispiel 8.8 hat dieses Tableau also anfanglich folgendes Aussehen:

ξ1 ξ2 ξ3 ξ4 ξ5

BV cBV 20 25 0 0 0 xBV Ω

ξ3 0 1 1 1 0 0 40ξ4 0 1 2 0 1 0 60ξ5 0 1 0 0 0 1 25

−20 −25 0 0 0 0

Es sind nun folgende Schritte bzw. Tests auszufuhren:

1. Sind alle Optimatlitatsindikatoren nichtnegativ, so ist die aktuelle zulassige Basislosungoptimal (Satz 8.6).

2. Existiert eine Spalte im Tableau mit negativem Optimalitatsindikator und keinem positi-vem Matrixeintrag, so ist die LOA nicht losbar (Satz 8.7).

3. Anhand der letzten Zeile des Tableaus wahlt man nun eine Spalte (Index k0) aus, die dasKriterium (8.16) (oder wenigstens ∆k0 < 0) erfullt, und schreibt in die letzte Spalte dieentsprechenden Ωj (gleich dem Quotienten aus dem entsprechenden Eintrag in der SpaltexBV und dem Matrixeintrag in der ausgewahlten Spalte, siehe (8.17)) fur die Zeilen mitpositivem Matrixeintrag in der ausgewahlten Spalte.


Im Beispiel 8.8 wahlten wir die zweite Spalte aus:

ξ1 ξ2 ξ3 ξ4 ξ5

BV cBV 20 25 0 0 0 xBV Ω

ξ3 0 1 1 1 0 0 40 40ξ4 0 1 2 0 1 0 60 30ξ5 0 1 0 0 0 1 25

−20 −25 0 0 0 0

4. Die Basisvariable (Spalte BV des Tableaus), die in einer Zeile mit minimalem Ωj (Spal-te Ω des Tableaus) steht, wird zur Nichtbasisvariablen (vgl. (8.17)) und gemeinsam mitdem entsprechenden Zielfunktionskoeffizienten (Spalte cBV des Tableaus) gegen die neueVariable ξk0 bzw. den Zielfunktionskoeffizienten γk0 ausgetauscht.

5. Mittels des Gaußschen Algorithmus (angewendet auf die zu den Entscheidungsvariablenξ1, . . . , ξn gehorenden Spalten der Matrix A1 und auf die Spalte xBV ) werden in der zu ξk0

gehorenden Spalte der Matrix A1 in der zur neuen Basisvariablen gehorenden Zeile eineEins und sonst Nullen erzeugt.

Im Beispiel 8.8 erhielten wir:

ξ1 ξ2 ξ3 ξ4 ξ5

BV cBV 20 25 0 0 0 xBV Ω

ξ3 0 0.5 0 0 −0.5 0 10 20ξ2 25 0.5 1 0 0.5 0 30 60ξ5 0 1 0 0 0 1 25 25

−7.5 0 0 12.5 0 750

Hier haben wir gleich die neuen Optimalitatsindikatoren, den neuen Zielfunktionswert unddie neuen relevanten Ωj (bzgl. der zu ξ1 gehorenden Spalte) ausgerechnet. Dabei ist leichtnachzuvollziehen, dass (und dies gilt allgemein) sich die letzte Zeile im Tableau auch gleichdurch formale Einbeziehung dieser Zeile in den Gaußschen Algorithmus ergibt.

Der letzte Schritt im Beispiel 8.8 lieferte:

ξ1 ξ2 ξ3 ξ4 ξ5

BV cBV 20 25 0 0 0 xBV Ω

ξ1 20 1 0 2 −1 0 20ξ2 25 0 1 −1 1 0 20ξ5 0 0 0 −2 1 1 5

0 0 15 5 0 900


8.5 Endlichkeit des Simplex-Algorithmus

In der Simplexmethode konnen Situationen auftreten, in denen nicht mehr garantiert ist, dasseine optimale Losung nach endlich vielen Schritten erreicht wird.Entartete zulassige Basislosung. Sind in einer zulassigen Basislosung weniger als m Varia-ble positiv, so kann es sein, dass sich beim Ubergang zu einer benachbarten Basislosung derZielfunktionswert nicht andert.

Beispiel 8.9 Diese Folge von Simplex-Tableaus

ξ1 ξ2 ξ3 ξ4 ξ5 ξ6 ξ7

BV cBV 0.75 −150 0.02 −6 0 0 0 xBV Ω

ξ5 0 0.25 −60 −0.04 9 1 0 0 0 0ξ6 0 0.5 −90 −0.02 3 0 1 0 0 0ξ7 0 0 0 1 0 0 0 1 1

−0.75 150 −0.02 6 0 0 0 0

ξ1 0.75 1 −240 −0.16 36 4 0 0 0ξ6 0 0 30 0.06 −15 −2 1 0 0 0ξ7 0 0 0 1 0 0 0 1 1

0 −30 −0.14 33 3 0 0 0

ξ1 0.75 1 0 0.32 −84 −12 8 0 0 0ξ2 −150 0 1 0.002 −0.5 −1/15 1/30 0 0 0ξ7 0 0 0 1 0 0 0 1 1 1

0 0 −0.08 18 1 1 0 0

ξ3 0.02 3.125 0 1 −262.5 −37.5 25 0 0ξ2 −150 −1/160 1 0 0.025 1/120 −1/60 0 0 0ξ7 0 −3.125 0 0 262.5 37.5 −25 1 1 2/525

0.25 0 0 −3 −2 3 0 0

ξ3 0.02 −62.5 10500 1 0 50 −150 0 0 0ξ4 −6 −0.25 40 0 1 1/3 −2/3 0 0 0ξ7 0 62.5 −10500 0 0 −50 150 1 1

−0.5 120 0 0 −1 1 0 0

ξ5 0 −1.25 210 0.02 0 1 −3 0 0ξ4 −6 1/6 −30 −1/150 1 0 1/3 0 0 0ξ7 0 0 0 1 0 0 0 1 1

−0.5 120 0 0 −1 1 0 0

ξ5 0 0.25 −60 −0.04 9 1 0 0 0 0ξ6 0 0.5 −90 −0.02 3 0 1 0 0 0ξ7 0 0 0 1 0 0 0 1 1

−0.75 150 −0.02 6 0 0 0 0

erhalt man bei der Losung der LOA

0.75 ξ1 − 150 ξ2 + 0.02 ξ3 − 6 ξ4 −→ Max ,

8.5. ENDLICHKEIT DES SIMPLEX-ALGORITHMUS 19

0.25 ξ1 − 60 ξ2 − 0.04 ξ3 + 9 ξ4 ≤ 0 ,

0.5 ξ1 − 90 ξ2 − 0.02 ξ3 + 3 ξ4 ≤ 0 ,

ξ3 ≤ 1 ,

ξk ≥ 0 , k = 1, 2, 3, 4 ,

Nach einigen Schritten kehren wir also zum Ausgangstableau zuruck. Eine solche Zyklusbildungkann vermieden werden, wenn man die Auswahl der neuen Basisvariablen variiert, falls diesenicht eindeutig festgelegt ist. So konnte man in unserem Beispiel auch wie folgt vorgehen, undman erhalt eine optimale Losung.

ξ1 ξ2 ξ3 ξ4 ξ5 ξ6 ξ7

BV cBV 0.75 −150 0.02 −6 0 0 0 xBV Ω

ξ5 0 0.25 −60 −0.04 9 1 0 0 0 0ξ6 0 0.5 −90 −0.02 3 0 1 0 0 0ξ7 0 0 0 1 0 0 0 1 1

−0.75 150 −0.02 6 0 0 0 0

ξ5 0 0 −15 −0.03 7.5 1 −0.5 0 0ξ1 0.75 1 −180 −0.04 6 0 2 0 0ξ7 0 0 0 1 0 0 0 1 1 1

0 15 −0.05 10.5 0 1.5 0 0

ξ5 0 0 −15 0 7.5 1 −0.5 0.03 0.03ξ1 0.75 1 −180 0 6 0 2 0.04 0.04ξ3 0.02 0 0 1 0 0 0 1 1

0 15 0 10.5 0 1.5 0.05 0.05

Unendlich viele optimale Losungen. Diese Situation tritt auf, wenn fur eine vorliegendeoptimale Losung Optimalitatsindikatoren gleich Null sind, die zu Nichtbasisvariablen gehoren.Tauscht man eine solche Nichtbasisvariable gegen eine Basisvariable aus, kann man eventuelleine neue Basislosung berechnen, wobei sich naturlich der Zielfunktionswert nicht verandert.Dann sind auch alle konvexen Linearkombinationen der letzten beiden berechneten Basislosun-gen optimale Losungen.

Das folgende Beispiel zeigt ein solches Vorgehen.

Beispiel 8.10 Wir betrachten die LOA

3 ξ1 + 2ξ2 − 3ξ3 − 4ξ4 − ξ5 −→ Max ,

6 ξ1 − ξ2 + ξ3 = 25 ,

2ξ1 − 2 ξ2 + ξ4 = 8 ,

ξ1 + 4 ξ2 + ξ5 = 21 ,

ξk ≥ 0 , k = 1, 2, 3, 4, 5 .


ξ1 ξ2 ξ3 ξ4 ξ5

BV cBV 3 2 −3 −4 −1 xBV Ω

ξ3 −3 6 −1 1 0 0 25 25/6ξ4 −4 2 −2 0 1 0 8 4ξ5 −1 1 4 0 0 1 21 21

−30 5 0 0 0 −128

ξ3 −3 0 5 1 −3 0 1 0.2ξ1 3 1 −1 0 0.5 0 4ξ5 −1 0 5 0 −0.5 1 17 3.4

0 −25 0 15 0 −8

ξ2 2 0 1 0.2 −0.6 0 0.2ξ1 3 1 0 0.2 −0.1 0 4.2ξ5 −1 0 0 −1 2.5 1 16 16

0 0 5 0 0 −3

ξ2 2 0 1 −0.04 0 0.24 4.04ξ1 3 1 0 0.16 0 0.04 4.84ξ4 −4 0 0 −0.4 1 0.4 6.4

0 0 5 0 0 −3

Unendlich viele optimale Losungen konnen auch in einer Situation auftreten, bei der zwar derzulassige Bereich unbeschrankt ist, der optimale Zielfunktionswert aber endlich.

8.6 Die Zwei-Phasen-Methode

Im folgenden zeigen wir, wie man die Simplexmethode verwenden kann, um eine erste zulassigeBasislosung (falls eine solche existiert) fur die gegebene LOA der Form (8.11), (8.12) zu finden.

Dazu fuhren wir zusatzliche (kunstliche) Variable ζ1 =: ξn+1, . . . , ζm =: ξn+m ein und betrachtendie LOA

−ζ1 − · · · − ζm = −ξn+1 − · · · − ξn+m −→ Max ,

α11ξ1 + α12ξ2 + · · · + α1nξn + ξn+1 = β1 ,

α21ξ1 + α22ξ2 + · · · + α2nξn + ξn+2 = β2 ,

......

.... . .

...

αm1ξ1 + αm2ξ2 + · · · + αmnξn + ξn+m = βm ,

ξk ≥ 0 , k = 1, . . . , n + m .

Hinweis: Falls in der Matrix A bereits Einheitsvektoren als Spalten auftreten, so kann man dieZahl der zusatzlichen Variablen ζk entsprechend verringern.

8.6. DIE ZWEI-PHASEN-METHODE 21

Satz 8.11 Ist x∗ =[

ξ∗k]n+m

k=1eine optimale Losung der obigen Hilfsaufgabe, so ist im Fall

ξ∗n+1 = · · · = ξ∗n+m = 0 der Vektor x1 =[

ξ∗k] n

k=1eine zulassige Losung der LOA (8.11), (8.12).

Andernfalls ist der zulassige Bereich der LOA (8.11), (8.12) leer.

Hinweis: Wir sind naturlich nicht an einer zulassigen Losung der LOA (8.11), (8.12) schlechthininteressiert, sondern an einer zulassigen Basislosung. Ist x∗ nicht entartet, so ist x1 zulassigeBasislosung fur die LOA (8.11), (8.12). Sind im entarteten Fall unter den Basisvariablen keine derξn+1, . . . , ξn+m , so ist x1 auch eine entartete Basislosung fur die LOA (8.11), (8.12). Ansonstenmuss man durch geeignete Simplexschritte Basisvariablen unter den ξn+1, . . . , ξn+m erst nochgegen Nichtbasisvariable unter den ξ1, . . . , ξn austauschen.

Bemerkung 8.12 Die obige Hilfsaufgabe besitzt stets eine optimale Losung, da unter den ge-machten Voraussetzungen der zulassige Bereich nicht leer und die Zielfunktion auf diesem be-schrankt ist.

Beispiel 8.13 Bei der LOA

−3 ξ1 − 2ξ2 − 5ξ3 −→ Max ,

ξ1 + ξ2 ≥ 2 ,

ξ1 + ξ2 − ξ3 ≤ 0 ,

2 ξ1 + ξ2 + 4 ξ3 ≥ 20 ,

ξk ≥ 0 , k = 1, 2, 3 ,

fuhrt die Verwendung von nichtnegativen Schlupfvariablen η1 =: ξ4 , η2 =: ξ5 und η3 =: ξ6 nichtsofort zu einer zulassigen Basislosung:

ξ1 + ξ2 − ξ4 = 2 ,

ξ1 + ξ2 − ξ3 + ξ5 = 0 ,

2 ξ1 + ξ2 + 4 ξ3 − ξ6 = 20 ,

ξk ≥ 0 , k = 1, . . . , 6 .

Da aber bereits ein Einheitsvektor als Spalte in der Systemmatrix auftritt, genugt es, zwei zusatz-liche Variable ζ1 =: ξ7 und ζ2 =: ξ8 einzufuhren:

−ξ7 − ξ8 −→ Max ,

ξ1 + ξ2 − ξ4 + ξ7 = 2 ,

ξ1 + ξ2 − ξ3 + ξ5 = 0 ,

2 ξ1 + ξ2 + 4 ξ3 − ξ6 + ξ8 = 20 ,

ξk ≥ 0 , k = 1, . . . , 8 .


Der Simplexalgorithmus fur diese Hilfsaufgabe liefert nun die folgenden Tableaus:

ξ1 ξ2 ξ3 ξ4 ξ5 ξ6 ξ7 ξ8

BV cBV 0 0 0 0 0 0 −1 −1 xBV Ω

ξ7 −1 1 1 0 −1 0 0 1 0 2ξ5 0 1 1 −1 0 1 0 0 0 0ξ8 −1 2 1 4 0 0 −1 0 1 20 5

−3 −2 −4 1 0 1 0 0 −22

ξ7 −1 1 1 0 −1 0 0 1 0 2 2ξ5 0 1.5 1.25 0 0 1 −0.25 0 0.25 5 10/3ξ3 0 0.5 0.25 1 0 0 −0.25 0 0.25 5 10

−1 −1 0 1 0 0 0 1 −2

ξ1 0 1 1 0 −1 0 0 1 0 2ξ5 0 0 −0.25 0 1.5 1 −0.25 −1.5 0.25 2ξ3 0 0 −0.25 1 0.5 0 −0.25 −0.5 0.25 4

0 0 0 0 0 0 1 1 0

Da der Zielfunktionswert gleich 0 ist und keine der kunstlichen Variablen ξ7 und ξ8 Basisvariablegeblieben ist, konnen wir sofort zum Ausgangstableau der zweiten Phase ubergehen. Dabei sindgegenuber den vorhergehenden Tableaus die Zielfunktionskoeffizienten gegen die der ursprungli-chen Aufgabenstellung auszutauschen:

ξ1 ξ2 ξ3 ξ4 ξ5 ξ6

BV cBV −3 −2 −5 0 0 0 xBV Ω

ξ1 −3 1 1 0 −1 0 0 2ξ5 0 0 −0.25 0 1.5 1 −0.25 2ξ3 −5 0 −0.25 1 0.5 0 −0.25 4

0 0.25 0 0.5 0 1.25 −26

Da bereits alle Optimalitatsindikatoren nichtnegativ sind, haben wir die optimale Losung x∗ =[ξ1 ξ2 ξ3]

T = [2 0 4]T erhalten.

Beispiel 8.14 Betrachtet man die LOA

−ξ1 + ξ2 −→ Max ,

ξ1 + 2 ξ2 ≤ 4 ,

2 ξ1 + ξ2 ≥ 10 ,

ξ1, ξ2 ≥ 0 ,

so bietet es sich an, neben zwei Schlupfvariablen η1 =: ξ3 und η2 =: ξ4 eine weitere kunstlicheVariable ζ1 =: ξ5 einzufuhren und in der ersten Phase die Hilfsaufgabe

−ξ5 −→ Max ,

8.7. DUALITAT 23

ξ1 + 2 ξ2 + ξ3 = 4 ,

2 ξ1 + ξ2 − ξ4 + ξ5 = 10 ,

ξk ≥ 0 , k = 1, . . . , 5 ,

zu losen:

ξ1 ξ2 ξ3 ξ4 ξ5

BV cBV 0 0 0 0 −1 xBV Ω

ξ3 0 1 2 1 0 0 4 4ξ5 −1 2 1 0 −1 1 10 5

−2 −1 0 1 0 −10

ξ1 0 1 2 1 0 0 4ξ5 −1 0 −3 −2 −1 1 2

0 3 2 1 0 −2

Da der optimale Zielfunktionswert negativ ist, ist der zulassige Bereich der ursprunglichen LOAleer.

8.7 Dualitat

Gegeben seien eine Matrix A =[

αjk

] m n

j=1,k=1∈ R

m×n und zwei Vektoren b =[

βj

] m

j=1∈ R

m ,

c =[

γk

] n

k=1∈ R

n . Wir betrachten die LOA

γ1ξ1 + γ2ξ2 + · · · + γnξn −→ Max ,

α11ξ1 + α12ξ2 + · · · + α1nξn ⋄1 β1 ,

α21ξ1 + α22ξ2 + · · · + α2nξn ⋄2 β2 ,

......

...

αm1ξ1 + αm2ξ2 + · · · + αmnξn ⋄m βm ,

ξk ≥ 0 , k = 1, . . . , n0 ≤ n .

(P)


Dabei kann fur ⋄j ein beliebiges der Zeichen ≤ , = oder ≥ stehen. Zu dieser sogenannten pri-malen Aufgabe konstruieren wir nach gewissen Regeln die entsprechende duale Aufgabe:

β1η1 + β2η2 + · · · + βmηm −→ Min ,

α11η1 + α21η2 + · · · + αm1ηm ≥ γ1

α12η1 + α22η2 + · · · + αm2ηm ≥ γ2

......

...

α1,n0η1 + α2,n0η2 + · · · + αm,n0ηm ≥ γn0

α1,n0+1η1 + α2,n0+1η2 + · · · + αm,n0+1ηm = γn0+1

......

...

α1nη1 + α2nη2 + · · · + αmnηm = γn

ηj ⋄Tj 0 , j ∈ ω ,

(D)

wobeiω = ℓ = 1, . . . ,m, fur die ⋄ℓ nicht das Gleichheitszeichen ist

und ≤T gleich ≥ und ≥T gleich ≤ zu setzen sind.

Beispiel 8.15 Die duale Aufgabe zu

〈x, c〉 −→ Max ,

Ax = b ,

x ≥ Θ ,

lautet〈y, b〉 −→ Min ,

AT y ≥ c .

Aus Ax = b , x ≥ θ und c ≤ AT y folgt dabei

〈x, c〉 ≤⟨x,AT y

⟩= 〈y,Ax〉 = 〈y, b〉

(vgl. Theorem 8.19).

Beispiel 8.16 Die duale Aufgabe zu

12 ξ1 + 13 ξ2 − 9 ξ4 −→ Max ,

ξ1 − ξ2 + ξ3 − ξ4 = 5

2 ξ1 + 7 ξ2 + 2 ξ4 ≤ 6

3 ξ1 − 8 ξ2 + 4 ξ3 ≥ 3

ξ1 ≥ 0 , ξ2 ≥ 0 , ξ4 ≥ 0 ,

8.7. DUALITAT 25

ist die Aufgabe5 η1 + 6 η2 + 3 η3 −→ Min ,

η1 + 2 η2 + 3 η3 ≥ 12 ,

−η1 + 7 η2 − 8 η3 ≥ 13 ,

η1 + 4 η3 = 0 ,

−η1 + 2 η2 ≥ −9 ,

η2 ≥ 0 , η3 ≤ 0 .

Wir bezeichnen mit DP und DD die zulassigen Bereiche der LOA (P) bzw. der LOA (D).

Theorem 8.17 Die LOA (P) ist genau dann losbar, wenn die LOA (D) losbar ist. Ist derzulassige Zielfunktionswert der LOA (P) auf DP nach oben unbeschrankt, so gilt DD = ∅ . Istder Zielfunktionswert der LOA (D) auf DD nach unten nicht beschrankt, so ist DP leer.

Folgerung 8.18 Sind also beide zulassigen Bereiche DP und DD nicht leer, so sind auch beideLOA losbar.

Theorem 8.19 Sind DP 6= ∅ und DD 6= ∅ , so gilt

〈x, c〉 ≤ 〈y, b〉 ∀x ∈ DP , ∀ y ∈ DD . (8.18)

Die zulassigen Losungen x∗ ∈ DP und y∗ ∈ DD sind genau dann optimale Losungen der ent-sprechenden LOA, wenn 〈x∗, c〉 = 〈y∗, b〉 gilt.

Folgerung 8.20 Nach (8.18) ist also die Differenz des Zielfunktionswertes 〈x, c〉 einer zulassi-gen Losung der primalen Aufgabe zum optimalen Zielfunktionswert dieser Aufgabe nicht großerals 〈y, b〉 − 〈x, c〉 , wobei y ∈ DD beliebig ist.

Theorem 8.21 Sind die zulassigen Losungen x∗ =[

ξ∗k] n

k=1∈ DP und y∗ =

[η∗j] m

j=1∈ DD

optimale Losungen der entsprechenden LOA, so gilt

m∑

j=1

αjkη∗j − γk

ξ∗k = 0 , k = 1, . . . , n , (8.19)

und (n∑

k=1

αjkξ∗k − βj

)η∗j = 0 , j = 1, . . . ,m . (8.20)

Beispiel 8.22 Der Vektor x∗ =[

0 14 1]T

ist eine zulassige Losung der LOA

6 ξ1 + 10 ξ2 + 12 ξ3 −→ Max ,


ξ1 + 2 ξ2 + 4 ξ3 ≤ 32 ,

2 ξ1 + ξ2 + 2 ξ3 ≤ 42 ,

3 ξ1 + 2 ξ2 + 2 ξ3 ≤ 30 ,

ξ1, ξ2, ξ3 ≥ 0 .

Unter Verwendung von (8.19) und (8.20) findet man die zulassige Losung y∗ =[

1 0 4]T

der dualen LOA

32 η1 + 42 η2 + 30 η3 −→ Min ,

η1 + 2 η2 + 3η3 ≥ 6 ,

2 η1 + η2 + 2 η3 ≥ 10 ,

4 η1 + 2 η2 + 2 η3 ≥ 12 ,

η1, η2, η3 ≥ 0 .

Da die beiden entsprechenden Zielfunktionswerte ubereinstimmen, sind nach Theorem 8.19 x∗

und y∗ optimale Losungen der jeweiligen LOA.

Um zu zeigen, dass die optimale Losung y∗ =[

η∗j] m

j=1der dualen Aufgabe zur Bewertung

der einzelnen Restriktionen der primalen Aufgabe herangezogen werden kann, betrachten wirfolgende Situation: Ein Betrieb moge die Produkte P1, . . . , Pn unter Verwendung der Rohstoffebzw. Ausgangsprodukte R1, . . . , Rm herstellen. In der Maximierungsaufgabe in Standardform

n∑

k=1

γkξk −→ Max ,

n∑

k=1

αjkξk ≤ βj , j = 1, . . . ,m ,

ξk ≥ 0 , k = 1, . . . , n ,

sollen die vorkommenden Großen folgende Bedeutung haben:

- γk : Gewinn pro produzierter ME des Produktes Pk ,

- βj : verfugbare MEn der Resource Rj ,

- αjk : zu verwendende MEn von Rj zur Produktion von Pk ,

- ξk : zu produzierende MEn von Pk .

Ist nun x∗ =[

ξ∗k] n

k=1optimale Losung dieser Aufgabe, so gilt nach Theorem 8.19

〈c, x∗〉 = 〈y∗, b〉 =

m∑

j=1

βjη∗j .

8.7. DUALITAT 27

Ferner besagt die Beziehung (8.20), dass η∗j = 0 gilt, falls Rj nicht vollstandig verbrauchtwird. Hat also die Dualvariable η∗j einen großen Wert, so wirken sich Veranderungen in derentsprechenden Resource Rj stark auf die Veranderung des optimalen Zielfunktionswertes aus.

Die η∗j werden auch Schattenpreise genannt, da sie den Aufwand pro zusatzlich zu beschaffenderME der Resource Rj unter der Annahme beschreiben, dass der gesamte zusatzliche Aufwandgleich dem dadurch erzielten Gewinn ist (im weiteren sei x∗ eine nicht entartete Basislosung):Bezeichnen wir diese Schattenpreise vorerst mit πj , so ist es sinnvoll πj = 0 zu setzen, fallsn∑

k=1

αjkξ∗k < βj ist. Andererseits ist fur ξ∗k > 0 der durch Anderung um ∆ξ∗k erzielte Gewinn

gleich γk∆ξ∗k , und dieser soll gleich

m∑

j=1

αjkπj∆ξ∗k sein, d.h.

m∑

j=1

αjkπj = γk .

Also genugen x∗ =[

ξ∗k] n

k=1und y∗ =

[η∗j] m

j=1mit η∗j = πj den Bedingungen (8.19) und

(8.20).

An dieser Stelle sei bemerkt, dass (8.19) und (8.20) im Falle der Zulassigkeit von x∗ und y∗ auchhinreichend fur die Optimalitat von x∗ und y∗ sind, da aus diesen beiden Beziehungen

〈y∗, b〉 =

m∑

j=1

βjη∗j =

m∑

j=1

n∑

k=1

αjkξ∗kη

∗j =

n∑

k=1

m∑

j=1

αjkη∗j ξ

∗k =

n∑

k=1

γkξ∗k = 〈x∗, c〉

folgt und nur noch Theorem 8.19 anzuwenden bleibt.

Beispiel 8.23 Ein Landwirt kann fur ein 500 ha großes Stuck Land, welches er fur den Anbauvon Raps, Weizen, Gerste und Mais vorgesehen hat, wahrend der Vegationszeit insgesamt 550Arbeitsstunden aufwenden. Flachenbedarf der einzelnen Fruchte, Arbeitsaufwand und Gewinnsind der folgenden Tabelle zu entnehmen:

Anbauflache (in ha) Gesamtarbeitszeit (in h) Gewinn (in e)pro kg Saatgut pro kg Saatgut pro kg Saatgut

Raps 1,2 1,6 18Weizen 0,5 0,5 9Gerste 0,8 1,0 17Mais 1,6 2,0 20

Welche und wieviel Fruchte sollte der Landwirt anbauen, um den Gewinn zu maximieren?

18 ξ1 + 9 ξ2 + 17 ξ3 + 20 ξ4 −→ Max ,

1, 2 ξ1 + 0, 5 ξ2 + 0, 8 ξ3 + 1, 6 ξ4 ≤ 500 ,

1, 6 ξ1 + 0, 5 ξ2 + 1, 0 ξ3 + 2, 0 ξ4 ≤ 550 ,

ξ1, ξ2, ξ3, ξ4 ≥ 0 .


Wir losen vorerst das zur Gewinnmaximierung duale Problem

500 η1 + 550 η2 −→ Min ,

1, 2 η1 + 1, 6 η2 ≥ 18 ,

0, 5 η1 + 0, 5 η2 ≥ 9 ,

0, 8 η1 + 1, 0 η2 ≥ 17 ,

1, 6 η1 + 2, 0 η2 ≥ 20 ,

η1, η2 ≥ 0 ,

unter Verwendung der Zwei-Phasen-Methode:

η1 η2 η3 η4 η5 η6 η7 η8 η9 η10

BV cBV 0 0 0 0 0 0 −1 −1 −1 −1 yBV Ω

η7 −1 6/5 8/5 −1 0 0 0 1 0 0 0 18 45/4η8 −1 1/2 1/2 0 −1 0 0 0 1 0 0 9 18η9 −1 4/5 1 0 0 −1 0 0 0 1 0 17 17η10 −1 8/5 2 0 0 0 −1 0 0 0 1 20 10

−41/10 −51/10 1 1 1 1 0 0 0 0 −64

η7 −1 −2/25 0 −1 0 0 4/5 1 0 0 −4/5 2 5/2η8 −1 1/10 0 0 −1 0 1/4 0 1 0 −1/4 4 16η9 −1 0 0 0 0 −1 1/2 0 0 1 −1/2 7 14η2 0 4/5 1 0 0 0 −1/2 0 0 0 1/2 10

−1/50 0 1 1 1 −31/20 0 0 0 51/20 −13

η6 0 −1/10 0 −5/4 0 0 1 5/4 0 0 −1 5/2η8 −1 1/8 0 5/16 −1 0 0 −5/16 1 0 0 27/8 54/5η9 −1 1/20 0 5/8 0 −1 0 −5/8 0 1 0 23/4 46/5η2 0 3/4 1 −5/8 0 0 0 5/8 0 0 0 45/4

−7/40 0 −15/16 1 1 0 31/16 0 0 1 −73/8

η6 0 0 0 0 0 0 1 0 0 2 −1 14η8 −1 1/10 0 0 −1 1/2 0 0 1 −1/2 0 1/2 1η3 0 4/50 0 1 0 −8/5 0 −1 0 8/5 0 46/5η2 0 4/5 1 0 0 −1 0 0 0 1 0 17

−1/10 0 0 1 −1/2 0 1 0 3/2 1 −1/2

η6 0 0 0 0 0 0 1 14η5 0 1/5 0 0 −2 1 0 1η3 0 2/5 0 1 −16/5 0 0 54/5η2 0 1 1 0 −2 0 0 18

0 0 0 0 0 0 0

8.7. DUALITAT 29

η1 η2 η3 η4 η5 η6

BV cBV −500 −550 0 0 0 0 yBV Ω

η6 0 0 0 0 0 0 1 14η5 0 1/5 0 0 −2 1 0 1 5η3 0 2/5 0 1 −16/5 0 0 54/5 27η2 −550 1 1 0 −2 0 0 18 18

−50 0 0 1100 0 0 −9900

η6 0 0 0 0 0 0 1 14η1 −500 1 0 0 −10 5 0 5η3 0 0 0 1 −12/5 −4 0 44/5η2 −550 0 1 0 8 −5 0 13

0 0 0 600 250 0 −9650

Wir erhalten also η∗1 = 5 und η∗2 = 13 . Dabei sind die erste und die vierte Restriktion mit “>”erfullt, woraus wegen (8.19) ξ∗1 = ξ∗4 = 0 folgt. Aus (8.20) ergeben sich weiterhin die Gleichungen

0, 5 ξ∗2 + 0, 8 ξ∗3 = 500 und 0, 5 ξ∗2 + ξ∗3 = 550 ,

also ξ∗2 = 600 , ξ∗3 = 250 .

Beispiel 8.24 Ein Mensch benotigt wochentlich mindestens 200 mg Vitamin B, 720 mg VitaminC und 60 mg Vitamin H. In einer Apotheke gibt es zwei Sorten von Tabletten T1 und T2 zumPreis von 1e bzw. 2e pro Stuck und mit folgenden Vitaminanteilen in mg:

T1 T2

Vitamin B 20 20Vitamin C 180 60Vitamin H 5 15

Wieviel Stuck pro Sorte sind wochentlich notig, um den Bedarf bei minimalen Kosten zu decken?

η1 + 2 η2 −→ Min ,

20 η1 + 20 η2 ≥ 200 ,

180 η1 + 60 η2 ≥ 720 ,

5 η1 + 15 η2 ≥ 60 ,

η1, η2 ≥ 0 .

Wir losen das zugehorige duale Problem

20 ξ1 + 720 ξ2 + 60 ξ3 −→ Max ,

20 ξ1 + 180 ξ2 + 5 ξ3 ≤ 1 ,

20 ξ1 + 60 ξ2 + 15 ξ3 ≤ 2 ,

ξ1, ξ2, ξ3 ≥ 0 .


ξ1 ξ2 ξ3 ξ4 ξ5

BV cBV 200 720 60 0 0 xBV Ω

ξ4 0 20 180 5 1 0 1 1/180ξ5 0 20 60 15 0 1 2 1/30

−200 −720 −60 0 0 0

ξ2 720 1/9 1 1/36 1/180 0 1/180 1/20ξ5 0 40 0 40 1 3 6 3/20

−120 0 −40 4 0 4

ξ1 200 1 9 1/4 1/20 0 1/20 1/5ξ5 0 0 −120 10 −1 1 1 1/10

0 1080 −10 10 0 10

ξ1 200 1 12 0 3/40 −1/40 1/40ξ3 60 0 −12 1 −1/10 1/10 1/10

0 960 0 9 1 11

In den zwei Spalten, die zu den Schlupfvariablen gehoren, stehen in der letzten Zeile des letzten

Tableaus die Werte 9 und 1. Offenbar ist y∗ =

[91

]zulassig fur das ursprungliche Minimum-

Problem. Ausserdem gilt 1 · 9 + 2 · 1 = 11 , so dass nach Theorem 8.19 y∗ optimale Losung ist(vgl. Bem. 8.25).

Bemerkung 8.25 Fur A ∈ Rm×n , b ∈ R

m (b ≥ Θ) und c ∈ Rn betrachten wir das Maximie-

rungsproblem〈x, c〉 −→ Max ,

Ax ≤ b ,

x ≥ Θ ,

(P1)

und das zugehorige duale Problem

〈y, b〉 −→ Min ,

AT y ≥ c ,

y ≥ Θ .

(D1)

Wir nehmen an, dass wir auf das Problem (P1) unter Verwendung von Schlupfvariablen dieSimplexmethode angewandt und im letzten Schritt das folgende Simplex-Tableau erhalten haben:

ξ1 · · · ξn ξn+1 · · · ξn+m

BV cBV γ1 · · · γn 0 · · · 0 xBV Ω

∗ ∗ αr11 · · · αr

1n αr1,n+1 · · · αr

1,n+m βr1

∗ ∗ α121 · · · α1

2n αr2,n+1 · · · αr

2,n+m βr2

......

......

......

......

...∗ ∗ αr

m1 · · · αrmn αr

m,n+1 · · · αrm,n+m βr

m

∆r1 · · · ∆r

n ∆rn+1 · · · ∆r

n+m g(xr)

8.8. UBUNGSAUFGABEN 31

Dann ist

y∗ =

∆rn+1

...∆r

n+m

optimale Losung der dualen Aufgabe (D1).

8.8 Ubungsaufgaben

1. Eine Firma stellt Herrenparfum her, dessen Absatz mit Hilfe geeigneter Werbemaßnah-men in Zeitschriften beeinflusst werden soll. Zur Auswahl der Werbemittel sollen nur reinquantitative Kriterien zum Zuge kommen, namlich Kosten pro Anzeige und streutechni-sche Gesichtspunkte, d. h. die Reichweite der Zeitschriften. Es stehen zwei Zeitschriften zurAuswahl. Die Kosten fur eine ganzseitige Anzeige (1/1 Seite, vierfarbig) betrage in Zeit-schrift 1 70 000e und in Zeitschrift 2 40 000e (je Anzeige und Auflage). Die Anzahl derin Zeitschrift 1 und 2 aufzugebenden (ganzseitigen) Anzeigen x1 und x2 ist unter folgendenBedingungen zu bestimmen:

(a) Die Gesamtkosten K sind zu minimieren.

(b) In der Zeitschrift 1 sollen mindestens vier Anzeigen und in Zeitschrift 2 mindestenssechs Anzeigen erscheinen.

(c) Auf Grund von Mediaanalysen sei festgestellt, dass Zeitschrift 1 von 3 Millionen undZeitschrift 2 von 2 Millionen mannlichen Lesern regelmaßig gelesen und die Anzei-gen wahrgenommen werden. Es wird dabei unterstellt, dass eine in den Zeitschriftenmehrfach platzierte Anzeige auch entsprechend mehrfach wahrgenommen wird. Ge-fordert wird, dass die Anzeigen von den mannlichen Lesern der beiden Zeitschrifteninsgesamt mindestens 36 Millionen mal wahrgenommen werden.

(d) Von den durch die Mediaanalyse ermittelten 2,4 Millionen mannlichen Lesern derZeitschrift 1, die monatlich mindestens 3000e verdienen bzw. von den 1 Millionenmannlichen Lesern der Zeitschrift 2, die ebenfalls mindestens 3000e im Monat ver-dienen, sollen die Anzeigen insgesamt mindestens 24 Millionen mal wahrgenommenwerden.

Hinweis: Formulieren Sie ein lineares Optimierungsproblem und losen Sie es grafisch unterVernachlassigung des Ganzzahligkeitsgesichtspunktes!

2. Im Wohnheim ist eine große Weihnachtsfeier geplant. Nachdem die veranstaltenden Erst-semester in der Mathe-Vorlesung bereits die Lineare Optimierung kennengelernt haben,wollen sie ihre Kenntnisse endlich auch zu ihrem Vorteil einsetzen konnen und versuchen,den benotigten Gluhweinbedarf des Abends nach okonomischen Gesichtspunkten zusam-menzustellen. Folgende Informationen tragen sie zusammen:

• 25 Liter Gluhwein sollen aus trockenem Rotwein, Rum und Holunderbeersaft herge-stellt werden.


• Zwecks guter Stimmung soll der Alkoholgehalt zwischen 20 und 25 Vol.-% liegen.

• Der Zuckergehalt soll aber hochstens 20 Vol.-% betragen.

• Sieben Literflaschen gekauften Gluhweins vom letzten Jahr sollen vollstandig aufge-braucht werden.

• Der beigemischte Rum soll hochstens 20% der fertigen Mischung ausmachen, der zu-gegebene Holunderbeersaft weniger als 25%, wohingegen der trockene Rotwein min-destens zu 10% enthalten sein soll.

• Es soll trotz zum Teil teurer Zutaten ein moglichst billiges Getrank entstehen.

Von den Etiketten der verschiedenen Flaschen laßt sich noch folgendes erfahren:

Alkohol [Vol.-%] Zucker [Vol.-%] Preis[e/ℓ]

Rotwein 12 10 2,99fertiger Gluhwein 19 30 3,49Rum 60 5 19,95Holunderbeersaft 0 15 4,49

Wie laßt sich dieses Problem mathematisch modellieren?

3. In einer Fertigungsabteilung werden aus Stahlblechen einer vorgegebenen Breite von 200cm kleinere Bleche der Breiten 85 cm, 60 cm und 45 cm gefertigt. Die Lange der ursprung-lichen Bleche und der zu fertigenden schmaleren Bleche stimmen uberein. Der Bedarf anden drei Blechteilen betragt:

Breite (in cm) 85 60 45

Menge (in Stuck) 450 800 700

Erstellen Sie ein lineares Optimierungsmodell fur dieses Zuschnittproblem unter der Ziel-setzung der Minimierung des Materialverlustes.

4. Zu losen sind die folgenden Aufgaben:

(a) 2x1 + 3x2 −→ max

2x1 + x2 ≤ 2

−3x1 − x2 ≤ −2

x1, x2 ≥ 0

(b) 2x1 + 3x2 −→ max

2x1 + x2 ≤ 2

−3x1 − x2 ≤ −4

x1, x2 ≥ 0

(c) − x2 −→ min

−x1 + x2 ≤ 0

x1 ≥ 2

x2 ≥ 1

(d) x1 − x2 −→ min

−x1 + x2 ≤ 0

x1 ≥ 2

x2 ≥ 1

5. Losen Sie die folgenden linearen Optimierungsprobleme mit Hilfe des Simplexalgorithmus!


(a) x1 + x2 −→ max

−x1 + 2x2 ≤ 2

x1 ≤ 2

x1, x2 ≥ 0

(b) x1 − x2 −→ max

2x1 + x2 − x3 ≤ 8

x1 + x2 − 2x3 ≤ 6

x1, x2, x3 ≥ 0

(c) −3x1 + 2x2 − 2x3 + x4 − x5 −→ min

2x1 − x2 + x3 = 6

x1 − 4x2 + x4 = 8

2x1 − 2x2 + x5 = 12

x1, x3, x4, x5 ≥ 0

x2 ≤ 0

(d) 3x1 + x2 − x3 −→ max

x1 + 2x2 + x3 = 8

2x1 + 2x2 + 3x3 = 12

x1, x2, x3 ≥ 0

(e) x1 − x2 + x3 −→ max

2x1 + x2 + x3 ≤ 6

x1 − x2 + 2x3 ≥ 8

x1 + x2 + 2x3 = 6

x1, x2, x3 ≥ 0

(f) −x1 − x2 −→ min

−x1 + x2 + x3 + x4 = 1

x1 − 2x2 + x4 = 1

x1, x2, x3, x4 ≥ 0

6. In einer Tischlerei werden unter anderem drei Sorten Tische produziert. Die Lieferungeiner gewissen Anzahl von Tischen wurde bereits vertraglich vereinbart.


(a) Es ist ein Modell zu erstellen, das einen maximalen Gewinn realisiert und die ange-gebenen Zeit- bzw. Materialkapazitaten einhalt!

(b) Aus Rentabilitatsgesichtspunkten soll in der Tischlerei die Produktion der Tischsorte2 nach Lieferung der bereits bestellten zwei Einheiten eingestellt werden. Wie siehtunter diesen Gegebenheiten der optimale Produktionsplan aus? (Hinweis: Nach Um-stellung ist eine grafische Losung moglich.)

in gewissen Einheiten Tisch1 Tisch2 Tisch3 Kap.

Gewinn je Stuck 3 1 2

Zeitaufwand je Stuck 2 1 1 40

Materialaufwand je Stuck 4 2 3 100

vereinbarte Menge 3 2 2

7. Ist der Vektor x = (4, 0, 2, 0)T optimal fur die folgende lineare Optimierungsaufgabe?Begrunden bzw. beweisen Sie Ihre Antwort, indem Sie die duale Aufgabe aufstellen undanalysieren!

5x1 + 2x2 + 4x3 + x4 −→ max

x1 + 3x2 + 4x3 + 4x4 = 12

4x1 + x2 + x3 + 3x4 = 18

xi ≥ 0, i = 1, . . . , 4

8. Finden Sie die optimale Losung der folgenden Aufgabe mit Hilfe der dualen Aufgabe:

(P )

x1 +2x2 +3x3 · · · +nxn → min

x1 ≥ 1

x1 +x2 ≥ 2

...

x1 +x2 +x3 · · · +xn ≥ n

x1, . . . , xn ≥ 0

Kapitel 9

Kryptographie

9.1 Grundprobleme der Kryptographie

9.1.1 Geheimhaltung

Aufgabenstellung: Ubermittlung einer Nachricht, ohne dass ein Unbeteiligter Kenntnis vondieser erhalt.

Kryptographische Maßnahme: Verschlusselung (Entstellung) der Nachricht, die nur derberechtigte Empfanger mittels einer geheimen Zusatzinformation (dem Schlussel) lesen(entschlusseln) kann.

Kryptographische Verfahren: Unterscheidung nach Verschlusselungsvorgang

- symmetrische Verfahren: Sender und Empfanger benotigen den geheimen Schlusselund konnen dadurch auch ihre Rollen vertauschen.

- asymmetrische Verfahren: Der Sender verschlusselt seine Nachricht nur mit Hil-fe offentlich zuganglicher Daten, der geheime Schlussel verbleibt beim Empfanger(Public-Key-Verfahren).

9.1.2 Authentifikation

Aufgabenstellungen: Zweifelsfreie Ausweisung gegenuber anderen. Absichern, dass eineempfangene Nachricht tatsachlich vom angegebenen Sender stammt.

Methoden:

- Teilnehmerauthentifikation (peer entity authentication): Nachweis der Identitateiner Person oder Instanz

Beispiele: Personalausweis, Geheimzahl (PIN, Geheimnis, Parole), Fingerabdruck,Unterschrift

Die Kryptographie beschaftigt sich vornehmlich mit dem Nachweis der Identitat durchgeheimes Wissen.

35

36 KAPITEL 9. KRYPTOGRAPHIE

Problem: Wie kann ich den anderen davon uberzeugen, dass ich ein bestimmtes Ge-heimnis besitze? Hier gibt es zwei Ebenen der Unterscheidung:

1. Wird das Geheimnis direkt ubermittelt oder wird das Geheimnis selbst nichtubertragen, sondern indirekt erschlossen?

2. Braucht der Andere zur Identifikation mein Geheimnis oder kommt er mit allge-mein zuganglichen Daten aus?

- Nachrichtenauthentifikation (message authentication): Nachweis des Ursprungseiner Nachricht und Erkennen von Veranderungen der Nachricht

Beispiele: Unterschrift, Siegel oder Dienststempel unter einem Dokument, Echtheits-merkmale in Geldscheinen, Falschungssicherheit (z.B. Einschweißen des Personalaus-weises in Plastik)

Der Ersteller eines Dokumentes besitzt also ein Geheimnis (oder eine Fahigkeit), mitdem (der) er das Dokument authentisch macht.

Unterscheidungsebenen wie bei der Teilnehmerauthentifikation

9.1.3 Anonymitat

Aufgabenstellung: Teilnahme an einem Informationsaustausch, ohne dabei erkannt zu wer-den

Es soll also nicht (nur) die Nachricht geheim bleiben, sondern der Sender, der Empfangerund/oder die Tatsache, dass beide kommuniziert haben.

9.1.4 Protokolle

Unter einem Protokoll versteht man eine Gesamtheit von Regeln, nach denen Personen oderInstanzen miteinander kommunizieren.

Beispiele:

- Geschaftsordnungen von Gremien

- Ablauf zum Abheben von Geld an einem Geldautomaten: Einfuhren der Geldkarte, Ein-geben der Geheimzahl, Eingeben des gewunschten Betrages, Entnehmen der Geldkarte,Entnehmen des Geldes

9.1.5 Vermeidung von Ubertragungsfehlern (Prufziffernverfahren)

Haufige Fehlerquellen bei der Ubertragung von Nachrichten sind

- die einfache Vertauschung von Ziffern,

- die mehrfache Vertauschung von Ziffern,

- zu viele oder zu wenige Ziffern.

Solche Ubertragungsfehler konnen durch Prufziffernverfahren erkannt bzw. vermieden werden.

9.2. ZAHLENTHEORETISCHE GRUNDLAGEN 37

Beispiel 9.1 Die ISBN (Internationale Standard-Buchnummer) eines Buches besteht aus denneun Informationsziffern z1, . . . , z9 und einer Prufziffer z10 . Die Informationsziffern konnen dieWerte von 0 bis 9 annehmen. Dabei kennzeichnet die erste Ziffer Lander bzw. Landergruppen, diefolgenden drei Ziffern den Verlag bzw. die Verlagsgruppe. Die restlichen funf Ziffern beinhaltenTitelinformationen. Die Prufziffer z10 ∈ 0, 1, . . . , 9,X ergibt sich als Rest der Prufsumme1 · z1 + 2 · z2 + · · · + 9 · z9 bei Division durch 11,

1 · z1 + 2 · z2 + · · · + 9 · z9 ≡ z10 mod 11 .

Beispiele: ISBN 3-486-25783-8, ISBN 3-519-12098-4

Die ISBN zeigt folgende Fehler an:

1. Verwechslung einer Ziffer,

2. Vertauschung benachbarter Ziffern,

3. Vertauschung einer Ziffer mit einer beliebigen anderen Ziffer.

Eine gleichzeitige Anderung von zwei Informationsziffern wird i.a. nicht bemerkt. Sind z.B.z1 = 3 und z3 = 2 , so andert sich der Rest der Prufsumme bei Division durch 11 nicht, wennz1 auf 6 und z3 auf 1 abgeandert wird.

9.2 Zahlentheoretische Grundlagen

9.2.1 Der Euklidische Algorithmus

Satz 9.2 (Division mit Rest) Fur a ∈ Z und b ∈ Z∗ := ±1,±2, . . . existiert genau ein

Paar (q, r) ∈ Z2 ganzer Zahlen mit den Eigenschaften 0 ≤ r < |b| und a = b q + r . (Dabei heißt

r Rest bei der Division von a durch b .)

Man sagt, dass eine ganze Zahl b die ganze Zahl a teilt (in Zeichen: b|a), wenn r = 0 gilt, d.h.,wenn eine ganze Zahl q mit der Eigenschaft a = b q existiert. Die Zahl b heißt dann auch Teilervon a . Man nennt eine ganze Zahl p ∈ N \ 1 eine Primzahl, wenn p nur durch 1 und sichselbst teilbar ist. Fur ganze Zahlen a1, . . . , am , die nicht alle gleich Null sind, definiert man dengroßten gemeinsamen Teiler g = ggT(a1, . . . , am) als die großte naturliche Zahl, die Teilervon allen Zahlen a1, . . . , am ist. Man nennt a, b ∈ Z teilerfremd, wenn ggT(a, b) = 1 gilt.

Aus der Darstellung a = b q + r folgt, dass jeder gemeinsame Teiler von a und b auch gemein-samer Teiler von b und r ist. Daraus ergibt sich der folgende Algorithmus zur Bestimmung vonggT(a, b) .


Euklidischer Algorithmus zur Berechnung von ggT (a, b) fur a ∈ Z , b ∈ N :

a = b q1 + r1 , 0 < r1 < b ,

b = r1q2 + r2 , 0 < r2 < r1 ,

r1 = r2q3 + r3 , 0 < r3 < r2 ,

...

rk−2 = rk−1qk + rk , 0 < rk < rk−1 ,

rk−1 = rkqk+1 , ggT(a, b) = rk .

Erweiterterung des Euklidischen Algorithmus:Stellt man die obigen Gleichungen um,

r1 = a − b q1 ,

r2 = b − r1q2 ,

...

rk = rk−2 − rk−1qk ,

so erhalt man sukzessive

r2 = b − (a − b q1)q2 = b(1 + q1q2) − a q2 ,

...

rk = b v + au , u, v ∈ Z .

Satz 9.3 (Existenz des großten gemeinsamen Teilers) Zu jedem System a1, . . . , am gan-zer Zahlen, die nicht alle gleich Null sind existiert genau ein ggT(a1, . . . , am) . Ein gemeinsamerTeiler g ∈ N der Zahlen a1, . . . , am ist genau dann gleich ggT(a1, . . . , am) , wenn ganze Zahlenu1, . . . , um existieren, so dass

g = u1a1 + u2a2 + · · · + umam

gilt.

Folgerung 9.4 Zwei ganze Zahlen a, b sind genau dann teilerfremd, wenn ganze Zahlen u, vmit der Eigenschaft ua + v b = 1 existieren.

Folgerung 9.5 Es seien a, b ∈ N , d|a b und ggT (d, a) = 1 . Dann gilt d|b .

Folgerung 9.6 Ist p eine Primzahl, die Teiler von a1 · · · ak mit ak ∈ Z ist, so ist p auch Teilervon wenigstens einem der Faktoren aj .

Satz 9.7 (Fundamentalsatz der Zahlentheorie) Jede naturliche Zahl a > 1 besitzt eineeindeutige Zerlegung in Primfaktoren pj:

a = pm11 pm2

2 · · · pmk

k , 2 ≤ p1 < p2 < · · · < pk , mj ∈ N .

Satz 9.8 Es gibt unendlich viele Primzahlen.


9.2.2 Zahlenkongruenzen

Es sei m ∈ N , m > 1 . Wir sagen, dass zwei ganze Zahlen a und b kongruent modulo m sind,wenn b − a durch m teilbar ist, und schreiben dafur

a ≡ b mod m .

Man nennt ein System a1, . . . , am von m ganzen Zahlen ein vollstandiges System vonResten modulo m , wenn jede ganze Zahl zu einem dieser aj kongruent modulo m ist. Offenbarist ein System a1, . . . , am ganzer Zahlen genau dann ein vollstandiges System von Restenmodulo m , wenn fur beliebige Indizees i, j ∈ 1, . . . ,m aus ai ≡ aj mod m die Beziehungi = j folgt.

Lemma 9.9 Sind k a ≡ k b mod m und ggT(k,m) = d , so gilt a ≡ b mod m/d .

Lemma 9.10 Ist a1, . . . , am ein vollstandiges System von Resten modulo m und ggT(k,m) =1 , so ist auch k a1, . . . , k am ein vollstandiges System von Resten modulo m .

Die Eulersche Funktion ϕ : N −→ N ist definiert als die Anzahl der Reste modulo m , die zum teilerfremd sind, d.h.

ϕ(m) = # r ∈ Z : 0 ≤ r < m, ggT(r,m) = 1 .

(ϕ(m) ist somit gleich der Anzahl der sog. primen Restklassen modulo m .)

Satz 9.11 (Teilersummenformel) Fur alle naturlichen Zahlen n ∈ N gilt

∑

d∈N, d|n

ϕ(d) = n .

Ein Systema1, . . . , aϕ(m)

von ϕ(m) ganzen Zahlen, nennt man ein reduziertes System von

Resten modulo m , wenn jede ganze Zahl, die zu m teilerfremd ist, zu einem der aj kongruentmodulo m ist.

Lemma 9.12 Ista1, . . . , aϕ(m)

ein reduziertes System von Resten modulo m und ggT(k,m) =

1 , so ist auchk a1, . . . , k aϕ(m)

ein reduziertes System von Resten modulo m .

Satz 9.13 (Fermat) Fur jede Primzahl p und jede naturliche Zahl x ∈ N mit ggT(x, p) = 1gilt

xp ≡ x mod p .

Der folgende Satz stellt eine Verallgemeinerung dieser Aussage dar.

Satz 9.14 (Euler) Fur x ∈ N mit ggT(x,m) = 1 gilt

xϕ(m) ≡ 1 mod m .

Man nennt eine Funktion f : N −→ N multiplikativ, wenn fur beliebige m,n ∈ N mitggT(m,n) = 1 die Beziehung f(m n) = f(m)f(n) gilt.


Lemma 9.15 Die Eulersche Funktion ϕ : N −→ N ist multiplikativ.

Folgerung 9.16 Ist

a = pm11 pm2

2 · · · pmk

k , 2 ≤ p1 < p2 < · · · < pk , mj ∈ N ,

die Primfaktorzerlegung von a ∈ N , a > 1 , so gilt

ϕ(a) = a

k∏

j=1

(1 − 1

pj

).

Fur gegebene Zahlen a ∈ N und b ∈ Z betrachten wir die lineare Kongruenz

ax ≡ b mod m , x ∈ Z . (9.1)

Satz 9.17 Die lineare Kongruenz (9.1) ist genau dann losbar, wenn ggT(a,m)|b gilt. Dabei istdie Anzahl verschiedener Losungen x modulo m gleich ggT(a,m) .

Im Fall ggT(a,m) = 1 kann man die Losung von (9.1) mit Hilfe des erweiterten EuklidischenAlgorithmus finden. Aus ua + v m = 1 folgt namlich ua ≡ 1 mod m , so dass x ≡ b u mod mdie Losung von (9.1) darstellt.

Beispiel 9.18 Die lineare Kongruenz 14x ≡ 26 mod 34 hat die Losungen 14 und 31 modulo34 .

Satz 9.19 (Chinesischer Restsatz) Die Zahlen mj ∈ N , mj > 1 , j = 1, . . . , k , seien paar-weise teilerfremd und fur die Zahlen aj ∈ N gelte ggT(aj ,mj) = 1 , j = 1, . . . , k . Dann hat dasSystem linearer Kongruenzen

ajx ≡ bj mod mj , j = 1, . . . , k ,

fur beliebige bj ∈ Z eine eindeutige Losung modulo m1m2 · · ·mk .

Aus Satz 9.13 erhalt man den folgenden “negativen” Primzahltest: Existiert eine ganze Zahla ∈ 1, 2, . . . ,m − 1 mit der Eigenschaft am−1 6≡ 1 mod m , so ist m keine Primzahl.

Es ist ein sehr schwieriges Problem, eine naturliche Zahl m , von der man weiß, dass sie keinePrimzahl ist, in ihre Primfaktoren zu zerlegen. Die einfachste Methode ware, alle moglichenTeiler durchzuprobieren. Das musste man aber im Extremfall fur alle Zahlen von 1 bis

√m

machen, was fur große Zahlen praktisch unmoglich ist.

Mit Zm = (Zm,⊕,⊙) bezeichnen wir den Restklassenring modulo m , d.h., die Menge

Zm = [0]m, [1]m, . . . , [m − 1]m

der Restklassen modulo m wird mit den Operationen der Addition und Multiplikation

[k]m ⊕ [j]m := [k + j]m und [k]m ⊙ [j]m := [k · j]m


versehen. Dabei gelten die gleichen Gesetze wie im Bereich der ganzen Zahlen. Ist m = p einePrimzahl, so ist Zp sogar ein Korper, d.h., jede Restklasse [k]p 6= [0]p besitzt eine zu ihr inverseRestklasse [j]p ,

[k]p ⊙ [j]p = [1]p .

Das folgt aus Satz 9.13 bzw. aus Satz 9.14. Mit Z∗m bezeichnen wir die Menge der primen

Restklassen modulo m , d.h.

Z∗m =

[k]m : k ∈ 1, . . . ,m − 1 , ggT(k,m) = 1

.

Im weiteren schreiben wir z.B. fur [a]m ∈ Zm auch einfach a ∈ Zm .

9.2.3 Quadratische Reste

Definition 9.20 Eine Zahl a ∈ Z∗m wird quadratischer Rest modulo m genannt, falls ein

b ∈ Z∗m existiert, so dass

b2 ≡ a mod m

gilt. Eine Zahl b mit dieser Eigenschaft heißt dann Quadratwurzel von a modulo m . Ist akein quadratischer Rest modulo m , so nennt man a einen quadratischen Nichtrest modulom .

Ein quadratischer Rest hat im allgemeinen mehr als zwei modulare Quadratwurzeln. Ist m einePrimzahl, so besitzt jede Zahl a ∈ Z

∗m entweder keine oder genau zwei Quadratwurzeln modulo

m . Ist m = p q das Produkt zweier ungerader Primzahlen p und q 6= p , so hat jede Zahla ∈ Z

∗m entweder keine oder genau vier Quadratwurzeln b, m − b, c, m − c . In diesem Fall ist

das Berechnen von Quadratwurzeln modulo m genau so schwierig, wie das Faktorisieren von m .

Das Entscheidungsproblem, ob eine Zahl ein quadratischer Rest ist oder nicht, ist ebenfalls einsehr schwieriges. Dazu definieren wir das Legendre-Symbol (x|p) fur ungerade Primzahlen pund Zahlen x ∈ Z

∗p sowie das Jacobi-Symbol (x|m) fur Zahlen m = p q , die Produkt zweier

ungerader Primzahlen p und q sind, und x ∈ Z∗m wie folgt:

(x|p) :=

+1 : x ist quadratischer Rest modulo p ,

−1 : x ist quadratischer Nichtrest modulo p ,

und (x|m) := (x|p)(x|q) . Es gelten folgende Regeln:

1. (x|m) = (x mod m|m) ,

2. (x|m)(y|m) = (x y|m) ,

3. (−1|m) = (−1)m−1

2 ,

4. (2|m) = (−1)m

2−1

8 .


Satz 9.21 (Quadratisches Reziprozitatsgesetz) Fur alle ungeraden Zahlen m,k > 2 mitggT(m,k) = 1 gilt

(k|m)(m|k) = (−1)(m−1)(k−1)

4 .

Jeder quadratische Rest modulo m = p q ist sowohl quadratischer Rest modulo p als auchquadratischer Rest modulo q . Ist also (k|m) = −1 , so ist k quadratischer Nichtrest modulom . Aus (k|m) = +1 folgt aber nicht, dass k quadratischer Rest modulo m ist, da ja +1 =(+1)(+1) = (−1)(−1) gilt.Quadratische-Reste-Annahme: Im Fall m = p q , x ∈ Z

∗m und (x|m) = +1 ist es praktisch

unmoglich zu entscheiden, ob x quadratischer Rest modulo m ist oder nicht.

9.2.4 Der diskrete Logarithmus

In der Kryptologie spielen solche Funktionen eine große Rolle, die zwar leicht zu berechnen sind,aber sehr schwer umzukehren. So ist z.B die Multiplikation zweier naturlicher Zahlen einfachauszufuhren, die Umkehrung, namlich die Faktorisierung einer naturlichen Zahl, ist fur sehrgroße Zahlen praktisch unmoglich. Als ein weiteres Beispiel einer solchen sog. Einwegfunktionbetrachten wir die diskrete Exponentialfunktion zur Basis g ∈ N mit g ≤ p − 1 , wobei peine Primzahl ist:

k 7→ gk mod p .

Die Umkehrung dieser Funktion nennen wir diskrete Logarithmusfunktion dℓg .

Problem des diskreten Logarithmus: Gegeben seien die Primzahl p , die naturliche Zahl gund y ∈ Z . Man bestimme ein k ∈ Z , so dass y ≡ gk mod p gilt.

Die Berechnung der diskreten Exponentialfunktion kann sehr effektiv gestaltet werden. Z. B.kann man g19 in der Form

g19 =

(((g2)2)2

)2

g2g

schreiben. Im allgemeinen braucht man zur Berechnung von gk nicht mehr als 2 log2 k Multipli-kationen.

Zur Berechnung des diskreten Logarithmus konnte man wie folgt vorgehen: Gesucht ist eineganze Zahl k , so dass

[g]kp = [y]p ∈ Z∗p

gilt. Da Z∗p aus p − 1 Elementen besteht und nach Satz 9.13 [g]0p = [g]p−1

p = [1]p gilt, genugt es1 ≤ k ≤ p − 2 zu betrachten. Es sei w ∈ Z mit

√p − 2 ≤ w <

√p − 2 + 1 . Wir suchen k in der

Form k = aw + b mit 0 ≤ b ≤ w − 1 . Es muss dann

[y]p = [g]a wp ⊙ [g]bp ,

gelten. Aus [g]p−b−1p ⊙ [g]bp = [1]p folgt

[ga w]p = [y gp−b−1]p .

9.3. KRYPTOLOGISCHE GRUNDLAGEN 43

Nun kann man k = aw + b finden, indem man ga w mod p fur a ∈ 0, 1, . . . , w und y gp−b−1

mod p fur b ∈ 0, 1, . . . , w − 1 berechnet und vergleicht.

9.3 Kryptologische Grundlagen

9.3.1 Symmetrische Verschlusselung

Ein symmetrischer Verschlusselungsalgorithmus ist durch eine Funktion f(k,m) gegeben, dieunter Verwendung eines Schlussels k , den sowohl Sender als auch Empfanger der Nachrichtkennen, einen Klartext m in einen Geheimtext c umwandelt,

c = f(k,m) (Andere Schreibweise : c = fk(m) ).

Diese Funktion ist (von links) umkehrbar (bzgl. m), d.h. es existiert eine Funktion f∗(k, c) , sodass

f∗(k, f(k,m)) = m (bzw. f∗k (fk(m)) = m)

fur jeden Klartext m gilt.

Folgende Angriffe auf eine Verschlusselungsfunktion f sind nun denkbar:

1. Aus der Kenntnis einer gewissen Anzahl von Geheimtexten will der Angreifer die zugehori-gen Klartexte oder den Schlussel berechnen. (ciphertext-only attack)

2. Aus der Kenntnis einer gewissen Anzahl von Geheimtexten und den zugehorigen Klar-texten will der Angreifer den verwendeten Schlussel oder den Klartext zu einem weiterenGeheimtext berechnen. (known-plaintext attack)

3. Der Angreifer kennt die Verschlusselungsfunktion fk . Er kann zwar den Schlussel nichtauslesen, aber ausgewahlte Klartexte mit fk verschlusseln. Er will andere Geheimtexteentschlusseln bzw. den Schlussel k berechnen. (chosen-plaintext attack)

4. Der Angreifer kennt die Entschlusselungsfunktion f∗k . Er kann zwar den Schlussel k nicht

auslesen, aber gewisse Geheimtexte mit f∗k entschlusseln. Er will den Schlussel k berechnen.

(chosen-ciphertext attack)

Bei den Algorithmen zur symmetrischen Verschlusselung unterscheidet man zwischen Blockchiff-ren und Stromchiffren.

Blockchiffren: Die Nachricht wird in Blocke unterteilt und jeder Block einzeln ver-schlusselt.

Stromchiffren: Die Nachricht wird zeichenweise verschlusselt, wozu als Schlussel ein Zei-chenstrom verwendet wird.


9.3.2 Asymmetrische Verschlusselung (Public-Key-Kryptographie)

Jedem Teilnehmer T eines bestimmten Systems des Nachrichtenaustauschs werden ein geheimer(privater) Schlussel d = dT und ein offentlicher Schlussel e = eT zugeordnet. Zu jedem Klartextm wird der Geheimtext c = fe(m) unter Verwendung des offentlichen Schlussels e gebildet. Mit-tels des privaten Schlussels d wird der Klartext m′ = fd(c) erzeugt. Damit die Entschlusselungkorrekt ist, muss

fd(fe(m)) = m

fur jeden Klartext m gelten. Um die Public-Key-Eigenschaft zu erfullen, muss es praktischunmoglich sein, aus der Kenntnis des offentlichen Schlussels e auf den privaten Schlussel dschließen zu konnen.

9.3.3 Einwegfunktionen

Eine Funktion f : A −→ B , a 7→ f(a) wird Einwegfunktion genannt, wenn fur jedes a ∈ Ader Funktionswert f(a) leicht zu berechnen ist, aber es fur (fast) jedes b ∈ B sehr schwer(praktisch unmoglich) ist, ein a ∈ A zu finden, so dass b = f(a) gilt. Ist dabei f : A −→ Bbijektiv, so spricht man von einer Einwegpermutation. Eine Einwegfunktion f : A −→ Bheißt kollisionsfrei, wenn es praktisch unmoglich ist, zwei Elemente a1, a2 ∈ A mit a1 6= a2 zufinden, so dass f(a1) = f(a2) gilt.

Offenbar ist jede Einwegpermutation kollisionsfrei.

Eine Trapdoor-Einwegfunktion ist eine Einwegfunktion, zu der es eine Geheiminformation(“Geheimtur”) gibt, mittels der man die Funktion leicht invertieren kann.

9.3.4 Die digitale Signatur (Die elektronische Unterschrift)

Ein Signaturschema kann wie folgt definiert werden: Jedem Teilnehmer T werden eine geheimeSignaturfunktion sT und eine offentliche Verifikationsfunktion vT zugeordnet. Der Teilneh-mer T unterschreibt eine Nachricht m durch Bilden von

sig = sT (m) .

Der Empfanger der Nachricht m , die er gemeinsam mit der Signatur sig erhalt, uberpruft unterVerwendung der offentlichen Verifikationsfunktion vT die Echtheit der Signatur.

Die Verifikationsfunktion kann z. B. die Umkehrung der Signaturfunktion sein, d.h.

vT (sig) = vT (sT (m)) = m .

9.3.5 Der RSA-Algorithmus

RSA steht fur R. Rivest, A. Shamir und L. Adleman, die 1978 diesen Algorithmus erfanden.

9.3. KRYPTOLOGISCHE GRUNDLAGEN 45

Ist n = p q das Produkt zweier verschiedener Primzahlen p und q , so gilt fur jede naturlicheZahl m ≤ n und jedes k ∈ N die Beziehung

mk(p−1)(q−1)+1 ≡ m mod n . (9.2)

Zu zwei verschiedenen und großen Primzahlen p und q berechnet man nun n = p q und ϕ(n) =(p − 1)(q − 1) . Dann wahlt man eine zu ϕ(n) teilerfremde Zahl e ∈ N und berechnet eine Zahld ∈ N mit

e d ≡ 1 mod ϕ(n) .

Man findet also d ∈ N und k ∈ N , so dass

e d = 1 + k(p − 1)(q − 1) (9.3)

(Euklidischer Algorithmus). Man erhalt nun ein asymmetrisches Verschlusselungsverfahren (denRSA-Algorithmus), indem man (e, n) als offentlichen und d als geheimen Schlussel verwendetund die Verschlusselungsfunktion fe sowie die Entschlusselungsfunktion fd wie folgt definiert:

fe(m) := me mod n und fd(c) := cd mod n .

Die Korrektheit dieses Algorithmus ergibt sich nun aus (9.2) und (9.3):

fd(fe(m)) ≡ (me)d mod n ≡ m mod n .

Das Potenzieren mit e mod n ist eine Trapdoor-Einwegfunktion. Dabei konnen sowohl die Zahld als auch ϕ(n) oder die Faktorisierung n = p q als Geheiminformation fur die Umkehrfunktion,das Potenzieren mit d mod n dienen.

Der RSA-Algorithmus kann auch als Signaturverfahren verwendet werden. Dabei ist die Signa-turfunktion das Potenzieren mod n mit dem geheimen Schlussel d ,

sig = sT (m) := md mod n .

Als Verifikationsfunktion dient das Potenzieren mit e mod n ,

vT (sig) := sig e mod n?≡ m mod n .

Angriffe auf den RSA-Algorithmus:

• Unter Verwendung des offentlichen Schlussels (e, n) kann man die Nachricht m1m2 ver-schlusseln, ohne die einzelnen Nachrichten m1 und m2 zu kennen. Das folgt aus demPotenzgesetz

me1m

e2 mod n ≡ (m1m2)

e mod n .

Ebenso kann man aus den beiden Signaturen md1 mod n und md

2 mod n die Signatur(m1m2)

d mod n zur Nachricht m1m2 bilden, ohne Kenntnis vom privaten Schlussel d zuhaben.


• Aus einer Signatur kann man eine Nachricht konstruieren, die diese Signatur tatsachlich alsSignatur besitzt: Mittels des offentlichen Schlussels (e, n) bildet man m := sig e mod n .Die Signatur dieser Nachricht ist dann md = (sig e)d mod n ≡ sig mod n .

• Bei der Verwendung kleiner Exponenten e im offentlichen Schlussel (e, n) kann eventuellder Klartext zu einem Geheimtext berechnet werden, wenn dieser Geheimtext an mehrereTeilnehmer verschickt wird: Ist z.B. e = k und wird der Geheimtext mk an k Teilnehmermit den paarweise teilerfremden Moduli nj , j = 1, . . . , k , gesendet,

bj := mk mod nj , j = 1, . . . , k ,

so gibt es nach dem Chinesischen Restsatz eine eindeutige Losung x mod n mit n =n1n2 · · · nk des Systems

x ≡ bj mod nj , j = 1, . . . , k .

Wir schreiben die Losung so, dass x ∈ 0, 1, . . . , n − 1 erfullt ist. Da fur j = 1, . . . , k dieZahl m zu 0, 1, . . . , nj − 1 gehoren muss, gilt auch 0 ≤ mk < n , so dass m = k

√x den

Klartext liefert.

• Benutzen zwei Teilnehmer den gleichen Modul n = p q , so kann jeder die Nachrichten desanderen lesen: Der zweite Teilnehmer kennt ja e1 , e2 und d2 , wobei

ejdj = 1 + kj(p − 1)(q − 1) , j = 1, 2 ,

gilt. Er bildet die Zahl

h =e2d2 − 1

ggT(e1, e2d2 − 1)=

k2ϕ(n)

ggT(e1, e2d2 − 1),

die offenbar ein Vielfaches von ϕ(n) und teilerfremd zu e1 ist. Mit Hilfe des erweitertenEuklidischen Algorithmus kann man also ganze Zahlen c und d finden, so dass

c h + d e1 = 1

gilt. Hieraus folgt e1d ≡ 1 mod ϕ(n) , weil c h ≡ 0 mod ϕ(n) . Somit hat der zweiteTeilnehmer mit d1 = d den geheimen Schlussel des ersten Teilnehmers gefunden.

Blinde Signaturen: Eine Person A will ein Dokument m von einer Person B blind signierenlassen.

1. Es seien n = p q der Modul sowie e der offentliche und d der geheime Schlussel (desRSA-Algorithmus) von B .

2. A wahlt eine zu n teilerfremde Zufallszahl r .

3. A berechnet x = m re mod n und sendet x an B .

4. B unterschreibt durch Bilden von y = xd mod n und Senden von y an A .

5. A erhalt mittels

y r−1 = xdr−1 = (m re)dr−1 = mdre dr−1 = mdr r−1 = md mod n

die unterschriebene Nachricht.

9.4. PROTOKOLLE 47

9.4 Protokolle

Ein kryptographisches Protokoll (siehe Abschnitt 9.1.4) sollte mindestens die folgenden zweiForderungen erfullen:

1. Durchfuhrbarkeit. Verhalten sich alle beteiligten Instanzen nach den Regeln des Pro-tokolls, so muss auch immer (bzw. mit sehr hoher Wahrscheinlichkeit) das gewunschteErgebnis eintreten.

2. Korrektheit. Die Wahrscheinlichkeit, dass ein Teilnehmer erfolgreich betrugen kann, istvernachlassigbar klein.

9.4.1 Protokolle zur Authentikation

Passwortverfahren

Bei einem Passwortverfahren benutzt jeder Teilnehmer ein individuelles Geheimnis (sein Pass-wort oder seine PIN). Damit er sich aber damit gegenuber einer zentralen Stelle authentifizierenkann, muss diese Stelle alle diese Geheimnisse kennen.

Schwachen der Passwortverfahren und mogliche Gegenmaßnahmen:

1. “Sinnvolle” Passworter konnen erraten oder durch Ausprobieren gefunden werden. Pass-worter sollten deshalb moglichst “unsinnige” Zeichenfolgen sein.

2. Zum Schutz der Passworter konnen diese mit einer Einwegfunktion f verschlusselt werden.Danach werden nur die Werte f(PW ) abgespeichert. Die Korrekheit eines Passwortes PW

wird dann durch Vergleich der Funktionswerte f(PW ) und f(PW ) verifiziert.

3. Ein abgehortes Passwort kann missbraucht werden. Man sollte deshalb die Gultigkeitsdauerder Passworter kurz halten.

Beispiel: Transaktionsnummern (TAN) beim Homebanking (vgl. auch den folgenden Ab-schnitt uber Wechselcodeverfahren).

Wechselcodeverfahren

Bei einem Wechselcodeverfahren berechnet jeder Teilnehmer nach einem festgelegten Verfahrenaus seinem individuellen Geheimnis (konstanter Wert) und einem veranderlichen Wert einenAuthentikationscode. Dieser wird zusammen mit seiner Identitat an die Zentrale ubermittelt.Die Zentrale kann diese Berechnung nachvollziehen und beide Ergebnisse vergleichen, benotigtdazu naturlich auch das individuelle Geheimnis und den veranderlichen Wert.

Beispiel 9.22 A will sich gegenuber B mittels einer Verschlusselungsfunktion f authentisieren.Beide kennen den geheimen Schlussel k und einen Anfangszahlerstand m ∈ N . Beim erstenAuthentikationsvorgang sendet A den Wert f(k,m + 1) , beim zweiten den Wert f(k,m + 2) ,usw. Durchfuhrbarkeit und Korrektheit dieses Verfahrens sind leicht einzusehen.


Beispiel 9.23 Statt eines symmetrischen Algorithmus f konnte man auch ein Signaturverfah-ren verwenden (siehe Abschnitt 9.3.4). Dieser Aufwand ist aber nicht notwendig. Man brauchtnur eine Einwegfunktion f , einen Startwert m0 und eine Abschatzung N dafur, wie oft dasWechselcodeverfahren hochstens benutzt werden soll. A berechnet dann die Werte

mj+1 = f(mj) , j = 0, 1, . . . , N − 1 ,

ubermittelt an B den Wert mN . Beim ersten Authentikationsvorgang sendet A den Wert mN−1

und B verifiziert durch Bilden von f(mN−1) und Vergleichen mit mN . Beim zweiten Authenti-kationsvorgang sendet A den Wert mN−2 , usw. usf.

Dieses Verfahren ist korrekt, wenn der Startwert m0 nur A bekannt ist, da niemand die Einweg-funktion umkehren kann. Es ist durchfuhrbar, wenn beiden Teilnehmern A und B die Einweg-funktion f bekannt ist.

Challenge-and-Response

Bei Challenge-and-Response-Verfahren ist ein Angriff aufgrund von “vorproduzierten” Authen-tikationsnachrichten nicht moglich.

B stellt eine unvorhersagbare Frage an A , auf die A mittels seines Geheimnisses die richtigeAntwort berechnen und an B senden kann. Im Unterschied zu den bisher vorgestellten unidi-rektionalen Verfahren ist dies ein bidirektionales.

Beispiel 9.24 A und B kennen eine Einwegfunktion fk , die von einem Schlussel k abhangt. Bwahlt eine Zufallszahl r und sendet diese an A . Der Teilnehmer A bildet s = fk(r) und sendetdas Ergebnis an den Teilnehmer B , der s mit dem von ihm berechneten Wert fk(r) vergleicht.

9.4.2 Vereinbarung eines geheimen Schlussels

Ziel: Vereinbarung geheimer Schlussel uber offentliche Kanale. (Man braucht also keine abhorsi-cheren Verbindungen oder vertrauenswurdige Boten, . . .)

Das Protokoll der Diffie-Hellman-Schlusselvereinbarung:

1. Beide Teilnehmer kennen die Primzahl p und die naturliche Zahl g .

2. Beide Teilnehmer wahlen jeweils eine geheime Zahl a ∈ N und b ∈ N und bilden die Werte

a1 = ga mod p und b1 = gb mod p .

3. Die Zahlen a1 und b1 werden ausgetauscht. Teilnehmer A bildet die Zahl

a2 = ba1 mod p ,

Teilnehmer B die Zahlb2 = ab

1 mod p .

9.4. PROTOKOLLE 49

Durchfuhrbarkeit: A und B erhalten den gleichen Wert

a2 =(gb)a

mod p = (ga)b mod p = b2 .

Korrektheit: Außer von A und B kann dieser gemeinsame Wert von Niemandem berechnetwerden (vgl. Abschnitt 9.2.4).

Das Protokoll des ElGamal-Verschlusselungsverfahrens:

1. Alle Teilnehmer kennen die Primzahl p und die naturliche Zahl g < p .

2. Jeder Teilnehmer T wahlt sich eine naturliche Zahl t als geheimen (privaten) Schlussel undberechnet seinen offentlichen Schlussel τ = gt mod p .

3. Ein Sender A verschlusselt seine Nachricht an den Teilnehmer T wie folgt: Er wahlt einenaturliche Zahl a und berechnet

α = ga mod p und k = τa mod p .

Die Nachricht m verschlusselt A mittels eines symmetrischen Algorithmus f und demSchlussel k ,

c = f(k,m) .

Er sendet c und α an T .

4. T bildetαt mod p = (ga)t mod p =

(gt)a

mod p = k

und kann c mit dem Schlussel k entschlusseln.

9.4.3 Das ElGamal-Signaturverfahren

1. Es werden derselbe private Schlussel t und derselbe offentliche Schlussel τ wie beimElGamal-Verschlusselungsverfahren verwendet.

2. Der Teilnehmer T erzeugt seine Unterschrift zu einer Nachricht m wie folgt: Er wahlt einezu p − 1 teilerfremde Zufallszahl r und bildet k = gr mod p . Er berechnet dann eineLosung s der Kongruenz

t k + r s ≡ m mod p − 1 .

Die digitale Unterschrift besteht aus dem Paar (k, s) .

3. Der Empfanger der signierten Nachricht (m, (k, s)) pruft die Unterschrift durch Vergleichder beiden Zahlen

gm mod p und τkks mod p .

Durchfuhrbarkeit: Nach dem Satz von Fermat (Satz 9.13) gilt fur jede korrekt signierte Nachricht(m, (k, s))

gm ≡ gt k+r s mod p ≡ τkks mod p .


9.4.4 Shamirs No-Key-Protokoll

Ziel: Zwei Teilnehmer, von denen keiner den Schlussel des anderen kennt, wollen vertraulichmiteinander kommunizieren, ohne vorher einen gemeinsamen Schlussel auszutauschen oder zuvereinbaren.

1. Beide Teilnehmer einigen sich auf eine große Primzahl p .

2. A und B bilden jeweils ein Paar (a, a1) bzw. (b, b1) ganzer Zahlen mit der Eigenschafta a1 ≡ 1 mod p − 1 bzw. b b1 ≡ 1 mod p − 1 .

3. A berechnet x = ma mod p und sendet x an B .

4. B berechnet y = xb mod p und sendet y an A .

5. A berechnet z = ya1 mod p und sendet z an B .

6. B berechnet

zb1 mod p = ma b a1b1 mod p = (ma a1)b b1 mod p = m .

9.5 Ubungsaufgaben

1. Gegeben sei folgender Code:

A = 001011,E = 010110,F = 101100,K = 011001,L = 110010,M = 100101,S = 000000

(a) Kodieren Sie die Nachrichten SEELE, FASE, MASSE, SEMMEL, KLASSE.

(b) Was bedeuten die folgenden Nachrichten

001011 101100 101100 010110

011001 001011 100101 010110 110010

110010 001011 100101 001011

001011 100101 000000 010110 110010

010110 000000 010110 110010

(c) Nach der Ubertragung durch eine gestorte Telefonleitung, konnten folgende Bitfolgenermittelt werden:

001011 000100 000000 010010 110010

001011 101101

000000 011110 000000 000000 010110 100010

001011 111010 110010 010110 001000

010110 011001 000110 110000

Was wollte der Absender ubermitteln?


2. Zur Kontrolle von Kreditkartennummern verwendet man ein 16-stelliges Prufziffernverfah-ren: Gebrauchliche Kreditkarten beinhalten i. d. R. eine 16-stellige Kreditkartennummer(KKN). Der erste Teil einer KKN bestimmt den Typ (American Express, MasterCard,Visa, etc.), der zweite Teil die Bank und den Kunden. Die letzte Ziffer reprasentiert einePrufziffer. Verwende folgenden Prufziffernalgorithmus fur Kreditkartennummern: Beginnemit der 1. Ziffer von links und multipliziere sie mit 2. Addiere die Quersumme des Ergeb-nisses zu der Prufsumme. Verfahre ebenso mit der 3., 5., 7., 9., 11., 13. und 15. Ziffer vonlinks. Addiere im Anschluß die bisher nicht verwendeten Ziffern der KKN zu der Prufsum-me, also auch die letzte (Pruf-) Ziffer. Die KKN ist ungultig, wenn bei der ganzzahligenDivision der Prufsumme durch 10 ein Divisionsrest (ungleich Null) verbleibt.

Beispiel KKN: 4907 4499 2739 8714

Prufsumme: 8 + 0 + 8 + (1 + 8) + 4 + 6 + (1 + 6) + 2 + 9 + 7 + 4 + 9 + 7 + 9 + 7 + 4

Uberprufen Sie folgende KKNs:

8475 2494 2354 2358, 1943 8432 1463 3745, 5123 5246 0230 4232, 2963 4634 2474 2345

3. Um Storungen bei der Datenubertragung zwischen dem SCSI-Hostcontroler und den an-geschlossenen Geraten zu erkennen wird zusatzlich zu den 8 oder 16 Datenbits noch einweiteres Bit, das sogenannte Paritatsbit ubertragen. Dabei wird das Paritatsbit immerso gewahlt, dass die Anzahl der Einsen ungerade (odd parity) ist. Uberprufen Sie, ob dieuntenstehende Ubertragung fehlerfrei ablief.

0101 0001 00101 0101 10011 0111 01101 0111 11101 0101 10101 0111 00010 1011 01111 0111 0

4. Bestimmen Sie den großten gemeinsamen Teiler der Zahlen

(a) 15 und 10, (b) 30030 und 3570, (c) 4250 und 14300.

5. Berechnen Sie den Rest der folgenden Zahlen z bei Division durch m :

(a) z = 257 · 65535 , m = 16 , (b) z = 171 + 346 , m = 17 ,

(c) z = 171 + 346 , m = 25 , (d) z = 7627423 · 1776451 , m = 2 ,

(e) z = 502002 , m = 7 , (f) z = 4225 , m = 10 , (g) z = 17129 , m = 5 .

6. Berechnen Sie ϕ(k) fur k = 1, . . . , 20 und k = 1013 . (ϕ : N −→ N - Eulersche Funktion)

7. Losen Sie folgende Kongruenzen:

(a) 3 + a ≡ 2 mod 5 , (b) 1 − b ≡ 4 mod 7 , (c) 2c ≡ 3 mod 7 ,

(d) 2d ≡ 3 mod 6 , (e) 3e ≡ 0 mod 9 , (f) 5f ≡ 1 mod 7 ,

(g) x2 ≡ 4 mod 11 , (h) 101000x ≡ 600 mod 997 , (i) 10y ≡ 15 mod (11 · 13) .


8. Berechnen Sie

(a) 5−1 mod 13 , (b) 27−1 mod 31 , (c) 767−1 mod 4080 .

9. Bestimmen Sie alle x ∈ Z , die folgendes System von Kongruenzen losen:

4x ≡ 1 mod 15

3x ≡ 2 mod 16

2x ≡ 3 mod 17

10. Bestimmen Sie die quadratischen Reste modulo 11 und modulo 21 sowie die dazugehorigenQuadratwurzeln modulo 11 bzw. modulo 21.

11. Ist 74 ein quadratischer Rest modulo 131?

12. Bestimmen Sie alle Zahlen k ∈ N , so dass k < 19 und 3k ≡ 5 mod 19 gilt.

13. Wir betrachten das RSA-Verfahren mit dem offentlichen Schlussel (167119821,13090615).

(a) Verschlusseln Sie die Zahlenfolge 34056, 110594, 194716 .

(b) Entschlusseln Sie die Zahlenfolge 6907692, 9173950, 7952026 .

Kapitel 10

Graphentheorie

10.1 Grundbegriffe

Ein Graph G wird aus einer Knotenmenge V und einer Kantenmenge E gebildet und kannals Teilmenge G ⊂ V × V × E des Kreuzproduktes V × V × E aufgefasst werden. Genauerspricht man in diesem Fall von einem gerichteten Graphen. (Da in diesem Fall die Kanteneinen Richtungssinn haben.) Identifiziert man (u, v, e) ∈ G mit (v, u, e) ∈ V ×V ×E , so sprichtman von einem ungerichteten Graphen. (Wir betrachten hier nur Graphen mit endlich vielenKnoten und Kanten.)

Beachte: G ⊂ V × V × E ist nur dann ein Graph, wenn fur jedes e ∈ E gilt

# (u, v) ∈ V × V : (u, v, e) ∈ G ≤ 1

im Fall eines gerichteten Graphen und

# (u, v) ∈ V × V : (u, v, e) ∈ G ≤ 2

sowie# (v, v) ∈ V × V : (v, v, e) ∈ G ≤ 1

im Fall eines ungerichteten Graphen gilt.

Beispiel 10.1 In der Menge 1, 2, . . . , n der naturlichen Zahlen von 1 bis n lasst sich dieBeziehung zweier Zahlen, nicht teilerfremd zu sein, als Graph darstellen.

Beispiel 10.2 Am linken Ufer eines Flusses steht ein Fahrmann. Er soll mit seinem Kahn eineZiege, einen Wolf und Heu uber den Fluss setzen. Das Boot ist klein, und außer dem Fahrmannpasst nur einer der genannten Passagiere bzw. nur das Heu in den Kahn. Kann der FahrmannZiege, Wolf und Heu nacheinander uber den Fluss setzen, wenn er weder die Ziege mit dem Wolfnoch die Ziege mit dem Heu am Ufer allein lassen darf?

Einen Graphen G nennt man schlicht, wenn er keine parallelen Kanten und keine Schlingen hat.Dabei werden zwei Kanten e, f ∈ E mit e 6= f parallel genannt, wenn mit (u, v, e) ∈ G auch

53

54 KAPITEL 10. GRAPHENTHEORIE

(u, v, f) ∈ G gilt. Ist (v, v, e) ∈ G , so nennt man (v, v, e) eine Schlinge von G . Ein schlichterGraph G heißt vollstandig, wenn zu jedem Knotenpaar (u, v) ∈ V × V eine Kante e ∈ E mit(u, v, e) ∈ G existiert.

Eine Teilmenge H ⊂ G ⊂ V × V ×E des Graphen G nennt man Teilgraph von G . Die Anzahld(v) der Kanten an einem Knoten v , d.h.

d(v) = # e ∈ E : ∃u ∈ V mit (u, v, e) ∈ G oder (v, u, e) ∈ G ,

wird Knotengrad von v genannt. (Dabei wird eine Schlinge an einem Knoten als zwei Kantengezahlt.) Im Fall eines gerichteten Graphen G gilt

d(v) = d+(v) + d−(v) ,

wobei d+(v) die Anzahl eingehender und d−(v) die Anzahl ausgehender Kanten an v bezeichnen,

d+(v) = # e ∈ E : ∃u ∈ V mit (u, v, e) ∈ G ,

d−(v) = # e ∈ E : ∃u ∈ V mit (v, u, e) ∈ G .

(Gesamtgrad eines Graphen := Summe aller Knotengrade. Dabei gilt: Der Gesamtgrad ist stetseine gerade Zahl, und die Anzahl der Knoten mit ungeradem Knotengrad ist stets gerade, vgl.Abschnitt 10.6.)

10.2 Bipartite Graphen

Zerfallt die Knotenmenge V eines Graphen in zwei nichtleere und zueinander disjunkte MengenV1 ud V2 , so dass jede Kante des Graphen einen Knoten aus V1 mit einem Knoten aus V2

verbindet, so spricht man von einem bipartiten Graphen oder von einem Beziehungsgraphen.

Beispiel 10.3 Die Menge V1 bestehe aus Wohnungssuchenden und die Menge V2 aus freienWohnungen. Eine Kante verbinde eine freie Wohnung mit einem Wohnungssuchenden, der sichfur diese Wohnung interessiert. Ein solcher Graph ist bipartit.

Liegt ein bipartiter Graph mit den beiden Parteien V1 und V2 vor, so kann man sich die Fragestellen, ob eine erschopfende Paarbildung, auch Verkupplung genannt, uber den beiden MengenV1 und V2 und die Kanten des Graphen moglich ist. Man spricht dann von einer vollstandigenKuppelei, wenn die Paare einer solchen Verkupplung untereinander knotendisjunkt sind.

Satz 10.4 (Hall, 1935) Ein bipartiter Graph mit den beiden gleichmachtigen Parteien V1 undV2 besitzt genau dann eine vollstandige Kuppelei, wenn jede Teilmenge U1 ⊂ V1 mit mindestens#U1 Knoten in V2 uber Kanten verbunden ist (Verastelungsbedingung).

Beispiel 10.5 Aus der Menge der vier Jungen Heiner, Anton, Kay und Bernd und der Mengeder vier Madchen Eva, Silke, Gudrun und Doris sollen Tanzpaare gebildet werden. Die folgendenPaare charakterisieren den Sympathie-Graphen:

(A,G), (A,S), (A,D), (B,G), (B,D), (H,E), (H,S), (K,S), (K,D) .

Kann jeder einen geeigneten Tanzpartner finden?

10.3. WEGE UND KREISE. DIE ADJAZENZMATRIX 55

10.3 Wege und Kreise. Die Adjazenzmatrix

Im folgenden betrachten wir ganz spezielle Teilgraphen eines Graphen G .

Unter einer Kantenfolge mit dem Startknoten v und dem Zielknoten w versteht man eine Folgevon Knoten und Kanten der Gestalt

v1e1v2e2v3 · · · en−1vn mit v = v1 und w = vn ,

wobei die Kante ej vom Knoten vj zum Knoten vj+1 geht (j = 1, . . . , n−1). Ist dabei v = w , sonennt man die Kantenfolge geschlossen, sonst offen. Eine Kantenfolge ohne Kantenwiederho-lungen bezeichnet man als Kantenzug. Sind alle Knoten einer Kantenfolge einschließlich Start-und Zielknoten paarweise verschieden, so spricht man von einem Weg.

Ein Weg ist somit ein offener Kantenzug ohne Knotenwiederholungen. Einen geschlossenen Kan-tenzug ohne Knotenwiederholungen nennt man Kreis.

Definition 10.6 Ein ungerichteter Graph heißt zusammenhangend, wenn je zwei Knotendurch einen Weg miteinander verbunden werden konnen. Einen gerichteten Graphen nennt manstark zusammenhangend, wenn zwischen je zwei Knoten ein Weg existiert. Er heißt schwachzusammenhangend, wenn der zugehorige ungerichtete Graph zusammenhangend ist.

Fur die Zusammenhangsuntersuchung eines Graphen kann man das Matrixprodukt benutzen.Dazu ordnet man einem Graphen mit n Knoten v1, . . . , vn seine Adjazenzmatrix A =

[αjk

]∈

Rn×n zu, wobei αjk gleich der Anzahl der Kanten vom Knoten vj zum Knoten vk ist. Offenbar

ist die Adjazenzmatrix eines ungerichteten Graphen stets symmetrisch, die eines gerichtetenGraphen i.a. nicht.

- Die Adjazenzmatrix A zeigt also alle einkantigen Wege an.

- Die Matrix A2 informiert uber alle zweikantigen Wege, usw.

- Die Matrix B =[

βjk

]= A + A2 lasst erkennen, zwischen welchen Punkten ein Weg mit

hochstens zwei Kanten existiert. Die Matrix E =[

εjk

]∈ R

n×n mit

εjk =

1 , falls βjk > 0 ,

0 , falls βjk = 0 ,

nennt man Erreichbarkeitsmatrix fur ein- und zweikantige Wege.

Beispiel 10.7 Wir untersuchen den Graphen G mit der Adjazenzmatrix

A =

0 1 1 01 0 1 11 1 0 00 1 0 0

auf Zusammenhang.


Auf der Menge V der Knoten eines ungerichteten Graphen G erklaren wir folgende Relation:Wir sagen, dass u ∈ V in Relation zu v ∈ V steht (in Zeichen u

w∼ v), wenn ein Weg von u nachv existiert. Diese Relation ist offenbar eine Aquivalenzrelation. Die entsprechenden Aquivalenz-klassen [u]w

∼nennen wir Zusammenhangskomponenten oder einfach nur Komponenten

des Graphen G .

Ein Graph G heißt gewichtet, wenn jeder Kante eine reelle Zahl (ein Gewicht) zugeordnet ist.Solche Gewichte konnten z.B. Entfernungen, Kosten oder Zeiten sein. Einem solchen Graphenkann man neben der Adjazenzmatrix auch die sog. Gewichts- oder Wichtungsmatrix Wzuordnen. Fur den Fall, dass von einem beliebigen Knoten vj zu einem beliebigen Knoten vk

hochstens eine Kante geht, sind die Eintrage ωjk der Matrix W =[

ωjk

]gleich dem Gewicht

der Kante von vj zu vk falls eine solche existiert, bzw. gleich Null, falls keine solche Kanteexistiert.

10.4 Eulersche Graphen

Unter einer Eulerschen Linie eines Graphen G versteht man einen geschlossenen Kantenzug,der alle Kanten von G enthalt. Besitzt ein Graph G eine Eulersche Linie, so nennt man ihn einenEulerschen Graphen.

Satz 10.8 Ein ungerichteter zusammenhangender Graph besitzt genau dann eine Eulersche Li-nie, wenn alle Knoten einen geradzahligen Knotengrad haben.

Eine Idee fur die Konstruktion einer Eulerschen Linie kann wie folgt beschrieben werden: Manbildet vorerst aus allen Kanten des Graphen Kreise, verheftet diese uber geeignete Knoten undsetzt die Eulersche Linie dann aus den entsprechenden “Kreisbogen” zusammen.

Beispiel 10.9 Wir konstruieren eine Eulersche Linie zum Graphen G mit der Adjazenzmatrix

A =

0 1 1 0 01 0 0 1 01 0 0 1 20 1 1 0 20 0 2 2 1

.

Satz 10.10 Ein Graph ist genau dann ein offener Kantenzug, wenn er zusammenhangend istund genau zwei Knoten ungeraden Grades besitzt.

10.5 Baume und Geruste

Im Rest dieses Kapitels wollen wir uns nur mit ungerichteten Graphen befassen.

Einen zusammenhangenden und kreisfreien Graphen nennt man Baum.

Satz 10.11 In einem Baum mit mindestens einer Kante existieren mindestens zwei Knotenersten Grades.

10.6. REGULARE GRAPHEN 57

Satz 10.12 Ein zusammenhangender Graph mit der Knotenmenge V und der Kantenmenge Eist genau dann ein Baum, wenn #E = #V − 1 gilt.

Einen Teilgraph G1 des Graphen G nennt man einen Faktor oder einen Kantenteilgraph vonG , wenn er dieselbe Knotenmenge wie G besitzt.

Satz 10.13 Jeder zusammenhangende Graph besitzt einen Baum als Faktor.

Man nennt einen solchen Faktor ein Gerust des Graphen.

10.6 Regulare Graphen

Satz 10.14 Es sei G ein Graph mit den Knoten v1, . . . , vn und den Kanten e1, . . . , em . Danngilt

n∑

j=1

d(vj) = 2m .

Satz 10.15 Die Anzahl der Knoten ungeraden Grades eines Graphen ist stets gerade.

Satz 10.16 Es seien u ∈ V ein Knoten ersten Grades des zusammenhangenden Graphen G ,eu ∈ E die zugehorige Kante und G1 der Graph der aus G durch Entfernen des Knotens u undder Kante eu entsteht. Dann ist auch G1 zusammenhangend.

Einen schlichten Graphen, dessen Knoten alle denselben Knotengrad g haben, nennt man einenregularen Graphen g-ten Grades. Offenbar ist ein zusammenhangender regularer Graph zwei-ten Grades ein Kreis.

Satz 10.17 Jeder regulare Graph ungeraden Grades hat eine gerade Anzahl an Knoten.

Satz 10.18 Fur jede gerade naturliche Zahl m ≥ 4 existiert ein regularer Graph dritten Gradesmit m Knoten.

10.7 Hamiltonsche Graphen. Kurzeste Wege

Ist ein Faktor G1 eines Graphen G ein regularer Graph k-ten Grades, so nennt man G1 einenFaktor k-ten Grades von G . Die Faktoren ersten Grades bezeichnet man auch als lineareFaktoren, die zweiten Grades als quadratische Faktoren.

Dafur, dass der Graph G einen Faktor ungeraden Grades besitzt, ist es notwendig, dass dieAnzahl der Knoten von G gerade ist (vgl. Satz 10.15). Diese Bedingung ist aber nicht hinreichend.So besitzt z.B. ein “Stern” mit gerader Knotenzahl ≥ 4 keinen Faktor ungeraden Grades.

Existiert in G ein quadratischer Faktor, so ist offenbar jede Komponente dieses Faktors einKreis. Einen zusammenhangenden quadratischen Faktor nennt man eine Hamiltonsche Linieoder einen Hamiltonschen Kreis. Graphen, die einen solchen Kreis besitzen, werden Hamil-tonsche Graphen genannt.


Satz 10.19 (Dirac 1952) Ein schlichter Graph G mit n ≥ 3 Knoten, dessen Knoten samtlicheinen Knotengrad ≥ n/2 haben, ist ein Hamiltonscher Graph.

Die Bedingung an den Knotengrad in diesem Satz besagt also, dass fur die Moglichkeit ei-ner “Rundreise” eine hinreichend große Verastelungsdichte des Graphen ausreicht. In einemvollstandigen Graphen ware dies abgesichert. Es ist leicht einzusehen, dass die Bedingung desSatzes 10.19 an den Knotengrad fur n ≥ 5 nicht notwendig ist.

Definition 10.20 Es sei G ein gewichteter Graph. Fur zwei verschiedene Knoten u, v diesesGraphen bezeichnen wir mit ρ(u, v) das minimale Kantengewicht (die Summe der Gewichte derKanten des Weges) unter allen Wegen, die u mit v verbinden. Wir setzen ρ(v, v) = 0 fur alleKnoten v . Ist F eine Kantenfolge von G mit der Knotenmenge VF ⊂ V , so sei der Abstandeines Knoten v zu F gleich

ρ(v, F ) = min ρ(v, u) : u ∈ V ∩ F .

Ist ein Graph G mit mindestens drei Knoten schlicht und vollstandig, so besagt der Satz 10.19,dass es in G wenigstens einen Hamilton-Kreis gibt. Unter allen diesen Rundreisen gibt es we-nigstens eine mit minimalem Gesamtgewicht (eine kurzeste Rundreise). Die Ermittlung allerHamilton-Kreise ist allerdings fur große Knotenzahlen sehr aufwendig. In praktischen Algorith-men versucht man deshalb schrittweise durch den Vergleich von Alternativen wenigstens einesuboptimale Rundreise zu finden.

Methode des dichtesten Knotens:

1. Man wahlt einen Startknoten v0 und einen dazu dichtesten Knoten v1 .

2. Die dazugehorige Kantenfolge erganzt man durch weitere dichteste Knoten zu einemStartkreis K1 .

3. Man wahlt einen weiteren zu K1 dichtesten Knoten v2 .

4. Unter allen Kreisen, die aus K1 durch Einbeziehung von v2 entstehen, wahlt maneinen Kreis K2 mit minimalem Kantengewicht aus.

5. Mit K2 verfahrt man wie mit K1 , falls K2 noch kein Hamilton-Kreis ist.

Beispiel 10.21 Wir wenden auf den Graphen G mit der Gewichtsmatrix

W =

0 10 20 19 11 20

10 0 10 11 6 11

20 10 0 17 15 10

19 11 17 0 15 10

11 6 15 15 0 15

20 11 15 10 15 0

die Methode des dichtesten Knotens an.

10.7. HAMILTONSCHE GRAPHEN. KURZESTE WEGE 59

Wir betrachten noch ein Verfahren zur Bestimmung des kurzesten Weges zwischen zwei Knotenin einem gewichteten Graphen, welches 1959 von Dijkstra vorgeschlagen wurde. Bei diesemVerfahren werden die Wege vom Start- zum Zielknoten schrittweise verlangert. Dies geschiehtmit Hilfe eines weiteren ausgewerteten Knotens und durch Langenvergleich der zur Verfugungstehenden Alternativen. Ein Knoten v gilt dabei als ausgewertet, wenn der kurzeste Weg vomStartknoten zu v gefunden ist.

Beispiel 10.22 Wir betrachten einen gewichteten zusammenhangenden Graphen G mit derKnotenmenge vs, v1, v2, v3, v4, vz und der Gewichtstabelle

vs v1 v2 v3 v4 vz

vs 0 18 0 15 0 0

v1 18 0 9 6 0 0

v2 0 9 0 14 10 28

v3 15 6 14 0 7 0

v4 0 0 10 7 0 36

vz 0 0 28 0 36 0

Wir suchen den kurzesten Weg vom Startknoten vs zum Zielknoten vz uber die Zwischenknotenv1, v2, v3 und v4 . Wir realisieren das Verfahren von Dijkstra als eine Folge von Tabellen. JedeTabelle besteht aus

• der Knotenzeile aus allen Knoten des Graphen,

• der Markierungszeile, die den jeweils kurzesten Weg unter allen ausgewerteten Wegenvom Startknoten zum Knoten der jeweiligen Spalte enthalt,

• der Zeile mit der aktuellen Knotenmenge, die alle Knoten enthalt, fur die noch keinevollstandige Wegeauswertung erfolgt ist.

Ein Knoten v verschwindet aus der aktuellen Knotenmenge, wenn alle von vs nach v fuhrendenWege ausgewertet sind und der kurzeste Weg bestimmt worden ist. Somit endet das Verfahren,wenn der Zielknoten vz aus der aktuellen Knotenmenge gestrichen wird. Dabei steht die minimaleWeglange als Markierung unter vz .

Knoten vs v1 v2 v3 v4 vz

Markierung 0 ∞ ∞ ∞ ∞ ∞aktuelle Knotenmenge vs v1 v2 v3 v4 vz

Alle noch nicht ausgewerteten Wege werden mit ∞ markiert. Das Minimum der Markierungenist 0 . Der zugehorige Startknoten wird aus der aktuellen Knotenmenge gestrichen. Nun wird derWeg von vs aus um eine Kante verlangert. Die Markierungen zeigen die jeweilige Weglange an.


Markierung 0 18 ∞ 15 ∞ ∞(Wege) (vs, v1) (vs, v3)

aktuelle Knotenmenge v1 v2 v3 v4 vz


Der Knoten v3 mit der geringsten Markierung unter den noch nicht ausgewerteten Knoten wirdaus der aktuellen Knotenmenge gestrichen. Nun werden alle zweikantigen Wege von vs uberausgewerte Knoten (v3) zu noch nicht ausgewerteten Knoten (v2, v4) betrachtet.


Markierung 0 18 29 15 22 ∞(Wege) (vs, v3, v2) (vs, v3, v4)

aktuelle Knotenmenge v1 v2 v4 vz

Die minimale Markierung unter den noch nicht ausgewerteten Knoten hat v1 . Er wird aus deraktuellen Knotenmenge gestrichen und kann jetzt in den Weg nach v2 einbezogen werden.


Markierung 0 18 27 15 22 ∞(Wege) (vs, v1, v2)

aktuelle Knotenmenge v2 v4 vz

Der Knoten v4 mit der minimalen Markierung wird aus der aktuellen Knotenmenge gestrichenund kann zur Wegverlangerung von vs nach vz verwendet werden.


Markierung 0 18 27 15 22 58(Wege) (vs, v3, v4, vz)

aktuelle Knotenmenge v2 vz

Jetzt hat der Knoten v2 die minimale Markierung, und er wird aus der aktuellen Knotenmengegestrichen.


Markierung 0 18 27 15 22 55(Wege) (vs, v1, v2, vz)

aktuelle Knotenmenge vz

(vs, v1, v2, vz) ist der gesuchte minimale Weg.

10.8 Optimale Geruste

Im Abschnitt 10.5 haben wir den Begriff des Gerustes eines Graphen G , kennengelernt. Das istein Faktor von G , der gleichzeitig ein Baum ist und auch spannender Baum von G genanntwird. Nach Satz 10.13 besitzt jeder zusammenhangende Graph ein Gerust. Liegt nun ein ge-wichteter Graph vor, so ist die Frage nach optimalen spannenden Baumen interessant, d.h. manversucht einen gewichteten Graphen so auszulichten, dass ein minimal oder maximal gewichteterspannender Baum ubrig bleibt.

Weit verbreitet ist das Verfahren von Kruskal (1956): Es wird eine Startkante gewahlt (je nachZielstellung eine schwerste oder eine leichteste unter allen Kanten). An diese Startkante werdenschrittweise weitere Kanten angehangt (je nach Zielstellung gewichtsmaßig ab- oder aufsteigend).

10.8. OPTIMALE GERUSTE 61

In jedem Schritt wird auf Kreisfreiheit uberpruft: Fuhrt eine neue Kante auf einen Kreis, so wirdsie sofort wieder entfernt.

Beispiel 10.23 Eine Fluggesellschaft biete zwischen den Stadten Berlin, London, Paris, Rom,Munchen und Frankfurt folgende Direktverbindungen (mit Entfernung in km) an:

B F L M P R

B - 433 932 473 869 1205

F 433 - 637 299 460 962

L 932 637 - 925 - -

M 473 299 925 - 689 732

P 869 460 - 689 - -

R 1205 962 - 732 - -

Aus Rationalisierungsgrunden soll der Fluggraph gelichtet werden.

Abschließend geben wir noch zwei Tabellen an ([3]). Die erste nimmt noch einmal Bezug aufdie Definitionen verschiedener Teilgraphen, die zweite auf verschiedene Aufgabenstellungen undAlgorithmen zu ihrer Losung:

Teilgraph Kanten- Knoten- Anfangs- gleichwiederholung wiederholung Endknoten

Kantenfolge moglich moglich moglichgeschlossene Kantenfolge moglich moglich jaKantenzug nein moglich moglichWeg nein nein neinKreis nein nur einmal ja

Typen von Teilgraphen

Ziel Merkmal Existenzkriterium Algorithmus Probleme

Eulersche geschlossener Kantenzug G zusammenhangend, Verheftung Mehrd.Linie uber alle Kanten von G alle Knotengr. gerade von Kreisen

(notw. und Hinr.)minimaler Kreis uber alle n G schlicht, Erweiterung nur subopt.Hamilton- Knoten von G mit min. d(v) ≥ n/2 von Kreisen Losungen,Kreis Gesamtgewicht (hinr.) um den dicht. Mehrd.Kurzester Weg zwischen zwei G zusammen- sukzessive Weg- Mehrd.Weg Knoten mit hangend verlangerung

Minimalgewicht (notw. und hinr.) nach Dijkstra

Gerust kreisfreier Teilgraph uber G zusammen- Kantenauswertung Mehrd.alle Knoten mit hangend uber geordneteopt. Gesamtgewicht (notw. und hinr.) Gewichte

nach Kruskal

Graphalgorithmen


10.9 Ubungsaufgaben

1. Gegeben seien eine Knotenmenge V , eine Kantenmenge E und der ungerichtete Graph G :

V = v1, v2, v3, v4, v5 ,

E = e1, e2, e3, e4, e5, e6, e7, e8 ,

G = (v1, v5, e1), (v1, v2, e2), (v1, v4, e3), (v2, v3, e4),

(v3, v4, e5), (v4, v5, e6), (v2, v2, e7), (v1, v2, e8) .

(a) Stellen Sie G graphisch dar.

(b) Welche Kanten mussen aus G mindestens entfernt werden, damit der entstehendeTeilgraph G′ ⊂ G ein schlichter Graph ist?

(c) Bestimmen Sie alle Knotengrade.

(d) Geben Sie die Adjazenzmatrix an.

(e) Geben Sie einen Kantenzug von v1 nach v3 an, der kein Weg ist.

(f) Geben Sie eine geschlossene Kantenfolge mit v1 an, die kein Kreis ist.

2. Gegeben sei nebenstehender Graph.

(a) Stellen Sie die Gewichtsmatrix auf.

(b) Geben Sie die Vorganger und Nachfolger des Kno-tens 2 an.

(c) Bestimmen Sie die Langen der kurzesten Wegevom Knoten 1 zu allen anderen Knoten des Gra-phen.

1

2 3

54

10

20

50

20

20

5010 20

3. Gegeben sei der nebenstehende ungerichtete Graph.

(a) Zeigen Sie, dass der gegebene Graph bipartit ist,indem Sie die beiden Parteien V1 und V2 sowieeine moglichst umfangreiche Paarbildung (Mat-ching) angeben.

(b) Existiert eine vollstandige Kuppelei?

(c) Erganzen Sie eine Kante im Graphen so, dasses einen Kreis gibt, der alle Knoten enthalt(Hamilton-Kreis).

1

2

36

54

7

Literaturverzeichnis

[1] A. Beutelspacher, Moderne Verfahren der Kryptographie (Von RSA zu Zero-Knowledge),Vieweg, Braunschweig, Wiesbaden, 1999.

[2] M. Clausen, A. Kerber, Mathematische Grundlagen fur Wirtschaftswissenschaftler, B·I· Wis-senschaftsverlag, Mannheim, Wien, Zurich,1991.

[3] W. Gotze, Mathematik fur Wirtschaftsinformatiker (Lehr- und Ubungsbuch), R. OldenbourgVerlag, Munchen, Wien, 2001.

[4] B. Luderer, U. Wurker, Einstieg in die Wirtschaftsmathematik, B. G. Teubner, Stuttgart,1997.

63

Documents

Mathematik III - TU Chemnitzpeju/skripte/wiinf/wiinf3.pdf · x ∈ R3, auf denen der Gewinn zu maximieren ist. Um die Grenzen der zur Verfugung stehenden¨ Rohstoﬀmengen nicht zu