DualitePL AlgoSimplex TD

OPTI1- Dualité en PL - Algorithme dual du simplexe
Exercice 1. Dualité.
Un pays désire accroître son potentiel d’armement ; il veut acquérir au moins :
- 100 000 fusils

- 200 000 grenades
- 100 chars
- 400 mitrailleuses
- 400 bazookas
Il s’adresse pour ce faire à des marchands qui lui proposent 3 lots décrits ci-dessous :
Lot 1 Lot 2 Lot 3

fusils 500 300 800
grenades 1000 2000 1500
chars 10 20 15
mitrailleuses 100 80 150
bazookas 80 120 200
Coûts des lots 10 M$ 12 M$ 15 M$
Les lots sont fractionnables : on peut acheter une fraction de lot.
1-Le pays en question va essayer de minimiser le coût de l’armement supplémentaire qu’il va acheter.
Modéliser son problème par un programme linéaire P1.
2-Un fabricant qui produit ces différents types d’’armes à la demande veut s’emparer du marché. Pour
emporter le marché, le fabricant d’armement doit calculer ses prix de vente unitaires de façon à
concurrencer les marchands d’armes tout en maximisant son profit.
Modéliser son problème par un programme linéaire P2. Quelle est la nature de P2 relativement à P1 ?
Exercice 2. Ecarts complémentaires
On considère le programme linéaire (P) suivant :
min 𝑧 = 2𝑥1 + 3𝑥2
4𝑥1 + 𝑥2 ≥ 5 (1)
3𝑥1 + 2𝑥2 ≥ 6 (2)
Sous les contraintes {
𝑥1 + 2𝑥2 ≥ 3 (3)
𝑥1 , 𝑥2 ≥ 0
La solution optimale est x1=3/2, x2= ¾ et l’objectif z=21/4
1° Ecrire (D) le dual de (P).
2° A l’aide des écarts complémentaires, trouver la solution optimale de (D).
1
Exercice 3. Ecarts complémentaires.
Soit le programme linéaire PL défini par :
min 𝑧 = 2𝑥1 + 3𝑥2
2𝑥1 + 𝑥2 ≥ 3
2𝑥 − 𝑥2 ≥ 5
Sous contraintes { 1
𝑥1 + 4𝑥2 ≥ 6
𝑥1 0 , 𝑥2 ≥ 0
1-La solution définie par 𝑥
̃1 = 3 , 𝑥
̃2 = 1 est-elle réalisable ? optimale ?
26 7
2-La solution définie par 𝑥
̃1 = 9
,𝑥
̃2 = 9 est-elle réalisable ? optimale ?
Répondre à ces questions en utilisant le théorème des écarts complémentaires.
Exercice 4. Algorithme dual du simplexe.
Soit le programme linéaire PL défini par :
min 𝑧 = 2𝑥1 + 𝑥3
𝑥1 + 𝑥2 − 𝑥3 ≥ 5
Sous contraintes { 𝑥1 − 2𝑥2 + 4𝑥3 ≥ 8
𝑥1 ≥ 0 , 𝑥2 ≥ 0 , 𝑥3 ≥ 0
1-Mettre le problème sous forme standard en rajoutant 2 variables d’écarts.
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 résolution graphique du dual de PL.
Exercice 5. Algorithme dual du simplexe.
Soit le PL suivant :
min 𝑧 = 2𝑥1 + 3𝑥2
4𝑥1 + 𝑥2 ≥ 8
𝑥 + 4𝑥2 ≥ 8
s.c. { 1
7𝑥1 + 10𝑥2 ≥ 47
𝑥1 ≥ 0, 𝑥2 ≥ 0
Résoudre à l’aide de l’algorithme dual du simplexe.
2
Correction.
Exercice 2.
4𝑦1 + 3𝑦2 + 𝑦3 ≤ 2 (𝑎)
1° (D) est max 𝑤 = 5𝑦1 + 6𝑦2 + 3𝑦3 sous les contraintes {𝑦1 + 2𝑦2 + 2𝑦3 ≤ 3 (𝑏)
𝑦1 , 𝑦2 , 𝑦3 ≥ 0
2° Le théorème des écarts complémentaires peut se résumer ainsi :
- à une contrainte non saturée correspond une variable duale nulle

- à une variable duale non nulle correspond une contrainte saturée
On reporte la solution de (P) dans les contraintes de (P). La contrainte (1) n’est pas saturée. Donc y1=0.
Maintenant x1 et x2 sont non nuls. Comme ce sont les variables duales de (D) associées aux contraintes
(a) et (b), (a) et (b) sont saturées. Ce qui nous donne le système :
4𝑦1 + 3𝑦2 + 𝑦3 = 2 (𝑎)
{𝑦1 + 2𝑦2 + 2𝑦3 = 3 (𝑏)
𝑦1 = 0
Ce qui donne y2= ¼ , y3= 5/4
Vérifions que l’objectif z de (P) et l’objectif w de (D) coïncident. On reporte la solution trouvée dans w
et on trouve : w=21/4 .
Exercice 5.
On rajoute 3 variables d’écart x3, x4, x50 (une pour chaque contrainte) pour mettre le PL sous forme
standard (contraintes d’égalités). On part ensuite de la base évidente (variables d’écart en base) qui
est duale réalisable (coûts réduits0) mais pas primale réalisable car la solution de base
correspondante est x1=x2=0 et x3=-8, x4=-8,x5=-47 qui a des composantes <0. On a donc le tableau
suivant :
base X1 X2 X3 X4 X5
X3 -4 -1 1 0 0 =-8
X4 -1 -4 0 1 0 =-8
X5 -7 -10 0 0 1 =-47
2 3 0 0 0 =0 + z
On fait sortir de la base x5 qui est la coordonnée la plus négative (ligne jaune). Qui va rentrer ?
Max{2/-7 , 3/-10} = - Min{2/7 , 3/10}=- 2/7 . La variable qui rentre est celle qui a réalisé ce min c’est-à-
dire x1 (colonne jaune). Le pivot -7 est indiqué en gras sur le tableau. On pivote et on obtient le tableau
ci-dessous :
3
base X1 X2 X3 X4 X5
X3 0 33/7 1 0 -4/7 =132/7
X4 0 -18/7 0 1 -1/7 =-9/7
X1 1 10/7 0 0 -1/7 =47/7
0 1/7 0 0 2/7 =-247/7 + z
On vérifie que la solution de base correspondante est toujours duale réalisable (coûts réduits0).
La variable sortante est x4<0. La variable entrante est celle qui réalise max{(1/7)/(-18/7) , (2/7)/(-1/7)}=-
1/18 variable x2. Le pivot est -18/7 en gras. On pivote :
- On divise la ligne du pivot Lx4 (ligne jaune) par le pivot -18/7. On obtient la nouvelle ligne L’x4
- La nouvelle ligne de x3 est L’x3 = Lx3 -33/7 L’x4
- La nouvelle ligne de x1 est L’x1 = Lx1 -10/7 L’x4
- La nouvelle ligne de z est L’z = Lz -1/7 L’x4
On obtient le nouveau tableau :
base X1 X2 X3 X4 X5
X3 0 0 1 33/18 -35/(67) =33/2
X2 0 1 0 -7/18 1/18 =1/2
X1 1 0 0 10/18 -2/9 =6
0 0 0 1/18 5/18 =-27/2 + z
On arrive à la solution de base x1=6, x2=1/2, x3=33/2 x4=x5=0 primal réalisable donc optimale.
On vérifie z=26 + 31/2 = 13,5 = 27/2 .
La contrainte n°1 : 46 + ½ - 8 = 16 + ½ = 33/2 = x3.
La contrainte n°2 : 6 + 4½ - 8 = 0 = x4.
La contrainte n°3 : 76 + 10½ - 47 = 0 = x5.

DualitePL AlgoSimplex TD

Transféré par

Droits d'auteur :

Formats disponibles

DualitePL AlgoSimplex TD

Transféré par

Informations du document

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

DualitePL AlgoSimplex TD

Transféré par

Droits d'auteur :

Formats disponibles

OPTI1- Dualité en PL - Algorithme dual du simplexe

Un pays désire accroître son potentiel d’armement ; il veut acquérir au moins :

- 100 000 fusils

Lot 1 Lot 2 Lot 3

Les lots sont fractionnables : on peut acheter une fraction de lot.

Exercice 2. Ecarts complémentaires

On considère le programme linéaire (P) suivant :

min 𝑧 = 2𝑥1 + 3𝑥2

1° Ecrire (D) le dual de (P).

2° A l’aide des écarts complémentaires, trouver la solution optimale de (D).

Soit le programme linéaire PL défini par :

min 𝑧 = 2𝑥1 + 3𝑥2

Répondre à ces questions en utilisant le théorème des écarts complémentaires.

Exercice 4. Algorithme dual du simplexe.

Soit le programme linéaire PL défini par :

3-Vérifier les calculs en faisant une résolution graphique du dual de PL.

Exercice 5. Algorithme dual du simplexe.

min 𝑧 = 2𝑥1 + 3𝑥2

- à une contrainte non saturée correspond une variable duale nulle

On obtient le nouveau tableau :

On vérifie z=26 + 31/2 = 13,5 = 27/2 .

La contrainte n°1 : 46 + ½ - 8 = 16 + ½ = 33/2 = x3.

La contrainte n°2 : 6 + 4½ - 8 = 0 = x4.

La contrainte n°3 : 76 + 10½ - 47 = 0 = x5.

Vous aimerez peut-être aussi