Mein MATLAB Forum - goMatlab.de

Mein MATLAB Forum

 
Gast > Registrieren       Autologin?   
Bücher:

Fachkräfte:
weitere Angebote

Partner:


Vermarktungspartner


Forum
      Option
[Erweitert]
  • Diese Seite per Mail weiterempfehlen
     


Gehe zu:  
Neues Thema eröffnen Neue Antwort erstellen

Optimierungsproblem (Zuordnungsproblem) definieren.

 

Harald
Forum-Meister

Forum-Meister


Beiträge: 20.061
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2014a
     Beitrag Verfasst am: 15.04.2019, 13:00     Titel:
  Antworten mit Zitat      
Hallo,

bei fmincon wirst du aber auch wieder das Problem haben, dass kontinuierlich variiert wird.

Wie gesagt: wenn die Matrizen nicht größer werden und es nicht sehr zeitkritisch ist, würde ich alle Kombinationen durchtesten.

Bei ga kannst du dir so behelfen, dass du mit CreationFcn Individuen erzeugst, die die Gleichungsnebenbedingungen erfüllen und auch CrossoverFcn und MutationFcn entsprechend implementierst. Das wird allerdings ein gewisser Aufwand sein.

1. Wahl bei dieser Problemgröße meines Erachtens wirklich: alle Kombinationen durchtesten.

Grüße,
Harald
_________________

1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
Private Nachricht senden Benutzer-Profile anzeigen


Bernd_Maler
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 26
Anmeldedatum: 10.04.19
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 22.04.2019, 14:45     Titel:
  Antworten mit Zitat      
Hallo,

ich habe das ganze mal etwas umformuliert, sodass ich ein lineares Problem habe. Und zwar habe ich das wie folgt gemacht:

minimiere \sum_{i=1}^m \sum_{j=1}^m \sum_{r=1}^n \sum_{s=1}^n x_{ir} x_{js} t_{rs} y_{ij}

habe ich zu einem linearen Problem machen wollen indem ich mir eine neue Variable q_{i,j,r,s} := x_{i,r}*x_{j,s}
Jetzt habe ich nur noch ein lineares Problem mit den folgenden zusätzlichen Nebenbedingungen:
q_{i,j,r,s} \geq 0 ,\\ q_{i,j,r,s} \leq x_{i,r} ,\\ q_{i,j,r,s} \leq x_{j,s} , \\ q_{i,j,r,s} \geq x_{i,r}+x_{j,s} - 1
Somit habe ich ein lineares Problem und möchte es nun in Matlab implementieren.
Meine Frage ist nun:

Wie implementiere ich die Nebenbedingungen ? Ich habe ja meine Bedingungen an die x_{i,j} und an meine q_{i,j,r,s}. Ich habe keine Ahnung wie ich das clever übergeben kann, sodass meine Gleichheits und Ungleichheitsrestriktionen an beide Variablen erhalten bleiben. Geht das irgendwie ?

Liebe Grüße !
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 20.061
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2014a
     Beitrag Verfasst am: 22.04.2019, 16:05     Titel:
  Antworten mit Zitat      
Hallo,

ich fürchte, das wird nichts. Es gibt ja eine Interaktion, die so nicht abgebildet wird.

Probierst du denn die Ansätze aus, die ich dir vorschlage?
Falls nein, warum nicht?
Falls ja, welche Probleme treten dabei auf?

Grüße,
Harald
_________________

1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
Bernd_Maler
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 26
Anmeldedatum: 10.04.19
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 22.04.2019, 16:29     Titel:
  Antworten mit Zitat      
Hallo Harald,

natürlich probiere ich deine Vorschläge, ohne die wäre ich total aufgeschmissen.
Ich kann es aber nicht als Schleife implementieren, weil meine Matritzen eigentlich viel größer sind. Ich schreibe nur dieses Programm für kleine Matritzen zum Test um zu gucken ob es was richtiges liefert. Mein x-Vektor hat jetzt 12 Argumente als Input, eigentlich sind es aber (wie ich jetzt festgestellt habe) circa 100. Da kann ich keine Schleife bauen und alles durchtesten, das muss ich mit einem Algorithmus optimieren lassen.
ga sollte ich bei einem ganzzahligen Optimierungsproblem mit Ungleichungen und Gleichungen bei den Nebenbedingungen nicht nehmen, weil dieses keine optimale, genaue Lösung liefert, sagte mein Chef.
Ich habe als Tipp bekommen mein quadratisches Problem als lineares umzuformulieren, weil Matlab damit super umgehen kann. Jetzt muss ich also das Problem was ich am Anfang formuliert habe linear machen und die Nebenbedingungen anpassen und es dann Matlab übergeben. Jetzt bin ich ratlos, wie ich das machen soll.

Liebe Grüße
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 20.061
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2014a
     Beitrag Verfasst am: 22.04.2019, 18:57     Titel:
  Antworten mit Zitat      
Hallo,

Zitat:
ga sollte ich bei einem ganzzahligen Optimierungsproblem mit Ungleichungen und Gleichungen bei den Nebenbedingungen nicht nehmen, weil dieses keine optimale, genaue Lösung liefert, sagte mein Chef.

Da hat der Chef grundsätzlich Recht. Die Frage ist, welche Alternative er sieht. Ansonsten ist man doch wieder bei ga.

Gedanke noch dazu: kannst du die Nebenbedingungen von 14.04.2019, 16:59 nicht so umformulieren, dass du den Index optimierst?
x1 muss ganzzahlig zwischen 1 und 4 sein
x2 muss ganzzahlig zwischen 5 und 8 sein
x3 muss ganzzahlig zwischen 9 und 12 sein
Damit hättest du für ga ein Problem ohne lineare Nebenbedingungen.

Grüße,
Harald
_________________

1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
Bernd_Maler
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 26
Anmeldedatum: 10.04.19
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 24.04.2019, 09:05     Titel:
  Antworten mit Zitat      
Guten Morgen,

Zitat:
x1 muss ganzzahlig zwischen 1 und 4 sein
x2 muss ganzzahlig zwischen 5 und 8 sein
x3 muss ganzzahlig zwischen 9 und 12 sein

Wie meinst du das ? Das verstehe ich nicht. Mein Chef meinte, dass ga ungeeignet ist und daher probiere ich es mit linprog oder irgendwas anderem. Das ist jetzt meine Idee:

Meine Nebenbedingungen vom 14.04. 16.59 sollten auch hier passen.
Ich kann das ganze zu einem linearen Optimierungsproblem umformen, also
minimiere  \ c^{T} * q
Beides Vektoren, die werden zwar riesig, aber so ist es linear und ich habe was ich will.
Mein q setzt sich dann zusammen aus meinen x_{i,j}. Alsoq_{i,j,r,s} := x_{i,r}* x_{j,s}. Es ist also ein Zeilenvektor aus 0en und 1en und natürlich nur dann 1, wenn x_{i,r} = x_{j,s} = 1. Mein c ist ebenfalls ein Vektor, der sich aus der Matrix M erstellt (die ich am 14.04.2019, 21:48 angegeben habe). In dem Fall werden einfach alle Zeilen von der Matrix M hintereinander geschrieben und so wird aus der 12x12 Matrix ein 144-er Vektor. Mein x bestehend aus den x_{i,j} war ein 12-er Vektor, also ist q auch ein 144er Vektor. Passt schonmal.
Meine Nebenbedingungen sind dann A und Aeq entsprechender Dimension vom 14.04. um 16.59. Also
A*q \leq (1,...,1) und
Aeq *q = (1,...,1).
Sollte so passen.
Jetzt habe ich also ein binäres lineares Optimierungsproblem mit Gleichungs - und Ungleichungsrestriktionen der Dimension 144.
Passt das so ? Ich glaube schon, dass es so Sinn macht.
Ich übergebe einen 144-er Vektor und bekomme den auch wieder als Ergebnis. Und den großen Vektor muss ich dann wieder aufdröseln, denn ich will ja wissen an welchen Stellen meine x 1 sind.
Jetzt meine Frage:
Macht das Sinn oder habe ich irgendwo einen Fehler ?
Wie sinnvoll ist es ein binäres, lineares Optimierungsproblem mit 144 Variabeln lösen zu wollen ? Oder kann ich es einfacher und "kleiner" optimieren?
Ich bin noch zu Hause und probiere es auf Arbeit dann mal aus.
Grade wenn mein x später eine 10x20 - Matrix ist, dann habe ich ein binäres lineares Optimierungsproblem mit 200*200 = 40.000 Variablen. Das ist dann schon etwas groß. Laughing

Liebe Grüße
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 20.061
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2014a
     Beitrag Verfasst am: 24.04.2019, 18:02     Titel:
  Antworten mit Zitat      
Hallo,

Zitat:
Wie meinst du das ?

Genau so wie es da steht. Statt einem Vektor v mit 4 Elementen, von denen genau eines 1 sein soll und die anderen 0, kannst du auch eine ganze Zahl k zwischen 1 und 4 nehmen und sagen:
Code:
v = zeros(1,4);
v(k) = 1;


Meines Erachtens geht das Umschreiben nicht, weil du dir mehr Freiheitsgrade nimmst als es gibt. Wenn z.B. ein x 0 ist, dann sind automatisch viele q 0. Umgekehrt aber nicht.

Wenn, dann intlinprog statt linprog.

Grüße,
Harald
_________________

1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
Bernd_Maler
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 26
Anmeldedatum: 10.04.19
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 24.04.2019, 20:09     Titel:
  Antworten mit Zitat      
Ach jetzt habe ich verstanden wie du das meinst mit den Indizes !
Das wäre evtl eine Idee, aber da habe ich noch weniger Ahnung wie das gehen soll, als jetzt eh schon. Aber bezüglich meinem q sollte doch was möglich sein. Mal angenommen meine Matrix X sieht jetzt so aus
Code:
X =

     1     0     0
     0     0     1


Also jetzt ist m=2 und n=3 von meinem Anfangs definierten Optimierungsproblem.
Nochmal zur Erinnerung, ich will dann haben minimiere \sum_{i=1}^m \sum_{j=1}^m \sum_{r=1}^n \sum_{s=1}^n x_{ir} x_{js} t_{rs} y_{ij} .
Dann muss ich ja erstmal mein q erzeugen, das wäre in dem Fall ein 3*3*2*2= 36-er Vektor, der nur an 4 Stellen eine 1 hat.
Also sieht q so aus
Code:
q_ijrs =

  Columns 1 through 17

     1     0     0     0     0     0     0     0     0     0     0     1     0     0     0     0     0

  Columns 18 through 34

     0     0     0     0     0     0     0     1     0     0     0     0     0     0     0     0     0

  Columns 35 through 36

     0     1


Entschuldige bitte für so viel Code, das kleine Beispiel wird schon sehr groß und unübersichtlich, aber du bist meine letzte Rettung. Also ist q =1 wenn
i=j=r=s = 1
i=1, j=2, r=1, s=3
i=2, j=1, r=3, s=1,
i=2, j=2, r=3, l=3

Also, q hat 36 Einträge. q(1) heißt i=j=r=s=1
q(9) heißt i=j=1 und r=s=3
q(10) ist dann i=1, j=2, r=1, s=1
usw.... Jetzt muss ich doch irgendwie mit Matlab aus dem Vektor q "rauslesen" können: Wenn q(i) = 1, dann gib mir die dazugehörigen Indizes i,j,r,s und für diese Indizes weiß ich dann, dass x_ir und x_js in dem Fall 1 sind. Wie mache ich das ? Wenn ich das habe, dann kann ich das Problem formulieren, bekomme als Ergebnis ein Vektor q der Größe m*m*n*n und kann den dann wieder in x umformen.
Verstehst du was ich meine ? Das geht doch hoffentlich in einer Schleife mit If Bedingungen oder so, hoffe ich !

Liebe Grüße und tausend Dank für deine Hilfen.
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 20.061
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2014a
     Beitrag Verfasst am: 24.04.2019, 20:41     Titel:
  Antworten mit Zitat      
Hallo,

reshape kann für die Umformung helfen, etwa in der Form
Code:
x = reshape(q, 3, 3, 2, 2)

Dabei auf die Reihenfolge achten.

Zitat:
Wenn q(i) = 1, dann gib mir die dazugehörigen Indizes i,j,r,s und für diese Indizes weiß ich dann, dass x_ir und x_js in dem Fall 1 sind.

Und da sind wir genau bei dem Problem, das ich sehe: was, wenn ein anderes q impliziert, dass x_ir = 0?

Grüße,
Harald
_________________

1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
Bernd_Maler
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 26
Anmeldedatum: 10.04.19
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 24.04.2019, 21:16     Titel:
  Antworten mit Zitat      
Hmmm, also mit reshape komme ich auf folgendes
Code:
y= reshape(q_ijrs, 3,2,3,2)

y(:,:,1,1) =

     1     0
     0     0
     0     0


y(:,:,2,1) =

     0     0
     0     0
     0     1


y(:,:,3,1) =

     0     0
     0     0
     0     0


y(:,:,1,2) =

     0     0
     0     0
     0     0


y(:,:,2,2) =

     1     0
     0     0
     0     0


y(:,:,3,2) =

     0     0
     0     0
     0     1


Bei deiner Reihenfolge in reshape (3,3,2,2) bekomme ich ja eine 3x3 Matrix,deswegen habe ich es mal so probiert.
Das sieht schon ziemlich gut aus, ich will nur eine von den Matritzen und zwar zum Beispiel y(:,:,3,2) + y(:,:,2,2) und das dann Transponiert und schon habe ich genau meine ursprüngliche Matrix wieder.
Ich hatte erst an eine Funktion gedacht, wie :
Code:
x= find(q_ijrs ==1)
und dann habe ich ja die Indizes auch, aber da weiß ich auch nicht wirklich.
Anderes Problem, was ich grade sehe: wie definiere ich denn sinnvoll mein q ?
Das ist nicht so einfach wie ich dachte...

Liebe Grüße

Bernd
Private Nachricht senden Benutzer-Profile anzeigen
 
Bernd_Maler
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 26
Anmeldedatum: 10.04.19
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 25.04.2019, 00:39     Titel:
  Antworten mit Zitat      
Ich habe es. Ich habe mir mit der Funktion
Code:
aus dem Vektor q alle Einträge mit 1 rausfinden lassen und dann in einer Schleife ganz einfach die Matrix X wieder erzeugt. Liefert auch das richtige Ergebnis.
Auch q sollte ich ganz unkompliziert erzeugen können. Mal sehen was dann morgen auf Arbeit rauskommt.

Grüße,

Bernd
Private Nachricht senden Benutzer-Profile anzeigen
 
Bernd_Maler
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 26
Anmeldedatum: 10.04.19
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 25.04.2019, 15:47     Titel:
  Antworten mit Zitat      
Hallo,

ich stehe vor meinem nächsten Problem und ich glaube ich habe jetzt verstanden, was du mit den Freiheitsgraden meinst.
Die Umwandlung von meinem m*m*n*n Vektor in meine mxn Matrix X ist kein Problem. Das habe ich so gelöst: y ist hierbei ein Vektor, indem die Indizes stehen, wo meine Lösung 1 ist. also y = find(optimales q ==1)

Code:
function [x1,x2] = lsg(y,T,Y)
%y ist find(Lösungsvektor ==1)
counter = 0;
z = 1;
x1 =zeros(size(Y,1),size(T,1));
x2 =zeros(size(Y,1),size(T,1));

for i = 1:size(Y,1)
   for j = 1:size(Y,1)
      for k = 1:size(T,1)
         for l = 1:size(T,1)

         counter = counter + 1;
            if counter == y(z)
            x1(i,k) = 1;
            x2(j,l) = 1;
               if z <= size(y)
                 z = z+1;
               end
            end
         end
      end
   end
end


end
 

und intlinprog wirft mir auch schnell eine zulässige Lösung raus. ABER:
Ich muss meine Nebenbedingungen verschärfen und ich weiß nicht wie.
Wenn ich das so betrachte: minimiere f^T*q. Dann muss ja f als Input für ein lineares Optimierungsproblem ein Vektor sein. Mein f setzt sich ja aus der Matrix T und der Matrix Y zusammen und da sind ja ein paar Nullen dabei und wenn intlinprog es minimiert, dann kommt als optimaler Wert 0 raus, was nicht sein kann.
Ich kann doch in den Nebenbedingungen nur mein q betrachten und ich muss ihm auch in den Nebenbedingungen übergeben, dass sich q_ijrs := x_ir* x_js und das dann für x_ij meine bekannten Nebenbedingungen gelten, also die vom 14.04. 16.59.
Bekomme ich es irgendwie hin, dass ich an mein x_ij die Nebenbedingungen fordere, aber eine optimale Lösung für mein q suche ??
Oder schaffe ich das irgendwie anders sinnvoll zu formulieren.
Ich bin schon wieder am verzweifeln und ratlos.

Liebe Grüße,

Bernd
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 20.061
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2014a
     Beitrag Verfasst am: 25.04.2019, 19:17     Titel:
  Antworten mit Zitat      
Hallo,

die Möglichkeit sehe ich eben leider nicht. Vor allem nicht ausschließlich mit linearen Nebenbedingungen.

Grüße,
Harald
_________________

1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
Bernd_Maler
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 26
Anmeldedatum: 10.04.19
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 25.04.2019, 20:16     Titel:
  Antworten mit Zitat      
Hm Mist, dann muss ich mal weiter basteln.
Ich bin grade auf die Funktion solve gestoßen. Kann ich mir damit nicht ein Problem definieren und es dann mit solve lösen ???

Grüße,

Bernd
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 20.061
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2014a
     Beitrag Verfasst am: 25.04.2019, 22:20     Titel:
  Antworten mit Zitat      
Hallo,

solve ruft im Hintergrund andere Solver auf. Es ist nur eine andere Art, ein Problem zu formulieren.

Grüße,
Harald
_________________

1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
Neues Thema eröffnen Neue Antwort erstellen

Gehe zu Seite Zurück  1, 2, 3  Weiter

Einstellungen und Berechtigungen
Beiträge der letzten Zeit anzeigen:

Du kannst Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
Du kannst Dateien in diesem Forum posten
Du kannst Dateien in diesem Forum herunterladen
.


goMatlab ist ein Teil des goForen-Labels
goForen.de goMATLAB.de goLaTeX.de


 Impressum  | Nutzungsbedingungen  | Datenschutz  | Werbung/Mediadaten | Studentenversion | FAQ | goMatlab RSS Button RSS


Copyright © 2007 - 2019 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks
Partner: LabVIEWforum.de

MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.