Questions sur la méthode du simplexe
RCP101 – Recherche opérationnelle et aide à la décision
Question 1 :
Dans le cours et les exercices les programmes linéaires se présentent tous sous la
forme :
Variables : ≥0
Contraintes : ≤
Objectif : Max
Pourquoi le cas :
Variables : ≥0
Contraintes : ≥
Objectif : Max
n’est-il pas intéressant ?
Question 2 :
Peut-on concevoir un programme du type suivant :
Variables : ≥0
Contraintes : ≤, ≥, =
Objectif : Max
Donner un exemple concret.
Question 3 :
Ecrire le programme standard correspondant au programme linéaire suivant :
≥0; ≥0
2 + ≤ 300
+ ≥ 50
−2 = 70
Max 25 + 34
Question 4 :
Trouver, dans le même esprit qu’en cours, une solution évidente au système linéaire
suivant :
≥ 0; ≥ 0; ≥0; ≥ 0; ≥0
− = 100
− = 110
+ = 200
+ 4 = − 500
S’agit-il, toujours au sens du cours, d’une solution de base ? Pourquoi ?
Question 5 :
Mêmes questions pour le système suivant :
≥ 0; ≥ 0; ≥0; ≥0
+ = 200
1 1
+ + = 300
2 2
+2 =
Question 6 :
Pour déterminer la colonne du pivot on considère le plus fort coefficient positif dans la
ligne de la fonction économique.
Pour déterminer la ligne du pivot on considère le plus petit des rapports positifs R.
Ces deux critères sont-ils obligatoires, ou l’un d’eux est-il facultatif ? Lequel ?
Pourquoi ?
Question 7 :
Une entreprise fabrique et commercialise trois produits A, B et C. Elle fait face à deux
contraintes, une concernant le nombre maximal de machines à sa disposition et une
autre en rapport avec son stock limité de matières premières.
Elle désire maximiser son bénéfice.
On peut dès maintenant prévoir une particularité de la solution du programme linéaire
associé à cette situation. Laquelle ? Pourquoi ?
2
Question 8 :
On fabrique et on commercialise trois produits A, B et C. On fait maintenant face à
quatre contraintes.
Il s’agit toujours de maximiser le bénéfice.
Que peut-on prévoir quant à la solution du programme linéaire associé ?
Question 9 :
Cette question est une petite initiation à la mise en œuvre de l’une des méthodes
possibles à utiliser lorsque le programme linéaire comporte à la fois des contraintes
du type ≤ et du type ≥.
Soit le programme linéaire suivant :
≥ 0; ≥0
≥ 100
≥ 100
+ ≤ 400
Max +4
1) Ecrire le programme standard associé.
2) Remplir le premier tableau. Dispose-t-on d’une solution de base ?
3) En utilisant des formules de transformations de lignes comme en cours, obtenir
un nouveau tableau où la première colonne comporte un 1 en première ligne et
des 0 ailleurs.
4) Refaire le même travail avec la deuxième colonne de ce nouveau tableau pour
obtenir un troisième tableau comportant une deuxième colonne où figure un 1 en
deuxième ligne et des 0 ailleurs. Ce troisième tableau fournit-il une solution de
base permettant d’initier la méthode du simplexe ? Laquelle ?
5) Terminer en continuant de manière habituelle.
3
Question 10 :
Cette question est destinée à montrer qu’avec la méthode du simplexe il est possible
de mettre en évidence plusieurs solutions quand elles existent, et de détecter cette
situation.
Soit le programme linéaire suivant :
≥ 0; ≥0
≤ 200
+ 2 ≤ 600
Max +2
1) Ecrire le programme standard, compléter le premier tableau et déterminer le
deuxième tableau avec la méthode habituelle.
2) Que remarque-t-on d’inhabituel dans ce second tableau ?
3) Remplacer le 0 de la dernière ligne qui correspond à la variable hors base par
> 0 et faire entrer cette variable dans la base pour obtenir un nouveau
tableau. Que constate-t-on si on fait maintenant = 0 ?
4) Conclure.
5) Pouvait-on prévoir ce cas de figure en examinant le système linéaire initial ?
