Systeme von linearen Ungleichungen

Zu meinem Eintritt in den Ruhestand haben mir die Buben und Mädchen der Klasse 8b, die ich bis dahin in Mathematik unterrichtet hatte, ein Geschenk gemacht, das mir seither viel Freude bereitet hat. Sie hatten einen Kalender gefertigt, und zu jedem zweiten Monat gab es ein mathematisches Rätsel. Die September – Aufgabe führte auf ein System von linearen Ungleichungen.

Systeme von linearen Ungleichungen kann man in ähnlicher Weise angehen wie Systeme von linearen Gleichungen, z.B. nach dem folgenden Muster, das an das Gauß-Verfahren zur Lösung linearer Gleichungssysteme erinnert.

Seien A, B, C, D Terme und sei k eine positive Zahl. Es gelte das System (1),(2):

(1) A ≥ B, (2) C ≥ D => k•A ≥ k•B => (1’) A ≥ B , (2’) k•A + C ≥ k•B + D

Wie wir noch sehen werden, ist diese Umformung zwar notwendig, aber nicht äquivalent. Will heißen: Lösungen des Systems (1),(2) sind auch Lösungen des Systems (1’),(2’). Aber (1’),(2’) können darüber hinaus Lösungen enthalten, welche das ursprüngliche System (1),(2) nicht lösen. Und so geht man wie folgt vor. Man formt nach dem beschriebenen Muster um mit dem Ziel, möglichst enge Intervalle zu finden, in dem die Lösungen des ursprünglichen Systems liegen müssen. Dann folgt die Probe: Die „Lösungsvorschläge“ werden in das ursprüngliche System eingesetzt, um die echten Lösungen zu finden.

Mit a, b und c seien die Maßzahlen der in cm gemessenen Seitenlängen eines Dreiecks bezeichnet. Über sie ist folgendes bekannt.

Die drei Zahlen sind ganze Zahlen.
Die Summe aus a und c ist um 13 größer als b.
Das Doppelte von a ist mindestens so groß wie b.
Das Dreifache von b ist nicht größer als das Doppelte von c.
Addiere ich zum Dreifachen von a das Doppelte von c, so erhalte ich mindestens 56.

Lassen sich aus diesen Angaben die Zahlen a, b und c bestimmen?

Übersetzen wir die vier Bedingungen in Gleichungen bzw. Ungleichungen
(1) a +c = b + 13    (2) 2a ≥ b    (3) 3b ≤ 2c    (4) 3a + 2c ≥ 56

Wir ordnen, indem wir die Variablen auf eine Seite bringen und zugleich die Ungleichheitszeichen alle "in eine Richtung" zeigen lassen.

In einem ersten Schritt verwenden wir die erste Gleichung, um die Variable a in den folgenden Ungleichungen zu eliminieren. Dazu multipliziert man die erste mit –2 und addiert zur zweiten, danach multipliziert man die erste mit –3 und addiert zur vierten; die dritte bleibt unverändert.

(2’) wird mit 3 multipliziert und zu (3’) addiert, (3’) und (4’) werden addiert. Wir erhalten:

(3’’) bedeutet c ≤ 78/4 = 19,5 ; zusammen mit (4’’) lässt sich c in ein Intervall "einsperren":
17 ≤ c ≤ 19,5.

Lösungsmengen von Ungleichungen sind Intervalle, aber in unserer Aufgabe wurde c als eine ganze Zahl vorausgesetzt. So erhalten wir die drei Fälle c=17, c=18, c=19.

Jetzt ist Vorsicht geboten: Wir müssen zum Aufspüren der Lösungen in die Anfangsbedingungen gehen; das hübsche Rückwärtsaufrollen, wie es beim Gaußverfahren am Ende steht, kann hier in die Irre führen. So ist z.B. a= 8, b =13, c = 18 Lösung des zuletzt erhaltenen Systems ( des "zweigestrichenen"), widerspricht aber der Anfangsbedingung (3) 3b ≤ 2c.

Mit einem Wort: Die hier vorgenommenen Umformungen sind keine äquivalenten Umformungen! Sie sind nur notwendig. Will heißen: Jedes Lösungstripel der Anfangsbedingungen – also jede gesuchte Lösung - ist auch eine Lösung des zuletzt erhaltenen Systems. Die Umkehrung gilt, wie wir sahen, nicht: Das "zweigestrichene" System hat Lösungen, welche das ursprüngliche System nicht hat; da haben sich beim Umformen Lösungen "eingeschlichen".

Für jede Lösung a, b, c der Anfangsbedingungen gilt notwendig das zuletzt erhaltene System. Insbesondere gilt hier für jedes c, das die Anfangsbedingungen löst, dass es gleich 17 oder gleich 18 oder gleich 19 sein muss. Der erste Schritt des oben beschriebenen Verfahrens ist damit getan.

Zum Aufsuchen der Lösungen legen wir eine Tabelle an. Die erste Spalte enthält die drei möglichen Werte für c. Die folgenden Spalten zeigen, was sich aus den vier Anfangsbedingungen für die Werte von a und b ergibt. Dabei wertet man zunächst (3) und (4) aus, führt dann (1) und (3) zusammen und beachtet die Voraussetzung, dass die Variablen nur ganzzahlige Werte annehmen dürfen. Die vorletzte Spalte enthält die Lösungen (a|b|c) des ursprünglichen Systems (der Anfangsbedingungen), und schließlich prüft die letzte Spalte die sog. Dreiecksungleichung: Ist die Summe der beiden kürzeren Seiten größer als die längste Seite?

Die Bedingung (2) wird zur Ausrechnung nicht benötigt; wohl aber ist jeweils zu prüfen, ob die erhaltenen Lösungen sie erfüllen.

Ergebnis: Es gibt zwei Lösungen für die Gleichungen bzw. Ungleichungen (1) bis (4), aber nur eine davon ergibt die Maßzahlen der Längen eines Dreiecks, ist also zugleich Lösung der gestellten Aufgabe:

a=7cm,b=12cm,c=18cm

Und nun gehen wir nochmals auf die Sache mit der nicht äquivalenten Umformung ein.

Es mag verwirrend sein, dass Umformungen, die bei Gleichungssystemen die Lösungsmenge nicht verändern (äquivalent sind), es bei Systemen von Ungleichungen nicht sind. Schauen wir uns die Sache nochmals an einem einfachen Beispiel an . Gegeben sind zwei Ungleichungen (Wir wählen sie aus unserem obigen "gestrichenen System"; der Einfachheit halber nehmen wir nur zwei Ungleichungen mit zwei Variablen)
.

Wir sehen, dass b = 13, c = 18 keine Lösung des ursprünglichen Systems ist, wohl aber eine des umgeformten Systems. Bei der Umformung hat sich eine Lösung "eingeschlichen"; die Umformung ist nicht äquivalent.
Das Problem besteht darin, dass in dem ursprünglichen System für eine bestimmte Einsetzung die Ungleichheitszeichen in entgegengesetzte Richtung zeigen. Dann kann das Addieren der jeweils linken und rechten Seiten keine äquivalente Umformung sein. Ein weiteres Beispiel für die logische Regel, dass "aus etwas Falschem" auch bei korrekter Umformung "etwas Richtiges" werden kann! Genauer ausgedrückt: Ergibt eine Aussageform für eine bestimmte Einsetzung eine falsche Aussage, und formt man sie in einer Weise um, die für jede korrekte Einsetzung erlaubt wäre, so kann sie eine Form annehmen, bei der eben die Einsetzung, die vor der Umformung zu einer falschen Aussage führte, jetzt zu einer richtigen führt.
Das bekannteste Beispiel dafür ist wohl das folgende.
Gegeben ist als Definitionsmenge die Menge der rationalen Zahlen. Die Aussageform a = - a ist für die Einsetzung 0 richtig, für alle anderen falsch. Beidseitiges Quadrieren führt zu a2 = a2, was für die zuvor richtige Einsetzung 0 immer noch richtig ist, allerdings für die zuvor falschen ebenfalls richtig ist.
Und so verhält es sich auch bei den Systemen von Ungleichungen. Die vor der Umformung richtigen Einsetzungen – die Lösungen – müssen auch nach den Umformung noch Lösung sein. Allerdings muss man damit rechnen, dass sich neue Lösungen "einschleichen", welche im ursprünglichen System nicht gegeben waren.
Also: Probe unerlässlich!