Recherche Opérationnelle
Corrigé TD1
Corrigé Ex. 1.
Les variables de décision sont :
x1 : quantité de fourgons à fabriquer/semaine;
x2 : quantité de plateaux à fabriquer/semaine.
Le tableau suivant donne la consommation en temps pour la fabrication d'un fourgons et d'un
plateau :
moyen ↓ type →
fourgon plateau
mécanique 5 10
tôlerie 12 0
sellerie 0 12
peinture 10 5
Le problème est de déterminer les la quantité à fabriquer (pour maximiser le bénéfice) sous
les contraintes suivantes :
5x1 + 10x2 ≤ 60
12x1 ≤ 60
12x2 ≤ 60
10x1 + 5x2 ≤ 60
où x1 et x2 les variables de décision qui désignent les quantités à fabr iquer pour les fourgons et
les plateaux.
Le bénéfice à maximiser est : z = f(x 1 , x2 ) = max 5000(x 1 + x2 )
Le problème peut être mis sous forme matricielle :
Maximiser z = c Tx=(5000 5000) T (x1 x2 )
sous les contraintes Ax ≤ b
5 10 60
12 0 x1 60
0 12 x ≤ 60 et (x1 x2 ) ≥ 0
2
10 5 60
La solution optimale est x1 = 4, x 2 = 4 et z = 40000
Corrigé Ex. 2.
Pour la contrainte x1 + 2x2 - 3x3 = 1, on la remplace par les deux contraintes suivantes :
x1 + 2x2 - 3x3 ≤ 1
-x1 - 2x2 + 3x3 ≤ -1
Pour la contrainte x1 + 3x2 - x3 ≥ 1, on la remplace par la contrainte suivante :
-x1 - 3x2 + x3 ≤ -1
On met le programme linéaire suivant sous forme canonique :
Maximiser z =c Tx = (1 2 3) T (x1 x2 x3 )
sous les contraintes suivantes
1
1 2 − 3 1
x1
− 1 − 2 3 − 1
2 − 1 − 5 x 2 ≤ 2 (x1 x2 x3 ) ≥0
− 1 − 3 1 x 3 − 1
Corrigé Ex. 3.
Pour ce problème, les variables de décisions sont les suivantes :
x1 : le nombre d'heures par semaine consacrées à la fabrication des tarots;
x2 : le nombre d'heures par semaine consacrées à la fabrication des 7 familles;
x3 : le nombre d'heures par semaine consacrées à la fabrication des 32 cartes.
Le problème est de maximiser le profit de l'entreprise :
Maximiser z = 4,8×25x 1 + 1,6×50x 2 + 1,2×75x 3 = 120x 1 + 80x 2 + 90x3
Les contraintes sont les suivantes :
x1 +x2 +x3 ≤ 45 (1)
25x1 ≤ 500 (2)
50x2 ≤ 1000 (3)
75x3 ≤ 1500 (4)
25x1 + 0,5×50x 2 + 75x3 ≤ 2000 (5)
xi ≥ 0 pour i = 1, 2, 3 (6)
où
(1) la contrainte sur les heures disponibles par semaine pour fabriquer l'ensemble des cartes;
(2), (3) et (4) la quantité de tarots (resp. des 7 familles, des 32 cartes) fabriquée ne doit pas
être supérieurs à la demande du marché;
(5) supposons que la surface de stockage est 2000 unités, alors un jeu de tarot prend une unité
de place, un jeu de 7 familles prend 0,5 place et un jeu de 32 cartes prend une unité de place.
Dans ce cas, la fabrication totale ne doit pas dépasser 2000 unités.
On peut aussi modéliser ce problème en utilisant d’autres variables de décisions.
Pour ce problème, les variables de décisions sont les suivantes :
x1 : le nombre de jeux de tarots fabriqués par semaine;
x2 : le nombre de jeux de 7 familles fabriqués par semaine;
x3 : le nombre de jeu de 32 cartes fabriqués par semaine.
Le problème est de maximiser le profit de l'entreprise :
Maximiser z = 4,8x 1 + 1,6x2 + 1,2x 3
Les contraintes sont les suivantes :
3x1 +1,5x2 +x3 ≤ 3375 (1)
x1 ≤ 500 (2)
x2 ≤ 1000 (3)
x3 ≤ 1500 (4)
2x1 + x2 + 2x3 ≤ 4000 (5)
xi ≥ 0 pour i = 1, 2, 3 (6)
Ces deux problèmes sont équivalents.
2
Corrigé Ex. 4.
Pour ce problème, les variables de décision sont les suivantes :
Pour la site de Quimper :
x1 : la quantité à expédier à Paris par semaine;
x2 : la quantité à expédier à Rouen par semaine;
x3 : la quantité à expédier à Bordeaux par semaine.
Pour la site à Vanne, alors :
x4 : la quantité à expédier à Paris par semaine;
x5 : la quantité à expédier à Rouen par semaine;
x6 : la quantité à expédier à Bordeaux par semaine.
Le problème est de minimiser le coût de transport :
Minimiser z = c Tx = 25x 1 + 17x2 + 18x 3 + 25x4 + 18x5 + 14x 6
Les contraintes sont les suivantes :
x1 + x2 + x3 ≤ 350 (1)
x4 + x5 + x6 ≤ 650 (2)
x1 + x4 ≥ 300 (3)
x2 + x5 ≥ 300 (4)
x3 + x6 ≥ 300 (5)
xi ≥ 0 pour i = 1, 2, 3, 4, 5, 6 (6)
Corrigé Ex .5.
Les variables de décision sont les suivantes :
xA: la quantité de X à acheter pour fabriquer le produit A ;
yA: la quantité de Y à acheter pour fabriquer le produit A ;
zA : la quantité de Z à acheter pour fabriquer le produit A ;
xB : la quantité de X à acheter pour fabriquer le produit B;
yB : la quantité de Y à acheter pour fabriquer le produit B ;
zB : la quantité de Z à acheter pour fabriquer le produit B ;
xC: la quantité de X à acheter pour fabriquer le produit C ;
yC: la quantité de Y à acheter pour fabriquer le produit C ;
zC: la quantité de Z à acheter pour fabriquer le produit C ;
Le problème consiste à maximiser le bénéfice de l'entreprise :
Maximiser z =[68(x A + y A + z A) + 57(x B + y B + zB ) + 45(x C +yC + zC)] - [70(x A + x B + x C)+
50(y A + yB + yC) + 40(z A + z B + zC )]
3
Les contraintes sont les suivantes :
xA + xB + xC ≤ 2000 (1)
yA + yB + yC ≤ 2500 (2)
zA + zB + zC ≤ 1200 (3)
xA
≥ 0,6 ⇒ -0,4x A + 0,6y A+ 0,6z A ≤ 0 (4)
xA + yA + z A
zA
≤ 0, 2 ⇒ -0,2x A - 0,2y A + 0,8z A ≤ 0 (5)
xA + yA + z A
xB
≥ 0,15 ⇒ -0,85x B + 0,15y B + 0,15zB ≤ 0 (6)
x B + y B + zB
zB
≤ 0,6 ⇒ -0,6x B -0,6y B + 0,4zB ≤ 0 (7)
xB + yB + z B
zC
≤ 0,5 ⇒ -0,5x C -0,5y C + 0,5zC ≤ 0 (8)
xC + yC + zC
xi ≥ 0 pour i = A, B, C (9)
yi ≥ 0 pour i = A, B, C (10)
zi ≥ 0 pour i = A, B, C (11)
où les contraintes (1) -(3) sont les contraintes d'achat;
les contraintes (4)-(8) sont les contraintes sur les compositions;
les contraintes (9)-(11) sont les contraintes de positivité.
