MathProf - Lineares Optimieren - Grafische Methode - Optimierung

 

Modul Lineare Optimierung

---

 
Das Unterprogramm [Algebra] - [Lineare Optimierung] - Lineare Optimierung - Grafische Methode ermöglicht die Anwendung der grafischen Methode der linearen Optimierung.

 

 

Lineare Optimierung ist ein Verfahren bei welchem eine lineare Zielfunktion mit Hilfe von mehreren Variablen und linearen Nebenbedingungen an einem mathematischen Modell dargestellt wird. In einem kartesischen Koordinatensystem wird der zulässige Bereich für die Gültigkeit der gestellten Nebenbedingungen grafisch ermittelt.

Die Nebenbedingungen, welche als Ungleichungen gegeben sind und als Geraden dargestellt werden, teilen die entsprechende Fläche in einen für diese möglichen bzw. unmöglichen Bereich.

Die Zielfunktion wird durch die Niveaulinien z(x₁,x₂) = c dargestellt. Das entsprechende Optimum entsteht für c = c_min bzw. c = c_max. Verläuft die Niveaulinie durch eine Ecke des möglichen Bereichs, so ist die Niveaulösung mehrdeutig. Verläuft sie hingegen parallel zu einer der Geraden (durch Nebenbedingungen bestimmt), so ist sie eindeutig.
 
Mit Hilfe dieser Methode können Extremwerte linearer Funktionen bestimmt werden, wobei es Nebenbedingungen zu beachten gibt. Diese Nebenbedingungen, welche oftmals Kapazitätsbedingungen ausdrücken, lassen sich in Form linearer Ungleichungen darstellen. Sind dabei nicht mehr als zwei Variablen zu beachten, so lässt sich dieses Problem grafisch lösen. Sind jedoch mehr als zwei Variablen zu berücksichtigen, muss ein analytisches Lösungsverfahren gewählt werden, zum Beispiel die Simplex-Methode.

 

Dieses Unterprogramm ermöglicht die Ermittlung von Lösungen mit Hilfe der grafischen Methode der linearen Optimierung wenn zwei Variablen zu berücksichtigen sind.
 

Grafisch Lösen - Allgemeine Vorgehensweise zur Auffindung von Lösungen mit Hilfe dieser Methode (lineares Optimieren):

1. Einzeichnen aller Nebenbedingungen in ein Koordinatensystem
2. Festlegung des zulässigen Bereichs
3. Für einen beliebigen festgelegten Funktionswert Eintragung der Zielfunktion
4. Bestimmung des Extremwertes durch Parallelverschiebung.
   Wenn ein Maximum gesucht ist, wird die Zielfunktion so lange nach oben verschoben,
   bis der zulässige Bereich gerade noch berührt wird. Bei der Bestimmung eines Minimums wird die Gerade möglichst nah an den Koordinatenursprung geschoben
5. Berechnung des grafisch ermittelten Punktes
6. Wenn zwei benachbarte Punkte und damit auch alle Punkte auf deren Verbindungsstrecke Lösungen sind, ist die Lösung mehrdeutig

 
Optimierung - Optimieren - Optimierungsproblem (mathematische Optimierung): Bei einem Optimierungsproblem (einer durchzuführenden Optimierung) handelt es sich um ein mathematisches Problem, bei welchem die Aufgabe darin besteht, aus einer vorhandenen Menge von Auswahlmöglichkeiten die beste hinsichtlich von Zielkriterien zu ermitteln.

Zielfunktion: Als Zielfunktion wird eine mathematische zu maximierende oder minimierende lineare Funktion bezeichnet, die unter Verwendung von Variablen beschreibt, welches Ziel bei der Durchführung einer Optimierung erreicht werden soll. Die Zielfunktion wird auch als Hauptbedingung bezeichnet.

Zielfunktionswert: Der Zielfunktionswert gibt den Erlös einer durchgeführten Optimierung an.

Nebenbedingungen (Restriktionen): Nebenbedingungen liegen in Form linearer Ungleichung vor, deren Werte für Variablen in der Form festgelegt werden müssen, dass die Bedingungen aller Ungleichungen erfüllt werden.

Entscheidungsvariablen: Als Entscheidungsvariablen werden die in der Zielfunktion auftretenden Variablen x und y bezeichnet.

Maximierung, Maximieren, Maximierungsproblem, Minimierung, Minimieren, Minimierungsproblem: Wird bei der Durchführung einer linearen Optimierung ein möglichst großer Zielwert (ein Maximum) angestrebt, so wird von einem Maximierungsproblem gesprochen. Wird hingegen ein möglichst kleiner Zielwert (ein Minimum) angestrebt, so handelt es sich um ein Minimierungsproblem.

Lineare Ungleichungssysteme: Bei Systemen dieser Art handelt es sich um Systeme, die aus Ungleichungen bestehen und anstelle der Gleichheitszeichen über entsprechende Vergleichszeichen (>, <) verfügen.

Optimierungsmodell: Als Optimierungsmodell wird ein mathematisches Modell bezeichnet, welches eine zu optimierende Begebenheit beschreibt. Es setzt sich aus Daten, einer Zielfunktion und entsprechenden beeinflussbaren Größen sowie einer zulässigen Menge zusammen.
 
 

Führen Sie Folgendes durch, um mit Hilfe der Anwendung der grafischen Methode der linearen Optimierung Analysen durchzuführen:
 

1. Legen Sie durch die Bedienung des Steuerelements mit der Bezeichnung Anz. NB fest, wie viele Nebenbedingungen zu erfüllen sind.
    
2. Bedienen Sie die Schaltfläche Koeffizienten und geben Sie in die Felder im Formularbereich HB die Koeffizienten der Gleichung der zu erfüllenden Hauptbedingung der Form z = a·x + b·y ein.

   Geben Sie in den Formularbereichen NB 1, NB 2 und NB 3 die Koeffizienten a₁, a₂, a₃, b₁, b₂, b_3, c₁, c₂ und c₃ der Gleichungen (Formeln) der zu erfüllenden (nachfolgend aufgeführten) Nebenbedingungen ein:

   a₁·x + b₁·y ≤ c₁  bzw.  a₁·x + b₁·y ≥ c₁

   a₂·x + b₂·y ≤ c₂  bzw.  a₂·x + b₂·y ≥ c₂

   a₃·x + b₃·y ≤ c₃  bzw.  a₃·x + b₃·y ≥ c₃
   
   Selektieren Sie aus der Auswahlbox das entsprechende Symbol <= bzw. >= um die Art der jeweils zu erfüllenden Nebenbedingung festzulegen und bestätigen Sie mit Ok.
    

3. Durch eine Aktivierung des Kontrollkästchens Hauptbedingung blenden Sie die Zielfunktion ein. Die Aktivierung der Kontrollkästchen Gerade durch Max. und Gerade durch Min. bewirkt die Darstellung der Geraden durch das ermittelte Maximum bzw. Minimum.

 

 

Nachfolgend finden Sie ein Video zu diesem Fachthema, welches Sie durch die Ausführung eines Klicks
auf die nachfolgend gezeigte Grafik abspielen lassen können.

 

 
Auf dem Bedienformular, welches durch Anklicken im obersten schmalen Bereich und bei Gedrückthalten der linken Maustaste verschiebbar ist, können Sie u.a. durch die Aktivierung bzw. Deaktivierung der entsprechenden Kontrollkästchen folgende zusätzliche Einstellungen vornehmen:

• Punkte: Darstellung relevanter Punkte ein-/ausschalten
• Punkte  beschriften: Beschriftung relevanter Punkte ein-/ausschalten
• Koordinaten: Anzeige der Koordinaten relevanter Punkte ein-/ausschalten

 

 

Allgemeines zum Handling des Programms bzgl. der Darstellung zweidimensionaler Grafiken wird unter Zweidimensionale Grafiken - Handling beschrieben. Wie Sie das Layout einer 2D-Darstellung konfigurieren können, erfahren Sie unter Layoutkonfiguration. Methoden zur Implementierung und zum Umgang mit grafischen Objekten werden unter Implementierung und Verwendung grafischer Objekte behandelt.

 

 

Lineare Optimierung - Simplex-Methode

 

 

Zwei verschiedene Kunststoffprodukte I und II werden aus demselben Rohgranulat erstellt. Drei Vorgänge bestimmen die Produktion: Warmpressen, Spritzguss, Verpackung. Produkt I entsteht durch Warmpressen, Produkt II durch Spritzguss. Beide werden verpackt. Die Warmpresse steht für maximal 10 h zur Verfügung. Pro Tonne des Produktes I wird 1 h gebraucht. Die Spritzguss-Maschine steht für maximal 6 h zur Verfügung. Pro Tonne des Produktes II wird 1 h gebraucht. Pro t von Produkt I werden 2h, pro t des Produktes II 4h von einer Person in der Verpackungsabteilung benötigt. Dort arbeiten 4 Personen à 8h. Der (gesicherte) Absatz der beiden Güter ergibt für Gut I einen Preis von 30GE/t, für Gut II 20 GE/t.

Wieviel von jedem Gut sollte das Unternehmen produzieren, um den Erlös zu maximieren?

Lösung des Problems:

Die Erlösfunktion (= Zielfunktion = Hauptbedingung) ist: z = 30·x +20·y

Gesucht ist z_max (maximaler Erlös)

Folgende Nebenbedingungen (Restriktionen) müssen erfüllt sein:

x ≤ 10
y ≤ 6
2x + 4y ≤ 32

sowie:

 

x ≥ 0 und
y ≥ 0 (Nichtnegativitätsbedingungen)

Durch jede Restriktion wird eine Ungleichungsrelation festgelegt. Die Schnittmenge (bei grafischer Darstellung die gefüllte Polygonfläche) aller dieser Ungleichungsrelationen ist der zulässige Bereich.

 

Es wird ein zweidimensionales Koordinatensystem betrachtet, in welchem der zulässige Bereich eingezeichnet wird. Dessen Grenzen sind die Geraden x = 10; y = 6; 2·x + 4·y = 32. Dieser Bereich wird markiert.

 

Es gilt nun, die Gerade zu finden, die den höchsten Ordinatenabschnitt hat und deren Schnittmenge mit der Menge, die die Restriktionen erfüllt, nicht leer ist. Dies bedeutet, die Gerade so weit nach oben rechts zu verschieben, bis sie nur noch einen Punkt der roten Fläche berührt. (Bei der Suche nach einem Minimum würde dies bedeuten, die Gerade so weit nach links unten zu verschieben, bis sie nur noch einen Punkt der roten Fläche berührt)

 

Wird dies durchgeführt, so ist zu erkennen:

 

Die gesuchte Gerade verläuft durch den Schnittpunkt der Geraden x = 10 und 2·x + 4·y = 32, also durch den Punkt (10 / 3). Diese Gerade besitzt den größten Ordinatenabschnitt und hat immer noch einen Punkt mit der roten Fläche gemeinsam. Der Erlös an diesem Punkt ist somit: y = 30·10 + 20·3 = 360 GE.
 

Werden nach einem Klick auf die Schaltfläche Koeffizienten die Eingaben und Einstellungen vorgenommen, wie auf nachfolgendem Bild gezeigt, so kann die oben aufgeführte Aufgabe mit diesem Unterprogramm gelöst werden.
 

 
 
Das Programm gibt für die Gleichung der Geraden durch das Maximum aus: y = 1,5·x+18. Für die Gleichung der Geraden durch das Minimum wird y = 1,5·x ermittelt. Geraden welche durch ein Minimum oder ein Maximum verlaufen sind grau, Grenzgeraden sind blau, die Gerade der Hauptbedingung ist braun markiert.
 

 

 

Grafische Darstellung - Beispiel 1


Grafische Darstellung - Beispiel 2


Grafische Darstellung - Beispiel 3

 

Hilfreiche Informationen zu diesem Fachthema sind unter Wikipedia - Lineare Optimierung zu finden. 

 

Cramersche Regel - Matrizen - Lineares Gleichungssystem - Gauß'scher Algorithmus - Unterbestimmtes lineares Gleichungssystem - Überbestimmtes lineares Gleichungssystem - Komplexes Gleichungssystem - Lineare Optimierung - Simplex-Methode - Gleichungen - Gleichungen 2.- 4. Grades - Ungleichungen - Prinzip - Spezielle Gleichungen - Richtungsfelder von DGL 1. Ordnung - Interaktiv - DGL 1. Ordnung (Differentialgleichungen) - DGL n-ter Ordnung (Differentialgleichungen) - DGL-Gleichungssystem - Mengenelemente - Venn-Diagramm - Zahluntersuchung - Bruchrechnung - Primzahlen - Sieb des Eratosthenes - Taschenrechner - Langarithmetik - Einheitskreis komplexer Zahlen - Schreibweisen komplexer Zahlen - Berechnungen mit komplexen Zahlen - Addition komplexer Zahlen - Multiplikation komplexer Zahlen - Taschenrechner für komplexe Zahlen - Zahlen I - Zahlen II - Zahlensysteme - Zahlumwandlung - P-adische Brüche - Bruch - Dezimalzahl - Kettenbruch - Binomische Formel - Addition - Subtraktion - Irrationale Zahlen - Wurzellupe - Dezimalbruch - Mittelwerte

 

MathProf 5.0 - Unterprogramm Simplex-Methode

---

MathProf 5.0 - Unterprogramm Kurven von Funktionen in Parameterform
 

 

PhysProf 1.1 - Unterprogramm Adiabatische Zustandsänderung
 

SimPlot 1.0 - Grafik-  und Animationsprogramm für unterschiedlichste Anwendungszwecke

 

Nachfolgend finden Sie ein Video zu einer mit SimPlot 1.0 erstellten Animationsgrafik, welches Sie durch die Ausführung eines Klicks auf die nachfolgend gezeigte Grafik abspielen lassen können.

Nachfolgend finden Sie ein Video zu einer mit SimPlot 1.0 erstellten Animationsgrafik, welches Sie durch die Ausführung eines Klicks auf die nachfolgend gezeigte Grafik abspielen lassen können.

Nachfolgend finden Sie ein Video zu einer mit SimPlot 1.0 erstellten Animationsgrafik, welches Sie durch die Ausführung eines Klicks auf die nachfolgend gezeigte Grafik abspielen lassen können.

---