[PDF] SOLUTIONNAIRE : DUAL EXERCICES 1 Formulation du dual





Previous PDF Next PDF



Chapitre 4 Dualité

Dans cet exemple on observe que la valeur minimale du primal est égale à la dual à l'aide du tableau final du simplexe appliqué au problème primal.



IFT 2505 Programmation Linéaire

Exemple sur le simplexe dual et primal-dual. On consid`ere le probl`eme min x. 3x1 + 4x2 + 6x3 + 7x4 + x5 s.`a. 2x1 ? x2 + x3 + 6x4 ? 5x5 ? 6.



SOLUTIONNAIRE : DUAL EXERCICES 1 Formulation du dual

Il y a 3 contraintes dans le PPL donc 3 variables dans le modèle dual Excel dans son algorithme du simplexe utilise une construction du dual directe ...



Dualité en Programmation Linéaire Algorithmes primal et dual du

Algorithmes primal et dual du simplexe. Alain Faye. Option 3A Définition du dual d'un programme linéaire ... Exemple : écrire le dual de ce PL.



MÉTHODE DU SIMPLEXE DUAL (REVISITÉE) 1. Introduction La

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 



IFT 2505 Programmation Linéaire

Dualité : relations `a la procédure du simplexe. Résoudre le primal par le simplexe donne la solution duale. Supposons que le programme Exemple : dual.



Algorithme primal-dual

Simplexe primal-dual. L'idée est de travailler simultanément Algorithme primal-dual : exemple ... du simplexe avec la solution du dual `a l'optimalité.





Sujet 5: Dualité --- faible et forte

Mar 24 2010 Si le primal est non-borné



Programmation linéaire (dualité et analyse de sensibilité) Dualité

Dualité : exemple Wyndor Glass Voici le modèle pour Dual Glass appelé modèle dual : ... du simplexe : ce sont les coefficients dans la ligne.



[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] Exemple sur le simplexe dual et primal-dual

Exemple sur le simplexe dual et primal-dual On consid`ere le probl`eme min x 3x1 + 4x2 + 6x3 + 7x4 + x5 s `a 2x1 ? x2 + x3 + 6x4 ? 5x5 ? 6



[PDF] Chapitre 4 Dualité

Dans cet exemple on observe que la valeur minimale du primal est égale à la valeur maximale du dual Essayons de dualiser d'autres types de problèmes



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

Programmation linéaire et dualité – Définition du dual d'un programme linéaire – Théorème de dualité forte • Algorithmes primal et dual du simplexe



[PDF] OPTI1- Dualité en PL - Algorithme dual du simplexe - ENSIIE

2-Résoudre PL en appliquant l'algorithme dual du simplexe en partant de la base constituée par les 2 variables d'écart 3-Vérifier les calculs en faisant une 



[PDF] SOLUTIONNAIRE : DUAL EXERCICES 1 Formulation du dual

Il y a 3 contraintes dans le PPL donc 3 variables dans le modèle dual Excel dans son algorithme du simplexe utilise une construction du dual directe 



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

11 mar 2010 · “Le dual du dual c'est le primal ” Page 7 Dualité : introduction La formule Un exemple



[PDF] Sujet 5: Dualité --- faible et forte

L'utilisation du théor`eme dans la méthode du simplexe Rappel : un exemple maximisation et ¯y une solution réalisable de son dual



[PDF] Cours 8 Dualité

En effet à tout modèle de programmation linéaire primal correspond résolution comme l'algorithme du dual simplexe que nous traitons dans ce chapitre



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

La méthode du simplexe est un algorithme qui permet la recherche de la solution optimale Donc on présente la méthode à l'aide d'un exemple illustratif

  • Comment calculer la dualité ?

    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.

  • Comment faire le tableau de simplexe ?

    Le tableau initial de la méthode du Simplexe est composé par tous les coefficients des variables de décision du problème original et les variables d'écart, excès et artificielles ajutées dans la deuxième étape (dans les colonnes, étant P0 0 le terme indépendant et le reste de variables Pi sont les mêmes que Xi), et les

  • 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 (?).
  • 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

y

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

y

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

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). (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

y

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

y

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.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). (5) PROBLÈME - PPL : Maximiserz= 6x

1+ 5x2sujet aux contraintes

x

1+x2≥8

-2x

1+ 3x2≥6

x

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

3y

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

3

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+

6x

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

x

12+x22+x32≥75

x

13+x23+x33≥25

x

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-

6x

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

y

2-y4≥ -8

y

3-y4≥ -6

y

1-y5≥ -2

y

2-y5≥ -6

y

3-y5≥ -4

y

1-y6≥ -6

y

2-y6≥ -10

y

3-y6≥ -8

y

1-y7≥ -4

y

2-y7≥ -8

y

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 variablex

21ce qui donne la deuxième contrainte

du dual. Le même principe est appliqué pour toutes les variables du PPL pour donner chacune des contraintes du dual. (8) PROBLÈME : Une compagnie fabrique 3 modèles de jouets : voiture de police, camions dequotesdbs_dbs35.pdfusesText_40
[PDF] programme dual et primal

[PDF] dualité onde particule formule

[PDF] dualité synonyme

[PDF] dualité exemple

[PDF] dualité définition

[PDF] dualité adjectif

[PDF] dualité de l'homme définition

[PDF] dualité humaine

[PDF] dualité entre deux personnes

[PDF] dualité définition philosophique

[PDF] duane hanson oeuvre

[PDF] duane hanson biography

[PDF] duane hanson supermarket lady

[PDF] tourists ii

[PDF] duane hanson tourists