Vektorrechnung und Lineare Algebra
Buchtipp
Statistische Datenanalyse
W.-M. Kähler
29,90 €

Buchcover

Anzeige
Stichwortwolke
forum

Zurück   ChemieOnline Forum > Naturwissenschaften > Mathematik > Vektorrechnung und Lineare Algebra

Hinweise

Anzeige

Antwort
 
Themen-Optionen Ansicht
Alt 14.05.2008, 12:08   #1   Druckbare Version zeigen
Pudutzki  
Mitglied
Themenersteller
Beiträge: 7
Lineare Optimierung? Problem aus der Praxis.

Hallo zusammen,

da dies mein erster Beitrag ist, werfe ich erstmal ein allgemeines Hallo in die Runde.

Ich habe ein Problem, von dem ich vermute, daß es mit linearer Optimierung zu lösen ist. Mangels mathematischer Ausbildung und Praxis stellt sich dieses Problem jedoch als harte Nuss dar und ich hoffe, daß mir jemand hier Hilfe leisten kann.

Das Problem ist folgendes:

Es soll für die Beleuchtung eines Werbeträgers (Aluprofil) die optimale Ausleuchtung erreicht werden. Wir haben drei Lampenlängen zur Verfügung:

890mm
1190mm
1490mm

Die entscheidende Größe ist die Rahmenhöhe, da diese optimal durch eine beliebige Kombination der Lampen ausgefüllt werden muss.

Beispiel:

Höhe 3000mm
Hier würden drei 890mm Lampen passen, oder zwei 1490mm Lampen, es würden zwar auch 2x1190mm oder 1x1490mm+1x1190mm gehen, aber hier ensteht zuviel Rand zum Rahmen.

Meiner meinung nach muss ja immer folgende Forderung erfüllt sein:

1490x + 1190y + 890z <= L

wobei L die vorgegebene Größe ist und die optimale Lösung gefunden ist, wenn der linke Term gleich L ist und möglichst wenig Lampen verwendet werden müssen.

Erschwerend kommt hinzu, daß die Lampen sich bis maximal 120mm überlappen dürfen (also dann versetzt montiert werden) und der Abstand zum Rahmenrand zwischen 80 und 100mm variieren darf.

Zum besseren Verständnis hier noch ein Bild wie so ein Rahmen bestückt wird:



Wichtig ist nur die Verteilung auf die Höhe bezogen, die Verteilung auf die Breite wird manuell eingestellt.

Ich sitze schon seit Tagen an diesem Problem, und da ich der einzige in der Firma bin, der halbwegs programmieren kann,muss ich die Sache jetzt ausbaden. Leider ist es mit meinen Mathekenntnissen nicht weit her.

Ich würde mich sehr freuen, wenn mir jemand zumindest einen Denkanstoß geben könnte.

Gruß
Matthias
Pudutzki ist offline   Mit Zitat antworten
Anzeige
Alt 14.05.2008, 12:33   #2   Druckbare Version zeigen
kleinerChemiker Männlich
Mitglied
Beiträge: 4.044
AW: Lineare Optimierung? Problem aus der Praxis.

Genau genommen muss eine Ungleichung erfüllt werden, wie Du eh schon hingeschrieben hast, nur muss die Gleichung um einen Term, nämlich L-T<=1490x+1190y+890z<=L ergänzt werden, da Du ja auch eine optimale Beleuchtung haben willst, also auch nicht zuwenig ausgeleuchtet haben möchtest. T = Toleranzabstand zum Rand.

Die Gleichung würd ich meinen, ist schonmal ziemlich ok, allerdings berücksichtig sie nicht, dass sich die Lampen auch überschneiden dürfen.

Als weitere Nebenbedinung muss natürlich auch gelten: x+y+z --> min.

und x, y und z müssen natürlich ganzzahlig sein, was man ja aber eh bei der Deklaration der Variablen eingeben muss.


Ob das ganze Zeug analytisch lösbar ist oder nicht, kann ich Dir leider auch nicht sagen, würde sowas aber mittels Zufallszahlengenerator lösen:

Sprich als Gleichung, die zu erfüllen gilt, nimmst Du L-T<=(1490-a)*x+(1190-b)*y+(890-c)*z<=L

a, b und c sind Zufallszahlen zw. 0 und 120 mm, x, y und z sind ganzzahlige Zufallszahlen.

Du generierst alle 6 Zufallszahlen, überprüfst mittels If-SChleife, ob Deine Bedingung erfüllt ist, wenn ja, dann in den Speicher, ansonsten verwerfen und mittels Do-Schleife zum Start zurück und neue Zufallszahlen generieren, wird eine Bessere Lösung als die alte Gefunden, also xneu+yneu+zneu<xalt+yalt+zalt, dann überschreibst du das alte Ergebnis, wird was schlechteres gefunden, wieder zurück an den Start.


Und die Do-Schleife kannst Du ja in so einem leichten mathematischen Problem relativ oft durchlaufen lassen ohne Große Rechenzeiten erwarten zu müssen.





lg, Peter
kleinerChemiker ist offline   Mit Zitat antworten
Alt 14.05.2008, 12:44   #3   Druckbare Version zeigen
Pudutzki  
Mitglied
Themenersteller
Beiträge: 7
AW: Lineare Optimierung? Problem aus der Praxis.

Hallo,

danke für die schnelle Antwort.

Die Sache mit dem Abständen konnte ich soweit abklären, daß wir feste Werte für Überlappung und Abstand vorgeben. Hier muss also nicht mit Zufallsvariablen gearbeitet werden.

Mein Problem ist eher, daß ich keinen Ansatz finde, die Aufgabe mittels Ungleichungen zu lösen. Die Nebenbedingung, die Du aufgeführt hast verstehe ich nicht wirklich:

x+y+z --> min.

Was ist hier min.?

Wenn ich nun L vorgegeben habe, wie komme ich nun auf einfachstem Wege an x,y und z ?

Gruß
(der vollig ratlose) Matthias
Pudutzki ist offline   Mit Zitat antworten
Alt 14.05.2008, 12:58   #4   Druckbare Version zeigen
kleinerChemiker Männlich
Mitglied
Beiträge: 4.044
AW: Lineare Optimierung? Problem aus der Praxis.

jesas, min. heißt es soll minimal werden.
also hier ein stülperhaftes program im schnell durchlauf (basierend auf der Sprache Fortran95):

read*, L

T=Abstandstoleranz zum Rand
a=konst.=festgelegte Überlappung

do i=1,unendlich

x=random()
y=random()
z=random()

Lpr=(1490-a)*x+(1190-a)*y+(890-a)*z
s=x+y+z

if (L-T<Lpr<L .and. s<sopt) then

sopt=s
xopt=x
yopt=y
zopt=z

end if

end do


Kann sein, dass einige Befehle nicht ganz astrein sind, hab das auch nur in einem 20h-Kurs gelernt, aber so im Groben sollte es passen.


Wie ist eigentlich Dein Stundenlohn? Hätte jetzt gern meinen 10minütigen Anteil davon.



lg, Peter
kleinerChemiker ist offline   Mit Zitat antworten
Alt 14.05.2008, 13:01   #5   Druckbare Version zeigen
kleinerChemiker Männlich
Mitglied
Beiträge: 4.044
AW: Lineare Optimierung? Problem aus der Praxis.

Zitat:
Zitat von Pudutzki Beitrag anzeigen
...Die Sache mit dem Abständen konnte ich soweit abklären, daß wir feste Werte für Überlappung und Abstand vorgeben. ...

Moment mal, meinst Du, auch der Abstand zum Rand hin soll konstant sein? Denke, das ist keine so gute Idee, da kommt es schnell mal zu Gleichungen mit leerer Menge als Ergebnis.



lg, peter
kleinerChemiker ist offline   Mit Zitat antworten
Alt 14.05.2008, 13:36   #6   Druckbare Version zeigen
Pudutzki  
Mitglied
Themenersteller
Beiträge: 7
AW: Lineare Optimierung? Problem aus der Praxis.

Hallo Peter,

danke für Deine hilfreichen Antworten.

Die leere Menge macht nichts, da dann der Rahmen eh neu kalkuliert werden muss.

Das Einzige was ich an Deinem Programm nicht verstehe ist, wie die Endlosschleife beendet wird? Wie ist den die Abbruchbedingung?

Welchen initialen Wert muss denn sopt haben?

Ich werde hier nicht nach Stunden bezahlt, wenn ich das hier hinbekomme, werde ich ich mich aber gerne erkenntlich zeigen.
Pudutzki ist offline   Mit Zitat antworten
Alt 14.05.2008, 13:48   #7   Druckbare Version zeigen
kleinerChemiker Männlich
Mitglied
Beiträge: 4.044
AW: Lineare Optimierung? Problem aus der Praxis.

das mit unendlich in der do-schleife war nur ein scherz, du solltest da halt eine sehr große zahl hinschreiben, wie 100000 oder eine million oder so, damit es oft genug durchlaufen wird und man sicher sein kann, dass man ziemlich sicher die billigste lösung gefunden hat.

für den initialen wert von sopt kannst du irgendwas sehr großes nehmen, so dass aufjedenfall beim ersten durchlauf der do-schleife das sopt kleiner ist als das initiale sopt.


Bezüglich leerer Menge, dass das nicht stört, muss ich mir noch gedanken machen, denn dann, denke ich, sollte es kein problem mehr sein, das ganze auch analytisch zu lösen.

Muss jetzt aber in die uni, bin erst am abend wieder zurück.



lg, peter
kleinerChemiker ist offline   Mit Zitat antworten
Alt 14.05.2008, 15:18   #8   Druckbare Version zeigen
ThePat Männlich
Mitglied
Beiträge: 1.869
AW: Lineare Optimierung? Problem aus der Praxis.

Moin,

also was du moechtest ist eine Anzahl von Lampen der Sorte 1,2 und 3. Diese Variablen nennen wir mal i1,i2,i3. Zusaetzlich willst du noch einen Wert fuer die Ueberschneidung der Lampen, damit am Ende eine Laenge L moeglichst perfekt ausgefuellt ist. Dazu musst du folgende Funktion minimieren:

{\left(890i_1+1190 i_2 + 1490 i_3 - a\cdot 120\cdot (i_1 + i_2 + i_3 - 1) - L\right)^2}

Als Bedingungen hast du

{i_1,i_2,i_3\in \mathbb{N}\geq 0\\a\in \mathbb{R} \quad 0\leq a \leq 1}

Nehmen wir also an, du willst eine 12m lange Flaeche mit Lampen bestuecken, dann liefert mir Mathematica fuer diese Problem

Code:
NMinimize[
{(890 i1 + 1190 i2 + 1490 i3 - a*(i1 + i2 + i3 - 1)*120 - 12000)^2, 
Element[{i1, i2, i3}, Integers] && 
i1 >= 0 && i2 >= 0 && i3 >= 0 && 
Element[a, Reals] && a >= 0 && a <= 1}, 
{i1, i2, i3, a}]

{0., {a -> 0.408333, i1 -> 5, i2 -> 3, i3 -> 3}}
Das heisst du nimmst 5 Stueck 890mm Lampen, 3 Stueck 1190mm Lampen und von den 1490mm Lampen nimmst du auch 3. Alle Lampen laesst du mit 0.408*120=49mm ueberlappen.

Bei 5+3+3=11 Lampen ergeben sich 10 Zwischenraeume bei den Lampen. Bei 10*49mm=490mm haben wir also

{890\cdot 5+1190\cdot 3+1490\cdot 3 - 490=12000}

Perfekt.

Fuer die Minimierung benutzt Mathematica eins oder mehrere der folgenden Algorithmen:
  • NelderMead
  • DifferentialEvolution
  • SimulatedAnnealing

Es gibt aber auch einfacherer Verfahren. Dazu muesstest du ein Buch ueber Optimierung bemuehen. Falls du sowas wie Mathematica, MuPad, Maple, etc. kriegen kannst wuerde ich das vorziehen und schauen, ob die nicht sowas von Haus aus koennen.

Cheers
Patrick
__________________
"A difference is a difference only if it makes a difference" (Old saying, stolen from "How to lie with statistics")
pages: image processing and hardrock
ThePat ist offline   Mit Zitat antworten
Alt 14.05.2008, 16:51   #9   Druckbare Version zeigen
Pudutzki  
Mitglied
Themenersteller
Beiträge: 7
AW: Lineare Optimierung? Problem aus der Praxis.

Hallo zusammen und nochmals danke für eure Antworten.

Ich habe es jetzt mit der Methode von kleinerChemiker zufriedenstellend lösen können. Wie's aussieht schulde ich Dir einige Biere.

Gruß
Matthias
Pudutzki ist offline   Mit Zitat antworten
Alt 14.05.2008, 21:51   #10   Druckbare Version zeigen
kleinerChemiker Männlich
Mitglied
Beiträge: 4.044
AW: Lineare Optimierung? Problem aus der Praxis.

@ ThePat

Wie kommt man auf diese Formel, die Du angeschrieben hast? Erinnert mich irgendwie an das least-sqare-Verfahren, mit dem ich aber im Zusammenhang mit einer Extremwertaufgabe nicht viel anfangen kann.



@ Pudutzki

Und wie hast Du das jetzt genau gemacht? Mit konstant vorgegebener Überlappung und mit vorgegebenen Abstand zum Rand oder mit Toleranzgrenzen für beide?



lg, peter


PS: Bier mag ich keines, Cola ist mir lieber!
kleinerChemiker ist offline   Mit Zitat antworten
Alt 14.05.2008, 22:34   #11   Druckbare Version zeigen
Pudutzki  
Mitglied
Themenersteller
Beiträge: 7
AW: Lineare Optimierung? Problem aus der Praxis.

Ich habs mit konstant vorgegebener Überlappung und mit vorgegebenen Abstand gemacht.

Danke nochmals.
Pudutzki ist offline   Mit Zitat antworten
Alt 15.05.2008, 09:49   #12   Druckbare Version zeigen
ThePat Männlich
Mitglied
Beiträge: 1.869
AW: Lineare Optimierung? Problem aus der Praxis.

Moin,

Zitat:
Wie kommt man auf diese Formel
also vielleicht erstmal zu diesem Term:

{120\cdot a\cdot (i_1+i_2+i_3-1)}

Wenn ich a einschraenke auf das Intervall [0,1], dann kommt dort immer etwas raus in der Form "irgendwas zwischen 0 und 120" mal "Anzahl der Abstaende zwischend den Lampen". Irgendeine Loesung von Lampenanzahlen i1,i2,i3 hat immer genau (i1+i2+i3-1) "Lampe an Lampe Uebergaenge".

Dann willst du sicher wissen, warum ein Quadrat an der Formel ist. Das folgt daraus, dass wir diese Formel minimieren wollen. Nehmen wir als einfachen (und total sinnlosen) Fall, du hast eine einzige Lampe, die du von der Laenge her frei waehlen koenntest. Wie muesste denn diese Laenge sein, um moeglichst perfekt ueber die Laenge L zu passen? Einfacher Fall: die Lampe muss ebenfalls die Laenge L haben. Wie berechnen wir das aber? Das macht man indem man den Unterschied von Lampenlaenge l und "Wandlaenge" L minimiert. Dieser ist eigentlich:

{\sqrt{(l-L)^2}}

da das Weglassen der Wurzel das Minimierungs-Problem trotzdem erhaelt macht man das einfach. Diese Formel koennte man jetzt einfach mal per Extremwertaufgabe loesen und das Minimum waere bei l=L.

Das ganze Vorgehen ausgeweitet auf 3 Lampenanzahlen und einen Parameter a und man erhaelt meine Formel, die man dann mittels irgendeines Algorithmus minimieren muss. Man koennte dort im Uebrigen auch ohne Probleme noch den Abstand zu den Raendern einbringen.

Zitat:
Ich habe es jetzt mit der Methode von kleinerChemiker zufriedenstellend lösen können.
Also die Methode "Zufall" halte ich in dem Fall fuer noch schlechter als einfach alle Moeglichkeiten durchzugehen, aber gut. Was liefert denn dein Algorithmus, wenn wir eine Wandlaenge von sagen wir

L=22367mm

haben?

Cheers
Patrick
__________________
"A difference is a difference only if it makes a difference" (Old saying, stolen from "How to lie with statistics")
pages: image processing and hardrock
ThePat ist offline   Mit Zitat antworten
Alt 15.05.2008, 09:54   #13   Druckbare Version zeigen
kleinerChemiker Männlich
Mitglied
Beiträge: 4.044
AW: Lineare Optimierung? Problem aus der Praxis.

Zitat:
Zitat von Pudutzki Beitrag anzeigen
Ich habs mit konstant vorgegebener Überlappung und mit vorgegebenen Abstand gemacht.

Danke nochmals.

Gerne gerne, keine Ursache.

Und das funktioniert, wenn man eine konstant vorgegebene Überlappung und mit vorgegebenem ABstand das Programm schreibt, da finde er dann auch tatsächlich eine Lösung??
Wieviele iterationsschritte hast Du ihm gegeben?


@ ThePat

Alles klar, mit hat am Anfang nur das -L und das Quadrat über das ganze irritiert, da es mich sehr stark an das least square Verfahren bei Regressionen erinnert hat und unseres hier ja auf den ersten Blick garnix damit zu tun hat.
Nachdem ichs dann im SChlaf nochmals ruhig durchgegangen bin, hats *bing* gemacht und mir ging ein Licht auf.
In gewisser Weise ist das ja auch sogar verwandt mit der least square Methode bei Regressionsbestimmungen, finde ich.






lg, peter

Geändert von kleinerChemiker (15.05.2008 um 10:00 Uhr)
kleinerChemiker ist offline   Mit Zitat antworten
Alt 15.05.2008, 11:31   #14   Druckbare Version zeigen
Pudutzki  
Mitglied
Themenersteller
Beiträge: 7
AW: Lineare Optimierung? Problem aus der Praxis.

Zitat:
Und das funktioniert, wenn man eine konstant vorgegebene Überlappung und mit vorgegebenem ABstand das Programm schreibt, da finde er dann auch tatsächlich eine Lösung??
Wieviele iterationsschritte hast Du ihm gegeben?
Ja, ich optimiere allerdings nicht auf die geringstmögliche Anzahl von lampen, sondern auf maximale Auffüllung mit Lampen. Ab 100000 Iterationen wird jetzt immer das richtige Ergebnis gefunden.

Hier der JAVA Code:

PHP-Code:
    private static int depth;
    
    private static 
int x,y,z;
    
    private static 
int guess;
    private static 
int lastguess
    private static 
int xopt,yopt,zopt;

    private static final 
int MAXDEPTH 100000;
    
    public static 
boolean calculateFrame(int heightint widthint borderint overlap) {
        
        
0;
        
xopt 0;
        
yopt 0;
        
zopt 0;
        
depth 0;
        
guess 0;
        
lastguess 0;
        
        do {
            
Vector v createRandomPool(35);
                    
            
= (Integer)v.get(0);
            
= (Integer)v.get(1);
            
= (Integer)v.get(2);
            
            
guess =(1490-overlap)*x+(1190-overlap)*y+(890-overlap)*z;
            
            if (
guess <= (height-2*border) && guess >= lastguess) {
            
                
lastguess guess;
                
                
xopt x;
                
yopt y;
                
zopt z;
                
            }
            
depth++;
            
        } while(
depth MAXDEPTH);

        if (
xopt || yopt || zopt 0)
            return 
true;
        else 
            return 
false;
            
        
    }
    
    private static 
Vector createRandomPool (int countint range) {
        
        
Vector<Integer= new Vector<Integer>();
        
        
Random r = new Random();
        
        for (
int i 0count;i++ ) {
            
int randomNumber r.nextInt(range);
            
            
v.add(randomNumber);
        }
        
        return 
v;
        
    } 
Gruß
Matthias
Pudutzki ist offline   Mit Zitat antworten
Alt 15.05.2008, 18:50   #15   Druckbare Version zeigen
kleinerChemiker Männlich
Mitglied
Beiträge: 4.044
AW: Lineare Optimierung? Problem aus der Praxis.

Oh wow, JAVA ist ganz anders als Fortran, verstehe so gut wie 0 von den Befehlen da in JAVA, aber solange es funktioniert und das richtige rauskommt, kann man ja zufrieden sein!

@ The Pat

Ich glaube, ich habe da zwei Schönheitsfehler in Deiner Formel gefunden.
Wenn mich nicht alles täuscht, ist Deine Formel darauf ausgelegt, die Parameter so zu wählen, dass L so gut wie möglich erreicht wird.
Darin geht aber dann garnicht ein, dass die Anzahl der Lampen minimal werden soll, was ja wohl das Hauptaugenmerk der Firma sein wird.
Und das zweite, was mir aufgefallen ist, wie stellst Du sicher, dass a nur zw. 0 und 1 liegt, kann man das Mathematica einfach so sagen und es berücksichtigt das dann automatisch?


lg, peter
kleinerChemiker ist offline   Mit Zitat antworten
Anzeige


Antwort

Themen-Optionen
Ansicht

Gehe zu

Ähnliche Themen
Thema Autor Forum Antworten Letzter Beitrag
Frage aus der Histotechnik-Praxis gula Schwerpunktforum: pH-Wert und Gleichgewichtsberechnungen 0 14.09.2008 17:56
Lineare Optimierung ehemaliges Mitglied Vektorrechnung und Lineare Algebra 3 23.09.2007 23:21
Aufgabe aus der Praxis! Taxxis Verfahrenstechnik und Technische Chemie 10 10.02.2007 17:10
Beispiel aus der Praxis ehemaliges Mitglied Wahrscheinlichkeitsrechnung und Statistik 1 14.07.2005 12:22
lineare Optimierung arne Mathematik 1 06.04.2003 11:23


Alle Zeitangaben in WEZ +2. Es ist jetzt 22:42 Uhr.



Anzeige