- 67 -

4. Lineare Optimierung

Die lineare Optimierung (engl.: linear programming) ist ein Teilgebiet der Mathematik, insbesondere

des Operations Research, das in den 30er und 40er Jahren des 20. Jahrhunderts seine Entwicklung

begann. Berühmte Namen wie Dantzig1, Kantorowitsch2 und Leontief3 sind damit verbunden. Im We-

sentlichen werden lineare Funktionen optimiert unter Berücksichtigung von Nebenbedingungen in

Form linearer Gleichungen bzw. Ungleichungen. Auf solche Probleme trifft man in verschiedenen

betriebswirtschaftlichen Gebieten.

4.1. Einführende Beispiele

4.1.1. Ein Problem der Produktionsplanung

Zwei verschiedene Kunststoffprodukte I und II werden aus einem in beliebiger Menge verfügbaren

Rohgranulat hergestellt. Die Produktion wird durch die drei Prozesse „Warmpressen“, „Spritzguss“

und „Verpackung“ bestimmt. Das Produkt I entsteht durch Warmpressen des Granulats und das Pro-

dukt II durch Spritzguss des verflüssigten Granulats. Beide Produkte werden anschließend für den

Versand verpackt.

Die Abteilung „Warmpressen“ steht pro Tag für maximal 10 Stunden zur Verfügung und benötigt je

Tonne von Produkt I eine Stunde. Die Abteilung „Spritzguss“ steht sechs Stunden am Tag zur Verfü-

gung und benötigt ebenfalls eine Stunde für die Produktion von einer Tonne des Produktes II. In der

Verpackungsabteilung stehen vier Arbeitskräfte jeweils höchstens acht Stunden zur Verfügung. Je

Tonne von I werden 2 Stunden und je Tonne von II werden vier Stunden gebraucht. Die jeweiligen

Stückdeckungsbeiträge betragen bei I 30,- €/t und bei II 20,- €/t.

In welcher Mengenkonstellation soll die Firma die beiden Produkte herstellen, damit der Gesamtde-

ckungsbeitrag pro Tag maximiert wird?

Produkt I Produkt II max. Tageskapazität

Warmpressen 1 h/t 10 h

Spritzguss 1 h/t 6 h

Verpackung 2 h/t 4 h/t 32 h

Deckungsbeitrag 30,- €/t 20,- €/t

z ... Gesamtdeckungsbeitrag

1 G.B. Dantzig: US-amerikanischer Mathematiker (1914-2005), entwickelte das Simplex-Verfahren. 2 L.V. Kantorowitsch: russischer Mathematiker und Wirtschaftswissenschaftler (1912-1986), erhielt 1975 den

Nobelpreis für Wirtschaftswissenschaften. 3 W.W. Leontief: russischer Wirtschaftswissenschaftler (1905-1999), erhielt 1973 den Nobelpreis für Wirt-

schaftswissenschaften.

- 68 -

1x ... Produktionsmenge von Produkt I in t/Tag

2x ... Produktionsmenge von Produkt II in t/Tag

Mathematisches Modell: !2030 21 Maxxxz →+= (Zielfunktion)

≤+≤≤

3242

6

10

21

2

1

xx

x

x

(Nebenbedingungen)

0, 21 ≥xx (Nichtnegativitätsbedingungen)

4.1.2. Ein Diät-Problem

Ein Mensch benötigt täglich ein Mindestmaß an unterschiedlichen Nährstoffen (Kohlenhydrate, Ei-

weiß, Fett). Es stehen ihm die zwei Nahrungsmittelsorten I und II zur Verfügung.

Wie muss der Mensch sein tägliches Menü zusammenstellen, damit er einerseits genügend Nährstoffe

erhält und andererseits möglichst wenig dafür bezahlen möchte?

in ME/100g

Nahrungsmittel täglicher Mindest-

I II bedarf (in ME)

Eiweiß 3 1 15

Fett 1 1 11

Kohlenhydrate 2 8 40

Preis (in €/100g) 2,- 4,-

z ... Gesamtkosten

1x ... Nahrungsmittelmenge von I (in 100g/Tag)

2x ... Nahrungsmittelmenge von II (in 100g/Tag)

Mathematisches Modell: !42 21 Minxxz →+= (Zielfunktion)

≥+≥+≥+

4082

11

153

21

21

21

xx

xx

xx

(Nebenbedingungen)

0, 21 ≥xx (Nichtnegativitätsbedingungen)

- 69 -

4.2. Allgemeines Modell

Wir wollen nun in allgemeiner Form das mathematische Modell einer linearen Optimierungsaufgabe

(hier: LOA ) formulieren. Dabei wollen wir anfangs möglichst viele Varianten einschließen.

→++=!

!...11 Min

Maxxcxcz nn (Zielfunktion)

=++

=++

≤

≥

≤

≥

mnmnm

nn

b

b

xaxa

xaxa

M

K

MM

K 1

11

1111

(Nebenbedingungen)

0,...,1 ≥nxx (Nichtnegativitätsbedingungen)

In Vektor- bzw. Matrixschreibweise ergibt sich dann mit einer (m,n)-Matrix A und einer komponen-

tenweisen Interpretation der Relationszeichen bei den Vektoren:

→= xcz T rr

!

!

Min

Max

xAr

=≤

≥br

0rr ≥x

Insbesondere im Zusammenhang mit dem später zur rechnerischen Lösung einer LOA zu be-

nutzenden Simplexalgorithmus gewinnt die Normalform einer LOA (hier: NFLOA ), ein li-

neares Maximierungsproblem mit Nebenbedingungen in Gleichungsform, an Bedeutung:

→= xcz T rr!Max

xAr = b

r (mit 0

rr≥b )

0rr ≥x

Durch geeignete Umformungen bzw. Transformationen kann man eine beliebige LOA in ihre Normal-

form überführen.

• Liegen die Nebenbedingungen in der Form xAr

≤ br

vor, so kann man durch Einführung

eines Vektors yr

von nichtnegativen Schlupfvariablen (ökonomisch: freie, nicht ge-

nutzte Kapazitäten) die Gleichungsform erreichen: yExArr + = b

r. Im Fall der Form

xAr

≥ br

benutzt man yExArr − = b

r.

• Liegt ein Minimierungsproblem vor, so ist !Maxxcz T →−= rr das äquivalente Maximie-

rungsproblem.

- 70 -

• Im Fall von Variablenbeschränkungen führt eine lineare Transformation zur NFLOA:

(a) )0(≠≥ jj sx : jjj xsx ′+= mit 0≥′jx ,

(b) jj Sx ≤ : jjj xSx ′−= mit 0≥′jx .

• Fehlen die Nichtnegativitätsbedingungen gänzlich, so ersetzt man die Variable jx durch zwei

nichtnegative Variablen jx′ und jx ′′ mit jjj xxx ′′−′= (Nachteil: Verdopplung der Zahl der

Variablen).

Betrachtet man eine NFLOA, dann heißt ein Punkt nx �∈0r mit 0xAr = b

r und 00

rr ≥x zulässige

Lösung. Die Menge aller zulässigen Lösungen wird als zulässiger Bereich B bezeichnet.

Eine zulässige Lösung optxr

nennt man optimale Lösung der LOA, wenn für alle zulässigen

Lösungen Bx ∈r die Bedingung optTT xcxcrrrr ≤ erfüllt wird.

Eine Menge { }β=∈ xax Tn rrr|� mit �∈β heißt Hyperebene und die Menge { |nx �∈r

}β≤xaT rr nennt man einen Halbraum . Der Durchschnitt von endlich vielen Halbräumen im

n� wird konvexes Polyeder genannt. Handelt es sich um ein beschränktes konvexes Po-

lyeder, so spricht man auch von einem konvexen Polytop. Eine Linearkombination ∑=

n

jjj x

1α

mit

11

=∑=

n

jjα nennt man eine konvexe Linearkombination. Unter einem Extremalpunkt wollen

wir einen Punkt optxr

eines konvexen Polytops verstehen, der sich nicht als konvexe Linear-

kombination zweier verschiedener Punkte des konvexen Polytops darstellen lässt. Konvexe

Polyeder/Polytope besitzen nur eine endliche Anzahl an Extremalpunkten. Der zulässige Be-

reich B einer LOA ist ein konvexes Polyeder.

4.3. Grafische Lösung einer LOA

Für den Fall zweier Variabler ( 2=n ) besteht die Möglichkeit der grafischen Lösung der LOA. Ne-

benbedingungen und Nichtnegativitätsbedingungen beschreiben i.a. als lineare Ungleichungen Halb-

ebenen in der reellen Ebene, deren Durchschnitt ein ebenes konvexes Polyeder ist.

Vorgehen für eine grafische Lösung:

(1) Aufstellen des mathematischen Modells: xcz T rr= , xAr

=≤

≥br

, 0rr ≥x .

- 71 -

(2) Grafische Darstellung des zulässigen Bereichs B als Schnittmenge der Halbebenen, die den

Nebenbedingungen und Nichtnegativitätsbedingungen genügen.

(3) Grafische Darstellung einer beliebigen Zielfunktionsgeraden (z beliebig gewählt):

21

2

12 c

zx

c

cx +−= .

(4) Parallelverschiebung dieser Zielfunktionsgeraden in Richtung

• wachsender z-Werte bei Maximierungsproblemen,

• fallender z-Werte bei Minimierungsproblemen.

bis das zulässige Maximum/Minimum in (mindestens) einem Eckpunkt von B erreicht ist:

(a) Zielfunktionsgerade und B haben genau einen Eckpunkt → eindeutige optimale Lösung,

B

X1

X2

NNB x1

NNB x2

NB 1

NB 2

NB 3

ZF-Start

ZF-Optimum

(b) Zielfunktionsgerade und eine Kante von B fallen zusammen → unendlich viele optimale

Lösungen (Kante),

B

X1

X2

NNB x1

NNB x2

NB 1

NB 2

NB 3

ZF-Start

ZF-Optimum

- 72 -

(c) B ist in Richtung der verschobenen Zielfunktionsgeraden unbeschränkt → keine optima-

le Lösung.

B

X1

X2

NNB x1

NNB x2

NB 1

NB 2

NB 3

ZF-Start

ZF-später

Es sollen nun die einführenden Beispiele 4.1.1. und 4.1.2. grafisch gelöst werden. Wir beginnen mit

dem Produktionsplanungsproblem 4.1.1.

B

0

1

2

3

4

5

6

7

8

9

0 5 10 15X1

X2

NNB x1

NNB x2

NB 1

NB 2

NB 3

ZF-Start

ZF-Optimum

Bei den sich ergebenden Eckpunkten als Schnittpunkte zweier Restriktionen (NB bzw. NNB) unter-

scheidet man in zulässige Eckpunkte (0|0), (10|0), (10|3), (4|6), (0|6), welche den zulässigen Bereich B

definieren, und nichtzulässige Eckpunkte (16|0), (10|6), (0|8).

Der optimale Gesamtdeckungsbeitrag von 360max == zzopt € pro Tag wird durch die optimale Lö-

sung Toptx )3|10(=r

realisiert. Im Optimalpunkt )3|10( werden die maximalen Kapazitäten

beim Warmpressen und beim Verpacken exakt ausgenutzt sein (� „Engpassfertigungsstel-

len“), während die Fertigungsstelle Spritzguss nur zur Hälfte ausgelastet ist.

- 73 -

Es folgt das Diätproblem 4.1.2.

B

0

2

4

6

8

10

12

14

0 5 10 15 20X1

X2

NNB x1

NNB x2

NB 1

NB 2

NB 3

ZF-Start

ZF-Optimum

Bei den sich hier ergebenden Eckpunkten als Schnittpunkte zweier Restriktionen (NB bzw. NNB)

unterscheidet man in zulässige Eckpunkte (0|15), (2|9), (8|3), (20|0), welche den zulässigen Bereich B

definieren, und nichtzulässige Eckpunkte (11|0), (5|0), (11

40|11

45), (0|0), (0|5), (0|11).

Die optimalen (minimalen) Nahrungsmittelkosten von −== ,28minzzopt € pro Tag werden durch

die optimale Lösung Toptx )3|8(=r

realisiert. Im Optimalpunkt )3|8( , d.h. bei 800g der Sorte I

und 300g der Sorte II, werden die Mindestmengen bei Fett und bei Kohlenhydraten exakt

ausgenutzt, während 12 Mengeneinheiten mehr Eiweiß als erforderlich enthalten sind.

Bei beiden Aufgabenstellungen wurde deutlich, dass man sich bei der Lösungssuche auf die Eckpunk-

te des zulässigen Bereichs beschränken kann.

4.4. Anwendungsgebiete der Linearen Optimierung

4.4.1. Mischungsprobleme

Eine mögliche Anwendung der linearen Optimierung sind Mischungsprobleme, bei denen es darum

geht, Rohstoffe oder Halbprodukte zu einem Endprodukt zusammenzustellen, wobei die Menge der

jeweiligen Bestandteile innerhalb eines bestimmten Bereichs variieren können. Dabei sind in der Re-

gel die Kosten zu minimieren bzw. der Gesamtgewinn zu maximieren. Geht es beim Mischen um die

Zusammenstellung von Speise- oder Diätplänen, so findet man in der Literatur auch die Begriffe

Hausfrauen- bzw. Diätproblem.

- 74 -

Bei unserem Mischungsproblem soll in einer Firma Tierfutter produziert werden, wofür die zwei Zu-

sätze Z1 und Z2 verwendet werden. Jeder Sack Tierfutter muss mindestens 100g des Nährstoffes N1,

mindestens 80g des Nährstoffes N2 und mindestens 120g des Nährstoffes N3 beinhalten.

Anteil N1

(in g/Sack)

Anteil N2

(in g/Sack)

Anteil N3

(in g/Sack)

Kosten

(in €/Sack)

Z1 20 20 60 8

Z2 50 30 40 9

Wie viel Zusatzmittel sind jeweils pro Sack Futter zu verarbeiten, damit die Kosten für die Zusatzmit-

tel pro Sack minimal werden?

Mathematisches Modell: !98 21 Minxxz →+= (Zielfunktion)

1246

832

1052

21

21

21

≥+≥+≥+

xx

xx

xx

(Nebenbedingungen)

0, 21 ≥xx (Nichtnegativitätsbedingungen)

Dieses Minimierungsproblem ist mit seinen zwei Variablen ( 2=n ) auch grafisch lösbar. Mit der

optimalen Lösung Toptx )4,2|4,0(=r

ergeben sich 24,80 € als minimale Kosten pro Sack Futter.

B

0

1

2

3

4

5

6

0 1 2 3 4 5 6X1

X2

NNB x1

NNB x2

NB 1

NB 2

NB 3

ZF-Start

ZF-Optimum

4.4.2. Transportplanung

Das nächste Beispiel für die Behandlung als lineares Optimierungsproblem soll die Transportplanung

sein. Diese Problemart zeichnet sich durch eine spezielle Art der Koeffizientenmatrix in den Nebenbe-

dingungen aus, was auch zu speziellen Lösungsmethoden führt. Auf diese kann hier aber nicht einge-

- 75 -

gangen werden, so dass an dieser Stelle nur die aufwendigere Simplexmethode benutzt werden soll.

Grafische Lösungen scheiden wegen der großen Anzahl an Variablen aus ( 2>n ). Bei Transportprob-

lemen ist ein einheitliches Gut zu transportieren, wobei der Transportaufwand proportional zu den

Entfernungen und zu den zu transportierenden Mengen ist. Das Gut wird an mehreren Orten produ-

ziert oder gelagert, und es wird an verschiedenen (anderen) Orten benötigt. Das Gesamtaufkommen ist

gleich dem Gesamtbedarf. Die Gesamtkosten sind dann zu minimieren.

In unserem Beispiel wird ein Produkt an zwei Standorten für drei Verbraucher hergestellt. Der Stand-

ort S1 kann höchstens 150 ME liefern, der Standort S2 200 ME. Die Verbraucher V1, V2, V3 haben

einen Bedarf von 80, 90 bzw. 130 ME. Bei der Auslieferung entstehen wegen der unterschiedlichen

Entfernungen verschiedene Kosten:

V1 (in GE) V2 (in GE) V3 (in GE)

S1 4 8 6

S2 10 3 5

Welche Mengen sind von den einzelnen Standorten an die Verbraucher zu liefern, so dass die Ge-

samttransportkosten minimal werden?

Mathematisches Modell:

!5310684 232221131211 Minxxxxxxz →+++++= (Gesamttransportkosten)

130

90

80

2313

2212

2111

=+=+=+

xx

xx

xx

(Bedarfsdeckung)

200

150

232221

131211

≤++≤++

xxx

xxx (Lieferkapazitäten)

0≥ijx ( 2,1=i und 3,2,1=j )

S2

200 ME

S1

150 ME

V1

80 ME

V3

130 ME

V2

90 ME

x11 x13 x12 x23 x22 x21

- 76 -

Die optimale Lösung dieses Transportproblems ist dann Toptx )110|90|0|20|0|80(=r

, was zu

minimalen Gesamtkosten von 1260=optz GE führt.

4.4.3. Produktionsprogrammplanung

Wie soll ein Betrieb seine Produktion auslegen, damit das geplante Produktionsprogramm auch reali-

sierbar ist und z.B. der Deckungsbeitrag maximiert wird?

In unserem Beispiel sollen drei Produkte auf vier Maschinen produziert werden. Die notwendigen

Informationen für die Produktion sind:

P1 P2 P3

M1 2 4 3

M2 3 6 9

M3 5 2 4

M4 7 1 7

Maschine 1 steht maximal 500 ZE, Maschine 2 maximal 600 ZE, Maschine 3 maximal 1000 ZE und

Maschine 4 maximal 750 ZE zur Verfügung. Beim Verkauf der Produkte 1, 2, 3 werden die De-

ckungsbeiträge 20, 15 bzw. 32 GE/ME erzielt.

Wie viel soll von den einzelnen Produkten gefertigt werden, damit die Maschinenkapazitäten nicht

überschritten werden und der Gesamtdeckungsbeitrag maximal wird?

Mathematisches Modell: jx ... produzierte Menge von Produkt j

!321520 321 Maxxxxz →++= (Zielfunktion)

75077

1000425

600963

500342

321

321

321

321

≤++≤++≤++≤++

xxx

xxx

xxx

xxx

(Nebenbedingungen)

0,, 321 ≥xxx (Nichtnegativitätsbedingungen)

Die optimale Lösung Toptx )0|50|100(=r

führt auf einen maximalen Deckungsbeitrag von

2750=optz GE.

In einem allgemeineren Beispiel für die Produktionsprogrammplanung sind auch noch Mindest- und

Maximalfertigungsmengen gegeben, d.h. es gibt eine zusätzliche Bedingung Sxsrrr ≤≤ .

- 77 -

4.4.4. Ablaufplanung

Ein betrachteter Prozess besteht aus verschiedenen Teilprozessen. Diese können dabei teils parallel

ablaufen, aber auch nacheinander. Es gibt n Knoten (Knoten ... Beginn oder Ende eines Teilprozes-

ses). Mit C bezeichnen wir die Matrix der Zeitdauern der Teilprozesse. Ein Ereignis i kann erst eintre-

ten, wenn alle im Knoten i endenden Teilprozesse abgeschlossen sind. Der Knoten 1 steht für den

Beginn, der Knote n entspricht dem Ende.

Für 5=n betrachten wir den folgenden Beispielprozess (ZE ... Zeiteinheit):

Zwei mögliche Fragestellungen sind hierbei von Interesse:

• Vorwärtsplanung: Gegeben ist ein Starttermin t1 und gesucht wird der frühest mögliche

Endtermin tn ,

• Rückwärtsplanung: Gegeben ist ein Endtermin tn und gesucht wird der spätest mögliche

Starttermin t1 .

(i,j) ... Teilprozess, der im Knoten i beginnt und im Knoten j endet

cij ... Zeitdauer des Teilprozesses (i,j) mit )( ijcC = , wobei 0=ijc für den Fall, dass kein

Prozess (i,j) existiert

Bj ... Menge aller Teilprozesse (i,j)

nt �∈r

... Vektor der Zeitpunkte ti , an denen das Ereignis i eintritt

Es gelten die folgenden Restriktionen:

• jiji tctnj =+=∀ :,...,2 für alle (i,j) jB∈ ,

• 0:,...,1 ≥=∀ itni .

Die Zielfunktion ist dann für die

• Vorwärtsplanung: !Mintn → ,

• Rückwärtsplanung: !1 Maxt → .

2

1

4

3

5

10 ZE 6 ZE

12 ZE 11 ZE

13 ZE

9 ZE 5 ZE

- 78 -

Für unser konkretes Beispiel liefert die Rückwärtsplanung den spätesten Anfangstermin von 30 (ZE)

und die Vorwärtsplanung den frühesten Endtermin nach 30 (ZE).

4.4.5. Ermittlung optimaler Zuschnittpläne

Optimaler Zuschnitt bedeutet die Lösung eines Minimierungsproblems, bei dem ein Ausgangsmaterial

(Stahlbleche, Papierrollen, ...) in kleinere Bestandteile zerlegt werden muss bei kleinstmöglichem Ver-

schnitt.

In unserem Beispiel soll das Ausgangsmaterial aus Papierrollen fester Länge und vorgegebener Breite

von 2,10m bestehen. Diese werden in Rollen von 62cm, 55cm bzw. 40cm Breite zerschnitten. Die

Länge der schmaleren Rollen soll gleich der der Ausgangsrolle sein. Es gibt dann sechs sinnvolle Va-

rianten des Zuschnitts:

Zuschnittvariante Bedarf

Rollenbreite 1 2 3 4 5 6 (in Stück)

62cm 3 2 1 0 0 0 300

55cm 0 0 1 3 2 0 600

40cm 0 2 2 1 2 5 600

Verschnitt 24 6 13 5 20 10

Es soll nun ermittelt werden, wie oft welche Zuschnittvariante angewendet werden muss, damit der

Materialverlust minimiert und die Einhaltung des Bedarfs an schmaleren Rollen gesichert wird.

Mathematisches Modell (minimaler Materialverlust):

!1020513624 654321 Minxxxxxxz →+++++= (Zielfunktion)

6005222

60023

30023

65432

543

321

≥++++≥++≥++

xxxxx

xxx

xxx

(Nebenbedingungen)

0,,,,, 654321 ≥xxxxxx (Nichtnegativitätsbedingungen)

Alternativ wäre auch eine andere Zielfunktion für einen minimalen Rollenverbrauch denkbar:

!654321 Minxxxxxxz →+++++= .

Die optimale Kombination der Zuschnittvarianten )20|0|200|0|150|0( ergibt einen Zuschnitt

von 370 Rollen und ist hier wegen der Zahl der Variablen ( 6=n ) nicht grafisch bestimmbar.

Anmerkungen:

(1) Ein klassisches Anwendungsgebiet der linearen Optimierung ist die Bestimmung eines Rou-

tings für Verkehrsanforderungen in Telekommunikations- oder Verkehrsnetzen, oft in Verbindung mit

- 79 -

Kapazitätsplanungen. Dabei müssen Verkehrsflüsse so durch ein Netz geroutet werden, dass alle Ver-

kehrsanforderungen erfüllt werden, ohne die Kapazitätsbedingungen zu verletzen. Diese sogenannten

Mehrgüterflüsse (engl.: multicommodity flow) sind ein Beispiel für ein Problem, das mit linearer

Optimierung gut lösbar ist, für das aber im allgemeinen Fall kein exakter Algorithmus bekannt ist.

(2) Zu den Beispielen 4.4.1.- 4.4.5. kann man sich eine Übungsmappe in Excel (lin-opt.xls) von

der Homepage des Autors (www.math-service.de) herunterladen. Dort wird die Lösung der Beispiele

mittels des Solvers von Excel demonstriert (Blätter „...-Muster“) und eine Möglichkeit zur eigenen

Übung (Blätter „...-Übung“) eingeräumt.

4.5. Der primale Simplexalgorithmus

Der primale Simplexalgorithmus löst das LOA in Normalform: →= xcz T rr!Max , xA

r = br

(mit der (m,n)-Matrix A und 0rr

≥b ), 0rr ≥x . Es sei { }0,|

rrrrr ≥=∈= xbxAxB n� ein gegebenes

Polyeder.

Eine Lösung xr

des linearen Gleichungssystems xAr = b

r heißt Basislösung, wenn eine Indexmenge

I mit mI = existiert, so dass 0=jx für alle Ij ∉ und die Spaltenvektoren { }IjA j ∈| der Ma-

trix A linear unabhängig sind.

Eine Basislösung heißt (primal) zulässig, wenn sie außer den linearen Gleichungsbedingungen

xAr = b

r auch noch die Nichtnegativitätsbedingungen 0

rr ≥x erfüllt.

Folgende Merkmale zeichnen den zulässigen Bereich { }0,|rrrrr ≥=∈= xbxAxB n

� der NFLOA aus:

• Wenn ∅≠B , so besitzt B mindestens einen Eckpunkt. Jedem Eckpunkt von B entspricht

eine zulässige Basislösung.

• Das Polyeder B besitzt nur endlich viele Eckpunkte.

• Wenn die NFLOA lösbar ist, so besitzt sie auch eine optimale zulässige Basislösung.

Als Basismatrix A der Matrix A bezeichnen wir eine quadratische Teilmatrix von A mit

mArgArg == )()( . Mit )|( NAA = ist das Gleichungssystem xAr = b

r mit )|( NA

T xxxrrr =

äquivalent zu bxNxA NA

rr =+ . Dabei bezeichnen wir Axr

als Vektor der Basisvariablen und Nxr

als Vektor der Nichtbasisvariablen. Damit gilt:

NA xNAbAx 11 −− −=rr

, (1)

d.h. mit 0rr =Nx und 01

rr≥− bA erhält man eine zulässige Basislösung.

Beispiel: (NFLOA)

!21 Maxxxz →+=

- 80 -

42

42

221

121

=++=++

yxx

yxx

0, 21 ≥xx

Rechnung mit dem Gauß-Jordan-Algorithmus:

I.

BV 1x 2x 1y 2y br

1y 2 1 1 0 4

2y 1 2 0 1 4

1y 0 -3 1 -2 -4

1x 1 2 0 1 4

II.

BV 1x 2x 1y 2y br

1y 2 1 1 0 4

2y 1 2 0 1 4

1x 1 0,5 0,5 0 2

2y 0 1,5 -0,5 1 2

1x 1 0 6,0 - 3,0 3,1

2x 0 1 - 3,0 6,0 3,1

Die entsprechenden Basislösungen sind dann

• Tx )4|4|0|0(1 =r, Tx )2|0|0|2(2 =r

, Tx )0|0|3,1|3,1(3 =r (zulässige Basislösungen)

• Tx )0|4|0|4(4 −=r (entartete Basislösung)

Die optimale Basislösung ist hier Tx )0|0|3,1|3,1(3 =r, womit die Basismatrix bzw. die Inverse

der Basismatrix dann

=

21

12A bzw.

−−

=−

6,03,0

3,06,01A

sind. Die grafische Lösung der LOA demonstriert dies anschaulich.

B

0

1

2

3

4

5

0 1 2 3 4 5X1

X2

NNB x1

NNB x2

NB 1

NB 2

ZF-Start

ZF-Optimum

- 81 -

Zwei Basislösungen nennt man benachbart, wenn die ihnen entsprechenden Darstellungen (1) der

allgemeinen Lösung von xAr = b

r durch einen Schritt im Gauß-Jordan-Algorithmus überführt wer-

den.

4.5.1. Der Optimalitätstest

Wir setzen nun die allgemeine Lösung (1) des linearen Gleichungssystems xAr = b

r in die NFLOA

ein: ( ) NT

NNT

ANT

NAT

AT xcxNAbAcxcxcxcz

rrrrrrrrrr +−=+== −− 11

( ) NT

NT

AT

A xcNAcbAcrrrrr −−= −− 11 .

Die Zielfunktion ist lediglich unter Einbeziehung der Nichtnegativitätsbeziehungen zu maxi-

mieren: ( ) !11 MaxxcNAcbAcz NT

NT

AT

A →−−= −− rrrrr ,

011rrr ≥−= −−

NA xNAbAx ,

0rr ≥Nx .

Die reellen Zahlen ( )j

N

TTAj cNAc

−=∆ − rr 1 heißen Optimalitätsindikatoren (der Nichtbasis-

variablen) und für eine zulässige Basislösung, die optimal ist, gilt dann: 0rr

≥∆ .

Im Beispiel erhalten wir somit für die entartete Basislösung Tx )0|4|0|4(4 −=r die Werte

( )0|0|1|1 −−=∆Tr , für die zulässige Lösung Tx )2|0|0|2(2 =r die Werte =∆Tr

( )0|5,0|5,0|0 − und für die optimale Lösung Tx )0|0|3,1|3,1(3 =r die Werte =∆Tr

( ) T03,0|3,0|0|0r

≥ .

1 1 0 0

BV Acr

1x 2x 1y 2y br

1y 0 2 1 1 0 4

2y 0 1 2 0 1 4

„Kellerzeile“ -1 -1 0 0 0

1x 1 1 0,5 0,5 0 2

2y 0 0 1,5 -0,5 1 2

„Kellerzeile“ 0 -0,5 0,5 0 2

- 82 -

1x 1 1 0 6,0 - 3,0 3,1

2x 1 0 1 - 3,0 6,0 3,1

„Kellerzeile“ 0 0 3,0 3,0 6,2

Stopp ( 0≥ )

In der sogenannten Kellerzeile stehen dann also die Werte TN

TA cNAc

rr −−1 , bAc TA

rr 1− und

TTA

TA cAAc 01

rrr =−− .

Eine zulässige Basislösung TNA xxx )|( *** rrr = mit bAxA

rr 1* −= und 0*rr =Nx ist primal nicht-

entartet, wenn 01rr

>− bA ist, d.h. alle Basisvariablen echt positiv sind. Ist *xr

eine primal

nichtentartete zulässige Basislösung zur Basismatrix A und 00

<∆ j für eine Nichtbasisva-

riable (NBV) 0j

x , so ist *xr

nicht optimal.

4.5.2. Der Verbesserungsschritt

Sei nun 00

<∆ j für eine NBV 0j

x in der aktuellen zulässigen Basislösung. Dann kann durch

eine Vergrößerung von 0j

x eine Lösung mit größerem bzw. (im Entartungsfall) nicht kleine-

rem Zielfunktionswert konstruiert werden. Für die Nebenbedingungen gilt damit:

( ) ( ) 000

11 ≥− −−jiji xAAbA

r für alle mi ,...,1= mit 0

0≥jx ,

wenn alle anderen NBV gleich Null sind. Die 0j -te Spalte ( )0

1jAA − von AA 1− gehört zu

NA 1− . Die Auflösung dieses Ungleichungssystems ergibt somit

( )( ) ( )

( )( ) ( )

>≤

<≥

−−

−

−−

−

0für

0für

0

0

0

0

0

11

1

11

1

ijij

i

ijij

i

j

AAAA

bA

AAAA

bA

xr

r

wobei ( )

( ) ( )

>≤ −−

−0min

0

0

0

11

1

ijij

ij AA

AA

bAx

r

.

- 83 -

Für den Fall ( ) 00

1r

>−jAA bestimmt man =Θi

( )( )

0

1

1

ij

i

AA

bA−

− r

für ( ) 00

1 >−ijAA und =Θ *

i

( )( ) ( )

>−−

−0min

0

0

11

1

ijij

i AAAA

bAr

und fügt diese Werte als zusätzliche Spalte an die Berech-

nungstabelle an.

Für den Fall ( ) 00

1r

≤−jAA ist der Wert *Θ nicht bestimmbar, d.h. die LOA ist dann nicht lösbar,

weil die Zielfunktionswerte nach oben unbeschränkt wachsen über dem zulässigen Bereich B.

1 1 0 0

BV Acr

1x 2x 1y 2y br

Θr

1y 0 2 1 1 0 4

←

= 22

4

2y 0 1 2 0 1 4 4

1

4 =

„Kellerzeile“ -1↑ -1 0 0 0

1x 1 1 0,5 0,5 0 2 4

5,0

2 =

2y 0 0 1,5 -0,5 1 2

←

= 3,15,1

2

„Kellerzeile“ 0 -0,5↑ 0,5 0 2

1x 1 1 0 6,0 - 3,0 3,1

2x 1 0 1 - 3,0 6,0 3,1

„Kellerzeile“ 0 0 3,0 3,0 6,2

Stopp ( 0≥ )

4.5.3. Der Simplexalgorithmus

Zur schematischen Darstellung einer Simplextabelle nehmen wir an, dass das lineare Gleichungssy-

stem bxArr = nach den ersten m Variablen aufgelöst wird. Mit )(1

ijaAA =− und ( )bAr

1− )( ib= star-

tet der Simplexalgorithmus mit der Tabelle:

- 84 -

1c 2c K mc 1+mc K nc

BV Acr

1x 2x K mx 1+mx K nx b

r

Θr

1x 1c 1 0 K 0 1,1 +ma K na ,1 1b 1Θ

2x 2c 0 1 K 0 1,2 +ma K na ,2 2b 2Θ

M M M M M M M M M

mx mc 0 0 K 1 1, +mma K nma , mb mΘ

0 0 K 0 1+∆m K n∆ bc TA

rr

Bemerkungen:

(1) In der Simplextabelle sind 1x , ... , mx die Basisvariablen (BV). Im Allgemeinen muss das

nicht so sein.

(2) Der Wert einer BV jx ist jb .

(3) NBV haben den Wert Null.

(4) Der aktuelle Zielfunktionswert ist bAcbcxc TA

TAA

TA

rrr

rrr 1−== .

Primaler Simplexalgorithmus:

Gegeben: Eine lineare Optimierungsaufgabe in Normalform:

≥=

→=

0

!

rr

rr

rr

x

bxA

Maxxcz T

(NFLOA).

Gesucht: Eine optimale Lösung.

(1) Bestimme eine Basismatrix A mit 01rr

≥− bA und stelle die Simplextabelle auf.

(2) Wenn alle 0≥∆ j sind, dann ist die vorliegende zulässige Basislösung optimal, stopp.

Sonst wähle ein 0j mit 00

<∆ j .

(3) Wenn ( ) 00

1 ≤−ijAA ist für alle i, dann ist die LOA nicht lösbar, da die Zielfunktion über dem

zulässigen Bereich B nach oben unbeschränkt ist. Sonst bestimme die Werte ( )

( )0

1

1

ij

ii

AA

bA−

−=Θ

r

für

alle i mit ( ) 00

1 >−ijAA sowie =Θ

0i ( ){ }0|min

0

1 >Θ −iji AA .

(4) Die Basisvariable zur Zeile i0 in der Simplextabelle verlässt die Basis, dafür wird 0j

x in die

Basis aufgenommen. Entsprechend wird die Simplextabelle umgerechnet: In den Spalten BV und

- 85 -

Acr

wird die Basisvariable in der i0-ten Zeile durch 0j

x und deren Zielfunktionskoeffizient durch 0j

c

ersetzt. Der Rest der Tabelle wird mit dem Algorithmus von Gauß-Jordan umgerechnet, wobei in der

Spalte j0 eine Einheitsspalte mit einer 1 in der Zeile i0 geschaffen wird.

Bemerkungen:

(1) Die Kellerzeile T∆ der Optimalitätsindikatoren kann sowohl mit dem Gauß-Jordan-

Algorithmus (Schaffung einer Null in der j0-ten Spalte) als auch mit der entsprechenden Definitions-

formel berechnet werden.

(2) Aktuelle Zielfunktionswerte dürfen nicht fallen und 01rr

≥− bA in allen Iterationen.

(3) Wenn ein i∆ einer NBV ix zur optimalen Lösung Null ist, so können weitere optimale Lö-

sungen existieren. Die Aufnahme von ix in die Basis kann dann weitere optimale Lösungen liefern.

Geht die Aufnahme nicht, so gibt es eine unbeschränkte Kante optimaler Lösungen.

Beispiel:

LOA: !21 Maxxxz →+= NFLOA: !21 Maxxxz →+=

2

22

1

21

≤≤+−

x

xx

2

22

21

121

=+=++−

yx

yxx

0, 21 ≥xx 0,,, 2121 ≥yyxx

Simplextabelle:

1 1 0 0

BV Acr

1x 2x 1y 2y br

Θr

1y 0 -1 2 1 0 2 ---

2y 0 1 0 0 1 2 ←2

-1↑ -1 0 0 0

1y 0 0 2 1 1 4 ←2

1x 1 1 0 0 1 2 ---

0 -1↑ 0 1 2

2x 1 0 1 0,5 0,5 2

1x 1 1 0 0 1 2

0 0 0,5 1,5 4

Stopp ( 0≥ )

- 86 -

Damit ist die optimale Lösung der LOA ( )Toptx 2|2=r, welche zum optimalen (maximalen) Ziel-

funktionswert 4=optz führt.

Beispiel:

LOA: !21 Maxxxz →−= NFLOA: !21 Maxxxz →−=

6

8

2

2

321

321

≤≤

−+−+

xxx

xxx

6

8

2

2

2

1

321

321

==

++

−+−+

y

y

xxx

xxx

0,, 321 ≥xxx 0,,,, 21321 ≥yyxxx

Simplextabelle:

1 -1 0 0 0

BV Acr

1x 2x 3x 1y 2y br

Θr

1y 0 2 1 -1 1 0 8 ←4

2y 0 1 1 -2 0 1 6 6

-1↑ 1 0 0 0 0

1x 1 1 0,5 -0,5 0,5 0 4 ---

2y 0 0 0,5 -1,5 -0,5 1 2 ---

0 1,5 -0,5↑ 0,5 0 4

Wegen 0)(0

1r

≤−jAA für 30 =j ist die LOA nicht lösbar, weil die Zielfunktion über dem zulässi-

gen Bereich B nicht nach oben beschränkt ist.

Im Fall primal entarteter zulässiger Basislösungen kann 0* =Θ sein und die Umrechnung der Simp-

lextabelle kann zu keiner neuen zulässigen Basislösung führen. Bei Wiederholung dieses Prozesses

werden nacheinander verschiedene Basismatrizen pAAA ,...,, 21 berechnet, die alle den gleichen

Eckpunkt erzeugen. Gilt dann auch noch pAA =1 , so spricht man von einem Zyklus und der Simp-

lexalgorithmus ist nicht mehr endlich.

Beispiel: !65,02075,0 4321 Maxxxxxz →−+−=

1

035,0125,0

09825,0

33

24321

14321

=+=++−−=++−−

yx

yxxxx

yxxxx

0,rrr ≥yx

- 87 -

Wenn im Schritt 2 des primalen Simplexalgorithmus stets die Spalte mit dem kleinsten Wert des Op-

timalitätsindikators gewählt wird, so berechnet der Algorithmus die Folge der Basislösungen

)||( 321 yyy , )||( 321 yyx , )||( 321 yxx , )||( 323 yxx , )||( 343 yxx , )||( 341 yxy ,

)||( 321 yyy mit dem gleichen Zielfunktionswert 0=z (Zyklus!). Zyklen vermeiden kann man

beispielsweise mit der Bland’schen Regel:

Es ist der zulässige Bereich B nicht leer. Wenn im Schritt 2 des primalen Simplexalgorithmus der In-

dex 0j als kleinster Index mit negativem Optimalitätsindikator und im Schritt 3 der kleinste Index i0

mit *0

Θ=Θi gewählt wird, so endet der primale Simplexalgorithmus nach endlich vielen Iterationen

mit der optimalen Lösung oder mit der Unbeschränktheit nach oben der Zielfunktion.

Im Beispiel würde somit aus )||( 343 yxx dann in )||( 143 xxx übergegangen werden und die op-

timale Lösung ist somit Toptx )0|0|75,0|0|1|0|1(=r

mit dem maximalen (optimalen) Zielfunkti-

onswert 25,1=optz .

4.5.4. Berechnung einer ersten zulässigen Basislösung

Ist die LOA in der Gestalt

0

)0(

!

rr

rrrr

rr

≥≥≤

→=

x

bbxA

Maxxcz T

gegeben, so kann man auf einfache Weise eine zulässige Startlösung bestimmen. Die Normalform der

LOA ist dann nach Einführung von Schlupfvariablen

0,

)0(

!

rrr

rrrrr

rr

≥≥=+

→=

yx

bbyExA

Maxxcz T

.

Wegen 0rr

≥b ist mit der Basismatrix EA = der Vektor TNA xxx )|( *** rrr = mit byxA

rrr ==* und

0*rrr == xxN eine zulässige Basislösung.

Eine andere Möglichkeit bei einer NFLOA eine zulässige Basislösung zu finden, ist die Zwei-

Phasen-Methode. Wir betrachten eine NFLOA

0

)0(

!

rr

rrrr

rr

≥≥=

→=

x

bbxA

Maxxcz T

.

- 88 -

Bei der Aufgabe der ersten Phase, einer Ersatzaufgabe mit künstlichen Variablen mvv ,,1 K , wird

eigentlich die Summe aller künstlichen Variablen minimiert.

!ˆ 21 Maxvvvz m →−−−−= K

0,rrr

rrr

≥

=+

vx

bvExA

Eine erste zulässige Basislösung dafür ist mit EA = der Vektor TNA xxx )|( *** rrr = mit vxA

rr =*

br

= und 0*rrr == xxN . Die Zielfunktion des Ersatzproblems z ist nach oben durch Null be-

schränkt, so dass die Ersatzaufgabe auch immer lösbar ist.

Die NFLOA besitzt genau dann eine zulässige Lösung, wenn die obige Ersatzaufgabe eine

zulässige Lösung mit 0rr =v besitzt.

Die Aufgabe der ersten Phase hat den optimalen Zielfunktionswert Null genau dann, wenn die

NFLOA eine zulässige Lösung besitzt.

Zwei-Phasen-Algorithmus:

Gegeben: Eine lineare Optimierungsaufgabe in Normalform:

≥=

→=

0

!

rr

rr

rr

x

bxA

Maxxcz T

(NFLOA).

Gesucht: Eine optimale Lösung.

(1) Wenn in A eine Einheitsmatrix vorhanden ist, gehe zu Schritt (4).

(2) Konstruiere und löse die Aufgabe der ersten Phase:

0,

!ˆ 21

rrr

rrr

K

≥

=+

→−−−−=

vx

bvExA

Maxvvvz m

Wenn der optimale Zielfunktionswert *z dieser Aufgabe kleiner als Null ist, stopp, die zu lösende

LOA hat einen leeren zulässigen Bereich, d.h. sie ist nicht lösbar.

(3) Berechne die Starttabelle der Aufgabe der zweiten Phase (d.h. der ursprünglichen NFLOA)

unter Zuhilfenahme der zur optimalen Lösung der Aufgabe der ersten Phase gehörigen Simplextabelle

(z.B. nach Streichung der jv -Spalten).

(4) Löse die Aufgabe der zweiten Phase, d.h. die ursprüngliche LOA.

Beispiel: !3 321 Maxxxxz →++−=

0,,

32

1

321

321

31

≥=++=−

xxx

xxx

xx

- 89 -

Anwendung der Zwei-Phasen-Methode:

(Phase 1) Einführung künstlicher Variabler 21, vv und Anwendung des Simplexalgorithmus auf

die Ersatzaufgabe: !ˆ 21 Maxvvz →−−=

0,,,,

3

1

2

21321

2321

131

≥=+=

+++−

vvxxx

vxxx

vxx

0 0 0 -1 -1

BV Acr

1x 2x 3x 1v 2v br

Θr

1v -1 1 0 -1 1 0 1 ←1

2v -1 1 2 1 0 1 3 3

-2↑ -2 0 0 0 -4

1x 0 1 0 -1 1 0 1 ---

2v -1 0 2 2 -1 1 2 ←1

0 -2↑ -2 2 0 -2

1x 0 1 0 -1 1 0 1

2x 0 0 1 1 -0,5 0,5 1

0 0 0 1 1 0

Stopp ( 0≥ )

(Phase 2) Anwendung des Simplexalgorithmus auf die Originalaufgabe nach Streichung der v-

Spalten im Schlusstableau der Ersatzaufgabe und Ersetzen der Zielfunktionskoeffizienten:

-1 1 3

BV Acr

1x 2x 3x br

Θr

1x -1 1 0 -1 1 ---

2x 1 0 1 1 1 ←1

0 0 -1↑ 0

1x -1 1 1 0 2

3x 3 0 1 1 1

0 1 0 1

Stopp ( 0≥ )

- 90 -

Die optimale Lösung Toptx )1|0|2(=r

führt zum optimalen (maximalen) Zielfunktionswert

1=optz .

4.6. Dualität in der linearen Optimierung

In der Optimierung spielt der Begriff der Dualität eine große Rolle. Es werden immer Paare zueinan-

der dualer Aufgaben betrachtet. Die Formulierung einer dualen LOA erfolgt ausgehend vom Aussehen

der primalen LOA mittels folgender Konstruktionsprinzipien:

Primale LOA Duale LOA

!Maxxcz Tp →= rr

!Minybz Td →= rr

Zielfunktionskoeffizienten jc rechte Seite jc

rechte Seite ib Zielfunktionskoeffizienten ib

Koeffizientenmatrix A Koeffizientenmatrix AT

Nebenbedingung i

m

jjij bxa ≤∑

=1

Vorzeichenbedingung 0≥iy

Nebenbedingung i

m

jjij bxa ≥∑

=1

Vorzeichenbedingung 0≤iy

Nebenbedingung i

m

jjij bxa =∑

=1

keine Vorzeichenbedingung für iy

Vorzeichenbedingung 0≥jx Nebenbedingung j

n

iiij cya ≥∑

=1

Vorzeichenbedingung 0≤jx Nebenbedingung j

n

iiij cya ≤∑

=1

keine Vorzeichenbedingung für jx Nebenbedingung j

n

iiij cya =∑

=1

Durch die Anwendung dieser Prinzipien entstehen folgende Paare dualer Aufgaben:

Primale LOA Duale LOA

NFLOA:

0

!

rr

rr

rr

≥=

→=

x

bxA

Maxxcz Tp

DNFLOA:

cyA

MinybzT

Td

rr

rr

≥

→= !

- 91 -

PLOA:

0

!

rr

rr

rr

≥≤

→=

x

bxA

Maxxcz Tp

DLOA:

0

!

rr

rr

rr

≥

≥

→=

y

cyA

MinybzT

Td

In diesem Abschnitt wollen wir uns auf das Paar dualer Aufgaben NFLOA und DNFLOA beschrän-

ken. Mittels Transformation kann man sich analoge Aussagen ableiten.

Es seien *xr

eine zulässige Lösung von der Aufgabe NFLOA und *yr

eine zulässige Lösung von der

Aufgabe DNFLOA. Dann gilt ** ybxc TT rrrr ≤ (schwache Dualität).

Ein Optimalitätskriterium lautet: Seien *xr

eine zulässige Lösung der NFLOA und *yr

eine zulässige

Lösung der DNFLOA. Dann sind folgende Aussagen äquivalent:

(1) *xr

ist optimal für die NFLOA, *yr

ist optimal für die DNFLOA.

(2) ** ybxc TT rrrr = (starke Dualität).

(3) ( ) 0** =− cyAx TT rrr (Komplementaritätsbedingungen).

Unter Umständen ist das Lösen der dualen Aufgabe günstiger, wenn z.B. das Originalproblem die

Struktur der DLOA mit 0rr ≥c hat. Dann hat das dazu duale Problem PLOA sofort die zulässige Lö-

sung 0rr =x .

Beispiel: !23 4321 Maxxxxxz p →−++=

532

4

4321

4321

≤+−+≤+++

xxxx

xxxx

0rr ≥x

hat die duale LOA !54 21 Minyyzd →+=

1

1

23

32

21

21

21

21

−≥+≥−≥+≥+

yy

yy

yy

yy

0rr ≥y .

Die duale Aufgabe ist damit grafisch lösbar und hat die optimale Lösung T

opty

=3

2|

3

5r mit dem

optimalen Zielfunktionswert 10, =optdz . Mittels der Komplementaritätsbedingungen ( )cyAx TT rrr −

- 92 -

0= und 0)( =− bxAyTrrr

erhält man dann als optimale Lösung für das Originalproblem

=optxr T)0|1|0|3( mit dem optimalen Zielfunktionswert 10, =optpz .

Zur Feststellung der Lösbarkeit einer LOA kann die Dualität ebenfalls benutzt werden:

Folgende fünf Aussagen sind äquivalent.

(1) Die Aufgabe NFLOA ist lösbar.

(2) Die Aufgabe DNFLOA ist lösbar.

(3) Die Aufgaben NFLOA und DNFLOA haben beide gleichzeitig zulässige Lösungen,

d.h. die Mengen { }0,|rrrrr ≥== xbxAxB p und { }cyAyB T

drrr ≥= | sind beide nicht-

leer.

(4) Die Aufgabe NFLOA hat einen nichtleeren zulässigen Bereich und ihre Zielfunktion

ist über dem zulässigen Bereich nach oben beschränkt.

(5) Die Aufgabe DNFLOA hat einen nichtleeren zulässigen Bereich und ihre Zielfunktion

ist über dem zulässigen Bereich nach unten beschränkt.

Die optimalen Lösungen der dualen Aufgabe heißen Schattenpreise und stellen einen ideellen Wert

der Faktoren für die zu lösende Aufgabe dar.

Oft ist es also günstiger, die duale LOA zu lösen und aus deren Lösung eine optimale Lösung der pri-

malen LOA zu bestimmen. Das soll am folgenden Beispiel demonstriert werden.

Beispiel:

Primale Aufgabe: Duale Aufgabe:

!2 321 Minxxxz p →++=

8

102

122

321

321

321

≥++≥++≥++

xxx

xxx

xxx

0rr ≥x

!81012 321 Maxyxyyzd →++=

2

12

12

321

321

321

≤++≤++≤++

yyy

yyy

yyy

0rr ≥y

Anwendung des primalen Simplexalgorithmus auf die duale LOA:

12 10 8 0 0 0

BV Abr

1y 2y 3y 1u 2u 3u cr

Θr

1u 0 1 2 1 1 0 0 1 ←1

2u 0 2 1 1 0 1 0 1 1

3u 0 1 1 1 0 0 1 2 2

-12 -10 -8 0 0 0 0

- 93 -

3y 8 1 2 1 1 0 0 1 1

2u 0 1 -1 0 -1 1 0 0 ←0

3u 0 0 -1 0 -1 0 1 1 ---

-4↑ 6 0 8 0 0 8

3y 8 0 3 1 2 -1 0 1

1y 12 1 -1 0 -1 1 0 0

3u 0 0 -1 0 -1 0 1 1

0 2 0 4 4 0 8

Die eindeutige optimale Lösung dieser dualen Aufgabe lautet Topty )1|0|0(=r

. Eine optimale Lö-

sung der primalen Aufgabe lässt sich in der letzten Zeile ablesen Toptx )0|4|4(=r

. Zu bemerken ist

hier, dass die duale Lösung entartet ist, d.h. zu ihr gehören mehr als eine Basismatrix (deshalb wurde

die optimale Lösung nicht schon in der 2. Tabelle erkannt). Die Anwendung des Simplexalgorithmus

auf die primale Aufgabe hätte die Zwei-Phasen-Methode erfordert.

Mit Hilfe des noch zu beschreibenden dualen Simplexalgorithmus kann festgestellt werden, dass durch

Aufnahme von 2y in die Basis eine weitere Simplextabelle erstellt werden kann, die auch zu dieser

optimalen Lösung gehört:

12 10 8 0 0 0

BV Abr

1y 2y 3y 1u 2u 3u cr

Θr

3y 8 3 0 1 -1 2 0 1

2y 10 -1 1 0 1 -1 0 0

3u 0 -1 0 0 0 -1 1 1

2 0 0 2 6 0 8

Die entsprechende optimale Lösung der primalen Aufgabe lässt sich dann auch in der letzten Zeile

ablesen Toptx )0|6|2(=r

. Damit ist die Menge der optimalen Lösungen der primalen Aufgabe die

beschränkte Kante { }10|)0|6|2()1()0|4|4( ≤≤⋅−+⋅ ααα TT .

Der folgende duale Simplexalgorithmus wird die Aufgabe dadurch lösen, dass er auf die primale Auf-

gabe angewendet wird.

- 94 -

Es sei TNA xxx )|( *** rrr = mit bAxA

rr 1* −= und 0*rr =Nx eine Basislösung für die NFLOA. Wenn

die Optimalitätsindikatoren TTTA

T cAAc 01rrrr

≥−=∆ − sind, dann heißt sie dual zulässig.

Eine dual zulässige Basislösung ist im Allgemeinem nicht primal zulässig. Eine primal und

dual zulässige Basislösung ist dann optimal.

Die NFLOA ist nicht lösbar, weil ihr zulässiger Bereich leer ist, wenn für eine Basislösung

TNA xxx )|( *** rrr = mit bAxA

rr 1* −= und 0*rr =Nx eine negative Komponente 0*

0<ix existiert,

die zu Zeile i0 der Tabelle gehört, und ( ) 00

1 ≥−jiAA ist für alle j.

Die Umrechnung der Simplextabelle nach Auswahl einer Zeile i0 mit ( ) 00

1 <−ibA

r erfolgt

durch Division derselben durch ein Element ( )00

1jiAA− < 0 und Schaffung einer Einheitsspalte in

der Spalte j0. Dabei wird die Kellerzeile so umgerechnet: ( )

( )00

00

1

1

:ji

jijjj

AA

AA

−

−⋅∆−∆=∆ für

nj ,,1K= . Damit die entstehenden Optimalitätsindikatoren nicht negativ sind, muss die Spalte j0 mit

( ) ( ) jji

j

ji

j

AAAAδ:

000

0

11=

∆≥

∆−− für alle j mit ( ) jiAA

0

1− < 0

gewählt werden.

Dualer Simplexalgorithmus:

Gegeben: Eine lineare Optimierungsaufgabe in Normalform:

≥=

→=

0

!

rr

rr

rr

x

bxA

Maxxcz T

(NFLOA).

Gesucht: Eine optimale Lösung.

(1) Bestimme eine Basismatrix A mit =∆Tr TTTA cAAc 01

rrr ≥−− und stelle die Simplextabelle

auf.

(2) Wenn alle Komponenten von bAr

1− 0≥ sind, dann ist die vorliegende Basislösung optimal,

stopp. Sonst wähle ein 0i mit ( ) 00

1 <−ibA

r.

- 95 -

(3) Wenn ( ) 00

1 ≥−jiAA ist für alle j, dann ist die LOA nicht lösbar, da der zulässige Bereich B

leer ist. Sonst bestimme eine Spalte j0 unter Verwendung der Bedingung ( ) ≥∆

−00

0

1ji

j

AA

( ) jji

j

AAδ:

0

1=

∆− für alle j mit ( ) jiAA

0

1− < 0.

(4) Die Basisvariable zur Zeile i0 in der Simplextabelle verlässt die Basis, dafür wird 0j

x in die

Basis aufgenommen. Entsprechend wird die Simplextabelle umgerechnet: In den Spalten BV und

Acr

wird die Basisvariable in der i0-ten Zeile durch 0j

x und deren Zielfunktionskoeffizient durch 0j

c

ersetzt. Der Rest der Tabelle wird mit dem Algorithmus von Gauß-Jordan umgerechnet, wobei in der

Spalte j0 eine Einheitsspalte mit einer 1 in der Zeile i0 geschaffen wird.

Fortsetzung des Beispiels: (Anwendung des dualen Simplexalgorithmus)

-1 -1 -2 0 0 0

BV Acr

1x 2x 3x 1u 2u 3u br

1u 0 -1 -2 -1 1 0 0 -12

2u 0 -2 -1 -1 0 1 0 -10

3u 0 -1 -1 -1 0 0 1 ←− 8

j∆ 1 1 2 0 0 0 0

jδ -1↑ -1 -2 --- --- ---

1u 0 0 -1 0 1 0 -1 ←

− 4

2u 0 0 1 1 0 1 -2 6

1x -1 1 1 1 0 0 -1 8

j∆ 0 0 1 0 0 1 -8

jδ --- 0↑ --- --- --- -1

2x -1 0 1 0 -1 0 1 4

2u 0 0 0 1 1 1 -3 2

1x -1 1 0 1 1 0 -2 4

j∆ 0 0 1 0 0 1 -8

- 96 -

Auch hier ist jetzt eine optimale Lösung Toptx )0|4|4(=r

berechnet worden. Da der Optimalitätsin-

dikator zur NBV 1u Null ist, kann 1u in die Basis aufgenommen werden, wodurch sich wieder eine

andere optimale Lösung Toptx )0|6|2(=r

ergibt (keine primale Entartung). Zu beachten ist hier,

dass die Nebenbedingungen mit (-1) multipliziert wurden, damit die Schlupfvariablen gleich als Start-

lösung dienen können. Des Weiteren wurde die ursprünglich zu minimierende Zielfunktion mit (-1)

multipliziert, um so ein Maximierungsproblem zu schaffen. Der optimale (minimale) Zielfunktions-

wert des Originalproblems ist dann 8=optz .

4.7. Abschlussbemerkungen

In dieser Lehrveranstaltung konnte aus Zeitgründen nicht auf weitere interessante Aufgaben-

stellungen der linearen Optimierung eingegangen werden. Dazu zählen u.a. einparametrige

lineare Optimierungsprobleme, Fragen der Vektoroptimierung, polynomiale Verfahren zur

Lösung von LOA (Ellipsoidmethode, Innere-Punkte-Methode), spezielle Verfahren der

Transportoptimierung, Optimierung auf Graphen, Modelle der Logistik (Touren-, Standort-

probleme), ganzzahlige LOA und die mathematische Spieltheorie.

Aus der Sicht der Komplexitätstheorie ist die lineare Optimierung ein einfaches Problem, da

es sich z.B. mit einigen Innere-Punkte-Verfahren von Karmarkar oder der Ellipsoidmethode

von Khachijan in polynomialer Zeit lösen lässt. Aus praktischer Sicht ist jedoch oft das

Simplexverfahren schneller, obwohl es theoretisch exponentielle Laufzeit besitzt. Neben dem

originalen Problem löst es immer auch das sogenannte duale Problem mit, was u.a. in mehre-

ren Verfahren zur Lösung ganzzahliger linearer Probleme ausgenutzt wird. Es ist bis heute

nicht bekannt, ob es einen streng polynomialen Algorithmus zur Lösung allgemeiner linearer

Probleme gibt, also einen Algorithmus, dessen Laufzeit nicht von der Größe der auftretenden

Zahlen abhängt.