Eindimensionales Zuschnittsproblem

11.10.2021, 09:51

Ploki

Eindimensionales Zuschnittsproblem

Meine Frage:
[attach]53773[/attach]

Meine Ideen:
Liebes Matheboard!

Ich bin, was lineare Optimierung angeht, kein Spezialist und benötige bei dieser Aufgabe ein wenig Hilfe. Ich habe die Fragestellung und meinen bisweiligen Lösungsansatz in einem LaTeX-Dokument zusammengefasst und hier angehängt. Folgendes ist mir unklar:

(1) Ich hab ein Bauchgefühl, dass ich mit meinem Ansatz tatsächlich alle Varianten benötigen werde, auch die verschnittreichen, wie etwa $\begin{eqnarray*} a = \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} \end{eqnarray*}$

(2) Würde mein Gleichungssystem so schon ausreichen, um es mit einem Programm, wie SageMath oder Matlab, zu lösen?

(3) Was passiert, wenn ich bei den Nebenbedingungen das $\begin{eqnarray*} = \end{eqnarray*}$ durch ein $\begin{eqnarray*} \geq \end{eqnarray*}$ ersetze?

EDIT: Wahrscheinlich gehört meine Aufgabenstellung eher in das Forum der Linearen Algebra.

11.10.2021, 15:09

Huggy

Auf diesen Beitrag antworten »

RE: Eindimensionales Zuschnittsproblem
In deiner Nebenbedingung sollte die Zahl der Stäbe stehen und nicht die Länge der Stäbe.

Es scheint mir nicht sinnvoll, bestimmte Varianten von vorneherein auszuschließen. Da kann man leicht Fehler machen. Mit Mathematica bin ich auf folgende Lösung gekommen:

$\begin{eqnarray*} 49\begin{pmatrix} 0 \\ 0 \\ 4 \end{pmatrix}+26\begin{pmatrix} 0 \\ 3\\ 0 \end{pmatrix}+1\begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}+1\begin{pmatrix} 2 \\ 0 \\ 0 \end{pmatrix}+59\begin{pmatrix} 2\\ 0 \\ 1 \end{pmatrix} \end{eqnarray*}$

11.10.2021, 18:17

Ploki

Auf diesen Beitrag antworten »

RE: Eindimensionales Zuschnittsproblem
Ja natürlich! Habe den falschen Vektor angegeben. Danke für den Hinweis!

Na gut, dann werde ich noch alle verschnittreichen Varianten miteinschließen - habs mir eh gedacht.

Welchen Algorithmus hast du verwendet? Simplex?

LG Ploki

11.10.2021, 20:01

Huggy

Auf diesen Beitrag antworten »

RE: Eindimensionales Zuschnittsproblem

Zitat:

Original von Ploki
Welchen Algorithmus hast du verwendet? Simplex?

Ich habe mir die Sache einfach gemacht und eine der in Mathematica für solche Probleme vorhandenen Funktionen benutzt.

12.10.2021, 10:57

Ploki

Auf diesen Beitrag antworten »

Vielen Dank Huggy!

12.10.2021, 12:28

Huggy

Auf diesen Beitrag antworten »

RE: Eindimensionales Zuschnittsproblem

Zitat:

Original von Ploki
(2) Würde mein Gleichungssystem so schon ausreichen, um es mit einem Programm, wie SageMath oder Matlab, zu lösen?

Zwar kenne ich beide Programme nicht, aber es ist wahrscheinlich, dass sie auch fertige Funktionen haben, um solche Probleme zu lösen. Es ist schon aufwendig, so etwas selbst zu programmieren und ganz besonders, wenn nur ganzzahlige Lösungen erlaubt sind.

13.10.2021, 12:46

hawe

Auf diesen Beitrag antworten »

RE: Eindimensionales Zuschnittsproblem
Das in der Aufgabenstellung angegebene Schnittmuster enthält (2,0,0) (Huggy's Lösung) nicht. Mit den gegebenen Schnittmustern hab ich den XL Solver befragt und der kommt auf immer auf 136 Stangen egal ob mal die gewünschte Stückzahl = oder <= ansetzt.

[attach]53783[/attach]

13.10.2021, 13:19

Huggy

Auf diesen Beitrag antworten »

RE: Eindimensionales Zuschnittsproblem

Zitat:

Original von hawe
Das in der Aufgabenstellung angegebene Schnittmuster enthält (2,0,0) (Huggy's Lösung) nicht.

Die Aufgabenstellung enthält keine bestimmten Schnittmuster. Der Fragesteller hatte lediglich bestimmte Schnittmuster vorab ausgeschlossen.

Zitat:

Mit den gegebenen Schnittmustern hab ich den XL Solver befragt und der kommt auf immer auf 136 Stangen egal ob mal die gewünschte Stückzahl = oder <= ansetzt.

Das muss wohl $\begin{eqnarray*} \geq \end{eqnarray*}$ heißen. Sonst wäre die Nulllösung optimal. Es ist nicht ungewöhnlich, dass so ein Problem mehrere untersxchiedliche Lösungen besitzt.

13.10.2021, 14:04

hawe

Auf diesen Beitrag antworten »

RE: Eindimensionales Zuschnittsproblem
Hm,

siehe pdf-Anhang

>Durch Ausprobieren kommt man auf folgende Varianten:<

a_i, i=1...7

könnte es sein, dass

>II) x2 + x4 + x5 + x7 = 79<

entsprechend diesem Zuschnittmuster falsch angegeben ist?
vergleichbar Zeile 3 in meiner Tabelle

mein <= bezieht sich auf meine Tabellenanordnung.
Unsere Ergebnisse liegen ja nahe beisammen unterscheiden sich nur durch unterschiedlche Schnittmustervarianten...

Mit wxMaxima komm ich auf das gleiche Ergebnis, da muß ich aber das Branch&Bound zu Integer selber machen - braucht dankenswerter Weise nur einen Zweig...

code:

1:
2:
3:

minimize_lp( x1+x2+x3+x4+x5+x6+x7,[ 2*x1+x2+x3  = 121,  x2+2*x4+x5+3*x7  = 79, x1+x2+2*x3+x4+2*x5+4*x6 = 257 ] ), nonegative_lp=true, numer;
[135.9583333333333,[x6=49.125,x7=26.33333333333333,x5=0,x4=0,x3=0,x2=0,x1=60.5]]

code:

1:
2:
3:

minimize_lp( x1+x2+x3+x4+x5+x6+x7,[ 2*x1+x2+x3  = 121,  x2+2*x4+x5+3*x7  = 79, x1+x2+2*x3+x4+2*x5+4*x6 = 257, x1<=60 ] ), nonegative_lp=true, numer;
[136.0,[x6=49.0,x7=26.0,x5=0,x4=0,x3=0,x2=1,x1=60]]

Neue Frage »

Antworten »

Eindimensionales Zuschnittsproblem

Verwandte Themen