Programmation linéaire Python

Je suis en train de résoudre l'équation suivante:Programmation linéaire Python

maximize x^{T}Ax où x est un vecteur à maximisée 3 X 1 des variables et A est une matrice de valeurs 3 X 3.

Donc, fondamentalement, x^{T} = [a,b,c] qui sont inconnues à maximisés et A pourrait être quelque chose comme

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

Quelqu'un pourrait-il me montrer comment représenter ce sous la forme d'un problème de maximisation utilisant de la pâte ou une autre linéaire paquet de programmation en python?

Toute aide serait grandement appréciée. Je suis extrêmement nouveau dans ce domaine et je ne sais pas comment commencer à représenter cette formulation.

J'ai jusqu'ici essayé d'utiliser CVXPY pour modéliser cette fonction. Je le code suivant, mais je vois une erreur:

[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.

Source

2016-06-08 Nikhil

Toutes les questions ne nécessitent pas de code, mais dans ce cas, il semble que vous ayez juste jeté la question et que vous souhaitiez que quelqu'un rédige la solution pour vous. Ce n'est pas vraiment une question de programmation, c'est une question de maths. Vous devez avoir une compréhension rudimentaire de Python avant toute réponse ici pourrait vous aider. –

Oui, j'ai plus d'une compréhension rudimentaire de python. Je voudrais juste que quelqu'un me pointe dans la bonne direction en ce qui concerne un exemple ou quelque chose de ce genre car je manque complètement de toute compréhension du domaine de l'optimisation ou de la programmation linéaire et des paquets correspondants en python. – Nikhil

On dirait que vous avez besoin d'un tutoriel, parce que c'est un problème XY. Votre vraie question semble être "Comment puis-je effectuer une programmation linéaire en Python" qui apparaît trop large. Une recherche rapide google a été lancée [ce tutoriel sur PuLP] (http://thomas-cokelaer.info/blog/2012/11/solving-a-linear-programming-problem-with-python-pulp/) qui pourrait vous aider . –

Je ne crois pas soutient la programmation quadratique LA PÂTE (QP). Votre modèle est quadratique et PuLP ne concerne que les modèles de programmation linéaire (LP et MIP). Il y a pas mal d'options pour exprimer les QP en Python. Les solveurs commerciaux haute performance fournissent souvent des liaisons Python, et vous pouvez par exemple regarder par exemple CVXOPT. Notez que seuls les QP convexes sont "faciles" à résoudre. Si vous avez une QP non convexe, les choses deviennent beaucoup plus difficiles et vous devrez peut-être regarder un solveur global (il n'y a pas autant de solveurs de ce type). Les QP non convexes peuvent être reformulées via les conditions KKT en tant que modèle MIP linéaire, bien que ces modèles ne soient pas toujours très performants.

Source

2016-06-08 22:07:27

merci pour l'entrée. J'utilise actuellement http://www.cvxpy.org/fr/latest/ mais une erreur se produit lorsque j'essaie de mettre la fonction objectif suivante: 'A = np.array ([[29,29 , 79], [28,28,48], [9,40,0]]) objective = Réduire (xT * A * x) ' L'erreur que je vois est' Formant une expression non convexe (affine) * (affine). warnings.warn ("Former une expression non convexe (affine) * (affine).") '. Une idée de comment je pourrais résoudre ça? Ou ce que je fais mal? – Nikhil

Cvxopt est pour les problèmes convexes, et il semble que vous essayez de transmettre un problème non-convexe. –

Hmm à droite mais ce que je ne comprends pas est, si le problème est intrinsèquement non-convexe ou si je peux réellement modifier la représentation de la fonction objectif pour la rendre convexe? Que puis-je reformuler le problème d'une manière ou d'une autre pour le rendre convexe? @erwinkalvelagen – Nikhil

Programmation linéaire Python

Répondre

Questions connexes