Benutzer:Stepri2005/Kurs:Optimierung/Grundlagen der linearen Optimierung

4.1 Das lineare Optimierungsproblem in Normalform

Bearbeiten

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.

Beispiel 4.1

Bearbeiten

(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):

  1.  . Dann ist  .
  2.  . 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.

Beispiel 4.2

Bearbeiten

Gegeben sei das Problem

 

Mit   geht dieses Problem über in das Problem

 

Mit  ,

 

bekommt letzteres Problem die Gestalt von   mit   und  .


4.2 Die Rangbedingung

Bearbeiten

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.

Satz 4.3

Bearbeiten
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  .

4.3 Der Rand des zulässigen Bereichs

Bearbeiten

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.)

Definition 4.4

Bearbeiten
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.

Definition 4.5

Bearbeiten
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)  

Lemma 4.6

Bearbeiten
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.

Bemerkung 4.7

Bearbeiten

(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.

Satz 4.8

Bearbeiten
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:

Satz 4.9

Bearbeiten
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.

Beispiel 4.10

Bearbeiten

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:

Lemma 4.11

Bearbeiten
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:

Lemma 4.12

Bearbeiten
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.

4.5 Existenz von Lösungen

Bearbeiten

Wir beweisen den folgenden Existenzsatz.

Satz 4.13

Bearbeiten
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.

Satz 4.14

Bearbeiten
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.

4.6 Dualitätstheorie

Bearbeiten

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.

4.6.1 Das duale Problem zu einem Problem in Normalform

Bearbeiten

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:

Satz 4.15

Bearbeiten
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

4.6.2 Dualitätssätze

Bearbeiten

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.

Satz 4.16 (Schwacher Dualitätssatz)

Bearbeiten
Für   und   gilt
(4.11)  

Weiter bekommt man:

Satz 4.17

Bearbeiten
(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.

Satz 4.18 (Starker Dualitätssatz)

Bearbeiten
(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.

Korollar 4.19

Bearbeiten

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.

Korollar 4.20

Bearbeiten
(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.

4.6.3 Strikte Komplementarität

Bearbeiten

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)  

Satz 4.21

Bearbeiten
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:

Korollar 4.22

Bearbeiten
Es gilt:
  ist lösbar   ist lösbar   ist lösbar.

Wir schließen mit einem Beispiel ab.

Beispiel 4.23

Bearbeiten

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.


4.6.4 Das duale Problem zu einem Problem in beliebiger Form

Bearbeiten

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:

Korollar 4.24

Bearbeiten
(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.

4.6.5 Ein Beispiel

Bearbeiten

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   gegenüber.

Die Anzahl der Iterationen, die z. B. der Simplexalgorithmus benötigt, wird im Normalfall vornehmlich durch die Anzahl der Gleichungsrestriktionen bestimmt. (Dantzig, der 1947 den im nächsten Kapitel beschriebenen Simplexalgorithmus zur Lösung linearer Optimierungsprobleme entwickelt hatte, hat aufgrund von langjährigen Erfahrungen die Vermutung geäußert, dass dieser im Mittel   Iterationen für ein LOP in Normalform mit   benötigt.) Bei Verwendung dieses Verfahrens ist es daher üblicherweise sehr viel effizienter, anstelle von   das Problem   zu lösen. Löst man   mit dem Simplexalgorithmus, so liefert einem dieser (wie die meisten Verfahren zur Lösung linearer Optimierungsprobleme) gleichzeitig eine Lösung des dazu dualen Problems   mit, an der man ja hauptsächlich interessiert ist (s. Abschnitt 5.5).