Linearisieren < Nichtlineare Gleich. < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 13:57 Di 01.08.2006 | | Autor: | Mermaid |
Hi,
ich habe ein mathematisches Optimierungsmodell aufgestellt mit Zielfunktion und Nebenbedingungen, das nichtlineare Gleichungen enthält. Leider kann meine Optimierungssoftware nur lineare Gleichungen lösen. Gibt es eine Möglichkeit, die Gleichungen in lineare zu 'transformieren'?
Ein Beispiel für diese Gleichungen ist:
[mm] \summe_{j=1}^{J}(BOGENAUFLAGE(j)*ANZAHL(i,j)*YIJ(i,j)) \ge [/mm] BESTELLUNG(i)
für alle i = 1 bis I
BOGENAUFLAGE und ANZAHL sind Variablen, YIJ ist eine binäre Variable.
Danke im voraus.
Kim
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:48 Di 01.08.2006 | | Autor: | RAT |
Hi,
bei manchen Spezialfällen geht das, aber allgemein nicht. Was du da hast ist ja dann ein nichtlinearen, nichtkonvexes Problem...was übleres gibt's wohl nicht. Vielleicht kannst du das ganze anders modellieren.
Ich weiss ja nicht, was du genau modellieren wollst, aber eine Binärvariable gibt ja meistens an, ob was genommen wird oder nicht. Wäre das dann nicht schon in der Anzahl Variable drin? Und was ist dieses Bogenlänge?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:16 Mi 02.08.2006 | | Autor: | Mermaid |
Hi,
Bogenauflage beschreibt die Stückzahl, in der ein Bogenlayout gedruckt wird. Auf diesem ist eine bestimmte Anzahl von einem Artikel, was miteinander multipliziert die bestellte menge des Artikels ergeben soll. Die hier aufgeschriebene Bedingung ist nur eine Nebenbedingung des Modells.
Das mit der Binärvariable stimmt, allerdings werde ich um den Teil BOGENAUFLAGE*ANZAHL nicht herum kommen...oder?
Aber vielen Dank fürs Gedanken machen.
Gruß
Kim
|
|
|
| |
|
Hallo Kim
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
Und was soll minimiert/maximiert werden? Um die Frage nach der Linearisierbarkeit zu beantworten solltest Du imho etwas mehr zu deinem Problem schreiben. (gegeben gesucht etc.)
viele Grüße
mathemaduenn
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:54 Mi 02.08.2006 | | Autor: | Mermaid |
Sorry, hatte ich nicht gemacht/bedacht, weil.... keine Ahnung.
Also, die Zielfunktion lautet (ungefähr):
max z = [mm] \summe_{j=1}^{J}( \summe_{i=1}^{I}(ANZAHL(i,j)*YIJ(i,j))-BOGENAUFLAGE(j))
[/mm]
Dabei soll eine möglichst große Anzahl jedes Artikels bei einer möglichst geringen Bogenauflage gedruckt werden. Die Binärvariable YIJ war notwendig, weil die Optimierungssoftware Lingo sonst einfach auch irrelevante und nicht gedruckte Mengen hinzugenommen hatte. Vielleicht kann sie aber auch weggelassen werden...
|
|
|
| |
|
Hallo Kim,
> Also, die Zielfunktion lautet (ungefähr):
>
> max z = [mm]\summe_{j=1}^{J}( \summe_{i=1}^{I}(ANZAHL(i,j)*YIJ(i,j))-BOGENAUFLAGE(j))[/mm]
>
> Dabei soll eine möglichst große Anzahl jedes Artikels bei
> einer möglichst geringen Bogenauflage gedruckt werden.
![[kopfkratz3]](/images/smileys/kopfkratz3.gif "[kopfkratz3]")
Wenn man Anzahl[i,j] erhöht bleibt die NB erfüllt und deine Zielfunktion wird immer größer.
Gibts noch mehr NB.
viele Grüße
mathemaduenn
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:42 Mi 02.08.2006 | | Autor: | Mermaid |
Hi Christian,
ja, es gibt noch einige weitere Nebenbedingungen, z.B. eine Flächenrestriktion (die Flächensumme der Teile auf einem Bogen darf nicht größer sein als der Bogen selbst), der Artikel darf nur auf einer Einteilung vorkommen (Summe über YIJ = 1), die Bogenauflagen sind in einem Intervall festgelegt etc.
Die Knackpunkte sind nur die Zielfunktion und die angegebene Nebenbedingung, sonst ist alles bestens, außer, dass mir eine Bedingung fehlt, die sagt, wenn YIJ(i,j) = 0 ist, dann ist auch ANZAHL(i,j) = 0. In Lingo lässt sich die mit Hilfe einer IF-Funktion praktisch nicht erstellen. Deshalb muss ich auch immer ANZAHL(i,j) mit YIJ(i,j) multiplizieren, um dies zu bewerkstelligen...
Grüße
Kim
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:47 Mi 02.08.2006 | | Autor: | RAT |
Das erreichst du mit
ANZAHL(j) <= M*YIJ(i,j)
Wobei M eine große Zahl ist, die zb das Maximimum von dem ist was ANZAHL(i,j) annehmen kann. Dann wird, wenn YIJ=0 auch ANZAHL zu 0 gezwungen und sonst ist es egal , da dann ANZAHL<=M dasteht.
Ich glaube es ist am besten, wenn du mal die ganze Aufgabe und die komplette Modellierung hinschreibst.
Gruß
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:02 Mi 02.08.2006 | | Autor: | Mermaid |
Klar, die berühmte 'große Zahl'... war mal wieder zu blöd, um selbst darauf zu kommen...
Ich werde mich jetzt mal daran machen, das Modell aus der Lingosprache wieder in die mathematische komplett umzusetzen und es dann reinstellen. Allerdings glaube ich mittlerweile nicht mehr, dass das Problem anders zu lösen ist als über einen nichtlinearen Solver. Aber zumindest ist es jetzt schon mal in der Komplexität etwas reduziert. Danke.
Gruß
Kim
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 16:10 Mi 02.08.2006 | | Autor: | Mermaid |
Also, hier ist jetzt das gesamte Modell:
Index i beschreibt den Artikel i
Index j die einteilung/ den Bogen j
max z = $ [mm] \summe_{j=1}^{J}( \summe_{i=1}^{I}(ANZAHL(i,j))-BOGENAUFLAGE(j)) [/mm] $
u.d.NB.
[mm] \summe_{j=1}^{J}YIJ(i,j) [/mm] = 1 für alle i = 1...I
$ [mm] \summe_{i=1}^{I}ANZAHL(i,j)*FLAECHE(i) \le [/mm] BOGENFLAECHE(j)$ für alle j = 1..J
$ [mm] \summe_{j=1}^{J}(BOGENAUFLAGE(j)\cdot{}ANZAHL(i,j)\cdot{}YIJ(i,j)) \ge [/mm] BESTELLUNG(i) $
für alle i = 1 bis I
$ [mm] \summe_{j=1}^{J}(BOGENAUFLAGE(j)\cdot{}ANZAHL(i,j)\cdot{}YIJ(i,j)) \le [/mm] ANTEIL*BESTELLUNG(i) $
für alle i = 1 bis I
$ BOGENAUFLAGE(j) [mm] \le [/mm] 5000$
$ BOGENAUFLAGE(j) [mm] \ge [/mm] 500$
$ANZAHL(i,j) [mm] \le [/mm] 100*YIJ(i,j) $ für alle i=1...I und j=1..J
$YIJ(i,j) [mm] \in{0,1}$
[/mm]
Das Modell ist dazu da, bei einer gegebenen Anzahl an Einteilungen, Layouts zu ermitteln, die die Bögen möglichst gut mit Artikeln belegen, so dass die Auflage j und die Anzahl eines Artikels i auf Einteilung j bestimmt und die Bestellungen möglichst genau eingehalten werden.
Ich habe den Rat von RAT (haha) bereits umgesetzt (hoffentlich richtig...). So wie ich das jetzt sehe, lässt sich wohl kein lienares Modell daraus machen. Aber ich lasse mich gerne belehren
Verbesserungsvorschläge werden gerne genommen 
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:20 Mi 09.08.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
