Programmation Lineaire

Forme standard et forme canonique d’un programme linéaire
Forme canonique
Définition :
Un programme linéaire est sous forme canonique lorsque toutes ses contraintes
sont des inégalités (inférieur ou égal), toutes ses variables sont positives et la
fonction objective est toujours à maximiser.
Forme canonique d’un programme linéaire :
a11 x1 + a12 x2 +……….......+a1n xn ≤ b1

a21 x1 + a22 x2 +……….......+a2n xn ≤ b2
am1 x1 + am2 x2 +……….......+amn xn ≤ bm
x1 ≥ 0 ; x2 ≥ 0; ..................................... ; xn ≥ 0
Max z=c1 x1 + c2 x2 + ……………….+ cn xn
Forme standard
Définition :
Un programme linéaire est sous forme standard lorsque toutes ses contraintes
sont des égalités, toutes ses variables sont positives et la fonction objective est
toujours à maximiser.
Forme standard d’un programme linéaire :
a11 x1 + a12 x2 +……….......+a1n xn ¿ b 1

a21 x1 + a22 x2 +……….......+a2n xn ¿ b 2
am1 x1 + am2 x2 +……….......+amn xn ¿ b m
x1 ≥ 0 ; x2 ≥ 0; ..................................... ; xn ≥ 0
Max z=c1 x1 + c2 x2 + ……………….+ cn xn
Résolution de programmes linéaires
Résolution graphique
Dualité
La dualité est une notion essentielle en programmation linéaire. A un programme
linéaire donné que nous appelons primal, l’opération de dualité associe un autre
programme linéaire dit son dual, qui ne sera défini qu’à l’aide des seules données
du primal.
La dualité présente un double intérêt :
 D’une part, le programme dual à une interprétation économique
importante :il constitue une autre vision du programme initial
primal .En particulier, la dualité permet de montrer qu’un problème
d’allocation optimale des ressources rares est aussi un problème de
tarification optimale de ces ressources ;
 D’autre part, les propriétés liant le programme primal et son dual
permettront de résoudre des problèmes de minimisation en termes
de maximisation, ce qui est souvent plus facile, et développer de
nouveaux algorithmes qui se révéleront plus performants dans un
grand nombre de situations.
Caractéristiques :
La dualité est caractérisée par les règles suivantes :
 Le sens de l’optimisation est inversé. La maximisation(respectivement

minimisation ) dans le primal devient une minimisation(respectivement
maximisation ) dans le dual ;
 Les coefficients de la fonction économique du primal deviennent les
seconds membres des contraintes duales ; les seconds membres des
contraintes primales deviennent les coefficients de la fonction économique
du dual ;
 Les signes dans les inégalités des contraintes ou dans la contrainte de
positivité des variables de décision suivent des règles précises de
transformation ;
 Comme le problème dual du dual est le problème primal initial, il convient
donc de parler d’une paire de problèmes de programmation linéaire liés par
la dualité
Règle de dualisation:
Maximisation Minimisation
Nombre de contraintes Nombre de variables
Nombre de variables Nombre de contraintes
Type des contraintes Type des variables principales
= quelconque
≤ >0
> ≤0
Type des variables de décision Type des contraintes
quelconque =
>0 >
<0 <
Théorème des écarts complémentaires :
Comment retrouver une solution d’un problème avec la solution de l’autre ?

Notons x* la solution optimale du primal et y* la solution optimale du dual.
 Si x*j > 0, alors la j-ième contrainte du dual est saturée .
 Si la j-ième contrainte du dual n’est pas saturée, alors x* j = 0
 Si y*i > 0, alors la i-ième contrainte du primal est saturée.
 Si la i-ième contrainte du primal n’est pas saturée, alors y* i = 0
Exercice d’application :
On considère le PL primal (P) suivant :
Min z =2x 1 + 5x2 + 3x3
x1 ≥ 10
x2 ≥ 15
(P) x1 + 2 x2 + x3≥ 60
2x1 + x2 + 2x3≥ 95
x1 ≥ 0 , x2 ≥ 0 , x 3≥ 0
1 .Donner (D) le dual du programme (P)
2. Résoudre (D) par l’algorithme du simplexe
3. Déduire la solution optimale du programme primal (P)
Implémentation

Programmation Lineaire

Transféré par

Droits d'auteur :

Formats disponibles

Programmation Lineaire

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

Programmation Lineaire

Transféré par

Droits d'auteur :

Formats disponibles

Forme standard et forme canonique d’un programme linéaire

Forme canonique d’un programme linéaire :

a11 x1 + a12 x2 +……….......+a1n xn ≤ b1

am1 x1 + am2 x2 +……….......+amn xn ≤ bm

Forme standard d’un programme linéaire :

a11 x1 + a12 x2 +……….......+a1n xn ¿ b 1

am1 x1 + am2 x2 +……….......+amn xn ¿ b m

 Le sens de l’optimisation est inversé. La maximisation(respectivement

Théorème des écarts complémentaires :

Comment retrouver une solution d’un problème avec la solution de l’autre ?

Vous aimerez peut-être aussi