‫!

‪Welcome‬‬
‫ا‬
‫سهًل‪ ،‬اللهم اجعل‬ ‫اللهم ال سهْل اإال ما قد جعلته‬
‫ا‬
‫سهًل‪ ،‬اللهم ذكرني منه ما نسيتُ وال‬ ‫صعب لي‬
‫ال ا‬
‫حول وال قوة إال باهلل العلي العظيم‪.‬‬

‫‪1‬‬
C’est quoi la recherche
opérationnelle ?

ensemble des méthodes et techniques rationnelles

orientées vers la recherche du meilleur choix

2
Programmation
Linéaire
- Modélisation
- Solution graphique
- Forme standard
- Forme canonique
- Simplexe (simple , big M , 2 phases)
- Branch and Bound

01
• Généralement:

Problème

Min Max
(cout) (profit)
4
1-Modélisation :

Étape 01 : variables de décision

Étape 02: fonction objective

Étape 03: Contraintes

5
 Exemple Maximisation
une compagnie est spécialisée dans la production de deux types de produits : climatiseurs et
ventilateurs , le tableau suivant donne le nécessaire du fabrication : nombre d’heures machine , et
mains d’œuvre , le profit , et la disponibilité des ressources , > Maximisez le profit !!!!!

Heures Main d’œuvre profit

machine

Climatiseurs 2h/unité 3h / unité 25 Da / unité

Ventilateurs 2h/ unité 1h/unité 15 Da / unité

Total 240h 140h

disponible

Solution cliquez sur : Solution enonce 01 .pdf 6

Exemple Minimisation

Solution Cliquez ici : Solution enonce [Link]

7
EXERCICES :
MODELISATIONS
Enoncé 03 : Solution enonce [Link]

Enoncé 04 : Solution enonce [Link]

Enoncé 05 : Solution enonce [Link]

Enoncé 06 : Solution enonce [Link]

8
 2
Solution Graphique
• Les contraintes deviennent des égalités
• Trouver x et y pour dessiner la droite
• Tracer les (D) : chaque contrainte devient droite ( un graphe)
• Trouver l’ensemble des solutions réalisables
• Trouver la solution optimale ,

9
 Exemple :
Heures Main d’œuvre profit
machine

Climatiseurs 2h/unité 3h / unité 25 Da / unité Max (Z) = 25 x + 15 y

Sous les contraintes :
2 x + 2 y < = 240
Ventilateurs 2h/ unité 1h/unité 15 Da / unité 3x + y < = 140
x>= 0, y > = 0

Total 240h 140h

disponible

10
1- Les contraintes deviennent des égalités 2- Trouver x et y pour dessiner la droite

2x +2y = 240 (D1) : 2x +2y = 240 pt (0, 120) , pt (120, 0)

3x + y = 140 (D2) : 3x + y = 140 pt ( 0 ,140), pt (40, 20)

3- Tracer les (D ) ( résultat : un graphe)

PS : le graphe est un peu décalé 4- Trouver l’ensemble des solutions réalisables:

La couleur noir présente les solutions réalisables ,
n’importe quel x ou y réalise les contraintes

5- Trouver la solution optimale:

La solution optimale se trouve dans les extimités du
graphes ( A , B , C , D )

11
 PS : le graphe est un peu décalé Comment choisir la solution optimale ?
1- Calculer les x et y de chaque point
A , B , C , D mathématiquement ,
2- remplacer dans la fonction objective et
calculer Z
3- Le plus grand Z donne la quantité optimale
de x et y à produire

La solution optimale est pour

x = 10 et y = 110
qui donne Z = 1900
A ( 140/3 , 0 ) A ( 140/3, 0 ) -> Z = 3500/3
B ( 10,110 ) B ( 10, 110) -> Z = 1900
C ( 0 , 120 ) C (0 ,120 ) -> Z = 1800
D ( 0,0) D ( 0,0) -> Z = 0

12
 Z = 1900
X = 10
Y = 110

Pour un profit maximal Z = 1900 da il faut produire

10 climatiseurs et 110 ventilateurs

13
Exercices
Cliquez
graphique_Exos.pdf

Cliquez
Solutions_graphique_Exos.pdf

14
3 - Forme Standard
Ax=B

Contrainte : supérieure ou égale > =

Inférieure ou égale < = et « b » négatif
Rendre « b » positif et Ajouter -e, +A

Contrainte : égale =
Ajouter +A

Contrainte : inférieure ou égale et « b » positif < =

Ajouter +e

A : variable artificielle
E : variable d’écart 15
 4- Forme Canonique

• Max (Z) = - Min (-Z)

• x + y > = b → -x -y < = -b

16
 5- Simplexe
Simplexe

Simple BIG M 2 Phases

17
 Astuces
1- les contraintes → Canoniques
2- Max → Cj – Zj
3- Min → Zj – Cj
Notions
1- Variables de base
2- Pivot
3- Variable entrante
4- Variable sortante

Exceptions
Watch :
[Link]

18
 PIVOTAGE
case ligne pivot * case colonne pivot
Nouvelle valeur = Ancienne valeur -
pivot

19
Comment trouver la solution ?
Début

Ecrire programme sous forme standard

Construire le premier tableau

Choisir la variable à introduire dans la base NON

Choisir la variable à enlever Les coefficients de

la fonction sont OUI
Encadrer le pivot tous nul /
négatifs ???
Diviser la ligne du pivot par pivot
FIN

Calculer les valeurs autres lignes

20
 Cj ‫معامًلت جميع‬
Tableau Simplexe ‫المتغيرات من‬
Fonct object
VB : variables de base ( expliquée en détails dans les diapos suivantes, )
Zj exemple
Cj / / Coeff Coeff ,,, 0 0 0,,, W’’ =
x y (w*a)+(w’*b)
/ VB Q x y ,,, e1 e2 ,,, RT Cj –Zj ‫نحسب‬
‫اكبر قيمة هي‬
a w Colonne pivot
‫و نلقا‬
b W’ Variable entrante
Rt =
/ Zj / W’’ Chaque case = Q /
case ligne
colonne pivot
/ Cj –Zj /
‫ا صغر قيمة هي‬
ligne pivot
Pivot = ‫و نلقا‬
‫نقطة تقاطع‬ Variable sortante
Ligne et colonne pivot
 Tableau Simplexe 02 :

Diviser la ligne de la variable sortante ( ligne pivot) sur le pivot

Remplir les autres cases par la règle du pivotage

Répéter les étapes précédentes avec les nouvelle valeurs

Répéter jusqu’à Cj – Zj < = 0

 Exemple :
Max (Z) = 100 x + 150 y
Sous les contraintes :
10 x + 4 y < = 160
x + y < = 20
10 x + 20 y < = 300
x>= 0, y > = 0

Max (Z) = 100 x + 150 y + 0 e1+ 0e2+ 0 e3

Sous les contraintes :
10 x + 4y + e1 = 160
x + y +e2 = 20
10 x + 20 y +e3 = 300
x ,y , e1 , e2 , e3 >= 0

23
• Transformation → standard :
Max (Z) = 100 x + 150 y Max (Z) = 100 x + 150 y + 0e1+ 0e2+ 0 e3
Sous les contraintes : Sous les contraintes :
10 x + 4 y < = 160 10 x + 4y + e1 = 160
x + y < = 20 x + y +e2 = 20
10 x + 20 y < = 300 10 x + 20 y +e3 = 300
x>= 0, y > = 0 x ,y , e1 , e2 , e3 >= 0
Comment choisir les variables de base ?
- Le nombre de contrainte = le nombre des variable d’écarts
- Dans ce cas 3 contraintes et 3 variables d’écart
- Voir les coeff du chaque variable et décider quels sont les var de base

x1 x2 e1 e2 e3
1 , 0,0
Contrainte 1 10 4 1 0 0
La matrice est 0, 1,0
Contrainte 2 1 1 0 1 0
0,0,1
Contrainte 3 10 20 0 0 1

24
Remplir le 1 er tableau :
Max (Z) = 100 x + 150 y + 0e1+ 0e2+ 0 e3
- Cj Coeff fonction objective,
- Variable de base : e1 , e2,
Sous les contraintes :
10 x + 4y + e1 = 160
- Qt = contrainte
x + y +e2 = 20
10 x + 20 y +e3 = 300
- = 160*0 + 20*0+300*0
x ,y , e1 , e2 , e3 >= 0

Cj / / 100 150 0 0 0 - = 10*0 + 1*0 +10*0

/ VB Q x y e1 e2 e3 RT - La plus grande valeur

Cj -Zj = colonne pivot
0 e1 160 10 4 1 0 0 40
- RT = Q / case colonne pivot
- La plus petite valeur = ligne pivot
0 e2 20 1 1 0 1 0 20
- Le pivot = 20
0 e3 300 10 20 0 0 1 15
- y : variable entrante
- e3 variable sortante,
/ Zj 0 0 0 0 0 0 - Cj-Zj > 0 → tableau 2 ,

/ Cj – / 100 150 0 0 0 ‫تمثل الربح اذا انتج الكمية المحددة‬

Zj ‫من‬var de bases 25
Tableau_02: C
j

/
/

VB
/

Q
100

x
150

y
0

e1
0

e2
0

e3 RT

0 e1 160 10 4 1 0 0 40

0 e2 20 1 1 0 1 0 20
Cj / / 100 150 0 0 0
0 e3 300 10 20 0 0 1 15

/ Zj 0 0 0 0 0 0
/ VB Q x y e1 e2 e3 RT / Cj / 100 150 0 0 0
–Zj

0 e1 100 8 0 1 0 -1/5 12,5

- Changer e3 par y et son coeff,
- Diviser la ligne du pivot sur pivot
0 e2 5 1/2 0 0 1 -1/20 10 - Remplir les autres cases par
pivotage , (explication dans diapo
suivante )
150 y 15 1/2 1 0 0 1/20 30
- Répeter les étapes 1 : calculer Zj
- Calculer Cj- Zj
/ Zj 2250 75 150 0 0 15/2
- 25 > 0 → tableau 3
- E2 sortante
/ Cj – / 25 0 0 0 -15/2
- Calculer Rt
Zj
26
Tableau_03:
répéter les mêmes étapes
Cj / / 100 150 0 0 0

/ VB Q x y e1 e2 e3 RT

0 e1 20 0 0 1 -16 3/5 Cj – Zj <= 0

La solution optimale est
100 x 10 1 0 0 2 -1/10 X= 10 et y = 10 donnent z
= 2500
150 y 10 0 1 0 -1 1/10

/ Zj 2500 100 150 0 50 5

/ Cj – / 0 0 0 -50 -5
Zj
27
28
 5- Simplexe
Simplexe

Simple BIG M 2 Phases

29
 Notions et Méthodes :
- Dans le cas d’ajout d’une variable d’écart et une variable artificielle ,
- M est un nombre trés grand → + infinie
Si la fonction objective est Max on pénalise M par un –
- Si min + M
- M est très grand pour assurer son exclusion de la solution optimale ( puisque A est
artificielle) ,
- Le simple simplexe ,

Watch :
[Link]

30
 5- Simplexe
Simplexe

Simple BIG M 2 Phases

31
 Watch :

[Link]
qpvt=simplexe+%c3%a0+2+phases&view=detail&mid=84B7399035D39986
6DE784B7399035D399866DE7&&FORM=VRDGAR&ru=%2Fvideos%2Fsearc
h%3Fq%3Dsimplexe%2B%25c3%25a0%2B2%2Bphases%26qpvt%3Dsimp
lexe%2B%25c3%25a0%2B2%2Bphases%26FORM%3DVDRE

32
 6 –BRANCH AND
BOUND
X1 = 15/4 = 3,75 → 3<3,75<4
Je calcule Z et X2 pour 3 et 4
X1 = 3 , X2 = 3 , Z =39 optimale ?
X 1 = 4 donne → X2 = 9/5 = 1,8 → 1<1,8<2
Je calcule Z et X1 pour 1 et2
X2 = 2 non réalisable ( dépant le problème )
X2 = 1 , X 1= 4,4 , Z = 40,5
X1 = 4,4 → 4<4,4<5
Je calcule Z et X2 pour 3 et 4
X1=4, X2 =1, Z =37optimale ?
X1 = 4,4 → 4<4,4<5
Je calcule Z et X2 pour 3 et 4
X1=5, X2 =0, Z =40 optimale ?
Comparer 39 et 40 → 40 > 39
alors Z = 40 ( 5 , 0)
33
 Ressources :

-Programmation linéaire et application K,Mellouli * A, El Kamel * P,Borne

- Saïd Chermak - YouTube

By : BENHACINE Serine Amina

34
Etudiante en informatique : université Constantine 2
‫‪Thank you‬‬
‫! ‪<3‬‬
‫وفقك هللا وسدد خطاك‬
‫‪35‬‬