PolyRo IAP

Recherche Opérationnelle
Abdelkader BELAHCENE
23 avril 2012
Table des matières
1 Contexte de la Recherche Opérationnelle 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Méthodologie de Résolution . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Analyse du Système . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Modélisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5 Recherche de Solutions et Mise en Oeuvre . . . . . . . . . . . . . . . . . . 9
1.6 Étude de Cas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.7 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Programmation Linéaire 14
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Méthodes de Résolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 La Méthode du Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.4 Recherche d'une Solution de Base Réalisable . . . . . . . . . . . . . . . . 27
2.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3 Concepts Avancés de la PL 33
3.1 Modèles Particuliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 La Dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3 Analyse Post Optimale et Sensitive . . . . . . . . . . . . . . . . . . . . . 44
3.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4 Problème du Transport 53
4.1 Position du problème et modélisation . . . . . . . . . . . . . . . . . . . . 53
4.2 Recherche d'une solution de base réalisable . . . . . . . . . . . . . . . . . 55
4.3 Amélioration de la solution . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.4 Série d'exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
2
1 Contexte de la Recherche
Opérationnelle
1.1 Introduction
Depuis l'avènement de la révolution industrielle, le monde a connu une remarquable

croissance de ses organisations. Cette croissance a générer un souci de performance,
d'ecacité et de rentabilité des ces organisations. La Recherche Opérationnelle (R.O) est
une des disciplines qui a contribué signicativement au développement des organisations
quelque soit leur nature.
L'une des raisons majeures de la réussite de R.O est l'immense progrès de l informatique
qui a vu la mise en application des théories mathématiques restées longtemps de l'encre
sur du papier. Les diérentes branches de la R.O (Programmation Mathématique, Gestion
des Stocks, File d'attente ...) qui nécessite des calculs intenses, ont vu l'application dans
l'industrie grâce à l'apport du computer et de l'informatique en général.
La Recherche Opérationnelle ne se restreint pas uniquement aux problèmes dont les

objectifs du système sont connus et ses contraintes parfaitement cernées mais aussi aux
problèmes complexes , souvent mal posés .
La Recherche Opérationnelle (R.O) contribue à la résolution d'un problème, en analysant

le système dans lequel il est posé, en extrayant une image aussi dèle que possible de
la réalité que l'on appelle modèle (voir Figure 1.1), pour ensuite trouver une solution à
l'aide des techniques mathématiques . Souvent , la mise en oeuvre d'une solution sert de
retour en arrière aux étapes antérieures.
SYSTEME EXTRACTION
MODELE
REEL PERCU
Figure 1.1: Principe de la Modélisation
3
1.1.2. Méthodologie de Résolution A.Belahcene
1.2 Méthodologie de Résolution
En général, lorsque les organisations sollicites l'aide des spécialistes en Recherche Opéra-
tionnelle c'est que, d'une part, celles-ci ont pris conscience du mauvais fonctionnement
de leur organisation et que, d'autre part , elles souhaitent trouver des solutions à leur
problèmes . il est utile pour ces spécialistes d'avoir une démarche à suivre qui inclut aussi
bien l'aspect d'analyse contextuelle du problème que sa résolution.
La méthodologie que nous proposons et une procédure systématique de résolution de

problème de Recherche Opérationnelle les diérentes étapes se résument comme suit :
analyse de système , formulation modélisation, recherche d'une solution , mise en oeuvre
de cette solution et enn le retourne sur les étapes précédentes lorsque cette dernière n'est
pas satisfaisante . La gure résume le cheminement de ces étapes , que nous expliquerons
par la suite .
1.3 Analyse du Système
C'est l'étape la plus dicile d'un problème de Recherche Opérationnelle, le but de cette
analyse est de comprendre l'environnement dans lequel le problème est posé pour mieux
cerner les aspects les plus importants. Souvent le problème posé est vague et les informa-
tions ne sont pas disponibles et quand elles le sont , elles ne sont pas ables. il faut donc
consacrer beaucoup de temps et d'eorts à cette phase en procédant à des interviews
et des séances de concertation pour s'assurer que le problème pose est réellement celui
auquel il faut s'atteler pour le résoudre. il est important d'associer tout les décideurs
ainsi que les acteurs principaux du système à ce stade d'analyse.
Souvent, certains problèmes sont corrigibles de par leur nature, c'est-a-dire, qu' il est
possible, moyennant des corrections, d'améliorer le comportement du système.
Dans ce cas, il faut distinguer entre les symptômes et les causes du problème. Par exemple,
la baisse des ventes, qui est un symptôme, peut être due au fait que le voyageur de
commerce ne dispose pas susamment de temps pour visiter tous les points de vente.
ceci constitue la cause du problème parfois, certains problèmes trouvent leurs solutions
en recherchant leurs causes et en montrant comment les symptômes se présentent.
Une mauvaise analyse du système inue considérablement sur sa structuration.
1.3.1 Types de contraintes

Une contrainte peut être liée à n'importe quel aspect d'un problème, Elle peut être de
plusieurs nature. Voici quelques contraintes facilement reconnaissables.
Contrainte technologique Les diérentes opérations nécessaires au processus de fabri-

cation d'un produit.
23 avril 2012 Page 4 de 60

1.1.4. Modélisation A.Belahcene
Contrainte de marché Le potentiel des ventes d'un produit. Le taux d'additif présent
dans la composition d'un carburant.
Contrainte organisationnelle : La structure hiérarchique d'une organisation.

Contrainte liée aux ressources : Le budget disponible ou le nombre d'heures de main-
d'oeuvre disponible.
Dans plusieurs situations les contraintes n'apparaissent pas lors de l'étude et cela en
raison de la mauvaise connaissance du problème ou de la diculté d'obtention de la
précision de durée de vie d'un produit, lorsque l'on considère un problème de gestion des
stocks, ne peut-être connue d'une manière précise.
1.3.2 Types d'objectifs

Un objectif est eu but que l'on se xe à atteindre. il ne faut pas le confondre avec une
action , qui est un moyen pour atteindre cet objectif.
On peut aussi avoir plusieurs objectifs en parallèle, ce qui un problème Multi-critère.
Il existe des situations ou le système en question possède un objectif, facilement identi-

able et quantiable Par exemple :
Maximiser un prot sur un ou plusieurs produits
Minimiser le coût total de stockage lorsqu'il s'agit d'un problème de gestion des stocks
Minimiser la distance globale parcourue par le voyageur de commerce
Par contre, il existe d'autres situations ou le système possède plusieurs objectifs dont
certains ne sont pas facilement quantiables et parfois même conictuels Par exemple,
maximiser la satisfaction de la clientèle tout en voulant aussi maximiser le prot global
dans le cas d'une entreprise de production d'un bien de consommation.
Parfois, L'objectif ainsi que les contrainte du système sont exprimes par des fonctions
linéaire (cf. programmation linéaire). Dans certains cas, la fonction objective ainsi que las
contraintes sont exprimées par des fonctions non-linéaires. Les techniques de résolution
diérent selon le type d'objectif et de contraintes du système en étude.
1.4 Modélisation
Il s'agit dans ce cas d'extraire une image aussi dèle que possible de la réalité voir gure
1.1 .
Cette image peut prendre plusieurs formes. Elle peut être mathématique, comme en
programmation linéaire, ou sous forme , d'un graphe, comme en théorie des graphes ou
encore sous une forme visuelle comme en simulation.
La construction d'un modèle passe par plusieurs à savoir :
Recueil et Analyse des données, construction de modèle et sa validation gure 1.2. La

partie validation revêt une importance capitale car le modèle recherché doit être proche
de la réalité.

Reel Percu
Detection Modelisation
d’Anomalies
Resolution
Validation
Non Accepte
Accepte
Figure 1.2: Schématisation de la Modélisation
1.4.1 Données
Cette étape est consacrée à la collecte de toutes sortes d'informations liées au problème,
Il est impératif d'avoir une connaissance détaillée du problème et de son environnement.
Il est important de considérer les données internes et externes au système. Ensuite, on
envisage la possibilité de réduire le volume des informations recueillies en ne gardant que
celles qui sont importantes le choix des données se fait selon les critères suivants :
Importance Il s'agit de savoir si l'information disponible est la plus signicative.

Fiabilité Il s'agit de voir la source de l'information recueillie et son degré de abilité.
Actualité Il s'agit de remonter à la période d'obtention de l'information et de voir si celle-
ci reste toujours d'actualité. Dans le cas contraire, quand sera-t-elle disponible ?
Lorsque le minimum d'information est obtenu, il est recommandé de répartir les données
en deux classes. La première classe permet d'établir le modèle, la seconde sert à tester
sa qualité.
1.4.2 Construction d'un modèle

Un modèle est une représentation d'une situation réel. Il existe plusieurs types de mod-
èles : les modèle iconiques, les modèle analogues et les modèles mathématiques.
Le premier modèle est une miniaturisation du système. La carte géographique d'un pays
est un exemple de modèle iconique. Le modèle analogue représente un système physique.
Il ne prend pas la même forme que le système qu'il représente. Le thermomètre est un
exemple de ce type de modèle, il permet de mesurer la température. Un modèle mathé-
matique décrit un système donné par le biais de relations et de symboles mathématiques.
Description Le modèle doit bien décrire les facteurs principaux du système.

Explication On doit s'assurer que les relations qui existent dans le modèle donnent une
explication satisfaisante du comportement et de l'évolution du système.
Contrôlabilité Un modèle de décision doit monter aux décideurs les actions à entrepren-
dre pour arriver aux résultats désirés. Ce modèle doit inclure aussi bien les facteurs
contrôlables que ceux qui ne le sont pas.
Les facteurs contrôlables sont ceux qui sont contrôlés directement par les décideurs, Par
contre, les facteurs non-contrôlables représentent tout les facteurs imposés par l'environ-
nement. En statistiques, on distingue généralement trois types de modèles : les modèles
descriptifs, les modèle explicatifs et les modèle extrapolatifs.
Les méthodes factorielles d'analyse des données sont des exemples de modèles descriptifs,
Les modèles de régression constituent un exemple de modèles explicatifs. Les modèles de
décomposition, les lissages exponentiels et les modèles de Box-Jenkins sont des modèles
extrapolatifs.
Un modèle pour la prise de décision s'écrit sous la forme suivante :
y=R ({X},{C}), où {X} est l'ensemble des facteurs contrôlables que l'on appelle vari-
ables de décision et {C} est l'ensemble des facteurs non contrôlables et des contraintes.
R(., .) représente la forme générale d'une relation fonctionnelle.
Exemple 1.4.1. Une entreprise recrute deux employées pour le nettoyage hebdomadaire
du lieu de travail composé de 12 bureaux, 18 étagères et 5 toilettes. La première employée
ne peut nettoyer qu'une toilette, 3 bureaux et 3 étagères par jour, la seconde peut faire 2
bureaux, 6 étagères et 1 toilette par jour. Le salaire journalier des employées sont respec-
tivement 250 et 220 DA. Quelle est la charge hebdomadaire des employées qui minimise
les coûts de nettoyage ?
Le problème étant bien posé, Ce que nous voulons obtenir est clairement indiqué, nous
passons directement à la phase formulation qui consiste à identier les objectifs et les
contraintes du problème.
L'objectif de l'entreprise est de minimiser le coût total à dépenser pour payer hebdo-
madairement les deux employées. Les contraintes représentent les limites sur le nombre
d'objets (étagères, toilettes et bureaux) à nettoyer par semaine. Nous avons donc 3 con-
traintes dans ce problème.
La phase suivante est la modélisation Identiant les facteurs contrôlables et non-contrôlables
Le premier type de facteur représente les variables de décision, x1 et x2 . Elles signient

respectivement le nombre de jour de travail par semaine chacune des employées. c'est ce
qui est demandé de trouver dans l'énoncé du problème.
Les facteurs non-contrôlables sont les prix d'une journée de travail pour chacune, les
limites sur les objets à nettoyer ( contraintes). Il ne faudrait pas oublier la non-négativité
des variables sinon cela n'aurait aucun sens.
Il ne reste plus qu'à traduire tout cela sous forme d'équations. Le coût total est égal au
coût d'une journée par le nombre de journées Évidemment, il faut sommer sur les deux
employées. donc, l'expression mathématique de la fonction objective est :

Min Z = 250x1 + 220x2
On notera que Min est l'abréviation du terme minimiser, de même Max pour maximiser.
Pour formuler les contraintes, nous allons procéder de la même manière, nous avons 12
bureaux à nettoyer par semaine, Par ailleurs, nous savons que la première ne peut nettoyer
que 3 bureaux par jour. Par conséquent, si elle travaille x1 journées elle pourrait nettoyer
3x1 bureaux par semaine. De même la deuxième ne peut nettoyer que 3x2 La contrainte
sur le nombre de bureaux à nettoyer par semaine se traduit comme : 3x1 + 2x2 ≥ 12 .
On raisonne de la même façon pour les deux autres contraintes. On obtient alors :
pour les toilettes : x1 + x2 ≥ 5
pour les étagères : 3x1 + 6x2 ≥ 18
Ci-aptès le modèle pour l'entreprise. min Z = 250x1 + 220x2

Quant aux contraintes de non-négativité et
3x1 + 2x2 ≥ 12
d'intégrité des variables, elles se traduisent
x1 + x2 ≥5
comme x1 ∈ N et x2 ∈ N où N est l'ensem-
ble des entiers naturels. 3x1 + 6x2 ≥ 18
x1 , x2 ∈ N+
On remarquera que la fonction objective et le système des contraintes sont linéaires par
rapport aux variables de décision, ce problème est dit de programmation linéaire mais
en nombres entiers, on doit théoriquement ajouter la contrainte du nombre de jours
inférieur à 5.
1.4.3 Validation d'un modèle

Pour qu'un modèle soit utilisable, on doit trouver un moyen de le valider sinon il ne
serait d'aucune utilité pratique. Souvent l'information nécessaire au processus de mod-
élisation est approximative et insusante, et donc l'extrapolation des données s'impose.
Un modèle peut être valide pour une extrapolation à court terme mais ne pas l'être pour
une extrapolation à long terme en raison de changement possible dans la structure des
données.
Un modèle est valide par comparaison a la réalité. L'approche est de le comparer, en

utilisant des méthodes statistiques appropriées, les sorties du modèle avec les données
réelles, c'est-à-dire, celles obtenues directement à partir du système en étude sur une
même période.
Dans le schéma précédant (gure 1.2) , lorsque le modele est refusé, la réctication du
processus doit ce faire a plusieurs niveaux. Il s'agit de savoir où ce trouve l'erreur qui
a donné la ou les anomalies. Cette anomalie peut etre une mauvaise perception de la
realité, ou une mauvaise formulation, de l'imprecision des données ou encore la methode
de résolution est inadéquate.

1.1.5. Recherche de Solutions et Mise en Oeuvre A.Belahcene
Exemple de validation
Supposons que l'on dispose d'un historique de 12 années de la consommation en gaz
butane (en bouteille) dans la region de Djelfa bouteille (une donnée représente une con-
sommation mensuelle). On peut diviser cet historique en
10 années de consommation, soit 120 mois de consommation pour les données de mod-
élisation,
le reste, c'est-à-dire, 2 années de consommation, soit 24 mois vont servir pour tester le
modele.
On détermine à partir du modèle les prévisions pour les deux années couvrant la même
période que celle des données test ; ensuite on comparera selon une critère xé, les
données test ou les données simulés avec les prévisions.
On notera qu'il n'existe pas de moyens précis de diviser les données. En général, la
proportion des données qui serve à l'estimation du modelé doit être plus importante.
Parfois, il ne sut pas d exiger du modèle de calquer la réalité, mais plutôt de s'assurer
que les relations qui composent ce modèle aient un sens. Ce type de validation est vu
comme étant un processus continu et qui se fait en parallèle avec la phase de modélisation.
Le but est d'examiner toutes les composantes du modèle au fur et à mesure qu'elles se
développent.
Cette validation se fait en essayant d'apporter des éléments de réponse aux questions
relative à la logique du modèle, ses relations.. etc.
Parmi les questions que l'on doit considérer :
1. Est-ce que la logique du modèle est la même que celle du système réel ?
2. Est-ce qu'une relation quelconque du modèle correspond a une certaine théorie ?
3. Est ce que les données disponibles ne suivent pas une certaine distributions statis-
tique ?
4. Est ce que les données utilisées sont d'actualitées. Dans notre exemple, si les statis-
tiques de consommation sont antéerieur, par exemple a l'arrivée du gaz de ville sur
la ville de djelfa, elles ne sont plus valables ! ! !.
D'autres questions pourraient être examinées avec collaboration des décideurs.
1.5 Recherche de Solutions et Mise en Oeuvre
La recherche de solution d'un problème donné se fait de plusieurs manières :
Techniques d'optimisation Pour une certaine classe de problème, il existe des algo-
rithmes garantissant la solution optimale, si elle existe, (c'est le cas pour la pro-
grammation linéaire), plusieurs chapitres sont consacrées à ces problèmes.

1.1.6. Étude de Cas A.Belahcene
Méthodes heuristiques Pour certains problèmes la solution ne peut être trouvée di-
rectement, ou que le temps de calcul est trop important ou les coûts sont élevés, on
développe alors des heuristiques, des algorithmes approchés. C'est le cas des as-
tuce ou heuristique qu'on ajoute au branch and bound, pour le temps d'exécution
raisonnable.
Simulation Le modèle imite le comportement réel d'un système. On fait varier diérents
paramètres et observer les conséquence jusqu'à obtenir satisfaction ou rejeter le
modèle. Ce type de techniques est utilisée quand la modèle est trop complexe,
et que les méthodes exactes ne sont pas applicables, et les heuristiques ne sont
satisfaisantes.
La dernière phase du cheminement d'un problème de recherche Opérationnelle consiste

à mettre en oeuvre et à contrôler la solution obtenue à partir du modèle établi et validé.
Souvent l'implémentassions sert de FeedBack, ou de retour en arrière , aux étapes

précédentes, et par là ajouter ou enlever une contrainte, sous estimer ou surestimer un
paramètre. Ou prendre en compte de nouveau éléments qui n'étaient pas visibles au
départ.
1.6 Étude de Cas
1.6.1 Position du problème

Un propriétaire de diérents types de magasins veut acquérir 3 locaux commerciaux a
Alger. L'un d'eux se situe au quartier résidentiel les roses, le second à la cité Le citadin
et le troisième dans la banlieue les vergers. L'administration a imposé les activités de 2
types : Alimentation générale et gastronomie.
Le propriétaire voudrait connaître les avantages et risques de cette acquisition. Il a à sa

disposition des statistiques sur certains quartiers d'Alger résumé dans le tableau 1.1
Les ventes 1 et 2 représentent les ventes annuelles réalisées par les activités (Alimentation
2
et Gastronomie) . Le revenu moyen annuel du citoyen. La deuxième colonne donne le
nombre d'habitants.
On suppose que les coûts d'entretien et de fonctionnement sont évalués respectivement

à 1500 et 1300. Le tableau 1.2 page suivante donne les statistiques sur les quartiers en
question (les Roses, les vergers et le citadin).
Par ailleurs il estime qu'il n'est pas intéressant d'investir sur un local qui ne rapporterait
un prot annuel de moins de 1500.
2. Tous les coûts rapportés dans ce cas sont en milliers de DA

Site Population Revenu Vente 1 Vente 2
Didouche Mourad 7 000

1 200 2 500 2 000
Krim Belkacem 9 000 120 2 000 3 000
Med Boudiaf 12 000 80 3 000 4 000
Ben M'hidi 5 000 350 1 500 2 500
Fadma Nsoumer 6 000 160 2 300 1 900
Ali la Pointe 10 000 100 2 400 1 950
H. BenBouali 5 000 400 2 800 3 000
Amirouche 8 000 100 2 500 2 000
Abane Ramdane 15 000 150 4 000 2 700
Zighout Youcef 7 500 250 1 800 2 300
Table 1.1: Statistique d'Investissement
Site Population Revenu
Les Roses 2 000 300

Les Vergers 10 000 150
Le Citadin 20 000 60
Table 1.2: Lieux d'investissement
1.6.2 Proposition de Solution

Il s'agit d'aider le décideur à faire le choix du lieu et de l'activité qui convient. L'objectif
est de réaliser un prot, le plus grand possible. L'investissement ne se fera que si le prot
attendu est supérieur à 1500. Ceci représente une contrainte du problème. Les facteurs
contrôlables (variables de décision) sont le lieu et le type d'investissement. Les facteurs
non contrôlables sont les ventes le revenu moyen et le nombre de citoyens.
Il s'agit de déterminer les actions les plus appropriées. La décision dépend du prot
attendu dans chaque site. Il faut donc trouver un moyen d'estimer le prot. Pour cela
nous utilisons les statistiques des ventes des autres sites (table 1.1) et construire un
modèle statistique.
Ce modèle permettra d'exprimer les ventes en fonction de la taille de la population et

de son revenu moyen. Nous faisons ici évidemment des hypothèses, entre autres, le com-
portement de la population des quartiers d'Alger est semblable, pour ces deux activités,
il se diérencie uniquement par l'importance de sa taille et son revenue.
Les coûts d'entretien et de fonctionnement sont à déduire du prot. En outre la contrainte

doit être prise en compte.
Nous supposons que les ventes se comportent linéairement par rapport à la population
et au revenu moyen. Dans la pratique ce travail de modélisation est plus complexe et
nécessite plus d attention, on se contentera ici, de la forme linéaire.
Notation adoptée :
V 1t ,V 2t ventes de type alimentaire et gastronomie du site t
Pt Taille de la population du site t
Rt Revenu moyen du citoyen du site t
Un modèle mathématique simple qu'on peut utiliser (pour le type 1) est :
V 1t = α + β Pt + γ Rt + et
où α, β, et γ sont des paramètres réels, et est un aléas. P et R sont les moyennes des
populations et des revenues.
La méthode des moindres carrés

3 appliquée aux erreurs et , c'est à dire
10
X
M in Z = (et )2
i=1
α = 319 , β = 0.209 et γ = 2.08. La variable dépendante
Donne pour solution les valeurs :
Z est une fonction quadratique des variables indépendantes α, β et γ . La meme procédure
de calcul est utilisée pour le deuxième cas, on obtient .
4
Site V1 V2
Les Roses 1 361 1954

V 1t = 319 + 0.21Pt + 2.08Rt
Les Vergers 2 721 2 635
V 2t = 977 + 0.13Pt + 2.39Rt
Le Citadin 4 623 3 720
Compte tenu de la contrainte (vente supérieur à 1 500) on peut choisir d'investir en

alimentaire au Citadin (Colonne V1) et en gastronomie aux vergers et au roses
(colonne V2) .
Ce modèle n'est plus valable (dépendant de 2 variables : P et R ), si d'autres facteurs

peuvent inuer. Par exemple le manque de moyen de transport, qui peut, dans un quartier
donné, obliger les habitants à s'alimenter sur place, même si c'est plus cher, alors que
dans un autre quartier, les gens préfèrent se déplacer, pour de meilleurs prix, si le trans-
port est disponible. En d autre termes, pour deux quartiers de même population et
même revenu moyen par habitant, les ventes peuvent diérentes si les facilités de trans-
port sont diérentes. Dans ce cas alors il faut ajouter une 3ieme variable indépendante
avec les données sur les transports.
3. Voir pour le détails de la méthode n'importe quel livre d' analyse numérique
4. Voir le programme LeastDiscrete et les données vente1.dat et vente2.dat

1.1.7. Exercices A.Belahcene
1.7 Exercices
1. La composition d'un aliment pour bétail est obtenue par le mélange de 3 matières :
L'orge, l'arachide et le sésame.

Cet aliment doit comporter au Matière Orge Ara. Sés.
moins 22% de protéines et 3.6% de Protéine(%) 12 52 42
matières grasses. Le tableau résume Graisses(%) 2 2 10
la composition et les coûts. Faire la Coût(Da/kg) 25 41 39
formulation du problème.
2. Une compagnie pétrolière désire installer une ranerie qui sera alimentée par 3
ports A, B et C. Le port B est à 300km Est, 400km Nord du port A. Le port C
est à 400km Est, 100km Nord du port B. Localiser la ranerie de sorte que la
longueur des pipelines reliant la ranerie aux ports soit minimale. Y a t il d'autres
contraintes implicites non apparentes.
3. Une compagnie vend 2 types de lubriants pour machines à turbines. Le premier

lubriant est de meilleur qualité. Pour ses besoins de fabrication, elle utilise 4
matières chimiques A,B,C, et D, qui contiennent une quantité en additif A1 et A2.
Chaque lubriant doit satisfaire les normes sur le maximum en A1 (supérieure à la
limite) et un minimum en A2 (inférieure à la limite) .
a) La quantité de l'additif contenue dans un produit ni est la moyenne volumétrique

des quantités de ses composés. La première table résume la demande journal-
ière, en nombre de barils, et le prix de vente du baril. La deuxième donne les
disponibilités et les coûts des matières premières.
b) Structurer le problème du point de vue du responsable des ventes. Faire la

modélisation.
Lubrif. A1 A2 Ore Coût

Lubrif. A1 A2 Demande Prix A 8 101 800 970
Prod 1 10 100 1400 900 B 9.5 90 700 685
Prod 2 10 110 900 1 000 C 7 83 1000 630
D 21 103 600 680
4. Vérier que la solution par arrondi n'est la solution optimal pour le programme
suivant :
5
3x1 +4x2 max Utiliser par exemple lp-solve pour le
2x1 +x2 ≤6 resoudre avec puis sans la contrainte
2x1 +3x ≥9 d'integrite et comparer avec les
x1 , x2 ∈ N + solutions de l'arrondi.
5. voir solution du chier Ch1_ex4.lp

2 Programmation Linéaire
2.1 Introduction
L'objectif principal de ce chapitre est d'initier le lecteur à la reconnaissance, la for-

mulation et la résolution d'une classe de problèmes en recherche opérationnelle dit de
programmation linéaire. Ce chapitre sera illustré par un exemple pédagogique que l'on
désignera par P.L 1 (cf. Exemple 2.1.1). Il est fortement recommandé au lecteur d'utiliser
la méthodologie exposée au chapitre 1 pour formuler et modéliser ce problème.
Exemple 2.1.1. Une usine fabrique deux produits

P1 et P2 sur 3 machines M1 , M2 et M3 . Le produit M1 M2 M3
P1 est fabriqué par les machines M1 et M2 alors que le
produit P2 est fabriqué sur les 3 machines. Le tableau
P1 0.25 0.4 0
suivant donne le temps de séjour des produits sur les P2 0.5 0.2 0.8
machines.
Le temps de séjour est donné en heure/unité de produit. La disponibilité hebdomadaire

de chaque machine est de 40 h. Le produit P1 engendre un prot unitaire de 2 D.A et le
produit P2 un prot unitaire de 3 D.A. Le problème consiste à déterminer le planning de
production qui maximise le prot total.
Ce problème contient un objectif, à savoir la maximisation du prot total. Les contraintes

représentent la disponibilité hebdomadaire de chaque machine. Les variables de décisions
(ou facteurs contrôlables) représentent le volume de production de chaque produit que
l'on désigne respectivement par x1 et x2 . Les facteurs non-contrôlables sont les prots
unitaires sur chaque produit et la disponibilité hebdomadaire de chaque machine. La
formulation de ce problème se trouve à la section 2.1.2. La fonction objective ainsi que
les contraintes sont des fonctions linéaires par rapport aux variables de décision, d'où le
nom de programmation linéaire.
2.1.1 Dénition :
Un programme linéaire est un problème qui consiste à optimiser (maximiser ou minimiser)
une fonction linéaire à plusieurs variables soumise à un ensemble de contraintes linéaires.
D'une manière générale, un programme linéaire s'écrit sous la forme suivante :
14
2.2.1. Introduction A.Belahcene
max F = c1 x1 +...+ cn xn
a11 x1 ...........+ a1n xn R1 b1
a21 x1 ...........+ a1n xn R2 b2 (2.1)
....
am1 x1 ...........+ amn xn Rm bm
Les relations R1 , R2 , ..., Rm sont soient des égalités ou des inégalités. Les coecients
c1 et cn dans la fonction objective sont des nombres réels. De même que tous les coe-
cients dans le système des contraintes sont des réels. Ce programme général peut aussi
être exprimé sous la forme matricielle suivante :
max F = C x
Ax Rb
où A est la matrice m×n des coecients des variables dans le système des contraintes,
i.e.,
a11 ... a1n

A= . . .
am1 ... amn
C est le vecteur des coecients dans la fonction objective C = (c , ..., cn ) , X est le

vecteur représentant les variables de décision ( x1 , x2 , ..., xn ) et b le vecteur second
membre du système des
t
contraintes ( b1 , b2 , ..., bm ) = b .
Dans le cas du programme de l'exemple2.1.1, le nombre de variables n est 2 et le nombre

de contraintes m est egal a 5 . Les éléments de la matrice A sont résumés comme suit :
a11 = 0.25 a21 = 0.4 a31 = 0 a41 = 1 a51 = 0

a12 = 0.5 a22 = 0.2 a32 = 0.8 a42 = 0 a52 = 1
Les vecteurs b et C sont : C = (2, 3) et bt = (40, 40, 40, 0, 0) . Les trois premières relations
R1 , R2 , et R3 sont sous forme ≤ . Par contre, les relations R4 et R5 sont sous la forme
≥ . Ces deux dernières contraintes assurent la non-négativité des variables.
Remarque 2.1.2 . Comme tout programme linéaire peut se ramener à la forme standard
d'un système d'équations voir système, nous allons uniquement nous intéressé à la réso-
lution de ce type de programme.

2.1.2 Formulation d'un Programme Linéaire

La formulation d'un problème en programme linéaire peut se faire en 4 étapes :
Identication des variables elles sont souvent connues comme étant des activités et
représentent les facteurs (objets) que nous contrôlons. Par exemple, les activités
de l'usine précédente étant la production des produits P1 et P2 , d'où le choix des
variables x1 et x2 . Il est important de bien dénir les unités de chaque variable.
Les variables sont indépendantes, si une variables dépend d'autres elle est éliminée
pour la taille du programme.
Identication des objets sous contraintes. Dans l'exemple 2.1.1, le temps de séjour de
chaque produit dans chacune des trois machines.
Traduction Objectif sous forme mathématique de la fonction objective en termes de

variables. Dans l'exemple 2.1.1 : max F (x1 , x2 ) = 2 x1 + 3 x2
Traduction Contraintes mise en forme des contraintes du problème qui ne sont rien
d'autre que les limites sur les objets. Dans l'exemple 2.1.1
Exemple 2.1.3. Le Probleme se formule comme suit
0.25 x1 +0.5 x2 ≤ 40
0.4 x1 +0.2 x2 ≤ 40
0.8 x2 ≤ 40
Il ne faut pas oublier les contraintes de non-négativités des variables : x1 ≥ 0 et x2 ≥ 0

En résumé le problème de l'exemple 2.1.1 se modélise comme :
max F = 2x1 + 3x2

0.25x1 +0.5x2 ≤ 40
0.4x1 +0.2x2 ≤ 40 (2.2)
0.8x2 ≤ 40
x1 ≥ 0 et x2 ≥ 0
2.1.3 La Forme Standard

Les méthodes de résolution d'un programme linéaire utilise souvent la forme standard.
Nous allons donner sa dénition ainsi que les transformations utiles pour ramener un
programme linéaire donne sous forme générale à une forme standard.
On appelle forme standard d'un programme linéaire, la forme suivante :

n
X
max F = cj xj
j=1
n
X
aij xj = bi i = 1, m
j=1
xj ≥ 0
Cette forme impose aussi que les seconds membres des contraintes soient des nombres
réels positifs ou nuls, c'est-à-dire, b1 ≥ 0 , i = 1, 2, ..., m . La traduction matricielle de
la forme standard d'un programme linéaire est :
max F = CX
AX = b X≥0
Lorsque le programme n'est pas donné sous la forme standard, il est utile d'utiliser les
transformations suivantes :
1. La fonction objective consiste à minimiser une fonction linéaire F . Ceci est équiv-
alent à maximiser G = −F et on a la relation suivante : min F = − max (G)
2. Lorsque une contrainte (par exemple la i ème ) n'est pas une égalité, deux cas
peuvent se produire :
a) ai1 x1 + .... + ain xn ≤ bi , on introduit une variable d'écart ei ≥ 0 pour avoir

ai1 x1 + .... + ain xn + e i = bi
b) ai1 x1 + .... + ain xn ≥ bi , on introduit une variable d'écart ei ≥ 0 pour avoir
ai1 x1 + .... + ain xn − e i = bi
3. Il arrive parfois qu'un ou plusieurs seconds membres des contraintes soit négatif.
Pour mieux xer les idées, supposons que la contrainte i possède un bi négatif, en
d'autres termes : ai1 x1 + .... + ain xn = bi avec bi < 0, Il sut, dans ce cas, de
multiplier les deux termes de cette contrainte par (−1) et on obtient :
−ai1 x1 − .... − ain xn = −bi avec − bi ≥ 0,

4. Supposons que la
eme variable soit quelconque. Il faut, dans ce cas, faire des
j
1 2 1 2
changements de variables et poser xj = xj − xj avec xj ≥ 0, xj ≥ 0 .
Écrivons la forme standard du programme linéaire associé à l'exemple précèdent. On

introduit une variable d'écart pour chacune des trois contraintes on obtient :
max F = 2x1 + 3x2

0.25x1 +0.5x2 +e1 = 40
0.4x1 +0.2x2 +e2 = 40
0.8x2 +e3 = 40
x1 x2 e1 e2 e3 ≥ 0

2.2.2. Méthodes de Résolution A.Belahcene
2.1.4 Espaces des Solutions

Une solution d'un programme linéaire est un vecteur (x1 , ..., xn ) de R satisfaisant aux
contraintes du système. Par exemple, (−1, −1) est solution du programme de l'exemple
2.1.1.
Un vecteur de valeurs (x1 , ..., xn ) est dit solution réalisable s'il vérie les contraintes du
système . La solution (−1, −1) n'est pas réalisable car elle ne vérie pas une containte.
Par contre (0, 0) est solution réalisable.
Une solution est dite de base si elle possède m variables de base et n−m variables
hors-base. Les variables hors-base doivent être nécessairement nulles. Une solution de
base réalisable vérie en plus toutes les contraintes. Par exemple (0, 0, 40, 40, 40) est
une solution de base réalisable pour le P.L 1 . Cette dernière est obtenue en annulant les
variables de décision x1 et x2 . Elles sont donc des variables hors-base et les variables
d'écart sont de base. Évidemment cette solution de base réalisable n'est pas unique et on
peut trouver d'autres.
On montre que la solution optimale est nécessairement de base. Un ensemble est convexe
si, tout segment ayant ses extrémités dans l'ensemble, est dans cet ensemble.
L'ensemble de toutes les solutions réalisables forme un polyèdre convexe. Il peut être
vide, borné ou non-borné. Si ce polyèdre convexe est vide cela signie que le système des
contraintes est incompatible, dans ce cas une analyse détaillée doit être envisagée. Lorsque
le polyèdre est borné alors le problème possède au moins une solution optimale. Enn
lorsque ce convexe n'est pas borné alors, soit nous avons omis une ou plusieurs contraintes,
ou que le problème ne possède pas de solution optimale nie. Nous reviendrons en détail
à ces problèmes particuliers dans le prochain chapitre.
Il est important de savoir (la théorie l'a montré) que les sommets du convexe correspon-
dent à des solutions de base réalisable et que si la solution optimale existe elle doit être
forcément un de ces sommets. En d'autres termes la solution optimale est atteinte en un
sommet du convexe.
2.2 Méthodes de Résolution
Dans la littérature existante on distingue deux classes de méthodes de résolution d'un

programme linéaire à savoir la méthode graphique et la méthode du simplexe avec ses
diérentes variantes.
Nous allons résoudre ce programme de 2 manières :

Méthode graphique nous servira simplement a comprendre la procédure et énumérer
les concepts de base importants, qui de toute façon est limitée a 2 variables.
Méthode algébrique qui est évidemment celle utilisée dans les algorithmes de résolu-
tion. Il faut dire aussi que les méthodes implémentées dièrent quelque peu de
celle présentée ici. Elle a été simpliée pour l'ecacité de l'utilisation de l'outil
informatique.

2.2.1 La Méthode Graphique

Cette méthode est simple mais malheureusement elle ne s'applique qu'aux programmes
linéaires possédant au plus deux variables. Le principe de cette méthode est de représenter
graphiquement l'espace engendré par l'ensemble des contraintes, de parcourir tous les
sommets du polyèdre et de choisir ensuite celui qui optimise la fonction objective.
Reprenons la forme initiale de l'exemple, et donnons les droites correspondant aux iné-
galités voir gure 2.1. Chaque droite (prenons le cas par exemple de la droite D1) divise
le plan en 3 parties :
1. la droite elle-même : ensemble des couples de points (x1 , x2 ) vériant l'équation :

0.25x1 + 0.5x2 = 40.
2. le demi-plan inférieur ensemble des couples de points (x1 , x2 ) vériant l'inéqua-
tion : 0.25x1 + 0.5x2 < 40.
3. le demi-plan supérieur ensemble des couples de points (x1 , x2 ) vériant l'inequa-
tion : 0.25x1 + 0.5x2 > 40.
Les 2 premières parties sont solutions au problème, la troisième ne l'est pas. Par con-
séquent un point (x1 , x2 ) est solution au problème si vérie toutes les contraintes, et donc
appartient a l'intersection des domaines. De façon pratique prendre un point et voir s'il
est ou non dans le domaine. Par exemple le point (0, 0) vérie toutes les contraintes.
La droite D0 est au fait un faisceau de droites parallèles. Le déplacement de cette

droite fait changer la valeur de la fonction objective, déterminer donc le sens de l'amélio-
ration de la fonction objective. Par exemple pour le point (0, 0) la valeur de la fonction est
0 pour (30, 20) la valeur est 120 donc le déplacement de la droite vers la droite améliore
la solution.
On voit donc facilement la solution optimale, le dernier point du domaine réalisable en

déplaçant D0 vers la droite , ici le point C. Voir le graphe 2.1 page suivante.
D0 2x1 +3x2 =z
max F = 2x1 + 3x2
D1 0.25x1 +0.5x2 = 40
0.25x1 +0.5x2 ≤ 40
D2 0.4x1 +0.2x2 = 40
0.4x1 +0.2x2 ≤ 40
D3 +0.8x2 = 40
0.8x2 ≤ 40
x1 ≥ 0 et x2 ≥ 0 D4 x1 =0
D5 x2 =0
Table 2.1: Résolution Graphique d'un PL
Le domaine ainsi représenté est un polyèdre convexe, qui a des propriétés très intéres-
santes que nous allons voir ci après.

Figure 2.1: Résolution graphique du P.L. 1
Dans le cas de l'exemple 2.1.1, le polyèdre convexe correspondant est représenté sur la
gure 2.1. Ce polyèdre possède 5 sommets O, A, B, C, D de coordonnées respectives
(0,0), (0,50), (60,50), (80,40) et (100,0). Les valeurs de la fonction objective en ces points
sont respectivement 0, 150, 270, 280 et 270. Il est donc évident que le sommet C est la
solution optimale, correspondant aux valeurs : x1 = 80, x2 = 40 et F = 280.
2.2.2 Principes Fondamentaux

La Solution est un Sommet
La solution optimale d'un PL (Programme Linéaire) si elle existe, est un sommet : Dans
notre cas un sommet est l'intersection de 2 droites, dans l'espace a 3 dimensions, c'est
l'intersection de 3 plans, en général dans l'espace à n dimensions c'est l'intersection de
n hyperplans.
Considérons le point B(60, 50) sur le graphe, il se trouve sur la droite D1 donc la variable
d'écart correspondante e1 = 0 et sur la droite D3, donc e3 = 0. Ceci est valable pour
tous les sommets. Notons que certains sommets ne sont par réalisables, comme pour le
sommet S(75, 50) intersection D2 et D3. Un sommet peut être l'intersection de plus de 2
droites, c'est alors un sommet dégénéré .

La Signication Algébrique
Algébriquement, un sommet (toujours dans le plan) correspond une solution de base,
c'est a dire, 2 variables (au moins) sont nulles. Si on revient a notre exemple, voir le
système de la section 2.1.3 page 17. La solution optimale est donc une solution de base,
correspondant a 2 variables nulles et les autres sont calculées par résolution du système
d'équations 3X3. Par exemple le point O(0, 0) correspond aux valeurs (x1 = 0 , x2 = 0 ,
e1 = 40, e2 = 40 et e3 = 40). Le point A(0, 50) correspond a la solution ( x1 = 0,
x2 = 50, e1 = 15, e2 = 30 et e3 = 0). On dira que la variable x2 est entrée dans la base,
devenue non nulle et la variable e3 est sortie de la base avec la valeur 0; De plus c'est
deux sommets sont adjacents.
Direction de Déplacement
La procédure d'optimisation est donc de se déplacer d'un sommet à un autre sommet
adjacent en s'assurant de l'amélioration de la solution.
Exercice 2.2.1. Donner pour notre exemple, le nombre de sommets, de sommets réal-
isables et comment trouver leur coordonnées. Généraliser pour un PL avec N variables
principales et M contraintes.
A deux sommets adjacents correspond deux solutions de base qui varient uniquement
par une variable. Les sommets O et A sont adjacents, leur solutions de base (e1 , e2 , e3 )
et ( e1 , e2 , x2 ) varient par les variables e3 et x2 . C'est a dire e3 est sortie de la base et
x2 est entrée.
Ici nous avons choisi de nous déplacer dans la direction x2 , c'est à dire on a choisi de
faire rentrer cette variable dans la base, car on sait qu'elle améliore
1 la solution.
Limite des valeurs des variables

Pourquoi sommes nous arrêter au point A, au lieu d'aller au point T(0, 80) par exemple
qui est aussi un sommet ? La réponse est évidente au vue du graphe, sinon on sort du
domaine de faisabilité, T est un point non réalisable, il ne vérie par la troisième con-
trainte. Maintenant comment le traduire algébriquement ? Nous verrons la justication
détaillée plus tard, pour l'instant nous disons, que la variable e3 est positive au dessous
de la droite D3, elle devient nulle sur D3 et devient négative plus haut. Puisque toutes
les variables doivent être non-négative, T est donc refuse. La procédure de passage d'un
sommet a un autre doit prendre en charge la positivite des variables.
Critère d'arrêt
Lorsqu'il n'y a plus d'amélioration possible, si la solution est réalisable alors
elle est optimale sinon elle n'existe pas.
1. On verra plus tard pour la justication algébrique

2.2.3. La Méthode du Simplex A.Belahcene
2.3 La Méthode du Simplex
2.3.1 Les Concepts de Base

Cette section fait suite, à la section sur les Principes Fondamentaux , dans laquelle
nous allons traduire algébriquement les règles déjà obtenues graphiquement.
Cette méthode a été mise au point par Dantzig en 1948. Elle permet de résoudre les
problèmes de la programmation linéaire. Son principe est de passer d'une solution de base
réalisable à une autre solution de base réalisable meilleure (amélioration de la valeur de
la fonction objective). Dans le cas où il n'est pas possible d'améliorer cette valeur alors
la solution optimale est atteinte (si elle existe).
Néanmoins, l'utilisation de cette méthode nécessite une solution de base réalisable de

départ. Cette condition n'est pas un handicap puisque l'on verra à la section 2.4 comment
obtenir une solution de base réalisable de départ.
Les diérentes étapes de la résolution du P.L.1 par la méthode du simplexe sont décrites
par la gure 2.2 suivante :
Etape 1 A B Etape 2
C Fin
Debut O D
Figure 2.2: Cheminement de la méthode du simplexe
Nous allons illustrer à travers l'exemple 2.1.1 le fonctionnement de la méthode du sim-

plexe et déduire par la suite l'algorithme de résolution d'une manière générale et donner
les justication des règles utilisées. Reprenons la forme standard vue a la section 2.1.3 et
donnons le tableau du simplex associé :
Cette solution de base (ce tableau) correspond sur le graphe à l'origine O = (0,0). Nous
avons noté par :
XB , XN Variables de base et hors base. Rappelons que les variables hors base sont
toujours nulles
CB , C N Coecients de ces variables dans la fonction objective, respectivement des vari-

ables de base et hors base.

XB CB P1 P2 P3 P4 P5 b
e1 0 0.25 0.5 1 0 0 40
e2 0 0.4 0.2 0 1 0 40
e3 0 0 0.8 0 0 1 40
Cj 2 3 0 0 0
Yj 0 0 0 0 0
∆j 2 3 0 0 0 Z=0
Figure 2.3: Tableau Initial de l'exemple
AB , A N Matrice des coecients des contraintes scindée en colonnes des variables de

base et hors base.
Yj = CB .Pj est le produit scalaire des vecteurs colonnes Pj et CB . Il représente l'inuence

des variables de base dans la fonction objective.
∆j est le gain réduit causé par la variable hors base j si elle rentrait dans la base.
Z Valeur de la fonction objective.
2.3.2 Méthode Pratique par les Tableaux

Dans ce tableau ( 2.3), La solution actuelle est (40, 40, 40), qui est le vecteur b, corre-
spondant aux variables de base e1 , e 2 et e3 . La valeur de la fonction objective est nulle
Z = 0. Les variables hors base sont nulles.
Nous résumons les étapes a suivre, nous verrons plus loin les justications.
1. Une hors base peut rentrer si son coût réduit est positif. Dans notre cas x2 (ou
d'ailleurs x1 ) peut rentrer dans la base, car son delta est positif (∆2 = 3). On
choisit donc la colonne pivot .
2. Parmi les variables de base, prendre celle qui correspond au minimum du rapport
de b et de la colonne pivot. Dans notre cas, on choisit de sortir de la base la variable
e3 qui correspond au minimum :
b 40 40 40
min ( ) = min( , , ) = 50
P2 0.5 0.2 0.8
3. La case pivot ainsi obtenue, va permettre de transformer le tableau avec la

méthode de Gauss, et obtenir la nouvelle solution, de sorte que le vecteur entrant
dans la base (ici P2 ) devient identité, 1 a la position e3 et 0 ailleurs.
Voyons comment la transformation est faite sur l'exemple, la généralisation est
immédiate.
Soit Lp=(e3 , 0, 0, 0.8, 0, 0, 1, 40), la nouvelle ligne pivot sera NLp=(x2 , 3, 0, 1, 0,

0, 1.25, 50), après division par le pivot 0.8, évidemment les 2 premiers éléments x2
et 3, ne sont pas concernés par la division. La nouvelle ligne une : NL1 est obtenue
à partir de L1 (ancienne ligne une) et de NL1 comme suit : NL1= L1 - 0.5*NLp, ou

0.5 est la case colonne pivot ligne une. Ainsi NL1= (e1 , 0.25, 0, 1, 0, 0, 0.625, 25).
On fait de même pour la ligne 2. Notons l'ordre de la soustraction, ne pas détruire
l'identité
4. Compléter le tableau par calcul des autres éléments (Y , ∆ et Z ).

Les deuxième et troisième tableaux obtenus sont comme suit :
Xb Cb P1 P2 P3 P4 P5 b Xb Cb P1 P2 P3 P4 P5 b
1
e1 0 4 0 1 0 − 85 15 x1 2 1 0 4 0 − 25 60
4
e2 0 10 0 0 1 − 14 30 e2 0 0 0 − 58 1 3
4 6
5 5
x2 3 0 1 0 0 4 50 x2 3 0 1 0 0 4 50
Cj 2 3 0 0 0 Cj 2 3 0 0 0
15
Yj 0 3 0 0 4 150 Yj 2 3 8 0 − 54 270
∆j 2 0 0 0 − 15
4 ∆j 0 0 -8 0 5
4
Exercice 2.3.1. Donner le tableau suivant et vérie qu'il est optimal, et correspond au
sommet C sur le graphe 2.1 page 20. La variable d'écart e3 n'est pas nulle à l'optimum.
En pratique, cela signie que la troisième contrainte n'est pas serrée. Ceci veut dire que
l'utilisation hebdomadaire de la troisième machine n'a pas atteint la limite qui est de 40
heures.
2.3.3 Justication de la Méthode

Critère d'entrée
La variable candidate à entrer dans la base est celle qui possède un coecient reduit
∆j positif, en général on choix le plus élevé dans l'espoir d'arriver plus vite, ce qui
n'est pas toujours vrai. En d'autres termes la nouvelle variable de base xr est telle que :
∆r = max{∆j , |∆j > 0} où ∆j représente le coecient de la variable xj dans le vecteur
F , son expression sera explicitée ultérieurement. Ainsi, la variable x2 à la première étape
de résolution du programme linéaire rentre en base car elle possède le coecient le plus
élevé dans ∇j .
Nous allons donner la justication de ce choix. A une étape quelconque, disons p, de notre
algorithme, nous pouvons éclater notre espace en variables de base XB , B ensemble de
variables de base, et hors base XN , N ensemble de variables hors base, ces dernières
sont nulles. Regardons la condition sur une variable hors base xk avec k ∈ N, notons
N = N − {k}, les variables hors base qui restent donc nulles. Nous donnons ici le debut
de la démonstration, Le reste est laissé en exercice.
X X X
Z= ci xi + ci xi + ck xk = ci xi (2.3)
i∈B i∈N i∈B
X X X
Z= ci x̄i + ci xi + ck xk = ci x̄i + ck xk (2.4)
i∈B i∈N i∈B

Dans la pemiere equation 2.3 toutes les variables de i ∈ N , sont nulles, dans la seconde 2.4
page précédente la variable xk prend une valeur, de meme les variables de base changent
de valeur.
Démonstration. La variable xk améliore la solution si Z − Z > 0. Déterminons d'abord

les nouvelles valeurs des variables de base xi pour i∈B .
X
xi = bi − aik xk − aij xi = bi − aik xk (2.5)
j∈N
Cette equation correspondant à la ligne xi du tableau du simplex est établie car variables
j∈N restent nulles. En d'autres termes la quantité aik xk est la modication de la valeur
de la variable xi (elle était bi ) lorsque xk devient positive. Pour l'ensemble du problème,
faire la somme pour toutes les variables de base. Ainsi l'équation 2.4 page précédente
devient
X X X
Z = ci (bi − aik xk ) + ck xk = ci bi + ck xk − ci aik xk (2.6)
i∈B i∈B i∈B
X
= Z + (ck − ci aik )xk = Z + (ck − CB Pk )xk = Z + ∆k xk (2.7)
i∈B
L'amélioration est donc possible si ∆k = ck − Yk > 0, où Pk est la colonne correspondant

à la variable xk et Yk = CB Pk du tableau du simplexe .
Critère de sortie
Pour déduire la formule permettant de trouver la variable xs qui sort de la base, il

serait utile de reprendre l'illustration de la méthode du simplexe et de voir comment, par
exemple, à la première étape la variable e3 est sortie de la base :
e1 = 40 −0.5x2 ≥ 0
e2 = 40 −0.2x2 ≥ 0 (2.8)
e3 = 40 −0.8x2 ≥ 0
Ce système est équivalent à :
40 40 40
x2 ≤ = 80, x2 ≤ = 200, x2 ≤ = 50, (2.9)
0.5 0.2 0.8
Ceci implique que x2 = min{80, 200, 50} = 50 . Ensuite, on a posé que x2 = 50 . Il
ne faut pas perdre de vue que x2 représente la variable rentrante, c'est-à-dire xr . La
variable xs doit donc satisfaire le critère suivant : min{bi /air , air > 0} = bs /asr ou
air est appelé le pivot. La variable xs est la première variable de base qui s'annule quand
on augmente la valeur de la variable hors base xr et toutes les autres variables de base
b1 b2 b3
restent donc positives. A la première étape on a : = 80 , = 200 , = 50 Par
a12 a22 a32

b3 b1 b2 b3
suite la variable e3 sort de la base car elle vérie bien : = min { ; ; }.
a32 a12 a22 a32
Formellement on peut écrire les formules de passage d'une étape à une autre comme suit :
Soient r et s les indices des variables entrante et sortante, et akij l'élément de la ligne i,
de la colonne j du k
em tableau et aksj l'élément pivot. Nous aurons alors :
aksj
ak+1
sj = j = 1, ..., m + n + 1
aksr (2.10)
ak+1
sj = aksj − aksr ∗ akir i 6= s et j = 1, ..., m + n + 1
Rappelons que le tableau du simplexe a n + m colonnes correspondant aux variables

initiales et d'écart et une colonne correspondant au second membre.
Critère d'arrêt
Nous avons vu que la méthode du simplexe dans le cas d'un problème de maximisation
se termine lorsque les coecients des variables hors-base dans le vecteur F sont tous
négatifs ou nuls. En d'autres termes, on doit avoir : ∇j ≤ 0, ∀j ∈ N où N) représente les
indices des variables hors-base.
Résumé
Tous les mécanismes de calculs que nous venons d'eectuer peuvent être résumés dans
un tableau, appelé, tableau du simplexe. Reprenons le programme 2.1.3 page 17
max F = 2x1 +3x2

0.25x1 +0.5x2 +e1 = 40
0.4x1 +0.2x2 +e2 = 40
0.8x2 +e3 = 40
x1 , x2 , e1 , e2 , e3 ≥ 0
On remarque que tous les coecients ∆j sont négatifs ou nuls, la solution courante est
donc optimale.
L'algorithme du simplexe s'énonce comme suit :
1. Mettre le programme linéaire sous sa forme standard.
2. Recherche d'une solution de base réalisable de départ.
3. Construire le premier tableau du simplexe.
Tester si : ∇j ≤ 0, ∀j ∈ {1, ..., n}

4. si oui ; terminer la solution est optimale
si non ; aller en (5)

2.2.4. Recherche d'une Solution de Base Réalisable A.Belahcene
5. Soit∇r = max{∆j |∆j > 0} la variable xr entre en base
Tester si : air ≤ 0 ∀i ∈ {1, ..., m}
si oui ; terminer le problème ne possède pas de solution optimale nie.
si non ; aller en (6)
6. On détermine la variable sortante xs par :

bs bi
= min{ , air > 0} où asr est le pivot. Aller en (6)
asr air
7. Obtenir le nouveau tableau du simplexe en divisant la ligne-pivot par le pivot. Les
autres éléments du tableau sont obtenus par la règle précédente ( voir formule 2.10).
Aller en (3).
2.4 Recherche d'une Solution de Base Réalisable
Il est impératif d'avoir une solution de base réalisable de départ pour pouvoir utiliser
la méthode du simplexe. Dans plusieurs situations, celle-ci n'est pas toujours facile à
obtenir. La méthode des deux phases que nous allons exposer dans ce paragraphe est une
variante de la méthode du simplexe. La première phase consiste à associer un problème
auxiliaire au programme-standard pour déterminer une solution de base réalisable. La
deuxième phase utilise la méthode du simplexe pour optimiser cette solution obtenue.
On general on utilise 2 methodes :

methode du BigM : consiste a ajouter des variables articielles pour obtenir une so-
lution de base , avec un cout tres negatif penalisant donc ces varaibles de sorte
a les faire sortir de la base. On fait sortir les variables articielles grace au cout tres
negatif. On obtient une base de depart, bien sur non realisable. On utilise l'algorithme
de facon tout a fait ordinaire. Voir exercice.
methode du programme auxilliaire. Nous la presentons ici en detail.
Considérons le problème linéaire sous sa forme standard :
max F = cx
(2.11)
Ax = b x≥0
Nous Associons 2.11 le programme auxiliaire suivant :
m
X
min ϕ= yi
i=1
Ax +y =b
x≥0 , y≥0

x désigne le vecteur variable du programme d'origine ainsi que les variables d'écarts et y
le vecteur représentant les variables articielles. Le programme auxiliaire 2.4 est obtenu
a partir du programme 2.11 après ajout des variables yi appelées variables articielles.
On rajoute les variables articielles uniquement aux contraintes du programme 2.4 qui
ne contiennent pas de variable de base. La solution de base ne peut être réalisable que si
les valeurs des Y sont nulles. Le principe de la méthode des deux phases est :
Phase 1 : Résoudre le problème auxiliaire par la méthode du simplexe. Si ce problème

possède une solution optimale nie, alors cette solution est de base réalisable pour le
problème initial.
Phase 2 : Résoudre le problème initial en utilisant comme solution de base réalisable

de départ, celle trouvée à la n de la phase 1.
Exemple 2.4.1. Soit le programme linéaire puis réecrit sous forme standard. Utiliser la
méthode des deux phases pour résoudre ce problème
min f = x1 + 2x2 0
max f = −x1 −2x2
2x1 + x2 ≤ 6
2x1 +x2 +e1 =6
x1 + x2 = 4
x1 +x2 =4 (2.12)
x1 + 3x2 ≥ 8
x1 +3x2 −e2 =8
x1 , x 2 ≥ 0
x1 , x2 , e1 , e2 ≥ 0
Exercice 2.4.2. Faire la resolution graphique, puis utiliser la méthode du BigM puis
des deux phases pour résoudre ce problème
Il n'est pas nécessaire de rajouter une variable articielle à la première contrainte. En

eet, en écrivant la forme standard du programme (P.L.2) on obtient :
La première contrainte contient la variable e1 comme variable de base. Par contre, on doit
rajouter une variable articielle à la deuxième et à la troisième contrainte. Le problème
auxiliaire (P.L.A) du problème (P.L 2) s'écrit comme :
min ϕ = y1 +y2
2x1 +x2 +e1 =6
x1 +x2 +y1 =4 (2.13)
x1 +3x2 −e2 + y2 = 8
x1 , x 2 , e 1 , e 2 , y1 , y2 ≥0
Avant d'utiliser la méthode du simplexe pour résoudre le programme 2.13. on se gardera

de ne pas oublier d'exprimer la fonction objective de ce programme en termes de variables
hors-base.
A la n de la phase 1, s'il existe une solution optimale nie alors elle doit être néces-
sairement nulle avec yi = 0 ∀ i ∈ I(A), où I(A) représente l'ensemble des indices des
variables articielles. Nous discuterons dans le prochain chapitre le cas où il n'existe pas
de solution optimale nie.

Pour accroître la rapidité de résolution du problème, il est conseillé d'introduire dans le

tableau du simplexe, lors de la résolution de la phase 1 du programme 2.13, la fonction
objective du programme 2.12. et lui faire subir les mêmes mécanismes de calcul que ceux
eectués pour la fonction objective ϕ.
Utilisons la méthode des deux phases pour résoudre le problème 2.13. Pour cela, expri-
mons la fonction objective du problème en terme de variable hors-base x1 , x 2 et e2 . Ce
problème est équivalent au problème suivant
2 :
max (−ϕ) = 2x1 + 4x2 −e2

2x1 +x2 +e1 =6
x1 +x2 +y1 =4 (2.14)
x1 +3x2 −e2 + y2 = 8
x1 , x 2 , e 1 , e2 , y1 , y2 ≥0
Phase 1 : Le premier et deuxième tableau du simplexe ( pour le probleme modie) :
XB CB x1 x2 e1 e2 y1 b
XB CB x1 x2 e1 e2 y1 y2 b 5 1 10
e1 0 0 1 0
e1 0 2 1 1 0 0 0 6 3 3 3
2 1 4
y1 0 1 1 0 0 1 0 4 y1 0 0 0 1
3 3 3
y2 0 1 3 0 -1 0 1 8
1 1 8
x2 4 1 0 − 0
3 3 3
Cj 2 4 0 -1 0 0 Cj 2 4 0 -1 0
Yj 0 0 0 0 0 0 0 4 4 32
Yj 4 0 − 0
3 3 3
∆j 2 4 0 -1 0 0
2 1
∆j 0 0 0
3 3
La variable x2 entre en base et la variable articielle y2 sort de cette base.
On remarque que la dernière colonne du tableau initial ne gure plus dans ce tableau cela
est dû au fait que lorsqu'une variable articielle quitte la base, elle ne la réintègre plus,
il est donc inutile de conserver la colonne correspondante. La variable x1 entre en base et
remplace la variable articielle y2 . Remarquant que nous pouvons faire sortir aussi la
variable e1 au lieu de y1 , mais la nouvelle valeur de y1 sera nulle et donc nous l'eliminons
de toute facon. On obtient donc le tableau de la seconde itération.
Le critère d'optimalité pour la fonctionϕ est vérié car ∀j , ∇j = 0 . D'où la solution

de base réalisable de départ : x1 = 2 , x2 = 2 , e1 = e2 = 0 . On integre la fonction
objective max −f = f
0 = −x − 2x , initiale dans le tableau realisable et on continue
1 2
l'algorithme.
2. Nous negligeons la constante 12,

Phase 2 : Utilisons la méthode du simplexe avec comme solution de départ la solution

de base réalisable obtenue à la phase 1. Voir les tableaux suivants.
XB CB x1 x2 e1 e2 b
XB CB x1 x2 e1 e2 b 1
1 e1 0 0 0 1 − 0
e1 0 0 0 1 − 0 2
2 1
1 x1 -1 1 0 0 2
x1 2 1 0 0 2 2
2 1
1 x2 -2 0 1 0 − 2
x2 4 0 1 0 − 2 2
2 Cj -1 -2 0 0
Cj 2 4 0 -1
1
Yj 2 4 0 -1 12
Yj -1 -2 0 -6
2
1
∆j 0 0 0 0 ∆j 0 0 0 -
2
Les coecients des variables dans la fonction objective étant tous négatifs ou nuls, la
solution courante (x1
∗ = 2, x∗2 = 2, e∗1 = e∗2 = 0 et F ∗ = 6) est donc optimale.
2.5 Exercices
1. Déterminer la forme standard associée aux programmes linéaires suivants : et don-

ner la forme matricielle.
3x1 −3x2 +7x3 min 6x1 −3x2 +2x3 min
x1 +x2 +3x3 ≤ 40 x1 +3x2 +x3 ≥ 40
x1 +9x2 −7x3 ≥ 50 2x1 +3x2 +3x3 ≤ 50
5x1 +3x2 = 20 4x1 +2x2 +x3 ≤ 20
5x2 +8x3 ≤ −100
x1 ≥ 0 x2 ≥ 0 x3 ∈ R x1 ≥ 0 x2 ≥ 0 x3 ≥ 0
2. Un producteur fabrique deux produits A et B. La table suivante résume les besoins

du producteur. Celui-ci a décidé de ne pas produire plus de 5 unités du produit A.
Les prots unitaires de chaque produit est de 300 DA et 400 DA respectivement.
Les matières premières nécessaires à la fab-
rication de ces deux produits sont l'alu-
Prod Alum Bois M.O
minium, le bois et la main-d'oeuvre. Les lim-
A 2 1 7
ites sur ces ressources sont respectivement de
B 1 8 8
11 unités, 40 unités et 52 heures par semaine
par ouvrier.
a) Formuler ce problème en programme Lineaire.
b) Résoudre graphiquement ce problème.
c) Résoudre ce problème par la méthode du simplexe.

3. Les disponibles pour la matière première A et B sont évalués respectivement à 14

unités et 20 unités. Il s'agit de déterminer les quantités en matière première de
chaque type à utiliser de manière à minimiser le coût total de production.
Deux matières premières sont utilisées

Matière Coût (D.A) Poids (Kg)
dans un processus de fabrication. Le
Unitaire Unitaire
produit nal doit avoir un poids égal à
A 4 5
150 kg. Les coûts et les poids unitaires
B 8 10
sont résumés dans le tableau ci-contre.
a) Formuler ce problème comme un programme linéaire.
b) Écrire la forme standard associée.
c) Résoudre graphiquement ce problème. Conclure.
d) Résoudre ce programme linéaire en utilisant la méthode des deux phases.
e) Resoudre ce programme avec la methode du BigM.
f ) reprendre le meme probleme (meme contraintes), en remplacant l'objectif min-

imisation des couts par maximisation des prots.
4. Le directeur commercial d'une entreprise désire maximiser la couverture publicitaire

d'un de ses produits. Il a le choix entre un placard publicitaire dans un magazine
avec lequel il pourrait atteindre 10 millions de personne et un spot publicitaire où
il toucherait 20 millions de personnes. Le coût d'un placard publicitaire s'élève à
40,000 D.A et le coût d'un spot publicitaire à 75,000 D.A. Le directeur commercial
dispose d'une enveloppe de 2000,000 D.A et doit acheter au moins 20 placards
publicitaires dans un magazine. Le problème est de savoir combien d'unités de
chaque type de publicité acheter de manière à maximiser la couverture commerciale
de ce directeur
a) Structurer, formuler et modéliser ce problème.
b) Écrire sa forme standard.
c) Résoudre graphiquement ce problème.
d) Résoudre ce problème par l'algorithme du simplexe.
5. Démontrer que le choix de la variable entrant est correct, voir section 2.3.3 page 24
6. Soient les programmes linéaires suivants :
max Z = −x1 +2x2 −3x3 max Z = −x3 −2x4 −x5 +11

x1 +x2 +x3 =6 x1 +x3 −x4 +2x5 = 2
−x1 +x2 +2x3 =4 x2 −x3 +2x4 −x5 ≤ 50
+2x2 +3x3 =0 4x1 +2x2 +x3 ≤ 20
x3 ≤2
x1 ≥ 0 x2 ≥ 0 x3 ≥ 0 xj ≥ 0 j = 1..5
Résoudre ces programmes linéaires en utilisant la méthode la plus appropriée.

7. Une entreprise de conserve de tomates utilise 2 ateliers pour l'emballage et 3 dépôts

pour le stockage du produit ni.
Elle organise le transport des ateliers aux Dépot D1 D2 D3
dépôts de sorte a satisfaire la demande aux Atelier
moindres coûts. Les coûts de transport sont A1 25 17 18
résumés dans le tableau. A2 25 18 14
L'atelier 1 peut produire jusqu'à 850 cartons en une semaine, l'atelier 2 son niveau
de production maximal atteint 650 cartons en une semaine. La demande au niveau
de chaque dépôt est estimée respectivement à 300, 400 et 500 cartons.
a) Structurer, formuler et modéliser ce problème.
b) Résoudre ce problème en utilisant une méthode appropriée.
8. Montrer, en utilisant la méthode graphique, que ce programme linéaire possède une

innité de solutions.
Le domaine convexe de ce pro-

gramme linéaire est donné par la
gure ci-contre. Les sommets B =
(2.6) et C = (4.3) sont solutions /home/bela/Education/Ro/PolyRo/infinite.ep
optimales. Donc toute combinaison
convexe de ces deux solutions opti-
males est aussi optimale.
L'ensemble des solutions optimales est O = { (x1 , x2 ) | 3 x1 + 2 x2 = 18. Le

lecteur est invité à montrer algébriquement ce résultat.

3 Concepts Avancés de la PL
Nous allons exposer quelques modèles particuliers de programmation linéaire et nous
donnons les méthodes adéquates de résolution. Ensuite nous abordons l'analyse sensitive
et post-optimale qui est d'un intérêt capital dans la vie pratique. Une autre partie sera
consacrée à la notion de dualité en programmation linéaire. L'accent sera mis sur l'intérêt
pratique de la dualité surtout en analyse sensitive et post-optimale.
3.1 Modèles Particuliers
3.1.1 Modèle irréalisable

Un programme linéaire est dit irréalisable si certaines de ses contraintes se contredisent.
Prenons à titre d'exemple un programme linéaire ayant les contraintes suivantes :
x1 + x2 ≥ 7 et x1 + x2 ≤ 2.
Ce programme est irréalisable, puisque il n'a pas de solution. Lorsqu'un tel cas se présente
la formulation du problème doit être revue. On peut reconnaître un tel cas par la présence
d'une variable articielle dans la base à la n de la phase 1.
3.1.2 Modèle dégénéré

Un modèle est dégénéré si une variable de base est nulle. Le cas de degenerescence
est extremment rare, malgre tout il faut le prendre en consideration. Dans ce cas, il est
possible qu'une itération de la méthode du simplexe n'améliore pas la valeur de la fonction
objective. Pour illustrer ce cas, considérons un programme linéaire dont l'ensemble des
contraintes est délimité par les contraintes A, B et C. On rappelle, qu'en général, la
méthode du simplexe passe d'un sommet S1 où les contraintes A et B se rencontrent au
sommet S2 où les contraintes B et C se rencontrent tout en améliorant la valeur de la
fonction objective. La gure 3.1(a) donne un cas de situation normale et la gure 3.1(b)
le cas d'un modèle dégénéré.
Exemple 3.1.1. Considerons le cas suivant. Si on fait entrer la variable x2 et donc

e5 sort en entre dans le cycle de degenrescence, par contre si e1 entre et donc e2 on evite
la degenerescence du moins pour le moment.
33
3.3.1. Modèles Particuliers A.Belahcene
XB CB x1 x2 x3 e1 e2 e3 e4 e5 b
4
x3 0 2 1 -3 0 2 0 0 1
3
e2 0 0 -1 0 3 1 -1 0 0 4
11
x1 − 1 0 0 0 0 2 0 0 3
6
e4 0 0 0 0 1 0 -1 1 0 2
e5 0 0 1 0 -1 0 0 0 1 0
11 23 4
Cj − 0 0 0 0 0
6 3 3
11 8 4
Yj − -4 0 −1 0 0
6 3 3
∆j 0 5 0 4 0 1 0 0
A S2
S1 S1 = S2
B C A C
B
a) Situation normale b) Situation degeneree
Figure 3.1: Situation normale et situation dégénérée
Considérons la situation où, lors de la résolution d'un problème par la méthode du sim-
plexe, on passe du sommet S1 au sommet S2 , correspondant à deux solutions de bases
diérentes.
Dans certains cas, voir l exemple de la gure 3.1 (b), S1 et S2 est le même sommet, on
peut ainsi rester au même point après plusieurs itérations.
Cette situation est aussi appelée cycle. Le cycle peut être inni. La convergence de
l'algorithme du simplexe n'est pas assurée dans ce type de problème. Pour éviter le cycle,
on peut utiliser, par exemple, la méthode de perturbation. Elle permet de passer d'une
première solution de base réalisable à la solution optimale, si elle existe, sans retourner
à une solution antérieure. Dans cette méthode le vecteur b est substitué par le vecteur
b(ε), déni comme suit ( on l'appelle représentation lexicographique) :
n
X
j
b(ε) = b + ε Pj
j=1
où ε est un nombre très petit et Pj représente le vecteur-colonne de la variable xj dans

la matrice du système des contraintes. Cette façon de faire permet de séparer les cas

3.3.1. Modèles Particuliers A.Belahcene
ex-equo, c'est a dire 0 + εest diérent de 0 + ε2 bien qu a la limite (ε = 0) la valeur sera

la même. géometriquement cela signie que l'on sépare légèrement les sommets S1 et S2
par exemple de la gure 3.1, et quand on quitte le sommet S1 pour S2 on ne revient plus
sur S1 , car S2 correspond à une meilleure solution que S1 . On résout par la méthode
du simplexe ce problème perturbé puis on revient, à la n de la résolution, au problème
initial en posant ε = 0.
3.1.3 Modèle non borné

Un programme linéaire est dit non borné si son optimum est inni. On reconnaît un tel
modèle lorsqu'à une itération donnée, le vecteur-colonne de la variable xr qui entre dans
la base est négatif ou nul. Le programme linéaire ne possède pas de solution optimale
nale car on peut augmenter indéniment la valeur de la variable xr .
Soit le programme linéaire 3.1 suivant :
x2
max F = x1 +x2
x1 −x2 ≤ 1 Domain
(0.3)
(3.1)
−2 x1 +x2 ≤ 3
x1 , x2 ≥ 0
x1
(1.0)
Résoudre ce programme linéaire en utilisant la méthode du simplexe. Retrouver le resultat
en vous inspirant de la gure.
les variables d'écart e1 et e2 , en util-

Base CB x1 x2 e1 e2 b
isant la méthode du simplexe et après x1 1 1 -1 1 0 1
une itération, on obtient le tableau suiv- e2 0 0 -1 2 1 5

ant : ∆1 0 2 -1 0 -1
La variable x2 est candidate à entrer dans la base. Mais, le vecteur P2 est négatif. On
ne peut sortir une variable, car la variable x2 peut être augmentée indéniment sans que
l'une des variables de base devienne négative. En eet, la première ligne s'écrit :
x1 − x2 + e 1 = 1 ou encore, x1 = 1 + x2 − e1
En gardant e1 = 0 , on peut augmenter indéniment la variable x2 la variable x1 reste

positive ou nulle. On peut faire de même pour la seconde ligne de ce tableau. En pra-
tique, cette situation peut signier l'omission d'une contrainte vitale. Dans ce cas, une
restructuration du problème s'impose.

3.3.2. La Dualité A.Belahcene
3.1.4 Modèles à innité de solutions

Il existe en pratique des modèles qui possèdent une innité de solutions optimales. Ce
type de modèle apparaît lorsqu'à la n de la résolution du programme linéaire par la
méthode du simplexe une variable hors-base possède un coecient reduit nul ( ∆ = 0).
Dans ce cas, une itération supplémentaire donnera une seconde solution optimale. Toute
combinaison convexe (i . e. combinaison linéaire dont la somme des coecients est égale
à 1) de ces deux solutions est une solution optimale.
Soit le programme linéaire 3.2 suivant :
x2
max F = 3 x1 + 2 x2
(0.6) (2.6)
3x1 +2 x2 ≤ 18
x1 ≤ 18 (3.2)
(4.3)
2 x2 ≤ 18
x1 , x2 ≥0
x1
droite de F
Montrer , en utilisant la méthode graphique, que ce programme linéaire possède une
innité de solutions Le domaine convexe de ce programme linéaire est donné par la
gure.
Les sommets B = (2.6) et C = (4.3) sont solutions optimales. Donc toute combinaison
convexe de ces deux solutions optimales est aussi optimale.
L'ensemble des solutions optimales est O = { (x1 , x2 ) | 3 x1 + 2 x2 = 18 }. Le lecteur

est invité à montrer algébriquement ce résultat.
3.2 La Dualité
En pratique, il arrive que la résolution d'un programme linéaire par la méthode du

simplexe soit dicile en raison du nombre important de contraintes dans le programme
linéaire. Le passage à la forme duale réduit la taille des solutions de base, la résolution
traitera des matrices réduites. La dualité joue un rôle important en analyse post-optimale
et sensitive, à cause surtout du théorème des écarts complémentaires que nous verrons à
la soussection 3.2.2
Considérons les programmes linéaire duaux : primal et dual suivants. A chaque contrainte
i du primal on associe une variable duale

c1 x1 +c2 x2 +... +cxnn M in z

a11 x1 +a12 x2 +... +ahn xn ≥ bl
... ... ... ... ...
ahl x1 +ah2 x2 +... +ahn xn ≥ bh
ui . a(h+1)1 x1 +... +a(h+n)n xn = b(h+1)
... ... ... ... ...
aml xl +am2 x2 +... +amn xn = bm
xj ≥ 0 xj ∈ R
j = 1, ..., K j = k − 1, ..., n
Associons a chaque contrainte i une variable duale uj . nous obtenons le programme dual :
b1 u1 +b2 u2 +... +bm un M axW

a11 u1 +a12 u2 +... +alm um ≤ cl
... ... ... ... ...
ak1 u1 +ak2 u2 +... +akm um ≤ ck
a(k−1)1 u1 +.. +a(k−l)m um = c(k+1)
... ... ... ... ...
an1 u1 +an2 u2 +... +amn un = cn
u1 ≥ 0 i = 1, ..., h
u1 ∈ R j = h + 1, ..., m
La façon la plus simple d'obtenir le programme dual à partir du primal est de le mettre
sous l'une des formes standards, on peut passer de l'un à l'autre et inversement.
maxZ =C x min W = ub
(P ) Ax ≤b (D) uA ≥c
x≥ 0 u ≥0
Par exemple les 2 programmes suivant sont duaux :
max F = 2 x1 + 3 x2 min W =40u1 +40u2 +40u3

0.25 x1 + 3 x2 ≤ 40
0, 25u1 +0, 4u2 ≥2
0.4 x1 + 0.2 x2 ≤ 40 (3.3) (3.4)
0.8 x2 ≤ 40 0, 5u1 +0, 2u2 +0, 8u3 ≥ 3
x1 ≥ 0, x2 ≥ 0 u1 ≥ 0 u2 ≥ 0 u3 ≥ 0
De cette dénition, on tire les propriétés suivantes :
1. Cette transformation est involutive (le dual du dual est primal).
2. Une variable primale non-négative correspond à une contrainte-inégalité dans le

dual.
3. Une variable primale non astreinte correspond à une contrainte-égalité dans le dual..
4. La matrice des contraintes du dual est la transposée de la matrice du primal.
5. Les coecients de la fonction objective du primal sont le second membre du dual.
6. Un problème de minimisation primal devient un problème de maximisation dual.

3.2.1 Procedure de transformation

Pour obtenir le dual il est utile de tenir compte des regles suivantes :
1. Ramener le programme sous forme 3.3 ou 3.4
2. Eclater une equation en 2 inéquations équivalentes
3. Remplacer une variable non astreinte en variables positives.
Exercice 3.2.1. En vous inspirant des regles précédantes, donner les programmes duaux
des programmes linéaires suivants.
min f = x1 + 2 x2 max f = 2 x1 + 3 x2
5x1 +3x2 ≥ 12 x1 +2 x2 ≥5
(3.5) (3.6)
x1 −x2 =2 x1 +x2 =4
x1 ≥ 0 , x2 ∈ R x1 ≥ 0 , x2 ≥ 0
3.2.2 Théorème des écarts complémentaires

Avant d'énoncer ce théorème nous donnons deux lemmes :
lemme 1 : Si la solution optimale du primal x∗ existe et est nie alors celle du dual u∗
existe aussi et est nie. A l'optimum les valeurs des fonctions objectives sont égales,
c'est-à-dire c x∗ = u∗ b
.
lemme 2 : Si la solution optimale du primal est innie positive, alors le dual n'a pas de
solution. La réciproque n'est pas vraie. (La démonstration de ce lemme est laissée
en exercice).
On ne mettra pas l'exposant t pour la transposition de la matrice ou des vecteurs pour

alléger l'écriture. Il est évident que les opérations doivent être possibles, par exemple,
cx=ub devrait être écrite. ct x = ut b où c et u sont des vecteurs-colonnes.
Si la solution optimale du primal est innie positive, alors le dual n'a pas de solution. La
réciproque n'est pas vraie.
Démonstration :
Considérons les problèmes duaux :
min Z = C x max W = ub
(P1 ) Ax =b (D1 ) uA ≤c
x≥ 0 u ∈R
Si x∗ est solution réalisable du primal et u∗ solution du dual vériant : u∗ b = c x∗ , alors x∗ et u∗
sont des solutions optimales.

En eet, posons :
P = { x | A x = b et x ≥ 0 }
D={u | uA ≤c}
Soit x∈P alors A x = b. Multiplions cette équation par u on obtient : uAx=ub (1)
Soit u∈D alors uA≤c . Multiplions cette inéquation par x on trouve uAx≤cx (2)
En utilisant (1) et (2) on tire :u b ≤ c x, ∀ x ∈ P, ∀u ∈ D (3)
Soit u∗ ∈ D alors c x ≥ u∗ b, ∀x ∈ P. comme, c x∗ = u∗ b (par hypothèse), Il s'ensuit

que :
c x ≥ c x∗ , ∀x ∈ P. Donc x∗ est solution optimale de (P1 ).

De la même façon on montre que u est solution optimale de (D1 ).
Théorème 3.2.2. (Ecarts Complementaires) Une condition nécessaire et susante pour

que les solutions réalisables x∗ et u∗ soient optimales est qu'elles vérient les conditions
suivantes :
u∗ (A x∗ − b ) = 0
(3.7)
( c − u∗ A ) x∗ = 0
La traduction de la première condition est :

Si la contrainte primale n'est pas serrée alors la variable duale correspondante est nulle.
Si une variable duale est positive alors la contrainte primale est serrée.
La deuxième condition peut se traduire de la même façon. Montrons maintenant ce
théorème. Soient x∗ et u∗ solutions optimales. Par hypothèse on a :
Ax∗ − b = 0 , x∗ ≥ 0 (3.8)
et
c − u∗ A ≥ 0 (3.9)
En multipliant l'equation 3.8 par u∗ et l'equation 3.9 par x∗ on obtient :
ξ1 = u∗ (A x∗ − b) = 0 et ξ2 = (c − u∗ A) x∗ ≥ 0
Or, ξ1 + ξ2 = cx∗ − u∗ b = 0 car x∗ et u∗ sont optimales et le Lemme 1 donne u∗ b = c x∗ .

Il s'ensuit que : ξ1 = ξ2 = 0. D'où la condition nécessaire.
Supposons maintenant que x∗ et u∗ vérient le système 3.7 du théorème. Alors,
c∗ x = u∗ b. D'après le Lemme, 2 x∗ et u∗ sont optimales respectivement pour (P1 ) et (D1 ) .

D'où la condition susante.
La démonstration reste valable pour le cas d'un programme primal mis sous forme général
car une contrainte inégalité peut être transformée en une contrainte égalité.

Exercice 3.2.3. Soient le programme linéaire et son dual :
max F = x1 + 3 x2 +2 x3 max W = −8u1 +2u2 −2u3

x1 − 5 x2 +7 x3 ≤8 −u1 +2u2 −u3 ≤ −1
−2 x1 + 4 x2 −2 x3 ≤ −2 5u1 −4u2 +3u3 ≤ −3
x1 − 3 x2 +2 x3 ≤2 −7u1 +2u2 −2u3 ≤ −2
x1 , x 2 , x 3 ≥ 0 u1 , u1 , u3 ≥ 0
(3.10) (3.11)
1. Vérier que chacun des programmes est dual de l'autre.
2. Vérier que les solutions suivantes respectivement du primal et dual sont optimales.
xt = (1, 0, 0) et u = (0, 0.5, 0)
3. Vérier le théorème des écarts complémentaires c est a dire les conditions 3.7,
a) u(Ax − b) = (0, 1/2, 0) ∗ (−7, 0, 0) = 0

b) (c − uA)x = (0, 1, 3)∗, (1, 0, 0) = 0
Ces solutions sont donc optimales.
3.2.3 Déduction du Dernier Tableau du Simplexe du Dual (D)

Dans ce paragraphe nous allons donner une démarche qui permet de reconstituer le
dernier tableau du simplexe du programme dual à partir du dernier tableau du simplexe
du programme primal. On établit d'abord la correspondance entre les variables primales
avec celles du duales comme suit :
Variables
Programme Primal principales d'écarts

x1 xs e1 ep
⇓ ⇓ ⇑ ⇑
Programme Dual v1 vs u1 up
d'écarts principales
La solution du dual représente les coecients marginaux du primal à un signe près.

On identie les variables de base et hors-base du programme dual puis on exprime, en
utilisant le tableau du simplexe, les variables de base en fonction des variables hors-base
en inversant le signe des coecients.
Soit le programme linéaire de l'exemple 3.3 page 37 et son programme dual voir les
programmes 3.5 et 3.6.
Écrire le programme dual qui lui est associé, déduire le dernier tableau du simplexe de
ce programme dual puis donner sa solution optimale.
Les variables de base duale sont donc u1 et u2 . Par contre les variables u3 , v1 , v2 sont
hors-base. Exprimons les variables de base en fonction des variables hors base :
De façon pratique on procède comme suit :

Placer la matrice identité après avoir déterminé les variables de bases, correspon-
dant respectivement ( variable d'ecart primale donne variable principale duale et in-
versement) donne aux variables hors base du primal.
Mettre les coecients en changeant le signe des lignes y compris le Delta et Second
membre.
Compléter la ligne des coecients de la fonction objective. Ne pas oublier que nous
résolvons toujours un problème de maximisation ;
Vérier le calcul des delta en les recalculant à partir du tableau obtenu
D'où les derniers tableaux du simplexe du programme (D) et primal (P) sont : (on note
P les vecteurs colonnes)
Le programme dual de l'exemple 2.1.3 page 16est :
min W = 40u1 +40u2 40u3

0.25u1 +0.4u2 ≥2
0.5u1 +0.2u2 +0.8u3 ≥ 3
u1 u2 u3 ≥ 0
Xb Cb x1 x2 e1 e2 e3 b
Xb Cb u1 u2 u3 v1 v2 b
x1 2 1 0 −4/3 10/3 0 80
u1 -40 1 0 2.13 1,33 -8/3 16/3
e3 0 0 0 −32/15 4/3 1 8
u2 -40 0 1 -1,33 -3,33 1,67 5/3
x2 3 0 1 8/3 −5/3 0 40 .
C -40 -40 -40 0 0
C 2 3 0 0 0
Y -40 -40 -32 80 40
Y 2 3 16/3 5/3 0
∆j 0 0 -8 -80 -40
∆i 0 0 −16/3 -5/3 0
Exercice 3.2.4. En tirant les u1 et u2 du tableau Dual, et en les remplacant dans le

programme initial, verier que le tableau correspond reellemnt au prgramme D, et qu il
est optimal.
Les variables v1 , v2 et v3 sont des variables d'écarts du programme dual .
3.2.4 Interprétation Économique de la Dualité

La dualité joue un rôle particulièrement important en pratique. L'interprétation économique
de la dualité dépend évidement de la nature du programme primal.
Considérons le problème d'une entreprise qui met en oeuvre n diérentes activités en

faisant intervenir m ressources disponibles en quantités bi , i = 1, ..., m. A chaque activité
on associe un coût dépendant de son intensité. Ce problème se modélise comme suivant
max z = nj=1 cj xj
P
Pn
j=1 aij xj ≤ bi i = 1, ..., m
xj ≥ 0 j = 1, ..., n

cj est le prot unitaire de l'activité j,
xj est l'intensité de l'activité j,
bi représente la quantité de la ressource i consommée par les activités du problème
aij la quantité de la ressource i consommée par une unité de l'activité j.

Le programme dual correspondant est :
min w = m
P
i=1 bi ui
Pm
i=1 aij ui ≥ cj j = 1, ..., n
ui ≥ 0 j = 1, ..., m
Les variables duales représentent les contributions unitaires des ressources au prot f
(voir Exercice ). Autrement dit, la variable duale ui représente la variation de la fonction
objective en fonction de la disponibilité de la ressource i (bi ) . Elle est souvent appelée
coût marginal et représente la somme que nous sommes prêts à payer pour augmenter la
disponibilité de la ressource i . Ce qui explique la minimisation de la fonction objective
du dual qui représente le plus faible prix à payer pour augmenter la disponibilité des
ressources et par conséquent augmenter le prot . La contrainte j du dual signie que la
contribution au prot des ressources consommées par une unité de l'activité j doit être
au moins égale au prot unitaire de cette activité.
En particulier si une variable duale ui est nulle, le coût à payer pour l'augmentation
du disponible bi est nul ; ce qui est évident puisque le disponible n'est pas entièrement
consommé car la contrainte primale correspondante est inactive
max W = −V = −3y1 −5y2 Yb Cb b y1 y2 e1 e2

−y1 − 2y2 ≤ −3
e01 0 -3 -1 -2 1 0
−y1 − 1.25y2 ≤ −2.5
e02 0 -2.5 -1 -1.25 0 1
y1 ≥ 0 et y2 ≥ 0
4j 0 -3 -5 0 0
(3.12)
Tableaux Optimums non réalisables correspondent successivement aux points ( O' sur
GD et A' sur GD )
Yb Cb b y1 y2 e01 e02 Yb Cb b y1 y2 e01 e02

y20 -5 1.5 0.5 1 -0.5 0 y10 -5 2/3 0 1 -4/3 4/3
e02 0 -5/8 -3/8 0 -5/8 1 y20 -3 5/3 1 0 5/3 -8/3
4' j -7.5 -0.5 0 -2.5 0 4j -25/3 0 0 -5/3 -4/3
Le dernier Tableau Optimal non réalisable correspond a B' sur GD.
Les graphes représentant les solutions du primal (P) et du dual (D)
Le domaine réalisable est noté par DR pour les deux graphes.3.2

x2 y2
C
A’
B B’
DR
DR
x1 y1
O A O’
GP : Graphe du Primal GD : Graphe du Dual
Figure 3.2: Tableau du Primal et Dual
A Chaque tableau du Primal (P) correspond un tableau du dual (D)
Par changement de ligne en colonne, de colonne en ligne et par changement de signe , la

variable principale devient d'écart et la variable d'écart devient principale.
Notons que le changement de signe vient du fait que nous avons résolu le programme Dual
avec la maximisation. Par exemple Le tableau optimale réalisable de (D) correspondant
à B' s'obtient du tableau optimal de (P) correspondant à B.
2 2 5 5
y2 = correspond ∆2 = − et y1 = correspond ∆1 = −
3 3 3 3
4 4 5 5
x2 = correspond ∆02 = − et x1 = correspond ∆01 = −
3 3 3 3
Interprétation des variables duales :
La valeur de la variable duale correspond à l'importance accordée à la contrainte associée

du primale. Si cette valeur est nulle par exemple, cela signie que cette contrainte n'est
pas bloquante , non saturée, en d'autres termes l'augmentation du second membre de
cette contrainte n'est intéressante.
5
Considérons la solution optimale, et la variabley1 = 3 . La valeur 5000/3 DA (rappelons
que l'unité est le Millier de DA) correspond au coût (l'importance) que l'on peut payer
l'augmentation dune unité ( 1m3 ) la capacité du camion. C'est à dire si le coût d'amor-
tissement de la transformation de notre camion ( par exemple atteler une remorque) est
inférieur à 5000/3 DA par m3 il est alors intéressant de faire cette transformation.

3.3.3. Analyse Post Optimale et Sensitive A.Belahcene
Importante : ce coût marginal est une variation unitaire, c'est a dire pas forcément
valable pour une augmentation de plusieurs m3 par exemple. La solution optimale peut
alors changer (Voir la partie : programme linéaire paramétré).
Une autre façon de voir
un entrepreneur de construction de bâtiment pour un projet important doit-il acheter

un camion pour faire son propre transport ? ou louer un camion à chaque fois qu'il en a
besoin ?
Dans quelles limites de prix, il serait plus intéressant d'acheter un camion, par forcement
de même tonnage et capacité volume ?
3.3 Analyse Post Optimale et Sensitive
Les variables duales permettent donc d'établir un ordre de paramétrisation du second

membre des contraintes du primal. Autrement dit, en analyse post-optimale et sensitive
la priorité est donnée aux contraintes du primal dont les variables duales correspondantes
ont une valeur importante.
Dans les précédents paragraphes notre souci majeur était la recherche de solution op-
timale lorsqu'elle existe. En réalité, certaines valeurs utilisées lors de la formulation du
problème ne sont pas exactes. Il est d'un grand intérêt de savoir si la solution trouvée
reste optimale pour une variation de certaines valeurs du programme et de déterminer un
intervalle pour lequel cette solution reste optimale. Ces problèmes sont appelés "Analyse
sensitive" ou programmation paramètre. Un cas de problème intéressant en pratique est
l'étude de l'eet du changement des coecients de la fonction objective sur la solution.
Ce problème est aussi appelé " Analyse post-optimale".
Dans ce paragraphe, nous nous limitons aux changements dans le second membre des
contraintes et des coecients de la fonction objective. L'exemple 3.3 suivant illustrera ce
paragraphe :
Reprendre le programme linéaire (P.L. 1) :
max F = 2x1 + 3x2

0.25x1 + 0.5x2 ≤ 40
x ≥0 et x2 ≥ 0
0.4x1 + 0.2x2 ≤ 40 1
0.8x2 ≤ 40
Discuter l'eet sur la solution optimale et sur l'optimum, dun changement du problème
sur :
- prot unitaire du produit P1 de 2 à (2 + a).
- second membre de la deuxième contrainte : 0.4x1 + 0.2x2 ≤ 40 + b

3.3.1 Changement dans la fonction objective

Supposons que l'on change le coecient de la variable principale de base x de 2 à (2 +
a). La fonction objective s'écrit : F = (2 + a) x1 + 3 x2
A partir du système (3.5) les variables de base x1 et x2 s'écrivent en fonction des variables
hors base :x1 = 80 + 1.33e1 − 3.33e2
x2 = 40 − 2.67e1 − 1.67e2
Le remplacement de ces variables dans la fonction objective f donne :
F = (280 + 80a) + (−5.33 + 1.33a)e1 +(−1.67 − 3.33)e2
Le tableau du simplexe correspondant est :
Base b x1 x2 e1 e2 e3
x1 80 1 0 -1.3 3.33 0
e3 8 0 0 -2.33 1.33 1
x2 40 0 1 2.67 -1.67 0
4j -280-80a 0 0 -5.33+1.33a -1.67-3.33a 0
Cette solution reste optimale si et seulement si :
-5.33 + 1.33a≤0
-1.67 - 3.33a≤0
C'est la condition d'optima lité du tableau du simplexe, autrement dit, l'augmentation

de e1 ou de e2 fera diminuer la valeur de la fonction objective.
La résolution de ce système d'inéquations donne a ∈ [−0.5, 4]. Pour a dans cet intervalle
la solution optimale reste la même (x1 = 80, x2 = 40) mais la valeur de la fonction
objective (l'optimum) change et devient égale à 280 + 80 a.
Notons d'abord que pour a = 0, le tableau est optimal. Suivant les valeurs de a, la
variable e1 ou e2 rentre dans la base et la solution présente ne sera plus optimale. Nous
avons les résultats suivants :
−0.5 ≤ a ≤ 4 la solution actuelle est optimale et correspond au point C (cf. g 3.2).
a > 4 la variable e1 rentre dans la base et correspond au point D.
a ≤ −0.5 la variable e2 rentre dans la base mais la solution est optimale uniquement
pour a ≥ −2 ; il faut faire une autre itération pour le cas a < −2.

Nous donnons uniquement pour ce dernier cas le tableau obtenu, pour les autres le lecteur
est invité à faire les calculs et vérier nos résultats.
x1 60 1 0 4 0 -2.5
Pour a < −0.5 e2 6 0 0 -1.6 1 0.75
x2 50 0 1 0 0 1.25
4j -270-60a 0 0 -8-4a 0 1.25+2.5a
Le tableau n'est pas optimal si a < −2 , puisque le coecient de e1 est positif.
La variablee1 rentre dans la base et x1 en sort, on obtient le tableau suivant :
x1 150 0.25 0 1 0 -5/8
pour a < −2 e2 6 0.2 0 0 1 -0.25
x2 50 0 1 0 0 1.25
4j -150 2+a 0 0 0 -15
Ce tableau est optimal pour a < −2.

Récapitulatif :
Valeur de a −∞ 2 0.5 4 +∞
Variable entrant e2 e2 aucune e1
Variables de base e1 , e2 ,x2 x1 ,x2 , e2 x1 , x2 , e3 x1 , e1 , e3
Solution ( 0.50 ) ( 60.0 ) (80.40 ) ( 100.0 )
Valeur de Z 150 270 + 60 a 280+80a 200 + 100 a
3.3.2 Changement dans le second membre

Dans certains cas, on désire savoir comment change la solution optimale (valeur des
variables et de la fonction objective) quand le second membre du programme change. Ce
problème se ramène au cas précédent, lorsqu'on utilise le programme dual.
On sait, de la section précédente, que le second membre du primal devient la fonction

objective du dual. Au fait, ce n'est pas un deuxième cas que l'on étudie mais simplement
un autre problème pour le même cas. Le dernier tableau du simplexe du programme dual
est :
CB Base b u1 u2 u3 v1 v2
40 u1 5.33 1 0 2.13 1.33 -2.67
40 u2 1.67 0 1 -1.13 -3.33 1.67
4j -280 0 0 -8 -80 -40

Faisons la paramétrisation de la 2eme contrainte du problème initial primal :
0.4x1 + 0.2x2 ≤40 + b
Le coecient de u2 (variable associée a cette contrainte dans le dual) est donc −40 − b
(le signe est négatif à cause du problème de minimisation ramené à la maximisation).
Rappelons que les coûts réduits ∆j sont obtenus à partir des coecients de la fonction
objective par la transformation suivante ∆j = cj − CB Pj dans laquelle CB représente
les coecients des variables de base et Pj le vecteur colonne du tableau.
La dernière ligne du tableau peut être alors obtenue directement du tableau précédent :
−CB Base b u1 u2 u3 v1 v2
-40 u1 5.33 1 0 2.13 1.33 -2.67
-40 u2 1.67 0 1 -1.13 -3.33 1.67
4j -280-5/3b 0 0 -8-1.33b -80-3.33b -40+1.67b
La solution initiale reste optimale pour ∆j négatif, c'est-à-dire,
8 − 1.33b ≤ 0 ; − 80 − 3.33b ≤ 0 et − 40 + 1.67b ≤ 0 ,
Ce qui donne : −6 ≤ b ≤ 24 .
b ∈ [−6, 24] la solution précédente reste optimale, en d'autres termes pour la contrainte
2 variant de : 0.4x1 + 0.2x2 ≤ 34 à 0.4x1 + 0.2x2 ≤ 64.En dehors de ces valeurs le tableau
doit être changé.
b < −6 : La variable u3 rentre dans la base et la variable u1 en sort.
b > 24 : La variable v2 rentre et u2 sort.
De la même façon que pour le cas du primal, nous faisons les changements de tableau.
Regardons ce que devient le tableau précédant pour le cas b > 24, les autres cas sont
laissés au soin du lecteur, nous donnons cependant le tableau récapitulatif.
b > 24, ce cas correspond au second membre supérieur à 64, de la deuxième contrainte.
Après avoir fait entrer la variable v2 et sortir u2 on obtient le tableau optimal suivant :
CB Base b u1 u2 u3 v1 v2
-40 u1 8 1 8/5 0 1.33 0
0 u2 1 0 3/5 -4/5 -2 1
4j -320 0 24-b -40 -160 0

La solution primale correspondante est : x1 = 160 et x2 = 0 puisque ∆v1 = −x1 = −160

∆v2 = −2 x2 = 0
Récapitulatif :
Valeur de b −40 −30 −6 24 −→ ∞

Base du dual v1 , u2 u3 , u2 u1 , u2 u1 , v2
10
Sol. Primal x1 = 0 x1 = 2.5(30 + b) x1 = 80 + 3 b x1 = 160
x2 = 5(40 + b) x2 = 50 x2 = 40 − 53 b x2 = 0
5
Valeur de Z 600 + 15b 300 + 5b 280 + b 320
3
3.3.3 Interprétation graphique

Dans le cas de l'exemple 3.3, nous pouvons donner une interprétation géométrique à la
signication des variations du paramètre. La variation du coecient dans la fonction
objective revient à faire changer la pente de cette droite. La pente dans notre problème
est l'opposé du rapport des coecients de x1 et de x2 . Autrement dit
2+a
P =−
3
Quand cette pente est positive, l'optimum est le point A, ( donc pour a ≤ −2 ). Dans
le cas où elle est comprise entre les pentes de AB et BC, l'optimum est le point B, etc...
Notons que, lorsqu'elle est parallèle à une droite- contrainte, tous les points du segment
réalisable sont optimums.
La variation dans le second membre revient à déplacer parallèlement la droite contrainte.

Dans le cas de l'exemple , on déplacera parallèlement la droite contenant le segment
CD. Si on éloigne cette droite de l'origine, la contrainte devient inutile et redondante, les
points C et D sont alors confondus et loin de la contrainte. En d'autres termes, le point
optimum C glisse vers D. Ceci revient à augmenter la valeur du paramètre b, à partir b
= 24.
Inversement si b < 0 le point optimal C glisse vers B, puisque la droite contenant le

segment DC se déplace parallèlement vers l'origine, jusqu'à atteindre le point B avec la
valeur b = - 6.
Si b < -6 les point B et C (confondus) glissent vers A. Ce point est atteint pour b= -30,
si la valeur de b continue à diminuer, le point optimal se rapprochera de O.
Notons cependant que pour un problème économique, un coût négatif na pas de sens,
donc doit être supérieur ou égal à -2. De même, b doit être supérieur ou égal à - 40 car
la contrainte, qui dans la pratique, représente une capacité, ne peut être négative.

x2
A B
C
Fonct. Objective
2 ieme contrainte
D x1
Figure 3.3: Variation de la seconde contrainte de l'exemple3.3
3.4 Exercices
1. Donner les programmes duaux des programmes linéaires suivants :
3x1 −3x2 +7x3 Max 6x1 −3x2 +2x3 min

x1 +x2 +3x3 ≤ 40 x1 +3x2 +x3 ≥ 40
x1 +9x2 −7x3 ≥ 50 2x1 +3x2 +3x3 = 50
5x1 +3x2 = 20 4x1 +2x2 +x3 ≤ 20
5x2 +8x3 ≤ 100
x1 ≥ 0 x2 ≥ 0 x3 ∈ R x1 ∈ R x2 ≥ 0 x3 ≥ 0
2. Le directeur commercial d'une entreprise désire maximiser la couverture publicitaire
d'un de ses produits. Il a le choix entre un placard publicitaire dans un magazine
avec lequel il pourrait atteindre 10 millions de personne et un spot publicitaire où
il toucherait 20 millions de personnes. Le coût d'un placard publicitaire s'élève à
40,000 D.A et le coût d'un spot publicitaire à 75,000 D.A. Le directeur commercial
dispose d'une enveloppe de 2000,000 D.A et doit acheter au moins 20 placards
publicitaires dans un magazine.
Le problème est de savoir combien d'unités de chaque type de publicité acheter de
manière à maximiser la couverture commerciale de ce directeur
a) Modéliser ce problème.
b) Résoudre graphiquement ce problème.
c) Résoudre ce problème par l'algorithme du simplexe.
3. Résoudre ces programmes linéaires suivants :
−x1 +2x2 −3x3 max max −x3 −2x4 −x5 +11

x1 +x2 +x3 =6 x1 +x3 −x4 +2x5 = 2
−x1 +x2 +2x3 = 4 x2 −x3 +2x4 −x5 ≤ 50
+2x2 +3x3 = 10 4x1 +2x2 +x3 ≤ 20
x1 ≥ 0 x2 ≥ 0 x3 ≥ 0 xj ≥ 0 j = 1..5
4. Montrer, avec l'algorithme du simplexe,

que le programme suivant n'a pas de max F = x1 +x2

solution nie. Interpréter le coecient x1 −x2 ≤ 1
négatif dans la colonne de la variable −2 x1 +x2 ≤ 3
entrant dans la base. x1 , x2 ≥ 0
5. Montrer, en utilisant la méthode graphique, que ce programme linéaire possède une
innité de solutions.
x2
Le domaine convexe de ce programme

linéaire est donné par la gure.
(0.6) (2.6)
Les sommets B = (2.6) et C = (4.3)
sont solutions optimales. Donc toute
combinaison convexe de ces deux solu-
(4.3)
tions optimales est aussi optimale.
x1
droite de F
L'ensemble des solutions optimales est O = { (x1 , x2 ) | 3 x1 + 2 x2 = 18 . Le
lecteur est invité à montrer algébriquement ce résultat.
6. Soit le programme linéaire suivant :
max F = x1 + x2 + x3 + x4
a) Faire une analyse graphique
x1 + x2 ≤2
b) Utiliser le Simplex. Que Con- x3 + x4 ≤5
clure ? x1 , x2 , x3 ,x4 ≥0
a) Résoudre graphiquement ce programme linéaire. Que peut-on conclure ?
b) Résoudre par l'algorithme du simplexe ce programme. On donnera toutes les

solutions optimales de ce problème.
7. Soit le graphique suivant, donner le programme lineaire correspondant, son dual,

le tableau nal du primal et determiner le tableau optimal dual a partir du primal
8. Montrer par le simplex que le problème suivant est non-borné :
6x1 +2x2 +10x3 + 8x4 max

3x1 −3x2 2x3 + 8x4 ≤ 25
−5x1 +6x2 −4x3 − 4x4 ≤ 20
4x1 −2x2 +x3 + 3x4 ≤ 10
x1 ≥ 0 x2 ≥ 0 x3 ≥ 0 x4 ≥ 0
9. Etudier la nature des tableaux (optimalité, degenerescence, faisabilité, possibilité
d'amélioration etc ..., a1 variable articielle et M 0).

Base x1 x2 x3 e1 e2 e3 b Base x1 x2 x3 e1 e2 a1 b
x1 1 0 1.5 4 1 0 10 x1 1 0 3 2 -1 0 1
x2 0 1 2 1 -3 0 5 x2 0 1 2 1 -3 0 5
e3 0 0 3 0 2 1 7 a1 0 0 -1 0 0 1 4
∆ 0 0 -4.5 -13 0 0 ∆ 0 0 M-9 0 6 0
10. Etudier graphiquement le changement du coecient dans la fonction objective de

la variable X1 puis de la contrainte Une dans le programme suivant :
max X1 + X2 0 ≤ X1 ≤ 1 0 ≤ X2 ≤ 1
11. Soit le programme linéaire (P) avec son dernier tableau du simplexe :
max F = 3x1 + x2 − x3 Base b x1 x2 x3 e1 e2 e3

x1 6.5 1 0.75 0 0.5 0.25 0
x1 + x2 +2 x3 ≤10
x3 1.75 0 1/8 1 0.25 -1/8 0
2x1 +x2 −4x3 ≤6
e3 3.75 0 0.12 0 -0.75 -1/8 1
x1 +x2 + x3 ≤12
71
x1 , x2 , x3 ≥ 0 ∆ F = 0 -9/8 0 -1.25 -7/8 0
4
a) Donner le dual (D) de (P).
b) Donner le tableau optimal de (D)
c) Discuter l'eet d'un changement du coecient de la variable x2 dans la fonc-

tion objective de 1 à 1+α .
d) Nous remplacons la capacité de la contrainte 3 par 12+β , dans quelle limite la

solution actuelle reste optimale, et quelle est la valeur de la fonction objective
optimale.
12. Une entreprise fabrique 4 types de bureau. Chaque bureau est fabriqué dans l'ate-
lier 1 de menuiserie puis envoyé à l'atelier 2 pour les travaux de nition (peinture,
vernissage...). Le nombre d'heures de main-d'oeuvre dans chaque atelier et les prof-
its unitaires sont donnés dans le tableau :
Bureau 1 2 3 4
La disponibilité en heures de main-
Atelier 1 4 9 7 10
d'oeuvre pour l'atelier 1 est de 6000 h.
Atelier 2 1 1 3 40
Elle est de 4000 h pour l'atelier 2.
Prot 12 20 18 40
a) Formuler ce problème comme un programme linéaire P.
b) Soit xi le nombre de bureaux du type i que l'on doit fabriquer. Le dernier

tableau du simplexe est :
Base x1 x2 x3 x4 e1 e2 b
4 −1 4000
x1 1 2.3 1.6 0
15 15 3
1 1 1 2 200
x4 0 − 30 30 1 − 150 75 3
20 10 44 4 56000
∆ 0 − − 0 − − f=
3 3 15 15 3

où e1 et e2 sont des variables d'écarts.
Donner le plan de production optimale pour cette entreprise.
c) Écrire le programme dual associé au programme primal P. En déduire son

dernier tableau du simplexe ainsi que la solution optimale du dual. Donner
une interprétation économique du dual.
d) Le directeur de cette entreprise décide d'augmenter la capacité maximale de

l'atelier 1 d'une quantité α. Pour quelles valeurs de α la solution optimale
trouvée reste-t-elle optimale ?
e) Le directeur envisage la possibilité d'augmenter son prot de 400 unités.

Quelles sont les changements à opérer sur les capacités des deux ateliers pour
atteindre cet objectif ?
Le plan de production optimal
Bureau 1 2 3 4
f ) trouvé serait-il aecté pour les prof-
prot 10 22 20 38
its unitaires suivants :
Problème 3.4.1. Soit le domaine denie par le triangle (OAB) sur la gure.
1. Donner le programme linéaire correspondant.
2. Donner la solution optimale par le simplexe et préciser le point sur le graphe.
3. Donner le programme dual et son graphe.
4. Donner la solution optimale duale a partir de l'optimal dual.
5. On fait deplacer la contrainte droite OB, Donner les solutions correspondantes.

4 Problème du Transport
Nous allons étudier dans ce chapitre un problème combinatoire, à savoir le problème de
transport.. Nous verrons aussi que ce problème peut être formulé comme un problème
de programmation linéaire. En raison de sa structure particulière , il est plus facile et
surtout plus rapide d'utiliser d'autres méthodes de résolution que celle du simplexe.
4.1 Position du problème et modélisation
Soit r = (X, U, c) un réseau dit de transport où :

l'ensemble X est partitionné en deux sous-ensembles disjoints X1 et X2 :
X = X1 ∪ X2 et X1 ∩X2 =
l'application C : U → R+
C(u) représente le coût de l'arc u ou encore le coût de transport d'une matière du sommet
i au sommet j avec u = (i, j).
Soient X1 = {x1 , x2 , ..., xm }
X2 = {y1 , y2 , ..., yn }. On désignera par origine un sommet
et
de X1 et destination un sommet X2 . Supposons qu'une matière est disponible au niveau
de chaque sommet origine xi en quantité ai ;i = 1, m . Une demande bj j = 1, n est
formulée par chaque sommet destination yj .
Le problème de transport consiste à transporter une matière des m origines pour couvrir
la demande des n destinations en respectant les contraintes suivantes :
Disponibilité de la matière en chacune des origines.
Satisfaction d'une demande en chacune des destinations.
L'objectif étant, bien entendu, la minimisation du coût global de transport sur tout le
réseau. Si on désigne par xij la quantité acheminée de l'origine i à la destination j. Ce
problème se modélise comme suit :
min f = m
P Pn
i=1 j=1 cij xij
Pm
i=1 xij ≥ bj j = 1, ..., n
Pn
j=1 xij ≤ ai i = 1, ..., m
xij ≥ 0
53
4.4.1. Position du problème et modélisation A.Belahcene
Ce problème est un problème de programmation linéaire. En raison du nombre de vari-

ables et du nombre de contraintes, souvent très grand, la résolution par les méthodes
de programmation linéaire classiques devient impossible de par l'espace-mémoire qu'il
occupe et du temps d'exécution trop élevé. Ce problème est, pour les raisons que nous
venons d'exposer, dit combinatoire et nécessite des méthodes particulières pour sa réso-
lution. Le programme dual associé au programme primal précédent est :
Le problème de transport
Pm Pn
max W = i=1 ai ui + j=1 bj vj
ui + vj ≤ cij ∀i, j
ui , vj ≥0 ∀i, j
Les variables ui et vj seront dites respectivement coût d'envoi et coût de réception. Ces
variables sont ctives mais joueront un rôle important dans les prochaines considérations.
Remarques : P P
Dans le cas où ai > bj , on crée une destination ctive, yn+1 et on rajoute un arc
de coût inni entre chaque sommet de
P P X1 et yn+1 .
Lorsque ai < bj , on crée une origine ctive xm+1 et rajoute un arc de coût inni
entre xm+1 et chaque sommet de X2 .
Exemple 4.1.1. Une entreprise fabrique et vend un produit alimentaire possède deux
(2) ateliers de fabrication et trois (3) dépôts pour stocker le produit ni. La production
journalière dans chaque atelier est respectivement de 400 et 500 caisses.
La demande journalière est la même

Atelier/Dépot D1 D2 D3
pour chaque dépôt et est estimée à
A1 2.5 1.7 1.8
300 caisses. Les coûts de transport
A2 2.8 1.8 1.4
sont donnés comme suit :
La demande journalière est la même pour chaque dépôt et est estimée à 300 caisses. Les
coûts sont donnés en milliers de dinars. Le problème est d'établir un plan de transport
du produit des deux ateliers aux trois dépôts qui minimise le coût total de transport.
La résolution du problème de transport par ces méthodes se fait en deux phases. On

commence par déterminer une solution de base réalisable et ensuite on l'améliore en
utilisant une méthode basée sur le théorème des écarts complémentaires. Nous allons
présenter des méthodes de résolution de ce problème. Ces méthodes seront illustrées par
l'exemple.

4.4.2. Recherche d'une solution de base réalisable A.Belahcene
4.2 Recherche d'une solution de base réalisable
Il existe plusieurs méthodes qui permettent de déterminer une solution de base réalisable.
Les principales méthodes sont : Ballas-Hammer, la méthode du coin "Nord-Ouest", la
méthode du minimum en ligne. Parmi toutes les méthodes existantes celle de Ballas-
Hammer est la plus utilisée car la solution de base réalisable oerte par cette méthode
est proche de la solution optimale. Dans certaines situations, cette solution de base
réalisable est optimale.
Nous allons exposer la principale méthode à savoir celle de Ballas-Hammer. Elle est basée
sur la notion de regret.
On commence par calculer pour chaque rangée de la matrice coût, la diérence entre
le plus petit élément avec l'élément immédiatement supérieur (ou égal) dans la même
rangée. On choisit parmi les diérences obtenues, tant en ligne qu'en colonne, celle qui
est la plus grande. Deux cas peuvent se présenter :
1. La ligne i a la plus grande diérence, alors on attribue à la case (i,k) possédant

un coût minimum sur cette ligne, une quantité ϕ(i, k) égale au minimum entre la
disponibilité ai et la demande bk , c'est-à-dire, ϕ(i, k) = min{ai , bk } et on raye la
ligne ou la colonne comportant cette valeur.
2. La colonne j a la plus grande diérence, alors on attribue à la case (k, j) ayant un

coût minimum sur cette colonne, une quantité ϕ(k, j) = min{ak , bj } et on raye la
ligne ou la colonne comportant cette valeur.
Puis, on met à jour les disponibilités ou les demandes en retranchant le minimum

précédemment trouvé à la ligne ou la colonne non rayée.
On recommence cette procédure jusqu'à l'obtention d'une matrice à deux éléments. Les
deux relations restantes sont retenues automatiquement. On calcule ensuite le coût total
de cette solution.
Utilisons la méthode de Ballas-Hammer pour obtenir une solution de base réalisable du

problème de l'exemple.
Calcul des regrets de la matrice des coûts

D1 D2 D3 aj ∆j
A1 2.5 1.7 1.8 400 0.1
A2 2.8 1.8 1.4 500 0.4
bj 300 300 300 900
∆j 0.3 0.1 0.4
L'écart maximal est égal à 0.4, il est atteint par la ligne correspondant à l'atelier A2 . Le
minimum des coûts sur cette ligne est 1.4. On aecte alors à la case (A2 , D3 ) la quantité
300 car
ϕ(A2 , D3 ) = min(300, 500) = 300

4.4.2. Recherche d'une solution de base réalisable A.Belahcene
A2 −→ D3
Le coût de cette transaction s'élève à : 300 * 1.4 = 420
Le dépôt D3 étant entièrement satisfait par l'atelier A2 . La disponibilité dans cet atelier
devient alors a2 = 500 − 300 = 200. On raye la colonne D3 et on obtient la nouvelle
matrice (voir table4.2)
Calcul des regrets de la nouvelle matrice

D1 D2 aj ∆j
A1 2.5 1.7 400 0.8
A2 2.8 1.8 200 1
bj 300 300 600
∆j 0.3 0.1
L'écart maximal est égal à 1, il est atteint par la ligne correspondant à l'atelier A2 . Le
minimum des coûts sur cette ligne est 1.8. On aecte alors à la case (A2 , D3 ) la quantité
200 car :
ϕ(A2 , D2 ) = min{300, 200} = 300
A2 −→ D2
Le coût de cette transaction est : 200 * 1.8 = 360.
Le dépôt D2 étant partiellement satisfait alors que l'atelier A2 est pourvu du produit.
La disponibilité dans cet atelier devient alors a2 = 500 − 300 = 200. On raye la ligne A2
et on obtient la nouvelle matrice (voir table4.2 :)
Matrice nale obtenue

D1 D2 aj
A1 2.5 1.7 400
bj 300 100 400
Cette table contient deux éléments, on retient les relations qui restent, à savoir :
Le dépôt D1 sera alimenté par l'atelier A1 , ϕ(A1 , D1 ) = 300
Le dépôt D2 sera complété par A1 , ϕ(A1 , D2 ) = 100
Le coût de cette transaction est de 100 ∗ 1.7 + 300 ∗ 2.5 = 920.
En résumé, la solution de base réalisable obtenue par la méthode Ballas-Hammer, de

coût total égal à 920 + 360 + 420 = 1700, est :
A2 −→ D3 , A2 −→ D2 , A1 −→ D1 , A1 −→ D2
Le dépôt D1 est alimenté par A2 , D2 par les ateliers A1 et A2 et D3 parA2 .

4.4.3. Amélioration de la solution A.Belahcene
4.3 Amélioration de la solution
Considérons les deux premiers problèmes duaux donnés précédemment. En utilisant le

théorème des écarts complémentaires, on tire, à l'optimum, les conclusions suivantes :
Si Xij > 0, c'est-à-dire que cette variable est de base, alors la variable d'écart associée à
la contrainte du dual est nulle. En d'autres termes : ui + vj = cij
Si Xij = 0, cette variable étant hors-base, alors la variable associée à la contrainte
correspondante du dual est positive, c'est-à-dire, ui + vj < cij
Les conditions 4.3 et 4.3 dénissent un critère d'optimalité d'une solution de base réal-
isable. En d'autres termes, une solution de base réalisable est optimale si le coût de
transport, pour les cases représentant les variables hors-base, est supérieur à la somme
des deux coûts.
La vérication commence par supposer que, pour les cellules représentant les variables
de base, le coût de transport est égal à la somme du coût d'envoi et du coût de réception.
On xe arbitrairement un de ces deux coûts égal à 0, soit l'un des coûts d'envoi puis on
évalue les autres en ne considérant que les cellules des variables de base. Par exemple le
tableau 4.1, la variable X12 = 100 est dans la base ( puisque positive), on choisit par
exemple u1 = 0, donc on calcule le reste, v2 = 1.7, car c12 = u1 + v2 = 1.7, puis les autres
valeurs ui et vj , ainsi v1 = 2.5, v3 = 1.8 et u2 = 0.1.
Dans le cas de l'exemple 4.1, on obtient :
D1 D2 D3 aj
uj
A1 300 100 400
2.5 1.7 1.8 0
A2 200 300 500
2.8 1.8 1.4 0.1
bj 300 300 300
vj 2.5 1.7 1.3
Table 4.1: Amélioration de la solution
On notera que le chire gras donné en haut à gauche d'une cellule représente la valeur de
la variable de base qui est la quantité à transporter. Par contre le chire en bas à droite
de cette cellule est le coût de transport. La dernière colonne (ligne) de cette matrice
résume la disponibilité (demande) en haut et le coût d'envoi (coût de réception) en bas
de chaque cellule.
On remarque que le critère d'optimalité est vérié car pour les cellules des variables hors-
base, à savoir (A1 , D3 ) et (A2 , D1 ), la condition ui + vj < cij est vériée. La solution de
base réalisable oerte par Ballas-Hammer, dans cet exemple, est optimale.

4.4.4. Série d'exercices A.Belahcene
Dans le cas où nous avons plusieurs cellules des variables hors-base ne vériant pas le
critère d'optimalité alors on ramène dans la base la cellule ayant la plus grande diérence,
en valeur absolue, entre le coût de transport et la somme des coûts d'envoi et de réception.
On augmente d'une quantité α cette cellule puis on observe l'eet d'un tel changement
sur les autres variables de base. Ces changements successifs doivent décrire un cycle, qui
commence et se termine par cette cellule hors-base, et dont les sommets sont des variables
de base.
Exemple 4.2 Supposer que l'atelier A1 alimente le dépôt D1 d'une quantité égale à 100
caisses et le dépôt D2 d'une quantité égale à 300 caisses. Par contre, l'atelier A2 alimente
les dépôts D1 et D3 d'une quantité respectivement égale à 200 et 300 caisses. Optimiser
cette solution de base réalisable en utilisant la procédure décrite ci-haut.
Reportons cette solution de base réalisable sur le tableau de transport et calculons les
diérents coûts :
D1 D2 D3 aj
uj
A1 100 300 400
2.5 1.7 1.8
A2 200 300 500
2.8 1.8 1.4 0
bj 300 300 300 900
vj 2.5 1.1
Table 4.2: Solution Réalisable de l exemple
La cellule hors-base (A2 , D2 ) ne vérie pas le critère d'optimalité car son coût de transport
(1.8) est inférieur à la somme de son coût d'envoi ( 0.3) et de son coût de réception (1.7)
qui est de (2.0). Cette cellule est donc candidate à entrer en base. La quantité à aecter
à cette cellule est obtenue par le cycle suivant4.1 :
La quantité maximale que peut prendre α est 200 ; sinon la solution ne serait plus réal-
isable. La nouvelle solution est :
Le critère d'optimalité étant vérié, donc elle est optimale.
4.4 Série d'exercices
1. Vérier que cette solution est réalisable ? Vérier si elle optimale ? Si non, déter-
miner la solution optimale ?

100 + a 300 − a
200 − a a
Figure 4.1: Représentation d un Cycle
D1 D2 D3 ai
uij
A1 300 100 400
2.5 1.7 1.8 0
A2 200 300 500
2.8 1.8 1.4 0.3
bj 300 300 300 900
vj 2.5 1.7 1.1
Table 4.3: Amélioration de la solution exemple 4.3
A B C D Ore
Le tableau suivant ré-
D1 4 6 6 2 18
sume les informations con-
21 36 43 20
cernant un problème de
D2 5 5
transport de 3 dépôts à 4
60 30 50 43
clients. Dans ce tableau on
D3 7 7
trouvera aussi une solution
18 10 48 72
à ce problème.
Dem 4 18 6 2 30
2. Suite aux récentes restrictions sur ses importations, une usine métallurgique peut
disposer des quantités maximales de minerais A, B, C, D et E respectivement égales
à 150t, 100t, 75t, 250t et 200t.
Quatre fournisseurs étrangers peuvent ex-
Minerais
porter, dans le cadre de la réglementation
A B C D E
de leurs pays, les quantités totales respec-
Four 1 2 3 2 4 1
tivement égales à 300t, 250t, 150t et 200t.
nis- 2 3 4 1 2 4
Les teneurs en métal des diérents minerais
seur 3 2 3 4 1 2
de chacun des fournisseurs sont données par
4 3 4 2 3 2
la table suivante :
On vous demande d'établir le programme de commande de manière à maximiser la

teneur contenue dans les minerais achetés.
3. Une importante société de verrerie dispose de quatre usines et de 5 points de ventes.

La demande pour le prochain mois au niveau de chaque point de vente et La
production mensuelle au niveau de chaque usine sont comme suit :
Point de vente P1 P2 P3 P4 P5 Usine U1 U2 U3 U4

Demande 75 20 15 25 40 Production 60 75 80 35
P1 P2 P3 P4 P5
Les coûts de transports entre les usines
U1 8 25 17 14 9
et les points de ventes sont donnés par la
U2 8 5 10 2 10
table suivante. Etablir le plan de trans-
U3 7 21 18 14 10
port qui minimise le coût total.
U4 23 9 12 18 25
4. Une rôtisserie possède 4 comptoirs de livraison dans une importante ville dont les
capacités de livraison sont respectivement de 150, 100, 80 et 140 repas par jour.
Cette ville est divisée en 6 secteurs : Est, Ouest, Nord, Sud, Centre et Banlieue.
Le nombre moyen de commande de chaque secteur est respectivement de 75, 50,
75, 125, 50 et 25 repas par jour. Les coûts unitaires de livraison des comptoirs aux
régions sont :
Est Ouest Nord Sud Centre Banlieue

C1 0.16 0.10 0.17 0.10 0.11 0.25
C2 0.06 0.15 0.08 0.22 0.16 0.23
C3 0.32 0.32 0.22 0.18 0.11 0.08
C4 0.22 0.26 0.09 0.21 0.10 0.10
Donner le plan de livraison optimal.

PolyRo IAP

Transféré par

Droits d'auteur :

Formats disponibles

PolyRo IAP

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

PolyRo IAP

Transféré par

Droits d'auteur :

Formats disponibles

Recherche Opérationnelle

Depuis l'avènement de la révolution industrielle, le monde a connu une remarquable

La Recherche Opérationnelle ne se restreint pas uniquement aux problèmes dont les

La Recherche Opérationnelle (R.O) contribue à la résolution d'un problème, en analysant

Figure 1.1: Principe de la Modélisation

1.2 Méthodologie de Résolution

La méthodologie que nous proposons et une procédure systématique de résolution de

1.3 Analyse du Système

Une mauvaise analyse du système inue considérablement sur sa structuration.

1.3.1 Types de contraintes

Contrainte technologique Les diérentes opérations nécessaires au processus de fabri-

23 avril 2012 Page 4 de 60

Contrainte organisationnelle : La structure hiérarchique d'une organisation.

1.3.2 Types d'objectifs

On peut aussi avoir plusieurs objectifs en parallèle, ce qui un problème Multi-critère.

Il existe des situations ou le système en question possède un objectif, facilement identi-

La construction d'un modèle passe par plusieurs à savoir :

Recueil et Analyse des données, construction de modèle et sa validation gure 1.2. La

23 avril 2012 Page 5 de 60

Figure 1.2: Schématisation de la Modélisation

Importance Il s'agit de savoir si l'information disponible est la plus signicative.

1.4.2 Construction d'un modèle

Description Le modèle doit bien décrire les facteurs principaux du système.

23 avril 2012 Page 6 de 60

Un modèle pour la prise de décision s'écrit sous la forme suivante :

La phase suivante est la modélisation Identiant les facteurs contrôlables et non-contrôlables

Le premier type de facteur représente les variables de décision, x1 et x2 . Elles signient

23 avril 2012 Page 7 de 60

Min Z = 250x1 + 220x2

Ci-aptès le modèle pour l'entreprise. min Z = 250x1 + 220x2

1.4.3 Validation d'un modèle

Un modèle est valide par comparaison a la réalité. L'approche est de le comparer, en

23 avril 2012 Page 8 de 60

Parmi les questions que l'on doit considérer :

2. Est-ce qu'une relation quelconque du modèle correspond a une certaine théorie ?

D'autres questions pourraient être examinées avec collaboration des décideurs.

1.5 Recherche de Solutions et Mise en Oeuvre

La recherche de solution d'un problème donné se fait de plusieurs manières :

23 avril 2012 Page 9 de 60

La dernière phase du cheminement d'un problème de recherche Opérationnelle consiste

Souvent l'implémentassions sert de FeedBack, ou de retour en arrière , aux étapes

1.6 Étude de Cas

1.6.1 Position du problème

Le propriétaire voudrait connaître les avantages et risques de cette acquisition. Il a à sa

On suppose que les coûts d'entretien et de fonctionnement sont évalués respectivement

2. Tous les coûts rapportés dans ce cas sont en milliers de DA

23 avril 2012 Page 10 de 60

Site Population Revenu Vente 1 Vente 2

Didouche Mourad 7 000

Krim Belkacem 9 000 120 2 000 3 000

Med Boudiaf 12 000 80 3 000 4 000

Ben M'hidi 5 000 350 1 500 2 500

Fadma Nsoumer 6 000 160 2 300 1 900

Ali la Pointe 10 000 100 2 400 1 950

H. BenBouali 5 000 400 2 800 3 000

Amirouche 8 000 100 2 500 2 000

Abane Ramdane 15 000 150 4 000 2 700

Zighout Youcef 7 500 250 1 800 2 300

Table 1.1: Statistique d'Investissement

Une mauvaise analyse du système inue considérablement sur sa structuration.

Contrainte technologique Les diérentes opérations nécessaires au processus de fabri-

Recueil et Analyse des données, construction de modèle et sa validation gure 1.2. La

Importance Il s'agit de savoir si l'information disponible est la plus signicative.

La phase suivante est la modélisation Identiant les facteurs contrôlables et non-contrôlables

Le premier type de facteur représente les variables de décision, x1 et x2 . Elles signient

Souvent l'implémentassions sert de FeedBack, ou de retour en arrière , aux étapes

Les coûts d'entretien et de fonctionnement sont à déduire du prot. En outre la contrainte

3. Une compagnie vend 2 types de lubriants pour machines à turbines. Le premier

a) La quantité de l'additif contenue dans un produit ni est la moyenne volumétrique

Lubrif. A1 A2 Ore Coût

5. voir solution du chier Ch1_ex4.lp

Ce problème contient un objectif, à savoir la maximisation du prot total. Les contraintes

C est le vecteur des coecients dans la fonction objective C = (c , ..., cn ) , X est le

1. la droite elle-même : ensemble des couples de points (x1 , x2 ) vériant l'équation :

La droite D0 est au fait un faisceau de droites parallèles. Le déplacement de cette

On voit donc facilement la solution optimale, le dernier point du domaine réalisable en

1. On verra plus tard pour la justication algébrique

CB , C N Coecients de ces variables dans la fonction objective, respectivement des vari-

AB , A N Matrice des coecients des contraintes scindée en colonnes des variables de

Yj = CB .Pj est le produit scalaire des vecteurs colonnes Pj et CB . Il représente l'inuence