+1 Daumen
349 Aufrufe
Wir haben im Numerik-Programmierpraktikum diese Aufgabe bekommen:

Eine Firma stellt m verschieden Produkte her, für deren Fertigung n Maschinen benötigt werden. Die j-te Maschine hat eine maximale monatliche Laufzeit von l_j Stunden. Das k-te Produkt generiert pro ME einen Ertrag e_k Euro und belegt die j-te Maschine t_jk h pro ME.

Der monatliche Gesamtertrag soll ohne Überschreitung der Maxiallaufzeiten optimiert werden.

i) Formulieren Sie den beschriebenen Sachverhalt als Maximierungsproblem mit Nebenbedingungen in der Form:

Maximiere f(x) = c* x unter den Bedingungen Ax <= b, x >= 0

wobei x = (x_1, x_2, ..., x_m) die monatlichen Mengeneinheiten der verschiedenen Produkte seien und die Ungleichungen komponentenewise zu verstehen sind.

ii) Verwenden Sie die Matlab-Routine linprog. um das Problem für verschiedene Testdaten zu lösen. Wie groß ist der optimale monatliche Ertrag?

Jetzt meine Frage:

Ich habe mir bereits überlegt, dass die Formel vermutlich f(x) = c * x sein muss.
Bei den Nebenbedingungen bin ich mir allerdings sehr unsicher.
Stimmt : Die Summe über alle t_jk <= l_j?
Avatar von

1 Antwort

0 Daumen

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.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community