Exercices

1 Programmes linéaires

Modélisation et géométrie
Exercice 1. Votre régime alimentaire exige que tous les aliments que vous mangez proviennent
de l’un des quatre “groupes d’aliments de base” (gâteau au chocolat, crème glacée, soda et chee-
secake). À l’heure actuelle, les quatre aliments suivants sont disponibles pour la consommation :
brownies, glace au chocolat, cola et cheesecake à l’ananas. Chaque brownie coûte 1e, chaque
boule de glace au chocolat coûte 40 centimes, chaque bouteille de cola coûte 60 centimes, et
chaque morceau de cheesecake aux ananas coûte 1,60e. Tous les jours, vous devez consommer
au moins 500 calories, 120 g de chocolat, 200 g de sucre et 160 g de matières grasses. Le contenu
nutritionnel par unité de chaque aliment est indiqué dans le tableau ci-dessous. Formuler un
modèle de programmation linéaire qui peut être utilisé pour satisfaire vos besoins nutritionnels
quotidiens à un coût minimal.

Calories Chocolat (g) Sucre (g) Graisses (g)

Brownie 400 60 40 40
Glace au chocolat (boule) 20 40 40 80
Cola (bouteille) 150 0 80 20
Cheesecake ananas (morceau) 500 0 80 100

Exercice 2. Vous avez décidé ouvrir une fabrique de bonbons. Vous envisagez de produire deux
types de bonbons : Slugger et Cool Breeze, les deux composés uniquement de sucre, de noix et
de chocolat. À l’heure actuelle, vous avez en stock 100 kg de sucre, 20 kg de noix, et 30 kg
de chocolat. Le mélange utilisé pour faire Cool Breeze doit contenir au moins 20% de noix. Le
mélange utilisé pour préparer Slugger doit contenir au moins 10% de noix et 10% de chocolat.
Chaque kilo de Cool Breeze peut être vendu pour 25e, et chaque kilo de Slugger pour 20e.
Formuler un PL qui vous permettra de maximiser vos revenus de vente. Rédigez-le en forme
standard ou canonique.

Exercice 3. La compagnie Chandler Oil possède 5.000 barils de pétrole de type 1 et 10.000
barils de pétrole type 2. La société vend deux produits : l’essence et le fioul. Les deux produits
sont fabriqués en combinant le pétrole 1 et le pétrole 2. Les niveaux de qualité des pétroles 1 et
2 sont respectivement 10 et 5. L’essence doit avoir un niveau de qualité moyen d’au moins 8 et
le mazout au moins 6. La demande pour chaque produit doit être créée par publicité. Chaque
dollar dépensé en publicité pour l’essence crée une demande de 5 barils, et chaque dollar dépensé
pour le fioul de chauffage crée une demande de 10 barils. L’essence est vendue pour 25$ le baril,
le mazout pour 20$. Formuler un PL pour aider Chandler Oil à maximiser ses profits. On admet
qu’aucun pétrole de l’un ou l’autre type ne peut être acheté.

1
Exercice 4. Vers 435 av. J.-C., Sparte décida de constituer des troupes de réserve pour compléter
son armée régulière. De nouveaux guerriers pourraient être enrôlés pour 1, 2, 3 ou 4 ans. Soit
x1t , x2t , x3t et x4t le nombre de soldats enrôlés l’année t pour respectivement 1, 2, 3 et 4 ans,
et soit les coûts unitaires associés c1t , c2t , c3t et c4t . Chaque année t, la force minimale de la
réserve totale en soldats était fixée à Rt ; Rt a varié d’année en année.
En tant que général spartiate, vous devez trouver une politique d’enrôlement optimale pour les
10 années suivantes en résolvant le problème en tant que modèle de programmation linéaire.
Pour simplifier, on pose t = 1 pour l’année 435 av. J.-C.

Exercice 5. Quand est-ce qu’un demi-espace contient un autre ? Sous quelles conditions

{x ∈ Rn : aT x ≤ b} ⊆ {x ∈ Rn : (a0 )T x ≤ b0 }

(on suppose que a 6= 0 et a0 6= 0). Sous quelles conditions les 2 demi-espaces coincident ?
Calculez la distance entre les 2 hyperplans parallèles {x ∈ Rn : aT x = b1 } et {x ∈ Rn :
T
a x = b2 }.

Exercice 6. Dans les problèmes suivantes dessinez l’ensemble réalisable, les lignes de niveau de
la fonction-objective, en indiquant la direction de la valeur objective croissante et la solution
optimale.  
 x1 + x2 ≥ 1 
(a) min c1 x1 + c2 x2 + c3 x3 : x1 + 2x2 ≤ 3
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
 

pour les valeurs d’objectif c = [−1; 0; 1], c = [0; 1; 0], c = [0; 0; −1].
 
 3x1 + 2x2 ≥ 36 
(b) min z = 3x1 + 4x2 : 3x1 + 5x2 ≥ 45
x1 ≥ 0, x2 ≥ 0
 

Exercice 7.Meuble&Co fabrique des bureaux et des fauteuils. Le profit de vente d’un bureau est
40e, et d’un fauteuil – 25e. Chaque bureau utilise 4 unités de bois, et chaque fauteuil en utilise
3. Seulement 20 unités de bois sont disponibles. Les contraintes de commercialisation exigent
que le nombre de fauteuils soit au moins deux fois supérieur au nombre de bureaux produits.
La demande de fauteuils est limitée à 6. En outre, en raison de ses engagements précédents,
Meuble&Co doit fabriquer au moins 2 fauteuils.
Formulez le problème de maximisation du profit de Meuble&Co comme PL par rapport aux
variables x1 et x2 , les quantités de tables et de fauteuils réalisés.
1. Indiquez la région réalisable du PL de Meuble&Co en montrant les lignes définies par
chaque inégalité (y compris les contraintes de signe).
2. Dénombrez tous les points extrêmes et calculer leur valeur objective.
3. Dessinez la ligne d’iso-profit qui passe par la solution optimale et indiquez la direction
de la valeur objective croissante.

2
 4. Identifiez la solution optimale et calculer les valeurs des variables à la solution optimale.
5. Indiquer toutes les contraintes “actives” à la solution optimale.
6. Supposons que la contribution d’un fauteuil augmente de 25 à 30e, trouver deux solutions
optimales – points extrêmes – pour la nouvelle fonction objective.
7. Convertir le problème de depart en forme standard.

Exercice 8. Pour chaque PL suivant exprimer la solution optimale en fonction des données du
problème (paramètres c, n, d, etc). Si la solution optimale n’est pas unique, il suffit de donner
une solution optimale.
1. minx∈Rn {cT x : 0 ≤ x ≤ 1}
2. minx∈Rn {cT x : −1 ≤ x ≤ 1}
3. minx∈Rn {cT x : −1 ≤ 1T x ≤ 1}
4. minx∈Rn {cT x : 1T x = 1, x ≥ 0}
5. minx∈Rn {cT x : 0 ≤ x1 ≤ x2 ≤ ... ≤ xn ≤ 1}
6. minu,v∈Rn {1T u + 1T v : u − v = c, u ≥ 0, v ≥ 0}
7. minu,v∈Rn {dT1 u + dT2 v : u − v = c, u ≥ 0, v ≥ 0} pour d1 > d2

Algorithme du simplexe
Exercice 9. Résoudre les programmes linéaires suivants par algorithme du simplexe
 

 −x1 + x2 ≤ 11,  
x1 + x2 ≤ 27
 
(1) max 4x1 + 6x2 :
x1 ,x2  2x1 + 5x2 ≤ 90  
x1 ≥ 0, x2 ≥ 0
 
 
 x1 + 3x3 ≤ 6, 
(2) max 4x1 + x2 − x3 : 3x1 + x2 + 3x3 ≤ 9
x1 ,x2 ,x3 
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0


Exercice 10. Les tableaux suivants ont été obtenus en cours de résolution des programmes
linéaires avec deux variables non négatives x1 et x2 et deux contraintes d’inégalité (la fonction
objective z est maximisée). Les variables d’écart (slack) s1 et s2 ont été ajoutées. Dans chaque
cas, indiquez si le programme linéaire
(i) n’est pas borné
(ii) a une solution optimale unique
(iii) a une solution optimale cyclique
(iv) est dégénéré (dans ce cas, indiquer si l’un des éléments ci-dessus est valable).
Dans chaque cas précisez la base et la valeur courante du problème.
z x1 x2 s1 s2 RHS
1 0 3 2 0 20
(a)
0 1 −2 −1 0 4
0 0 −1 0 1 2

3
 z x1 x2 s1 s2 RHS
1 0 −1 0 2 20
(b)
0 0 0 1 −2 5
0 1 −2 0 3 6

z x1 x2 s1 s2 RHS
1 2 0 0 1 8
(c)
0 3 1 0 −2 4
0 −2 0 1 1 0

z x1 x2 s1 s2 RHS
1 0 0 2 0 5
(d)
0 0 −1 1 1 4
0 1 1 −1 0 4

Exercice 11. Soit le programme linéaire

 
 x1 + x2 + x3 ≤ 6, 
max 5x1 + 3x2 + x3 : 5x1 + 3x2 + 6x3 ≤ 15
x1 ,x2 ,x3 
x1 ≥ 0, x2 ≥ 0, x2 ≥ 0


et le tableau associé
z x 1 x2 x3 s 1 s2 RHS
1 0 0 5 0 1 15
0 0 2/5 −1/5 1 −1/5 3
0 1 3/5 6/5 0 1/5 3
(a) Quelle solution basique ce tableau représente-t-il ? Cette solution est-elle opti-
male ? Justifiez votre réponse.
(b) Ce tableau représente-t-il un optimum unique ? Sinon, trouvez une solution op-
timale alternative.

Exercice 12. En utilisant l’algorithme du simplex et x1 , x4 comme base de départ,

résolvez le LP suivant :
 
 2x2 − 2x3 + 4x4 = 5 
max 5x1 − x2 − x3 + x4 : 2x1 + 3x2 − x3 = 2;
x1 ,...x4 
x1 , x 2 , x 3 , x 4 ≥ 0


Si vous avez trouvé une solution optimale, précisez les valeurs des variables de
décision et de l’objectif. Sinon, expliquez l’étape à laquelle l’algorithme du simplex
a échoué, et la conclusion pour le type de problème.

Exercice 13. Une usine peut fabriquer cinq produits P1 , P2 , P3 , P4 et P5 . L’usine possède
deux zones de travail : la zone A1 d’atelier et la zone A2 d’assemblage. Le temps requis pour

4
traiter une unité de produit Pj dans la zone de travail Ai est pij (en heures), pour i = 1, 2 et
j = 1, ..., 5. La capacité hebdomadaire (en heures) de la zone de travail Ai est Ci . La société
peut vendre tout ce qu’elle produit de Pj au profit sj , pour j = 1, ..., 5.
Le directeur de l’usine pense régulièrement à écrire un programme linéaire pour maximiser
ses profits, mais ne l’a jamais fait pour la raison suivante : de l’expérience passée, il a observé
que l’usine fonctionne mieux quand au plus deux produits sont fabriqués à la fois. Il croit
que s’il utilise la programmation linéaire, la solution optimale consistera à produire tous les
cinq produits. Êtes-vous d’accord avec lui ? Expliquez, en vous servant de vos connaissances en
programmation linéaire.

Dualité linéaire
Exercice 14. On considère de nouveau le problème du régime mais sous une forme différente.
On suppose qu’il y a 6 aliments de base (numérotés de 1 à 6), dont le contenu en vitamines A
et C (unités/kg) et le coût (cents/kg) sont donnés dans le tableau suivant :

Aliments 1 2 3 4 5 6 Minimum vitamines

Contenu en vitamine A 1 0 2 2 1 2 9
Contenu en vitamine C 0 1 3 1 3 2 19
Coût des aliments 35 30 60 50 27 2
1. Un consommateur essaie de se constituer un régime diététique de coût minimal, de
manière à absorber au moins 9 unités de vitamine A et 19 unités de vitamine C par
jours. En supposant que le régime cherché comporte yj kg de chaque aliment, écrire le
problème linéaire du consommateur diététicien amateur.
2. Un industriel de la pharmacie, fabricant de pilules, s’attaque au marché en proposant
au consommateur des pilules contenant les vitamines. Mais pour le convaincre, il doit
proposer les pilules à un prix inférieur à celui des aliments nécessaires pour arriver au
même résultat. Soit alors x1 et x2 le prix des vitamines A et C en pilules (en cents/unité).
Considérons maintenant, par exemple l’aliment numéro 5 : un kilogramme de cet aliment
contient 1 unité de vitamine A et 3 unités de vitamine C, de valeur x1 + 3x2 pour
le fabricant. Sachant qu’un kilogramme d’aliment 5 coûte 27 cents au consommateur,
le fabricant n’aura de chances de le convaincre que si ses prix vérifient la contrainte
x1 + 3x2 ≤ 27. Il en sera de même pour les autres aliments...
Formulez le problème du fabricant, qui, sous ces contraintes, cherchera à maximiser son
profit, c’est à dire ici son prix de vente de la dose quotidienne de vitamines.
3. Comparez les problèmes obtenu. Trouvez la solution du problème de fabricant des pilules
par l’algorithme du simplexe. Identifiez les solutions optimales du problème de consom-
mateur, interprétez-les.

Exercice 15.
1. Montrez que l’ensemble polyédrique
 
n x1 + x2 ≤ 2, x2 + x3 ≤ 2, ..., xn + x1 ≤ 2,
X= x∈R :
−x1 − ... − xn ≤ −n

5
 n’est pas vide.
2. Montrez que l’ensemble polyédrique
 
n x1 + x2 ≤ 2, x2 + x3 ≤ 2, ..., xn + x1 ≤ 2,
X= x∈R :
−x1 − ... − xn ≤ −n−0.01

est vide.

Exercice 16. L’agriculteur Mr Robin possède 45 hectares de terre. Chaque hectare peut être
planté avec du blé ou du maı̈s. Chaque hectare de blé rapporte 2000ede profit ; et chaque hectare
de maı̈s en rapporte 3000e. Travail et les besoins en engrais par hectare pour planter du blé et
du maı̈s sont les suivants :

maı̈s blé
Travail 3 travailleurs 2 travailleurs
Engrais 2 tonnes 4 tonnes

On suppose que 100 travailleurs et 120 tonnes d’engrais sont disponibles.

(1) Proposer une formulation LP du problème de maximisation du profit de Mr
Robin.
(2) Développer le problème dual et écrivez une interprétation de celui-ci.

Exercice 17. Écrire le problème dual au problème du regime de l’exercice 1. Donner une breve
interprétation de celui-ci.

Exercice 18. Une usine produit, sur deux chaı̂nes, des appareils électroniques. En raison de
différences importantes dans les procédés de fabrication, les temps nécessaires aux machines
outils “fabrication” (FAB) et “finition-réglage” (FIR) pour traiter un appareil diffèrent sensible-
ment sur chaque chaı̂ne, avec des prix de revient eux aussi sensiblement différents. L’élaboration
d’un appareil sur la chaı̂ne 1 nécessite 3 heures de FAB et 1 heure de FIR, pour un prix de
revient unitaire de 20Ke, tandis que la 2ème chaı̂ne le produit pour 60Ke avec 1 heure de FAB
et 2 heures de FIR. La machine FAB est disponible 60 heures par mois, et la machine FIR 70
heures.
1. La demande étant de 30 appareils par mois au moins, écrire le problème d’OL permettant
de déterminer le plan de production (charges x1 et x2 des chaı̂nes) de coût minimal.
2. Écrire et interpreter son dual.
3. Quel problème est plus adapté pour être résolu par l’algorithme du simplexe ? Trouver la
solution optimale de ce problème (primal ou dual, à vous de decider) et reconstruire la
solution du problème complémentaire.

6
Exercice 19. Soit PL
    

 −1 2 0   1 

1 −2 −2 x −3
 

 


 1 



min 2x2 − 4x3 : 
 0 2 −2   x2  ≥  0
 




  1 5 1  x3  −2 

 
−1 −1 3 0
 

Montrez que x = [1; 1; 1] est une solution optimale.

Exercice 20. Expliquez comment vous allez résoudre le problème suivant en utilisant l’OL :
étant donné deux polyèdres

P1 = {x ∈ Rn : Ax ≤ b}, P2 = {x ∈ Rn : Cx ≤ d},

vous devez soit montrer que P1 ⊆ P2 , soit trouver un point dans P1 qui n’est pas dans P2 .
On suppose données les matrices A, C ∈ Rm×n et les vecteurs b, d ∈ Rm .

Exercice 21. Proposez une méthode de construction d’un hyperplan qui sépare deux polyèdres

P1 = {x ∈ Rn : Ax ≤ b}, P2 = {x ∈ Rn : Cx ≤ d}.

(on suppose que l’intersection de P1 et P2 soit vide.)

aT x = γ

Votre méthode doit rendre un vecteur a ∈ Rn tel que

aT x < γ ∀x ∈ P1 , et aT x < γ ∀x ∈ P2 .

Réduction aux problèmes linéaires

Exercice 22. Formulez les problèmes suivantes comme programmes linéaires. Pour chaque
programme donner une forme canonique ou standard du problème (assemblez avec soin la matrice
A du problème). Dans tous les problèmes C ∈ Rm×n et d ∈ Rm .

7
 1. minz∈Rn {kCz − dk1 : kzk∞ ≤ 1}
2. minz∈Rn {kzk1 : kCz − dk∞ ≤ 1}
3. minz∈Rn kCz − dk1 + rkzk∞ , avec r > 0
4. minz∈Rn m T T
P
i=1 max{0, ci z + di }, où ci sont les lignes de C
5. minz∈Rn {kzk1 : kCz − dk∞ ≤ r}, r > 0
6. minz∈Rn rkCz − dk∞ + kzk1 , r > 0.

Exercice 23. On considère le problème d’optimisation en x ∈ R :

min{cT x : kAx + bk1 ≤ 1},

où A ∈ Rm×n , b ∈ Rm et c ∈ Rn .
1. Formuler le problème comme un PL avec des contraintes d’inégalité.
2. Dérivez le problème linéaire dual, et montrez qu’il est équivalent au problème

max{bT z − kzk∞ : AT z + c = 0}.

Quel est le lien de z optimal et de la solution optimale du problème linéaire dual.

Exercice 24. On considère le problème PM suivant en x ∈ Rn :

min{kxk1 : kAx − bk∞ ≤ γ}.

1. Formuler le problème comme un PL avec des contraintes d’inégalité.

2. Dérivez le problème linéaire dual, vérifiez qu’il est équivalent au problème

max{bT z − γkzk1 : kAT zk∞ ≤ 1}.

2 Programmes convexes

Fonctions et ensembles convexes

Exercice 25. On définit la dimension d’ensemble X comme la dimension du plus petit ensemble
affine (plan dans l’espace) qui contient X.

Dans la liste ci-dessous donnez la dimension de chaque ensemble et indiquez si l’ensemble

est convexe.
1. Rn
2. {0}
Pn
3. {x ∈ Rn : i=1 ixi = 0}
Pn
4. {x ∈ Rn : i=1 ixi ≤ 0}

8
 Pn
5. {x ∈ Rn : i=1 ixi ≥ 0}
Pn
6. {x ∈ Rn : 2
i=1 ixi = 1}
Pn
7. {x ∈ Rn : 2
i=1 ixi ≤ 1}
Pn
8. {x ∈ Rn : 2
i=1 ixi ≥ 1}
9. {x ∈ R2 : |x1 | + |x2 | ≤ 1}
10. {x ∈ R2 : |x1 | − |x2 | ≤ 1}
11. {x ∈ R2 : −|x1 | − |x2 | ≤ 1}

Exercice 26. Cochez les fonctions convexes dans la liste ci-dessous :

— f (x) ≡ 1 sur R
— f (x) = x sur R
— f (x) = |x| sur R
— f (x) = −|x| sur R
— f (x) = −|x| sur R+ = {x : x ≥ 0}
— exp{x} sur R
— exp{x2 } sur R
— exp{−x2 } sur R
— exp{−x2 } sur {x : x ≥ 100}

Exercice 27. Vérifiez que les fonctions suivantes sont convexes sur les domaines indiqués :
2
— xy on {(x, y) ∈ R2 : y > 0}
— ln(exp{x} + exp{y}) sur R2

Dualité de Lagrange
Exercice 28. Trouver l’expression analytique des fonctions

1
xT x − z T x

1. f (z) = minx∈Rn
 21 T T
z T x , avec B tel que B T B est inversible.

2. f (z) = minx∈Rn 2 x B Bx −

Exercice 29. Soit a ∈ Rn et G ⊂ Rn convexe et fermé. On appelle x∗ = πG (a) projection

(Euclidienne) de y sur G si x∗ est la solution optimale de problème

min{ka − xk2 : x ∈ G}.

x

Calculez les projections dans les cas suivants :

— G = {x ∈ Rn : kxk2 ≤ 1}
— G = {x ∈ Rn : −1 ≤ xP i ≤ 1, i = 1, ..., n}
— G = {x ∈ R : Pn x ≥ 0, ni=1 xi = 1}
— G = {x ∈ R : ni=1 |xi | ≤ 1}
n

9
Exercice 30. Soit le problème d’optimization lineaire

min{cT x Ax ≤ b}
x

avec la matrice A m×n et soit x∗ une solution optimale. Cela implique que x∗ est un minimiseur
de la fonction convexe et différentiable f (x) = cT x sous les contraintes convexe et différentiables
Ax ≤ b. Ainsi, les conditions nécessaires et suffisantes de Karush-Kuhn-Tucker sont satisfaites
en x∗ .
Que signifient ces conditions en termes de A, b, c ?

Exercice 31. Trouver le minimum de la fonction linéaire

f (x) = cT x

sur l’ensemble
n
X
Bp = {x ∈ Rn | |xi |p ≤ 1};
i=1

où p, 1 < p < ∞, est le paramètre. Qu’arrive-t-il quand le paramètre devient 0.5 ?

Exercice 32. Soit a1 , ..., an > 0. Résoudre le problème d’optimisation

( n )
X ai X
min : x > 0, xi ≤ 1
x x2
i=1 i i

Exercice 33.
1. On considère le problème de moindres carrés sous contrainte de norme `1 :

min 12 (Ax − b)T (Ax − b) : kxk1 ≤ r


(LSC )
x

où r > 0 est un paramètre. Écrire le problème dual de (LSC ) (pour simplifier, on supposera
que AT A est inversible).
2. Soit
− b)T (Ax − b) + κkxk1
1 
min 2 (Ax (LSP )
x

On écrira (LSP ) sous la forme équivalente, en introduisant une variable supplémentaire :

min 12 (Ax − b)T (Ax − b) + κv : kxk1 − v ≤ 0 (LSP0 )


x,v

Écrivez le problème dual de (LS0P ), comparez-le au dual de (LSC ).

10