LINEARE PROGRAMMIERUNG: WOFÜR IST ES, MODELLE, EINSCHRÄNKUNGEN, ANWENDUNGEN - MATHE - 2025

Die lineare Programmierung ist eine mathematische Methode, mit der eine Funktion, deren Variablen eingeschränkt sind, optimiert (je nach Bedarf maximiert oder minimiert) wird, solange die Funktion und die Einschränkungen linear abhängige Variablen sind.

Im Allgemeinen modelliert die zu optimierende Funktion eine praktische Situation, beispielsweise den Gewinn eines Herstellers, dessen Input, Arbeitskräfte oder Maschinen begrenzt sind.

Abbildung 1. Lineare Programmierung wird häufig verwendet, um Gewinne zu optimieren. Quelle: Piqsels.

Einer der einfachsten Fälle ist der einer zu maximierenden linearen Funktion, die nur von zwei Variablen abhängt, die als Entscheidungsvariablen bezeichnet werden. Es kann von der Form sein:

Z = k ₁ x + k ₂ y

Mit k ₁ und k ₂ konstant. Diese Funktion wird als Zielfunktion bezeichnet. Natürlich gibt es Situationen, die mehr als zwei Variablen für das Studium verdienen und komplexer sind:

Z = k ₁ x ₁ + k ₂ x ₂ + k ₃ x ₃ +….

Und die Einschränkungen werden auch mathematisch durch ein System von Gleichungen oder Ungleichungen modelliert, die in x und y gleichermaßen linear sind.

Die Menge der Lösungen in diesem System wird als realisierbare Lösungen oder realisierbare Punkte bezeichnet. Und unter den möglichen Punkten gibt es mindestens einen, der die Zielfunktion optimiert.

Die lineare Programmierung wurde vom amerikanischen Physiker und Mathematiker George Dantzig (1914-2005) und dem russischen Mathematiker und Ökonomen Leonid Kantorovich (1912-1986) kurz nach dem Zweiten Weltkrieg unabhängig voneinander entwickelt.

Die als Simplex-Methode bekannte Problemlösungsmethode stammt von Dantzig, der für die US Air Force, die Berkeley University und die Stanford University arbeitete.

Abbildung 2. Mathematiker George Dantzig (links) und Leonid Kantorovich (rechts). Quelle: F. Zapata.

Lineare Programmiermodelle

Die Elemente, die erforderlich sind, um ein lineares Programmiermodell zu erstellen, das für eine praktische Situation geeignet ist, sind:

-Zielfunktion

-Entscheidungsvariablen

-Beschränkungen

In der Zielfunktion definieren Sie, was Sie erreichen möchten. Angenommen, Sie möchten die Gewinne aus der Herstellung bestimmter Produkte maximieren. Dann wird die "Gewinn" -Funktion entsprechend dem Preis eingerichtet, zu dem die Produkte verkauft werden.

In mathematischen Begriffen kann diese Funktion mit der Summationsnotation abgekürzt ausgedrückt werden:

Z = ∑k _i x _i

In dieser Gleichung sind k _i Koeffizienten und x _i die Entscheidungsvariablen.

Die Entscheidungsvariablen sind die Elemente des Systems, deren Kontrolle vorhanden ist, und ihre Werte sind positive reelle Zahlen. In dem vorgeschlagenen Beispiel sind die Entscheidungsvariablen die Menge jedes Produkts, das hergestellt werden soll, um den maximalen Gewinn zu erzielen.

Schließlich haben wir die Einschränkungen, die lineare Gleichungen oder Ungleichungen in Bezug auf die Entscheidungsvariablen sind. Sie beschreiben die bekannten Einschränkungen des Problems und können beispielsweise die bei der Herstellung verfügbaren Rohstoffmengen sein.

Arten von Einschränkungen

Sie können eine Anzahl M von Einschränkungen haben, beginnend mit j = 1 bis j = M. Mathematisch gibt es drei Arten von Einschränkungen:

1. A _j = ∑ a _ij . x _i
2. B _j ≥ ∑ b _ij . x _i
3. C _j ≤ ∑ c _ij . x _i

Die erste Einschränkung ist vom Typ der linearen Gleichung und bedeutet, dass der bekannte Wert A _j eingehalten werden muss.

Die beiden verbleibenden Einschränkungen sind lineare Ungleichungen und bedeuten, dass die bekannten Werte _Bj und _Cj respektiert oder überschritten werden können, wenn das angezeigte Symbol ≥ (größer oder gleich) ist oder respektiert oder nicht überschritten wird, wenn das Symbol ≤ ist (Gleich oder kleiner als).

Modellbeispiel

Die Anwendungsbereiche sind sehr unterschiedlich und reichen von der Betriebswirtschaft bis zur Ernährung. Um die Methode zu verstehen, wird im Folgenden ein einfaches Modell einer praktischen Situation mit zwei Variablen vorgeschlagen.

Eine lokale Konditorei ist bekannt für zwei Spezialitäten: Schwarzwälder Kirschtorte und Sakripantinkuchen.

Bei der Zubereitung benötigen sie Eier und Zucker. Für den Schwarzwald benötigen Sie 9 Eier und 500 g Zucker, für das Sakripantin 8 Eier und 800 g Zucker. Die jeweiligen Verkaufspreise betragen 8 USD und 10 USD.

Das Problem ist: Wie viele Kuchen jeder Art muss die Bäckerei machen, um ihren Gewinn zu maximieren, wenn sie weiß, dass sie 10 Kilo Zucker und 144 Eier hat?

Entscheidungsvariablen

Die Entscheidungsvariablen sind "x" und "y", die reale Werte annehmen:

-x: die Anzahl der Schwarzwälder Kuchen

-y: Kuchen vom Typ Sacripantine.

Beschränkungen

Die Einschränkungen ergeben sich aus der Tatsache, dass die Anzahl der Kuchen eine positive Menge ist und es nur begrenzte Mengen an Rohmaterial gibt, um sie zuzubereiten.

In mathematischer Form haben diese Einschränkungen daher die Form:

1. x ≥ 0
2. und ≥0
3. 9x + 8y ≤ 144
4. 0,5 x + 0,8y ≤ 10

Die Einschränkungen 1 und 2 stellen den Zustand der zuvor aufgedeckten Nicht-Negativität dar, und alle aufgeworfenen Ungleichungen sind linear. In den Einschränkungen 3 und 4 sind die Werte angegeben, die nicht überschritten werden dürfen: 144 Eier und 10 kg Zucker.

Zielfunktion

Schließlich ist die Zielfunktion der Gewinn, der bei der Herstellung der Menge „x“ Schwarzwälder Kuchen plus der Menge „y“ Sakripantine erzielt wird. Es wird gebaut, indem der Preis mit der Menge der hergestellten Kuchen multipliziert und für jeden Typ addiert wird. Es ist eine lineare Funktion, die wir G (x, y) nennen werden:

G = 8x + 10y

Lösungsmethoden

Die verschiedenen Lösungsmethoden umfassen grafische Methoden, den Simplex-Algorithmus und die Innenpunktmethode, um nur einige zu nennen.

- Grafische oder geometrische Methode

Wenn Sie ein Problem mit zwei Variablen wie das im vorherigen Abschnitt haben, bestimmen die Einschränkungen einen polygonalen Bereich in der xy-Ebene, der als realisierbarer Bereich oder Lebensfähigkeitsbereich bezeichnet wird.

Abbildung 3. Der mögliche Bereich, in dem die Lösung des Optimierungsproblems gefunden wird. Quelle: Wikimedia Commons.

Diese Region wird unter Verwendung der Restriktionslinien konstruiert, die die Linien sind, die aus den Ungleichungen der Restriktionen erhalten werden und nur mit dem Gleichheitszeichen arbeiten.

Bei der Bäckerei, die den Gewinn optimieren möchte, lauten die Beschränkungslinien:

1. x = 0
2. y = 0
3. 9x + 8y = 144
4. 0,5 x + 0,8y = 10

Alle Punkte in der von diesen Linien eingeschlossenen Region sind mögliche Lösungen, daher gibt es unendlich viele davon. Außer in dem Fall, in dem sich herausstellt, dass der realisierbare Bereich leer ist, hat das aufgeworfene Problem keine Lösung.

Glücklicherweise ist für das Gebäckproblem die realisierbare Region nicht leer, wir haben sie unten.

Abbildung 4. Der mögliche Bereich des Gebäckproblems. Die Linie mit der Verstärkung 0 kreuzt den Ursprung. Quelle: F. Zapata mit Geogebra.

Die optimale Lösung, falls vorhanden, wird mit Hilfe der Zielfunktion gefunden. Wenn wir beispielsweise versuchen, den maximalen Gewinn G zu ermitteln, haben wir die folgende Zeile, die als Iso-Profit-Zeile bezeichnet wird:

G = k ₁ x + k ₂ y → y = -k ₁ x / k ₂ + G / k ₂

Mit dieser Linie erhalten wir alle Paare (x, y), die eine gegebene Verstärkung G liefern. Es gibt also eine Familie von Linien gemäß dem Wert von G, aber alle mit der gleichen Steigung -k ₁ / k ₂ , also sind sie es parallele Linien.

Die optimale Lösung

Nun kann gezeigt werden, dass die optimale Lösung eines linearen Problems immer ein Extrempunkt oder Scheitelpunkt des realisierbaren Bereichs ist. So:

Wenn die Linie, die dem Ursprung am nächsten liegt, ein ganzes Segment mit der realisierbaren Region gemeinsam hat, wird gesagt, dass es unendlich viele Lösungen gibt. Dieser Fall tritt auf, wenn die Steigung der Iso-Profit-Linie gleich der einer der anderen Linien ist, die die Region begrenzen.

Für unser Gebäck sind die Eckpunkte A, B und C.

- Dantzigs Simplex-Methode

Die grafische oder geometrische Methode ist für zwei Variablen anwendbar. Es ist jedoch komplizierter, wenn drei Variablen vorhanden sind, und es ist unmöglich, sie für eine größere Anzahl von Variablen zu verwenden.

Bei Problemen mit mehr als zwei Variablen wird die Simplex-Methode verwendet, die aus einer Reihe von Algorithmen zur Optimierung der Zielfunktionen besteht. Zur Durchführung der Berechnungen werden häufig Matrizen und einfache Arithmetik verwendet.

Die Simplex-Methode beginnt mit der Auswahl einer praktikablen Lösung und der Überprüfung, ob diese optimal ist. Wenn dies der Fall ist, haben wir das Problem bereits gelöst. Wenn dies nicht der Fall ist, gehen wir weiter zu einer Lösung, die der Optimierung näher kommt. Wenn die Lösung vorhanden ist, findet der Algorithmus sie in wenigen Versuchen.

Anwendungen

Lineare und nichtlineare Programmierung werden in vielen Bereichen angewendet, um die besten Entscheidungen hinsichtlich Kostensenkung und Gewinnsteigerung zu treffen, was nicht immer monetär ist, da sie beispielsweise zeitlich gemessen werden können, wenn Sie die erforderliche Zeit minimieren möchten eine Reihe von Operationen durchzuführen.

Hier sind einige Felder:

-Im Marketing wird es verwendet, um die beste Kombination von Medien (soziale Netzwerke, Fernsehen, Presse und andere) zu finden, um für ein bestimmtes Produkt zu werben.

-Für die Zuweisung angemessener Aufgaben an das Personal eines Unternehmens oder einer Fabrik oder an Zeitpläne.

-In der Auswahl der nahrhaftesten Lebensmittel und zu den niedrigsten Kosten in der Vieh- und Geflügelindustrie.

Gelöste Übungen

- Übung 1

Lösen Sie das in den vorhergehenden Abschnitten erwähnte lineare Programmiermodell grafisch.

Lösung

Es ist erforderlich, den Wertesatz grafisch darzustellen, der durch das im Problem angegebene System von Einschränkungen bestimmt wird:

1. x ≥ 0
2. und ≥0
3. 9x + 8y ≤ 144
4. 0,5 x + 0,8y ≤ 10

Der durch die Ungleichungen 1 und 2 gegebene Bereich entspricht dem ersten Quadranten der kartesischen Ebene. In Bezug auf die Ungleichungen 3 und 4 beginnen wir mit der Ermittlung der Restriktionslinien:

9x + 8y = 144

0,5 x + 0,8y = 10 → 5x + 8y = 100

Der mögliche Bereich ist ein Viereck, dessen Eckpunkte die Punkte A, B, C und D sind.

Der minimale Gewinn ist 0, daher ist die Linie 8x + 10y = 0 die Untergrenze und die Iso-Profit-Linien haben eine Steigung von -8/10 = - 0,8.

Dieser Wert unterscheidet sich von den Steigungen der anderen Beschränkungslinien, und da der realisierbare Bereich begrenzt ist, existiert die eindeutige Lösung.

Abbildung 5. Grafische Lösung von Übung 1, die den realisierbaren Bereich und den Lösungspunkt C an einem der Eckpunkte dieses Bereichs zeigt. Quelle: F. Zapata.

Diese Lösung entspricht einer Steigungslinie von -0,8, die durch einen der Punkte A, B oder C verläuft, deren Koordinaten sind:

A (11; 5,625)

B (0; 12,5)

C (16, 0)

Optimale Lösung

Wir berechnen den Wert von G für jeden dieser Punkte:

(11; 5,625) -: G _A = 8 x 11 + 10 x 5,625 = 144,25

- (0; 12,5): G _B = 8 x 0 + 10 x 12,5 = 125

- (16, 0): G _C = 8 × 16 + 10 × 0 = 128

Der höchste Gewinn wird bei der Herstellung von 11 Schwarzwälder Kuchen und 5.625 Sakripantinkuchen erzielt. Diese Lösung stimmt mit der durch die Software gefundenen überein.

- Übung 2

Überprüfen Sie das Ergebnis der vorherigen Übung mithilfe der Solver-Funktion, die in den meisten Tabellenkalkulationen wie Excel oder LibreOffice Calc verfügbar ist und den Simplex-Algorithmus zur Optimierung in der linearen Programmierung enthält.

Lösung

Abbildung 6. Detail der Lösung aus Übung 1 über die Libre Office Calc-Tabelle. Quelle: F. Zapata.

Abbildung 7. Detail der Lösung aus Übung 1 über die Libre Office Calc-Tabelle. Quelle: F. Zapata.

Verweise

1. Brillant. Lineares Programmieren. Wiederhergestellt von: brillant.org.
2. Eppen, G. 2000. Operations Research in Administrative Science. 5 .. Auflage. Prentice Hall.
3. Haeussler, E. 1992. Mathematik für Management und Wirtschaft. 2 .. Auflage. Grupo Editorial Iberoamericana.
4. Hiru.eus. Lineares Programmieren. Wiederhergestellt von: hiru.eus.
5. Wikipedia. Lineares Programmieren. Wiederhergestellt von: es. wikipedia.org.