Es seien
und
gegeben. Dann hat ein lineares Optimierungsproblem (kurz: LOP) allgemein die Form

Ein Problem vom Typ
mit zwei Variablen lässt sich auf geometrische Weise lösen.
(i) Man betrachte das Problem

Wie man sich deutlich macht, wird für dieses Problem der kleinste Zielfunktionswert hinsichtlich des zulässigen Gebietes im Punkt
angenommen und beträgt dieser Wert 0.5.
(ii) Ändert man das Beispiel aus (i) so ab, dass man darin die Zielfunktion mit
multipliziert, dann gilt:

Für dieses Beispiel existieren also zulässige Punkte mit beliebig kleinen Zielfunktionswerten.
Beispiel 4.1 macht deutlich, dass nur eine der folgenden Situationen eintreten kann, wobei
der zulässige Bereich von
ist (mit Satz 4.13 wird dies auch noch bewiesen):
. Dann ist
.
. Dann hat man entweder:
- (a) es existiert ein
mit
(dies ist z. B. der Fall, wenn
beschränkt ist) oder
- (b) es gibt eine Folge
in
mit
, d. h. es ist
.
Man sagt nun weiter, dass ein LOP in Normalform vorliegt, wenn es die Gestalt

bzw. mit
und
die folgende Gestalt hat:

Den zulässigen Bereich von
bezeichnen wir mit
- (4.1)

Bemerkenswert ist nun, dass sich jedes LOP durch die folgenden Operationen in ein LOP in Normalform überführen lässt:
- Man streiche die Konstante
in der Zielfunktion. (Sie ist dann nach Lösung des Problems zu dem optimalen Zielfunktionswert hinzu zu addieren.)
- Ein Maximierungsproblem mit Zielfunktion
schreibe man als Minimierungsproblem mit Zielfunktion
. (Der optimale Zielfunktionswert des Minimierungsproblems ist dann mit
zu multiplizieren.)
- „
“-Restriktionen forme man durch Multiplikation mit
zu „
“-Restriktionen um.
- „
“-Restriktionen schreibe man mittels Hinzufügung von Schlupfvariablen
als „
“-Restriktionen.
- Jede vorzeichenfreie Variable
ersetze man durch
mit
und
.
Offenbar ist dann das Ausgangsproblem mit dem zugehörigen Problem in Normalform in dem Sinne äquivalent, dass die optimalen Zielfunktionswerte beider Probleme identisch sind und dass das eine der beiden Probleme genau dann eine Lösung besitzt, wenn das andere eine hat, wobei sich eine Lösung des einen Problems aus einer Lösung des anderen ableiten lässt.
Gegeben sei das Problem

Mit
geht dieses Problem über in das Problem

Mit
,

bekommt letzteres Problem die Gestalt von
mit
und
.
Wir betrachten nun das lineare Optimierungsproblem
in Normalform und seinen zulässigen Bereich
(siehe (4.1)). Üblicherweise setzt man in diesem Zusammenhang
- (4.2)

voraus und damit insbesondere
. Dies ist eine sinnvolle Arbeitsannahme. Denn hat man
, dann besitzt das lineare Gleichungssystem
entweder keine Lösung oder enthält dieses
überflüssige Zeilen, die gestrichen werden können. Ist andererseits
, also das System
überbestimmt, so ist es ebenfalls entweder unlösbar oder können in diesem Fall mindestens
Gleichungen aus ihm entfernt werden. Demzufolge kann man, wenn das System
überhaupt eine Lösung besitzt, nach Beseitigung aller überflüssigen Gleichungen und nach Benennung der Anzahl der verbleibenden Gleichungen in
zu einem Gleichungssystem gelangen, dessen Matrix die Bedingung (4.2) erfüllt.
Sei nun
. Dann existieren
Spalten von
, die linear unabhängig sind. Weiter hat man im Hinblick auf die Lösbarkeit des Systems
bekanntlich folgendes Resultat, wobei
- (4.3)

den Nullraum von
bezeichnet.
- Sei
und
. Dann gilt:
- (i) Ist
, dann hat das homogene System
die Lösungsmenge
. Ist
, so besitzt es
linear unabhängige Lösungen
und ist seine Lösungsmenge
gleich dem von
aufgespannten
-dimensionalen Teilraum des
.
- (ii) Das inhomogene lineare Gleichungssystem
besitzt eine Lösung
und seine Lösungsmenge ist der affine Teilraum
.
Ist insbesondere
, so hat also das System
unter der Rangbedingung (4.2) eine eindeutige Lösung
. Im Fall
ist dann
und folglich
Lösung von
. Ist dagegen
, so folgt
. Interessant ist also vor allem der Fall
.
In diesem Abschnitt stellen wir Untersuchungen zu dem zulässigen Bereich
- (4.4)

von Problem
an, wobei wie zuvor
und
seien. Die Spalten von
bezeichnen wir mit
, so dass
folgt. (Die Rangbedingung für
wird hier nicht benötigt.)
- Eine (konvexe) Menge
, die sich mit
und
in der Form

- darstellen lässt, heißt Polyeder. Ein beschränktes Polyeder heißt Polytop.
Insbesondere ist also die Menge
ein Polyeder. Der Simplexalgorithmus zur Lösung linearer Optimierungsprobleme, den wir später diskutieren wollen, erzeugt Iterierte, die auf dem Rand von
liegen. Deshalb wollen wir im folgenden Eigenschaften des Randes untersuchen.
Auf folgende Weise kann man Ecken von
charakterisieren.
- Ein Punkt
einer konvexen Menge
heißt Ecke oder Extrempunkt von
, wenn es keine Punkte
mit
und kein
gibt, so dass
ist.
Für
sei nun
die Indexmenge
- (4.5)

- Sei
. Dann gilt:
- (i)
ist eine Ecke von
sind linear unabhängig.
- (ii)
sind linear abhängig
es existiert ein
mit
.
Sei
. Dann ist insbesondere
.
Sind die
linear abhängig, dann existieren
, welche nicht alle identisch Null sind, so dass gilt:

Seien
und
definiert durch

Wegen
folgt
und
sowie
. Für
und
mit

hat man daher, wie man leicht verifiziert,
.
(i) Sei nun
eine Ecke von
. Dann müssen die
linear unabhängig sein, da wir anderenfalls für
die Beziehung
hätten.
Seien jetzt umgekehrt die
linear unabhängig und sei

mit
und
gegeben. Dann folgt zunächst wegen
und
, dass
für
ist. Also hat man

Wegen der linearen Unabhängigkeit der
muss
sein, so dass insgesamt
folgt. Also ist
eine Ecke von
.
(ii) Es ist
und wegen
, d. h.
, daher
oder/und
.
q.e.d.
(i) Falls
gilt, ist 0 Ecke von
. (Denn der Nullvektor lässt sich nicht als „echte Konvexkombination“ zweier Vektoren
darstellen.)
(ii) Gilt
, so können gegebenenfalls dem Nullvektor und jeder anderen Ecke
von
eine Anzahl von
linear unabhängigen Spalten
zugeordnet werden, wobei
eine Indexmenge ist mit
und
. (Denn falls
ist, kann man die nach Lemma 4.6 linear unabhängigen Vektoren
nach einem Satz aus der linearen Algebra durch
weitere Spalten
zu
linear unabhängigen Vektoren ergänzen.)
Für die lineare Optimierung grundlegend ist der folgende Satz.
- Sei
das Polyeder in (4.4). Dann gilt:
- (i) Ist
, so besitzt
mindestens eine Ecke.
- (ii) Die Anzahl der Ecken von
ist höchstens

(i) Sei
und
ein Punkt mit
- (4.6)

Ist
, so ist
und folglich
Ecke von
. Also sei
. Auch dann muss
eine Ecke von
sein. Denn anderenfalls wären nach Aussage (i) von Lemma 4.6 die
linear abhängig und gäbe es dann nach Lemma 4.6 (ii) im Widerspruch zu (4.6) ein
mit
.
(ii) Nach Lemma 4.6 ist
genau dann Ecke von
, wenn
linear unabhängig sind. Wegen
hat man
. Nun ergänze man
durch beliebige weitere
zu insgesamt
Spalten auf (auch gegebenenfalls für
). Es gibt maximal
Möglichkeiten,
aus
Spalten auszuwählen (die nicht notwendig zu einer Ecke gehören müssen).
q.e.d.
Man kann sich geometrisch klarmachen, dass jeder Punkt eines beschränkten Polyeders, eines Polytops, als Konvexkombination seiner endlich vielen Ecken dargestellt werden kann. Für das Polyeder
kann man zeigen:
- Sei
und bezeichne
die nichtleere Menge der Ecken von
. Dann lässt sich jeder Punkt
mit einer Lösung
von
in der Form
- (4.7)

- darstellen. Ist
beschränkt, so ist insbesondere
.
Für
sei
wie in (4.5) definiert. Der Beweis erfolgt per vollständiger Induktion nach der Anzahl
positiver Komponenten von
.
Ist
, so ist
. Da 0 Ecke von
ist, folgt (4.7) trivialerweise. Wir nehmen nun an, dass sich jedes
mit
in der Form (4.7) darstellen lässt. Es sei weiter
derart, dass
gilt und
selbst keine Ecke ist. (Anderenfalls wären wir fertig.) Nach Lemma 4.6 sind dann
linear abhängig, so dass ein
existiert mit
und
. Wir nehmen nun zunächst an, dass
positive und negative Komponenten besitzt.
Wir definieren positive Zahlen


und damit

Nach Konstruktion hat man
mit
für
und gilt
mit
.
Nach Induktionsvoraussetzung besitzen
und
also Darstellungen

der Form (4.7). Mit

folgt die gewünschte Darstellung (4.7) für
.
Nun sei
. Wie oben definiere man
und
und wende man auf
die Induktionsvoraussetzung an. Die Darstellung (4.7) von
folgt dann aus
. Für
verfahre man entsprechend. Schließlich ist für jedes
und
mit
auch
für alle
, so dass das System
im Fall, dass
beschränkt ist, keine Lösung
mit
haben kann.
q.e.d.
4.4 Das Innere des zulässigen Bereichs
[Bearbeiten]
Der später im Kurs vorgestellte Simplexalgorithmus erzeugt in seiner Phase II Iterierte, welche Ecken des Polyeders
darstellen. Innere-Punkte-Verfahren der linearen Optimierung bewegen sich dagegen im sog. Inneren von
. Das relative Innere der zulässigen Menge bezüglich der Fläche
ist durch das straffierte Dreieck ohne den Rand gegeben.
Allgemein ist das relative Innere
von
bezüglich der linearen Mannigfaltigkeit
definiert durch

In diesem Zusammenhang betrachten wir die Menge

Offenbar gilt
- (4.8)

wobei
und
leer sein können. Besteht die Lösungsmenge des Systems
nur aus einem Punkt
mit
, so hat man insbesondere
und somit
. In einer anderen Situation ist jedoch
möglich, wie folgendes Beispiel zeigt.
Es seien
und

Dann folgt:

In dem durch dieses Beispiel beschriebenen Problem existiert eine Variable, die für alle
identisch Null ist. In Verallgemeinerung von Beispiel 4.10 hat man:
- Sei
. Dann sind folgende Bedingungen äquivalent:
- (i)
.
- (ii) Es gibt ein
, so dass
für alle
gilt.
Die Implikation „(ii)
(i)“ ist trivial. Gilt andererseits (ii) nicht, so existiert zu jedem Index
ein
mit
. Wegen
und der Konvexität von
folgt
und somit
.
q.e.d.
Ist jedoch
(und damit trivialerweise auch
), so hat man:
- Ist
, so gilt
.
Sei
. Dann existiert ein
, so dass für jedes
mit
und
auch
folgt. Wäre nun
, dann könnte man ein
wählen und wegen
und
gäbe es ein
, so dass
gelten würde. Weiter wäre
für mindestens ein
und wegen
außerdem
. Mit
folgte daher
, d. h.
.
Andererseits hätte man aber
und
, was wegen
auch
implizierte. Also gilt
und folglich
. Mit (4.8) folgt die Behauptung.
q.e.d.
Im Zusammenhang mit Verfahren, die Iterierte im relativen Inneren
von
erzeugen, ist trivialerweise
anzunehmen und ist es nach obigen Ergebnissen darüber hinaus sinnvoll,
zu fordern. Denn ist
, dann kann man alle Variablen
, die für alle
identisch Null sind, aus dem Problem entfernen (Lemma 4.11) und erfüllt das so verkleinerte Problem nach Umbenennung der erhaltenen Variablenzahl in
die Bedingung
. (Wie man solche Variablen entdeckt, findet man z. B. in Abschnitt 6.7.2 von [Ree01].) Die Forderung
garantiert überdies, dass man das relative Innere
von
durch die einfacher definierte Menge
beschreiben kann (Lemma 4.12). Die Menge
wird in diesem Zusammenhang kurz als das Innere von
und ein Punkt
als innerer Punkt von
bezeichnet.
Wir beweisen den folgenden Existenzsatz.
- Sei
der zulässige Bereich eines Minimierungsproblems der Form
. Ist
und
, so besitzt das Problem
eine Lösung.
Aufgrund der Äquivalenz von Problem
mit einem Problem der Form
können wir von
ausgehen. Seien daher
die nach Satz 4.8 nichtleere Menge der Ecken von
und
beliebig. Nach Satz 4.9 lässt sich dann
in der Form

darstellen. Es muss
sein, da
im Widerspruch zur Voraussetzung

implizieren würde. Demnach hat man
- (4.9)

q.e.d.
Für jedes Problem der Form
kann man darüber hinaus Folgendes aussagen.
- Besitzt das LOP in Normalform
eine Lösung, so existiert auch eine Ecke von
, welche Lösung von
ist.
Wenn
eine Lösung besitzt, sind die Voraussetzungen von Satz 4.13 erfüllt, so dass (4.9) folgt. Demnach löst eine Ecke
mit
das Problem
.
q.e.d.
Wir gehen in diesem Abschnitt zunächst von einem LOP in Normalform aus und leiten für dieses und das dazu als „duales“ bezeichnete Problem Ergebnisse her. Im Unterabschnitt 4.6.4 behandeln wir dann allgemeine lineare Optimierungsprobleme.
Seien
und
. Wir betrachten das LOP in Normalform

mit zulässigem Bereich

Nach Beispiel 3.16 (1) ist
genau dann eine Lösung des Problems
, wenn es Vektoren
und
gibt, so dass
das folgende System löst

Die Lösbarkeit des Systems
ist auch notwendig und hinreichend dafür, dass das Problem

mit zulässigem Bereich

eine Lösung
besitzt. Denn zu
gehören mit
die KKT-Bedingungen

Führt man den Schlupfvariablenvektor
für
ein, so sieht man, dass letzteres System genau dann eine Lösung besitzt, wenn
lösbar ist.
Wir hätten
auch gleich anstelle von
das mit
äquivalente Problem

mit zulässigem Bereich

gegenüberstellen können, für das natürlich ebenfalls die Bedingungen
notwendige und hinreichende Optimalitätsbedingungen sind. Man bezeichnet
in diesem Zusammenhang als das primale und
bzw.
als das dazu duale Problem. Wir werden uns hier der Einheitlichkeit halber fast ausschließlich auf
beziehen, auch in Fällen, in denen der Vektor
nicht explizit benötigt wird und sich daher die Verwendung von
anbieten würde.
Die ersten beiden Zeilen von
sind äquivalent mit der Forderung, dass
primal und
dual zulässig ist. Die dritte Bedingung
in
ist gerade die Komplementaritätsbedingung. In diesem Zusammenhang stellen wir noch fest, dass für ein zulässiges Punktepaar
und
gilt:
- (4.10)

Abschließend beweisen wir:
- Das duale Problem zu
ist äquivalent mit
.
Wir schreiben
in ein äquivalentes Problem der Form
um, um dann daraus das dazu duale Problem ableiten zu können. Mit
und
ist
äquivalent mit

Das dazu duale Problem lautet

Mit
kann dies offenbar wie ein Problem vom Typ
geschrieben werden.
q.e.d
Aus den Ergebnissen des vorangehenden Unterabschnitts gehen unmittelbar die als schwacher und starker Dualitätssatz bekannten Sätze hervor. So liefert (4.10) die Aussage des schwachen Dualitätssatzes.
- Für
und
gilt
- (4.11)

Weiter bekommt man:
- (i) Es gilt:
ist lösbar
ist lösbar
ist lösbar.
- (ii)
und
sind genau dann Lösungen von
und
, wenn
das System
löst.
Aussage (i) ergibt sich aus Abschnitt 4.6.1. Seien nun
und
Lösungen von
bzw.
. Dann ist zu zeigen, dass dieses Punktepaar eine Lösung von
bildet.
Gemäß (i) gibt es in diesem Fall zu
eine Lösung
von
, so dass
das System
läst und somit
gilt. Nach (4.10) hat man also
- (4.12)

Dies impliziert
und somit nach (4.10)
. Also folgt, dass
eine Lösung von
ist. Die Umkehrung von Aussage von (ii) kann man unmittelbar aus Abschnitt 4.6.1 schließen.
q.e.d.
Bei einem Satz, der als Aussage die Identität (4.12) beinhaltet, spricht man von einem starken Dualitätssatz. Aus historischen Gründen geben wir als nächstes einen solchen Satz an. Bis auf Aussage (i) ist dieser in Satz 4.17 enthalten.
- (i) Gilt
und
, so besitzen beide Probleme
und
eine Lösung.
- (ii)
und
sind genau dann Lösungen von
und
, wenn
und
(bzw.
) gilt.
(i) Man wähle ein
. Dann folgt aus Satz 4.16

und damit aus Satz 4.13, dass
eine Lösung besitzt. Für
kann man analog schließen. Aussage (ii) ist eine Folge der Sätze 4.16 und 4.17.
q.e.d.
Aus den Dualitätssätzen leiten wir weitere Aussagen ab. Die nachfolgende wird uns später ein Abbruchkriterium für Algorithmen liefern.
Seien
und
mit
- (4.13)

für ein
gegeben. Dann besitzen
und
eine Lösung und gilt


Nach Satz 4.18 existieren Lösungen
und
von
und
. Für solche Punkte liefern der schwache und der starke Dualitätssatz mit (4.13)

und

q.e.d.
Für ein primal und dual zulässiges Punktepaar
und
bezeichnet man die nichtnegative Zahl
als Dualitätslücke. Ist diese für ein
kleiner oder gleich
, wie in (4.13) gefordert, so sprechen wir aufgrund von Korollar 4.19 von
-optimalen Lösungen von
und
.
Eine weitere wichtige Folgerung aus dem Vorangegangenen ist die folgende.
- (i) Es sei
. Dann gilt:

- (ii) Es sei
. Dann gilt:

(i) Sei
. Gäbe es ein
, so folgte aus Satz 4.16 im Widerspruch zur Annahme, dass
für alle
ist. Ist andererseits
, so ist nach Satz 4.13 die Lösungsmenge von
und daher nach Satz 4.18 auch die von
nichtleer. Also ist insbesondere
.
Aussage (ii) folgt unter Verwendung von (1.2) entsprechend.
q.e.d.
In Abschnitt 4.6.1 haben wir festgestellt, dass ein Punktepaar
und
genau dann optimal für
und
ist, wenn es primal bzw. dual zulässig ist und der Komplementaritätsbedingung
genügt, was gleichbedeutend damit ist, dass die zugehörige Dualitätslücke den Wert Null hat. In diesem Abschnitt beweisen wir, dass es immer ein Lösungspaar
und
von
und
gibt, für das die strikte Komplementaritätsbedingung erfüllt ist, d. h. für das gilt:
- entweder
oder
.
Letztere Eigenschaft lässt sich wegen
und
äquivalent ausdrücken durch
- (4.14)

- Besitzen die Probleme
und
eine Lösung, so existieren auch Lösungen
und
von
und
, für die (4.14) gilt.
Wir wollen zeigen, dass zu jedem
ein Lösungspaar
und
der Probleme
und
mit
existiert. Denn dann folgt für

wegen der Konvexität der Lösungsmengen von
und
(siehe Satz 2.37), dass
und
die Probleme
und
lösen und somit (s. Satz 4.18)
ist und dass gilt:

Sei also
fest gewählt. Existiert eine Lösung
von
mit
, so ist für jede Lösung
von
wegen
trivialerweise
. Daher gelte
- (4.15)
für jede Lösung
von
.
Wir betrachten nun das Problem

und das zugehörige duale Problem

wobei
der optimale Zielfunktionswert von
und
ist. Jeder zulässige Punkt
von
genügt
und wegen
insbesondere
. Also ist
Lösung von
und notwendig
. Weiter folgt damit aus (4.15), dass der Zielfunktionswert von
für jeden zulässigen Punkt von
identisch Null ist. Nach Satz 4.18 besitzt somit
eine Lösung
mit optimalem Zielfunktionswert Null. Für diese gilt
- (4.16)

und
- (4.17)

Wegen
muss insbesondere
sein.
Sei zunächst
. Für jede Lösung
von
gilt
- (4.18)

was zu (4.17) addiert,

liefert. Wegen
folgt

Da (4.16)

impliziert, muss
eine Lösung von
sein. Ferner ist

so dass man in diesem Fall
für jede Lösung
von
schließt.
Nun sei
. Dann folgt aus (4.16) und (4.17) für

so dass man wegen
folgert, dass
Lösung von
ist. Schließlich ist
und damit wiederum
für jede Lösung
von
.
q.e.d.
In Verbindung mit den Ergebnissen von Abschnitt 4.6.1 können wir also im Hinblick auf das System

schließen:
- Es gilt:
ist lösbar
ist lösbar
ist lösbar.
Wir schließen mit einem Beispiel ab.
Gegeben sei das Problem

mit zugehörigem dualen Problem

Für jedes
ist
mit

eine Lösung des Systems
, welches hier lautet:

Gemäß Satz 4.17 ist damit
eine Lösung von
und
eine von
. Man sieht ferner, dass
genau dann die Bedingung
erfüllt, d. h. genau dann eine Lösung von
ist, wenn
ist.
In Abschnitt 4.1 haben wir festgestellt, dass sich jedes LOP äquivalent in ein LOP in Normalform umschreiben lässt. Demnach kann jedem (primalen) LOP mittels der Ergebnisse aus Abschnitt 4.6.1 ein duales LOP zugeordnet werden. Wir führen dies zunächst anhand des Problems

vor. Dieses ist äquivalent mit dem Problem

Zu letzterem Problem gehört nach Abschnitt 4.6.1 das duale Problem

Setzt man
, so bekommt dieses Problem die einfachere Gestalt

Mit den Schlupfvariablenvektoren

für
und
erhalten wir für Punkte
und
, welche zulässig für
und
sind, die schwache Dualitätsaussage

und die Komplementaritätsbedingung

Ähnlich kann man auch für ein allgemeines Minimierungsproblem
mit
„
“-Restriktionen,
Gleichheitsrestriktionen,
nichtnegativen und
freien Variablen ein duales Problem
aufstellen, wobei man sinnvollerweise
und
annimmt. („
“-Restriktionen seien bereits als „
“-Restriktionen beschrieben worden.) Spaltet man die in
und
vorkommenden Größen wie folgt auf:


so gelangt man zu folgendem Paar von Problemen

Offenbar gehen „
“-Restriktionen im primalen Problem in „
“-Variable im dualen Problem über, Gleichheitsrestriktionen in freie Variable, „
“-Variable in „
“-Restriktionen und freie Variable in Gleichheitsrestriktionen.
Die Paare
und
bzw.
und
sind Spezialfälle von
und
. Da die Probleme
und
auf äquivalente Probleme des Typs
und
zurückgeführt werden können, sieht man leicht ein, dass die Aussagen der Sätze 4.15, 4.16 und 4.18 entsprechend auch für sie gelten. Sind
und
die zulässigen Gebiete von
und
, so hat man daher zusammengefasst:
- (i) Das duale Problem zu
ist äquivalent zu
.
- (ii) Für
und
gilt
.
- (iii) Gilt
und
, so haben die Probleme
und
Lösungen.
- (iv)
besitzt genau dann eine Lösung, wenn
eine Lösung hat.
- (v)
und
lösen
und
genau dann, wenn
gilt und
ist.
In der Praxis ist es manchmal effizienter, statt des gegebenen LOPs das dazu duale Problem zu lösen (sofern man nicht ein primal-duales Verfahren verwendet). Ein Beispiel, wo man das tun sollte, ist das im folgenden beschriebene diskrete lineare Tschebyscheff-Problem.
Gegeben seien
Punkte
und dazu gehörige Werte
, welche z. B. Messwerte oder Funktionswerte
einer bekannten, in den
definierten Funktion
sein können. Weiter seien
in den
definierte Ansatzfunktionen
gegeben (z.B. die Monome
. Ziel ist es, die
durch eine Linearkombination der
(im Fall der Monome also durch ein Polynom vom Grad
) in den Punkten
bezüglich der Maximumnorm mit kleinst möglichem Fehler zu approximieren, also folgendes Problem zu lösen:

Wir wollen
als ein LOP schreiben. Dazu führen wir den zusätzlichen Parameter

ein. Fassen wir
als zusätzliche Komponente des Variablenvektors auf, so erhalten wir das zu
äquivalente Problem

mit Variablenvektor
. Der optimale Zielfunktionswert
gibt offenbar gerade den kleinst möglichen Approximationsfehler an. (Analog kann man übrigens jedes Optimierungsproblem in eines mit linearer Zielfunktion überführen.)
Die Ungleichungsrestriktion in dem letzten Problem lässt sich äquivalent durch die
Restriktionen
- (4.19)

ausdrücken, so dass wir durch Auflösung der Beträge zu folgendem äquivalenten linearen Optimierungsproblem gelangen:

Letzteres Problem ist ein lineares Optimierungsproblem. Mit den Definitionen

und den Daten
sowie

bekommt es die Gestalt

Wie sich aus der Herleitung ergibt, könnte man zu
noch die Bedingung
- (4.20)

hinzufügen. Man muss dies aber nicht tun, da sie wegen (4.19) für zulässige Punkte automatisch erfüllt ist.
Wegen (4.20) ist insbesondere
für alle für
zulässigen Punkte
. Die Menge der für
zulässigen Punkte ist nichtleer, da man nach beliebiger Wahl von
die Komponente
so wählen kann, dass alle Ungleichungen in
erfüllt sind. Nach Satz 4.13 besitzt daher
und damit auch das Ausgangsproblem
eine Lösung.
Zum Erreichen der Normalform, von der viele Algorithmen der linearen Optimierung ausgehen, müsste man nach Hinzufügung der Ungleichung (4.20)
Schlupfvariable und
zusätzliche Variable für die
vorzeichenfreien Variablen einführen. Das zu
gehörende Problem in Normalform hätte also
Gleichungsrestriktionen und
Variable.
Das zu
duale Problem lautet

Dieses LOP hat offenbar bereits die Normalform und
Gleichungsrestriktionen und
Variable.
(Hätten wir die Bedingung (4.20) in
explizit mitberücksichtigt, so hätte uns dies eine unerwünschte „
“-Restriktion im dualen Problem eingebracht.)
In der Praxis ist die Punktzahl
im allgemeinen sehr viel größer als die Variablenzahl
. Realistisch ist eine Beziehung
, wobei
mindestens gleich 10 und häufig sehr viel größer als 10 ist. Nehmen wir z. B.
an, so stehen also
Gleichungsrestriktionen und
Variable
des primalen Problems
Gleichungsrestriktionen und
Variablen
des dualen Problems