Werkstatt LP < Optimierung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:49 Mi 13.05.2015 | | Autor: | triad |
| Aufgabe | Eine Werkstatt hat eine Bohr- und 5 Fräsmaschinen, um Teile zu produzieren, die aus 2 Werkstücken bestehen. Die Werkstücke müssen jeweils gebohrt und gefräst werden. Die Bearbeitungszeiten der Werkstücke sind:
Werkstück Bohren (minuten) Fräsen (minuten)
1 3 20
2 5 15
Alle Maschinen sollen so ausgelastet sein, dass keine Maschine mehr als 30 Minuten pro Tag länger läuft als jede der anderen. Die Fräsmaschinen seien dabei alle (so) gleichmäig (wie möglich) ausgelastet. Ein Arbeitstag hat 8 Stunden.
Formulieren Sie das Problem, die Maschinen so auszulasten, dass die maximale Anzahl von kompletten
Teilen produziert wird, als LP (Lineares Programm). |
Hallo Leute,
mein Problem bei dieser Aufgabe besteht schon darin, welche und wie viele Variablen für was einzusetzen sind. Brauche ich nun für jede Maschine eine Variable oder für jedes Werkstück eine oder beides?
Ich habe mal so angefangen: Die Summe der Bohr- und Fräsminuten überschreiten nicht 8 Stunden (480 Minuten), daher die zwei Nebenbedingungen [mm] (x_i [/mm] für Werkstück i)
$\ [mm] 3x_1 [/mm] + \ [mm] 5x_2 \le [/mm] 480$
$20 [mm] x_1 [/mm] + [mm] 15x_2 \le [/mm] 480$
Dann habe ich überlegt, wie man modelliert, dass "keine Maschine mehr als 30 Minuten pro Tag länger läuft als jede der anderen". Dazu nehme ich mir 6 Variablen [mm] $y_0,\ldots,y_5$ (y_0 [/mm] für Bohrmaschine, rest für Fräsmaschinen) für die gelten muss
[mm] $y_i \le y_j [/mm] + 30$ für alle [mm] $i\not= [/mm] j$
Dann muss ich die Variablen noch irgendwie in Beziehung miteinander setzen und wie die Zielfunktion aussieht weiss ich auch noch nicht.
Naja bis hierhin erstmal. Ich werde noch weiter an der Aufgabe arbeiten. Für hilfreiche Ideen wäre ich dankbar.
LG
triad
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:26 Do 14.05.2015 | | Autor: | meili |
Hallo triad,
> Eine Werkstatt hat eine Bohr- und 5 Fräsmaschinen, um
> Teile zu produzieren, die aus 2 Werkstücken bestehen. Die
> Werkstücke müssen jeweils gebohrt und gefräst werden.
> Die Bearbeitungszeiten der Werkstücke sind:
>
> Werkstück Bohren (minuten) Fräsen (minuten)
> 1 3 20
> 2 5 15
>
> Alle Maschinen sollen so ausgelastet sein, dass keine
> Maschine mehr als 30 Minuten pro Tag länger läuft als
> jede der anderen. Die Fräsmaschinen seien dabei alle (so)
> gleichmäig (wie möglich) ausgelastet. Ein Arbeitstag hat
> 8 Stunden.
>
> Formulieren Sie das Problem, die Maschinen so auszulasten,
> dass die maximale Anzahl von kompletten
> Teilen produziert wird, als LP (Lineares Programm).
> Hallo Leute,
>
> mein Problem bei dieser Aufgabe besteht schon darin, welche
> und wie viele Variablen für was einzusetzen sind. Brauche
> ich nun für jede Maschine eine Variable oder für jedes
> Werkstück eine oder beides?
Beides, [mm] $x_1$ [/mm] und [mm] $x_2$ [/mm] für Anzahl der Werkstücke 1 und 2.
[mm] $y_0, y_1, \ldots y_5$ [/mm] Anzahl der Betriebsminuten für jede Maschine an einem Tag.
Wenn sich später herausstellt, dass eine Variable durch andere dargestellt
werden kann, ist das auch nicht schlimm.
>
> Ich habe mal so angefangen: Die Summe der Bohr- und
> Fräsminuten überschreiten nicht 8 Stunden (480 Minuten),
> daher die zwei Nebenbedingungen [mm](x_i[/mm] für Werkstück i)
>
> [mm]\ 3x_1 + \ 5x_2 \le 480[/mm]
![[ok]](/images/smileys/ok.gif "[ok]")
> [mm]20 x_1 + 15x_2 \le 480[/mm]
Da es 5 Fräsmaschinen gibt, müsste diese Ungleichung
$20 [mm] x_1 [/mm] +15 [mm] x_2 \le [/mm] 5*480$
sein.
>
> Dann habe ich überlegt, wie man modelliert, dass "keine
> Maschine mehr als 30 Minuten pro Tag länger läuft als
> jede der anderen". Dazu nehme ich mir 6 Variablen
> [mm]y_0,\ldots,y_5[/mm] [mm](y_0[/mm] für Bohrmaschine, rest für
> Fräsmaschinen) für die gelten muss
>
> [mm]y_i \le y_j + 30[/mm] für alle [mm]i\not= j[/mm]
Das ist erst die Hälfte der Bedingung.
Du hast die Laufzeit nach oben begrenzt,
aber sie muss auch noch nach unten eingegrenzt werden.
>
> Dann muss ich die Variablen noch irgendwie in Beziehung
> miteinander setzen und wie die Zielfunktion aussieht weiss
> ich auch noch nicht.
Zielfunktion ist recht einfach: $max [mm] \{x_1+x_2\}$
[/mm]
Da ein komplettes Bauteil aus einem Werkstück 1 und einem Werkstück 2
besteht, muss [mm] $x_1 [/mm] = [mm] x_2$ [/mm] gelten.
>
> Naja bis hierhin erstmal. Ich werde noch weiter an der
> Aufgabe arbeiten. Für hilfreiche Ideen wäre ich dankbar.
>
>
> LG
> triad
Gruß
meili
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:02 Fr 15.05.2015 | | Autor: | triad |
hallo und danke für deine antwort!
> Hallo triad,
>
> > Eine Werkstatt hat eine Bohr- und 5 Fräsmaschinen, um
> > Teile zu produzieren, die aus 2 Werkstücken bestehen. Die
> > Werkstücke müssen jeweils gebohrt und gefräst werden.
> > Die Bearbeitungszeiten der Werkstücke sind:
> >
> > Werkstück Bohren (minuten) Fräsen (minuten)
> > 1 3 20
> > 2 5 15
> >
> > Alle Maschinen sollen so ausgelastet sein, dass keine
> > Maschine mehr als 30 Minuten pro Tag länger läuft als
> > jede der anderen. Die Fräsmaschinen seien dabei alle (so)
> > gleichmäig (wie möglich) ausgelastet. Ein Arbeitstag hat
> > 8 Stunden.
> >
> > Formulieren Sie das Problem, die Maschinen so auszulasten,
> > dass die maximale Anzahl von kompletten
> > Teilen produziert wird, als LP (Lineares Programm).
> > Hallo Leute,
> >
> > mein Problem bei dieser Aufgabe besteht schon darin, welche
> > und wie viele Variablen für was einzusetzen sind. Brauche
> > ich nun für jede Maschine eine Variable oder für jedes
> > Werkstück eine oder beides?
> Beides, [mm]x_1[/mm] und [mm]x_2[/mm] für Anzahl der Werkstücke 1 und 2.
> [mm]y_0, y_1, \ldots y_5[/mm] Anzahl der Betriebsminuten für jede
> Maschine an einem Tag.
> Wenn sich später herausstellt, dass eine Variable durch
> andere dargestellt
> werden kann, ist das auch nicht schlimm.
>
> >
> > Ich habe mal so angefangen: Die Summe der Bohr- und
> > Fräsminuten überschreiten nicht 8 Stunden (480 Minuten),
> > daher die zwei Nebenbedingungen [mm](x_i[/mm] für Werkstück i)
> >
> > [mm]\ 3x_1 + \ 5x_2 \le 480[/mm]
>
>
> > [mm]20 x_1 + 15x_2 \le 480[/mm]
> Da es 5 Fräsmaschinen gibt,
> müsste diese Ungleichung
> [mm]20 x_1 +15 x_2 \le 5*480[/mm]
> sein.
o.k.
>
> >
> > Dann habe ich überlegt, wie man modelliert, dass "keine
> > Maschine mehr als 30 Minuten pro Tag länger läuft als
> > jede der anderen". Dazu nehme ich mir 6 Variablen
> > [mm]y_0,\ldots,y_5[/mm] [mm](y_0[/mm] für Bohrmaschine, rest für
> > Fräsmaschinen) für die gelten muss
> >
> > [mm]y_i \le y_j + 30[/mm] für alle [mm]i\not= j[/mm]
> Das ist erst die
> Hälfte der Bedingung.
> Du hast die Laufzeit nach oben begrenzt,
> aber sie muss auch noch nach unten eingegrenzt werden.
Meinst du damit die nicht-negativitäts Bedingungen [mm] $y_i \ge [/mm] 0$ oder weitere Bedingungen der obigen Form? Denn die Aufgabenstellung verlangt doch nur "länger laufen", also nach oben beschränkt.
>
>
> >
> > Dann muss ich die Variablen noch irgendwie in Beziehung
> > miteinander setzen und wie die Zielfunktion aussieht weiss
> > ich auch noch nicht.
> Zielfunktion ist recht einfach: [mm]max \{x_1+x_2\}[/mm]
>
> Da ein komplettes Bauteil aus einem Werkstück 1 und einem
> Werkstück 2
> besteht, muss [mm]x_1 = x_2[/mm] gelten.
Die Bedingung [mm] $x_1 [/mm] = [mm] x_2$ [/mm] ist dann einfach eine Nebenbedingung in meinem System?
Das LP sähe dann so aus:
[mm] \begin{matrix}
\max & x_1+x_2 & & & \\
s.t. & 3x_1 + 5x_2 & \le & 480 & \\
& 20x_1+15x_2 & \le & 5\cdot{}480 & \\
& y_i & \le & y_j +30 & \forall i\not= j,\ i,j\in\{0,\ldots,5\} \\
& \glqq\mbox{2. Hälfte der Bedingung}\grqq & & & \\
& x_1 & = & x_2 & \\
& x_i & \ge & 0 & i=1,2 \\
& y_i & \ge & 0 & i=0,\ldots,5 \\
\end{matrix}
[/mm]
Wie setze ich jetzt noch die [mm] $x_i$ [/mm] mit den [mm] $y_i$ [/mm] in Beziehung? Das muss ich
offensichtlich tun, sonst könnte ich die Bedingungen mit [mm] $y_i$ [/mm] im LP einfach weglassen.
Wenn man nach dem Prinzip "3 Minuten bohren und 20 Minuten fräsen ergibt ein Werkstück 1" geht,
wären das die Nebenbedingungen
[mm] $3y_0 [/mm] + [mm] 20y_i [/mm] = [mm] x_1 \qquad i=1,\ldots,5$
[/mm]
Analog für Werkstück 2. Aber stimmt das?
LG
triad
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:44 Sa 16.05.2015 | | Autor: | meili |
Hallo triad,
> hallo und danke für deine antwort!
>
>
> > Hallo triad,
> >
> > > Eine Werkstatt hat eine Bohr- und 5 Fräsmaschinen, um
> > > Teile zu produzieren, die aus 2 Werkstücken bestehen. Die
> > > Werkstücke müssen jeweils gebohrt und gefräst werden.
> > > Die Bearbeitungszeiten der Werkstücke sind:
> > >
> > > Werkstück Bohren (minuten) Fräsen (minuten)
> > > 1 3 20
> > > 2 5 15
> > >
> > > Alle Maschinen sollen so ausgelastet sein, dass keine
> > > Maschine mehr als 30 Minuten pro Tag länger läuft als
> > > jede der anderen. Die Fräsmaschinen seien dabei alle (so)
> > > gleichmäig (wie möglich) ausgelastet. Ein Arbeitstag hat
> > > 8 Stunden.
> > >
> > > Formulieren Sie das Problem, die Maschinen so auszulasten,
> > > dass die maximale Anzahl von kompletten
> > > Teilen produziert wird, als LP (Lineares Programm).
> > > Hallo Leute,
> > >
> > > mein Problem bei dieser Aufgabe besteht schon darin, welche
> > > und wie viele Variablen für was einzusetzen sind. Brauche
> > > ich nun für jede Maschine eine Variable oder für jedes
> > > Werkstück eine oder beides?
> > Beides, [mm]x_1[/mm] und [mm]x_2[/mm] für Anzahl der Werkstücke 1 und
> 2.
> > [mm]y_0, y_1, \ldots y_5[/mm] Anzahl der Betriebsminuten für
> jede
> > Maschine an einem Tag.
> > Wenn sich später herausstellt, dass eine Variable
> durch
> > andere dargestellt
> > werden kann, ist das auch nicht schlimm.
> >
> > >
> > > Ich habe mal so angefangen: Die Summe der Bohr- und
> > > Fräsminuten überschreiten nicht 8 Stunden (480 Minuten),
> > > daher die zwei Nebenbedingungen [mm](x_i[/mm] für Werkstück i)
> > >
> > > [mm]\ 3x_1 + \ 5x_2 \le 480[/mm]
> >
> >
> > > [mm]20 x_1 + 15x_2 \le 480[/mm]
> > Da es 5 Fräsmaschinen
> gibt,
> > müsste diese Ungleichung
> > [mm]20 x_1 +15 x_2 \le 5*480[/mm]
> > sein.
>
> o.k.
>
> >
> > >
> > > Dann habe ich überlegt, wie man modelliert, dass "keine
> > > Maschine mehr als 30 Minuten pro Tag länger läuft als
> > > jede der anderen". Dazu nehme ich mir 6 Variablen
> > > [mm]y_0,\ldots,y_5[/mm] [mm](y_0[/mm] für Bohrmaschine, rest für
> > > Fräsmaschinen) für die gelten muss
> > >
> > > [mm]y_i \le y_j + 30[/mm] für alle [mm]i\not= j[/mm]
> > Das ist erst
> die
> > Hälfte der Bedingung.
> > Du hast die Laufzeit nach oben begrenzt,
> > aber sie muss auch noch nach unten eingegrenzt werden.
>
> Meinst du damit die nicht-negativitäts Bedingungen [mm]y_i \ge 0[/mm]
> oder weitere Bedingungen der obigen Form? Denn die
> Aufgabenstellung verlangt doch nur "länger laufen", also
> nach oben beschränkt.
Ja, $ [mm] y_i \ge [/mm] 0$ kannst du zur Klarstellung mit aufnehmen.
Das habe ich aber nicht gemeint, z.B. dürfte Fräsmachine 1 nicht
[mm] $y_1 [/mm] = 180$ Minuten laufen und Fräsmaschine 4 [mm] $y_4 [/mm] = 360$ Minuten.
Dazu habe ich aber zu sehr die einzelne Gleichung angesehen, und nicht
bedacht, dass wenn man alle Gleichungen
[mm] $y_i \le y_j [/mm] + 30, i [mm] \not= [/mm] j, [mm] \mbox{ für alle } [/mm] i,j [mm] \in \{0,1,2,3,4,5\}$ [/mm] zusammen nimmt, dies gewährleitet ist.
>
> >
> >
> > >
> > > Dann muss ich die Variablen noch irgendwie in Beziehung
> > > miteinander setzen und wie die Zielfunktion aussieht weiss
> > > ich auch noch nicht.
> > Zielfunktion ist recht einfach: [mm]max \{x_1+x_2\}[/mm]
> >
> > Da ein komplettes Bauteil aus einem Werkstück 1 und einem
> > Werkstück 2
> > besteht, muss [mm]x_1 = x_2[/mm] gelten.
>
> Die Bedingung [mm]x_1 = x_2[/mm] ist dann einfach eine
> Nebenbedingung in meinem System?
Ja.
>
> Das LP sähe dann so aus:
>
> [mm]\begin{matrix}
\max & x_1+x_2 & & & \\
s.t. & 3x_1 + 5x_2 & \le & 480 & \\
& 20x_1+15x_2 & \le & 5\cdot{}480 & \\
& y_i & \le & y_j +30 & \forall i\not= j,\ i,j\in\{0,\ldots,5\} \\
& \glqq\mbox{2. Hälfte der Bedingung}\grqq & & & \\
& x_1 & = & x_2 & \\
& x_i & \ge & 0 & i=1,2 \\
& y_i & \ge & 0 & i=0,\ldots,5 \\
\end{matrix}[/mm]
>
> Wie setze ich jetzt noch die [mm]x_i[/mm] mit den [mm]y_i[/mm] in Beziehung?
> Das muss ich
> offensichtlich tun, sonst könnte ich die Bedingungen mit
> [mm]y_i[/mm] im LP einfach weglassen.
> Wenn man nach dem Prinzip "3 Minuten bohren und 20 Minuten
> fräsen ergibt ein Werkstück 1" geht,
> wären das die Nebenbedingungen
>
> [mm]3y_0 + 20y_i = x_1 \qquad i=1,\ldots,5[/mm]
Ja, wobei das mit den [mm] $y_i$ [/mm] noch etwas ungenau ist.
Besser:
[mm] $3x_1 +5x_2 [/mm] = [mm] y_0$
[/mm]
[mm] $20x_1 [/mm] + [mm] 15x_2 [/mm] = [mm] \summe_{i=1}^{5} y_i$
[/mm]
>
> Analog für Werkstück 2. Aber stimmt das?
Ausserdem würde ich noch aufnehmen: [mm] $x_1, x_2 \in \IN$,
[/mm]
denn es sollen nur vollständige Teile produziert werden.
>
> LG
> triad
Gruß
meili
|
|
|
|
