Devoir 1
1. Considérer le problème de programmation linéaire suivant :
Max 1000x1 + 1200x2
Sujet à
8x1 + 4x2 ≤ 160
4x1 + 6x2 ≤ 120
x1 ≤ 34
x2 ≤ 14
x1 , x2 ≥ 0
Résoudre ce problème avec l’algorithme du simplexe (forme tableau).
2. Considérer le problème de programmation linéaire suivant :
Max 45x1 + 80x2
Sujet à
5x1 + 20x2 ≤ 400
10x1 + 15x2 ≤ 450
x1 , x2 ≥ 0
Résoudre ce problème avec l’algorithme du simplexe (forme tableau).
3. Résoudre les problèmes avec la méthode graphique
a) Min - 2x1 - x2
Sujet à
x1 + 4x2 ≤ 24
x1 + 2x2 ≤ 14
2x1 - x2 ≤ 8
x1 - x2 ≤ 3
x1 , x2 ≥ 0
b) Max 45x1 + 80x2
Sujet à
5x1 + 20x2 ≤ 400
10x1 + 15x2 ≤ 450
x1 , x2 ≥ 0
4. Considérer le problème de programmation linéaire suivant :
Min -3x1 - 6x2
Sujet à
3x1 + x2 ≤ 48
x1 + 3x2 ≤ 48
x1 , x2 ≥ 0
a) Résoudre le problème avec la méthode graphique.
b) Résoudre ce problème avec l’algorithme du simplexe (forme tableau).
1
Devoir 2
1. Déterminer toutes les solutions de base réalisables pour le système
2 x1 + 6 x2 + x3 + x 4 = 3
6 x1 + 4 x2 + 3 x3 + 6 x4 = 2
x j ≥ 0, j = 1,2,3,4
2. Considérer le problème de programmation linéaire
min z = − x1 − 2 x2 − 3x3 + x 4
Sujet à
x1 + 2 x2 + 3 x3 = 15
2 x1 + x2 + 5 x3 = 20
x1 + 2 x2 + x3 + x 4 = 10
x j ≥ 0, j = 1,2,3,4
À une certaine itération du simplexe, l’inverse de la base est
⎡ 5 / 7 − 3 / 7 0⎤
⎢− 1 / 7 2 / 7 0 ⎥ .
⎢ ⎥
⎢⎣− 9 / 7 4 / 7 1⎥⎦
a) Poursuivre la résolution de ce problème après avoir identifié le tableau du
simplexe associé à cette base.
b) Supposons que le terme de droite de la troisième contrainte devienne égale à
8 (i.e., x1 + 2 x2 + x3 + x 4 = 8 ). La solution de base optimale obtenue en a)
demeure-t-elle réalisable? Quelle est la modification de la valeur optimale de
la fonction économique?
2
3. Considérer le problème de programmation linéaire suivant
min z = −4 x1 − 12 x2 − 3x3
Sujet à
x1 ≤ 100
x2 ≤ 50
x3 ≤ 150
3x1 + 6 x2 + 2 x3 ≤ 675
x j ≥ 0, j = 1,2,3
Dénotant x4 , x5 , x6 , x7 les variables d’écart, le tableau du simplexe associé à la base où
x4 , x5 , x6 , x7 sont les variables de base est de la forme
Var. base Termes
x1 x2 x 3 x 4 x5 x 6 x 7 − z droite
x4 1 0 0 1 0 0 0 0 100
x5 0 1 0 0 1 0 0 0 50
x6 0 0 1 0 0 1 0 0 150
x7 3 6 2 0 0 0 1 0 675
−z -4 -12 -3 0 0 0 0 1 0
Tableau 1
À une certaine itération de l’algorithme du simplexe, nous retrouvons le tableau
suivant
Var. base Termes
x1 x 2 x3 x 4 x5 x6 x7 − z droite
x1 1 0 0 0 –2 –2/3 1/3 0 a4
x2 0 1 0 0 1 0 0 0 50
x4 0 0 0 1 2 2/3 –1/3 0 75
x3 0 0 1 0 0 1 0 0 150
−z a1 a 2 a3 0 4 1/3 4/3 1 1150
Tableau 2
3
a) Spécifier l’inverse de la base associée au Tableau 2. Justifier comment on peut
la lire directement dans le Tableau 2.
b) Déterminer les valeurs de a1 , a 2 , a3 , a 4 dans le Tableau 2.
c) La solution dans le tableau 2 est-elle optimale? Pourquoi.
4. Considérer le problème de programmation linéaire suivant
min z = −3x1 − x 2 − 3x3
Sujet à
2 x1 + x2 + x3 ≤ 2
x1 + 2 x2 + 3x3 ≤ 5
2 x1 + 2 x2 + x3 ≤ 6
x j ≥ 0, j = 1,2,3
Utilisons les variables d’écart x 4 , x5 , x6 pour transformer le problème sous forme
standard.
À une itération du simplexe nous retrouvons le tableau suivant
x1 x2 x3 x 4 x5 x 6 − z
5 1 0 3 –1 0 0 f
e 0 1 –2 1 0 0 1
–5 0 0 –4 1 1 0 3
d 0 0 g 2 0 1 4
a) Spécifier l’inverse de la base associée à ce tableau du simplexe.
b) Déterminer les valeurs de d ,e, f, g.
c) La solution dans ce tableau est-elle optimale? Pourquoi. Sinon poursuivre la
résolution du problème pour identifier une solution optimale.
d) Quelle est la plus grande valeur ∆ de laquelle nous pouvons augmenter le
terme de droite de la première contrainte pour que la solution optimale
identifiée en c) demeure réalisable pour le nouveau problème ainsi généré, et
quelle est la valeur optimale de ce nouveau problème.
Devoir 3
1. Résoudre les problèmes suivants en utilisant d’abord une phase I
a) min z = –2x1 – x2 – x3
Sujet à
2x1 + 3x2 – x3 ≤ 9
2x2 + x3 ≥ 4
x1 + x3 = 6
xj ≥ 0, j = 1,2,3
b) min z = x1
Sujet à
x1 – 2x2 + x3 = 2
– x1 + 3x2 + x3 = 1
2x1 – 3x2 + 4x3 = 7
xj ≥ 0, j = 1,2,3
c) min z = x1
Sujet à
x1 + x 2 = 2
– 3x1 – 3x2 = 3
xj ≥ 0, j = 1,2
2. Considérons le système d’inégalités Ax ≥ b, x ≥ 0, où b ≥ 0. Nous transformons ce
système sous une forme standard en introduisant m variables d’écart y pour
obtenir le système suivant Ax – y = b, x ≥ 0, y ≥ 0 où b ≥ 0. Dénotons
bk = max {bi },
1≤i ≤ m
et considérons le nouveau sous forme standard obtenu du précédent en
additionnant la kième ligne à toutes les autres lignes après avoir changé leur signe.
Indiquer pourquoi il suffit d’introduire une seule variable artificielle pour obtenir
une solution de base réalisable initiale.
Illustrer cette procédure sur le problème suivant
x1 + 2x2 + x3 ≥ 4
2x1 + x2 + x3 ≥ 5
2x1 + 3x2 + 2x3 ≥ 6
xj ≥ 0, j = 1,2,3
Devoir 4
1. Résoudre avec la variante du simplexe pour problème avec variables bornées:
max x1 + 3x2 – 2x3
Sujet à
x2 – 2x3 ≤ 1
2x1 + x2 + 2x3 ≤ 8
0≤ x1 ≤1, 0≤ x2 ≤3, 0≤ x3 ≤2
2. Résoudre avec la variante du simplexe pour problème avec variables bornées
max 2x1 + 3x2 – 2x3 + 5x4
Sujet à
2x1 + 2x2 + x3 + 2x4 ≤ 5
x1 + 2x2 – 3x3 + 4x4 ≤ 5
0≤ xj ≤1 , j =1,2,3,4
Devoir 5
1. a) Supposant que le dual de
min c T x max b T y
Sujet à Ax ≥ b est Sujet à AT y ≤ c
x≥0 y ≥ 0.
démontrer que le dual de
min c T x max b T y
Sujet à Ax = b est Sujet à AT y ≤ c.
x≥0
b) Démontrer que le dual
max b T y min c T x
Sujet à AT y ≤ c est Sujet à Ax ≥ b
y≥0 x ≥ 0.
2. Supposer que x* et y* soient des solutions optimales du couple de problèmes
primal-dual suivant :
min c T x max b T y
Sujet à Ax ≥ b Sujet à AT y ≤ c
x≥0 y ≥ 0.
Supposer que x' soit une solution optimale du problème
min c T x
Sujet à Ax ≥ b′
x ≥ 0.
Démontrer que c T x′ ≥ b′T y * .
3. a) Résoudre graphiquement le problème de programmation linéaire suivant
max 3 y1 + 4 y 2
Sujet à 2 y1 + y 2 ≤ 2
y1 − 2 y 2 ≤ 6
3 y1 + 9 y 2 ≤ 1.
b) Écrire le dual de ce problème. Utiliser la théorie des écarts complémentaires
pour déterminer une solution optimale de ce problème à partir d’une solution
optimale de primal qui lui est associé.
Devoir 6
1. Démontrer que ni le problème suivant, ni son dual ne possèdent de solution
réalisable :
min x1 − 2 x2
Sujet à x1 − x2 ≥ 2
− x1 + x2 ≥ −1
2. Considérer le problème suivant
max z = 2 x1 − 4 x2
(Primal) Sujet à x1 − x2 ≤ 1
x1 , x2 ≥ 0
a) Écrire le problème dual et le résoudre par observation.
b) Utiliser la théorie des écarts complémentaires et la solution optimale du
problème dual pour déterminer une solution optimale du primal.
c) Pour quelles valeurs de c1, le coefficient de x1 dans la fonction
économique du primal, le problème dual n’a pas de solution réalisable?
Pour ces valeurs de c1, qu’arrive-t-il pour le problème primal?
3. Utiliser la méthode duale du simplexe pour résoudre le problème suivant :
min 3 x1 + x2 + x3
Sujet à x1 + 2 x2 ≥8
3 x1 − 2 x 2 − x3 ≥ 6
− x1 − x2 + 4 x3 ≥ 2
x1 , x2 , x3 ≥ 0.
Devoir 7
1. Soit le problème
min z = 2 x1 + x 2 − 3 x 3 + 2 x 4
Sujet à x1 + 3 x 2 − x 3 + 2 x 4 ≤ 7
− x1 − 2 x 2 + 4 x 3 ≤ 12
− x1 − 4 x 2 + 3x 3 + 8 x 4 ≤ 10
x1 , x 2 , x 3 , x 4 ≥ 0.
Supposer que le tableau associé à la solution optimale de ce problème est le suivant :
x1 x2 x3 x4 x5 x6 x7 –z
3/10 1 0 4/5 2/5 1/10 0 0 4
–1/10 0 1 2/5 1/5 3/10 0 0 5
1/2 0 0 10 1 –1/2 1 0 11
7/5 0 0 12/5 1/5 4/5 0 1 11
a) De quelle quantité faut-il modifier le coût c4 pour qu’il devienne avantageux de
rendre la variable x4 positive?
b) Déterminer l’intervalle de variation [γ1 ,γ2] du coût c2 pour que la solution actuelle
demeure optimale.
c) Déterminer l’intervalle de variation [τ1 ,τ2] du terme de droite de la seconde
contrainte pour que la solution actuelle demeure réalisable et optimale.
d) Introduire une nouvelle variable y dans le problème original ayant 1 comme
coefficient dans chacune des contraintes et un coût unitaire égal à –2. Déterminer
une solution optimale du problème modifié.
e) Introduire la nouvelle contrainte suivante dans le problème original :
x1 + x 2 + x 3 + x 4 ≤ 15.
Le problème modifié possède-t-il une solution réalisable? Si oui, déterminer une
solution optimale du problème modifié.
2. Soit le problème
min z = x1 − 3x 2 + 2 x 3
Sujet à 3 x1 − x 2 + 2 x 3 ≤ 7
− 2 x1 + 4 x 2 ≤ 12
− 4 x1 + 3x 2 + 8 x 3 ≤ 10
x1 , x 2 , x 3 ≥ 0.
Le tableau associé à la solution optimale de ce problème est le suivant :
x1 x2 x3 x4 x5 x6 –z
1 0 4/5 2/5 1/10 0 0 4
0 1 2/5 1/5 3/10 0 0 5
0 0 10 1 –1/2 1 0 11
0 0 12/5 1/5 4/5 0 1 11
a) De quelle quantité faut-il modifier le coût c3 pour qu’il devienne avantageux de
rendre la variable x3 positive?
b) Déterminer l’intervalle de variation [γ1 ,γ2] du coût c6 pour que la solution actuelle
demeure optimale.
c) Déterminer l’intervalle de variation [τ1 ,τ2] du terme de droite de la seconde
contrainte pour que la solution actuelle demeure réalisable et optimale.
d) Supposons que le coefficient a33 de la variable x3 dans la troisième contrainte
prenne la valeur 12 plutôt que 8 comme dans le problème original. Déterminer
une solution optimale du problème modifié.
e) Introduire une nouvelle variable y dans le problème original ayant 1 comme
coefficient dans la première contrainte, 1 dans la deuxième, 9 dans la troisième, et
un coût unitaire égal à –1. Déterminer une solution optimale du problème modifié.
f) Introduire la nouvelle contrainte suivante dans le problème original :
x1 + 3 x 2 + x 3 ≤ 18.
Le problème modifié possède-t-il une solution réalisable? Si oui, déterminer une
solution optimale du problème modifié.
