EN SI 2012/2013

Classe I.I.1: Recherche Opérationnelle.

Série Programmation Linéaire

Exercice 1
Une personne a la possibilité de vendre: - 500 cartes postales,
- 20 guides touristiques.
Elle constitue deux lots publicitaires:
- Lot n 1 = un guide et 10 cartes postales,
- Lot n 2 = un guide et 50 cartes postales.
Son béné…ce unitaire est fonction du lot vendu, il est de 6 francs par lot n 1
et de 10 francs par lot n 2:
1) Formuler un modèle donnant un plan qui maximise le béné…ce total.
2) Mettre le modèle obtenu sous forme standard.
Exercice 2
Un atelier peut fabriquer trois types d’articles:
- Article A1 à la cadence de 35 pièces à l’heure
- Article A2 à la cadence de 45 pièces à l’heure
- Article A1 à la cadence de 20 pièces à l’heure
Cette fabrication utilise une machine-outil unique, disponible 200 heures par
mois. Le béné…ce unitaire pour l’article A1 est de 60 dinars, pour A2 est de
40 dinars et pour A3 est de 80 dinars.
Ces articles sont vendus en totalité à des grossiste. On a observé qu’on
ne pouvait écouler, par mois, plus de 4900 pièces de types A1 ;ni plus de
5400 pièces du type A2 ;ni plus de 2000 pièces du type A3 . D’autre part,
chaque pièce doit être véri…ée avant sa commercialisation. Une équipe de
trois techniciens est chargée de cette mission. Chaque technicien travaille
170 heures par mois. La véri…cation d’une pièce du type A1 prend 4 minutes,
du type A2 prend 3 minutes et du type A3 prend 2 minutes.
1) Formuler un modèle donnant un plan de production qui maximise le pro…t
de l’entreprise.
2) Mettre le modèle obtenu sous forme standard.
Exercice 3
On désire déterminer la composition, à coût minimal, d’un aliment pour bé-
tail qui est obtenu en mélangeant au plus trois produits bruts: orge, arachide
et sésame. L’aliment ainsi conditionné devra comporter au moins 22% de pro-
téines et 3; 6% de graisses, pour se conformer aux exigences de la clientele.

1
Dans le tableau ci-dessous, on indique les pourcentages de protéines et de
graisses contenus, respectivement, dans l’orge, les arachides et le sésame,
ainsi que le coût par tonne de chacun des produits bruts:

produit brut orge arachides sésame

pourcentage de protéines 12% 52% 42%
pourcentage de graisses 2% 2% 10%
coût par tonne 25 41 39

1) A…n de déterminer la composition, à coût minimal, d’un tonne d’aliment

conforme aux exigences de la clientèle, donner une formulation du problème
posé sous forme d’un programme linéaire.
Exercice 4
Une compagnie X s’est vue attribuer la tâche de préparer un portefeuille
d’investissement pour une socièté industrielle. Les fonds disponibles représen-
tent un montant de 250 000 dolars. L’analyse …nancier de la compagnie à
retenu 6 possibilités d’investissements réparties dans l’industrie du pétrole,
l’industrie de l’électronique et l’industrie pharmaceutique. Les diverses so-
ciétés dans les quelles on désire investir et les rendements anticipés sont
présentés dans le tableau ci-après.

Société Secteur d’activités Rendement anticipé (%)

Simco Pétrole 09; 35
Plurimax Pétrole 08; 00
Microtel Electronique 10; 90
CAX Electronique Electronique 07; 80
Biomed pharmaceutique 09; 60
Cronex pharmaceutique 08; 50

Les directives suivante ont été émises:

1. Les investissements dans le secteur pharmaceutique devrait représenter
au moins 30% des investissements dans le secteur électronique.
2. Aucun secteur d’activités ne devrait se voir allouer plus de 55% des fonds
disponibles.
3. Bien que la société électronique Microtel présente un rendement anticipé
élevé, on veut limiter le montant investi dans cette société, à cause de son
risque élevé, à 60% des investissements dans le secteur électronique.

2
4. On a demandé également à la compagnie X d’investir au moins 15 000
dolars dans l’industrie pétrolière.
L’objectif de l’analyste …nancier de la compagnie X est de maximiser le ren-
dement anticipé.
Formuler le modèle de programmation linéaire qui permettrait à l’analyste
…nancier de lui suggérer une stratégie de placement tout en respectant les
directives mentionnées.
Exercice 5
Une importante entreprise d’appareils électroniques dispose de trois usines à
di¤érents endroits au pays. La production annuelle de chaque unsine pour
un certain type d’appareils est la suvante:

Usine Production annuelle

U-1 15 000 unités
U-2 12 000 unités
U-3 23 000 unités

Ces usines alimentent quatre points de vente dont la demande annuelle est
la suivante:

Points de vente Demande annuelle

A 10 000 unités
B 5 000 unités
C 20 000 unités
D 15 000 unités

Les coûts unitaires de transport de chaque usine à chaque point de vente sont
indiqués dans le tableau suivant:

A B C D
U-1 5 6 6 8
U-2 11 9 4 7
U-3 12 7 8 5

Formuler le modèle de programmation linéaire qui permettrait d’obtenir un

plan de transport à coût minimum.

3
Exercice 6
On considère le programme linéaire suivant:
8
>
> M ax z = 5x1 + x2 + 6x3 + 24x4
>
>
< Sous-Contraintes:
(P L) 4x1 + 4x2 + 4x3 + x4 24
>
>
>
> 8x1 + 6x2 + 4x3 + 3x4 36
:
xj 0; j = 1; :::; 4

a- Ecrire (P L) sous forme standard, les variables d’écart seront nomées x5

et x6 :
b- soit B = (A3 ; A4 ): Cette base est-elle réalisable? est-elle optimale?
Exercice 7
On considère les programmes linéaires suivants:
8
> M ax z = 2x1 + x2 + x3
>
>
>
> Sous-Contraintes:
>
<
2x1 + x2 + x3 2
(P L) (P L)
>
> x 1 + x2 10
>
>
>
> 2x + 4x2 + x3 8
: 1
8 xj 0; j = 1; :::; 3
>
> max z = 3x1 + 4x2 + x3
>
>
< Sous-Contraintes :
x1 + 2x2 + 2x3 83
>
>
>
> x1 + 2x2 + 3x3 73
:
xj 0; j = 1; 2; 3

a- Ecrire (P L) sous forme standard.

b- Ce problème admet-il une solution initiale évidente? justi…er votre réponse.
Exercice 8
On considère le programme linéaire suivant:
8
>
> M ax z = 25x1 + 15x2
>
>
< Sous-Contraintes:
P.L 2x1 + 2x2 240
>
>
>
> 3x1 + x2 140
:
xj 0; j = 1; 2

4
a- Représenter l’ensemble des solutions admissibles.
b- Localiser toutes les solutions de base réalisables.
c- Calculer la valeur de la fonction coût Z en chacun de ces points et donner
la solution optimale.
d- E¤ectuer une résolution graphique de ce problème.
Exercice 9
On considère le programme linéaire suivant:
8
>
> M in z = x2 x1
>
>
>
> Sous Contraintes :
<
2x1 x2 2
(P L)
>
> x 1 x 2 2
>
>
>
> x 1 + x 2 5
:
xj 0; j = 1; :::; 2

a- Représenter l’ensemble des solutions admissibles.

b- Localiser toutes les solutions de base réalisables.
c-Calculer la valeur de la fonction coût Z en chacun de ces points et donner
la solution optimale.
d- Déterminer graphiquement l’ensemble des solutions optimales.
Exercice 10
On considère le programme linéaire suivant:
8
>
> max z = 3x1 + 2x2 + 5x3
>
>
>
> Sous Contraintes:
<
x1 + 2x2 + x3 + x4 = 430
(P:L)
>
> 3x1 + 2x3 + x5 = 460
>
>
>
> x + 4x2 + x6 = 420
: 1
xj > 0; j = 1; ::::; 6

1) Montrer que la solution : X = (0; 0; 230; 200; 0; 420) est une solution de
base réalisable du programme linéaire (P:L).
2) Donner le tableau du simplexe correspondant à cette solution de base.
3) Le tableau obtenu est-il optimal? Justi…er votre réponse.
Exercice 11:
On considère le programme linéaire suivant:

5
 8
>
> max z = 15x1 + 40x2 + 12x3
>
>
< Sous-Contraintes :
(P L) 6x1 + 10x2 + 2x3 60
>
>
>
> 2x1 + 10x2 + 6x3 140
:
xj 0; j = 1; 2; 3

Résoudre le programme linéaire à l’aide de la méthode des tableaux du sim-

plexe.
Exercice 12 :
On considère le programme linéaire suivant:
8
>
> max z = 2x1 x2
>
>
>
> Sous-Contraintes :
<
3x1 + x2 = 3
(P L)
>
> 4x1 + 3x2 6
>
>
>
> x + 2x2 3
: 1
xj 0; j = 1; 2

1) Résoudre ce programme linéaire à l’aide de la méthode des deux phases.

2) Donner une résolution graphique de (LP ) dans le plan (x1 ; x2 ). Décrire,
dans ce plan, le cheminement qui correspond à l’application de la méthode
du simplexe.
Exercice 13 :
On considère le programme linéaire suivant:
8
>
> max z = x1 + 2x2
>
>
>
> Sous-Contraintes :
<
2x1 + x2 2
(P L)
>
> x 1 + 2x2 5
>
>
>
> x 4x2 4
: 1
xj 0; j = 1; 2

1) Tenter de résoudre ce programme linéaire à l’aide de la méthode du sim-

plexe.
2) Faire une résolution graphique.

6
 Exercice 14:
Donner le programme dual de chaque programme linéaire.
8 8
>
> Max z = 15x 1 + 40x 2 + 12x 3 >
> Max z = 4x1 + 5x2 + 9x3
>
> >
>
< Sous-Contraintes: < Sous-Contraintes:
P1 6x1 + 10x2 + 2x3 + x4 = 60 P2 x1 + x2 + 2x3 = 16
>
> >
>
>
> 2x 1 + 10x 2 + 6x 3 + x 5 = 140 >
> 7x1 + 5x2 + 3x3 25
: :
xj 0; j = 1; :::; 5 xj 0; j = 1; :::; 3
Exercice 15:
Résoudre, à l’aide de l’algorithme dual simplexe, le programme linéaire su-
vant:

8
>
> Min z = x1 + 2x2 + 3x3
>
>
< Sous-Contraintes:
(P L) x1 + 3x2 + 5x3 6
>
>
>
> 5x x2 + 2x3 4
: 1
xj 0; j = 1; 2; 3

Exercice 16:
On considère le programme linéaire suivant:

8
>
> M in z = 2x1 + 3x2
>
>
>
> Sous Contraintes :
<
4x1 + x2 8
(P:L)
>
> x1 + 4x2 8
>
>
>
> 7x1 + 10x2 47
:
xj 0; j = 1; 2;

1- Donner le programme dual de P.L.

2- Donner une solution initiale évidente du programme dual.
3- Résoudre le programme dual à l’aide de la méthode du tableau de simplex.
4- Donner le tableau optimal du programme primal à l’aide du tableau opti-
mal dual.
5-Résoudre le programme P.L à l’aide de la méthode dual du simplex.
Exercice 17

On considère le programme linéaire suivant:

7
 8
>
> max Z = 6x1 + 5x2
>
>
>
> sous contraintes
<
x1 + x2 8
(P L)
>
> 2x 1 + 3x2 6
>
>
>
> x1 x2 2
:
xi 0; i = 1; 2

1- Donner une résolution graphique de ce programme linéaire.

2- Soit un modèle de programmation linéaire qui doit être appliqué régulière-
ment mais dont certains coe¢ cients varient d’une application à l’autre. Prenons
le cas où les coe¢ cients de la fonction coût Z varient en fonction d’un facteur
extérieur (prix d’une matière première, taux d’intérêt, indice des prix,...etc).
Ce phénomène peut être modélisé par un paramètre intervenant dans ces
coe¢ cients.
En introduisant un paramètre dans la fonction coût Z, le programme
linéaire (P L) s’écrit:
8
>
> max Z = (6 2 )x1 + (5 + )x2
>
>
>
> sous contraintes
<
x1 + x2 8
(P L)
>
> 2x1 + 3x2 6
>
>
>
> x1 x2 2
:
xi 0; i = 1; 2

a- Résoudre ce programme linéaire suivant les valeurs de :

b- Parmi les solutions réalisables trouvées dans la première question, quelles
sont celles qui ne sont jamais solutions optimales.
c- Pour quelles valeurs de ; le programme linéaire (P L) admet une in…nité
de solutions optimales?

Exercice 18

On considère le programme linéaire suivant:

8
>
> max Z = 3x1 + 4x2
>
>
>
> sous contraintes
<
2x1 + x2 2
(P L)
>
> x1 + 2x2 6
>
>
>
> 3x 1 + 9x2 1
:
xi 0; i = 1; 2

8
1- Donner une résolution graphique de ce programme linéaire.
2- Ecrire le dual de ce problème et utiliser le théorème des écarts complé-
mentaires pour déterminer la solution optimale du dual.