TD3 Corr

LPSIL Année 2007-2008
TD MathOpt - Feuille 3 - Correction
Dualité
Correction de l’exercice 1
a) Le programme sous forme standard:

Maximiser 2x1 + 3x2 + 2x3 + 3x4
Sous les contraintes :
2x1 + x2 + 3x3 + 2x4 ≤ 8
3x1 + 2x2 + 2x3 + x4 ≤ 7
x1 , x2 , x3 , x4 ≥ 0
b) Le dual:
Minimiser 8y1 + 7y2

2y1 + 3y2 ≥ 2
y1 + 2y2 ≥ 3
3y1 + 2y2 ≥ 2
2y1 + y2 ≥ 3
y1 , y2 ≥ 0
c) Représentation graphique
1
La solution obtenue est donc : y1 = 1, y2 = 1.
d) 1ère itération du simplexe:

On introduit les variables d’écart x5 , x6 et on obtient le premier dictionnaire:
x5 = 8 − 2x1 − x2 − 3x3 − 2x4

x6 = 7 − 3x1 − 2x2 − 2x3 − x4
z = 2x1 + 3x2 + 2x3 + 3x4
La solution de base associée à ce dictionnaire est:x1 = x2 = x3 = x4 = 0, x5 = 8, x6 = 7 et z = 0.

On choisit x2 comme variable entrante, car son coefficient dans la fonction objectif est le plus élevé (on
pouvait aussi choisir x4 qui a le même coefficient).
On cherche la variable sortante et on écrit pour cela les contraintes de positivité sur les variables en base,
avec x1 = x3 = x4 = 0.
• La contrainte associée à x5 donne x2 ≤ 8.
• La contrainte associée à x6 donne x2 ≤ 72 .
C’est donc la variable x6 qui borne la croissance de x2 , c’est elle qui sort de la base. On obtient après pivot:
7 3 1 1
x2 = 2 − 2 x1 − x3 − 2 x4 − 2 x6
9 1 3 1
x5 = 2 − 2 x1 − 2x3 − 2 x4 + 2 x6
21 5 3 3
z = 2 − 2 x1 − x3 + 2 x4 − 2 x6
e) Les solutions primale et duale sont optimales.

En effet, les solutions trouvées sont réalisables (il suffit de voir que la solution primale vérifie toutes les
contraintes du problème primal et la solution duale toutes celles du problème dual). Elles donnent comme
valeur pour les fonctions objectif 15 (valeur de l’objectif du primal) et 15 (valeur de l’objectif du dual). Le
théorème vu en cours sur la dualité nous permet donc (puisque 15=15) d’affirmer que nos solutions sont
optimales.
(a) Le problème dual est:

Minimiser 4y1 + 2y2 + 5y3
2y1 − 4y2 + 3y3 ≥ 1
−y1 + 3y2 − 2y3 ≥ −3
y1 − y3 ≥ 3
y1 , y2 , y3 ≥ 0
On vérifie que la solution proposée est réalisable.
– 1ère contrainte 4 = 4
– 2e contrainte 0 < 2
2
– 3e contrainte −4 < 5
Les contraintes associées à y2 et y3 étant lâches (inégalités strictes), d’après le théorème des écarts
complémentaires, y2 = y3 = 0.
D’après ce même théorème, les contraintes du dual associées à une variable primale strictement posi-
tive sont vérifiées à l’égalité. On a donc, puisque x3 > 0:
y1 − y3 = 3
Donc la solution duale associée à la solution primale donnée est:

y1 = 3, y2 = 0 et y3 = 0.
Cette solution étant dual-réalisable, on en déduit que la solution proposée est optimale.
(b) Non, la solution proposée n’est pas optimale.

On vérifie tout d’abord qu’elle est réalisable :
– 1ère contrainte 4=4

– 2ème contrainte 3=3
14
– 3ème contrainte 3 <5
– 4ème contrainte 1=1
Le problème dual est:
Minimiser 4y1 + 3y2 + 5y3 + y4

y1 + 4y2 + 2y3 + 3y4 ≥ 7
3y1 + 2y2 + 4y3 + y4 ≥ 6
5y1 − 2y2 + 4y3 + 2y4 ≥ 5
−2y1 + y2 − 2y3 − y4 ≥ −2
2y1 + y2 + 5y3 − 2y4 ≥ 3
y1 , y2 , y3 , y4 ≥ 0
D’après le théorème 4.3, x∗ est optimale si et seulement si il existe y∗1 , y∗2 , y∗3 , y∗4 tels que :
3y∗1 + 2y∗2 + 4y∗3 + y∗4 = 6

5y∗1 − 2y∗2 + 4y∗3 + 2y∗4 = 5
−2y∗1 + y∗2 − 2y∗3 − y∗4 = −2
y∗3 = 0
et tels que y∗ soit dual réalisable.

La solution du système est y∗1 = y∗2 = y∗4 = 1 et y∗3 = 0. Mais cette solution n’est pas duale réalisable,
x∗ n’est donc pas optimale.
3
On définit tout d’abord les variables de décision suivantes :
• x1 est le nombre d’offres ’un téléphone + deux cartes prépayées’ préparées,
• x2 est le nombre d’offres ’un téléphone + un kit mains libres + 3 cartes prépayées’ préparées.
Puisque la première offre rapporte 7 euros et la deuxième 9 euros, le profit réalisé par le vendeur est :
7x1 + 9x2 , c’est la fonction objectif que l’on désire maximiser.
De plus, le vendeur ne peut pas vendre plus d’offres que ne le permet son stock.
x1 + x2 ≤ 8 les téléphones,
2 x1 + 3 x2 ≤ 19 les cartes,
x2 ≤ 4 les kits mains libres,
Les variables sont positives, ainsi le programme linéaire à résoudre est le suivant.
Maximiser 7 x1 + 9 x2
sous : x1 + x2 ≤ 8
2 x1 + 3 x2 ≤ 19
x2 ≤ 4
x1 , x2 ≥ 0
La solution optimale de ce programme est x1 = 5 et x2 = 3, et la valeur optimale est 62.

L’objectif de la grande surface est de minimiser le prix d’achat du stock, mais il doit quand même proposer
un prix intéressant pour le revendeur. On pose donc les variables suivantes :
• y1 est le prix d’achat d’un téléphone du stock,
• y2 est le prix d’achat d’une carte,
• y3 est le prix d’achat d’un kit mains libres,
Le prix d’achat du stock est donc : 8y1 + 19y2 + 4y3 . Pour que les prix proposés par la grande surface soient
intéressants pour le revendeur, il ne faut pas qu’il perde de l’argent par rapport aux offres qu’il aurait pu
écouler, c’est à dire :
y1 + 2 y3 ≥ 7
y1 + y2 + 3 y3 ≥ 9
Les prix sont évidemment positifs. Le programme que doit résoudre la grande surface pour décider des prix
qu’elle doit proposer correspond en fait au programme dual.

TD3 Corr

Transféré par

Droits d'auteur :

Formats disponibles

TD3 Corr

Transféré par

Informations du document

Titre original

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

TD3 Corr

Transféré par

Droits d'auteur :

Formats disponibles

LPSIL Année 2007-2008

TD MathOpt - Feuille 3 - Correction

a) Le programme sous forme standard:

Minimiser 8y1 + 7y2

d) 1ère itération du simplexe:

x5 = 8 − 2x1 − x2 − 3x3 − 2x4

La solution de base associée à ce dictionnaire est:x1 = x2 = x3 = x4 = 0, x5 = 8, x6 = 7 et z = 0.

• La contrainte associée à x5 donne x2 ≤ 8.

• La contrainte associée à x6 donne x2 ≤ 72 .

e) Les solutions primale et duale sont optimales.

(a) Le problème dual est:

On vérifie que la solution proposée est réalisable.

Donc la solution duale associée à la solution primale donnée est:

(b) Non, la solution proposée n’est pas optimale.

– 1ère contrainte 4=4

Le problème dual est:

Minimiser 4y1 + 3y2 + 5y3 + y4

3y∗1 + 2y∗2 + 4y∗3 + y∗4 = 6

et tels que y∗ soit dual réalisable.

On définit tout d’abord les variables de décision suivantes :

• x1 est le nombre d’offres ’un téléphone + deux cartes prépayées’ préparées,

La solution optimale de ce programme est x1 = 5 et x2 = 3, et la valeur optimale est 62.

• y1 est le prix d’achat d’un téléphone du stock,

• y2 est le prix d’achat d’une carte,

• y3 est le prix d’achat d’un kit mains libres,

Vous aimerez peut-être aussi