Feuille d’exercices N° 1

Exercice N° 1 :
x1, 2x2 – x3 = 1
(P) 2x1 – x2 – 5x3 ≤ 2
x1 , x 2 ≥ 0
x1 + 3x2 – 5x3 ≥ 1
x1 + 2x2 + 3x3 = Z(Max)

Forme canonique :
x1 + 2x2 – x3 ≤ 1
(P) -x1 – 2x2 + x3 ≤ 1
x1, x2 ≥ 0
2x1 + x2 – 5x3 ≤ 2
3x’3, x’’3 ≥ 0 / x3 = x’3 – x’’3
-x1 – 3x2 + 5x3 ≤ -1
x1 + 2x2 + 3x3 = Z(Max)

Forme normale :

 x1 x 2 x' 3 x' ' 3 

  1 
1 2 − 1 1   
 Ax ≤ b  − 1
(P)  , A =  − 1 − 21 − 1  ;b=
 2  ; c = (1, 2, 3, -3)
 
c x = Z (Max )  2 −1 − 55   
 − 1
   
 − 1− 3 5 − 5 

Forme standard
x1 + 2x2 – x3 = 1
(P) 2x1 - x2 – 5x3 + e4 = 2 x1, x2 ≥ 0 ; e1, e2 ≥ 0
x1 + 3x2 - 5x3 – e2 =1 3x’3, x’’3 ≥ 0 / x3 = x’3 – x’’3
x1 + 2x2 + 3x3 = Z(Max)

Forme normale

 x1 x 2 x' 3 x' ' 3 e1 e2 

  1 
 A' x = b' 1 2 − 1 1 0 0   
(P)  , A’ =   ; b’ =  2  ; c = (1, 2, 3, -3,0, 0)
c' x = Z ( Max ) 
2 − 1− 5 5 1 0
 1 
1 3 − 5 5 0 − 1   
 

1
 2  −1 
   
A² : On prend la 2ème colonne de A : A² =  − 1 ; A3 =  − 5
3   − 5
   
J = (2, 4, 5)

2 −1 1
 
A = −1
J
−5 5
3 −5 5 


1 2 −1 1 0 0 
I = (1, 3) ; AI =  
1 3 −5 5 0 −1 

2 1 0 
AIJ =  
3 5 0 

Exercice 2 :
30%Cu

Alliage final 30% Zn ; 9 alliages sur machine
40% Fe

Qi : la quantité de l’alliage i (1 ≤ i ≤ 9) nécessaire pour la fabrication de l’alliage final.
Contrainte de cuivre 0.1Q1 + 0.1Q2 + 0.4Q3 + 0.6Q4 + 0.3Q5 + 0.3Q6 + 0.3Q7 + 0.5Q8 + 0.2Q9
Contrainte de Zinc 0.1Q1 + 0.3Q2 + 0.5Q3 + 0.3Q4 + 0.3Q5 + 0.4Q6 + 0.2Q7 + 0.4Q8 + 0.3Q9
Contrainte de Fer 0.8Q1 + 0.6Q2 + 0.1Q3 + 0.1Q4 + 0.4Q5 + 0.3Q6 + 0.5Q7 + 0.1Q8 + 0.5Q9
La fct objective 4Q1 + 5Q2 + 6Q3 + 6Q4 + 8Q5 + 7Q7 + 6Q8 + 4Q9 = Z(Max)

Exercice 3
 A = 20 H
Parcelles 
 B = 40 H
xiA : quantité de céréale de sorte i cultivée sur parcelle A

xiB : quantité de céréale de sorte i cultivée sur parcelle B

xi = xiA + xiB : la quantité totale cultivée sur A ou B ; xi ≥ 0 et i = 1 …..6 (1 ≤ i ≤ 6)

2
La contrainte de parcelle A :
0.01x1A + 0.015 x 2A + 0.01x3A + 0.008 x 4A + 0.025 x5A + 0.02 x6A ≤ 20
La contrainte de parcelle B :
0.01x1B + 0.017 x 2B + 0.012 x3B + 0.01x 4B + 0.03 x5B + 0.017 x6B ≤ 40
La contrainte d’eau :
60x1 + 80 x2 + 50x3 + 70 x4 + 107x5 + 90x6 ≤ 400 000
Fonction objective

∑ (x )
6
24x1 + 31x2 + 14 x3 + 18x4 + 61x5 + 47 x6 = Z(Max) = i
A
+ xiB
i =1

Exercice 4
 PL1 = 40T / jours
Pétroles 
 PL2 = 70T / jours

TPL1 = 104
Taux d’octobre 
TPL2 = 94
T = (2*104) + (3*94) /5
QPL1 *104 + QPL2 94
T=
QPL1 + QPL2
Kérosène : si T ≥ 102 ; PK = 16D
Super : si T ≥ 96 ; PS = 10D
x1K : quantité de PL1 en kérosène

x1S : quantité de PL1 en Super

x 2K : quantité de PL2 en kérosène

x 2S : quantité de PL2 en Super

Tel que :
x1K + x1S ≤ 40

x 2K + x 2S ≤ 70

104 x1K + 94 x 2K ≥ 102 ⇒ 4 x1S − x 2S ≥ 0

104 x1S + 94 x 2S ≥ 96 ⇒ x1K − x 2K ≥ 0

3
16( x1K + x 2K ) + 10( x1S + x 2S ) = Z ( Max )

Exercice 5 :
T1 → 40
T → 60
 2
4 modèles : 
T3 → 80
T4 → 100

xi : nombre de poste de Ti ; 1 ≤ i ≤ 4
2 ateliers : Montage → 6000h/mois
Test → 1500h/mois
1 Transformateur → poste → 450 transformateurs
 x1 + x 2 + x3 + x 4 ≤ 450

 x3 + x 4 ≤ 300

8 x1 + 10 x 2 + 4 x3 + 5 x 4 ≤ 6000 ; xi ≥ 0 tel que 1 ≤ i ≤ 4
2 x + 2 x + 4 x + 5 x ≤ 1500
 1 2 3 4

40 x1 + 60 x 2 + 80 x3 + 100 x 4 = Z ( Max )

Exercice 6 :
xi : la quantité de vêtement i ; 1 ≤ i ≤ 4
La contrainte de coupe :
x1 + 3x2 + 5.5x3 + 5x4 ≤ 2000
la contrainte de couture :
4x1 + 6x2 + 7x3 + 10x4 ≤ 3000
La fonction objective :
1.2x1 + 2x2 + 3x3 + 4x4 = Z(Max)
Formulation :
 x1 + 3 x 2 + 5.5 x3 + 5 x 4 ≤ 2000

( P)4 x1 + 6 x 2 + 7 x3 + 10 x 4 ≤ 3000 ; xi ≥ 0 ; 1 ≤ i ≤ 4
1.2 x + 2 x + 3 x + 4 x = Z
 1 2 3 4 ( Max )

Exercice 8 :
 Ax = b
 ; αi ≤ x j ≤ β j ; j = 1,2,…. n
C x = Z (Max )

4
  Ax = b  Ax = b
x ≥ α x ≥ α
 j j 
⇔ j = 1,2,……n ⇔
x j ≤ β j x ≤ β
Cx = Z Cx = Z (Max )
 (Max )

x’ , x’’ ≥ 0 tel que

 Ax ' − Ax '' = b
 x '− x ' ' ≥ α

⇔ ; x’, x’’ ≥ 0
 x '− x ' ' ≤ β
Cx'−Cx' ' = Z ( Max )

Exercice 9 :
 Ax + uϑ = b
 ;x≥0
Cx − ∑ ϑi = Z (Max )
Soient
ϑ ' = ϑ
ϑ ' = sup(0,ϑ ) si ϑ ≥ 0 
ϑ ' ' = 0
ϑ ' = 0
ϑ ' ' = inf(0,ϑ ) si ϑ ≤ 0 
ϑ ' ' = −ϑ
ϑ = ϑ '−ϑ ' '
ϑ + ϑ ' ? pour chercher la valeur absolue de ϑ
ϑ '+ϑ " = ϑ
a
(ϑ '+ϑ" = −ϑ ) x(−1)
Donc :
ϑ = ϑ '−ϑ"

 ϑ = ϑ '+ϑ "
 Ax + u (ϑ '−ϑ" )

Cx − ∑(ϑ '+ϑ" ) = Z ( Max )

5
 Feuille d’exercices N° 2
Dualité

Exercice 1 :
Rappel du cours
Maximiser Minimiser
Matrices de contraintes de format (m, n) Transposée de la matrice des contraintes de
format (n, m)
Second membres Coefs de la fonction objective
Coefs de la fonction objective Second membre
Nombre de contraintes Nombre de variable principale
ième contrainte « ≤ » ième variable ≥ 0
ième contrainte « ≥ » ième variable ≤ 0
ième contrainte « = » ième variable de signé équation
Nombre de variables principales Nombre de contraintes
jème variable ≥ 0 jème contrainte « ≥ »
jème variable ≤ 0 jème contrainte « ≤ »
jème variable acque jème contrainte « = »

3 x1 + x 2 + 2 x3 = 4
 x − 2 x + 3x ≤ 1
 1 2 3
( P) , x1 , x 2 ≥ 0
2 x1 + x 2 − x3 ≥ 2
3 x1 + 4 x 2 + 2 x3 = Z ( Min )


3 y1 + y 2 + 2 y 3 ≤ 3
y − 2y + y ≤ 4
 1 2 3
D
2 y1 + 3 y 2 − y 3 = 2
4 y1 + y 2 + 2 y 3 = W( Max )


6
Exercice 2 :
 Ax ≤ b  yA ≥ c
( P) x≥0 ( D) y≥0
Cx = Z ( Max ) Yb = W( Min )

 Ax ≤ b
( P) x≥0
Cx = Z ( Max )
a)
 Ax + y1 = b
( P) ; x ≥ 0 et y1 ≥ 0
Cx = Z ( Max )
b)
(P) primal réalisable = b ≥ 0
 Ax ≤ b
( P) x≥0
Cx = Z ( Max )
A.O ≤ b → b≥0
(P) dual réalisable
c ≤ 0
⇒
x ≥ 0
Donc Cx ≤ 0
Donc on a Cx ≤ 0 donc le max de Cx = 0
La solution optimale est x0 = 0
c)
(P) primal réalisable
(P) possède au moins une solution réalisable
(D) dual réalisable
(D) possède au moins une solution réalisable
d)
on a
br < 0 et Ar > 0
 Ar ≥ 0
 ⇒ Arx ≥ 0
x ≥ 0
(P) n’admet pas de solution.

7
Exercice 3 :
2 x1 + x 2 ≤ 6
x − x ≤ 1
 1 2
( P) ; x1 , x 2 ≥ 0
 x1 + x 2 ≤ 3
3 x1 + 2 x 2 = Z ( Max )

a)
2 y1 + y 2 + y 3 ≥ 3

( D) y1 − y 2 + y 3 ≥ 2 ; y1, y2, y3 ≥ 0
6 y + y + y = W
 1 2 3 ( Min )

b)
x1 = 2 , x2 = 1 5
y1 = 0 ; y2 = ½ ; y3 =
2x2+1=5≤6 2

2–1=1≤1 3≥3

2–1=3≤3 2≥2

6 + 2 = 8 = Z(Max) 1 + 15
= 8 = W( Min )
2
x1 = 2 , x2 = 1
5
la solution réalisable y1 = 0 ; y2 = ½ ; y3 =
2
solution réalisable
On a L = W = 8
Donc : x0 = (x1, x2) est une solution optimal de (P)
y0 = (y1, y2) est une solution optimal de (D)
D’après le corollaire le cours

Exercice 4 :
A B C D
1 Kg H 0.1 0 .01 0.2
1 Kg N 0 0.1 0.2 0.1

8
 
0.1x1 ≥ 0.4( I )

0.1x 2 ≥ 0.6( II )

( P)0.1x1 + 0.2 x 2 ≥ 2( III )
0.2 x + 0.1x ≥ 0.1(VI )
 1 2

 1
 x1 + 2 x 2 = Z ( Min )

X1 + ½ x2 = cte → dte // à (IV)

0.1 y1 + 0.1 y 3 + 0.2 y 4 ≤ 1

( D)0.1 y 2 + 0.2 y 3 + 0.1 y 4 ≤ 0.5
0.4 y + 0.6 y + 2 y + 1.7 y = W
 1 2 3 4 ( Max )

b) Résolution graphique :

c) Variable yi, i = (A,B,C,D)

fonction objective :
0.4yA + 0.6yB + 2yC + 1.7yD = Z(Max)
Contraintes :
0.1y A + 0.1y C + 0.2 y D ≤ 1
 ; y0 ≥ 0
0.1y B + 0.2 yC + 0.1 y D ≤ 0.5

9
d) A B C D
(0, 0, 0, 5) → 0 x 0.4 + 0 x 0.6 + 0 x 2 + 5 x 1.7 = 8.5 = W
C’est la solution optimale
e) la même solution trouvée graphiquement.

Exercice 5 :
Minimiser S sous les contraintes suivantes :
 n
∑ x j = 1
 j = 1
 Ai X j ≤ S

 X ≥ 0


σ + a11 y1 + a 21 y 2 + .......... + a m1 y m ≤ 0

σ + a12 y1 + a 22 y 2 + .......... + a m 2 y m ≤ 0

σ + a1n y1 + a 2 n y 2 + .......... + a mn y m ≤ 0
− y − y ........................... y = 1
 1 2 m

W( Max ) = σ

On pose y’i = - yi
σ − a11 y '1 − a 21 y 2 − .......... − a m1 y ' m ≤ 0

σ − a12 y '1 − a 22 y ' 2 −........... − a m 2 y ' m ≤ 0
 y' ≥ 0
σ − a1n y '1 − a 2 n y ' 2 −........... − a mn y ' m ≤ 0 ;
 y ' + y ' +............................ + y ' = 1 σ ≤0
 1 2 m

W( Max ) = σ

Exercice 6 :
 Ax ≤ b
( PS ) ; x≥0
t A x = Z ( Max )
t A y ≥ t (t b ) = b
( D) ;y ≥0
t b y = W( Min )
Soit x0 solution de (PS)
Z = tbx0 = W Donc x0 est une solution optimale.

10
 Feuille d’exercice n° 3

Résolution des systèmes linéaires

Bases et solution de bases

Exercice 1 :
rg (M) ≤ min (3.5)
les lignes de la matrice M soit linéairement indépendantes, alors rg(M) = 3

autres méthodes :
2 0 4 1 − 5
 
M = 0 1 3 1 9 
1 1 5 1 8 

L1 ← L1 – 2L3
0 −2 −6 −1 − 21
 
0 1 3 1 9 
1 1 5 1 8 

L3 ← L3 – L2
0 −2 −6 −1 − 21
 
0 1 3 1 9 
1 0 2 0 − 1 

L1 ← L1 + 2L2
0 0 0 1 − 3
 
0 1 3 1 9 
1 0 2 0 − 1 

L2 ← L2 – L1
0 0 0 1 − 3
 
0 1 3 0 12 
1 0 2 0 − 1 

Rg(M) = 3

11
Exercice 2 :
1 2 − 3 1 0 0
   
M = 0 2 7  I = 0 1 0
−1 −3 0  0 0 1 
 

L3 ← L3 + L1
1 2 − 3 1 0 0
   
0 2 7  P1  0 1 0
0 −1 − 3  1 0 1 
 

L2 ← ½ L2

−3 0
1 2  1 0
 7   1 
0 1 0 0
0 2  0 2
 −1   1 
− 3  0

L3 ← L2 + L3
− 3 0

1 2 7  1 1 0
  
0 1 2  0 2 0
0  0
 0 1   1 1 

2  2

L1 ← L1 - 2L2
− 10  −1

1 0 7  1 1 0
  
0 1 2  0 2 0
0  0
 0 1   1 1 

2  2

12
L3 ← 2L3
− 10 
1 0  1 0 0
 7   
0 1 0 1 0
0 2  0
 0   0 2 
1 

L1 ← L1 + 10L3
0
1 0  1 0 20 
 7  
0 1 0 1 0 
0 2 0
 0   0 2 
1 

7
L2 ← L2 + L3
2
1 0 0 1 0 20 
   
0 1 0 0 1 − 7  = P3
0 0 1  0 0 2 
 

M-1 = P3 x P2 x P1

Exercice 3 :
La base J = (1, 2, 3)
 x1 + x 2 + x3 + 10 x 4 + 2 x5 = 10

 x1 + x 2 − x3 + x 4 + x5 = 6
2 x + 3x − 2 x + 3x + 10 x = 17
 1 2 3 4 5

x1 x2 x3 x4 x5 b
1 1 1 10 2 10 
 
1 1 −1 1 1 6  J = (1,2,3)
2 3 −2 3 10 17 

Algorithme pivotage
M est matrice m x n tq M rs ≠ 0

13
  1 
θ1  r , 
 M rs 
Pour i de 1 à m ; i ≠ r, faire
Li ← Li – MiLr ← θ 2 (r, i, -Mi)
Fin
1 1 1 10 2  10 
   
0 0 −2 −9 1  4 
0 1 −4 − 17 − 6   − 3
  

10 2
1 1 1  10 
 9 1  
0 0 1 2 
0 2 2  − 3
 1 −1   
− 17 6

11 3

1 1 1 2 2 8 
 9 1  
0 0 1 2 
0 2 2   − 3
 1 −4  
− 17 6



11 3

1 1 1 2 2 8 
 9 1  
0 0 1  2
0 2 2  5
 1 0  
1 8



9 − 13 

1 0 0 2 2  3
 9 1   
0 0 1  2
0 2 2  5
 1 0  
1 8 



X4 = x5 = 0

14
  x1 = 3

⇒  x2 = 5
x = 2
 3

Exercice 4 :
1 1 1 10 2  10 
   
1 1 −1 1 1  6  ; j = (1, 2, 3)
2 3 −2 3 10  17 
  

r=1
θ1 (1,1) 1 1 1 10 2  10 
   
θ 2 (1,2,−1) ⇒ 0 0 −2 −9 − 1  − 4
θ 3 (1,3,−2) 0 1 −4 − 17 6  − 3
  

r=3
5 23  37 
1 7   
θ1 (3,− ) 4 4   4 
4 1 0 2 
 1 1  5
θ 2 (3,1,−1) ⇒ 0 − 0 − −4 − 2 
0 2 2   
θ 3 (3,2,2)  1 6
1 17 −  3 
− 4  
4 4 4 

r=2
9 13 
θ1 (2,−2) − 
1 0 0 2 2 3
1   
θ 2 (2,3, ) ⇒ 0 1 0 1 8  5
4 0   2
 0 1 9 1   
5 
θ 3 (2,12 − ) 2 2 
4

 9 13
 x1 + 2 x 4 − 2 x5 = 3

 x 2 + x 4 + 8 x5 = 5
 9 1
 x3 + x 4 + x5 = 2
 2 2

15
J = (1,2,3)
 x 4 = x5 = 0
x = 3
 1

 x2 = 5
 x3 = 2

Exercice 4 :
 x1 + x 2 + x3 ≤ 550(1)
 x + x + x ≤ 350(2)
 4 5 6

 x1 + x 4 ≥ 400(3)
 x + x ≥ 300(4)
 2 5

 x3 + x6 ≥ 200(5)
6
(3) + (4) + (5) ⇒ ∑ x1 ≥ 900
i =1

6
Donc : ∑x
i =1
1 = 900

(1) , (2) , (6)


 x + x + x ≤ 550 6
 1 2 3 ∑ xi ≤ 900
 i =1
 x 4 + x5 + x 6 ≤ 350 ⇒  6 absurde alors x1 + x2 + x3 = 550
6  x = 900
∑ x1 = 900 ∑
i =1
i

 i =1

 x1 + x 2 + x3 = 550
 x + x + x = 350
 4 5 6

 x1 + x 4 = 400
 ; x1 ≥ 0
 x 2 + x5 = 300
 x3 + x6 = 200

5 x1 + 6 x 2 + 3 x3 + 3 x 4 + 5 x5 + 4 x6 = Z ( Max )

b) N’importe quelle équation peut être considérée comme redondante

en effet :
(1) = (3) + (4) + (5) – (2)
(2) = (3) + (4) + (5) – (1)
On considère l’équation (2) une équation redondante.

16
c) J = (3,4,5,6) ⇒ x1 = x2 = 0
Écrivant les éléments de la base J en fonction des éléments hors base.
 x3 = 550 − x1 − x 2  x3 = 550
x = 400 − x1 x = 400
 4  4
 ⇒ 
 x5 = 300 − x 2  x5 = 300
 x6 = 200 − x3  x6 = 200 − 500 = −350 p 0

A xi ≥ 0 et on a x6 = - 350 < 0
La base n’est pas réalisable.
J = (1,2,5,6)
 x 2 = 150  x1 = 400
 x = 400  x = 200
 1  6
 ⇒ x3 = x 4 = 0 ⇒ 
 x5 = 150  x5 = 300 − x 2
 x6 = 200  x 2 = 550 − x1

d)
0 0 0 1 1 1 350 
 
1 0 0 1 0 0 400 
0 1 0 0 1 0 300 
 
0 0 1 0 0 1 200 
5 6 3 3 5 4 70 

on considère ici l’équation (1) est redondante

 x1 + 5 x 2 + 4 x3 ≤ 23

( P)2 x1 + 6 x 2 + 5 x3 ≥ 28 ; x1 , x 2 , x3 ≥ 0
4 x + 7 x + 6 x = Z
 1 2 3 ( Min )

a)
 y1 + y 2 ≤ 4
5 y + 6 y ≤ 7
 1 2 y1 ≤ 0
( D) ;
4 y1 + 5 y 2 ≤ 6 y2 ≥ 0
23 y1 + 28 y 2 = W( Max )


17
b) Mettre (P) sous forme standard :
 x1 + 5 x 2 + 4 x3 + x 4 = 23
 x1 , x 2 , x3 ≥ 0
2 x1 + 6 x 2 + 5 x3 − x5 = 28
4 x + 7 x + 6 x = Z x 4 , x5 ≥ 0
 1 2 3 ( Min )

c) J = (4,1)
1 5 4 1 0 23 
 
2 6 5 0 −1 28 
4 7 6 0 0 0 

1
θ1 (1, ) ; θ 2 (2,1,−1) ; θ 3 (2,3,−4)
2
3 1
0 2 2 1 2 9 
 5 1 
1 3 0 − 14 
0 2 2
 −5 0 − 56 
−4 2

La solution :
 x 2 = x3 = x5 = 0

 x4 = 9
 x = 14
 1
La base est réalisable.

Exercice 6 :
4 x1 + 4 x 2 + 4 x3 + x 4 ≤ 24

( P)8 x1 + 6 x 2 + 4 x3 + 3 x 4 ≤ 26 ; xi ≥ 0
5 x + x + 6 x + 2 x = Z
 1 2 3 4 ( Max )

a)
4 x1 + 4 x 2 + 4 x3 + x 4 + x5 = 24

8 x1 + 6 x 2 + 4 x3 + 3 x 4 + x6 = 26 ; xi ≥ 0
5 x + x + 6 x + 2 x = Z
 1 2 3 4 ( Max )

18
b) J = (……………..)
1
L1 ← L1
4 4 4 1 1 0 24  4
 
8 6 4 3 0 1 36  L2 ← L2 − 4 L1
5 1 6 2 0 0 Z  L3 ← L3 − 6 L1


L2
1 1 L2 ←
1 1 1 0 6  2
 4 4  1
4 2 0 2 −1 1 12  L1 ← L1 − L2
 −1 4
 −5 0 1 3 0 Z − 36 
− 1
2 2 L3 ← L3 − L2
2

3 1
1 3 − 9 
 1 0 8 8 
2 4
1 1
2 
2 1 0 1 − 6 
 2 2 
 − 2 −
1 0 0
5 1
Z − 39 

 2 − − 
4 4

1 3 3 1 9
 2 x1 + 4 x 2 + x3 + 8 x5 − 8 x6 = 2

 1 1
2 x1 + x 2 + x 4 − x5 + x6 = 6 ; xi ≥ 0
 2 2
 11 5 1
− 2 x1 − 2 x 2 − 4 x5 − 4 x6 = Z − 39


La solution :
 x1 = x 2 = x5 = x6 = 0

 9
 x3 = ⇒ Z = 39
 2
 4
x = 6

⇒ J est réalisable.
⇒ J est optimale car Z est à maximiser et le vecteur coût est négatif.

3) 24 → 26 : J = (3,4) ⇒ x1 = x 2 = x5 = x6 = 0

19
 4 x3 + x 4 = 26 (1)
⇒ 
4 x3 + 3x 4 = 36 (2)

21
(2) – (1) 2 x 4 = 10 ⇒ x 4 = 5 et x3 =
4
21 83 5
Z =6x +2 x 5 = = 39 +
4 2 2
5
Le projet a augmenté de
2
4) 24 → 44
4 x3 + x 4 = 44
 ⇒ 2 x 4 = −8 ⇒ x 4 = −4
4 x3 + 3x 4 = 36
J n’est pas réalisable.

Exercice : 5
2 x1 + x 2 ≤ 4
4 x − 3 x ≤ 2
 1
⇒ x1 − 3 x 2 + 3 x3 ≤ 14
2

 − 3 x1 + 2 x2 ≤ 3
 xi , x 2i , x3 ≥ 0

x3 variable d’écart de la 1ère contrainte

2 x1 + x 2 + x3 = 4
4 x − 3 x + x = 2
 1
xi ≥ 0
2 4

− 3 x1 + 2 x 2 + x5 = 3
 x1 − 3 x1 + 3 x3 = Z ( Max )


x1 x2 x3 x4 x5 b

2 1 1 0 0 4
4 -3 0 1 0 2
-3 2 0 0 1 3
1 -3 3 0 0 0

2 1 1 0 0 4
4 -3 0 1 0 2

20
 -3 2 0 0 1 3
-5 -6 0 0 0 -12

xi ci ≤ 0 J est optimale et Z = 12 < 14

x1 − 3 x 2 + 3 x3 ≤ 14

Exercice 6 :
2 x + y + 3 = 3
− 2 x + y + b = 1


x + w = 1
 x + y = Z ( Max )

x y z t w b
2 1 1 0 0 3
-2 1 0 1 0 1
1 0 0 0 1 1
1 1 0 0 0 0

0 1 1 0 -2 1
0 1 0 1 2 3
1 0 0 0 1 1
0 1 0 0 -1 -1

0 1 1 0 -2 1
0 0 -1 1 4 2
1 0 0 0 1 3
0 0 -1 0 1 -2

21
 Correction du TD 5
Exercice 1 :
 x1 + x 2 ≥ 2

( P)− x1 + x 2 ≥ 3 ; x1 , x 2 ≥ 0
3 x + 2 x = Z
 1 2 ( Min )

La phase I :
 x1 + x 2 − x3 = 2
− x + x − x = 3
 1
xi ≥ 0
2 4
( PS ) ; ; i = 1,2,3,4
x
 1 − x 5 = 4
3 x1 + 2 x 2 = Z ( Max )


 x1 + x 2 − x3 + v1 = 2

− x1 + x 2 − x 4 + v 2 = 3

( PA) x1 − x5 + v3 = 4
− 3 x − 2 x + Z = 0
 1 2

− x1 − 2 x 2 + x3 + x 4 + x5 = W( Min ) − 9

x1 x2 x3 x4 x5 v1 v2 v3 Z b

1 1 -1 0 0 1 0 0 0 2
-1 1 0 -1 0 0 1 0 0 3
1 0 0 0 -1 0 0 1 0 4
-3 -2 0 0 0 0 0 0 1 0
-1 -2* 1 1 1 0 0 0 0 -9
1 1 -1 0 0 0 0 0 2
-2 0 1 -1 0 1 0 0 1
1 0 0 0 -1 0 1 0 4
-1 0 -2 0 0 0 0 1 4
1 0 -1* 1 1 0 0 0 -5
-1 1 0 -1 0 0 0 3
-2 0 1 -1 0 1 0 4
-5 0 0 -2 0 0 1 6
-1* 0 0 0 1 0 0 -4

22
 0 1 0 -1 -1 0 7
0 0 1 -1 -2 0 9
1 0 0 0 -1 0 4
0 0 0 -2 -5 1 26
0 0 0 0 0 0 0

W = 0 donc le système admet une solution réalisable.

Exercice 2 :
 x1 + x 2 + 2 x3 ≤ 6

( P)2 x1 − x 2 + 2 x3 ≥ 2 ; x1 , x 2 , x3 ≥ 0
2 x + x = Z
 2 3 ( Max )

 x1 + x 2 + x3 + x 4 = 6
2 x − x + 2 x − x + v = 2
 1
xi ≥ 0
2 3 5 1
( PS ) ;
− 2 x 2 − x 3 + Z = 0
− 2 x1 + x 2 − 2 x3 + x5 = W( Min ) − 2


x1 x2 x3 x4 x5 v1 Z b

1 1 2 1 0 0 0 6
2 -1 2 0 -1 1 0 2
0 -2 -1 0 0 0 1 0
-2* 1 -2 0 1 0 0 -2
0 3 1 1 ½ 0 5
2
1 -½ 1 0 -½ 0 1
0 -2 -1 0 0 1 0
0 0 0 0 0 0 0

23
Phase II :
x1 x2 x3 x4 x5 b

0 3 1 1 ½ 5
2
1 -½ 1 0 -½ 1
0 -2 -1 0 0 0
0 1 2 2 1 10
3 3 3 3
1 0 4 1 1 8
-
3 3 3 3
0 0 1 4 2 20
- - - -
3 3 3 3

C ≤ 0 et Z à minimiser
J = (2 , 1) est une solution de base optimale.
Le système est écrit sous forme C% à une base ep. J = (2 , 1)
 10
 x2 = 3

 8
⇒  x1 =
 3
 20
Z = 3


Exercice 3 :
 x'1 + x 2 + x3 − x 4 = 1
 − 2 x ' +7 x + x + 8 x = 7 x1 ≤ 0

x 2 , x3 , x 4 ≥ 0
1 2 3 4
( P) ;
 − 2 x ' + 10 x + 2 x + 10 x 4 = 10
on pose x'1 = − x1
1 2 3
− 2 x'1 +18 x 2 + 5 x3 + 14 x 4 = Z ( Max )


 x'1 + x 2 + x3 − x 4 + v1 = 1

− 2 x'1 +7 x 2 + x3 + 8 x 4 + v 2 = 7

( PA)− 2 x'1 +10 x 2 + 2 x3 + 10 x 4 + v3 = 10
− 2 x' +18 x + 5 x + 14 x + Z = 0
 1 2 3 4

3 x'1 −18 x 2 − 4 x3 − 17 x 4 = W( Min ) − 18

24
 x1 x2 x3 x4 v1 v2 v3 Z b

1 1 1 -1 1 0 0 0 1
-2 7 1 8 0 1 0 0 7
-2 20 2 10 0 0 1 0 10
2 -18* -5 -14 0 0 0 1 0
3 -18 -4 -17 0 0 0 0 -18
1 1 1 -1 0 0 0 1
-9 0 -6 15 1 0 0 0
-12 0 -8 20 0 1 0 0
20 0 13 -32 0 0 1 18
21 0 14 -35* 0 0 0 0
6 1 9 0 0 0 1
15 15
9 0 6 1 0 0 0
- -
15 15
0 0 0 0 1 0
4 0 1 0 1 0 18
5 5
0 0 0 0 0 0 0

Conclusion
W = 0 alors le PL admet une solution réalisable
C≥0 J = (2 , 4) est une base réalisable
Pas de variable d’écart dans ma base.
De plus,

4 1 Ci ≤ 0
On : Z = − x1 − x3 ⇒  d’où J = (2 ,4) est une base optimale.
5 5 Z ( Max )

25
Exercice 4 :
 x1 + x 2 + x3 − x5 = 1
2 x + 2 x − x − x = 2
 2 3 4 5 x1 , x 2 , x3 , x 4 ≥ 0
( P) ;
− x1 + 4 x 2 − 2 x3 + 8 x 4 + 3 x5 = 4 x5 ≤ 0
− 2 x1 + 14 x 2 + x3 + 14 x 4 + 4 x5 = Z ( Min )

On pose x' 5 = − x5 ≥ 0
vi variable artificielle, i = (1,2,3)
 x1 + x 2 + x3 + x' 5 + v1 = 1

2 x 2 + 2 x 3 − x 4 + x ' 5 + v 2 = 2

( PA)− x1 + 4 x 2 − 2 x3 + 8 x 4 − 3 x' 5 + v3 = 4
2 x − 14 x − x − 14 x + 4 x' + Z
( Min ) = 0
 1 2 3 4 5

− 7 x 2 − x3 − 7 x 4 + x'5 = W( Min ) − 7

x1 x2 x3 x4 x '5 v1 v2 v3 Z b

1 1 1 0 1 1 0 0 0 1
0 2 2 -1 1 0 1 0 0 2
1 4 -2 8 -3 0 0 1 0 4
2 -14 -1 -14 4 0 0 0 1 0
0 -7* -1 -7 1 0 0 0 0 7
1 1 1 0 1 0 0 0 1
-2 0 0 -1 -1 1 0 0 0
-5 0 -6 8 -7 0 1 0 0
16 0 13 -14 18 0 0 1 14
7 0 6 -7* 8 0 0 0 0
1 1 1 0 1 0 0 1
2 0 0 1 1 0 0 0
-21 0 -6 0 -15 0 0 0
5 1 0 0 3 0 1
- -
2 2
2 0 0 1 1 0 0
7 0 1 0 5 0 0
2 2
3 0 0 0 -½ 1 14
-
2

26
 0 0 0 0 0 0 0

Conclusion :
W=0
Vecteur coût ≥ 0
Pas devi
La base (2,4) est une base réalisable
De plus ,
Z à minimiser vecteur coût ≥ 0
Donc la base est optimale.

Zop = 14 ; x2 = 1 ; x3 = x4 = 0

Exercice 5 :
2 x1 + x 2 − x3 ≥ 4
4 x − 3 x ≥ 2
 1
x1 , x 2 , x3 ≥ 0
2
( P) ;
− 3 x1 + 2 x 2 + x3 ≥ 3
− x1 + 3 x 2 − 3 x3 = Z ( Max )


2 x1 + x 2 − x3 − x 4 + v1 = 4

4 x1 − 3 x 2 − x5 + v 2 = 2

( PA)− 3 x1 + 2 x 2 + x3 − x6 + v3 = 3
 x − 3x + 3x + Z = 0
 1 2 3

− 3 x1 + x 4 + x5 + x6 = WMin ) − 9

x1 x2 x3 x4 x5 x6 v1 v2 v3 Z b

2 1 -1 -1 0 0 1 0 0 0 4
4 -3 0 0 -1 0 0 1 0 0 2
-3 2 1 0 0 -1 0 0 1 0 3
1 -3 3 0 0 0 0 0 0 1 0
-3 0 0 1 1 1 0 0 0 0 -9
0 5 -1 -1 ½ 0 1 0 0 3
2

27
 1 3 0 0 1 0 0 0 0 ½
- -
4 4
0 1 1 0 3 -1 0 1 0 9
- -
4 4 2
0 9 3 0 1 0 0 0 1 -½
-
4 4
0 9 0 0 1 1 0 0 0 15
- * -
4 4 2
0 1 2 2 1 0 0 0 6
- -
5 5 5 5
1 0 3 3 1 0 0 0 7
- - -
10 10 10 5
0 0 9 1 7 -1 1 0 24
- -
10 10 10 5
0 0 21 9 7 0 0 1 13
10 10 10 10
0 0 2 1 7 1 0 0 24
- -
10 10 10 5
0 1 0 4 1 4 0 10
- - -
9 9 9 3
1 0 0 1 1 1 0 3
- - -
3 3 3
0 0 1 1 7 10 0 10
- - -
9 9 9 3
0 0 0 17 7 7 1 99
-
15 3 3 10
0 0 0 0 0 0 0 1

Conclusion :
W = 0 vecteur coût ≥ 0 pas
J = (2,1,0) est une base réalisable
99
De plus , Z à Max vecteur coût ≤ 0 solution optimale = Zap =
10
10 16
x1 = 3; x 2 = ; x3 =
3 3
x 4 = x5 = x6 = 0

28
Exercice 6 :
3 x1 + x 2 − x3 = 6

( P) x1 + 3 x 2 − x 4 = 10 ; xi ≥ 0; i ∈ {1,2,3,4}
x + 2 x = Z
 1 2 ( Max )

3 x1 + x 2 − x3 + v1 = 6

 x1 + 3 x 2 − x 4 + v 2 = 10
( PA)
− x1 − 2 x 2 + Z = 0
− 4 x1 − 4 x 2 + x3 + x 4 = W( Min ) − 16


Phase I :
x1 x2 x3 x4 v1 v2 Z b

3 1 -1 0 1 0 0 6
1 3 0 -1 0 1 0 -10
-1 -2 0 0 0 0 1 0
-4* -4 1 1 0 0 0 -16
1 1 1 0 0 0 2
-
3 3
0 8 1 -1 1 0 8
3 3
0 5 1 -1 0 1 2
- -
3 3
0 8 1 1 0 0 -8
- * -
3 3
1 0 3 1 0 1
-
8 8
0 1 1 3 0 3
-
8 8
0 0 1 5 1 7
- -
8 8
0 0 0 0 0 0

29
Conclusion :
W = 0 vecteur coût ≥ 0 pas de Vi
La base (1,2) est réalisable.

Phase II :
x1 x2 x3 x4 b

1 0 3 1 1
-
8 8
0 1 1 3 3
-
8 8
0 0 1 5 -7
*
8 8
8 0 -3 1 8
3 1 -1 0 27
8
-5 0 2* 0 -12

Conclusion
Z est non bornée.

Graphique :

30
Exercice 9 :
Th des alternatives :
L’un et U un seul de ces systèmes admet une solution :
A = b  yA ≤ 0
( I ) x et ( II )
x ≥ 0  yb f 0
a)
 x1 + 3x 2 − 5 x3 = 2
( I ) , x1 , x 2 , x3 ≥ 0
 x1 − 4 x 2 − 7 x3 = 3

 y1 + y 2 ≤ 0 y1 + y 2 = 0
3 y − 4 y ≤ 0 3 y1 − 4 y 2 = 0

( II ) 1 2

− 5 y1 − 7 y 2 ≤ 0 − 5 y1 − 7 y 2 = 0
2 y1 + 3 y 2 f 0 2 y1 + 3 y 2 = 0

Méthode 1 : une solution particulière.

31
Exercice 1 :
 y1 + 3 y 3 + 4 y5 ≥ 1
2 y + y + 2 y ≥ 2
 1 4 5

 2
3 y1 − 2 y 2 + 4 y 3 − y 4 − 3 y 5 ≥ −
 3 ; yi ≥ 0
− 4 y 3 + y 2 + y 5 ≥ 0

5 y1 + 3 y 2 − y 3 + 2 y 4 + 2 y 5 ≥ 4
4 y + 3 y + 2 y + 13 y = W
 2 3 4 5 ( Min )

x1 > 0 : 1ère contrainte.

x2 > 0 : 1ère contrainte.
x4 > 0 : 1ère contrainte.
1
y3 =
3
y4 = 2
y2 = 0
y = (0, 0, 1/3, 2, 0) solution réalisable.
W = 4 x 0 + 3 x 1/3 + 2 x 2 + 13 x 0 = 1 + 4 = 5
Z = W = 5 : Solution optimale.

Exercice 2 :
20
x1 = ≥0
3
11
x2 = ≥ 0
3
20 11 42
+ x2 = = 14 ≤ 14
3 3 3
20 11 29
2x − = ≤ 10
3 3 3
20 11 9
− = =3≤3
3 3 3
20 11
x1 = ; x 2 = est solution réalisable.
3 3
Elle est une solution de base car elle vérifie n = 2 contraintes avec égalité.

32
  y1 + 2 y 2 + y 3 ≥ 2

( B)2 y1 − y 2 − y3 ≥ 1 ; y1 , y 2 , y 3 ≥ 0
14 y + 10 y + 3 y = W
 1 2 3 ( Min )

x1 f 0 ⇒ y1 + 2 y 2 + y 3 = 2
x 2 f 0 ⇒ 2 y1 − y 2 − y 3 = 1

2ème contrainte tâche donc y 2 = 0

 y1 + y 3 = 2  y1 = 1
 ⇒ 
2 y1 − y 3 = 1  y3 = 1

y = (1,0,1) solution réalisable.

w = 10 x1 + 10 x0 + 3 x1 = 17 

11 51 w = Z
Z = 2 x2 + 3 + = = 17 
3 3 
20 11 
x=( , )
et 3 3  solution optimale de (B) et (A) respectivement.
y = (9,0,1) 

x1 = x 2 = 0
x 3 = 4 .5
x4 = 6

4 y1 + 8 y 2 ≥ 5

4 y1 + 6 y 2 ≥ 1

( D)4 y1 + 4 y 2 ≥ 6 ; y i ≥ 0; i = 1.2
 y + 3y ≥ 2
 1 2

24 y 2 + 36 y 2 = W( Min )

x3 > 0 → 3ème contrainte serré 4y1 + 4y2 = 6

x4 > 0 → 3ème contrainte serré y1 + 3y2 = 2

33
  5
 3 y =
 y1 + y 2 =  1
4
 2 ⇒ 
 y1 + 3 y 2 = 2 y = 1
 2 4

5 1
y = ( , ) solution réalisable de (D)
4 4
W(Min) = 39 ; Z(Max) = 39 ⇒ W = Z
5 1
y = ( , ) solution optimale.
4 4

Exercice :
 x1 + x 2 ≥ 4 − µ

 x1 + 4 x 2 ≥ 5 − µ ; xi ≥ 0
x + x = Z
 1 2 ( Min )

Pour µ ≥ 5 , (P) admet une solution évidente ?

− 3 x1 − x 2 ≤ µ − 4

− x1 − 4 x 2 ≤ µ − 5 ; xi ≥ 0
x + x = Z
 1 2 ( Min )

b ≥ 0 donc P ' µ est primal réalisable.

c ≥ 0 donc P ' µ est dual réalisable.

P ' µ est à la fois dual réalisable et primal réalisable. Donc on est à l’optimalité.

 x1 − x 2 + x3 = µ − 4

 x1 − 4 x 2 + x 4 = µ − 5 ; xi ≥ 0
x + x = Z
 1 2 ( Min )

L’écrit s.f.c % à une base optimale

Base est (3,4). Donc
 x3 = µ − 4

 x 4 = µ − 5 est une solution évidente de P ' µ .
x = x = 0
 1 2

Solution de ( Pµ ) pour 0 ≤ µ ≤ 5

34
− 3 x1 − x 2 + x3 = µ − 4

− x1 − 4 x 2 + x 4 = µ − 5
x + x = Z
 1 2 ( Min )

x2 x3 x4 b

-1 1 0 µ −4
-4 0 1 µ −5
1 0 0 0
0 1 1 3µ − x1
-
4 4
1 0 1 5−µ
-
4 4
0 0 1 µ −5
4 4
0 4 1 11 − 3µ
-
11 11 11
1 1 3 11 − 2 µ
-
11 11 11
0 3 2
11 11

Base (2,3) est optimale ssi b1 ≥ 0.

11
3µ − µ ≥ 0 ⇒ 3µ ≥ 11 ⇒ µ ≥
3
11
Donc (2,3) est optimale ssi ≤µ ≤5
3
Base (1,2) est optimale ssi b’1 ≥ 0.
11
11 − 3µ ≥ 0 ⇒ 11 ≥ 3µ ⇒ ≥µ
3
11
Base (1,2) est optimale ssi 0 ≤ µ ≤ .
3

35
Exercice 5 :
 x1 + x 2 + 2 x3 ≤ 6

P1 2 x1 − x 2 + 2 x3 ≤ 2 ; xi ≥ 0
2 x + 2 x + x = Z
 1 2 3 ( Max )

a) pour α = −1
 x1 + x 2 + 2 x3 ≤ 6

P−1 2 x1 − x 2 + 2 x3 ≤ 2 ; xi ≥ 0
− x + 2 x + x = Z
 1 2 3 ( Max )

x1 x2 x3 x4 x5 b

1 1 2 1 0 6
2 -1 2 0 1 2
-1 2* 1 0 0 0
1 1 2 1 0 6
3 0 4 1 1 8
-3 0 -3 -2 0 -3

C’est l’optimalité.
x1 = x3 = x 4 = 0
x2 = 6
x5 = 8
Z = 12
J (2,5) est une base optimale.
π = (π 1 , T1 ) = (2,0)
c’1 = 2 – (2,0) (½) = α − 2
on a calculé c’1 car le seul coût qui change dans le reste du vecteur coût reste (0,-3,-2,0) donc
la base (2,5) est optimale ssi c’1 ≤ 0
⇒ α −2≤0 ⇒ α ≤2
Pour α f 2 ?
x1 x2 x3 x4 x5 b

1 1 2 1 0 6
3 0 4 1 1 8
(α − 2 ) 0 -3 -2 0 -12

36
 0 1 2 2 1 16
-
3 3 3 3
1 0 4 1 1 8
3 3 3 3
0 0 1 + 4α 4 +α 2 −α 20 + 8α
- - -
3 3 3 3

On a
1
− 1 − 4α ≤ 0 → α ≥ − or α f 2
4
− 4 − α ≤ 0 → α ≥ −4 or α f 2
2 −α ≤ 0 → α ≥ 2 or α f 2
Donc la base (1,2) est optimale.
10 8
x2 = ; x1 =
3 3
20 + 8α
x3 = x 4 = x 5 = 0 et Z=
3

Exercice 6 :
 x1 + x 2 ≥ 2

P1  x1 + 2 x 2 ≥ 3 ; xi ≥ 0
(2 + 2) x + 4 x = Z
 1 2 ( Min )

1)
 x1 + x 2 ≥ 2

P0  x1 + 2 x 2 ≥ 3 ; xi ≥ 0
2 x + 4 x = Z
 1 2 ( Max )

a)
 y1 + y 2 ≥ 2

D0  y1 + 2 y 2 ≥ 3 ; yi ≥ 0
2 y + 3 y = W
 1 2 ( Max )

b) x1 = 2 ; x2 = ½
er
x1 > 0 donc 1 contrainte du dual est serré :
y1 + y2 = 2

37
x2 > 0 donc 2ème contrainte du dual est serré :
y1 + y2 = 4

 y1 + 2 y 2 = 2 y1 = 0
 ⇒
 y1 + 2 y 2 = 4 y2 = 2

 x1 = 2
  y1 = 0
 1 
 x2 = et  y2 = 2 solution optimale
 2 W = 6
Z = 6 

c)
 x1 + x 2 − x3 + v1 = 2

 x1 + x 2 − x 4 + v 2 = 3
− 2 x − 2 x + x + x = W
 1 2 3 4 ( Min ) − 5

x1 x2 x3 x4 v1 v2 Z b

1 1 -1 0 1 0 0 2
1 2 0 -1 0 1 0 3
-2 -4 0 0 0 0 1 0
2 -3* 1 1 0 0 0 -5
½ 0 -1 ½ 1 0 ½
½ 1 0 -½ 0 0 3/2
0 0 0 -2 0 1 -6
-½ * 0 1 -½ 0 0 -½
1 0 -2 1 0 1
0 1 1 -1 0 1
0 0 0 -2 1 -6
0 0 0 1 0 0

Donc J (1,2) est une base réalisable. Elle est aussi optimale car c ≥ 0.

38
d) toute solution optimale de P0 est telle que :
 x1 + x 2 ≥ 2(1)

 x1 + 2 x 2 ≥ 3(2) ; xi ≥ 0
2 x + 4 x = 6
 3 2

On a :
(2) x1 = 3 − 2 x 2 ≥ 0
(1) 3 − 2 x 2 + x 2 ≥ 2 donc x2 ≤ 1 et x1 ≥ 0
Les bases optimales sont tel que Z = 6 une base optimale est (1,2) donc x1 et x2 sont VB
(variable de base).
Pour une autre phase il faut que soit x1 soit x2 devient un VHB (variable hors base).
Si x2 est VBH donc x2 = 0
 x4 = 0

On aura  x1 = 3 dans ce cas la base optimale sera (1,3)
x = 1
 3

 x1 = 1
Sinon x2 = 1 alors  de base (1,2).
 x3 = x 4 = 0

Dans des autres cas

Si α p −2
x1 x2 x3 x4 b

1 2 0 -1 3
0 1 1 -1 1
0 -2 α 0 2+ α *

Si α f 2
x1 x2 x3 x4 b

1 0 -2 1 1
0 1 1 -1 1
0 0 2α 2- α *
1 0 -2 1 1
1 1 -1 0 2
α −2 0 4 0 -8

39
C’est l’optimalité J = (4,2) est une base optimale si α f 2 .
 x1 = x3 = 0
x = 0
 4

 x1 = 2
Z = 8

Résumé :
α -2 0 2
x1 3 1 0

x2 0 1 2

x3 1 0 0

x4 0 0 1

J Z(Min) bornée (1 ;3) (1,2) (4,2)

40
 TD6
Algorithme dual – P.L à variable bornées

Exercice 1 :
 x1 − x 2 + x3 = 6
x + x + x = 4 (1)
 4 5 6
( 2)
 x1 + x 4 = 5
( P) (3) ; xi ≥ 0
 x 2 + x5 = 3 ( 4)
 x3 + x 6 = 2
 (5)
3 x1 + x 2 + 2 x3 + 6 x 4 + 2 x5 + 4 x6 = Z ( Max )

a) (2) = (3) + (4) + (5) – (1)

la contrainte (2) est résonante.
b) tel que J = (1,2,5,6) est une base réalisable pour P
donc x3 = x4 = 0 (variable hors base).

 x1 + x 2 = 6  x1 = 5 ≥ 0
x + x = 4 x = 1 ≥ 0
 1  2
⇒
4
 
 x5 + x 2 = 3  x5 = 2 ≥ 0
 x6 = 2  x6 = 2 ≥ 0

Alors comme la solution de (1,2,5,6) est positive et unique alors la base (1,2,5,6) est
réalisable.
c) πA J = C J
1 1 0 0
 
1 0 0 0
AJ = 
0 1 1 0
 
0 1 
 0 0

1 1 0 0
 
1 0 0 0
( π1 π2 π3 π4)  = (3 1 2 4)
0 1 1 0
 
0 1 
 0 0

41
π 1 + π 2 = 3 π 1 = 1
π + π = 1 π = 4
 1  2
⇒
3
 
π 3 = 2 π 3 = 2
π 4 = 4 π 4 = 4

(C J ) = C J − πA J 1 
 3  
(C ) = 2 − (1,4,2,4) 0
 3 0
(C )' = −1  
(C 4 )' = C 4 − πA 4 1 
  

x4 entre dans la base.

A J + ( A J ) S = AS ⇒ A J + ( A J ) 4 = A4

1 1 0 0  A1  0  A1 = 1
       A = −1
1 0 0 0  A2  1   2
0 A  = ⇒ 
1 1 0 0
 A3 = 1
   3  
0 1  A  0  A4 = 0
 0 0  4  

1 1 0 0   b1  6
     
1 0 0 0   b2  5
A J .b( J ) = b ⇒  0 1 1 0 b  = 3
   3  
0 0 0 1  b   2
   4  

b1 = 5
b = 1
 2 b b  5 2
 , Min 2 ; 3  = Min ;  = 2
b3 = 2  A1 A3  1 1
b4 = 2

Donc x5 soir de la base

J1 (1,2,4,6)

42
πA2J = C 7
1 1 0 0 
 
1 0 1 0 
(π 1 ; π 2 ; π 3 ; π 4 )  0 1 0 0  = ( 3 1 6 4)
 
0 0 0 1 
 

π 1 + π 2 = 3 π 1 = −3
π + π = 1 π = 6
 1  2
⇒
3
 
π 2 = 6 π 3 = 4
π 4 = 4 π 4 = 4

(C )J1 5
= C J1 − πA J1 ⇒ (C )' = C
5 5
− πA5

0
 
0
= 2 – (-3 6 4 4)  0  = 2 – 4 = -2 < 0
 
1 
 
(C '9 ) = C 3 − πA 3
1 
 
0
= 2 – (-3 6 4 4)   = 1
0
 
1 
 
Donc x3 entre dans la base

( )
AJ . AJ
S
( )
= AS ⇒ A J . A J
3
= A3

1 1 0 0   A1  1   A1 = 1
      A = 0
1 0 1 0   A2  0  2
 0 1 0 0 A  = 0 ⇒ 
   3    A3 = −1
0 0 0 1  A  1   A4 = 1
   4  

1 1 0 0   b1  6
     
1 0 1 0   b2  5
A J .b( J ) = b ⇒  0 1 0 0 b  = 3
   3  
0 0 0 1  b   2
   4  

43
b1 = 3
b = 3
 2 b b 
 = Min ;  =
3 2 2
 ; Min 1 ; 4
b3 = 2  A1 A4  1 1 1
b4 = 2

J2 = (1,2,3,4) ; πA J 2 ; C J2

1 1 1 0 
 
1 0 0 1 
(π 1 ; π 2 ; π 3 ; π 4 )  0 1 0 0  = ( 3 1 2 6)
 
 0 0 1 0
 
π 1 = −3
π = 6
 2
 ; (C ) J2 S
= C J 2 − πA S
π 3 = 4
π 4 = 5

C ' 5 = C 5 − πA 5 = −2 p 0

C ' 6 = C 6 − πA 6 = −1 p 0
D’où la base (1,2,3,4) est optimale.

Exercice 2 :
 x1 − x 2 ≤ 1
x ≥ 1
 1
( P1 ) ; xJ ≥ 0
 x1 + x 2 ≥ 3
 x1 + 2 x 2 = Z ( Min )


 x1 − x 2 + x3 = 1
x − x = 1
 1 4
( P1 S )
 x1 + x 2 − x5 = 3
 x1 + 2 x 2 = Z ( Min )


 x1 − x 2 + x3 = 1
 − x + x = −1
 1 4

− x1 − x 2 + x5 = −3
 x1 + 2 x 2 = Z ( Min )


44
 x1 x2 x3 x4 x5 b

1 -1 1 0 0 1
-1 0 0 1 0 -1
-1 -1 0 0 1 -3*
1 2 0 0 0 0
0 -2 1 0 1 -2
0 1 0 1 -1 2
1 1 0 0 -1 3
0 1 0 0 1 -3
0 1 -½ 0 -½ 1
0 0 -½ 1 -½ 2
0 0 ½ 0 3/2 -4

b > 0 ; la base (2,,4,1) est une base optimale.

Exercice 3 :
1 ≤ x1 ≤ 10
4 x1 + 4 x 2 + 4 x3 + x 4 ≤ 48
 2 ≤ x2 ≤ 5
( P)8 x1 + 6 x 2 + 4 x3 + 3 x 4 ≤ 72
5 x + x + x + 2 x = Z 3 ≤ x3 ≤ 6
 1 2 3 4 ( Max )
4 ≤ x4 ≤ 8

4 x1 + 4 x 2 + 4 x3 + x 4 + x5 = 48

( PA)8 x1 + 6 x 2 + 4 x3 + 3 x 4 + x6 = 72
5 x + x + x + 2 x = Z
 1 2 3 4 ( Max )

Borner de x5

4 ≤ 4 x1 ≤ 40 

8 ≤ 4 x 2 ≤ 20 

12 ≤ 4 x3 ≤ 24  donc 0 ≤ x5 ≤ 20
4 ≤ x4 ≤ 8 

4

28 ≤ ∑ α , x1 ≤ 92
i =1 
9
Donc x1 =
2

45
 x6 = 0
x5 = 2
Alors x2 = 2 ⇒ variable hors base.
x3 = 3
x4 = 4
Donc la base sera (1,5)
 41 
πA S = C S ⇒ (π 1 ; π 2 )  = (5,0 )
 80 
π 1 = 0

⇒ 5
π 2 = 8

x2 entre dans la base

4 x1 + 8 + 12 + x 4 + x5 = 48

5 x1 + 12 + 12 + 3x 4 + 0 = 72

4 x1 + x 4 − x5 = 28

8 x1 + 3x 4 = 48
 x = 28 − 4 x − x
 4 1 5

1
x 4 = (48 − 8 x1 )
3
− 32 ≤ x 4 ≤ 24 
32 40 
− ≤ x4 ≤ 
3 3
4 ≤ x4 ≤ 8 

Borner x6 :
8 ≤ 8 x1 ≤ 80
12 ≤ 6 x 2 ≤ 30
12 ≤ 4 x3 ≤ 24 0 ≤ x6 ≤ 28
12 ≤ 3 x 4 ≤ 24
4
44 ≤ ∑ α i xi ≤ 958
i =1

J1 = (5,6)
10 
πA J = C J ⇒ (π 1π 2 )  = (0,0) ⇒ π = 0
 01
On prend pour les variables hors base leur bornes et pour de base leur bornes est p alors :

46
 x1 = 1
x = 2
 2
 x3 = 3

 x4 = 4
 x5 = 20

 x6 = 28

x1 x2 x3 x4 x5 x6

C S − πA S 5 1 1 2 0 0

x1 entre dans la base

4 x1 + 8 + 12 + 4 + x5 = 48

8 x1 + 12 + 12 + 12 + x6 = 72

4 x1 + x5 = 24

8 x1 + x6 = 36
 24 − x5
 x1 = 4

 x = 36 − x 6

1
8
0 ≤ x5 ≤ 20 0 ≤ x6 ≤ 28
4 ≤ 24 − x5 ≤ 24 8 ≤ 36 − x6 ≤ 36
24 − x5 36 − x6 9
1≤ ≤6 1≤ ≤
4 8 2

⇒ 1 ≤ x1 ≤ 6 1 ≤ x1 ≤
9
et 1 ≤ x1 ≤ 10
2
x4 est candidate pour entrer dans la base (1,5) ; la base reste inchangeable
 x1 = 2
x = 8
 5
 x 4 = 8

 x2 = 2
 x3 = 3

 x6 = 0

47
Exercice 4 :
J (1,4)
x1 = 1 ; x2 = 1 ; x3 = 4 ; x4 = 5
π ?

(π 1π 2 )
11 
 = (4,10)
12 
π 1 + π 2 = 4 π 1 = −2
 ⇒  ; π = (−2,6)
π 1 − 2π 2 = 10 π 2 = 6

1 2 3 4
C’ 0 6 5 0

3
C’2 = C2 - π A2 = 12 – (-2,6)   = 6
 2
 2
C’3 = C3 - π A3 = 7 – (-2,6)   = 5
1 

x2 entre dans la base

 x1 + 3x 2 + x 4 = 9

 x1 + 2 x 2 + 2 x 4 = 13

 x + a1 x 2 = b1

a 2 x 2 + x 4 = b2
A(J) (A(J)) = A2

1 1   a1   3  a1 + a 2 = 3 a1 = 4
    =   ⇒  ⇒ 
1 2   a2   2  a1 + 2a 2 = 2  a 2 = −1

1 1   b1   9  b1 + b2 = 9 b1 = 5
    =   ⇒  ⇒ 
1 2   b2  13  b1 + 2b2 = 13 b2 = 14

 5 − x1
 x1 + 4 x 2 = 5 → x 2 =
 4
− x 2 + x 4 = 4 → x 2 = x 4 − 4

48
0 ≤ x1 ≤ 0
− 2 ≤ − x1 ≤ 0 3 ≤ x4 ≤ 5
3 ≤ 5 − x1 ≤ 5 − 1 ≤ x4 − 4 ≤ 1 1 ≤ x2 ≤ 3 x2 = 1
3 5 − x1 5 − 1 ≤ x2 ≤ 1
≤ ≤
4 4 4
3 5
≤ x2 ≤
4 4

x4 soit de la base
J1 = (1,2)
x2 = 1 ; x1 = 1 ; x3 = 4 ; x4 = 5

(π 1π 2 )
13 
 = (4,12)
12 
π 1 + π 2 = 4 π 1 = 4
 ⇒ 
3π 1 − 2π 2 = 12 π 2 = 0

 2
C’3 = 1 – (4,0)   = 7 – 8 = -1
1 
1 
C’4 = 10 – (4,0)   = 10 – 4 = 6
 2
x3 entre dans la base :
 x1 + 3x 2 + 2 x3 = 12

 x1 + 2 x 2 + x3 = 7

 x1 + a1 x1 = b1

 x 2 + a 2 x3 = b2

1 3   a1   2 a1 + 3a 2 = 2 a1 = 3
    =   ⇒  ⇒ 
1 2   a2  1  a1 + 2a 2 = 1 a 2 = 1

1 3   b1  12  b1 + 3b2 = 12 b1 = 3

    =   ⇒  ⇒ 
1 2   b2  7  b1 + 2b2 = 7 b2 = 5

49