exercices de recherche operationnelle - Exercices corriges

INTRODUCTION A LA RECHERCHE OPERATIONNELLE
RECUEIL D'EXERCICES
Année académique 2002-2003
Yves CRAMA Méthode du Simplexe S1) Ecrivez le problème PL suivant sous forme standard avec des M.d.D.
non négatifs:
Max z = 2x1 + 3 x2 + 5 x3 [pic]
Formulez son dual.
S2) Considérons l'ensemble de contraintes suivant:
x1 + 7 x2 + 3x3 + 7 x4 ( 46
3 x1 - x2 + x3 + 2 x4 ( 8
2 x1 + 3 x2 - x3 + x4 ( 10
Résolvez par la méthode du simplexe le problème obtenu lorsque la
fonction objectif est donnée par:
|a)|max z |= | 2x1|+ |- |+ 5x4|
| | | | |x2 |3x3 | |
|b)|max z |= |- 2x1|+ 6x2|+ 3x3|- |
| | | | | | |2x4 |
|c)|max z |= | 3x1|- |+ 3x3|+ 4x4|
| | | | |x2 | | |
|d)|min z |= | 5x1|- |+ 6x3|+ 8x4|
| | | | |4x2 | | |
|e)|min z |= | 3x1|+ 6x2|- |+4x4 |
| | | | | |2x3 | |
S3) Résolvez le problème suivant par la méthode du simplexe
max z = 5x1 + 4x2 + 3x3
s.c. 2 x1 + 3 x2 + x3 ( 5
4 x1 + x2 + 2 x3[pic] ( 11
3 x1 + 4 x2 + 2 x3 ( 8
x1, x2, x3 ( 0
S4) Résolvez le problème suivant par simple inspection, puis par la
méthode du simplexe
max z = 5 x1 - 6 x2 + 3 x3 - 5 x4 + 12 x5
s.c. [pic]
S5) Résolvez le problème suivant par la méthode du simplexe :
On doit organiser un pont aérien pour transporter 1600 personnes et 90
tonnes de bagages. Les avions disponibles sont de deux types: 12 du
type A et 9 du type B. Le type A peut transporter, à pleine charge,
200 personnes et 6 tonnes de bagages. Le type B, 100 personnes et 6
tonnes de bagages. La location d'un avion du type A coûte 800.000 F;
la location d'un avion du type B coûte 200.000 F.
S6) Les dictionnaires ci-dessous ont été obtenus après exécution de
quelques itérations de la méthode du simplexe sur différents
problèmes. Quelles conclusions pouvez-vous tirer sur base de
l'information contenue dans ces dictionnaires?
Les conclusions possibles sont par exemple:
. la solution courante est optimale, et vaut ...;
. le problème est non borné parce que ...;
. le problème est non réalisable parce que ...;
. la solution courante n'est pas optimale; dans ce cas, calculez la
solution optimale.
a) min z
[pic]
b) max z
[pic]
c) max z
s.c. [pic] Dualité & Sensibilité
DS1) Suite de l'exercice S6a).
Quel est le coût réduit de chacune des variables du problème?
DS2) Suite de l'exercice S3).
a) Si le coefficient de la variable x2 dans la fonction objectif
augmentait de 2 unités, quel serait l'effet produit sur la solution
optimale et la valeur optimale du problème? Et si cette augmentation
était de 4 unités?
b) Quel est le coût réduit de chacune des variables du
problème?
c) Quel est le prix dual de chacune des contraintes d'inégalité
du problème?
DS3) Considérons le programme linéaire suivant, exprimé sous forme
standard:
min z = 2x1 + x2
s.c.[pic]
a) Calculer le dictionnaire associé à la base B définie par les
variables de base x1, x2, x5 .
[pic]
b) La solution de base associée à B est-elle réalisable et
optimale? DS4) Soit le problème (P):
max z = 2x1 + 4x2 + 4x3 - 3x4
[pic]
La base optimale de (P) est
[pic]
et son inverse
[pic]
a) Formulez le problème dual de (P). b) Sur base des informations fournies (et donc, sans utiliser la
méthode du simplexe ni la méthode graphique), calculez la solution
optimale de (P) et celle de son dual. Expliquez la méthode que vous
utilisez. c) Si la fonction objectif de (P) est remplacée par
max z = 3x1 + 4x2 + 4x3 - 3x4 ,
la base B donnée ci-dessus reste-t-elle optimale? Justifiez
votre réponse.
DS5) Soit le problème suivant (P):
max z = 100x1 + 50x2 + 25 x3
[pic]
La base optimale de (P) est
[pic] [pic]
a) Ecrivez le dual de (P)
b) Quelle est la solution optimale du programme (P) et celle de son
dual?
c) Dans quel intervalle peut varier le membre de droite de la
contrainte (2) sans affecter l'optimalité de B ?
DS6) Soit le problème de programmation linéaire
max z = 60x1 + 30x2 + 20x3
[pic]
La résolution de ce problème par la méthode du simplexe permet de
calculer la base optimale
[pic] [pic]
a) Calculez la solution optimale et la valeur optimale du problème.
b) Calculez et interprétez le prix dual de la contrainte (2).
DS7) Soit le problème de programmation linéaire
max z = 30 x1 + 20x2
[pic]
a) Résolvez le problème graphiquement.
b) Sur base de a), déterminez la base optimale B.
c) Pourrait-on déduire les prix duaux sur base de cette
information? DS8) Soit le problème de programmation linéaire (P):
min z = 500x1 + 500x2 + 500x3 + 300x4 + 425x5
[pic]
A l'optimum de (P), on a x1 = x2 = x3 = x5 = 0
a) Trouvez la solution optimale et la matrice de base optimale pour
(P).
b) A partir de la matrice de base, calculez la valeur optimale des
variables duales.
c) Ecrivez le problème dual de (P).
DS9) Soit le problème de programmation linéaire
max z = 4x1 + 5x2 + 6x3
[pic]
a) Formulez le dual et résolvez-le (par inspection)
b) Utilisez a) et le théorème de dualité forte pour résoudre le
primal.
DS10) Soit le problème de programmation linéaire:
min z = 2x1 + 3x2
[pic] Son dual s'écrit
max w = 30y1 + 10y2
[pic]
Déterminez si les solutions suivantes sont réalisables et optimales:
a) ( x1 = 10, x2 = 10/3; y1 = 0, y2 = 1, y3 = 1)
b) (x1 = 20, x2 = 10; y1 = 1, y2 = 4, y3 = 0)
c) (x1 = 10/3, x2 = 10/3; y1 = 0, y2 = 5/3, y3 = 1/3)
DS11) Considérons le programme linéaire suivant max z = 5x1 + 2x2 + 3x3
[pic] La solution optimale est donnée par le dictionnaire final
max z [pic] a) Ecrivez le problème dual associé.
b) Déterminez la matrice de base optimale B. Déduisez-en la solution
optimale du dual.
c) Dans quel intervalle peut varier c1 (idem c2, c3) sans affecter
l'optimalité de la solution?
d) Dans quel intervalle peut varier b1 (idem b2) sans affecter
l'optimalité de la base B?
e) Déterminez les prix duaux.
DS12) Considérons le problème de l'exercice DS11.
a) Supposons que le M. de D. des contraintes devienne (30 + (, 40 -
(), où ( est un paramètre non négatif. Déterminez les valeurs de (
pour lesquelles la base B reste optimale.
b) Pour chacune des fonctions objectif suivantes, trouvez la nouvelle
solution optimale en utilisant la procédure d'analyse de
sensibilité.
i) max z = 12x1 + 5x2 + 2x3
ii) min z = 2x2 - 5x3
DS13) Voici la formulation d'un petit problème de transport impliquant 3
entrepôts et 2 clients: min z = 3x11 + 2x12 + 4x21 + x22 + 2x31 + 3x32 [pic] (remarquez que le problème est non équilibré). Ce problème a été mis sous forme standard en introduisant des
variables d'écart s1 , s2 et s3 dans les trois premières contraintes,
puis résolu par un logiciel utilisant la méthode du simplexe. Voici
quelques informations sur la solution optimale:
1. les variables en base à l'optimum sont x11, x12, x22, x31 et s1;
2. le coût réduit de x21 et celui de x32 sont égaux à 2;
3. les prix duaux des contraintes sont donnés par (y1, y2, y3, y4, y5)
= (0, -1, -1, 3, 2).
a) Mettez le problème sous forme standard (comme suggéré ci-dessus)
et formulez son problème dual.
b) Utilisez l'information donnée plus haut pour calculer la
solution optimale du problème et le coût de transport
correspondant.
c) Si le coût unitaire de transport entre l'entrepôt 2 et le client
1 diminuait de 1 unité (passant ainsi de 4 à 3), quelle serait
l'incidence de ce changement sur la solution optimale et la valeur
optimale calculées précédemment?
d) Le gestionnaire du troisième entrepôt s'aperçoit qu'il a commis
une erreur en évaluant ses stocks: il possède en fait 55 unités en
stock. En supposant que la base optimale ne soit pas affectée, quel
sera l'effet de cette correction sur le coût de transport optimal?
Files d'attente
F1) Le responsable d'un parking du centre-ville a compté le nombre de
voitures garées dans son parking à différents instants de la journée.
En moyenne, il en a trouv