[PDF] [PDF] Dualité --- la formule pour définir le dual dun programme linéaire





Previous PDF Next PDF



[PDF] Chapitre 4 Dualité

le dual Le problème original est le primal Le problème dual s'écrit sous la forme : du dual Essayons de dualiser d'autres types de problèmes



[PDF] La dualité associe à tout problème linéaire un autre problème

— Le sens des contraintes réelles est inversé — Les variables duales doivent être positives ou nulles Page 14 Définition du problème dual



[PDF] SOLUTIONNAIRE : DUAL EXERCICES 1 Formulation du dual

(1) PROBLÈME–PPL : Maximiser z = x1 + 7x2 sujet aux contraintes DUAL : Le nombre de variables est déterminé par le nombre de contrainte du primal : il y



[PDF] Optimisation linéaire La dualité

Le problème dual • Soit g(p) le coût optimal du problème relaxé • Soit x* solution optimale du problème primal Dualité Michel Bierlaire



[PDF] Dualité en Programmation Linéaire Algorithmes primal et dual du

Confirmer votre réponse en résolvant (P) par l'algorithme du simplexe Que se passe-t-il si l'un des 2 problèmes (primal ou dual) est non borné ?



[PDF] 1 TD5 - Dualité Lagrangienne Résolution du problème dual par la

2° On relâche la contrainte et on lui affecte le multiplicateur de Lagrange ? 0 Enoncer (D) le problème dual lagrangien de (P) Calculer la fonction duale 



[PDF] Dualité lagrangienne

Le problème dual lagrangien associé au problème primal relativement aux contraintes du problème Max Inf est le supremum de la fonction = Dual



[PDF] 5Dualité en programmation linéaire

Théorème de dualité forte Si un des deux problèmes primal ou dual possède une solution optimale avec valeur finie alors la même chose est vraie pour l'autre 



[PDF] Dualité --- la formule pour définir le dual dun programme linéaire

11 mar 2010 · Il n'est possible de trouver une solution optimale et vérifier que c'est optimale sans la dualité Pour comprendre comment fonctionne les 



[PDF] méthode du simplexe dual (revisitée)

Cette méthode s'applique en ayant déjà déterminer une solution de base réalisable pour le problème dual C'est par exemple le cas si c ? 01 dans (2) La 



[PDF] Chapitre 4 Dualité

A chaque problème d'optimisation linéaire nous allons définir un nouveau problème appellé le dual Le problème original est le primal Soit le problème d' 



[PDF] SOLUTIONNAIRE : DUAL EXERCICES 1 Formulation du dual

(1) PROBLÈME–PPL : Maximiser z = x1 + 7x2 sujet aux contraintes x1 + x2 ? 8 ?2x1 + 3x2 ? 6 x1 ? x2 ? 2 où x1 ? 0 et x2 ? 0 DUAL : Le nombre de 



[PDF] Dualité en Programmation Linéaire Algorithmes primal et dual du

Si le primal admet une solution optimale alors le dual admet une solution optimale et les valeurs optimales des 2 problèmes coïncident Théorème de dualité



[PDF] Optimisation linéaire La dualité

C'est ce qui génère les contraintes du problème dual • A chaque contrainte du primal (autres que les contraintes de signe) est associée une variable duale



[PDF] méthode du simplexe dual (revisitée)

A chaque itération de la méthode du simplexe dual les variables primales entrante et sortante de (1) sont déterminées en examinant le problème dual (2)



[PDF] Cours 8 Dualité

La dualité qui existe entre le primal et le programme dual permet : a) en résolvant le problème primal d'obtenir également d'un tableau optimal la solution 



[PDF] Primal Dual a) Max Z = 2x

L'algorithme primal-dual permet de passer à chaque itération d'une solution réalisable pour le problème dual à une autre et d'une solution irréalisable 



[PDF] Dualité --- la formule pour définir le dual dun programme linéaire

11 mar 2010 · Sujet 4: Dualité — la formule pour définir le dual d'un programme linéaire MHT 423 : Mod`eles et méthodes d'optimisation Andrew J Miller



[PDF] FSJES-AC RECHERCHE OPERATIONNELLE Semestre 6 Filière

B - LE PROBLEME DUAL Le programme dual est un programme associé au premier ( primal ) Comment interpréter ce programme dual ?



[PDF] Programmation linéaire

On a les relations suivantes entre un problème P et son dual Q : P admet une solution optimale si et seulement si Q en admet une Si P est faisable alors Q est 

  • Comment trouver le dual ?

    Le dual est max z = bty, Aty ? c, y ? 0. min z = ctx, (At)tx ? b, x ? 0. ?? min z = ctx, Ax ? b, x ? 0. Donc, le dual du dual est le primal.

  • C'est quoi un programme dual ?

    Par définition, le programme dual est un programme linéaire consistant à minimiser une fonction économique dans un domaine défini par des contraintes sous forme d'inéquations de type inférieures ou égales (?).

  • Quelle est la relation entre les solutions optimales du primal et du son dual ?

    Le primal a une solution optimale est le dual a aussi une solution optimale. Le primal est non-borné est le dual est irréalisable. Le dual est irréalisable est le primal est non-borné. Tous les deux probl`emes sont irréalisables.
  • La dualité, c'est la théorie qui nous permet de trouver avec confiance une solution optimale d'un programme linéaire. Si on a une solution réalisable qui n'est pas optimale, la dualité nous donne la capacité de savoir pourquoi cela n'est pas optimale.11 mar. 2010

Dualite : introductionLa formule

Sujet 4: Dualite | la formule pour denir le dual d'un programme lineaire

MHT 423 :

Modeles et methodes d'optimisation

Andrew J. Miller

Derniere mise a jour: March 11, 2010

Dualite : introductionLa formule

Dans ce sujet...

1Introduction a la dualite

2La formule pour denir le probleme dual

Dualite : introductionLa formule

1Introduction a la dualite

2La formule pour denir le probleme dual

Dualite : introductionLa formule

Qu'est-ce que c'est?

La dualite, c'est la theorie qui nous permet de trouver avec

conanceune solution optimaled'un programme lineaire.Si on a une solution realisable qui n'est pas optimale, la dualite

nous donne la capacite de savoirpourquoicela n'est pas optimale.

Dualite : introductionLa formule

Motivations

Il n'est possible de trouver une solution optimale, et verier que c'est optimale, sans la dualite.Pour comprendre comment fonctionneles logiciels , il faut

comprendre les conceptes de la dualite.Pour une utlilisation (eventuelle) plus approndies des outils et

methodes d'optimisation, il faut comprendre ces conceptes.L'analyse de sensibilite: La dualit enous p ermetd'acceder a

beaucoup d'information sur des eets eventuels des changements des donnees d'un programme lineaire, sans que nous soyons obliges de le re-resoudre.

Dualite : introductionLa formule

Probleme primal et probleme dual

Chaque programme lineaire peut ^etre considere comme un p robleme primal .Il y a un autre programme lineaire associe avec le primal, uniquement deni par celui-la. Ce programme lineaire-ci est le p roblemedual Ces deux programmes sont toujourssymmetriques, dans les sens suivants (entre autres):Il y a unecontrainte du alep ourchaque va riablep rimale, et une variable duale p ourchaque contrainte p rimale .Lesco ecientsobject ivesdes va riablesp rimalesdeviennent les cot es droits des contraintes duales, et les cot esdr oits des contraintes primales deviennent les co ecientsobjectives des va riablesduales. \Le dual du dual, c'est le primal."

Dualite : introductionLa formule

Un exemple

Rappelons l'exemple de deux variables que nous avons vu dans la premiere partie: max 1:9x1+ 2:6x2 s.a. 2x1+x24000 x

1+ 2x25000

x 1;x20 Pour pratiquer: resoudre le dual par l'interpretation geometrique dans deux dimensions.

Dualite : introductionLa formule

Encore un exemple

Rappelons l'exemple dietetique :

min 2x1+x2+x3+ 5x4 s.ax2+ 0:1x410 x

1+ 2x3+ 9:9x470

200x1+ 100x32000

10x2+ 100x4600

x

1;x2;x3;x40

Dualite : introductionLa formule

Exemple 3

Rappelons le probleme Monet :

max 6x1+ 2x2+ 4x3+ 3x4 s.a. 2x1+x2+ 3x3+ 2x44000

4x1+ 2x2+x3+ 2x46000

6x1+ 2x2+x3+ 2x410000

x

11000;x22000;x3500;x41000

x

1;x2;x3;x40

Dualite : introductionLa formule

Exemple 4

Planication multi-periode :

min 6X t=1C txt+5X t=1Hs t s. ax1+S0=D1+s1 x t+st1=Dt+st;t= 2;:::;5 x

6+s5=D6+S6

s tK;t= 1;:::;5 x t0;t= 1;:::;6;st0;t= 1;:::;5

Dualite : introductionLa formule

Exemple 4 (suite)

Le dual :

min (D1S0) +5X t=2D tyt+ (D6+s6)y65X t=1Kw t s. aytCt;t= 1;:::;6 y t+1ytwtH;t= 1;:::;5 y tlibre;t= 1;:::;6;wt0;t= 1;:::;5

Dualite : introductionLa formule

1Introduction a la dualite

2La formule pour denir le probleme dual

Dualite : introductionLa formule

Formulation generale

Rapellons la formulation generale d'un programme lineaire :

Soientc2IRn,b2IRm,A2IRmn.max

nX j=1c jxj s.a. nX j=1a ijxjbi;i= 1;:::;m x j0;j= 1;:::;nmax x2IRncTx s.a.Axb x0Notez qu'on suppose que toutes les inegalites non-triviales ont le sens de.

Dualite : introductionLa formule

Formulation generale (suite)

Forme standard :

Pour les problemes demaximisation, un programme lineaire est mis enforme standardsi toutes les inegalites non-triviales ont le sens. Pour les problemes deminimisation, un programme lineaire est mis enforme standardsi toutes les inegalites non-triviales ont le sens.Dans chaque contrainte, il faut que la partiec onstante,et seulement la partie constante , se trouve au c^ otedroit Ceci est tres important, car la formule pour denir le dual suppose que le primal soit mis en forme standard.

Dualite : introductionLa formule

Formule

variables et contraintes:

variable primale non-negative()inegalite dualevariable primale libre()equation dualecotes droits et objectives :

coecient de fonction objective de la variable primale cote droite de la contrainte dualecolonnes et lignes : coecients de la variable primale dans la matriceA coecients de la contrainte duale dans la transpose deA

Dualite : introductionLa formule

Formulation general d'un programme lineaire et son dual

Primal :

max nX j=1c jxj s.a. nX j=1a ijxjbi;i= 1;:::;m x j0;j= 1;:::;nDual: min nX j=1b iyi s.a. nX i=ma ijyicj;j= 1;:::;n y i0;i= 1;:::;m

Dualite : introductionLa formule

Formulation general d'un PL et son dual (forme matricielle)

Primal :

max x2IRncTx s.a.Axb x0Dual: minbTy s.a.ATyc y0

Dualite : introductionLa formule

Pour pratiquer

Vous pouvez trouver les duals de chaque exemple qu'on a vu dans les transparents jusqu'ici.

Dualite : introductionLa formule

A souvenir

Comment denirle probleme dual du probleme primal

quotesdbs_dbs44.pdfusesText_44
[PDF] photo citoyenneté canadienne

[PDF] photo visa canada 2017

[PDF] photo visa touriste canada

[PDF] tracer la hauteur d'un triangle cm2

[PDF] hauteur triangle obtusangle

[PDF] comment tracer une hauteur d'un triangle

[PDF] tracer les hauteurs d'un triangle exercices

[PDF] comment tracer la hauteur d'un triangle isocele

[PDF] dimensionnement pompe de relevage eaux usées

[PDF] calcul hmt pompe immergée

[PDF] calcul hmt pompe immergée forage

[PDF] calcul puissance pompe

[PDF] hauteur manométrique pompe centrifuge

[PDF] dimensionnement d'une pompe immergée

[PDF] dimensionnement d'une station de pompage pdf