Optimierungsproblem (Zuordnungsproblem) definieren.

WICHTIG: Der Betrieb von goMatlab.de wird privat finanziert fortgesetzt. - Mehr Infos...

Partner:

Forum

Option

[Erweitert]

• Diese Seite per Mail weiterempfehlen

Gehe zu:

Bernd_Maler

Forum-Anfänger


	Beiträge: 26

	Anmeldedatum: 10.04.19

	Wohnort: ---

	Version: ---

Verfasst am: 10.04.2019, 16:08 Titel: Optimierungsproblem (Zuordnungsproblem) definieren.

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

Harald

Forum-Meister


	Beiträge: 24.448

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 12.04.2019, 17:11 Titel:

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 ;)

Bernd_Maler

Themenstarter

Forum-Anfänger


	Beiträge: 26

	Anmeldedatum: 10.04.19

	Wohnort: ---

	Version: ---

Verfasst am: 14.04.2019, 16:59 Titel:

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.

Harald

Forum-Meister


	Beiträge: 24.448

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 14.04.2019, 17:18 Titel:

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 ;)

Bernd_Maler

Themenstarter

Forum-Anfänger


	Beiträge: 26

	Anmeldedatum: 10.04.19

	Wohnort: ---

	Version: ---

Verfasst am: 14.04.2019, 17:24 Titel:

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

Harald

Forum-Meister


	Beiträge: 24.448

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 14.04.2019, 17:26 Titel:

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 ;)

Bernd_Maler

Themenstarter

Forum-Anfänger


	Beiträge: 26

	Anmeldedatum: 10.04.19

	Wohnort: ---

	Version: ---

Verfasst am: 14.04.2019, 17:38 Titel:

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]

Funktion ohne Link?

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

Harald

Forum-Meister


	Beiträge: 24.448

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 14.04.2019, 17:43 Titel:

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 ;)

Bernd_Maler

Themenstarter

Forum-Anfänger


	Beiträge: 26

	Anmeldedatum: 10.04.19

	Wohnort: ---

	Version: ---

Verfasst am: 14.04.2019, 17:51 Titel:

Okay Dankeschön, dann gucke ich mir mal an wie die Funktion ga funktioniert und werde es darüber probieren. Genau die $x_{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

Harald

Forum-Meister


	Beiträge: 24.448

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 14.04.2019, 18:06 Titel:

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 ;)

Bernd_Maler

Themenstarter

Forum-Anfänger


	Beiträge: 26

	Anmeldedatum: 10.04.19

	Wohnort: ---

	Version: ---

Verfasst am: 14.04.2019, 21:35 Titel:

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

Funktion ohne Link?

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

Funktion ohne Link?

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 !

Bernd_Maler

Themenstarter

Forum-Anfänger


	Beiträge: 26

	Anmeldedatum: 10.04.19

	Wohnort: ---

	Version: ---

Verfasst am: 14.04.2019, 21:48 Titel:

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

Funktion ohne Link?

Die (12x12)-Matrix M habe ich vorher berechnet und zur Probe mal statisch übergeben. Und beim ga kommt er nicht auf das optimale Ergebnis.

Harald

Forum-Meister


	Beiträge: 24.448

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 15.04.2019, 10:07 Titel:

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 ;)

Bernd_Maler

Themenstarter

Forum-Anfänger


	Beiträge: 26

	Anmeldedatum: 10.04.19

	Wohnort: ---

	Version: ---

Verfasst am: 15.04.2019, 11:44 Titel:

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

Bernd_Maler

Themenstarter

Forum-Anfänger


	Beiträge: 26

	Anmeldedatum: 10.04.19

	Wohnort: ---

	Version: ---

Verfasst am: 15.04.2019, 12:10 Titel:

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.

	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

Impressum | Nutzungsbedingungen | Datenschutz | FAQ |

RSS

Hosted by:

Copyright © 2007 - 2024 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks

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.