Mathematische Inhalte:

1.1 Beispiel 1: Gärtnerproblem

Ein Gärtner will seinen 100 m² großen Garten mit Blumen und Gemüse bepflanzen. Folgende Daten stehen zur Verfügung:
 
 

Der Gärtner will nur 7200 S investieren und außerdem nicht mehr als 60% der Anbaufläche für Blumen beanspruchen. Wieviel m² soll er mit Blumen und wieviel mit Gemüse bepflanzen, damit sein Reingewinn möglichst groß wird?

Zur Formulierung der vorliegenden Problemstellung als mathematisches Modell wählen wir die folgenden Bezeichnungen:

Die linearen Ungleichungen (1.1), (1.2) und (1.3) heißen Nebenbedingungen oder Restriktionen.

(1.4) sind die Nichtnegativitätsbedingungen.

Für Gleichung (1.5) ist aus den Lösungen des Ungleichungssystems (1.1), (1.2) und (1.3) das Maximum zu bestimmen. Sie wird als Zielfunktion des Problems bezeichnet.
Das entwickelte Modell ist ein lineares Modell, ein sog. Lineares Programm (LP) oder Lineares Optimierungsproblem.

1.2 Beispiel 2

Ein Betrieb stellt zwei Produkte P1 und P2 her, die die drei Maschinentypen A, B,und C durchlaufen müssen. Die folgende Tabelle enthält die erforderlichen Bearbeitungszeiten pro Mengeneinheit (ME), die monatlich zur Verfügung stehenden Maschinenkapazitäten und den Gewinn pro Mengeneinheit (ME) in Gewinneinheiten (GE) für jedes Produkt:

Gesucht ist das gewinnmaximale Produktionsprogramm.

Auch dieses einfache Planungsprogramm läßt sich ohne Einsatz mathematischer Hilfsmittel nur mit Mühe (z. B. durch Probieren) lösen. Bei umfangreicheren Problemen ist ein Lösen durch Probieren unmöglich.

Für die vorliegenden Problemstellung soll ein mathematisches Modell erstellt werden. Man wählt dazu die folgenden Bezeichnungen:

Für dieses Optimierungsproblem erhalten wir das folgende mathematische Modell:

2. Graphische Veranschaulichung von Linearen Programmen in zwei Variablen

Bei nur zwei Variablen x1 und x2 läßt sich der zulässige Bereich in einem zweidimensionalen kartesischen Normalkoordinatensystem veranschaulichen.
In Abb. 1.1 ist die graphische Lösung für Beispiel 1 dargestellt. Die Ungleichungen (1.1), (1.2), (1.3) aus Beispiel 1 werden durch Halbebenen dargestellt, die von den Geraden 1), 2) und 3) mit den folgenden Gleichungen (1.1'), (1.2') und (1.3') erzeugt werden.

        Abb. 1.1

Die Lösungsmenge X des Ungleichungssystems besteht aus allen geordneten Paaren (x1, x2), die die Ungleichungen (1.1), (1.2) und (1.3) und die Nichtnegativitätsbedingungen (1.4) erfüllen. Geometrisch bedeutet das die Durchschnittsmenge aller beteiligten Halbebenen. Dieser Durchschnitt ist der zulässige Bereich des Optimierungsproblems und wird als konvexes Polyeder bezeichnet. Die zulässige Menge X mit den Eckpunkten E0, E1, E2, E3, E4 ist in Abb. 1.1 schraffiert dargestellt.

Die Gleichung der Zielfunktion (1.5) beschreibt eine Schar paralleler Geraden (sog. Isogewinngeraden), wobei durch die Koeffizienten von x1 und x2 der Normalvektor (200,100)T dieser Geraden festgelegt ist. Da die optimale Lösung aus dem zulässigen Bereich sein muß, ist jene Gerade zu zeichnen, die mit dem zulässigen Bereich genau einen Punkt gemeinsam und den größten x2-Abschnitt hat.

Die graphische Lösung für Beispiel 2 ist in der folgenden Abbildung Abb. 2.1 veranschaulicht. Die Geraden 1), 2) und 3) werden durch die Gleichungen (2.1'), (2.2') und (2.3') beschrieben.

        Abb. 2.1

3. Folgerungen aus der graphischen Lösung von Linearen Programmen mit zwei Variablen

1) Die optimale Lösung liegt am Rand des zulässigen Bereichs.
2) Mindestens ein Eckpunkt des zulässigen Bereichs ist die optimale Lösung des Problems.
Daraus folgt, daß man sich bei der Bestimmung der optimalen Lösung(en) auf die endlich vielen Eckpunkte des zulässigen Bereichs beschränken kann.

4. Berechnung der Eckpunkte und der Zielfunktionswerte

Die Eckpunkte des zulässigen Bereichs sollen nun als Schnittpunkte von je zwei Geraden mit Hilfe eines Programmes für einen basicprogrammierbaren Taschenrechner ermittelt werden. Gleichzeitig wird für jeden berechneten Eckpunkt auch der zugehörige Wert der Zielfunktion berechnet. Aus Abb. 1.1 bzw. Abb. 2.1 ist ersichtlich, welche Geraden für das jeweilige Problem dazu miteinander zu schneiden sind.

Die Bestimmung des Schnittpunktes zweier Geraden ist mathematisch gesehen die Ermittlung der Lösung eines linearen Gleichungssystemes in 2 Variablen. Als Lösungsalgorithmus wählen wir die Cramersche Regel:

Für den Fall D = 0 ist noch zu unterscheiden, ob D1 (D2) von Null verschieden ist. Geometrisch bedeutet D = 0 und D₁ <>  0, daß die durch (I) und (II) beschriebenen Geraden parallel, aber verschieden sind. D = 0 und D₁ = 0 bedeutet, daß die Geraden zusammenfallen.

Das Basic-Programm (List. 1.1) ist für den Befehlssatz des programmierbaren Taschenrechners SHARP Pocket Computer PC-1403 entwickelt. Um bei der Programmierung die Verwendung von indizierten Variablen zu vermeiden und ein Variablenname aus maximal 2 Zeichen bestehen darf, wird das Gleichungssystem in der folgenden Form geschrieben:

In den folgenden Tabellen (Tab 1.2 und Tab. 2.2) sind die berechneten Koordinaten der Eckpunkte und die zugehörigen Werte der Zielfunktion für Beispiel 1 und Beispiel 2 zusammengestellt.

Wir untersuchen das Ergebnis von Beispiel 2: Den maximalen Wert der Zielfunktion unter den gegebenen Nebenbedingungen liefert der Eckpunkt E3 (70,90) mit 410 GE.

Setzt man nun (70,90) in die einzelnen Ungleichungen ein, so erhält man:

Da die Ungleichungen (2.1), (2.2) und (2.3) des Linearen Problems Maschinenkapazitäten der Maschinen A, B und C bedeuten, können wir daraus folgern: Die errechneten Fertigungsmengen beanspruchen die gesamten Kapazitäten der Maschinen B und C. Bei Maschine A bleiben
600 - 60 = 40 h ungenutzt. Man spricht dabei von einer freien Kapazität.

Literatur: