Le simplexe

LE SIMPLEXE

I - EXEMPLE :
Forme canonique
2x+y≤800
x+2y≤700
yœ300

Forme standard
2x+y+e1=800
x+2y+e2=700
y+e3=300

Il y a autant de variables d'écart que d'inéquations

Fonction économique à maximiser :
30000x+40000y

Variable entrante = coef>0 de la fonction objectif le plus grand (40M)
Variable sortante = plus petit dernier terme/coefficient colonne (700/2)

Transformation de la matrice :
Pivot = intersection variable entrante et sortante
Dans la colonne du pivot : on met un 1 à la place du pivot et un 0 ailleurs
Sur la ligne du pivot : on garde les mêmes coefficients
Calcul des autres coefficients : coef-(coef ligne pivot*coef colonne pivot)/pivot

On a atteint la solution optimale lorsque tous les coefficients sont négatifs ou nuls

Donc solution optimale : x=100 y=300
30mx+40my=15M
e1 non saturé 
e2 et e3 saturés (=0) car hors base



II - TRANSFORMATION D'UN PROGRAMME PRIMAL EN DUAL

PRIMAL
A 18x+18y≥9000
B 6x+24y≥6000
C 20x+6y≥7200
x et y≥0
MIN : 1200x+1000y


DUAL
18a+6b+20c≤1200
18a+24b+6c≤1000
MAX : 9000a+6000b+7200c



III - PROCESSUS DE RESOLUTION

1) Formalisation du problème sous forme canonique
Les contraintes sont exprimées sous forme d'inéquations


2) Passage à la forme standard
Les inéquations sont remplacées par des équations et on introduit des variables d'écart


3) Résolution du pb
Si nb variables ≤ 3 ® résolution graphique ou algébrique
Si nb variables > 3 ® résolution par le simplexe


4) Détermination de la sol de départ


5) Détermination de la sol optimale
Dans le cas de la maximisation, les coefficients de la fonction sont tous négatifs, les variables hors base sont négatives et les variables en base sont nulles
Dans le cas de la minimisation, les coefficients de la fonction sont tous positifs, les variables hors base sont positives et les variables en base sont nulles

OUTGDA Mektar