Université Paris 7 Algorithmique Avancée M1 TD Du 25 Février 2009 ...
Université Paris 7
Algorithmique Avancée M1
TD du 25 Février 2009 : Fin de résolution
de systèmes d'équations linéaires
et méthode du simplexe avancée
Exercice 1 Résolution de système singulier
Résoudre le système Ax = b avec
1 2 −3 4
5
1
2
−2
2
8
A =
1
2
−1
1
10
1 2 −1 1 13
1
2
−1
1
15
et
3
5
5
5
b =
et
7
b = 5
10
10
12
12
Exercice 2 Matrices bandes
Une matrice carrée est dite k-bande si tous les éléments
sont nuls, sauf ceux appartenant aux k sur-diagonales et aux k sous-diagonales.
Si A a B sont k-bandes, est-il vrai qye leur produit soit -bande pour un certain entier et si
oui, l'entier s'exprime-t-il facilement en fonction de k ?
Exercice 3 Algorithme avancé
On considère le problème suivant
maximiser 19x1 + 13x2 + 12x3 + 17x4
soumis aux contraintes
3x1 + 2x2 + x3 + 2x4
225
x1 + x2 + x3 + x4
117
4x1 + 3x2 + 3x3 + 4x4
420
x1, x2, x3, x4
0
Sachant que les variables basiques à une étape sont x1, x3, x7, calculer le tableau qui corres-
pond.
Ce tableau donne-t-il la valeur maximale ? Sinon, dire quelles sont les variables entrante et
sortante et donner le tableau suivant.
Mêmes questions avec les variables basiques x1, x3, x4.
