Exercices

1 Problèmes d’optimisation linéaire

1. Un étudiant dispose de 100 heures de travail pour étudier les examens A, B et C. Il pense gagner
par heure de travail et par cours: 1/5 de points pour le cours A, 2/5 de points pour le cours B
et 3/5 pour le cours C. Chaque examen est noté sur 20. Les exercices de ces cours comptent
pour la moitié de la note finale. Ses résultats pour les exercices lui ont été communiqués. Il a
obtenu 12/20 pour A, 12.5/20 pour B et 13.4/20 pour C. L’étudiant doit obtenir au minimum une
note globale de 12/20 pour chaque cours. Tous les cours ont la même pondération et l’étudiant
désire obtenir la moyenne la plus élevée possible. Formulez ce problème comme un problème
d’optimisation linéaire (solution lors d’une séance ultérieure).
2. Une société produit des biens A, B et C. La production des biens nécessite l’utilisation de 4
machines. Les temps de production et les profits générés sont repris dans le tableau suivant :

Machines
Biens 1 2 3 4 Profit
A 1 3 1 2 6
B 6 1 3 3 6
C 3 3 2 4 6

Les temps de production disponibles sur les machines 1, 2, 3 et 4 sont de 84, 42, 21 et 42 et la
société cherche à maximiser son profit. Formulez ce problème comme un problème d’optimisation
linéaire.

3. Il y a au Bénin I communes, J écoles et G niveaux d’enseignement. L’école j possède une capacité

d’accueil de cj g écoliers pour le niveau g. Dans la commune i, le nombre d’écoliers devant suivre
le niveau d’enseignement g est égal à sig . Enfin, la distance de l’école j à la commune i est égale
à dij . On demande d’affecter les écoliers dans les écoles de façon à minimiser la distance totale
parcourue par l’ensemble des écoliers. Formulez ce problème comme un problème d’optimisation
linéaire.

4. Résolvez géométriquement le problème suivant :

maximiser 12x1 + 16x2

x1 + x2 ≤ 150
1/2x1 + 3x2 ≤ 200
x1 , x2 ≥ 0

La fonction objectif change et devient 17x1 + 16x2 . Que se passe-t-il? L’ensemble des solutions
optimales est-il toujours fini?
5. Soit le problème d’optimisation linéaire :

minimiser c1 x1 + c2 x2 + c3 x3
x1 + x2 ≥ 1
x1 + 2x2 ≤ 3
x1 , x2 , x3 ≥ 0

1
 Représentez l’ensemble des solutions admissibles en utilisant les variables x1 et x2 . Trouvez le
coût optimal et les solutions optimales pour les valeurs suivantes de c: c = ( 1, 0, 1), c = (0, 1,
0) et c = (0, 0, 1).
6. Trouvez, si possible, des problèmes d’optimisation linéaire pour lesquels le problème

(a) Possède un coût optimal fini et exactement une solution optimale.

(b) Possède exactement deux solutions optimales.
(c) Possède un coût optimal infini.
(d) Possède un coût optimal fini et un ensemble de solutions optimales infini et borné.
(e) Possède un coût optimal fini et un ensemble de solutions optimales non-borné.

7. Soit le problème d’optimisation linéaire

maximiser cT x
Ax ≥ b

Comment évolue l’objectif optimum si on ajoute une contrainte?

2
2 Forme canonique
1. Ecrivez le programme linéaire suivant sous forme géométrique

maximiser -x1 + 8x2

x1 + x2 = 1
x1 + 2x2 ≤ 3
x1 ≥ 0

2. Ecrivez le programme linéaire suivant sous forme standard

minimiser -x1 + 8x2

x1 + x2 = 1
x1 + 2x2 ≤ 3
x1 ≥ 0

3. Ecrivez le programme linéaire suivant sous forme standard

minimiser x1 - 5x2 - 7x3

5x1 - 2x2 + 6x3 ≥ 5
3x1 + 4x2 - 9x3 = 3
7x1 + 3x2 + 5x3 ≤ 9
x1 ≥ -2

4. Soit le problème d’optimisation

minimiser 2x1 + 3|x2 − 10|

|x1 + 2| + |x2 | ≤ 5

3
3 Simplexe
1. Soit le problème d’optimisation

minimiser -2x1 - x2
x1 - x2 ≤ 2
x1 + x2 ≤ 6
x1 , x2 ≥ 0

Convertissez ce problème sous forme standard et trouvez un sommet pour lequel x1 = x2 = 0.

Résolvez le problème au moyen de la méthode du simplexe. Tracez une représentation graphique
en terme des variables x1 , x2 et indiquez le chemin suivi par la méthode.
2. Considérez le problème

minimiser 20x1 + αx2 + 12x3

x1 ≤ 400
2x1 + βx2 + x3 ≤ 1000
2x1 + γx2 + 3x3 ≤ 1600
x1 , x2 , x3 ≥ 0

Proposez, si possible, des valeurs pour α, β et γ pour lesquelles:

(a) Le coût optimal est fini et la solution optimale est unique.
(b) Le coût optimal est fini et il y a une infinité de solutions optimales.
(c) Le coût optimal est non borné (trouvez une paramétrisation de valeurs de x parmi lesquelles
se trouvent des solutions de coûts arbitrairement faibles).
(d) Le polyèdre possède un sommet dégénéré.
3. Résoudre par l’algorithme du simplexe les problèmes

maximiser 2x1 + 3x2

x1 + 2x2 ≤ 4
x1 + x2 = 3
x1 , x2 ≥ 0

maximiser 20x1 + 16x2 + 12x3

x1 ≤ 400
2x1 + x2 + x3 ≤ 1000
2x1 + 2x2 + 3x3 ≤ 1600
x1 , x2 , x3 ≥ 0

maximiser 4x1 + 3x2 + 6x3

3x1 + x2 + 3x3 ≤ 30
2x1 + 2x2 + 3x3 ≤ 40
x1 , x2 , x3 ≥ 0

maximiser -x1 + 4x2

-3x1 + 4x2 ≤ 6
x1 + 2x2 ≤ 4
x2 ≥ -3

4
4. Nous reprenons un des problèmes précédents. Un étudiant dispose de 100 heures de travail pour
étudier les examens A, B et C. Il pense gagner par heure de travail et par cours: 1/5 de points
pour le cours A, 2/5 de points pour le cours B et 3/5 pour le cours C. Chaque examen est noté
sur 20. Les exercices de ces cours comptent pour la moitié de la note finale. Ses résultats pour
les exercices lui ont été communiqués. Il a obtenu 12/20 pour A, 12.5/20 pour B et 13.4/20 pour
C. L’étudiant doit obtenir au minimum une note globale de 12/20 pour chaque cours. Tous les
cours ont la même pondération et l’étudiant désire obtenir la moyenne la plus élevée possible.
Formulez ce problème comme un problème d’optimisation linéaire et résolvez-le. Vous pouvez
utiliser le fait que l’étudiant a avantage à utiliser la totalité des 100 heures de travail. L’étudiant
obtiendra-t-il une distinction?
5. Une société produit des biens A, B et C. La production des biens nécessite l’utilisation de 4
machines. Les temps de production et les profits générés sont repris dans le tableau :

Machines
Biens 1 2 3 4 Profit
A 1 3 1 2 6
B 6 1 3 3 6
C 3 3 2 4 6

Si les temps de production disponibles sur les machines 1, 2, 3 et 4 sont de 84, 42, 21 et 42,
déterminez la quantité de biens à produire pour maximiser le profit.
6. Considérez le problème d’optimisation

minimiser 20x1 + αx2 + 12x3

x1 ≤ 4
2x1 - x2 + x3 ≤ 10
2x1 + βx2 + 3x3 ≤ 16
x1 , x2 , x3 ≥ 0

Trouvez une solution optimale au moyen de l’algorithme du simplexe lorsque α = -2 et β = 1.

Proposez des valeurs pour α et β pour lesquelles le coût optimal est non borné et proposez dans
ce cas une solution pour laquelle le coût optimal est inférieur à -1000.
7. Considérez le problème d’optimisation

minimiser αx1 + 16x2 + 12x3

x1 ≤ 400
2x1 - x2 + x3 ≤ 1000
2x1 + 2x2 + 3x3 ≤ 1600
x1 , x2 , x3 ≥ 0

Trouvez une solution optimale au moyen de l’algorithme du simplexe lorsque α = 20. Existe-t-il
une valeur de α pour laquelle le coût optimal est non borné? Si oui, proposez une solution pour
laquelle le coût est supérieur à 10000. Si non, justifiez votre réponse.

5
4 Optimisation discrète
1. Considérez le problème d’optimisation en nombres entiers

maximiser 5x1 + x2
-x1 + 2x2 ≤ 4
x1 - x2 ≤ 1
4x1 + x2 ≤ 12
x1 , x2 ≥ 0
x1 , x2 entiers

Trouvez graphiquement une solution de ce problème. Trouvez graphiquement une solution op-
timale du problème relaxé. Trouvez la solution entière la plus proche de la solution optimale
du problème relaxé. Enumérez toutes le solutions entières obtenues en arrondissant la solution
optimale du problème relaxé. Une de ces solutions est-elle optimale?
2. Yves et Muriel désirent partager les principales tâches ménagères (courses, cuisine, vaisselle et
nettoyage) entre eux. Leurs efficacités à la réalisation de ces tâches diffèrent. Yves est rapide
pour faire les courses et la vaisselle mais il se fait distancer par Murielle pour la cuisine et le
nettoyage.

courses cuisine vaisselle nettoyage

Yves 4.5 7.8 3.6 3.1
Muriel 4.9 7.2 4.3 2.9

Le jeune couple désire partager les tâches de manière équitable (deux tâches par personne) et
optimale (temps total minimum). Formulez ce problème comme un problème d’optimisation en
nombres entiers. Donnez une relaxation de ce problème. La solution du problème relaxé est-elle
entière? Que pouvez-vous en déduire?
3. Vouz désirez choisir un ensemble de cours parmi huit cours {1, . . . , 8} pour vous constituer
un programme. Modélisez les contraintes suivantes:

(a) Vous ne pouvez pas choisir plus de 5 cours mais devez en choisir au moins 3.
(b) Le cours 3 est un prérequis du cours 6 et le cours 2 un prérequis du cours 7.
(c) Les cours 8 et 6 forment une paire. Vous devez les prendre tous les deux, ou aucun des
deux.
(d) Pour des questions de conflit horaire, vous ne pouvez pas choisir les cours 5 et 2, ni les cours
3 et 6.
(e) Pour vous conformer aux contraintes de votre programme d’étude vous devez choisir au
moins un des cours 1, 2, 3 ou au moins deux cours parmi les cours 5, 6, 7, 8.

4. Une société a développé deux nouveaux jouets pour la Noël. La production du jouet 1 nécessite
des investissements initiaux de 50000 EUR et celle du jouet 2 des investissements initiaux de
80000 EUR. Les jouets génèrent un profit de 10 EUR pour le jouet 1 et de 15 EUR pour le jouet
2. Le jouet 1 est produit à un taux de 50 l’heure et le jouet 2 à un taux de 25 l’heure. On dispose
de 500 heures d’ici Noël.
Déterminez le nombre de jouets à produire de manière à maximiser le profit.
Supposons maintenant que la société possède deux usines. Une seule usine sera choisie pour
la production. Le jouet 1 est produit à un taux de 50 l’heure dans l’usine 1 et de 40 l’heure
dans l’usine 2. Le jouet 2 est produit à un taux de 25 l’heure dans les deux usines. Les usines
disposent de 500 et 700 heures d’ici Noël. Le problème consiste à déterminer le nombre de jouets
à produire de manière à maximiser le profit.
5. Vous disposez de 4 objets de poids respectifs 5, 3, 8 et 7. Les utilités des objets sont de 17, 10,
25 et 7. Vous désirez sélectionner un ensemble d’objets de poids total inférieur à 12 et dont la
somme des utilités est maximale. Formulez le problème comme un problème d’optimisation en
nombres entiers. Trouvez la solution.

6
6. Vous disposez de 5 objets de poids respectifs 2, 4, 3, 3 et 2. Les utilités des ob- jets sont
respectivement de 9, 20, 14, 10 et 6. Vous désirez sélectionner un ensemble d’objets de poids
total inférieur à 10 et dont la somme des utilités est maximale. For- mulez le problème comme un
problème d’optimisation en nombres entiers. Appliquez l’algorithme “branch and bound” pour
trouver la solution. Justifiez les étapes de l’algorithme.

7. Considérez le problème d’optimisation en nombres entiers

maximiser 9x1 + 5x2

4x1 + 9x2 ≤ 35
x1 ≤ 6
x1 - 3x2 ≥ 1
3x1 + 2x2 ≤ 19
x1 , x2 entiers

Résolvez le problème graphiquement et algébriquement en utilisant la méthode “branch and

bound”.