Lineare Optimierung – Ungleichungssysteme

Um eine Lineare Optimierung bzw. ein lineares Optimierungsproblem lösen zu können, solltest du mit Ungleichungen und deren Systemen vertraut sein. Eine Ungleichung ist eine Behauptung, die von einer (oder mehreren) Variablen abhängt. Allerdings behauptet sie nicht, dass zwei Terme gleich sind, sondern dass ein Term größer oder kleiner (oder größer-gleich oder kleiner-gleich) als ein anderer Term ist. Variablenwerte, die eine Ungleichung erfüllen, stellen Lösungen dar. Die Menge aller Lösungen heißt Lösungsmenge. Einfache Ungleichungen kannst du ohne großartigen Formalismus durch ein bisschen Nachdenken (nach Art einer Denksportaufgabe) lösen. Es gibt Verfahren (Äquivalenzumformungen), die gewissen Regeln genügen, systematisch angewandt helfen sie dir beim Auffinden der Lösungsmenge. Um sicher zu gehen, kannst du für einzelne „Lösungskandidaten“ immer die Probe durch Einsetzen machen. Führt sie auf eine wahre Aussage, so handelt es sich tatsächlich um eine Lösung

Allerdings gibt es auch wichtige Unterschiede zwischen Gleichungen und Ungleichungen, die du beachten solltest:

Eine Ungleichung besitzt in der Regel nicht nur eine, sondern viele (unendlich viele, siehe grafischen Lösungsansatz) Lösungen. Um die Menge all dieser Lösungen angeben zu können, sind etwas mehr mathematische Kenntnisse nötig als beim Hinschreiben einer einzigen Zahl. Die Regeln zum Umformen von Ungleichungen (Äquivalenzumformungen) sind etwas komplizierter als die Regeln zum Umformen von Gleichungen. Manchmal führen sie auf Fallunterscheidungen. Um die Lösungsmenge einer Ungleichung zu finden, sind dann mehrere vereinfachte Ungleichungen zu lösen und deren Lösungsmengen zu kombinieren.

Was ist eine Lineare Optimierung?

Ungleichungsprobleme werden manchmal von vornherein in Form mehrerer Ungleichungen gestellt. Diese sollen alle gleichzeitig erfüllt sein (oder – was auch vorkommt – von denen zumindest eine erfüllt sein soll). In solchen Fällen handelt es sich genau genommen um Ungleichungssysteme, aber diese lassen sich von den Ungleichungen weniger scharf trennen als Gleichungssysteme von Gleichungen. Auch wenn eine einzige Ungleichung gegeben ist, kannst du durch eine Fallunterscheidung erkennen, dass du mehrere Ungleichungen betrachten musst. All das macht die Sache etwas komplizierter als das Gleichungslösen.

Die lineare Optimierung oder lineare Programmierung beschäftigt sich mit der Optimierung linearer Zielfunktionen über einer Menge, die durch lineare Gleichungen und Ungleichungen eingeschränkt ist. Häufig lassen sich lineare Programme (LPs) zur Lösung von Problemen einsetzen, für die keine speziell entwickelten Lösungsverfahren bekannt sind, beispielsweise bei der Planung von Verkehrs- oder Telekommunikationsnetzen oder in der Produktionsplanung. 

Das ökonomische Prinzip tritt dabei in den Formen des Maximaprinzips und des Minimalprinzips auf. Beim Maximalprinzip möchte man aus einem Bestand an Mitteln (Material, Arbeitsstunden, Kapital etc.) ein möglichst großer Nutzen und/oder Gewinn erzielen. Beim Minimalprinzip soll ein Ziel mit möglichst kleinen Aufwand oder Kosten erreicht werden.

Eine Lineare Zielfunktion, deren Funktionswert maximal oder minimal werden soll und Nebenbedingungen, die die Möglichkeiten einschränken und den Lösungsbereich begrenzen, stehen dabei als mathematische Werkzeuge zur Verfügung.

Was ist eine Primzahl?

Eine natürliche Zahl die größer als 1 ist, ist eine Primzahl, wenn sie nur durch sich selbst und durch 1 teilbar ist. Das bedeutet, eine natürliche Zahl ist eine Primzahl, wenn sie genau zwei Teiler besitzt.

Eine Primzahl ist eine natürliche Zahl, die größer als 1 und ausschließlich durch sich selbst und durch 1 teilbar ist. Das Wort „Primzahl“ leitet sich ab von lateinisch numerus primus ‚erste Zahl‘, wobei primus speziell ‚Anfang, das Erste (der Dinge)‘ bedeutet, sodass eine ‚Anfangszahl‘ gemeint ist, die man aus keiner anderen (vorhergehenden) Zahl konstruieren kann.

Die Menge der Primzahlen wird in der Regel mit dem Symbol P bezeichnet. Mit P verknüpft ist eine Folge, die nach ihrer Größe geordneten Primzahlen enthält, die man auch Primzahlfolge nennt.

Die Bedeutung der Primzahl

Für viele Bereiche der Mathematik beruht auf drei Folgerungen aus ihrer Definition:

  • Existenz und Eindeutigkeit der Primfaktorzerlegung: Jede natürliche Zahl, die größer als 1 und selbst keine Primzahl ist, lässt sich als Produkt von mindestens zwei Primzahlen schreiben. Diese Produktdarstellung ist bis auf die Reihenfolge der Faktoren eindeutig. Zum Beweis dient das
  • Lemma von Euklid: Ist ein Produkt zweier natürlicher Zahlen durch eine Primzahl teilbar, so ist mindestens einer der Faktoren durch sie teilbar.
  • Primzahlen lassen sich nicht als Produkt zweier natürlicher Zahlen, die beide größer als 1 sind, darstellen.

Diese Eigenschaften kannst du in der Algebra für Verallgemeinerungen des Primzahlbegriffs nutzen. Eine Zahl, die das Produkt von zwei oder mehr Primfaktoren ist, nennt man zusammengesetzt. Die Zahl 1 ist weder prim noch zusammengesetzt, was mit ihrer Invertierbarkeit zusammenhängt. Alle anderen natürlichen Zahlen sind eines von beiden, entweder prim (also Primzahl) oder zusammengesetzt.

Die Primfaktorzerlegung ist die Darstellung einer natürlichen Zahl n als Produkt aus Primzahlen, die man dann als Primfaktoren von n bezeichnet. Diese Darstellung ist eindeutig (bis auf die Reihenfolge der Faktoren; es ist eine Multimenge) und zählt zu den grundlegenden und klassischen Werkzeugen der Zahlentheorie. Sie ist Gegenstand des Fundamentalsatzes der Arithmetik. Es ist bisher kein effizientes Faktorisierungsverfahren bekannt, um die Primfaktorzerlegung einer beliebigen Zahl zu erhalten.

Was ist die mehrdimensionale Analysis?

Die mehrdimensionale Analysis betrachtet Funktionen mehrerer reeller Variablen, die oft als ein Vektor beziehungsweise n-Tupel dargestellt werden. Wir kennen bisher Differential- und Integralrechnung für Funktionen, die von einer Variablen abhängen. In Informatikgebieten wie Optimierung und Visual Computing spielen jedoch sehr oft Funktionen eine Rolle, die von mehreren Variablen abhängen. Die Ableitungsregeln für Funktionen einer Variabler übertragen sich direkt auf Funktionen mehrerer Variablen.

Viele Lehrbücher unterscheiden zwischen Analysis in einer und Analysis in mehreren Dimensionen. Diese Differenzierung berührt die grundlegenden Konzepte nicht, allerdings gibt es in mehreren Dimensionen eine größere mathematische Vielfalt. Die Begriffe der Norm (als Verallgemeinerung des Betrags), der Konvergenz, der Stetigkeit und der Grenzwerte lassen sich einfach von einer in mehrere Dimensionen verallgemeinern.

Wie ist die mehrdimensionale Analysis zu verstehen?

Die Differentiation von Funktionen mehrerer Variablen unterscheidet sich von der →eindimensionalen Differentiation. Wichtige Konzepte sind die Richtungs- und die partielle Ableitung, die Ableitungen in einer Richtung beziehungsweise in einer Variable sind. Der Satz von Schwarz stellt fest, wann partielle beziehungsweise Richtungsableitungen unterschiedlicher Richtungen vertauscht werden dürfen. Außerdem ist der Begriff der totalen Differentiation von Bedeutung. Diesen kannst du als die lokale Anpassung einer linearen Abbildung an den Verlauf der mehrdimensionalen Funktion interpretieren und als das mehrdimensionale Analogon der (eindimensionalen) Ableitung verstehen. 

Der Satz von der impliziten Funktion über die lokale, eindeutige Auflösung impliziter Gleichungen ist eine wichtige Aussage der mehrdimensionalen Analysis und kann als eine Grundlage der Differentialgeometrie verstanden werden.

In der mehrdimensionalen Analysis gibt es unterschiedliche Integralbegriffe wie das Kurvenintegral, das Oberflächenintegral und das Raumintegral. Jedoch von einem abstrakteren Standpunkt aus der Vektoranalysis unterscheiden sich diese Begriffe nicht. Zum Lösen dieser Integrale sind der Transformationssatz als Verallgemeinerung der Substitutionsregel und der Satz von Fubini, welcher es erlaubt, Integrale über n-dimensionale Mengen in iterierte Integrale umzuwandeln, von besonderer Bedeutung. 

Auch die Integralsätze aus der Vektoranalysis von Gauß, Green und Stokes sind in der mehrdimensionalen Analysis von Bedeutung. Du kannst sie als Verallgemeinerung des Hauptsatzes der Integral- und Differentialrechnung verstehen.

Die Ableitung einer Funktion – Differenzieren

Die Ableitung einer Funktion einer reellen Variablen misst die Empfindlichkeit gegenüber einer Änderung des Funktionswertes. Der Ausgabewert bezieht sich dabei auf eine Änderung des Arguments (Eingabewertes). Ableitungen sind ein grundlegendes Werkzeug der Analysis. Zum Beispiel ist die Ableitung der Position eines sich bewegenden Objekts in Bezug auf die Zeit die Geschwindigkeit des Objekts. Sie misst, wie schnell sich die Position des Objekts ändert, wenn die Zeit fortschreitet.

Die Ableitung einer Funktion einer einzelnen →Variablen bei einem gewählten Eingabewert ist die Steigung der Tangente. Wenn sie existiert, beschreibt sie die Tangente am Graphen der Funktion an diesem Punkt. Die Tangentenlinie ist die beste lineare Annäherung der Funktion in der Nähe dieses Eingangswertes. Aus diesem Grund wird die Ableitung oft als „momentane Änderungsrate“ beschrieben. Das heißt als das Verhältnis der momentanen Änderung der abhängigen Variablen zu der der unabhängigen Variablen.

Ableitungen können auf Funktionen mehrerer reeller Variablen verallgemeinert werden. Bei dieser Verallgemeinerung wird die Ableitung in eine lineare Transformation umgedeutet. Der Graph ist die beste lineare Annäherung an den Graphen der ursprünglichen Funktion. Die Jacobimatrix ist die Matrix, die diese lineare Transformation in Bezug auf die durch die Wahl der unabhängigen und abhängigen Variablen gegebene Grundlage darstellt. Du kannst sie auf die partiellen Ableitungen in Bezug auf die unabhängigen Variablen berechnen. Für eine reellwertige Funktion mehrerer Variablen reduziert sich die Jacobimatrix auf den Gradientenvektor.

Wie berechnet man die Ableitung?

Der Prozess, eine Ableitung zu finden, nennt man Differenzierung. Den umgekehrte Prozess nennt man Antidifferenzierung. Das fundamentale Theorem der Analysis verbindet Antidifferenzierung mit Integration. Differentiation und →Integration sind die beiden Grundoperationen in der Ein-Variablen-Kalkulation.

Differenzierung ist die Aktion der Berechnung einer Ableitung. Die Ableitung einer Funktion y = f(x) einer Variablen x ist ein Maß für die Rate, mit der sich der Wert y der Funktion in Bezug auf die Änderung der Variablen x ändert. Sie wird Ableitung von f in Bezug auf x genannt. Wenn x und y reelle Zahlen sind und wenn der Graph von f gegen x aufgetragen wird, ist die Ableitung die Steigung dieses Graphen an jedem Punkt.

Steigung einer →linearen Funktion: m = Δy/Δx

Der einfachste Fall, abgesehen vom trivialen Fall einer konstanten Funktion, ist, wenn y eine lineare Funktion von x ist, was bedeutet, dass der Graph von y eine Linie ist. In diesem Fall ist y = f(x) = mx + b, für die reellen Zahlen m und b, und die Steigung m ist gegeben durch:

m = Δy/Δx

wobei das Symbol Δ (Delta) eine Abkürzung für „Veränderung“ ist, und die Kombinationen Δx und Δy beziehen sich auf entsprechende Änderungen.

Was ist das Tangentenproblem?

Ein zentrales Thema in der →Differentialrechnung ist das Tangentenproblem. Du wirst sehen, mit Hilfe von Grenzwerten und Steigungsberechnung ist es gar nicht so schwierig, damit umzugehen.

Beim Tangentenproblem geht es um die Frage, ob in einem bestimmten Punkt einer Kurve eine Tangente vorhanden ist und wie groß deren Steigung ist. Mittels Differenzenquotient und Differentialquotient kannst du diese sehr einfach berechnen.

Das Tangentenproblem

Die Aufgabe, die Tangente an die Bildkurve einer Funktion f(x) zu einem beliebigen Punkt P mit den Koordinaten x und f(x) zu legen, führt bei der Ermittlung der Steigung zu einem Quotienten besonderer Art, dem Differentialquotienten. Die Untersuchung der Eigenschaften des Differentialquotienten einer Funktion ist Gegenstand der Differentialrechnung. Als Voraussetzung dafür solltest du wissen, wie du die Steigung einer Geraden bildest.

Der Graph einer Funktion f verläuft zwischen den Punkten P1und P2verschieden steil. Über die →Steilheit des Graphen kannst du an einer bestimmten Stelle x0zwischen Px1und Px2keine genaue Angabe machen. Es lässt sich lediglich eine mittlere Steilheit zwischen P1und P2angeben, die der Steigung der Geraden g durch diese Punkte entspricht. Der Graph wird sozusagen zwischen den Punkten P1und P2durch die Gerade linearisiert.

Wir suchen die Steigung des Funktionsgraphen im Punkt P1. Dazu lassen wir den Summanden x immer kleiner werden, bis aus der Sekante eine Tangente wird. Der Wert von y bestimmt die Lage des Punktes P2. Für x gleich Null fallen P1und P2zusammen.

Durch Null darfst du aber nicht teilen, somit musst du zumindest versuchen, so nahe wie möglich an den Nennwert Null heranzukommen – das heißt, du musst den Summanden x möglichst klein werden lassen. Er soll also gegen Null gehen, aber den Wert Null gerade nicht erreichen. Im Differentialquotienten geht dann der Wert für xgegen Null. Und es wird ein Grenzwert (Limes) gebildet.

Wie kann man eine Tangente berechnen?

Eine Tangente ist eine Gerade, die etwas nur berührt, aber nicht schneidet. Unter Kurvendiskussion versteht man in der Mathematik die Untersuchung des Graphen einer Funktion. Untersucht werden dessen geometrische Eigenschaften. Wie zum Beispiel Schnittpunkte mit den Koordinatenachsen, Hoch- und Tiefpunkte, Wendepunkte, gegebenenfalls Sattel- und Flachpunkte, Asymptoten, Verhalten im Unendlichen usw. Diese Informationen erlauben es, eine Skizze des Graphen anzufertigen, aus der all diese für die Funktion charakteristischen Eigenschaften unmittelbar ablesbar sind.

Eine Tangente ist eine Gerade, die etwas nur berührt, aber nicht schneidet. Legt man zum Beispiel eine Kugel auf ein glattes Brett, so berührt das Brett die Kugel ja nur. Das Brett wäre also eine Tangente an die Kugel. 

Findet man eine Tangente an einen Funktionsgraphen in einem Punkt, dann kann man sagen, dass der Graph in dem Punkt die gleiche Steigung hat wie diese. Also verwendet man Tangenten oft, um gut über die Steigung eines Funktionsgraphen reden zu können.

Wie kann man eine Tangente berechnen?

Wenn du Tangenten an der Stelle x finden willst, machst du folgendes:

x in die →lineare Funktion einsetzen, dann erhält man schon mal den Punkt, an dem die Tangente berührt.

x in die Ableitung einsetzen, dann erhält man die Steigung m.

m und den obigen Punkt in die →Geradengleichung y=m*x+b einseten, dann erhält man b.

Eine Wendetangenten sind Tangenten im Wendepunkt. Waagerechte Tangenten haben die Steigung Null und beschreiben die mögliche Stelle für Hochpunkt, Tiefpunkt oder Sattelpunkt.

Tangenten (von lateinisch: tangere ‚berühren‘) sind in der Geometrie Geraden, die eine gegebene Kurve in einem bestimmten Punkt berühren. Beispielsweise ist die Schiene für das Eisenbahnrad eine Tangente. Da der Auflagepunkt des Rades ein Berührungspunkt der beiden geometrischen Objekte, Gerade und Kreis, ist. Tangente und Kurve haben im Berührungspunkt die gleiche Richtung. Tangenten in diesen Punkten sind die beste lineare Näherungsfunktion für die Kurve.

Ein Funktionsgraph hat an einer Stelle x = x0 eine waagerechte Tangente, wenn dort die erste Ableitung verschwindet, d. h. den Wert null hat: 𝑓′(𝑥0)=0. Dies kann bedeuten, dass sich dort eine Extremstelle befindet. Also ein Maximum oder Minimum der Funktion, es kann dort aber auch ein Sattelpunkt vorliegen.

Werde Teil von Lernflix

Bleib´ am Laufenden und versäume keinen neuen Beitrag von lernflix

Newsletter-anmeldunG