Recherche opérationnelle

séance 1 – ( 05/11/2020 ; 09 :00 )

Un ensemble d’outil qui aide à prendre des décision au niveau opérationnel

Partie 1 : Programmation linéaire

Partie 2 : Technique d’ordonnancement de tâches

Partie 1 : Programmation linéaire

Déf : permet d’optimiser un certain objectif ( fonction économique ; fct linéaire de variables de
décisions qui sont soumises à des contraintes ss formes d’équations ou inéquations linéaires )

Les variables sont tjrs positives ( Qté … ) et ne dépassent pas une certaine valeurs ( ex : contrainte
interne comme la capacité de productions ou des contraintes externes comme la capacité de marché
)

Contrainte de demande : équation, Contrainte de capacité : inéquation

Il y a 2 phases :

Phase de modélisation : la mise en équation des problèmes

Phase de résolution du modèle

1- Etapes de modélisation :
a- Définir les variables de décision (R+ , entières N , Binaire 0 ;1 )
b- Formuler la fonction objectif ( Fct mathématique , linéaire )
c- Formuler les contraintes du problème ( équations ou inéquations linéaires )

Exemple simple :

Atl 1 : Cadre aluminium , Atl 2 : Cadre bois , Atl 3 : Montage de verre

Nombre d’heures : contraintes

Phase de modélisation :

a- Définition des Variables : 2 variables ( Qté de chaque produit par semaine )

X1 : Nombre de châssis en Alimnium à fabriquer par semaine

X2 : Nombe de châssis en bois à fabriquer par semaine

b- Formulation de l’objectif

Max ( Z = 3X1+5X2 )

Z : La marge par semaine

c- Formulation des contraintes

On a 3 contraintes par rapport aux 3 ateliers ( Contraintes de capacité = inéquations )

Atelier 1 : X1 ≤ 4

Atelier 2 : 2X2 ≤12 === X2≤6

Atelier 3 : 3X1+2X2 ≤18

Contraintes naturelles : X1,X2 élements de N ( entiers )

Le Programme linéaire (P.L) à résoudre est le suivant : Max ( Z= 3X1 + 5X2)

S/C : X1 ≤ 4

2X2 ≤12 === X2≤6

3X1+2X2 ≤18

X1, X2 élements de N

On va tracer les droites X1 et X2 et on garder le domaine des solution réalisables puis on va chercher
les solutions optimales

Phase de résolution :
( explication du cours )

Ensemble Convexe SSI

pour 2 points QLQ le segment
de droite joignant ces 2
points est aussi dans l’ensemble

Exemple :
Un point extrême exemple : sur la frontière mais on ne peut pas le mettre sur un segement de droite
reliant de points A et B

Propriétés :

Pr 1 : le domaine des solutions réalisables d’un PL est un ensemble convexe

Pr2 : la solution optimale d’un PL est atteinte au moins en un point extrême de l’ensemble des
solutions réalisables de ce PL

Il faut chercher un point extrême parmi les points extrême

Pr3 : adjacents = sur la même frontière si X1 et X2 sont adjacents , optimales donc tt les points reliant
les points A et B sont des résolutions optimales .

Séance 2 – ( 19/11/2020 ; 09 :00 ) – Rattrapage de la semaine du 12/11/2020

La méthode graphique ( Cas 2 variables seulement )

1ere étape : Résoudre graphiquement les contrainte ; la région réalisable ( L’ensemble des valeurs de
vairiables de décision qui satisfont toutes les contraintes )

Exemple : Suite exemple 1

Etape 1 : Résoudre graphiquement le système des contraintes

La seule méthode pour résoudre un système d’inéquations est graphique

On va résoudre contrainte par contrainte

Il faut tracer la frontiére la droite de chaque inéquation

X1 ≤ 4 Droite : X1=4

2X2 ≤12 === X2≤6 Droite : X2=6

3X1+2X2 ≤18 Droite : 3X1+2X2=18 (Il faut 2 points ; (0,9)(6,0))

X1,X2 élements de N

Etape 2 : Recherche de la solution optimale Max (Z=3X1+5X2)

Points extrêmes Objectif Z

O (0,0) 0
A (0,6) 30
B (2,6) 36
C (4,3) 27
D (4,0) 12

Le Maximum est 36 donc la solution optimale est le point B

Donc la production optimale de l’entreprise est égale à 2 Chassis en aliminium et 6 en bois

Et la marge maximale sera égale à 36 dollars par semaine

Exercice 1 :

1- Etapes de modélisation :

a- Définition des Variables :

X1 : la quantité en Kg du produit A à transporter , X2 : la quantité en Kg du produit B à transporter

b- Formulation de l’objectif :

Max ( Z= 400X1 + 600X2 ) Z : Le gain

c- Formulation des contraintes

Contrainte de poids : 0.032X1+0.1X2 ≤ 2000

Contrainte de volume : X1+X2 ≤ 50000

Le PL à résoudre est : Max ( Z=400X1 + 600X2)

SC

 X1+X2 ≤ 50000
 8X1 + 25X2 ≤ 500000
 X1 et X2 appartiennent à R+
2- Phase de résolution :
a- Résoudre graphiquement le système des contraintes :

X1+X2 ≤
50000 Droite
oblique passant par
(0,50000) ( 50000 ,0)

8X1 + 25X2 ≤
500000 Droite
oblique (0,20000)
( 62,500 , 0)
O(0,0) 0
A(0,20000) 12 000 000
B ( 44117,65 , 5882,35) 21 176 470
C(50000,0) 20 000 000

Calcul de B : B appartient à (1) et (2)

X1 + X2 = 50000

8X1 + 25X2 = 500000

8X1 + 8 X2 = 400000

8X1 + 25X2 = 500000

(2)- (1) = 17 X2 = 10000

X2 = 5882 ,35

X1 = 50000-5882,35

X1 = 44 117,65

La solution optimale est B

Donc il faut mettre dans l’avion

X1 = 44 117,68 de A

X2 = 5882,65 de B

Pour maximiser ses gains

TAF

1- Etapes de modélisation :

a- Définition des Variables : 2 variables

X1 : la quantité en tonne de X à acheter , X2: la quantité en tonne de Y à acheter

 b- Formulation de l’objectif :

Min ( Z= 1000X1 + 800X2 ) Z : Le coût d’achat

c- Formulation des contraintes :

Contrainte de besoins :

A : 0.8X1+0.6X2 ≥ 1800

B : 0.2X1+0.4X2 ≥ 800
Contrainte d’achat :

X : X1 ≤ 6400

Y : X2 ≤ 4400

Le PL à résoudre est : Min ( Z= 1000X + 800Y )

SC

- A=4X1+3X1 ≥ 9000 4X1+3X2=9000 (0,3000) (2250,0)

- B=X1+2X2 ≥ 4000 X1+2X2 = 4000 (0,2000) (4000,0)
- X1 ≤ 6400 X1 = 6400
- X2 ≤ 4400 X2 = 4400
- X1, X2 ≥ 0

2- Phase de résolution :
 a- Résoudre graphiquement le système des contraintes :

Rechercher la solution optimale :

P.E Objectif
A(4000,0) 4 000 000
B (1200, 1400) 2 320 000 MINIMUM
C (0,3000) 2 400 000
D (0,4400) 3 520 000
E (6400,4400) 9 920 000
F (6400,0) 6 400 000

Calcul de B

B est un point dans l’intersection de la droite 1 et 2

Donc le couple X1B et X2B va verfier les équation des deux droites

4X1+3X2 = 9000

X1 + 2X2 = 4000

On va multiplier la 2eme par 4

4 X1+3X2 = 9000 (1)

4X1 + 8X2 = 1600 (2)

(2)-(1) = 5X2 = 7000

X2 = 7000/5 = 1400

X1+X2 = 4000 X1 + 2*1400 = 4000

X1 +2800 = 4000

X1 = 4000-2800 = 1200

Pour réaliser sa production avec un minimum de coût d’achat de matière première égale à 2 320 000
MAD , Cette entreprise doit acheter 1200 tonnes de X et 1400 tonnes de Y

Séance 3 : 26/11/2020 9 :00

ALGORITHME DU SIMPLEXE

1- Forme canonique d’un PL

C’est quand toutes les contraintes sont sous forme d’inéquation

 X1 ≤4
 2X2 ≤ 12
 3X1 + 2X2 ≤ 18
 X1 ≥0
 X2 ≥ 0
- Transformer le sysytèmes des inéquations en équations
 X1 ≤ 4 ; X1 + e1 = 4 (e1 est un écart positif pour passer de l’inéquation à l’équation)

2- Forme standard :
Introduction des variables d’écarts ei

Max Z= 3X1 + 5X2

 X1 + e1 = 4
 2X2 + e2 = 12
 3X1 + 2X2 + e3 = 18
 X1,X2,e1,e2,e3 ≥ 0

On a 3 équations et 5 variables

Interprétations économiques

e1 : nombre d’heures non encore utilisées dans l’atelier 1

e2 : nombre d’heures non encore utilisées dans l’atelier 2

e3 : nombre d’heures non encore utilisées dans l’atelier 3

l’optimum X1=2 , X2= 6 donc ; e1=2 , e2=0 , e3=0

donc on a saturé les contraintes e2 et e3 et reste 2 heures en e1

Il ne faut pas négliger les variables d’écarts et se renseigner sur leurs valeur sur beaucoup de choses

Il faut résoudre le systéme de 3 équations et 5 variables

L’écriture matricielle

X1 X2 E1 E2 E3
1 0 1 0 0
0 2 0 1 0
3 2 0 1 1

X1

X2 4

E1 = 12

E2 18

E3

Pour inverser une matrice la matrice doit être carrée et le déterminant de A est différent de 0

Ax = b

X = b/a si a diff 0

= 1/a*b

= a^-1 *b

Pour rendre la matrice inversible il faut annuler 2 variables pour laisser 3 variables et 3 équations

Les variables annulées dont appelées hors bases et les autres de base

La solution obtenue est un point extrême

Le nombre de variable à annuler c’est : NV -VE

3- Recherche de la base initiale :

On annule les variables de manière de garder (extraire) la matrice identité

x1
1 0 1 0 0 x2 4
0 2 0 1 0 e1 = 12
3 2 0 0 1 e2 18
e3

1 0 1 0 0 e1 4
x1
0 2 + 0 1 0 e 2 = 12
x2
3 2 0 0 1 e 3 18
Les variables de base sont e1, e2, e3
Les variables hors base sont x1, x2

Cette base initiale est évidente

Séance 4 03/12/2020 09 :00

4- Tableau initiale T0 :

T x x e e e
C C/coefs
e
1 0 1 0 0 4 ∞
e 1 12/2=6*
0 2 0 1 0 *
e 1
3 2 0 0 1 18/2=9
Z 3 5 0 0 0 0*

Solution : X1= 0 , X2=0 , Z=0 , e1=4 , e2=12 , e3=18

La base initiale = (e1, e2, e3)

C/Coef : ce rapport va nous aider pour savoir les variables à faire sortir

*L’opposé de Z

Toutes les bases initiales sont formées d’une matrice identité avec des variables de 0 contribution

Si toutes les variables ont des contributions négatives ou nulles ils ne peuvent pas entrer dans la base
, et donc on a la solution optimale

Pour notre exemple on a pas un tableau optimale donc on va procéder à une itération

1ère itération : passage de T0 à T1

Etape 1 : Sélection de la variable entrante dans la base

- Pour un problème de maximisation, on choisit la variable hors base qui a la contribution

marginale dans l’objectif la plus élevé. (C’est X2 dans notre exemple avec une contribution
de 5)
- Pour un problème de minimisation, c’est le contraire

Etape 2 : Sélection de la variable sortante de la base

Pour faire sortir une variable de la base il faut l’annuler ( dans notre exemple on ne peut pas annuler
e1 , e2 peut être annulée si X2 prend 6 )

Le critère de sortie d’une variable de la base : Qlq soit l’objectif on doit choisir la variables qui admets
C/Coef le plus petit positif

**e2 a un rapport de 6 donc elle va sortir , variable entrante est X 2

Etape 3 : detérmination du pivot

Colonne entrante = colonne pivot

Ligne de la vraible sortante = ligne pivot

Leur intersection nous donne le pivot

Dans notre exemple le Pivot est 2

C/
co
T x e e ef
x2 e2 C s
e1 1 0 1 0 0 4
1/
x2 0 1*** 0 0 6
0***
e3 3 0 -1 1 6
5/ 3
Z 3 0 0 0

X2 va reprendre la ligne de e2 pour conserver la matrice identité

Donc on doit dans notre exemple diviser la ligne pivot par 2

*** L2(T1) = L2(T0)/pivot = L2(T0)/2

On a dèja un 0 au niveau de e1 donc on va garder la ligne de T0

L3(T1) = L3(T0) - (la valeur qu’on veut annuler/pivot)*L2(T0) = L3(T0) – L2

**** L3(T1) = ( 3, 2, 0, 0, 1, 18 ) – ( 0, 2, 0, 1, 0, 12 ) = ( 3, 0, 0, -1, 1, 6 )

L4(T1) = L4(T0) – 5/2*L2(T0) = ( 3, 5, 0, 0, 0, 0 ) – 5/2 ( 0, 2, 0, 1, 0, 12 ) =

= (3, 5, 0, 0, 0, 0 ) – ( 0, 5, 0, 5/2, 0, 30 )

= ( 3, 0, 0, -5/2, 0, -30 )

Donc : X1= 0, X2= 6, Z=30 (La valeur absolue) , e1=4, e2=0, e3=6

Cette solution n’est pas optimale car la contribution de la variables X1 HB est positive

Cet objectif peut être encore amélioré donc on va procéder à une nouvelle itération

2ème itération : T1 à T2

V.E = X1

V.S = e3 (division de la ligne des contrainte sur la colonne de la variable sortante)

Pivot = 3

Le Tableau T2 :
 T2 x1 x2 e1 e2 e3 C C/coefs
**e1 0 0 1 0,33 -0,3 2
***x2 0 1 0 0,5 0 6
*x1 1 0 0 -0,3 0,33 2

****Z 0 0 0 -1,5 -1 -36

*L3(T2) = L3(T1)/pivot

**L1(T2) = L1(T1) – (la valeur qu’on veut annuler /pivot) * la ligne pivot

***L2(T2) est la même de T1 car on veut annuler aucune ligne

****L4(T2) = L4(T1) – 3/pivot*L3 = L4(T1) –L3

La solution X1= 2, X2=6, Z=36 , e1 = 2 , e3=0 ,e2=0

Cette solution est optimale car les valeur hors base sont tous nulle

Une solution optimale pour un problème de maximisation est unique si les variables HB sont
strictement négative

Exercice 3 :

1- Etapes de modélisation :
a- Définition des Variables :

X1 : la quantité en Kg du produit A à transporter , X2 : la quantité en Kg du produit B à transporter

b- Formulation de l’objectif :

Max [Z= 400X1 + 600X2] Z : Le gain

c- Formulation des contraintes

Contrainte de volume : 0.032X1+0.1X2 ≤ 2000

Contrainte de poids : X1+X2 ≤ 50000

- Le PL à résoudre est : Max [Z=400X1 + 600X2]

SC

- X1+X2 ≤ 50000
- 8X1 + 25X2 ≤ 500000
 - X1, X2, A, B appartiennent à R+

2- Etape de résolution : (Méthode de symplex)

a- Forme standard

- X1 + X2 + e1 = 50000
- 8X1 + 25X2 + e2 = 500000
- X1, X2,e1,e2 ≥ 0

b- L’écriture matricielle :

On a 2 équations et 4 variables

Interprétations économiques

e1 : Quantité en Kg non encore utilisée

e2 : Volume en m3 non encore utilisé dans l’avion

x1
1 1 1 0 x 2 50 000
x =
8 25 0 1 e 1 500 000
e2
1 1 x 1 1 0 e 1 50 000
x + x =
8 25 x 2 0 1 e 2 500 000
Matrice identité de taille 2 , donc B=(e1,e2) H.B=(X1,X2)

3- Tableau initiale T0 :

e
-
T0 x1 x2 e1 C C/coefs

L1 e1 1 1 1 0 50000 50000
L2 e2 8 25 0 1 500000 20000
40
L3
Z 600 0 0 0 -

X1= 0, X2=0, Z=0, e1= 50 000, e2=500 000

T0 n’est pas optimal car la contribution de X1 et X2 est positive

4- Tableau T1 :
 - T1 x1 x2 e1 e2 C C/coefs

L1
e1 17/25 0 1 -1/25 30 000 750 000 /17
L2 X2 8/25 1 0 1/25 20 000 62 500
L3 Z 208 0 0 - 24 -12 000 000 -

L1(T1) = L1(T0) - (1/25)*L2(T0) = ( 1, 1, 1, 0, 50 000 ) – ( 1/25)*(8, 25, 0, 1, 500 000 )

= ( 1, 1, 1, 0, 50 000 ) – (8/25 , 1 , 0, 1/25 , 20 000 )

= ( 17/25, 0, 1, -1/25, 30 000)

600 / 25 = 24

L3/(T1) = L3(T0) – 24*L2(T0) = (400, 600, 0, 0,0) – 24*(8, 25, 0, 1, 500 000)

= (400, 600, 0, 0,0) – ( 192, 600, 0 , 24, 12 000 000)

= (208, 0, 0, -24, -12 000 000)

5- T2 :

x
-
T2 x1 e1 e2 C C/coefs

L1
X1 1 0 25/17 -1/17 750 000/17
L2 X2 0 1 -8/17 1/17 100 000/17
L3 Z 0 0 -5200/17 -200/17 -21 176 470,59 -

L2(T2) = L2(T1) – (8/25)/(17/25)*L1

= (8/25, 1, 0, 1/25, 20 000) – (8/17)*(17/25, 0, 1, -1/25, 30 000)

= (8/25, 1, 0, 1/25, 20 000) – (8/25, 0, 8/17, -8/425, 240 000/17)

= (0, 1, -8/17, 1/17, 100 000/17)

L3(T2) = L3(T1)-(208/(17/25))*L1(T1)

= (208, 0, 0, -24, -12 000 000) – (5200/17) *(17/25, 0, 1, -1/25, 30 000)

= (208, 0, 0, -24, -12 000 000) – (208, 0, 5200/17, -208/17, 156 000 000/17)

= (0 , 0, -5200/17, -200/17, -21 176 470,59)

La solution X1= 44 117,64 , X2=5882,35 , Z=21 176 470,59 , e1 = 0 , e2=0

Cette solution est optimale car les valeurs hors base sont toutes nulles
Une solution optimale pour un problème de maximisation est unique si les variables HB sont
strictement négative

Exercice 4 :

1- Etapes de modélisation :

a- Définition des Variables :

X1 : Nombre d’unités produites par semaine (sachets) de M1, X2 : Nombre d’unités produites par
semaine (sachets) de M2, X3 : Nombre d’unités produites par semaine (sachets) de M3

b- Formulation de l’objectif :

Max [Z= 2X1 + 1,5X2 + 1X3] Z : Le gain

c- Formulation des contraintes

Contrainte de quantité d’arachide : 30X1 + 30X2 + 20X3 ≤ 2400

Contrainte de quantité de raisin sec : 10X1 + 10X2 + 20X3 ≤ 1200

Contrainte de quantité de noix : 30X1 + 10X2 + 10X3 ≤ 1200

- Le PL à résoudre est : Max [Z= 2X1 + 1,5X2 + 1X3]

SC

- 3X1 + 3X2 + 2X3 ≤ 240

- 1X1 + 1X2 + 2X3 ≤ 120
- 3X1 + 1X2 + 1X3 ≤ 120
- X1, X2, X3 appartiennent à N

2- Etape de résolution : (Méthode de Simplex)

a- Forme standard

- 3X1 + 3X2 + 2X3 + e1 = 240

- 1X1 + 1X2 + 2X3 + e2 = 120
- 3X1 + 1X2 + 1X3 + e3 = 120
- X1 , X2 , X3 , e1, e2, e3 appartient à N

Interprétations économiques

- e1 : quantité d’arachide non utilisée

- e2 : quantité de raisin sec non utilisée
- e3 : quantité de noix non utilisée
b- L’écriture matricielle :

On a 3 équations et 6 variables

Interprétations économiques

e1 : quantité d’arachide non utilisée

e2 : quantité de raisin sec non utilisée

e3 : quantité de noix non utilisée

x1
x2
3 3 2 1 0 0 240
x3
1 1 2 0 1 0 = 120
e1
3 1 1 0 0 1 120
e2
e3
3 3 2 x1 1 0 0 e 1 240
1 1 2 x2 + 0 1 0 e 2 = 120
3 1 1 x3 0 0 1 e 3 120
Les variables de base sont e1, e2, e3 / Les variables hors base sont x1, x2, x3 (Cette base initiale est
évidente).

1- T0

- t0 x1 x2 x3 e1 e2 e3 c c/coefs
L1 e1 3 3 2 1 0 0 240 240/3=80
L2 e2 1 1 2 0 1 0 120 120/1=120
L3 e3 3 1 1 0 0 1 120 120/3=40
L4 z 2 1,5 1 0 0 0 0 -

La ligne pivot e3, la colonne pivot x1, le pivot = 3

2- T1

- T1 x1 x2 x3 e1 e2 e3 c c/coefs
L1 e1 0 2 1 1 0 -1 120 60
L2 e2 0 2/3 5/3 0 1 -1/3 80 120
L3 x1 1 1/3 1/3 0 0 1/3 40 120
L4 z 0 5/6 1/3 0 0 -2/3 -80 -

La ligne pivot e1, la colonne pivot x2, le pivot = 2

Calcul de L1
L1(T1) = L1(T0) -3/3*L3(T0)

= (3, 3, 2, 1, 0, 0, 240) – (3, 1, 1, 0, 0, 1, 120)

= (3, 3, 2, 1, 0, 0, 240) – (3, 1, 1, 0, 0, 1, 120)

= (0, 2, 1, 1, 0, -1, 120)

L2(T1) = L2(T0) -1/3*(3,1, 1, 0, 0, 1,120)

= (1, 1, 2, 0, 1, 0, 120) – (1, 1/3, 1/3, 0, 0, 1/3, 40)

=(0, 2/3, 5/3, 0, 1, -1/3, 80)

L3(T1) = L3(T0)/3

L4(T1) = L4(T0)-2/3*L3(T0)

= (2, 3/2, 1, 0, 0, 0, 0 )- 2/3*(3, 1, 1, 0, 0, 1, 120)

= (2, 3/2, 1, 0, 0, 0, 0 )- (2, 2/3, 2/3, 0, 0, 2/3, 80)

= (0, 5/6, 1/3, 0, 0, -2/3, -80)

3- T2 :

e
- T1 x1 x2 x3 e1 e3 c c/coefs

L1 X2 0 1 1/2 1/2 0 -1/2 60

L2 e2 0 0 4/3 -1/3 1 0 40
L3 x1 1 0 1/6 -1/6 0 1/2 20
L4 z 0 0 -1/12 -5/12 0 -1/4 -130 -

L1(T2) = L1(T1)/2

= (0, 1, ½, ½, 0, -1/2, 60)

L2(T2) = L2(T1) – (2/3) /2*L1

= (0, 2/3, 5/3, 0, 1, -1/3, 80) – 1/3*(0, 2, 1, 1, 0, -1, 120)

= (0, 2/3, 5/3, 0, 1, -1/3, 80) – (0, 2/3, 1/3, 1/3, 0, -1/3, 40)

= (0, 0, 4/3, -1/3, 1, 0, 40)

L3(T2) = L3(T1) – 1/6*L1

= (1, 1/3, 1/3, 0, 0, 1/3, 40) – 1/6*(0, 2, 1, 1, 0, -1, 120)

= (1, 1/3, 1/3, 0, 0, 1/3, 40) – (0, 1/3, 1/6, 1/6, 0, -1/6, 20)

= (1, 0, 1/6, -1/6, 0, ½, 20)

L4(T2) = L4(T1) – (5/6) /2 * (0, 2, 1, 1, 0, -1, 120)

 = (0, 5/6, 1/3, 0, 0, -2/3, -80) – 5/12*(0, 2, 1, 1, 0, -1, 120)

= (0, 5/6, 1/3, 0, 0, -2/3, -80) – (0, 10/12, 5/12, 5/12, 0, -5/12, 50)

= (0, 0,-1/12, -5/12, 0, -1/4, -130)

La solution X1= 20, X2=60 X3= 0, Z=130, e1 = 0, e2=400, e3=0

Cette solution est optimale car les valeurs hors base sont toutes nulles ou négatives

E2 signifie que 400 gr de raisin sec n’a pas été utilisé.

Séance 5 10/12/2020 09 :00 Correction des exercices au-dessus (Correctes à 100%)

Séance 6 17/12/2020 13 :30

PROBLEME DE MINIMISATION SELON LA METHODE DU SIMPLEXE :

Exercice 5 :

Résoudre le P.L de l’exercice 2 par l’algorithme du simplexe

Le PL à résoudre est : Min [Z= 1000X1 + 800X2]

SC

- A = 4X1 + 3X1 ≥ 9000

- B = X1 + 2X2 ≥ 4000
- X1 ≤ 6400
- X2 ≤ 4400
- X1, X2 ≥ 0

Etape 1 : Passage de la forme canonique à la forme standard :

Min ( Z= 1000X1 + 800X2 )

SC

- A = 4X1 + 3X2 – e1 = 9000

- B = X1 + 2X2 – e2 = 4000
- X1 – e3 = 6400
 - X2 – e4 = 4400
- X1,X2,e1,e2,e3,e4 ≥ 0

Etape 2 : Recherche de la base initiale :

1- Ecriture matricielle de la forme canonique :

x1
4 3 −1 0 0 0 x 2 9000
1 2 0 −1 0 0 e1 4000
=
1 0 0 0 1 0 e2 6400
0 1 0 0 0 1 e3 4400
e4
On doit avoir donc une matrice identité de taille 4 , car on a 4 variables

On a une absence d’une base initiale évidente à cause de l’absence d’une matrice identité

Ils nous manquent 2 colonnes pour avoir une matrice identité donc on doit ajouter 2 colonnes pour
les faire apparaître, donc le système sera pas le même, il va être différent, donc on va appliquer la
programmation linéaire sur un nouveau système dans 2 phases, une première phase pour résoudre
le nouveau système et la deuxième pour résoudre le système initiale sur la base des résultats de la
première phase .

Le nouveau P.L s’appellera un P.L auxiliaire (P.L*)

PHASE 1 :

Résoudre le P.L* auxiliaire suivant :

Les variables qu’on va ajouter s’appellent des variables artificielles, car elles n’ont aucune
interprétation économique. Notées par a et indexées par 1 et 2.

Min [Z* = a1 + a2]

SC

- A = 4X1 + 3X2 – e1 + a1 = 9000

- B = X1 + 2X2 – e2 + a2 = 4000
- X1 – e3 = 6400
- X2 – e4 = 4400
- X1,X2,e1,e2,e3,e4,a1,a2 ≥ 0

Pour l’objectif de ce P.L on doit minimiser une équation des variables artificielles pour les annuler

2- Recherche de la base initiale :

a) Ecriture matricielle de la forme canonique :
 x1
x2
4 3 −1 0 1 0 0 0 e1 9000
1 2 0 −1 0 1 0 0 e2 4000
=
1 0 0 0 0 0 1 0 a1 6400
0 1 0 0 0 0 0 1 a2 4400
e3
e4
On a une matrice identité de taille 4

La base initiale est donc composée de : a1, a2, e3, e4

3- Itération 0 :

N.B : à propos de l’ordre des variables dans le tableau, on ne met pas l’ordre de la matrice mais
l’ordre suivant : VARIABLES DE DECISION, VARIABLES D’ECART, VARIABLES ARTFICIELLES

- T0* x1 x2 e1 e2 e3 e4 a1 a2 c c/coefs
L1 a1 4 3 -1 0 0 0 1 0 9000 2250
L2 a2 1 2 0 -1 0 0 0 1 4000 4000
L3 e3 1 0 0 0 1 0 0 0 6400 6400

L4 e4 0 1 0 0 0 1 0 0 4400 ∞
L5 Z* -5 -5 1 1 0 0 0 0 -13000 -

On a une fausse contradiction car a1 et a2 ont une contribution de 1 de l’équation, donc on doit
changer Z*

Calcul de la contribution de x1, x2, e1, e3

On sait que Z* = a1 + a2 et

a1 = 9000 – 4x1 – 3x2 +e1

a2 = 4000 – x1 -2x2 + e2

Z* = 13000 – 5x1 – 5x2 + e1 + e2

T0* n’est pas optimale car x1 = -5 ≤ 0, X2 ≤ 0

1ere itération : T0* à T1*

V.E = x1, VS = a1, le pivot c’est 4

T1
- x1 x2 e1 e2 e3 e4 a1 a2 c c/coefs

L1 x1 1 ¾ -1/4 0 0 0 ¼ 0 2250 3000

L2 a2 0 5/4 ¼ -1 0 0 -1/4 1 1750 1400
L3 e3 0 -3/4 ¼ 0 1 0 -1/4 0 4150 ≤0
 L4 e4 0 1 0 0 0 1 0 0 4400 4400
L5 Z* 0 -5/4 -1/4 1 0 0 5/4 0 -1750 -

L1(T1*) = L1(T0*)/4

L2(T1*) = L2(T0*) – ¼*L1(T0*)

L3(T1*) = L3(T0*) - 1/4*L1(T0*)

L4(T1*) = L4(T0*)

L5(T1*) = L5(T0*) – (-5)*1/4*L1(T0*)

2éme itération : T1* - T2*

V.E = x2, V.S = a2, Pivot = 5/4

T2
- x1 x2 e1 e2 e3 e4 a1 a2 c c/coefs

L1 x1 1 0 -2/5 3/5 0 0 2/5 -3/5 1200

L2 x2 0 1 1/5 -4/5 0 0 -1/5 4/5 1400
L3 e3 0 0 2/5 -3/5 1 0 -2/5 3/5 5200
L4 e4 0 0 -1/5 4/5 0 1 1/5 -4/5 3000
L5 Z* 0 0 0 0 0 0 1 1 0

L1(T2*) = L1(T1*) – ¾/5/4*L2(T1*)

= L1(T1*) – 3/5*L2(T1*)

= (1, ¾, -1/4, 0, 0, 0, ¼, 0, 2250) – 3/5*(0, 5/4, ¼, -1, 0, 0, -1/4, 1, 1750)

= (1, ¾, -1/4, 0, 0, 0, ¼, 0, 2250) – (0, ¾, 3/20, -3/5, 0, 0, -3/20, 3/5, 1050)

= (1, 0, -2/5, 3/5, 0, 0, 2/5, -3/5, 1200)

L2(T2*) = L2(T1*)/ 5/4

= (0, 5/4, ¼, -1, 0, 0, -1/4, 1, 1750)/ 5/4

= (0 , 1, 1/5, -4/5, 0, 0, -1/5, 4/5, 1400)

L3(T2*) = L3(T1*)- (-3/4)/ 5/4*L2(T1*)

= L3(T1*)- (-3/5)*L2(T1*)

= L3(T1*) + 3/5*L2(T1*)

= (0, -3/4, ¼, 0, 1, 0, -1/4, 0, 4150) + 3/5*(0, 5/4, ¼, -1, 0, 0, -1/4, 1, 1750)

= (0, -3/4, ¼, 0, 1, 0, -1/4, 0, 4150) + (0, ¾, 3/20, -3/5, 0, 0, -3/20, 3/5, 1050)
 = (0, 0, 2/5, -3/5, 1, 0, -2/5, 3/5, 5200)

L4(T2*) = L4(T1*) - 1/5/4*L2(T1*)

= L4(T1*) – 4/5*L2(T1*)

= (0, 1, 0, 0, 0, 1, 0, 0, 4400) – 4/5*(0, 5/4, ¼, -1, 0, 0, -1/4, 1, 1750)

= (0, 1, 0, 0, 0, 1, 0, 0, 4400) – (0, 1, 1/5, -4/5, 0, 0, -1/5, 4/5, 1400)

= (0, 0, -1/5, 4/5, 0, 1, 1/5, -4/5, 3000)

L5(T2*) = L5(T1*) – (-5/4) / 5/4 * L2(T1*)

= L5(T1*) – (-1)*L2(T1*)

= L5(T1*) + L2(T1*)

= (0, -5/4, -1/4, 1, 0, 0, 5/4, 0, -1750) + (0, 5/4, ¼, -1, 0, 0, -1/4, 1, 1750)

= (0, 0, 0, 0, 0, 0, 1, 1, 0)

T2* est un tableau optimal car aucune des contributions des variables hors base n’est négatives ou
nulles,

L’objectif de cette première phase est de minimiser Z est avoir une base pour la deuxième phase

PHASE 2 :

Revenant à l’objectif initial : Min [ Z= 1000X1 + 800X2]

- T0 x1 x2 e1 e2 e3 e4 c c/coefs
L1 x1 1 0 -2/5 3/5 0 0 1200
L2 x2 0 1 1/5 -4/5 0 0 1400
L3 e3 0 0 2/5 -3/5 1 0 5200
L4 e4 0 0 -1/5 4/5 0 1 3000
L5 Z* 0 0 240 40 0 0 -2 320 000

Calcul des contributions de e1 et e2 dans Z :

Z = 1000X1 + 800X2

On doit exprimer Z en fonction des variables qui sont hors base (e1,e2)

On va faire cela d’après le tableau T0 en exprimant X1 et X2 en fonction de e1 et e2

X1 = 1200 +2/5 e1 – 3/5 e2

X2 = 1400 -1/5 e1 + 4/5 e2

On multiplie par les facteurs de X1 et X2

1000X1 = 1 200 000 + 400 e1 – 600 e2

800 X2 = 1 120 000 – 160 e1 + 640 e2

On remplace dans Z :

Z = 2 320 000 + 240 e1 + 40 e2

Le tableau T0 est optimale car on a achevé l’objectif de minimisation des variables de base

Donc la solution optimale :

X1 = 1200 tonnes , X2 = 1400 tonnes, Z min = 2 320 000 Dhs , e1 = 0, e2 = 0, e3 = 5200, e4 = 3000

Exercice 6 :

Max Z = [X1 + 2X2]

S.c

- 7X1 + 2X2 ≥ 28

- X1 + 6X2 ≥ 12

- X1 ≥ 0, X2 ≥ 0

1- De la forme canonique à la forme standard :

Max Z = [X1 + 2X2]

S.c

- 7X1 + 2X2 – e1 ≥ 28

- X1 + 6X2 – e2 ≥ 12

- X1 ≥ 0, X2 ≥ 0 , e1 ≥ 0 , e2 ≥ 0

2- Recherche de la base initiale :

x1
7 2 −1 0 x 2 28
* =
1 6 0 −1 e 1 12
e2
On a pas de base initiale donc on doit procéder à la méthode des deux phases
PHASE 1 :

Min Z = [ a1 + a2]

S.c

- 7X1 + 2X2 – e1 + a1 ≥ 28

- X1 + 6X2 – e2 + a 2 ≥ 12

- X1 ≥ 0, X2 ≥ 0 , e1 ≥ 0 , e2 ≥ 0, a1 ≥ 0, a2 ≥ 0

Recherche de la base initiale du PL* :

x1
7 2 −1 0 1 0 x 2 28
=
1 6 0 −1 0 1 e 1 12
e2
On a une matrice identité de taille 2

Le PL* admet une base initiale qui admet : (a1,a2)

- T0* x1 x2 e1 e2 A1 A2 c c/coefs
L1 a1 7 2 -1 0 1 0 28
L2 a2 1 6 0 -1 0 1 12
L3 Z* -8 -8 1 1 0 0 -40
On sait que :

Z- = a1 + a2

Et on sait que :

A1 = 28 – 7X1 – 2X2 + e1

A2 = 12 – X1 - 6X2 + e2

Donc

Z* = 40 – 8X1 + 8X2 + e1 + e2

T0* n’est pas optimale car on a encore des variables hors base qui sont encore négatives

Donc on va procéder à une peremière itération :

1ére itération T0* à T1*

V.E = X1

V.S = A1

Pivot = 7

N.B = on deux variables avec la même contribution donc on va chooisir une au hasard

- T1* x1 x2 e1 e2 A1 A2 c c/coefs
 L1 x1 1 2/7 -1/7 0 1/7 0 4 14
L2 a2 0 40/7 1/7 -1 -1/7 1 8 7/5
L3 Z* 0 -40/7 -1/7 1 8/7 0 -8

L1(T1*) = L1(T0*) / 7

L2(T1*) = L(T0*) – 1/7 * L1(T0*)

L3(T1*) = L3(T0*) + 8/7 * L1(T0*)

T1* n’est pas optimale puisqu’on a 2 variables hors base qui contribuent négativement

2ème itération T1* à T2*

V.E = X2

V.S = A2

Pivot = 40/7

- T2* x1 x2 e1 e2 A1 A2 c c/coefs
L1 x1 1 0 -3/20 1/20 3/20 -1/20 18/5
L2 x2 0 1 1/40 -7/40 -1/40 7/40 7/5
L3 Z* 0 0 0 0 1 1 0

L1(T2*) = L1(T1*) – 2/7 / 40/7 * L2(T2*)

L1(T2*) = L1(T1*) –1/20* L2(T2*)

L2(T2*) = L2(T1*) *7/40

L3(T2*) = L3(T1*) – (-40/7) / 40/7 * L2(T2*)

L3(T2*) = L3(T1*) + L2(T2*)

T2* est optimal , Fin de l premiere phase

PHASE 2 :

Revenir à l’objectif initial : Max Z = [X1 + 2X2]

- T2* x1 x2 e1 e2 c c/coefs
L1 x1 1 0 -3/20 1/20 18/5
L2 x2 0 1 1/40 -7/40 7/5
L3 Z 0 0 1/10 3/10 -32/5

Calcul des contributions de e1 et e2 dans Z

Z = X1 + 2X2

X1 = 18/5 +3/20 e1 – 1/20 e2

X2 = 7/5 – 1/40 e1 + 7/40 e2

X1 = 18/5 + 3/10 e1 – 1/20 e2

2X2 = 14/5 -1/20 e1 +7/20 e2

Z= 32 /5 +1/10 e1 + 3/10 e2

T0 n’est pas optimal , car on a encore des variables hors base qui contribuent positivement

Donc on va procéder à une première itération

1ére itération T0 à T1

V.E = e2

V.S = x1

Pivot = 1/20

- T1 x1 x2 e1 e2 c c/coefs
L1 E2 20 0 -3 1 72 Négative
L2 X2 7/2 1 -1/2 0 14 Négative
L3 Z* -6 0 1 0 -28

L1(T1) = L1(T0) *20

L2(T1) = L2(T0) + 7/2 L1 ( T0)

L3(T1) = L3(T0) – 6 L1 (T0)

T1 n’est pas optimal , car on a encore des variables hors base qui contribuent positivement

Donc on va procéder à une deuxième itération

2ème itération T1 à T2

V.E = e1

V.S = Aucune

Pivot = Aucun pivot

On conclue que ce PL n’admet pas une solution optimale

Séance 8 31/12/2020 10 :15

Exercie 7 :

Max Z = [3X1 + 2X2]

S.c

- X1 + 2X2 ≤ 2

- 2X1 + 4X2 ≥ 8

Passage à la forme canonique :

- X1 + 2X2 – e1 = 2

- 2X1 + 4X2 – e2 = 8

- X1 ≥ 0, X2 ≥ 0 , e1 ≥ 0 , e2 ≥ 0

Recherche de la base initiale

x1
1 2 1 0 x2 2
=
2 4 0 −1 e1 8
e2
On a pas la matrice identité de taille 2 , donc absence de base initiale évidente

Donc on va procéder à l’utilisation de la méthode des 2 phases

PHASE 1 : Résoudre le PL*suivant :

On va introduire une seule variable artificielle au niveau de la 2ème équation

Min [Z* = a]

Sc :
 - X1 + 2X2 + e1 = 2
- 2X1 + 4X2 -e1 + a = 8
- Xi, ei, a ≥ 0

Recherche de la base initiale du PL*

x1
x2
1 2 1 0 0 2
e1 =
2 4 0 −1 1 8
e2
a

On a une matrice identité de taille 2, donc le PL* admet une base initiale évidente (e1,a)

- T0* x1 x2 e1 e2 a c c/coefs
L1 E1 1 2 1 0 0 2 1
L2 a 2 4 0 -1 1 8 2
L3 Z* -2 -4 0 1 0 -8

On sait que : Z* = a et on sait que a = 8-2X1-4X2+e2

Donc Z*= 8-2X1-4X2+e2

Ce tableau n’est pas optimal car on a des variables H.B qui contribuent négativement

Donc on va procéder à une première itération

1ère itéation : T0* vers T1* :

V.E = X2, V.S = e1, Pivot = 2

- T1* x1 x2 e1 e2 a c c/coefs
L1 X2 ½ 1 1/2 0 0 1
L2 a 0 0 -2 -1 1 4
L3 Z* 0 0 2 1 0 -4

L1(T1*) = L1(T0*)/2

L2(T1*) = L2(T0*) – 2 L1(T0*)

L3tT1*) = L3(T0*) + 2L1(T0*)

On constate que T1* est optimale car les variables H.B sont positives , mais Z* est encore positive au
moments elle doit être nulle pour achever l’objectif du PL* qui de annuler la valeur artificielle

Z* = 4 différent de 0

Donc le PL initial n’a pas de solution optimale

Comme on peut le déduire depuis le PL initiale ou on a une contradiction

Exercice 8 :

Max [Z = x1 + 3x2]

s.c.

- 2x1+6x2 ≤ 30
- x1 ≤ 10
- x2 ≤ 4
- x1 ≥ 0, x2 ≥ 0

F.C à F.S :

Max [Z = x1 + 3x2]

s.c.

- 2x1 + 6x2 + e1 = 30
- x1 + e2 = 10
- x2 + e3 = 4
- Xi ≥ 0, ei ≥ 0

Recherhce de la base initiale :

x1
2 6 1 0 0 x2 30
1 0 0 1 0 e 1 = 10
0 1 0 0 1 e2 4
e3

Le PL admet une base initiale évidente : (e1,e2,e3)

- T0 x1 x2 e1 e2 e3 c c/coefs
L1 E1 2 6 1 0 0 30 5
 L2 E2 1 0 0 1 0 10 ∞
L3 E3 0 1 0 0 1 4 4
L4 Z 1 3 0 0 0

T0 n’est pas optimale, donc on va procéder à une première itération

1ère itération : T0 vers T1

V.E = X2 V.S = e3 Pivot = 1

- T1 x1 x2 e1 e2 e3 c c/coefs
L1 E1 2 0 1 0 -6 6 3
L2 E2 1 0 0 1 0 10 10

L3 X2 0 1 0 0 1 4 ∞
L4 Z 1 0 0 0 -3 12

L3(T1) = L3(T0)

L1(T1) = L1(T0) – 6*L3(T0)

L2(T1) = L2 (T0)

L4(T0) = L4(T0) – 3 L3(T0)

T1 n’est pas optimale car X1 contribue toujours positivement

Donc on va procéder à une deuxième itération

2ème itération : T1 vers T2

V.E=X1 , V.S =e1 Pivot = 2

- T1 x1 x2 e1 e2 e3 c c/coefs
L1 x1 1 0 1/2 0 -3 3
L2 E2 0 0 -1/2 1 3 7
L3 X2 0 1 0 0 1 4
L4 Z 0 0 -1/2 0 0 -15
L1(T2) = L1(T1)/2

L2(T2) = L2(T1) – ½* L1(T1)

L3(T2) = L3(T1)

L4(T2) = L4(T1) – ½ L1(T2)

Le tableau T2 est optimale, car les variables hors base contribuent d’une manière nulle ou négative

E1 = -1/2

E3 = 0

Donc ce PL admet une solution optimale

X1 = 3, X2 = 4, Z max = 15, e1 = 0, e2=7, e3=0

Cette solution n’est pas unique , car les variables hors base ne sont pas strictement négatives cont e
3=0

Recherche des autres solutions optimales

3ème itération : T2 vers T3

V.E = e3, V.S = e2, Pivot = 3

- T1 x1 x2 e1 e2 e3 c c/coefs
L1 x1 1 0 0 1 0 10
L2 E3 0 0 -1/6 1/3 1 7/3
L3 X2 0 1 1/6 -1/3 0 5/3
L4 Z 0 0 -1/2 0 0 -15

L2(T3) = L2(T2)/2

L1(T3) = L1(T2) + L2 (T2)

L3(T3) = L3(T2) – 1/3 L2(T2)

L4(T3) = L4(T2)

T3 est optimale , donc on a une 2ème solution optimale

X1 = 10, X2 = 5/3, Z max = 15, e1 = 0, e2 = 0, e3 = 7/3

1ère solution optimale ( 3,4)

2ème solution optimale (10, 5/3)

Vérifier est-ce que ces 2 solutions optimales sont adjacentes

- 2x1+6x2 ≤ 30 2x1+6x2 = 30
- x1 ≤ 10 x1 = 10
- x2 ≤ 4 x2 = 4
Donc les 2 solutions optimales sont sur la même frontière de l’équation 2x1 + 6x2 = 30 , donc elle
sont adjacente

Donc ce PL admet une infinité de solutions optimales , ces solutions sont tous les points qui se
trouvent sur le segment de droite reliant les 2 solutions optimales adjacentes.

Partie 2 : Techniques d’ordonnancement

- Contrainte de production
- Contrainte de temps
- Contrainte d’antériorité

Dans un premier temps on prendra en considération que les 2 dernières contraintes

On a 2 méthodes utilisées :

- La méthode MPM
- La méthode PERT

Ils sont basés sur la même théorie « Théorie des graphes »

1- La méthode MPM :

T+ : date au plus tôt de la tâche

T- : date au plus tard de la tâche

Calcul des dates au plus tôt :

T+(B) = T+(A) + durée (A)

Si la tâche C est précédée par 2 tâches on prend la plus grandes des valeurs

Calcul des dates au plus tard

T-(A) = T-(B) – durée (A)

Si la tâche A est suivie par 2 tâches on prend la plus petites des valeurs

Application :

1- Construction de tableau des niveaux

Niveau Tâches
0 A, B
1 C, D
2 E

2- Construction de tableau des successeurs

Tâches Successeurs
A C, D
B D
C E
D E
E -

3- Construction de réseau des tâches

Les tâches début et fin sont des tâches fictives avec une durée 0

4- Calcul de la marge de chaque tâche :

La marge totale : retard maximum qu’on peut admettre sur une tâche sans impacter la durée
optimale de projet

Une tâche sans marges totale est tâche critique

La durée optimale d’un projet est donnée par le cumul des durées des tâches critiques

La marge libre : c’est le retard permis qui n’impacte pas la durée totale du projet et la date au plus
tôt des tâches suivantes

Si un tâche est succédée par 2 tâches , on prend la valeur minimale