Wie Lineares Programm formulieren?

Question

Aufgabe:

Ein Papierfabrikant stellt Papierrollen mit einer Standardbreite von 105 cm und einer Länge von L cm her. Die Kunden verlangen jedoch Rollen der Länge L cm mit geringerer Breite. Es liegen folgende Aufträge vor:

- 100 Rollen 25 cm breit,

- 125 Rollen 30 cm breit,

- 80 Rollen 35 cm breit.

Zur Erledigung der Aufträge werden Standardrollen zerschnitten. Zum Beispiel kann der Fabrikant aus einer Papierrolle mit Standardbreite zwei Rollen von je 35 cm Breite und eine Rolle von 30 cm Breite schneiden. Das ergibt einen Schnittverlust von 5×L cm2. Ziel des Fabrikanten ist die Minimierung der Schnittverluste für die vorliegenden Aufträge.

Formulieren Sie dieses Problem als lineares Programm.

Ansatz,Problem:

NNB

\(x_{1}, x_{2}, x_{3} \geq 0\)

Wie ich den Rest formulieren soll bin ich mir nicht sicher.

Comments

Man kann verlustfrei 78 Rollen mit 35 cm Breite herstellen.

Dann bleiben noch herzustellen:
- 100 Rollen 25 cm breit,
- 125 Rollen 30 cm breit,
- 2 Rollen 35 cm breit.

Man kann verlustfrei 99 Rollen mit 25 cm Breite und 33 Rollen mit 30 cm herstellen.

Dann bleiben:
- 1 Rolle 25 cm breit,
- 92 Rollen 30 cm breit,
- 2 Rollen 35 cm breit.

Es braucht 91 Rohlinge.

---

Wie kommst du auf 78×35, 99×25 und 33×30?

---

Hallo

Man muss ja mindestens 125 Rollen zerschneiden für die 30cm. dann bleiben 125 Rollen mit 75cm  für den Rest, versuche die zu verteilen, wenn das reicht ok , sonst weitere Rollen.

lul

---

Wie kann ich den so die Nebenbedingungen und eine Zielfunktion formulieren?

NNB:

\(x_{1}, x_{2}, x_{3} \geq 0\)

Entscheidungsvariablen:

X1=35cm

X2=30cm

X3=25cm

So würde ich die variablen und die NNB aufstellen, aber wie ich die Nebenbedingungen und die Zielfunktion formulieren soll, weiß ich nicht.

---

Wie kommst du auf 78×35, 99×25 und 33×30?

Man kann so einen Rohling in drei Stücke zu 35 cm zerschneiden.

Man kann ihn auch in drei Stücke zu 25 cm und ein Stück zu 30 cm zerschneiden.

Man muss ja mindestens 125 Rollen zerschneiden

Nein. Siehe oben: Es braucht 91 Rohlinge.

Ich denke, die einschlägige Publikation ist https://doi.org/10.1287/opre.9.6.849 von 1961.

---

Hier eine Lösung des linearen Problems. Die Matrix enthält die benutzbaren Schnittmuster und die Koeffizienten des linearen Optimierungsproblems.

---

Danke.

Bei der Lösung der Aufgabe geht es Primär nur um die Formulierung der Entscheidungsvariablen, Nebenbedingungen, NNB und Zielfunktion.

Woher kommen die zahlen für den 2. Vektor?

---

Du meinst den Vektor auf der Rechten Seite? Der Entsteht, wenn ich die Matrix und den Vektor auf der linken Seite des Gleichheitszeichen multipliziere. Und du siehst das damit die Nebenbedingungen erfüllt sind.

---

ich meine den vektor den du mit der matrix multiplizierst.

---

Den habe ich pi mal Daumen erstellt, sodass ich die Bedingungen erfülle und auf die 91 Rohlinge komme, die döschwo netterweise hat berechnen lassen.

Aber die Lösung sollte erstmal für dich uninteressant sein. Stelle das lineare Programm auf und wenn du Interesse hast löst du das mit einem Verfahren deiner Wahl. Dann solltest du doch eine ähnliche Lösung heraus bekommen.

---

Wegen der Zielfunktion

Mit den Zahlen von MC:

Benötigt werden 100*25+125*30+80*35=9050

Lösung sind 91 Rollen, ergibt 91*105 =9555 Verbrauch

Verschnitt: 505

Zielfunktion: 470

Also ergibt der Wert der Zielfunktion nicht den Verschnitt.

---

Du hast ja auch einen Denkfehler. Bei seiner Lösung kommen 81 Rollen mit 35 Meter heraus. Das erklärt die Differenz von 35. ;)

---

Ja, das heißt doch, dass 1 35-Rolle weggeworfen wird, also zum Verschnitt zu rechnen ist.

---

Dann sollte man eher die Nebenbedingung so formulieren, dass die Gleichheit erfüllt ist. Das bedarf dann keiner Anpassung der Zielfunktion. Dann stellt sich allerdings die Frage, ob es lösbar ist.

---

habe ich pi mal Daumen erstellt,

Ich würde stattdessen noch das Schnittmuster vorschlagen:

\( \begin{pmatrix} 0\\1\\1\\50 \end{pmatrix} \text{oder}  \begin{pmatrix} 2\\0\\0\\35 \end{pmatrix} \)

Ich schreibe nachher noch eine Antwort auf, ist ein bisschen eine Fummelei mit der Formatierung, und es ist gerade ziemlich laut im "Ruheabteil" meines Zuges - Fahrgäste aus "einem Nachbarland".

Answer 1

Überlege dir, welche Schnittmuster es gibt und stelle dann damit das lineare Programm auf.

Zum Beispiel:

1) 3 mal 35 cm = 105 cm, Rest: 0 cm, Kurzschreibweise: (0, 0, 3, 0). Dabei geben die ersten drei Zahlen die jeweilige Anzahl der Rollen an (25cm, 30cm, 35cm), die letzte Zahl gibt den Rest an.

2) 2 mal 35 cm, 1 mal 30 cm, Rest: 5 cm, kurz: (0, 1, 2, 5).

usw.

Wenn nun \(\mathbf{r}\) der Vektor der Reste und \(\mathbf{m}\) die Anzahl der jeweiligen Schnittmuster ist, dann

minimiere \(\mathbf{r}^T\cdot \mathbf{m}L\), so dass

\(m_i\geq 0\) für alle \(i\) und

\(A\mathbf{m}=\begin{pmatrix}100 \\125\\ 80 \end{pmatrix}\)

In der Matrix \(A\) stehen dann entsprechend die Anzahl der Rollen, die beim jeweiligen Schnittmuster erhalten werden. Dazu bietet es sich an, eine Tabelle anzufertigen.

Melde dich gerne, wenn du Fragen hast.

Streng genommen handelt es sich hier sogar um ein ganzzahliges lineares Programm, da die \(m_i\) ganzzahlige Werte sein müssen.

Comments

Überlege dir, welche Schnittmuster es gibt

muss ich alle Schnittmuster aufstellen oder reichen 4 z.B ?

Wenn ich die Aufgabe so wie du geschrieben hast löse, kann ich dann die Nebenbedingungen und Zielfunktion so aufstellen?

Nebenbedigungen:

x1≤ 10

Zielfunktion:

Z=30x

(Nur als Beispiel)

---

Es ist schon sinnvoll, alle möglichen Schnittmuster zu betrachten, um sicherzustellen, dass man nicht eine noch bessere Lösung vergisst. Aber so viele Schnittmuster gibt es ja nun auch nicht.

Du kannst die Nebenbedingungen natürlich auch als einzelne Ungleichungen ohne Matrix formulieren sowie die Zielfunktion ebenfalls. Mache dir dazu klar, was die verschiedenen Variablen bedeuten und wie die Bedingungen entsprechend formuliert werden müssen.

Eine Ungleichung der Form \(ax+b\geq c\) kann man durch Multiplikation mit -1 umformen in \(-ax-b\leq c\).

---

Ich habe Bedenken bei der Zielfunktion: Es könnte doch weiterer Verschnitt anfallen, wenn einige Rollen "angeschnitten" aber nicht vollständig verwertet werden. Meiner Meinung nach muss der Verschnitt angesetzt werden als Differenz der Anzahl der verwendeten Rollen mal Standardbreite und der benötigten Menge, also 100*25 + ...

---

Wären dann die Schnittmuster die Nebenbedingungen?

---

Die Anzahlen der Schnittmuster, also die \(m_i\) sind deine Variablen und die kommen natürlich in den Nebenbedingungen vor.

Ich habe Bedenken bei der Zielfunktion: Es könnte doch weiterer Verschnitt anfallen, wenn einige Rollen "angeschnitten" aber nicht vollständig verwertet werden. Meiner Meinung nach muss der Verschnitt angesetzt werden als Differenz der Anzahl der verwendeten Rollen mal Standardbreite und der benötigten Menge, also 100*25 + ...

Das leuchtet mir nicht so ganz ein. Wenn Rollen angeschnitten und nicht vollständig verwertet werden, ist doch gerade das der Rest oder eben auch Verschnitt genannt. Wenn ich jetzt also 20 mal Schnittmuster 2 von oben brauche, ergibt sich ja, dass der Verschnitt \(20\cdot 5=100L\) beträgt.

Ich habe mal noch die Variable \(L\) für die Länge einer Rolle hinzugefügt. Die spielt aber für das Optimierungsproblem keine Rolle. Der Vollständigkeit halber sollte sie aber dennoch in der Zielfunktion auftauchen.

---

35=x1 , 30=x2 , 25=x3

wäre das falsch, wenn das meine variablen wären?

---

Das ist hochgradig falsch, denn wozu brauchst du noch ein lineares Programm, wenn du direkt die Variablen mit einem festen Wert angeben kannst. Das ergibt keinen Sinn. Und was sollen die Variablen überhaupt angeben?

Ich verstehe aber auch nicht, wieso du das Vorgehen meiner Antwort einfach ignorierst.

Answer 2

Mit einem linearen Programm auf ganze Zahlen zu optimieren braucht es mehrere Durchläufe (aufwendig - ob die Aufgabe so gemeint ist?), da schau ich erstmal bei XL vorbei - der Solver kommt auf insgesamt 89 Rollen

\(\small\begin{array}{|r|r|r|r|r|r|r|r|r|r|} \hline Längen & Anzahl & Schnittmuster & 105 & 105 & 105 & 105 & 105 & 105 & 105 \\ \hline 25 & 100 & 100 & 4 & 3 & 1 & 0 & 0 & 0 & 1 \\ \hline 30 & 120 & 120 & 0 & 1 & 1 & 2 & 1 & 0 & 0 \\ \hline 35 & 80 & 80 & 0 & 0 & 1 & 1 & 2 & 3 & 2 \\ \hline & & \red{89} & \red{1} & \red{32} & 0 & \red{32} & \red{24} & 0 & 0 \\ \hline Waste & & & 5 & 0 & 15 & 10 & 5 & 0 & 10 \\ \hline \mathbf{4 4 5}  & & & 5 & 0 & 0 & 320 & 120 & 0 & 0 \\ \hline \end{array}\)

Interessanter Weise lässt er die 3x35cm aus...

um der neben Lösung von MC noch einen Vorschlag zu machen

Comments

Würdest du die Frage lesen, wüsstest du, dass die Aufgabe nicht so gemeint ist, da es gar nicht darum geht, das Problem zu lösen, sondern lediglich darum, ein lineares Programm aufzustellen. Deine Antwort zielt also nicht auf die Frage ab.

Zu allem Überfluss arbeitest du auch nur mit 120 30er Rollen statt der geforderten 125 Rollen, was die Diskrepanz zur Lösung von MC erklärt.

Answer 3

Wenn man sich vorerst die verlinkte Literatur (die allerdings zielführend ist) nicht zumuten möchte, sondern ein herkömmliches LP aufstellen will (wogegen es gute Gründe gibt, die in der verlinkten Literatur erklärt werden), dann sollte man alle Schnittmuster in Betracht ziehen, nicht nur die von denen man meint, sie seinen sinnvoll.

Schnittmuster:

Name	Anzahl Stücke vom Rohling	35 cm	30 cm	25 cm	Verschnitt
A	1	1			70
B	1		1		75
C	1			1	80
D	2	2			35
E	2		2		45
F	2			2	55
G	2	1	1		40
H	2	1		1	45
I	2		1	1	50
K	3	3			0
M	3		3		15
N	3			3	30
P	3	2	1		5
Q	3	2		1	10
R	3	1	2		10
S	3		2	1	20
T	3	1		2	20
U	3		1	2	25
V	4			4	5
W	4		1	3	0

Wenn a die Anzahl Rohlinge sind, die nach Schnittmuster A zerschnitten werden, usw., dann ist die Zielfunktion:

minimiere Verschnitt(a, b, ... w) = 70a + 75b + 80c + 35d + 45e + 55f + 40g + 45h + 50i + 0k + 15m + 30n + 5p + 10q + 10r + 20s + 20t + 25u + 5v

s.t.

a + 2d + g + h + 3k + 2p + 2q + r + t = 80
b + 2e + g + i + 3m + p + 2r + 2s + u + w = 125
c + 2f + h + i + 3n + q + s + 2t + 2u + 4v + 3w = 100
Nichtnegativitätsbedingungen
ganzzahlig

Es gibt mehrere Lösungen für das Minimum 505, bspw.:

d = 1, k = 26, m = 31, v = 1, w = 32
oder
i = 1, k = 26, m = 29, r = 2, w = 33