lineare Optimierung |
| 31.01.2011, 10:05 | Jonny22 | Auf diesen Beitrag antworten » | ||
| lineare Optimierung ich habe folgendes Optimierungsproblem: x11 + x 12 + ..... x1n = 5 x21 + x22 + ...... x2n = 5 xn1 ................... xnn = 5 Zielfunktion: max = x11 + x12 .... xnn Erläuterung: Nicht allle xij Variablen sind besetzt bzw. es gibt nur die Möglichkeiten 0*xij oder 1*xij. Dies ist jedoch vorgegeben. Es sei z.B. gegeben: 1*x11 und alle anderen Variablen dieser Spalte sind nicht besetzt und 1*x12 und 1*x22 und alle anderen Variablen dieser Spalte sind ebenfalls nicht besetzt. Legt man diese beiden Spalten nun zusammen, ergibt sich eine neue Spalte mit 1*x11 und 1*x22 (ok, die Indizes des neuen Systems müssten eigentlich neu vergeben werden). Es stellt sich nun die Frage, welche Spalten man zusammenlegen sollte, damit die Bedingungen eingehalten werden (am Ende genau 5 Spalten) und die ZF maximiert wird. Wie müsste man das rechnen, um z.B. die optimale Lösung mit für mehrere tausend xij Variablen zu berechnen? Gruß Jonny |
||||
| 31.01.2011, 13:18 | Reksilat | Auf diesen Beitrag antworten » | ||
| RE: lineare Optimierung Hi Jonny, Ist Deine Zielfunktion nicht einfach nur die Summe aller Gleichungen? Dann ist doch aber immer konstant. Und was meinst Du mit:
Sollte da ein "=" stehen? Gruß, Reksilat. |
||||
| 31.01.2011, 13:46 | Jonny22 | Auf diesen Beitrag antworten » | ||
| RE: lineare Optimierung Hi Reksilat, Jede Variable xij hat einen Koeffizienten. Dieser ist entweder 0 oder 1, was dann soviel bedeutet, dass die Variable zum Tragen kommt oder nicht. Wie gesagt, dass ist aber zu Anfang fest vorgegeben. Aber es ist eigentlich auch nicht korrekt von mir formuliert, dass es sich dabei um unterschiedliche Variable handeln. Denn es ist ja so, dass eine spaltweise Zusammenfassung erfolgen soll und von angeblich unterschiedlichen Variablen... das ginge ja gar nicht. Bzgl. der Zielfunktion. Du hast Recht. Da ist mir ein Fehler unterlaufen. Bei den Gleichungen muss überall <= 5 stehen. Mittlerweile bin ich mir auch gar nicht mehr so sicher, ob das überhaupt ein lineares Optimierungproblem ist, da am Ende nicht steht, diese oder jene Variable soll 0 oder eins sein. Vielmehr soll eine Aussage gemacht werden, welche Spalten zusammenzufügen sind. Dabei ist es übrigens auch erlaubt, mehrere Spalten zusammen zu fügen. Welches Problem ich damit lösen möchte.... die Erklärung würde einfach zu lange dauern. Ich hoffe, dass das Problem bereits so "rüberkommt". Ich hoffe es zumindest. Gruß Jonny |
||||
| 31.01.2011, 15:07 | Reksilat | Auf diesen Beitrag antworten » | ||
RE: lineare Optimierung
Du kannst also nicht sagen, ob die Variablen verschieden sind oder nicht?
Wenn sie alle verschieden sind, dann hast Du für jede Zeile ein von den anderen unabhängiges Maximierungsproblem dort stehen. Ansonsten habe ich keine Ahnung, was Du unter "spaltweise Zusammenfassung" verstehst. Gruß, Reksilat. |
||||
| 31.01.2011, 16:58 | Jonny22 | Auf diesen Beitrag antworten » | ||
Ok, dann versuche ich es noch einmal praktischer zu erklären. Gegeben sind genau 37 Spalten und exakt 1000 Reihen. Die Zellenwert sind dabei entweder 1 oder 0 z.B: 1 2 3 4 5 6 .....37 1 1 1 1 1 1 1 ..... 1 2 1 0 0 1 0 0 ..... 0 3 0 0 0 0 0 0 ..... 0 4 1 0 1 1 0 1 ..... 1 . . . . . . . ..... . . . . . . . ..... 1000 0 1 0 1 1 1 ..... 1 Selbstverständlich können Spalten auch verschoben werden. Z.B. könnte man die erste Spalte auch vor die letzte Spalte setzen. Das spielt keine Rolle. Bei einer Zusammenfügung von Spalten gelten nun folgende Gesetze: Fügt man zwei Spalten zusammen, wird eine Zelle nur dann 0, wenn beide korrespondierenden Zellen 0 sind, andernfalls 1. z.B. Zusammenfügung von Spalte1 und Spalte2: Spalte 1 und 2 fallen weg und es entsteht die Neue Spalte. 1 1 0 1 . . 1 Nun stellt sich also die Frage, welche Spalten zusammengefügt werden sollten. Im Ergebnis sollen nur noch 5 Spalten übrig bleiben und bestenfalls die Summe einer jeden Spalte 1000 sein. Im obigen Beispiel wäre das z.B. nicht mehr möglich, da die 3. Reihe komplett Null ist. Aber das ist auch nicht so schlimm, solange die Lösung letztlich maximal wird. |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
