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.

 

Bernd_Maler
Forum-Anfänger

Forum-Anfänger


Beiträge: 26
Anmeldedatum: 10.04.19
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 10.04.2019, 16:08     Titel: Optimierungsproblem (Zuordnungsproblem) definieren.
  Antworten mit Zitat      
Guten Tag liebe Community,

ich bin ein Anfänger mit Matlab und entschuldige mich bereits im Voraus, falls ich Mist mache.
Ich möchte ein Optimierungsproblem definieren und zwar
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}
Dabei habe ich eine (nxn)-Matrix T und eine (mxm)-Matrix Y gegeben.
Zusätzlich habe ich die Nebenbedingung, dass

\sum_{i=1}^m x_{i} \leq 1 \forall j =1,...,n und
\sum_{j=1}^n x_{j} = 1 \forall i =1,...,m

Ich habe leider keine Ahnung wie ich das Matlab übergeben soll, damit es mir eine Lösung liefert. Für meine x soll also gelten: x_{ij} \in {0,1}.
Jetzt hätte ich gerne die Matrix X (wo nur 0en und 1en sind) und den optimalen Funktionswert dazu. Ich bin über jeden Hinweis sehr dankbar.

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: 12.04.2019, 17:11     Titel:
  Antworten mit Zitat      
Hallo,

wie groß sind die Matrizen?

Die Formulierung der Nebenbedingungen ist mir nicht klar. Sollte x nicht mit 2 Indizes angesprochen werden?

Für kleine Matrizen würde ich alle Kombinationen durchtesten.
Meine einzige Idee für große Matrizen wäre, mit ga die mxn-Matrix x als Vektor mit m*n Elementen aufzufassen und Integer Constraints anzugeben.

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: 14.04.2019, 16:59     Titel:
  Antworten mit Zitat      
Hallo Harald,

du hast natürlich komplett recht was die Nebenbedingungen angeht. Ich meine natürlich x_{i,j} in der Summe bei den Nebenbedingungen.
Ich habe das ganze jetzt implementiert und will es über quadprog lösen.
Mein Problem ist, dass er bei exitflag = -6 angibt und 0 Iterationen macht.
Ich habe es wie folgt lösen wollen: quadprog(M,f,A,b,Aeq,beq,lb,ub)
M ist eine (12x12)-Matrix, f ist ein Vektor aus 0en (12 Einträge), da ich f gar nicht betrachten möchte. Das ist A

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

Das ist b

1
1
1
1

Die Bedingung Ax \leq b ergibt mir \sum_{i=1}^4 x_{i,j} \leq 1 \ \ \forall j= 1...3.

Und die Matrix Aeq ist dann

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

mit beq =

1
1
1

Die Bedingung Ax = b ergibt mir \sum_{j=1}^3 x_{i,j} = 1 \ \ \forall i= 1...4.
Weil meine x_{i,j} \in{0,1} sein sollen, habe ich noch lb und ub dazu genommen, wobei lb der 0-Vektor mit 12 Einträgen ist und ub ist der 1-Vektor (auch 12 Einträge. Ich finde mein Problem nicht und warum matlab das mit quadprog nicht löst.
Ich habe noch vergessen zu erwähnen, dass mein x jetzt ein 12-er Vektor ist, damit ich das als x^THx formulieren kann. Mein x sind dann natürlich alle Einträge der Matrix, also ein Vektor mit 12 Einträgen.
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: 14.04.2019, 17:18     Titel:
  Antworten mit Zitat      
Hallo,

siehe hier:
https://www.gomatlab.de/exitflag-6-bei-quadprog-t47732.html

Die Frage einmal stellen reicht an sich ;)

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: 14.04.2019, 17:24     Titel:
  Antworten mit Zitat      
Hallo Harald,

danke für die schnelle Antwort. Das mit der Exitflag habe ich jetzt raus, aber wieso liefert er mir wenn ich quadprog anwende eine falsche Lösung.
Ich habe die Matritzen und Vektoren so definiert, wie ich es vorher beschrieben habe und er gibt mir als Lösung den Vektor x mit 12 1en als Eintrag.
Da sind doch aber meine Nebenbedingungen verletzt und ich kann meinen Fehler nicht finden.

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: 14.04.2019, 17:26     Titel:
  Antworten mit Zitat      
Hallo,

poste bitte den kompletten zusammenhängenden Code, inkl. Aufruf von quadprog. Sonst kann man dir schlecht helfen.

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: 14.04.2019, 17:38     Titel:
  Antworten mit Zitat      
Code:
[x,fval,exitflag,output,lambda] = quadprog(M,f,A,b,Aeq,beq,lb,ub).

Warning: Your Hessian is not symmetric. Resetting H=(H+H')/2.
> In quadprog (line 330)

The problem is non-convex.


x =

     1
     1
     1
     1
     1
     1
     1
     1
     1
     1
     1
     1


fval =

        1458


exitflag =

    -6


output =

  struct with fields:

            message: '↵The problem is non-convex.↵↵'
          algorithm: 'interior-point-convex'
      firstorderopt: 296.7112
    constrviolation: 3
         iterations: 0
       linearsolver: 'dense'
       cgiterations: []


lambda =

  struct with fields:

    ineqlin: [4×1 double]
      eqlin: [3×1 double]
      lower: [12×1 double]
      upper: [12×1 double]


Meine Matrix M sieht so aus:
0 14 28 42 0 6 12 18 0 20 40 60
14 0 21 35 6 0 9 15 20 0 30 50
28 21 0 49 12 9 0 21 40 30 0 70
42 35 49 0 18 15 21 0 60 50 70 0
0 10 20 30 0 0 0 0 0 24 48 72
10 0 15 25 0 0 0 0 24 0 36 60
20 15 0 35 0 0 0 0 48 36 0 84
30 25 35 0 0 0 0 0 72 60 84 0
0 20 40 60 0 12 24 36 0 2 4 6
20 0 30 50 12 0 18 30 2 0 3 5
40 30 0 70 24 18 0 42 4 3 0 7
60 50 70 0 36 30 42 0 6 5 7 0

Es tut mir leid, ich bin neu hier und bin mir nicht sicher ob ich jetzt das gemacht habe, was du wolltest.
Jetzt stehen hier alle Matritzen und alle Vektoren drin, die ich quadprog übergebe.
Mit der Beschreibung nachdem ich die Funktion quadprog aufrufe, kann ich absolut gar nichts anfangen.

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: 14.04.2019, 17:43     Titel:
  Antworten mit Zitat      
Hallo,

negative exitflag bedeutet, dass ein Problem aufgetreten ist und die Lösung nicht verwertbar ist. Welche, ist ja auch angegeben.
Die Alternative wäre ein anderer Algorithmus, der aber wiederum nicht alle Nebenbedingungen verwerten kann. Somit bliebe fmincon oder eben... wolltest du nicht, dass die Lösung nur 0 und 1 hat? Dann bietet sich (wie gesagt) nur ga an.

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: 14.04.2019, 17:51     Titel:
  Antworten mit Zitat      
Okay Dankeschön, dann gucke ich mir mal an wie die Funktion ga funktioniert und werde es darüber probieren. Genau diex_{ij} sollen nur 0 oder 1 sein.
Ich wundere mich aber etwas, warum er über quadprog eine unzulässige Lösung ausgibt. Beide Nebenbedingungen sind ja verletzt. Mal sehen was ga ausgibt. Vielen Dank für deine Hilfe !

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: 14.04.2019, 18:06     Titel:
  Antworten mit Zitat      
Hallo,

Zitat:
warum er über quadprog eine unzulässige Lösung ausgibt.

Weil mit dem Algorithmus keine gefunden werden kann, weil er nur für konvexe Probleme funktioniert und dieses als nichtkonvex erkannt wurde.

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: 14.04.2019, 21:35     Titel:
  Antworten mit Zitat      
Super, vielen Dank ! Ich wusste nicht, dass der nur für konvexe OP gedacht ist.
Ich habe es jetzt mit ga probiert und er funktioniert auch, also er gibt mir ein Ergebnis. Aber das Ergebnis ist nicht die beste Lösung. Er beachtet zwar die Nebenbedingungen, aber ich habe über Ausprobieren einen Wert gefunden, der einen niedrigeren Funktionswert liefert.

Code:
>> [x,fval,exitflag,output]=ga(@Test,12,A,b,Aeq,beq,lb,ub)
Optimization terminated: average change in the fitness value less than options.FunctionTolerance.

x =

  Columns 1 through 10

    0.0000    0.9992    0.0000    0.0000    0.9991    0.0000    0.0000    0.0000    0.0000    0.0000

  Columns 11 through 12

    0.0000    1.0000


fval =

  223.7938


exitflag =

     1


output =

  struct with fields:

      problemtype: 'linearconstraints'
         rngstate: [1×1 struct]
      generations: 98
        funccount: 19601
          message: 'Optimization terminated: average change in the fitness value less than options.FunctionTolerance.'
    maxconstraint: 8.8534e-04


Aber wenn ich es mit dem Vektor C=
1
0
0
0
0
1
0
0
0
0
1
0

probiere, komme ich auf einen niedrigeren Funktionswert.
Code:
Test(C')

ans =

   150
 


Aber mit ga bin ich schon mal einen Schritt weiter, dass er zulässige Sachen berechnet und überhaupt etwas löst. Vielen Dank schonmal dafür !
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: 14.04.2019, 21:48     Titel:
  Antworten mit Zitat      
Ich habe ganz vergessen meine Funktion Test zu posten. Sie ist ganz einfach und sieht so aus:
Code:
function Testi = Test (X)
M= [0,14,28,42,0,6,12,18,0,20,40,60;
14,0,21,35,6,0,9,15,20,0,30,50;
28,21,0,49,12,9,0,21,40,30,0,70;
42,35,49,0,18,15,21,0,60,50,70,0;
0,10,20,30,0,0,0,0,0,24,48,72;
10,0,15,25,0,0,0,0,24,0,36,60;
20,15,0,35,0,0,0,0,48,36,0,84;
30,25,35,0,0,0,0,0,72,60,84,0;
0,20,40,60,0,12,24,36,0,2,4,6;
20,0,30,50,12,0,18,30,2,0,3,5;
40,30,0,70,24,18,0,42,4,3,0,7;
60,50,70,0,36,30,42,0,6,5,7,0];

Testi = X*M*X';


end


Die (12x12)-Matrix M habe ich vorher berechnet und zur Probe mal statisch übergeben. Und beim ga kommt er nicht auf das optimale Ergebnis.
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: 15.04.2019, 10:07     Titel:
  Antworten mit Zitat      
Hallo,

Zitat:
Ich wusste nicht, dass der nur für konvexe OP gedacht ist.

Die Statusmeldung beklagt sich ja über die Nicht-Konvexität. In der Doku steht's auch.

Zitat:
Ich habe es jetzt mit ga probiert und er funktioniert auch, also er gibt mir ein Ergebnis. Aber das Ergebnis ist nicht die beste Lösung.

Das liegt in der Natur von ga. Wenn du nur 0 und 1 als Lösung haben willst, solltest du das Argument IntCon von ga nutzen. Dann dürfte es besser aussehen.

Bei 0/1 - Einträgen würde ich auch in Betracht ziehen, alle Kombinationen in einer for-Schleife durchzutesten. Sind ja "nur" 2^12 = 4096

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: 15.04.2019, 11:44     Titel:
  Antworten mit Zitat      
Hallo Harald,

dankeschön für deine Hilfe, du rettest mir hier echt den Arsch. Ich werde es zu Hause gleich mal mit IntCon probieren, aber so wie ich das verstehe (und wie du ja auch schon angedeutet hast), habe ich bei ga mit Intcon keine Gleichheitsrestriktionen. Das wäre schon blöd, da ich die brauche und nicht in Ungleichheitsrestriktionen umformulieren kann. Gibt es denn nicht eine Funktion die folgendes kann:
- x*M*x' minimieren für x gleich 0 oder 1 (wobei M eine Matrix ist und x ein Vektor)
- Restriktionen: A*x \leq b und Aeq*x = beq
- das richtige Ergebnis liefern

quasi ga mit Intcon und Gleichheitsrestriktionen und einem richtigen Ergebnis. Very Happy
Das mit der Schleife habe ich mir auch schon gedacht, aber ich bastele dieses Bsp nur um zu probieren ob ich es richtig implementiere. Mein x Vektor hat später circa 40 Argumente und das in einer Schleife ist glaube ich etwas zu aufwendig.

Vielen Dank und beste 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: 15.04.2019, 12:10     Titel:
  Antworten mit Zitat      
Ach mensch, ich muss mal anfangen richtig zu lesen. Du hast mir ja auch schon fmincon empfohlen und laut Beschreibung sollte der funktionieren. Da kann ich bei min f(x) mein x auch als Matrix übergeben und ich habe Gleichheits und Ungleichheitsrestriktionen zur Verfügung. Ich bin gespannt ob es funktioniert. Ich probiere es nachher gleich mal und mal sehen ob ich es hinbekomme ein x als Matrix zu übergeben.
Private Nachricht senden Benutzer-Profile anzeigen
 
Neues Thema eröffnen Neue Antwort erstellen

Gehe zu Seite 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.