Problème algorithme simplexe

Version imprimable

16/01/2011, 16h37
muskachew

Problème algorithme simplexe

Bonjour,

j'ai un problème d'optimisation qui ne comporte au des contraintes d'égalité et de positivité (pas de borne supérieure à mes variables) que j'aimerais résoudre grâce à l'algorithme du simplex, j'ai donc consulté l'aide, et matlab m'explique qu'il faut utiliser la fonction linprog avec les options suivantes :

Code:

options = optimset('LargeScale','off','Simplex','on')

donc avant d'applique cette fonction à mon problème, j'ai effectué un test avec un problème de petite taille, pour comprendre comment marche la fonction linprog. Or il me retourne un vieux message d'erreur.

j'ai utilisé la fonction comme il suit :

Code:

linprog(f,[],[],A,b,0,[],[],options = optimset('LargeScale','off','Simplex','on'))

les entrées sont :

f =[1 2 1]
A=[2 1 -1;2 -1 5;4 1 1]
b=[2 6 6]

pourriez vous m'aider, car l'objectif de mon projet, n'est pas de passer du temps sur cet algorithme, mais juste de l'utiliser. Il se concentre plus sur la modélisation.

Merci
16/01/2011, 19h21
Jean Dumoncel
Bonjour

Il faut définir les options avant d'utiliser linprog :
Code:

1 2 options = optimset('LargeScale','off','Simplex','on'); x = linprog(f,[],[],A,b,0,[],[],options);

j'ai réessayé, mais voila la réponse de matlab (avec les donnée de mon exemple):

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
>> c=-[ 19 13 12 17 0 0 0];
>> A=[3 2 1 2 1 0 0;
1 1 1 1 0 1 0;
4 3 3 4 0 0 1;
]
 
A =
 
     3     2     1     2     1     0     0
     1     1     1     1     0     1     0
     4     3     3     4     0     0     1
 
>> b=[225;117;420]
 
b =
 
   225
   117
   420
 
>> options = optimset('LargeScale','off','Simplex','on');
>> x=linprog(c,A,b,[],[],[],[],[],options)
??? Error: File: simplexphasetwo.m Line: 432 Column: 9
 "z" previously appeared to be used as a function or command, conflicting with its use here as the name of a variable.
 A possible cause of this error is that you forgot to initialize the
 variable, or you have initialized it implicitly using load or eval.
 
 
Error in ==> simplex at 191
    [xs, fv, dualvars, exitflagPhase2, niters, basicVarIdx, nonbasicVarIdx] = simplexphasetwo(c1, A, b, lbs, ubs,
    basicVarIdx, nonbasicVarIdx, x1opt, maxiter, tol, verbosity, computeLambda);
 
Error in ==> linprog at 260
    [x,fval,lambda,exitflag,output] = simplex(f,A,B,Aeq,Beq,lb,ub,options,defaultopt,computeLambda);

17/01/2011, 17h02
muskachew

pas de solution ?

de plus j'ai un pb de programation basique, la question risque de vous sembler triviale à mon avis.

Dans le mini programme que j'essaie de faire, je veux remplir une matrice d'une certaine façon. Bon, j'ai géré ca par bloc, en multipliant élément pas élément de chaque ligne à un vecteur.

Matrice définie en deux blocs, donc deux vecteurs.

Or ce vecteur, je veux le remplir de 1 et de 0 d'une certaine façon (un vecteur étant le "négatif" de l'autre, cad ou il y a des zéros il y a des 1 et inversement).

Je voudrais donc appeler mon programme dans matlab, qu'il me pose les deux question qui aillent bien (qui sont en gros les coordonnées de l'élément que je veux changer dans le vecteur), et qu'il aille me positioner un 0 ou il faut dans le premier vecteur, et un 1 à la meme position dans le second vecteur.

Pouvez vous m'aider à programmer la question et comment stocker les "coordonées" que je veux ?

(je précise que je ne suis pas familier avec le concept de fonction, main, etc ... donc soyez indulgents svp)

Citation:

Envoyé par muskachew

j'ai réessayé, mais voila la réponse de matlab (avec les donnée de mon exemple):

Voici ce que ça donne avec MATLAB R2009a :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 >> c=-[ 19 13 12 17 0 0 0]; >> A=[3 2 1 2 1 0 0 1 1 1 1 0 1 0 4 3 3 4 0 0 1]; >> b=[225;117;420]; >> options = optimset('LargeScale','off','Simplex','on'); >> x=linprog(c,A,b,[],[],[],[],[],options) Exiting: The problem is unbounded; the constraints are not restrictive enough. x = 1.0e+016 * 1.0000 0 0 0 -3.0000 -1.0000 -4.0000
Quelle est ta version de MATLAB et sur quel système d'exploitation travailles-tu ?

Citation:

Envoyé par muskachew

Pouvez vous m'aider à programmer la question et comment stocker les "coordonées" que je veux ?
Code:

1 2 3 doc input % ou doc inputdlg

17/01/2011, 20h38
muskachew

je suis sous matlab R2009b.
Et je travailles bêtement sous windows vista.

merci