Scribd
Importer
170 vues4 pages

Résolution de programmes linéaires et dualité

Le document présente une série d'exercices sur la dualité en programmation linéaire, incluant la formulation de programmes linéaires, la résolution par la méthode du simplexe, et la détermination de solutions optimales. Chaque exercice aborde des aspects différents tels que la résolution graphique, l'écriture de programmes duals, et l'application du théorème des écarts complémentaires. Les exercices impliquent des calculs et des tableaux pour illustrer les méthodes de résolution.

Transféré par

salimamri9999
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
170 vues4 pages

Résolution de programmes linéaires et dualité

Le document présente une série d'exercices sur la dualité en programmation linéaire, incluant la formulation de programmes linéaires, la résolution par la méthode du simplexe, et la détermination de solutions optimales. Chaque exercice aborde des aspects différents tels que la résolution graphique, l'écriture de programmes duals, et l'application du théorème des écarts complémentaires. Les exercices impliquent des calculs et des tableaux pour illustrer les méthodes de résolution.

Transféré par

salimamri9999
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

TD dualité

Exercice 1
On considère le programme linéaire suivant :

Max Z  9 x1  4 x2  4 x3
3x1  2 x2  x3  10

S / C 3x1  x2  2 x3  16
x , x , x  0
 1 2 3

1) Résoudre ce programme linéaire par la méthode de simplexe. (2,5 points)


2) Écrire le dual de ce programme linéaire. (1 point)
3) Déduire le dernier tableau de Dual à partir de celui du primal. (1,5 points)

Exercice 2

Soit le programme linéaire (PL) suivant :


Max Z  9 x1  4 x2  4 x3
3x1  2 x2  x3  10

S / C 3 x1  x2  2 x3  16
x , x , x  0
 1 2 3
1. Écrire le Dual de ce programme linéaire. (1 point)
2. Résoudre graphiquement le programme dual. (3 points)
3. Donner la solution du primal et son dernier tableau du simplexe déduite de celle du
dual.
(3 points)
Exercice 3

On considère PL suivant :

Max Z  10 x1  4 x2  6 x3
 x1  5 x2  2 x3  30

S / C  x1  5 x2  6 x3  40
x , x , x  0
 1 2 3
On vous donne le tableau courant incomplet de ce PL.

x1 x2 x3 a1 e2
x1 1 5 2 1 0 30
e2 0 -10 -8 -1 1 10
1. Compléter le tableau courant de ce programme linéaire et déterminez la solution
optimale.

2. Ecrire le programme dual, déduire la solution optimale et son dernier tableau du


simplexe.

Exercice 4
Soit le programme linéaire suivant :

Min C  8 X 1  2 X 2  X 3  3 X 4
4 X 1  X 2  X 3 3

S .C. X 1  X 2  X 3  X 4  5
 X  0, i  1, 2, 3, 4
 i

1. Écrire le programme linéaire dual de ce programme linéaire. (1 point)

2. Résoudre graphiquement le programme linéaire dual. (3 points)

3. En utilisant le théorème des écarts complémentaires, donner la solution optimale du


programme primal. (2.5 points)

4. Donnez le tableau optimal du primal. (2,5 points)

Exercice 5
Soit le programme linéaire suivant :

Max Z  5 X 1  X 2  6 X 3  2 X 4
 4 X 1  4 X 2  4 X 3  X 4  44

S .C. 8 X 1  6 X 2  4 X 3  3 X 4  60
 X  0, i  1, 2, 3, 4
 i  

1. Écrire le programme linéaire dual de ce programme linéaire. (1 point)

2. Résoudre graphiquement le programme linéaire dual. (2 points)


3. En utilisant le théorème des écarts complémentaires, donner la solution optimale du
programme primal. (2 points)

4. Donnez le tableau optimal du primal. (2 points)

Exercice 6
Soit le programme linéaire (PL) suivant :

Min C  2 X 1  X 2  X 3
 X 1  X 2  X 3  2

S .C.  X 1  X 2  2 X 3  1
 X  0, i  1, 2,3
 i  

4. Résoudre par la méthode du simplexe (3 points)

5. Donnez le tableau optimal du programme linéaire dual (2 points)

Exercice 7
Le 1er tableau incomplet d’un programme linéaire est représenté ci-dessous :

1 1 0 0 -M -M
VB
𝑥 𝑥 𝑠 𝑠 𝑎 𝑎 Q
𝑎 1 2 -1 2
𝑎 -5 15 0 5
𝑠 3 6 0 12
zj
zj

1. Complétez le tableau du simplexe et déduire le programme linéaire

2. Résoudre graphiquement ce PL

3. Ecrivez le programme linéaire dual

Exercice 8
Soit le programme linéaire suivant :

Min C  X 1  4 X 2  X 3
 X 1  X 2  2 X 3  16

S .C. 2 X 1  X 2  4 X 3  8
 X  0, i  1, 2,3
 i  
1. Ecrivez le premier tableau du simplexe de ce programme linéaire. (1 points)

2. Donnez le tableau du simplexe pour la base {X2, S2} en ayant recours à la méthode
matricielle. (2 points)

3. Retrouvez le tableau optimal du simplexe (2 points)

4. Donnez le programme linéaire dual (1 points)

5. Déduisez la solution optimale duale à partir du tableau optimal primal (1 point)

6. Déduisez le tableau optimal dual à partir du tableau optimal primal (2 points)

Vous aimerez peut-être aussi