Python Lineare Programmierung

Ich versuche, die folgende Gleichung zu lösen:Python Lineare Programmierung

maximize x^{T}Ax wo x ist ein 3 X 1 Vektor der Variablen maximiert werden und A ist eine 3 X 3 Matrix von Werten.

Also im Grunde x^{T} = [a,b,c] welche die Unbekannten maximiert werden und A so etwas wie

könnte

A = [ [29, 29, 79], [28, 28, 48], [9, 40, 0 ]]

Könnte jemand mir zeigen, wie dies zu repräsentieren in Form eines Maximierungsproblem unter Verwendung von Pulp oder eine andere lineare Programmierpaket in Python?

Jede Hilfe würde sehr geschätzt werden. Ich bin extrem neu in diesem Bereich und habe keine Ahnung, wie ich anfangen soll, diese Formulierung zu repräsentieren.

Ich habe bisher versucht, CVXPY zu verwenden, um diese Funktion zu modellieren. Ich habe den folgenden Code, aber einen Fehler sehe:

[1] A = np.array([[29,29,79],[28,28,48],[9,40,0]]) 
    [2] x=Variable(3) 
    [3] objective=Minimize(x.T*A*x) 
    Warning: Forming a nonconvex expression (affine)*(affine). 
    warnings.warn("Forming a nonconvex expression (affine)*(affine).") 
    [4] constraints=[0<=x,x<=1,sum_entries(x)==1] #what I'm trying to say is each entry of x should be between 0 and 1 and all entries should add up to 1. 
    [5] prob = Problem(objective, constraints) 
    [6] prob.solve() 
    DCPError: Problem does not follow DCP rules.

Quelle

2016-06-08 Nikhil

Nicht alle Fragen brauchen Code, aber in diesem Fall sieht es eher so aus, als hättest du die Frage einfach fallen lassen und gehofft, dass jemand die Lösung für dich schreibt. Das ist keine Programmierfrage, es ist eine mathematische Frage. Sie müssen ein rudimentäres Verständnis von Python haben, bevor irgendeine Antwort hier Ihnen helfen könnte. –

Ja, ich habe mehr als ein rudimentäres Verständnis von Python. Ich möchte nur, dass mir jemand in die richtige Richtung weist, was ein Beispiel oder etwas Ähnliches betrifft, da mir jegliche Art von Verständnis für das Gebiet der Optimierung oder linearen Programmierung und die entsprechenden Pakete in Python völlig fehlt. – Nikhil

Klingt wie Sie brauchen ein Tutorial, weil dies ein XY-Problem ist. Ihre eigentliche Frage scheint "Wie führe ich lineare Programmierung in Python durch?", Die zu breit erscheint. Eine schnelle Google-Suche ergab [dieses Tutorial über PuLP] (http://thomas-cokelaer.info/blog/2012/11/solving-a-linear-programming-problem-with-python-pulp/), die Ihnen helfen könnte . –

Ich glaube nicht, Pulp unterstützt quadratische Programmierung (QP). Ihr Modell ist quadratisch und PuLP ist nur für lineare Programmiermodelle (LPs und MIPs). Es gibt einige Möglichkeiten, QPs in Python auszudrücken. Leistungsfähige kommerzielle Solver bieten oft Python-Bindungen, und ansonsten können Sie sich beispielsweise CVXOPT ansehen. Beachten Sie, dass nur konvexe QPs "leicht" zu lösen sind. Wenn Sie eine nicht-konvexe QP haben, werden die Dinge viel schwieriger und Sie müssen vielleicht einen globalen Solver betrachten (dort nicht so viele Solver dieser Art). Nicht-konvexe QPs können über die KKT-Bedingungen als lineares MIP-Modell neu formuliert werden, obwohl diese Modelle nicht immer sehr gut funktionieren.

Quelle

2016-06-08 22:07:27

danke für die Eingabe. Ich verwende derzeit http://www.cvxpy.org/en/latest/, aber ich sehe einen Fehler, wenn ich versuche, die folgende Zielfunktion einzufügen: 'A = np.array ([[29,29 , 79], [28,28,48], [9,40,0]]) objective = Minimieren (xT * A * x) ' Der Fehler, den ich sehe, ist' Bilden eines nichtkonvexen Ausdrucks (affine) * (affin). warnings.warn ("Bilden eines nichtkonvexen Ausdrucks (affine) * (affine).") '. Irgendeine Idee, wie ich das beheben könnte? Oder was mache ich falsch? – Nikhil

Cvxopt ist für konvexe Probleme, und es scheint, dass Sie versuchen, ein nicht-konvexes Problem weiterzugeben. –

Hmmm, aber was ich nicht verstehe, ist, wenn das Problem inhärent nicht konvex ist oder wenn ich tatsächlich die Darstellung der Zielfunktion modifizieren kann, um sie konvex zu machen? Bedeutung kann ich das Problem irgendwie neu formulieren, um es konvex zu machen? @erwinkalvelagen – Nikhil

Antwort

Verwandte Themen