|
|
| Zeile 1: |
Zeile 1: |
| | = Lineares Optimierungsproblem = |
| | |
| == 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) |
| | |
| | === Allgemeine Form === |
| | Maximiere bzw. minimiere die Zielfunktion |
| | :<math>Z = c_1x_1 + c_2x_2 + \dots + c_nx_n</math> |
|
| |
|
| Ein Lineares Optimierungsproblem besteht aus drei Hauptkomponenten:
| | unter den Nebenbedingungen |
| # '''Zielfunktion''': Eine Funktion, deren Wert entweder maximiert (z. B. [[Gewinnfunktion]] oder [[Erlösfunktion]]) oder minimiert (z. B. [[Kostenfunktion]]) werden soll.
| | :<math> |
| # '''Bedingungssystem (Nebenbedingungen)''': Ein System von linearen Ungleichungen, das die verfügbaren Ressourcen wie Maschinenkapazitäten, Materialvorräte oder Arbeitszeit beschreibt (siehe auch [[Kapazitätsgrenze]]).
| | \begin{aligned} |
| # '''Nichtnegativitätsbedingungen (NNB)''': Da in wirtschaftlichen Kontexten keine negativen Mengen produziert werden können, muss für alle Entscheidungsvariablen gelten: \(x_i \ge 0\).
| | 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> |
|
| |
|
| Es wird unterschieden zwischen:
| | sowie den '''Nichtnegativitätsbedingungen''' |
| * '''Maximierungsproblem''': Ziel ist das Erreichen des höchsten Wertes (z. B. Deckungsbeitragsmaximierung).
| | :<math>x_1 \ge 0,\; x_2 \ge 0,\; \dots</math> |
| * '''Minimierungsproblem''': Ziel ist das Erreichen des geringsten Wertes (z. B. Kostenminimierung beim Einsatzproblem).
| |
|
| |
|
| == Modellierung ökonomischer Prozesse ==
| | Die Menge aller zulässigen Lösungen heißt '''zulässiger Bereich'''. |
| 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.
| |
|
| |
|
| == Beispiel == | | == Ökonomische Interpretation == |
| Die '''Modellwerk Ruhr GmbH''' produziert zwei Spielzeugmodelle:
| | * Zielfunktion: [[Gewinnfunktion]] oder Erlösfunktion |
| * '''Kran''': 40 € Deckungsbeitrag (DB) pro Stück. | | * Nebenbedingungen: Kapazitätsgrenzen (vgl. [[Kapazitätsgrenze]]) |
| * '''Lok''': 50 € DB pro Stück. | | * Variablen: Produktionsmengen |
|
| |
|
| Die Produktion ist durch zwei Abteilungen begrenzt:
| | == Grafische Lösung == |
| # Holzbearbeitung: \(2x_1 + 1x_2 \le 100\) Stunden
| | Bei zwei Entscheidungsvariablen kann das Problem grafisch gelöst werden: |
| # 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!}\)
| | * Zeichnen der Nebenbedingungen als Geraden (vgl. [[Lineare Funktion]]) |
| | * Bestimmung des zulässigen Bereichs |
| | * Untersuchung der Eckpunkte (vgl. [[Eckpunktberechnungsmethode]]) |
|
| |
|
| | == Beispiel (Gewinnmaximierung) == |
| | Ein Unternehmen produziert zwei Produkte: |
| | |
| | * 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> |
| | |
| | === Grafische Darstellung (JSXGraph) === |
| <html> | | <html> |
| <head> | | <head> |
| <script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/jsxgraph/1.4.6/jsxgraphcore.js"></script>
| | <script src="https://cdnjs.cloudflare.com/ajax/libs/jsxgraph/1.4.6/jsxgraphcore.js"></script> |
| <link rel="stylesheet" type="text/css" href="https://cdnjs.cloudflare.com/ajax/libs/jsxgraph/1.4.6/jsxgraph.css" />
| |
| </head> | | </head> |
| <body> | | <body> |
| <div id=" box_lop" class="jxgbox" style="width: 400px; height: 400px; margin-top:20px;"></div> | | <div id="lp1" style="width:400px;height:300px;"></div> |
| <script type="text/javascript">
| | <script> |
| (function() {
| | var board = JXG.JSXGraph.initBoard('lp1',{ |
| var board = JXG.JSXGraph.initBoard('box_lop', {
| | boundingbox:[-1,9,9,-1], axis:true, grid:true |
| boundingbox: [-10, 110, 110, -10],
| | }); |
| axis: true,
| | |
| showCopyright: false
| | var g1 = board.create('line', [[0,8],[4,0]]); |
| });
| | var g2 = board.create('line', [[0,4],[8,0]]); |
| 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});
| | board.create('text',[5,5,'Zulässiger Bereich']); |
| board.create('polygon', [[0,0], [50,0], [40,20], [0,40]], {fillColor: '#0055aa', fillOpacity: 0.2, borders: {visible: false}});
| | </script> |
| var k = board.create('slider', [[10, 90], [60, 90], [0, 0, 3000]], {name: 'DB'});
| |
| board.create('line', [function(){ return -k.Value(); }, 40, 50], {strokeColor: 'green', dash: 2, name: 'Zielfunktion', withLabel: true});
| |
| })();
| |
| </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]] |
