GINF1/GSTR1

Matière : RO
Année 2019/2020

I. Problèmes Linéaires

Exercice 1 :

Résoudre par la méthode du simplexe le programme linéaire suivant :

⎧ Maximiser z = 8x1 +8 x 2 + 47 x 3
⎪
⎪ sous les contraintes :
⎪
⎨ 4x1 + x 2 + 7 x 3 ≤ 2
⎪ x + 4 x + 10 x ≤ 3
⎪ 1 2 3

⎪⎩ x1 ≥ 0 , x 2 ≥ 0 , x 3 ≥ 0

Retrouver le résultat par Matlab

Exercice 2 :

Trois personnes P1, P2 et P3 sont associées dans une entreprise de terrassement. Les travaux nécessitent
l'utilisation complémentaire de 3 engins. Chacun des 3 associés est spécialisé dans la conduite d'un de ces
engins. La pénibilité de leur travail est différente et ils ne peuvent donc travailler le même nombre
d'heures par jour. Un mois de travail est constitué respectivement pour chacun d'entre eux de 141,160 et
181 heures. Les différents travaux qu'ils peuvent effectuer sont de trois types T1, T2, T3. Le nombre
d'heures de travail nécessaires pour la réalisation de chacun de ces types de travaux est donné dans le
tableau ci-dessous :

P1 P2 P3
T1 3 4 5
T2 2 2 3
T3 3 2 2
Les travaux T1, T2, T3 procurent une marge bénéficiaire de 200, 120 et 100 $.On note par x1, x2, x3 le
nombre de travaux de chaque type T1, T2, T3, qu'ils doivent effectuer mensuellement pour maximiser leur
bénéfice.

1. Ecrire le programme linéaire que les 3 associés sont amenés à résoudre.

2. Quel sera le bénéfice mensuel de leur entreprise ?
3. Quel est l'associé qui aura du temps libre pour s'occuper des taches de gestion ?
4. Si la personne P3 devait s'absenter 1 heure pendant le mois, quelle conséquence cela aurait-il sur le
bénéfice optimal ?
5. Donner le problème dual de 1).
6. En déduire la solution optimale du dual à partir du tableau optimal du primal.
Exercice 3 : Soit le programme linéaire suivant :

Minimiser z = 2x1 + x2 +35x3

sous les contraintes :
4 x1 -2 x2- 6x3 ≥ 1
-3 x1 + x2+14x3 ≥ 2
x1 ≥ 0 , x2 ≥ 0, x3 ≥ 0

1. Donner le programme dual (PL)* de (PL).

2. Résoudre (PL)* par la méthode du simplexe.
3. En déduire le tableau optimal du (PL).

Exercice 4 :

Résoudre par la méthode de séparation & évaluation, le problème linéaire en nombre entier
suivant :

Exercice 5 :

Le directeur financier d’une société décide d’investir une somme de 100 unités de manière à
maximiser le revenu. Il considère les possibilités suivantes :

Type d’investissement : A1 A2 B1 B2 C1 C2
Intérêts : 6% 5% 7% 8% 10% 9%

Au moins 40% de la somme totale doit être investie en valeur de type A et au plus 35% dans l’un
quelconque des deux autres types.

1. Ecrire la formulation mathématique du problème.

2. Résoudre le problème à l’aide de l’algorithme du simplexe.
Exercice 6 :

Dans une entreprise de transport, les demandes journalières en chauffeur sont présentées par le
tableau suivant :
Lu Ma Me Je Ve Sa Di
13 18 21 16 12 25 9

Les chauffeurs travaillent 5 jours d’affilée ( peuvent avoir leurs deux jours de congé n’importe quand
dans la semaine ).

Déterminer les effectifs formant les sept équipes possible de chauffeurs de manière à :

1. Couvrir tous les besoins

2. Engager un nombre minimum de chauffeurs.

Exercice 7 :

Une compagnie doit transporter du gravier vers trois sites de construction, S1, S2 et S3 ; La compagnie
achète ce gravier de deux fournisseurs F1 et F2. La compagnie devra louer des camions pour assurer le
transport du gravier des fournisseurs vers les sites de construction. Chaque camion coûte 50€ et peut
transporter jusqu’à 5 tonnes du gravier.

Les autres données du problème sont représentées dans le tableau suivant, qui indique :

• Pour chaque site de construction et chaque fournisseur, le prix (en €) de chargement par tonne
• Pour chaque fournisseur, l’offre, soit le nombre de tonnes de gravier disponibles
• Pour site de construction, la demande, soit le nombre de tonnes de gravier demandées.

Sites S1 S2 S3 Offre
Fournisseurs (tonnes)
F1 130 160 150 18
F2 180 150 160 14
Demandes 10 5 10
(tonnes)

Le problème consiste à minimiser le coût total afin de transporter le gravier des fournisseurs vers les sites
de construction.
On note par :

le nombre de tonnes de gravier transportées entre le fournisseur et le site

le nombre de camions utilisés pour transporter du gravier entre le fournisseur et le site

1. Modéliser le problème sous forme d’un PL en nombres entiers (en fonction de

2. Utiliser la méthode de séparation et évaluation pour trouver la solution du problème.

 II. Problèmes non linéaires

Exercice 8 :

Un atelier peut fabriquer des articles de deux types A1 et A2, sur une machine donnée, disponible 100
heures par mois compte tenu des heures de réglage et d’entretien. Les articles de type A1 sont fabriqués à
la cadence de 50 articles par heures, et les articles de type A2 sont fabriqués à la cadence de 25 articles par
heure .La capacité d’absorption du marché étant limitée, on ne peut écouler par mois plus de 3000 articles
de types A1, ni plus de 2000 articles de types A2. En raison d’un système de prix dégressifs consentis aux
clients, le prix de chaque article décroît légèrement avec la quantité vendue: ainsi, un article de type A1
rapporte 30(1- x1/6000) dh lorsqu’on en vend x1 , et un article de type A2 rapporte 20(1- x2 /4000) dh
lorsqu’on en vend x2 .
Montrer que le problème de l’atelier peut être mis sous la forme d’un programme non linéaire (PNL) puis
donner la solution optimale par Matlab.

Exercice 9 :

Une entreprise spécialisée en télécommunication voudrait installer une antenne pour connecter 4
nouveaux clients importants.
Cette antenne doit se trouver au plus proche de chaque client, en donnant priorité aux meilleurs
clients.
Pour chaque client l’entreprise connait, selon le graphe suivant :
ü Sa localisation (coordonnées (x,y))
ü Le nombre d’heures de communication par mois

(0 ; 12)

200h (5 ; 10)

200h

Antenne (x,y) * 150h (10 ;5)

300h

(12 ;0)

1. Modéliser ce problème sous forme d’un programme non linéaire sans contraintes.
2. Donner la solution par Matlab.

Supposons que l’entreprise veut installer une troisième antenne par rapport aux deux autres déjà installées
dans les positions (-5 ;10) et (5 ;0).
On interdit le placement de cette troisième antenne à moins de 10 km des antennes existantes.
3. Montrer que le nouveau problème se modélise sous forme d’un programme non linéaire sous
contraintes inégalités (P).
4. Trouver la solution par Matlab.