Exercices de Programmation Lineaire

Modelisation

exercice 1 : On veut preparer 500 litres de punch `a partir de cinq boissons A, B, C, D et E. Le punch doit
comporter au moins 20% de jus dorange, 10% de jus de pamplemousse et 5% de jus de framboise. Dapr`es les
donnees suivantes, quelle quantite de chaque boisson est necessaire pour obtenir la composition requise au co
ut
minimum ?
boisson
A
B
C
D
E

jus d
orange (%)
40
5
100
0
0

jus de
pamplemousse (%)
40
10
0
100
0

jus de
framboise (%)
0
20
0
0
0

quantite
disponible (l)
200
400
100
50
800

prix/l
1.50
0.75
2.00
1.75
0.25

exercice 2 : Un avion cargo poss`ede trois compartiments pour le chargement de fret : un `a lavant, un au centre
et un dernier `a larri`ere. Les limites de capacite en poids et en volume sont resumees dans le tableau suivant :
capacite
poids (tonne) volume
12
18
10

compartiment
avant
centre
arri`ere

(m3 )
1000
1300
700

Pour des raisons de stabilite de lavion en vol, le chargement doit etre equilibre dans chaque compartiment,
cest-`a-dire que, pour les trois compartiments, le chargement doit representer la meme proportion, en poids, de
la limite de charge. Lavion a la possibilite de charger les quatre frets suivant :
fret
1
2
3
4

poids
(tonne)
20
16
25
13

encombrement
(m3 /tonne)
70
100
85
60

benefice
(euro / tonne)
220
280
250
200

On peut prendre nimporte quelle portion de ces frets. En dautres termes, on peut choisir de ne pas transporter

le probl`eme qui consiste `a trouver un chargement de cet avion qui maximise le

lintegralite dun fret. Ecrire
benefice sous forme dun programme lineaire.
suppl
ement : Comment faire lorsque chaque type de fret est compose de palettes de 500 kg ?
exercice 3 : Mergin Equipements fabrique de gros transformateurs electriques. Les commandes de la companie
pour les six prochains mois sont donnes dans le tableau ci-apr`es. Les co
uts de fabrication dun transformateur
sont sujets `a des variations dues au cours des mati`eres premi`eres et au prix de la main duvre. Lusine peut
fabriquer jusqu`
a 50 unites par mois en heures normales et 20 unites supplementaires en heures supplementaires.
Les co
uts de ces deux types de production sont egalement donnes dans le tableau.
mois
nombre dunites commandees
co
ut en heures normales (Keuro)
co
ut en heures supp. (Keuro)

janvier
58
18.0
20.0

fevrier
36
17.0
19.0

mars
34
17.0
21.0

avril
69
18.5
22.0

mai
72
19.0
22.0

juin
43
19.0
23.0

Le co
ut de stockage dun transformateur invendu est de 500 euros par mois. La companie poss`ede 15 unites en
stock debut janvier et aimerait en avoir au moins 5 en stock fin juin (i.e. debut juillet). Formuler le probl`eme
consistant `a determiner le plan de production le plus rentable sous la forme dun programme lineaire.
exercice 4 : Un investisseur a deux activites depargne A et B au debut dune periode de 5 ans. Chaque euro
investi en A au debut dune annee rapporte 1.40 euro (soit un profit de 0.40 euro) au bout de 2 ans, quil peut
aussitot reinvestir. Chaque euro investi en B au debut dune annee rapporte 1.70 euro au bout de 3 ans. Deux
autres actions C et D peut etre envisagees `a lavenir. Chaque euro investi en C au debut de la seconde annee
rapporte 1.90 euro `
a la fin de lannee 5. Pour laction D, 1 euro investi au debut de lannee 5 rapporte 1.30 euro
`a la fin de cette meme annee. Lepargnant commence la periode avec 60000 euro et souhaite connatre un plan
depargne qui maximise la somme totale accumulee en debut de sixi`eme annee. Formuler ce probl`eme comme un
programme lineaire.
suppl
ement : Comment faire lorsquon fixe un plafond dinvestissement dans chaque activite depargne ? Lintegration
dune fiscalisation constante sur les plus-values financi`eres modifie-t-elle la formulation ? Et si la fiscalisation est

lineaire croissante pas morceaux ? Comment faire pour prendre en compte une inflation sur chaque annee ?
` cet
exercice 5 : Un supporter du PSG desire faire une pri`ere `a la Bonne M`ere sur les hauteurs de Marseille. A
effet, il consulte sa carte de France pour trouver la meilleure route possible et il identifie les troncons suivants :

Paris

350
300
500

150

Lyon

Clermont

400

300

Bordeaux

250

Toulouse

300
Marseille

Figure 1 Carte des deplacements possibles

Les sommets sont des villes et le kilometrage est indique sur les arcs du graphe.
1. Formaliser le probl`eme de trouver le chemin le plus court comme un programme lineaire.
2. On consid`ere maintenant que certains supporters de lOM peuvent se trouver sur les differentes portions de
route, ce qui pourrait lempecher de continuer son chemin. Si la probabilite pij de rencontrer un supporter
de lOM est constante, quelque soit la route, proposer une formulation permettant de maximiser ses chances
darriver `a Marseille.
3. Si maintenant la probabilite pij est specifique `a chaque arc (i, j), on ne peut plus appliquer lastuce
prededente. Montrer quon peut reformuler le probl`eme de mani`ere `a ne faire intervenir que des multiplications de probabilites. Utiliser alors la transformation en log pour retrouver des additions et proposer
un mod`ele lineaire. Que doit-on faire pour convertir la solution obtenue en une solution utilisable ?
4. On suppose que notre supporter a pu faire le voyage. Il telephone `a ses amis pour leur dire que la vue est
tr`es belle du haut de la colline. Si on consid`ere maintenant que les valeurs sur les arcs (i, j) sont les places
disponibles sur des trains faisant le trajet entre les villes i et j, combien damis maximum peuvent venir ?

Exercices de Programmation Lineaire

Simplexe Primal

exercice 1 : Resoudre le programme lineaire suivant par la methode du simplexe

Max z =5x1 +6x2 +9x3 +8x4
s.c.
x1 +2x2 +3x3 + x4 65
x1 + x2 +2x3 +3x4 63
x1 , x2 , x3 , x4 >0
en faisant entrer en base la variable hors base dont le co
ut reduit est le plus grand
en faisant entrer en base la variable hors base dont laugmentation de valeur reelle engendre la plus grande
augmentation dans la fonction objectif
exercice 2 : Resoudre le programme lineaire `a laide de lalgorithme primal du simplexe `a deux phases
Max z = x1 - 2x2 - x3
s.c.
2x1 + x2 - x3 6-1
x1 - 2x2 +x3 6-2
x1 , x2 , x3 > 0
exercice 3 : On consid`ere le programme lineaire suivant
Min z = 3x1 + x2
- 2x4
s.c.
2x1 + x2 +3x3 - 5x4 62
x1 +2x2 - 2x3 + 3x4 >3
x1 + x2 + x3 + 2x4 =7
x1 , x2 , x3 , x4 >0
La solution x = (2, 5, 0, 0) est-elle une solution realisable ? Apr`es avoir introduit deux variables decart, on se
demandera si `a x correspond une solution de base du programme lineaire transforme. Dans laffirmative, est-elle
optimale ?
exercice 4 (Klee & Minty)) : On consid`ere le programme lineaire suivant
Max z =100x1 +10x2 +x3
s.c.
x1
6
1
20x1 + x2
6 100
200x1 +20x2 +x3 610000
x1 , x2 , x3 >
0
En initialisant en x = (0, 0, 0), resoudre le probl`eme par la methode du simplexe
Verifier que la transformation lineaire x1 = y1 , x2 = 100y2, x3 = 10000y3 transforme le poly`edre anterieur
dans le cube unitaire de R3 . Verifier que lalgorithme a parcouru tous les sommets du cube avant de trouver le
sommet optimal.
Que suggerer pour remedier `
a ce probl`eme ?
exercice 5 (examen juin 2007) : On consid`ere le programme lineaire (P ) suivant :

Max
x1
2x2 + 20x3

s.t.

10x1 +
5x2
x3 30
(P )
5x

x3 10

25x

10x
+
2x

1
2
3 105

x1 , x2 , x3 0.

(a) Appliquez la phase I du simplexe au probl`eme (P ) pour montrer quil admet une solution realisable de base.
` partir de la resolution precedente, conclure quant `a loptimisation du probl`eme (P ).
(b) A
(c) On se propose dinserer la contrainte x1 2x2 + 20x3 98 dans le programme lineaire (P ). A-t-on une base
optimale ? Est-elle unique ? Justifiez votre reponse.

u est un reel :
exercice 6 (examen juin 2009) : On consid`ere le programme lineaire P suivant o`

Max z = 2x1 + x2 + 3x3

sous les contraintes
x1 + 3x2 + 2x3 30
x1 + x2 + x3 24
3x1 + 5x2 + 3x3 60
x1 0, x2 0, x3 0

On consid`ere le probl`eme P4 . On nous informe que x1 > 0, x2 = 0 et x3 > 0 dans la base optimale de P4 .
Comment utiliser cette information pour resoudre le probl`eme P4 donne en un nombre minimum diterations.

Etudier,
sans developper aucune iteration, la solution optimale de P4 et donner cette solution quand cest
possible.
Donner le dual D4 de P4 . Deduire de la question precedente et sans aucun calcul supplementaire, la valeur
des variables duales et des variables decart duales.
En tenant compte des calculs effectues dans la partie precedente, resoudre par le simplexe revise, le probl`eme
P5 .
exercice 7 (juin 2011) : soit (P) le programme lineaire suivant :

max 5x1 + 4x2 + 7x3

s.t.

3x1 + 8x2 + 2x3 40

(P )
9x

1 + 5x2 + 7x3 35

7x
+ 3x2 + 3x3 51

x1 0, x2 0, x3 0

Montrer quune seule des solutions suivantes est realisable de base pour (P). Justifier chaque cas.
x1 = ( 53 , 3, 0)
x2 = ( 51
7 , 0, 0)
x3 = (4, 2, 6)

En partant de la solution obtenue en 1), optimiser le programme lineaire (P). Ecrire

le dual (D) de (P).
Sans aucun calcul, utiliser les questions precedentes pour obtenir la solution du dual (D).
On suppose maintenant que le sens de linegalite dans la 2`eme contrainte de (P) est inverse, cest-`a-dire quon
remplace 9x1 + 5x2 + 7x3 35 par 9x1 + 5x2 + 7x3 35. Montrer en utilisant la phase I du simplexe que le
nouveau programme lineaire est irrealisable.

Exercices de Programmation Lineaire

Dualite

le dual du programme lineaire suivant :

exercice 1 : Ecrire
Max z =2x1 +4x2 + x3 + x4
s.c.
x1 - x2 +3x3 - x4 =2
2x1 - x2 - 5x3 +2x4 >1
3x1 +4x2 +5x3 - 3x4 62
x1 > 0, x2 > 0, x3 6 0, x4 qcq
exercice 2 : On consid`ere le programme lineaire (P ) suivant :
Max z =3x1 +2x2
s.c.
2x1 + x2 66
x1 - x2 61
x1 + x2 63
x1 , x2 >0

Ecrire
le dual (D) de (P

).


Verifier que x = 2 1 est solution realisable de (P ) et que y = 0 1/2 5/2 est solution realisable de (D).
Conclusion ?
exercice 3 : On consid`ere le programme lineaire suivant :
Min z =14x1 +10x2 - 3x3
s.c.
x1 + 2x2 - x3 >2
2x1 - x2 + x3 >1
x1 > 0, x2 > 0, x3 6 0
En utilisant le theor`eme des ecarts complementaires, determiner la solution optimale de ce programme lineaire.
exercice 4 : Resoudre par la methode du simplexe :
Min z =x1 - 4x2 - 3x3
s.c.
2x1 +2x2 + x3 64
x1 +2x2 +2x3 66
x1 , x2 , x3 >0
Indiquer le probl`eme dual et donner une interpretation compl`ete `a chaque iteration : la solution primale, la base
B et B 1 , la solution duale et sa valeur, les contraintes duales qui sont satisfaites.
exercice 5 : Une entreprise fabrique 3 produits `a partir de 3 ressources. Le processus de fabrication de certains
produits peut creer certaines ressources (cest le cas par exemple de la fabrication de certains produits petroliers).
Le premier produit utilise 3 unites de la ressource 1, 1 unite de la ressource 2 et 1 unite de la ressource 3. Le
deuxi`eme produit utilise 1 unite des ressources 1 et 3 et produit 1 unite de la ressource 2. Enfin le troisi`eme
produit utilise 1 unite de la ressource 1, 2 unites de la ressource 2 et produit 1 unite de la ressource 3. Le premier
produit rapporte 4, le troisi`eme rapporte 2, tandis que le deuxi`eme co
ute 2 par unite produite. On dispose au
depart de 180, 30 et 60 unites des ressources 1, 2 et 3 respectivement.

Ecrire
le programme lineaire dont la resolution permet de trouver la production qui maximise le benefice.
Resoudre ce programme lineaire par la methode du simplexe.
Verifier votre solution soit en utilisant la dualite soit en utilisant le theor`eme des ecarts complementaires.
Quel serait le prix maximum `
a payer pour une unite supplementaire des ressources 1, 2 et 3 ? Quel serait le
prix minimum de revente de ces produits ?
` partir de quel benefice sur le produit 3 devient-il rentable den produire ?
A
Quel est lintervalle dans lequel le co
ut de fabrication du produit 2 peut varier sans changer la solution optimale ?
Quelles sont laugmentation et la diminution permises de la quantite disponible de la ressource 2 qui ne change
pas la base optimale ?

Exercices de Programmation Lineaire

Complements

exercice 1 : Soit programme lineaire P (a, b) suivant :

Max z =7x1 +11x2 +(12 b)x3 +9x4

s.c.
x1 + 4x2 +
2x3 - 3x4 620-a
2x1 + x2 +
3x3 + x4 6 6
x1 , x2 , x3 , x4 > 0
`
A quelle(s) condition(s) la base B = {2, 4} est-elle realisable ? Dans quel cas ny a-t-il pas unicite de loptimum ?
Expliciter la(les) nouvelle(s) base(s).

On supposera dans toute la suite que B est realisable. Ecrire

le dual D(a, b) de p(a, b). Representer D(0, 0) dans
2
R . Determiner les variables duales associees `a la base B. Retrouver la condition doptimalite de la premi`ere
question.
Pour toutes les questions suivantes, on pose a = b = 0. On ajoute une variable u > 0 au probl`eme primal,
de gain c, de coefficient 2 dans (1) et 10 dans (2). Comment est transforme le probl`eme dual ? Pour quelles
valeurs de c la base B conserve-t-elle son caract`ere optimal ? On compl`etera le dessin avec c = 20.
Si on ajoute maintenant au lieu de u une variable v > 0, de gain 1, de coefficients 2 et 3, que peut-on dire
`a partir du primal et du dual ?

exercice 2 : On veut fabriquer 3 produits P 1, P 2 et P 3 dont le profit unitaire est de 250, 100 et 100 euros
respectivement. Le produit P 1 (P 2) (P 3) necessite 2, 5, 5 et 2 (3, 2, 3 et 1) (1, 0, 0 et 1) tonnes de nickel,
chrome, germanium et magnesium. On peut disposer de 7, 11, 10 et 6 tonnes de Ni, Cr, Ge et Mg par jour. Les
produits P 1 et P 2 doivent passer par un four separement 1 et 2 heures quotidiennement. Le four est operationnel

6 heures par jour. On veut connatre la politique de production qui maximise le profit. Ecrire
et resoudre le dual
du probl`eme decrit. Interpreter la solution optimale du dual et en deduire la solution du probl`eme primal.
a laide du simplexe en variables bornees
exercice 3 : Resoudre le probl`eme suivant `
Max z =4x1 +12x2 +7x3 +10x4
s.c.
x1 + 3x2 +2x3 + x4 =17
x1 + 2x2 + x3 + 2x4 =17
i 1 6 xi 6 i + 1
on choisit comme base initiale B = {x1 , x4 } correspondant `a la solution x = 1
comment faire lorsquon ne connait pas de base initiale ?
a laide du simplexe en variables bornees
exercice 4 : Resoudre le probl`eme suivant `
Max z =5x1 + x2 + x3 +2x4
s.c.
4x1 +4x2 +4x3 + x4 648
8x1 +6x2 +4x3 +3x4 672
1 6 x1 6 10
2 6 x1 6 5
3 6 x1 6 5
4 6 x1 6 8
exercice 5 : Resoudre le probl`eme suivant `
a laide du simplexe en variables bornees
Max z =5x1 -2x2 +3x3 + x4 +2x5
s.c.
3x1 - x2 +2x3 - 2x4 +4x5 619
i 1 6 xi 6 i + 1

4 5