Optimierungsproblem < Optimierung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:16 Do 28.09.2006 | | Autor: | Amokkx |
| Aufgabe | Es gibt x Autos, die in einer jewiligen Zeit y(index x) von zwei Werkstätten reperariert werden. Diese Werkstätten reparieren die jeweiligen Autos in der Zeit z1 * y(index x) bzw werkstatt zwei z2 * y(index x). Berechnen Sie die optimale Verteilung der Autos auf die zwei Werkstätte, damit die Autos möglichst schnell fertig sind.
Erweiterung es gibt drei Werkstätte die jeweils ind er Zeit z1 * y(index x) , zwei z2 * y(index x) und z3 * y(index x). |
Die Aufgabe is anundfürsich schon mein Problem. Ich habe keine Ahnung wie ich das lösen kann, allgemeine versteht sich.
Wenn ich es ausprobieren würde hätte ich für 100 Autos 2 hoch 100 Lösungen. Ein bisschen viel :)
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo Amokkx!
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> Es gibt x Autos, die in einer jewiligen Zeit y(index x) von
> zwei Werkstätten reperariert werden. Diese Werkstätten
> reparieren die jeweiligen Autos in der Zeit z1 * y(index x)
> bzw werkstatt zwei z2 * y(index x). Berechnen Sie die
> optimale Verteilung der Autos auf die zwei Werkstätte,
> damit die Autos möglichst schnell fertig sind.
> Erweiterung es gibt drei Werkstätte die jeweils ind er
> Zeit z1 * y(index x) , zwei z2 * y(index x) und z3 *
> y(index x).
Für mich gibt es hier noch ein paar Unklarheiten bezüglich der Notation um die Frage zu lösen:
[mm]x[/mm] ... Das ist wohl die Gesamtzahl der zu reparierenden Austos.
[mm] y_{x} [/mm] ... Soll dies die Zeit sein, mit der ein Auto repariert wird (unabhängig ob in Werkstatt 1 oder Werkstatt 2)?Das hieße dann, daß beide Werkstätten die Autos gleich schnell repariren würden.
[mm] z_{1}*y_{x} [/mm] ... Wenn das die Zeit sein soll mit der Werkstatt 1 die ihr zugewiesenen Autos bearbeitet und [mm] y_{x} [/mm] die Zeit ist, mit der ein Auto repariert wird, dann muss [mm] z_{1} [/mm] folglich die Anzahl der Autos sein, die Werkstatt 1 repariert. (Analog dazu für [mm] z_{1})
[/mm]
Unter diesen Annahmen wäre die Lösung denkbar einfach: Wenn beide Werkstätten die Autos gleich schnell reparieren, dann gebe ich 50% von x in Werktstatt 1 und 50% von x in Werkstatt 2 zu Reparatur.
Da mir diese Lösung allerdings zu einfach erscheint, vermute ich mal, daß die Aufgabe nicht ganz klar verständlich gestellt wurde.
Könntest du ein paar mehr Informationen dazu geben, sofern du diese zur Hand hast?
Gruß,
Tommy
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:16 Do 28.09.2006 | | Autor: | Amokkx |
Also [mm] y_x [/mm] ist die Zeit in der ein Auto reperariert wird in "Normalform". Die 2 Werkstätten jedoch bearbeiten dieses auto um den Faktor [mm] z_1 [/mm] bzw [mm] z_2 [/mm] schneller. Dabei gilt dass [mm] z_1 [/mm] nicht umbedingt gleich [mm] z_2 [/mm] ist, dies wäre eher der ausnahmezustand.
Also ist [mm] y_x * z_1 [/mm] die Zeit, in der Werkstatt 1 das Auto X repariert.
Und [mm] y_x * z_2 [/mm] die Zeit, in der Werkstatt 2 das Auto X repariert.
|
|
|
| |
|
Ok, mit den nun vorliegenden Informationen komme ich auf folgende Lösung:
Wir gehen von folgendem aus:
[mm]y_{x}[/mm] ist die Normalzeit für die Reparatur eines Autos.(z.B. 10 min)
(Hinweis: [mm] y_{x} [/mm] spielt im weiteren Verlauf der Betrachtungen keine wesentliche Rolle, da die Determinanten für die Optimale Verteilung der Autos durch die Reperaturproduktivitäten [mm] z_{1} [/mm] und [mm] z_{2} [/mm] gegeben sind)
[mm] z_{1} [/mm] und [mm] z_{2} [/mm] sind quasi ein Schnelligkeitsfaktor für die Bearbeitungszeiten der Autos in der jeweiligen Werkstatt. Ein Faktor von [mm] z_{1}=1,1 [/mm] und ein Faktor von [mm] z_{2}=0,8 [/mm] hießen, daß Werkstatt 1 10% länger braucht als normal (z.B. [mm] y_{x}*z_{1} [/mm] = 1,1*10min = 11 min) um ein Auto zu reparieren und das Werkstatt 2 80% der nomalen Bearbeitungszeit (z.B. 0,8*10 min = 8 min) braucht um ein Auto zu bearbeiten (also schneller arbeitet als 'normal' ist).
Nun könnte man fälschlicher Weise der Annahme sein, daß die optimale Verteilung der Menge x diese wäre, bei der die gesamte Bearbeitungsdauer der Reaparaturen in Werkstatt 1 und Werkstatt 2 die minimale Zeit ist. Dem ist aber nicht so, da die Reparaturprozesse nicht hintereinandergelagert sind, sondern parallel ablaufen (in jeder Werkstatt separat, also unabhängig von der anderen)! Die optimale Verteilung der Menge an Autos auf die beiden Werkstätten ist jene, welche in beiden Werkstätten jeweils die gleiche Bearbeitungsdauer erfordert. (Wenn dem nicht so wäre, dann wäre eine Werkstatt schneller fertig als die andere und hätte demzufolge noch Bearbeitungskapazitäten zu bieten).
Es muss demnach gelten:
[mm]z_{1}*x_{1}=z_{2}*x_{2}[/mm] Formel (I)
[mm] x_{1} [/mm] ist hier die Menge an Autos, die in Werkstatt 1 bearbeitet werden. [mm] x_{2} [/mm] gibt demnach die Menge an Reparaturen in Werkstatt 2 an. Beide zusammen ergeben die Gesamtmenge x. Es gilt also: [mm] x_{1}+x_{2}=x [/mm] Formel (II)
Stellt man nun (II) nach [mm] x_{2} [/mm] um und setzt dann in (I) ein erhält man:
[mm] z_{1}*x_{1}=z_{2}*(x-x_{1})
[/mm]
Das Ganze nach [mm] x_{1} [/mm] umgestellt ergibt:
[mm] x_{1}=\bruch{z_{2}*x}{z_{1}+z_{2}} [/mm] Formel (III)
Setzt man nun (III) in (II) ein, so erhält man für [mm] x_{2} [/mm] :
[mm] x_{2}=\bruch{z_{1}*x}{z_{1}+z{2}} [/mm] Formel (IV)
Wenn du nun Formel (III) und Formel (IV) ins Verhältnis setzt ergibt sich:
[mm] \bruch{x_{1}}{x_{2}}=\bruch{\bruch{z_{2}*x}{z_{1}+z{2}}}{\bruch{z_{1}*x}{z_{1}+z{2}}}
[/mm]
Gekürzt erhält man die Lösung:
[mm] \bruch{x_{1}}{x_{2}}=\bruch{z_{2}}{z_{1}}
[/mm]
Das bedeutet, daß die Aufteilung der gesamten Autos so erfolgen sollte, daß der Quotient der Menge der jeweils in der Werkstatt bearbeiteten Auto dem Kehrwert der zugehörigen Reperaturproduktivitäten entspricht. Da [mm] z_{1} [/mm] und [mm] z_{2} [/mm] ja vorgegeben sind, ist demnach auch die Aufteilung der Menge x auf die Werkstätten determiniert.
Hoffe ich habs halbwegs verständlich erklärt.
Für die Zusatzfrage sollte die Lösung ähnlich aussehen und sich nur dahingehend erschweren, da 3 Werkstätten beteiligt sind. Herangehensweise sollte aber die gleiche sein.
Schöne Aufgabe. 
Gruß,
Tommy
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 07:49 Fr 29.09.2006 | | Autor: | Amokkx |
Du gehst davon aus, das die Zeit [mm] y_x [/mm] für alle [mm] x [/mm] Autos gleich ist. Dies ist aber nicht so, deswegen auch die Indizierung [mm] y_x [/mm].
Einfaches Beispiel, ich hätte es am besten gleich mit reinstellen sollen.
Wir geen davon aus, des es 3 Autos gibt.
Auto 1 braucht 1h zum Reperarien, Auto 2 braucht 2h und Auto 3 braucht 3h.
Es folgt:
[mm] y_1 = 1
y_2 = 2
y_3 = 3
[/mm]
[mm] z_1 = 1 [/mm]
[mm] z_1 = 0,9 [/mm]
Die Beste Lösung wäre in diesem Fall in Werkstatt 1 Auto 1 und 2 zu reparieren (3h) und in Werkstatt 2 das Auto 3. (2,7h)
oder in Werkstatt 1 Auto 3 und in Werkstatt 2 Auto 1 und 2.
Hoffe du verstehst wo dein Fehler ist :)
Gruß
Eike
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:42 Fr 29.09.2006 | | Autor: | VNV_Tommy |
Hallo Eike!
> Du gehst davon aus, das die Zeit [mm]y_x[/mm] für alle [mm]x[/mm] Autos
> gleich ist. Dies ist aber nicht so, deswegen auch die
> Indizierung [mm]y_x [/mm].
Tut mir leid. Diese Indizierung zeigt mir an, daß die Reparaturzeit für alle Autos gleich sei. (Deswegen ja auch meine anfängliche Nachfrage die zur Klärung dieser Unklarheit beitragen sollte)
Tipp: Verwende doch bitte den Formeleditor um die Indizes richtig klar darzustellen. Das kann Mißverständnissen vorbeugen.
> Einfaches Beispiel, ich hätte es am besten gleich mit
> reinstellen sollen.
Ja, wäre besser gewesen. Ein Beispiel erklärt mitunter mehr als eine unklare aufgabenstellung.
> Wir geen davon aus, des es 3 Autos gibt.
>
> Auto 1 braucht 1h zum Reperarien, Auto 2 braucht 2h und
> Auto 3 braucht 3h.
>
> Es folgt:
> [mm]y_1 = 1
y_2 = 2
y_3 = 3
[/mm]
>
> [mm]z_1 = 1[/mm]
> [mm]z_1 = 0,9[/mm]
>
> Die Beste Lösung wäre in diesem Fall in Werkstatt 1 Auto 1
> und 2 zu reparieren (3h) und in Werkstatt 2 das Auto 3.
> (2,7h)
> oder in Werkstatt 1 Auto 3 und in Werkstatt 2 Auto 1 und
> 2.
>
> Hoffe du verstehst wo dein Fehler ist :)
Ich denke du verstehst, daß bei einer derart unklar gestellten Frage diese Art von 'Fehler' entstehen kann. Man sieht mal wieder: Noch wichtiger als die richtigen Antworten geben zu können ist es, die richtigen Fragen zu stellen.
> Gruß
> Eike
>
>
Abschließend noch ein Kommentar:
Anscheinend hast du die Lösung vor dir liegen, denn sonst wärst du dir nicht so sicher, daß meine Ansätze falsch sind. Mit deiner Art, Aufgaben zu formulieren hättest du mich auch nach einem Lied fragen können, in welchem die Wörter "freedom", "happy" und "party" auftauchen. Wahrscheinlich hätte ich dir auch den ein oder anderen Song nennen können, auf den deine Frage zutreffen könnte, allerdings hättest du dann sicher erst im Laufe der Lösung erwähnt, daß die Wörter nicht in dieser Reihenfolge auftauchen dürfen, anders betont werden etc. ... Das Ganze würde jedenfalls viel Zeit und Nerven kosten. Da ich von beidem jedoch nur begrenzte Ressourcen zur Verfügung habe, wirst du sicher verstehen, daß ich mich nun deiner Aufgabe nicht mehr widmen werde. Zumal die Lösung an sich quasi schon gegeben wurde, sie bedarf nur noch einem geringfügigen Zusatz - ich bin mir sicher, du wirst schon wissen, wo dieser zu setzen ist. Viel Erfolg.
Gruß,
Tommy
|
|
|
| |
|
Hallo und guten Morgen,
schreib doch das Problem als ganzzahliges Lineares Programm. Variablen: für jedes Auto x eine 0-1 Variable [mm] a_x, [/mm] Wert 0 stehe für Werkstatt 1 und Wert 1
für Werkstatt 2.
Dann:
[mm] \min [/mm] T
so dass
[mm] \sum_{x\:\: Auto} (1-a_x)\cdot z_1\cdot y_x\:\:\leq [/mm] T
[mm] \sum_{x\:\: Auto} a_x\:\: \cdot z_2\cdot y_x\:\:\leq [/mm] T
[mm] \forall\: x\:\:\: a_x\in\{0,1\}
[/mm]
Das kannst Du in einen ILP-Solver einspeisen, der Dir dann
zu gegebenen Werten eine Lösung berechnet.
Das Problem ist NP-schwer, so dass man momentan keine Hoffnung auf effiziente Lösungsverfahren hat geschweige denn
eine Lösung in geschlossener Form oder eine ganz einfache effiziente Lösungsstrategie hinschreiben kann.
Die andere Möglichkeit ist es, sich mit suboptimalen Lösungen zu begnügen und sogenannte effiziente Approximationsalgorithmen zu entwerfen.
Ordne zB die Autos in absteigender Reihenfolge nach den Werten [mm] y_x, [/mm] so dass sich zB die Reihenfolge [mm] y_1\geq \ldots \geq y_n [/mm] ergibt
(bei n Autos).
Dann:
[mm] T_1=T_2=0 [/mm] (Zeit, die die Werkstätten bei bisheriger Zuordnung schon arbeiten müssen)
for x=1 to n
[mm] \:\: [/mm] Sei [mm] i\in \{1,2\} [/mm] so dass
[mm] \:\:\:\: T_i+y_x\cdot z_i\leq T_j+y_x\cdot z_j [/mm] ( j die andere Werkstatt)
[mm] \:\: [/mm] Ordne das Auto x der Werkstatt i zu, setze [mm] T_i:=T_i+y_x\cdot z_i
[/mm]
Das wäre ein solches Näherungsverfahren, es ist effizient (d.h. schnell) und berechnet stets eine Lösung,
bei der [mm] \max{T_1,T_2\} [/mm] am Ende höchstens [mm] 2\cdot [/mm] die optimale zu erreichende Zeit ist.
Es handelt sich bei Deinem Problem um das sogenannte Minimum Multiprocessor Scheduling Problem, und für jede
feste Zahl von Werkstätten gibt es einen - allerdings etwas aufwendigeren- Algorithmus, der das problem mit bel Genauigkeit approximiert
(ein sogenanntes FPTAS).
Siehe zB das Buch ''Approximation Algorithms for NP-Hard Problems'', editiert von Dorith Hochbaum, dort das kapitel über Scheduling-Probleme.
Gruss,
Mathias
|
|
|
|
