Solution TD1-RO

Exercice 1

a- Soit le problème linéaire suivant :

max z  2 x1  x2
1
s.c x1  x2  2
3
 2 x1  5 x2  7
x1  x2  4
x1  0, x2  IR

*) la forme canonique du problème initial

En posant : x2= x+2 - x-2, et remplaçant cela dans le problème initial en utilisant les
règles de transformation équation-inéquation, on aura :
max z  2 x1  x2  x2
1
s.c x1  x2  x2  2
3
1
 x  x2  x2  2
3
 2 x1  5 x2  5 x2 2  7
x1  x2  x2  4
x1 , x2 , x2  0,
Avec x2 = x+2 - x-2

*) La forme standard du problème initial

En posant : x2= x+2 - x-2, et remplaçant cela dans le problème initial en utilisant les
règles de transformation inéquation-équation, on aura :

max z  2 x1  x2  x2

1
s.c x1  x2  x2  2
3
 2 x1  5 x2  5 x2  7
x1  x2  x2  4
x1 , x2 , x2  0,

Avec x2= x+2 - x-2

 D’où, en faisant entrer les variables d’écart dont le nombre est égale aux nombre des
inéquations, on aura
max z  2 x1  x2  x2
1
s.c x1  x2  x2  2
3
 2 x1  5 x2  5 x2  x3  7
x1  x2  x2  x4  4
x1 , x2 , x2 , x3 , x4  0,
Avec x2 = x+2 - x-2

b- On considère le problème linéaire suivant :

min z  3x1  x3

s.c x1  1 x2  3x3  2
2
4 x2  x3  5
x1, x3  0, x2  0

*) La forme canonique du problème initiale

On a le problème initial est équivalent au problème suivant :
_
max z  3x1  x3

s.c x1  1 x2  3x3  2
2
4 x2  x3  5
x1, x3  0, x2  0
_
Avec z =-z.
En posant x   x  avec x   0 , le problème devient sous la forme
2 2 2
canonique
 _
max z  3x  x
1 3
s.c  x  1 x   3x  2
1 2 2 3

 4x  x  5
2 3

4 x  x  5
2 3
x , x , x  0
1 2 3

_
Avec x  x et z =- z.
2 2
*) La forme standard du problème initial
A partir du problème mis sous format canonique et en ajoute les variables d’écart, on
déduit la forme standard suivant :
_
max z  3x1  x3

s.c  x1  1 x2  3x  x  2
2 3 4
  x 5
 4 x2 3
, x , x  0
x1, x2 3 4

_
Avec x  x et z =- z.
2 2
Le système final est donné par :
_
max z  3x1  x3

s.c x1  1 x2  3x  x  2
2 3 4
  x 5
 4 x2 3

x1, x2 , x3, x4  0
c- On considère le problème linéaire suivant
 min z  2 x  3x 1 2

s.c x  3
2

2x  x  2
1 2

 x  3x  1
1 2

x  0, x  IR
1 2

*) Format canonique du problème initial

Le problème équivalent est donné par :

max z  2 x  3 x 1 2

s.c x  3
2

2x  x  2
1 2

 x  3x  1
1 2

x  0, x  IR
1 2
_

Avec z   z , d’où la forme canonique est donnée par :

_
max z  2 x1  3x2  3x2
s.c  x2  x2  3
2 x1  x2  x2  2
 2 x1  x2  x2  2
x1  3x2  3x2  1
x1 , x2 , x2  0

Avec z   z et x  x  x
2

2

2

*) La forme standard du problème initial

En utilisant la forme canonique, en déduit
 _
max z  2 x1  3x2  3x2
s.c  x2  x2  x3  3
2 x1  x2  x2  2
x1  3x2  3x2  x4  1
x1 , x2 , x2 , x3 , x4  0

Avec z   z et x  x  x2

2

2

Exercice 2

Une usine produit des câbles de cuivre de 5mm et de 10mm de diamètre, sur lesquels le
bénéfice est de respectivement 2 et 7 Dirhams au mètre. Le cuivre dont dispose l’usine permet
de produire 20 km de câble de 5 mm de diamètre par semaine. La production de câble de 10
mm demande 4 fois plus de cuivre que celle de câble de 5mm. Pour des raisons de demande,
la production hebdomadaire de câble de 5mm ne doit pas dépasser 15 km et pour des raisons
de logistique la production de câble de 10 mm ne doit pas représenter plus de 40% de la
production totale.
Question : Donnez le programme linéaire dont l’objectif est de maximiser le bénéfice
hebdomadaire de l’usine, en supposant que dans les contraintes énoncées, tout se qui est
produit est vendu.

Remarque

-) Comprendre la question de l’objectif

-) Identifier ou définir les variables dont dépend l’objectif de la question

-) Définir les règles associées à ses variables et leurs interactions

-) Définir la fonction objectif

-) Résoudre le problème avec la méthode adéquate.

Réponse

 Objectif : maximiser le bénéfice hebdomadaire des ventes des câbles de cuivre à

fabriqués par l’usine. « Problème de maximisation »
 Les variables de décision : On a le bénéfice dépend du nombre de mètre de câbles de
cuivre des deux types à fabriquer par semaine par l’usine. On pose

X1 : le nombre de mètres de câbles de 5 mm fabriqués par semaine par l’usine.

X2 : le nombre de mètres de câbles de 10 mm fabriqués par semaine par l’usine.

 Le profit total en Dirhams par semaine : comme le prix de vente d’un mètre de câble de
5mm est 2 Dirhams et celui de 10mm est 7 Dirhams, alors le profit par semaine est
z = 2 * X1 + 7 * X2.
 Les contraintes sont données par :
o Contrainte sur le cuivre disponible : On a les ressources en cuivre disponibles par
semaine dans l’usine permettent de produire 20 km de câble de 5 mm de diamètre
par semaine et donc permettent de produire 20000 m de câbles de 5mm de
diamètre. Comme La production de câble de 10 mm demande 4 fois plus de cuivre
que celle de câble de 5mm, donc la production de 1m de câble de 10mm coute en
cuivre l’équivalent de 4 m de câble de 5 mm. En déduit alors la relation suivante
a*X1+4*a*X2≤ 20000*a ;
Avec a correspond au poids de 1 mètre de cuivre de diamètre 5mm, d’où on a la
contrainte finale
X1 + 4 * X2 ≤ 20000.
o Contrainte sur la demande du câble de diamètre de 5 mm: on doit avoir
X1 ≤ 15000
o Contrainte de logistique : on la production de câble de 10 mm ne doit pas
représenter plus de 40% de la production totale qui est égale à (X1+X2), ceci
donne la contrainte suivante
X2 ≤ 2/5 *(X1+X2)
Donc, la contrainte finale est
3*X2≤ 2*X1

En final, on obtient le système suivant

Max z = 2 * X1 + 7 * X2
X1 + 4 * X2 ≤ 20000
X1 ≤ 15000
-2*X1 + 3*X2 ≤ 0
X1; X2 ≥ 0

Exercice 3

Un magasin veut faire fabriquer des pantalons et des vestes de sport à une usine textile qui
dispose de 750 m2 de coton et 1000 m2 de polyester. La fabrication d'une paire de pantalon
requiert 1 m2 de coton et 2 m2 de polyester et celle d'une veste requiert 1,5 m2 de coton et
1 m2 de polyester. Sachant que le bénéfice du magasin sur une paire de pantalon est de 50 DH
et de 40 DH pour une veste.

Question : Formuler le programme linéaire dont l’objectif est de maximiser le bénéfice total
du magasin linéaire en précisant la signification de chaque variable de décision.

Réponse

 Objectif : maximisation du bénéfice total des ventes des pantalons et des vestes fabriqués
par l’usine et qui sont demandés par le magasin. « Problème de maximisation »
 Variables de décisions : Comme le bénéfice dépend du nombre de des pantalons et des
vestes vendus alors on pose :
X1 : nombre de pantalons demandés par le magasin à l’usine.
X2 : nombre de vestes demandées par le magasin à l’usine.

 La fonction objectif : cette fonction dépend du nombre de pantalon et vestes demandés

par le magasin à l’usine et sachant que la vente d’un pantalon est 50 DH et la vente de
veste est 40 DH. On déduit alors la fonction objectif est donné par :
z = 50*X1 + 40*X2
 Les contraintes
o Contrainte sur les ressources de coton pour la fabrication de vestes et pantalon, on
aura
 X1 + 1,5*X2 ≤ 750
o Contrainte sur les ressources de polyptère pour la fabrication de vestes et pantalon,
on aura
 2*X1 + X2 ≤ 1000

En final, on obtient le système suivant :

Max z=50*X1 + 40*X2

X1 + 1,5*X2 ≤ 750

2*X1 + X2 ≤ 1000

X1; X2 ≥ 0

Exercice 4

Un producteur d’électricité souhaite que ces deux centrales nucléaires P et Q fournissent une
quantité d’énergie aux villes A, B et C. Les quantités d’énergie minimales à satisfaire sont de
16 pour A, 12 pour B et 18 pour C. Quand un réacteur de P produit, il envoie 2 unités à A, 1
unité à B et 1 unité à C ; et coûte 20 DH par jour. Quand un réacteur de Q produit, il envoie 1
unité à A, 1 unité à B et 3 unités à C ; et il coûte 40 DH. Le producteur cherche la
combinaison la moins coûteuse de réacteurs de P et Q qui respectera l’exigence de
consommation minimale pour les villes A, B, C.

Les données sont récapitulées dans le tableau suivant :

P Q Besoins minimaux
A 2 1 16
B 1 1 12
C 1 3 18
Coût unitaire 20 40

Question : Formuler le problème linéaire répondant à l’objectif.

Réponse

 Objectif : satisfaire les villes A, B et C en quantité de consommation d’énergie minimal

avec un moins de coût possible sur la quantité d’énergie fabriquée par les deux centrales P
et Q : Donc, on a un problème de minimisation.

 Les variables de décisions :

o X1 nombre de quantité d’énergie produite par le producteur P par jour.
o X2 nombre de quantité d’énergie produite par le producteur Q par jour.

 Les contraintes sont exprimées sur les trois premières lignes, ce qui permet d’avoir :
o La première ligne donne : 2X1+X2 ≥ 16.
o La deuxième ligne donne : X1+X2 ≥ 12.
o La troisième ligne donne : X1+3X2 ≥ 18.

 La fonction objectif est déduite de la dernière ligne donnant la valeur en coût de chaque
unité d’énergie fabriquée par P et Q, d’où on obtient : w = 20 * X1 + 40 * X2

En final, on obtient le système suivant :

min w = 20 * X1 + 40 * X2
2X1+X2 ≥ 16
X1+X2 ≥ 12
X1+3X2 ≥ 18
X1 ; X2 ≥ 0

Exercice 5

Un industriel doit livrer trois biens A, B et C à raison de « en proportion de » 6 unités de A, 11

unités de B et 23 unités de C. Il dispose de deux facteurs de production X et Y. L’emploi
d’une unité de X permet de réaliser une unité de A, une de B et une de C. Une unité de Y
permet de réaliser une unité de A, 2 de B et 5 de C. Le prix du facteur X est de 1000 DH
l’unité et celui du facteur de Y est de 4000 DH.

Question : sachant l’industriel doit satisfaire la demande à un coût minimal, donner le

problème linéaire qui modéliser cette situation.

Question : Donner le problème linéaire (PL) qui modélise l’objectif de l’industriel qui est de
satisfaire la demande à un coût minimal

Réponse

- Objectif : Minimiser le coût de fabrication des trois bien en respectant les contraintes,
donc on a un problème de minimisation.
Comme le nombre des biens A, B et C dépend des nombres des unités de X et Y utilisés et
que le cout dépendra des dépenses des achats relatives aux unités de X et Y alors:

- On a les variables de décision sont données par

*) x : la quantité positive du facteur X à utiliser dans le plan de production

*) y : la quantité positive du facteur Y à utiliser dans le plan de production

 On a, le coût de fabrication est donné par :

z = 1000 x + 4000 y

 On a, une unité du facteur X permet de réaliser une unité de A et une unité du facteur Y
permet de réaliser une unité de A de plus on a dans l’objectif on doit fabriquer au minimum 6
unité du bien A. ce qui permet d’avoir

x y6

 On a, une unité du facteur X permet de réaliser une unité de B et une unité du facteur Y
permet de réaliser 2 unité B de plus on a dans l’objectif on doit fabriquer au minimum 11
unité du bien B. ce qui permet d’avoir

x  2 y  11

 On a, une unité du facteur X permet de réaliser une unité de C et une unité du facteur Y
permet de réaliser 5 unité de C de plus on a dans l’objectif on doit fabriquer au minimum 23
unité du bien C. ce qui permet d’avoir

x  5 y  23

Ce qui permet d’avoir le système linéaire qui modélise le problème de l’industriel

min z  1000 x  4000 y

S .C x  y  6
x  2 y  11
x  5 y  23
x, y  0

Exercice 6

Reformuler les problèmes d’optimisation suivants sous forme de programmes linéaires

canoniques.

a)
 min z  max x1  2 x2  5 x3 , 2 x1  3x2  x3 
s.c x1  x3  6
4 x1  x2  x3  5
x1 , x2 , x3  0
b)

min z  x  3x  2 x  x  5x  x
1 2 3 1 2 3

s .c 2 x  x  3 x  12
1 2 3

2x  5x  9
2 3

x ,x ,x  0
1 2 3

c)

min z  x1  x2  10  max 2 x2  4,4 x2  x3 , 2 x1  3x2  x3 

s.c x1  x2  3x2  5
max  x1  2 x2  5 x3 , 2 x1  4 x3   15
x1 , x2 , x3  0

Réponse

a- Soit le problème min-max suivant

min z  max x1  2 x2  5 x3 , 2 x1  3x2  x3 

s.c x1  x3  6
4 x1  x2  x3  5
x1 , x2 , x3  0

En utilisant les transformations vues au cours, on obtient le problème équivalent suivant

 min z t
s.c x1  x3  6
4 x1  x2  x3  5
x1  2 x2  5 x3  t  0
2 x1  3x2  x3  t  0
x1 , x2 , x3  0; t  IR

En posant t  t  t avec t,t  0

Le (PL) ci-dessus devient :

min z  t  t
s.c x1  x3  6
4 x1  x2  x3  5
x1  2 x2  5 x3  t   t   0
2 x1  3 x2  x3  t   t   0
x1 , x2 , x3 , t  , t   0;

avec t  t  t
Sous format canonique, le P.L devient :

_
max z  t   t 
s.c x1  x3  6
 x1  x3  6
4 x1  x2  x3  5
x1  2 x2  5 x3  t   t   0
2 x1  3 x2  x3  t   t   0
x1 , x2 , x3 , t  , t   0;
_
 
Avec t  t t et z  z
b- Soit le problème suivant
 min z  x13 x2  2 x3  x15 x2  x3
s.c 2 x1 x2 3 x3 12
2 x2 5 x3 9
x1, x2 , x3  0

En utilisant les transformations vues en cours et en utilisant, le problème initial est

équivalent au problème suivant :

min z  t1  t 2
s.c 2 x  x  3 x  12
1 2 3
 2 x  x  3 x  12
1 2 3
2 x2  5 x3  9
x1  3 x2  2 x3  t1  0
 x1  3 x2  2 x3  t1  0
x1  5 x2  x3  t 2  0
 x1  5 x2  x3  t 2  0
x1 , x2 , x3 , t1 , t 2  0;

Enfin, on aura le (P.L) sous format canonique

 _
max z  t1  t 2
s.c 2 x  x  3x  12
1 2 3
 2 x  x  3x  12
1 2 3
2 x2  5 x3  9
x1  3x2  2 x3  t1  0
 x1  3 x2  2 x3  t1  0
x1  5 x2  x3  t 2  0
 x1  5 x2  x3  t 2  0
x1 , x2 , x3 , t1 , t 2  0;

_
Avec z  z
c- Soit le problème suivant

min z  x1  x2  10  max 2 x2  4,4 x2  x3 , 2 x1  3x2  x3 

s.c x1  x2  3x2  5
max  x1  2 x2  5 x3 , 2 x1  4 x3   15
x1 , x2 , x3  0
 En utilisant les règles de transformation, ce problème est équivalent au P.L suivant :
min z  t1  t 2
s.c x1  x2  3x3  5
 x1  x2  3x3  5
 x1  2 x2  5 x3  15
2 x1  4 x3  7
x1  x2  10  t1  0
 x1  x2  10  t1  0
2 x2  4  t 2  0
4 x2  x3  t 2  0
2 x1  3x2  x3  t 2  0
 2 x1  3x2  x3  t 2  0
x1 , x2 , x3 , t1  0; t 2  IR

   
En posant t2  t2  t2 avec t2 , t2  0
Le problème sous forme canonique est donné par
_
max z  t1  t 2  t 2
s.c x1  x2  3 x3  5
 x1  x2  3x3  5
 x1  2 x2  5 x3  15
2 x1  4 x3  7
x1  x2  10  t1  0
 x1  x2  10  t1  0
2 x2  4  t 2  t 2  0
4 x2  x3  t 2  t 2  0
2 x1  3 x2  x3  t 2  t 2  0
 2 x1  3 x2  x3  t 2  t 2  0
x1 , x2 , x3 , t1 , t 2 , t 2  0; t 2  IR
 _
Avec z  z et t2  t2  t2
Attention : on doit avoir 2x1 - 4x3 ≤ 15 et t2 doit etre >= 0 car il représente un max d’une
valeur absolue.