14/02/2018 Projet de
recherche
opérationnelle
Programme linéaire primal et dual
associés
Membre du groupe :
1-Guibinga dann yannick / 20170340
L3D-S5DA
Table des matières
1. Introduction ..................................................................................................................................... 2
2. Programme linéaire et dualité .......................................................................................................... 2
2.1 Définition et présentation ........................................................................................................ 2
2.2 Propriétés et signification économique du programme dual .......... Error! Bookmark not defined.
2.2 Tableau de correspondance primal-dual ........................................ Error! Bookmark not defined.
3. Conclusion ......................................................................................... Error! Bookmark not defined.
1
1. Introduction
La recherche opérationnelle (aussi appelée aide à la décision) peut être définie
Comme l’ensemble des méthodes et techniques rationnelles orientées vers la
Recherche de la meilleure façon d’opérer des choix en vue d’aboutit au résultat
Visé ou au meilleur résultat visé ou au meilleur résultat possible. Elle fait partie des
« Aides à la décision » dans la mesure où elle propose des modèles conceptuels en
Vu d’analyse et de maitriser des situations complexes pour permettre aux décideurs
De comprendre et d’évaluer les enjeux et d’abriter ou de faire le choix plus
Efficaces. Le domaine fait largement appel au raisonnement mathématique (logique,
Probabilités, analyse de données) et à la modélisation des processus. Il est fortement
Lié à l’ingénierie des systèmes, ainsi au management du système d’information
2. Programme linéaire et dualité
2.1 Définition et présentation
La forme d’un programme linéaire de type maximisation est
Max z ct x
S.C Ax b PL1
x0
avec x, b , c des vecteurs de dimensions respectives n, m et n , et A une matrice de dimension
m, n
On appelle programme dual de PL1 , le programme linéaire suivant :
Min w bt y
S.C t
A.Y c
y0
avec y un vecteur de dimension m et t A la transposée de la matrice A .
Le programme PL1 est appelé programme Primal.
Pour passer du primal au dual, on remarque que :
a ) Les termes du second membre deviennent les coefficients de la fonction objectif et
réciproquement.
b ) Le problème de maximisation devient un problème de minimisation.
c ) Les inégalités " " deviennent des inégalités " "
2
d ) La matrice A se transforme en sa transposée.
Exemple : Le programme primal (problème de l’agriculteur) est
Max z 100x1 200x2
S.C x1 x2 150
4x1 2x2 440
x1 4x2 480
x1 90
x1 0 , x2 0
Donc le programme dual est
Min w 150 y1 440 y 2 480 y3 90 y 4
S.C y1 4 y 2 y3 y 4 100
y1 2 y 2 4 y3 200
y1 0 , y2 0
