Cours

Cours " Recherche Opérationnelle "
1
Introduction Générale
• La recherche opérationnelle est une discipline qui a pour rôle d'assurer la compréhension et la modélisation des
systèmes industriels et du secteur public et de les traduire au monde théorique fondé principalement par des
mathématiques, des statistiques et de l'informatique.
• L'employabilité de la recherche opérationnelle est composée de deux phases concaténées dont la première
consiste à formuler mathématiquement un problème qui demande une analyse détaillée et suffisamment précise
pour recueillir les caractéristiques essentielles du problème posé en plus d'un savoir-faire et d'une certaine
expérience.
• Dans la deuxième phase on procède à la résolution du problème par l'utilisation d’algorithmes rigoureux et bien
déterminés.
2
Introduction Générale
• L’objectif de ce cours est double, dans un premier temps nous allons nous concentrer sur la
formulation des modèles d’optimisation.
• Dans cette partie, nous commencerons par la collecte des données et des informations
fournies par le problème traité.
• Ensuite nous présentons les différentes étapes à suivre pour donner une vision
mathématique globale avant de passer à la deuxième étape qui concerne la présentation des
différentes techniques de résolution de ces problèmes dont le but est de trouver la meilleure
solution(appelée solution optimale) pour le problème étudié.
3
Chapitre 1 : Introduction à l'Optimisation
4
1.1 Quelques exemples de modèles mathématiques
• Exemple 1
• Une entreprise fabrique des tables et des chaises à partir de deux matières : le bois et la peinture, sachant que la
réalisation d'une table nécessite 3 m de bois et 4 kg de peinture, la réalisation d'une chaise nécessite 2 m de bois et 1 kg
de peinture. Les moyens financiers de l'entreprise acceptent un approvisionnement de 100 m de bois et 120 kg de
peinture par semaine. Les produits ainsi fabriqués fournissent un bénéfice de 500 D par table et 300 D par chaise
vendue.
• Question
• À partir de la description donnée, plusieurs questions se révèlent :
 Quelle quantité de table et quelle quantité de chaise doit produire l'entreprise ?
 Quelles sont les ressources disponibles, les limites et les barrières à ne pas dépasser ?
 Quel est le but de l'entreprise ? 5

1.1 Quelques exemples de modèles mathématiques
 Dans ce cas plusieurs propositions intuitives peuvent avoir lieu par exemple :
• 32 tables et 0 chaise avec un bénéfice de 16000
• 20 tables et 20 chaises avec un bénéfice de 16000
• 0 table et 50 chaises avec un bénéfice de 15000
• etc.
 Nous remarquons qu'il y a une infinité de solutions possibles. Parmi toutes les solutions proposées,
comment choisir la meilleure ? Existe-t-il une technique qui pointe directement sur la solution optimale ?
Pour répondre à ces questions plusieurs techniques inspirées de la recherche Opérationnelle sont
proposées.
6
1.2. Définition de la Recherche Opérationnelle RO
• La recherche Opérationnelle est une discipline qui permet de formuler des problèmes par
des supports scientifiques, mathématiques et informatiques pour aider à mieux décider.
• La Recherche Opérationnelle ( R.O.) est avant tout un outil d’aide à la décision.
• Autrement définie, la Recherche Opérationnelle (RO) traduit des énoncés ou des cahiers de
charges liés à des problématiques spécifiques sous forme de méthodes et des démarches à
base d'équation mathématique, des algorithmes et des outils statistiques.
• La Recherche Opérationnelle (RO) permet d'assurer la communication entre le milieu

industriel (les secteurs extérieurs) et les applications théoriques dans le but de proposer les
solutions les mieux adaptées à une situation donnée. 7
• La procédure utilisée par la recherche Opérationnelle RO peut être schématisée
comme suit :
8
Figure 1.1 Schéma de procédure utilisée par la
• La recherche opérationnelle (RO) est utilisée dans les domaines ou la prise de

décision fait appel à la résolution des problèmes d’optimisation telle que les
problèmes de :
Dimensionnement, localisation
Gestion de ressources
Rentabilisation des investissements
Détection de dysfonctionnements : diagnostics, réparation, maintenance.
Partage des ressources
9
1.3 Enjeux de la recherche opérationnelle RO
• L'utilisation de la recherche opérationnelle devient de plus en plus sollicitée dans la vie

quotidienne et à différents niveaux puisqu'elle offre plusieurs avantages et traite plusieurs
points tels que :
 l'amélioration de la compétitivité des entreprises
 la préservation des emplois
 l'accession à l’innovation
elle propose les meilleures décisions stratégiques
fournit une meilleure gestion des ressources. Etc. 10

1.4 Formulation d’un problème d’optimisation
• La modélisation du problème ou le passage du texte vers les équations mathématiques ne se fait pas
de manière aléatoire. Il doit vérifier certaines conditions et doit passer par plusieurs étapes :
l’analyse, la modélisation et le critère à optimiser décrit comme suit :
1.4.1 Analyse
Dans cette phase, on commence toujours par l'identification des données nécessaires à la résolution
du problème, les valeurs de consommations ou les fiches techniques des articles, la quantité des
ressources disponibles, les coûts de transport, la capacité de production, les gains engendrés par
chaque article ou les dépenses établies pour la réalisation d'une action.
Dans cette phase, on détermine les composantes, les enjeux et les limites du problème. Toutes ces
11
1.4.2 Modélisation
• L’optimisation repose toujours sur des modèles mathématiques qui sont

généralement simples et partiels. Pour définir le modèle du système, on définit :
 Ses variables
• Une fois l'analyse effectuée, on détermine les variables du Système qui représente
les décisions à prendre et qui doit répondre à un certain nombre de questions : que
faut-il réaliser et en quelle quantité ? Combien doit-on acheter ? Combien de classes
à faire dans une école ? Les variables représentent les inconnues du système.
12
 Les contraintes
• Les objets mathématiques qui assurent l'interaction et la liaison des variables par
rapport aux ressources disponibles et aux données du problème sont appelées
contraintes.
1.4.3 Critère a optimisé
• Représente l’objectif ou le but attendu du problème. il peut être une fonction de

minimisation lorsqu'il s'agit d'une dépense, d'un investissement ou une fonction de
maximisation lorsqu'il s'agit d'un profit ou de gain.
13
1.4.4 Application a un exemple
14
• Solution : reprenons les données de l'exemple sur un tableau :
 Les variables :
x1 : représente la quantité des tables ;
x2 : représente la quantité des chaises.
 Les contraintes :
Pour le bois : 3x1 + 2x2 ≤ 100 (1)
Pour la peinture : 4x1 + 5x2 ≤ 150 (2)
15
• Pour soulever le problème de la non-négativité des variables, puisqu'on
ne peut pas produire moins deux tables ou moins vingt chaises nous
supposons que les variables sont positives, en ajoutons une contrainte
supplémentaire au problème :
16
1.5 Solutions d’un problème
Solution admissible
• On appelle solution admissible (ou solution) d’un problème tout vecteur x ∈ S qui satisfait
toutes les contraintes du problème.
Solution optimale
• On appelle solution optimale x*, la solution parmi toutes les solutions admissibles qui
fournissent le meilleur résultat, c'est à dire de trouver le max pour un problème de
maximisation ou trouver le min pour un problème de minimisation.
17
1.6 Exemples d'applications
1.6.1 Problème de production
• Une usine fabrique 2 produits P1 et P2 en utilisant un certain nombre de
ressources : post opératoire (machine), main-d'oeuvre et emballage.
• Ces besoins sont indiqués dans le tableau ci-dessous. Par ailleurs, chaque
ressource est disponible en quantités limitées.
18
• Les deux produits P1 et P2 rapportent à la vente respectivement des bénéfices
de 600 D et 400 D par unité. Quelles quantités de produits P1 et P2, doit
produire l’usine afin de maximiser le bénéfice total venant de la vente des 2
produits ?
Choix des variables (les inconnues)
• x1 et x2 sont respectivement les quantités des produits P1 et P2 à fabriquer
(x1, x2 ∈ N).
19
Choix de la fonction objectif à maximiser
• La fonction objective F correspond au bénéfice total. Elle vaut :
F(x1, x2) = 600x1 + 400x2.
• Le problème se traduit donc par :
Max F= 600 x1 + 400 x2 .
Détermination des contraintes
a) La disponibilité de chacune des ressources s'écrit sous la forme suivante :
20
b) Positivité des variables : x1, x2 ≥ 0.

En résumé, le problème de production se modélise sous la forme:
21
• 1.6.2 Réseaux de transport
• On désire acheminer des marchandises de n dépôts à m points de vente
• On connaît :
cij avec i = 1..n et j = 1..m, coût de transport (i, j),
Xi avec i = 1..n, stocks de dépôts,
Dj avec j = 1..m, niveaux de demande aux points de vente.
• On recherche, pour chaque couple (i, j), la quantité (positive) wij à transporter
du dépôt Xi au point de vente Dj.
• Question : formuler mathématiquement le problème
22
• Solution : formulation mathématiquement du problème.
• Pour la formulation de cet exemple nous nous avons choisit un réseau

composé de 4 dépôts (n=4) et 6 points de vente (m=6).
• Les variables :
• w11, w12, w13, w14, w15, w16, w21, w22, w23, w24, w25, w26, w31, w32,
w33, w34, w35, w36, w41, w42,w43, w44, w45, w46 >= 0
23
• Les contraintes :
Contraintes de capacité des producteurs :
• w11+ w12+ w13+ w14+ w15+ w16 = X1
• w21+ w22+ w23+ w24+ w25+ w26 = X2
• w31+ w32+ w33+ w34+ w35+ w36 = X3
• w41+ w42+ w43+ w44+ w45+ w46 = X4
24
Contraintes de satisfaction de la demande :

• w11 + w21 + w31 + w41 = D1
• w12 + w22 + w32 + w42 = D2
• w13 + w23 + w33 + w43 = D3
• w14 + w24 + w34 + w44 = D4
• w15 + w25 + w35 + w45 = D5
• w16 + w26 + w36 + w46 = D6
25
Fonction objective:
• Min Z = c11 w11+ c12w12+ c13w13+ c14w14+ c15w15+ c16 w16+

c21w21+ c22w22+ c23w23+c24w24+ c25w25+ c26w26+ c31w31+
c32w32+ c33w33+ c34w34+ c35w35+ c36w36+ c41w41+ c42w42+
c43w43+ c44w44+ c45w45+ c46w46
26
• Solution du problème de programmation linéaire :
• Le critère représente le coût total de transport.

• Les contraintes expriment l’égalité de l’offre et de la demande pour chaque point de
vente et chaque dépôt.
27
1.7 Définitions mathématique
• 1.7.1 Problème d’optimisation :
• Un problème d’optimisation est un problème d’analyse fonctionnelle qui
cherche l’extremum d’une fonction de n variables sur un domaine
appartenant à :
28
1.7.2 Critère
Le critère représente la fonction objectif:
 Maximiser f (x) qui est équivalent à minimiser −f (x).
1.7.3 Contraintes
Chaque fonction gi définissant une contrainte est une fonction
de sur R
Toute contrainte égalité h(x) = 0 est équivalente à :
29
1.7.4 Non-négativité
• Tout nombre, positif ou négatif, peut toujours être écrit comme la

différence de deux nombres non négatifs (par exemple, - 4 = 6 - 10).
• Il suffit donc de remplacer la variable d'activité par la différence de

deux nouvelles variables d'activité non négatives (le nombre de
variables d'activité augmente de 1).
30
1.8 Complexité Algorithmique
1.8.1 Notion de Complexité
• La complexité algorithmique est une notion qui concerne l'évaluation des performances des algorithmes
réalisant les mêmes procédés ou les mêmes fonctionnalités et permettant de comparer et de déterminer
si un algorithme "a" est meilleur qu'un algorithme "b" et s'il est optimal ou s'il ne doit pas être utilisé.
• Le but principal pour tout algorithme d’optimisation globalement convergent est de trouver une valeur
très proche de la solution optimale au bout d'un certain nombre fini d’itérations. Mais ce nombre peut
être extrêmement grand. Dans ce contexte, l'étude de la complexité algorithmique prend en
considération le nombre d’opérations, plus précisément le temps d’exécution nécessaire sur ordinateur et
l’encombrement mémoire, en fonction de la taille du problème à traiter à savoir le nombre de variables et
le nombre de contraintes du problème.
31
• Considérons l’exemple-1 suivant :
32
Le temps d’exécution nécessaire pour cet algorithme t(n), composé de plusieurs temps de
chaque instruction. Nous supposons que :
• t1 est le temps d’exécution entre le début et la lecture des différentes variables d'initiation {"1"}
• t2 représente le temps d’exécution de la comparaison {"2"}
• t3 est le temps d’exécution de l’action {"3"}
• t4 est le temps d’exécution de l’action {"4"}
 Sachant que le temps t2, t3, t4 sont bien définis et inchangés durant l'exécution de cette ligne.
Par ailleurs ces temps représentent une boucle qui se répète n fois.
33
• Donc le temps nécessaire pour l'exécution de la boucle est donné par :
• De ce fait, le temps d’exécution t(n) de cet algorithme s’écrit :
• Ce qui signifie que le temps d’exécution dépend linéairement de la taille n.
34
1.8.2 Évaluation temporelle

• L'évaluation temporelle d'un algorithme peut avoir plusieurs possibilités parmi
elles lorsqu'il s'agit d'une :
• Somme des temps exp : l'exécution de trois actions l'une après l'autre ou chaque
action demande un temps de traitement relatif,
35
• Maximum de temps exp : c'est dans le cas d'une boucle avec la condition si
• si < condition est vérifiée > alors on effectue
• Somme des temps de passages successifs exp:

tant que < condition est vérifiée > faire Traitement (t1)
Le temps d'exécution : tn = n* t1 avec n le nombre de tests à effectuer
36
• Note : d'une manière générale, les performances asymptotiques des

algorithmes dépendent principalement du nombre de variables, n, et la
taille du problème, en négligeant les termes de degré inferieur par
exemple :
37
Chapitre 2 :Formulation d'un programme linéaire
38
1 Introduction
• La programmation linéaire est l’une des plus importantes techniques d’optimisation
utilisées en recherche opérationnelle. Ceci est dû à la facilité de la modélisation, à
l’efficacité des algorithmes développés et à l’existence sur le marché de nombreux
logiciels.
• La généralisation de micro-informatique a mis la programmation linéaire à la portée de

tous.
• L'objectif de programmation linéaire est de déterminer l’affectation optimale de

ressources rares entre des activités ou produits concurrents. Les situations économiques
demandent souvent qu’on optimise une fonction sous plusieurs contraintes prenant la
39
1 Introduction
 En mathématiques, les problèmes de programmation linéaire (PL)
sont des problèmes d'optimisation où la fonction objective et les
contraintes sont toutes linéaires.
40
2 Programmation linéaire
• La programmation linéaire est une branche des mathématiques appliquées et plus

précisément de l'optimisation dont l'objectif est minimiser ou maximiser une fonction
numérique à plusieurs variables sachant que ces dernières sont liées par des relations
appelées contrainte.
• Le principe de la programmation linéaire est fondé sur le fait que :
• La fonction à optimiser appelée fonction objectif ou fonction économique a une

expression linéaire ;
• Les expressions des contraintes sont tous linéaires. 41

42
• Remarque : En économie et gestion, l'objectif est à :

• Maximiser s'il s'agit d'un avantage (bénéfice, coût de vente, rendement.......) ;
• Minimiser s'il s'agit d'un inconvénient (perte, coût de production, dépense,
consommation.....)
43
3 Forme d’un programme linéaire
1 Forme générale
La forme générale d’un problème d’optimisation est la suivante :
44
D'une manière plus détaillée, un programme linéaire (PL) est dit sous
forme générale s’il s'écrit de la façon suivante :
La fonction 2.1 peut s'exprimer par une sommation de n terme (variables)

comme suit :
45
Sous les contraintes :
46
2 Forme standard ou forme canonique d’un programme linéaire
• Un problème linéaire est sous forme standard si toutes les contraintes sont des
contraintes égalité. Pour transformer une contrainte d'inégalité en contrainte
d'égalité, il faut ajouter aux membres de gauche d’une contrainte, une quantité (une
mesure) appelée variable d'écart qui sert à absorber l'écart entre le membre gauche
et le membre droit d'une contrainte si l'écart existe, bien sûr, sinon cette variable
vaut zéro.
• La forme standard peut être donnée par la forme suivante :
47
• Cette forme standard est obtenue en introduisant des variables d'écart dans
toutes les contraintes d'inégalité(à) et que ces variables soient non négatives(β).
• La forme canonique d'un programme linéaire peut être exprimée par un
ensemble de vecteurs comme suit :
48
Et la matrice A de taille m x n
Z= CX est la fonction objective, ou critère à

minimiser. 49
• Exemple :
• Reprenons l’exemple du problème de production de l’introduction. Sous
forme standard (en introduisant des variables d'écart), le PL s'écrit :
50
• Pour cet exemple :
Le vecteur des variables dans le système est :
Le vecteur des coefficients c est donné par c=(600 , 400 , 0 , 0 , 0) puisque
max F peut s'écrire comme suit :
 Le vecteur des coefficients b est donné par b=(55 , 27 , 20)

 La matrice A :
51
4 Construction des programmes linéaires :
Modélisation
• Pour modéliser un problème linéaire, il faut suivre les étapes suivantes :
• I) Identifier les variables principales ou les variables de décision du

problème.
• II) Exprimer la fonction objectif en termes des variables identifiées en
précisant s'il s'agit d'un problème à maximiser ou à minimiser (l'objectif
traduit les buts et les préférences des décideurs économistes).
• III) Formuler les contraintes sous forme d'équations et (ou) d'inéquations
linéaires.
52
Modélisation
53
Modélisation
54
4.1 Énonce du problème
• Une entreprise fabrique deux produits A et B, en utilisant une machine m
et deux matières premières p et q.
• On dispose chaque jour de 8 heures de m, de 10 kg de p et de 36 kg de q.
• On suppose que :
— la production d’une unité de A nécessite 2 kg de p et 9 kg de q, et utilise la
machine m durant 1 heure ;
— la production d’une unité de B nécessite 2 kg de p et 4 kg de q, et utilise la
machine m durant 2 heure ;
— les profits réalisés sont de 50 dh par unité de A et 60 dh par unité de B.
L’objectif que poursuit l’entreprise est de maximiser le profit qu’elle pourra
tirer, par jour, de ces 2 produits en utilisant au mieux ses ressources.
55
4.1 Énonce du problème
• Le tableau suivant résume les données afférentes à ce problème de

production :
56
4.2 La construction d’un modèle linéaire
• Quelles sont les informations dont doit disposer le directeur de l’entreprise

pour considérer que son problème est résolu ?
• Il suffit de connaître la quantité du produit A et la quantité du produit B à
fabriquer quotidiennement, n’est-ce pas ?
• Agissons comme si ces quantités nous étaient connues et dénotons-les par :
• x1 = la quantité du produit A à produire
• x2 = la quantité du produit B à produire
Les variables x1 et x2 sont dites variables de décision.
57
• Quel profit l’entreprise retirera-t-elle de la vente de ces deux produits ?
• Il s’agit d’additionner les bénéfices à tirer de chacun des 2 produits :
pour le produit A, elle retire 50 dh par unité et en fabrique x1 unités ;
cette production lui rapporte donc un profit de (50 x1) dh ;
de même, la quantité x2 du produit B lui permet de faire un profit de (60 x2)
dh.
Le profit total à tirer des deux produits s’élève donc à : (50 x1 + 60 x2) dh
58
• Nous dénoterons ce profit total par z et laisserons implicite l’unité monétaire :
z = 50 x1 + 60 x2
• Nous cherchons évidemment à rendre z aussi grand que possible en donnant à
x1 et x2 des valeurs appropriées.
• La grandeur z est une fonction qui, à chaque plan de production (une quantité
de A, une quantité de B), associe le nombre de dinars que l’entreprise retirerait
comme profit si elle adoptait ce plan. Cette fonction z, qui traduit l’objectif de
notre problème, s’appelle fonction objectif ou fonction économique. Et,
comme nous cherchons à rendre z aussi grand que possible, nous écrivons :
Maximiser z où z = 50 x1 + 60 x2
59
• ce que généralement l’on convient d’abréger comme suit :

• Max z = 50 x1 + 60 x2
• S’il ne s’agissait pour l’entreprise que de maximizer z, il suffirait de laisser
augmenter x1 ou x2 pour que z prenne une valeur aussi grande qu’elle le
souhaite.
• Mais s’attendre à de tels profits s’apparente plus au rêve qu’à la situation
de notre entreprise. Il y a bien sûr des empêchements naturels, appelés
contraintes, qui freinent le rêve d’un profit infini. Prenons en
considération tour à tour chacune des contraintes
60
• Contrainte relative à la machine m Le temps d’utilisation de la

machine m pour fabriquer les produits A et B ne peut excéder les 8
heures disponibles :
• Or, ce temps utilisé est la somme des heures consacrées à chacun des
types de produits. Pour le produit A, le temps nécessaire à la
fabrication de la quantité x1 se calcule ainsi :
61
62
• On emploie le signe «<=», et non « = », car il n’est pas obligatoire que toutes
les heures disponibles soient utilisées pour la fabrication des produits A et B,
bien qu’il ne soit pas interdit qu’il en soit ainsi.
• Contraintes relatives aux matières premières: En s’inspirant de la contrainte
relative à la machine, ces contraintes s’écrivent tout naturellement :
63
• Contraintes de positivité: Elles assurent que la solution ne comporte pas

des valeurs négatives (inacceptables).
• Le modèle se résume ainsi :
64
4.3 Variables d’écart
65
4.3 Variables d’écart
• Afin de ramener les contraintes à des égalités (qui sont plus faciles à
traiter que les inégalités), on introduit des variables d’écart.
• Ces variables seront toujours, comme les variables de décision x1 et x2,
positives ou nulles. Après l’ajout des variables d’écart x3, x4 et x5 relatives
aux contraintes (m), (p) et (q), nous obtenons la formulation :
• La variable d’écart d’une contrainte représente la quantité disponible non

utilisée. C’est l’écart entre la disponibilité et le besoin. 66
4.4 Généralisation : Problème de
production
• Soient m machines Mi (i = 1,. . ., m) qui fabriquent en série n types de
produits Pj (j = 1,. . ., n). La machine Mi a une capacité maximum de bi
unités de temps. La fabrication d’une unités du produit Pj nécessite
l’utilisation de la machine Mi durant aij unités de temps.
• Si cj représente le gain relatif à la production d’une unité du produit Pj
67
4.4 Généralisation : Problème de
production
• la résolution du problème fournira les valeurs optimales des quantités
xj à produire de chacun des produits ;
• la fonction économiques représente le gain total ; le premier membre
de chaque contrainte (Mi) représente le temps total d’utilisation de la
machine Mi .
• Les valeurs des variables d’écart associées à chacune de ces
contraintes correspondent au temps disponible non utilisé de chaque
machine
68
5 Résolution de programmes linéaires
• Il existe plusieurs techniques de résolution pour les programmes linéaires.
Cela dit nous présenterons dans cette section :
• la résolution graphique et la résolution analytique en détaillant deux
procédures : méthode Simplexe et tableaux Simplexe.
5.1 Résolution graphique
• La résolution graphique d'un problème linéaire consiste à tracer la droite qui
sépare les demi-plans pour chaque contrainte tout en conservant le demi-
plan acceptable, c'est-à dire le demi-plan des solutions réalisables pour la
contrainte. L'intersection des différents demi-plans de toutes les contraintes
sans oublier les contraintes de positivité forme le polygone des solutions,
appelé aussi "région des solutions admissibles".
69
70
a. Système d'axes
71
b. Représentation de la région réalisable
72
• Exemples : soit le problème suivant :
Le problème possède trois contraintes plus la contrainte de positivité. On

commence à tracer chaque contrainte séparément.
73
• On prend la première contrainte du système et on remplace l'inégalité par une
égalité sans l'ajout de variable d'écart, (cette façon de faire est applicable
seulement pour la résolution graphique). L'équation résultante correspond à
une droite. Pour tracer une droite, il faudrait déterminer deux points, ce qui
donne pour la première contrainte notre exemple :
4X1+5X2=55
 Si x1=0 alors x2=11 le premier point est (x1 , x 2) =(0 , 11)
Si x2=0 alors x1=55/4 = 13.75 le deuxième point est (x1 , x 2) =(13.75 , 0) 74
• À partir de ces points on trace la première droite et on conserve ce qui est en
dessus de la droite. On élimine ensuite la partie supérieure puisque la
contrainte est une contrainte d'infériorité.
75
• Ainssi, on applique le même principe pour toutes les contraintes du système :
X1+3X2=27
Si x1=0 alors x2=9 le premier point est (x1 , x 2) =(0 , 9)
Si x2=0 alors x1=27 le deuxième point est (x1 , x 2) =(27 , 0)
• 2X1+X2=20
Si x1=0 alors x2=20 le premier point est (x1 , x 2) =(0 , 20)
Si x2=0 alors x1=10 le deuxième point est (x1 , x 2) =(10 , 0)
76
• Bien évidemment, il faut tracer aussi les contraintes de positivité. L'intersection
de toutes les contraintes forme le polygone de solutions tel qu'il est donné par
la figure2.2.
77
• La question qui se pose maintenant est : quel est le point qui donne la valeur optimale
pour ce problème ?
• Pour répondre à cette question nous expliquerons la procédure à suivre pour déterminer
la valeur maximale pour ce problème qui consiste à tracer la droite qui correspond à la
fonction objective.
• Tout d'abord, on prend l'équation de la fonction objective et on lui attribue la valeur de

zéro puisque c'est la plus petite valeur pour la fonction objective. Ce qui donne pour cet
exemple :
78
Le coefficient directeur de cette fonction est (−1, 1.5). Il passe par l'origine (0, 0).
Une fois la droite tracée on effectue une translation parallèle à la direction de la
droite du bas vers le haut jusqu’à rencontrer le dernier point du polygone
satisfaisant les contraintes
79
80
• Le maximum de Z sur cet ensemble de contraintes est alors atteint. On obtient ainsi le point qui
correspond à la solution optimale. Par la projection de ce point sur les axes x1 et x2 on obtient : x1=7.5
et x2 = 5, ce qui donne une valeur maximale Z = 6000.
• La méthode graphique pour la résolution d'un problème linéaire à deux variables est très facile à
appliquer. Sa difficulté augmente par l'augmentation des variables dans le système.
• Elle devient difficile pour trois variables et, voire impossible, au delà de trois inconnus
dans le système étudié.
• Afin d'ôter cette difficulté, une méthode appelée méthode du simplexe a été proposée et développée
par Dantzig afin de résoudre des problèmes de programmation linéaire avec plusieurs variables.
81
Exemple
Problème de fabrication
82
83
84
Exemple
85
Exercice
86
 Différentes formes de programmes linéaires
87
Différentes formes de programmes linéaires
88
Exercice
89
Correction
90
Résultats fondamentaux de la P.L.
91
Résultats fondamentaux de la P.L.
92
5.2 La méthode du simplexe
• La méthodologie proposée pour cette technique consiste à visiter tous les états
possibles dans un système en partant d'un sommet vers un sommet adjacent de
manière à réviser et améliorer la fonction objective. Pour ce faire, nous procédons à
l'exploration des différentes démarches selon l'ordre de priorité donné ci dessous :
• Démarche 1 : On démarre l'application de l'approche (méthode du simplexe) par la
transformation des contraintes d'inégalité en contraintes d'égalité en ajoutant les
variables d’écart.
• Démarche 2 : Dans un second temps nous sélectionnons les variables originales
comme variables hors-base et les variables d'écarts comme variable basique. puis
nous effectuerons une permutation entre une variable hors-base de notre choix qui
sera remplacée par une variable de base (entrante). Le choix de la variable entrante
repose sur la variable dont le coefficient est le plus élevé dans la fonction objective.
93
• Démarche 3 : La variable sortante est la première à s’annuler. On répète le processus
jusqu’à ce que tous les coefficients de fonction objective soient négatifs ou nuls.
Dans ce cas, on arrête et la solution optimale est trouvée.
• Exemple : Considérons le problème suivant :
94
• Soit y3, y4 et y5, les variables d’écart relatif respectivement aux contraintes 2.10,
2.11 et 2.12, qui permettent de transformer les contraintes d'inégalité pour obtenir
les égalités suivantes :
• On commence à partir du point y1=0, y2=0 et on vérifie s'il est possible d'augmenter
la fonction objective sachant que notre système est un système de trois équations
avec cinq inconnues. Pour trouver la solution on impose deux des variables à zéro et
on déduit les valeurs des trois variables restantes. Ce qui donne :
95
y1 = 0,
y2 = 0 ;
• Pour les variables de base et :
y3 = 70
y4 = 40
y5 = 90
• Pour les variables hors base.
• Et la valeur de la fonction objective F = 40 y1 + 60 y2= 0,
96
• La question qui se pose est : Est-il possible d'augmenter F ?
• Pour répondre à cette question, on vérifie la fonction objective. Si les coefficients
sont positifs, ce qui est le cas, on a donc la possibilité d'augmenter F. On favorise
l'augmentation de la variable qui a le plus grand coefficient dans la fonction
objective. Donc on choisit y2 en maintenant y1 = 0.
On remplace y1=0 dans équation 2.13, 2.14, et 2.15
97
• On réécrit les variables restantes en fonction d'y2 pour chaque équation. Ce qui
nous donne :
• On peut augmenter la valeur de y2 au maximum à 30 puisque c'est la valeur

qui permet de satisfaire les équations 2.19, 2.20 et 2.21.
Nouvelle solution admissible :
y1 = 0 ;
y2 = 30 ;
y3 = 40 ;
y4 = 10 ; 98
• On remarque bien que y1=0 est toujours maintenu à zéro. Par ailleurs, y5 est passé
de 90 a 0 et y2 est passé de 0 a 30 .Donc on déduit que pour cette étape la variable
sortante de la base est y2 et la variable entrante à la base est y5.
• La nouvelle valeur de la fonction objective est :
F = 40 y1 + 60y2 = 1800
• Les coefficients de la fonction objective sont positifs.
• Ce qui permet améliorer d'avantage la solution obtenue. Dans ce cas on s'arrange
pour exprimer toutes les équations en fonction de y1 et y5. Pour ce faire on retire la
valeur de y2 de la troisième équation et on remplace son expression dans les deux
premières. Il en est de même pour F, ce qui nous donne dans cette étape les
équations 2.22, 2.23 et 2.24
99
Nouvelle expression de la fonction objective F = 1800 + 20y1 - 20y5

D'après l'expression de la fonction objective de l'étape précédente on choisit
d’augmenter y1 en gardant y5 =
100
• La valeur maximale admissible pour y1 = 15.

• Nouvelle solution admissible :
y1 = 15;
y2 = 25;
y3 = 15;
y4 = 0;
y5 = 0
• Pour cette étape, la variable sortante de la base est y2 et la variable
entrante à la base est y4. L'expression de la nouvelle valeur du critère est
F = 2100 - 30y4 - 10y5
101
Les coefficients de y4 et y5 dans la fonction objective de la dernière

étape sont négatifs, quelle que soient la valeur de y4 et y5 qui implique
une diminution de la valeur du critère F.
Il n’existe donc plus d'augmentation et d’amélioration possible et la

dernière solution obtenue représente la solution optimale qui est égale à
2100.
102
5.3 Résolution par Tableaux de simplexe
103

Cours

Transféré par

Informations du documentcliquez pour développer les informations du document

Droits d'auteur :

Formats disponibles

Cours

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Cours

Transféré par

Droits d'auteur :

Formats disponibles

Cours " Recherche Opérationnelle "

• À partir de la description donnée, plusieurs questions se révèlent :

 Quelle quantité de table et quelle quantité de chaise doit produire l'entreprise ?

 Quel est le but de l'entreprise ? 5

• 32 tables et 0 chaise avec un bénéfice de 16000

• 20 tables et 20 chaises avec un bénéfice de 16000

• 0 table et 50 chaises avec un bénéfice de 15000

• La Recherche Opérationnelle ( R.O.) est avant tout un outil d’aide à la décision.

• La Recherche Opérationnelle (RO) permet d'assurer la communication entre le milieu

• La recherche opérationnelle (RO) est utilisée dans les domaines ou la prise de

• L'utilisation de la recherche opérationnelle devient de plus en plus sollicitée dans la vie

 la préservation des emplois

elle propose les meilleures décisions stratégiques

fournit une meilleure gestion des ressources. Etc. 10

• L’optimisation repose toujours sur des modèles mathématiques qui sont

• Représente l’objectif ou le but attendu du problème. il peut être une fonction de

1.4.4 Application a un exemple

• Solution : reprenons les données de l'exemple sur un tableau :

b) Positivité des variables : x1, x2 ≥ 0.

• Solution : formulation mathématiquement du problème.

• Pour la formulation de cet exemple nous nous avons choisit un réseau

Contraintes de satisfaction de la demande :

• Min Z = c11 w11+ c12w12+ c13w13+ c14w14+ c15w15+ c16 w16+

• Le critère représente le coût total de transport.

• Tout nombre, positif ou négatif, peut toujours être écrit comme la

• Il suffit donc de remplacer la variable d'activité par la différence de

• t2 représente le temps d’exécution de la comparaison {"2"}

• t3 est le temps d’exécution de l’action {"3"}

• t4 est le temps d’exécution de l’action {"4"}

• De ce fait, le temps d’exécution t(n) de cet algorithme s’écrit :

• Ce qui signifie que le temps d’exécution dépend linéairement de la taille n.

1.8.2 Évaluation temporelle

• Somme des temps de passages successifs exp:

• Note : d'une manière générale, les performances asymptotiques des

• La généralisation de micro-informatique a mis la programmation linéaire à la portée de

• L'objectif de programmation linéaire est de déterminer l’affectation optimale de

• La programmation linéaire est une branche des mathématiques appliquées et plus

• Le principe de la programmation linéaire est fondé sur le fait que :

• La fonction à optimiser appelée fonction objectif ou fonction économique a une

• Les expressions des contraintes sont tous linéaires. 41

• Remarque : En économie et gestion, l'objectif est à :

La fonction 2.1 peut s'exprimer par une sommation de n terme (variables)

Sous les contraintes :

Z= CX est la fonction objective, ou critère à

 Le vecteur des coefficients b est donné par b=(55 , 27 , 20)

• I) Identifier les variables principales ou les variables de décision du

• Le tableau suivant résume les données afférentes à ce problème de

• Quelles sont les informations dont doit disposer le directeur de l’entreprise

Les variables x1 et x2 sont dites variables de décision.

• ce que généralement l’on convient d’abréger comme suit :

• Contrainte relative à la machine m Le temps d’utilisation de la

• Contraintes de positivité: Elles assurent que la solution ne comporte pas

• Le modèle se résume ainsi :

• La variable d’écart d’une contrainte représente la quantité disponible non

Le problème possède trois contraintes plus la contrainte de positivité. On

 Si x1=0 alors x2=11 le premier point est (x1 , x 2) =(0 , 11)

• Tout d'abord, on prend l'équation de la fonction objective et on lui attribue la valeur de

dans le système étudié.