Antwort mit KI erzeugt
Numerik: Maximierungsproblem bei Programmierpraktikum. Fertigung mit n Maschinen
Bei dem betrachteten Fall handelt es sich um ein lineares Programmierungsproblem, das sich durchaus als Maximierungsproblem formulieren lässt. Konkret soll der monatliche Gesamtertrag optimiert werden, während die maximalen Laufzeiten der Maschinen nicht überschritten werden dürfen. Lass uns die Aufgabe in zwei Teile gliedern, entsprechend deiner Fragen.
i) Formulierung des Maximierungsproblems
Zunächst definieren wir die Variablen und Funktionen, die zur Formulierung des Problems wichtig sind:
- \(x = (x_1, x_2, ..., x_m)\) repräsentiert die monatlich gefertigten Mengeneinheiten der \(m\) verschiedenen Produkte.
- \(e = (e_1, e_2, ..., e_m)\) gibt den Ertrag pro Mengeneinheit der jeweiligen Produkte an. Also ist \(c = e\).
- \(A = (t_{jk})\) ist eine Matrix, die die benötigten Zeiten der \(n\) Maschinen für jedes der \(m\) Produkte beschreibt; \(t_{jk}\) bezeichnet die Zeit, die die \(j\)-te Maschine für die Produktion einer Einheit des \(k\)-ten Produktes benötigt.
Das Maximierungsproblem lässt sich dann wie folgt formulieren:
Maximiere die Funktion \(f(x) = e \cdot x\), unter den Nebenbedingungen, dass \(Ax \leq b\) und \(x \geq 0\), wobei:
- \(b = (l_1, l_2, ..., l_n)^T\) die maximalen monatlichen Laufzeiten der \(n\) Maschinen in Stunden angibt.
Hierbei ist \(e \cdot x\) das Skalarprodukt von \(e\) und \(x\), welches den gesamten Ertrag repräsentiert. Die Nebenbedingung \(Ax \leq b\) sichert, dass die gesamten monatlichen Betriebszeiten der Maschinen die maximal zur Verfügung stehenden Stunden nicht überschreiten. Genauer formuliert bedeutet dies für jede Maschine \(j\):
\(\sum_{k=1}^{m} t_{jk} \cdot x_k \leq l_j\)
Somit ist deine Überlegung bezüglich der Nebenbedingungen im Grunde richtig, wobei die korrekte Formulierung der Ungleichung für jede Maschine \(j\) ist:
\(\sum_{k=1}^{m} t_{jk} \cdot x_k \leq l_j\).
ii) Nutzung der Matlab-Routine linprog
Für die Lösung dieses Problems mit Matlab kann die linprog
-Funktion verwendet werden. Die Syntax für linprog
sieht in etwa so aus:
matlab
x = linprog(f, A, b, Aeq, beq, lb, ub);
In unserem Fall benötigen wir:
- f
ist der zu minimierende Kostenvektor, also \(-e\) (da linprog
eine Minimierung durchführt, während wir maximieren wollen).
- A
und b
sind wie oben definiert.
- Aeq
und beq
werden nicht benötigt, da keine Gleichheitsbedingungen vorliegen.
- lb
ist der Vektor der unteren Schranken für \(x\), welcher in diesem Fall Nullen enthält.
- ub
kann undefiniert bleiben, wenn es keine obere Schranke für die Produktionsmengen gibt.
Die tatsächliche Implementierung variiert basierend auf deinen spezifischen Daten. Hier ein vereinfachtes Beispiel:
matlab
e = [-e1; -e2; ...; -em]; % Kostenvektor für linprog
A = [t11, t12, ..., t1m;
t21, t22, ..., t2m;
...
tn1, tn2, ..., tnm]; % Matrix der Zeiten
b = [l1; l2; ...; ln]; % Vektor der maximalen Laufzeiten
lb = zeros(m, 1); % untere Schranken
[x, fval] = linprog(e, A, b, [], [], lb, []);
optimaler_Ertrag = -fval;
Der optimale monatliche Ertrag (optimaler_Ertrag
) resultiert aus der Optimierung. Da linprog
eine Minimierung durchführt und unser Problem eine Maximierungsaufgabe ist, minimieren wir den negativen Ertrag, wodurch fval
auch negativ ist. Dessen Negation gibt uns den gesuchten maximalen Ertrag.