Linearprogrammierung

Einschränkungen und Zielfunktion

In der Linearprogrammierung musst du zwei Hauptkomponenten beachten: die Einschränkungen und die Zielfunktion. Die Einschränkungen sind lineare Gleichungen oder Ungleichungen, die die Bedingungen beschreiben, die die Variablen erfüllen müssen. Ein einfaches Beispiel könnte sein:

• Einschränkungen: \( 2x + y \leq 20 \)\,\( x + 3y \leq 30 \)

• Maximieren: \( z = 3x + 4y \)

Lineare Optimierung und Optimierungsprobleme

Die lineare Optimierung ist ein wesentlicher Bestandteil der mathematischen Modellierung, der die Minimierung oder Maximierung einer linearen Zielfunktion unter Einhaltung von Restriktionen ermöglicht. Diese Techniken werden in der Praxis eingesetzt, um optimale Lösungen für komplexe Probleme in der Wirtschaft, Technik und Logistik zu finden.

Mathematische Formulierung

Die mathematische Formulierung eines linearen Optimierungsproblems besteht aus:

• Zielfunktion: Dies ist die Funktion, die maximiert oder minimiert werden muss, z.B. \( z = c_1x_1 + c_2x_2 + \, ... \, + c_nx_n \).
• Einschränkungen: Die Restriktionen sind lineare Gleichungen oder Ungleichungen, die die Zielfunktion beschränken, z.B. \( a_{11}x_1 + a_{12}x_2 + \, ... \, + a_{1n}x_n \leq b_1 \).

Simplex Verfahren in der Linearen Programmierung

Das Simplex-Verfahren ist eine leistungsfähige Methode, die in der Linearen Programmierung zur Lösung von Optimierungsproblemen verwendet wird. Es wurde in den 1940er Jahren von George Dantzig entwickelt und ermöglicht es, die beste Lösung einer linearen Zielfunktion zu finden, indem es durch die zulässigen Ecken oder Eckpunkte eines Polyederbereichs navigiert.

Wie funktioniert das Simplex-Verfahren?

Das Simplex-Verfahren beginnt mit der Identifikation einer zulässigen Basislösung, die sich an den Eckpunkten des zulässigen Bereichs befindet. Von diesem Punkt aus erfolgt eine iterative Navigation zu benachbarten Eckpunkten, die die Zielfunktion verbessern. Dies geschieht folgendermaßen:

• Wähle die Variable aus, die in die Basis eintreten soll, basierend auf dem höchsten Koeffizienten in der Zielfunktion.
• Ermittle, welche Variable die Basis verlassen wird, indem du die minimale Verhältnisregel anwendest.
• Führe eine Pivot-Operation durch, um die neue Basislösung zu finden.

Dualität in der Linearen Programmierung

In der Dualität der linearen Programmierung spielen zwei verwandte Probleme eine zentrale Rolle: das Primär- und das Dualproblem. Die Dualitätstheorie hilft dabei, die Beziehung zwischen diesen beiden Problemen zu verstehen und letztlich effizientere Lösungen zu finden.

Lineare Gleichungssysteme lösen in der Optimierung

Bei der Lösung von linearen Gleichungssystemen in der Optimierung ist es entscheidend, die Konzepte der Dualität zu verstehen. Das **Primärproblem** ist in der Regel das ursprünglich formulierte Problem, wo die Zielfunktion maximiert oder minimiert wird. Im Normalfall hat es die Form:Maximiere \( z = c^Tx \)Unter den Beschränkungen \( Ax \leq b \) und \( x \geq 0 \).Das korrespondierende **Dualproblem** hat die Form:Minimiere \( w = b^Ty \)Unter den Beschränkungen \( A^Ty \geq c \)und \( y \geq 0 \). Die *Optimalität* in einem der Probleme deutet auch auf die Optimalität im anderen hin, was heißt, dass beide Probleme bei korrekter Lösung dasselbe Ergebnis erzielen.