Le 03/12/2010 par norma :
Bonjour. J'ai rencontré le problème suivant: MIN Z= l3x-yl+v - S/C ..... J'ai pu le résoudre grâce aux réponses des membres animant l'une des discussions portant sur la valeur absolue en programmation linéaire, mais ce que je n'ai pas saisi, c'est le sens de cette fonction. C'est à dire je n'arrive pas à imaginer l'énoncé du problème initial de telle manière qu'apparaît une valeur absolue lors la formulation de la fonction d'objectif. Je vous serais très reconnaissante si vous pouviez m'éclairer ou me donner un exemple montrant une problématique dont la résolution nécessite l'introduction de la valeur absolue lors de la formulation de la fonction d'objectif.
Le 06/12/2010 par convexe :
Je pense qu'un exemple classique c'est la minimisation d'une distance, pour avoir un PL on utilise en général la norme 1 ou la norme sup (d'où la valeur absolue).
Exemple :
Tu cherches le point X le plus proche de A (donné) dans un domaine :
Min | X - A |
SC ...
Le 06/12/2010 par norma :
Mille Mercis Convexe. Grâce à toi , je crois avoir compris le principe : On introduit la valeur absolue lors de la formulation de la fonction d'objectif pour exprimer l'existence d'une relation entre deux variables , dans ton exemple X et A qui doivent être proches (Tu me corriges si ce n'est pas ça!). Maintenant, tu m'as posé une nouvelle colle, Qu'est -ce- que c'est que ces normes 1 et sup: Le fait est que je suis étudiante en Management et ce sont mes premiers pas dans la recherche opérationnelle. Encore Merci et à bientôt.
Le 09/12/2010 par convexe :
Pour ta question sur les normes, je te renvoie à wikipédia : http://fr.wikipedia.org/wiki/Norme_%28math%C3%A9matiques%29
Section Exemples / En dimension finie. (norme sup = norme infinie)
Le 09/12/2010 par norma :
Encore merci convexe. J'ai consulté le lien comme tu me l'as conseillé, ça m'a donné une petite idée sur les normes que tu as mentionnées, mais je vois que ça relève d'un niveau en mathématiques bien trop supérieur pour moi. Bref encore une petite question si ça ne t'ennuie pas [ je voudrais encore profiter de tes connaissances ;-) ] peux-tu me confirmer la justesse de la manière dont j'ai résolu le problème posé dans ma précédente participation: j'ai remplacé la valeur absolue l3x-yl par une variable w. En utilisant la méthode du simplexe, je suis arrivée à un résultat w=6, donc j'ai déduit -sans grande conviction- en me référant à d'autres participations sur ce forum (liées à la linéarisation de la valeur absolue) que les valeurs de x et y doivent être telles que
-6<= l3x-yl <= +6. Est-bien ça??? A bientôt j'espère.
Le 09/12/2010 par norma :
J'avais oublié, en programmation linéaire quand on a w=lfl, pourquoi déduisons-nous que -f<=w<=f et non pas w=f et w=-f?? Je te saurais fort gré si tu pouvais répondre à mes questions, car j'avoue être dans le brouillard concernant ce cours de PL. Encore merci
Le 10/12/2010 par convexe :
Je reprend le poste http://www.roadef.org/forums/index.php?action=vthread&forum=3&topic=842.
Tu remplaces : |3x-y| = s1 + s2
Tu rajoutes dans les contraintes :
3x-y = s1 - s2
s1>=0
s2>=0
s1 représente partie positive de la valeur absolue et s2 la partie négative.
A première vu on peut se dire "oui mais qu'est qui empèche d'avoir s1 > 0 et s2 > 0 ?". La réponse est un peu théorique et a été donnée par dgravot dans le poste précédent, si s1 >0 alors s2 = 0 et inversement.
Il te suffit donc d'appliquer le simplexe sur ce problème modifié pour avoir la bonne solution pour tes variables x et y.
Le 10/12/2010 par norma :
OK Convexe. Donc selon toi, je ne dois pas remplacer toute la formule 3x-y par une autre variable w mais je devrais la remplacer plutôt par deux variables de telle manière à ce que S1=3x et S2= Y.
Désolée pour toutes ces questions Convexe, mais, pour une raison que j'ignore, ce problème me cause un véritable bug dans le cerveau. A bientôt j'espère et surtout MERCI encore.
Le 10/12/2010 par convexe :
C'est pas S1=3x et S2= Y, mais 3x-y = S1 - S2.
Poste ton problème, se sera plus simple :)
Le 10/12/2010 par norma :
Re-bonjour ,
OK Convexe, merci de te casser la tête à ce point pour moi. Voilà je vais recopier ci-dessous le problème exact:
MIN Z= 2X3-X1+X2
S/C
4X1-X2+2X3=6
2X2-4X3>=4
X1,X2,X3>=0
Encore une fois, merci pour le temps que tu me consacres. A bientôt.
P.S. Vas-y très doucement lors la présentation de la solution, comme tu as dû le remarquer: tu as affaire à une véritable bleue en recherche opérationnelle :(
Le 10/12/2010 par norma :
Et Voilà je me suis trompée en recopiant la fonction d'objectif, je rectifie:
Min Z= l2X3-X1l+X2.
Le 10/12/2010 par convexe :
problème linéarisé :
MIN Z= S1+S2+X2
S/C
2X3-X1 = S1 - S2
4X1-X2+2X3=6
2X2-4X3>=4
X1,X2,X3,S1,S2>=0
Le 10/12/2010 par norma :
Merci Convexe. Seulement Si on met:
2X3-X1 = S1 "moins" S2
Pourquoi a-t-on au niveau de la fonction d'objectif
Min Z= S1 "plus" S2 + X2 ???? Désolée je bloque vraiment dessus.
Le 10/12/2010 par norma :
Je veux dire:
lS1-S2l est-elle équivalente à S1+S2????
Mettons S1=3 et S2=4
l3-4l = l-1l = 1 et non 7 [3+4]
A moins que ces S1 et S2 aient une signification particulière et que j'ignore.
Encore désolée de devoir t'importuner à ce point Convexe. mais j'aimerais vraiment comprendre ce qui m'échappe parce que là c'est le véritable court-circuit dans mon cerveau.
Le 13/12/2010 par convexe :
S1 = 3 et S2 = 4, c'est pas possible car S1 et S2 ne peuvent pas être simultanément non nuls (propriété du simplexe).
Exemple :
y = S1 - S2
|y| = S1 + S2
si y = 3 alors S1 = 3 et S2 = 0, |y| = S1 + S2 = 3
si y = -3 alors S1 = 0 et S2 = 3, |y| = S1 + S2 = 3
S1 représente la partie positive de y, et S2 sa partie négative.
Le 13/12/2010 par norma :
MEEEEEEEEEEEEEERCCCIIIIIIIIIIIIII COVEXE :-D, je commençais à déjanter avec ce problème . Je ne te remercierai jamais assez, pour la solution d'une part mais aussi et surtout pour ta grande PATIENCE face à ma grande ignorance. A bientôt et encore Mille Merci.
P.S. J'espère que j'ai vraiment tout compris cette fois-ci ;-)
Le 13/12/2010 par norma :
Encore une chose Convexe!!! vraiment désolée mais je voudrais te poser une petite question supplémentaire. Tu dois te dire que je suis vraiment maniaque, mais le fait est que je n'ai pas encore de bonnes bases en recherche opérationnelle . Tu dis que S1 et S2 ne peuvent pas être toutes les deux des variables de bases, c'est à dire non nulles, alors, si tu as encore du temps à me consacrer, je voudrais bien connaître la genèse de cette propriété du simplexe. Mille Merci pour l'excellent professeur que tu représentes pour moi Convexe et encore Mille fois PARDON pour le casse-tête que je te cause.
Le 14/12/2010 par convexe :
Je ne connais pas la démonstration exacte.
Un truc qui aide, c'est souvent de faire un petit dessin 2D des contraintes et de regarder les points extrèmes (qui sont les solutions du simplexe) :
Par exemple pour ton problème, prenont la contrainte :
Y = S1 - S2
suppose que Ymin < Y < Ymax, avec par exemple Ymin < 0 et Ymax > 0.
Tu trace les 2 fonctions 2D ( abscisse : S2, ordonnée S1 ) :
S1 = f(S2) = S2 + Ymin
S1 = g(S2) = S2 + Ymax
Tu verras très bien les 3 points extrêmes :
s1 = 0 et S2 = 0
S1 = Ymax et S2 = 0
S1 = 0 et S2 = Ymin
Le 14/12/2010 par norma :
Je vais effectuer la représentation géométrique comme tu me l'as conseillé en espérant comprendre cette fois-ci. Encore une fois, Je suis sincèrement ravie d'avoir rencontré l'excellent professeur que tu es, tu m'es d'un grand secours. A Bientôt et encore Merci pour la gentillesse dont tu fais preuve à mon égard, en me consacrant tout ce temps et surtout en fournissant tout cet effort d'explication de telle manière à me simplifier les choses au maximum . MERCI et encore MERCI :-)
Le 14/12/2010 par norma :
Re Convexe. Je me permets -si ça ne t'ennuie pas- de profiter encore un peu de tes connaissances: Je viens de consulter la participation de dgravot sur le lien suivant:
http://www.roadef.org/forums/index.php?action=vthread&forum=3&topic=842
et lui, a trouvé un autre fil d'Ariane: il explique la même chose que toi à l'aide du dual du problème. Est-ce possible? et si oui comment?
P.S. Tu dois penser que tu ne te débarrasseras jamais de moi, mais j'aimerais vraiment comprendre. Encore Mille fois PARDON Convexe .
Le 15/12/2010 par convexe :
C'est possible exploitant la structure du problème dual, mais mes cours de PL remonte à trop loin pour que je me souvienne comment :)
Le 15/12/2010 par norma :
MMMMMMEEEEEEERRRCCCI Convexe :-) Je me contenterais donc de l'astuce que tu m'as donnée ... mais il reste une chose que je voudrais confirmer si ça ne t'ennuie pas: A quoi fais-tu référence avec Ymin et Ymax? Est-ce des valeurs de Y que je peux donner de façon aléatoire juste pour avoir une idée sur la représentation géométrique de la contrainte Y=S1-S2, ou est-ce obligatoirement les valeurs de Y (>0 ou <0)=S1-S2 après la résolution du programme linéaire à l'aide du simplexe???
Le 16/12/2010 par convexe :
Le dessin, c'est juste pour te donner une intuition de "pourquoi ça marche". En pratique tu ne connais pas à l'avance le Ymin et le Ymax.
Tu peux prendre n'importe quelle valeur pour Ymin et Ymax, c'est juste plus parlant si tu prend Ymax > 0 et Ymin < 0.
Le 16/12/2010 par norma :
ENCORE MERCI CONVEXE aussi bien pour ta patience que pour la rapidité de tes réponses . Bonne journée et à très bientôt :-)
P.S. Je suis ravie d'avoir rencontré l'excellent professeur que tu es, aussi, je te prie de me permettre de t'appeler au secours si j'ai un autre pépin en Recherche Opérationnelle.
Le 23/12/2010 par norma :
Bonjour,
J'ai rencontré un problème où il est demandé de présenter la solution géométrique d'un programme linéaire présentant un systèmes d'inéquations à trois inconnues et non pas deux. Or, je ne sais pas comment effectuer une représentation géométrique dans un espace 3D. Auriez-vous un document présentant de manière simple les rudiments de cette représentation? Encore Merci.
Le 04/01/2011 par convexe :
Salut,
Si une de tes contraintes est une contrainte d'égalité, tu peux supprimer une des variables par subsitution pour avoir que 2 variables (et donc un dessin 2D)
Le 04/01/2011 par norma :
Salut Convexe
Ça me fait plaisir de te "revoir". OK, c'est ce que j'ai fait, et tu me dis -s'il te plait- si c'est bien ça: j'ai utilisé la contrainte où il y a l'équation pour remplacer une des variables par les deux autres, puis j'ai transformé cette même contrainte après suppression de la troisième variable qu'elle contenait en une contrainte d'infériorité (<=) au lieu d'égalité pour que le programme reste juste.
Mais, maintenant s'il n'y avait pas eu cette contrainte d'égalité fort salvatrice d'ailleurs, comment aurais-je pu faire????
A Bientôt j'espère. Je ne te remercierai jamais assez Convexe .
Le 05/01/2011 par convexe :
Oui c'est ça.
En général si on te demande dessiner un domaine, c'est forcément que tu peux te ramener à un cas 2D. Sinon en 3D, tu prends du papier et un ciseau et tu fait du découpage :), mais ça devient plus de l'art plastique que de la PL.
Le 05/01/2011 par norma :
Salut,
Oui, ça je l'ai bien constaté mais je me disais que peut-être...!!!, Parce que si tu te réfères au livre de Robert Faure par exemple, il effectue la représentation géométrique en 3D, mais cerner et comprendre ses uvres d'art relève de l'acrobatie cervicale. Je ne vois rien à part des surfaces qui se chevauchent et le plus drôle, c'est qu'on est sensé s'y retrouver et définir l'optimum dans ce schéma "effrayant".
Je voudrais te consulter sur une autre chose Convexe. On m'a conseillé de passer au programme dual [encore le dual :)] sous prétexte que le nombre de variables diminue au niveau de celui-ci, faire sa représentation géométrique, puis déduire la solution du primal. Est-ce faisable?
ENCORE MEEEERRRRRCCCI MILLE MILLIONS DE MILLIARDS DE FOIS CONVEXE. A bientôt.
Le 06/01/2011 par convexe :
Effectivement c'est une bonne idée de passer au dual.
Quand tu passes au dual, tes contraintes deviennent des variables et inversement, donc si tu a beaucoup de variables mais pas beaucoup de contrainte ça devient intéressant.
Par exemple :
Primal : 20 variables + 2 contraintes -> difficile à dessiner
Dual : 2 variables + 20 contraintes -> facile à dessiner
Une fois que tu as la solution du dual, tu peux retrouver facilement celle du primal (cf théorème de la dualité forte http://www.iecn.u-nancy.fr/~scheid/Enseignement/dualite.pdf)
Le 06/01/2011 par norma :
OK. Alors, c'est intéressant seulement quand il y a deux contraintes pas plus.
Encore une chose s'il te plaît Convexe, as-tu une idée sur la façon de dessiner dans un espace 3D -juste pour savoir-, est-ce le même que dans un espace 2D? C'est à dire on met X1=0, X2=0 pour avoir X3 et vice versa jusqu'à l'obtention de trois points (au lieu de deux), puis on relie ces trois points...??? parce que dans les représentations 3D je ne vois que des triangles, et ne me demande surtout pas pas de retrouver la direction où se situe le domaine des solutions admissibles :-(
Encore Merci beaucoup beaucoup beaucoup x 999999999999 de fois Convexe. A bientôt.
P.S. Mille MERCIS pour le lien que tu m'as donné (théorème de la dualité forte) , ça m'as permis de comprendre le dual et d'avoir une idée sur les règles du passage de la solution de celui-ci à celle du primal .
Le 07/01/2011 par convexe :
Oui c'est ça, en 3D, une contrainte = 1 plan. Donc tu traces chaque contrainte en prenant 3 points.
Visuelement, c'est comme si tu partais d'un cube (définie par les bornes de x1,x2 et x3). Puis tu rajoutes chaque contrainte (plan) pour "couper" ce cube.
Le 07/01/2011 par norma :
OK. Mais comment situer le domaine des solutions admissibles par rapport à ces plans? Est-ce le même principe que pour la représentation 2D? C'est à dire on prend un point de test (0,0,0) et on vérifie s'il réalise les contraintes pour voir de quel côté se situe le domaine des solutions admissibles par rapport aux plans au lieu des droites dans les représentations 2D. Mille MERCI Convexe. A bientôt.
Le 07/01/2011 par convexe :
Oui ta méthode marche (mais il y a peut-être plus simple ??)
Le 07/01/2011 par norma :
Je ne sais pas s'il y a plus simple, c'est pourquoi je te le demande Convexe. Dans les bouquins que j'ai consulté, ce n'est même pas expliqué, il y a juste la représentation graphique "renversante" d'ailleurs tellement le nombre de contraintes est important, puis la solution optimale est donnée directement de la façon suivante par exemple: le polyèdre des solutions OABCDEFPQR est coupé par le plan parallèle au plan ICJ qui a un point de contact avec Q (X1,X2,X3) d'où X1*=X1, X2*=X2, X3*= X3 avec Z*=tant.
MILLE MEEERRRCIS Convexe. A bientôt.
P.S. Désolée de te poser autant de questions. et encore Merci pour l'aide que tu m'offres si généreusement.
Le 09/03/2011 par norma :
Bonjour,
Dans le cas d'un problème de transport, si on tombe sur un cas de dégénérescence (nombre des variables de base <n+m-1), Quelle variable doit-on intégrer dans la base de façon à ce qu'on puisse constituer tous les chemins à partir des autres cases restées vides (et ainsi définir les variables entrante et sortante afin d'optimiser la solution)?
J'ai trouvé une méthode, comme quoi "à chaque fois qu'on sera amené à effectuer une attribution qui sature à la fois une ligne et une colonne, on choisira, dans cette ligne ou dans cette colonne, une autre case que celle qui reçoit l'attribution , pour y inscrire explicitement 0 (plus précisément, on choisit la case de coût unitaire minimal pour y inscrire 0.
et dans le cas où ce coût minimal se retrouve dans plus d'une case
de ces rangées, on tranche au hasard).
La variable associée à cette case sera considérée comme une
variable de base prenant la valeur 0.
Mais ça ne marche pas avec le cas que j'ai, car je n'arrive pas à constituer toutes les boucles qui permettent de calculer les Sij des cases vides et ainsi de définir la variable sortante. A l'Aide SVP et A tout éclaireur MERCI.
Le 10/03/2011 par convexe :
Hello :)
Tu peux poster ton exemple (si il est pas trop gros).
Le 11/03/2011 par norma :
Hello Convexe :)
Ça me fait toujours plaisir de te retrouver. Désolée, je n'ai pas pu me connecter et donc consulter ta réponse plus tôt.
Voici le tableau représentant les coûts unitaires, demandes, et disponibilités:
....................................Ai
.......4 ....5.... 3.... 7.. // 30
.......3 ....4.... 2.... 3 ..// 5
.......7 ....5.... 2.... 4 ..// 20
------------------------------
Bj// 30.. 15.. 10.. 5.. // 60/55
Il est demandé de trouver la solution initiale en utilisant la méthode du "Coin Nord-Ouest". (Avec les méthodes de Vogel et des coûts minimums on peut éviter la solution dégénérée.)
Mille Merci de répondre à chaque fois à mes appels "au secours" Convexe. A bientôt.
Le 14/03/2011 par convexe :
Si j'ai bien compris la méthode du "Coin Nord-Ouest", ça fait :
30 .. .. ..
.. 5 .. ..
.. 10 10 ..
Coût : 30x4 + 5x4 + 10x5 + 10x2 = 210
Je ne vois pas trop le problème de solution dégénérée dont tu parles. Est-ce que j'aurais raté quelque chose ?
Le 14/03/2011 par norma :
Salut Convexe,
Oui, c'est ça, et si on prend en considération la ligne fictive qu'on doit ajouter pour assurer l'équilibre entre la demande et les disponibilités (Disponibilités réelles = 55 + ligne fictive avec disponibilité = 5, ce qui donne 60), ceci donne plus précisément:
30 .. .. . .
.. 5 .. ..
.. 10 10 ..
.. .. .. 5 ligne fictive
Coût= 30(4)+ 5(4)+ 10(5) + 10(2)+ [5(0)]= 210.
d'où le nombre de variables de base= 5 <n+m-1(=7), ce qui fait qu'il nous manque deux cases à remplir pour que la solution initiale soit admissible, donc, on est face à un cas de dégénérescence (5 cases pleines au lieu de 7).
Pour rappel Convexe:
théorèmes liés au problème de transport:
1/ Somme des Demandes (Ai) doit être= Somme des Disponibilités (Bj) sinon nécessité d'ajouter selon le cas, une ligne ou colonne fictives.
2/ le nombre des variables de base doit être= n+m-1 ( rang de la matrice correspondant au contraintes du problème de transport)
n: nombre de ligne=4 dans notre exemple
m= nombre de colonnes= 4 aussi
n+m-1= 4+4-1=7 dans notre exemple.
Encore MERCI Convexe pour l'aide que tu m'offres. A bientôt.
Le 14/03/2011 par convexe :
J'avoue que je ne connais pas trop ces théorèmes.
Moi j'utilise des algos de flots pour résoudre les problèmes de transport :
http://www.math.u-bordeaux.fr/~gstauffer/cours/MSE3211A/MSE3211A_5.pdf
J'espère que ça pourras t'aider.
Le 14/03/2011 par norma :
Merci beaucoup beaucoup Convexe.
Je tâcherai de comprendre ces algos de flots, à première vue ils offrent une meilleure visibilité du problème, mais malheureusement je suis tenue d'appliquer les théorèmes sus-cités.
Voilà le lien où j'ai trouvé un excellent cours les concernant, mais le comble de la malchance "IL N'EST PLUS DISPONIBLE":
http://www.ift.ulaval.ca/~Dupuis/Optimisation lineaire et applications/Probleme de transport/Probleme de transport.ppt
J'ai téléchargé le cours mais je ne trouve pas comment te l'envoyer directement sur le forum.
Le 14/03/2011 par norma :
Re Convexe.
Voici le lien du document que j'ai fini par faire héberger, si tu as encore du temps à me consacrer, je te prie de bien vouloir le consulter et me dire ce que tu as compris, car je n'arrête pas d'appliquer et de ré-appliquer cette méthode en vain, je ne sors pas de ce problème.
Encore Mille Milliards de fois "Merci" Convexe. A bientôt j'espère.
le document en question:
http://www.sendspace.com/file/fj7n4u
Le 15/03/2011 par convexe :
J'ai un peu relu ton powerpoint. Il est écrit qu'il faut que le nombre de variables non null doit être inférieur ou égale à n+m-1 et non strictement égale.
J'ai vérifié, la solution proposée ci-dessus est bien une solution de base.
Le 15/03/2011 par norma :
Merci Convexe,
Mais alors, pourquoi -quelle que soit la méthode que j'utilise: stepping stone ou MODI- je n'arrive pas à établir un chemin pour toutes les variables hors base (cases vides). Je tombe toujours sur une impasse. hors si la solution était de base, tout les chemins s'établiront systématiquement. J'ai cru au début que je me trompais quelque part, mais toutes les personnes que j'ai consulté jusque là tombent sur la même impasse. Qu'en penses-tu Convexe???
A bientôt j'espère.
Le 16/03/2011 par convexe :
Tu as de la doc sur les méthodes dont tu parles ?
Le 16/03/2011 par norma :
Salut Convexe,
Apparemment la documentation concernant ces méthodes ne foisonne pas, ça fait une heure que je cherche sur le net en vain. je n'arrive pas à trouver un document assez explicite. Ceci dit, le powerpoint que je t'ai déjà envoyé traite implicitement de la méthode MODI (revois à partir de la page36).
Mais si tu veux Convexe, je pourrais saisir la documentation manuscrite ou imprimée que j'ai et te l'envoyer. mais pour faire plus court, commence par reconsulter le powerpoint puis fais-moi part des points qui persistent à être flous pour toi.
Enfin, encore mille MERCIS Convexe pour l'attention que tu m'accordes.
Le 16/03/2011 par norma :
J'ai oublié de le noter. la méthode du Stepping stone ne fait pas recours aux coûts marginaux ui et Vj, mais calcule la marge de coût concernant les cases restées vides à partir des coûts des autres cases pleines en constituant des boucles démarrant de la case vide dont on veut calculer la marge et revenant vers elle en prenant un chemin passant par les autres cases pleines, et en alternant les signes (+,-) de façon à garder l'équilibre des quantités (demandes/offres) dans les lignes et colonnes du tableau.
Regarde la page 37. on aurait mis pour la variable X31:
S31= C13 (-) C11 (+) C12 (-) C22 (+) C24 (-) C34= 5-3+1-6+2-4= (-5)
Encore MERCI. et à bientôt j'espère.
Le 13/05/2011 par norma :
Bonjour,
Comment peut-on proposer un programme linéaire pour un réseau PERT?
Quelles variables peut-on définir pour ce programme et comment se présenteront les contraintes surtout??? ça reste très flou pour moi.
Please, A L'aide !!!
