RCP101 – Examen Février 2013(Corrigé)

RCP101 – Recherche Opérationnelle et Aide à la Décision

Exercice I (2,5 pts)

�����maximiser � 100��souslescontraintes ��

Remarque : en toute rigueur, il faudr

fractionnaire de téléviseur n’a pas de sens). On aboutirait alors non pas à un programme

linéaire, mais un PLNE (programme linéaire en nombres entiers).

Exercice II (9 pts)

1) Le PL n’a que des contraintes du type

naturellement une base de départ réalisable pour (

nécessaire d’écrire ni de résoudre un programme auxiliaire. Avec les va

Le premier tableau du simplexe

B ��← ��� 0��� 0

�� Δ

2) La base n’est pas optimale car

• !" entre en base (plus grand coût réduit)

• Min$%&' , ��&) * � %&' , obtenu pour la ligne de

On pivote alors autour de l’élément

combinaisons linéaires qui permettent que la nouvelle colonne de

colonne de ���.

D’où le deuxième tableau du simplexe

1 Pour toute question concernant ce corrigé

Recherche Opérationnelle et Aide à la Décision

Examen du 9 février 2013

Corrigé indicatif1

� + 70����1,2�� + �� . 7/tempsdetravail�� 3 20 /productionminimale�� 3 10 /productionminimale120�� + 60�� . 6500/budgetmaxpiècesdétachées��, �� 3 0

en toute rigueur, il faudrait imposer aux variables x1 et x2 d’être entières (produire un nombre

fractionnaire de téléviseur n’a pas de sens). On aboutirait alors non pas à un programme

linéaire, mais un PLNE (programme linéaire en nombres entiers).

que des contraintes du type ≤. On introduit donc des variables d’écart qui vont former

naturellement une base de départ réalisable pour (P). Il n’y a donc pas de phase 1

nécessaire d’écrire ni de résoudre un programme auxiliaire. Avec les variables d’écart, (

; maximiser � 6�� + 10��s.c. =2�� + 4�� + ��� � 803�� + 5�� + ��� � 110��, ��, ���, ��� 3 0 AA

premier tableau du simplexe s’écrit alors :

� �� �� ��� ��� BC

0 2 4 1 0 80 D�

0 3 5 0 1 110 D�

� 6 10 0 0 Δ 6 10 0 0 Z=0 DE

↑

La base n’est pas optimale car Δ n’est pas . 0. On effectue une itération de l’algorithme du simplexe

(plus grand coût réduit)

, obtenu pour la ligne de ��� : !G� sort de la base.

élément 4 du tableau (ligne 1, colonne2), c’est-

combinaisons linéaires qui permettent que la nouvelle colonne de �� corresponde à l’ancienne

deuxième tableau du simplexe :

Pour toute question concernant ce corrigé : eric.soutif@gmail.com

1

Recherche Opérationnelle et Aide à la Décision

tempsdetravailHproductionminimaletéléviseursHproductionminimalemachinesHpiècesdétachéesHAA

d’être entières (produire un nombre

fractionnaire de téléviseur n’a pas de sens). On aboutirait alors non pas à un programme

≤. On introduit donc des variables d’écart qui vont former

). Il n’y a donc pas de phase 1 : il n’est pas

riables d’écart, (P) devient :

AA

. On effectue une itération de l’algorithme du simplexe :

-à-dire qu’on effectue les

corresponde à l’ancienne

RCP101 – Examen Février 2013(Corrigé)

B �� �� 10 ��� 0

��

Δ

3) a) La base est optimale car

base associée est donc la solution optimale du problème. !∗ � /"J, GJH. ��∗ � 20, b) Il existe une variable hors

n’est pas unique (on dit qu’il s’adit d’une solution dual

sortira et Z restera à la vale

c) On doit recalculer les coûts réduits des variables hors

restent négatifs ou nuls, la solution reste optimale.

Or Δ�� � 0 K $ 6GG* LK5/3/2 Et Δ�� � 0 K $ 6GG* $ 2K1* Les coûts réduits restent négatifs ou nuls, par conséquent la solution de la question (a) reste

optimale.

4) Le problème dual (D) de (P) est

/5) ���hors-basedans/OH ⇒ Q�enbasedans

���hors-basedans/OH ⇒ Q�enbasedansB Q� Q� -

6) Recalculons les coûts réduits duaux. Attention, les coûts initiaux

80 pour c1 et -100 (au lieu de

�� � 0 K $ K80KGJJ*$5/2K2* � 0

�� �� ��� ��� BC

1/2 1 1/4 0 20 D�R � �'D�1/2 0 -5/4 1 10 D�R � D�6 10 0 0

1 0 -5/2 0 -200

(Z=200) DER � DE

La base est optimale car Δ . 0 (dans le tableau obtenu après plusieurs itérations)

base associée est donc la solution optimale du problème. L’optimum du PL de départ est donc , ��∗ � 10, ���∗ � ���∗ � 0H.La valeur optimale est

Il existe une variable hors-base de coût réduit nul : Δ�� � 0. Par conséquent la solution optimale

n’est pas unique (on dit qu’il s’adit d’une solution dual-dégénérée) : si

sortira et Z restera à la valeur 220.

On doit recalculer les coûts réduits des variables hors-base avec la nouvelle valeur de c

restent négatifs ou nuls, la solution reste optimale. L /22 S � 15 K EE� � K E� . J

* � K12 + 11 � K1 . J

s restent négatifs ou nuls, par conséquent la solution de la question (a) reste

) est :

/TH;minimiser R � 80Q� + 110Q�

s.c. = 2Q� + 3Q� 3 64Q� + 5Q� 3 10Q�, Q� 3 0 A A enbasedans/TH enbasedans/TH �� Q� Q� Q�� Q�� BC

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

-110 0 1 -2 1 2 �� -80 -110 0 0 Δ 0 0 -20 -10

-Z’=-220

(Z’=220)

Recalculons les coûts réduits duaux. Attention, les coûts initiaux �� sont ceux de la fonction

100 (au lieu de -110) pour c2.

* 0 + 200 K 200 � 0 . J

2

� K 5/4D�

K �&' D�

(dans le tableau obtenu après plusieurs itérations). La solution de

du PL de départ est donc

est U∗ � ""J.

. Par conséquent la solution optimale

: si ��� entre en base, x2 en

base avec la nouvelle valeur de c2. S’ils

s restent négatifs ou nuls, par conséquent la solution de la question (a) reste

A

C

220

sont ceux de la fonction –Z’ donc -

RCP101 – Examen Février 2013(Corrigé)

Δ�� � 0 K $ K80KGJJ*$K3/21 * � Les coûts réduits duaux restent négatifs ou nuls. La solution duale reste optimale et la base prim

reste également optimale. Par conséquent la solution optimale du primal reste inchangée�∗ � /20, 10H, de valeur 220.

Exercice III (4,5 pts)

1) M/M/2/3

2) Il y a 4 états possibles correspondant au fait que 0, 1, 2 ou 3 personnes sont présentent dans le

système d’attente.

3) En appliquant le théorème des coupes, on obtient successivement

• V&W � V�X soit : V� � YZ• V�W � V� [ 2X soit : V�• V�W � VE [ 2X soit : VE• Et de façon générale : V\

4) W � 12arrivées/h et X � 10

a) V& + V� + V� + VE � 1. On en déduit

V&b) ]C � ∑ _ [ V� �\�`& 0 [ V&

Or V&Ka0,30, V� � YZ V&KaAinsi, le nombre moyen de clients dans l’organisme est

* � K120 + 100 � K20 . J

Les coûts réduits duaux restent négatifs ou nuls. La solution duale reste optimale et la base prim

reste également optimale. Par conséquent la solution optimale du primal reste inchangée

, de valeur 220.

Il y a 4 états possibles correspondant au fait que 0, 1, 2 ou 3 personnes sont présentent dans le

En appliquant le théorème des coupes, on obtient successivement : YZ V&

� � Y²�Z²V&

E � Yc�dZc V&

\ � Ye�efgZe V&, pour ] 3 1.

services/h. Donc YZ � 1,2.

. On en déduit V& :

V& h1 + WX + W²2X² + WE2�XEi � 1

& � 11 + 1,2 + 0,5 [ 1,2² + 0,25 [ 1,2EKa0,30

& + 1 [ V� + 2 [ V� + 3 [ VE

Ka0,36, V� � Y²�Z²V&Ka0,21, et VE � Yc�dZc V&Ka0,13Ainsi, le nombre moyen de clients dans l’organisme est : ]C � ∑ _ [ V�\�`& K

3

Les coûts réduits duaux restent négatifs ou nuls. La solution duale reste optimale et la base primale

reste également optimale. Par conséquent la solution optimale du primal reste inchangée :

Il y a 4 états possibles correspondant au fait que 0, 1, 2 ou 3 personnes sont présentent dans le

13.

Ka1,17.

RCP101 – Examen Février 2013(Corrigé)

Exercice IV (4 pts)

1) et 2) a) Graphe PERT :

• La tâche fictive j�est nécessaire pour matérialiser l’attente de 2 jours après la fin de a et b avant de

commencer d.

• j� est nécessaire car E1 a plusieurs successeurs et

terminée avant le début de d (après l’attente de 2 jours).

• jE est nécessaire car E1 a plusieurs successeurs et

2) a) C.f. graphe PERT. Durée minimale du projet : 14 j

b) Marge totale de la tâche (

Tâche

Marge totale

c) Les tâches critiques sont a et d (de marge totale nulle). Remarque

également critique.

est nécessaire pour matérialiser l’attente de 2 jours après la fin de a et b avant de

a plusieurs successeurs et j� sert à représenter le fait que b doit être

terminée avant le début de d (après l’attente de 2 jours).

a plusieurs successeurs et jE sert à représenter le fait que b précède e.

Durée minimale du projet : 14 jours (date au plus tôt de l’évènement fin).

Marge totale de la tâche (i,j) : k�,� � l�∗ K m�� K l� a b c d e

Marge totale 0 3 3 0 3

Les tâches critiques sont a et d (de marge totale nulle). Remarque :

4

est nécessaire pour matérialiser l’attente de 2 jours après la fin de a et b avant de

sert à représenter le fait que b doit être

sert à représenter le fait que b précède e.

ours (date au plus tôt de l’évènement fin).

: la tâche fictive j� est