Lineares Optimierungsproblem: Unterschied zwischen den Versionen

Aus FLBK-Wiki
Zur Navigation springen Zur Suche springen
← Zum vorherigen Versionsunterschied
Flbkwikiadmin (Diskussion | Beiträge)
Bürokraten, Oberflächenadministratoren, Administratoren
2.097 Bearbeitungen
VisuellWikitext
 
(7 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 1: Zeile 1:
== Definition ==
== Definition ==
Ein '''Lineares Optimierungsproblem''' ist eine mathematische Aufgabenstellung, bei der eine lineare Zielfunktion unter Berücksichtigung von linearen Nebenbedingungen (Einschränkungen) optimiert werden soll.
Ein '''lineares Optimierungsproblem''' besteht aus einer '''Zielfunktion''' und einem System von '''einschränkenden Bedingungen''' (Nebenbedingungen), die alle linear sind.
 
Man unterscheidet:
 
* '''Maximierungsprobleme''' (z. B. Maximierung von Gewinn oder Deckungsbeitrag)
* '''Minimierungsprobleme''' (z. B. Minimierung von Kosten oder Transportaufwand)
 
Maximiere bzw. minimiere die Zielfunktion
:<math>Z = c_1x_1 + c_2x_2 + \dots + c_nx_n</math>
 
unter den Nebenbedingungen
:<math>
\begin{aligned}
a_{11}x_1 + a_{12}x_2 &\le b_1\\
a_{21}x_1 + a_{22}x_2 &\le b_2\\
\vdots
\end{aligned}
</math>
 
sowie den '''Nichtnegativitätsbedingungen'''
:<math>x_1 \ge 0,\; x_2 \ge 0,\; \dots</math>


Ein LOP besteht aus drei Hauptkomponenten:
Die Menge aller zulässigen Lösungen heißt '''zulässiger Bereich'''.
# '''Zielfunktion''': Eine Funktion, deren Wert entweder maximiert (z. B. [[Gewinnfunktion]] oder [[Erlösfunktion]]) oder minimiert (z. B. [[Kostenfunktion]]) werden soll.
# '''Bedingungssystem (Nebenbedingungen)''': Ein System von linearen Ungleichungen, das die verfügbaren Ressourcen wie Maschinenkapazitäten, Materialvorräte oder Arbeitszeit beschreibt (siehe auch [[Kapazitätsgrenze]]).
# '''Nichtnegativitätsbedingungen (NNB)''': Da in wirtschaftlichen Kontexten keine negativen Mengen produziert werden können, muss für alle Entscheidungsvariablen gelten: \(x_i \ge 0\).


Es wird unterschieden zwischen:
== Ökonomische Interpretation ==
* '''Maximierungsproblem''': Ziel ist das Erreichen des höchsten Wertes (z. B. Deckungsbeitragsmaximierung).
* Zielfunktion: [[Gewinnfunktion]] oder Erlösfunktion
* '''Minimierungsproblem''': Ziel ist das Erreichen des geringsten Wertes (z. B. Kostenminimierung beim Einsatzproblem).
* Nebenbedingungen: Kapazitätsgrenzen (vgl. [[Kapazitätsgrenze]])
* Variablen: Produktionsmengen


== Modellierung ökonomischer Prozesse ==
== Grafische Lösung ==
Um ein reales Problem mathematisch abzubilden, werden Entscheidungsvariablen definiert (z. B. \(x_1\) für Produkt A, \(x_2\) für Produkt B). Die sprachlichen Informationen werden dann in ein mathematisches Modell übersetzt, das oft die Form eines [[Lineares Gleichungssystem|linearen Systems]] annimmt, jedoch mit Ungleichungen statt Gleichungen.
Bei zwei Entscheidungsvariablen kann das Problem grafisch gelöst werden:


== Beispiel ==
* Zeichnen der Nebenbedingungen als Geraden (vgl. [[Lineare Funktion]])
Die '''Modellwerk Ruhr GmbH''' produziert zwei Spielzeugmodelle:
* Bestimmung des zulässigen Bereichs
* '''Kran''': 40 € Deckungsbeitrag (DB) pro Stück.
* Untersuchung der Eckpunkte (vgl. [[Eckpunktberechnungsmethode]])
* '''Lok''': 50 € DB pro Stück.


Die Produktion ist durch zwei Abteilungen begrenzt:
== Beispiel==
# Holzbearbeitung: \(2x_1 + 1x_2 \le 100\) Stunden
Ein Unternehmen produziert zwei Produkte:
# Endmontage: \(1x_1 + 2x_2 \le 80\) Stunden
# NNB: \(x_1, x_2 \ge 0\)


Die Zielfunktion lautet: \(z = 40x_1 + 50x_2 \rightarrow \text{max!}\)
* Gewinn pro Stück A: 3 GE
* Gewinn pro Stück B: 5 GE
 
Nebenbedingungen:
:<math>
\begin{aligned}
2x + y &\le 8\\
x + 2y &\le 8\\
x,y &\ge 0
\end{aligned}
</math>
 
Zielfunktion:
:<math>Z = 3x + 5y \rightarrow \max</math>


<html>
<html>
Zeile 34: Zeile 63:
     <div id="box_lop" class="jxgbox" style="width: 400px; height: 400px; margin-top:20px;"></div>
     <div id="box_lop" class="jxgbox" style="width: 400px; height: 400px; margin-top:20px;"></div>
     <script type="text/javascript">
     <script type="text/javascript">
         (function() {
         (function () {
             var board = JXG.JSXGraph.initBoard('box_lop', {
             var board = JXG.JSXGraph.initBoard('box_lop', {
                 boundingbox: [-10, 110, 110, -10],
                 boundingbox: [-1, 9, 9, -1],
                 axis: true,
                 axis: true,
                 showCopyright: false
                grid: true,
                 showCopyright: false,
                defaultAxes: {
                    x: {
                        withLabel: true,
                        name: 'x',
                        label: { position: 'rt', offset: [-10, 15] }
                    },
                    y: {
                        withLabel: true,
                        name: 'y',
                        label: { position: 'rt', offset: [10, -5] }
                    }
                }
            });
 
            // Nebenbedingung: 2x + y = 8  -> y = -2x + 8
            var nb1 = board.create('functiongraph', [
                function (x) { return -2 * x + 8; }
            ], {
                strokeColor: 'red',
                name: '2x + y = 8',
                withLabel: true,
                label: { offset: [-60, 20] }
            });
 
            // Nebenbedingung: x + 2y = 8  -> y = -0.5x + 4
            var nb2 = board.create('functiongraph', [
                function (x) { return -0.5 * x + 4; }
            ], {
                strokeColor: 'blue',
                name: 'x + 2y = 8',
                withLabel: true,
                label: { offset: [10, -20] }
            });
 
            // Zulässiger Bereich
            board.create('polygon', [
                [0, 0],
                [4, 0],
                [8 / 3, 8 / 3],
                [0, 4]
            ], {
                fillColor: '#0055aa',
                fillOpacity: 0.2,
                borders: { visible: false }
            });
 
            // Slider für Zielfunktion Z = 3x + 5y
            var Z = board.create('slider', [[0.5, 8.6], [6.5, 8.6], [0, 0, 40]], {
                name: 'Z'
             });
             });
             var f1 = board.create('line', [[0, 100], [50, 0]], {straightFirst:false, straightLast:false, strokeColor:'red', name:'Holz', withLabel:true});
 
            var f2 = board.create('line', [[0, 40], [80, 0]], {straightFirst:false, straightLast:false, strokeColor:'blue', name:'Montage', withLabel:true});
             // Zielfunktion: 3x + 5y = Z  -> y = (Z - 3x)/5
             board.create('polygon', [[0,0], [50,0], [40,20], [0,40]], {fillColor: '#0055aa', fillOpacity: 0.2, borders: {visible: false}});
             board.create('functiongraph', [
            var k = board.create('slider', [[10, 90], [60, 90], [0, 0, 3000]], {name: 'DB'});
                function (x) { return (Z.Value() - 3 * x) / 5; }
            board.create('line', [function(){ return -k.Value(); }, 40, 50], {strokeColor: 'green', dash: 2, name: 'Zielfunktion', withLabel: true});
            ], {
                strokeColor: 'green',
                dash: 2,
                name: 'Zielfunktion',
                withLabel: true
            });
 
         })();
         })();
     </script>
     </script>
</body>
</body>
</html>
</html>
== Zusammenhang zu anderen Themen ==
* Lösung von Gleichungssystemen: [[Lineares Gleichungssystem]]
* Darstellung in Tabellenform: [[Matrix]]


[[Kategorie:Lineare_Optimierung]]
[[Kategorie:Lineare_Optimierung]]
[[Kategorie:AHR_WuV_Mathe_GK]]
[[Kategorie:AHR_WuV_Mathe_GK]]

Aktuelle Version vom 6. Februar 2026, 09:20 Uhr

Definition

Ein lineares Optimierungsproblem besteht aus einer Zielfunktion und einem System von einschränkenden Bedingungen (Nebenbedingungen), die alle linear sind.

Man unterscheidet:

  • Maximierungsprobleme (z. B. Maximierung von Gewinn oder Deckungsbeitrag)
  • Minimierungsprobleme (z. B. Minimierung von Kosten oder Transportaufwand)

Maximiere bzw. minimiere die Zielfunktion

[math]\displaystyle{ Z = c_1x_1 + c_2x_2 + \dots + c_nx_n }[/math]

unter den Nebenbedingungen

[math]\displaystyle{ \begin{aligned} a_{11}x_1 + a_{12}x_2 &\le b_1\\ a_{21}x_1 + a_{22}x_2 &\le b_2\\ \vdots \end{aligned} }[/math]

sowie den Nichtnegativitätsbedingungen

[math]\displaystyle{ x_1 \ge 0,\; x_2 \ge 0,\; \dots }[/math]

Die Menge aller zulässigen Lösungen heißt zulässiger Bereich.

Ökonomische Interpretation

Grafische Lösung

Bei zwei Entscheidungsvariablen kann das Problem grafisch gelöst werden:

Beispiel

Ein Unternehmen produziert zwei Produkte:

  • Gewinn pro Stück A: 3 GE
  • Gewinn pro Stück B: 5 GE

Nebenbedingungen:

[math]\displaystyle{ \begin{aligned} 2x + y &\le 8\\ x + 2y &\le 8\\ x,y &\ge 0 \end{aligned} }[/math]

Zielfunktion:

[math]\displaystyle{ Z = 3x + 5y \rightarrow \max }[/math]

Zusammenhang zu anderen Themen

Abgerufen von „https://wiki.flbk-hamm.de/index.php?title=Lineares_Optimierungsproblem&oldid=2663“