75. Un plombier connaît la disposition de trois tuyaux sous des

3ième année Licence LMD de mathématiques, USDBlida 29

75. Un plombier connaît la disposition de trois tuyaux sous des dalles ( voir figure ci

dessous ) et il lui suffit de découvrir une partie de chacun d’eux pour pouvoir y poser

les robinets. Il cherche à soulever un nombre minimale de dalles.

1 2 3 4

5 6 7 8

Trouver une solution minimale par la programmation linéaire.

( Indication: poser xi = 0 ou 1, i = 1,.,8;si on ne soulève pas ou on soulève la dalle i )

Ecrire un programme linéaire avec les contraintes d’intégrité. Remplacer les

contraintes par 0 ≤ xi ≤ 1, i = 1, …, 8. Appliquer l’algorithme du simplexe, puis

justifier ce changement de contraintes.

76. Résoudre par la méthode des deux phases les problème linéaires suivant :

a) min z = 2 x1 - x2 + x3

x1 + x2 - x3 = - 1

- 2 x1 - x2 + x4 = 1

x1 + 4 x2 - x4 = 2

x1 ≥ 0,…, x4 ≥ 0

b) min z = x1 + x2 - x3 – 2 x5

x1 + 2 x2 + x4 = 3

3 x2 - x4 + x5 ≤ 5

x2 + x5 ≥ 3

x1 ≥ 0,…, x5 ≥ 0

77. En utilisant la forme produit de l’inverse, déterminer A-1 si :

a) A =

4 2 3

1 1 1

4 1 1

b) A =

1 1 2 1

1 1 1 1

2 3 1 1

1 2 3 2

−−

Exercices du Cours de la programmation linéaire donné par le Dr. Ali DERBALA


78. Par la méthode révisée du simplexe ( forme matricielle de la méthode du

simplexe), résoudre les problèmes:

a) min z = - 2 x1 + x2 - 3x3 – x4 – x5

x1 + x2 + 2 x3 + 3 x4 – 2 x5 ≤ 4

- x1 - 2 x2 + 3 x3 - 2 x4 + 3x5 ≤ 10

x1 ≥ 0,…, x5 ≥ 0

b) max z = 9 x1 + 7 x2

10 x1 + 5 x2 ≤ 50

6 x1 + 6 x2 ≤ 36

4,5 x1 + 18 x2 ≤ 81

x1 ≥ 0, x2 ≥ 0

c) min z = - 6 x2 - 5x3

x1 + 2 x2 + x3 + x4 = 10

2 x1 + 3 x2 + 7 x3 + 3 x4 = 21

x1 ≥ 0,…, x4 ≥ 0

d) max z = x1 - x2 + x3 + 2 x4

x1 + x2 + x3 + 2 x4 = 7

x2 + x3 + x4 = 5

x3 - x4 = 9

x1 ≥ 0,…, x4 ≥ 0

79. Par la méthode révisée du simplexe ou méthode matricielle, résoudre le problème

suivant :

MinZ = - 5 x1 - 6 x2

2 x1 + 3 x2 + x3 = 10

x1 + 2 x2 + x4 = 6

x1 ≥ 0 ; .. ; x4 ≥ 0



80. On considère les problèmes de programmation linéaire :

a) min z = - 3/4 x1 + 150 x2 – 1/50 x3 + 6 x4

1 / 4 x1 - 60 x2 – 1 / 25 x3 + 9 x4 + x5 = 0

1 / 2 x1 – 90 x2 - 1/ 50 x3 + 3 x4 + x5 = 0

x3 + x7 = 1

xj ≥ 0, j = 1,…,7.

b) max z = x3 - x4 + x5 - x6

x1 + x3 – 2 x4 - 3 x5 + 4 x6 = 0

x2 + 4 x3 - 3 x4 - 2 x5 + x6 = 0

x3 + x4 + x5 + x6 + x7 = 1

xj ≥ 0, j = 1,…,7.

1) Résoudre ces problèmes par l’algorithme du simplexe et montrer que dans ces

exemples, le phénomène de cycles se produit.

2) En appliquant la méthode lexicographique, éviter le cycle et obtenir la solution

optimale de chaque problème.

81. On considère les problèmes de programmation linéaire

a) minx z = 3x1 - x2 + 4 x3

2 x1 - x2 - x3 + x4 ≥ -1

x2 + x4 ≥ 2

xj ≥ 0, j = 1,…,4.

b) max z = 2x1 + 3 x2 - x3

x1 + x2 ≤ 10

2 x1 - x2 + x3 ≤ 7

x2 - x3 ≤ 0

x1 - x3 ≤ 10

xj ≥ 0, j = 1,…,3.

c) max z = - 2 x2 + x4 + 3 x5

x1 – 2 x2 + 3 x4 + x5 = 8

x2 + x3 + x4 - 2 x5 = 6

xj ≥ 0, j = 1,…,5.

Déterminer les problèmes duaux correspondants.



82. Donner les problèmes duaux pour les problèmes suivants :

a) min z = x1 - 2 x2 +x3 - x4 + x5

x1 – 2 x2 + x3 – 3 x4 - 2 x5 = 6

2 x1 + 3 x2 - 2 x3 - x4 + x5 ≤ 4

x1 + 3 x3 - 4 x5 ≥ 8

x1 ≥ 0, x2 ≥ 0, x3 et x4 sont quelconques.

b) max z = 2 x1 - x3

x1 + x2 + x3 ≤ 4

3 x2 + 5 x3 = 5

- x1 + x2 ≥ 0

x2 - x3 = 2

x1 - x2 - x3 ≤ - 2

x1 ≥ 0, x3 ≥ 0, x2 est quelconque.

c) minz = c x + d y

A1 x + A2 y ≥ a

B1 x + B2 y = b

x ≥ 0, y quelconque.

83. Par l’algorithme du simplexe , résoudre les problèmes :

a) max z = 2 x1 + 3 x2

- x1 + 2 x2 ≤ 6

x1 - 4 x2 ≤ 2

x1 - x2 ≤ 5

x1 ≥ 0, x2 ≥ 0.

b) max z = 2 x1 - x2 + 3 x3 – 2 x4 + x5

- x1 + x2 + x3 = 1

x1 - x2 + x4 = 1

x1 + x2 + x5 = 2

xi ≥ 0, i = 1,…,5.

Déterminer les solutions optimales des problèmes duaux correspondants.



84. Soit le programme linéaire suivant :

MinZ = 2 x1 + x3

x1 + x2 - x3 ≥ 5

x1 - 2 x2 + 4 x3 ≥ 8

x1 ≥ 0 ; .. ; x3 ≥ 0

Ecrire son dual. Le résoudre géométriquement.

Déterminer une solution optimale du problème primal. Conclure.

85. On considère le programme linéaire :

max z = 4 x1 + 2 x2

- x1 + 2 x2 ≤ 6

x1 + x2 ≤ 9

3 x1 - x2 ≤ 15

x1 ≥ 0, x2 ≥ 0.

En utilisant l’interprétation géométrique, trouver la solution optimale. En utilisant

le théorème fondamental de la dualité, déterminer la solution optimale du

programme dual correspondant.

86. On considère le programme linéaire suivant :

min z = x1 + 3 x2 + 2 x3

3 x1 – 2 x2 + x3 ≥ 5

x1 + x2 + 2 x3 ≥ 10

- 2 x1 + 3 x2 - x3 ≥ 2

x1 ≥ 0, x2 ≥ 0.

Par la méthode du simplexe, résoudre le problème dual correspondant et

déterminer la solution optimale du problème primal.

87. Résoudre le programme linéaire :

min z = x1 + 2 x2 +…+ n xn

x1 + x2 + ..+ xi ≥ i ( i = 1,…, n )

xj ≥ 0, j = 1,…, n.

( Indication : considérer le problème dual correspondant)



88. Soit le programme linéaire suivant :

min z = 2 x1 + 3 x2 + x3

x1 + x2 - x3 ≥ 1/2

x2 + x3 ≥ 1

xi ≥ 0, i = 1,…,3

Ecrire et résoudre le programme dual.

Retrouver une solution du problème initial appelé primal en utilisant le théorème

des écarts complémentaires.

89. En utilisant le théorème des écarts complémentaires, vérifier si x = (3, 0, 1, 3) est

une solution optimale des problèmes suivants :

a) max z = - 2 x1 - x2 + x3 + x4

2 x1 + x2 - 3 x3 + x4 = 6

x1 - x2 + 2 x3 - x4 = 2

x1 - 3 x2 - 2 x3 – x4 = - 2

xi ≥ 0, i = 1,…,4.

b) max z = 2 x1 - x2 + 4 x3 - 6 x4

3 x1 - x2 + 2 x4 ≤ 15

x1 + 2 x2 - x3 - 2 x4 ≥ - 4

x2 + 3 x3 – x4 ≥ 0

xi ≥ 0, i = 1,…,4.

c) max z = 2 x1 - x2 + 4 x3 - 6 x4

2 x1 - x3 + 2 x4 = 10

x1 + x2 - x4 = 0

2 x1 - 2 x3 + 3 x4 = 13

xi ≥ 0, i = 1,…,4.

90. Soit le problème linéaire

max. W = ½ x1 + x2

x1 ≤ 2

(P) x1 + x2 ≤ 3

- x1 + x2 ≤ 1

x1 ≥ 0 , x2 ≥ 0 .



a) Déterminer une solution de ce problème.

b) Ecrire le dual de (P). En utilisant les résultats du théorème des écarts

complémentaires, déterminer une solution du dual.

91. On considère le problème de la PL

max z = ( 3 – m )x1 + ( m – 3 ) x2 + x3

x1 + 2 x2 + 3 x3 ≤ 5

2 x1 + x2 + x3 ≤ 7

xi ≥ 0, i = 1,…,3.

a) résoudre ce problème selon les valeurs de « m ».

b) Pour m = 0, déterminer une solution optimale du problème dual si elle existe.

92. Par la méthode duale du simplexe, résoudre le problème suivant :

min z = 2 x1 + x3

x1 + x2 - x3 ≥ 5

x1 - 2 x2 + 4 x3 ≥ 8

xi ≥ 0, i = 1,…,3.

93. a) Soit un couple de problèmes duaux sous forme standard

( I )

min z cx

Ax d

x

==≥

0

et (II)

maxw ud

uA c

u quelconque

=≤

c∈n, x∈n , A : m x n , d∈m, u∈m.

1) Montrer que si x est une solution réalisable de (I) et u est une solution du dual (II)

alors on a : c x ≥ u d.

2) Montrer que si x est une solution réalisable du (I) et u est une solution du dual (II)

et si c x = u d alors x et u sont des solutions optimales respectivement de (I) et (II).

b) Soit un couple de problèmes duaux sous forme canonique

( I )

min z cx

Ax d

x

=≥≥

0

et (II)

maxw ud

uA c

u

=≤≥

0

3) Montrer qu’une condition nécessaire et suffisante pour que x et u soient des

solutions optimales de (I) et (II) est que : u ( A x - d ) = 0 et (c- u A) x = 0.



4) Que deviennent ces conditions si les problèmes sont mis sous la forme

standard ?

5) On appelle « Lagrangien » associé à ces problèmes la fonction des variables x

et u définie par : (x, u) = c x + u d – u A x.

On dit que le couple ( x , u ), x ≥ 0, u ≥ 0, constitue un col ou « point selle » si

pour tout x ≥ 0, u ≥ 0 on a : ( x , u) ≤ ( x , u ) ≤ ( x, u ).

6) Montrer qu’une condition nécessaire et suffisante pour que ( x , u ) soient

deux solutions optimales du problème primal (I) et du dual (II) est que le

couple ( x , u ) constitue le col du Lagrangien ( x, u). La valeur commune

des fonctions objectives de (I) et (II) est égale à ( x , u ).

94. Soit le problème linéaire suivant (P)

max z cx

Ax b

x

=≤≥

0

Montrer que la variation de la valeur optimum de la fonction objective du problème

linéaire pour une variation δb suffisamment faible pour que la base optimale (P) soit

encore la base optimale de (Pδ)

max z cx

Ax b b

x

=≤ +≥

δ

0

est égale à yδ b où y est une

solution optimale du dual de (P).

95. Par la méthode du grand M, résoudre le problème de la programmation linéaire

suivant :

min Z = - 2 x1 - x2 - x3

4 x1 + 6 x2 + 3 x3 ≤ 8

- x1 + 9 x2 - x3 ≥ 3

2 x1 + 3 x2 - 5 x3 ≥ 4

x1 ≥ 0, x2 ≥ 0 et x3 ≥ 0.

96. Résoudre par la méthode du problème augmenté le problème de la programmation

linéaire suivant :

min Z = - x1 - 2 x2

3 x1 + x2 + x3 = 6

x1 + 3 x2 - x4 = 10



x1 ≥ 0,…, x4 ≥ 0

97. Résoudre le problème suivant :

min Z = x1 + x2 - x3 – 2 x5

x1 + 2 x2 + x4 = 3

x3 - 2 x4 = 2

3 x2 - x4 + x5 ≤ 5

x2 + x5 ≥ 3

x1 ≥ 0, x2 ≥ 0, …, x5 ≥ 0.

98. Enoncer l’algorithme de transport.

Résoudre le problème de transport donné par le tableau suivant :

bj

ai

10 8 8 6

12 1 2 3 4

10 4 5 2 3

10 1 3 2 1

Où ai et bj représentent respectivement les quantités d’un produit disponible au site i

et la quantité demandée par le lieu de vente j. Les éléments du tableau sont les coûts

de transport du site i au lieu de vente j. Ecrire le problème dual correspondant.

99. Résoudre le problème de transport donné par le tableau suivant :

bj

ai

10 8 8 6

14 4 2 3 5

11 4 5 2 3

10 1 3 2 1

Où ai et bj représentent respectivement les quantités d’un produit disponible au site i

et la quantité demandée par le lieu de vente j. Les éléments du tableau sont les coûts

de transport du site i au lieu de vente j.



100. Soit un problème de transport donné par le tableau ci dessous :

bj

ai

20 16 16 12

24 2 4 6 8

20 8 10 4 6

20 2 6 4 2

où ai et bj représentent respectivement les quantités d’un produit disponible au site i et

la quantité demandée par le lieu de vente j. Les éléments du tableau sont les coûts de

transport du site i au lieu de vente j.

a. Ecrire le programme linéaire correspondant à ce problème de transport et lui

associer son dual.

b. par la règle du produit minimum, déterminer une solution de base réalisable.

c. par la règle de Houthaker, déterminer une solution de base réalisable.

d. Est-elle optimale ? Sinon déterminer une solution optimale.



Annexe 1 : La méthode Lexicographique

Un vecteur a ∈ n est dit lexicographiquement positif si sa première composante non

nulle est positif ( ou 1-positif ). Un vecteur a ∈ n est 1-supérieur à un vecteur b ∈ n

est si a – b > 0 ( a > b lexicographiquement ). Cette relation définit un ordre total sur

les vecteurs de n( par analogie avec l’ordre dans lequel sont rangés les mots d’un

dictionnaire ).

Etant donné une suite finie de vecteurs de n, on peut définir 1-max ou 1-min de cette

suite finie. Soit le problème (P)

min

,

z cx

Ax b

x b

==

≥ ≥

0 0

On suppose que rang A = rang (A, b) = m. On suppose que A est rangée de façon que

les « m » premières colonnes forment une base initiale AB = ( a1, a2,…, am )

Formons ( b , AB ) =

a a a

a a a

a a a

m

m

m m mm

10 11 1

20 21 2

0 1

....

....

... ... ... ...

....

=

αα

α

1

2

...

m

Avec αi = ( ai0, ai1, …, aim ).

Supposons que chaque αi ( i = 1,…,m) soit l-positif.

La méthode de simplexe est basée sur un changement de base pour améliorer la

fonction objectif.

Si x = = ( a10, a20, …, ai0, …, am0, 0,…,0 ) n’est pas optimale, pour déterminer la

colonne pivot, on utilise { min cj, cj < 0 }= cs

Le critère de sortie à la même forme que la méthode de simplexe, mais le minimum

doit être pris lexicographiquement. α αr

rs a

i

isal

ais

= −

>

min0

On calcule mini I

i

is

a

a∈

0 , I ensemble des indices de vecteurs ( des variables de bases).

Si ce minimum est unique et a lieu pour i = r, on fait sortir ar

si mini I

i

is

a

a∈

0 est atteint en plusieurs points, on calcule mini I

i

is

a

a∈

1

1 , I1 ⊂ I et on répète

l’opération sur Ir avec mini I

ir

isr

a

a∈

.



Si rg(A) = m, deux lignes de A ne peuvent pas être proportionnelles et donc au plus

tard à ( m + 1 ) étapes d’application de cette procédure on a un minimum unique.

Montrons que dans ce nouveau tableau

a) Chaque ligne est l-positive

b) La ligne a augmenté lexicographiquement c’est à dire

a

a

a

a

a

a

a

ai

is

i

is

im

is

in

is

0 1, ,..., ,...

>

a

a

a

a

a

a

a

ar

rs

r

rs

rm

rs

rn

rs

0 1, ,..., ,...

(*)

Si ais > 0 alors pour obtenir la ième ligne du nouveau tableau, il suffit de retrancher

( ar0, ar1, …, ar n ) multiplié par a

ais

rs

de ( ai0, ai1, …, ai n ).

Soit ( ai0, ai1, …, ai n ) - ( ar0, ar1, …, ar n ) x a

ais

rs

> 0.

D’après (*) la ième ligne est l-positive.

Si ais < 0, ( ai0, ai1, …, ai n ) - ( ar0, ar1, …, ar n ) x a

ais

rs

est la somme de deux vecteurs

l-positifs est l-positive.

Pour obtenir la ligne de – z, il faut ajouter v = ( ar0, ar1, …, ar n ) multiplié par a

ais

rs

à

la ligne de – z.

Puisque v est l-positif, - z augmente lexicographiquement.

La ligne de – z sert à ordonner les bases du problème de la programmation linéaire.

Dans le cas de dégénèrescence, la valeur de – z est la somme d’un tableau du

simplexe à un nouveau tableau mais la ligne de – z augmente.



Annexe 2 : Indications sur la résolution de quelques exercices de modélisation

Réponse 01. Soient xi la quantité de P livrée au détaillant Di ( i = 1, 2, 3). Les

contraintes sont:

x1 + x2 + x3 = 24

x2 ≤ 9, x3 ≤ 9

x1 ≥ 2 x2 + 6

x1 ≥ 0, x2 ≥ 0 et x3 ≥ 0.

Minz = 4 x1 + 2 x2 + 3 x3

Réponse 2. Si on note xj le nombre de gâteaux de type Gj, le problème s’écrit :

Maxz = 2 x1 + 5 x2 + 7 x3

x1 + x2 + 2 x3 ≤ 20

x1 + 2 x2 + x3 ≤ 10

2 x1 + x2 + x3 ≤ 20

x1 + 2 x2 ≤ 20

x1 + 2 x2 + 2x3 ≤ 10

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.

Réponse 3. Une plaque de 200 cm de largeur peut être coupée de cinq façons :

1. une plaque de 75 cm et deux plaques de 60 cm. Les déchets seront de 05 cm.

2. une plaque de 110 cm et une plaque de 75 cm. Les déchets seront de 15 cm.

3. une plaque de 110 cm et une plaque de 60 cm. Les déchets seront de 30 cm.

4. trois plaques de 60 cm. Les déchets seront de 20 cm.

5. deux plaques de 75 cm. Les déchets seront de 50 cm.

Soit xi : le nombre de plaques à découper par la façon i, le problème s’écrit :

Min z = 5 x1 + 15 x2 + 30 x3 + 20 x4 + 50 x5

x2 + x3 ≥ 30

x1 + x2 + x5 ≥ 40

2 x1 + x3 + 3 x4 ≥ 15.

x1 ≥ 0, …, x5 ≥ 0.



Réponse 4.

Soit x et y respectivement le nombre d’assiettes de type 1 et du type 2 à offrir.

Le problème est de maximiser la fonction 80 x + 120 y sous les contraintes:

5 x + 3 y ≤ 30

2 x + 3 y ≤ 24

x + 3 y ≤ 18

x ≥ 0 et y ≥ 0.

Réponse 5.

Soient x1 le nombre de bouteilles de type boisson_a et x2 le nombre de bouteilles de

type boisson_b. Le problème est de :

Max z = 3 x1 + 2 x2

2 x1 + x2 ≤ 10 000

x1 + x2 ≤ 8 000

x1 ≤ 4 000

x2 ≤ 7 000

x1 ≥ 0 et x2 ≥ 0.

Réponse 6. Soient x1 et x2 respectivement le nombre d’inspecteurs de 1er et du 2nd

catégorie à affecter à l’inspection. Chaque inspecteur de 1er catégorie inspecte 25 x 8

pièces par jour, soit 200 pièces. S’il commette 2% d’erreur, cela représentera 4 pièces

qui coûteront 4 x 50 DA. Chaque inspecteur de 2nd catégorie inspecte 15 x 8 pièces

par jour, soit 120 pièces. S’il commette 5% d’erreur, cela représentera 6 pièces qui

coûteront 6 x 50 DA. Le problème est de :

Minz = ( 100 x 8 + 200 ) x1 + ( 70 x 8 + 300 ) x2

200 x1 + 120 x2 ≤ 1000

x1 ≤ 12

x2 ≤ 17

x1 ≥ 0, x2 ≥ 0.

Réponse 7. Le problème de transport est un problème particulier de la programmation

linéaire. Sa formulation mathématiques est :



Minz = cij xijj

n

i

m

=

−∑

=∑

1

1

1

ai b jj

n

i

m≥

=

−∑

=∑

1

1

1. Cette équation traduit que la demande doit être satisfaite.

xijj

n

=

−∑

1

1 ≤ ai , i = 1, …, m.

xiji

m

=∑

1= bj, j = 1, …, n - 1.

xij ≥ 0, i = 1,…, m et j = 1,…, n – 1.

ai ≥ 0, i = 1,…, m, bj ≥ 0, j = 1,…, n – 1, cij ≥ 0, i = 1,…, m et j = 1,…, n – 1.

Réponse 8. Il s’écrit, Max z = c j x jj

n

=∑

1

aij x jj

nbi

=∑ ≤

1 i = 1,…, m.

xj ≥ 0, j = 1,…, n.

Réponse 09.

Soient x1 et x2 le nombre de mètres cubes de carburant de type 1 et 2 à produire.

Max z = 6000 x1 + 5000 x2

20 % x1 + 10 % x2 ≤ 9000

20 % x1 + 20 % x2 ≤ 14000

30 % x1 + 10 % x2 ≥ 6000

30 % x1 + 60 % x2 ≥ 18000

x1 ≥ 0, x2 ≥ 0.

Réponse 10. Si x1 , x2, x3 représentent les nombres de pièces de type p1, p2, p3 à

fabriquer, le profit total est: max Z = 50 x1 + 80 x2 + 60 x3

2 x1 + 4 x2 + 3 x3 ≤ 480

6 x1 + 12 x2 + 3 x3 ≤ 600

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.



Réponse 11.

Soient x1, x2 et x3 le nombre de produits à fabriquer respectivement de type A, B et C

Max Z = ( 200- 160) x1 + ( 270 – 210 ) x2 + ( 250 – 220 )x3

x1+ 4 x2 + 2 x3 ≤ 210

x1+ x2 + 4 x3 ≤ 160

2 x1+ 3 x2 + x3 ≤ 210

x1+ 4 x2 + x3 ≤ 205

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0

Réponse 12.

Soient x1, x2 et x3 le nombre de produits à fabriquer respectivement de type A, B et C

Max Z = ( 200- 160) x1 + ( 270 – 210 ) x2 + ( 250 – 220 )x3

x1+ 3 x2 + 2 x3 ≤ 205

0 ≤ x1 ≤ 100

x2 ≥ 30

x2 / 3 ≤ x3

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0

Réponse13. Soient x1, x2 et x3 le nombre de m3 à fabriquer respectivement du 1er , 2 nd

et du 3 ième gaz.

Min Z = 100 x1 + 250 x2 + 200 x3

1700 ≤ 1000 x1+ 2000 x2 + 1500 x3 ≤ 2000

6 x1 + 2 x2 + 3 x3 ≤ 2.8

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0

Réponse 14.

Soit x1 le nombre de pain introduit dans la ration de 100g

x2 le nombre de beurre introduit dans la ration de 100g

x3 le nombre de fromage introduit dans la ration de 100g

x4 le nombre de pois introduit dans la ration de 100g

x5 le nombre d’épinards introduit dans la ration de 100g



Max Z = 3 x1 + 7 x2 + 7 x3 + 5 x4 + 5 x5

10 x1 + 30 x2 + 35 x3 + 20 x4 + 25 x5 ≥ 70

300 x1 + 1800 x2 + 800 x3 + 1500 x4 + 300 x5 ≥ 3000

50 x1 + 400 x2 + 450 x3 + 750 x4 + 120 x5 ≥ 800

4 x1 + 4 x4 + 15 x5 ≥ 12

xi ≥ 0, i = 1,…, 5

Réponse 15. Soit xij le nombre de pièces i à fabriquer sur la machine j. On aura 12

variables. Le problème s’écrit :

Minz = 3x11 + 3x21 + 2x31 + 5x41 + 4x12 + x22 + x32 + 2x42 + 2x13 + 2x23 + 3 x33 + 4 x43

Sous les contraintes :

3x11 + 3x21 + 2x31 + 5x41 ≤ 80

4x12 + x22 + x32 + 2x42 ≤ 30

2x13 + 2x23 + 3 x33 + 4 x43 ≤ 130

3x11 +x12 + x13 = 10

x21 + x22 + x23 = 40

x31 + x32 + x33 = 50

x41 + x42 + x43 = 20

xij ≥ 0, i = 1, …, 4 et j = 1, 2, 3.

Réponse 16. Soient x1 le nombre de bureau A, x2 le nombre de bureau B, x3 le nombre

de bureaux C, x4 le nombre de bureau D à fabriquer.

Max z = 900 x1 + 1800 x2 + 1400 x3 + 450 x4

x1 + 3 x2 + x3 + x4 ≤ 4500

2 x1 + x2 + 2 x3 + x4 ≤ 4000

x2 + 4 x3 + x4 ≤ 3000

xi ≥ 0, i = 1, …, 4.

Réponse 17.

Soit x1 le nombre d’autos à construire et x2 le nombre de camions.

4/3 x1 + 4/3 x2 représente le nombre d’heures de travail dans l’atelier I

½ x1 + 3 x2 représente le « « « « « « I I

8/7 x1 + 5/2 x2 « « « « « « « « I I I


Exercices du Cours de la programmation linéaire donné par le Pr. Ali DERBALA


1) 4 3 4 3 2 200

3 2 200

/ / 1

1 / 2 x1

x x

x

+ =+ =

, x1 = 100 et x2 = 50.

2) 8/7 x 100 + 5/2 x 50 = 239, 28. La production en 1) n’est pas possible.

3) et 4)

x x

x x

x x

1 2 200

1 6 2 400

8 7 1 5 2 2 200

+ ≤+ ≤+ ≤

(I)

(II)

( III)/ /

L’intersection de (I) et (II) donne l’optimum et qui est le point B = ( 128,94; 21,05) et

Z(B) = 188.400. 103 DA.

Réponse 18. Soit xij le nombre de tonnes de métal qui sont acheminés chaque semaine

depuis le port i vers l’usine j ( i = 1, 2 et j = 1, 2, 3). Le programme s’écrit :

minz = 500 x11 + 600 x12 + 700 x13 + 1000 x21 + 900 x22 + 800 x23

x11 + x21 ≥ 400

x12 + x22 ≥ 500

x13 + x23 ≥ 600

x11 + x12 + x13 ≤ 500

x21 + x22 + x23 ≤ 300

xij ≥ 0 ( i = 1, 2 et j = 1, 2, 3 )

Réponse 19.

Réponse 20. Soient xij : le nombre de tonnes de déchets à transporter de la ville i ( i =

1, 2 ) à l’incinérateur j ( j = 1, 2 ) et yjk le nombre de tonnes de débris à transporter de

l’incinérateur j au terrain-vague k ( k = 1, 2 )

min Z = 40 (x11 + x21 ) + 30 (x12 + x22 ) + 3 ( 30 x11 + 5 x12 + 36 x21 + 42 x22 + 5 y11+

9 y12 + 8 y21 + 6 y22 )

x11 + x12 = 500

x21 + x22 = 400

y11+ y12 = 0.2 ( x11 + x21 )

y21 + y22 = 0.2 (x12 + x22 )

x11 + x21 ≤ 500

x12 + x22 ≤ 500


y11+ y21 ≤ 200

y12 + y22 ≤ 200

xij ≥ 0, yjk ≥ 0 ( i, j, k = 1, 2 )

La programmation linéaire est notamment très utilisée dans l’industrie du pétrole.

Réponse 21. Appelons respectivement x1 , x2 et x3 les quantités de brut, en millions

de tonnes, traitées annuellement par la raffinerie. Le tableau des rendements ci-dessus

montre que la production de gaz et gaz liquéfiés correspondant à 1 million de tonnes

de pétrole brut atteint :

0.02 million de tonnes quand on traite du brut n°1

0.06 million de tonnes quand on traite du brut n°3

Comme la fabrication de cette catégorie de produit est limitée à 300 000 tonnes, soit

0.3 million de tonnes, la contrainte correspondante s’écrit :

0.2 x1 + 0.06 x3 ≤ 0.30

Soit encore :

x1 + 3 x3 ≤ 15

On obtient de même :

- pour la limitation de production d’essences :

0.20 x1 + 0.25 x2 + 0.30 x3 ≤ 1.05

soit encore :

4 x1 + 5 x2 + 6 x3 ≤ 21

- pour la limitation de production de pétrole :

0.08 x1 + 0.04 x3 ≤ 0.18

soit encore :

4 x1 + 2 x3 ≤ 9

- pour la limitation de production de gasoil :

0.40 x1 + 0.25 x2 + 0.30 x3 ≤ 1.35

qui est équivalent à l’équation : 8 x1 + 5 x2 + 6 x3 ≤ 27

- pour la limitation de production de fuel-oil :

0.30 x1 + 0.50 x2 + 0.30 x3 ≤ 1.80

Soit encore :

3 x1 + 5 x2 + 3 x3 ≤ 18.



Le problème est de maximiser le bénéfice en millions de DA, qui s’écrit :

Max z = 40 x1 + 50 x2 + 60 x3

Sous les contraintes :

x1 + 3 x3 ≤ 15

4 x1 + 5 x2 + 6 x3 ≤ 21

4 x1 + 2 x3 ≤ 9

8 x1 + 5 x2 + 6 x3 ≤ 27

3 x1 + 5 x2 + 3 x3 ≤ 18

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.

Réponse 22.

1) a) Pour assurer une production hebdomadaire de 400 téléviseurs et 600

magnétoscopes il faut : 400 x 0,5 + 600 x 1 = 800 heures de main d’œuvre.

L’entreprise dispose de 20 x 39 = 780 heures de main d’œuvre. Elle ne dispose

donc pas de la main d’œuvre suffisante pour assurer cette production.

b) Une production de 600 téléviseurs et 400 magnétoscopes nécessite

3000 x 600 + 200 x 400 = 1 880 000 DA de composants.

Comme elle ne peut consacrer que 256 000 DA par semaine au financement de ses

approvisionnements en composants, elle ne peut donc assurer cette production.

c)

3000 200 256000

0 5 780

600600

0 0

x y

x y

xy

x y

+ ≤+ ≤≤

≤≥ ≥

,

,

⇔

3 2 256

0 5 780

600600

0 0

x y

x y

xy

x y

+ ≤+ ≤≤

≤≥ ≥

,

,

La représentation est facile.

2) Le bénéfice est 1500 x + 2000y. Si le bénéfice réalisé est 1900 000 DA, alors

1500 x + 2000 y = 1900 000, soit 3 x + 4 y = 3800.

Les couples qui réalisent cette équation sont à l’extérieur du polyèdre de réalisabilité.

L’entreprise ne peut assurer une telle production. ( 400, 570 ) ; ( 450, 550) sont les

points qui assurent un bénéfice supérieur ou égal à 1700 000 DA.



Réponse 23.

Si le gérant achète x lots A et y lots B ( x ≥ 0, y ≥ 0 )

Le nombre de draps de bain est 2 x + 3 y. Il doit être supérieur ou égale à 90 d’où la

condition 2 x + 3 y ≥ 90.

Le nombre de serviettes est 4 x + 12 y. Il doit être supérieur ou égal à 240 d’où la

condition 4 x + 12 y ≥ 240.

Le nombre de gants de toilette est 8 x + 6 y. Il doit être supérieur ou égal à 240 d’où la

condition 8 x + 6 y ≥ 240. Le système des contraintes est donc:

2 3 90

4 12 240

8 6 240

0

x y

x y

x y

x et

+ ≥+ ≥+ ≥≥ ≥

y 0

équivalent à

2 3 90

3 60

4 3 120

0

x y

x y

x y

x et

+ ≥+ ≥+ ≥≥ ≥

y 0

Réponse 24. Définissons les variables de décision par :

X1 : le nombre de verres à café produits pendant la semaine à venir ;

X2 : le nombre de verres à thé produits pendant la semaine à venir ;

X3 : le nombre de verres à eau produits pendant la semaine à venir ;

Le plan de production maximisant le chiffre d'affaires est solution du programme

linéaire : Max z = 8 X1 + 6 X2 + 15 X3

4 X1 + 2 X2 + 12 X3 ≤ 3000

2 X1 + X2 + 4 X3 ≤ 1200

0,1 X1 + 0,15 X2 + 0,1 X3 ≤ 100

X1 ≥ 0, X2 ≥ 0 et X3 ≥ 0


Documents

75. Un plombier connaît la disposition de trois tuyaux sous des