[PDF] SOLUTIONNAIRE : DUAL EXERCICES 1 Formulation du dual 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}

SOLUTIONNAIRE : DUAL

EXERCICES

1 Formulation du dual

(1) PROBLÈME-PPL : Maximiserz=x1+ 7x2sujet aux contraintes x -2x x oùx

1≥0etx2≥0.

DUAL : Le nombre de variables est déterminé par le nombre de contrainte du primal : il y a donc 3 variables dans le modèledual.Le nombre de contraintes dans le dual est égal au nombre de variables dans le primal : il y a deux contraintes. DUAL : Minimiser w= 8y

1+ 6y2+ 2y3

sujet aux contraintes y

1-2y2+y3≥1

1+ 3y2-y3≥7

avecy i≥0pouri= 1,2,3. -La premième contrainte est déterminée par les coefficient de la première variable (x

1) dans

chacune des contraintes du primal (du PPL original) sous forme standard.x

1a comme

coefficient 1 pour la première contrainte (y

1), -2 pour la deuxième contrainte (y2) et 1 pour

la troisième contrainte (y 3). -La deuxième contrainte est déterminée par les coefficient de la deuxième variable (x 2) dans chacune des contraintes du primal (du PPL original) sous forme standard.x 2a comme coefficient 1 pour la première contrainte (y

1), 3 pour la deuxième contrainte (y2)

et -1 pour la troisième contrainte (y 3). (2) PROBLÈME-PPL : Maximiserx

1-3x2=zsujet aux contraintes

x -2x

1+ 3x2≥6

x oùx

1≥0etx2≥0.

DUAL : Le modèle n'est pas sous forme canonique : il est plus simple de considérer la forme canonique pour construire le dual. FORME CANONIQUE DU PPL : Maximiserx1-3x2=zsujet aux contraintes x 2x x oùx

1≥0etx2≥0.

-Il y a 3 contraintes dans le PPL donc il y a 3 variables dans ledual -Il y a 2 variables de décision dans le PPL donc il y a deux contraintes dans le dual.

DUAL : Minimiser

w= 8y

1-6y2+ 2y3

sujet aux contraintes y

1+ 2y2+y3≥1

1-3y2-y3≥ -3

avecy

1≥0,y2≥0ety3≥0.

-La premième contrainte est déterminée par les coefficient de la première variable (x

1) dans

chacune des contraintes du primal (du PPL original) sous forme standard.x

1a comme

coefficient 1 pour la première contrainte (y

1), 2 pour la deuxième contrainte (y2) et 1 pour

1), -3 pour la deuxième contrainte (y2)

et -1 pour la troisième contrainte (y 3). (3) PROBLÈME-PPL : Maximiserz= 6x

1+ 5x2sujet aux contraintes

x -2x x avecx i≥0 Le problème est déjà sous forme canonique. -Il y a 3 contraintes dans le PPL donc 3 variables dans le modèledual -Il y a deux variables de décision dans le PPL donc deux contraintes dans le dual.

DUAL : Minimiser

w= 8y

1+ 6y2+ 2y3

sujet aux contraintes y

1-2y2+y3≥6

1+ 3y2-y3≥5

avecy

1≥0,y2≥0ety3≥0.

-La premième contrainte est déterminée par les coefficient de la première variable (x

1) dans

chacune des contraintes du primal (du PPL original) sous forme standard.x

1a comme

coefficient 1 pour la première contrainte (y

1), -2 pour la deuxième contrainte (y2) et 1 pour

la troisième contrainte (y 3). -La deuxième contrainte est déterminée par les coefficient de la deuxième variable (x 2) dans chacune des contraintes du primal (du PPL original) sous forme standard.x2a comme coefficient 1 pour la première contrainte (y

1), 3 pour la deuxième contrainte (y2)

et -1 pour la troisième contrainte (y 3). (4) PROBLÈME-PPL : Maximiserz= 5x

1+ 5x2sujet aux contraintes

x -2x

1+ 3x2≥6

x oùx

1≥0etx2≥0.

Le modèleprimalsous sa forme canonique est donné par :

Maximiserz= 5x

1+ 5x2sujet aux contraintes

x 2x x oùx

1≥0etx2≥0.

-Il y a 3 variables dans le modèledual(nombre de contraintes dans le PPL) -Il y a deux contraintes dans le modèle dual (nombre de variables dans le PPL).

DUAL : Minimiser

w= 8y

1-6y2+ 2y3

sujet aux contraintes y

1+ 2y2+y3≥5

1-3y2-y3≥5

avecy

1≥0,y2≥0ety3≥0.

-La premième contrainte est déterminée par les coefficient de la première variable (x

1) dans

chacune des contraintes du primal (du PPL original) sous forme standard.x

1a comme

coefficient 1 pour la première contrainte (y

1), 2 pour la deuxième contrainte (y2) et 1 pour

1), -3 pour la deuxième contrainte (y2)

et -1 pour la troisième contrainte (y 3). (5) PROBLÈME - PPL : Maximiserz= 6x

1+ 5x2sujet aux contraintes

1+x2≥8

-2x

1+ 3x2≥6

1-x2≥2

oùx

1≥0etx2≥0.

DUAL : La forme canonique du modèleprimalest de maximiserz= 6x

1+ 5x2sujet aux

contraintes -x 2x -x oùx1≥0etx2≥0. -Il y a trois variables dans le modèledual -Il y a deux contraintes dans le modèle dual.

DUAL : Minimiser

w=-8y

1-6y2-2y3

sujet aux contraintes -y

1+ 2y2-y3≥6

-y

1-3y2+y3≥5

avecy i≥0, pouri= 1,2,3... -La premième contrainte est déterminée par les coefficient de la première variable (x

1) dans

chacune des contraintes du primal (du PPL original) sous forme standard.x

1a comme

coefficient -1 pour la première contrainte (y

1), 2 pour la deuxième contrainte (y2) et -1

pour la troisième contrainte (y 3). -La deuxième contrainte est déterminée par les coefficient de la deuxième variable (x 2) dans chacune des contraintes du primal (du PPL original) sous forme standard.x 2a comme coefficient -1 pour la première contrainte (y

1), -3 pour la deuxième contrainte (y2)

et 1 pour la troisième contrainte (y 3). (6) PROBLÈME : Une compagnie fabrique deux types d'acier : Acier trempé (T) et l'acier détrempé (D). Le profit pour une tonne d'acier est de 6k$ et 4k$ pour l'acier T et D respectivement. Il faut 2 et 3 tonnes de matières premières pour les aciers T et D respectivement tandis que le temps de production est respectivement de 6 et 4 unités. La compagnie dispose de 120 tonnes de matières premières et de 100 unités de temps. PPL : Le problème de programmation linéaire sous forme canonique est de maximiser z= 6x

1+ 4x2

sujet aux contraintes 2x 6x etx i≥0pouri= 1,2. -Ledualcomprend 2 variables -Le dual comprend 2 contraintes

DUAL : Minimiser

w= 120y

1+ 100y2

sujet aux contraintes 2y

1+ 6y2≥6

1+ 4y2≥4

avecy

1≥0ety2≥0.

(7) PROBLÈME : Un constructeur automobile doit livrer son modèle AA à 4 concessionnaires à partir de trois usines de production. Les disponibilités aux usines sont respectivement de

80, 40 et 100 unités tandis que les démandes des vendeurs sont de 40, 75, 25 et 60 pour les

concessionnaires I, II, III et IV respectivement. Les coûts de livraison des automobiles, en centaine de $, sont donnés par le tableau suivant :

Concessionnaire

I II III IV

14 2 6 4

Usines2

8 6 10 8

6 4 8 6

On cherche à établir le plan de livraison optimal.

VARIABLES DE DÉCISION : Considéronsx

ijles variables de décision qui donnent le nombre de véhicules livrés de l'usine i vers le concessionnairej. On cherche à minimiser le coût de la livraison. Le PPL donne comme fonction objectif à minimiser : 4x

11+ 8x21+ 6x31+ 2x12+ 6x22+ 4x32+

13+ 10x23+ 8x33+ 4x14+ 8x24+ 6x34

Les contraintes sont des contraintes de production et des contraintes de demande : x x x x

11+x21+x31≥40

12+x22+x32≥75

13+x23+x33≥25

14+x24+x34≥60

avec les contraintes de non négativitéx ij≥0. Le modèle sous sa forme canonique est de maximiser z=-4x

11-8x21-6x31-2x12-6x22-4x32-

13-10x23-8x33-4x14-8x24-6x34

sujet à x x x -x -x -x -x -Puisqu'il y a 7 contraintes pour le PPL dans sa forme canonique, le dual a 7 variables -Puisqu'il y a 12 variables dans le PPL sous sa forme canonique il y a 12 contraintes dansle dual.

DUAL : Minimiser

w= 80y

1+ 40y2+ 100y3-40y4-75y5-25y6-60y7

sujet aux contraintes y

1-y4≥ -4

2-y4≥ -8

3-y4≥ -6

1-y5≥ -2

2-y5≥ -6

3-y5≥ -4

1-y6≥ -6

2-y6≥ -10

3-y6≥ -8

1-y7≥ -4

2-y7≥ -8

3-y7≥ -6

avecy i≥0pouri= 1,...,7. -Pour la première contrainte du dual on s'intéresse aux coefficients de la variablex

11dans

chaque contrainte du PPL.x

11se retrouve avec un coefficient 1 dans la première contrainte

et -1 dans la quatrièmre contrainte du PPL sous forme canonique. -On procède de la même façon pour la variablexquotesdbs_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

[PDF] [PDF] SOLUTIONNAIRE : DUAL EXERCICES 1 Formulation du dual

Comment trouver le dual ?

C'est quoi un programme dual ?

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

SOLUTIONNAIRE : DUAL

EXERCICES

1 Formulation du dual

1≥0etx2≥0.

1+ 6y2+ 2y3

1-2y2+y3≥1

1+ 3y2-y3≥7

1) dans

1a comme

1), -2 pour la deuxième contrainte (y2) et 1 pour

1), 3 pour la deuxième contrainte (y2)

1-3x2=zsujet aux contraintes

1+ 3x2≥6

1≥0etx2≥0.

1≥0etx2≥0.

DUAL : Minimiser

1-6y2+ 2y3

1+ 2y2+y3≥1

1-3y2-y3≥ -3

1≥0,y2≥0ety3≥0.

1) dans

1a comme

1), 2 pour la deuxième contrainte (y2) et 1 pour

1), -3 pour la deuxième contrainte (y2)

1+ 5x2sujet aux contraintes

DUAL : Minimiser

1+ 6y2+ 2y3

1-2y2+y3≥6

1+ 3y2-y3≥5

1≥0,y2≥0ety3≥0.

1) dans

1a comme

1), -2 pour la deuxième contrainte (y2) et 1 pour

1), 3 pour la deuxième contrainte (y2)

1+ 5x2sujet aux contraintes

1+ 3x2≥6

1≥0etx2≥0.

Maximiserz= 5x

1+ 5x2sujet aux contraintes

1≥0etx2≥0.

DUAL : Minimiser

1-6y2+ 2y3

1+ 2y2+y3≥5

1-3y2-y3≥5

1≥0,y2≥0ety3≥0.

1) dans

1a comme

1), 2 pour la deuxième contrainte (y2) et 1 pour

1), -3 pour la deuxième contrainte (y2)

1+ 5x2sujet aux contraintes

1+x2≥8

1+ 3x2≥6

1-x2≥2

1≥0etx2≥0.

1+ 5x2sujet aux

DUAL : Minimiser

1-6y2-2y3

1+ 2y2-y3≥6

1-3y2+y3≥5

1) dans

1a comme

1), 2 pour la deuxième contrainte (y2) et -1

1), -3 pour la deuxième contrainte (y2)

1+ 4x2

DUAL : Minimiser

1+ 100y2

1+ 6y2≥6

1+ 4y2≥4

1≥0ety2≥0.

80, 40 et 100 unités tandis que les démandes des vendeurs sont de 40, 75, 25 et 60 pour les

Concessionnaire

I II III IV

14 2 6 4

Usines2

8 6 10 8

6 4 8 6