Exercices à résoudre

1. Appliquer la méthode des 2 phases pour résoudre le problème suivant:

Min z = x1 + 2x2 + x4 + x5 - 5x6

6x1 - 2x2 + x3 - x4 + x5 + 2x6 = 4
2x1 - 1/3x2 - x3 + x4 + 1/2x5 = 3
3x1 - x2 + 2x3 + 4x4 + 1/2x5 + x6 = 2

xi ≥ 0, i = 1, 2, 3, 4, 5, 6.

2. i) Déterminer toutes les solutions de base réalisables pour le système suivant:

2x1 + 6x2 + x3 + x4 = 3
6x1 + 4x2 + 3x3 + 6x4 = 2
x1 ≥ 0, x2 ≥ 0, x3≥ 0, x4 ≥0

ii) L'hypothèse de non-dégénérescence est-elle vérifiée? Pourquoi?

3. [DANT 63]

Déterminer une condition suffisante pour qu'un problème de programmation linéaire possède une
solution optimale unique. Si la condition n'est pas vérifiée, indiquer comment construire les
autres solutions optimales s'il en existe.

4. [DANT 63]

Étant donné une solution de base réalisable pour un problème de programmation linéaire où les
variables de base sont xj , xj , ..., xj , démontrer que la variable hors-base xs peut remplacer la
1 2 m
variable de base xj pour former une nouvelle solution de base seulement si ars ≠ 0 dans la forme
r
canonique.

5. [LUEN 73]

Démontrer que lorsqu'on applique la Phase I du simplexe à un problème de programmation

linéaire ayant un ensemble de points réalisables non vide, si une variable artificielle sort de la
base, il ne sera jamais nécessaire qu'elle devienne une variable d'entrée. Ainsi, lorsqu'une
variable artificielle sort de la base on peut l'éliminer du problème.
6. [DANT 63]

Supposons que la Phase I du simplexe appliquée à un problème de programmation linéaire se

termine avec une valeur Min w = 0 et qu'une variable artificielle est une variable de base avec un
coefficient unitaire dans la kième ligne de la forme canonique. Démontrer que toute variable
originale ayant un coefficient akj ≠ 0 peut remplacer cette variable artificielle comme variable de
base. Démontrer également que si akj = 0 pour toute variable originale, alors la k ième contrainte
est redondante dans le système original et on peut tout simplement la laisser tomber.

7. [GASS 75]

Supposons que le problème de programmation linéaire sous forme standard possède une solution
optimale finie et dénotons la valeur optimale de l'objectif par z 0. On utilise l'algorithme du
simplexe pour résoudre ce problème. Supposons qu'à la k ième itération on retrouve une solution
de base réalisable dégénérée comportant exactement une variable de base nulle. Dénotons par z k
la valeur de l'objectif à la k ième itération et supposons que zk > z0. Démontrer que la base qu'on
retrouve à la kième itération ne peut se représenter au cours des itérations subséquentes.

8.

Considérons un modèle de substitution-Léontief. On doit produire m items. La constante b i, i =

1, 2, ..., m, représente le nombre d'unités de l'item i que doit fournir annuellement le système pour
satisfaire aux demandes des clients.

Chaque activité produit un et un seul item. Indexons par j k la kième activité pouvant produire
l'item j, et dénotons par la variable x j le nombre d'unités d'item j produit annuellement par
k
l'activité jk. Pour produire une unité d'item j, l'activité jk requiert l'utilisation de aij unités d'item
k
i et incombe un coût de cj . Supposons que n activités sont disponibles et que pour chaque
k
activité j, 1 ≤ j ≤ n, m
å aij < 1.
i=1

i) Formuler le problème correspondant de programmation linéaire où on doit satisfaire aux

demandes annuelles à un coût minimum.
ii) Supposons que bi > 0, i = 1, 2, ..., m. Démontrer que dans toute solution de base réalisable du
problème formulé en i), il y a exactement une activité pour chaque item qui est opérée à un
niveau positif.

iii) Supposons que bi ≥ 0, i = 1, 2, ..., m. Démontrer qu'il existe une solution de base réalisable
du problème formulé en i).

9. Trouver une solution optimale au programme linéaire:

2x1 + x2 - x3 ≤ 4, xi ≥ 0,
4x1 - 3x2 ≤ 2
- 3x1 + 2x2 + x3 ≤ 3
x1 - 7x2 + 3x3 = z(Max)

10. En introduisant un nombre minimal de variables artificielles, résoudre le programme linéaire:

2x1 + 4x2 - 3x3 ≥ 1, x1, x2, x3 ≥ 0,

x1 - 3x2 + 2x3 ≥ -3
- x1 + x3 ≥ 3
4x1 + 2x2 + 3x3 = z(Min)

11. Résoudre le problème de l'exercice 10 sans introduire de variables artificielles.

12. Résoudre le programme linéaire:

x1 + 2x2 - 3x3 = 1, xi ≥ 0, i = 1, 2, 3
2x1 - x2 - 5x3 ≤ 2
x1 + 3x2 - x3 ≥ 1
x1 + 2x2 + 3x3 = z(Min)

en employant deux méthodes différentes.

13. Résoudre le programme linéaire

x1 ≥ 0, x2 ≤ 0,
4x1 + 2x2 + x3 ≤ 65
x1 + x2 - x3 ≥ 5
x1 + x2 = 10
6x1 - 3x2 + x3 = C(Min)
14. Résoudre le programme linéaire

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0,
x1 + 2x2 + 3x3 ≤ 14
2x1 - x2 + 3x3 ≤ 9
x1 + 3x2 - 2x3 ≤ 3
x1 + x2 + x3 ≤ 7
3x1 + 2x2 + x3 = P(Max)

15. Trouver une solution non négative au système:

3x - 4y -6z ≤ 2
2x +y +2z ≥ 11
x + 3y -2z ≤ 5.

16. En appliquant l'algorithme du simplexe à un problème de minimisation, on obtient à une

itération le tableau suivant:

x y z s t u v

1 4/5 0 6/5 3/5 1/5 0 9/5

0 -6/5 1 1/5 -2/5 1/5 0 9/5
0 3/5 0 -13/5 1/5 -3/5 1 3/5

0 -3/5 0 13/5 4/5 8/5 0 -3/5

Étant donné que la matrice inverse de la base courante est:

B-1 = [a.1, a.3, a.7]-1

= 3/5 1/5 0
-2/5 1/5 0
1/5 -3/5 1

et que le vecteur correspondant des coûts cB est égal à:

cB = (c1, c3, c7) = (0, 0, 1)

retrouver le problème original.

Pour faciliter les calculs numériques, vous pouvez utiliser le fait que la matrice

3/5 1/5 0
-2/5 1/5 0
1/5 -3/5 1

admet pour inverse

1 -1 0
2 3 0
1 2 1

17. [HILL 90]

En utilisant une extension de la méthode du simplexe pour des problèmes linéaires avec variables
bornées, résoudre les problèmes suivants:

i) Max Z = 2x +y
sujet à x -y ≤5
x ≤ 10
y ≤ 10
x, y ≥ 0.

ii) Max Z = x + 3y - 2z
sujet à y - 2z ≤1
2x +y + 2z ≤8
x ≤1
y ≤3
z ≤2

x, y, z ≥ 0.

iii) Max Z = 2x + 3y - 2z + 5u
sujet à 2x + 2y +z + 2u ≤5
x + 2y - 3z + 4u ≤5
x, y, z, u ≥ 0.
18. [GAUV 95, pp. 37, 39]

Remarquons qu'à une solution de base optimale x dégénérée peuvent correspondre plusieurs
bases {B} qui permettent d'écrire que: xB = B-1b ≥ 0 avec la possibilité pour l'une ou l'autre
t
d'entre elles que le vecteur des multiplicateurs du simplexe π B = B-1 cB ne soit pas une solution
réalisable pour le dual. Cette situation montre que la condition suffisante (un vecteur de coût
relatif non-négatif) n'est pas une condition nécessaire d'optimalité. Par contre, la méthode du
simplexe conduit nécessairement à une solution de base optimale avec une base pour laquelle le
vecteur des multiplicateurs du simplexe est réalisable, donc optimal pour le dual.

Illustrons ceci à l'aide du programme linéaire suivant:

Min x + 2y + 3z
sujet à x +y +z =1
x -y -z =1
x, y, z ≥0

Ce programme possède une seule solution réalisable, soit x = 1, y = z = 0, qui constitue une
solution de base optimale dégénérée. Montrer que, pour l'une des bases correspondant à cette
solution, il est possible d'avoir un coût relatif négatif pour une variable hors base. Ensuite,
formuler le dual et vérifier que cela correspond à un vecteur des multiplicateurs qui n'est pas
réalisable pour le dual. Enfin, donner toutes les solutions optimales du dual.

19. [GAUV 95, pp. 39-40]

Soit le programme linéaire suivant :

Min ctx
sujet à A x = b, x ≥ 0

où A est une matrice m x n de rang m. De plus, on émet l'hypothèse qu'il existe une solution x
telle que: A x = b, x > 0.

a) Peut-on vérifier cette hypothèse pour le programme de l'exercice 3.14.18?

b) Montrer que, selon cette hypothèse, une solution de base réalisable est optimale si et
seulement si les coûts relatifs sont tous positifs ou nuls.
20. [GAUV 95, p. 55]

Vérifier que la première phase de la méthode du simplexe conduit à détecter:

a) que le système suivant n'a pas de solution réalisable:

x +y +z =1
x -y +z =2
x, y, z ≥0

b) que le système suivant possède une équation redondante:

x +y +z =1
2x + 2y + 2z =2
x, y, z ≥0

21. [CULI 94, p. 163]

Voici un exemple de cyclage de l'algorithme du simplexe. On considère le problème de Klee-

Minty 1

n
Max ∑ 10n-j xj
x ≥ 0 j=1

i-1
sujet à (2 ∑ 10i-j xj) + xi ≤ 100i-1, i = 1, ..., n
j=1

Résoudre ce problème pour n = 3 en utilisant, pour passer d'une base à l'autre, la variable
correspondant au plus grand coût relatif. Le résoudre à nouveau en éliminant la variable de plus
faible coût relatif. Que pouvez-vous conclure sur la complexité de l'algorithme du simplexe? Sur
sa nature exponentielle?

22.

Résoudre par l'algorithme du simplexe modifié pour les variables bornées supérieurement, le
problème suivant:
1
Voir V. Klee, G.J.Minty, "How good is the simplex algorithm?", in Inequalities-III (O. Shisha,
Ed.). New-York: Academic Press, 1972, pp.159-175.
 Min W = - x1 - 7x2 - 3 x3 - 2 x4

sujet à 3x1 + 6x2 + x3 + x4 ≤ 12

2x1 + 3x2 - x3 + 3x4 ≤ 10
0 ≤ x1 ≤ 3, 0 ≤ x2 ≤ 3, 0 ≤ x3 ≤ 4, 0 ≤ x4 ≤ 4.

23.

Soit à résoudre par la méthode des 2 phases les programmes linéaires suivants:

i) Min W = 4x1 + x2 + x3

sujet à 2x1 + x2 + 2x3 = 4

3x1 + 3x2 + x3 = 3
0 ≤ x1, 0 ≤ x2, 0 ≤ x3.

ii) Min W = - x1 - 1.5x2 - 5 x3 - 2 x4

sujet à 3x1 + 2x2 + x3 + 4x4 ≤ 6

2x1 + x2 + 5x3 + x4 ≤ 4
2x1 + 6x2 - 4x3 + 8x4 = 0
x1 + 3x2 - 2x3 + 4x4 = 0
0 ≤ x1, 0 ≤ x2, 0 ≤ x3, 0 ≤ x4.

24.

Soit le problème de programmation linéaire

Min W = ctx
sujet à a1x1 + a2x2 + ...+ anxn ≤b
0≤xj ≤uj, 1≤ j ≤n.

Supposons que cj < 0, aj > 0, uj > 0, pour tout j, 1≤ j ≤n.

Supposons de plus que les variables sont ordonnées de telle sorte que

c1 / a1 < c2 / a2 < ... < cn / an.

a) Si nous résolvons ce problème avec la variante du simplexe pour les problèmes avec
variables bornées, indiquer l'ordre dans lequel les variables entrent et sortent de la base au
cours des itérations tout en justifiant votre réponse.

b) Supposons que, dans une solution optimale, x s soit la variable de base. Démontrer que x j =
uj pour tout j < s et xj = 0 pour tout j > s.

25.

Considérons l'exemple suivant proposé par E. Beale (l955):

Min z = -3/4x1 + 150 x2 - 1/50 x3 + 6 x4

sujet à x5 +1/4x1 -60x2 - 1/25 x3 + 9x4 = 0
x6 +1/2x1 -90x2 -1/50x3 +3x4 = 0
x7 +x3 = 1
xi ≥ 0, i = 1, 2, 3, 4, 5, 6, 7.

i) La méthode du simplexe cycle. Illustrez.

ii) En réexaminant les critères d'entrée et de sortie du simplexe, pouvez-vous éviter le

cyclage? Illustrez.

26. [NOBE 95, p. 219] Le jeu de société

Un manufacturier a obtenu la licence de fabrication d'un nouveau jeu de société. Il pense en

fabriquer 3 versions qui ne différeraient que par la qualité des matériaux utilisés. Il songe à une
version «Mordus», dont il pourrait tirer des profits de 4$ par unité vendue, à une version
«Amateurs», qui lui rapporterait 3$ l'unité et à une version «Grand Public», qui lui donnerait 2$
pour chaque unité vendue. Une étude de marché prédit une grande vogue pour ce nouveau jeu de
société. Durant les premiers mois, il n'aura pas de peine à écouler toute la production qu'il pourra
assurer. La fabrication d'une unité du jeu requiert, toutes versions confondues, le concours de 3
ateliers. Au cours du mois prochain, il compte se servir des heures de main-d'œuvre disponibles
dans ces ateliers pour maximiser ses profits. Voici, pour chaque atelier, le nombre de minutes
requises pour fabriquer une unité de chaque version.
 Nombre de minutes requises pour la fabrication d'une unité

Version Atelier 1 Atelier 2 Atelier 3

Mordus 3 4 2
Amateurs 4 3 3
Grand Public 2 2 2

Heures disponibles 300 300 200

Le manufacturier tient à fabriquer, du moins le premier mois, au moins 1000 unités de la version
Grand public. Combien doit-il fabriquer d'unités de chaque version au cours de ce premier mois
pour maximiser ses profits?

27. [NOBE 95, p. 220] Combinaisons linéaires convexes

Soit le modèle linéaire suivant:

Max z = 2x1 + x2
sujet à 2 x1 + 4 x2 ≥ 48
2 x1 + x2 ≥ 15
4 x1 + 2 x2 ≤ 60
x1, x2 ≥ 0

(a) Trouver les 2 tableaux optimaux de ce modèle.

(b) Trouver une expression algébrique qui permette de calculer toutes les solutions optimales
de ce modèle linéaire.
----------------------------------------------------------