Bonjour,
Je souhaite transformer un problème non linéaire en linéaire et j'ai de la difficulté à procéder. Voici le problème que j'ai
Avec les contrainte suivantes
Je me demande si vous avez une suggestion de comment procéder? Je crois que je dois ajouter des contraintes supplémentaires, mais je ne suis pas certain de savoir comment les formuler.
Merci
Bonjour,
Je suppose qu'il s'agit de maximiser cette fonction?
Inutile de se compliquer la vie : il s'agit de simples fonctions du second degré sans termes croisés, dont l'optimum hors contraintes se trouve aisément :
X1= 2,5, x2=4, x3=5 x4=7,5, x5=10
Ensuite, comme les valeurs possibles sont discrètes, on prend pour chacune la plus proche de l'optimum:
X1=3, x2=3, X3=6, x4=6 x5=9
Il reste à vérifier que la contrainte x1+x3+x4 est satisfaite : cela marche...
Why, sometimes I've believed as many as six impossible things before breakfast
Bonjour,
C'est mon erreur, mais c'est une fonction que l'on veut minimiser. Pourriez vous dire s'il y a une transformation à faire pour obtenir vos résultats, car j'aimerais comprend la résolution derrière. D'après ce que je vois vous avez dérivé les termes avec les mêmes variables. Le seul problème c'est que dans mon cours, on utilise pas les dérivées et on demande de transformer le problème en un problème linéaire en nombre entier. Je possède un logiciel qui me permet de résoudre les problèmes linéaires. Est-ce qu'il y a une autre moyen d'y arriver sans utiliser les dérivées?
Merci encore!
Bonsoir, je souhaites transformer le système plus haut en un système linéaire par le biais d'ajout de contrainte(s). Je n'ai aucune technique précise pour savoir qu'elle contrainte ajoutée avec quelle variable. Quelqu'un peut m'aider?
Au revoir
Bonjour,
En posant Yk = Nkxk - xk2 , l'expression devient F = Y1 + Y2 + Y3 + Y4 + Y5
mais on n'échappe pas aux considérations exposées par Resartus.
S'il s'agit d'entiers comme cela paraît être le cas, rien n'interdit l'énumération de toutes les combinaisons possibles, puisqu'il y a
- 2 valeurs pour x2 et x4 ,
- 3 pour x1 ,
- 4 pour x3 et x5 ,
soit un total de 12*16 = 192 .Mais le procédé paraît grossier.
Cet énoncé est-il le point de départ de plus grands développements ?
Bonjour,
Étant donné que ma question doit se résoudre à l'aide d'un solveur de programme linéaire, j'ai bien peur d'avoir de la difficulté à résoudre les contraintes de type Nkxk - xk2 que vous proposez, car oui elles font du sens et oui les nombres doivent être entier. Avec mon solveur, les équations ne se ressouderont probablement pas? En fait, je viens de tester votre suggestion dans mon solveur et celui-ci n'obtient pas de solution.
Pour répondre à votre question Opabinia, non ce n'est pas un point de départ de plus grand développement.
Merci
L'algorithme traduisant directement l'énoncé conduit à un résultat conforme à celui de Resartus.
Néanmoins le procédé mis en oeuvre par ce dernier est beaucoup plus léger.
Bonjour,
Ma réponse (et le calcul de Opabinia) supposaient qu'on cherche le maximum de la fonction. Si, comme tu l'écris au post 3 c'est une minimisation qui est demandée, le problème est différent :
Dans ce cas on est dans un cas comparable aux optimisations linéaires, c'est à dire que c'est sur les sommets du polyèdre de définition qu'on va trouver le minimum.
Peut-être alors tes profs souhaitent-ils que tu te ramènes à un tel type de problème en traitant ces variables discrètes comme des variables continues bornées c'est à dire de rajouter des contraintes de type
x1>=3, x1<=12, X2>=3, etc., et de lancer le programme de résolution
Mais c'est quand même une approche risquée, car la résolution en variables continues peut très bien aboutir à une réponse inacceptable
De manière générale, l'optimisation en variables discrètes est difficile, et la seule solution exhaustive serait de faire comme le suggérait opabinia, c'est à dire de tester tous les cas.
Mais cela ne semble pas être la réponse attendue par tes profs...
Why, sometimes I've believed as many as six impossible things before breakfast
Oui c'est effectivement une minimisation. Je souhaite transformer l'objectif en une équation linéaire qui se résout avec un solveur linéaire et sans utiliser les dérivées pour y arriver.
J'avais penser résoudre ce problème en posant que y1 = 5*x1 - x1^2 et ainsi de suite comme on me l'a proposée et par la suite essayer d'ajuster la valeur au minimum le plus près, mais je ne peux tout de même pas résoudre les équations transformées, car il y a toujours un ''au carré'' de présent. Quelqu'un m'a proposé de poseren utilisant des variables binaires pour renforcer le choix et aussi en utilisant les valeurs entières possibles comme dans l'énoncé, mais elle est aussi dans le néant que moi.
L'énoncé est ici : ''Transformer le problème en un programme linéaire en nombres entiers. Mettez votre
modèle dans votre rapport. Résolvez-le avec un solveur et indiquez la solution''.
Je crois que les combinaisons doivent porter sur les indices, et les sommes sur les valeurs pré-calculées des fonctions
F(Ni, xij) = xij*(Ni - xij) .
